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