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