Subversion Repositories HelenOS-historic

Rev

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