check_type: fix incorrect documentation.
[ccan] / ccan / strmap / strmap.c
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. */
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
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
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
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
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
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
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
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
242 void strmap_clear_(struct strmap *map)
243 {
244         if (map->u.n)
245                 clear(*map);
246         map->u.n = NULL;
247 }