1: /*
2: * Copyright (C) 2007-2009 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: radix.c,v 1.1.1.1 2012/05/29 12:08:38 misho Exp $ */
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
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
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
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
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
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
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
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
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
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
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
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: */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to radix.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / ntp / lib / isc