1 /*
2  # This file is part of the Astrometry.net suite.
3  # Licensed under a 3-clause BSD style license - see LICENSE
4  */
5 
6 #ifndef BT_H
7 #define BT_H
8 
9 #include "astrometry/keywords.h"
10 #include "astrometry/an-bool.h"
11 /*
12  We distinguish between "branch" (ie, internal) nodes and "leaf" nodes
13  because leaf nodes can be much smaller.  Since there are a lot of leaves,
14  the space savings can be considerable.
15 
16  The data owned by a leaf node follows right after the leaf struct
17  itself.
18  */
19 
20 struct bt_leaf {
21     // always 1; must be the first element in the struct.
22     unsigned char isleaf;
23     // number of data elements.
24     short N;
25     // data follows implicitly.
26 };
27 typedef struct bt_leaf bt_leaf;
28 
29 struct bt_branch {
30     // always 0; must be the first element in the struct.
31     unsigned char isleaf;
32     // AVL balance
33     signed char balance;
34 
35     //struct bt_node* children[2];
36     union bt_node* children[2];
37 
38     // the leftmost leaf node in this subtree.
39     bt_leaf* firstleaf;
40 
41     // number of element in this subtree.
42     int N;
43 };
44 typedef struct bt_branch bt_branch;
45 
46 union bt_node {
47     bt_leaf leaf;
48     bt_branch branch;
49 };
50 typedef union bt_node bt_node;
51 
52 struct bt {
53     bt_node* root;
54     int datasize;
55     int blocksize;
56     int N;
57 };
58 typedef struct bt bt;
59 
60 typedef int (*compare_func)(const void* v1, const void* v2);
61 
62 typedef int (*compare_func_2)(const void* v1, const void* v2, void* token);
63 
64 Malloc bt* bt_new(int datasize, int blocksize);
65 
66 void bt_free(bt* tree);
67 
68 Pure //Inline
69 int bt_size(bt* tree);
70 
71 anbool bt_insert(bt* tree, void* data, anbool unique, compare_func compare);
72 
73 anbool bt_insert2(bt* tree, void* data, anbool unique, compare_func_2 compare, void* token);
74 
75 anbool bt_contains(bt* tree, void* data, compare_func compare);
76 
77 anbool bt_contains2(bt* tree, void* data, compare_func_2 compare, void* token);
78 
79 void* bt_access(bt* tree, int index);
80 
81 void bt_print(bt* tree, void (*print_element)(void* val));
82 
83 void bt_print_structure(bt* tree, void (*print_element)(void* val));
84 
85 int bt_height(bt* tree);
86 
87 int bt_count_leaves(bt* tree);
88 
89 int bt_check(bt* tree);
90 
91 #endif
92