Subversion Repositories HelenOS-historic

Rev

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