2 Copyright (c) 2010 Joseph A. Adams
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions
8 1. Redistributions of source code must retain the above copyright
9 notice, this list of conditions and the following disclaimer.
10 2. Redistributions in binary form must reproduce the above copyright
11 notice, this list of conditions and the following disclaimer in the
12 documentation and/or other materials provided with the distribution.
13 3. The name of the author may not be used to endorse or promote products
14 derived from this software without specific prior written permission.
16 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 #define MAX (BTREE_ITEM_MAX)
35 #define MIN (BTREE_ITEM_MAX >> 1)
37 static struct btree_node *node_alloc(int internal);
38 static void node_delete(struct btree_node *node, struct btree *btree);
40 static void branch_begin(btree_iterator iter);
41 static void branch_end(btree_iterator iter);
42 static void begin_end_lr(btree_iterator iter, struct btree_node *node, int lr);
45 * If iter->node has parent, returns 1 and ascends the iterator such that
46 * iter->node->branch[iter->k] will be what iter->node was.
48 * If iter->node does not have a parent (is a root), returns 0 and leaves the
51 #define ascend(iter) ((iter)->node->parent \
52 ? (iter)->k = (iter)->node->k, (iter)->node = (iter)->node->parent, 1 \
55 static void node_insert(const void *x, struct btree_node *xr,
56 struct btree_node *p, unsigned int k);
57 static void node_split(const void **x, struct btree_node **xr,
58 struct btree_node *p, unsigned int k);
60 static void node_remove_leaf_item(struct btree_node *node, unsigned int k);
61 void node_restore(struct btree_node *node, unsigned int k);
63 static int node_walk_backward(const struct btree_node *node,
64 btree_action_t action, void *ctx);
65 static int node_walk_forward(const struct btree_node *node,
66 btree_action_t action, void *ctx);
69 /************************* Public functions *************************/
71 struct btree *btree_new(btree_search_t search)
73 struct btree *btree = calloc(1, sizeof(struct btree));
74 struct btree_node *node = node_alloc(0);
79 btree->search = search;
84 void btree_delete(struct btree *btree)
86 node_delete(btree->root, btree);
90 bool btree_insert(struct btree *btree, const void *item)
94 if (btree_find_last(btree, item, iter) && !btree->multi)
97 btree_insert_at(iter, item);
101 bool btree_remove(struct btree *btree, const void *key)
104 bool success = false;
105 bool multi = btree->multi;
108 if (btree_find_first(btree, key, iter)) {
109 btree_remove_at(iter);
117 void *btree_lookup(struct btree *btree, const void *key)
121 if (btree_find_first(btree, key, iter))
127 int btree_begin_end_lr(const struct btree *btree, btree_iterator iter, int lr)
129 struct btree_node *node;
131 iter->btree = (struct btree *)btree;
132 begin_end_lr(iter, btree->root, lr);
134 /* Set iter->item if any items exist. */
137 iter->item = (void*)node->item[iter->k - lr];
144 int btree_deref(btree_iterator iter)
146 if (iter->k >= iter->node->count) {
147 struct btree_iterator_s tmp = *iter;
153 } while (iter->k >= iter->node->count);
156 iter->item = (void*)iter->node->item[iter->k];
160 int btree_prev(btree_iterator iter)
162 if (iter->node->depth) {
164 } else if (iter->k == 0) {
165 struct btree_iterator_s tmp = *iter;
171 } while (iter->k == 0);
174 iter->item = (void*)iter->node->item[--iter->k];
178 int btree_next(btree_iterator iter)
180 int ret = btree_deref(iter);
183 if (iter->node->depth)
189 int btree_find_lr(const struct btree *btree, const void *key,
190 btree_iterator iter, int lr)
192 struct btree_node *node = btree->root;
197 iter->btree = (struct btree *)btree;
203 k = btree->search(key, node->item, node->count, lr, &f);
206 iter->item = (void*)node->item[k - lr];
212 node = node->branch[k];
221 int btree_walk_backward(const struct btree *btree,
222 btree_action_t action, void *ctx)
224 return node_walk_backward(btree->root, action, ctx);
227 int btree_walk_forward(const struct btree *btree,
228 btree_action_t action, void *ctx)
230 return node_walk_forward(btree->root, action, ctx);
233 void btree_insert_at(btree_iterator iter, const void *item)
235 const void *x = item;
236 struct btree_node *xr = NULL;
237 struct btree_node *p;
238 struct btree *btree = iter->btree;
240 /* btree_insert_at always sets iter->item to item. */
241 iter->item = (void*)item;
244 * If node is not a leaf, fall to the end of the left branch of item[k]
245 * so that it will be a leaf. This does not modify the iterator's logical
248 if (iter->node->depth)
252 * First try inserting item into this node.
253 * If it's too big, split it, and repeat by
254 * trying to insert the median and right subtree into parent.
256 if (iter->node->count < MAX) {
257 node_insert(x, xr, iter->node, iter->k);
261 node_split(&x, &xr, iter->node, iter->k);
266 if (iter->node->count < MAX) {
267 node_insert(x, xr, iter->node, iter->k);
273 * If splitting came all the way up to the root, create a new root whose
274 * left branch is the current root, median is x, and right branch is the
275 * half split off from the root.
277 assert(iter->node == btree->root);
281 p->depth = btree->root->depth + 1;
283 p->branch[0] = btree->root;
284 btree->root->parent = p;
297 int btree_remove_at(btree_iterator iter)
299 struct btree *btree = iter->btree;
300 struct btree_node *root;
302 if (!btree_deref(iter))
305 if (!iter->node->depth) {
306 node_remove_leaf_item(iter->node, iter->k);
307 if (iter->node->count >= MIN || !iter->node->parent)
311 * We can't remove an item from an internal node, so we'll replace it
312 * with its successor (which will always be in a leaf), then remove
313 * the original copy of the successor.
316 /* Save pointer to condemned item. */
317 const void **x = &iter->node->item[iter->k];
319 /* Descend to successor. */
323 /* Replace condemned item with successor. */
324 *x = iter->node->item[0];
326 /* Remove successor. */
327 node_remove_leaf_item(iter->node, 0);
331 * Restore nodes that fall under their minimum count. This may
332 * propagate all the way up to the root.
335 if (iter->node->count >= MIN)
339 node_restore(iter->node, iter->k);
343 * If combining came all the way up to the root, and it has no more
344 * dividers, delete it and make its only branch the root.
347 assert(root == btree->root);
348 assert(root->depth > 0);
349 if (root->count == 0) {
350 btree->root = root->branch[0];
351 btree->root->parent = NULL;
362 * ascends iterator a until it matches iterator b's depth.
364 * Returns -1 if they end up on the same k (meaning a < b).
365 * Returns 0 otherwise.
367 static int elevate(btree_iterator a, btree_iterator b)
369 while (a->node->depth < b->node->depth)
377 int btree_cmp_iters(const btree_iterator iter_a, const btree_iterator iter_b)
379 btree_iterator a = {*iter_a}, b = {*iter_b};
385 /* Check cases where one or both iterators are at the end. */
391 /* Bring iterators to the same depth. */
392 if (a->node->depth < b->node->depth) {
395 } else if (a->node->depth > b->node->depth) {
400 /* Bring iterators to the same node. */
401 while (a->node != b->node) {
406 /* Now we can compare by k directly. */
415 /********************* Built-in ordering functions *******************/
417 btree_search_implement
421 int c = strcmp(a, b),
427 /************************* Private functions *************************/
429 static struct btree_node *node_alloc(int internal)
431 struct btree_node *node;
432 size_t isize = internal
433 ? sizeof(struct btree_node*) * (BTREE_ITEM_MAX+1)
435 node = malloc(sizeof(struct btree_node) + isize);
439 static void node_delete(struct btree_node *node, struct btree *btree)
441 unsigned int i, count = node->count;
444 if (btree->destroy) {
445 for (i=0; i<count; i++)
446 btree->destroy((void*)node->item[i], btree->destroy_ctx);
449 for (i=0; i<count; i++) {
450 node_delete(node->branch[i], btree);
452 btree->destroy((void*)node->item[i], btree->destroy_ctx);
454 node_delete(node->branch[count], btree);
460 /* Set iter to beginning of branch pointed to by iter. */
461 static void branch_begin(btree_iterator iter)
463 struct btree_node *node = iter->node->branch[iter->k];
464 unsigned int depth = node->depth;
466 node = node->branch[0];
471 /* Set iter to end of branch pointed to by iter. */
472 static void branch_end(btree_iterator iter)
474 struct btree_node *node = iter->node->branch[iter->k];
475 unsigned int depth = node->depth;
477 node = node->branch[node->count];
479 iter->k = node->count;
482 /* Traverse to the beginning or end of node, depending on lr. */
483 static void begin_end_lr(btree_iterator iter, struct btree_node *node, int lr)
486 iter->k = lr ? node->count : 0;
488 (lr ? branch_end : branch_begin)(iter);
492 * Inserts item x and right branch xr into node p at position k.
494 * Assumes p exists and has enough room.
495 * Ignores xr if p is a leaf.
497 static void node_insert(const void *x, struct btree_node *xr,
498 struct btree_node *p, unsigned int k)
502 for (i = p->count; i-- > k;)
503 p->item[i+1] = p->item[i];
508 for (i = p->count+1; i-- > k;) {
509 p->branch[i+1] = p->branch[i];
510 p->branch[i+1]->k = i+1;
521 * Inserts item *x and subtree *xr into node p at position k, splitting it into
522 * nodes p and *xr with median item *x.
524 * Assumes p->count == MAX.
525 * Ignores original *xr if p is a leaf, but always sets it.
527 static void node_split(const void **x, struct btree_node **xr,
528 struct btree_node *p, unsigned int k)
530 unsigned int i, split;
531 struct btree_node *l = p, *r;
534 * If k <= MIN, item will be inserted into left subtree, so give l
535 * fewer items initially.
536 * Otherwise, item will be inserted into right subtree, so give r
537 * fewer items initially.
545 * If l->depth is 0, allocate a leaf node.
546 * Otherwise, allocate an internal node.
548 r = node_alloc(l->depth);
550 /* l and r will be siblings, so they will have the same parent and depth. */
551 r->parent = l->parent;
555 * Initialize items/branches of right side.
556 * Do not initialize r's leftmost branch yet because we don't know
557 * whether it will be l's current rightmost branch or if *xr will
560 for (i = split; i < MAX; i++)
561 r->item[i-split] = l->item[i];
563 for (i = split+1; i <= MAX; i++) {
564 r->branch[i-split] = l->branch[i];
565 r->branch[i-split]->parent = r;
566 r->branch[i-split]->k = i-split;
572 r->count = MAX - split;
575 * The nodes are now split, but the key isn't inserted yet.
577 * Insert key into left or right half,
578 * depending on which side it fell on.
581 node_insert(*x, *xr, l, k);
583 node_insert(*x, *xr, r, k - split);
586 * Give l's rightmost branch to r because l's rightmost item
587 * is going up to become the median.
590 r->branch[0] = l->branch[l->count];
591 r->branch[0]->parent = r;
596 * Take up l's rightmost item to make it the median.
597 * That item's right branch is now r.
599 *x = l->item[--l->count];
604 * Removes item k from node p, shifting successor items back and
605 * decrementing the count.
607 * Assumes node p has the item k and is a leaf.
609 static void node_remove_leaf_item(struct btree_node *node, unsigned int k)
612 for (i = k+1; i < node->count; i++)
613 node->item[i-1] = node->item[i];
617 static void move_left(struct btree_node *node, unsigned int k);
618 static void move_right(struct btree_node *node, unsigned int k);
619 static void combine(struct btree_node *node, unsigned int k);
622 * Fixes node->branch[k]'s problem of having one less than MIN items.
623 * May or may not cause node to fall below MIN items, depending on whether
624 * two branches are combined or not.
626 void node_restore(struct btree_node *node, unsigned int k)
629 if (node->branch[1]->count > MIN)
633 } else if (k == node->count) {
634 if (node->branch[k-1]->count > MIN)
635 move_right(node, k-1);
638 } else if (node->branch[k-1]->count > MIN) {
639 move_right(node, k-1);
640 } else if (node->branch[k+1]->count > MIN) {
647 static void move_left(struct btree_node *node, unsigned int k)
649 struct btree_node *l = node->branch[k], *r = node->branch[k+1], *mv;
652 l->item[l->count] = node->item[k];
653 node->item[k] = r->item[0];
654 for (i = 1; i < r->count; i++)
655 r->item[i-1] = r->item[i];
659 l->branch[l->count+1] = mv;
663 for (i = 1; i <= r->count; i++) {
664 r->branch[i-1] = r->branch[i];
665 r->branch[i-1]->k = i-1;
673 static void move_right(struct btree_node *node, unsigned int k)
675 struct btree_node *l = node->branch[k], *r = node->branch[k+1];
678 for (i = r->count; i--;)
679 r->item[i+1] = r->item[i];
680 r->item[0] = node->item[k];
681 node->item[k] = l->item[l->count-1];
684 for (i = r->count+1; i--;) {
685 r->branch[i+1] = r->branch[i];
686 r->branch[i+1]->k = i+1;
688 r->branch[0] = l->branch[l->count];
689 r->branch[0]->parent = r;
697 /* Combine node->branch[k] and node->branch[k+1]. */
698 static void combine(struct btree_node *node, unsigned int k)
700 struct btree_node *l = node->branch[k], *r = node->branch[k+1], *mv;
701 const void **o = &l->item[l->count];
704 //append node->item[k] followed by right node's items to left node
705 *o++ = node->item[k];
706 for (i=0; i<r->count; i++)
709 //if applicable, append right node's branches to left node
711 for (i=0; i<=r->count; i++) {
713 l->branch[l->count + i + 1] = mv;
715 mv->k = l->count + i + 1;
719 //remove k and its right branch from parent node
720 for (i = k+1; i < node->count; i++) {
721 node->item[i-1] = node->item[i];
722 node->branch[i] = node->branch[i+1];
723 node->branch[i]->k = i;
726 //don't forget to update the left and parent node's counts and to free the right node
727 l->count += r->count + 1;
732 static int node_walk_backward(const struct btree_node *node,
733 btree_action_t action, void *ctx)
735 unsigned int i, count = node->count;
739 if (!action((void*)node->item[i], ctx))
742 if (!node_walk_backward(node->branch[count], action, ctx))
744 for (i=count; i--;) {
745 if (!action((void*)node->item[i], ctx))
747 if (!node_walk_backward(node->branch[i], action, ctx))
755 static int node_walk_forward(const struct btree_node *node,
756 btree_action_t action, void *ctx)
758 unsigned int i, count = node->count;
761 for (i=0; i<count; i++)
762 if (!action((void*)node->item[i], ctx))
765 for (i=0; i<count; i++) {
766 if (!node_walk_forward(node->branch[i], action, ctx))
768 if (!action((void*)node->item[i], ctx))
771 if (!node_walk_forward(node->branch[count], action, ctx))