Subversion Repositories HelenOS

Rev

Rev 1164 | Rev 1196 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Copyright (C) 2006 Jakub Jermar
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  *
  9.  * - Redistributions of source code must retain the above copyright
  10.  *   notice, this list of conditions and the following disclaimer.
  11.  * - Redistributions in binary form must reproduce the above copyright
  12.  *   notice, this list of conditions and the following disclaimer in the
  13.  *   documentation and/or other materials provided with the distribution.
  14.  * - The name of the author may not be used to endorse or promote products
  15.  *   derived from this software without specific prior written permission.
  16.  *
  17.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18.  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20.  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23.  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24.  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25.  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26.  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27.  */
  28.  
  29. /*
  30.  * This B-tree has the following properties:
  31.  * - it is a ballanced 3-4-5 tree (i.e. BTREE_M = 5)
  32.  * - values (i.e. pointers to values) are stored only in leaves
  33.  * - leaves are linked in a list
  34.  * - technically, it is a B+tree (because of the previous properties)
  35.  *
  36.  * Be carefull when using these trees. They need to allocate
  37.  * and deallocate memory for their index nodes and as such
  38.  * can sleep.
  39.  */
  40.  
  41. #include <adt/btree.h>
  42. #include <adt/list.h>
  43. #include <mm/slab.h>
  44. #include <debug.h>
  45. #include <panic.h>
  46. #include <typedefs.h>
  47. #include <print.h>
  48.  
  49. static void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node);
  50. static void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node);
  51. static void node_initialize(btree_node_t *node);
  52. static void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree);
  53. static void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
  54. static void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key);
  55. static void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key);
  56. static btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median);
  57. static btree_node_t *node_combine(btree_node_t *node);
  58. static index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right);
  59. static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx);
  60. static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx);
  61. static bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
  62. static bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
  63. static bool try_rotation_from_left(btree_node_t *rnode);
  64. static bool try_rotation_from_right(btree_node_t *lnode);
  65.  
  66. #define ROOT_NODE(n)        (!(n)->parent)
  67. #define INDEX_NODE(n)       ((n)->subtree[0] != NULL)
  68. #define LEAF_NODE(n)        ((n)->subtree[0] == NULL)
  69.  
  70. #define FILL_FACTOR     ((BTREE_M-1)/2)
  71.  
  72. #define MEDIAN_LOW_INDEX(n) (((n)->keys-1)/2)
  73. #define MEDIAN_HIGH_INDEX(n)    ((n)->keys/2)
  74. #define MEDIAN_LOW(n)       ((n)->key[MEDIAN_LOW_INDEX((n))]);
  75. #define MEDIAN_HIGH(n)      ((n)->key[MEDIAN_HIGH_INDEX((n))]);
  76.  
  77. static slab_cache_t *btree_node_slab;
  78.  
  79. /** Initialize B-trees. */
  80. void btree_init(void)
  81. {
  82.     btree_node_slab = slab_cache_create("btree_node_slab", sizeof(btree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
  83. }
  84.  
  85. /** Create empty B-tree.
  86.  *
  87.  * @param t B-tree.
  88.  */
  89. void btree_create(btree_t *t)
  90. {
  91.     list_initialize(&t->leaf_head);
  92.     t->root = (btree_node_t *) slab_alloc(btree_node_slab, 0);
  93.     node_initialize(t->root);
  94.     list_append(&t->root->leaf_link, &t->leaf_head);
  95. }
  96.  
  97. /** Destroy empty B-tree. */
  98. void btree_destroy(btree_t *t)
  99. {
  100.     ASSERT(!t->root->keys);
  101.     slab_free(btree_node_slab, t->root);
  102. }
  103.  
  104. /** Insert key-value pair into B-tree.
  105.  *
  106.  * @param t B-tree.
  107.  * @param key Key to be inserted.
  108.  * @param value Value to be inserted.
  109.  * @param leaf_node Leaf node where the insertion should begin.
  110.  */
  111. void btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *leaf_node)
  112. {
  113.     btree_node_t *lnode;
  114.    
  115.     ASSERT(value);
  116.    
  117.     lnode = leaf_node;
  118.     if (!lnode) {
  119.         if (btree_search(t, key, &lnode)) {
  120.             panic("B-tree %P already contains key %d\n", t, key);
  121.         }
  122.     }
  123.    
  124.     _btree_insert(t, key, value, NULL, lnode);
  125. }
  126.  
  127. /** Recursively insert into B-tree.
  128.  *
  129.  * @param t B-tree.
  130.  * @param key Key to be inserted.
  131.  * @param value Value to be inserted.
  132.  * @param rsubtree Right subtree of the inserted key.
  133.  * @param node Start inserting into this node.
  134.  */
  135. void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node)
  136. {
  137.     if (node->keys < BTREE_MAX_KEYS) {
  138.         /*
  139.          * Node conatins enough space, the key can be stored immediately.
  140.          */
  141.         node_insert_key_and_rsubtree(node, key, value, rsubtree);
  142.     } else if (try_insert_by_rotation_to_left(node, key, value, rsubtree)) {
  143.         /*
  144.          * The key-value-rsubtree triplet has been inserted because
  145.          * some keys could have been moved to the left sibling.
  146.          */
  147.     } else if (try_insert_by_rotation_to_right(node, key, value, rsubtree)) {
  148.         /*
  149.          * The key-value-rsubtree triplet has been inserted because
  150.          * some keys could have been moved to the right sibling.
  151.          */
  152.     } else {
  153.         btree_node_t *rnode;
  154.         btree_key_t median;
  155.        
  156.         /*
  157.          * Node is full and both siblings (if both exist) are full too.
  158.          * Split the node and insert the smallest key from the node containing
  159.          * bigger keys (i.e. the new node) into its parent.
  160.          */
  161.  
  162.         rnode = node_split(node, key, value, rsubtree, &median);
  163.  
  164.         if (LEAF_NODE(node)) {
  165.             list_prepend(&rnode->leaf_link, &node->leaf_link);
  166.         }
  167.        
  168.         if (ROOT_NODE(node)) {
  169.             /*
  170.              * We split the root node. Create new root.
  171.              */
  172.             t->root = (btree_node_t *) slab_alloc(btree_node_slab, 0);
  173.             node->parent = t->root;
  174.             rnode->parent = t->root;
  175.             node_initialize(t->root);
  176.            
  177.             /*
  178.              * Left-hand side subtree will be the old root (i.e. node).
  179.              * Right-hand side subtree will be rnode.
  180.              */        
  181.             t->root->subtree[0] = node;
  182.  
  183.             t->root->depth = node->depth + 1;
  184.         }
  185.         _btree_insert(t, median, NULL, rnode, node->parent);
  186.     }  
  187.        
  188. }
  189.  
  190. /** Remove B-tree node.
  191.  *
  192.  * @param B-tree.
  193.  * @param key Key to be removed from the B-tree along with its associated value.
  194.  * @param leaf_node If not NULL, pointer to the leaf node where the key is found.
  195.  */
  196. void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node)
  197. {
  198.     btree_node_t *lnode;
  199.    
  200.     lnode = leaf_node;
  201.     if (!lnode) {
  202.         if (!btree_search(t, key, &lnode)) {
  203.             panic("B-tree %P does not contain key %d\n", t, key);
  204.         }
  205.     }
  206.    
  207.     _btree_remove(t, key, lnode);
  208. }
  209.  
  210. /** Recursively remove B-tree node.
  211.  *
  212.  * @param B-tree.
  213.  * @param key Key to be removed from the B-tree along with its associated value.
  214.  * @param node Node where the key being removed resides.
  215.  */
  216. void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node)
  217. {
  218.     if (ROOT_NODE(node)) {
  219.         if (node->keys == 1 && node->subtree[0]) {
  220.             /*
  221.              * Free the current root and set new root.
  222.              */
  223.             t->root = node->subtree[0];
  224.             t->root->parent = NULL;
  225.             slab_free(btree_node_slab, node);
  226.         } else {
  227.             /*
  228.              * Remove the key from the root node.
  229.              * Note that the right subtree is removed because when
  230.              * combining two nodes, the left-side sibling is preserved
  231.              * and the right-side sibling is freed.
  232.              */
  233.             node_remove_key_and_rsubtree(node, key);
  234.         }
  235.         return;
  236.     }
  237.    
  238.     if (node->keys <= FILL_FACTOR) {
  239.         /*
  240.          * If the node is below the fill factor,
  241.          * try to borrow keys from left or right sibling.
  242.          */
  243.         if (!try_rotation_from_left(node))
  244.             try_rotation_from_right(node);
  245.     }
  246.    
  247.     if (node->keys > FILL_FACTOR) {
  248.         int i;
  249.  
  250.         /*
  251.          * The key can be immediatelly removed.
  252.          *
  253.          * Note that the right subtree is removed because when
  254.          * combining two nodes, the left-side sibling is preserved
  255.          * and the right-side sibling is freed.
  256.          */
  257.         node_remove_key_and_rsubtree(node, key);
  258.         for (i = 0; i < node->parent->keys; i++) {
  259.             if (node->parent->key[i] == key)
  260.                 node->parent->key[i] = node->key[0];
  261.         }
  262.        
  263.     } else {
  264.         index_t idx;
  265.         btree_node_t *rnode, *parent;
  266.  
  267.         /*
  268.          * The node is below the fill factor as well as its left and right sibling.
  269.          * Resort to combining the node with one of its siblings.
  270.          * The node which is on the left is preserved and the node on the right is
  271.          * freed.
  272.          */
  273.         parent = node->parent;
  274.         node_remove_key_and_rsubtree(node, key);
  275.         rnode = node_combine(node);
  276.         if (LEAF_NODE(rnode))
  277.             list_remove(&rnode->leaf_link);
  278.         idx = find_key_by_subtree(parent, rnode, true);
  279.         ASSERT((int) idx != -1);
  280.         slab_free(btree_node_slab, rnode);
  281.         _btree_remove(t, parent->key[idx], parent);
  282.     }
  283. }
  284.  
  285. /** Search key in a B-tree.
  286.  *
  287.  * @param t B-tree.
  288.  * @param key Key to be searched.
  289.  * @param leaf_node Address where to put pointer to visited leaf node.
  290.  *
  291.  * @return Pointer to value or NULL if there is no such key.
  292.  */
  293. void *btree_search(btree_t *t, btree_key_t key, btree_node_t **leaf_node)
  294. {
  295.     btree_node_t *cur, *next;
  296.    
  297.     /*
  298.      * Iteratively descend to the leaf that can contain the searched key.
  299.      */
  300.     for (cur = t->root; cur; cur = next) {
  301.  
  302.         /* Last iteration will set this with proper leaf node address. */
  303.         *leaf_node = cur;
  304.        
  305.         /*
  306.          * The key can be in the leftmost subtree.
  307.          * Test it separately.
  308.          */
  309.         if (key < cur->key[0]) {
  310.             next = cur->subtree[0];
  311.             continue;
  312.         } else {
  313.             void *val;
  314.             int i;
  315.        
  316.             /*
  317.              * Now if the key is smaller than cur->key[i]
  318.              * it can only mean that the value is in cur->subtree[i]
  319.              * or it is not in the tree at all.
  320.              */
  321.             for (i = 1; i < cur->keys; i++) {
  322.                 if (key < cur->key[i]) {
  323.                     next = cur->subtree[i];
  324.                     val = cur->value[i - 1];
  325.  
  326.                     if (LEAF_NODE(cur))
  327.                         return key == cur->key[i - 1] ? val : NULL;
  328.  
  329.                     goto descend;
  330.                 }
  331.             }
  332.            
  333.             /*
  334.              * Last possibility is that the key is in the rightmost subtree.
  335.              */
  336.             next = cur->subtree[i];
  337.             val = cur->value[i - 1];
  338.             if (LEAF_NODE(cur))
  339.                 return key == cur->key[i - 1] ? val : NULL;
  340.         }
  341.         descend:
  342.             ;
  343.     }
  344.  
  345.     /*
  346.      * The key was not found in the *leaf_node and is smaller than any of its keys.
  347.      */
  348.     return NULL;
  349. }
  350.  
  351. /** Return pointer to B-tree leaf node's left neighbour.
  352.  *
  353.  * @param t B-tree.
  354.  * @param node Node whose left neighbour will be returned.
  355.  *
  356.  * @return Left neighbour of the node or NULL if the node does not have the left neighbour.
  357.  */
  358. btree_node_t *btree_leaf_node_left_neighbour(btree_t *t, btree_node_t *node)
  359. {
  360.     ASSERT(LEAF_NODE(node));
  361.     if (node->leaf_link.prev != &t->leaf_head)
  362.         return list_get_instance(node->leaf_link.prev, btree_node_t, leaf_link);
  363.     else
  364.         return NULL;
  365. }
  366.  
  367. /** Return pointer to B-tree leaf node's right neighbour.
  368.  *
  369.  * @param t B-tree.
  370.  * @param node Node whose right neighbour will be returned.
  371.  *
  372.  * @return Right neighbour of the node or NULL if the node does not have the right neighbour.
  373.  */
  374. btree_node_t *btree_leaf_node_right_neighbour(btree_t *t, btree_node_t *node)
  375. {
  376.     ASSERT(LEAF_NODE(node));
  377.     if (node->leaf_link.next != &t->leaf_head)
  378.         return list_get_instance(node->leaf_link.next, btree_node_t, leaf_link);
  379.     else
  380.         return NULL;
  381. }
  382.  
  383. /** Initialize B-tree node.
  384.  *
  385.  * @param node B-tree node.
  386.  */
  387. void node_initialize(btree_node_t *node)
  388. {
  389.     int i;
  390.  
  391.     node->keys = 0;
  392.    
  393.     /* Clean also space for the extra key. */
  394.     for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {
  395.         node->key[i] = 0;
  396.         node->value[i] = NULL;
  397.         node->subtree[i] = NULL;
  398.     }
  399.     node->subtree[i] = NULL;
  400.    
  401.     node->parent = NULL;
  402.    
  403.     link_initialize(&node->leaf_link);
  404.  
  405.     link_initialize(&node->bfs_link);
  406.     node->depth = 0;
  407. }
  408.  
  409. /** Insert key-value-lsubtree triplet into B-tree node.
  410.  *
  411.  * It is actually possible to have more keys than BTREE_MAX_KEYS.
  412.  * This feature is used during insert by right rotation.
  413.  *
  414.  * @param node B-tree node into wich the new key is to be inserted.
  415.  * @param key The key to be inserted.
  416.  * @param value Pointer to value to be inserted.
  417.  * @param lsubtree Pointer to the left subtree.
  418.  */
  419. void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree)
  420. {
  421.     int i;
  422.  
  423.     for (i = 0; i < node->keys; i++) {
  424.         if (key < node->key[i]) {
  425.             int j;
  426.        
  427.             for (j = node->keys; j > i; j--) {
  428.                 node->key[j] = node->key[j - 1];
  429.                 node->value[j] = node->value[j - 1];
  430.                 node->subtree[j + 1] = node->subtree[j];
  431.             }
  432.             node->subtree[j + 1] = node->subtree[j];
  433.             break; 
  434.         }
  435.     }
  436.     node->key[i] = key;
  437.     node->value[i] = value;
  438.     node->subtree[i] = lsubtree;
  439.            
  440.     node->keys++;
  441. }
  442.  
  443. /** Insert key-value-rsubtree triplet into B-tree node.
  444.  *
  445.  * It is actually possible to have more keys than BTREE_MAX_KEYS.
  446.  * This feature is used during splitting the node when the
  447.  * number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation
  448.  * also makes use of this feature.
  449.  *
  450.  * @param node B-tree node into wich the new key is to be inserted.
  451.  * @param key The key to be inserted.
  452.  * @param value Pointer to value to be inserted.
  453.  * @param rsubtree Pointer to the right subtree.
  454.  */
  455. void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree)
  456. {
  457.     int i;
  458.  
  459.     for (i = 0; i < node->keys; i++) {
  460.         if (key < node->key[i]) {
  461.             int j;
  462.        
  463.             for (j = node->keys; j > i; j--) {
  464.                 node->key[j] = node->key[j - 1];
  465.                 node->value[j] = node->value[j - 1];
  466.                 node->subtree[j + 1] = node->subtree[j];
  467.             }
  468.             break; 
  469.         }
  470.     }
  471.     node->key[i] = key;
  472.     node->value[i] = value;
  473.     node->subtree[i + 1] = rsubtree;
  474.            
  475.     node->keys++;
  476. }
  477.  
  478. /** Remove key and its left subtree pointer from B-tree node.
  479.  *
  480.  * Remove the key and eliminate gaps in node->key array.
  481.  * Note that the value pointer and the left subtree pointer
  482.  * is removed from the node as well.
  483.  *
  484.  * @param node B-tree node.
  485.  * @param key Key to be removed.
  486.  */
  487. void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
  488. {
  489.     int i, j;
  490.    
  491.     for (i = 0; i < node->keys; i++) {
  492.         if (key == node->key[i]) {
  493.             for (j = i + 1; j < node->keys; j++) {
  494.                 node->key[j - 1] = node->key[j];
  495.                 node->value[j - 1] = node->value[j];
  496.                 node->subtree[j - 1] = node->subtree[j];
  497.             }
  498.             node->subtree[j - 1] = node->subtree[j];
  499.             node->keys--;
  500.             return;
  501.         }
  502.     }
  503.     panic("node %P does not contain key %d\n", node, key);
  504. }
  505.  
  506. /** Remove key and its right subtree pointer from B-tree node.
  507.  *
  508.  * Remove the key and eliminate gaps in node->key array.
  509.  * Note that the value pointer and the right subtree pointer
  510.  * is removed from the node as well.
  511.  *
  512.  * @param node B-tree node.
  513.  * @param key Key to be removed.
  514.  */
  515. void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
  516. {
  517.     int i, j;
  518.    
  519.     for (i = 0; i < node->keys; i++) {
  520.         if (key == node->key[i]) {
  521.             for (j = i + 1; j < node->keys; j++) {
  522.                 node->key[j - 1] = node->key[j];
  523.                 node->value[j - 1] = node->value[j];
  524.                 node->subtree[j] = node->subtree[j + 1];
  525.             }
  526.             node->keys--;
  527.             return;
  528.         }
  529.     }
  530.     panic("node %P does not contain key %d\n", node, key);
  531. }
  532.  
  533. /** Split full B-tree node and insert new key-value-right-subtree triplet.
  534.  *
  535.  * This function will split a node and return pointer to a newly created
  536.  * node containing keys greater than or equal to the greater of medians
  537.  * (or median) of the old keys and the newly added key. It will also write
  538.  * the median key to a memory address supplied by the caller.
  539.  *
  540.  * If the node being split is an index node, the median will not be
  541.  * included in the new node. If the node is a leaf node,
  542.  * the median will be copied there.
  543.  *
  544.  * @param node B-tree node wich is going to be split.
  545.  * @param key The key to be inserted.
  546.  * @param value Pointer to the value to be inserted.
  547.  * @param rsubtree Pointer to the right subtree of the key being added.
  548.  * @param median Address in memory, where the median key will be stored.
  549.  *
  550.  * @return Newly created right sibling of node.
  551.  */
  552. btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median)
  553. {
  554.     btree_node_t *rnode;
  555.     int i, j;
  556.  
  557.     ASSERT(median);
  558.     ASSERT(node->keys == BTREE_MAX_KEYS);
  559.  
  560.     /*
  561.      * Use the extra space to store the extra node.
  562.      */
  563.     node_insert_key_and_rsubtree(node, key, value, rsubtree);
  564.  
  565.     /*
  566.      * Compute median of keys.
  567.      */
  568.     *median = MEDIAN_HIGH(node);
  569.        
  570.     /*
  571.      * Allocate and initialize new right sibling.
  572.      */
  573.     rnode = (btree_node_t *) slab_alloc(btree_node_slab, 0);
  574.     node_initialize(rnode);
  575.     rnode->parent = node->parent;
  576.     rnode->depth = node->depth;
  577.    
  578.     /*
  579.      * Copy big keys, values and subtree pointers to the new right sibling.
  580.      * If this is an index node, do not copy the median.
  581.      */
  582.     i = (int) INDEX_NODE(node);
  583.     for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
  584.         rnode->key[j] = node->key[i];
  585.         rnode->value[j] = node->value[i];
  586.         rnode->subtree[j] = node->subtree[i];
  587.        
  588.         /*
  589.          * Fix parent links in subtrees.
  590.          */
  591.         if (rnode->subtree[j])
  592.             rnode->subtree[j]->parent = rnode;
  593.            
  594.     }
  595.     rnode->subtree[j] = node->subtree[i];
  596.     if (rnode->subtree[j])
  597.         rnode->subtree[j]->parent = rnode;
  598.  
  599.     rnode->keys = j;    /* Set number of keys of the new node. */
  600.     node->keys /= 2;    /* Shrink the old node. */
  601.        
  602.     return rnode;
  603. }
  604.  
  605. /** Combine node with any of its siblings.
  606.  *
  607.  * The siblings are required to be below the fill factor.
  608.  *
  609.  * @param node Node to combine with one of its siblings.
  610.  *
  611.  * @return Pointer to the rightmost of the two nodes.
  612.  */
  613. btree_node_t *node_combine(btree_node_t *node)
  614. {
  615.     index_t idx;
  616.     btree_node_t *rnode;
  617.     int i;
  618.  
  619.     ASSERT(!ROOT_NODE(node));
  620.    
  621.     idx = find_key_by_subtree(node->parent, node, false);
  622.     if (idx == node->parent->keys) {
  623.         /*
  624.          * Rightmost subtree of its parent, combine with the left sibling.
  625.          */
  626.         idx--;
  627.         rnode = node;
  628.         node = node->parent->subtree[idx];
  629.     } else {
  630.         rnode = node->parent->subtree[idx + 1];
  631.     }
  632.  
  633.     /* Index nodes need to insert parent node key in between left and right node. */
  634.     if (INDEX_NODE(node))
  635.         node->key[node->keys++] = node->parent->key[idx];
  636.    
  637.     /* Copy the key-value-subtree triplets from the right node. */
  638.     for (i = 0; i < rnode->keys; i++) {
  639.         node->key[node->keys + i] = rnode->key[i];
  640.         node->value[node->keys + i] = rnode->value[i];
  641.         if (INDEX_NODE(node)) {
  642.             node->subtree[node->keys + i] = rnode->subtree[i];
  643.             rnode->subtree[i]->parent = node;
  644.         }
  645.     }
  646.     if (INDEX_NODE(node)) {
  647.         node->subtree[node->keys + i] = rnode->subtree[i];
  648.         rnode->subtree[i]->parent = node;
  649.     }
  650.  
  651.     node->keys += rnode->keys;
  652.  
  653.     return rnode;
  654. }
  655.  
  656. /** Find key by its left or right subtree.
  657.  *
  658.  * @param node B-tree node.
  659.  * @param subtree Left or right subtree of a key found in node.
  660.  * @param right If true, subtree is a right subtree. If false, subtree is a left subtree.
  661.  *
  662.  * @return Index of the key associated with the subtree.
  663.  */
  664. index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right)
  665. {
  666.     int i;
  667.    
  668.     for (i = 0; i < node->keys + 1; i++) {
  669.         if (subtree == node->subtree[i])
  670.             return i - (int) (right != false);
  671.     }
  672.     panic("node %P does not contain subtree %P\n", node, subtree);
  673. }
  674.  
  675. /** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling.
  676.  *
  677.  * The biggest key and its value and right subtree is rotated from the left node
  678.  * to the right. If the node is an index node, than the parent node key belonging to
  679.  * the left node takes part in the rotation.
  680.  *
  681.  * @param lnode Left sibling.
  682.  * @param rnode Right sibling.
  683.  * @param idx Index of the parent node key that is taking part in the rotation.
  684.  */
  685. void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx)
  686. {
  687.     btree_key_t key;
  688.  
  689.     key = lnode->key[lnode->keys - 1];
  690.        
  691.     if (LEAF_NODE(lnode)) {
  692.         void *value;
  693.  
  694.         value = lnode->value[lnode->keys - 1];
  695.         node_remove_key_and_rsubtree(lnode, key);
  696.         node_insert_key_and_lsubtree(rnode, key, value, NULL);
  697.         lnode->parent->key[idx] = key;
  698.     } else {
  699.         btree_node_t *rsubtree;
  700.  
  701.         rsubtree = lnode->subtree[lnode->keys];
  702.         node_remove_key_and_rsubtree(lnode, key);
  703.         node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree);
  704.         lnode->parent->key[idx] = key;
  705.  
  706.         /* Fix parent link of the reconnected right subtree. */
  707.         rsubtree->parent = rnode;
  708.     }
  709.  
  710. }
  711.  
  712. /** Rotate one key-value-lsubtree triplet from the right sibling to the left sibling.
  713.  *
  714.  * The smallest key and its value and left subtree is rotated from the right node
  715.  * to the left. If the node is an index node, than the parent node key belonging to
  716.  * the right node takes part in the rotation.
  717.  *
  718.  * @param lnode Left sibling.
  719.  * @param rnode Right sibling.
  720.  * @param idx Index of the parent node key that is taking part in the rotation.
  721.  */
  722. void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx)
  723. {
  724.     btree_key_t key;
  725.  
  726.     key = rnode->key[0];
  727.        
  728.     if (LEAF_NODE(rnode)) {
  729.         void *value;
  730.  
  731.         value = rnode->value[0];
  732.         node_remove_key_and_lsubtree(rnode, key);
  733.         node_insert_key_and_rsubtree(lnode, key, value, NULL);
  734.         rnode->parent->key[idx] = rnode->key[0];
  735.     } else {
  736.         btree_node_t *lsubtree;
  737.  
  738.         lsubtree = rnode->subtree[0];
  739.         node_remove_key_and_lsubtree(rnode, key);
  740.         node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree);
  741.         rnode->parent->key[idx] = key;
  742.  
  743.         /* Fix parent link of the reconnected left subtree. */
  744.         lsubtree->parent = lnode;
  745.     }
  746.  
  747. }
  748.  
  749. /** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done.
  750.  *
  751.  * Left sibling of the node (if it exists) is checked for free space.
  752.  * If there is free space, the key is inserted and the smallest key of
  753.  * the node is moved there. The index node which is the parent of both
  754.  * nodes is fixed.
  755.  *
  756.  * @param node B-tree node.
  757.  * @param inskey Key to be inserted.
  758.  * @param insvalue Value to be inserted.
  759.  * @param rsubtree Right subtree of inskey.
  760.  *
  761.  * @return True if the rotation was performed, false otherwise.
  762.  */
  763. bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
  764. {
  765.     index_t idx;
  766.     btree_node_t *lnode;
  767.  
  768.     /*
  769.      * If this is root node, the rotation can not be done.
  770.      */
  771.     if (ROOT_NODE(node))
  772.         return false;
  773.    
  774.     idx = find_key_by_subtree(node->parent, node, true);
  775.     if ((int) idx == -1) {
  776.         /*
  777.          * If this node is the leftmost subtree of its parent,
  778.          * the rotation can not be done.
  779.          */
  780.         return false;
  781.     }
  782.        
  783.     lnode = node->parent->subtree[idx];
  784.     if (lnode->keys < BTREE_MAX_KEYS) {
  785.         /*
  786.          * The rotaion can be done. The left sibling has free space.
  787.          */
  788.         node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
  789.         rotate_from_right(lnode, node, idx);
  790.         return true;
  791.     }
  792.  
  793.     return false;
  794. }
  795.  
  796. /** Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done.
  797.  *
  798.  * Right sibling of the node (if it exists) is checked for free space.
  799.  * If there is free space, the key is inserted and the biggest key of
  800.  * the node is moved there. The index node which is the parent of both
  801.  * nodes is fixed.
  802.  *
  803.  * @param node B-tree node.
  804.  * @param inskey Key to be inserted.
  805.  * @param insvalue Value to be inserted.
  806.  * @param rsubtree Right subtree of inskey.
  807.  *
  808.  * @return True if the rotation was performed, false otherwise.
  809.  */
  810. bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
  811. {
  812.     index_t idx;
  813.     btree_node_t *rnode;
  814.  
  815.     /*
  816.      * If this is root node, the rotation can not be done.
  817.      */
  818.     if (ROOT_NODE(node))
  819.         return false;
  820.    
  821.     idx = find_key_by_subtree(node->parent, node, false);
  822.     if (idx == node->parent->keys) {
  823.         /*
  824.          * If this node is the rightmost subtree of its parent,
  825.          * the rotation can not be done.
  826.          */
  827.         return false;
  828.     }
  829.        
  830.     rnode = node->parent->subtree[idx + 1];
  831.     if (rnode->keys < BTREE_MAX_KEYS) {
  832.         /*
  833.          * The rotaion can be done. The right sibling has free space.
  834.          */
  835.         node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
  836.         rotate_from_left(node, rnode, idx);
  837.         return true;
  838.     }
  839.  
  840.     return false;
  841. }
  842.  
  843. /** Rotate in a key from the left sibling or from the index node, if this operation can be done.
  844.  *
  845.  * @param rnode Node into which to add key from its left sibling or from the index node.
  846.  *
  847.  * @return True if the rotation was performed, false otherwise.
  848.  */
  849. bool try_rotation_from_left(btree_node_t *rnode)
  850. {
  851.     index_t idx;
  852.     btree_node_t *lnode;
  853.  
  854.     /*
  855.      * If this is root node, the rotation can not be done.
  856.      */
  857.     if (ROOT_NODE(rnode))
  858.         return false;
  859.    
  860.     idx = find_key_by_subtree(rnode->parent, rnode, true);
  861.     if ((int) idx == -1) {
  862.         /*
  863.          * If this node is the leftmost subtree of its parent,
  864.          * the rotation can not be done.
  865.          */
  866.         return false;
  867.     }
  868.        
  869.     lnode = rnode->parent->subtree[idx];
  870.     if (lnode->keys > FILL_FACTOR) {
  871.         rotate_from_left(lnode, rnode, idx);
  872.         return true;
  873.     }
  874.    
  875.     return false;
  876. }
  877.  
  878. /** Rotate in a key from the right sibling or from the index node, if this operation can be done.
  879.  *
  880.  * @param rnode Node into which to add key from its right sibling or from the index node.
  881.  *
  882.  * @return True if the rotation was performed, false otherwise.
  883.  */
  884. bool try_rotation_from_right(btree_node_t *lnode)
  885. {
  886.     index_t idx;
  887.     btree_node_t *rnode;
  888.  
  889.     /*
  890.      * If this is root node, the rotation can not be done.
  891.      */
  892.     if (ROOT_NODE(lnode))
  893.         return false;
  894.    
  895.     idx = find_key_by_subtree(lnode->parent, lnode, false);
  896.     if (idx == lnode->parent->keys) {
  897.         /*
  898.          * If this node is the rightmost subtree of its parent,
  899.          * the rotation can not be done.
  900.          */
  901.         return false;
  902.     }
  903.        
  904.     rnode = lnode->parent->subtree[idx + 1];
  905.     if (rnode->keys > FILL_FACTOR) {
  906.         rotate_from_right(lnode, rnode, idx);
  907.         return true;
  908.     }  
  909.  
  910.     return false;
  911. }
  912.  
  913. /** Print B-tree.
  914.  *
  915.  * @param t Print out B-tree.
  916.  */
  917. void btree_print(btree_t *t)
  918. {
  919.     int i, depth = t->root->depth;
  920.     link_t head, *cur;
  921.  
  922.     printf("Printing B-tree:\n");
  923.     list_initialize(&head);
  924.     list_append(&t->root->bfs_link, &head);
  925.  
  926.     /*
  927.      * Use BFS search to print out the tree.
  928.      * Levels are distinguished from one another by node->depth.
  929.      */
  930.     while (!list_empty(&head)) {
  931.         link_t *hlp;
  932.         btree_node_t *node;
  933.        
  934.         hlp = head.next;
  935.         ASSERT(hlp != &head);
  936.         node = list_get_instance(hlp, btree_node_t, bfs_link);
  937.         list_remove(hlp);
  938.        
  939.         ASSERT(node);
  940.        
  941.         if (node->depth != depth) {
  942.             printf("\n");
  943.             depth = node->depth;
  944.         }
  945.  
  946.         printf("(");
  947.         for (i = 0; i < node->keys; i++) {
  948.             printf("%d%s", node->key[i], i < node->keys - 1 ? "," : "");
  949.             if (node->depth && node->subtree[i]) {
  950.                 list_append(&node->subtree[i]->bfs_link, &head);
  951.             }
  952.         }
  953.         if (node->depth && node->subtree[i]) {
  954.             list_append(&node->subtree[i]->bfs_link, &head);
  955.         }
  956.         printf(")");
  957.     }
  958.     printf("\n");
  959.    
  960.     printf("Printing list of leaves:\n");
  961.     for (cur = t->leaf_head.next; cur != &t->leaf_head; cur = cur->next) {
  962.         btree_node_t *node;
  963.        
  964.         node = list_get_instance(cur, btree_node_t, leaf_link);
  965.        
  966.         ASSERT(node);
  967.  
  968.         printf("(");
  969.         for (i = 0; i < node->keys; i++)
  970.             printf("%d%s", node->key[i], i < node->keys - 1 ? "," : "");
  971.         printf(")");
  972.     }
  973.     printf("\n");
  974. }
  975.