Cleanup
[carla.git] / source / modules / lilv / sord-0.16.0 / src / zix / btree.c
blob4557ad49fddb55894d51da0df6356a54cd6dcc6d
1 /*
2 Copyright 2011-2014 David Robillard <http://drobilla.net>
4 Permission to use, copy, modify, and/or distribute this software for any
5 purpose with or without fee is hereby granted, provided that the above
6 copyright notice and this permission notice appear in all copies.
8 THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 #include <assert.h>
18 #include <stdint.h>
19 #include <stdio.h>
20 #include <stdlib.h>
21 #include <string.h>
23 #include "zix/btree.h"
25 // #define ZIX_BTREE_DEBUG 1
27 #define ZIX_BTREE_PAGE_SIZE 4096
28 #define ZIX_BTREE_NODE_SPACE (ZIX_BTREE_PAGE_SIZE - 2 * sizeof(uint16_t))
29 #define ZIX_BTREE_LEAF_VALS ((ZIX_BTREE_NODE_SPACE / sizeof(void*)) - 1)
30 #define ZIX_BTREE_INODE_VALS (ZIX_BTREE_LEAF_VALS / 2)
32 struct ZixBTreeImpl {
33 ZixBTreeNode* root;
34 ZixDestroyFunc destroy;
35 ZixComparator cmp;
36 void* cmp_data;
37 size_t size;
38 unsigned height; ///< Number of levels, i.e. root only has height 1
41 struct ZixBTreeNodeImpl {
42 uint16_t is_leaf;
43 uint16_t n_vals;
44 // On 64-bit we rely on some padding here to get page-sized nodes
45 void* vals[ZIX_BTREE_INODE_VALS]; // ZIX_BTREE_LEAF_VALS for leaves
46 ZixBTreeNode* children[ZIX_BTREE_INODE_VALS + 1]; // Nonexistent for leaves
49 typedef struct {
50 ZixBTreeNode* node;
51 unsigned index;
52 } ZixBTreeIterFrame;
54 struct ZixBTreeIterImpl {
55 unsigned level; ///< Current level in stack
56 ZixBTreeIterFrame stack[]; ///< Position stack
59 #ifdef ZIX_BTREE_DEBUG
61 ZIX_PRIVATE void
62 print_node(const ZixBTreeNode* n, const char* prefix)
64 printf("%s[", prefix);
65 for (uint16_t v = 0; v < n->n_vals; ++v) {
66 printf(" %lu", (uintptr_t)n->vals[v]);
68 printf(" ]\n");
71 ZIX_PRIVATE void
72 print_tree(const ZixBTreeNode* parent, const ZixBTreeNode* node, int level)
74 if (node) {
75 if (!parent) {
76 printf("TREE {\n");
78 for (int i = 0; i < level + 1; ++i) {
79 printf(" ");
81 print_node(node, "");
82 if (!node->is_leaf) {
83 for (uint16_t i = 0; i < node->n_vals + 1; ++i) {
84 print_tree(node, node->children[i], level + 1);
87 if (!parent) {
88 printf("}\n");
93 #endif // ZIX_BTREE_DEBUG
95 ZIX_PRIVATE ZixBTreeNode*
96 zix_btree_node_new(const bool leaf)
98 assert(sizeof(ZixBTreeNode) == ZIX_BTREE_PAGE_SIZE);
99 ZixBTreeNode* node = (ZixBTreeNode*)malloc(sizeof(ZixBTreeNode));
100 if (node) {
101 node->is_leaf = leaf;
102 node->n_vals = 0;
104 return node;
107 ZIX_API ZixBTree*
108 zix_btree_new(const ZixComparator cmp,
109 void* const cmp_data,
110 const ZixDestroyFunc destroy)
112 ZixBTree* t = (ZixBTree*)malloc(sizeof(ZixBTree));
113 if (t) {
114 t->root = zix_btree_node_new(true);
115 t->destroy = destroy;
116 t->cmp = cmp;
117 t->cmp_data = cmp_data;
118 t->size = 0;
119 t->height = 1;
120 if (!t->root) {
121 free(t);
122 return NULL;
125 return t;
128 ZIX_PRIVATE void
129 zix_btree_free_rec(ZixBTree* const t, ZixBTreeNode* const n)
131 if (n) {
132 if (t->destroy) {
133 for (uint16_t i = 0; i < n->n_vals; ++i) {
134 t->destroy(n->vals[i]);
137 if (!n->is_leaf) {
138 for (uint16_t i = 0; i < n->n_vals + 1; ++i) {
139 zix_btree_free_rec(t, n->children[i]);
142 free(n);
146 ZIX_API void
147 zix_btree_free(ZixBTree* const t)
149 if (t) {
150 zix_btree_free_rec(t, t->root);
151 free(t);
155 ZIX_API size_t
156 zix_btree_size(const ZixBTree* const t)
158 return t->size;
161 ZIX_PRIVATE uint16_t
162 zix_btree_max_vals(const ZixBTreeNode* const node)
164 return node->is_leaf ? ZIX_BTREE_LEAF_VALS : ZIX_BTREE_INODE_VALS;
167 ZIX_PRIVATE uint16_t
168 zix_btree_min_vals(const ZixBTreeNode* const node)
170 return ((zix_btree_max_vals(node) + 1) / 2) - 1;
173 /** Shift pointers in `array` of length `n` right starting at `i`. */
174 ZIX_PRIVATE void
175 zix_btree_ainsert(void** const array,
176 const uint16_t n,
177 const uint16_t i,
178 void* const e)
180 memmove(array + i + 1, array + i, (n - i) * sizeof(e));
181 array[i] = e;
184 /** Erase element `i` in `array` of length `n` and return erased element. */
185 ZIX_PRIVATE void*
186 zix_btree_aerase(void** const array, const uint16_t n, const uint16_t i)
188 void* const ret = array[i];
189 memmove(array + i, array + i + 1, (n - i) * sizeof(ret));
190 return ret;
193 /** Split lhs, the i'th child of `n`, into two nodes. */
194 ZIX_PRIVATE ZixBTreeNode*
195 zix_btree_split_child(ZixBTreeNode* const n,
196 const uint16_t i,
197 ZixBTreeNode* const lhs)
199 assert(lhs->n_vals == zix_btree_max_vals(lhs));
200 assert(n->n_vals < ZIX_BTREE_INODE_VALS);
201 assert(i < n->n_vals + 1);
202 assert(n->children[i] == lhs);
204 const uint16_t max_n_vals = zix_btree_max_vals(lhs);
205 ZixBTreeNode* rhs = zix_btree_node_new(lhs->is_leaf);
206 if (!rhs) {
207 return NULL;
210 // LHS and RHS get roughly half, less the middle value which moves up
211 lhs->n_vals = max_n_vals / 2;
212 rhs->n_vals = max_n_vals - lhs->n_vals - 1;
214 // Copy large half of values from LHS to new RHS node
215 memcpy(rhs->vals,
216 lhs->vals + lhs->n_vals + 1,
217 rhs->n_vals * sizeof(void*));
219 // Copy large half of children from LHS to new RHS node
220 if (!lhs->is_leaf) {
221 memcpy(rhs->children,
222 lhs->children + lhs->n_vals + 1,
223 (rhs->n_vals + 1) * sizeof(ZixBTreeNode*));
226 // Move middle value up to parent
227 zix_btree_ainsert(n->vals, n->n_vals, i, lhs->vals[lhs->n_vals]);
229 // Insert new RHS node in parent at position i
230 zix_btree_ainsert((void**)n->children, ++n->n_vals, i + 1, rhs);
232 return rhs;
235 /** Find the first value in `n` that is not less than `e` (lower bound). */
236 ZIX_PRIVATE uint16_t
237 zix_btree_node_find(const ZixBTree* const t,
238 const ZixBTreeNode* const n,
239 const void* const e,
240 bool* const equal)
242 uint16_t first = 0;
243 uint16_t len = n->n_vals;
244 while (len > 0) {
245 const uint16_t half = len >> 1;
246 const uint16_t i = first + half;
247 const int cmp = t->cmp(n->vals[i], e, t->cmp_data);
248 if (cmp == 0) {
249 *equal = true;
250 len = half; // Keep searching for wildcard matches
251 } else if (cmp < 0) {
252 const uint16_t chop = half + 1;
253 first += chop;
254 len -= chop;
255 } else {
256 len = half;
259 assert(!*equal || t->cmp(n->vals[first], e, t->cmp_data) == 0);
260 return first;
263 ZIX_API ZixStatus
264 zix_btree_insert(ZixBTree* const t, void* const e)
266 ZixBTreeNode* parent = NULL; // Parent of n
267 ZixBTreeNode* n = t->root; // Current node
268 uint16_t i = 0; // Index of n in parent
269 while (n) {
270 if (n->n_vals == zix_btree_max_vals(n)) {
271 // Node is full, split to ensure there is space for a leaf split
272 if (!parent) {
273 // Root is full, grow tree upwards
274 if (!(parent = zix_btree_node_new(false))) {
275 return ZIX_STATUS_NO_MEM;
277 t->root = parent;
278 parent->children[0] = n;
279 ++t->height;
282 ZixBTreeNode* const rhs = zix_btree_split_child(parent, i, n);
283 if (!rhs) {
284 return ZIX_STATUS_NO_MEM;
287 const int cmp = t->cmp(parent->vals[i], e, t->cmp_data);
288 if (cmp == 0) {
289 return ZIX_STATUS_EXISTS;
290 } else if (cmp < 0) {
291 // Move to new RHS
292 n = rhs;
293 ++i;
297 assert(!parent || parent->children[i] == n);
299 bool equal = false;
300 i = zix_btree_node_find(t, n, e, &equal);
301 if (equal) {
302 return ZIX_STATUS_EXISTS;
303 } else if (!n->is_leaf) {
304 // Descend to child node left of value
305 parent = n;
306 n = n->children[i];
307 } else {
308 // Insert into internal node
309 zix_btree_ainsert(n->vals, n->n_vals++, i, e);
310 break;
314 ++t->size;
316 return ZIX_STATUS_SUCCESS;
319 ZIX_PRIVATE ZixBTreeIter*
320 zix_btree_iter_new(const ZixBTree* const t)
322 const size_t s = t->height * sizeof(ZixBTreeIterFrame);
323 ZixBTreeIter* const i = (ZixBTreeIter*)malloc(sizeof(ZixBTreeIter) + s);
324 if (i) {
325 i->level = 0;
327 return i;
330 ZIX_PRIVATE void
331 zix_btree_iter_set_frame(ZixBTreeIter* const ti,
332 ZixBTreeNode* const n,
333 const uint16_t i)
335 if (ti) {
336 ti->stack[ti->level].node = n;
337 ti->stack[ti->level].index = i;
341 ZIX_PRIVATE bool
342 zix_btree_node_is_minimal(ZixBTreeNode* const n)
344 assert(n->n_vals >= zix_btree_min_vals(n));
345 return n->n_vals == zix_btree_min_vals(n);
348 /** Enlarge left child by stealing a value from its right sibling. */
349 ZIX_PRIVATE ZixBTreeNode*
350 zix_btree_rotate_left(ZixBTreeNode* const parent, const uint16_t i)
352 ZixBTreeNode* const lhs = parent->children[i];
353 ZixBTreeNode* const rhs = parent->children[i + 1];
355 // Move parent value to end of LHS
356 lhs->vals[lhs->n_vals++] = parent->vals[i];
358 // Move first child pointer from RHS to end of LHS
359 if (!lhs->is_leaf) {
360 lhs->children[lhs->n_vals] = (ZixBTreeNode*)zix_btree_aerase(
361 (void**)rhs->children, rhs->n_vals, 0);
364 // Move first value in RHS to parent
365 parent->vals[i] = zix_btree_aerase(rhs->vals, --rhs->n_vals, 0);
367 return lhs;
370 /** Enlarge right child by stealing a value from its left sibling. */
371 ZIX_PRIVATE ZixBTreeNode*
372 zix_btree_rotate_right(ZixBTreeNode* const parent, const uint16_t i)
374 ZixBTreeNode* const lhs = parent->children[i - 1];
375 ZixBTreeNode* const rhs = parent->children[i];
377 // Prepend parent value to RHS
378 zix_btree_ainsert(rhs->vals, rhs->n_vals++, 0, parent->vals[i - 1]);
380 // Move last child pointer from LHS and prepend to RHS
381 if (!lhs->is_leaf) {
382 zix_btree_ainsert((void**)rhs->children,
383 rhs->n_vals,
385 lhs->children[lhs->n_vals]);
388 // Move last value from LHS to parent
389 parent->vals[i - 1] = lhs->vals[--lhs->n_vals];
391 return rhs;
394 /** Move n[i] down, merge the left and right child, return the merged node. */
395 ZIX_PRIVATE ZixBTreeNode*
396 zix_btree_merge(ZixBTree* const t, ZixBTreeNode* const n, const uint16_t i)
398 ZixBTreeNode* const lhs = n->children[i];
399 ZixBTreeNode* const rhs = n->children[i + 1];
401 assert(zix_btree_node_is_minimal(n->children[i]));
402 assert(lhs->n_vals + rhs->n_vals < zix_btree_max_vals(lhs));
404 // Move parent value to end of LHS
405 lhs->vals[lhs->n_vals++] = zix_btree_aerase(n->vals, n->n_vals, i);
407 // Erase corresponding child pointer (to RHS) in parent
408 zix_btree_aerase((void**)n->children, n->n_vals, i + 1);
410 // Add everything from RHS to end of LHS
411 memcpy(lhs->vals + lhs->n_vals, rhs->vals, rhs->n_vals * sizeof(void*));
412 if (!lhs->is_leaf) {
413 memcpy(lhs->children + lhs->n_vals,
414 rhs->children,
415 (rhs->n_vals + 1) * sizeof(void*));
417 lhs->n_vals += rhs->n_vals;
419 if (--n->n_vals == 0) {
420 // Root is now empty, replace it with its only child
421 assert(n == t->root);
422 t->root = lhs;
423 free(n);
426 free(rhs);
427 return lhs;
430 /** Remove and return the min value from the subtree rooted at `n`. */
431 ZIX_PRIVATE void*
432 zix_btree_remove_min(ZixBTree* const t, ZixBTreeNode* n)
434 while (!n->is_leaf) {
435 if (zix_btree_node_is_minimal(n->children[0])) {
436 // Leftmost child is minimal, must expand
437 if (!zix_btree_node_is_minimal(n->children[1])) {
438 // Child's right sibling has at least one key to steal
439 n = zix_btree_rotate_left(n, 0);
440 } else {
441 // Both child and right sibling are minimal, merge
442 n = zix_btree_merge(t, n, 0);
444 } else {
445 n = n->children[0];
449 return zix_btree_aerase(n->vals, --n->n_vals, 0);
452 /** Remove and return the max value from the subtree rooted at `n`. */
453 ZIX_PRIVATE void*
454 zix_btree_remove_max(ZixBTree* const t, ZixBTreeNode* n)
456 while (!n->is_leaf) {
457 if (zix_btree_node_is_minimal(n->children[n->n_vals])) {
458 // Leftmost child is minimal, must expand
459 if (!zix_btree_node_is_minimal(n->children[n->n_vals - 1])) {
460 // Child's left sibling has at least one key to steal
461 n = zix_btree_rotate_right(n, n->n_vals);
462 } else {
463 // Both child and left sibling are minimal, merge
464 n = zix_btree_merge(t, n, n->n_vals - 1);
466 } else {
467 n = n->children[n->n_vals];
471 return n->vals[--n->n_vals];
474 ZIX_API ZixStatus
475 zix_btree_remove(ZixBTree* const t,
476 const void* const e,
477 void** const out,
478 ZixBTreeIter** const next)
480 ZixBTreeNode* n = t->root;
481 ZixBTreeIter* ti = NULL;
482 const bool user_iter = next && *next;
483 if (next) {
484 if (!*next && !(*next = zix_btree_iter_new(t))) {
485 return ZIX_STATUS_NO_MEM;
487 ti = *next;
488 ti->level = 0;
491 while (true) {
492 /* To remove in a single walk down, the tree is adjusted along the way
493 so that the current node always has at least one more value than the
494 minimum required in general. Thus, there is always room to remove
495 without adjusting on the way back up. */
496 assert(n == t->root || !zix_btree_node_is_minimal(n));
498 bool equal = false;
499 const uint16_t i = zix_btree_node_find(t, n, e, &equal);
500 zix_btree_iter_set_frame(ti, n, i);
501 if (n->is_leaf) {
502 if (equal) {
503 // Found in leaf node
504 *out = zix_btree_aerase(n->vals, --n->n_vals, i);
505 if (ti && i == n->n_vals) {
506 if (i == 0) {
507 ti->stack[ti->level = 0].node = NULL;
508 } else {
509 --ti->stack[ti->level].index;
510 zix_btree_iter_increment(ti);
513 --t->size;
514 return ZIX_STATUS_SUCCESS;
515 } else {
516 // Not found in leaf node, or tree
517 if (ti && !user_iter) {
518 zix_btree_iter_free(ti);
519 *next = NULL;
521 return ZIX_STATUS_NOT_FOUND;
523 } else if (equal) {
524 // Found in internal node
525 if (!zix_btree_node_is_minimal(n->children[i])) {
526 // Left child can remove without merge
527 *out = n->vals[i];
528 n->vals[i] = zix_btree_remove_max(t, n->children[i]);
529 --t->size;
530 return ZIX_STATUS_SUCCESS;
531 } else if (!zix_btree_node_is_minimal(n->children[i + 1])) {
532 // Right child can remove without merge
533 *out = n->vals[i];
534 n->vals[i] = zix_btree_remove_min(t, n->children[i + 1]);
535 --t->size;
536 return ZIX_STATUS_SUCCESS;
537 } else {
538 // Both preceding and succeeding child are minimal
539 n = zix_btree_merge(t, n, i);
541 } else {
542 // Not found in internal node, key is in/under children[i]
543 if (zix_btree_node_is_minimal(n->children[i])) {
544 if (i > 0 && !zix_btree_node_is_minimal(n->children[i - 1])) {
545 // Steal a key from child's left sibling
546 n = zix_btree_rotate_right(n, i);
547 } else if (i < n->n_vals &&
548 !zix_btree_node_is_minimal(n->children[i + 1])) {
549 // Steal a key from child's right sibling
550 n = zix_btree_rotate_left(n, i);
551 } else {
552 // Both child's siblings are minimal, merge them
553 if (i < n->n_vals) {
554 n = zix_btree_merge(t, n, i);
555 } else {
556 n = zix_btree_merge(t, n, i - 1);
557 if (ti) {
558 --ti->stack[ti->level].index;
562 } else {
563 n = n->children[i];
566 if (ti) {
567 ++ti->level;
571 assert(false); // Not reached
572 return ZIX_STATUS_ERROR;
575 ZIX_API ZixStatus
576 zix_btree_find(const ZixBTree* const t,
577 const void* const e,
578 ZixBTreeIter** const ti)
580 ZixBTreeNode* n = t->root;
581 if (!(*ti = zix_btree_iter_new(t))) {
582 return ZIX_STATUS_NO_MEM;
585 while (n) {
586 bool equal = false;
587 const uint16_t i = zix_btree_node_find(t, n, e, &equal);
589 zix_btree_iter_set_frame(*ti, n, i);
591 if (equal) {
592 return ZIX_STATUS_SUCCESS;
593 } else if (n->is_leaf) {
594 break;
595 } else {
596 ++(*ti)->level;
597 n = n->children[i];
601 zix_btree_iter_free(*ti);
602 *ti = NULL;
603 return ZIX_STATUS_NOT_FOUND;
606 ZIX_API ZixStatus
607 zix_btree_lower_bound(const ZixBTree* const t,
608 const void* const e,
609 ZixBTreeIter** const ti)
611 if (!t) {
612 *ti = NULL;
613 return ZIX_STATUS_BAD_ARG;
616 ZixBTreeNode* n = t->root;
617 bool found = false;
618 unsigned found_level = 0;
619 if (!(*ti = zix_btree_iter_new(t))) {
620 return ZIX_STATUS_NO_MEM;
623 while (n) {
624 bool equal = false;
625 const uint16_t i = zix_btree_node_find(t, n, e, &equal);
627 zix_btree_iter_set_frame(*ti, n, i);
629 if (equal) {
630 found_level = (*ti)->level;
631 found = true;
634 if (n->is_leaf) {
635 break;
636 } else {
637 ++(*ti)->level;
638 n = n->children[i];
639 assert(n);
643 const ZixBTreeIterFrame* const frame = &(*ti)->stack[(*ti)->level];
644 if (frame->index == frame->node->n_vals) {
645 if (found) {
646 // Found on a previous level but went too far
647 (*ti)->level = found_level;
648 } else {
649 // Reached end (key is greater than everything in tree)
650 (*ti)->stack[0].node = NULL;
654 return ZIX_STATUS_SUCCESS;
657 ZIX_API void*
658 zix_btree_get(const ZixBTreeIter* const ti)
660 const ZixBTreeIterFrame* const frame = &ti->stack[ti->level];
661 assert(frame->index < frame->node->n_vals);
662 return frame->node->vals[frame->index];
665 ZIX_API ZixBTreeIter*
666 zix_btree_begin(const ZixBTree* const t)
668 ZixBTreeIter* const i = zix_btree_iter_new(t);
669 if (!i) {
670 return NULL;
671 } else if (t->size == 0) {
672 i->stack[0].node = NULL;
673 } else {
674 ZixBTreeNode* n = t->root;
675 i->stack[0].node = n;
676 i->stack[0].index = 0;
677 while (!n->is_leaf) {
678 n = n->children[0];
679 ++i->level;
680 i->stack[i->level].node = n;
681 i->stack[i->level].index = 0;
684 return i;
687 ZIX_API bool
688 zix_btree_iter_is_end(const ZixBTreeIter* const i)
690 return !i || i->stack[0].node == NULL;
693 ZIX_API void
694 zix_btree_iter_increment(ZixBTreeIter* const i)
696 ZixBTreeIterFrame* f = &i->stack[i->level];
697 if (f->node->is_leaf) {
698 // Leaf, move right
699 assert(f->index < f->node->n_vals);
700 if (++f->index == f->node->n_vals) {
701 // Reached end of leaf, move up
702 f = &i->stack[i->level];
703 while (i->level > 0 && f->index == f->node->n_vals) {
704 f = &i->stack[--i->level];
705 assert(f->index <= f->node->n_vals);
708 if (f->index == f->node->n_vals) {
709 // Reached end of tree
710 assert(i->level == 0);
711 f->node = NULL;
712 f->index = 0;
715 } else {
716 // Internal node, move down to next child
717 assert(f->index < f->node->n_vals);
718 ZixBTreeNode* child = f->node->children[++f->index];
720 f = &i->stack[++i->level];
721 f->node = child;
722 f->index = 0;
724 // Move down and left until we hit a leaf
725 while (!f->node->is_leaf) {
726 child = f->node->children[0];
727 f = &i->stack[++i->level];
728 f->node = child;
729 f->index = 0;
734 ZIX_API void
735 zix_btree_iter_free(ZixBTreeIter* const i)
737 free(i);