The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/fs/befs/btree.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    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 
   29 #include "befs.h"
   30 #include "btree.h"
   31 #include "datastream.h"
   32 #include "endian.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 usefull 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 feild of node headers is used by internal nodes 
   59  * to point to another node that "effectivly continues this one". Here is what 
   60  * I belive 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 {
   82         befs_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 } befs_btree_node;
   86 
   87 /* local constants */
   88 const static befs_off_t befs_bt_inval = 0xffffffffffffffff;
   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 
  104 static u16 *befs_bt_keylen_index(befs_btree_node * node);
  105 
  106 static befs_off_t *befs_bt_valarray(befs_btree_node * node);
  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 nessisary.
  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;
  138         befs_btree_super *od_sup = NULL;
  139 
  140         befs_debug(sb, "---> befs_btree_read_super()");
  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         }
  148         od_sup = (befs_btree_super *) bh->b_data;
  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 
  165         befs_debug(sb, "<--- befs_btree_read_super()");
  166         return BEFS_OK;
  167 
  168       error:
  169         befs_debug(sb, "<--- befs_btree_read_super() ERROR");
  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 feilds are in cpu byteorder, byteswapping if 
  182  * nessisary.
  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 
  198         befs_debug(sb, "---> befs_bt_read_node()");
  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) {
  205                 befs_error(sb, "befs_bt_read_node() failed to read "
  206                            "node at %Lu", node_off);
  207                 befs_debug(sb, "<--- befs_bt_read_node() ERROR");
  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 
  224         befs_debug(sb, "<--- befs_btree_read_node()");
  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  *
  235  * On sucess, returns BEFS_OK and sets *@value to the value stored
  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 
  255         befs_debug(sb, "---> befs_btree_find() Key: %s", key);
  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 
  263         this_node = (befs_btree_node *) kmalloc(sizeof (befs_btree_node),
  264                                                 GFP_NOFS);
  265         if (!this_node) {
  266                 befs_error(sb, "befs_btree_find() failed to allocate %u "
  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 "
  277                            "node at %Lu", node_off);
  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 "
  288                                    "node at %Lu", node_off);
  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) {
  301                 befs_debug(sb, "<--- befs_btree_find() Key %s not found", key);
  302                 *value = 0;
  303                 return BEFS_BT_NOT_FOUND;
  304         }
  305         befs_debug(sb, "<--- befs_btree_find() Found key %s, value %Lu",
  306                    key, *value);
  307         return BEFS_OK;
  308 
  309       error_alloc:
  310         kfree(this_node);
  311       error:
  312         *value = 0;
  313         befs_debug(sb, "<--- befs_btree_find() ERROR");
  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  * (alpabeticly) 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;
  344         befs_off_t *valarray;
  345 
  346         befs_debug(sb, "---> befs_find_key() %s", findkey);
  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) {
  358                 befs_debug(sb, "<--- befs_find_key() %s not found", findkey);
  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                 *value = fs64_to_cpu(sb, valarray[mid]);
  375 
  376                 if (eq == 0) {
  377                         befs_debug(sb, "<--- befs_find_key() found %s at %d",
  378                                    thiskey, mid);
  379 
  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         befs_debug(sb, "<--- befs_find_key() found %s at %d", thiskey, mid);
  390         return BEFS_BT_PARMATCH;
  391 }
  392 
  393 /**
  394  * befs_btree_read - Traverse leafnodes of a btree
  395  * @sb: Filesystem superblock
  396  * @ds: Datastream containing btree
  397  * @key_no: Key number (alphabetical order) of key to read
  398  * @bufsize: Size of the buffer to return key in
  399  * @keybuf: Pointer to a buffer to put the key in
  400  * @keysize: Length of the returned key
  401  * @value: Value stored with the returned key
  402  *
  403  * Heres how it works: Key_no is the index of the key/value pair to 
  404  * retun in keybuf/value.
  405  * Bufsize is the size of keybuf (BEFS_NAME_LEN+1 is a good size). Keysize is 
  406  * the number of charecters in the key (just a convience).
  407  *
  408  * Algorithm:
  409  *   Get the first leafnode of the tree. See if the requested key is in that
  410  *   node. If not, follow the node->right link to the next leafnode. Repeat 
  411  *   until the (key_no)th key is found or the tree is out of keys.
  412  */
  413 int
  414 befs_btree_read(struct super_block *sb, befs_data_stream * ds,
  415                 loff_t key_no, size_t bufsize, char *keybuf, size_t * keysize,
  416                 befs_off_t * value)
  417 {
  418         befs_btree_node *this_node;
  419         befs_btree_super bt_super;
  420         befs_off_t node_off = 0;
  421         int cur_key;
  422         befs_off_t *valarray;
  423         char *keystart;
  424         u16 keylen;
  425         int res;
  426 
  427         uint key_sum = 0;
  428 
  429         befs_debug(sb, "---> befs_btree_read()");
  430 
  431         if (befs_bt_read_super(sb, ds, &bt_super) != BEFS_OK) {
  432                 befs_error(sb,
  433                            "befs_btree_read() failed to read index superblock");
  434                 goto error;
  435         }
  436 
  437         if ((this_node = (befs_btree_node *)
  438              kmalloc(sizeof (befs_btree_node), GFP_NOFS)) == NULL) {
  439                 befs_error(sb, "befs_btree_read() failed to allocate %u "
  440                            "bytes of memory", sizeof (befs_btree_node));
  441                 goto error;
  442         }
  443 
  444         node_off = bt_super.root_node_ptr;
  445         this_node->bh = NULL;
  446 
  447         /* seeks down to first leafnode, reads it into this_node */
  448         res = befs_btree_seekleaf(sb, ds, &bt_super, this_node, &node_off);
  449         if (res == BEFS_BT_EMPTY) {
  450                 brelse(this_node->bh);
  451                 kfree(this_node);
  452                 *value = 0;
  453                 *keysize = 0;
  454                 befs_debug(sb, "<--- befs_btree_read() Tree is EMPTY");
  455                 return BEFS_BT_EMPTY;
  456         } else if (res == BEFS_ERR) {
  457                 goto error_alloc;
  458         }
  459 
  460         /* find the leaf node containing the key_no key */
  461 
  462         while (key_sum + this_node->head.all_key_count <= key_no) {
  463 
  464                 /* no more nodes to look in: key_no is too large */
  465                 if (this_node->head.right == befs_bt_inval) {
  466                         *keysize = 0;
  467                         *value = 0;
  468                         befs_debug(sb,
  469                                    "<--- befs_btree_read() END of keys at %Lu",
  470                                    key_sum + this_node->head.all_key_count);
  471                         brelse(this_node->bh);
  472                         kfree(this_node);
  473                         return BEFS_BT_END;
  474                 }
  475 
  476                 key_sum += this_node->head.all_key_count;
  477                 node_off = this_node->head.right;
  478 
  479                 if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {
  480                         befs_error(sb, "befs_btree_read() failed to read "
  481                                    "node at %Lu", node_off);
  482                         goto error_alloc;
  483                 }
  484         }
  485 
  486         /* how many keys into this_node is key_no */
  487         cur_key = key_no - key_sum;
  488 
  489         /* get pointers to datastructures within the node body */
  490         valarray = befs_bt_valarray(this_node);
  491 
  492         keystart = befs_bt_get_key(sb, this_node, cur_key, &keylen);
  493 
  494         befs_debug(sb, "Read [%Lu,%d]: keysize %d", node_off, cur_key, keylen);
  495 
  496         if (bufsize < keylen + 1) {
  497                 befs_error(sb, "befs_btree_read() keybuf too small (%u) "
  498                            "for key of size %d", bufsize, keylen);
  499                 brelse(this_node->bh);
  500                 goto error_alloc;
  501         };
  502 
  503         strncpy(keybuf, keystart, keylen);
  504         *value = fs64_to_cpu(sb, valarray[cur_key]);
  505         *keysize = keylen;
  506         keybuf[keylen] = '\0';
  507 
  508         befs_debug(sb, "Read [%Lu,%d]: Key \"%.*s\", Value %Lu", node_off,
  509                    cur_key, keylen, keybuf, *value);
  510 
  511         brelse(this_node->bh);
  512         kfree(this_node);
  513 
  514         befs_debug(sb, "<--- befs_btree_read()");
  515 
  516         return BEFS_OK;
  517 
  518       error_alloc:
  519         kfree(this_node);
  520 
  521       error:
  522         *keysize = 0;
  523         *value = 0;
  524         befs_debug(sb, "<--- befs_btree_read() ERROR");
  525         return BEFS_ERR;
  526 }
  527 
  528 /**
  529  * befs_btree_seekleaf - Find the first leafnode in the btree
  530  * @sb: Filesystem superblock
  531  * @ds: Datastream containing btree
  532  * @bt_super: Pointer to the uperblock of the btree
  533  * @this_node: Buffer to return the leafnode in
  534  * @node_off: Pointer to offset of current node within datastream. Modified
  535  *              by the function.
  536  *
  537  *
  538  * Helper function for btree traverse. Moves the current position to the 
  539  * start of the first leaf node.
  540  *
  541  * Also checks for an empty tree. If there are no keys, returns BEFS_BT_EMPTY.
  542  */
  543 static int
  544 befs_btree_seekleaf(struct super_block *sb, befs_data_stream * ds,
  545                     befs_btree_super * bt_super, befs_btree_node * this_node,
  546                     befs_off_t * node_off)
  547 {
  548 
  549         befs_debug(sb, "---> befs_btree_seekleaf()");
  550 
  551         if (befs_bt_read_node(sb, ds, this_node, *node_off) != BEFS_OK) {
  552                 befs_error(sb, "befs_btree_seekleaf() failed to read "
  553                            "node at %Lu", *node_off);
  554                 goto error;
  555         }
  556         befs_debug(sb, "Seekleaf to root node %Lu", *node_off);
  557 
  558         if (this_node->head.all_key_count == 0 && befs_leafnode(this_node)) {
  559                 befs_debug(sb, "<--- befs_btree_seekleaf() Tree is EMPTY");
  560                 return BEFS_BT_EMPTY;
  561         }
  562 
  563         while (!befs_leafnode(this_node)) {
  564 
  565                 if (this_node->head.all_key_count == 0) {
  566                         befs_debug(sb, "befs_btree_seekleaf() encountered "
  567                                    "an empty interior node: %Lu. Using Overflow "
  568                                    "node: %Lu", *node_off,
  569                                    this_node->head.overflow);
  570                         *node_off = this_node->head.overflow;
  571                 } else {
  572                         befs_off_t *valarray = befs_bt_valarray(this_node);
  573                         *node_off = fs64_to_cpu(sb, valarray[0]);
  574                 }
  575                 if (befs_bt_read_node(sb, ds, this_node, *node_off) != BEFS_OK) {
  576                         befs_error(sb, "befs_btree_seekleaf() failed to read "
  577                                    "node at %Lu", *node_off);
  578                         goto error;
  579                 }
  580 
  581                 befs_debug(sb, "Seekleaf to child node %Lu", *node_off);
  582         }
  583         befs_debug(sb, "Node %Lu is a leaf node", *node_off);
  584 
  585         return BEFS_OK;
  586 
  587       error:
  588         befs_debug(sb, "<--- befs_btree_seekleaf() ERROR");
  589         return BEFS_ERR;
  590 }
  591 
  592 /**
  593  * befs_leafnode - Determine if the btree node is a leaf node or an 
  594  * interior node
  595  * @node: Pointer to node structure to test
  596  * 
  597  * Return 1 if leaf, 0 if interior
  598  */
  599 static int
  600 befs_leafnode(befs_btree_node * node)
  601 {
  602         /* all interior nodes (and only interior nodes) have an overflow node */
  603         if (node->head.overflow == befs_bt_inval)
  604                 return 1;
  605         else
  606                 return 0;
  607 }
  608 
  609 /**
  610  * befs_bt_keylen_index - Finds start of keylen index in a node
  611  * @node: Pointer to the node structure to find the keylen index within
  612  *
  613  * Returns a pointer to the start of the key length index array
  614  * of the B+tree node *@node
  615  *
  616  * "The length of all the keys in the node is added to the size of the
  617  * header and then rounded up to a multiple of four to get the begining
  618  * of the key length index" (p.88, practical filesystem design).
  619  *
  620  * Exept that rounding up to 8 works, and rounding up to 4 doesn't.
  621  */
  622 static u16 *
  623 befs_bt_keylen_index(befs_btree_node * node)
  624 {
  625         const int keylen_align = 8;
  626         unsigned long int off =
  627             (sizeof (befs_btree_nodehead) + node->head.all_key_length);
  628         ulong tmp = off % keylen_align;
  629 
  630         if (tmp)
  631                 off += keylen_align - tmp;
  632 
  633         return (u16 *) ((void *) node->od_node + off);
  634 }
  635 
  636 /**
  637  * befs_bt_valarray - Finds the start of value array in a node
  638  * @node: Pointer to the node structure to find the value array within
  639  *
  640  * Returns a pointer to the start of the value array
  641  * of the node pointed to by the node header
  642  */
  643 static befs_off_t *
  644 befs_bt_valarray(befs_btree_node * node)
  645 {
  646         void *keylen_index_start = (void *) befs_bt_keylen_index(node);
  647         size_t keylen_index_size = node->head.all_key_count * sizeof (u16);
  648 
  649         return (befs_off_t *) (keylen_index_start + keylen_index_size);
  650 }
  651 
  652 /**
  653  * befs_bt_keydata - Finds start of keydata array in a node
  654  * @node: Pointer to the node structure to find the keydata array within
  655  *
  656  * Returns a pointer to the start of the keydata array
  657  * of the node pointed to by the node header 
  658  */
  659 static char *
  660 befs_bt_keydata(befs_btree_node * node)
  661 {
  662         return (char *) ((void *) node->od_node + sizeof (befs_btree_nodehead));
  663 }
  664 
  665 /**
  666  * befs_bt_get_key - returns a pointer to the start of a key
  667  * @sb: filesystem superblock
  668  * @node: node in which to look for the key
  669  * @index: the index of the key to get
  670  * @keylen: modified to be the length of the key at @index
  671  *
  672  * Returns a valid pointer into @node on success.
  673  * Returns NULL on failure (bad input) and sets *@keylen = 0
  674  */
  675 static char *
  676 befs_bt_get_key(struct super_block *sb, befs_btree_node * node,
  677                 int index, u16 * keylen)
  678 {
  679         int prev_key_end;
  680         char *keystart;
  681         u16 *keylen_index;
  682 
  683         if (index < 0 || index > node->head.all_key_count) {
  684                 *keylen = 0;
  685                 return NULL;
  686         }
  687 
  688         keystart = befs_bt_keydata(node);
  689         keylen_index = befs_bt_keylen_index(node);
  690 
  691         if (index == 0)
  692                 prev_key_end = 0;
  693         else
  694                 prev_key_end = fs16_to_cpu(sb, keylen_index[index - 1]);
  695 
  696         *keylen = fs16_to_cpu(sb, keylen_index[index]) - prev_key_end;
  697 
  698         return keystart + prev_key_end;
  699 }
  700 
  701 /**
  702  * befs_compare_strings - compare two strings
  703  * @key1: pointer to the first key to be compared 
  704  * @keylen1: length in bytes of key1
  705  * @key2: pointer to the second key to be compared
  706  * @kelen2: lenght in bytes of key2
  707  *
  708  * Returns 0 if @key1 and @key2 are equal.
  709  * Returns >0 if @key1 is greater.
  710  * Returns <0 if @key2 is greater..
  711  */
  712 static int
  713 befs_compare_strings(const void *key1, int keylen1,
  714                      const void *key2, int keylen2)
  715 {
  716         int len = min_t(int, keylen1, keylen2);
  717         int result = strncmp(key1, key2, len);
  718         if (result == 0)
  719                 result = keylen1 - keylen2;
  720         return result;
  721 }
  722 
  723 /* These will be used for non-string keyed btrees */
  724 #if 0
  725 static int
  726 btree_compare_int32(cont void *key1, int keylen1, const void *key2, int keylen2)
  727 {
  728         return *(int32_t *) key1 - *(int32_t *) key2;
  729 }
  730 
  731 static int
  732 btree_compare_uint32(cont void *key1, int keylen1,
  733                      const void *key2, int keylen2)
  734 {
  735         if (*(u_int32_t *) key1 == *(u_int32_t *) key2)
  736                 return 0;
  737         else if (*(u_int32_t *) key1 > *(u_int32_t *) key2)
  738                 return 1;
  739 
  740         return -1;
  741 }
  742 static int
  743 btree_compare_int64(cont void *key1, int keylen1, const void *key2, int keylen2)
  744 {
  745         if (*(int64_t *) key1 == *(int64_t *) key2)
  746                 return 0;
  747         else if (*(int64_t *) key1 > *(int64_t *) key2)
  748                 return 1;
  749 
  750         return -1;
  751 }
  752 
  753 static int
  754 btree_compare_uint64(cont void *key1, int keylen1,
  755                      const void *key2, int keylen2)
  756 {
  757         if (*(u_int64_t *) key1 == *(u_int64_t *) key2)
  758                 return 0;
  759         else if (*(u_int64_t *) key1 > *(u_int64_t *) key2)
  760                 return 1;
  761 
  762         return -1;
  763 }
  764 
  765 static int
  766 btree_compare_float(cont void *key1, int keylen1, const void *key2, int keylen2)
  767 {
  768         float result = *(float *) key1 - *(float *) key2;
  769         if (result == 0.0f)
  770                 return 0;
  771 
  772         return (result < 0.0f) ? -1 : 1;
  773 }
  774 
  775 static int
  776 btree_compare_double(cont void *key1, int keylen1,
  777                      const void *key2, int keylen2)
  778 {
  779         double result = *(double *) key1 - *(double *) key2;
  780         if (result == 0.0)
  781                 return 0;
  782 
  783         return (result < 0.0) ? -1 : 1;
  784 }
  785 #endif                          //

Cache object: 4d62fe2c19eb0ceae34219e5d9602adb


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.