1
2 #include <assert.h>
3 #include <stdint.h>
4 #include <stdlib.h>
5 #include <string.h>
6
7 typedef struct FPST {
8 struct FPST *children;
9 const char *key;
10 uint16_t idx;
11 uint16_t bitmap;
12 uint32_t val;
13 } FPST;
14
15 #define fpst_GLOBALS
16 #include "fpst.h"
17
18 #ifdef __GNUC__
19 # define popcount(X) ((unsigned int) __builtin_popcount(X))
20 # define prefetch(X) __builtin_prefetch(X)
21 #else
22 # define prefetch(X) (void)(X)
23
24 static inline unsigned int
popcount(uint32_t w)25 popcount(uint32_t w)
26 {
27 w -= (w >> 1) & 0x55555555;
28 w = (w & 0x33333333) + ((w >> 2) & 0x33333333);
29 w = (w + (w >> 4)) & 0x0f0f0f0f;
30 w = (w * 0x01010101) >> 24;
31 return w;
32 }
33 #endif
34
35 static inline unsigned char
fpst_quadbit_at(const char * str,size_t i)36 fpst_quadbit_at(const char *str, size_t i)
37 {
38 unsigned char c;
39
40 c = (unsigned char) str[i / 2];
41 if ((i & 1U) == 0U) {
42 c >>= 4;
43 }
44 return c & 0xf;
45 }
46
47 static inline int
fpst_bitmap_is_set(const FPST * t,size_t bit)48 fpst_bitmap_is_set(const FPST *t, size_t bit)
49 {
50 return (t->bitmap & (((uint16_t) 1U) << bit)) != 0U;
51 }
52
53 static inline void
fpst_bitmap_set(FPST * t,size_t bit)54 fpst_bitmap_set(FPST *t, size_t bit)
55 {
56 t->bitmap |= (((uint16_t) 1U) << bit);
57 }
58
59 static inline size_t
fpst_actual_index(const FPST * t,size_t i)60 fpst_actual_index(const FPST *t, size_t i)
61 {
62 const uint16_t b = t->bitmap & ((((uint16_t) 1U) << i) - 1U);
63
64 return (size_t) popcount((uint32_t) b);
65 }
66
67 static inline FPST *
fpst_child_get(FPST * t,size_t i)68 fpst_child_get(FPST *t, size_t i)
69 {
70 if (!fpst_bitmap_is_set(t, i)) {
71 return NULL;
72 }
73 return &t->children[fpst_actual_index(t, i)];
74 }
75
76 static int
fpst_child_set(FPST * t,FPST * v,size_t i)77 fpst_child_set(FPST *t, FPST *v, size_t i)
78 {
79 FPST *previous;
80 FPST *tmp;
81 size_t ri;
82 size_t rcount;
83 size_t count;
84
85 if ((previous = fpst_child_get(t, i)) != NULL) {
86 *previous = *v;
87 return 0;
88 }
89 count = (size_t) popcount(t->bitmap) + 1U;
90 if ((tmp = (FPST *) realloc(t->children,
91 count * (sizeof *t->children))) == NULL) {
92 return -1;
93 }
94 t->children = tmp;
95 ri = fpst_actual_index(t, i);
96 if ((rcount = count - ri - 1U) > 0U) {
97 memmove(&t->children[ri + 1U], &t->children[ri],
98 rcount * (sizeof *t->children));
99 }
100 t->children[ri] = *v;
101 fpst_bitmap_set(t, i);
102
103 return 0;
104 }
105
106 FPST *
fpst_new(void)107 fpst_new(void)
108 {
109 return NULL;
110 }
111
112 FPST *
fpst_insert(FPST * trie,const char * key,size_t len,uint32_t val)113 fpst_insert(FPST *trie, const char *key, size_t len, uint32_t val)
114 {
115 FPST *new_node_p;
116 FPST *t;
117 const char *lk;
118 FPST new_node, saved_node;
119 size_t i;
120 size_t j;
121 unsigned char c;
122 unsigned char x;
123
124 if (len >= 0x7fff) {
125 return NULL;
126 }
127 if (trie == NULL) {
128 if ((new_node_p = (FPST *) malloc(sizeof *new_node_p)) == NULL) {
129 return NULL;
130 }
131 new_node_p->key = key;
132 new_node_p->val = val;
133 new_node_p->idx = 0U;
134 new_node_p->bitmap = 0U;
135 new_node_p->children = NULL;
136
137 return new_node_p;
138 }
139 t = trie;
140 j = 0U;
141 for (;;) {
142 lk = t->key;
143 x = 0U;
144 for (; j <= len; j++) {
145 x = ((unsigned char) lk[j]) ^ ((unsigned char) key[j]);
146 if (x != 0U) {
147 break;
148 }
149 }
150 if (j > len && lk[j - 1] == 0) {
151 assert(key[j - 1] == 0);
152 t->val = val;
153 return trie;
154 }
155 i = j * 2;
156 if ((x & 0xf0) == 0U) {
157 i++;
158 }
159 if (t->bitmap == 0U) {
160 /* keep index from the new key */
161 } else if (i >= t->idx) {
162 i = t->idx;
163 j = i / 2;
164 } else {
165 saved_node = *t;
166 t->key = key;
167 t->val = val;
168 t->idx = (uint16_t) i;
169 t->bitmap = 0U;
170 t->children = NULL;
171 c = fpst_quadbit_at(lk, i);
172 if (fpst_child_set(t, &saved_node, (size_t) c) != 0) {
173 *t = saved_node;
174 return NULL;
175 }
176 return trie;
177 }
178 prefetch(t->children);
179 c = fpst_quadbit_at(key, i);
180 if (!fpst_bitmap_is_set(t, c)) {
181 break;
182 }
183 t = fpst_child_get(t, (size_t) c);
184 }
185 t->idx = (uint16_t) i;
186 assert(!fpst_bitmap_is_set(t, c));
187 new_node.key = key;
188 new_node.val = val;
189 new_node.idx = 0U;
190 new_node.bitmap = 0U;
191 new_node.children = NULL;
192 if (fpst_child_set(t, &new_node, (size_t) c) != 0) {
193 return NULL;
194 }
195 return trie;
196 }
197
198 FPST *
fpst_insert_str(FPST * trie,const char * key,uint32_t val)199 fpst_insert_str(FPST *trie, const char *key, uint32_t val)
200 {
201 return fpst_insert(trie, key, strlen(key), val);
202 }
203
204 int
fpst_starts_with_existing_key(FPST * trie,const char * str,size_t len,const char ** found_key_p,uint32_t * found_val_p)205 fpst_starts_with_existing_key(FPST *trie,
206 const char *str, size_t len,
207 const char **found_key_p,
208 uint32_t *found_val_p)
209 {
210 FPST *t;
211 const char *lk;
212 size_t i;
213 size_t j;
214 unsigned char c;
215 int ret = 0;
216
217 if (trie == NULL) {
218 return 0;
219 }
220 t = trie;
221 j = 0U;
222 for (;;) {
223 lk = t->key;
224 for (; j <= len; j++) {
225 if (lk[j] != str[j]) {
226 if (lk[j] == 0) {
227 *found_key_p = t->key;
228 *found_val_p = t->val;
229 ret = 1;
230 }
231 break;
232 }
233 }
234 if (j > len) {
235 *found_key_p = t->key;
236 *found_val_p = t->val;
237 ret = 1;
238 break;
239 }
240 if (t->bitmap == 0U) {
241 break;
242 }
243 i = t->idx;
244 if (i > len * 2) {
245 break;
246 }
247 if (j > i / 2) {
248 j = i / 2;
249 }
250 prefetch(t->children);
251 c = fpst_quadbit_at(str, i);
252 if (!fpst_bitmap_is_set(t, c)) {
253 if (fpst_bitmap_is_set(t, 0U)) {
254 c = 0U;
255 } else {
256 break;
257 }
258 }
259 t = fpst_child_get(t, (size_t) c);
260 }
261 return ret;
262 }
263
264 int
fpst_str_starts_with_existing_key(FPST * trie,const char * str,const char ** found_key_p,uint32_t * found_val_p)265 fpst_str_starts_with_existing_key(FPST *trie, const char *str,
266 const char **found_key_p,
267 uint32_t *found_val_p)
268 {
269 return fpst_starts_with_existing_key(trie, str, strlen(str),
270 found_key_p, found_val_p);
271 }
272
273 static void
fpst_free_node(FPST * t,FPST_FreeFn free_kv_fn)274 fpst_free_node(FPST *t, FPST_FreeFn free_kv_fn)
275 {
276 size_t count;
277 size_t i;
278
279 if (t->bitmap == 0U) {
280 assert(t->children == NULL);
281 }
282 count = (size_t) popcount(t->bitmap);
283 for (i = 0; i < count; i++) {
284 fpst_free_node(&t->children[i], free_kv_fn);
285 }
286 free(t->children);
287 t->bitmap = 0U;
288 t->children = NULL;
289 free_kv_fn(t->key, t->val);
290 t->key = NULL;
291 }
292
293 int
fpst_has_key(FPST * trie,const char * key,size_t len,uint32_t * found_val_p)294 fpst_has_key(FPST *trie, const char *key, size_t len, uint32_t *found_val_p)
295 {
296 const char *found_key;
297 int ret;
298
299 ret = fpst_starts_with_existing_key(trie, key, len,
300 &found_key, found_val_p);
301 if (ret > 0 && strlen(found_key) != len) {
302 ret = 0;
303 }
304 return ret;
305 }
306
307 int
fpst_has_key_str(FPST * trie,const char * key,uint32_t * found_val_p)308 fpst_has_key_str(FPST *trie, const char *key, uint32_t *found_val_p)
309 {
310 return fpst_has_key(trie, key, strlen(key), found_val_p);
311 }
312
313 void
fpst_free(FPST * trie,FPST_FreeFn free_kv_fn)314 fpst_free(FPST *trie, FPST_FreeFn free_kv_fn)
315 {
316 if (trie == NULL) {
317 return;
318 }
319 fpst_free_node(trie, free_kv_fn);
320 free(trie);
321 }
322