Rev 3149 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
| Rev 3149 | Rev 4339 | ||
|---|---|---|---|
| Line 122... | Line 122... | ||
| 122 | ASSERT(value); |
122 | ASSERT(value); |
| 123 | 123 | ||
| 124 | lnode = leaf_node; |
124 | lnode = leaf_node; |
| 125 | if (!lnode) { |
125 | if (!lnode) { |
| 126 | if (btree_search(t, key, &lnode)) { |
126 | if (btree_search(t, key, &lnode)) { |
| 127 | panic("B-tree %p already contains key %" PRIu64 "\n", t, key); |
127 | panic("B-tree %p already contains key %" PRIu64 ".", t, key); |
| 128 | } |
128 | } |
| 129 | } |
129 | } |
| 130 | 130 | ||
| 131 | _btree_insert(t, key, value, NULL, lnode); |
131 | _btree_insert(t, key, value, NULL, lnode); |
| 132 | } |
132 | } |
| Line 222... | Line 222... | ||
| 222 | btree_node_t *lnode; |
222 | btree_node_t *lnode; |
| 223 | 223 | ||
| 224 | lnode = leaf_node; |
224 | lnode = leaf_node; |
| 225 | if (!lnode) { |
225 | if (!lnode) { |
| 226 | if (!btree_search(t, key, &lnode)) { |
226 | if (!btree_search(t, key, &lnode)) { |
| 227 | panic("B-tree %p does not contain key %" PRIu64 "\n", t, key); |
227 | panic("B-tree %p does not contain key %" PRIu64 ".", t, key); |
| 228 | } |
228 | } |
| 229 | } |
229 | } |
| 230 | 230 | ||
| 231 | _btree_remove(t, key, lnode); |
231 | _btree_remove(t, key, lnode); |
| 232 | } |
232 | } |
| Line 522... | Line 522... | ||
| 522 | node->subtree[j - 1] = node->subtree[j]; |
522 | node->subtree[j - 1] = node->subtree[j]; |
| 523 | node->keys--; |
523 | node->keys--; |
| 524 | return; |
524 | return; |
| 525 | } |
525 | } |
| 526 | } |
526 | } |
| 527 | panic("node %p does not contain key %" PRIu64 "\n", node, key); |
527 | panic("Node %p does not contain key %" PRIu64 ".", node, key); |
| 528 | } |
528 | } |
| 529 | 529 | ||
| 530 | /** Remove key and its right subtree pointer from B-tree node. |
530 | /** Remove key and its right subtree pointer from B-tree node. |
| 531 | * |
531 | * |
| 532 | * Remove the key and eliminate gaps in node->key array. |
532 | * Remove the key and eliminate gaps in node->key array. |
| Line 549... | Line 549... | ||
| 549 | } |
549 | } |
| 550 | node->keys--; |
550 | node->keys--; |
| 551 | return; |
551 | return; |
| 552 | } |
552 | } |
| 553 | } |
553 | } |
| 554 | panic("node %p does not contain key %" PRIu64 "\n", node, key); |
554 | panic("Node %p does not contain key %" PRIu64 ".", node, key); |
| 555 | } |
555 | } |
| 556 | 556 | ||
| 557 | /** Split full B-tree node and insert new key-value-right-subtree triplet. |
557 | /** Split full B-tree node and insert new key-value-right-subtree triplet. |
| 558 | * |
558 | * |
| 559 | * This function will split a node and return a pointer to a newly created |
559 | * This function will split a node and return a pointer to a newly created |
| Line 691... | Line 691... | ||
| 691 | 691 | ||
| 692 | for (i = 0; i < node->keys + 1; i++) { |
692 | for (i = 0; i < node->keys + 1; i++) { |
| 693 | if (subtree == node->subtree[i]) |
693 | if (subtree == node->subtree[i]) |
| 694 | return i - (int) (right != false); |
694 | return i - (int) (right != false); |
| 695 | } |
695 | } |
| 696 | panic("node %p does not contain subtree %p\n", node, subtree); |
696 | panic("Node %p does not contain subtree %p.", node, subtree); |
| 697 | } |
697 | } |
| 698 | 698 | ||
| 699 | /** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling. |
699 | /** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling. |
| 700 | * |
700 | * |
| 701 | * The biggest key and its value and right subtree is rotated from the left node |
701 | * The biggest key and its value and right subtree is rotated from the left node |