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