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>
6 #include <assert.h>
7 #include <stdlib.h>
8 #include <errno.h>
9
10 struct node {
11 /* These point to strings or nodes. */
12 struct strmap child[2];
13 /* The byte number where first bit differs. */
14 size_t byte_num;
15 /* The bit where these children differ. */
16 u8 bit_num;
17 };
18
19 /* Closest member to this in a non-empty map. */
closest(struct strmap * n,const char * member)20 static struct strmap *closest(struct strmap *n, const char *member)
21 {
22 size_t len = strlen(member);
23 const u8 *bytes = (const u8 *)member;
24
25 /* Anything with NULL value is a node. */
26 while (!n->v) {
27 u8 direction = 0;
28
29 if (n->u.n->byte_num < len) {
30 u8 c = bytes[n->u.n->byte_num];
31 direction = (c >> n->u.n->bit_num) & 1;
32 }
33 n = &n->u.n->child[direction];
34 }
35 return n;
36 }
37
strmap_get_(const struct strmap * map,const char * member)38 void *strmap_get_(const struct strmap *map, const char *member)
39 {
40 struct strmap *n;
41
42 /* Not empty map? */
43 if (map->u.n) {
44 n = closest((struct strmap *)map, member);
45 if (streq(member, n->u.s))
46 return n->v;
47 }
48 errno = ENOENT;
49 return NULL;
50 }
51
strmap_add_(struct strmap * map,const char * member,const void * value)52 bool strmap_add_(struct strmap *map, const char *member, const void *value)
53 {
54 size_t len = strlen(member);
55 const u8 *bytes = (const u8 *)member;
56 struct strmap *n;
57 struct node *newn;
58 size_t byte_num;
59 u8 bit_num, new_dir;
60
61 assert(value);
62
63 /* Empty map? */
64 if (!map->u.n) {
65 map->u.s = member;
66 map->v = (void *)value;
67 return true;
68 }
69
70 /* Find closest existing member. */
71 n = closest(map, member);
72
73 /* Find where they differ. */
74 for (byte_num = 0; n->u.s[byte_num] == member[byte_num]; byte_num++) {
75 if (member[byte_num] == '\0') {
76 /* All identical! */
77 errno = EEXIST;
78 return false;
79 }
80 }
81
82 /* Find which bit differs (if we had ilog8, we'd use it) */
83 bit_num = ilog32_nz((u8)n->u.s[byte_num] ^ bytes[byte_num]) - 1;
84 assert(bit_num < CHAR_BIT);
85
86 /* Which direction do we go at this bit? */
87 new_dir = ((bytes[byte_num]) >> bit_num) & 1;
88
89 /* Allocate new node. */
90 newn = malloc(sizeof(*newn));
91 if (!newn) {
92 errno = ENOMEM;
93 return false;
94 }
95 newn->byte_num = byte_num;
96 newn->bit_num = bit_num;
97 newn->child[new_dir].v = (void *)value;
98 newn->child[new_dir].u.s = member;
99
100 /* Find where to insert: not closest, but first which differs! */
101 n = map;
102 while (!n->v) {
103 u8 direction = 0;
104
105 if (n->u.n->byte_num > byte_num)
106 break;
107 /* Subtle: bit numbers are "backwards" for comparison */
108 if (n->u.n->byte_num == byte_num && n->u.n->bit_num < bit_num)
109 break;
110
111 if (n->u.n->byte_num < len) {
112 u8 c = bytes[n->u.n->byte_num];
113 direction = (c >> n->u.n->bit_num) & 1;
114 }
115 n = &n->u.n->child[direction];
116 }
117
118 newn->child[!new_dir] = *n;
119 n->u.n = newn;
120 n->v = NULL;
121 return true;
122 }
123
strmap_del_(struct strmap * map,const char * member,void ** valuep)124 char *strmap_del_(struct strmap *map, const char *member, void **valuep)
125 {
126 size_t len = strlen(member);
127 const u8 *bytes = (const u8 *)member;
128 struct strmap *parent = NULL, *n;
129 const char *ret = NULL;
130 u8 direction = 0; /* prevent bogus gcc warning. */
131
132 /* Empty map? */
133 if (!map->u.n) {
134 errno = ENOENT;
135 return NULL;
136 }
137
138 /* Find closest, but keep track of parent. */
139 n = map;
140 /* Anything with NULL value is a node. */
141 while (!n->v) {
142 u8 c = 0;
143
144 parent = n;
145 if (n->u.n->byte_num < len) {
146 c = bytes[n->u.n->byte_num];
147 direction = (c >> n->u.n->bit_num) & 1;
148 } else
149 direction = 0;
150 n = &n->u.n->child[direction];
151 }
152
153 /* Did we find it? */
154 if (!streq(member, n->u.s)) {
155 errno = ENOENT;
156 return NULL;
157 }
158
159 ret = n->u.s;
160 if (valuep)
161 *valuep = n->v;
162
163 if (!parent) {
164 /* We deleted last node. */
165 map->u.n = NULL;
166 } else {
167 struct node *old = parent->u.n;
168 /* Raise other node to parent. */
169 *parent = old->child[!direction];
170 free(old);
171 }
172
173 return (char *)ret;
174 }
175
iterate(struct strmap n,bool (* handle)(const char *,void *,void *),const void * data)176 static bool iterate(struct strmap n,
177 bool (*handle)(const char *, void *, void *),
178 const void *data)
179 {
180 if (n.v)
181 return handle(n.u.s, n.v, (void *)data);
182
183 return iterate(n.u.n->child[0], handle, data)
184 && iterate(n.u.n->child[1], handle, data);
185 }
186
strmap_iterate_(const struct strmap * map,bool (* handle)(const char *,void *,void *),const void * data)187 void strmap_iterate_(const struct strmap *map,
188 bool (*handle)(const char *, void *, void *),
189 const void *data)
190 {
191 /* Empty map? */
192 if (!map->u.n)
193 return;
194
195 iterate(*map, handle, data);
196 }
197
strmap_prefix_(const struct strmap * map,const char * prefix)198 const struct strmap *strmap_prefix_(const struct strmap *map,
199 const char *prefix)
200 {
201 const struct strmap *n, *top;
202 size_t len = strlen(prefix);
203 const u8 *bytes = (const u8 *)prefix;
204
205 /* Empty map -> return empty map. */
206 if (!map->u.n)
207 return map;
208
209 top = n = map;
210
211 /* We walk to find the top, but keep going to check prefix matches. */
212 while (!n->v) {
213 u8 c = 0, direction;
214
215 if (n->u.n->byte_num < len)
216 c = bytes[n->u.n->byte_num];
217
218 direction = (c >> n->u.n->bit_num) & 1;
219 n = &n->u.n->child[direction];
220 if (c)
221 top = n;
222 }
223
224 if (!strstarts(n->u.s, prefix)) {
225 /* Convenient return for prefixes which do not appear in map. */
226 static const struct strmap empty_map;
227 return &empty_map;
228 }
229
230 return top;
231 }
232
clear(struct strmap n)233 static void clear(struct strmap n)
234 {
235 if (!n.v) {
236 clear(n.u.n->child[0]);
237 clear(n.u.n->child[1]);
238 free(n.u.n);
239 }
240 }
241
strmap_clear_(struct strmap * map)242 void strmap_clear_(struct strmap *map)
243 {
244 if (map->u.n)
245 clear(*map);
246 map->u.n = NULL;
247 }
248