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 789