/[svn]/hopm/trunk/src/patricia.c
ViewVC logotype

Contents of /hopm/trunk/src/patricia.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 8753 - (show annotations)
Tue Jan 1 13:56:48 2019 UTC (21 months, 3 weeks ago) by michael
File MIME type: text/x-chdr
File size: 23620 byte(s)
- patricia: update to latest version from ircd-hybrid

1 /*
2 * $Id$
3 * Dave Plonka <plonka@doit.wisc.edu>
4 *
5 * This file had been called "radix.c" in the MRT sources.
6 *
7 * I renamed it to "patricia.c" since it's not an implementation of a general
8 * radix trie. Also I pulled in various requirements from "prefix.c" and
9 * "demo.c" so that it could be used as a standalone API.
10 *
11 * Copyright (c) 1999-2013
12 *
13 * The Regents of the University of Michigan ("The Regents") and Merit
14 * Network, Inc.
15 *
16 * Redistributions of source code must retain the above copyright notice,
17 * this list of conditions and the following disclaimer.
18 *
19 * Redistributions in binary form must reproduce the above copyright
20 * notice, this list of conditions and the following disclaimer in the
21 * documentation and/or other materials provided with the distribution.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
29 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
30 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
31 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
33 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 */
35
36 #include <assert.h> /* assert */
37 #include <stddef.h> /* NULL */
38 #include <stdio.h> /* sprintf, fprintf, stderr */
39 #include <stdlib.h> /* free, atol, calloc */
40 #include <string.h> /* memcpy, strchr, strlen */
41 #include <sys/types.h> /* BSD: for inet_addr */
42 #include <sys/socket.h> /* BSD, Linux: for inet_addr */
43 #include <netinet/in.h> /* BSD, Linux: for inet_addr */
44 #include <arpa/inet.h> /* BSD, Linux, Solaris: for inet_addr */
45
46 #include "patricia.h"
47 #include "memory.h"
48
49 /* { from prefix.c */
50
51 /* prefix_tochar
52 * convert prefix information to bytes
53 */
54 static unsigned char *
55 prefix_tochar(prefix_t *prefix)
56 {
57 if (prefix == NULL)
58 return NULL;
59 return (unsigned char *)&prefix->add.sin;
60 }
61
62 static int
63 comp_with_mask(void *addr, void *dest, unsigned int mask)
64 {
65 if ( /* mask/8 == 0 || */ memcmp(addr, dest, mask / 8) == 0)
66 {
67 int n = mask / 8;
68 int m = ~((1 << (8 - (mask % 8))) - 1);
69
70 if (mask % 8 == 0 || (((unsigned char *)addr)[n] & m) == (((unsigned char *)dest)[n] & m))
71 return 1;
72 }
73
74 return 0;
75 }
76
77 /*
78 * convert prefix information to ascii string with length
79 */
80 const char *
81 patricia_prefix_toa(const prefix_t *prefix, int with_len)
82 {
83 static char buf[INET6_ADDRSTRLEN + sizeof("/128")];
84
85 assert(prefix);
86 assert(prefix->ref_count >= 0);
87 assert((prefix->family == AF_INET && prefix->bitlen <= 32) ||
88 (prefix->family == AF_INET6 && prefix->bitlen <= 128));
89
90 inet_ntop(prefix->family, &prefix->add.sin6, buf, INET6_ADDRSTRLEN);
91
92 if (with_len)
93 sprintf(buf + strlen(buf), "/%d", prefix->bitlen);
94 return buf;
95 }
96
97 static prefix_t *
98 New_Prefix2(int family, void *dest, int bitlen, prefix_t *prefix)
99 {
100 int dynamic_allocated = 0;
101 int addr_size = 0;
102
103 switch (family)
104 {
105 case AF_INET:
106 addr_size = sizeof(struct in_addr);
107 break;
108 case AF_INET6:
109 addr_size = sizeof(struct in6_addr);
110 break;
111 default: return NULL;
112 }
113
114 if (prefix == NULL)
115 {
116 prefix = xcalloc(sizeof(*prefix));
117 dynamic_allocated = 1;
118 }
119
120 memcpy(&prefix->add.sin6, dest, addr_size);
121 prefix->bitlen = (bitlen >= 0) ? bitlen : addr_size * 8;
122 prefix->family = family;
123 prefix->ref_count = dynamic_allocated == 1;
124
125 /* fprintf(stderr, "[C %s, %d]\n", patricia_prefix_toa(prefix), prefix->ref_count); */
126 return prefix;
127 }
128
129 static prefix_t *
130 New_Prefix(int family, void *dest, int bitlen)
131 {
132 return New_Prefix2(family, dest, bitlen, NULL);
133 }
134
135 /* ascii2prefix
136 */
137 static prefix_t *
138 ascii2prefix(int family, const char *string)
139 {
140 char save[INET6_ADDRSTRLEN];
141 int bitlen, maxbitlen = 0;
142 union
143 {
144 struct in_addr sin;
145 struct in6_addr sin6;
146 } sin;
147
148 assert(string);
149
150 /* Easy way to handle both families */
151 if (family == 0)
152 {
153 family = AF_INET;
154
155 if (strchr(string, ':'))
156 family = AF_INET6;
157 }
158
159 if (family == AF_INET)
160 maxbitlen = sizeof(struct in_addr) * 8;
161 else if (family == AF_INET6)
162 maxbitlen = sizeof(struct in6_addr) * 8;
163
164 const char *const cp = strchr(string, '/');
165 if (cp)
166 {
167 size_t length = cp - string;
168
169 if (length >= sizeof(save))
170 return NULL;
171
172 bitlen = atoi(cp + 1);
173
174 /* Copy the string to save. Avoid destroying the string */
175 memcpy(save, string, length);
176 save[length] = '\0';
177
178 string = save;
179
180 if (bitlen < 0 || bitlen > maxbitlen)
181 bitlen = maxbitlen;
182 }
183 else
184 bitlen = maxbitlen;
185
186 if (inet_pton(family, string, &sin) <= 0)
187 return NULL;
188 return New_Prefix(family, &sin, bitlen);
189 }
190
191 static prefix_t *
192 Ref_Prefix(prefix_t *prefix)
193 {
194 if (prefix == NULL)
195 return NULL;
196
197 if (prefix->ref_count == 0)
198 /* Make a copy in case of a static prefix */
199 return New_Prefix2(prefix->family, &prefix->add, prefix->bitlen, NULL);
200
201 prefix->ref_count++;
202
203 /* fprintf(stderr, "[A %s, %d]\n", patricia_prefix_toa(prefix), prefix->ref_count); */
204 return prefix;
205 }
206
207 static void
208 Deref_Prefix(prefix_t *prefix)
209 {
210 if (prefix == NULL)
211 return;
212
213 /* For secure programming, raise an assert. No static prefix can call this */
214 assert(prefix->ref_count > 0);
215 if (--prefix->ref_count <= 0)
216 xfree(prefix);
217 }
218 /* } */
219
220 /* #define PATRICIA_DEBUG 1 */
221
222 /* these routines support continuous mask only */
223
224 patricia_tree_t *
225 patricia_new(unsigned int maxbits)
226 {
227 patricia_tree_t *patricia = xcalloc(sizeof(*patricia));
228 patricia->maxbits = maxbits;
229
230 assert(maxbits <= PATRICIA_MAXBITS); /* XXX */
231 return patricia;
232 }
233
234 /*
235 * if func is supplied, it will be called as func(node->data)
236 * before deleting the node
237 */
238 void
239 patricia_clear(patricia_tree_t *patricia, void (*func)(void *))
240 {
241 assert(patricia);
242
243 if (patricia->head)
244 {
245 patricia_node_t *Xstack[PATRICIA_MAXBITS + 1];
246 patricia_node_t **Xsp = Xstack;
247 patricia_node_t *Xrn = patricia->head;
248
249 while (Xrn)
250 {
251 patricia_node_t *l = Xrn->l;
252 patricia_node_t *r = Xrn->r;
253
254 if (Xrn->prefix)
255 {
256 Deref_Prefix(Xrn->prefix);
257
258 if (Xrn->data && func)
259 func(Xrn->data);
260 }
261 else
262 {
263 assert(Xrn->data == NULL);
264 }
265
266 xfree(Xrn);
267 patricia->num_active_node--;
268
269 if (l)
270 {
271 if (r)
272 {
273 *Xsp++ = r;
274 }
275
276 Xrn = l;
277 }
278 else if (r)
279 {
280 Xrn = r;
281 }
282 else if (Xsp != Xstack)
283 {
284 Xrn = *(--Xsp);
285 }
286 else
287 {
288 Xrn = NULL;
289 }
290 }
291 }
292
293 patricia->head = NULL;
294
295 assert(patricia->num_active_node == 0);
296 }
297
298 void
299 patricia_destroy(patricia_tree_t *patricia, void (*func)(void *))
300 {
301 patricia_clear(patricia, func);
302 xfree(patricia);
303 }
304
305 /*
306 * if func is supplied, it will be called as func(node->prefix, node->data)
307 */
308 void
309 patricia_process(patricia_tree_t *patricia, void (*func)(prefix_t *, void *))
310 {
311 patricia_node_t *node;
312
313 assert(func);
314
315 PATRICIA_WALK(patricia->head, node) {
316 func(node->prefix, node->data);
317 } PATRICIA_WALK_END;
318 }
319
320 patricia_node_t *
321 patricia_search_exact(patricia_tree_t *patricia, prefix_t *prefix)
322 {
323 patricia_node_t *node;
324 unsigned char *addr;
325 unsigned int bitlen;
326
327 assert(patricia);
328 assert(prefix);
329 assert(prefix->bitlen <= patricia->maxbits);
330
331 if (patricia->head == NULL)
332 return NULL;
333
334 node = patricia->head;
335 addr = prefix_touchar(prefix);
336 bitlen = prefix->bitlen;
337
338 while (node->bit < bitlen)
339 {
340 if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
341 {
342 #ifdef PATRICIA_DEBUG
343 if (node->prefix)
344 fprintf(stderr, "patricia_search_exact: take right %s/%d\n",
345 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
346 else
347 fprintf(stderr, "patricia_search_exact: take right at %u\n", node->bit);
348 #endif /* PATRICIA_DEBUG */
349 node = node->r;
350 }
351 else
352 {
353 #ifdef PATRICIA_DEBUG
354 if (node->prefix)
355 fprintf(stderr, "patricia_search_exact: take left %s/%d\n",
356 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
357 else
358 fprintf(stderr, "patricia_search_exact: take left at %u\n", node->bit);
359 #endif /* PATRICIA_DEBUG */
360 node = node->l;
361 }
362
363 if (node == NULL)
364 return NULL;
365 }
366
367 #ifdef PATRICIA_DEBUG
368 if (node->prefix)
369 fprintf(stderr, "patricia_search_exact: stop at %s/%d\n",
370 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
371 else
372 fprintf(stderr, "patricia_search_exact: stop at %u\n", node->bit);
373 #endif /* PATRICIA_DEBUG */
374
375 if (node->bit > bitlen || node->prefix == NULL)
376 return NULL;
377
378 assert(node->bit == bitlen);
379 assert(node->bit == node->prefix->bitlen);
380
381 if (comp_with_mask(prefix_tochar(node->prefix), prefix_tochar(prefix), bitlen))
382 {
383 #ifdef PATRICIA_DEBUG
384 fprintf(stderr, "patricia_search_exact: found %s/%d\n",
385 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
386 #endif /* PATRICIA_DEBUG */
387 return node;
388 }
389
390 return NULL;
391 }
392
393 /* if inclusive != 0, "best" may be the given prefix itself */
394 patricia_node_t *
395 patricia_search_best2(patricia_tree_t *patricia, prefix_t *prefix, int inclusive)
396 {
397 patricia_node_t *node;
398 patricia_node_t *stack[PATRICIA_MAXBITS + 1];
399 unsigned char *addr;
400 unsigned int bitlen;
401 int cnt = 0;
402
403 assert(patricia);
404 assert(prefix);
405 assert(prefix->bitlen <= patricia->maxbits);
406
407 if (patricia->head == NULL)
408 return NULL;
409
410 node = patricia->head;
411 addr = prefix_touchar(prefix);
412 bitlen = prefix->bitlen;
413
414 while (node->bit < bitlen)
415 {
416 if (node->prefix)
417 {
418 #ifdef PATRICIA_DEBUG
419 fprintf(stderr, "patricia_search_best: push %s/%d\n",
420 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
421 #endif /* PATRICIA_DEBUG */
422 stack[cnt++] = node;
423 }
424
425 if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
426 {
427 #ifdef PATRICIA_DEBUG
428 if (node->prefix)
429 fprintf(stderr, "patricia_search_best: take right %s/%d\n",
430 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
431 else
432 fprintf(stderr, "patricia_search_best: take right at %u\n", node->bit);
433 #endif /* PATRICIA_DEBUG */
434 node = node->r;
435 }
436 else
437 {
438 #ifdef PATRICIA_DEBUG
439 if (node->prefix)
440 fprintf(stderr, "patricia_search_best: take left %s/%d\n",
441 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
442 else
443 fprintf(stderr, "patricia_search_best: take left at %u\n", node->bit);
444 #endif /* PATRICIA_DEBUG */
445 node = node->l;
446 }
447
448 if (node == NULL)
449 break;
450 }
451
452 if (inclusive && node && node->prefix)
453 stack[cnt++] = node;
454
455 #ifdef PATRICIA_DEBUG
456 if (node == NULL)
457 fprintf(stderr, "patricia_search_best: stop at null\n");
458 else if (node->prefix)
459 fprintf(stderr, "patricia_search_best: stop at %s/%d\n",
460 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
461 else
462 fprintf(stderr, "patricia_search_best: stop at %u\n", node->bit);
463 #endif /* PATRICIA_DEBUG */
464
465 if (cnt <= 0)
466 return NULL;
467
468 while (--cnt >= 0)
469 {
470 node = stack[cnt];
471 #ifdef PATRICIA_DEBUG
472 fprintf(stderr, "patricia_search_best: pop %s/%d\n",
473 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
474 #endif /* PATRICIA_DEBUG */
475
476 if (comp_with_mask(prefix_tochar(node->prefix),
477 prefix_tochar(prefix), node->prefix->bitlen) && node->prefix->bitlen <= bitlen)
478 {
479 #ifdef PATRICIA_DEBUG
480 fprintf(stderr, "patricia_search_best: found %s/%d\n",
481 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
482 #endif /* PATRICIA_DEBUG */
483 return node;
484 }
485 }
486
487 return NULL;
488 }
489
490 patricia_node_t *
491 patricia_search_best(patricia_tree_t *patricia, prefix_t *prefix)
492 {
493 return patricia_search_best2(patricia, prefix, 1);
494 }
495
496 patricia_node_t *
497 patricia_lookup(patricia_tree_t *patricia, prefix_t *prefix)
498 {
499 patricia_node_t *node, *new_node, *parent, *glue;
500 unsigned char *addr, *test_addr;
501 unsigned int bitlen, check_bit, differ_bit;
502 int j, r;
503
504 assert(patricia);
505 assert(prefix);
506 assert(prefix->bitlen <= patricia->maxbits);
507
508 if (patricia->head == NULL)
509 {
510 node = xcalloc(sizeof(*node));
511 node->bit = prefix->bitlen;
512 node->prefix = Ref_Prefix(prefix);
513 patricia->head = node;
514 #ifdef PATRICIA_DEBUG
515 fprintf(stderr, "patricia_lookup: new_node #0 %s/%d (head)\n",
516 patricia_prefix_toa(prefix), prefix->bitlen);
517 #endif /* PATRICIA_DEBUG */
518 patricia->num_active_node++;
519 return node;
520 }
521
522 addr = prefix_touchar(prefix);
523 bitlen = prefix->bitlen;
524 node = patricia->head;
525
526 while (node->bit < bitlen || node->prefix == NULL)
527 {
528 if (node->bit < patricia->maxbits && BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
529 {
530 if (node->r == NULL)
531 break;
532 #ifdef PATRICIA_DEBUG
533 if (node->prefix)
534 fprintf(stderr, "patricia_lookup: take right %s/%d\n",
535 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
536 else
537 fprintf(stderr, "patricia_lookup: take right at %u\n", node->bit);
538 #endif /* PATRICIA_DEBUG */
539
540 node = node->r;
541 }
542 else
543 {
544 if (node->l == NULL)
545 break;
546 #ifdef PATRICIA_DEBUG
547 if (node->prefix)
548 fprintf(stderr, "patricia_lookup: take left %s/%d\n",
549 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
550 else
551 fprintf(stderr, "patricia_lookup: take left at %u\n", node->bit);
552 #endif /* PATRICIA_DEBUG */
553
554 node = node->l;
555 }
556
557 assert(node);
558 }
559
560 assert(node->prefix);
561 #ifdef PATRICIA_DEBUG
562 fprintf(stderr, "patricia_lookup: stop at %s/%d\n",
563 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
564 #endif /* PATRICIA_DEBUG */
565
566 test_addr = prefix_touchar(node->prefix);
567
568 /* Find the first bit different */
569 check_bit = (node->bit < bitlen) ? node->bit : bitlen;
570 differ_bit = 0;
571
572 for (unsigned int i = 0; i * 8 < check_bit; i++)
573 {
574 if ((r = (addr[i] ^ test_addr[i])) == 0)
575 {
576 differ_bit = (i + 1) * 8;
577 continue;
578 }
579
580 /* I know the better way, but for now */
581 for (j = 0; j < 8; j++)
582 if (BIT_TEST(r, (0x80 >> j)))
583 break;
584
585 /* Must be found */
586 assert(j < 8);
587 differ_bit = i * 8 + j;
588 break;
589 }
590
591 if (differ_bit > check_bit)
592 differ_bit = check_bit;
593 #ifdef PATRICIA_DEBUG
594 fprintf(stderr, "patricia_lookup: differ_bit %d\n", differ_bit);
595 #endif /* PATRICIA_DEBUG */
596
597 parent = node->parent;
598
599 while (parent && parent->bit >= differ_bit)
600 {
601 node = parent;
602 parent = node->parent;
603
604 #ifdef PATRICIA_DEBUG
605 if (node->prefix)
606 fprintf(stderr, "patricia_lookup: up to %s/%d\n",
607 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
608 else
609 fprintf(stderr, "patricia_lookup: up to %u\n", node->bit);
610 #endif /* PATRICIA_DEBUG */
611 }
612
613 if (differ_bit == bitlen && node->bit == bitlen)
614 {
615 if (node->prefix)
616 {
617 #ifdef PATRICIA_DEBUG
618 fprintf(stderr, "patricia_lookup: found %s/%d\n",
619 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
620 #endif /* PATRICIA_DEBUG */
621
622 return node;
623 }
624
625 node->prefix = Ref_Prefix(prefix);
626 #ifdef PATRICIA_DEBUG
627 fprintf(stderr, "patricia_lookup: new node #1 %s/%d (glue mod)\n",
628 patricia_prefix_toa(prefix), prefix->bitlen);
629 #endif /* PATRICIA_DEBUG */
630
631 assert(node->data == NULL);
632 return node;
633 }
634
635 new_node = xcalloc(sizeof(*new_node));
636 new_node->bit = prefix->bitlen;
637 new_node->prefix = Ref_Prefix(prefix);
638 patricia->num_active_node++;
639
640 if (node->bit == differ_bit)
641 {
642 new_node->parent = node;
643
644 if (node->bit < patricia->maxbits && BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
645 {
646 assert(node->r == NULL);
647 node->r = new_node;
648 }
649 else
650 {
651 assert(node->l == NULL);
652 node->l = new_node;
653 }
654 #ifdef PATRICIA_DEBUG
655 fprintf(stderr, "patricia_lookup: new_node #2 %s/%d (child)\n",
656 patricia_prefix_toa(prefix), prefix->bitlen);
657 #endif /* PATRICIA_DEBUG */
658 return new_node;
659 }
660
661 if (bitlen == differ_bit)
662 {
663 if (bitlen < patricia->maxbits && BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07)))
664 {
665 new_node->r = node;
666 }
667 else
668 {
669 new_node->l = node;
670 }
671
672 new_node->parent = node->parent;
673
674 if (node->parent == NULL)
675 {
676 assert(patricia->head == node);
677 patricia->head = new_node;
678 }
679 else if (node->parent->r == node)
680 {
681 node->parent->r = new_node;
682 }
683 else
684 {
685 node->parent->l = new_node;
686 }
687
688 node->parent = new_node;
689 #ifdef PATRICIA_DEBUG
690 fprintf(stderr, "patricia_lookup: new_node #3 %s/%d (parent)\n",
691 patricia_prefix_toa(prefix), prefix->bitlen);
692 #endif /* PATRICIA_DEBUG */
693 }
694 else
695 {
696 glue = xcalloc(sizeof(*glue));
697 glue->bit = differ_bit;
698 glue->parent = node->parent;
699 patricia->num_active_node++;
700
701 if (differ_bit < patricia->maxbits && BIT_TEST(addr[differ_bit >> 3], 0x80 >> (differ_bit & 0x07)))
702 {
703 glue->r = new_node;
704 glue->l = node;
705 }
706 else
707 {
708 glue->r = node;
709 glue->l = new_node;
710 }
711
712 new_node->parent = glue;
713
714 if (node->parent == NULL)
715 {
716 assert(patricia->head == node);
717 patricia->head = glue;
718 }
719 else if (node->parent->r == node)
720 {
721 node->parent->r = glue;
722 }
723 else
724 {
725 node->parent->l = glue;
726 }
727
728 node->parent = glue;
729 #ifdef PATRICIA_DEBUG
730 fprintf(stderr, "patricia_lookup: new_node #4 %s/%d (glue+node)\n",
731 patricia_prefix_toa(prefix), prefix->bitlen);
732 #endif /* PATRICIA_DEBUG */
733 }
734
735 return new_node;
736 }
737
738 void
739 patricia_remove(patricia_tree_t *patricia, patricia_node_t *node)
740 {
741 patricia_node_t *parent, *child;
742
743 assert(patricia);
744 assert(node);
745
746 if (node->r && node->l)
747 {
748 #ifdef PATRICIA_DEBUG
749 fprintf(stderr, "patricia_remove: #0 %s/%d (r & l)\n",
750 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
751 #endif /* PATRICIA_DEBUG */
752
753 /*
754 * This might be a placeholder node -- have to check and make sure
755 * there is a prefix associated with it !
756 */
757 if (node->prefix)
758 Deref_Prefix(node->prefix);
759
760 node->prefix = NULL;
761 /* Also I needed to clear data pointer -- masaki */
762 node->data = NULL;
763 return;
764 }
765
766 if (node->r == NULL && node->l == NULL)
767 {
768 #ifdef PATRICIA_DEBUG
769 fprintf(stderr, "patricia_remove: #1 %s/%d (!r & !l)\n",
770 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
771 #endif /* PATRICIA_DEBUG */
772
773 parent = node->parent;
774 Deref_Prefix(node->prefix);
775 xfree(node);
776 patricia->num_active_node--;
777
778 if (parent == NULL)
779 {
780 assert(patricia->head == node);
781 patricia->head = NULL;
782 return;
783 }
784
785 if (parent->r == node)
786 {
787 parent->r = NULL;
788 child = parent->l;
789 }
790 else
791 {
792 assert(parent->l == node);
793
794 parent->l = NULL;
795 child = parent->r;
796 }
797
798 if (parent->prefix)
799 return;
800
801 /* We need to remove parent too */
802 if (parent->parent == NULL)
803 {
804 assert(patricia->head == parent);
805 patricia->head = child;
806 }
807 else if (parent->parent->r == parent)
808 {
809 parent->parent->r = child;
810 }
811 else
812 {
813 assert(parent->parent->l == parent);
814 parent->parent->l = child;
815 }
816
817 child->parent = parent->parent;
818 xfree(parent);
819 patricia->num_active_node--;
820 return;
821 }
822
823 #ifdef PATRICIA_DEBUG
824 fprintf(stderr, "patricia_remove: #2 %s/%d (r ^ l)\n",
825 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
826 #endif /* PATRICIA_DEBUG */
827
828 if (node->r)
829 {
830 child = node->r;
831 }
832 else
833 {
834 assert(node->l);
835 child = node->l;
836 }
837
838 parent = node->parent;
839 child->parent = parent;
840
841 Deref_Prefix(node->prefix);
842 xfree(node);
843 patricia->num_active_node--;
844
845 if (parent == NULL)
846 {
847 assert(patricia->head == node);
848 patricia->head = child;
849 return;
850 }
851
852 if (parent->r == node)
853 {
854 parent->r = child;
855 }
856 else
857 {
858 assert(parent->l == node);
859 parent->l = child;
860 }
861 }
862
863 /* { from demo.c */
864 patricia_node_t *
865 patricia_make_and_lookup(patricia_tree_t *tree, const char *string)
866 {
867 prefix_t *prefix = ascii2prefix(0, string);
868
869 if (prefix)
870 {
871 patricia_node_t *node = patricia_lookup(tree, prefix);
872 Deref_Prefix(prefix);
873 return node;
874 }
875
876 return NULL;
877 }
878
879 patricia_node_t *
880 patricia_make_and_lookup_addr(patricia_tree_t *tree, struct sockaddr *addr, int bitlen)
881 {
882 int family;
883 void *dest;
884
885 if (addr->sa_family == AF_INET6)
886 {
887 if (bitlen == 0 || bitlen > 128)
888 bitlen = 128;
889 family = AF_INET6;
890 dest = &((struct sockaddr_in6 *)addr)->sin6_addr;
891 }
892 else
893 {
894 if (bitlen == 0 || bitlen > 32)
895 bitlen = 32;
896 family = AF_INET;
897 dest = &((struct sockaddr_in *)addr)->sin_addr;
898 }
899
900 prefix_t *prefix = New_Prefix(family, dest, bitlen);
901 if (prefix)
902 {
903 patricia_node_t *node = patricia_lookup(tree, prefix);
904 Deref_Prefix(prefix);
905 return node;
906 }
907
908 return NULL;
909 }
910
911 void
912 patricia_lookup_then_remove(patricia_tree_t *tree, const char *string)
913 {
914 patricia_node_t *node = patricia_try_search_exact(tree, string);
915 if (node)
916 patricia_remove(tree, node);
917 }
918
919 patricia_node_t *
920 patricia_try_search_exact(patricia_tree_t *tree, const char *string)
921 {
922 prefix_t *prefix = ascii2prefix(0, string);
923
924 if (prefix)
925 {
926 patricia_node_t *node = patricia_search_exact(tree, prefix);
927 Deref_Prefix(prefix);
928 return node;
929 }
930
931 return NULL;
932 }
933
934 patricia_node_t *
935 patricia_try_search_best(patricia_tree_t *tree, const char *string)
936 {
937 prefix_t *prefix = ascii2prefix(0, string);
938
939 if (prefix)
940 {
941 patricia_node_t *node = patricia_search_best(tree, prefix);
942 Deref_Prefix(prefix);
943 return node;
944 }
945
946 return NULL;
947 }
948
949 patricia_node_t *
950 patricia_try_search_exact_addr(patricia_tree_t *tree, struct sockaddr *addr, int bitlen)
951 {
952 int family;
953 void *dest;
954
955 if (addr->sa_family == AF_INET6)
956 {
957 if (bitlen == 0 || bitlen > 128)
958 bitlen = 128;
959 family = AF_INET6;
960 dest = &((struct sockaddr_in6 *)addr)->sin6_addr;
961 }
962 else
963 {
964 if (bitlen == 0 || bitlen > 32)
965 bitlen = 32;
966 family = AF_INET;
967 dest = &((struct sockaddr_in *)addr)->sin_addr;
968 }
969
970 prefix_t *prefix = New_Prefix(family, dest, bitlen);
971 if (prefix)
972 {
973 patricia_node_t *node = patricia_search_exact(tree, prefix);
974 Deref_Prefix(prefix);
975 return node;
976 }
977
978 return NULL;
979 }
980
981 patricia_node_t *
982 patricia_try_search_best_addr(patricia_tree_t *tree, struct sockaddr *addr, int bitlen)
983 {
984 int family;
985 void *dest;
986
987 if (addr->sa_family == AF_INET6)
988 {
989 if (bitlen == 0 || bitlen > 128)
990 bitlen = 128;
991 family = AF_INET6;
992 dest = &((struct sockaddr_in6 *)addr)->sin6_addr;
993 }
994 else
995 {
996 if (bitlen == 0 || bitlen > 32)
997 bitlen = 32;
998 family = AF_INET;
999 dest = &((struct sockaddr_in *)addr)->sin_addr;
1000 }
1001
1002 prefix_t *prefix = New_Prefix(family, dest, bitlen);
1003 if (prefix)
1004 {
1005 patricia_node_t *node = patricia_search_best(tree, prefix);
1006 Deref_Prefix(prefix);
1007 return node;
1008 }
1009
1010 return NULL;
1011 }
1012 /* } */

Properties

Name Value
svn:eol-style native
svn:keywords Id

svnadmin@ircd-hybrid.org
ViewVC Help
Powered by ViewVC 1.1.28