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