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;
83 void btree_delete(struct btree *btree)
85 node_delete(btree->root, btree);
89 int btree_begin_end_lr(const struct btree *btree, btree_iterator iter, int lr)
91 struct btree_node *node;
93 iter->btree = (struct btree *)btree;
94 begin_end_lr(iter, btree->root, lr);
96 /* Set iter->item if any items exist. */
99 iter->item = (void*)node->item[iter->k - lr];
106 int btree_deref(btree_iterator iter)
108 if (iter->k >= iter->node->count) {
109 struct btree_iterator_s tmp = *iter;
115 } while (iter->k >= iter->node->count);
118 iter->item = (void*)iter->node->item[iter->k];
122 int btree_prev(btree_iterator iter)
124 if (iter->node->depth) {
126 } else if (iter->k == 0) {
127 struct btree_iterator_s tmp = *iter;
133 } while (iter->k == 0);
136 iter->item = (void*)iter->node->item[--iter->k];
140 int btree_next(btree_iterator iter)
142 int ret = btree_deref(iter);
145 if (iter->node->depth)
151 int btree_find_lr(const struct btree *btree, const void *key,
152 btree_iterator iter, int lr)
154 struct btree_node *node = btree->root;
159 iter->btree = (struct btree *)btree;
165 k = btree->search(key, node->item, node->count, lr, &f);
168 iter->item = (void*)node->item[k - lr];
174 node = node->branch[k];
183 int btree_walk_backward(const struct btree *btree,
184 btree_action_t action, void *ctx)
186 return node_walk_backward(btree->root, action, ctx);
189 int btree_walk_forward(const struct btree *btree,
190 btree_action_t action, void *ctx)
192 return node_walk_forward(btree->root, action, ctx);
195 void btree_insert_at(btree_iterator iter, const void *item)
197 const void *x = item;
198 struct btree_node *xr = NULL;
199 struct btree_node *p;
200 struct btree *btree = iter->btree;
202 /* btree_insert_at always sets iter->item to item. */
203 iter->item = (void*)item;
206 * If node is not a leaf, fall to the end of the left branch of item[k]
207 * so that it will be a leaf. This does not modify the iterator's logical
210 if (iter->node->depth)
214 * First try inserting item into this node.
215 * If it's too big, split it, and repeat by
216 * trying to insert the median and right subtree into parent.
218 if (iter->node->count < MAX) {
219 node_insert(x, xr, iter->node, iter->k);
223 node_split(&x, &xr, iter->node, iter->k);
228 if (iter->node->count < MAX) {
229 node_insert(x, xr, iter->node, iter->k);
235 * If splitting came all the way up to the root, create a new root whose
236 * left branch is the current root, median is x, and right branch is the
237 * half split off from the root.
239 assert(iter->node == btree->root);
243 p->depth = btree->root->depth + 1;
245 p->branch[0] = btree->root;
246 btree->root->parent = p;
259 int btree_remove_at(btree_iterator iter)
261 struct btree *btree = iter->btree;
262 struct btree_node *root;
264 if (!btree_deref(iter))
267 if (!iter->node->depth) {
268 node_remove_leaf_item(iter->node, iter->k);
269 if (iter->node->count >= MIN || !iter->node->parent)
273 * We can't remove an item from an internal node, so we'll replace it
274 * with its successor (which will always be in a leaf), then remove
275 * the original copy of the successor.
278 /* Save pointer to condemned item. */
279 const void **x = &iter->node->item[iter->k];
281 /* Descend to successor. */
285 /* Replace condemned item with successor. */
286 *x = iter->node->item[0];
288 /* Remove successor. */
289 node_remove_leaf_item(iter->node, 0);
293 * Restore nodes that fall under their minimum count. This may
294 * propagate all the way up to the root.
297 if (iter->node->count >= MIN)
301 node_restore(iter->node, iter->k);
305 * If combining came all the way up to the root, and it has no more
306 * dividers, delete it and make its only branch the root.
309 assert(root == btree->root);
310 assert(root->depth > 0);
311 if (root->count == 0) {
312 btree->root = root->branch[0];
313 btree->root->parent = NULL;
324 * ascends iterator a until it matches iterator b's depth.
326 * Returns -1 if they end up on the same k (meaning a < b).
327 * Returns 0 otherwise.
329 static int elevate(btree_iterator a, btree_iterator b)
331 while (a->node->depth < b->node->depth)
339 int btree_cmp_iters(const btree_iterator iter_a, const btree_iterator iter_b)
341 btree_iterator a = {*iter_a}, b = {*iter_b};
347 /* Check cases where one or both iterators are at the end. */
353 /* Bring iterators to the same depth. */
354 if (a->node->depth < b->node->depth) {
357 } else if (a->node->depth > b->node->depth) {
362 /* Bring iterators to the same node. */
363 while (a->node != b->node) {
368 /* Now we can compare by k directly. */
378 /************************* Private functions *************************/
380 static struct btree_node *node_alloc(int internal)
382 struct btree_node *node;
383 size_t isize = internal
384 ? sizeof(struct btree_node*) * (BTREE_ITEM_MAX+1)
386 node = malloc(sizeof(struct btree_node) + isize);
390 static void node_delete(struct btree_node *node, struct btree *btree)
392 unsigned int i, count = node->count;
395 if (btree->destroy) {
396 for (i=0; i<count; i++)
397 btree->destroy((void*)node->item[i], btree->destroy_ctx);
400 for (i=0; i<count; i++) {
401 node_delete(node->branch[i], btree);
403 btree->destroy((void*)node->item[i], btree->destroy_ctx);
405 node_delete(node->branch[count], btree);
411 /* Set iter to beginning of branch pointed to by iter. */
412 static void branch_begin(btree_iterator iter)
414 struct btree_node *node = iter->node->branch[iter->k];
415 unsigned int depth = node->depth;
417 node = node->branch[0];
422 /* Set iter to end of branch pointed to by iter. */
423 static void branch_end(btree_iterator iter)
425 struct btree_node *node = iter->node->branch[iter->k];
426 unsigned int depth = node->depth;
428 node = node->branch[node->count];
430 iter->k = node->count;
433 /* Traverse to the beginning or end of node, depending on lr. */
434 static void begin_end_lr(btree_iterator iter, struct btree_node *node, int lr)
437 iter->k = lr ? node->count : 0;
439 (lr ? branch_end : branch_begin)(iter);
443 * Inserts item x and right branch xr into node p at position k.
445 * Assumes p exists and has enough room.
446 * Ignores xr if p is a leaf.
448 static void node_insert(const void *x, struct btree_node *xr,
449 struct btree_node *p, unsigned int k)
453 for (i = p->count; i-- > k;)
454 p->item[i+1] = p->item[i];
459 for (i = p->count+1; i-- > k;) {
460 p->branch[i+1] = p->branch[i];
461 p->branch[i+1]->k = i+1;
472 * Inserts item *x and subtree *xr into node p at position k, splitting it into
473 * nodes p and *xr with median item *x.
475 * Assumes p->count == MAX.
476 * Ignores original *xr if p is a leaf, but always sets it.
478 static void node_split(const void **x, struct btree_node **xr,
479 struct btree_node *p, unsigned int k)
481 unsigned int i, split;
482 struct btree_node *l = p, *r;
485 * If k <= MIN, item will be inserted into left subtree, so give l
486 * fewer items initially.
487 * Otherwise, item will be inserted into right subtree, so give r
488 * fewer items initially.
496 * If l->depth is 0, allocate a leaf node.
497 * Otherwise, allocate an internal node.
499 r = node_alloc(l->depth);
501 /* l and r will be siblings, so they will have the same parent and depth. */
502 r->parent = l->parent;
506 * Initialize items/branches of right side.
507 * Do not initialize r's leftmost branch yet because we don't know
508 * whether it will be l's current rightmost branch or if *xr will
511 for (i = split; i < MAX; i++)
512 r->item[i-split] = l->item[i];
514 for (i = split+1; i <= MAX; i++) {
515 r->branch[i-split] = l->branch[i];
516 r->branch[i-split]->parent = r;
517 r->branch[i-split]->k = i-split;
523 r->count = MAX - split;
526 * The nodes are now split, but the key isn't inserted yet.
528 * Insert key into left or right half,
529 * depending on which side it fell on.
532 node_insert(*x, *xr, l, k);
534 node_insert(*x, *xr, r, k - split);
537 * Give l's rightmost branch to r because l's rightmost item
538 * is going up to become the median.
541 r->branch[0] = l->branch[l->count];
542 r->branch[0]->parent = r;
547 * Take up l's rightmost item to make it the median.
548 * That item's right branch is now r.
550 *x = l->item[--l->count];
555 * Removes item k from node p, shifting successor items back and
556 * decrementing the count.
558 * Assumes node p has the item k and is a leaf.
560 static void node_remove_leaf_item(struct btree_node *node, unsigned int k)
563 for (i = k+1; i < node->count; i++)
564 node->item[i-1] = node->item[i];
568 static void move_left(struct btree_node *node, unsigned int k);
569 static void move_right(struct btree_node *node, unsigned int k);
570 static void combine(struct btree_node *node, unsigned int k);
573 * Fixes node->branch[k]'s problem of having one less than MIN items.
574 * May or may not cause node to fall below MIN items, depending on whether
575 * two branches are combined or not.
577 void node_restore(struct btree_node *node, unsigned int k)
580 if (node->branch[1]->count > MIN)
584 } else if (k == node->count) {
585 if (node->branch[k-1]->count > MIN)
586 move_right(node, k-1);
589 } else if (node->branch[k-1]->count > MIN) {
590 move_right(node, k-1);
591 } else if (node->branch[k+1]->count > MIN) {
598 static void move_left(struct btree_node *node, unsigned int k)
600 struct btree_node *l = node->branch[k], *r = node->branch[k+1], *mv;
603 l->item[l->count] = node->item[k];
604 node->item[k] = r->item[0];
605 for (i = 1; i < r->count; i++)
606 r->item[i-1] = r->item[i];
610 l->branch[l->count+1] = mv;
614 for (i = 1; i <= r->count; i++) {
615 r->branch[i-1] = r->branch[i];
616 r->branch[i-1]->k = i-1;
624 static void move_right(struct btree_node *node, unsigned int k)
626 struct btree_node *l = node->branch[k], *r = node->branch[k+1];
629 for (i = r->count; i--;)
630 r->item[i+1] = r->item[i];
631 r->item[0] = node->item[k];
632 node->item[k] = l->item[l->count-1];
635 for (i = r->count+1; i--;) {
636 r->branch[i+1] = r->branch[i];
637 r->branch[i+1]->k = i+1;
639 r->branch[0] = l->branch[l->count];
640 r->branch[0]->parent = r;
648 /* Combine node->branch[k] and node->branch[k+1]. */
649 static void combine(struct btree_node *node, unsigned int k)
651 struct btree_node *l = node->branch[k], *r = node->branch[k+1], *mv;
652 const void **o = &l->item[l->count];
655 //append node->item[k] followed by right node's items to left node
656 *o++ = node->item[k];
657 for (i=0; i<r->count; i++)
660 //if applicable, append right node's branches to left node
662 for (i=0; i<=r->count; i++) {
664 l->branch[l->count + i + 1] = mv;
666 mv->k = l->count + i + 1;
670 //remove k and its right branch from parent node
671 for (i = k+1; i < node->count; i++) {
672 node->item[i-1] = node->item[i];
673 node->branch[i] = node->branch[i+1];
674 node->branch[i]->k = i;
677 //don't forget to update the left and parent node's counts and to free the right node
678 l->count += r->count + 1;
683 static int node_walk_backward(const struct btree_node *node,
684 btree_action_t action, void *ctx)
686 unsigned int i, count = node->count;
690 if (!action((void*)node->item[i], ctx))
693 if (!node_walk_backward(node->branch[count], action, ctx))
695 for (i=count; i--;) {
696 if (!action((void*)node->item[i], ctx))
698 if (!node_walk_backward(node->branch[i], action, ctx))
706 static int node_walk_forward(const struct btree_node *node,
707 btree_action_t action, void *ctx)
709 unsigned int i, count = node->count;
712 for (i=0; i<count; i++)
713 if (!action((void*)node->item[i], ctx))
716 for (i=0; i<count; i++) {
717 if (!node_walk_forward(node->branch[i], action, ctx))
719 if (!action((void*)node->item[i], ctx))
722 if (!node_walk_forward(node->branch[count], action, ctx))