Subversion Repositories HelenOS-historic

Rev

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