1 /* CC0 license (public domain) - see LICENSE file for details */
2 /* This code is based on ccan/strmap.c. */
3 #include <ccan/intmap/intmap.h>
4 #include <ccan/short_types/short_types.h>
5 #include <ccan/str/str.h>
6 #include <ccan/ilog/ilog.h>
12 /* These point to strings or nodes. */
13 struct intmap child[2];
14 /* The bit where these children differ (0 == lsb) */
18 /* Closest member to this in a non-empty map. */
19 static struct intmap *closest(struct intmap *n, intmap_index_t index)
21 /* Anything with NULL value is a node. */
23 u8 direction = (index >> n->u.n->bit_num) & 1;
24 n = &n->u.n->child[direction];
29 void *intmap_get_(const struct intmap *map, intmap_index_t index)
34 if (!intmap_empty_(map)) {
35 n = closest((struct intmap *)map, index);
43 bool intmap_add_(struct intmap *map, intmap_index_t index, const void *value)
52 if (intmap_empty_(map)) {
54 map->v = (void *)value;
58 /* Find closest existing member. */
59 n = closest(map, index);
61 /* Find highest bit where they differ. */
62 bit_num = ilog64(n->u.i ^ index);
69 assert(bit_num < CHAR_BIT*sizeof(index));
71 /* Which direction do we go at this bit? */
72 new_dir = (index >> bit_num) & 1;
74 /* Allocate new node. */
75 newn = malloc(sizeof(*newn));
80 newn->bit_num = bit_num;
81 newn->child[new_dir].v = (void *)value;
82 newn->child[new_dir].u.i = index;
84 /* Find where to insert: not closest, but first which differs! */
89 /* Subtle: bit numbers are "backwards" for comparison */
90 if (n->u.n->bit_num < bit_num)
93 direction = (index >> n->u.n->bit_num) & 1;
94 n = &n->u.n->child[direction];
97 newn->child[!new_dir] = *n;
103 void *intmap_del_(struct intmap *map, intmap_index_t index)
105 struct intmap *parent = NULL, *n;
110 if (intmap_empty_(map)) {
115 /* Find closest, but keep track of parent. */
117 /* Anything with NULL value is a node. */
120 direction = (index >> n->u.n->bit_num) & 1;
121 n = &n->u.n->child[direction];
124 /* Did we find it? */
125 if (index != n->u.i) {
133 /* We deleted last node. */
136 struct node *old = parent->u.n;
137 /* Raise other node to parent. */
138 *parent = old->child[!direction];
145 void *intmap_first_(const struct intmap *map, intmap_index_t *indexp)
147 const struct intmap *n;
149 if (intmap_empty_(map)) {
155 /* Anything with NULL value is a node. */
157 n = &n->u.n->child[0];
163 void *intmap_after_(const struct intmap *map, intmap_index_t *indexp)
165 const struct intmap *n, *prev = NULL;
167 /* Special case of empty map */
168 if (intmap_empty_(map)) {
173 /* Follow down, track the last place where we could have set a bit
174 * instead of clearing it: this is the higher alternative tree. */
177 u8 direction = (*indexp >> n->u.n->bit_num) & 1;
180 n = &n->u.n->child[direction];
183 /* Found a successor? */
184 if (n->u.i > *indexp) {
190 /* Nowhere to go back up to? */
196 /* Get first one from that other branch. */
197 return intmap_first_(&prev->u.n->child[1], indexp);
200 static void clear(struct intmap n)
203 clear(n.u.n->child[0]);
204 clear(n.u.n->child[1]);
209 void intmap_clear_(struct intmap *map)
211 if (!intmap_empty_(map))