Subversion Repositories HelenOS

Rev

Rev 1965 | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

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