Subversion Repositories HelenOS

Rev

Rev 3058 | Rev 4153 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

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