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_last_(const struct intmap *map, intmap_index_t *indexp)
236 const struct intmap *n;
238 if (intmap_empty_(map)) {
244 /* Anything with NULL value is a node. */
246 n = &n->u.n->child[1];
252 static void clear(struct intmap n)
255 clear(n.u.n->child[0]);
256 clear(n.u.n->child[1]);
261 void intmap_clear_(struct intmap *map)
263 if (!intmap_empty_(map))
268 bool intmap_iterate_(const struct intmap *n,
269 bool (*handle)(intmap_index_t, void *, void *),
271 intmap_index_t offset)
273 /* Can only happen at root */
274 if (intmap_empty_(n))
278 return handle(n->u.i - offset, n->v, data);
280 return intmap_iterate_(&n->u.n->child[0], handle, data, offset)
281 && intmap_iterate_(&n->u.n->child[1], handle, data, offset);