1 /*
2 * udbradtree -- radix tree for binary strings for in udb file.
3 *
4 * Copyright (c) 2011, NLnet Labs. See LICENSE for license.
5 */
6 #include "config.h"
7 #include <string.h>
8 #include <assert.h>
9 #include <stdio.h>
10 #include "udbradtree.h"
11 #include "radtree.h"
12 #define RADARRAY(ptr) ((struct udb_radarray_d*)UDB_PTR(ptr))
13
14 /** see if radarray can be reduced (by a factor of two) */
15 static int udb_radarray_reduce_if_needed(udb_base* udb, udb_ptr* n);
16
udb_radix_tree_create(udb_base * udb,udb_ptr * ptr)17 int udb_radix_tree_create(udb_base* udb, udb_ptr* ptr)
18 {
19 if(!udb_ptr_alloc_space(ptr, udb, udb_chunk_type_radtree,
20 sizeof(struct udb_radtree_d)))
21 return 0;
22 udb_rel_ptr_init(&RADTREE(ptr)->root);
23 RADTREE(ptr)->count = 0;
24 return 1;
25 }
26
27 /** size of radarray */
size_of_radarray(struct udb_radarray_d * a)28 static size_t size_of_radarray(struct udb_radarray_d* a)
29 {
30 return sizeof(struct udb_radarray_d)+((size_t)a->capacity)*(
31 sizeof(struct udb_radsel_d)+(size_t)a->str_cap);
32 }
33
34 /** size in bytes of data in the array lookup structure */
size_of_lookup(udb_ptr * node)35 static size_t size_of_lookup(udb_ptr* node)
36 {
37 assert(udb_ptr_get_type(node) == udb_chunk_type_radnode);
38 return size_of_radarray((struct udb_radarray_d*)UDB_REL(*node->base,
39 RADNODE(node)->lookup.data));
40 }
41
42 /** external variant, size in bytes of data in the array lookup structure */
size_of_lookup_ext(udb_ptr * lookup)43 size_t size_of_lookup_ext(udb_ptr* lookup)
44 {
45 return size_of_lookup(lookup);
46 }
47
48 /** size needed for a lookup array like this */
size_of_lookup_needed(uint16_t capacity,udb_radstrlen_type str_cap)49 static size_t size_of_lookup_needed(uint16_t capacity,
50 udb_radstrlen_type str_cap)
51 {
52 return sizeof(struct udb_radarray_d)+ ((size_t)capacity)*(
53 sizeof(struct udb_radsel_d)+(size_t)str_cap);
54 }
55
56 /** get the lookup array for a node */
lookup(udb_ptr * n)57 static struct udb_radarray_d* lookup(udb_ptr* n)
58 {
59 assert(udb_ptr_get_type(n) == udb_chunk_type_radnode);
60 return (struct udb_radarray_d*)UDB_REL(*n->base,
61 RADNODE(n)->lookup.data);
62 }
63
64 /** get a length in the lookup array */
lookup_len(udb_ptr * n,unsigned i)65 static udb_radstrlen_type lookup_len(udb_ptr* n, unsigned i)
66 {
67 return lookup(n)->array[i].len;
68 }
69
70 /** get a string in the lookup array */
lookup_string(udb_ptr * n,unsigned i)71 static uint8_t* lookup_string(udb_ptr* n, unsigned i)
72 {
73 return ((uint8_t*)&(lookup(n)->array[lookup(n)->capacity]))+
74 i*lookup(n)->str_cap;
75 }
76
77 /** get a node in the lookup array */
lookup_node(udb_ptr * n,unsigned i)78 static struct udb_radnode_d* lookup_node(udb_ptr* n, unsigned i)
79 {
80 return (struct udb_radnode_d*)UDB_REL(*n->base,
81 lookup(n)->array[i].node.data);
82 }
83
84 /** zero the relptrs in radarray */
udb_radarray_zero_ptrs(udb_base * udb,udb_ptr * n)85 static void udb_radarray_zero_ptrs(udb_base* udb, udb_ptr* n)
86 {
87 unsigned i;
88 for(i=0; i<lookup(n)->len; i++) {
89 udb_rptr_zero(&lookup(n)->array[i].node, udb);
90 }
91 }
92
93 /** delete a radnode */
udb_radnode_delete(udb_base * udb,udb_ptr * n)94 static void udb_radnode_delete(udb_base* udb, udb_ptr* n)
95 {
96 if(udb_ptr_is_null(n))
97 return;
98 if(RADNODE(n)->lookup.data) {
99 udb_radarray_zero_ptrs(udb, n);
100 udb_rel_ptr_free_space(&RADNODE(n)->lookup, udb,
101 size_of_lookup(n));
102 }
103 udb_rptr_zero(&RADNODE(n)->lookup, udb);
104 udb_rptr_zero(&RADNODE(n)->parent, udb);
105 udb_rptr_zero(&RADNODE(n)->elem, udb);
106 udb_ptr_free_space(n, udb, sizeof(struct udb_radnode_d));
107 }
108
109 /** delete radnodes in postorder recursion, n is ptr to node */
udb_radnode_del_postorder(udb_base * udb,udb_ptr * n)110 static void udb_radnode_del_postorder(udb_base* udb, udb_ptr* n)
111 {
112 unsigned i;
113 udb_ptr sub;
114 if(udb_ptr_is_null(n))
115 return;
116 /* clear subnodes */
117 udb_ptr_init(&sub, udb);
118 for(i=0; i<lookup(n)->len; i++) {
119 udb_ptr_set_rptr(&sub, udb, &lookup(n)->array[i].node);
120 udb_rptr_zero(&lookup(n)->array[i].node, udb);
121 udb_radnode_del_postorder(udb, &sub);
122 }
123 udb_ptr_unlink(&sub, udb);
124 /* clear lookup */
125 udb_rel_ptr_free_space(&RADNODE(n)->lookup, udb, size_of_lookup(n));
126 udb_rptr_zero(&RADNODE(n)->parent, udb);
127 udb_rptr_zero(&RADNODE(n)->elem, udb);
128 udb_ptr_free_space(n, udb, sizeof(struct udb_radnode_d));
129 }
130
udb_radix_tree_clear(udb_base * udb,udb_ptr * rt)131 void udb_radix_tree_clear(udb_base* udb, udb_ptr* rt)
132 {
133 udb_ptr root;
134 udb_ptr_new(&root, udb, &RADTREE(rt)->root);
135 udb_rptr_zero(&RADTREE(rt)->root, udb);
136 /* free the root node (and its descendants, if any) */
137 udb_radnode_del_postorder(udb, &root);
138 udb_ptr_unlink(&root, udb);
139
140 RADTREE(rt)->count = 0;
141 }
142
udb_radix_tree_delete(udb_base * udb,udb_ptr * rt)143 void udb_radix_tree_delete(udb_base* udb, udb_ptr* rt)
144 {
145 if(rt->data == 0) return;
146 assert(udb_ptr_get_type(rt) == udb_chunk_type_radtree);
147 udb_radix_tree_clear(udb, rt);
148 udb_ptr_free_space(rt, udb, sizeof(struct udb_radtree_d));
149 }
150
151 /**
152 * Find a prefix of the key, in whole-nodes.
153 * Finds the longest prefix that corresponds to a whole radnode entry.
154 * There may be a slightly longer prefix in one of the array elements.
155 * @param result: the longest prefix, the entry itself if *respos==len,
156 * otherwise an array entry, residx. Output.
157 * @param respos: pos in string where next unmatched byte is, if == len an
158 * exact match has been found. If == 0 then a "" match was found.
159 * @return false if no prefix found, not even the root "" prefix.
160 */
udb_radix_find_prefix_node(udb_base * udb,udb_ptr * rt,uint8_t * k,udb_radstrlen_type len,udb_ptr * result,udb_radstrlen_type * respos)161 static int udb_radix_find_prefix_node(udb_base* udb, udb_ptr* rt, uint8_t* k,
162 udb_radstrlen_type len, udb_ptr* result, udb_radstrlen_type* respos)
163 {
164 udb_radstrlen_type pos = 0;
165 uint8_t byte;
166 udb_ptr n;
167 udb_ptr_new(&n, udb, &RADTREE(rt)->root);
168
169 *respos = 0;
170 udb_ptr_set_ptr(result, udb, &n);
171 if(udb_ptr_is_null(&n)) {
172 udb_ptr_unlink(&n, udb);
173 return 0;
174 }
175 while(!udb_ptr_is_null(&n)) {
176 if(pos == len) {
177 break;
178 }
179 byte = k[pos];
180 if(byte < RADNODE(&n)->offset) {
181 break;
182 }
183 byte -= RADNODE(&n)->offset;
184 if(byte >= lookup(&n)->len) {
185 break;
186 }
187 pos++;
188 if(lookup(&n)->array[byte].len != 0) {
189 /* must match additional string */
190 if(pos+lookup(&n)->array[byte].len > len) {
191 break;
192 }
193 if(memcmp(&k[pos], lookup_string(&n, byte),
194 lookup(&n)->array[byte].len) != 0) {
195 break;
196 }
197 pos += lookup(&n)->array[byte].len;
198 }
199 udb_ptr_set_rptr(&n, udb, &lookup(&n)->array[byte].node);
200 if(udb_ptr_is_null(&n)) {
201 break;
202 }
203 *respos = pos;
204 udb_ptr_set_ptr(result, udb, &n);
205 }
206 udb_ptr_unlink(&n, udb);
207 return 1;
208 }
209
210 /** grow the radnode stringcapacity, copy existing elements */
udb_radnode_str_grow(udb_base * udb,udb_ptr * n,udb_radstrlen_type want)211 static int udb_radnode_str_grow(udb_base* udb, udb_ptr* n,
212 udb_radstrlen_type want)
213 {
214 unsigned ns = ((unsigned)lookup(n)->str_cap)*2;
215 unsigned i;
216 udb_ptr a;
217 if(want > ns)
218 ns = want;
219 if(ns > 65535) ns = 65535; /* MAX of udb_radstrlen_type range */
220 /* if this fails, the tree is still usable */
221 if(!udb_ptr_alloc_space(&a, udb, udb_chunk_type_radarray,
222 size_of_lookup_needed(lookup(n)->capacity, ns)))
223 return 0;
224 /* make sure to zero the newly allocated relptrs to init them */
225 memcpy(RADARRAY(&a), lookup(n), sizeof(struct udb_radarray_d));
226 RADARRAY(&a)->str_cap = ns;
227 for(i = 0; i < lookup(n)->len; i++) {
228 udb_rel_ptr_init(&RADARRAY(&a)->array[i].node);
229 udb_rptr_set_rptr(&RADARRAY(&a)->array[i].node, udb,
230 &lookup(n)->array[i].node);
231 RADARRAY(&a)->array[i].len = lookup_len(n, i);
232 memmove(((uint8_t*)(&RADARRAY(&a)->array[
233 lookup(n)->capacity]))+i*ns,
234 lookup_string(n, i), lookup(n)->str_cap);
235 }
236 udb_radarray_zero_ptrs(udb, n);
237 udb_rel_ptr_free_space(&RADNODE(n)->lookup, udb, size_of_lookup(n));
238 udb_rptr_set_ptr(&RADNODE(n)->lookup, udb, &a);
239 udb_ptr_unlink(&a, udb);
240 return 1;
241 }
242
243 /** grow the radnode array, copy existing elements to start of new array */
udb_radnode_array_grow(udb_base * udb,udb_ptr * n,size_t want)244 static int udb_radnode_array_grow(udb_base* udb, udb_ptr* n, size_t want)
245 {
246 unsigned i;
247 unsigned ns = ((unsigned)lookup(n)->capacity)*2;
248 udb_ptr a;
249 assert(want <= 256); /* cannot be more, range of uint8 */
250 if(want > ns)
251 ns = want;
252 if(ns > 256) ns = 256;
253 /* if this fails, the tree is still usable */
254 if(!udb_ptr_alloc_space(&a, udb, udb_chunk_type_radarray,
255 size_of_lookup_needed(ns, lookup(n)->str_cap)))
256 return 0;
257 /* zero the newly allocated rel ptrs to init them */
258 memset(UDB_PTR(&a), 0, size_of_lookup_needed(ns, lookup(n)->str_cap));
259 assert(lookup(n)->len <= lookup(n)->capacity);
260 assert(lookup(n)->capacity < ns);
261 memcpy(RADARRAY(&a), lookup(n), sizeof(struct udb_radarray_d));
262 RADARRAY(&a)->capacity = ns;
263 for(i=0; i<lookup(n)->len; i++) {
264 udb_rptr_set_rptr(&RADARRAY(&a)->array[i].node, udb,
265 &lookup(n)->array[i].node);
266 RADARRAY(&a)->array[i].len = lookup_len(n, i);
267 }
268 memmove(&RADARRAY(&a)->array[ns], lookup_string(n, 0),
269 ((size_t)lookup(n)->len) * ((size_t)lookup(n)->str_cap));
270 udb_radarray_zero_ptrs(udb, n);
271 udb_rel_ptr_free_space(&RADNODE(n)->lookup, udb, size_of_lookup(n));
272 udb_rptr_set_ptr(&RADNODE(n)->lookup, udb, &a);
273 udb_ptr_unlink(&a, udb);
274 return 1;
275 }
276
277 /** make empty array in radnode */
udb_radnode_array_create(udb_base * udb,udb_ptr * n)278 static int udb_radnode_array_create(udb_base* udb, udb_ptr* n)
279 {
280 /* is there an array? */
281 if(RADNODE(n)->lookup.data == 0) {
282 /* create array */
283 udb_ptr a;
284 uint16_t cap = 0;
285 udb_radstrlen_type len = 0;
286 if(!udb_ptr_alloc_space(&a, udb, udb_chunk_type_radarray,
287 size_of_lookup_needed(cap, len)))
288 return 0;
289 memset(UDB_PTR(&a), 0, size_of_lookup_needed(cap, len));
290 udb_rptr_set_ptr(&RADNODE(n)->lookup, udb, &a);
291 RADARRAY(&a)->len = cap;
292 RADARRAY(&a)->capacity = cap;
293 RADARRAY(&a)->str_cap = len;
294 RADNODE(n)->offset = 0;
295 udb_ptr_unlink(&a, udb);
296 }
297 return 1;
298 }
299
300 /** make space in radnode for another byte, or longer strings */
udb_radnode_array_space(udb_base * udb,udb_ptr * n,uint8_t byte,udb_radstrlen_type len)301 static int udb_radnode_array_space(udb_base* udb, udb_ptr* n, uint8_t byte,
302 udb_radstrlen_type len)
303 {
304 /* is there an array? */
305 if(RADNODE(n)->lookup.data == 0) {
306 /* create array */
307 udb_ptr a;
308 uint16_t cap = 1;
309 if(!udb_ptr_alloc_space(&a, udb, udb_chunk_type_radarray,
310 size_of_lookup_needed(cap, len)))
311 return 0;
312 /* this memset inits the relptr that is allocated */
313 memset(UDB_PTR(&a), 0, size_of_lookup_needed(cap, len));
314 udb_rptr_set_ptr(&RADNODE(n)->lookup, udb, &a);
315 RADARRAY(&a)->len = cap;
316 RADARRAY(&a)->capacity = cap;
317 RADARRAY(&a)->str_cap = len;
318 RADNODE(n)->offset = byte;
319 udb_ptr_unlink(&a, udb);
320 return 1;
321 }
322 if(lookup(n)->capacity == 0) {
323 if(!udb_radnode_array_grow(udb, n, 1))
324 return 0;
325 }
326
327 /* make space for this stringsize */
328 if(lookup(n)->str_cap < len) {
329 /* must resize for stringsize */
330 if(!udb_radnode_str_grow(udb, n, len))
331 return 0;
332 }
333
334 /* other cases */
335 /* is the array unused? */
336 if(lookup(n)->len == 0 && lookup(n)->capacity != 0) {
337 lookup(n)->len = 1;
338 RADNODE(n)->offset = byte;
339 memset(&lookup(n)->array[0], 0, sizeof(struct udb_radsel_d));
340 /* is it below the offset? */
341 } else if(byte < RADNODE(n)->offset) {
342 /* is capacity enough? */
343 int i;
344 unsigned need = RADNODE(n)->offset-byte;
345 if(lookup(n)->len+need > lookup(n)->capacity) {
346 /* grow array */
347 if(!udb_radnode_array_grow(udb, n, lookup(n)->len+need))
348 return 0;
349 }
350 /* take a piece of capacity into use, init the relptrs */
351 for(i = lookup(n)->len; i< (int)(lookup(n)->len + need); i++) {
352 udb_rel_ptr_init(&lookup(n)->array[i].node);
353 }
354 /* reshuffle items to end */
355 for(i = lookup(n)->len-1; i >= 0; i--) {
356 udb_rptr_set_rptr(&lookup(n)->array[need+i].node,
357 udb, &lookup(n)->array[i].node);
358 lookup(n)->array[need+i].len = lookup_len(n, i);
359 /* fixup pidx */
360 if(lookup(n)->array[i+need].node.data)
361 lookup_node(n, i+need)->pidx = i+need;
362 }
363 memmove(lookup_string(n, need), lookup_string(n, 0),
364 ((size_t)lookup(n)->len)*((size_t)lookup(n)->str_cap));
365 /* zero the first */
366 for(i = 0; i < (int)need; i++) {
367 udb_rptr_zero(&lookup(n)->array[i].node, udb);
368 lookup(n)->array[i].len = 0;
369 }
370 lookup(n)->len += need;
371 RADNODE(n)->offset = byte;
372 /* is it above the max? */
373 } else if(byte - RADNODE(n)->offset >= lookup(n)->len) {
374 /* is capacity enough? */
375 int i;
376 unsigned need = (byte-RADNODE(n)->offset) - lookup(n)->len + 1;
377 /* grow array */
378 if(lookup(n)->len + need > lookup(n)->capacity) {
379 if(!udb_radnode_array_grow(udb, n, lookup(n)->len+need))
380 return 0;
381 }
382 /* take new entries into use, init relptrs */
383 for(i = lookup(n)->len; i< (int)(lookup(n)->len + need); i++) {
384 udb_rel_ptr_init(&lookup(n)->array[i].node);
385 lookup(n)->array[i].len = 0;
386 }
387 /* grow length */
388 lookup(n)->len += need;
389 }
390 return 1;
391 }
392
393 /** make space for string size */
udb_radnode_str_space(udb_base * udb,udb_ptr * n,udb_radstrlen_type len)394 static int udb_radnode_str_space(udb_base* udb, udb_ptr* n,
395 udb_radstrlen_type len)
396 {
397 if(RADNODE(n)->lookup.data == 0) {
398 return udb_radnode_array_space(udb, n, 0, len);
399 }
400 if(lookup(n)->str_cap < len) {
401 /* must resize for stringsize */
402 if(!udb_radnode_str_grow(udb, n, len))
403 return 0;
404 }
405 return 1;
406 }
407
408 /** copy remainder from prefixes for a split:
409 * plen: len prefix, l: longer bstring, llen: length of l. */
udb_radsel_prefix_remainder(udb_radstrlen_type plen,uint8_t * l,udb_radstrlen_type llen,uint8_t * s,udb_radstrlen_type * slen)410 static void udb_radsel_prefix_remainder(udb_radstrlen_type plen,
411 uint8_t* l, udb_radstrlen_type llen,
412 uint8_t* s, udb_radstrlen_type* slen)
413 {
414 *slen = llen - plen;
415 /* assert(*slen <= lookup(n)->str_cap); */
416 memmove(s, l+plen, llen-plen);
417 }
418
419 /** create a prefix in the array strs */
udb_radsel_str_create(uint8_t * s,udb_radstrlen_type * slen,uint8_t * k,udb_radstrlen_type pos,udb_radstrlen_type len)420 static void udb_radsel_str_create(uint8_t* s, udb_radstrlen_type* slen,
421 uint8_t* k, udb_radstrlen_type pos, udb_radstrlen_type len)
422 {
423 *slen = len-pos;
424 /* assert(*slen <= lookup(n)->str_cap); */
425 memmove(s, k+pos, len-pos);
426 }
427
428 static udb_radstrlen_type
udb_bstr_common(uint8_t * x,udb_radstrlen_type xlen,uint8_t * y,udb_radstrlen_type ylen)429 udb_bstr_common(uint8_t* x, udb_radstrlen_type xlen,
430 uint8_t* y, udb_radstrlen_type ylen)
431 {
432 assert(sizeof(radstrlen_type) == sizeof(udb_radstrlen_type));
433 return bstr_common_ext(x, xlen, y, ylen);
434 }
435
436 static int
udb_bstr_is_prefix(uint8_t * p,udb_radstrlen_type plen,uint8_t * x,udb_radstrlen_type xlen)437 udb_bstr_is_prefix(uint8_t* p, udb_radstrlen_type plen,
438 uint8_t* x, udb_radstrlen_type xlen)
439 {
440 assert(sizeof(radstrlen_type) == sizeof(udb_radstrlen_type));
441 return bstr_is_prefix_ext(p, plen, x, xlen);
442 }
443
444 /** grow array space for byte N after a string, (but if string shorter) */
445 static int
udb_radnode_array_space_strremain(udb_base * udb,udb_ptr * n,uint8_t * str,udb_radstrlen_type len,udb_radstrlen_type pos)446 udb_radnode_array_space_strremain(udb_base* udb, udb_ptr* n,
447 uint8_t* str, udb_radstrlen_type len, udb_radstrlen_type pos)
448 {
449 assert(pos < len);
450 /* shift by one char because it goes in lookup array */
451 return udb_radnode_array_space(udb, n, str[pos], len-(pos+1));
452 }
453
454
455 /** radsel create a split when two nodes have shared prefix.
456 * @param udb: udb
457 * @param n: node with the radsel that gets changed, it contains a node.
458 * @param idx: the index of the radsel that gets changed.
459 * @param k: key byte string
460 * @param pos: position where the string enters the radsel (e.g. r.str)
461 * @param len: length of k.
462 * @param add: additional node for the string k.
463 * removed by called on failure.
464 * @return false on alloc failure, no changes made.
465 */
udb_radsel_split(udb_base * udb,udb_ptr * n,uint8_t idx,uint8_t * k,udb_radstrlen_type pos,udb_radstrlen_type len,udb_ptr * add)466 static int udb_radsel_split(udb_base* udb, udb_ptr* n, uint8_t idx, uint8_t* k,
467 udb_radstrlen_type pos, udb_radstrlen_type len, udb_ptr* add)
468 {
469 uint8_t* addstr = k+pos;
470 udb_radstrlen_type addlen = len-pos;
471 if(udb_bstr_is_prefix(addstr, addlen, lookup_string(n, idx),
472 lookup_len(n, idx))) {
473 udb_radstrlen_type split_len = 0;
474 /* 'add' is a prefix of r.node */
475 /* also for empty addstr */
476 /* set it up so that the 'add' node has r.node as child */
477 /* so, r.node gets moved below the 'add' node, but we do
478 * this so that the r.node stays the same pointer for its
479 * key name */
480 assert(addlen != lookup_len(n, idx));
481 assert(addlen < lookup_len(n, idx));
482 /* make space for new string sizes */
483 if(!udb_radnode_str_space(udb, n, addlen))
484 return 0;
485 if(lookup_len(n, idx) - addlen > 1)
486 /* shift one because a char is in the lookup array */
487 split_len = lookup_len(n, idx) - (addlen+1);
488 if(!udb_radnode_array_space(udb, add,
489 lookup_string(n, idx)[addlen], split_len))
490 return 0;
491 /* alloc succeeded, now link it in */
492 udb_rptr_set_rptr(&RADNODE(add)->parent, udb,
493 &lookup_node(n, idx)->parent);
494 RADNODE(add)->pidx = lookup_node(n, idx)->pidx;
495 udb_rptr_set_rptr(&lookup(add)->array[0].node, udb,
496 &lookup(n)->array[idx].node);
497 if(lookup_len(n, idx) - addlen > 1) {
498 udb_radsel_prefix_remainder(addlen+1,
499 lookup_string(n, idx), lookup_len(n, idx),
500 lookup_string(add, 0),
501 &lookup(add)->array[0].len);
502 } else {
503 lookup(add)->array[0].len = 0;
504 }
505 udb_rptr_set_ptr(&lookup_node(n, idx)->parent, udb, add);
506 lookup_node(n, idx)->pidx = 0;
507
508 udb_rptr_set_ptr(&lookup(n)->array[idx].node, udb, add);
509 memmove(lookup_string(n, idx), addstr, addlen);
510 lookup(n)->array[idx].len = addlen;
511 /* n's string may have become shorter */
512 if(!udb_radarray_reduce_if_needed(udb, n)) {
513 /* ignore this, our tree has become inefficient */
514 }
515 } else if(udb_bstr_is_prefix(lookup_string(n, idx), lookup_len(n, idx),
516 addstr, addlen)) {
517 udb_radstrlen_type split_len = 0;
518 udb_ptr rnode;
519 /* r.node is a prefix of 'add' */
520 /* set it up so that the 'r.node' has 'add' as child */
521 /* and basically, r.node is already completely fine,
522 * we only need to create a node as its child */
523 assert(addlen != lookup_len(n, idx));
524 assert(lookup_len(n, idx) < addlen);
525 udb_ptr_new(&rnode, udb, &lookup(n)->array[idx].node);
526 /* make space for string length */
527 if(addlen-lookup_len(n, idx) > 1) {
528 /* shift one because a character goes into array */
529 split_len = addlen - (lookup_len(n, idx)+1);
530 }
531 if(!udb_radnode_array_space(udb, &rnode,
532 addstr[lookup_len(n, idx)], split_len)) {
533 udb_ptr_unlink(&rnode, udb);
534 return 0;
535 }
536 /* alloc succeeded, now link it in */
537 udb_rptr_set_ptr(&RADNODE(add)->parent, udb, &rnode);
538 RADNODE(add)->pidx = addstr[lookup_len(n, idx)] -
539 RADNODE(&rnode)->offset;
540 udb_rptr_set_ptr(&lookup(&rnode)->array[ RADNODE(add)->pidx ]
541 .node, udb, add);
542 if(addlen-lookup_len(n, idx) > 1) {
543 udb_radsel_prefix_remainder(lookup_len(n, idx)+1,
544 addstr, addlen,
545 lookup_string(&rnode, RADNODE(add)->pidx),
546 &lookup(&rnode)->array[ RADNODE(add)->pidx]
547 .len);
548 } else {
549 lookup(&rnode)->array[ RADNODE(add)->pidx].len = 0;
550 }
551 /* rnode's string has become shorter */
552 if(!udb_radarray_reduce_if_needed(udb, &rnode)) {
553 /* ignore this, our tree has become inefficient */
554 }
555 udb_ptr_unlink(&rnode, udb);
556 } else {
557 /* okay we need to create a new node that chooses between
558 * the nodes 'add' and r.node
559 * We do this so that r.node stays the same pointer for its
560 * key name. */
561 udb_ptr com, rnode;
562 udb_radstrlen_type common_len = udb_bstr_common(
563 lookup_string(n, idx), lookup_len(n, idx),
564 addstr, addlen);
565 assert(common_len < lookup_len(n, idx));
566 assert(common_len < addlen);
567 udb_ptr_new(&rnode, udb, &lookup(n)->array[idx].node);
568
569 /* create the new node for choice */
570 if(!udb_ptr_alloc_space(&com, udb, udb_chunk_type_radnode,
571 sizeof(struct udb_radnode_d))) {
572 udb_ptr_unlink(&rnode, udb);
573 return 0; /* out of space */
574 }
575 memset(UDB_PTR(&com), 0, sizeof(struct udb_radnode_d));
576 /* make stringspace for the two substring choices */
577 /* this allocates the com->lookup array */
578 if(!udb_radnode_array_space_strremain(udb, &com,
579 lookup_string(n, idx), lookup_len(n, idx), common_len)
580 || !udb_radnode_array_space_strremain(udb, &com,
581 addstr, addlen, common_len)) {
582 udb_ptr_unlink(&rnode, udb);
583 udb_radnode_delete(udb, &com);
584 return 0;
585 }
586 /* create stringspace for the shared prefix */
587 if(common_len > 0) {
588 if(!udb_radnode_str_space(udb, n, common_len-1)) {
589 udb_ptr_unlink(&rnode, udb);
590 udb_radnode_delete(udb, &com);
591 return 0;
592 }
593 }
594 /* allocs succeeded, proceed to link it all up */
595 udb_rptr_set_rptr(&RADNODE(&com)->parent, udb,
596 &RADNODE(&rnode)->parent);
597 RADNODE(&com)->pidx = RADNODE(&rnode)->pidx;
598 udb_rptr_set_ptr(&RADNODE(&rnode)->parent, udb, &com);
599 RADNODE(&rnode)->pidx = lookup_string(n, idx)[common_len] -
600 RADNODE(&com)->offset;
601 udb_rptr_set_ptr(&RADNODE(add)->parent, udb, &com);
602 RADNODE(add)->pidx = addstr[common_len] -
603 RADNODE(&com)->offset;
604 udb_rptr_set_ptr(&lookup(&com)->array[RADNODE(&rnode)->pidx]
605 .node, udb, &rnode);
606 if(lookup_len(n, idx)-common_len > 1) {
607 udb_radsel_prefix_remainder(common_len+1,
608 lookup_string(n, idx), lookup_len(n, idx),
609 lookup_string(&com, RADNODE(&rnode)->pidx),
610 &lookup(&com)->array[RADNODE(&rnode)->pidx].len);
611 } else {
612 lookup(&com)->array[RADNODE(&rnode)->pidx].len= 0;
613 }
614 udb_rptr_set_ptr(&lookup(&com)->array[RADNODE(add)->pidx]
615 .node, udb, add);
616 if(addlen-common_len > 1) {
617 udb_radsel_prefix_remainder(common_len+1,
618 addstr, addlen,
619 lookup_string(&com, RADNODE(add)->pidx),
620 &lookup(&com)->array[RADNODE(add)->pidx].len);
621 } else {
622 lookup(&com)->array[RADNODE(add)->pidx].len = 0;
623 }
624 memmove(lookup_string(n, idx), addstr, common_len);
625 lookup(n)->array[idx].len = common_len;
626 udb_rptr_set_ptr(&lookup(n)->array[idx].node, udb, &com);
627 udb_ptr_unlink(&rnode, udb);
628 udb_ptr_unlink(&com, udb);
629 /* n's string has become shorter */
630 if(!udb_radarray_reduce_if_needed(udb, n)) {
631 /* ignore this, our tree has become inefficient */
632 }
633 }
634 return 1;
635 }
636
637 uint64_t* result_data = NULL;
udb_radix_insert(udb_base * udb,udb_ptr * rt,uint8_t * k,udb_radstrlen_type len,udb_ptr * elem,udb_ptr * result)638 udb_void udb_radix_insert(udb_base* udb, udb_ptr* rt, uint8_t* k,
639 udb_radstrlen_type len, udb_ptr* elem, udb_ptr* result)
640 {
641 udb_void ret;
642 udb_ptr add, n; /* type udb_radnode_d */
643 udb_radstrlen_type pos = 0;
644 /* create new element to add */
645 if(!udb_ptr_alloc_space(&add, udb, udb_chunk_type_radnode,
646 sizeof(struct udb_radnode_d))) {
647 return 0; /* alloc failure */
648 }
649 memset(UDB_PTR(&add), 0, sizeof(struct udb_radnode_d));
650 udb_rptr_set_ptr(&RADNODE(&add)->elem, udb, elem);
651 if(!udb_radnode_array_create(udb, &add)) {
652 udb_ptr_free_space(&add, udb, sizeof(struct udb_radnode_d));
653 return 0; /* alloc failure */
654 }
655 udb_ptr_init(&n, udb);
656 result_data = &n.data;
657
658 /* find out where to add it */
659 if(!udb_radix_find_prefix_node(udb, rt, k, len, &n, &pos)) {
660 /* new root */
661 assert(RADTREE(rt)->root.data == 0);
662 if(len == 0) {
663 udb_rptr_set_ptr(&RADTREE(rt)->root, udb, &add);
664 } else {
665 /* add a root to point to new node */
666 udb_ptr_zero(&n, udb);
667 if(!udb_ptr_alloc_space(&n, udb,
668 udb_chunk_type_radnode,
669 sizeof(struct udb_radnode_d))) {
670 udb_radnode_delete(udb, &add);
671 udb_ptr_unlink(&n, udb);
672 return 0; /* alloc failure */
673 }
674 memset(RADNODE(&n), 0, sizeof(struct udb_radnode_d));
675 /* this creates the array lookup structure for n */
676 if(!udb_radnode_array_space(udb, &n, k[0], len-1)) {
677 udb_radnode_delete(udb, &add);
678 udb_ptr_free_space(&n, udb,
679 sizeof(struct udb_radnode_d));
680 return 0; /* alloc failure */
681 }
682 udb_rptr_set_ptr(&RADNODE(&add)->parent, udb, &n);
683 RADNODE(&add)->pidx = 0;
684 udb_rptr_set_ptr(&lookup(&n)->array[0].node, udb, &add);
685 if(len > 1) {
686 udb_radsel_prefix_remainder(1, k, len,
687 lookup_string(&n, 0),
688 &lookup(&n)->array[0].len);
689 }
690 udb_rptr_set_ptr(&RADTREE(rt)->root, udb, &n);
691 }
692 } else if(pos == len) {
693 /* found an exact match */
694 if(RADNODE(&n)->elem.data) {
695 /* already exists, failure */
696 udb_radnode_delete(udb, &add);
697 udb_ptr_unlink(&n, udb);
698 return 0;
699 }
700 udb_rptr_set_ptr(&RADNODE(&n)->elem, udb, elem);
701 udb_radnode_delete(udb, &add);
702 udb_ptr_set_ptr(&add, udb, &n);
703 } else {
704 /* n is a node which can accomodate */
705 uint8_t byte;
706 assert(pos < len);
707 byte = k[pos];
708
709 /* see if it falls outside of array */
710 if(byte < RADNODE(&n)->offset || byte-RADNODE(&n)->offset >=
711 lookup(&n)->len) {
712 /* make space in the array for it; adjusts offset */
713 if(!udb_radnode_array_space(udb, &n, byte,
714 len-(pos+1))) {
715 udb_radnode_delete(udb, &add);
716 udb_ptr_unlink(&n, udb);
717 return 0;
718 }
719 assert(byte>=RADNODE(&n)->offset && byte-RADNODE(&n)->
720 offset<lookup(&n)->len);
721 byte -= RADNODE(&n)->offset;
722 /* see if more prefix needs to be split off */
723 if(pos+1 < len) {
724 udb_radsel_str_create(lookup_string(&n, byte),
725 &lookup(&n)->array[byte].len,
726 k, pos+1, len);
727 }
728 /* insert the new node in the new bucket */
729 udb_rptr_set_ptr(&RADNODE(&add)->parent, udb, &n);
730 RADNODE(&add)->pidx = byte;
731 udb_rptr_set_ptr(&lookup(&n)->array[byte].node, udb,
732 &add);
733 /* so a bucket exists and byte falls in it */
734 } else if(lookup(&n)->array[byte - RADNODE(&n)->offset]
735 .node.data == 0) {
736 /* use existing bucket */
737 byte -= RADNODE(&n)->offset;
738 if(pos+1 < len) {
739 /* make space and split off more prefix */
740 if(!udb_radnode_str_space(udb, &n,
741 len-(pos+1))) {
742 udb_radnode_delete(udb, &add);
743 udb_ptr_unlink(&n, udb);
744 return 0;
745 }
746 udb_radsel_str_create(lookup_string(&n, byte),
747 &lookup(&n)->array[byte].len,
748 k, pos+1, len);
749 }
750 /* insert the new node in the new bucket */
751 udb_rptr_set_ptr(&RADNODE(&add)->parent, udb, &n);
752 RADNODE(&add)->pidx = byte;
753 udb_rptr_set_ptr(&lookup(&n)->array[byte].node, udb,
754 &add);
755 } else {
756 /* use bucket but it has a shared prefix,
757 * split that out and create a new intermediate
758 * node to split out between the two.
759 * One of the two might exactmatch the new
760 * intermediate node */
761 if(!udb_radsel_split(udb, &n, byte-RADNODE(&n)->offset,
762 k, pos+1, len, &add)) {
763 udb_radnode_delete(udb, &add);
764 udb_ptr_unlink(&n, udb);
765 return 0;
766 }
767 }
768 }
769 RADTREE(rt)->count ++;
770 ret = add.data;
771 udb_ptr_init(result, udb);
772 udb_ptr_set_ptr(result, udb, &add);
773 udb_ptr_unlink(&add, udb);
774 udb_ptr_unlink(&n, udb);
775 return ret;
776 }
777
778 /** Cleanup node with one child, it is removed and joined into parent[x] str */
779 static int
udb_radnode_cleanup_onechild(udb_base * udb,udb_ptr * n)780 udb_radnode_cleanup_onechild(udb_base* udb, udb_ptr* n)
781 {
782 udb_ptr par, child;
783 uint8_t pidx = RADNODE(n)->pidx;
784 radstrlen_type joinlen;
785 udb_ptr_new(&par, udb, &RADNODE(n)->parent);
786 udb_ptr_new(&child, udb, &lookup(n)->array[0].node);
787
788 /* node had one child, merge them into the parent. */
789 /* keep the child node, so its pointers stay valid. */
790
791 /* at parent, append child->str to array str */
792 assert(pidx < lookup(&par)->len);
793 joinlen = lookup_len(&par, pidx) + lookup_len(n, 0) + 1;
794 /* make stringspace for the joined string */
795 if(!udb_radnode_str_space(udb, &par, joinlen)) {
796 /* cleanup failed due to out of memory */
797 /* the tree is inefficient, with node n still existing */
798 udb_ptr_unlink(&par, udb);
799 udb_ptr_unlink(&child, udb);
800 udb_ptr_zero(n, udb);
801 return 0;
802 }
803 /* the string(par, pidx) is already there */
804 /* the array lookup is gone, put its character in the lookup string*/
805 lookup_string(&par, pidx)[lookup_len(&par, pidx)] =
806 RADNODE(&child)->pidx + RADNODE(n)->offset;
807 memmove(lookup_string(&par, pidx)+lookup_len(&par, pidx)+1,
808 lookup_string(n, 0), lookup_len(n, 0));
809 lookup(&par)->array[pidx].len = joinlen;
810 /* and set the node to our child. */
811 udb_rptr_set_ptr(&lookup(&par)->array[pidx].node, udb, &child);
812 udb_rptr_set_ptr(&RADNODE(&child)->parent, udb, &par);
813 RADNODE(&child)->pidx = pidx;
814 /* we are unlinked, delete our node */
815 udb_radnode_delete(udb, n);
816 udb_ptr_unlink(&par, udb);
817 udb_ptr_unlink(&child, udb);
818 udb_ptr_zero(n, udb);
819 return 1;
820 }
821
822 /** reduce the size of radarray, does a malloc */
823 static int
udb_radarray_reduce(udb_base * udb,udb_ptr * n,uint16_t cap,udb_radstrlen_type strcap)824 udb_radarray_reduce(udb_base* udb, udb_ptr* n, uint16_t cap,
825 udb_radstrlen_type strcap)
826 {
827 udb_ptr a;
828 unsigned i;
829 assert(lookup(n)->len <= cap);
830 assert(cap <= lookup(n)->capacity);
831 assert(strcap <= lookup(n)->str_cap);
832 if(!udb_ptr_alloc_space(&a, udb, udb_chunk_type_radarray,
833 size_of_lookup_needed(cap, strcap)))
834 return 0;
835 memset(RADARRAY(&a), 0, size_of_lookup_needed(cap, strcap));
836 memcpy(RADARRAY(&a), lookup(n), sizeof(struct udb_radarray_d));
837 RADARRAY(&a)->capacity = cap;
838 RADARRAY(&a)->str_cap = strcap;
839 for(i=0; i<lookup(n)->len; i++) {
840 udb_rel_ptr_init(&RADARRAY(&a)->array[i].node);
841 udb_rptr_set_rptr(&RADARRAY(&a)->array[i].node, udb,
842 &lookup(n)->array[i].node);
843 RADARRAY(&a)->array[i].len = lookup_len(n, i);
844 memmove(((uint8_t*)(&RADARRAY(&a)->array[cap]))+i*strcap,
845 lookup_string(n, i), lookup_len(n, i));
846 }
847 udb_radarray_zero_ptrs(udb, n);
848 udb_rel_ptr_free_space(&RADNODE(n)->lookup, udb, size_of_lookup(n));
849 udb_rptr_set_ptr(&RADNODE(n)->lookup, udb, &a);
850 udb_ptr_unlink(&a, udb);
851 return 1;
852 }
853
854 /** find the max stringlength in the array */
udb_radarray_max_len(udb_ptr * n)855 static udb_radstrlen_type udb_radarray_max_len(udb_ptr* n)
856 {
857 unsigned i;
858 udb_radstrlen_type maxlen = 0;
859 for(i=0; i<lookup(n)->len; i++) {
860 if(lookup(n)->array[i].node.data &&
861 lookup(n)->array[i].len > maxlen)
862 maxlen = lookup(n)->array[i].len;
863 }
864 return maxlen;
865 }
866
867 /** see if radarray can be reduced (by a factor of two) */
868 static int
udb_radarray_reduce_if_needed(udb_base * udb,udb_ptr * n)869 udb_radarray_reduce_if_needed(udb_base* udb, udb_ptr* n)
870 {
871 udb_radstrlen_type maxlen = udb_radarray_max_len(n);
872 if((lookup(n)->len <= lookup(n)->capacity/2 || lookup(n)->len == 0
873 || maxlen <= lookup(n)->str_cap/2 || maxlen == 0) &&
874 (lookup(n)->len != lookup(n)->capacity ||
875 lookup(n)->str_cap != maxlen))
876 return udb_radarray_reduce(udb, n, lookup(n)->len, maxlen);
877 return 1;
878 }
879
880 static int
udb_radnode_array_clean_all(udb_base * udb,udb_ptr * n)881 udb_radnode_array_clean_all(udb_base* udb, udb_ptr* n)
882 {
883 RADNODE(n)->offset = 0;
884 lookup(n)->len = 0;
885 /* reallocate lookup to a smaller capacity structure */
886 return udb_radarray_reduce(udb, n, 0, 0);
887 }
888
889 /** remove NULL nodes from front of array */
890 static int
udb_radnode_array_clean_front(udb_base * udb,udb_ptr * n)891 udb_radnode_array_clean_front(udb_base* udb, udb_ptr* n)
892 {
893 /* move them up and adjust offset */
894 unsigned idx, shuf = 0;
895 /* remove until a nonNULL entry */
896 while(shuf < lookup(n)->len && lookup(n)->array[shuf].node.data == 0)
897 shuf++;
898 if(shuf == 0)
899 return 1;
900 if(shuf == lookup(n)->len) {
901 /* the array is empty, the tree is inefficient */
902 return udb_radnode_array_clean_all(udb, n);
903 }
904 assert(shuf < lookup(n)->len);
905 assert((int)shuf <= 255-(int)RADNODE(n)->offset);
906 /* move them */
907 for(idx=0; idx<lookup(n)->len-shuf; idx++) {
908 udb_rptr_set_rptr(&lookup(n)->array[idx].node, udb,
909 &lookup(n)->array[shuf+idx].node);
910 lookup(n)->array[idx].len = lookup_len(n, shuf+idx);
911 memmove(lookup_string(n, idx), lookup_string(n, shuf+idx),
912 lookup(n)->array[idx].len);
913 }
914 /* zero the to-be-unused entries */
915 for(idx=lookup(n)->len-shuf; idx<lookup(n)->len; idx++) {
916 udb_rptr_zero(&lookup(n)->array[idx].node, udb);
917 memset(lookup_string(n, idx), 0, lookup(n)->array[idx].len);
918 lookup(n)->array[idx].len = 0;
919 }
920 RADNODE(n)->offset += shuf;
921 lookup(n)->len -= shuf;
922 for(idx=0; idx<lookup(n)->len; idx++)
923 if(lookup(n)->array[idx].node.data)
924 lookup_node(n, idx)->pidx = idx;
925
926 /* see if capacity has to shrink */
927 return udb_radarray_reduce_if_needed(udb, n);
928 }
929
930 /** remove NULL nodes from end of array */
931 static int
udb_radnode_array_clean_end(udb_base * udb,udb_ptr * n)932 udb_radnode_array_clean_end(udb_base* udb, udb_ptr* n)
933 {
934 /* shorten it */
935 unsigned shuf = 0;
936 /* remove until a nonNULL entry */
937 /* remove until a nonNULL entry */
938 while(shuf < lookup(n)->len && lookup(n)->array[lookup(n)->len-1-shuf]
939 .node.data == 0)
940 shuf++;
941 if(shuf == 0)
942 return 1;
943 if(shuf == lookup(n)->len) {
944 /* the array is empty, the tree is inefficient */
945 return udb_radnode_array_clean_all(udb, n);
946 }
947 assert(shuf < lookup(n)->len);
948 lookup(n)->len -= shuf;
949 /* array elements can stay where they are */
950 /* see if capacity has to shrink */
951 return udb_radarray_reduce_if_needed(udb, n);
952 }
953
954 /** clean up radnode leaf, where we know it has a parent */
955 static int
udb_radnode_cleanup_leaf(udb_base * udb,udb_ptr * n,udb_ptr * par)956 udb_radnode_cleanup_leaf(udb_base* udb, udb_ptr* n, udb_ptr* par)
957 {
958 uint8_t pidx;
959 /* node was a leaf */
960
961 /* delete leaf node, but store parent+idx */
962 pidx = RADNODE(n)->pidx;
963 assert(pidx < lookup(par)->len);
964
965 /** set parent ptr to this node to NULL before deleting the node,
966 * because otherwise ptrlinks fail */
967 udb_rptr_zero(&lookup(par)->array[pidx].node, udb);
968
969 udb_radnode_delete(udb, n);
970
971 /* set parent+idx entry to NULL str and node.*/
972 lookup(par)->array[pidx].len = 0;
973
974 /* see if par offset or len must be adjusted */
975 if(lookup(par)->len == 1) {
976 /* removed final element from array */
977 if(!udb_radnode_array_clean_all(udb, par))
978 return 0;
979 } else if(pidx == 0) {
980 /* removed first element from array */
981 if(!udb_radnode_array_clean_front(udb, par))
982 return 0;
983 } else if(pidx == lookup(par)->len-1) {
984 /* removed last element from array */
985 if(!udb_radnode_array_clean_end(udb, par))
986 return 0;
987 }
988 return 1;
989 }
990
991 /**
992 * Cleanup a radix node that was made smaller, see if it can
993 * be merged with others.
994 * @param udb: the udb
995 * @param rt: tree to remove root if needed.
996 * @param n: node to cleanup
997 * @return false on alloc failure.
998 */
999 static int
udb_radnode_cleanup(udb_base * udb,udb_ptr * rt,udb_ptr * n)1000 udb_radnode_cleanup(udb_base* udb, udb_ptr* rt, udb_ptr* n)
1001 {
1002 while(!udb_ptr_is_null(n)) {
1003 if(RADNODE(n)->elem.data) {
1004 /* see if if needs to be reduced in stringsize */
1005 if(!udb_radarray_reduce_if_needed(udb, n)) {
1006 udb_ptr_zero(n, udb);
1007 return 0;
1008 }
1009 /* cannot delete node with a data element */
1010 udb_ptr_zero(n, udb);
1011 return 1;
1012 } else if(lookup(n)->len == 1 && RADNODE(n)->parent.data) {
1013 return udb_radnode_cleanup_onechild(udb, n);
1014 } else if(lookup(n)->len == 0) {
1015 udb_ptr par;
1016 if(!RADNODE(n)->parent.data) {
1017 /* root deleted */
1018 udb_rptr_zero(&RADTREE(rt)->root, udb);
1019 udb_radnode_delete(udb, n);
1020 return 1;
1021 }
1022 udb_ptr_new(&par, udb, &RADNODE(n)->parent);
1023 /* remove and delete the leaf node */
1024 if(!udb_radnode_cleanup_leaf(udb, n, &par)) {
1025 udb_ptr_unlink(&par, udb);
1026 udb_ptr_zero(n, udb);
1027 return 0;
1028 }
1029 /* see if parent can now be cleaned up */
1030 udb_ptr_set_ptr(n, udb, &par);
1031 udb_ptr_unlink(&par, udb);
1032 } else {
1033 /* see if if needs to be reduced in stringsize */
1034 if(!udb_radarray_reduce_if_needed(udb, n)) {
1035 udb_ptr_zero(n, udb);
1036 return 0;
1037 }
1038 /* node cannot be cleaned up */
1039 udb_ptr_zero(n, udb);
1040 return 1;
1041 }
1042 }
1043 /* ENOTREACH */
1044 return 1;
1045 }
1046
udb_radix_delete(udb_base * udb,udb_ptr * rt,udb_ptr * n)1047 void udb_radix_delete(udb_base* udb, udb_ptr* rt, udb_ptr* n)
1048 {
1049 if(udb_ptr_is_null(n))
1050 return;
1051 udb_rptr_zero(&RADNODE(n)->elem, udb);
1052 RADTREE(rt)->count --;
1053 if(!udb_radnode_cleanup(udb, rt, n)) {
1054 /* out of memory in cleanup. the elem ptr is NULL, but
1055 * the radix tree could be inefficient. */
1056 }
1057 }
1058
udb_radix_search(udb_ptr * rt,uint8_t * k,udb_radstrlen_type len)1059 udb_void udb_radix_search(udb_ptr* rt, uint8_t* k, udb_radstrlen_type len)
1060 {
1061 /* since we only perform reads, and no udb_mallocs or udb_frees
1062 * we know the pointers stay the same */
1063 struct udb_radnode_d* n;
1064 udb_radstrlen_type pos = 0;
1065 uint8_t byte;
1066 void* base = *rt->base;
1067
1068 n = (struct udb_radnode_d*)UDB_REL(base, RADTREE(rt)->root.data);
1069 #define NARRAY(n) ((struct udb_radarray_d*)UDB_REL(base, n->lookup.data))
1070 #define NSTR(n, byte) (((uint8_t*)(&NARRAY(n)->array[NARRAY(n)->capacity]))+byte*NARRAY(n)->str_cap)
1071 while(n != *rt->base) {
1072 if(pos == len)
1073 return UDB_SYSTOREL(*rt->base, n);
1074 byte = k[pos];
1075 if(byte < n->offset)
1076 return 0;
1077 byte -= n->offset;
1078 if(byte >= NARRAY(n)->len)
1079 return 0;
1080 pos++;
1081 if(NARRAY(n)->array[byte].len != 0) {
1082 /* must match additional string */
1083 if(pos+NARRAY(n)->array[byte].len > len)
1084 return 0; /* no match */
1085 if(memcmp(&k[pos], NSTR(n, byte),
1086 NARRAY(n)->array[byte].len) != 0)
1087 return 0; /* no match */
1088 pos += NARRAY(n)->array[byte].len;
1089 }
1090 n = (struct udb_radnode_d*)UDB_REL(base,
1091 NARRAY(n)->array[byte].node.data);
1092 }
1093 return 0;
1094 }
1095
1096 /** go to last elem-containing node in this subtree (excl self) */
1097 static void
udb_radnode_last_in_subtree(udb_base * udb,udb_ptr * n)1098 udb_radnode_last_in_subtree(udb_base* udb, udb_ptr* n)
1099 {
1100 int idx;
1101 /* try last entry in array first */
1102 for(idx=((int)lookup(n)->len)-1; idx >= 0; idx--) {
1103 if(lookup(n)->array[idx].node.data) {
1104 udb_ptr s;
1105 udb_ptr_init(&s, udb);
1106 udb_ptr_set_rptr(&s, udb, &lookup(n)->array[idx].node);
1107 /* does it have entries in its subtrees? */
1108 if(lookup(&s)->len > 0) {
1109 udb_radnode_last_in_subtree(udb, &s);
1110 if(!udb_ptr_is_null(&s)) {
1111 udb_ptr_set_ptr(n, udb, &s);
1112 udb_ptr_unlink(&s, udb);
1113 return;
1114 }
1115 }
1116 udb_ptr_set_rptr(&s, udb, &lookup(n)->array[idx].node);
1117 /* no, does it have an entry itself? */
1118 if(RADNODE(&s)->elem.data) {
1119 udb_ptr_set_ptr(n, udb, &s);
1120 udb_ptr_unlink(&s, udb);
1121 return;
1122 }
1123 udb_ptr_unlink(&s, udb);
1124 }
1125 }
1126 udb_ptr_zero(n, udb);
1127 }
1128
1129 /** last in subtree, incl self */
1130 static void
udb_radnode_last_in_subtree_incl_self(udb_base * udb,udb_ptr * n)1131 udb_radnode_last_in_subtree_incl_self(udb_base* udb, udb_ptr* n)
1132 {
1133 udb_ptr self;
1134 udb_ptr_init(&self, udb);
1135 udb_ptr_set_ptr(&self, udb, n);
1136 udb_radnode_last_in_subtree(udb, n);
1137 if(!udb_ptr_is_null(n)) {
1138 udb_ptr_unlink(&self, udb);
1139 return;
1140 }
1141 if(RADNODE(&self)->elem.data) {
1142 udb_ptr_set_ptr(n, udb, &self);
1143 udb_ptr_unlink(&self, udb);
1144 return;
1145 }
1146 udb_ptr_zero(n, udb);
1147 udb_ptr_unlink(&self, udb);
1148 }
1149
1150 /** return first elem-containing node in this subtree (excl self) */
1151 static void
udb_radnode_first_in_subtree(udb_base * udb,udb_ptr * n)1152 udb_radnode_first_in_subtree(udb_base* udb, udb_ptr* n)
1153 {
1154 unsigned idx;
1155 /* try every subnode */
1156 for(idx=0; idx<lookup(n)->len; idx++) {
1157 if(lookup(n)->array[idx].node.data) {
1158 udb_ptr s;
1159 udb_ptr_init(&s, udb);
1160 udb_ptr_set_rptr(&s, udb, &lookup(n)->array[idx].node);
1161 /* does it have elem itself? */
1162 if(RADNODE(&s)->elem.data) {
1163 udb_ptr_set_ptr(n, udb, &s);
1164 udb_ptr_unlink(&s, udb);
1165 return;
1166 }
1167 /* try its subtrees */
1168 udb_radnode_first_in_subtree(udb, &s);
1169 if(!udb_ptr_is_null(&s)) {
1170 udb_ptr_set_ptr(n, udb, &s);
1171 udb_ptr_unlink(&s, udb);
1172 return;
1173 }
1174
1175 }
1176 }
1177 udb_ptr_zero(n, udb);
1178 }
1179
1180 /** Find an entry in arrays from idx-1 to 0 */
1181 static void
udb_radnode_find_prev_from_idx(udb_base * udb,udb_ptr * n,unsigned from)1182 udb_radnode_find_prev_from_idx(udb_base* udb, udb_ptr* n, unsigned from)
1183 {
1184 unsigned idx = from;
1185 while(idx > 0) {
1186 idx --;
1187 if(lookup(n)->array[idx].node.data) {
1188 udb_ptr_set_rptr(n, udb, &lookup(n)->array[idx].node);
1189 udb_radnode_last_in_subtree_incl_self(udb, n);
1190 if(!udb_ptr_is_null(n))
1191 return;
1192 }
1193 }
1194 udb_ptr_zero(n, udb);
1195 }
1196
1197 /** return self or a previous element */
udb_ret_self_or_prev(udb_base * udb,udb_ptr * n,udb_ptr * result)1198 static int udb_ret_self_or_prev(udb_base* udb, udb_ptr* n, udb_ptr* result)
1199 {
1200 if(RADNODE(n)->elem.data) {
1201 udb_ptr_set_ptr(result, udb, n);
1202 } else {
1203 udb_ptr_set_ptr(result, udb, n);
1204 udb_radix_prev(udb, result);
1205 }
1206 udb_ptr_unlink(n, udb);
1207 return 0;
1208 }
1209
1210
udb_radix_find_less_equal(udb_base * udb,udb_ptr * rt,uint8_t * k,udb_radstrlen_type len,udb_ptr * result)1211 int udb_radix_find_less_equal(udb_base* udb, udb_ptr* rt, uint8_t* k,
1212 udb_radstrlen_type len, udb_ptr* result)
1213 {
1214 udb_ptr n;
1215 udb_radstrlen_type pos = 0;
1216 uint8_t byte;
1217 int r;
1218 /* set result to NULL */
1219 udb_ptr_init(result, udb);
1220 if(RADTREE(rt)->count == 0) {
1221 /* empty tree */
1222 return 0;
1223 }
1224 udb_ptr_new(&n, udb, &RADTREE(rt)->root);
1225 while(pos < len) {
1226 byte = k[pos];
1227 if(byte < RADNODE(&n)->offset) {
1228 /* so the previous is the element itself */
1229 /* or something before this element */
1230 return udb_ret_self_or_prev(udb, &n, result);
1231 }
1232 byte -= RADNODE(&n)->offset;
1233 if(byte >= lookup(&n)->len) {
1234 /* so, the previous is the last of array, or itself */
1235 /* or something before this element */
1236 udb_ptr_set_ptr(result, udb, &n);
1237 udb_radnode_last_in_subtree_incl_self(udb, result);
1238 if(udb_ptr_is_null(result)) {
1239 udb_ptr_set_ptr(result, udb, &n);
1240 udb_radix_prev(udb, result);
1241 }
1242 goto done_fail;
1243 }
1244 pos++;
1245 if(!lookup(&n)->array[byte].node.data) {
1246 /* no match */
1247 /* Find an entry in arrays from byte-1 to 0 */
1248 udb_ptr_set_ptr(result, udb, &n);
1249 udb_radnode_find_prev_from_idx(udb, result, byte);
1250 if(!udb_ptr_is_null(result))
1251 goto done_fail;
1252 /* this entry or something before it */
1253 udb_ptr_zero(result, udb);
1254 return udb_ret_self_or_prev(udb, &n, result);
1255 }
1256 if(lookup_len(&n, byte) != 0) {
1257 /* must match additional string */
1258 if(pos+lookup_len(&n, byte) > len) {
1259 /* the additional string is longer than key*/
1260 if( (memcmp(&k[pos], lookup_string(&n, byte),
1261 len-pos)) <= 0) {
1262 /* and the key is before this node */
1263 udb_ptr_set_rptr(result, udb,
1264 &lookup(&n)->array[byte].node);
1265 udb_radix_prev(udb, result);
1266 } else {
1267 /* the key is after the additional
1268 * string, thus everything in that
1269 * subtree is smaller. */
1270 udb_ptr_set_rptr(result, udb,
1271 &lookup(&n)->array[byte].node);
1272 udb_radnode_last_in_subtree_incl_self(udb, result);
1273 /* if somehow that is NULL,
1274 * then we have an inefficient tree:
1275 * byte+1 is larger than us, so find
1276 * something in byte-1 and before */
1277 if(udb_ptr_is_null(result)) {
1278 udb_ptr_set_rptr(result, udb,
1279 &lookup(&n)->array[byte].node);
1280 udb_radix_prev(udb, result);
1281 }
1282 }
1283 goto done_fail; /* no match */
1284 }
1285 if( (r=memcmp(&k[pos], lookup_string(&n, byte),
1286 lookup_len(&n, byte))) < 0) {
1287 udb_ptr_set_rptr(result, udb,
1288 &lookup(&n)->array[byte].node);
1289 udb_radix_prev(udb, result);
1290 goto done_fail; /* no match */
1291 } else if(r > 0) {
1292 /* the key is larger than the additional
1293 * string, thus everything in that subtree
1294 * is smaller */
1295 udb_ptr_set_rptr(result, udb,
1296 &lookup(&n)->array[byte].node);
1297 udb_radnode_last_in_subtree_incl_self(udb, result);
1298 /* if we have an inefficient tree */
1299 if(udb_ptr_is_null(result)) {
1300 udb_ptr_set_rptr(result, udb,
1301 &lookup(&n)->array[byte].node);
1302 udb_radix_prev(udb, result);
1303 }
1304 goto done_fail; /* no match */
1305 }
1306 pos += lookup_len(&n, byte);
1307 }
1308 udb_ptr_set_rptr(&n, udb, &lookup(&n)->array[byte].node);
1309 }
1310 if(RADNODE(&n)->elem.data) {
1311 /* exact match */
1312 udb_ptr_set_ptr(result, udb, &n);
1313 udb_ptr_unlink(&n, udb);
1314 return 1;
1315 }
1316 /* there is a node which is an exact match, but it has no element */
1317 udb_ptr_set_ptr(result, udb, &n);
1318 udb_radix_prev(udb, result);
1319 done_fail:
1320 udb_ptr_unlink(&n, udb);
1321 return 0;
1322 }
1323
udb_radix_first(udb_base * udb,udb_ptr * rt,udb_ptr * p)1324 void udb_radix_first(udb_base* udb, udb_ptr* rt, udb_ptr* p)
1325 {
1326 udb_ptr_init(p, udb);
1327 if(!rt || udb_ptr_is_null(rt) || RADTREE(rt)->count == 0)
1328 return;
1329 udb_ptr_set_rptr(p, udb, &RADTREE(rt)->root);
1330 if(RADNODE(p)->elem.data)
1331 return;
1332 udb_radix_next(udb, p);
1333 }
1334
udb_radix_last(udb_base * udb,udb_ptr * rt,udb_ptr * p)1335 void udb_radix_last(udb_base* udb, udb_ptr* rt, udb_ptr* p)
1336 {
1337 udb_ptr_init(p, udb);
1338 if(!rt || udb_ptr_is_null(rt) || RADTREE(rt)->count == 0)
1339 return;
1340 udb_ptr_set_rptr(p, udb, &RADTREE(rt)->root);
1341 udb_radnode_last_in_subtree_incl_self(udb, p);
1342 }
1343
udb_radix_next(udb_base * udb,udb_ptr * n)1344 void udb_radix_next(udb_base* udb, udb_ptr* n)
1345 {
1346 udb_ptr s;
1347 udb_ptr_init(&s, udb);
1348 if(lookup(n)->len) {
1349 /* go down */
1350 udb_ptr_set_ptr(&s, udb, n);
1351 udb_radnode_first_in_subtree(udb, &s);
1352 if(!udb_ptr_is_null(&s)) {
1353 udb_ptr_set_ptr(n, udb, &s);
1354 udb_ptr_unlink(&s, udb);
1355 return;
1356 }
1357 }
1358 /* go up - the parent->elem is not useful, because it is before us */
1359 while(RADNODE(n)->parent.data) {
1360 unsigned idx = RADNODE(n)->pidx;
1361 udb_ptr_set_rptr(n, udb, &RADNODE(n)->parent);
1362 idx++;
1363 for(; idx < lookup(n)->len; idx++) {
1364 /* go down the next branch */
1365 if(lookup(n)->array[idx].node.data) {
1366 udb_ptr_set_rptr(&s, udb,
1367 &lookup(n)->array[idx].node);
1368 /* node itself */
1369 if(RADNODE(&s)->elem.data) {
1370 udb_ptr_set_ptr(n, udb, &s);
1371 udb_ptr_unlink(&s, udb);
1372 return;
1373 }
1374 /* or subtree */
1375 udb_radnode_first_in_subtree(udb, &s);
1376 if(!udb_ptr_is_null(&s)) {
1377 udb_ptr_set_ptr(n, udb, &s);
1378 udb_ptr_unlink(&s, udb);
1379 return;
1380 }
1381 }
1382 }
1383 }
1384 udb_ptr_unlink(&s, udb);
1385 udb_ptr_zero(n, udb);
1386 }
1387
udb_radix_prev(udb_base * udb,udb_ptr * n)1388 void udb_radix_prev(udb_base* udb, udb_ptr* n)
1389 {
1390 /* must go up, since all array nodes are after this node */
1391 while(RADNODE(n)->parent.data) {
1392 uint8_t idx = RADNODE(n)->pidx;
1393 udb_ptr s;
1394 udb_ptr_set_rptr(n, udb, &RADNODE(n)->parent);
1395 assert(lookup(n)->len > 0); /* since we are a child */
1396 /* see if there are elements in previous branches there */
1397 udb_ptr_init(&s, udb);
1398 udb_ptr_set_ptr(&s, udb, n);
1399 udb_radnode_find_prev_from_idx(udb, &s, idx);
1400 if(!udb_ptr_is_null(&s)) {
1401 udb_ptr_set_ptr(n, udb, &s);
1402 udb_ptr_unlink(&s, udb);
1403 return;
1404 }
1405 udb_ptr_unlink(&s, udb);
1406 /* the current node is before the array */
1407 if(RADNODE(n)->elem.data)
1408 return;
1409 }
1410 udb_ptr_zero(n, udb);
1411 }
1412
udb_radname_insert(udb_base * udb,udb_ptr * rt,const uint8_t * dname,size_t dlen,udb_ptr * elem,udb_ptr * result)1413 udb_void udb_radname_insert(udb_base* udb, udb_ptr* rt, const uint8_t* dname,
1414 size_t dlen, udb_ptr* elem, udb_ptr* result)
1415 {
1416 uint8_t k[300];
1417 radstrlen_type klen = (radstrlen_type)sizeof(k);
1418 radname_d2r(k, &klen, dname, dlen);
1419 return udb_radix_insert(udb, rt, k, klen, elem, result);
1420 }
1421
udb_radname_search(udb_base * udb,udb_ptr * rt,const uint8_t * dname,size_t dlen,udb_ptr * result)1422 int udb_radname_search(udb_base* udb, udb_ptr* rt, const uint8_t* dname,
1423 size_t dlen, udb_ptr* result)
1424 {
1425 udb_void r;
1426 uint8_t k[300];
1427 radstrlen_type klen = (radstrlen_type)sizeof(k);
1428 radname_d2r(k, &klen, dname, dlen);
1429 r = udb_radix_search(rt, k, klen);
1430 udb_ptr_init(result, udb);
1431 udb_ptr_set(result, udb, r);
1432 return (r != 0);
1433 }
1434
udb_radix_tree_walk_chunk(void * base,void * d,uint64_t s,udb_walk_relptr_cb * cb,void * arg)1435 void udb_radix_tree_walk_chunk(void* base, void* d, uint64_t s,
1436 udb_walk_relptr_cb* cb, void* arg)
1437 {
1438 struct udb_radtree_d* p = (struct udb_radtree_d*)d;
1439 assert(s >= sizeof(struct udb_radtree_d));
1440 (void)s;
1441 (*cb)(base, &p->root, arg);
1442 }
1443
udb_radix_node_walk_chunk(void * base,void * d,uint64_t s,udb_walk_relptr_cb * cb,void * arg)1444 void udb_radix_node_walk_chunk(void* base, void* d, uint64_t s,
1445 udb_walk_relptr_cb* cb, void* arg)
1446 {
1447 struct udb_radnode_d* p = (struct udb_radnode_d*)d;
1448 assert(s >= sizeof(struct udb_radnode_d));
1449 (void)s;
1450 (*cb)(base, &p->elem, arg);
1451 (*cb)(base, &p->parent, arg);
1452 (*cb)(base, &p->lookup, arg);
1453 }
1454
udb_radix_array_walk_chunk(void * base,void * d,uint64_t s,udb_walk_relptr_cb * cb,void * arg)1455 void udb_radix_array_walk_chunk(void* base, void* d, uint64_t s,
1456 udb_walk_relptr_cb* cb, void* arg)
1457 {
1458 struct udb_radarray_d* p = (struct udb_radarray_d*)d;
1459 unsigned i;
1460 assert(s >= sizeof(struct udb_radarray_d)+
1461 p->capacity*(sizeof(struct udb_radsel_d)+p->str_cap));
1462 (void)s;
1463 for(i=0; i<p->len; i++) {
1464 (*cb)(base, &p->array[i].node, arg);
1465 }
1466 }
1467