Rev 2787 | Rev 4377 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
| Rev 2787 | Rev 3424 | ||
|---|---|---|---|
| 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 %d\n", t, key); |
127 | panic("B-tree %p already contains key %" PRIu64 "\n", 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 %d\n", t, key); |
227 | panic("B-tree %p does not contain key %" PRIu64 "\n", 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 %d\n", node, key); |
527 | panic("node %p does not contain key %" PRIu64 "\n", 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 %d\n", node, key); |
554 | panic("node %p does not contain key %" PRIu64 "\n", 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 968... | Line 968... | ||
| 968 | depth = node->depth; |
968 | depth = node->depth; |
| 969 | } |
969 | } |
| 970 | 970 | ||
| 971 | printf("("); |
971 | printf("("); |
| 972 | for (i = 0; i < node->keys; i++) { |
972 | for (i = 0; i < node->keys; i++) { |
| 973 | printf("%llu%s", node->key[i], i < node->keys - 1 ? "," : ""); |
973 | printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : ""); |
| 974 | if (node->depth && node->subtree[i]) { |
974 | if (node->depth && node->subtree[i]) { |
| 975 | list_append(&node->subtree[i]->bfs_link, &head); |
975 | list_append(&node->subtree[i]->bfs_link, &head); |
| 976 | } |
976 | } |
| 977 | } |
977 | } |
| 978 | if (node->depth && node->subtree[i]) { |
978 | if (node->depth && node->subtree[i]) { |
| Line 990... | Line 990... | ||
| 990 | 990 | ||
| 991 | ASSERT(node); |
991 | ASSERT(node); |
| 992 | 992 | ||
| 993 | printf("("); |
993 | printf("("); |
| 994 | for (i = 0; i < node->keys; i++) |
994 | for (i = 0; i < node->keys; i++) |
| 995 | printf("%llu%s", node->key[i], i < node->keys - 1 ? "," : ""); |
995 | printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : ""); |
| 996 | printf(")"); |
996 | printf(")"); |
| 997 | } |
997 | } |
| 998 | printf("\n"); |
998 | printf("\n"); |
| 999 | } |
999 | } |
| 1000 | 1000 | ||