2 * Copyright (C) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to deal
6 * in the Software without restriction, including without limitation the rights
7 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 * copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
29 #define MAX (BTREE_ITEM_MAX)
30 #define MIN (BTREE_ITEM_MAX >> 1)
32 static struct btree_node *node_alloc(int internal);
33 static void node_delete(struct btree_node *node, struct btree *btree);
35 static void branch_begin(btree_iterator iter);
36 static void branch_end(btree_iterator iter);
37 static void begin_end_lr(btree_iterator iter, struct btree_node *node, int lr);
40 * If iter->node has parent, returns 1 and ascends the iterator such that
41 * iter->node->branch[iter->k] will be what iter->node was.
43 * If iter->node does not have a parent (is a root), returns 0 and leaves the
46 #define ascend(iter) ((iter)->node->parent \
47 ? (iter)->k = (iter)->node->k, (iter)->node = (iter)->node->parent, 1 \
50 static void node_insert(const void *x, struct btree_node *xr,
51 struct btree_node *p, unsigned int k);
52 static void node_split(const void **x, struct btree_node **xr,
53 struct btree_node *p, unsigned int k);
55 static void node_remove_leaf_item(struct btree_node *node, unsigned int k);
56 void node_restore(struct btree_node *node, unsigned int k);
58 static int node_walk_backward(const struct btree_node *node,
59 btree_action_t action, void *ctx);
60 static int node_walk_forward(const struct btree_node *node,
61 btree_action_t action, void *ctx);
64 /************************* Public functions *************************/
66 struct btree *btree_new(btree_search_t search)
68 struct btree *btree = calloc(1, sizeof(struct btree));
69 struct btree_node *node = node_alloc(0);
74 btree->search = search;
79 void btree_delete(struct btree *btree)
81 node_delete(btree->root, btree);
85 bool btree_insert(struct btree *btree, const void *item)
89 if (btree_find_last(btree, item, iter) && !btree->multi)
92 btree_insert_at(iter, item);
96 bool btree_remove(struct btree *btree, const void *key)
100 bool multi = btree->multi;
103 if (btree_find_first(btree, key, iter)) {
104 btree_remove_at(iter);
112 void *btree_lookup(struct btree *btree, const void *key)
116 if (btree_find_first(btree, key, iter))
122 int btree_begin_end_lr(const struct btree *btree, btree_iterator iter, int lr)
124 struct btree_node *node;
126 iter->btree = (struct btree *)btree;
127 begin_end_lr(iter, btree->root, lr);
129 /* Set iter->item if any items exist. */
132 iter->item = (void*)node->item[iter->k - lr];
139 int btree_deref(btree_iterator iter)
141 if (iter->k >= iter->node->count) {
142 struct btree_iterator_s tmp = *iter;
148 } while (iter->k >= iter->node->count);
151 iter->item = (void*)iter->node->item[iter->k];
155 int btree_prev(btree_iterator iter)
157 if (iter->node->depth) {
159 } else if (iter->k == 0) {
160 struct btree_iterator_s tmp = *iter;
166 } while (iter->k == 0);
169 iter->item = (void*)iter->node->item[--iter->k];
173 int btree_next(btree_iterator iter)
175 int ret = btree_deref(iter);
178 if (iter->node->depth)
184 int btree_find_lr(const struct btree *btree, const void *key,
185 btree_iterator iter, int lr)
187 struct btree_node *node = btree->root;
192 iter->btree = (struct btree *)btree;
198 k = btree->search(key, node->item, node->count, lr, &f);
201 iter->item = (void*)node->item[k - lr];
207 node = node->branch[k];
216 int btree_walk_backward(const struct btree *btree,
217 btree_action_t action, void *ctx)
219 return node_walk_backward(btree->root, action, ctx);
222 int btree_walk_forward(const struct btree *btree,
223 btree_action_t action, void *ctx)
225 return node_walk_forward(btree->root, action, ctx);
228 void btree_insert_at(btree_iterator iter, const void *item)
230 const void *x = item;
231 struct btree_node *xr = NULL;
232 struct btree_node *p;
233 struct btree *btree = iter->btree;
235 /* btree_insert_at always sets iter->item to item. */
236 iter->item = (void*)item;
239 * If node is not a leaf, fall to the end of the left branch of item[k]
240 * so that it will be a leaf. This does not modify the iterator's logical
243 if (iter->node->depth)
247 * First try inserting item into this node.
248 * If it's too big, split it, and repeat by
249 * trying to insert the median and right subtree into parent.
251 if (iter->node->count < MAX) {
252 node_insert(x, xr, iter->node, iter->k);
256 node_split(&x, &xr, iter->node, iter->k);
261 if (iter->node->count < MAX) {
262 node_insert(x, xr, iter->node, iter->k);
268 * If splitting came all the way up to the root, create a new root whose
269 * left branch is the current root, median is x, and right branch is the
270 * half split off from the root.
272 assert(iter->node == btree->root);
276 p->depth = btree->root->depth + 1;
278 p->branch[0] = btree->root;
279 btree->root->parent = p;
292 int btree_remove_at(btree_iterator iter)
294 struct btree *btree = iter->btree;
295 struct btree_node *root;
297 if (!btree_deref(iter))
300 if (!iter->node->depth) {
301 node_remove_leaf_item(iter->node, iter->k);
302 if (iter->node->count >= MIN || !iter->node->parent)
306 * We can't remove an item from an internal node, so we'll replace it
307 * with its successor (which will always be in a leaf), then remove
308 * the original copy of the successor.
311 /* Save pointer to condemned item. */
312 const void **x = &iter->node->item[iter->k];
314 /* Descend to successor. */
318 /* Replace condemned item with successor. */
319 *x = iter->node->item[0];
321 /* Remove successor. */
322 node_remove_leaf_item(iter->node, 0);
326 * Restore nodes that fall under their minimum count. This may
327 * propagate all the way up to the root.
330 if (iter->node->count >= MIN)
334 node_restore(iter->node, iter->k);
338 * If combining came all the way up to the root, and it has no more
339 * dividers, delete it and make its only branch the root.
342 assert(root == btree->root);
343 assert(root->depth > 0);
344 if (root->count == 0) {
345 btree->root = root->branch[0];
346 btree->root->parent = NULL;
357 * ascends iterator a until it matches iterator b's depth.
359 * Returns -1 if they end up on the same k (meaning a < b).
360 * Returns 0 otherwise.
362 static int elevate(btree_iterator a, btree_iterator b)
364 while (a->node->depth < b->node->depth)
372 int btree_cmp_iters(const btree_iterator iter_a, const btree_iterator iter_b)
374 btree_iterator a = {*iter_a}, b = {*iter_b};
380 /* Check cases where one or both iterators are at the end. */
386 /* Bring iterators to the same depth. */
387 if (a->node->depth < b->node->depth) {
390 } else if (a->node->depth > b->node->depth) {
395 /* Bring iterators to the same node. */
396 while (a->node != b->node) {
401 /* Now we can compare by k directly. */
410 /********************* Built-in ordering functions *******************/
412 btree_search_implement
416 int c = strcmp(a, b),
422 /************************* Private functions *************************/
424 static struct btree_node *node_alloc(int internal)
426 struct btree_node *node;
427 size_t isize = internal
428 ? sizeof(struct btree_node*) * (BTREE_ITEM_MAX+1)
430 node = malloc(sizeof(struct btree_node) + isize);
434 static void node_delete(struct btree_node *node, struct btree *btree)
436 unsigned int i, count = node->count;
439 if (btree->destroy) {
440 for (i=0; i<count; i++)
441 btree->destroy((void*)node->item[i], btree->destroy_ctx);
444 for (i=0; i<count; i++) {
445 node_delete(node->branch[i], btree);
447 btree->destroy((void*)node->item[i], btree->destroy_ctx);
449 node_delete(node->branch[count], btree);
455 /* Set iter to beginning of branch pointed to by iter. */
456 static void branch_begin(btree_iterator iter)
458 struct btree_node *node = iter->node->branch[iter->k];
459 unsigned int depth = node->depth;
461 node = node->branch[0];
466 /* Set iter to end of branch pointed to by iter. */
467 static void branch_end(btree_iterator iter)
469 struct btree_node *node = iter->node->branch[iter->k];
470 unsigned int depth = node->depth;
472 node = node->branch[node->count];
474 iter->k = node->count;
477 /* Traverse to the beginning or end of node, depending on lr. */
478 static void begin_end_lr(btree_iterator iter, struct btree_node *node, int lr)
481 iter->k = lr ? node->count : 0;
483 (lr ? branch_end : branch_begin)(iter);
487 * Inserts item x and right branch xr into node p at position k.
489 * Assumes p exists and has enough room.
490 * Ignores xr if p is a leaf.
492 static void node_insert(const void *x, struct btree_node *xr,
493 struct btree_node *p, unsigned int k)
497 for (i = p->count; i-- > k;)
498 p->item[i+1] = p->item[i];
503 for (i = p->count+1; i-- > k;) {
504 p->branch[i+1] = p->branch[i];
505 p->branch[i+1]->k = i+1;
516 * Inserts item *x and subtree *xr into node p at position k, splitting it into
517 * nodes p and *xr with median item *x.
519 * Assumes p->count == MAX.
520 * Ignores original *xr if p is a leaf, but always sets it.
522 static void node_split(const void **x, struct btree_node **xr,
523 struct btree_node *p, unsigned int k)
525 unsigned int i, split;
526 struct btree_node *l = p, *r;
529 * If k <= MIN, item will be inserted into left subtree, so give l
530 * fewer items initially.
531 * Otherwise, item will be inserted into right subtree, so give r
532 * fewer items initially.
540 * If l->depth is 0, allocate a leaf node.
541 * Otherwise, allocate an internal node.
543 r = node_alloc(l->depth);
545 /* l and r will be siblings, so they will have the same parent and depth. */
546 r->parent = l->parent;
550 * Initialize items/branches of right side.
551 * Do not initialize r's leftmost branch yet because we don't know
552 * whether it will be l's current rightmost branch or if *xr will
555 for (i = split; i < MAX; i++)
556 r->item[i-split] = l->item[i];
558 for (i = split+1; i <= MAX; i++) {
559 r->branch[i-split] = l->branch[i];
560 r->branch[i-split]->parent = r;
561 r->branch[i-split]->k = i-split;
567 r->count = MAX - split;
570 * The nodes are now split, but the key isn't inserted yet.
572 * Insert key into left or right half,
573 * depending on which side it fell on.
576 node_insert(*x, *xr, l, k);
578 node_insert(*x, *xr, r, k - split);
581 * Give l's rightmost branch to r because l's rightmost item
582 * is going up to become the median.
585 r->branch[0] = l->branch[l->count];
586 r->branch[0]->parent = r;
591 * Take up l's rightmost item to make it the median.
592 * That item's right branch is now r.
594 *x = l->item[--l->count];
599 * Removes item k from node p, shifting successor items back and
600 * decrementing the count.
602 * Assumes node p has the item k and is a leaf.
604 static void node_remove_leaf_item(struct btree_node *node, unsigned int k)
607 for (i = k+1; i < node->count; i++)
608 node->item[i-1] = node->item[i];
612 static void move_left(struct btree_node *node, unsigned int k);
613 static void move_right(struct btree_node *node, unsigned int k);
614 static void combine(struct btree_node *node, unsigned int k);
617 * Fixes node->branch[k]'s problem of having one less than MIN items.
618 * May or may not cause node to fall below MIN items, depending on whether
619 * two branches are combined or not.
621 void node_restore(struct btree_node *node, unsigned int k)
624 if (node->branch[1]->count > MIN)
628 } else if (k == node->count) {
629 if (node->branch[k-1]->count > MIN)
630 move_right(node, k-1);
633 } else if (node->branch[k-1]->count > MIN) {
634 move_right(node, k-1);
635 } else if (node->branch[k+1]->count > MIN) {
642 static void move_left(struct btree_node *node, unsigned int k)
644 struct btree_node *l = node->branch[k], *r = node->branch[k+1], *mv;
647 l->item[l->count] = node->item[k];
648 node->item[k] = r->item[0];
649 for (i = 1; i < r->count; i++)
650 r->item[i-1] = r->item[i];
654 l->branch[l->count+1] = mv;
658 for (i = 1; i <= r->count; i++) {
659 r->branch[i-1] = r->branch[i];
660 r->branch[i-1]->k = i-1;
668 static void move_right(struct btree_node *node, unsigned int k)
670 struct btree_node *l = node->branch[k], *r = node->branch[k+1];
673 for (i = r->count; i--;)
674 r->item[i+1] = r->item[i];
675 r->item[0] = node->item[k];
676 node->item[k] = l->item[l->count-1];
679 for (i = r->count+1; i--;) {
680 r->branch[i+1] = r->branch[i];
681 r->branch[i+1]->k = i+1;
683 r->branch[0] = l->branch[l->count];
684 r->branch[0]->parent = r;
692 /* Combine node->branch[k] and node->branch[k+1]. */
693 static void combine(struct btree_node *node, unsigned int k)
695 struct btree_node *l = node->branch[k], *r = node->branch[k+1], *mv;
696 const void **o = &l->item[l->count];
699 //append node->item[k] followed by right node's items to left node
700 *o++ = node->item[k];
701 for (i=0; i<r->count; i++)
704 //if applicable, append right node's branches to left node
706 for (i=0; i<=r->count; i++) {
708 l->branch[l->count + i + 1] = mv;
710 mv->k = l->count + i + 1;
714 //remove k and its right branch from parent node
715 for (i = k+1; i < node->count; i++) {
716 node->item[i-1] = node->item[i];
717 node->branch[i] = node->branch[i+1];
718 node->branch[i]->k = i;
721 //don't forget to update the left and parent node's counts and to free the right node
722 l->count += r->count + 1;
727 static int node_walk_backward(const struct btree_node *node,
728 btree_action_t action, void *ctx)
730 unsigned int i, count = node->count;
734 if (!action((void*)node->item[i], ctx))
737 if (!node_walk_backward(node->branch[count], action, ctx))
739 for (i=count; i--;) {
740 if (!action((void*)node->item[i], ctx))
742 if (!node_walk_backward(node->branch[i], action, ctx))
750 static int node_walk_forward(const struct btree_node *node,
751 btree_action_t action, void *ctx)
753 unsigned int i, count = node->count;
756 for (i=0; i<count; i++)
757 if (!action((void*)node->item[i], ctx))
760 for (i=0; i<count; i++) {
761 if (!node_walk_forward(node->branch[i], action, ctx))
763 if (!action((void*)node->item[i], ctx))
766 if (!node_walk_forward(node->branch[count], action, ctx))