1 /* This code is based on ccan/strset.c. */
2 #include <ccan/strmap/strmap.h>
3 #include <ccan/short_types/short_types.h>
4 #include <ccan/str/str.h>
5 #include <ccan/ilog/ilog.h>
11 /* These point to strings or nodes. */
12 struct strmap child[2];
13 /* The byte number where first bit differs. */
15 /* The bit where these children differ. */
19 /* Closest member to this in a non-empty map. */
20 static struct strmap *closest(struct strmap *n, const char *member, size_t len)
22 const u8 *bytes = (const u8 *)member;
24 /* Anything with NULL value is a node. */
28 if (n->u.n->byte_num < len) {
29 u8 c = bytes[n->u.n->byte_num];
30 direction = (c >> n->u.n->bit_num) & 1;
32 n = &n->u.n->child[direction];
37 void *strmap_getn_(const struct strmap *map,
38 const char *member, size_t memberlen)
44 n = closest((struct strmap *)map, member, memberlen);
45 if (!strncmp(member, n->u.s, memberlen) && !n->u.s[memberlen])
52 void *strmap_get_(const struct strmap *map, const char *member)
54 return strmap_getn_(map, member, strlen(member));
57 bool strmap_add_(struct strmap *map, const char *member, const void *value)
59 size_t len = strlen(member);
60 const u8 *bytes = (const u8 *)member;
71 map->v = (void *)value;
75 /* Find closest existing member. */
76 n = closest(map, member, len);
78 /* Find where they differ. */
79 for (byte_num = 0; n->u.s[byte_num] == member[byte_num]; byte_num++) {
80 if (member[byte_num] == '\0') {
87 /* Find which bit differs (if we had ilog8, we'd use it) */
88 bit_num = ilog32_nz((u8)n->u.s[byte_num] ^ bytes[byte_num]) - 1;
89 assert(bit_num < CHAR_BIT);
91 /* Which direction do we go at this bit? */
92 new_dir = ((bytes[byte_num]) >> bit_num) & 1;
94 /* Allocate new node. */
95 newn = malloc(sizeof(*newn));
100 newn->byte_num = byte_num;
101 newn->bit_num = bit_num;
102 newn->child[new_dir].v = (void *)value;
103 newn->child[new_dir].u.s = member;
105 /* Find where to insert: not closest, but first which differs! */
110 if (n->u.n->byte_num > byte_num)
112 /* Subtle: bit numbers are "backwards" for comparison */
113 if (n->u.n->byte_num == byte_num && n->u.n->bit_num < bit_num)
116 if (n->u.n->byte_num < len) {
117 u8 c = bytes[n->u.n->byte_num];
118 direction = (c >> n->u.n->bit_num) & 1;
120 n = &n->u.n->child[direction];
123 newn->child[!new_dir] = *n;
129 char *strmap_del_(struct strmap *map, const char *member, void **valuep)
131 size_t len = strlen(member);
132 const u8 *bytes = (const u8 *)member;
133 struct strmap *parent = NULL, *n;
134 const char *ret = NULL;
135 u8 direction = 0; /* prevent bogus gcc warning. */
143 /* Find closest, but keep track of parent. */
145 /* Anything with NULL value is a node. */
150 if (n->u.n->byte_num < len) {
151 c = bytes[n->u.n->byte_num];
152 direction = (c >> n->u.n->bit_num) & 1;
155 n = &n->u.n->child[direction];
158 /* Did we find it? */
159 if (!streq(member, n->u.s)) {
169 /* We deleted last node. */
172 struct node *old = parent->u.n;
173 /* Raise other node to parent. */
174 *parent = old->child[!direction];
181 static bool iterate(struct strmap n,
182 bool (*handle)(const char *, void *, void *),
186 return handle(n.u.s, n.v, (void *)data);
188 return iterate(n.u.n->child[0], handle, data)
189 && iterate(n.u.n->child[1], handle, data);
192 void strmap_iterate_(const struct strmap *map,
193 bool (*handle)(const char *, void *, void *),
200 iterate(*map, handle, data);
203 const struct strmap *strmap_prefix_(const struct strmap *map,
206 const struct strmap *n, *top;
207 size_t len = strlen(prefix);
208 const u8 *bytes = (const u8 *)prefix;
210 /* Empty map -> return empty map. */
216 /* We walk to find the top, but keep going to check prefix matches. */
220 if (n->u.n->byte_num < len)
221 c = bytes[n->u.n->byte_num];
223 direction = (c >> n->u.n->bit_num) & 1;
224 n = &n->u.n->child[direction];
229 if (!strstarts(n->u.s, prefix)) {
230 /* Convenient return for prefixes which do not appear in map. */
231 static const struct strmap empty_map;
238 static void clear(struct strmap n)
241 clear(n.u.n->child[0]);
242 clear(n.u.n->child[1]);
247 void strmap_clear_(struct strmap *map)