1 /* CC0 license (public domain) - see LICENSE file for details */
2 /* This code is based on ccan/strmap.c. */
3 #include <ccan/bitops/bitops.h>
4 #include <ccan/intmap/intmap.h>
5 #include <ccan/short_types/short_types.h>
6 #include <ccan/str/str.h>
12 /* These point to strings or nodes. */
13 struct intmap child[2];
14 /* Encoding both prefix and critbit: 1 is appended to prefix. */
15 intmap_index_t prefix_and_critbit;
18 static int critbit(const struct intmap *n)
20 return bitops_ls64(n->u.n->prefix_and_critbit);
23 static intmap_index_t prefix_mask(int critbit)
25 /* Mask does not include critbit itself, but can't shift by critbit+1 */
26 return -2ULL << critbit;
29 static intmap_index_t prefix_and_critbit(intmap_index_t v, int n)
31 intmap_index_t critbit = ((intmap_index_t)1 << n);
32 return (v & ~(critbit - 1)) | critbit;
35 void *intmap_get_(const struct intmap *map, intmap_index_t index)
38 if (!intmap_empty_(map)) {
39 const struct intmap *n = map;
40 /* Anything with NULL value is a node. */
42 /* FIXME: compare cmp prefix, if not equal, ENOENT */
43 u8 direction = (index >> critbit(n)) & 1;
44 n = &n->u.n->child[direction];
53 static bool split_node(struct intmap *n, intmap_index_t nodeindex,
54 intmap_index_t index, const void *value)
59 /* Find highest bit where they differ. */
60 unsigned int critbit = bitops_hs64(nodeindex ^ index);
61 assert(critbit < CHAR_BIT*sizeof(index));
63 /* Which direction do we go at this bit? */
64 new_dir = (index >> critbit) & 1;
66 /* Allocate new node. */
67 newn = malloc(sizeof(*newn));
72 newn->prefix_and_critbit = prefix_and_critbit(index, critbit);
73 newn->child[new_dir].v = (void *)value;
74 newn->child[new_dir].u.i = index;
75 newn->child[!new_dir] = *n;
82 bool intmap_add_(struct intmap *map, intmap_index_t index, const void *value)
89 if (intmap_empty_(map)) {
91 map->v = (void *)value;
96 /* Anything with NULL value is a node. */
98 int crit = critbit(n);
99 intmap_index_t mask = prefix_mask(crit);
100 u8 direction = (index >> crit) & 1;
102 if ((index & mask) != (n->u.n->prefix_and_critbit & mask))
103 return split_node(n, n->u.n->prefix_and_critbit & mask,
105 n = &n->u.n->child[direction];
108 if (index == n->u.i) {
113 return split_node(n, n->u.i, index, value);
116 void *intmap_del_(struct intmap *map, intmap_index_t index)
118 struct intmap *parent = NULL, *n;
123 if (intmap_empty_(map)) {
128 /* Find closest, but keep track of parent. */
130 /* Anything with NULL value is a node. */
132 /* FIXME: compare cmp prefix, if not equal, ENOENT */
134 direction = (index >> critbit(n)) & 1;
135 n = &n->u.n->child[direction];
138 /* Did we find it? */
139 if (index != n->u.i) {
147 /* We deleted last node. */
150 struct node *old = parent->u.n;
151 /* Raise other node to parent. */
152 *parent = old->child[!direction];
159 void *intmap_first_(const struct intmap *map, intmap_index_t *indexp)
161 const struct intmap *n;
163 if (intmap_empty_(map)) {
169 /* Anything with NULL value is a node. */
171 n = &n->u.n->child[0];
177 void *intmap_after_(const struct intmap *map, intmap_index_t *indexp)
179 const struct intmap *n, *prev = NULL;
180 intmap_index_t index = (*indexp) + 1;
182 /* Special case of overflow */
186 /* Special case of empty map */
187 if (intmap_empty_(map))
190 /* Follow down, until prefix differs. */
193 int crit = critbit(n);
195 intmap_index_t prefix, idx;
197 idx = (index >> crit);
200 /* Leave critbit in place: we can't shift by 64 anyway */
202 prefix = n->u.n->prefix_and_critbit >> crit;
204 /* If this entire tree is greater than index, take first */
206 return intmap_first_(n, indexp);
207 /* If this entire tree is less than index, we're past it. */
208 else if (idx > prefix)
209 goto try_greater_tree;
211 /* Remember greater tree for backtracking */
214 n = &n->u.n->child[direction];
217 /* Found a successor? */
218 if (n->u.i >= index) {
225 /* If we ever took a lesser branch, go back to greater branch */
227 return intmap_first_(&prev->u.n->child[1], indexp);
234 void *intmap_before_(const struct intmap *map, intmap_index_t *indexp)
236 const struct intmap *n, *prev = NULL;
237 intmap_index_t index = (*indexp) - 1;
239 /* Special case of overflow */
240 if (index == (intmap_index_t)-1ULL)
243 /* Special case of empty map */
244 if (intmap_empty_(map))
247 /* Follow down, until prefix differs. */
250 int crit = critbit(n);
252 intmap_index_t prefix, idx;
254 idx = (index >> crit);
257 /* Leave critbit in place: we can't shift by 64 anyway */
259 prefix = n->u.n->prefix_and_critbit >> crit;
261 /* If this entire tree is less than index, take last */
263 return intmap_last_(n, indexp);
264 /* If this entire tree is greater than index, we're past it. */
265 else if (idx < prefix)
266 goto try_lesser_tree;
268 /* Remember lesser tree for backtracking */
271 n = &n->u.n->child[direction];
274 /* Found a predecessor? */
275 if (n->u.i <= index) {
282 /* If we ever took a lesser branch, go back to lesser branch */
284 return intmap_last_(&prev->u.n->child[0], indexp);
291 void *intmap_last_(const struct intmap *map, intmap_index_t *indexp)
293 const struct intmap *n;
295 if (intmap_empty_(map)) {
301 /* Anything with NULL value is a node. */
303 n = &n->u.n->child[1];
309 static void clear(struct intmap n)
312 clear(n.u.n->child[0]);
313 clear(n.u.n->child[1]);
318 void intmap_clear_(struct intmap *map)
320 if (!intmap_empty_(map))
325 bool intmap_iterate_(const struct intmap *n,
326 bool (*handle)(intmap_index_t, void *, void *),
328 intmap_index_t offset)
330 /* Can only happen at root */
331 if (intmap_empty_(n))
335 return handle(n->u.i - offset, n->v, data);
337 return intmap_iterate_(&n->u.n->child[0], handle, data, offset)
338 && intmap_iterate_(&n->u.n->child[1], handle, data, offset);