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