Changeset 98000fb in mainline for kernel/generic/src/adt/btree.c
- Timestamp:
- 2009-06-03T19:34:45Z (15 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 301ff30
- Parents:
- 69e68e3
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/adt/btree.c
r69e68e3 r98000fb 64 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 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);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 69 static bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree); 70 70 static bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree); … … 138 138 void btree_destroy_subtree(btree_node_t *root) 139 139 { 140 count_t i;140 size_t i; 141 141 142 142 if (root->keys) { … … 270 270 271 271 if (node->keys > FILL_FACTOR) { 272 count_t i;272 size_t i; 273 273 274 274 /* … … 286 286 287 287 } else { 288 index_t idx;288 size_t idx; 289 289 btree_node_t *rnode, *parent; 290 290 … … 336 336 } else { 337 337 void *val; 338 count_t i;338 size_t i; 339 339 340 340 /* … … 443 443 void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree) 444 444 { 445 count_t i;445 size_t i; 446 446 447 447 for (i = 0; i < node->keys; i++) { 448 448 if (key < node->key[i]) { 449 count_t j;449 size_t j; 450 450 451 451 for (j = node->keys; j > i; j--) { … … 479 479 void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree) 480 480 { 481 count_t i;481 size_t i; 482 482 483 483 for (i = 0; i < node->keys; i++) { 484 484 if (key < node->key[i]) { 485 count_t j;485 size_t j; 486 486 487 487 for (j = node->keys; j > i; j--) { … … 511 511 void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key) 512 512 { 513 count_t i, j;513 size_t i, j; 514 514 515 515 for (i = 0; i < node->keys; i++) { … … 539 539 void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key) 540 540 { 541 count_t i, j;541 size_t i, j; 542 542 543 543 for (i = 0; i < node->keys; i++) { … … 577 577 { 578 578 btree_node_t *rnode; 579 count_t i, j;579 size_t i, j; 580 580 581 581 ASSERT(median); … … 604 604 * If this is an index node, do not copy the median. 605 605 */ 606 i = ( count_t) INDEX_NODE(node);606 i = (size_t) INDEX_NODE(node); 607 607 for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) { 608 608 rnode->key[j] = node->key[i]; … … 637 637 btree_node_t *node_combine(btree_node_t *node) 638 638 { 639 index_t idx;639 size_t idx; 640 640 btree_node_t *rnode; 641 count_t i;641 size_t i; 642 642 643 643 ASSERT(!ROOT_NODE(node)); … … 686 686 * @return Index of the key associated with the subtree. 687 687 */ 688 index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right)689 { 690 count_t i;688 size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right) 689 { 690 size_t i; 691 691 692 692 for (i = 0; i < node->keys + 1; i++) { … … 707 707 * @param idx Index of the parent node key that is taking part in the rotation. 708 708 */ 709 void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx)709 void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx) 710 710 { 711 711 btree_key_t key; … … 744 744 * @param idx Index of the parent node key that is taking part in the rotation. 745 745 */ 746 void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx)746 void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, size_t idx) 747 747 { 748 748 btree_key_t key; … … 787 787 bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree) 788 788 { 789 index_t idx;789 size_t idx; 790 790 btree_node_t *lnode; 791 791 … … 834 834 bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree) 835 835 { 836 index_t idx;836 size_t idx; 837 837 btree_node_t *rnode; 838 838 … … 873 873 bool try_rotation_from_left(btree_node_t *rnode) 874 874 { 875 index_t idx;875 size_t idx; 876 876 btree_node_t *lnode; 877 877 … … 908 908 bool try_rotation_from_right(btree_node_t *lnode) 909 909 { 910 index_t idx;910 size_t idx; 911 911 btree_node_t *rnode; 912 912 … … 941 941 void btree_print(btree_t *t) 942 942 { 943 count_t i;943 size_t i; 944 944 int depth = t->root->depth; 945 945 link_t head, *cur;
Note:
See TracChangeset
for help on using the changeset viewer.