Subversion Repositories HelenOS

Rev

Rev 1142 | Rev 1147 | 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. /** Initialize B-tree node.
  344.  *
  345.  * @param node B-tree node.
  346.  */
  347. void node_initialize(btree_node_t *node)
  348. {
  349.     int i;
  350.  
  351.     node->keys = 0;
  352.    
  353.     /* Clean also space for the extra key. */
  354.     for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {
  355.         node->key[i] = 0;
  356.         node->value[i] = NULL;
  357.         node->subtree[i] = NULL;
  358.     }
  359.     node->subtree[i] = NULL;
  360.    
  361.     node->parent = NULL;
  362.    
  363.     link_initialize(&node->leaf_link);
  364.  
  365.     link_initialize(&node->bfs_link);
  366.     node->depth = 0;
  367. }
  368.  
  369. /** Insert key-value-lsubtree triplet into B-tree node.
  370.  *
  371.  * It is actually possible to have more keys than BTREE_MAX_KEYS.
  372.  * This feature is used during insert by right rotation.
  373.  *
  374.  * @param node B-tree node into wich the new key is to be inserted.
  375.  * @param key The key to be inserted.
  376.  * @param value Pointer to value to be inserted.
  377.  * @param lsubtree Pointer to the left subtree.
  378.  */
  379. void node_insert_key_and_lsubtree(btree_node_t *node, __native key, void *value, btree_node_t *lsubtree)
  380. {
  381.     int i;
  382.  
  383.     for (i = 0; i < node->keys; i++) {
  384.         if (key < node->key[i]) {
  385.             int j;
  386.        
  387.             for (j = node->keys; j > i; j--) {
  388.                 node->key[j] = node->key[j - 1];
  389.                 node->value[j] = node->value[j - 1];
  390.                 node->subtree[j + 1] = node->subtree[j];
  391.             }
  392.             node->subtree[j + 1] = node->subtree[j];
  393.             break; 
  394.         }
  395.     }
  396.     node->key[i] = key;
  397.     node->value[i] = value;
  398.     node->subtree[i] = lsubtree;
  399.            
  400.     node->keys++;
  401. }
  402.  
  403. /** Insert key-value-rsubtree triplet into B-tree node.
  404.  *
  405.  * It is actually possible to have more keys than BTREE_MAX_KEYS.
  406.  * This feature is used during splitting the node when the
  407.  * number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation
  408.  * also makes use of this feature.
  409.  *
  410.  * @param node B-tree node into wich the new key is to be inserted.
  411.  * @param key The key to be inserted.
  412.  * @param value Pointer to value to be inserted.
  413.  * @param rsubtree Pointer to the right subtree.
  414.  */
  415. void node_insert_key_and_rsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree)
  416. {
  417.     int i;
  418.  
  419.     for (i = 0; i < node->keys; i++) {
  420.         if (key < node->key[i]) {
  421.             int j;
  422.        
  423.             for (j = node->keys; j > i; j--) {
  424.                 node->key[j] = node->key[j - 1];
  425.                 node->value[j] = node->value[j - 1];
  426.                 node->subtree[j + 1] = node->subtree[j];
  427.             }
  428.             break; 
  429.         }
  430.     }
  431.     node->key[i] = key;
  432.     node->value[i] = value;
  433.     node->subtree[i + 1] = rsubtree;
  434.            
  435.     node->keys++;
  436. }
  437.  
  438. /** Remove key and its left subtree pointer from B-tree node.
  439.  *
  440.  * Remove the key and eliminate gaps in node->key array.
  441.  * Note that the value pointer and the left subtree pointer
  442.  * is removed from the node as well.
  443.  *
  444.  * @param node B-tree node.
  445.  * @param key Key to be removed.
  446.  */
  447. void node_remove_key_and_lsubtree(btree_node_t *node, __native key)
  448. {
  449.     int i, j;
  450.    
  451.     for (i = 0; i < node->keys; i++) {
  452.         if (key == node->key[i]) {
  453.             for (j = i + 1; j < node->keys; j++) {
  454.                 node->key[j - 1] = node->key[j];
  455.                 node->value[j - 1] = node->value[j];
  456.                 node->subtree[j - 1] = node->subtree[j];
  457.             }
  458.             node->subtree[j - 1] = node->subtree[j];
  459.             node->keys--;
  460.             return;
  461.         }
  462.     }
  463.     panic("node %P does not contain key %d\n", node, key);
  464. }
  465.  
  466. /** Remove key and its right subtree pointer from B-tree node.
  467.  *
  468.  * Remove the key and eliminate gaps in node->key array.
  469.  * Note that the value pointer and the right subtree pointer
  470.  * is removed from the node as well.
  471.  *
  472.  * @param node B-tree node.
  473.  * @param key Key to be removed.
  474.  */
  475. void node_remove_key_and_rsubtree(btree_node_t *node, __native key)
  476. {
  477.     int i, j;
  478.    
  479.     for (i = 0; i < node->keys; i++) {
  480.         if (key == node->key[i]) {
  481.             for (j = i + 1; j < node->keys; j++) {
  482.                 node->key[j - 1] = node->key[j];
  483.                 node->value[j - 1] = node->value[j];
  484.                 node->subtree[j] = node->subtree[j + 1];
  485.             }
  486.             node->keys--;
  487.             return;
  488.         }
  489.     }
  490.     panic("node %P does not contain key %d\n", node, key);
  491. }
  492.  
  493. /** Split full B-tree node and insert new key-value-right-subtree triplet.
  494.  *
  495.  * This function will split a node and return pointer to a newly created
  496.  * node containing keys greater than or equal to the greater of medians
  497.  * (or median) of the old keys and the newly added key. It will also write
  498.  * the median key to a memory address supplied by the caller.
  499.  *
  500.  * If the node being split is an index node, the median will not be
  501.  * included in the new node. If the node is a leaf node,
  502.  * the median will be copied there.
  503.  *
  504.  * @param node B-tree node wich is going to be split.
  505.  * @param key The key to be inserted.
  506.  * @param value Pointer to the value to be inserted.
  507.  * @param rsubtree Pointer to the right subtree of the key being added.
  508.  * @param median Address in memory, where the median key will be stored.
  509.  *
  510.  * @return Newly created right sibling of node.
  511.  */
  512. btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median)
  513. {
  514.     btree_node_t *rnode;
  515.     int i, j;
  516.  
  517.     ASSERT(median);
  518.     ASSERT(node->keys == BTREE_MAX_KEYS);
  519.  
  520.     /*
  521.      * Use the extra space to store the extra node.
  522.      */
  523.     node_insert_key_and_rsubtree(node, key, value, rsubtree);
  524.  
  525.     /*
  526.      * Compute median of keys.
  527.      */
  528.     *median = MEDIAN_HIGH(node);
  529.        
  530.     /*
  531.      * Allocate and initialize new right sibling.
  532.      */
  533.     rnode = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
  534.     node_initialize(rnode);
  535.     rnode->parent = node->parent;
  536.     rnode->depth = node->depth;
  537.    
  538.     /*
  539.      * Copy big keys, values and subtree pointers to the new right sibling.
  540.      * If this is an index node, do not copy the median.
  541.      */
  542.     i = (int) INDEX_NODE(node);
  543.     for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
  544.         rnode->key[j] = node->key[i];
  545.         rnode->value[j] = node->value[i];
  546.         rnode->subtree[j] = node->subtree[i];
  547.        
  548.         /*
  549.          * Fix parent links in subtrees.
  550.          */
  551.         if (rnode->subtree[j])
  552.             rnode->subtree[j]->parent = rnode;
  553.            
  554.     }
  555.     rnode->subtree[j] = node->subtree[i];
  556.     if (rnode->subtree[j])
  557.         rnode->subtree[j]->parent = rnode;
  558.  
  559.     rnode->keys = j;    /* Set number of keys of the new node. */
  560.     node->keys /= 2;    /* Shrink the old node. */
  561.        
  562.     return rnode;
  563. }
  564.  
  565. /** Combine node with any of its siblings.
  566.  *
  567.  * The siblings are required to be below the fill factor.
  568.  *
  569.  * @param node Node to combine with one of its siblings.
  570.  *
  571.  * @return Pointer to the rightmost of the two nodes.
  572.  */
  573. btree_node_t *node_combine(btree_node_t *node)
  574. {
  575.     index_t idx;
  576.     btree_node_t *rnode;
  577.     int i;
  578.  
  579.     ASSERT(!ROOT_NODE(node));
  580.    
  581.     idx = find_key_by_subtree(node->parent, node, false);
  582.     if (idx == node->parent->keys) {
  583.         /*
  584.          * Rightmost subtree of its parent, combine with the left sibling.
  585.          */
  586.         idx--;
  587.         rnode = node;
  588.         node = node->parent->subtree[idx];
  589.     } else {
  590.         rnode = node->parent->subtree[idx + 1];
  591.     }
  592.  
  593.     /* Index nodes need to insert parent node key in between left and right node. */
  594.     if (INDEX_NODE(node))
  595.         node->key[node->keys++] = node->parent->key[idx];
  596.    
  597.     /* Copy the key-value-subtree triplets from the right node. */
  598.     for (i = 0; i < rnode->keys; i++) {
  599.         node->key[node->keys + i] = rnode->key[i];
  600.         node->value[node->keys + i] = rnode->value[i];
  601.         if (INDEX_NODE(node)) {
  602.             node->subtree[node->keys + i] = rnode->subtree[i];
  603.             rnode->subtree[i]->parent = node;
  604.         }
  605.     }
  606.     if (INDEX_NODE(node)) {
  607.         node->subtree[node->keys + i] = rnode->subtree[i];
  608.         rnode->subtree[i]->parent = node;
  609.     }
  610.  
  611.     node->keys += rnode->keys;
  612.  
  613.     return rnode;
  614. }
  615.  
  616. /** Find key by its left or right subtree.
  617.  *
  618.  * @param node B-tree node.
  619.  * @param subtree Left or right subtree of a key found in node.
  620.  * @param right If true, subtree is a right subtree. If false, subtree is a left subtree.
  621.  *
  622.  * @return Index of the key associated with the subtree.
  623.  */
  624. index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right)
  625. {
  626.     int i;
  627.    
  628.     for (i = 0; i < node->keys + 1; i++) {
  629.         if (subtree == node->subtree[i])
  630.             return i - (int) (right != false);
  631.     }
  632.     panic("node %P does not contain subtree %P\n", node, subtree);
  633. }
  634.  
  635. /** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling.
  636.  *
  637.  * The biggest key and its value and right subtree is rotated from the left node
  638.  * to the right. If the node is an index node, than the parent node key belonging to
  639.  * the left node takes part in the rotation.
  640.  *
  641.  * @param lnode Left sibling.
  642.  * @param rnode Right sibling.
  643.  * @param idx Index of the parent node key that is taking part in the rotation.
  644.  */
  645. void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx)
  646. {
  647.     __native key;
  648.  
  649.     key = lnode->key[lnode->keys - 1];
  650.        
  651.     if (LEAF_NODE(lnode)) {
  652.         void *value;
  653.  
  654.         value = lnode->value[lnode->keys - 1];
  655.         node_remove_key_and_rsubtree(lnode, key);
  656.         node_insert_key_and_lsubtree(rnode, key, value, NULL);
  657.         lnode->parent->key[idx] = key;
  658.     } else {
  659.         btree_node_t *rsubtree;
  660.  
  661.         rsubtree = lnode->subtree[lnode->keys];
  662.         node_remove_key_and_rsubtree(lnode, key);
  663.         node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree);
  664.         lnode->parent->key[idx] = key;
  665.  
  666.         /* Fix parent link of the reconnected right subtree. */
  667.         rsubtree->parent = rnode;
  668.     }
  669.  
  670. }
  671.  
  672. /** Rotate one key-value-lsubtree triplet from the right sibling to the left sibling.
  673.  *
  674.  * The smallest key and its value and left subtree is rotated from the right node
  675.  * to the left. If the node is an index node, than the parent node key belonging to
  676.  * the right node takes part in the rotation.
  677.  *
  678.  * @param lnode Left sibling.
  679.  * @param rnode Right sibling.
  680.  * @param idx Index of the parent node key that is taking part in the rotation.
  681.  */
  682. void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx)
  683. {
  684.     __native key;
  685.  
  686.     key = rnode->key[0];
  687.        
  688.     if (LEAF_NODE(rnode)) {
  689.         void *value;
  690.  
  691.         value = rnode->value[0];
  692.         node_remove_key_and_lsubtree(rnode, key);
  693.         node_insert_key_and_rsubtree(lnode, key, value, NULL);
  694.         rnode->parent->key[idx] = rnode->key[0];
  695.     } else {
  696.         btree_node_t *lsubtree;
  697.  
  698.         lsubtree = rnode->subtree[0];
  699.         node_remove_key_and_lsubtree(rnode, key);
  700.         node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree);
  701.         rnode->parent->key[idx] = key;
  702.  
  703.         /* Fix parent link of the reconnected left subtree. */
  704.         lsubtree->parent = lnode;
  705.     }
  706.  
  707. }
  708.  
  709. /** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done.
  710.  *
  711.  * Left sibling of the node (if it exists) is checked for free space.
  712.  * If there is free space, the key is inserted and the smallest key of
  713.  * the node is moved there. The index node which is the parent of both
  714.  * nodes is fixed.
  715.  *
  716.  * @param node B-tree node.
  717.  * @param inskey Key to be inserted.
  718.  * @param insvalue Value to be inserted.
  719.  * @param rsubtree Right subtree of inskey.
  720.  *
  721.  * @return True if the rotation was performed, false otherwise.
  722.  */
  723. bool try_insert_by_rotation_to_left(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)
  724. {
  725.     index_t idx;
  726.     btree_node_t *lnode;
  727.  
  728.     /*
  729.      * If this is root node, the rotation can not be done.
  730.      */
  731.     if (ROOT_NODE(node))
  732.         return false;
  733.    
  734.     idx = find_key_by_subtree(node->parent, node, true);
  735.     if ((int) idx == -1) {
  736.         /*
  737.          * If this node is the leftmost subtree of its parent,
  738.          * the rotation can not be done.
  739.          */
  740.         return false;
  741.     }
  742.        
  743.     lnode = node->parent->subtree[idx];
  744.     if (lnode->keys < BTREE_MAX_KEYS) {
  745.         /*
  746.          * The rotaion can be done. The left sibling has free space.
  747.          */
  748.         node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
  749.         rotate_from_right(lnode, node, idx);
  750.         return true;
  751.     }
  752.  
  753.     return false;
  754. }
  755.  
  756. /** Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done.
  757.  *
  758.  * Right sibling of the node (if it exists) is checked for free space.
  759.  * If there is free space, the key is inserted and the biggest key of
  760.  * the node is moved there. The index node which is the parent of both
  761.  * nodes is fixed.
  762.  *
  763.  * @param node B-tree node.
  764.  * @param inskey Key to be inserted.
  765.  * @param insvalue Value to be inserted.
  766.  * @param rsubtree Right subtree of inskey.
  767.  *
  768.  * @return True if the rotation was performed, false otherwise.
  769.  */
  770. bool try_insert_by_rotation_to_right(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)
  771. {
  772.     index_t idx;
  773.     btree_node_t *rnode;
  774.  
  775.     /*
  776.      * If this is root node, the rotation can not be done.
  777.      */
  778.     if (ROOT_NODE(node))
  779.         return false;
  780.    
  781.     idx = find_key_by_subtree(node->parent, node, false);
  782.     if (idx == node->parent->keys) {
  783.         /*
  784.          * If this node is the rightmost subtree of its parent,
  785.          * the rotation can not be done.
  786.          */
  787.         return false;
  788.     }
  789.        
  790.     rnode = node->parent->subtree[idx + 1];
  791.     if (rnode->keys < BTREE_MAX_KEYS) {
  792.         /*
  793.          * The rotaion can be done. The right sibling has free space.
  794.          */
  795.         node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
  796.         rotate_from_left(node, rnode, idx);
  797.         return true;
  798.     }
  799.  
  800.     return false;
  801. }
  802.  
  803. /** Rotate in a key from the left sibling or from the index node, if this operation can be done.
  804.  *
  805.  * @param rnode Node into which to add key from its left sibling or from the index node.
  806.  *
  807.  * @return True if the rotation was performed, false otherwise.
  808.  */
  809. bool try_rotation_from_left(btree_node_t *rnode)
  810. {
  811.     index_t idx;
  812.     btree_node_t *lnode;
  813.  
  814.     /*
  815.      * If this is root node, the rotation can not be done.
  816.      */
  817.     if (ROOT_NODE(rnode))
  818.         return false;
  819.    
  820.     idx = find_key_by_subtree(rnode->parent, rnode, true);
  821.     if ((int) idx == -1) {
  822.         /*
  823.          * If this node is the leftmost subtree of its parent,
  824.          * the rotation can not be done.
  825.          */
  826.         return false;
  827.     }
  828.        
  829.     lnode = rnode->parent->subtree[idx];
  830.     if (lnode->keys > FILL_FACTOR) {
  831.         rotate_from_left(lnode, rnode, idx);
  832.         return true;
  833.     }
  834.    
  835.     return false;
  836. }
  837.  
  838. /** Rotate in a key from the right sibling or from the index node, if this operation can be done.
  839.  *
  840.  * @param rnode Node into which to add key from its right sibling or from the index node.
  841.  *
  842.  * @return True if the rotation was performed, false otherwise.
  843.  */
  844. bool try_rotation_from_right(btree_node_t *lnode)
  845. {
  846.     index_t idx;
  847.     btree_node_t *rnode;
  848.  
  849.     /*
  850.      * If this is root node, the rotation can not be done.
  851.      */
  852.     if (ROOT_NODE(lnode))
  853.         return false;
  854.    
  855.     idx = find_key_by_subtree(lnode->parent, lnode, false);
  856.     if (idx == lnode->parent->keys) {
  857.         /*
  858.          * If this node is the rightmost subtree of its parent,
  859.          * the rotation can not be done.
  860.          */
  861.         return false;
  862.     }
  863.        
  864.     rnode = lnode->parent->subtree[idx + 1];
  865.     if (rnode->keys > FILL_FACTOR) {
  866.         rotate_from_right(lnode, rnode, idx);
  867.         return true;
  868.     }  
  869.  
  870.     return false;
  871. }
  872.  
  873. /** Print B-tree.
  874.  *
  875.  * @param t Print out B-tree.
  876.  */
  877. void btree_print(btree_t *t)
  878. {
  879.     int i, depth = t->root->depth;
  880.     link_t head, *cur;
  881.  
  882.     printf("Printing B-tree:\n");
  883.     list_initialize(&head);
  884.     list_append(&t->root->bfs_link, &head);
  885.  
  886.     /*
  887.      * Use BFS search to print out the tree.
  888.      * Levels are distinguished from one another by node->depth.
  889.      */
  890.     while (!list_empty(&head)) {
  891.         link_t *hlp;
  892.         btree_node_t *node;
  893.        
  894.         hlp = head.next;
  895.         ASSERT(hlp != &head);
  896.         node = list_get_instance(hlp, btree_node_t, bfs_link);
  897.         list_remove(hlp);
  898.        
  899.         ASSERT(node);
  900.        
  901.         if (node->depth != depth) {
  902.             printf("\n");
  903.             depth = node->depth;
  904.         }
  905.  
  906.         printf("(");
  907.         for (i = 0; i < node->keys; i++) {
  908.             printf("%d%s", node->key[i], i < node->keys - 1 ? "," : "");
  909.             if (node->depth && node->subtree[i]) {
  910.                 list_append(&node->subtree[i]->bfs_link, &head);
  911.             }
  912.         }
  913.         if (node->depth && node->subtree[i]) {
  914.             list_append(&node->subtree[i]->bfs_link, &head);
  915.         }
  916.         printf(")");
  917.     }
  918.     printf("\n");
  919.    
  920.     printf("Printing list of leaves:\n");
  921.     for (cur = t->leaf_head.next; cur != &t->leaf_head; cur = cur->next) {
  922.         btree_node_t *node;
  923.        
  924.         node = list_get_instance(cur, btree_node_t, leaf_link);
  925.        
  926.         ASSERT(node);
  927.  
  928.         printf("(");
  929.         for (i = 0; i < node->keys; i++)
  930.             printf("%d%s", node->key[i], i < node->keys - 1 ? "," : "");
  931.         printf(")");
  932.     }
  933.     printf("\n");
  934. }
  935.