Add licences/ dir and symlinks for a bit more clarity.
[ccan] / ccan / btree / btree.c
1 /*
2         Copyright (c) 2010  Joseph A. Adams
3         All rights reserved.
4         
5         Redistribution and use in source and binary forms, with or without
6         modification, are permitted provided that the following conditions
7         are met:
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.
15         
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.
26 */
27
28 #include "btree.h"
29
30 #include <assert.h>
31 #include <stdlib.h>
32 #include <stdio.h>
33
34 #define MAX (BTREE_ITEM_MAX)
35 #define MIN (BTREE_ITEM_MAX >> 1)
36
37 static struct btree_node *node_alloc(int internal);
38 static void node_delete(struct btree_node *node, struct btree *btree);
39
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);
43
44 /*
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.
47  *
48  * If iter->node does not have a parent (is a root), returns 0 and leaves the
49  * iterator untouched.
50  */
51 #define ascend(iter) ((iter)->node->parent \
52         ? (iter)->k = (iter)->node->k, (iter)->node = (iter)->node->parent, 1 \
53         : 0)
54
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);
59
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);
62
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);
67
68
69 /************************* Public functions *************************/
70
71 struct btree *btree_new(btree_search_t search)
72 {
73         struct btree *btree = calloc(1, sizeof(struct btree));
74         struct btree_node *node = node_alloc(0);
75                 node->parent = NULL;
76                 node->count = 0;
77                 node->depth = 0;
78         btree->root = node;
79         btree->search = search;
80         btree->multi = false;
81         return btree;
82 }
83
84 void btree_delete(struct btree *btree)
85 {
86         node_delete(btree->root, btree);
87         free(btree);
88 }
89
90 bool btree_insert(struct btree *btree, const void *item)
91 {
92         btree_iterator iter;
93         
94         if (btree_find_last(btree, item, iter) && !btree->multi)
95                 return false;
96         
97         btree_insert_at(iter, item);
98         return true;
99 }
100
101 bool btree_remove(struct btree *btree, const void *key)
102 {
103         btree_iterator iter;
104         bool success = false;
105         bool multi = btree->multi;
106         
107         do {
108                 if (btree_find_first(btree, key, iter)) {
109                         btree_remove_at(iter);
110                         success = true;
111                 }
112         } while (multi);
113         
114         return success;
115 }
116
117 void *btree_lookup(struct btree *btree, const void *key)
118 {
119         btree_iterator iter;
120         
121         if (btree_find_first(btree, key, iter))
122                 return iter->item;
123         
124         return NULL;
125 }
126
127 int btree_begin_end_lr(const struct btree *btree, btree_iterator iter, int lr)
128 {
129         struct btree_node *node;
130         
131         iter->btree = (struct btree *)btree;
132         begin_end_lr(iter, btree->root, lr);
133         
134         /* Set iter->item if any items exist. */
135         node = iter->node;
136         if (node->count) {
137                 iter->item = (void*)node->item[iter->k - lr];
138                 return 1;
139         }
140         
141         return 0;
142 }
143
144 int btree_deref(btree_iterator iter)
145 {
146         if (iter->k >= iter->node->count) {
147                 struct btree_iterator_s tmp = *iter;
148                 do {
149                         if (!ascend(iter)) {
150                                 *iter = tmp;
151                                 return 0;
152                         }
153                 } while (iter->k >= iter->node->count);
154         }
155         
156         iter->item = (void*)iter->node->item[iter->k];
157         return 1;
158 }
159
160 int btree_prev(btree_iterator iter)
161 {
162         if (iter->node->depth) {
163                 branch_end(iter);
164         } else if (iter->k == 0) {
165                 struct btree_iterator_s tmp = *iter;
166                 do {
167                         if (!ascend(iter)) {
168                                 *iter = tmp;
169                                 return 0;
170                         }
171                 } while (iter->k == 0);
172         }
173         
174         iter->item = (void*)iter->node->item[--iter->k];
175         return 1;
176 }
177
178 int btree_next(btree_iterator iter)
179 {
180         int ret = btree_deref(iter);
181         if (ret) {
182                 iter->k++;
183                 if (iter->node->depth)
184                         branch_begin(iter);
185         }
186         return ret;
187 }
188
189 int btree_find_lr(const struct btree *btree, const void *key,
190                                 btree_iterator iter, int lr)
191 {
192         struct btree_node *node = btree->root;
193         unsigned int k;
194         unsigned int depth;
195         int found = 0;
196         
197         iter->btree = (struct btree *)btree;
198         iter->item = NULL;
199         
200         depth = node->depth;
201         for (;;) {
202                 int f = 0;
203                 k = btree->search(key, node->item, node->count, lr, &f);
204                 
205                 if (f) {
206                         iter->item = (void*)node->item[k - lr];
207                         found = 1;
208                 }
209                 if (!depth--)
210                         break;
211                 
212                 node = node->branch[k];
213         }
214         
215         iter->node = node;
216         iter->k = k;
217         
218         return found;
219 }
220
221 int btree_walk_backward(const struct btree *btree,
222                                 btree_action_t action, void *ctx)
223 {
224         return node_walk_backward(btree->root, action, ctx);
225 }
226
227 int btree_walk_forward(const struct btree *btree,
228                                 btree_action_t action, void *ctx)
229 {
230         return node_walk_forward(btree->root, action, ctx);
231 }
232
233 void btree_insert_at(btree_iterator iter, const void *item)
234 {
235         const void *x = item;
236         struct btree_node *xr = NULL;
237         struct btree_node *p;
238         struct btree *btree = iter->btree;
239         
240         /* btree_insert_at always sets iter->item to item. */
241         iter->item = (void*)item;
242         
243         /*
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
246          * position.
247          */
248         if (iter->node->depth)
249                 branch_end(iter);
250         
251         /*
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.
255          */
256         if (iter->node->count < MAX) {
257                 node_insert(x, xr, iter->node, iter->k);
258                 goto finished;
259         } else {
260                 for (;;) {
261                         node_split(&x, &xr, iter->node, iter->k);
262                         
263                         if (!ascend(iter))
264                                 break;
265                         
266                         if (iter->node->count < MAX) {
267                                 node_insert(x, xr, iter->node, iter->k);
268                                 goto finished;
269                         }
270                 }
271                 
272                 /*
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.
276                  */
277                 assert(iter->node == btree->root);
278                 p = node_alloc(1);
279                 p->parent = NULL;
280                 p->count = 1;
281                 p->depth = btree->root->depth + 1;
282                 p->item[0] = x;
283                 p->branch[0] = btree->root;
284                         btree->root->parent = p;
285                         btree->root->k = 0;
286                 p->branch[1] = xr;
287                         xr->parent = p;
288                         xr->k = 1;
289                 btree->root = p;
290         }
291         
292 finished:
293         btree->count++;
294         iter->node = NULL;
295 }
296
297 int btree_remove_at(btree_iterator iter)
298 {
299         struct btree *btree = iter->btree;
300         struct btree_node *root;
301         
302         if (!btree_deref(iter))
303                 return 0;
304         
305         if (!iter->node->depth) {
306                 node_remove_leaf_item(iter->node, iter->k);
307                 if (iter->node->count >= MIN || !iter->node->parent)
308                         goto finished;
309         } else {
310                 /*
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.
314                  */
315                 
316                 /* Save pointer to condemned item. */
317                 const void **x = &iter->node->item[iter->k];
318                 
319                 /* Descend to successor. */
320                 iter->k++;
321                 branch_begin(iter);
322                 
323                 /* Replace condemned item with successor. */
324                 *x = iter->node->item[0];
325                 
326                 /* Remove successor. */
327                 node_remove_leaf_item(iter->node, 0);
328         }
329         
330         /*
331          * Restore nodes that fall under their minimum count.  This may
332          * propagate all the way up to the root.
333          */
334         for (;;) {
335                 if (iter->node->count >= MIN)
336                         goto finished;
337                 if (!ascend(iter))
338                         break;
339                 node_restore(iter->node, iter->k);
340         }
341         
342         /*
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.
345          */
346         root = iter->node;
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;
352                 free(root);
353         }
354         
355 finished:
356         btree->count--;
357         iter->node = NULL;
358         return 1;
359 }
360
361 /*
362  * ascends iterator a until it matches iterator b's depth.
363  *
364  * Returns -1 if they end up on the same k (meaning a < b).
365  * Returns 0 otherwise.
366  */
367 static int elevate(btree_iterator a, btree_iterator b)
368 {
369         while (a->node->depth < b->node->depth)
370                 ascend(a);
371         
372         if (a->k == b->k)
373                 return -1;
374         return 0;
375 }
376
377 int btree_cmp_iters(const btree_iterator iter_a, const btree_iterator iter_b)
378 {
379         btree_iterator a = {*iter_a}, b = {*iter_b};
380         int ad, bd;
381         
382         ad = btree_deref(a);
383         bd = btree_deref(b);
384         
385         /* Check cases where one or both iterators are at the end. */
386         if (!ad)
387                 return bd ? 1 : 0;
388         if (!bd)
389                 return ad ? -1 : 0;
390         
391         /* Bring iterators to the same depth. */
392         if (a->node->depth < b->node->depth) {
393                 if (elevate(a, b))
394                         return -1;
395         } else if (a->node->depth > b->node->depth) {
396                 if (elevate(b, a))
397                         return 1;
398         }
399         
400         /* Bring iterators to the same node. */
401         while (a->node != b->node) {
402                 ascend(a);
403                 ascend(b);
404         }
405         
406         /* Now we can compare by k directly. */
407         if (a->k < b->k)
408                 return -1;
409         if (a->k > b->k)
410                 return 1;
411         
412         return 0;
413 }
414
415 /********************* Built-in ordering functions *******************/
416
417 btree_search_implement
418 (
419         btree_strcmp,
420         char*,
421         int c = strcmp(a, b),
422         c == 0,
423         c < 0
424 )
425
426
427 /************************* Private functions *************************/
428
429 static struct btree_node *node_alloc(int internal)
430 {
431         struct btree_node *node;
432         size_t isize = internal
433                 ? sizeof(struct btree_node*) * (BTREE_ITEM_MAX+1)
434                 : 0;
435         node = malloc(sizeof(struct btree_node) + isize);
436         return node;
437 }
438
439 static void node_delete(struct btree_node *node, struct btree *btree)
440 {
441         unsigned int i, count = node->count;
442         
443         if (!node->depth) {
444                 if (btree->destroy) {
445                         for (i=0; i<count; i++)
446                                 btree->destroy((void*)node->item[i], btree->destroy_ctx);
447                 }
448         } else {
449                 for (i=0; i<count; i++) {
450                         node_delete(node->branch[i], btree);
451                         if (btree->destroy)
452                                 btree->destroy((void*)node->item[i], btree->destroy_ctx);
453                 }
454                 node_delete(node->branch[count], btree);
455         }
456         
457         free(node);
458 }
459
460 /* Set iter to beginning of branch pointed to by iter. */
461 static void branch_begin(btree_iterator iter)
462 {
463         struct btree_node *node = iter->node->branch[iter->k];
464         unsigned int depth = node->depth;
465         while (depth--)
466                 node = node->branch[0];
467         iter->node = node;
468         iter->k = 0;
469 }
470
471 /* Set iter to end of branch pointed to by iter. */
472 static void branch_end(btree_iterator iter)
473 {
474         struct btree_node *node = iter->node->branch[iter->k];
475         unsigned int depth = node->depth;
476         while (depth--)
477                 node = node->branch[node->count];
478         iter->node = node;
479         iter->k = node->count;
480 }
481
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)
484 {
485         iter->node = node;
486         iter->k = lr ? node->count : 0;
487         if (node->depth)
488                 (lr ? branch_end : branch_begin)(iter);
489 }
490
491 /*
492  * Inserts item x and right branch xr into node p at position k.
493  *
494  * Assumes p exists and has enough room.
495  * Ignores xr if p is a leaf.
496  */
497 static void node_insert(const void *x, struct btree_node *xr,
498                                 struct btree_node *p, unsigned int k)
499 {
500         unsigned int i;
501         
502         for (i = p->count; i-- > k;)
503                 p->item[i+1] = p->item[i];
504         p->item[k] = x;
505         
506         if (p->depth) {
507                 k++;
508                 for (i = p->count+1; i-- > k;) {
509                         p->branch[i+1] = p->branch[i];
510                         p->branch[i+1]->k = i+1;
511                 }
512                 p->branch[k] = xr;
513                 xr->parent = p;
514                 xr->k = k;
515         }
516         
517         p->count++;
518 }
519
520 /*
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.
523  *
524  * Assumes p->count == MAX.
525  * Ignores original *xr if p is a leaf, but always sets it.
526  */
527 static void node_split(const void **x, struct btree_node **xr,
528                                 struct btree_node *p, unsigned int k)
529 {
530         unsigned int i, split;
531         struct btree_node *l = p, *r;
532         
533         /*
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.
538          */
539         if (k <= MIN)
540                 split = MIN;
541         else
542                 split = MIN + 1;
543         
544         /*
545          * If l->depth is 0, allocate a leaf node.
546          * Otherwise, allocate an internal node.
547          */
548         r = node_alloc(l->depth);
549         
550         /* l and r will be siblings, so they will have the same parent and depth. */
551         r->parent = l->parent;
552         r->depth = l->depth;
553         
554         /*
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
558          * take its place.
559          */
560         for (i = split; i < MAX; i++)
561                 r->item[i-split] = l->item[i];
562         if (r->depth) {
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;
567                 }
568         }
569         
570         /* Update counts. */
571         l->count = split;
572         r->count = MAX - split;
573         
574         /*
575          * The nodes are now split, but the key isn't inserted yet.
576          *
577          * Insert key into left or right half,
578          * depending on which side it fell on.
579          */
580         if (k <= MIN)
581                 node_insert(*x, *xr, l, k);
582         else
583                 node_insert(*x, *xr, r, k - split);
584         
585         /*
586          * Give l's rightmost branch to r because l's rightmost item
587          * is going up to become the median.
588          */
589         if (r->depth) {
590                 r->branch[0] = l->branch[l->count];
591                 r->branch[0]->parent = r;
592                 r->branch[0]->k = 0;
593         }
594         
595         /*
596          * Take up l's rightmost item to make it the median.
597          * That item's right branch is now r.
598          */
599         *x = l->item[--l->count];
600         *xr = r;
601 }
602
603 /*
604  * Removes item k from node p, shifting successor items back and
605  * decrementing the count.
606  *
607  * Assumes node p has the item k and is a leaf.
608  */
609 static void node_remove_leaf_item(struct btree_node *node, unsigned int k)
610 {
611         unsigned int i;
612         for (i = k+1; i < node->count; i++)
613                 node->item[i-1] = node->item[i];
614         node->count--;
615 }
616
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);
620
621 /*
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.
625  */
626 void node_restore(struct btree_node *node, unsigned int k)
627 {
628         if (k == 0) {
629                 if (node->branch[1]->count > MIN)
630                         move_left(node, 0);
631                 else
632                         combine(node, 0);
633         } else if (k == node->count) {
634                 if (node->branch[k-1]->count > MIN)
635                         move_right(node, k-1);
636                 else
637                         combine(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) {
641                 move_left(node, k);
642         } else {
643                 combine(node, k-1);
644         }
645 }
646
647 static void move_left(struct btree_node *node, unsigned int k)
648 {
649         struct btree_node *l = node->branch[k], *r = node->branch[k+1], *mv;
650         unsigned int i;
651         
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];
656         
657         if (r->depth) {
658                 mv = r->branch[0];
659                 l->branch[l->count+1] = mv;
660                 mv->parent = l;
661                 mv->k = l->count+1;
662                 
663                 for (i = 1; i <= r->count; i++) {
664                         r->branch[i-1] = r->branch[i];
665                         r->branch[i-1]->k = i-1;
666                 }
667         }
668         
669         l->count++;
670         r->count--;
671 }
672
673 static void move_right(struct btree_node *node, unsigned int k)
674 {
675         struct btree_node *l = node->branch[k], *r = node->branch[k+1];
676         unsigned int i;
677         
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];
682         
683         if (r->depth) {
684                 for (i = r->count+1; i--;) {
685                         r->branch[i+1] = r->branch[i];
686                         r->branch[i+1]->k = i+1;
687                 }
688                 r->branch[0] = l->branch[l->count];
689                 r->branch[0]->parent = r;
690                 r->branch[0]->k = 0;
691         }
692         
693         l->count--;
694         r->count++;
695 }
696
697 /* Combine node->branch[k] and node->branch[k+1]. */
698 static void combine(struct btree_node *node, unsigned int k)
699 {
700         struct btree_node *l = node->branch[k], *r = node->branch[k+1], *mv;
701         const void **o = &l->item[l->count];
702         unsigned int i;
703         
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++)
707                 *o++ = r->item[i];
708         
709         //if applicable, append right node's branches to left node
710         if (r->depth) {
711                 for (i=0; i<=r->count; i++) {
712                         mv = r->branch[i];
713                         l->branch[l->count + i + 1] = mv;
714                         mv->parent = l;
715                         mv->k = l->count + i + 1;
716                 }
717         }
718         
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;
724         }
725         
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;
728         node->count--;
729         free(r);
730 }
731
732 static int node_walk_backward(const struct btree_node *node,
733                                 btree_action_t action, void *ctx)
734 {
735         unsigned int i, count = node->count;
736         
737         if (!node->depth) {
738                 for (i=count; i--;)
739                         if (!action((void*)node->item[i], ctx))
740                                 return 0;
741         } else {
742                 if (!node_walk_backward(node->branch[count], action, ctx))
743                         return 0;
744                 for (i=count; i--;) {
745                         if (!action((void*)node->item[i], ctx))
746                                 return 0;
747                         if (!node_walk_backward(node->branch[i], action, ctx))
748                                 return 0;
749                 }
750         }
751         
752         return 1;
753 }
754
755 static int node_walk_forward(const struct btree_node *node,
756                                 btree_action_t action, void *ctx)
757 {
758         unsigned int i, count = node->count;
759         
760         if (!node->depth) {
761                 for (i=0; i<count; i++)
762                         if (!action((void*)node->item[i], ctx))
763                                 return 0;
764         } else {
765                 for (i=0; i<count; i++) {
766                         if (!node_walk_forward(node->branch[i], action, ctx))
767                                 return 0;
768                         if (!action((void*)node->item[i], ctx))
769                                 return 0;
770                 }
771                 if (!node_walk_forward(node->branch[count], action, ctx))
772                         return 0;
773         }
774         
775         return 1;
776 }