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