Rev 1196 | Rev 1483 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
| Rev 1196 | Rev 1221 | ||
|---|---|---|---|
| Line 115... | Line 115... | ||
| 115 | ASSERT(value); |
115 | ASSERT(value); |
| 116 | 116 | ||
| 117 | lnode = leaf_node; |
117 | lnode = leaf_node; |
| 118 | if (!lnode) { |
118 | if (!lnode) { |
| 119 | if (btree_search(t, key, &lnode)) { |
119 | if (btree_search(t, key, &lnode)) { |
| 120 | panic("B-tree %P already contains key %d\n", t, key); |
120 | panic("B-tree %p already contains key %d\n", t, key); |
| 121 | } |
121 | } |
| 122 | } |
122 | } |
| 123 | 123 | ||
| 124 | _btree_insert(t, key, value, NULL, lnode); |
124 | _btree_insert(t, key, value, NULL, lnode); |
| 125 | } |
125 | } |
| Line 198... | Line 198... | ||
| 198 | btree_node_t *lnode; |
198 | btree_node_t *lnode; |
| 199 | 199 | ||
| 200 | lnode = leaf_node; |
200 | lnode = leaf_node; |
| 201 | if (!lnode) { |
201 | if (!lnode) { |
| 202 | if (!btree_search(t, key, &lnode)) { |
202 | if (!btree_search(t, key, &lnode)) { |
| 203 | panic("B-tree %P does not contain key %d\n", t, key); |
203 | panic("B-tree %p does not contain key %d\n", t, key); |
| 204 | } |
204 | } |
| 205 | } |
205 | } |
| 206 | 206 | ||
| 207 | _btree_remove(t, key, lnode); |
207 | _btree_remove(t, key, lnode); |
| 208 | } |
208 | } |
| Line 498... | Line 498... | ||
| 498 | node->subtree[j - 1] = node->subtree[j]; |
498 | node->subtree[j - 1] = node->subtree[j]; |
| 499 | node->keys--; |
499 | node->keys--; |
| 500 | return; |
500 | return; |
| 501 | } |
501 | } |
| 502 | } |
502 | } |
| 503 | panic("node %P does not contain key %d\n", node, key); |
503 | panic("node %p does not contain key %d\n", node, key); |
| 504 | } |
504 | } |
| 505 | 505 | ||
| 506 | /** Remove key and its right subtree pointer from B-tree node. |
506 | /** Remove key and its right subtree pointer from B-tree node. |
| 507 | * |
507 | * |
| 508 | * Remove the key and eliminate gaps in node->key array. |
508 | * Remove the key and eliminate gaps in node->key array. |
| Line 525... | Line 525... | ||
| 525 | } |
525 | } |
| 526 | node->keys--; |
526 | node->keys--; |
| 527 | return; |
527 | return; |
| 528 | } |
528 | } |
| 529 | } |
529 | } |
| 530 | panic("node %P does not contain key %d\n", node, key); |
530 | panic("node %p does not contain key %d\n", node, key); |
| 531 | } |
531 | } |
| 532 | 532 | ||
| 533 | /** Split full B-tree node and insert new key-value-right-subtree triplet. |
533 | /** Split full B-tree node and insert new key-value-right-subtree triplet. |
| 534 | * |
534 | * |
| 535 | * This function will split a node and return pointer to a newly created |
535 | * This function will split a node and return pointer to a newly created |
| Line 667... | Line 667... | ||
| 667 | 667 | ||
| 668 | for (i = 0; i < node->keys + 1; i++) { |
668 | for (i = 0; i < node->keys + 1; i++) { |
| 669 | if (subtree == node->subtree[i]) |
669 | if (subtree == node->subtree[i]) |
| 670 | return i - (int) (right != false); |
670 | return i - (int) (right != false); |
| 671 | } |
671 | } |
| 672 | panic("node %P does not contain subtree %P\n", node, subtree); |
672 | panic("node %p does not contain subtree %p\n", node, subtree); |
| 673 | } |
673 | } |
| 674 | 674 | ||
| 675 | /** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling. |
675 | /** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling. |
| 676 | * |
676 | * |
| 677 | * The biggest key and its value and right subtree is rotated from the left node |
677 | * The biggest key and its value and right subtree is rotated from the left node |