1 /*
2 * Copyright (C) 2007-2009, 2011, 2012 Internet Systems Consortium, Inc. ("ISC")
3 *
4 * Permission to use, copy, modify, and/or distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
7 *
8 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
9 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
10 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
11 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
12 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
13 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
14 * PERFORMANCE OF THIS SOFTWARE.
15 */
16
17 /* $Id$ */
18
19 /*
20 * This source was adapted from MRT's RCS Ids:
21 * Id: radix.c,v 1.10.2.1 1999/11/29 05:16:24 masaki Exp
22 * Id: prefix.c,v 1.37.2.9 2000/03/10 02:53:19 labovit Exp
23 */
24
25 #include <config.h>
26
27 #include <isc/mem.h>
28 #include <isc/types.h>
29 #include <isc/util.h>
30 #include <isc/radix.h>
31
32 static isc_result_t
33 _new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family,
34 void *dest, int bitlen);
35
36 static void
37 _deref_prefix(isc_mem_t *mctx, isc_prefix_t *prefix);
38
39 static isc_result_t
40 _ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix);
41
42 static int
43 _comp_with_mask(void *addr, void *dest, u_int mask);
44
45 static void
46 _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func);
47
48 static isc_result_t
_new_prefix(isc_mem_t * mctx,isc_prefix_t ** target,int family,void * dest,int bitlen)49 _new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest,
50 int bitlen)
51 {
52 isc_prefix_t *prefix;
53
54 REQUIRE(target != NULL);
55
56 if (family != AF_INET6 && family != AF_INET && family != AF_UNSPEC)
57 return (ISC_R_NOTIMPLEMENTED);
58
59 prefix = isc_mem_get(mctx, sizeof(isc_prefix_t));
60 if (prefix == NULL)
61 return (ISC_R_NOMEMORY);
62
63 if (family == AF_INET6) {
64 prefix->bitlen = (bitlen >= 0) ? bitlen : 128;
65 memcpy(&prefix->add.sin6, dest, 16);
66 } else {
67 /* AF_UNSPEC is "any" or "none"--treat it as AF_INET */
68 prefix->bitlen = (bitlen >= 0) ? bitlen : 32;
69 memcpy(&prefix->add.sin, dest, 4);
70 }
71
72 prefix->family = family;
73
74 isc_refcount_init(&prefix->refcount, 1);
75
76 *target = prefix;
77 return (ISC_R_SUCCESS);
78 }
79
80 static void
_deref_prefix(isc_mem_t * mctx,isc_prefix_t * prefix)81 _deref_prefix(isc_mem_t *mctx, isc_prefix_t *prefix) {
82 int refs;
83
84 if (prefix == NULL)
85 return;
86
87 isc_refcount_decrement(&prefix->refcount, &refs);
88
89 if (refs <= 0) {
90 isc_refcount_destroy(&prefix->refcount);
91 isc_mem_put(mctx, prefix, sizeof(isc_prefix_t));
92 }
93 }
94
95 static isc_result_t
_ref_prefix(isc_mem_t * mctx,isc_prefix_t ** target,isc_prefix_t * prefix)96 _ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix) {
97 INSIST(prefix != NULL);
98 INSIST((prefix->family == AF_INET && prefix->bitlen <= 32) ||
99 (prefix->family == AF_INET6 && prefix->bitlen <= 128) ||
100 (prefix->family == AF_UNSPEC && prefix->bitlen == 0));
101 REQUIRE(target != NULL && *target == NULL);
102
103 /*
104 * If this prefix is a static allocation, copy it into new memory.
105 * (Note, the refcount still has to be destroyed by the calling
106 * routine.)
107 */
108 if (isc_refcount_current(&prefix->refcount) == 0) {
109 isc_result_t ret;
110 ret = _new_prefix(mctx, target, prefix->family,
111 &prefix->add, prefix->bitlen);
112 return ret;
113 }
114
115 isc_refcount_increment(&prefix->refcount, NULL);
116
117 *target = prefix;
118 return (ISC_R_SUCCESS);
119 }
120
121 static int
_comp_with_mask(void * addr,void * dest,u_int mask)122 _comp_with_mask(void *addr, void *dest, u_int mask) {
123
124 /* Mask length of zero matches everything */
125 if (mask == 0)
126 return (1);
127
128 if (memcmp(addr, dest, mask / 8) == 0) {
129 int n = mask / 8;
130 int m = ((~0) << (8 - (mask % 8)));
131
132 if ((mask % 8) == 0 ||
133 (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m))
134 return (1);
135 }
136 return (0);
137 }
138
139 isc_result_t
isc_radix_create(isc_mem_t * mctx,isc_radix_tree_t ** target,int maxbits)140 isc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits) {
141 isc_radix_tree_t *radix;
142
143 REQUIRE(target != NULL && *target == NULL);
144
145 radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t));
146 if (radix == NULL)
147 return (ISC_R_NOMEMORY);
148
149 radix->mctx = mctx;
150 radix->maxbits = maxbits;
151 radix->head = NULL;
152 radix->num_active_node = 0;
153 radix->num_added_node = 0;
154 RUNTIME_CHECK(maxbits <= RADIX_MAXBITS); /* XXX */
155 radix->magic = RADIX_TREE_MAGIC;
156 *target = radix;
157 return (ISC_R_SUCCESS);
158 }
159
160 /*
161 * if func is supplied, it will be called as func(node->data)
162 * before deleting the node
163 */
164
165 static void
_clear_radix(isc_radix_tree_t * radix,isc_radix_destroyfunc_t func)166 _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
167
168 REQUIRE(radix != NULL);
169
170 if (radix->head != NULL) {
171
172 isc_radix_node_t *Xstack[RADIX_MAXBITS+1];
173 isc_radix_node_t **Xsp = Xstack;
174 isc_radix_node_t *Xrn = radix->head;
175
176 while (Xrn != NULL) {
177 isc_radix_node_t *l = Xrn->l;
178 isc_radix_node_t *r = Xrn->r;
179
180 if (Xrn->prefix != NULL) {
181 _deref_prefix(radix->mctx, Xrn->prefix);
182 if (func != NULL && (Xrn->data[0] != NULL ||
183 Xrn->data[1] != NULL))
184 func(Xrn->data);
185 } else {
186 INSIST(Xrn->data[0] == NULL &&
187 Xrn->data[1] == NULL);
188 }
189
190 isc_mem_put(radix->mctx, Xrn, sizeof(*Xrn));
191 radix->num_active_node--;
192
193 if (l != NULL) {
194 if (r != NULL) {
195 *Xsp++ = r;
196 }
197 Xrn = l;
198 } else if (r != NULL) {
199 Xrn = r;
200 } else if (Xsp != Xstack) {
201 Xrn = *(--Xsp);
202 } else {
203 Xrn = NULL;
204 }
205 }
206 }
207 RUNTIME_CHECK(radix->num_active_node == 0);
208 }
209
210
211 void
isc_radix_destroy(isc_radix_tree_t * radix,isc_radix_destroyfunc_t func)212 isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func)
213 {
214 REQUIRE(radix != NULL);
215 _clear_radix(radix, func);
216 isc_mem_put(radix->mctx, radix, sizeof(*radix));
217 }
218
219
220 /*
221 * func will be called as func(node->prefix, node->data)
222 */
223 void
isc_radix_process(isc_radix_tree_t * radix,isc_radix_processfunc_t func)224 isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func)
225 {
226 isc_radix_node_t *node;
227
228 REQUIRE(func != NULL);
229
230 RADIX_WALK(radix->head, node) {
231 func(node->prefix, node->data);
232 } RADIX_WALK_END;
233 }
234
235
236 isc_result_t
isc_radix_search(isc_radix_tree_t * radix,isc_radix_node_t ** target,isc_prefix_t * prefix)237 isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target,
238 isc_prefix_t *prefix)
239 {
240 isc_radix_node_t *node;
241 isc_radix_node_t *stack[RADIX_MAXBITS + 1];
242 u_char *addr;
243 isc_uint32_t bitlen;
244 int tfamily = -1;
245 int cnt = 0;
246
247 REQUIRE(radix != NULL);
248 REQUIRE(prefix != NULL);
249 REQUIRE(target != NULL && *target == NULL);
250 RUNTIME_CHECK(prefix->bitlen <= radix->maxbits);
251
252 *target = NULL;
253
254 if (radix->head == NULL) {
255 return (ISC_R_NOTFOUND);
256 }
257
258 node = radix->head;
259 addr = isc_prefix_touchar(prefix);
260 bitlen = prefix->bitlen;
261
262 while (node->bit < bitlen) {
263 if (node->prefix)
264 stack[cnt++] = node;
265
266 if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
267 node = node->r;
268 else
269 node = node->l;
270
271 if (node == NULL)
272 break;
273 }
274
275 if (node && node->prefix)
276 stack[cnt++] = node;
277
278 while (cnt-- > 0) {
279 node = stack[cnt];
280
281 if (_comp_with_mask(isc_prefix_tochar(node->prefix),
282 isc_prefix_tochar(prefix),
283 node->prefix->bitlen)) {
284 if (node->node_num[ISC_IS6(prefix->family)] != -1 &&
285 ((*target == NULL) ||
286 (*target)->node_num[ISC_IS6(tfamily)] >
287 node->node_num[ISC_IS6(prefix->family)])) {
288 *target = node;
289 tfamily = prefix->family;
290 }
291 }
292 }
293
294 if (*target == NULL) {
295 return (ISC_R_NOTFOUND);
296 } else {
297 return (ISC_R_SUCCESS);
298 }
299 }
300
301 isc_result_t
isc_radix_insert(isc_radix_tree_t * radix,isc_radix_node_t ** target,isc_radix_node_t * source,isc_prefix_t * prefix)302 isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target,
303 isc_radix_node_t *source, isc_prefix_t *prefix)
304 {
305 isc_radix_node_t *node, *new_node, *parent, *glue = NULL;
306 u_char *addr, *test_addr;
307 isc_uint32_t bitlen, fam, check_bit, differ_bit;
308 isc_uint32_t i, j, r;
309 isc_result_t result;
310
311 REQUIRE(radix != NULL);
312 REQUIRE(target != NULL && *target == NULL);
313 REQUIRE(prefix != NULL || (source != NULL && source->prefix != NULL));
314 RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits);
315
316 if (prefix == NULL)
317 prefix = source->prefix;
318
319 INSIST(prefix != NULL);
320
321 bitlen = prefix->bitlen;
322 fam = prefix->family;
323
324 if (radix->head == NULL) {
325 node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
326 if (node == NULL)
327 return (ISC_R_NOMEMORY);
328 node->bit = bitlen;
329 node->node_num[0] = node->node_num[1] = -1;
330 node->prefix = NULL;
331 result = _ref_prefix(radix->mctx, &node->prefix, prefix);
332 if (result != ISC_R_SUCCESS) {
333 isc_mem_put(radix->mctx, node,
334 sizeof(isc_radix_node_t));
335 return (result);
336 }
337 node->parent = NULL;
338 node->l = node->r = NULL;
339 if (source != NULL) {
340 /*
341 * If source is non-NULL, then we're merging in a
342 * node from an existing radix tree. To keep
343 * the node_num values consistent, the calling
344 * function will add the total number of nodes
345 * added to num_added_node at the end of
346 * the merge operation--we don't do it here.
347 */
348 if (source->node_num[0] != -1)
349 node->node_num[0] = radix->num_added_node +
350 source->node_num[0];
351 if (source->node_num[1] != -1)
352 node->node_num[1] = radix->num_added_node +
353 source->node_num[1];
354 node->data[0] = source->data[0];
355 node->data[1] = source->data[1];
356 } else {
357 if (fam == AF_UNSPEC) {
358 /* "any" or "none" */
359 node->node_num[0] = node->node_num[1] =
360 ++radix->num_added_node;
361 } else {
362 node->node_num[ISC_IS6(fam)] =
363 ++radix->num_added_node;
364 }
365 node->data[0] = NULL;
366 node->data[1] = NULL;
367 }
368 radix->head = node;
369 radix->num_active_node++;
370 *target = node;
371 return (ISC_R_SUCCESS);
372 }
373
374 addr = isc_prefix_touchar(prefix);
375 node = radix->head;
376
377 while (node->bit < bitlen || node->prefix == NULL) {
378 if (node->bit < radix->maxbits &&
379 BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
380 {
381 if (node->r == NULL)
382 break;
383 node = node->r;
384 } else {
385 if (node->l == NULL)
386 break;
387 node = node->l;
388 }
389
390 INSIST(node != NULL);
391 }
392
393 INSIST(node->prefix != NULL);
394
395 test_addr = isc_prefix_touchar(node->prefix);
396 /* Find the first bit different. */
397 check_bit = (node->bit < bitlen) ? node->bit : bitlen;
398 differ_bit = 0;
399 for (i = 0; i*8 < check_bit; i++) {
400 if ((r = (addr[i] ^ test_addr[i])) == 0) {
401 differ_bit = (i + 1) * 8;
402 continue;
403 }
404 /* I know the better way, but for now. */
405 for (j = 0; j < 8; j++) {
406 if (BIT_TEST (r, (0x80 >> j)))
407 break;
408 }
409 /* Must be found. */
410 INSIST(j < 8);
411 differ_bit = i * 8 + j;
412 break;
413 }
414
415 if (differ_bit > check_bit)
416 differ_bit = check_bit;
417
418 parent = node->parent;
419 while (parent != NULL && parent->bit >= differ_bit) {
420 node = parent;
421 parent = node->parent;
422 }
423
424 if (differ_bit == bitlen && node->bit == bitlen) {
425 if (node->prefix != NULL) {
426 /* Set node_num only if it hasn't been set before */
427 if (source != NULL) {
428 /* Merging node */
429 if (node->node_num[0] == -1 &&
430 source->node_num[0] != -1) {
431 node->node_num[0] =
432 radix->num_added_node +
433 source->node_num[0];
434 node->data[0] = source->data[0];
435 }
436 if (node->node_num[1] == -1 &&
437 source->node_num[0] != -1) {
438 node->node_num[1] =
439 radix->num_added_node +
440 source->node_num[1];
441 node->data[1] = source->data[1];
442 }
443 } else {
444 if (fam == AF_UNSPEC) {
445 /* "any" or "none" */
446 int next = radix->num_added_node + 1;
447 if (node->node_num[0] == -1) {
448 node->node_num[0] = next;
449 radix->num_added_node = next;
450 }
451 if (node->node_num[1] == -1) {
452 node->node_num[1] = next;
453 radix->num_added_node = next;
454 }
455 } else {
456 if (node->node_num[ISC_IS6(fam)] == -1)
457 node->node_num[ISC_IS6(fam)]
458 = ++radix->num_added_node;
459 }
460 }
461 *target = node;
462 return (ISC_R_SUCCESS);
463 } else {
464 result =
465 _ref_prefix(radix->mctx, &node->prefix, prefix);
466 if (result != ISC_R_SUCCESS)
467 return (result);
468 }
469 INSIST(node->data[0] == NULL && node->node_num[0] == -1 &&
470 node->data[1] == NULL && node->node_num[1] == -1);
471 if (source != NULL) {
472 /* Merging node */
473 if (source->node_num[0] != -1) {
474 node->node_num[0] = radix->num_added_node +
475 source->node_num[0];
476 node->data[0] = source->data[0];
477 }
478 if (source->node_num[1] != -1) {
479 node->node_num[1] = radix->num_added_node +
480 source->node_num[1];
481 node->data[1] = source->data[1];
482 }
483 } else {
484 if (fam == AF_UNSPEC) {
485 /* "any" or "none" */
486 node->node_num[0] = node->node_num[1] =
487 ++radix->num_added_node;
488 } else {
489 node->node_num[ISC_IS6(fam)] =
490 ++radix->num_added_node;
491 }
492 }
493 *target = node;
494 return (ISC_R_SUCCESS);
495 }
496
497 new_node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
498 if (new_node == NULL)
499 return (ISC_R_NOMEMORY);
500 if (node->bit != differ_bit && bitlen != differ_bit) {
501 glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
502 if (glue == NULL) {
503 isc_mem_put(radix->mctx, new_node,
504 sizeof(isc_radix_node_t));
505 return (ISC_R_NOMEMORY);
506 }
507 }
508 new_node->bit = bitlen;
509 new_node->prefix = NULL;
510 result = _ref_prefix(radix->mctx, &new_node->prefix, prefix);
511 if (result != ISC_R_SUCCESS) {
512 isc_mem_put(radix->mctx, new_node, sizeof(isc_radix_node_t));
513 if (glue != NULL)
514 isc_mem_put(radix->mctx, glue,
515 sizeof(isc_radix_node_t));
516 return (result);
517 }
518 new_node->parent = NULL;
519 new_node->l = new_node->r = NULL;
520 new_node->node_num[0] = new_node->node_num[1] = -1;
521 radix->num_active_node++;
522
523 if (source != NULL) {
524 /* Merging node */
525 if (source->node_num[0] != -1)
526 new_node->node_num[0] = radix->num_added_node +
527 source->node_num[0];
528 if (source->node_num[1] != -1)
529 new_node->node_num[1] = radix->num_added_node +
530 source->node_num[1];
531 new_node->data[0] = source->data[0];
532 new_node->data[1] = source->data[1];
533 } else {
534 if (fam == AF_UNSPEC) {
535 /* "any" or "none" */
536 new_node->node_num[0] = new_node->node_num[1] =
537 ++radix->num_added_node;
538 } else {
539 new_node->node_num[ISC_IS6(fam)] =
540 ++radix->num_added_node;
541 }
542 new_node->data[0] = NULL;
543 new_node->data[1] = NULL;
544 }
545
546 if (node->bit == differ_bit) {
547 INSIST(glue == NULL);
548 new_node->parent = node;
549 if (node->bit < radix->maxbits &&
550 BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
551 {
552 INSIST(node->r == NULL);
553 node->r = new_node;
554 } else {
555 INSIST(node->l == NULL);
556 node->l = new_node;
557 }
558 *target = new_node;
559 return (ISC_R_SUCCESS);
560 }
561
562 if (bitlen == differ_bit) {
563 INSIST(glue == NULL);
564 if (bitlen < radix->maxbits &&
565 BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) {
566 new_node->r = node;
567 } else {
568 new_node->l = node;
569 }
570 new_node->parent = node->parent;
571 if (node->parent == NULL) {
572 INSIST(radix->head == node);
573 radix->head = new_node;
574 } else if (node->parent->r == node) {
575 node->parent->r = new_node;
576 } else {
577 node->parent->l = new_node;
578 }
579 node->parent = new_node;
580 } else {
581 INSIST(glue != NULL);
582 glue->bit = differ_bit;
583 glue->prefix = NULL;
584 glue->parent = node->parent;
585 glue->data[0] = glue->data[1] = NULL;
586 glue->node_num[0] = glue->node_num[1] = -1;
587 radix->num_active_node++;
588 if (differ_bit < radix->maxbits &&
589 BIT_TEST(addr[differ_bit>>3], 0x80 >> (differ_bit & 07))) {
590 glue->r = new_node;
591 glue->l = node;
592 } else {
593 glue->r = node;
594 glue->l = new_node;
595 }
596 new_node->parent = glue;
597
598 if (node->parent == NULL) {
599 INSIST(radix->head == node);
600 radix->head = glue;
601 } else if (node->parent->r == node) {
602 node->parent->r = glue;
603 } else {
604 node->parent->l = glue;
605 }
606 node->parent = glue;
607 }
608
609 *target = new_node;
610 return (ISC_R_SUCCESS);
611 }
612
613 void
isc_radix_remove(isc_radix_tree_t * radix,isc_radix_node_t * node)614 isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) {
615 isc_radix_node_t *parent, *child;
616
617 REQUIRE(radix != NULL);
618 REQUIRE(node != NULL);
619
620 if (node->r && node->l) {
621 /*
622 * This might be a placeholder node -- have to check and
623 * make sure there is a prefix associated with it!
624 */
625 if (node->prefix != NULL)
626 _deref_prefix(radix->mctx, node->prefix);
627
628 node->prefix = NULL;
629 node->data[0] = node->data[1] = NULL;
630 return;
631 }
632
633 if (node->r == NULL && node->l == NULL) {
634 parent = node->parent;
635 _deref_prefix(radix->mctx, node->prefix);
636 isc_mem_put(radix->mctx, node, sizeof(*node));
637 radix->num_active_node--;
638
639 if (parent == NULL) {
640 INSIST(radix->head == node);
641 radix->head = NULL;
642 return;
643 }
644
645 if (parent->r == node) {
646 parent->r = NULL;
647 child = parent->l;
648 } else {
649 INSIST(parent->l == node);
650 parent->l = NULL;
651 child = parent->r;
652 }
653
654 if (parent->prefix)
655 return;
656
657 /* We need to remove parent too. */
658
659 if (parent->parent == NULL) {
660 INSIST(radix->head == parent);
661 radix->head = child;
662 } else if (parent->parent->r == parent) {
663 parent->parent->r = child;
664 } else {
665 INSIST(parent->parent->l == parent);
666 parent->parent->l = child;
667 }
668 child->parent = parent->parent;
669 isc_mem_put(radix->mctx, parent, sizeof(*parent));
670 radix->num_active_node--;
671 return;
672 }
673
674 if (node->r) {
675 child = node->r;
676 } else {
677 INSIST(node->l != NULL);
678 child = node->l;
679 }
680 parent = node->parent;
681 child->parent = parent;
682
683 _deref_prefix(radix->mctx, node->prefix);
684 isc_mem_put(radix->mctx, node, sizeof(*node));
685 radix->num_active_node--;
686
687 if (parent == NULL) {
688 INSIST(radix->head == node);
689 radix->head = child;
690 return;
691 }
692
693 if (parent->r == node) {
694 parent->r = child;
695 } else {
696 INSIST(parent->l == node);
697 parent->l = child;
698 }
699 }
700
701 /*
702 Local Variables:
703 c-basic-offset: 4
704 indent-tabs-mode: t
705 End:
706 */
707