1 /*
2  # This file is part of the Astrometry.net suite.
3  # Licensed under a 3-clause BSD style license - see LICENSE
4 
5  The AVL tree portion of this code was adapted from GNU libavl,
6  licensed under the GPL v2 or later.
7  */
8 
9 #include <stdio.h>
10 #include <errno.h>
11 #include <string.h>
12 #include <assert.h>
13 #include <stdlib.h>
14 
15 #include "bt.h"
16 
17 /*
18  The AVL tree portion of this code was adapted from GNU libavl.
19  */
20 #define AVL_MAX_HEIGHT 32
21 
22 // adapt compare_func to compare_func_2
compare_helper(const void * v1,const void * v2,void * token)23 static int compare_helper(const void* v1, const void* v2, void* token) {
24     compare_func f = token;
25     return f(v1, v2);
26 }
27 
28 // data follows the bt_datablock*.
NODE_DATA(bt_leaf * leaf)29 static Const void* NODE_DATA(bt_leaf* leaf) {
30     return leaf+1;
31 }
NODE_CHARDATA(bt_leaf * leaf)32 static Const char* NODE_CHARDATA(bt_leaf* leaf) {
33     return (char*)(leaf+1);
34 }
35 
isleaf(bt_node * node)36 static Pure anbool isleaf(bt_node* node) {
37     return node->leaf.isleaf;
38 }
39 
node_N(bt_node * node)40 static Pure int node_N(bt_node* node) {
41     if (isleaf(node))
42         return node->leaf.N;
43     return node->branch.N;
44 }
45 
sum_childN(bt_branch * branch)46 static Pure int sum_childN(bt_branch* branch) {
47     return node_N(branch->children[0]) + node_N(branch->children[1]);
48 }
49 
getchild(bt_node * node,int i)50 static Pure bt_node* getchild(bt_node* node, int i) {
51     if (isleaf(node)) return NULL;
52     return node->branch.children[i];
53 }
54 
getleftchild(bt_node * node)55 static Pure bt_node* getleftchild(bt_node* node) {
56     if (isleaf(node)) return NULL;
57     return node->branch.children[0];
58 }
59 
getrightchild(bt_node * node)60 static Pure bt_node* getrightchild(bt_node* node) {
61     if (isleaf(node)) return NULL;
62     return node->branch.children[1];
63 }
64 
firstleaf(bt_node * node)65 static Pure bt_leaf* firstleaf(bt_node* node) {
66     if (isleaf(node)) return &node->leaf;
67     return node->branch.firstleaf;
68 }
69 
height_slow(bt_node * node)70 static int height_slow(bt_node* node) {
71     int hl, hr;
72     if (isleaf(node)) return 1;
73     hl = height_slow(node->branch.children[0]);
74     hr = height_slow(node->branch.children[1]);
75     return 1 + (hl > hr ? hl : hr);
76 }
77 
78 #define CHECK(expr) {                           \
79         int truthval = (expr);                  \
80         assert(truthval);                       \
81         if (!truthval) return -1;               \
82     }
83 
bt_check_node(bt * tree,bt_node * node)84 static int bt_check_node(bt* tree, bt_node* node) {
85     int hl, hr;
86     bt_node* leftmost;
87     if (isleaf(node)) {
88         CHECK(node->leaf.N <= tree->blocksize);
89         return 0;
90     }
91 
92     CHECK(sum_childN(&node->branch) == node->branch.N);
93 
94     leftmost = node;
95     while (!isleaf(leftmost))
96         leftmost = leftmost->branch.children[0];
97     CHECK(&leftmost->leaf == node->branch.firstleaf);
98 
99     hl = height_slow(node->branch.children[0]);
100     hr = height_slow(node->branch.children[1]);
101     CHECK(node->branch.balance == (hr - hl));
102     CHECK((node->branch.balance == 0) ||
103           (node->branch.balance == 1) ||
104           (node->branch.balance == -1));
105 
106     if (bt_check_node(tree, node->branch.children[0]) ||
107         bt_check_node(tree, node->branch.children[1]))
108         return -1;
109     return 0;
110 }
111 
bt_check(bt * tree)112 int bt_check(bt* tree) {
113     if (tree->root) {
114         CHECK(node_N(tree->root) == tree->N);
115         return bt_check_node(tree, tree->root);
116     }
117     return 0;
118 }
119 
bt_new(int datasize,int blocksize)120 bt* bt_new(int datasize, int blocksize) {
121     bt* tree = calloc(1, sizeof(bt));
122     if (!tree) {
123         fprintf(stderr, "Failed to allocate a new bt struct: %s\n", strerror(errno));
124         return NULL;
125     }
126     tree->datasize = datasize;
127     tree->blocksize = blocksize;
128     return tree;
129 }
130 
bt_size(bt * tree)131 int bt_size(bt* tree) {
132     return tree->N;
133 }
134 
bt_height(bt * tree)135 int bt_height(bt* tree) {
136     bt_node* n;
137     int h;
138     n = tree->root;
139     if (!n) return 0;
140     if (isleaf(n)) return 1;
141     for (h=1; !isleaf(n); h++) {
142         if (n->branch.balance > 0)
143             n = getrightchild(n);
144         else
145             n = getleftchild(n);
146     }
147     return h;
148 }
149 
bt_count_leaves_rec(bt_node * node)150 static int bt_count_leaves_rec(bt_node* node) {
151     if (isleaf(node)) return 1;
152     else return
153              bt_count_leaves_rec(node->branch.children[0]) +
154              bt_count_leaves_rec(node->branch.children[1]);
155 }
156 
bt_count_leaves(bt * tree)157 int bt_count_leaves(bt* tree) {
158     return bt_count_leaves_rec(tree->root);
159 }
160 
bt_free_node(bt_node * node)161 static void bt_free_node(bt_node* node) {
162     if (!isleaf(node)) {
163         bt_free_node(getleftchild(node));
164         bt_free_node(getrightchild(node));
165     }
166     free(node);
167 }
168 
bt_free(bt * tree)169 void bt_free(bt* tree) {
170     if (tree->root)
171         bt_free_node(tree->root);
172     free(tree);
173 }
174 
get_element(bt * tree,bt_leaf * leaf,int index)175 static Pure void* get_element(bt* tree, bt_leaf* leaf, int index) {
176     return NODE_CHARDATA(leaf) + index * tree->datasize;
177 }
178 
first_element(bt_node * n)179 static Pure void* first_element(bt_node* n) {
180     if (isleaf(n)) return NODE_DATA(&n->leaf);
181     else return NODE_DATA(n->branch.firstleaf);
182 }
183 
bt_new_branch(bt * tree)184 static Malloc bt_node* bt_new_branch(bt* tree) {
185     bt_node* n = calloc(1, sizeof(bt_node));
186     if (!n) {
187         fprintf(stderr, "Failed to allocate a new bt_node: %s\n", strerror(errno));
188         return NULL;
189     }
190     return n;
191 }
192 
bt_new_leaf(bt * tree)193 static Malloc bt_node* bt_new_leaf(bt* tree) {
194     bt_node* n = malloc(sizeof(bt_leaf) + tree->datasize * tree->blocksize);
195     if (!n) {
196         fprintf(stderr, "Failed to allocate a new bt_node: %s\n", strerror(errno));
197         return NULL;
198     }
199     n->leaf.isleaf = 1;
200     n->leaf.N = 0;
201     return n;
202 }
203 
bt_leaf_insert(bt * tree,bt_leaf * leaf,void * data,anbool unique,compare_func_2 compare,void * token,void * overflow)204 static anbool bt_leaf_insert(bt* tree, bt_leaf* leaf, void* data, anbool unique,
205                              compare_func_2 compare, void* token, void* overflow) {
206     int lower, upper;
207     int nshift;
208     int index;
209 
210     // binary search...
211     lower = -1;
212     upper = leaf->N;
213     while (lower < (upper-1)) {
214         int mid;
215         int cmp;
216         mid = (upper + lower) / 2;
217         cmp = compare(data, get_element(tree, leaf, mid), token);
218         if (!cmp && unique) return FALSE;
219         if (cmp >= 0)
220             lower = mid;
221         else
222             upper = mid;
223     }
224     // index to insert at:
225     index = lower + 1;
226 
227     // duplicate value?
228     if (unique && (index > 0))
229         if (compare(data, get_element(tree, leaf, index-1), token) == 0)
230             return FALSE;
231 
232     // shift...
233     nshift = leaf->N - index;
234     if (leaf->N == tree->blocksize) {
235         // this node is full.  insert the element and put the overflowing
236         // element in "overflow".
237         if (nshift) {
238             memcpy(overflow, get_element(tree, leaf, leaf->N-1), tree->datasize);
239             nshift--;
240         } else {
241             memcpy(overflow, data, tree->datasize);
242             return TRUE;
243         }
244     } else {
245         leaf->N++;
246         tree->N++;
247     }
248     memmove(get_element(tree, leaf, index+1),
249             get_element(tree, leaf, index),
250             nshift * tree->datasize);
251     // insert...
252     memcpy(get_element(tree, leaf, index), data, tree->datasize);
253     return TRUE;
254 }
255 
next_node(bt_node ** ancestors,int nancestors,bt_node * child,bt_node ** nextancestors,int * nnextancestors)256 static bt_node* next_node(bt_node** ancestors, int nancestors,
257                           bt_node* child,
258                           bt_node** nextancestors, int* nnextancestors) {
259     // -first, find the first ancestor of whom we are a left
260     //  (grand^n)-child.
261     bt_node* parent = NULL;
262     int i, j;
263     for (i=nancestors-1; i>=0; i--) {
264         parent = ancestors[i];
265         if (parent->branch.children[0] == child)
266             break;
267         child = parent;
268     }
269     if (i < 0) {
270         // no next node.
271         return NULL;
272     }
273 
274     // we share ancestors from the root to "parent".
275     for (j=i; j>=0; j--)
276         nextancestors[j] = ancestors[j];
277     *nnextancestors = i+1;
278 
279     // -next, find the leftmost leaf of the parent's right branch.
280     child = parent->branch.children[1];
281     while (!isleaf(child)) {
282         nextancestors[(*nnextancestors)++] = child;
283         child = child->branch.children[0];
284     }
285     return child;
286 }
287 
288 // Pure?
bt_leaf_contains(bt * tree,bt_leaf * leaf,void * data,compare_func_2 compare,void * token)289 static anbool bt_leaf_contains(bt* tree, bt_leaf* leaf, void* data,
290                                compare_func_2 compare, void* token) {
291     int lower, upper;
292     lower = -1;
293     upper = leaf->N;
294     while (lower < (upper-1)) {
295         int mid;
296         int cmp;
297         mid = (upper + lower) / 2;
298         cmp = compare(data, get_element(tree, leaf, mid), token);
299         if (cmp == 0) return TRUE;
300         if (cmp > 0)
301             lower = mid;
302         else
303             upper = mid;
304     }
305     // duplicate value?
306     if (lower >= 0)
307         if (compare(data, get_element(tree, leaf, lower), token) == 0)
308             return TRUE;
309     return FALSE;
310 }
311 
312 // Pure?
bt_contains(bt * tree,void * data,compare_func compare)313 anbool bt_contains(bt* tree, void* data, compare_func compare) {
314     return bt_contains2(tree, data, compare_helper, compare);
315 }
316 
bt_contains2(bt * tree,void * data,compare_func_2 compare,void * token)317 anbool bt_contains2(bt* tree, void* data, compare_func_2 compare, void* token) {
318     bt_node *n;
319     int cmp;
320     int dir;
321 
322     if (!tree->root)
323         return FALSE;
324 
325     dir = 0;
326     for (n = tree->root; !isleaf(n); n = getchild(n, dir)) {
327         cmp = compare(data, first_element(n->branch.children[1]), token);
328         if (cmp == 0)
329             return TRUE;
330         dir = (cmp > 0);
331     }
332     return bt_leaf_contains(tree, &n->leaf, data, compare, token);
333 }
334 
update_firstleaf(bt_node ** ancestors,int nancestors,bt_node * child,bt_leaf * leaf)335 static void update_firstleaf(bt_node** ancestors, int nancestors,
336                              bt_node* child, bt_leaf* leaf) {
337     int i;
338     for (i=nancestors-1; i>=0; i--) {
339         if (ancestors[i]->branch.children[0] != child)
340             break;
341         ancestors[i]->branch.firstleaf = leaf;
342         child = ancestors[i];
343     }
344 }
345 
bt_insert(bt * tree,void * data,anbool unique,compare_func compare)346 anbool bt_insert(bt* tree, void* data, anbool unique, compare_func compare) {
347     return bt_insert2(tree, data, unique, compare_helper, compare);
348 }
349 
bt_insert2(bt * tree,void * data,anbool unique,compare_func_2 compare,void * token)350 anbool bt_insert2(bt* tree, void* data, anbool unique, compare_func_2 compare, void* token) {
351     bt_node *y, *z; /* Top node to update balance factor, and parent. */
352     bt_node *p, *q; /* Iterator, and parent. */
353     bt_node *n;     /* Newly inserted node. */
354     bt_node *w;     /* New root of rebalanced subtree. */
355     int dir;                /* Direction to descend. */
356     bt_node* np;
357 
358     bt_node* ancestors[AVL_MAX_HEIGHT];
359     int nancestors = 0;
360     unsigned char da[AVL_MAX_HEIGHT]; /* Cached comparison results. */
361     int k = 0;              /* Number of cached results. */
362     unsigned char overflow[tree->datasize];
363     anbool rtn;
364     anbool willfit;
365     int cmp;
366     int i;
367 
368     if (!tree->root) {
369         // inserting the first element...
370         n = bt_new_leaf(tree);
371         tree->root = n;
372         bt_leaf_insert(tree, &n->leaf, data, unique, compare, token, NULL);
373         return TRUE;
374     }
375 
376     z = y = tree->root;
377     dir = 0;
378 
379     for (q = z, p = y;
380          !isleaf(p);
381          q = p, p = p->branch.children[dir]) {
382         cmp = compare(data, first_element(p->branch.children[1]), token);
383         if (unique && (cmp == 0))
384             return FALSE;
385         if (p->branch.balance != 0) {
386             z = q;
387             y = p;
388             k = 0;
389         }
390         ancestors[nancestors++] = p;
391         da[k++] = dir = (cmp > 0);
392     }
393     cmp = compare(data, first_element(p), token);
394 
395     // will this element fit in the current node?
396     willfit = (p->leaf.N < tree->blocksize);
397     if (willfit) {
398         rtn = bt_leaf_insert(tree, &p->leaf, data, unique, compare, token, overflow);
399         // duplicate value?
400         if (!rtn)
401             return rtn;
402         for (i=0; i<nancestors; i++)
403             ancestors[i]->branch.N++;
404         return TRUE;
405     }
406 
407     da[k++] = (cmp > 0);
408 
409     if (cmp > 0) {
410         // insert the new element into this node and shuffle the
411         // overflowing element (which may be the new element)
412         // into the next node, if it exists, or a new node.
413         bt_node* nextnode;
414         bt_node* nextancestors[AVL_MAX_HEIGHT];
415         int nnextancestors;
416 
417         /*
418          HACK - should we traverse the tree looking for the next node,
419          or just take the right sibling if we're the left child of a
420          balanced parent?
421          */
422 
423         rtn = bt_leaf_insert(tree, &p->leaf, data, unique, compare, token, overflow);
424         if (!rtn)
425             // duplicate value.
426             return rtn;
427         nextnode = next_node(ancestors, nancestors, p, nextancestors, &nnextancestors);
428         assert(!nextnode || isleaf(nextnode));
429         if (nextnode && (nextnode->leaf.N < tree->blocksize)) {
430             // there's room; insert the element!
431             rtn = bt_leaf_insert(tree, &nextnode->leaf, overflow, unique, compare, token, NULL);
432             for (i=0; i<nnextancestors; i++)
433                 nextancestors[i]->branch.N++;
434             return rtn;
435         }
436 
437         // no room (or no next node); add a new node to the right to hold
438         // the overflowed data.
439         dir = 1;
440         data = overflow;
441     } else {
442         // add a new node to the left.
443         dir = 0;
444     }
445 
446     // we have "q", the parent node, and "p", the existing leaf node which is
447     // full.  we create a new branch node, "np", to take "p"'s place.
448     // we move "p" down to be the child (1-dir) of "np", and create a new
449     // leaf node, "n", to be child (dir) of "np".
450 
451     // create "n", a new leaf node to hold this element.
452     n = bt_new_leaf(tree);
453     if (!n)
454         return FALSE;
455     rtn = bt_leaf_insert(tree, &n->leaf, data, unique, compare, token, NULL);
456     if (!rtn) {
457         free(n);
458         return FALSE;
459     }
460 
461     // create "np", a new branch node to take p's place.
462     np = bt_new_branch(tree);
463     if (!np)
464         return FALSE;
465     np->branch.children[dir] = n;
466     np->branch.children[1-dir] = p;
467     np->branch.N = p->leaf.N + 1;
468     np->branch.firstleaf = &(np->branch.children[0]->leaf);
469     if (!isleaf(q)) {
470         if (q->branch.children[0] == p) {
471             q->branch.children[0] = np;
472             if (!dir)
473                 update_firstleaf(ancestors, nancestors, np, np->branch.firstleaf);
474         } else if (q->branch.children[1] == p) // need this because it could be that p = q = root.
475             q->branch.children[1] = np;
476     }
477 
478     if (p == tree->root)
479         tree->root = np;
480 
481     for (i=0; i<nancestors; i++)
482         ancestors[i]->branch.N++;
483 
484     if (!y || isleaf(y))
485         return TRUE;
486 
487     for (p = y, k = 0;
488          p != np;
489          p = p->branch.children[da[k]], k++)
490         if (da[k] == 0)
491             p->branch.balance--;
492         else
493             p->branch.balance++;
494 
495     if (y->branch.balance == -2) {
496         bt_node *x = y->branch.children[0];
497         if (x->branch.balance == -1) {
498             /*
499              y
500              |- x
501              |  |- x0
502              |  |- x1
503              |- y1
504 
505              becomes
506 
507              x
508              |- x0
509              |- y
510              .  |- x1
511              .  |- y1
512              */
513             w = x;
514             y->branch.children[0] = x->branch.children[1];
515             x->branch.children[1] = y;
516             x->branch.balance = y->branch.balance = 0;
517 
518             y->branch.firstleaf = firstleaf(y->branch.children[0]);
519             y->branch.N = sum_childN(&y->branch);
520             x->branch.N = sum_childN(&x->branch);
521 
522         } else {
523             /*
524              y
525              |- x
526              |  |- x0
527              |  |- x1 (= w)
528              |     |- x10
529              |     |- x11
530              |- y1
531 
532              becomes
533 
534              x1
535              |- x
536              |  |- x0
537              |  |- x10
538              |- y
539              .  |- x11
540              .  |- y1
541              */
542 
543             assert (x->branch.balance == 1);
544             w = x->branch.children[1];
545             x->branch.children[1] = w->branch.children[0];
546             w->branch.children[0] = x;
547             y->branch.children[0] = w->branch.children[1];
548             w->branch.children[1] = y;
549 
550             y->branch.firstleaf = firstleaf(y->branch.children[0]);
551             w->branch.firstleaf = x->branch.firstleaf;
552 
553             y->branch.N = sum_childN(&y->branch);
554             x->branch.N = sum_childN(&x->branch);
555             w->branch.N = sum_childN(&w->branch);
556 
557             if (w->branch.balance == -1) {
558                 x->branch.balance = 0;
559                 y->branch.balance = 1;
560             } else if (w->branch.balance == 0)
561                 x->branch.balance = y->branch.balance = 0;
562             else {
563                 x->branch.balance = -1;
564                 y->branch.balance = 0;
565             }
566             w->branch.balance = 0;
567 
568         }
569     } else if (y->branch.balance == 2) {
570         bt_node *x = y->branch.children[1];
571         if (x->branch.balance == 1) {
572             /*
573              y
574              |- y0
575              |- x
576              .   |- x0
577              .   |- x1
578 
579              becomes
580 
581              x
582              |- y
583              |  |- y0
584              |  |- x0
585              |- x1
586              */
587             w = x;
588             y->branch.children[1] = x->branch.children[0];
589             x->branch.children[0] = y;
590             x->branch.balance = y->branch.balance = 0;
591 
592             x->branch.firstleaf = y->branch.firstleaf;
593 
594             y->branch.N = sum_childN(&y->branch);
595             x->branch.N = sum_childN(&x->branch);
596 
597 
598         } else {
599             /*
600              y
601              |- y0
602              |- x
603              .  |- x0
604              .  |  |- x00
605              .  |  |- x01
606              .  |- x1
607 
608              becomes
609 
610              x0
611              |- y
612              |  |- y0
613              |  |- x00
614              |- x
615              .  |- x01
616              .  |- x1
617              */
618             assert (x->branch.balance == -1);
619             w = x->branch.children[0];
620             x->branch.children[0] = w->branch.children[1];
621             w->branch.children[1] = x;
622             y->branch.children[1] = w->branch.children[0];
623             w->branch.children[0] = y;
624 
625             y->branch.N = sum_childN(&y->branch);
626             x->branch.N = sum_childN(&x->branch);
627             w->branch.N = sum_childN(&w->branch);
628 
629             x->branch.firstleaf = firstleaf(x->branch.children[0]);
630             w->branch.firstleaf = y->branch.firstleaf;
631 
632             if (w->branch.balance == 1) {
633                 x->branch.balance = 0;
634                 y->branch.balance = -1;
635             } else if (w->branch.balance == 0)
636                 x->branch.balance = y->branch.balance = 0;
637             else {
638                 x->branch.balance = 1;
639                 y->branch.balance = 0;
640             }
641             w->branch.balance = 0;
642 
643         }
644     } else
645         goto finished;
646 
647     if (y == tree->root)
648         tree->root = w;
649     else {
650         if (y == z->branch.children[0]) {
651             z->branch.children[0] = w;
652             z->branch.firstleaf = w->branch.firstleaf;
653         } else
654             z->branch.children[1] = w;
655     }
656 
657  finished:
658     return TRUE;
659 }
660 
661 // Pure?
bt_access(bt * tree,int index)662 void* bt_access(bt* tree, int index) {
663     bt_node* n = tree->root;
664     int offset = index;
665     while (!isleaf(n)) {
666         int Nleft = node_N(n->branch.children[0]);
667         if (offset >= Nleft) {
668             n = n->branch.children[1];
669             offset -= Nleft;
670         } else
671             n = n->branch.children[0];
672     }
673     return get_element(tree, &n->leaf, offset);
674 }
675 
bt_print_node(bt * tree,bt_node * node,char * indent,void (* print_element)(void * val))676 static void bt_print_node(bt* tree, bt_node* node, char* indent,
677                           void (*print_element)(void* val)) {
678     printf("%s", indent);
679     printf("(%p) ", node);
680     printf("N=%i", node_N(node));
681 
682     if (!isleaf(node)) {
683         char* subind;
684         char* addind = "  ";
685         printf(", leftmost (%p)", node->branch.firstleaf);
686         printf(", Nleft=%i, Nright=%i, balance %i.\n",
687                node_N(node->branch.children[0]),
688                node_N(node->branch.children[1]),
689                node->branch.balance);
690         subind = malloc(strlen(indent) + strlen(addind) + 1);
691         sprintf(subind, "%s%s", indent, addind);
692         printf("%sLeft child:\n", indent);
693         bt_print_node(tree, node->branch.children[0], subind, print_element);
694         printf("%sRight child:\n", indent);
695         bt_print_node(tree, node->branch.children[1], subind, print_element);
696         free(subind);
697     } else {
698         int i;
699         printf(".  Leaf.");
700         if (print_element) {
701             printf("  [ ");
702             for (i=0; i<node_N(node); i++)
703                 print_element(get_element(tree, &node->leaf, i));
704         }
705         printf("]\n");
706     }
707 }
708 
bt_print(bt * tree,void (* print_element)(void * val))709 void bt_print(bt* tree, void (*print_element)(void* val)) {
710     printf("  bt: N=%i, datasize=%i, blocksize=%i.\n", tree->N,
711            tree->datasize, tree->blocksize);
712     printf("      root=(%p)\n", tree->root);
713     if (!tree->root) {
714         printf("  Empty tree.\n");
715         return;
716     }
717     bt_print_node(tree, tree->root, "  ", print_element);
718 }
719 
bt_print_struct_node(bt * tree,bt_node * node,char * indent,void (* print_element)(void * val))720 static void bt_print_struct_node(bt* tree, bt_node* node, char* indent,
721                                  void (*print_element)(void* val)) {
722 
723     printf("%s", indent);
724     if (!isleaf(node)) {
725         char* subind;
726         char* addind = "|--";
727         printf("(bal %i)\n", node->branch.balance);
728         subind = malloc(strlen(indent) + strlen(addind) + 1);
729         sprintf(subind, "%s%s", indent, addind);
730         bt_print_struct_node(tree, node->branch.children[0], subind, print_element);
731         bt_print_struct_node(tree, node->branch.children[1], subind, print_element);
732     } else {
733         int i;
734         printf("(leaf)");
735         if (print_element) {
736             printf(" [ ");
737             for (i=0; i<node_N(node); i++)
738                 print_element(get_element(tree, &node->leaf, i));
739             printf("]");
740         }
741         printf("\n");
742     }
743 }
744 
bt_print_structure(bt * tree,void (* print_element)(void * val))745 void bt_print_structure(bt* tree, void (*print_element)(void* val)) {
746     bt_print_struct_node(tree, tree->root, "   ", print_element);
747 }
748 
749