Bug Summary

File:src/usr.sbin/nsd/radtree.c
Warning:line 405, column 7
3rd function call argument is an uninitialized value

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name radtree.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 1 -pic-is-pie -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -target-feature +retpoline-indirect-calls -target-feature +retpoline-indirect-branches -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/usr.sbin/nsd/obj -resource-dir /usr/local/lib/clang/13.0.0 -I . -I /usr/src/usr.sbin/nsd -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -fdebug-compilation-dir=/usr/src/usr.sbin/nsd/obj -ferror-limit 19 -fwrapv -D_RET_PROTECTOR -ret-protector -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c /usr/src/usr.sbin/nsd/radtree.c
1/*
2 * radtree -- generic radix tree for binary strings.
3 *
4 * Copyright (c) 2010, NLnet Labs. See LICENSE for license.
5 */
6#include "config.h"
7#include <assert.h>
8#include <stdlib.h>
9#include <string.h>
10#include <unistd.h>
11#include <time.h>
12#include "radtree.h"
13#include "util.h"
14#include "region-allocator.h"
15
16#include <stdio.h>
17#include <ctype.h>
18
19struct radtree* radix_tree_create(struct region* region)
20{
21 struct radtree* rt = (struct radtree*)region_alloc(region, sizeof(*rt));
22 if(!rt) return NULL((void*)0);
23 rt->region = region;
24 radix_tree_init(rt);
25 return rt;
26}
27
28void radix_tree_init(struct radtree* rt)
29{
30 rt->root = NULL((void*)0);
31 rt->count = 0;
32}
33
34/** delete radnodes in postorder recursion */
35static void radnode_del_postorder(struct region* region, struct radnode* n)
36{
37 unsigned i;
38 if(!n) return;
39 for(i=0; i<n->len; i++) {
40 radnode_del_postorder(region, n->array[i].node);
41 region_recycle(region, n->array[i].str, n->array[i].len);
42 }
43 region_recycle(region, n->array, n->capacity*sizeof(struct radsel));
44 region_recycle(region, n, sizeof(*n));
45}
46
47void radix_tree_clear(struct radtree* rt)
48{
49 radnode_del_postorder(rt->region, rt->root);
50 rt->root = NULL((void*)0);
51 rt->count = 0;
52}
53
54void radix_tree_delete(struct radtree* rt)
55{
56 if(!rt) return;
57 radix_tree_clear(rt);
58 region_recycle(rt->region, rt, sizeof(*rt));
59}
60
61/** return last elem-containing node in this subtree (excl self) */
62static struct radnode*
63radnode_last_in_subtree(struct radnode* n)
64{
65 int idx;
66 /* try last entry in array first */
67 for(idx=((int)n->len)-1; idx >= 0; idx--) {
68 if(n->array[idx].node) {
69 /* does it have entries in its subtrees? */
70 if(n->array[idx].node->len > 0) {
71 struct radnode* s = radnode_last_in_subtree(
72 n->array[idx].node);
73 if(s) return s;
74 }
75 /* no, does it have an entry itself? */
76 if(n->array[idx].node->elem)
77 return n->array[idx].node;
78 }
79 }
80 return NULL((void*)0);
81}
82
83/** last in subtree, incl self */
84static struct radnode*
85radnode_last_in_subtree_incl_self(struct radnode* n)
86{
87 struct radnode* s = radnode_last_in_subtree(n);
88 if(s) return s;
89 if(n->elem) return n;
90 return NULL((void*)0);
91}
92
93/** return first elem-containing node in this subtree (excl self) */
94static struct radnode*
95radnode_first_in_subtree(struct radnode* n)
96{
97 unsigned idx;
98 struct radnode* s;
99 /* try every subnode */
100 for(idx=0; idx<n->len; idx++) {
101 if(n->array[idx].node) {
102 /* does it have elem itself? */
103 if(n->array[idx].node->elem)
104 return n->array[idx].node;
105 /* try its subtrees */
106 if((s=radnode_first_in_subtree(n->array[idx].node))!=0)
107 return s;
108 }
109 }
110 return NULL((void*)0);
111}
112
113/** Find an entry in arrays from idx-1 to 0 */
114static struct radnode*
115radnode_find_prev_from_idx(struct radnode* n, unsigned from)
116{
117 unsigned idx = from;
118 while(idx > 0) {
119 idx --;
120 if(n->array[idx].node) {
121 struct radnode* s = radnode_last_in_subtree_incl_self(
122 n->array[idx].node);
123 if(s) return s;
124 }
125 }
126 return NULL((void*)0);
127}
128
129/**
130 * Find a prefix of the key, in whole-nodes.
131 * Finds the longest prefix that corresponds to a whole radnode entry.
132 * There may be a slightly longer prefix in one of the array elements.
133 * @param result: the longest prefix, the entry itself if *respos==len,
134 * otherwise an array entry, residx.
135 * @param respos: pos in string where next unmatched byte is, if == len an
136 * exact match has been found. If == 0 then a "" match was found.
137 * @return false if no prefix found, not even the root "" prefix.
138 */
139static int radix_find_prefix_node(struct radtree* rt, uint8_t* k,
140 radstrlen_type len, struct radnode** result, radstrlen_type* respos)
141{
142 struct radnode* n = rt->root;
143 radstrlen_type pos = 0;
144 uint8_t byte;
145 *respos = 0;
146 *result = n;
147 if(!n) return 0;
27
←
Assuming 'n' is non-null
→
28
←
Taking false branch
→
148 while(n) {
29
←
Loop condition is true. Entering loop body
→
149 if(pos
29.1
'pos' is not equal to 'len'
 == len) {
30
←
Taking false branch
→
150 return 1;
151 }
152 byte = k[pos];
153 if(byte < n->offset) {
31
←
Assuming 'byte' is >= field 'offset'
→
32
←
Taking false branch
→
154 return 1;
155 }
156 byte -= n->offset;
157 if(byte >= n->len) {
33
←
Assuming 'byte' is < field 'len'
→
34
←
Taking false branch
→
158 return 1;
159 }
160 pos++;
161 if(n->array[byte].len != 0) {
35
←
Assuming field 'len' is not equal to 0
→
36
←
Taking true branch
→
162 /* must match additional string */
163 if(pos+n->array[byte].len > len) {
37
←
Assuming the condition is false
→
38
←
Taking false branch
→
164 return 1;
165 }
166 if(memcmp(&k[pos], n->array[byte].str,
39
←
Assuming the condition is true
→
40
←
Taking true branch
→
167 n->array[byte].len) != 0) {
168 return 1;
169 }
170 pos += n->array[byte].len;
171 }
172 n = n->array[byte].node;
173 if(!n) return 1;
174 *respos = pos;
175 *result = n;
176 }
177 /* cannot reach because of returns when !n above */
178 /* ENOTREACH */
179 return 1;
180}
181
182/** grow array to at least the given size, offset unchanged */
183static int
184radnode_array_grow(struct region* region, struct radnode* n, unsigned want)
185{
186 unsigned ns = ((unsigned)n->capacity)*2;
187 struct radsel* a;
188 assert(want <= 256)((void)0); /* cannot be more, range of uint8 */
189 if(want > ns)
190 ns = want;
191 if(ns > 256) ns = 256;
192 /* we do not use realloc, because we want to keep the old array
193 * in case alloc fails, so that the tree is still usable */
194 a = (struct radsel*)region_alloc_array(region, ns, sizeof(struct radsel));
195 if(!a) return 0;
196 assert(n->len <= n->capacity)((void)0);
197 assert(n->capacity < ns)((void)0);
198 memcpy(&a[0], &n->array[0], n->len*sizeof(struct radsel));
199 region_recycle(region, n->array, n->capacity*sizeof(struct radsel));
200 n->array = a;
201 n->capacity = ns;
202 return 1;
203}
204
205/** make space in radnode array for another byte */
206static int
207radnode_array_space(struct region* region, struct radnode* n, uint8_t byte)
208{
209 /* is there an array? */
210 if(!n->array || n->capacity == 0) {
211 n->array = (struct radsel*)region_alloc(region,
212 sizeof(struct radsel));
213 if(!n->array) return 0;
214 memset(&n->array[0], 0, sizeof(struct radsel));
215 n->len = 1;
216 n->capacity = 1;
217 n->offset = byte;
218 /* is the array unused? */
219 } else if(n->len == 0 && n->capacity != 0) {
220 n->len = 1;
221 n->offset = byte;
222 memset(&n->array[0], 0, sizeof(struct radsel));
223 /* is it below the offset? */
224 } else if(byte < n->offset) {
225 /* is capacity enough? */
226 unsigned idx;
227 unsigned need = n->offset-byte;
228 if(n->len+need > n->capacity) {
229 /* grow array */
230 if(!radnode_array_grow(region, n, n->len+need))
231 return 0;
232 }
233 /* reshuffle items to end */
234 memmove(&n->array[need], &n->array[0],
235 n->len*sizeof(struct radsel));
236 /* fixup pidx */
237 for(idx = 0; idx < n->len; idx++) {
238 if(n->array[idx+need].node)
239 n->array[idx+need].node->pidx = idx+need;
240 }
241 /* zero the first */
242 memset(&n->array[0], 0, need*sizeof(struct radsel));
243 n->len += need;
244 n->offset = byte;
245 /* is it above the max? */
246 } else if(byte-n->offset >= n->len) {
247 /* is capacity enough? */
248 unsigned need = (byte-n->offset) - n->len + 1;
249 /* grow array */
250 if(n->len + need > n->capacity) {
251 if(!radnode_array_grow(region, n, n->len+need))
252 return 0;
253 }
254 /* zero added entries */
255 memset(&n->array[n->len], 0, need*sizeof(struct radsel));
256 /* grow length */
257 n->len += need;
258 }
259 return 1;
260}
261
262/** create a prefix in the array strs */
263static int
264radsel_str_create(struct region* region, struct radsel* r, uint8_t* k,
265 radstrlen_type pos, radstrlen_type len)
266{
267 r->str = (uint8_t*)region_alloc(region, sizeof(uint8_t)*(len-pos));
268 if(!r->str)
269 return 0; /* out of memory */
270 memmove(r->str, k+pos, len-pos);
271 r->len = len-pos;
272 return 1;
273}
274
275/** see if one byte string p is a prefix of another x (equality is true) */
276static int
277bstr_is_prefix(uint8_t* p, radstrlen_type plen, uint8_t* x,
278 radstrlen_type xlen)
279{
280 /* if plen is zero, it is an (empty) prefix */
281 if(plen
48.1
'plen' is not equal to 0
55.1
'plen' is not equal to 0
 == 0)
49
←
Taking false branch
→
56
←
Taking false branch
→
282 return 1;
283 /* if so, p must be shorter */
284 if(plen
49.1
'plen' is <= 'xlen'
56.1
'plen' is <= 'xlen'
 > xlen)
50
←
Taking false branch
→
57
←
Taking false branch
→
285 return 0;
286 return (memcmp(p, x, plen) == 0);
51
←
Assuming the condition is false
→
52
←
Returning zero, which participates in a condition later
→
58
←
Assuming the condition is true
→
59
←
Returning the value 1, which participates in a condition later
→
287}
288
289/** number of bytes in common for the two strings */
290static radstrlen_type
291bstr_common(uint8_t* x, radstrlen_type xlen, uint8_t* y, radstrlen_type ylen)
292{
293 unsigned i, max = ((xlen<ylen)?xlen:ylen);
294 for(i=0; i<max; i++) {
295 if(x[i] != y[i])
296 return i;
297 }
298 return max;
299}
300
301
302int
303bstr_is_prefix_ext(uint8_t* p, radstrlen_type plen, uint8_t* x,
304 radstrlen_type xlen)
305{
306 return bstr_is_prefix(p, plen, x, xlen);
307}
308
309radstrlen_type
310bstr_common_ext(uint8_t* x, radstrlen_type xlen, uint8_t* y,
311 radstrlen_type ylen)
312{
313 return bstr_common(x, xlen, y, ylen);
314}
315
316/** allocate remainder from prefixes for a split:
317 * plen: len prefix, l: longer bstring, llen: length of l. */
318static int
319radsel_prefix_remainder(struct region* region, radstrlen_type plen,
320 uint8_t* l, radstrlen_type llen,
321 uint8_t** s, radstrlen_type* slen)
322{
323 *slen = llen - plen;
324 *s = (uint8_t*)region_alloc(region, (*slen)*sizeof(uint8_t));
325 if(!*s)
326 return 0;
327 memmove(*s, l+plen, llen-plen);
328 return 1;
329}
330
331/** radsel create a split when two nodes have shared prefix.
332 * @param r: radsel that gets changed, it contains a node.
333 * @param k: key byte string
334 * @param pos: position where the string enters the radsel (e.g. r.str)
335 * @param len: length of k.
336 * @param add: additional node for the string k.
337 * removed by called on failure.
338 * @return false on alloc failure, no changes made.
339 */
340static int
341radsel_split(struct region* region, struct radsel* r, uint8_t* k,
342 radstrlen_type pos, radstrlen_type len, struct radnode* add)
343{
344 uint8_t* addstr = k+pos;
345 radstrlen_type addlen = len-pos;
346 if(bstr_is_prefix(addstr, addlen, r->str, r->len)) {
48
←
Calling 'bstr_is_prefix'
→
53
←
Returning from 'bstr_is_prefix'
→
54
←
Taking false branch
→
347 uint8_t* split_str=NULL((void*)0), *dupstr=NULL((void*)0);
348 radstrlen_type split_len=0;
349 /* 'add' is a prefix of r.node */
350 /* also for empty addstr */
351 /* set it up so that the 'add' node has r.node as child */
352 /* so, r.node gets moved below the 'add' node, but we do
353 * this so that the r.node stays the same pointer for its
354 * key name */
355 assert(addlen != r->len)((void)0);
356 assert(addlen < r->len)((void)0);
357 if(r->len-addlen > 1) {
358 /* shift one because a char is in the lookup array */
359 if(!radsel_prefix_remainder(region, addlen+1, r->str,
360 r->len, &split_str, &split_len))
361 return 0;
362 }
363 if(addlen != 0) {
364 dupstr = (uint8_t*)region_alloc(region,
365 addlen*sizeof(uint8_t));
366 if(!dupstr) {
367 region_recycle(region, split_str, split_len);
368 return 0;
369 }
370 memcpy(dupstr, addstr, addlen);
371 }
372 if(!radnode_array_space(region, add, r->str[addlen])) {
373 region_recycle(region, split_str, split_len);
374 region_recycle(region, dupstr, addlen);
375 return 0;
376 }
377 /* alloc succeeded, now link it in */
378 add->parent = r->node->parent;
379 add->pidx = r->node->pidx;
380 add->array[0].node = r->node;
381 add->array[0].str = split_str;
382 add->array[0].len = split_len;
383 r->node->parent = add;
384 r->node->pidx = 0;
385
386 r->node = add;
387 region_recycle(region, r->str, r->len);
388 r->str = dupstr;
389 r->len = addlen;
390 } else if(bstr_is_prefix(r->str, r->len, addstr, addlen)) {
55
←
Calling 'bstr_is_prefix'
→
60
←
Returning from 'bstr_is_prefix'
→
61
←
Taking true branch
→
391 uint8_t* split_str = NULL((void*)0);
392 radstrlen_type split_len = 0;
393 /* r.node is a prefix of 'add' */
394 /* set it up so that the 'r.node' has 'add' as child */
395 /* and basically, r.node is already completely fine,
396 * we only need to create a node as its child */
397 assert(addlen != r->len)((void)0);
398 assert(r->len < addlen)((void)0);
399 if(addlen-r->len > 1) {
62
←
Taking false branch
→
400 /* shift one because a character goes into array */
401 if(!radsel_prefix_remainder(region, r->len+1, addstr,
402 addlen, &split_str, &split_len))
403 return 0;
404 }
405 if(!radnode_array_space(region, r->node, addstr[r->len])) {
63
←
3rd function call argument is an uninitialized value
406 region_recycle(region, split_str, split_len);
407 return 0;
408 }
409 /* alloc succeeded, now link it in */
410 add->parent = r->node;
411 add->pidx = addstr[r->len] - r->node->offset;
412 r->node->array[add->pidx].node = add;
413 r->node->array[add->pidx].str = split_str;
414 r->node->array[add->pidx].len = split_len;
415 } else {
416 /* okay we need to create a new node that chooses between
417 * the nodes 'add' and r.node
418 * We do this so that r.node stays the same pointer for its
419 * key name. */
420 struct radnode* com;
421 uint8_t* common_str=NULL((void*)0), *s1_str=NULL((void*)0), *s2_str=NULL((void*)0);
422 radstrlen_type common_len, s1_len=0, s2_len=0;
423 common_len = bstr_common(r->str, r->len, addstr, addlen);
424 assert(common_len < r->len)((void)0);
425 assert(common_len < addlen)((void)0);
426
427 /* create the new node for choice */
428 com = (struct radnode*)region_alloc_zero(region, sizeof(*com));
429 if(!com) return 0; /* out of memory */
430
431 /* create the two substrings for subchoices */
432 if(r->len-common_len > 1) {
433 /* shift by one char because it goes in lookup array */
434 if(!radsel_prefix_remainder(region, common_len+1,
435 r->str, r->len, &s1_str, &s1_len)) {
436 region_recycle(region, com, sizeof(*com));
437 return 0;
438 }
439 }
440 if(addlen-common_len > 1) {
441 if(!radsel_prefix_remainder(region, common_len+1,
442 addstr, addlen, &s2_str, &s2_len)) {
443 region_recycle(region, com, sizeof(*com));
444 region_recycle(region, s1_str, s1_len);
445 return 0;
446 }
447 }
448
449 /* create the shared prefix to go in r */
450 if(common_len > 0) {
451 common_str = (uint8_t*)region_alloc(region,
452 common_len*sizeof(uint8_t));
453 if(!common_str) {
454 region_recycle(region, com, sizeof(*com));
455 region_recycle(region, s1_str, s1_len);
456 region_recycle(region, s2_str, s2_len);
457 return 0;
458 }
459 memcpy(common_str, addstr, common_len);
460 }
461
462 /* make space in the common node array */
463 if(!radnode_array_space(region, com, r->str[common_len]) ||
464 !radnode_array_space(region, com, addstr[common_len])) {
465 region_recycle(region, com->array, com->capacity*sizeof(struct radsel));
466 region_recycle(region, com, sizeof(*com));
467 region_recycle(region, common_str, common_len);
468 region_recycle(region, s1_str, s1_len);
469 region_recycle(region, s2_str, s2_len);
470 return 0;
471 }
472
473 /* allocs succeeded, proceed to link it all up */
474 com->parent = r->node->parent;
475 com->pidx = r->node->pidx;
476 r->node->parent = com;
477 r->node->pidx = r->str[common_len]-com->offset;
478 add->parent = com;
479 add->pidx = addstr[common_len]-com->offset;
480 com->array[r->node->pidx].node = r->node;
481 com->array[r->node->pidx].str = s1_str;
482 com->array[r->node->pidx].len = s1_len;
483 com->array[add->pidx].node = add;
484 com->array[add->pidx].str = s2_str;
485 com->array[add->pidx].len = s2_len;
486 region_recycle(region, r->str, r->len);
487 r->str = common_str;
488 r->len = common_len;
489 r->node = com;
490 }
491 return 1;
492}
493
494struct radnode* radix_insert(struct radtree* rt, uint8_t* k,
495 radstrlen_type len, void* elem)
496{
497 struct radnode* n;
498 radstrlen_type pos = 0;
499 /* create new element to add */
500 struct radnode* add = (struct radnode*)region_alloc_zero(rt->region,
501 sizeof(*add));
502 if(!add) return NULL((void*)0); /* out of memory */
24
←
Assuming 'add' is non-null
→
25
←
Taking false branch
→
503 add->elem = elem;
504
505 /* find out where to add it */
506 if(!radix_find_prefix_node(rt, k, len, &n, &pos)) {
26
←
Calling 'radix_find_prefix_node'
→
41
←
Returning from 'radix_find_prefix_node'
→
42
←
Taking false branch
→
507 /* new root */
508 assert(rt->root == NULL)((void)0);
509 if(len == 0) {
510 rt->root = add;
511 } else {
512 /* add a root to point to new node */
513 n = (struct radnode*)region_alloc_zero(rt->region,
514 sizeof(*n));
515 if(!n) {
516 region_recycle(rt->region, add, sizeof(*add));
517 return NULL((void*)0);
518 }
519 if(!radnode_array_space(rt->region, n, k[0])) {
520 region_recycle(rt->region, n->array,
521 n->capacity*sizeof(struct radsel));
522 region_recycle(rt->region, n, sizeof(*n));
523 region_recycle(rt->region, add, sizeof(*add));
524 return NULL((void*)0);
525 }
526 add->parent = n;
527 add->pidx = 0;
528 n->array[0].node = add;
529 if(len > 1) {
530 if(!radsel_prefix_remainder(rt->region, 1, k, len,
531 &n->array[0].str, &n->array[0].len)) {
532 region_recycle(rt->region, n->array,
533 n->capacity*sizeof(struct radsel));
534 region_recycle(rt->region, n, sizeof(*n));
535 region_recycle(rt->region, add, sizeof(*add));
536 return NULL((void*)0);
537 }
538 }
539 rt->root = n;
540 }
541 } else if(pos
42.1
'pos' is not equal to 'len'
 == len) {
43
←
Taking false branch
→
542 /* found an exact match */
543 if(n->elem) {
544 /* already exists, failure */
545 region_recycle(rt->region, add, sizeof(*add));
546 return NULL((void*)0);
547 }
548 n->elem = elem;
549 region_recycle(rt->region, add, sizeof(*add));
550 add = n;
551 } else {
552 /* n is a node which can accomodate */
553 uint8_t byte;
554 assert(pos < len)((void)0);
555 byte = k[pos];
556
557 /* see if it falls outside of array */
558 if(byte
43.1
'byte' is >= field 'offset'
 < n->offset || byte-n->offset >= n->len) {
44
←
Taking false branch
→
559 /* make space in the array for it; adjusts offset */
560 if(!radnode_array_space(rt->region, n, byte)) {
561 region_recycle(rt->region, add, sizeof(*add));
562 return NULL((void*)0);
563 }
564 assert(byte>=n->offset && byte-n->offset<n->len)((void)0);
565 byte -= n->offset;
566 /* see if more prefix needs to be split off */
567 if(pos+1 < len) {
568 if(!radsel_str_create(rt->region, &n->array[byte],
569 k, pos+1, len)) {
570 region_recycle(rt->region, add, sizeof(*add));
571 return NULL((void*)0);
572 }
573 }
574 /* insert the new node in the new bucket */
575 add->parent = n;
576 add->pidx = byte;
577 n->array[byte].node = add;
578 /* so a bucket exists and byte falls in it */
579 } else if(n->array[byte-n->offset].node == NULL((void*)0)) {
45
←
Assuming field 'node' is not equal to NULL
→
46
←
Taking false branch
→
580 /* use existing bucket */
581 byte -= n->offset;
582 if(pos+1 < len) {
583 /* split off more prefix */
584 if(!radsel_str_create(rt->region, &n->array[byte],
585 k, pos+1, len)) {
586 region_recycle(rt->region, add, sizeof(*add));
587 return NULL((void*)0);
588 }
589 }
590 /* insert the new node in the new bucket */
591 add->parent = n;
592 add->pidx = byte;
593 n->array[byte].node = add;
594 } else {
595 /* use bucket but it has a shared prefix,
596 * split that out and create a new intermediate
597 * node to split out between the two.
598 * One of the two might exactmatch the new
599 * intermediate node */
600 if(!radsel_split(rt->region, &n->array[byte-n->offset],
47
←
Calling 'radsel_split'
→
601 k, pos+1, len, add)) {
602 region_recycle(rt->region, add, sizeof(*add));
603 return NULL((void*)0);
604 }
605 }
606 }
607
608 rt->count ++;
609 return add;
610}
611
612/** Delete a radnode */
613static void radnode_delete(struct region* region, struct radnode* n)
614{
615 unsigned i;
616 if(!n) return;
617 for(i=0; i<n->len; i++) {
618 /* safe to free NULL str */
619 region_recycle(region, n->array[i].str, n->array[i].len);
620 }
621 region_recycle(region, n->array, n->capacity*sizeof(struct radsel));
622 region_recycle(region, n, sizeof(*n));
623}
624
625/** Cleanup node with one child, it is removed and joined into parent[x] str */
626static int
627radnode_cleanup_onechild(struct region* region, struct radnode* n,
628 struct radnode* par)
629{
630 uint8_t* join;
631 radstrlen_type joinlen;
632 uint8_t pidx = n->pidx;
633 struct radnode* child = n->array[0].node;
634 /* node had one child, merge them into the parent. */
635 /* keep the child node, so its pointers stay valid. */
636
637 /* at parent, append child->str to array str */
638 assert(pidx < par->len)((void)0);
639 joinlen = par->array[pidx].len + n->array[0].len + 1;
640 join = (uint8_t*)region_alloc(region, joinlen*sizeof(uint8_t));
641 if(!join) {
642 /* cleanup failed due to out of memory */
643 /* the tree is inefficient, with node n still existing */
644 return 0;
645 }
646 /* we know that .str and join are malloced, thus aligned */
647 if(par->array[pidx].str)
648 memcpy(join, par->array[pidx].str, par->array[pidx].len);
649 /* the array lookup is gone, put its character in the lookup string*/
650 join[par->array[pidx].len] = child->pidx + n->offset;
651 /* but join+len may not be aligned */
652 if(n->array[0].str)
653 memmove(join+par->array[pidx].len+1, n->array[0].str, n->array[0].len);
654 region_recycle(region, par->array[pidx].str, par->array[pidx].len);
655 par->array[pidx].str = join;
656 par->array[pidx].len = joinlen;
657 /* and set the node to our child. */
658 par->array[pidx].node = child;
659 child->parent = par;
660 child->pidx = pidx;
661 /* we are unlinked, delete our node */
662 radnode_delete(region, n);
663 return 1;
664}
665
666/** remove array of nodes */
667static void
668radnode_array_clean_all(struct region* region, struct radnode* n)
669{
670 n->offset = 0;
671 n->len = 0;
672 /* shrink capacity */
673 region_recycle(region, n->array, n->capacity*sizeof(struct radsel));
674 n->array = NULL((void*)0);
675 n->capacity = 0;
676}
677
678/** see if capacity can be reduced for the given node array */
679static void
680radnode_array_reduce_if_needed(struct region* region, struct radnode* n)
681{
682 if(n->len <= n->capacity/2 && n->len != n->capacity) {
683 struct radsel* a = (struct radsel*)region_alloc_array(region,
684 sizeof(*a), n->len);
685 if(!a) return;
686 memcpy(a, n->array, sizeof(*a)*n->len);
687 region_recycle(region, n->array, n->capacity*sizeof(*a));
688 n->array = a;
689 n->capacity = n->len;
690 }
691}
692
693/** remove NULL nodes from front of array */
694static void
695radnode_array_clean_front(struct region* region, struct radnode* n)
696{
697 /* move them up and adjust offset */
698 unsigned idx, shuf = 0;
699 /* remove until a nonNULL entry */
700 while(shuf < n->len && n->array[shuf].node == NULL((void*)0))
701 shuf++;
702 if(shuf == 0)
703 return;
704 if(shuf == n->len) {
705 /* the array is empty, the tree is inefficient */
706 radnode_array_clean_all(region, n);
707 return;
708 }
709 assert(shuf < n->len)((void)0);
710 assert((int)shuf <= 255-(int)n->offset)((void)0);
711 memmove(&n->array[0], &n->array[shuf],
712 (n->len - shuf)*sizeof(struct radsel));
713 n->offset += shuf;
714 n->len -= shuf;
715 for(idx=0; idx<n->len; idx++)
716 if(n->array[idx].node)
717 n->array[idx].node->pidx = idx;
718 /* see if capacity can be reduced */
719 radnode_array_reduce_if_needed(region, n);
720}
721
722/** remove NULL nodes from end of array */
723static void
724radnode_array_clean_end(struct region* region, struct radnode* n)
725{
726 /* shorten it */
727 unsigned shuf = 0;
728 /* remove until a nonNULL entry */
729 while(shuf < n->len && n->array[n->len-1-shuf].node == NULL((void*)0))
730 shuf++;
731 if(shuf == 0)
732 return;
733 if(shuf == n->len) {
734 /* the array is empty, the tree is inefficient */
735 radnode_array_clean_all(region, n);
736 return;
737 }
738 assert(shuf < n->len)((void)0);
739 n->len -= shuf;
740 /* array elements can stay where they are */
741 /* see if capacity can be reduced */
742 radnode_array_reduce_if_needed(region, n);
743}
744
745/** clean up radnode leaf, where we know it has a parent */
746static void
747radnode_cleanup_leaf(struct region* region, struct radnode* n,
748 struct radnode* par)
749{
750 uint8_t pidx;
751 /* node was a leaf */
752 /* delete leaf node, but store parent+idx */
753 pidx = n->pidx;
754 radnode_delete(region, n);
755
756 /* set parent+idx entry to NULL str and node.*/
757 assert(pidx < par->len)((void)0);
758 region_recycle(region, par->array[pidx].str, par->array[pidx].len);
759 par->array[pidx].str = NULL((void*)0);
760 par->array[pidx].len = 0;
761 par->array[pidx].node = NULL((void*)0);
762
763 /* see if par offset or len must be adjusted */
764 if(par->len == 1) {
765 /* removed final element from array */
766 radnode_array_clean_all(region, par);
767 } else if(pidx == 0) {
768 /* removed first element from array */
769 radnode_array_clean_front(region, par);
770 } else if(pidx == par->len-1) {
771 /* removed last element from array */
772 radnode_array_clean_end(region, par);
773 }
774}
775
776/**
777 * Cleanup a radix node that was made smaller, see if it can
778 * be merged with others.
779 * @param rt: tree to remove root if needed.
780 * @param n: node to cleanup
781 * @return false on alloc failure.
782 */
783static int
784radnode_cleanup(struct radtree* rt, struct radnode* n)
785{
786 while(n) {
787 if(n->elem) {
788 /* cannot delete node with a data element */
789 return 1;
790 } else if(n->len == 1 && n->parent) {
791 return radnode_cleanup_onechild(rt->region, n, n->parent);
792 } else if(n->len == 0) {
793 struct radnode* par = n->parent;
794 if(!par) {
795 /* root deleted */
796 radnode_delete(rt->region, n);
797 rt->root = NULL((void*)0);
798 return 1;
799 }
800 /* remove and delete the leaf node */
801 radnode_cleanup_leaf(rt->region, n, par);
802 /* see if parent can now be cleaned up */
803 n = par;
804 } else {
805 /* node cannot be cleaned up */
806 return 1;
807 }
808 }
809 /* ENOTREACH */
810 return 1;
811}
812
813void radix_delete(struct radtree* rt, struct radnode* n)
814{
815 if(!n) return;
816 n->elem = NULL((void*)0);
817 rt->count --;
818 if(!radnode_cleanup(rt, n)) {
819 /* out of memory in cleanup. the elem ptr is NULL, but
820 * the radix tree could be inefficient. */
821 }
822}
823
824struct radnode* radix_search(struct radtree* rt, uint8_t* k,
825 radstrlen_type len)
826{
827 struct radnode* n = rt->root;
828 radstrlen_type pos = 0;
829 uint8_t byte;
830 while(n) {
831 if(pos == len)
832 return n->elem?n:NULL((void*)0);
833 byte = k[pos];
834 if(byte < n->offset)
835 return NULL((void*)0);
836 byte -= n->offset;
837 if(byte >= n->len)
838 return NULL((void*)0);
839 pos++;
840 if(n->array[byte].len != 0) {
841 /* must match additional string */
842 if(pos+n->array[byte].len > len)
843 return NULL((void*)0); /* no match */
844 if(memcmp(&k[pos], n->array[byte].str,
845 n->array[byte].len) != 0)
846 return NULL((void*)0); /* no match */
847 pos += n->array[byte].len;
848 }
849 n = n->array[byte].node;
850 }
851 return NULL((void*)0);
852}
853
854/** return self or a previous element */
855static int ret_self_or_prev(struct radnode* n, struct radnode** result)
856{
857 if(n->elem)
858 *result = n;
859 else *result = radix_prev(n);
860 return 0;
861}
862
863int radix_find_less_equal(struct radtree* rt, uint8_t* k, radstrlen_type len,
864 struct radnode** result)
865{
866 struct radnode* n = rt->root;
867 radstrlen_type pos = 0;
868 uint8_t byte;
869 int r;
870 if(!n) {
871 /* empty tree */
872 *result = NULL((void*)0);
873 return 0;
874 }
875 while(pos < len) {
876 byte = k[pos];
877 if(byte < n->offset) {
878 /* so the previous is the element itself */
879 /* or something before this element */
880 return ret_self_or_prev(n, result);
881 }
882 byte -= n->offset;
883 if(byte >= n->len) {
884 /* so, the previous is the last of array, or itself */
885 /* or something before this element */
886 if((*result=radnode_last_in_subtree_incl_self(n))==0)
887 *result = radix_prev(n);
888 return 0;
889 }
890 pos++;
891 if(!n->array[byte].node) {
892 /* no match */
893 /* Find an entry in arrays from byte-1 to 0 */
894 *result = radnode_find_prev_from_idx(n, byte);
895 if(*result)
896 return 0;
897 /* this entry or something before it */
898 return ret_self_or_prev(n, result);
899 }
900 if(n->array[byte].len != 0) {
901 /* must match additional string */
902 if(pos+n->array[byte].len > len) {
903 /* the additional string is longer than key*/
904 if( (memcmp(&k[pos], n->array[byte].str,
905 len-pos)) <= 0) {
906 /* and the key is before this node */
907 *result = radix_prev(n->array[byte].node);
908 } else {
909 /* the key is after the additional
910 * string, thus everything in that
911 * subtree is smaller. */
912 *result=radnode_last_in_subtree_incl_self(n->array[byte].node);
913 /* if somehow that is NULL,
914 * then we have an inefficient tree:
915 * byte+1 is larger than us, so find
916 * something in byte-1 and before */
917 if(!*result)
918 *result = radix_prev(n->array[byte].node);
919 }
920 return 0; /* no match */
921 }
922 if( (r=memcmp(&k[pos], n->array[byte].str,
923 n->array[byte].len)) < 0) {
924 *result = radix_prev(n->array[byte].node);
925 return 0; /* no match */
926 } else if(r > 0) {
927 /* the key is larger than the additional
928 * string, thus everything in that subtree
929 * is smaller */
930 *result=radnode_last_in_subtree_incl_self(n->array[byte].node);
931 /* if we have an inefficient tree */
932 if(!*result) *result = radix_prev(n->array[byte].node);
933 return 0; /* no match */
934 }
935 pos += n->array[byte].len;
936 }
937 n = n->array[byte].node;
938 }
939 if(n->elem) {
940 /* exact match */
941 *result = n;
942 return 1;
943 }
944 /* there is a node which is an exact match, but it has no element */
945 *result = radix_prev(n);
946 return 0;
947}
948
949
950struct radnode* radix_first(struct radtree* rt)
951{
952 struct radnode* n;
953 if(!rt || !rt->root) return NULL((void*)0);
954 n = rt->root;
955 if(n->elem) return n;
956 return radix_next(n);
957}
958
959struct radnode* radix_last(struct radtree* rt)
960{
961 if(!rt || !rt->root) return NULL((void*)0);
962 return radnode_last_in_subtree_incl_self(rt->root);
963}
964
965struct radnode* radix_next(struct radnode* n)
966{
967 if(!n) return NULL((void*)0);
968 if(n->len) {
969 /* go down */
970 struct radnode* s = radnode_first_in_subtree(n);
971 if(s) return s;
972 }
973 /* go up - the parent->elem is not useful, because it is before us */
974 while(n->parent) {
975 unsigned idx = n->pidx;
976 n = n->parent;
977 idx++;
978 for(; idx < n->len; idx++) {
979 /* go down the next branch */
980 if(n->array[idx].node) {
981 struct radnode* s;
982 /* node itself */
983 if(n->array[idx].node->elem)
984 return n->array[idx].node;
985 /* or subtree */
986 s = radnode_first_in_subtree(
987 n->array[idx].node);
988 if(s) return s;
989 }
990 }
991 }
992 return NULL((void*)0);
993}
994
995struct radnode* radix_prev(struct radnode* n)
996{
997 if(!n) return NULL((void*)0);
998 /* must go up, since all array nodes are after this node */
999 while(n->parent) {
1000 uint8_t idx = n->pidx;
1001 struct radnode* s;
1002 n = n->parent;
1003 assert(n->len > 0)((void)0); /* since we are a child */
1004 /* see if there are elements in previous branches there */
1005 s = radnode_find_prev_from_idx(n, idx);
1006 if(s) return s;
1007 /* the current node is before the array */
1008 if(n->elem)
1009 return n;
1010 }
1011 return NULL((void*)0);
1012}
1013
1014/** convert one character from domain-name to radname */
1015static uint8_t char_d2r(uint8_t c)
1016{
1017 if(c < 'A') return c+1; /* make space for 00 */
1018 else if(c <= 'Z') return c-'A'+'a'; /* lowercase */
1019 else return c;
1020}
1021
1022/** convert one character from radname to domain-name (still lowercased) */
1023static uint8_t char_r2d(uint8_t c)
1024{
1025 assert(c != 0)((void)0); /* end of label */
1026 if(c <= 'A') return c-1;
1027 else return c;
1028}
1029
1030/** copy and convert a range of characters */
1031static void cpy_d2r(uint8_t* to, const uint8_t* from, int len)
1032{
1033 int i;
1034 for(i=0; i<len; i++)
17
←
Assuming 'i' is >= 'len'
→
18
←
Loop condition is false. Execution continues on line 1034
→
1035 to[i] = char_d2r(from[i]);
1036}
1037
1038/** copy and convert a range of characters */
1039static void cpy_r2d(uint8_t* to, uint8_t* from, uint8_t len)
1040{
1041 uint8_t i;
1042 for(i=0; i<len; i++)
1043 to[i] = char_r2d(from[i]);
1044}
1045
1046/* radname code: domain to radix-bstring */
1047void radname_d2r(uint8_t* k, radstrlen_type* len, const uint8_t* dname,
1048 size_t dlen)
1049{
1050 /* the domain name is converted as follows,
1051 * to preserve the normal (NSEC) ordering of domain names.
1052 * lowercased, and 'end-of-label' is a '00' byte,
1053 * bytes 00-'A' are +1 moved to make space for 00 byte.
1054 * final root label is not appended (string ends).
1055 * because the only allowed empty label is the final root label,
1056 * we can also remove the last 00 label-end.
1057 * The total result length is one-or-two less than the dname.
1058 *
1059 * examples (numbers are bytes, letters are ascii):
1060 * - root: dname: 0, radname: ''
1061 * - nl.: dname: 3nl0, radname: 'nl'
1062 * - labs.nl: dname 4labs3nl0, radname: 'nl0labs'
1063 * - x.labs.nl: dname 1x4labs3nl0, radname: 'nl0labs0x'
1064 */
1065
1066 /* conversion by putting the label starts on a stack */
1067 const uint8_t* labstart[130];
1068 unsigned int lab = 0, kpos, dpos = 0;
1069 /* sufficient space */
1070 assert(k && dname)((void)0);
1071 assert(dlen <= 256)((void)0); /* and therefore not more than 128 labels */
1072 assert(*len >= dlen)((void)0);
1073 assert(dlen > 0)((void)0); /* even root label has dlen=1 */
1074
1075 /* root */
1076 if(dlen == 1) {
4
←
Assuming 'dlen' is not equal to 1
→
5
←
Taking false branch
→
1077 assert(dname[0] == 0)((void)0);
1078 *len = 0;
1079 return;
1080 }
1081
1082 /* walk through domain name and remember label positions */
1083 do {
10
←
Loop condition is true. Execution continues on line 1085
→
15
←
Loop condition is false. Exiting loop
→
1084 /* compression pointers not allowed */
1085 if((dname[dpos] & 0xc0)) {
6
←
Assuming the condition is false
→
7
←
Taking false branch
→
11
←
Assuming the condition is false
→
12
←
Taking false branch
→
1086 *len = 0;
1087 return; /* format error */
1088 }
1089 labstart[lab++] = &dname[dpos];
1090 if(dpos + dname[dpos] + 1 >= dlen) {
8
←
Assuming the condition is false
→
9
←
Taking false branch
→
13
←
Assuming the condition is false
→
14
←
Taking false branch
→
1091 *len = 0;
1092 return; /* format error */
1093 }
1094 /* skip the label contents */
1095 dpos += dname[dpos];
1096 dpos ++;
1097 } while(dname[dpos] != 0);
1098 /* exit condition makes root label not in labelstart stack */
1099 /* because the root was handled before, we know there is some text */
1100 assert(lab > 0)((void)0);
1101 lab-=1;
1102 kpos = *labstart[lab];
1103 cpy_d2r(k, labstart[lab]+1, kpos);
16
←
Calling 'cpy_d2r'
→
19
←
Returning from 'cpy_d2r'
→
1104 /* if there are more labels, copy them over */
1105 while(lab) {
20
←
Loop condition is true. Entering loop body
→
21
←
Loop condition is false. Execution continues on line 1114
→
1106 /* put 'end-of-label' 00 to end previous label */
1107 k[kpos++]=0;
1108 /* append the label */
1109 lab--;
1110 cpy_d2r(k+kpos, labstart[lab]+1, *labstart[lab]);
1111 kpos += *labstart[lab];
1112 }
1113 /* done */
1114 assert(kpos == dlen-2)((void)0); /* no rootlabel, one less label-marker */
1115 *len = kpos;
1116}
1117
1118/* radname code: radix-bstring to domain */
1119void radname_r2d(uint8_t* k, radstrlen_type len, uint8_t* dname, size_t* dlen)
1120{
1121 /* find labels and push on stack */
1122 uint8_t* labstart[130];
1123 uint8_t lablen[130];
1124 unsigned int lab = 0, dpos, kpos = 0;
1125 /* sufficient space */
1126 assert(k && dname)((void)0);
1127 assert((size_t)*dlen >= (size_t)len+2)((void)0);
1128 assert(len <= 256)((void)0);
1129 /* root label */
1130 if(len == 0) {
1131 assert(*dlen > 0)((void)0);
1132 dname[0]=0;
1133 *dlen=1;
1134 return;
1135 }
1136 /* find labels */
1137 while(kpos < len) {
1138 lablen[lab]=0;
1139 labstart[lab]=&k[kpos];
1140 /* skip to next label */
1141 while(kpos < len && k[kpos] != 0) {
1142 lablen[lab]++;
1143 kpos++;
1144 }
1145 lab++;
1146 /* skip 00 byte for label-end */
1147 if(kpos < len) {
1148 assert(k[kpos] == 0)((void)0);
1149 kpos++;
1150 }
1151 }
1152 /* copy the labels over to the domain name */
1153 dpos = 0;
1154 while(lab) {
1155 lab--;
1156 /* label length */
1157 dname[dpos++] = lablen[lab];
1158 /* label content */
1159 cpy_r2d(dname+dpos, labstart[lab], lablen[lab]);
1160 dpos += lablen[lab];
1161 }
1162 /* append root label */
1163 dname[dpos++] = 0;
1164 /* assert the domain name is wellformed */
1165 assert((int)dpos == (int)len+2)((void)0);
1166 assert(dname[dpos-1] == 0)((void)0); /* ends with root label */
1167 *dlen = dpos;
1168}
1169
1170/** insert by domain name */
1171struct radnode*
1172radname_insert(struct radtree* rt, const uint8_t* d, size_t max, void* elem)
1173{
1174 /* convert and insert */
1175 uint8_t radname[300];
1176 radstrlen_type len = (radstrlen_type)sizeof(radname);
1177 if(max > sizeof(radname))
1
Assuming the condition is false
→
2
←
Taking false branch
→
1178 return NULL((void*)0); /* too long */
1179 radname_d2r(radname, &len, d, max);
3
←
Calling 'radname_d2r'
→
22
←
Returning from 'radname_d2r'
→
1180 return radix_insert(rt, radname, len, elem);
23
←
Calling 'radix_insert'
→
1181}
1182
1183/** delete by domain name */
1184void
1185radname_delete(struct radtree* rt, const uint8_t* d, size_t max)
1186{
1187 /* search and remove */
1188 struct radnode* n = radname_search(rt, d, max);
1189 if(n) radix_delete(rt, n);
1190}
1191
1192/* search for exact match of domain name, converted to radname in tree */
1193struct radnode* radname_search(struct radtree* rt, const uint8_t* d,
1194 size_t max)
1195{
1196 /* stack of labels in the domain name */
1197 const uint8_t* labstart[130];
1198 unsigned int lab, dpos, lpos;
1199 struct radnode* n = rt->root;
1200 uint8_t byte;
1201 radstrlen_type i;
1202 uint8_t b;
1203
1204 /* search for root? it is '' */
1205 if(max < 1)
1206 return NULL((void*)0);
1207 if(d[0] == 0) {
1208 if(!n) return NULL((void*)0);
1209 return n->elem?n:NULL((void*)0);
1210 }
1211
1212 /* find labels stack in domain name */
1213 lab = 0;
1214 dpos = 0;
1215 /* must have one label, since root is specialcased */
1216 do {
1217 if((d[dpos] & 0xc0))
1218 return NULL((void*)0); /* compression ptrs not allowed error */
1219 labstart[lab++] = &d[dpos];
1220 if(dpos + d[dpos] + 1 >= max)
1221 return NULL((void*)0); /* format error: outside of bounds */
1222 /* skip the label contents */
1223 dpos += d[dpos];
1224 dpos ++;
1225 } while(d[dpos] != 0);
1226 /* exit condition makes that root label is not in the labstarts */
1227 /* now: dpos+1 is length of domain name. lab is number of labels-1 */
1228
1229 /* start processing at the last label */
1230 lab-=1;
1231 lpos = 0;
1232 while(n) {
1233 /* fetch next byte this label */
1234 if(lpos < *labstart[lab])
1235 /* lpos+1 to skip labelstart, lpos++ to move forward */
1236 byte = char_d2r(labstart[lab][++lpos]);
1237 else {
1238 if(lab == 0) /* last label - we're done */
1239 return n->elem?n:NULL((void*)0);
1240 /* next label, search for byte 00 */
1241 lpos = 0;
1242 lab--;
1243 byte = 0;
1244 }
1245 /* find that byte in the array */
1246 if(byte < n->offset)
1247 return NULL((void*)0);
1248 byte -= n->offset;
1249 if(byte >= n->len)
1250 return NULL((void*)0);
1251 if(n->array[byte].len != 0) {
1252 /* must match additional string */
1253 /* see how many bytes we need and start matching them*/
1254 for(i=0; i<n->array[byte].len; i++) {
1255 /* next byte to match */
1256 if(lpos < *labstart[lab])
1257 b = char_d2r(labstart[lab][++lpos]);
1258 else {
1259 /* if last label, no match since
1260 * we are in the additional string */
1261 if(lab == 0)
1262 return NULL((void*)0);
1263 /* next label, search for byte 00 */
1264 lpos = 0;
1265 lab--;
1266 b = 0;
1267 }
1268 if(n->array[byte].str[i] != b)
1269 return NULL((void*)0); /* not matched */
1270 }
1271 }
1272 n = n->array[byte].node;
1273 }
1274 return NULL((void*)0);
1275}
1276
1277/* find domain name or smaller or equal domain name in radix tree */
1278int radname_find_less_equal(struct radtree* rt, const uint8_t* d, size_t max,
1279 struct radnode** result)
1280{
1281 /* stack of labels in the domain name */
1282 const uint8_t* labstart[130];
1283 unsigned int lab, dpos, lpos;
1284 struct radnode* n = rt->root;
1285 uint8_t byte;
1286 radstrlen_type i;
1287 uint8_t b;
1288
1289 /* empty tree */
1290 if(!n) {
1291 *result = NULL((void*)0);
1292 return 0;
1293 }
1294
1295 /* search for root? it is '' */
1296 if(max < 1) {
1297 *result = NULL((void*)0);
1298 return 0; /* parse error, out of bounds */
1299 }
1300 if(d[0] == 0) {
1301 if(n->elem) {
1302 *result = n;
1303 return 1;
1304 }
1305 /* no smaller element than the root */
1306 *result = NULL((void*)0);
1307 return 0;
1308 }
1309
1310 /* find labels stack in domain name */
1311 lab = 0;
1312 dpos = 0;
1313 /* must have one label, since root is specialcased */
1314 do {
1315 if((d[dpos] & 0xc0)) {
1316 *result = NULL((void*)0);
1317 return 0; /* compression ptrs not allowed error */
1318 }
1319 labstart[lab++] = &d[dpos];
1320 if(dpos + d[dpos] + 1 >= max) {
1321 *result = NULL((void*)0); /* format error: outside of bounds */
1322 return 0;
1323 }
1324 /* skip the label contents */
1325 dpos += d[dpos];
1326 dpos ++;
1327 } while(d[dpos] != 0);
1328 /* exit condition makes that root label is not in the labstarts */
1329 /* now: dpos+1 is length of domain name. lab is number of labels-1 */
1330
1331 /* start processing at the last label */
1332 lab-=1;
1333 lpos = 0;
1334 while(1) {
1335 /* fetch next byte this label */
1336 if(lpos < *labstart[lab])
1337 /* lpos+1 to skip labelstart, lpos++ to move forward */
1338 byte = char_d2r(labstart[lab][++lpos]);
1339 else {
1340 if(lab == 0) {
1341 /* last label - we're done */
1342 /* exact match */
1343 if(n->elem) {
1344 *result = n;
1345 return 1;
1346 }
1347 /* there is a node which is an exact match,
1348 * but there no element in it */
1349 *result = radix_prev(n);
1350 return 0;
1351 }
1352 /* next label, search for byte 0 the label separator */
1353 lpos = 0;
1354 lab--;
1355 byte = 0;
1356 }
1357 /* find that byte in the array */
1358 if(byte < n->offset)
1359 /* so the previous is the element itself */
1360 /* or something before this element */
1361 return ret_self_or_prev(n, result);
1362 byte -= n->offset;
1363 if(byte >= n->len) {
1364 /* so, the previous is the last of array, or itself */
1365 /* or something before this element */
1366 *result = radnode_last_in_subtree_incl_self(n);
1367 if(!*result)
1368 *result = radix_prev(n);
1369 return 0;
1370 }
1371 if(!n->array[byte].node) {
1372 /* no match */
1373 /* Find an entry in arrays from byte-1 to 0 */
1374 *result = radnode_find_prev_from_idx(n, byte);
1375 if(*result)
1376 return 0;
1377 /* this entry or something before it */
1378 return ret_self_or_prev(n, result);
1379 }
1380 if(n->array[byte].len != 0) {
1381 /* must match additional string */
1382 /* see how many bytes we need and start matching them*/
1383 for(i=0; i<n->array[byte].len; i++) {
1384 /* next byte to match */
1385 if(lpos < *labstart[lab])
1386 b = char_d2r(labstart[lab][++lpos]);
1387 else {
1388 /* if last label, no match since
1389 * we are in the additional string */
1390 if(lab == 0) {
1391 /* dname ended, thus before
1392 * this array element */
1393 *result =radix_prev(
1394 n->array[byte].node);
1395 return 0;
1396 }
1397 /* next label, search for byte 00 */
1398 lpos = 0;
1399 lab--;
1400 b = 0;
1401 }
1402 if(b < n->array[byte].str[i]) {
1403 *result =radix_prev(
1404 n->array[byte].node);
1405 return 0;
1406 } else if(b > n->array[byte].str[i]) {
1407 /* the key is after the additional,
1408 * so everything in its subtree is
1409 * smaller */
1410 *result = radnode_last_in_subtree_incl_self(n->array[byte].node);
1411 /* if that is NULL, we have an
1412 * inefficient tree, find in byte-1*/
1413 if(!*result)
1414 *result = radix_prev(n->array[byte].node);
1415 return 0;
1416 }
1417 }
1418 }
1419 n = n->array[byte].node;
1420 }
1421 /* ENOTREACH */
1422 return 0;
1423}
1424