1 /* tag: Tom Lord Tue Dec 4 14:41:33 2001 (bitset-tree.h) 2 */ 3 /* bitset-tree.h - 4 * 5 **************************************************************** 6 * Copyright (C) 2000 Tom Lord 7 * 8 * See the file "COPYING" for further information about 9 * the copyright and warranty status of this work. 10 */ 11 12 #ifndef INCLUDE__BITSETS__BITSET_TREE_H 13 #define INCLUDE__BITSETS__BITSET_TREE_H 14 15 16 17 #include "hackerlab/mem/alloc-limits.h" 18 #include "hackerlab/bitsets/bitset.h" 19 20 21 22 /************************************************************************ 23 *(h2 "Bitset Tree Rules") 24 * 25 * The branching structure of a bitset tree is determined by an array 26 * of structures of type `struct bits_tree_rule': 27 * 28 */ 29 30 /* update bits-print.c when changing fields here */ 31 /*(c #s"struct bits_tree_rule" :category type) 32 * struct bits_tree_rule; 33 * 34 insert*/ 35 36 struct bits_tree_rule 37 { 38 int fanout; 39 size_t subset_size; 40 size_t subset_shift; 41 size_t subset_mask; 42 }; 43 44 /*end-insert 45 * 46 * An array of `struct bits_tree_rule' values determines the branching 47 * structure of a bitset tree. Nodes at distance `N' from the the 48 * root of the tree are defined by the `N'th element of the array. 49 * (See also xref:"The Bitset Tree Data Structure".) 50 * 51 * `fanout' is the number of sub-trees a node has. It is 0 for leaf 52 * nodes. 53 * 54 * `subset_size' is the number of bits in each sub-tree. For leaf 55 * nodes, this should be the number of bits in the leaf node. For 56 * optimal performance, `subset_size' should be a multiple of `sizeof 57 * (bitset_subset)'. 58 * 59 * Given a non-leaf bitset tree `T', and a bit address within that 60 * tree, `B', the subset containing that bit is: 61 * 62 * T[B / subset_size] 63 * 64 * The relative address of the bit within that subtree is: 65 * 66 * B % subset_size 67 * 68 * The fields `subset_shift' and `subset_mask' are not used for leaf 69 * nodes. For non-leaf nodes, if `subset_size' is not a power of two, 70 * the fields `subset_shift' and `subset_mask' should be 0. 71 * Otherwise, they should be set as follows: 72 * 73 * subset_shift = log2(subset_size) 74 * subset_mask = subset_size - 1 75 * 76 * Here is an example for bitset containing `1<<21' elements. In this 77 * example, the root node of the tree has 32 sub-trees; each second 78 * and third level tree has 16 sub-trees; leaf nodes have 256 bits 79 * (`32 * 16 * 16 * 256 == 1<<21'): 80 * 81 * struct bits_tree_rule bitset_rule[] = 82 * { 83 * {32, 1<<16, 16, 0xffff}, // root has 32 subtrees 84 * {16, 1<<12, 12, 0xfff}, // level 1 nodes have 16 subtrees 85 * {16, 256, 8, 0xff}, // level 2 nodes have 16 subtrees 86 * {0, 256, 0, 0} // leaf nodes have 256 bits 87 * }; 88 * 89 * Bitset trees of the same size (`1<<21' bits) could be represented 90 * other ways. For example: 91 * 92 * struct bits_tree_rule bitset_rule[] = 93 * { 94 * {16, 1<<17, 17, 0x1ffff}, // root has 16 subtrees 95 * {2, 1<<16, 16, 0xffff}, // level 1 nodes have 2 subtrees 96 * {16, 1<<12, 12, 0xfff}, // level 2 nodes have 16 subtrees 97 * {16, 256, 8, 0xff}, // level 3 nodes have 16 subtrees 98 * {0, 256, 0, 0} // leaf nodes have 256 bits 99 * }; 100 * 101 * Some care is necessary when choosing the values for an array of 102 * `struct bits_tree_rule'. For a given bitset size, a deeper bitset 103 * tree (more elements in the rules array) means that the worst-case 104 * cost of accessing or modifying a single bit is raised. On the 105 * other hand, homogenous sub-trees (at any depth) are (often) 106 * replaced by a 0 or `-1' pointer saving both space and time -- a 107 * deeper tree may offer more opportunities for that optimization. 108 * The best branching structure depends on the particular sets your 109 * programs uses and the particular access pattern of your program; 110 * experimentation with different branching structures may be 111 * necessary. 112 * 113 */ 114 115 116 struct bits_tree_no_such_structure; 117 118 typedef struct bits_tree_no_such_structure * bits_tree; 119 120 #define bits_tree_which_bitset(L, R, X) ((R)->subset_shift ? ((X) >> (R)->subset_shift) : ((X) / (R)->subset_size)) 121 122 #define bits_tree_which_bit(L, R, X) ((R)->subset_mask ? ((X) & (R)->subset_mask) : ((X) % (R)->subset_size)) 123 124 #define bits_tree_full_bitset ((bits_tree)-1L) 125 126 #define bits_tree_empty_bitset ((bits_tree)0) 127 128 129 130 131 /* automatically generated __STDC__ prototypes */ 132 extern bits_tree bits_tree_alloc (alloc_limits lim, 133 struct bits_tree_rule * rule); 134 extern void bits_tree_free (alloc_limits lim, 135 struct bits_tree_rule * rule, 136 bits_tree b); 137 extern bit_t bits_tree_compact (alloc_limits lim, 138 struct bits_tree_rule * rule, 139 bits_tree a); 140 extern bits_tree bits_tree_dup (alloc_limits lim, 141 struct bits_tree_rule * rule, 142 bits_tree a); 143 extern int bits_tree_get_subset (bitset_subset * answer, 144 alloc_limits lim, 145 struct bits_tree_rule * rule, 146 bits_tree b, 147 bit_t n); 148 extern int bits_tree_is_member (alloc_limits lim, 149 struct bits_tree_rule * rule, 150 bits_tree b, 151 int n); 152 extern int bits_tree_is_equal (alloc_limits lim, 153 struct bits_tree_rule * rule, 154 bits_tree a, bits_tree b); 155 extern int bits_tree_is_subset (alloc_limits lim, 156 struct bits_tree_rule * rule, 157 bits_tree a, 158 bits_tree b); 159 extern int bits_tree_is_empty (alloc_limits lim, 160 struct bits_tree_rule * rule, 161 bits_tree a); 162 extern int bits_tree_is_full (alloc_limits lim, 163 struct bits_tree_rule * rule, 164 bits_tree a); 165 extern int bits_tree_is_empty_range (alloc_limits lim, 166 struct bits_tree_rule * rule, 167 bits_tree a, 168 int from, 169 int to); 170 extern int bits_tree_is_full_range (alloc_limits lim, 171 struct bits_tree_rule * rule, 172 bits_tree a, 173 int from, 174 int to); 175 extern int bits_tree_adjoin (alloc_limits lim, 176 struct bits_tree_rule * rule, 177 bits_tree b, 178 int n); 179 extern int bits_tree_remove (alloc_limits lim, 180 struct bits_tree_rule * rule, 181 bits_tree b, int n); 182 extern int bits_tree_toggle (alloc_limits lim, 183 struct bits_tree_rule * rule, 184 bits_tree b, 185 int n); 186 extern void bits_tree_clear (alloc_limits lim, 187 struct bits_tree_rule * rule, 188 bits_tree b); 189 extern void bits_tree_fill (alloc_limits lim, 190 struct bits_tree_rule * rule, 191 bits_tree b); 192 extern int bits_tree_clear_range (alloc_limits lim, 193 struct bits_tree_rule * rule, 194 bits_tree b, 195 int from, 196 int to); 197 extern int bits_tree_fill_range (alloc_limits lim, 198 struct bits_tree_rule * rule, 199 bits_tree b, 200 int from, 201 int to); 202 extern void bits_tree_complement (alloc_limits lim, 203 struct bits_tree_rule * rule, 204 bits_tree b); 205 extern int bits_tree_assign (alloc_limits lim, 206 struct bits_tree_rule * rule, 207 bits_tree a, 208 bits_tree b); 209 extern int bits_tree_union (alloc_limits lim, 210 struct bits_tree_rule * rule, 211 bits_tree a, 212 bits_tree b); 213 extern int bits_tree_intersection (alloc_limits lim, 214 struct bits_tree_rule * rule, 215 bits_tree a, 216 bits_tree b); 217 extern int bits_tree_difference (alloc_limits lim, 218 struct bits_tree_rule * rule, 219 bits_tree a, 220 bits_tree b); 221 extern int bits_tree_revdifference (alloc_limits lim, 222 struct bits_tree_rule * rule, 223 bits_tree a, 224 bits_tree b); 225 extern int bits_tree_xor (alloc_limits lim, 226 struct bits_tree_rule * rule, 227 bits_tree a, 228 bits_tree b); 229 extern int bits_tree_population (alloc_limits lim, 230 struct bits_tree_rule * rule, 231 bits_tree a); 232 extern int bits_tree_population_range (alloc_limits lim, 233 struct bits_tree_rule * rule, 234 bits_tree a, int from, int to); 235 extern int bits_tree_ffs (alloc_limits lim, 236 struct bits_tree_rule * rule, 237 bits_tree b); 238 extern int bits_tree_ffc (alloc_limits lim, struct bits_tree_rule * rule, bits_tree b); 239 extern int bits_tree_ffs_range (alloc_limits lim, 240 struct bits_tree_rule * rule, 241 bits_tree b, 242 int from, 243 int to); 244 extern int bits_tree_ffc_range (alloc_limits lim, 245 struct bits_tree_rule * rule, 246 bits_tree b, 247 int from, 248 int to); 249 #endif /* INCLUDE__BITSETS__BITSET_TREE_H */ 250