Changeset 0cb56f5d in mainline
- Timestamp:
- 2006-04-01T11:02:05Z (19 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 5b04fc7
- Parents:
- ca687ad
- Files:
-
- 3 edited
-
generic/include/adt/btree.h (modified) (1 diff)
-
generic/src/adt/btree.c (modified) (17 diffs)
-
test/btree/btree1/test.c (modified) (1 diff)
Legend:
- Unmodified
- Added
- Removed
-
generic/include/adt/btree.h
rca687ad r0cb56f5d 84 84 extern void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node); 85 85 86 extern void *btree_node_min(btree_node_t *node);87 extern void *btree_node_max(btree_node_t *node);88 89 86 extern void btree_print(btree_t *t); 90 87 #endif -
generic/src/adt/btree.c
rca687ad r0cb56f5d 48 48 49 49 static void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node); 50 static void _btree_remove(btree_t *t, __native key, btree_node_t *node); 50 51 static void node_initialize(btree_node_t *node); 51 static void node_insert_key_ left(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);52 static void node_insert_key_ right(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);52 static void node_insert_key_and_lsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree); 53 static void node_insert_key_and_rsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree); 53 54 static btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median); 54 static void node_remove_key_left(btree_node_t *node, __native key); 55 static void node_remove_key_right(btree_node_t *node, __native key); 55 static btree_node_t *node_combine(btree_node_t *node); 56 static void node_remove_key_and_lsubtree(btree_node_t *node, __native key); 57 static void node_remove_key_and_rsubtree(btree_node_t *node, __native key); 56 58 static index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right); 57 static bool try_insert_by_left_rotation(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree); 58 static bool try_insert_by_right_rotation(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree); 59 static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx); 60 static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx); 61 static bool try_insert_by_rotation_to_left(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree); 62 static bool try_insert_by_rotation_to_right(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree); 63 static bool try_rotation_from_left(btree_node_t *rnode); 64 static bool try_rotation_from_right(btree_node_t *lnode); 59 65 60 66 #define ROOT_NODE(n) (!(n)->parent) … … 125 131 * Node conatins enough space, the key can be stored immediately. 126 132 */ 127 node_insert_key_ right(node, key, value, rsubtree);128 } else if (try_insert_by_ left_rotation(node, key, value, rsubtree)) {133 node_insert_key_and_rsubtree(node, key, value, rsubtree); 134 } else if (try_insert_by_rotation_to_left(node, key, value, rsubtree)) { 129 135 /* 130 136 * The key-value-rsubtree triplet has been inserted because 131 137 * some keys could have been moved to the left sibling. 132 138 */ 133 } else if (try_insert_by_r ight_rotation(node, key, value, rsubtree)) {139 } else if (try_insert_by_rotation_to_right(node, key, value, rsubtree)) { 134 140 /* 135 141 * The key-value-rsubtree triplet has been inserted because … … 184 190 btree_node_t *lnode; 185 191 192 panic("%s needs testing and is disabled in revision %s\n", __FUNCTION__, REVISION); 186 193 lnode = leaf_node; 187 194 if (!lnode) { … … 191 198 } 192 199 193 /* TODO */ 194 200 _btree_remove(t, key, lnode); 201 } 202 203 /** Recursively remove B-tree node. 204 * 205 * @param B-tree. 206 * @param key Key to be removed from the B-tree along with its associated value. 207 * @param node Node where the key being removed resides. 208 */ 209 void _btree_remove(btree_t *t, __native key, btree_node_t *node) 210 { 211 if (ROOT_NODE(node)) { 212 if (node->keys == 1 && node->subtree[0]) { 213 /* 214 * Free the current root and set new root. 215 */ 216 t->root = node->subtree[0]; 217 t->root->parent = NULL; 218 free(node); 219 } else { 220 /* 221 * Remove the key from the root node. 222 * Note that the right subtree is removed because when 223 * combining two nodes, the left-side sibling is preserved 224 * and the right-side sibling is freed. 225 */ 226 node_remove_key_and_rsubtree(node, key); 227 } 228 return; 229 } 230 231 if (node->keys <= FILL_FACTOR) { 232 /* 233 * If the node is below the fill factor, 234 * try to borrow keys from left or right sibling. 235 */ 236 if (!try_rotation_from_left(node)) 237 try_rotation_from_right(node); 238 } 239 240 if (node->keys > FILL_FACTOR) { 241 int i; 242 243 /* 244 * The key can be immediatelly removed. 245 * 246 * Note that the right subtree is removed because when 247 * combining two nodes, the left-side sibling is preserved 248 * and the right-side sibling is freed. 249 */ 250 node_remove_key_and_rsubtree(node, key); 251 for (i = 0; i < node->parent->keys; i++) { 252 if (node->parent->key[i] == key) 253 node->parent->key[i] = node->key[0]; 254 } 255 256 } else { 257 index_t idx; 258 btree_node_t *rnode, *parent; 259 260 /* 261 * The node is below the fill factor as well as its left and right sibling. 262 * Resort to combining the node with one of its siblings. 263 * The node which is on the left is preserved and the node on the right is 264 * freed. 265 */ 266 parent = node->parent; 267 node_remove_key_and_rsubtree(node, key); 268 rnode = node_combine(node); 269 if (LEAF_NODE(rnode)) 270 list_remove(&rnode->leaf_link); 271 idx = find_key_by_subtree(parent, rnode, true); 272 ASSERT((int) idx != -1); 273 free(rnode); 274 _btree_remove(t, parent->key[idx], parent); 275 } 195 276 } 196 277 … … 261 342 } 262 343 263 /** Get pointer to value with the smallest key within the node.264 *265 * Can be only used on leaf-level nodes.266 *267 * @param node B-tree node.268 *269 * @return Pointer to value assiciated with the smallest key.270 */271 void *btree_node_min(btree_node_t *node)272 {273 ASSERT(LEAF_NODE(node));274 ASSERT(node->keys);275 return node->value[0];276 }277 278 /** Get pointer to value with the biggest key within the node.279 *280 * Can be only used on leaf-level nodes.281 *282 * @param node B-tree node.283 *284 * @return Pointer to value assiciated with the biggest key.285 */286 void *btree_node_max(btree_node_t *node)287 {288 ASSERT(LEAF_NODE(node));289 ASSERT(node->keys);290 return node->value[node->keys - 1];291 }292 293 344 /** Initialize B-tree node. 294 345 * … … 327 378 * @param lsubtree Pointer to the left subtree. 328 379 */ 329 void node_insert_key_ left(btree_node_t *node, __native key, void *value, btree_node_t *lsubtree)380 void node_insert_key_and_lsubtree(btree_node_t *node, __native key, void *value, btree_node_t *lsubtree) 330 381 { 331 382 int i; … … 351 402 } 352 403 353 354 404 /** Insert key-value-rsubtree triplet into B-tree node. 355 405 * … … 364 414 * @param rsubtree Pointer to the right subtree. 365 415 */ 366 void node_insert_key_ right(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree)416 void node_insert_key_and_rsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree) 367 417 { 368 418 int i; … … 417 467 * Use the extra space to store the extra node. 418 468 */ 419 node_insert_key_ right(node, key, value, rsubtree);469 node_insert_key_and_rsubtree(node, key, value, rsubtree); 420 470 421 471 /* … … 459 509 } 460 510 511 /** Combine node with any of its siblings. 512 * 513 * The siblings are required to be below the fill factor. 514 * 515 * @param node Node to combine with one of its siblings. 516 * 517 * @return Pointer to the rightmost of the two nodes. 518 */ 519 btree_node_t *node_combine(btree_node_t *node) 520 { 521 index_t idx; 522 btree_node_t *rnode; 523 int i; 524 525 ASSERT(!ROOT_NODE(node)); 526 527 idx = find_key_by_subtree(node->parent, node, false); 528 if (idx == node->parent->keys) { 529 /* 530 * Rightmost subtree of its parent, combine with the left sibling. 531 */ 532 idx--; 533 rnode = node; 534 node = node->parent->subtree[idx]; 535 } else { 536 rnode = node->parent->subtree[idx + 1]; 537 } 538 539 /* Index nodes need to insert parent node key in between left and right node. */ 540 if (INDEX_NODE(node)) 541 node->key[node->keys++] = node->parent->key[idx]; 542 543 /* Copy the key-value-subtree triplets from the right node. */ 544 for (i = 0; i < rnode->keys; i++) { 545 node->key[node->keys + i] = rnode->key[i]; 546 node->value[node->keys + i] = rnode->value[i]; 547 if (INDEX_NODE(node)) { 548 node->subtree[node->keys + i] = rnode->subtree[i]; 549 rnode->subtree[i]->parent = node; 550 } 551 } 552 if (INDEX_NODE(node)) { 553 node->subtree[node->keys + i] = rnode->subtree[i]; 554 rnode->subtree[i]->parent = node; 555 } 556 557 node->keys += rnode->keys; 558 559 return rnode; 560 } 561 461 562 /** Remove key and its left subtree pointer from B-tree node. 462 563 * … … 468 569 * @param key Key to be removed. 469 570 */ 470 void node_remove_key_ left(btree_node_t *node, __native key)571 void node_remove_key_and_lsubtree(btree_node_t *node, __native key) 471 572 { 472 573 int i, j; … … 496 597 * @param key Key to be removed. 497 598 */ 498 void node_remove_key_ right(btree_node_t *node, __native key)599 void node_remove_key_and_rsubtree(btree_node_t *node, __native key) 499 600 { 500 601 int i, j; … … 533 634 } 534 635 636 /** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling. 637 * 638 * The biggest key and its value and right subtree is rotated from the left node 639 * to the right. If the node is an index node, than the parent node key belonging to 640 * the left node takes part in the rotation. 641 * 642 * @param lnode Left sibling. 643 * @param rnode Right sibling. 644 * @param idx Index of the parent node key that is taking part in the rotation. 645 */ 646 void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx) 647 { 648 __native key; 649 650 key = lnode->key[lnode->keys - 1]; 651 652 if (LEAF_NODE(lnode)) { 653 void *value; 654 655 value = lnode->value[lnode->keys - 1]; 656 node_remove_key_and_rsubtree(lnode, key); 657 node_insert_key_and_lsubtree(rnode, key, value, NULL); 658 lnode->parent->key[idx] = key; 659 } else { 660 btree_node_t *rsubtree; 661 662 rsubtree = lnode->subtree[lnode->keys]; 663 node_remove_key_and_rsubtree(lnode, key); 664 node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree); 665 lnode->parent->key[idx] = key; 666 667 /* Fix parent link of the reconnected right subtree. */ 668 rsubtree->parent = rnode; 669 } 670 671 } 672 673 /** Rotate one key-value-lsubtree triplet from the right sibling to the left sibling. 674 * 675 * The smallest key and its value and left subtree is rotated from the right node 676 * to the left. If the node is an index node, than the parent node key belonging to 677 * the right node takes part in the rotation. 678 * 679 * @param lnode Left sibling. 680 * @param rnode Right sibling. 681 * @param idx Index of the parent node key that is taking part in the rotation. 682 */ 683 void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx) 684 { 685 __native key; 686 687 key = rnode->key[0]; 688 689 if (LEAF_NODE(rnode)) { 690 void *value; 691 692 value = rnode->value[0]; 693 node_remove_key_and_lsubtree(rnode, key); 694 node_insert_key_and_rsubtree(lnode, key, value, NULL); 695 rnode->parent->key[idx] = rnode->key[0]; 696 } else { 697 btree_node_t *lsubtree; 698 699 lsubtree = rnode->subtree[0]; 700 node_remove_key_and_lsubtree(rnode, key); 701 node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree); 702 rnode->parent->key[idx] = key; 703 704 /* Fix parent link of the reconnected left subtree. */ 705 lsubtree->parent = lnode; 706 } 707 708 } 709 535 710 /** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done. 536 711 * … … 547 722 * @return True if the rotation was performed, false otherwise. 548 723 */ 549 bool try_insert_by_ left_rotation(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)724 bool try_insert_by_rotation_to_left(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree) 550 725 { 551 726 index_t idx; … … 568 743 569 744 lnode = node->parent->subtree[idx]; 570 571 745 if (lnode->keys < BTREE_MAX_KEYS) { 572 __native key;573 574 746 /* 575 747 * The rotaion can be done. The left sibling has free space. 576 748 */ 577 578 node_insert_key_right(node, inskey, insvalue, rsubtree); 579 key = node->key[0]; 580 581 if (LEAF_NODE(node)) { 582 void *value; 583 584 value = node->value[0]; 585 node_remove_key_left(node, key); 586 node_insert_key_right(lnode, key, value, NULL); 587 node->parent->key[idx] = node->key[0]; 588 } else { 589 btree_node_t *lsubtree; 590 591 lsubtree = node->subtree[0]; 592 node_remove_key_left(node, key); 593 node_insert_key_right(lnode, node->parent->key[idx], NULL, lsubtree); 594 node->parent->key[idx] = key; 595 596 /* Fix parent link of the reconnected left subtree. */ 597 lsubtree->parent = lnode; 598 } 749 node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree); 750 rotate_from_right(lnode, node, idx); 599 751 return true; 600 752 } … … 617 769 * @return True if the rotation was performed, false otherwise. 618 770 */ 619 bool try_insert_by_r ight_rotation(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)771 bool try_insert_by_rotation_to_right(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree) 620 772 { 621 773 index_t idx; … … 638 790 639 791 rnode = node->parent->subtree[idx + 1]; 640 641 792 if (rnode->keys < BTREE_MAX_KEYS) { 642 __native key;643 644 793 /* 645 794 * The rotaion can be done. The right sibling has free space. 646 795 */ 647 648 node_insert_key_right(node, inskey, insvalue, rsubtree); 649 key = node->key[node->keys - 1]; 650 651 if (LEAF_NODE(node)) { 652 void *value; 653 654 value = node->value[node->keys - 1]; 655 node_remove_key_right(node, key); 656 node_insert_key_left(rnode, key, value, NULL); 657 node->parent->key[idx] = key; 658 } else { 659 btree_node_t *rsubt; 660 661 rsubt = node->subtree[node->keys]; 662 node_remove_key_right(node, key); 663 node_insert_key_left(rnode, node->parent->key[idx], NULL, rsubt); 664 node->parent->key[idx] = key; 665 666 /* Fix parent link of the reconnected right subtree. */ 667 rsubt->parent = rnode; 668 } 796 node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree); 797 rotate_from_left(node, rnode, idx); 669 798 return true; 670 799 } 800 801 return false; 802 } 803 804 /** Rotate in a key from the left sibling or from the index node, if this operation can be done. 805 * 806 * @param rnode Node into which to add key from its left sibling or from the index node. 807 * 808 * @return True if the rotation was performed, false otherwise. 809 */ 810 bool try_rotation_from_left(btree_node_t *rnode) 811 { 812 index_t idx; 813 btree_node_t *lnode; 814 815 /* 816 * If this is root node, the rotation can not be done. 817 */ 818 if (ROOT_NODE(rnode)) 819 return false; 820 821 idx = find_key_by_subtree(rnode->parent, rnode, true); 822 if ((int) idx == -1) { 823 /* 824 * If this node is the leftmost subtree of its parent, 825 * the rotation can not be done. 826 */ 827 return false; 828 } 829 830 lnode = rnode->parent->subtree[idx]; 831 if (lnode->keys > FILL_FACTOR) { 832 rotate_from_left(lnode, rnode, idx); 833 return true; 834 } 835 836 return false; 837 } 838 839 /** Rotate in a key from the right sibling or from the index node, if this operation can be done. 840 * 841 * @param rnode Node into which to add key from its right sibling or from the index node. 842 * 843 * @return True if the rotation was performed, false otherwise. 844 */ 845 bool try_rotation_from_right(btree_node_t *lnode) 846 { 847 index_t idx; 848 btree_node_t *rnode; 849 850 /* 851 * If this is root node, the rotation can not be done. 852 */ 853 if (ROOT_NODE(lnode)) 854 return false; 855 856 idx = find_key_by_subtree(lnode->parent, lnode, false); 857 if (idx == lnode->parent->keys) { 858 /* 859 * If this node is the rightmost subtree of its parent, 860 * the rotation can not be done. 861 */ 862 return false; 863 } 864 865 rnode = lnode->parent->subtree[idx + 1]; 866 if (rnode->keys > FILL_FACTOR) { 867 rotate_from_right(lnode, rnode, idx); 868 return true; 869 } 671 870 672 871 return false; -
test/btree/btree1/test.c
rca687ad r0cb56f5d 78 78 79 79 btree_print(&t); 80 81 btree_remove(&t, 50, NULL); 80 82 81 83 }
Note:
See TracChangeset
for help on using the changeset viewer.
