"SfR Fresh" - the SfR Freeware/Shareware Archive 
Member "mod-cband-0.9.7.5/src/libpatricia.c" of archive mod-cband-0.9.7.5.tgz:
As a special service "SfR Fresh" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting with prefixed line numbers.
Alternatively you can here view or download the uninterpreted source code file.
That can be also achieved for any archive member file by clicking within an archive contents listing on the first character of the file(path) respectively on the according byte size field.
1 /*
2 * Dave Plonka <plonka@doit.wisc.edu>
3 *
4 * This product includes software developed by the University of Michigan,
5 * Merit Network, Inc., and their contributors.
6 *
7 * This file had been called "radix.c" in the MRT sources.
8 *
9 * I renamed it to "patricia.c" since it's not an implementation of a general
10 * radix trie. Also I pulled in various requirements from "prefix.c" and
11 * "demo.c" so that it could be used as a standalone API.
12 */
13
14 /*
15 static char copyright[] =
16 "This product includes software developed by the University of Michigan, Merit"
17 "Network, Inc., and their contributors.";
18 */
19
20 #ifndef _PATRICIA_H
21 #define _PATRICIA_H
22
23 /* typedef unsigned int u_int; */
24 typedef void (*void_fn_t)();
25 /* { from defs.h */
26 #define prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin)
27 #define MAXLINE 1024
28 #define BIT_TEST(f, b) ((f) & (b))
29 /* } */
30
31 #define addroute make_and_lookup
32
33 #include <netinet/in.h> /* for struct in_addr */
34
35 #include <sys/socket.h> /* for AF_INET */
36
37 /* { from mrt.h */
38
39 typedef struct _prefix4_t {
40 u_short family; /* AF_INET | AF_INET6 */
41 u_short bitlen; /* same as mask? */
42 int ref_count; /* reference count */
43 struct in_addr sin;
44 } prefix4_t;
45
46 typedef struct _prefix_t {
47 u_short family; /* AF_INET | AF_INET6 */
48 u_short bitlen; /* same as mask? */
49 int ref_count; /* reference count */
50 union {
51 struct in_addr sin;
52 #ifdef HAVE_IPV6
53 struct in6_addr sin6;
54 #endif /* IPV6 */
55 } add;
56 } prefix_t;
57
58 /* } */
59
60 typedef struct _patricia_node_t {
61 u_int bit; /* flag if this node used */
62 prefix_t *prefix; /* who we are in patricia tree */
63 struct _patricia_node_t *l, *r; /* left and right children */
64 struct _patricia_node_t *parent;/* may be used */
65 void *data; /* pointer to data */
66 void *user1; /* pointer to usr data (ex. route flap info) */
67 } patricia_node_t;
68
69 typedef struct _patricia_tree_t {
70 patricia_node_t *head;
71 u_int maxbits; /* for IP, 32 bit addresses */
72 int num_active_node; /* for debug purpose */
73 } patricia_tree_t;
74
75
76 patricia_node_t *patricia_search_best (patricia_tree_t *patricia, prefix_t *prefix);
77 patricia_node_t * patricia_search_best2 (patricia_tree_t *patricia, prefix_t *prefix,
78 int inclusive);
79 patricia_node_t *patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix);
80 void patricia_remove (patricia_tree_t *patricia, patricia_node_t *node);
81 patricia_tree_t *New_Patricia (int maxbits);
82 void Clear_Patricia (patricia_tree_t *patricia, void_fn_t func);
83 void Destroy_Patricia (patricia_tree_t *patricia, void_fn_t func);
84 void patricia_process (patricia_tree_t *patricia, void_fn_t func);
85
86 /* { from demo.c */
87
88 prefix_t *
89 ascii2prefix (int family, char *string);
90
91 patricia_node_t *
92 make_and_lookup (patricia_tree_t *tree, char *string);
93
94 /* } */
95
96 #define PATRICIA_MAXBITS 128
97 #define PATRICIA_NBIT(x) (0x80 >> ((x) & 0x7f))
98 #define PATRICIA_NBYTE(x) ((x) >> 3)
99
100 #define PATRICIA_DATA_GET(node, type) (type *)((node)->data)
101 #define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))
102
103
104 #endif /* _PATRICIA_H */
105
106
107
108
109 #include <assert.h> /* assert */
110 #include <ctype.h> /* isdigit */
111 #include <errno.h> /* errno */
112 #include <math.h> /* sin */
113 #include <stddef.h> /* NULL */
114 #include <stdio.h> /* sprintf, fprintf, stderr */
115 #include <stdlib.h> /* free, atol, calloc */
116 #include <string.h> /* memcpy, strchr, strlen */
117 #include <arpa/inet.h> /* for inet_addr */
118
119
120 #define Delete free
121
122 /* { from prefix.c */
123
124 /* prefix_tochar
125 * convert prefix information to bytes
126 */
127 u_char *
128 prefix_tochar (prefix_t * prefix)
129 {
130 if (prefix == NULL)
131 return (NULL);
132
133 return ((u_char *) & prefix->add.sin);
134 }
135
136 int
137 comp_with_mask (void *addr, void *dest, u_int mask)
138 {
139
140 if ( /* mask/8 == 0 || */ memcmp (addr, dest, mask / 8) == 0) {
141 int n = mask / 8;
142 int m = ((-1) << (8 - (mask % 8)));
143
144 if (mask % 8 == 0 || (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m))
145 return (1);
146 }
147 return (0);
148 }
149
150 /* inet_pton substitute implementation
151 * Uses inet_addr to convert an IP address in dotted decimal notation into
152 * unsigned long and copies the result to dst.
153 * Only supports AF_INET. Follows standard error return conventions of
154 * inet_pton.
155 */
156 int
157 inet_pton (int af, const char *src, void *dst)
158 {
159 u_long result;
160
161 if (af == AF_INET) {
162 result = inet_addr(src);
163 if (result == -1)
164 return 0;
165 else {
166 memcpy (dst, &result, 4);
167 return 1;
168 }
169 }
170 #ifdef NT
171 #ifdef HAVE_IPV6
172 else if (af == AF_INET6) {
173 struct in6_addr Address;
174 return (inet6_addr(src, &Address));
175 }
176 #endif /* HAVE_IPV6 */
177 #endif /* NT */
178 #ifndef NT
179 else {
180
181 errno = EAFNOSUPPORT;
182 return -1;
183 }
184 #endif /* NT */
185 }
186
187 /* this allows imcomplete prefix */
188 int
189 my_inet_pton (int af, const char *src, void *dst)
190 {
191 if (af == AF_INET) {
192 int i, c, val;
193 u_char xp[4] = {0, 0, 0, 0};
194
195 for (i = 0; ; i++) {
196 c = *src++;
197 if (!isdigit (c))
198 return (-1);
199 val = 0;
200 do {
201 val = val * 10 + c - '0';
202 if (val > 255)
203 return (0);
204 c = *src++;
205 } while (c && isdigit (c));
206 xp[i] = val;
207 if (c == '\0')
208 break;
209 if (c != '.')
210 return (0);
211 if (i >= 3)
212 return (0);
213 }
214 memcpy (dst, xp, 4);
215 return (1);
216 #ifdef HAVE_IPV6
217 } else if (af == AF_INET6) {
218 return (inet_pton (af, src, dst));
219 #endif /* HAVE_IPV6 */
220 } else {
221 #ifndef NT
222 errno = EAFNOSUPPORT;
223 #endif /* NT */
224 return -1;
225 }
226 }
227
228 /*
229 * convert prefix information to ascii string with length
230 * thread safe and (almost) re-entrant implementation
231 */
232
233 prefix_t *
234 New_Prefix2 (int family, void *dest, int bitlen, prefix_t *prefix)
235 {
236 int dynamic_allocated = 0;
237 int default_bitlen = 32;
238
239 #ifdef HAVE_IPV6
240 if (family == AF_INET6) {
241 default_bitlen = 128;
242 if (prefix == NULL) {
243 prefix = calloc(1, sizeof (prefix6_t));
244 dynamic_allocated++;
245 }
246 memcpy (&prefix->add.sin6, dest, 16);
247 }
248 else
249 #endif /* HAVE_IPV6 */
250 if (family == AF_INET) {
251 if (prefix == NULL) {
252 #ifndef NT
253 prefix = calloc(1, sizeof (prefix4_t));
254 #else
255 //for some reason, compiler is getting
256 //prefix4_t size incorrect on NT
257 prefix = calloc(1, sizeof (prefix_t));
258 #endif /* NT */
259
260 dynamic_allocated++;
261 }
262 memcpy (&prefix->add.sin, dest, 4);
263 }
264 else {
265 return (NULL);
266 }
267
268 prefix->bitlen = (bitlen >= 0)? bitlen: default_bitlen;
269 prefix->family = family;
270 prefix->ref_count = 0;
271 if (dynamic_allocated) {
272 prefix->ref_count++;
273 }
274 /* fprintf(stderr, "[C %s, %d]\n", prefix_toa (prefix), prefix->ref_count); */
275 return (prefix);
276 }
277
278 prefix_t *
279 New_Prefix (int family, void *dest, int bitlen)
280 {
281 return (New_Prefix2 (family, dest, bitlen, NULL));
282 }
283
284 /* ascii2prefix
285 */
286 prefix_t *
287 ascii2prefix (int family, char *string)
288 {
289 u_long bitlen, maxbitlen = 0;
290 char *cp;
291 struct in_addr sin;
292 #ifdef HAVE_IPV6
293 struct in6_addr sin6;
294 #endif /* HAVE_IPV6 */
295 int result;
296 char save[MAXLINE];
297
298 if (string == NULL)
299 return (NULL);
300
301 /* easy way to handle both families */
302 if (family == 0) {
303 family = AF_INET;
304 #ifdef HAVE_IPV6
305 if (strchr (string, ':')) family = AF_INET6;
306 #endif /* HAVE_IPV6 */
307 }
308
309 if (family == AF_INET) {
310 maxbitlen = 32;
311 }
312 #ifdef HAVE_IPV6
313 else if (family == AF_INET6) {
314 maxbitlen = 128;
315 }
316 #endif /* HAVE_IPV6 */
317
318 if ((cp = strchr (string, '/')) != NULL) {
319 bitlen = atol (cp + 1);
320 /* *cp = '\0'; */
321 /* copy the string to save. Avoid destroying the string */
322 assert (cp - string < MAXLINE);
323 memcpy (save, string, cp - string);
324 save[cp - string] = '\0';
325 string = save;
326 if (bitlen < 0 || bitlen > maxbitlen)
327 bitlen = maxbitlen;
328 }
329 else {
330 bitlen = maxbitlen;
331 }
332
333 if (family == AF_INET) {
334 if ((result = my_inet_pton (AF_INET, string, &sin)) <= 0)
335 return (NULL);
336 return (New_Prefix (AF_INET, &sin, bitlen));
337 }
338
339 #ifdef HAVE_IPV6
340 else if (family == AF_INET6) {
341 // Get rid of this with next IPv6 upgrade
342 #if defined(NT) && !defined(HAVE_INET_NTOP)
343 inet6_addr(string, &sin6);
344 return (New_Prefix (AF_INET6, &sin6, bitlen));
345 #else
346 if ((result = inet_pton (AF_INET6, string, &sin6)) <= 0)
347 return (NULL);
348 #endif /* NT */
349 return (New_Prefix (AF_INET6, &sin6, bitlen));
350 }
351 #endif /* HAVE_IPV6 */
352 else
353 return (NULL);
354 }
355
356 prefix_t *
357 Ref_Prefix (prefix_t * prefix)
358 {
359 if (prefix == NULL)
360 return (NULL);
361 if (prefix->ref_count == 0) {
362 /* make a copy in case of a static prefix */
363 return (New_Prefix2 (prefix->family, &prefix->add, prefix->bitlen, NULL));
364 }
365 prefix->ref_count++;
366 /* fprintf(stderr, "[A %s, %d]\n", prefix_toa (prefix), prefix->ref_count); */
367 return (prefix);
368 }
369
370 void
371 Deref_Prefix (prefix_t * prefix)
372 {
373 if (prefix == NULL)
374 return;
375 /* for secure programming, raise an assert. no static prefix can call this */
376 assert (prefix->ref_count > 0);
377
378 prefix->ref_count--;
379 assert (prefix->ref_count >= 0);
380 if (prefix->ref_count <= 0) {
381 Delete (prefix);
382 return;
383 }
384 }
385
386 /* } */
387
388 /* #define PATRICIA_DEBUG 1 */
389
390 static int num_active_patricia = 0;
391
392 /* these routines support continuous mask only */
393
394 patricia_tree_t *
395 New_Patricia (int maxbits)
396 {
397 patricia_tree_t *patricia = calloc(1, sizeof *patricia);
398
399 patricia->maxbits = maxbits;
400 patricia->head = NULL;
401 patricia->num_active_node = 0;
402 assert (maxbits <= PATRICIA_MAXBITS); /* XXX */
403 num_active_patricia++;
404 return (patricia);
405 }
406
407
408 /*
409 * if func is supplied, it will be called as func(node->data)
410 * before deleting the node
411 */
412
413 void
414 Clear_Patricia (patricia_tree_t *patricia, void_fn_t func)
415 {
416 assert (patricia);
417 if (patricia->head) {
418
419 patricia_node_t *Xstack[PATRICIA_MAXBITS+1];
420 patricia_node_t **Xsp = Xstack;
421 patricia_node_t *Xrn = patricia->head;
422
423 while (Xrn) {
424 patricia_node_t *l = Xrn->l;
425 patricia_node_t *r = Xrn->r;
426
427 if (Xrn->prefix) {
428 Deref_Prefix (Xrn->prefix);
429 if (Xrn->data && func)
430 func (Xrn->data);
431 }
432 else {
433 assert (Xrn->data == NULL);
434 }
435 Delete (Xrn);
436 patricia->num_active_node--;
437
438 if (l) {
439 if (r) {
440 *Xsp++ = r;
441 }
442 Xrn = l;
443 } else if (r) {
444 Xrn = r;
445 } else if (Xsp != Xstack) {
446 Xrn = *(--Xsp);
447 } else {
448 Xrn = (patricia_node_t *) 0;
449 }
450 }
451 }
452 assert (patricia->num_active_node == 0);
453 Delete (patricia);
454 }
455
456
457 void
458 Destroy_Patricia (patricia_tree_t *patricia, void_fn_t func)
459 {
460 Clear_Patricia (patricia, func);
461 Delete (patricia);
462 num_active_patricia--;
463 }
464
465
466 /*
467 * if func is supplied, it will be called as func(node->prefix, node->data)
468 */
469
470
471
472
473
474 /* if inclusive != 0, "best" may be the given prefix itself */
475 patricia_node_t *
476 patricia_search_best2 (patricia_tree_t *patricia, prefix_t *prefix, int inclusive)
477 {
478 patricia_node_t *node;
479 patricia_node_t *stack[PATRICIA_MAXBITS + 1];
480 u_char *addr;
481 u_int bitlen;
482 int cnt = 0;
483
484 assert (patricia);
485 assert (prefix);
486 assert (prefix->bitlen <= patricia->maxbits);
487
488 if (patricia->head == NULL)
489 return (NULL);
490
491 node = patricia->head;
492 addr = prefix_touchar (prefix);
493 bitlen = prefix->bitlen;
494
495 while (node->bit < bitlen) {
496
497 if (node->prefix) {
498 stack[cnt++] = node;
499 }
500
501 if (BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
502 node = node->r;
503 }
504 else {
505 node = node->l;
506 }
507
508 if (node == NULL)
509 break;
510 }
511
512 if (inclusive && node && node->prefix)
513 stack[cnt++] = node;
514
515 if (cnt <= 0)
516 return (NULL);
517
518 while (--cnt >= 0) {
519 node = stack[cnt];
520 if (comp_with_mask (prefix_tochar (node->prefix),
521 prefix_tochar (prefix),
522 node->prefix->bitlen)) {
523 return (node);
524 }
525 }
526 return (NULL);
527 }
528
529
530 patricia_node_t *
531 patricia_search_best (patricia_tree_t *patricia, prefix_t *prefix)
532 {
533 return (patricia_search_best2 (patricia, prefix, 1));
534 }
535
536
537 patricia_node_t *
538 patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix)
539 {
540 patricia_node_t *node, *new_node, *parent, *glue;
541 u_char *addr, *test_addr;
542 u_int bitlen, check_bit, differ_bit;
543 int i, j, r;
544
545 assert (patricia);
546 assert (prefix);
547 assert (prefix->bitlen <= patricia->maxbits);
548
549 if (patricia->head == NULL) {
550 node = calloc(1, sizeof *node);
551 node->bit = prefix->bitlen;
552 node->prefix = Ref_Prefix (prefix);
553 node->parent = NULL;
554 node->l = node->r = NULL;
555 node->data = NULL;
556 patricia->head = node;
557 patricia->num_active_node++;
558 return (node);
559 }
560
561 addr = prefix_touchar (prefix);
562 bitlen = prefix->bitlen;
563 node = patricia->head;
564
565 while (node->bit < bitlen || node->prefix == NULL) {
566
567 if (node->bit < patricia->maxbits &&
568 BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
569 if (node->r == NULL)
570 break;
571 node = node->r;
572 }
573 else {
574 if (node->l == NULL)
575 break;
576 node = node->l;
577 }
578
579 assert (node);
580 }
581
582 assert (node->prefix);
583
584 test_addr = prefix_touchar (node->prefix);
585 /* find the first bit different */
586 check_bit = (node->bit < bitlen)? node->bit: bitlen;
587 differ_bit = 0;
588 for (i = 0; i*8 < check_bit; i++) {
589 if ((r = (addr[i] ^ test_addr[i])) == 0) {
590 differ_bit = (i + 1) * 8;
591 continue;
592 }
593 /* I know the better way, but for now */
594 for (j = 0; j < 8; j++) {
595 if (BIT_TEST (r, (0x80 >> j)))
596 break;
597 }
598 /* must be found */
599 assert (j < 8);
600 differ_bit = i * 8 + j;
601 break;
602 }
603 if (differ_bit > check_bit)
604 differ_bit = check_bit;
605
606 parent = node->parent;
607 while (parent && parent->bit >= differ_bit) {
608 node = parent;
609 parent = node->parent;
610 }
611
612 if (differ_bit == bitlen && node->bit == bitlen) {
613 if (node->prefix) {
614 return (node);
615 }
616 node->prefix = Ref_Prefix (prefix);
617 assert (node->data == NULL);
618 return (node);
619 }
620
621 new_node = calloc(1, sizeof *new_node);
622 new_node->bit = prefix->bitlen;
623 new_node->prefix = Ref_Prefix (prefix);
624 new_node->parent = NULL;
625 new_node->l = new_node->r = NULL;
626 new_node->data = NULL;
627 patricia->num_active_node++;
628
629 if (node->bit == differ_bit) {
630 new_node->parent = node;
631 if (node->bit < patricia->maxbits &&
632 BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
633 assert (node->r == NULL);
634 node->r = new_node;
635 }
636 else {
637 assert (node->l == NULL);
638 node->l = new_node;
639 }
640 return (new_node);
641 }
642
643 if (bitlen == differ_bit) {
644 if (bitlen < patricia->maxbits &&
645 BIT_TEST (test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) {
646 new_node->r = node;
647 }
648 else {
649 new_node->l = node;
650 }
651 new_node->parent = node->parent;
652 if (node->parent == NULL) {
653 assert (patricia->head == node);
654 patricia->head = new_node;
655 }
656 else if (node->parent->r == node) {
657 node->parent->r = new_node;
658 }
659 else {
660 node->parent->l = new_node;
661 }
662 node->parent = new_node;
663 }
664 else {
665 glue = calloc(1, sizeof *glue);
666 glue->bit = differ_bit;
667 glue->prefix = NULL;
668 glue->parent = node->parent;
669 glue->data = NULL;
670 patricia->num_active_node++;
671 if (differ_bit < patricia->maxbits &&
672 BIT_TEST (addr[differ_bit >> 3], 0x80 >> (differ_bit & 0x07))) {
673 glue->r = new_node;
674 glue->l = node;
675 }
676 else {
677 glue->r = node;
678 glue->l = new_node;
679 }
680 new_node->parent = glue;
681
682 if (node->parent == NULL) {
683 assert (patricia->head == node);
684 patricia->head = glue;
685 }
686 else if (node->parent->r == node) {
687 node->parent->r = glue;
688 }
689 else {
690 node->parent->l = glue;
691 }
692 node->parent = glue;
693 }
694 return (new_node);
695 }
696
697
698 void
699 patricia_remove (patricia_tree_t *patricia, patricia_node_t *node)
700 {
701 patricia_node_t *parent, *child;
702
703 assert (patricia);
704 assert (node);
705
706 if (node->r && node->l) {
707 /* this might be a placeholder node -- have to check and make sure
708 * there is a prefix aossciated with it ! */
709 if (node->prefix != NULL)
710 Deref_Prefix (node->prefix);
711 node->prefix = NULL;
712 /* Also I needed to clear data pointer -- masaki */
713 node->data = NULL;
714 return;
715 }
716
717 if (node->r == NULL && node->l == NULL) {
718 parent = node->parent;
719 Deref_Prefix (node->prefix);
720 Delete (node);
721 patricia->num_active_node--;
722
723 if (parent == NULL) {
724 assert (patricia->head == node);
725 patricia->head = NULL;
726 return;
727 }
728
729 if (parent->r == node) {
730 parent->r = NULL;
731 child = parent->l;
732 }
733 else {
734 assert (parent->l == node);
735 parent->l = NULL;
736 child = parent->r;
737 }
738
739 if (parent->prefix)
740 return;
741
742 /* we need to remove parent too */
743
744 if (parent->parent == NULL) {
745 assert (patricia->head == parent);
746 patricia->head = child;
747 }
748 else if (parent->parent->r == parent) {
749 parent->parent->r = child;
750 }
751 else {
752 assert (parent->parent->l == parent);
753 parent->parent->l = child;
754 }
755 child->parent = parent->parent;
756 Delete (parent);
757 patricia->num_active_node--;
758 return;
759 }
760
761 if (node->r) {
762 child = node->r;
763 }
764 else {
765 assert (node->l);
766 child = node->l;
767 }
768 parent = node->parent;
769 child->parent = parent;
770
771 Deref_Prefix (node->prefix);
772 Delete (node);
773 patricia->num_active_node--;
774
775 if (parent == NULL) {
776 assert (patricia->head == node);
777 patricia->head = child;
778 return;
779 }
780
781 if (parent->r == node) {
782 parent->r = child;
783 }
784 else {
785 assert (parent->l == node);
786 parent->l = child;
787 }
788 }
789
790 patricia_node_t *
791 make_and_lookup (patricia_tree_t *tree, char *string)
792 {
793 prefix_t *prefix;
794 patricia_node_t *node;
795
796 prefix = ascii2prefix (AF_INET, string);
797 node = patricia_lookup (tree, prefix);
798 Deref_Prefix (prefix);
799 return (node);
800 }
801
802