1 | /* |
2 | * linux/fs/befs/btree.c |
3 | * |
4 | * Copyright (C) 2001-2002 Will Dyson <will_dyson@pobox.com> |
5 | * |
6 | * Licensed under the GNU GPL. See the file COPYING for details. |
7 | * |
8 | * 2002-02-05: Sergey S. Kostyliov added binary search within |
9 | * btree nodes. |
10 | * |
11 | * Many thanks to: |
12 | * |
13 | * Dominic Giampaolo, author of "Practical File System |
14 | * Design with the Be File System", for such a helpful book. |
15 | * |
16 | * Marcus J. Ranum, author of the b+tree package in |
17 | * comp.sources.misc volume 10. This code is not copied from that |
18 | * work, but it is partially based on it. |
19 | * |
20 | * Makoto Kato, author of the original BeFS for linux filesystem |
21 | * driver. |
22 | */ |
23 | |
24 | #include <linux/kernel.h> |
25 | #include <linux/string.h> |
26 | #include <linux/slab.h> |
27 | #include <linux/mm.h> |
28 | #include <linux/buffer_head.h> |
29 | |
30 | #include "befs.h" |
31 | #include "btree.h" |
32 | #include "datastream.h" |
33 | |
34 | /* |
35 | * The btree functions in this file are built on top of the |
36 | * datastream.c interface, which is in turn built on top of the |
37 | * io.c interface. |
38 | */ |
39 | |
40 | /* Befs B+tree structure: |
41 | * |
42 | * The first thing in the tree is the tree superblock. It tells you |
43 | * all kinds of useful things about the tree, like where the rootnode |
44 | * is located, and the size of the nodes (always 1024 with current version |
45 | * of BeOS). |
46 | * |
47 | * The rest of the tree consists of a series of nodes. Nodes contain a header |
48 | * (struct befs_btree_nodehead), the packed key data, an array of shorts |
49 | * containing the ending offsets for each of the keys, and an array of |
50 | * befs_off_t values. In interior nodes, the keys are the ending keys for |
51 | * the childnode they point to, and the values are offsets into the |
52 | * datastream containing the tree. |
53 | */ |
54 | |
55 | /* Note: |
56 | * |
57 | * The book states 2 confusing things about befs b+trees. First, |
58 | * it states that the overflow field of node headers is used by internal nodes |
59 | * to point to another node that "effectively continues this one". Here is what |
60 | * I believe that means. Each key in internal nodes points to another node that |
61 | * contains key values less than itself. Inspection reveals that the last key |
62 | * in the internal node is not the last key in the index. Keys that are |
63 | * greater than the last key in the internal node go into the overflow node. |
64 | * I imagine there is a performance reason for this. |
65 | * |
66 | * Second, it states that the header of a btree node is sufficient to |
67 | * distinguish internal nodes from leaf nodes. Without saying exactly how. |
68 | * After figuring out the first, it becomes obvious that internal nodes have |
69 | * overflow nodes and leafnodes do not. |
70 | */ |
71 | |
72 | /* |
73 | * Currently, this code is only good for directory B+trees. |
74 | * In order to be used for other BFS indexes, it needs to be extended to handle |
75 | * duplicate keys and non-string keytypes (int32, int64, float, double). |
76 | */ |
77 | |
78 | /* |
79 | * In memory structure of each btree node |
80 | */ |
81 | struct befs_btree_node { |
82 | befs_host_btree_nodehead head; /* head of node converted to cpu byteorder */ |
83 | struct buffer_head *bh; |
84 | befs_btree_nodehead *od_node; /* on disk node */ |
85 | }; |
86 | |
87 | /* local constants */ |
88 | static const befs_off_t BEFS_BT_INVAL = 0xffffffffffffffffULL; |
89 | |
90 | /* local functions */ |
91 | static int befs_btree_seekleaf(struct super_block *sb, const befs_data_stream *ds, |
92 | befs_btree_super * bt_super, |
93 | struct befs_btree_node *this_node, |
94 | befs_off_t * node_off); |
95 | |
96 | static int befs_bt_read_super(struct super_block *sb, const befs_data_stream *ds, |
97 | befs_btree_super * sup); |
98 | |
99 | static int befs_bt_read_node(struct super_block *sb, const befs_data_stream *ds, |
100 | struct befs_btree_node *node, |
101 | befs_off_t node_off); |
102 | |
103 | static int befs_leafnode(struct befs_btree_node *node); |
104 | |
105 | static fs16 *befs_bt_keylen_index(struct befs_btree_node *node); |
106 | |
107 | static fs64 *befs_bt_valarray(struct befs_btree_node *node); |
108 | |
109 | static char *befs_bt_keydata(struct befs_btree_node *node); |
110 | |
111 | static int befs_find_key(struct super_block *sb, |
112 | struct befs_btree_node *node, |
113 | const char *findkey, befs_off_t * value); |
114 | |
115 | static char *befs_bt_get_key(struct super_block *sb, |
116 | struct befs_btree_node *node, |
117 | int index, u16 * keylen); |
118 | |
119 | static int befs_compare_strings(const void *key1, int keylen1, |
120 | const void *key2, int keylen2); |
121 | |
122 | /** |
123 | * befs_bt_read_super() - read in btree superblock convert to cpu byteorder |
124 | * @sb: Filesystem superblock |
125 | * @ds: Datastream to read from |
126 | * @sup: Buffer in which to place the btree superblock |
127 | * |
128 | * Calls befs_read_datastream to read in the btree superblock and |
129 | * makes sure it is in cpu byteorder, byteswapping if necessary. |
130 | * Return: BEFS_OK on success and if *@sup contains the btree superblock in cpu |
131 | * byte order. Otherwise return BEFS_ERR on error. |
132 | */ |
133 | static int |
134 | befs_bt_read_super(struct super_block *sb, const befs_data_stream *ds, |
135 | befs_btree_super * sup) |
136 | { |
137 | struct buffer_head *bh; |
138 | befs_disk_btree_super *od_sup; |
139 | |
140 | befs_debug(sb, fmt: "---> %s" , __func__); |
141 | |
142 | bh = befs_read_datastream(sb, ds, pos: 0, NULL); |
143 | |
144 | if (!bh) { |
145 | befs_error(sb, fmt: "Couldn't read index header." ); |
146 | goto error; |
147 | } |
148 | od_sup = (befs_disk_btree_super *) bh->b_data; |
149 | befs_dump_index_entry(sb, od_sup); |
150 | |
151 | sup->magic = fs32_to_cpu(sb, n: od_sup->magic); |
152 | sup->node_size = fs32_to_cpu(sb, n: od_sup->node_size); |
153 | sup->max_depth = fs32_to_cpu(sb, n: od_sup->max_depth); |
154 | sup->data_type = fs32_to_cpu(sb, n: od_sup->data_type); |
155 | sup->root_node_ptr = fs64_to_cpu(sb, n: od_sup->root_node_ptr); |
156 | |
157 | brelse(bh); |
158 | if (sup->magic != BEFS_BTREE_MAGIC) { |
159 | befs_error(sb, fmt: "Index header has bad magic." ); |
160 | goto error; |
161 | } |
162 | |
163 | befs_debug(sb, fmt: "<--- %s" , __func__); |
164 | return BEFS_OK; |
165 | |
166 | error: |
167 | befs_debug(sb, fmt: "<--- %s ERROR" , __func__); |
168 | return BEFS_ERR; |
169 | } |
170 | |
171 | /** |
172 | * befs_bt_read_node - read in btree node and convert to cpu byteorder |
173 | * @sb: Filesystem superblock |
174 | * @ds: Datastream to read from |
175 | * @node: Buffer in which to place the btree node |
176 | * @node_off: Starting offset (in bytes) of the node in @ds |
177 | * |
178 | * Calls befs_read_datastream to read in the indicated btree node and |
179 | * makes sure its header fields are in cpu byteorder, byteswapping if |
180 | * necessary. |
181 | * Note: node->bh must be NULL when this function is called the first time. |
182 | * Don't forget brelse(node->bh) after last call. |
183 | * |
184 | * On success, returns BEFS_OK and *@node contains the btree node that |
185 | * starts at @node_off, with the node->head fields in cpu byte order. |
186 | * |
187 | * On failure, BEFS_ERR is returned. |
188 | */ |
189 | |
190 | static int |
191 | befs_bt_read_node(struct super_block *sb, const befs_data_stream *ds, |
192 | struct befs_btree_node *node, befs_off_t node_off) |
193 | { |
194 | uint off = 0; |
195 | |
196 | befs_debug(sb, fmt: "---> %s" , __func__); |
197 | |
198 | if (node->bh) |
199 | brelse(bh: node->bh); |
200 | |
201 | node->bh = befs_read_datastream(sb, ds, pos: node_off, off: &off); |
202 | if (!node->bh) { |
203 | befs_error(sb, fmt: "%s failed to read " |
204 | "node at %llu" , __func__, node_off); |
205 | befs_debug(sb, fmt: "<--- %s ERROR" , __func__); |
206 | |
207 | return BEFS_ERR; |
208 | } |
209 | node->od_node = |
210 | (befs_btree_nodehead *) ((void *) node->bh->b_data + off); |
211 | |
212 | befs_dump_index_node(sb, node->od_node); |
213 | |
214 | node->head.left = fs64_to_cpu(sb, n: node->od_node->left); |
215 | node->head.right = fs64_to_cpu(sb, n: node->od_node->right); |
216 | node->head.overflow = fs64_to_cpu(sb, n: node->od_node->overflow); |
217 | node->head.all_key_count = |
218 | fs16_to_cpu(sb, n: node->od_node->all_key_count); |
219 | node->head.all_key_length = |
220 | fs16_to_cpu(sb, n: node->od_node->all_key_length); |
221 | |
222 | befs_debug(sb, fmt: "<--- %s" , __func__); |
223 | return BEFS_OK; |
224 | } |
225 | |
226 | /** |
227 | * befs_btree_find - Find a key in a befs B+tree |
228 | * @sb: Filesystem superblock |
229 | * @ds: Datastream containing btree |
230 | * @key: Key string to lookup in btree |
231 | * @value: Value stored with @key |
232 | * |
233 | * On success, returns BEFS_OK and sets *@value to the value stored |
234 | * with @key (usually the disk block number of an inode). |
235 | * |
236 | * On failure, returns BEFS_ERR or BEFS_BT_NOT_FOUND. |
237 | * |
238 | * Algorithm: |
239 | * Read the superblock and rootnode of the b+tree. |
240 | * Drill down through the interior nodes using befs_find_key(). |
241 | * Once at the correct leaf node, use befs_find_key() again to get the |
242 | * actual value stored with the key. |
243 | */ |
244 | int |
245 | befs_btree_find(struct super_block *sb, const befs_data_stream *ds, |
246 | const char *key, befs_off_t * value) |
247 | { |
248 | struct befs_btree_node *this_node; |
249 | befs_btree_super bt_super; |
250 | befs_off_t node_off; |
251 | int res; |
252 | |
253 | befs_debug(sb, fmt: "---> %s Key: %s" , __func__, key); |
254 | |
255 | if (befs_bt_read_super(sb, ds, sup: &bt_super) != BEFS_OK) { |
256 | befs_error(sb, |
257 | fmt: "befs_btree_find() failed to read index superblock" ); |
258 | goto error; |
259 | } |
260 | |
261 | this_node = kmalloc(size: sizeof(struct befs_btree_node), |
262 | GFP_NOFS); |
263 | if (!this_node) { |
264 | befs_error(sb, fmt: "befs_btree_find() failed to allocate %zu " |
265 | "bytes of memory" , sizeof(struct befs_btree_node)); |
266 | goto error; |
267 | } |
268 | |
269 | this_node->bh = NULL; |
270 | |
271 | /* read in root node */ |
272 | node_off = bt_super.root_node_ptr; |
273 | if (befs_bt_read_node(sb, ds, node: this_node, node_off) != BEFS_OK) { |
274 | befs_error(sb, fmt: "befs_btree_find() failed to read " |
275 | "node at %llu" , node_off); |
276 | goto error_alloc; |
277 | } |
278 | |
279 | while (!befs_leafnode(node: this_node)) { |
280 | res = befs_find_key(sb, node: this_node, findkey: key, value: &node_off); |
281 | /* if no key set, try the overflow node */ |
282 | if (res == BEFS_BT_OVERFLOW) |
283 | node_off = this_node->head.overflow; |
284 | if (befs_bt_read_node(sb, ds, node: this_node, node_off) != BEFS_OK) { |
285 | befs_error(sb, fmt: "befs_btree_find() failed to read " |
286 | "node at %llu" , node_off); |
287 | goto error_alloc; |
288 | } |
289 | } |
290 | |
291 | /* at a leaf node now, check if it is correct */ |
292 | res = befs_find_key(sb, node: this_node, findkey: key, value); |
293 | |
294 | brelse(bh: this_node->bh); |
295 | kfree(objp: this_node); |
296 | |
297 | if (res != BEFS_BT_MATCH) { |
298 | befs_error(sb, fmt: "<--- %s Key %s not found" , __func__, key); |
299 | befs_debug(sb, fmt: "<--- %s ERROR" , __func__); |
300 | *value = 0; |
301 | return BEFS_BT_NOT_FOUND; |
302 | } |
303 | befs_debug(sb, fmt: "<--- %s Found key %s, value %llu" , __func__, |
304 | key, *value); |
305 | return BEFS_OK; |
306 | |
307 | error_alloc: |
308 | kfree(objp: this_node); |
309 | error: |
310 | *value = 0; |
311 | befs_debug(sb, fmt: "<--- %s ERROR" , __func__); |
312 | return BEFS_ERR; |
313 | } |
314 | |
315 | /** |
316 | * befs_find_key - Search for a key within a node |
317 | * @sb: Filesystem superblock |
318 | * @node: Node to find the key within |
319 | * @findkey: Keystring to search for |
320 | * @value: If key is found, the value stored with the key is put here |
321 | * |
322 | * Finds exact match if one exists, and returns BEFS_BT_MATCH. |
323 | * If there is no match and node's value array is too small for key, return |
324 | * BEFS_BT_OVERFLOW. |
325 | * If no match and node should countain this key, return BEFS_BT_NOT_FOUND. |
326 | * |
327 | * Uses binary search instead of a linear. |
328 | */ |
329 | static int |
330 | befs_find_key(struct super_block *sb, struct befs_btree_node *node, |
331 | const char *findkey, befs_off_t * value) |
332 | { |
333 | int first, last, mid; |
334 | int eq; |
335 | u16 keylen; |
336 | int findkey_len; |
337 | char *thiskey; |
338 | fs64 *valarray; |
339 | |
340 | befs_debug(sb, fmt: "---> %s %s" , __func__, findkey); |
341 | |
342 | findkey_len = strlen(findkey); |
343 | |
344 | /* if node can not contain key, just skip this node */ |
345 | last = node->head.all_key_count - 1; |
346 | thiskey = befs_bt_get_key(sb, node, index: last, keylen: &keylen); |
347 | |
348 | eq = befs_compare_strings(key1: thiskey, keylen1: keylen, key2: findkey, keylen2: findkey_len); |
349 | if (eq < 0) { |
350 | befs_debug(sb, fmt: "<--- node can't contain %s" , findkey); |
351 | return BEFS_BT_OVERFLOW; |
352 | } |
353 | |
354 | valarray = befs_bt_valarray(node); |
355 | |
356 | /* simple binary search */ |
357 | first = 0; |
358 | mid = 0; |
359 | while (last >= first) { |
360 | mid = (last + first) / 2; |
361 | befs_debug(sb, fmt: "first: %d, last: %d, mid: %d" , first, last, |
362 | mid); |
363 | thiskey = befs_bt_get_key(sb, node, index: mid, keylen: &keylen); |
364 | eq = befs_compare_strings(key1: thiskey, keylen1: keylen, key2: findkey, |
365 | keylen2: findkey_len); |
366 | |
367 | if (eq == 0) { |
368 | befs_debug(sb, fmt: "<--- %s found %s at %d" , |
369 | __func__, thiskey, mid); |
370 | |
371 | *value = fs64_to_cpu(sb, n: valarray[mid]); |
372 | return BEFS_BT_MATCH; |
373 | } |
374 | if (eq > 0) |
375 | last = mid - 1; |
376 | else |
377 | first = mid + 1; |
378 | } |
379 | |
380 | /* return an existing value so caller can arrive to a leaf node */ |
381 | if (eq < 0) |
382 | *value = fs64_to_cpu(sb, n: valarray[mid + 1]); |
383 | else |
384 | *value = fs64_to_cpu(sb, n: valarray[mid]); |
385 | befs_error(sb, fmt: "<--- %s %s not found" , __func__, findkey); |
386 | befs_debug(sb, fmt: "<--- %s ERROR" , __func__); |
387 | return BEFS_BT_NOT_FOUND; |
388 | } |
389 | |
390 | /** |
391 | * befs_btree_read - Traverse leafnodes of a btree |
392 | * @sb: Filesystem superblock |
393 | * @ds: Datastream containing btree |
394 | * @key_no: Key number (alphabetical order) of key to read |
395 | * @bufsize: Size of the buffer to return key in |
396 | * @keybuf: Pointer to a buffer to put the key in |
397 | * @keysize: Length of the returned key |
398 | * @value: Value stored with the returned key |
399 | * |
400 | * Here's how it works: Key_no is the index of the key/value pair to |
401 | * return in keybuf/value. |
402 | * Bufsize is the size of keybuf (BEFS_NAME_LEN+1 is a good size). Keysize is |
403 | * the number of characters in the key (just a convenience). |
404 | * |
405 | * Algorithm: |
406 | * Get the first leafnode of the tree. See if the requested key is in that |
407 | * node. If not, follow the node->right link to the next leafnode. Repeat |
408 | * until the (key_no)th key is found or the tree is out of keys. |
409 | */ |
410 | int |
411 | befs_btree_read(struct super_block *sb, const befs_data_stream *ds, |
412 | loff_t key_no, size_t bufsize, char *keybuf, size_t * keysize, |
413 | befs_off_t * value) |
414 | { |
415 | struct befs_btree_node *this_node; |
416 | befs_btree_super bt_super; |
417 | befs_off_t node_off; |
418 | int cur_key; |
419 | fs64 *valarray; |
420 | char *keystart; |
421 | u16 keylen; |
422 | int res; |
423 | |
424 | uint key_sum = 0; |
425 | |
426 | befs_debug(sb, fmt: "---> %s" , __func__); |
427 | |
428 | if (befs_bt_read_super(sb, ds, sup: &bt_super) != BEFS_OK) { |
429 | befs_error(sb, |
430 | fmt: "befs_btree_read() failed to read index superblock" ); |
431 | goto error; |
432 | } |
433 | |
434 | this_node = kmalloc(size: sizeof(struct befs_btree_node), GFP_NOFS); |
435 | if (this_node == NULL) { |
436 | befs_error(sb, fmt: "befs_btree_read() failed to allocate %zu " |
437 | "bytes of memory" , sizeof(struct befs_btree_node)); |
438 | goto error; |
439 | } |
440 | |
441 | node_off = bt_super.root_node_ptr; |
442 | this_node->bh = NULL; |
443 | |
444 | /* seeks down to first leafnode, reads it into this_node */ |
445 | res = befs_btree_seekleaf(sb, ds, bt_super: &bt_super, this_node, node_off: &node_off); |
446 | if (res == BEFS_BT_EMPTY) { |
447 | brelse(bh: this_node->bh); |
448 | kfree(objp: this_node); |
449 | *value = 0; |
450 | *keysize = 0; |
451 | befs_debug(sb, fmt: "<--- %s Tree is EMPTY" , __func__); |
452 | return BEFS_BT_EMPTY; |
453 | } else if (res == BEFS_ERR) { |
454 | goto error_alloc; |
455 | } |
456 | |
457 | /* find the leaf node containing the key_no key */ |
458 | |
459 | while (key_sum + this_node->head.all_key_count <= key_no) { |
460 | |
461 | /* no more nodes to look in: key_no is too large */ |
462 | if (this_node->head.right == BEFS_BT_INVAL) { |
463 | *keysize = 0; |
464 | *value = 0; |
465 | befs_debug(sb, |
466 | fmt: "<--- %s END of keys at %llu" , __func__, |
467 | (unsigned long long) |
468 | key_sum + this_node->head.all_key_count); |
469 | brelse(bh: this_node->bh); |
470 | kfree(objp: this_node); |
471 | return BEFS_BT_END; |
472 | } |
473 | |
474 | key_sum += this_node->head.all_key_count; |
475 | node_off = this_node->head.right; |
476 | |
477 | if (befs_bt_read_node(sb, ds, node: this_node, node_off) != BEFS_OK) { |
478 | befs_error(sb, fmt: "%s failed to read node at %llu" , |
479 | __func__, (unsigned long long)node_off); |
480 | goto error_alloc; |
481 | } |
482 | } |
483 | |
484 | /* how many keys into this_node is key_no */ |
485 | cur_key = key_no - key_sum; |
486 | |
487 | /* get pointers to datastructures within the node body */ |
488 | valarray = befs_bt_valarray(node: this_node); |
489 | |
490 | keystart = befs_bt_get_key(sb, node: this_node, index: cur_key, keylen: &keylen); |
491 | |
492 | befs_debug(sb, fmt: "Read [%llu,%d]: keysize %d" , |
493 | (long long unsigned int)node_off, (int)cur_key, |
494 | (int)keylen); |
495 | |
496 | if (bufsize < keylen + 1) { |
497 | befs_error(sb, fmt: "%s keybuf too small (%zu) " |
498 | "for key of size %d" , __func__, bufsize, keylen); |
499 | brelse(bh: this_node->bh); |
500 | goto error_alloc; |
501 | } |
502 | |
503 | strscpy(p: keybuf, q: keystart, size: keylen + 1); |
504 | *value = fs64_to_cpu(sb, n: valarray[cur_key]); |
505 | *keysize = keylen; |
506 | |
507 | befs_debug(sb, fmt: "Read [%llu,%d]: Key \"%.*s\", Value %llu" , node_off, |
508 | cur_key, keylen, keybuf, *value); |
509 | |
510 | brelse(bh: this_node->bh); |
511 | kfree(objp: this_node); |
512 | |
513 | befs_debug(sb, fmt: "<--- %s" , __func__); |
514 | |
515 | return BEFS_OK; |
516 | |
517 | error_alloc: |
518 | kfree(objp: this_node); |
519 | |
520 | error: |
521 | *keysize = 0; |
522 | *value = 0; |
523 | befs_debug(sb, fmt: "<--- %s ERROR" , __func__); |
524 | return BEFS_ERR; |
525 | } |
526 | |
527 | /** |
528 | * befs_btree_seekleaf - Find the first leafnode in the btree |
529 | * @sb: Filesystem superblock |
530 | * @ds: Datastream containing btree |
531 | * @bt_super: Pointer to the superblock of the btree |
532 | * @this_node: Buffer to return the leafnode in |
533 | * @node_off: Pointer to offset of current node within datastream. Modified |
534 | * by the function. |
535 | * |
536 | * Helper function for btree traverse. Moves the current position to the |
537 | * start of the first leaf node. |
538 | * |
539 | * Also checks for an empty tree. If there are no keys, returns BEFS_BT_EMPTY. |
540 | */ |
541 | static int |
542 | befs_btree_seekleaf(struct super_block *sb, const befs_data_stream *ds, |
543 | befs_btree_super *bt_super, |
544 | struct befs_btree_node *this_node, |
545 | befs_off_t * node_off) |
546 | { |
547 | |
548 | befs_debug(sb, fmt: "---> %s" , __func__); |
549 | |
550 | if (befs_bt_read_node(sb, ds, node: this_node, node_off: *node_off) != BEFS_OK) { |
551 | befs_error(sb, fmt: "%s failed to read " |
552 | "node at %llu" , __func__, *node_off); |
553 | goto error; |
554 | } |
555 | befs_debug(sb, fmt: "Seekleaf to root node %llu" , *node_off); |
556 | |
557 | if (this_node->head.all_key_count == 0 && befs_leafnode(node: this_node)) { |
558 | befs_debug(sb, fmt: "<--- %s Tree is EMPTY" , __func__); |
559 | return BEFS_BT_EMPTY; |
560 | } |
561 | |
562 | while (!befs_leafnode(node: this_node)) { |
563 | |
564 | if (this_node->head.all_key_count == 0) { |
565 | befs_debug(sb, fmt: "%s encountered " |
566 | "an empty interior node: %llu. Using Overflow " |
567 | "node: %llu" , __func__, *node_off, |
568 | this_node->head.overflow); |
569 | *node_off = this_node->head.overflow; |
570 | } else { |
571 | fs64 *valarray = befs_bt_valarray(node: this_node); |
572 | *node_off = fs64_to_cpu(sb, n: valarray[0]); |
573 | } |
574 | if (befs_bt_read_node(sb, ds, node: this_node, node_off: *node_off) != BEFS_OK) { |
575 | befs_error(sb, fmt: "%s failed to read " |
576 | "node at %llu" , __func__, *node_off); |
577 | goto error; |
578 | } |
579 | |
580 | befs_debug(sb, fmt: "Seekleaf to child node %llu" , *node_off); |
581 | } |
582 | befs_debug(sb, fmt: "Node %llu is a leaf node" , *node_off); |
583 | |
584 | return BEFS_OK; |
585 | |
586 | error: |
587 | befs_debug(sb, fmt: "<--- %s ERROR" , __func__); |
588 | return BEFS_ERR; |
589 | } |
590 | |
591 | /** |
592 | * befs_leafnode - Determine if the btree node is a leaf node or an |
593 | * interior node |
594 | * @node: Pointer to node structure to test |
595 | * |
596 | * Return 1 if leaf, 0 if interior |
597 | */ |
598 | static int |
599 | befs_leafnode(struct befs_btree_node *node) |
600 | { |
601 | /* all interior nodes (and only interior nodes) have an overflow node */ |
602 | if (node->head.overflow == BEFS_BT_INVAL) |
603 | return 1; |
604 | else |
605 | return 0; |
606 | } |
607 | |
608 | /** |
609 | * befs_bt_keylen_index - Finds start of keylen index in a node |
610 | * @node: Pointer to the node structure to find the keylen index within |
611 | * |
612 | * Returns a pointer to the start of the key length index array |
613 | * of the B+tree node *@node |
614 | * |
615 | * "The length of all the keys in the node is added to the size of the |
616 | * header and then rounded up to a multiple of four to get the beginning |
617 | * of the key length index" (p.88, practical filesystem design). |
618 | * |
619 | * Except that rounding up to 8 works, and rounding up to 4 doesn't. |
620 | */ |
621 | static fs16 * |
622 | befs_bt_keylen_index(struct befs_btree_node *node) |
623 | { |
624 | const int keylen_align = 8; |
625 | unsigned long int off = |
626 | (sizeof (befs_btree_nodehead) + node->head.all_key_length); |
627 | ulong tmp = off % keylen_align; |
628 | |
629 | if (tmp) |
630 | off += keylen_align - tmp; |
631 | |
632 | return (fs16 *) ((void *) node->od_node + off); |
633 | } |
634 | |
635 | /** |
636 | * befs_bt_valarray - Finds the start of value array in a node |
637 | * @node: Pointer to the node structure to find the value array within |
638 | * |
639 | * Returns a pointer to the start of the value array |
640 | * of the node pointed to by the node header |
641 | */ |
642 | static fs64 * |
643 | befs_bt_valarray(struct befs_btree_node *node) |
644 | { |
645 | void *keylen_index_start = (void *) befs_bt_keylen_index(node); |
646 | size_t keylen_index_size = node->head.all_key_count * sizeof (fs16); |
647 | |
648 | return (fs64 *) (keylen_index_start + keylen_index_size); |
649 | } |
650 | |
651 | /** |
652 | * befs_bt_keydata - Finds start of keydata array in a node |
653 | * @node: Pointer to the node structure to find the keydata array within |
654 | * |
655 | * Returns a pointer to the start of the keydata array |
656 | * of the node pointed to by the node header |
657 | */ |
658 | static char * |
659 | befs_bt_keydata(struct befs_btree_node *node) |
660 | { |
661 | return (char *) ((void *) node->od_node + sizeof (befs_btree_nodehead)); |
662 | } |
663 | |
664 | /** |
665 | * befs_bt_get_key - returns a pointer to the start of a key |
666 | * @sb: filesystem superblock |
667 | * @node: node in which to look for the key |
668 | * @index: the index of the key to get |
669 | * @keylen: modified to be the length of the key at @index |
670 | * |
671 | * Returns a valid pointer into @node on success. |
672 | * Returns NULL on failure (bad input) and sets *@keylen = 0 |
673 | */ |
674 | static char * |
675 | befs_bt_get_key(struct super_block *sb, struct befs_btree_node *node, |
676 | int index, u16 * keylen) |
677 | { |
678 | int prev_key_end; |
679 | char *keystart; |
680 | fs16 *keylen_index; |
681 | |
682 | if (index < 0 || index > node->head.all_key_count) { |
683 | *keylen = 0; |
684 | return NULL; |
685 | } |
686 | |
687 | keystart = befs_bt_keydata(node); |
688 | keylen_index = befs_bt_keylen_index(node); |
689 | |
690 | if (index == 0) |
691 | prev_key_end = 0; |
692 | else |
693 | prev_key_end = fs16_to_cpu(sb, n: keylen_index[index - 1]); |
694 | |
695 | *keylen = fs16_to_cpu(sb, n: keylen_index[index]) - prev_key_end; |
696 | |
697 | return keystart + prev_key_end; |
698 | } |
699 | |
700 | /** |
701 | * befs_compare_strings - compare two strings |
702 | * @key1: pointer to the first key to be compared |
703 | * @keylen1: length in bytes of key1 |
704 | * @key2: pointer to the second key to be compared |
705 | * @keylen2: length in bytes of key2 |
706 | * |
707 | * Returns 0 if @key1 and @key2 are equal. |
708 | * Returns >0 if @key1 is greater. |
709 | * Returns <0 if @key2 is greater. |
710 | */ |
711 | static int |
712 | befs_compare_strings(const void *key1, int keylen1, |
713 | const void *key2, int keylen2) |
714 | { |
715 | int len = min_t(int, keylen1, keylen2); |
716 | int result = strncmp(key1, key2, len); |
717 | if (result == 0) |
718 | result = keylen1 - keylen2; |
719 | return result; |
720 | } |
721 | |
722 | /* These will be used for non-string keyed btrees */ |
723 | #if 0 |
724 | static int |
725 | btree_compare_int32(cont void *key1, int keylen1, const void *key2, int keylen2) |
726 | { |
727 | return *(int32_t *) key1 - *(int32_t *) key2; |
728 | } |
729 | |
730 | static int |
731 | btree_compare_uint32(cont void *key1, int keylen1, |
732 | const void *key2, int keylen2) |
733 | { |
734 | if (*(u_int32_t *) key1 == *(u_int32_t *) key2) |
735 | return 0; |
736 | else if (*(u_int32_t *) key1 > *(u_int32_t *) key2) |
737 | return 1; |
738 | |
739 | return -1; |
740 | } |
741 | static int |
742 | btree_compare_int64(cont void *key1, int keylen1, const void *key2, int keylen2) |
743 | { |
744 | if (*(int64_t *) key1 == *(int64_t *) key2) |
745 | return 0; |
746 | else if (*(int64_t *) key1 > *(int64_t *) key2) |
747 | return 1; |
748 | |
749 | return -1; |
750 | } |
751 | |
752 | static int |
753 | btree_compare_uint64(cont void *key1, int keylen1, |
754 | const void *key2, int keylen2) |
755 | { |
756 | if (*(u_int64_t *) key1 == *(u_int64_t *) key2) |
757 | return 0; |
758 | else if (*(u_int64_t *) key1 > *(u_int64_t *) key2) |
759 | return 1; |
760 | |
761 | return -1; |
762 | } |
763 | |
764 | static int |
765 | btree_compare_float(cont void *key1, int keylen1, const void *key2, int keylen2) |
766 | { |
767 | float result = *(float *) key1 - *(float *) key2; |
768 | if (result == 0.0f) |
769 | return 0; |
770 | |
771 | return (result < 0.0f) ? -1 : 1; |
772 | } |
773 | |
774 | static int |
775 | btree_compare_double(cont void *key1, int keylen1, |
776 | const void *key2, int keylen2) |
777 | { |
778 | double result = *(double *) key1 - *(double *) key2; |
779 | if (result == 0.0) |
780 | return 0; |
781 | |
782 | return (result < 0.0) ? -1 : 1; |
783 | } |
784 | #endif //0 |
785 | |