/[svn]/ircd-hybrid/trunk/src/patricia.c
ViewVC logotype

Contents of /ircd-hybrid/trunk/src/patricia.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 7822 - (show annotations)
Wed Oct 19 21:53:19 2016 UTC (4 years, 1 month ago) by michael
File MIME type: text/x-chdr
File size: 24383 byte(s)
- patricia.h, patricia.c: constification

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 <ctype.h> /* isdigit */
38 #include <errno.h> /* errno */
39 #include <math.h> /* sin */
40 #include <stddef.h> /* NULL */
41 #include <stdio.h> /* sprintf, fprintf, stderr */
42 #include <stdlib.h> /* free, atol, calloc */
43 #include <string.h> /* memcpy, strchr, strlen */
44 #include <sys/types.h> /* BSD: for inet_addr */
45 #include <sys/socket.h> /* BSD, Linux: for inet_addr */
46 #include <netinet/in.h> /* BSD, Linux: for inet_addr */
47 #include <arpa/inet.h> /* BSD, Linux, Solaris: for inet_addr */
48
49 #include "patricia.h"
50 #include "memory.h"
51
52 /* { from prefix.c */
53
54 /* prefix_tochar
55 * convert prefix information to bytes
56 */
57 static unsigned char *
58 prefix_tochar (prefix_t * prefix)
59 {
60 if (prefix == NULL)
61 return (NULL);
62
63 return ((unsigned char *) & prefix->add.sin);
64 }
65
66 static int
67 comp_with_mask (void *addr, void *dest, unsigned int mask)
68 {
69
70 if ( /* mask/8 == 0 || */ memcmp (addr, dest, mask / 8) == 0) {
71 int n = mask / 8;
72 int m = ((-1) << (8 - (mask % 8)));
73
74 if (mask % 8 == 0 || (((unsigned char *)addr)[n] & m) == (((unsigned char *)dest)[n] & m))
75 return (1);
76 }
77 return (0);
78 }
79
80 /* this allows imcomplete prefix */
81 static int
82 my_inet_pton (int af, const char *src, void *dst)
83 {
84 if (af == AF_INET) {
85 int i, c, val;
86 unsigned char xp[sizeof(struct in_addr)] = {0, 0, 0, 0};
87
88 for (i = 0; ; i++) {
89 c = *src++;
90 if (!isdigit (c))
91 return (-1);
92 val = 0;
93 do {
94 val = val * 10 + c - '0';
95 if (val > 255)
96 return (0);
97 c = *src++;
98 } while (c && isdigit (c));
99 xp[i] = val;
100 if (c == '\0')
101 break;
102 if (c != '.')
103 return (0);
104 if (i >= 3)
105 return (0);
106 }
107 memcpy (dst, xp, sizeof(struct in_addr));
108 return (1);
109 } else if (af == AF_INET6) {
110 return (inet_pton (af, src, dst));
111 } else {
112 errno = EAFNOSUPPORT;
113 return -1;
114 }
115 }
116
117 #define PATRICIA_MAX_THREADS 16
118
119 /*
120 * convert prefix information to ascii string with length
121 * thread safe and (almost) re-entrant implementation
122 */
123 static const char *
124 prefix_toa2x (prefix_t *prefix, char *buff, int with_len)
125 {
126 if (prefix == NULL)
127 return ("(Null)");
128 assert (prefix->ref_count >= 0);
129 if (buff == NULL) {
130
131 struct buffer {
132 char buffs[PATRICIA_MAX_THREADS][48+5];
133 unsigned int i;
134 } *buffp;
135
136 # if 0
137 THREAD_SPECIFIC_DATA (struct buffer, buffp, 1);
138 # else
139 { /* for scope only */
140 static struct buffer local_buff;
141 buffp = &local_buff;
142 }
143 # endif
144 if (buffp == NULL) {
145 /* XXX should we report an error? */
146 return (NULL);
147 }
148
149 buff = buffp->buffs[buffp->i++%PATRICIA_MAX_THREADS];
150 }
151 if (prefix->family == AF_INET) {
152 unsigned char *a;
153 assert (prefix->bitlen <= sizeof(struct in_addr) * 8);
154 a = prefix_touchar (prefix);
155 if (with_len) {
156 sprintf (buff, "%d.%d.%d.%d/%d", a[0], a[1], a[2], a[3],
157 prefix->bitlen);
158 }
159 else {
160 sprintf (buff, "%d.%d.%d.%d", a[0], a[1], a[2], a[3]);
161 }
162 return (buff);
163 }
164 else if (prefix->family == AF_INET6) {
165 const char *r = inet_ntop(AF_INET6, &prefix->add.sin6, buff, 48 /* a guess value */ );
166 if (r && with_len) {
167 assert (prefix->bitlen <= sizeof(struct in6_addr) * 8);
168 sprintf (buff + strlen (buff), "/%d", prefix->bitlen);
169 }
170 return (buff);
171 }
172 else
173 return (NULL);
174 }
175
176 /* prefix_toa2
177 * convert prefix information to ascii string
178 */
179 const char *
180 prefix_toa2 (prefix_t *prefix, char *buff)
181 {
182 return (prefix_toa2x (prefix, buff, 0));
183 }
184
185 /* prefix_toa
186 */
187 const char *
188 prefix_toa (prefix_t * prefix)
189 {
190 return (prefix_toa2 (prefix, (char *) NULL));
191 }
192
193 static prefix_t *
194 New_Prefix2 (int family, void *dest, int bitlen, prefix_t *prefix)
195 {
196 int dynamic_allocated = 0;
197 int default_bitlen = sizeof(struct in_addr) * 8;
198
199 if (family == AF_INET6) {
200 default_bitlen = sizeof(struct in6_addr) * 8;
201 if (prefix == NULL) {
202 prefix = xcalloc(sizeof (prefix_t));
203 dynamic_allocated++;
204 }
205 memcpy (&prefix->add.sin6, dest, sizeof(struct in6_addr));
206 }
207 else if (family == AF_INET) {
208 if (prefix == NULL) {
209 prefix = xcalloc(sizeof (prefix_t));
210 dynamic_allocated++;
211 }
212 memcpy (&prefix->add.sin, dest, sizeof(struct in_addr));
213 }
214 else {
215 return (NULL);
216 }
217
218 prefix->bitlen = (bitlen >= 0)? bitlen: default_bitlen;
219 prefix->family = family;
220 prefix->ref_count = 0;
221 if (dynamic_allocated) {
222 prefix->ref_count++;
223 }
224 /* fprintf(stderr, "[C %s, %d]\n", prefix_toa (prefix), prefix->ref_count); */
225 return (prefix);
226 }
227
228 static prefix_t *
229 New_Prefix (int family, void *dest, int bitlen)
230 {
231 return (New_Prefix2 (family, dest, bitlen, NULL));
232 }
233
234 /* ascii2prefix
235 */
236 static prefix_t *
237 ascii2prefix (int family, const char *string)
238 {
239 unsigned long bitlen, maxbitlen = 0;
240 char *cp;
241 struct in_addr sin;
242 struct in6_addr sin6;
243 int result;
244 char save[MAXLINE];
245
246 if (string == NULL)
247 return (NULL);
248
249 /* easy way to handle both families */
250 if (family == 0) {
251 family = AF_INET;
252
253 if (strchr (string, ':')) family = AF_INET6;
254 }
255
256 if (family == AF_INET) {
257 maxbitlen = sizeof(struct in_addr) * 8;
258 }
259 else if (family == AF_INET6) {
260 maxbitlen = sizeof(struct in6_addr) * 8;
261 }
262
263 if ((cp = strchr (string, '/')) != NULL) {
264 bitlen = atol (cp + 1);
265 /* *cp = '\0'; */
266 /* copy the string to save. Avoid destroying the string */
267 assert (cp - string < MAXLINE);
268 memcpy (save, string, cp - string);
269 save[cp - string] = '\0';
270 string = save;
271 if (bitlen < 0 || bitlen > maxbitlen)
272 bitlen = maxbitlen;
273 }
274 else {
275 bitlen = maxbitlen;
276 }
277
278 if (family == AF_INET) {
279 if ((result = my_inet_pton (AF_INET, string, &sin)) <= 0)
280 return (NULL);
281 return (New_Prefix (AF_INET, &sin, bitlen));
282 }
283 else if (family == AF_INET6) {
284 if ((result = inet_pton (AF_INET6, string, &sin6)) <= 0)
285 return (NULL);
286
287 return (New_Prefix (AF_INET6, &sin6, bitlen));
288 }
289 else
290 return (NULL);
291 }
292
293 static prefix_t *
294 Ref_Prefix (prefix_t * prefix)
295 {
296 if (prefix == NULL)
297 return (NULL);
298 if (prefix->ref_count == 0) {
299 /* make a copy in case of a static prefix */
300 return (New_Prefix2 (prefix->family, &prefix->add, prefix->bitlen, NULL));
301 }
302 prefix->ref_count++;
303 /* fprintf(stderr, "[A %s, %d]\n", prefix_toa (prefix), prefix->ref_count); */
304 return (prefix);
305 }
306
307 static void
308 Deref_Prefix (prefix_t * prefix)
309 {
310 if (prefix == NULL)
311 return;
312 /* for secure programming, raise an assert. no static prefix can call this */
313 assert (prefix->ref_count > 0);
314
315 prefix->ref_count--;
316 assert (prefix->ref_count >= 0);
317 if (prefix->ref_count <= 0) {
318 free (prefix);
319 return;
320 }
321 }
322
323 /* } */
324
325 /* #define PATRICIA_DEBUG 1 */
326
327 static int num_active_patricia = 0;
328
329 /* these routines support continuous mask only */
330
331 patricia_tree_t *
332 New_Patricia (int maxbits)
333 {
334 patricia_tree_t *patricia = xcalloc(sizeof *patricia);
335
336 patricia->maxbits = maxbits;
337 patricia->head = NULL;
338 patricia->num_active_node = 0;
339 assert (maxbits <= PATRICIA_MAXBITS); /* XXX */
340 num_active_patricia++;
341 return (patricia);
342 }
343
344
345 /*
346 * if func is supplied, it will be called as func(node->data)
347 * before deleting the node
348 */
349
350 void
351 Clear_Patricia (patricia_tree_t *patricia, void (*func)(void *))
352 {
353 assert (patricia);
354 if (patricia->head) {
355
356 patricia_node_t *Xstack[PATRICIA_MAXBITS+1];
357 patricia_node_t **Xsp = Xstack;
358 patricia_node_t *Xrn = patricia->head;
359
360 while (Xrn) {
361 patricia_node_t *l = Xrn->l;
362 patricia_node_t *r = Xrn->r;
363
364 if (Xrn->prefix) {
365 Deref_Prefix (Xrn->prefix);
366 if (Xrn->data && func)
367 func (Xrn->data);
368 }
369 else {
370 assert (Xrn->data == NULL);
371 }
372 xfree (Xrn);
373 patricia->num_active_node--;
374
375 if (l) {
376 if (r) {
377 *Xsp++ = r;
378 }
379 Xrn = l;
380 } else if (r) {
381 Xrn = r;
382 } else if (Xsp != Xstack) {
383 Xrn = *(--Xsp);
384 } else {
385 Xrn = NULL;
386 }
387 }
388 }
389 assert (patricia->num_active_node == 0);
390 /* xfree (patricia); */
391 }
392
393
394 void
395 Destroy_Patricia (patricia_tree_t *patricia, void (*func)(void *))
396 {
397 Clear_Patricia (patricia, func);
398 xfree (patricia);
399 num_active_patricia--;
400 }
401
402
403 /*
404 * if func is supplied, it will be called as func(node->prefix, node->data)
405 */
406
407 void
408 patricia_process (patricia_tree_t *patricia, void (*func)(prefix_t *, void *))
409 {
410 patricia_node_t *node;
411 assert (func);
412
413 PATRICIA_WALK (patricia->head, node) {
414 func (node->prefix, node->data);
415 } PATRICIA_WALK_END;
416 }
417
418 patricia_node_t *
419 patricia_search_exact (patricia_tree_t *patricia, prefix_t *prefix)
420 {
421 patricia_node_t *node;
422 unsigned char *addr;
423 unsigned int bitlen;
424
425 assert (patricia);
426 assert (prefix);
427 assert (prefix->bitlen <= patricia->maxbits);
428
429 if (patricia->head == NULL)
430 return (NULL);
431
432 node = patricia->head;
433 addr = prefix_touchar (prefix);
434 bitlen = prefix->bitlen;
435
436 while (node->bit < bitlen) {
437
438 if (BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
439 #ifdef PATRICIA_DEBUG
440 if (node->prefix)
441 fprintf (stderr, "patricia_search_exact: take right %s/%d\n",
442 prefix_toa (node->prefix), node->prefix->bitlen);
443 else
444 fprintf (stderr, "patricia_search_exact: take right at %u\n",
445 node->bit);
446 #endif /* PATRICIA_DEBUG */
447 node = node->r;
448 }
449 else {
450 #ifdef PATRICIA_DEBUG
451 if (node->prefix)
452 fprintf (stderr, "patricia_search_exact: take left %s/%d\n",
453 prefix_toa (node->prefix), node->prefix->bitlen);
454 else
455 fprintf (stderr, "patricia_search_exact: take left at %u\n",
456 node->bit);
457 #endif /* PATRICIA_DEBUG */
458 node = node->l;
459 }
460
461 if (node == NULL)
462 return (NULL);
463 }
464
465 #ifdef PATRICIA_DEBUG
466 if (node->prefix)
467 fprintf (stderr, "patricia_search_exact: stop at %s/%d\n",
468 prefix_toa (node->prefix), node->prefix->bitlen);
469 else
470 fprintf (stderr, "patricia_search_exact: stop at %u\n", node->bit);
471 #endif /* PATRICIA_DEBUG */
472 if (node->bit > bitlen || node->prefix == NULL)
473 return (NULL);
474 assert (node->bit == bitlen);
475 assert (node->bit == node->prefix->bitlen);
476 if (comp_with_mask (prefix_tochar (node->prefix), prefix_tochar (prefix),
477 bitlen)) {
478 #ifdef PATRICIA_DEBUG
479 fprintf (stderr, "patricia_search_exact: found %s/%d\n",
480 prefix_toa (node->prefix), node->prefix->bitlen);
481 #endif /* PATRICIA_DEBUG */
482 return (node);
483 }
484 return (NULL);
485 }
486
487
488 /* if inclusive != 0, "best" may be the given prefix itself */
489 patricia_node_t *
490 patricia_search_best2 (patricia_tree_t *patricia, prefix_t *prefix, int inclusive)
491 {
492 patricia_node_t *node;
493 patricia_node_t *stack[PATRICIA_MAXBITS + 1];
494 unsigned char *addr;
495 unsigned int bitlen;
496 int cnt = 0;
497
498 assert (patricia);
499 assert (prefix);
500 assert (prefix->bitlen <= patricia->maxbits);
501
502 if (patricia->head == NULL)
503 return (NULL);
504
505 node = patricia->head;
506 addr = prefix_touchar (prefix);
507 bitlen = prefix->bitlen;
508
509 while (node->bit < bitlen) {
510
511 if (node->prefix) {
512 #ifdef PATRICIA_DEBUG
513 fprintf (stderr, "patricia_search_best: push %s/%d\n",
514 prefix_toa (node->prefix), node->prefix->bitlen);
515 #endif /* PATRICIA_DEBUG */
516 stack[cnt++] = node;
517 }
518
519 if (BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
520 #ifdef PATRICIA_DEBUG
521 if (node->prefix)
522 fprintf (stderr, "patricia_search_best: take right %s/%d\n",
523 prefix_toa (node->prefix), node->prefix->bitlen);
524 else
525 fprintf (stderr, "patricia_search_best: take right at %u\n",
526 node->bit);
527 #endif /* PATRICIA_DEBUG */
528 node = node->r;
529 }
530 else {
531 #ifdef PATRICIA_DEBUG
532 if (node->prefix)
533 fprintf (stderr, "patricia_search_best: take left %s/%d\n",
534 prefix_toa (node->prefix), node->prefix->bitlen);
535 else
536 fprintf (stderr, "patricia_search_best: take left at %u\n",
537 node->bit);
538 #endif /* PATRICIA_DEBUG */
539 node = node->l;
540 }
541
542 if (node == NULL)
543 break;
544 }
545
546 if (inclusive && node && node->prefix)
547 stack[cnt++] = node;
548
549 #ifdef PATRICIA_DEBUG
550 if (node == NULL)
551 fprintf (stderr, "patricia_search_best: stop at null\n");
552 else if (node->prefix)
553 fprintf (stderr, "patricia_search_best: stop at %s/%d\n",
554 prefix_toa (node->prefix), node->prefix->bitlen);
555 else
556 fprintf (stderr, "patricia_search_best: stop at %u\n", node->bit);
557 #endif /* PATRICIA_DEBUG */
558
559 if (cnt <= 0)
560 return (NULL);
561
562 while (--cnt >= 0) {
563 node = stack[cnt];
564 #ifdef PATRICIA_DEBUG
565 fprintf (stderr, "patricia_search_best: pop %s/%d\n",
566 prefix_toa (node->prefix), node->prefix->bitlen);
567 #endif /* PATRICIA_DEBUG */
568 if (comp_with_mask (prefix_tochar (node->prefix),
569 prefix_tochar (prefix),
570 node->prefix->bitlen) && node->prefix->bitlen <= bitlen) {
571 #ifdef PATRICIA_DEBUG
572 fprintf (stderr, "patricia_search_best: found %s/%d\n",
573 prefix_toa (node->prefix), node->prefix->bitlen);
574 #endif /* PATRICIA_DEBUG */
575 return (node);
576 }
577 }
578 return (NULL);
579 }
580
581
582 patricia_node_t *
583 patricia_search_best (patricia_tree_t *patricia, prefix_t *prefix)
584 {
585 return (patricia_search_best2 (patricia, prefix, 1));
586 }
587
588
589 patricia_node_t *
590 patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix)
591 {
592 patricia_node_t *node, *new_node, *parent, *glue;
593 unsigned char *addr, *test_addr;
594 unsigned int bitlen, check_bit, differ_bit;
595 int j, r;
596
597 assert (patricia);
598 assert (prefix);
599 assert (prefix->bitlen <= patricia->maxbits);
600
601 if (patricia->head == NULL) {
602 node = xcalloc(sizeof *node);
603 node->bit = prefix->bitlen;
604 node->prefix = Ref_Prefix (prefix);
605 node->parent = NULL;
606 node->l = node->r = NULL;
607 node->data = NULL;
608 patricia->head = node;
609 #ifdef PATRICIA_DEBUG
610 fprintf (stderr, "patricia_lookup: new_node #0 %s/%d (head)\n",
611 prefix_toa (prefix), prefix->bitlen);
612 #endif /* PATRICIA_DEBUG */
613 patricia->num_active_node++;
614 return (node);
615 }
616
617 addr = prefix_touchar (prefix);
618 bitlen = prefix->bitlen;
619 node = patricia->head;
620
621 while (node->bit < bitlen || node->prefix == NULL) {
622
623 if (node->bit < patricia->maxbits &&
624 BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
625 if (node->r == NULL)
626 break;
627 #ifdef PATRICIA_DEBUG
628 if (node->prefix)
629 fprintf (stderr, "patricia_lookup: take right %s/%d\n",
630 prefix_toa (node->prefix), node->prefix->bitlen);
631 else
632 fprintf (stderr, "patricia_lookup: take right at %u\n", node->bit);
633 #endif /* PATRICIA_DEBUG */
634 node = node->r;
635 }
636 else {
637 if (node->l == NULL)
638 break;
639 #ifdef PATRICIA_DEBUG
640 if (node->prefix)
641 fprintf (stderr, "patricia_lookup: take left %s/%d\n",
642 prefix_toa (node->prefix), node->prefix->bitlen);
643 else
644 fprintf (stderr, "patricia_lookup: take left at %u\n", node->bit);
645 #endif /* PATRICIA_DEBUG */
646 node = node->l;
647 }
648
649 assert (node);
650 }
651
652 assert (node->prefix);
653 #ifdef PATRICIA_DEBUG
654 fprintf (stderr, "patricia_lookup: stop at %s/%d\n",
655 prefix_toa (node->prefix), node->prefix->bitlen);
656 #endif /* PATRICIA_DEBUG */
657
658 test_addr = prefix_touchar (node->prefix);
659 /* find the first bit different */
660 check_bit = (node->bit < bitlen)? node->bit: bitlen;
661 differ_bit = 0;
662 for (unsigned int i = 0; i*8 < check_bit; i++) {
663 if ((r = (addr[i] ^ test_addr[i])) == 0) {
664 differ_bit = (i + 1) * 8;
665 continue;
666 }
667 /* I know the better way, but for now */
668 for (j = 0; j < 8; j++) {
669 if (BIT_TEST (r, (0x80 >> j)))
670 break;
671 }
672 /* must be found */
673 assert (j < 8);
674 differ_bit = i * 8 + j;
675 break;
676 }
677 if (differ_bit > check_bit)
678 differ_bit = check_bit;
679 #ifdef PATRICIA_DEBUG
680 fprintf (stderr, "patricia_lookup: differ_bit %d\n", differ_bit);
681 #endif /* PATRICIA_DEBUG */
682
683 parent = node->parent;
684 while (parent && parent->bit >= differ_bit) {
685 node = parent;
686 parent = node->parent;
687 #ifdef PATRICIA_DEBUG
688 if (node->prefix)
689 fprintf (stderr, "patricia_lookup: up to %s/%d\n",
690 prefix_toa (node->prefix), node->prefix->bitlen);
691 else
692 fprintf (stderr, "patricia_lookup: up to %u\n", node->bit);
693 #endif /* PATRICIA_DEBUG */
694 }
695
696 if (differ_bit == bitlen && node->bit == bitlen) {
697 if (node->prefix) {
698 #ifdef PATRICIA_DEBUG
699 fprintf (stderr, "patricia_lookup: found %s/%d\n",
700 prefix_toa (node->prefix), node->prefix->bitlen);
701 #endif /* PATRICIA_DEBUG */
702 return (node);
703 }
704 node->prefix = Ref_Prefix (prefix);
705 #ifdef PATRICIA_DEBUG
706 fprintf (stderr, "patricia_lookup: new node #1 %s/%d (glue mod)\n",
707 prefix_toa (prefix), prefix->bitlen);
708 #endif /* PATRICIA_DEBUG */
709 assert (node->data == NULL);
710 return (node);
711 }
712
713 new_node = xcalloc(sizeof *new_node);
714 new_node->bit = prefix->bitlen;
715 new_node->prefix = Ref_Prefix (prefix);
716 new_node->parent = NULL;
717 new_node->l = new_node->r = NULL;
718 new_node->data = NULL;
719 patricia->num_active_node++;
720
721 if (node->bit == differ_bit) {
722 new_node->parent = node;
723 if (node->bit < patricia->maxbits &&
724 BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
725 assert (node->r == NULL);
726 node->r = new_node;
727 }
728 else {
729 assert (node->l == NULL);
730 node->l = new_node;
731 }
732 #ifdef PATRICIA_DEBUG
733 fprintf (stderr, "patricia_lookup: new_node #2 %s/%d (child)\n",
734 prefix_toa (prefix), prefix->bitlen);
735 #endif /* PATRICIA_DEBUG */
736 return (new_node);
737 }
738
739 if (bitlen == differ_bit) {
740 if (bitlen < patricia->maxbits &&
741 BIT_TEST (test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) {
742 new_node->r = node;
743 }
744 else {
745 new_node->l = node;
746 }
747 new_node->parent = node->parent;
748 if (node->parent == NULL) {
749 assert (patricia->head == node);
750 patricia->head = new_node;
751 }
752 else if (node->parent->r == node) {
753 node->parent->r = new_node;
754 }
755 else {
756 node->parent->l = new_node;
757 }
758 node->parent = new_node;
759 #ifdef PATRICIA_DEBUG
760 fprintf (stderr, "patricia_lookup: new_node #3 %s/%d (parent)\n",
761 prefix_toa (prefix), prefix->bitlen);
762 #endif /* PATRICIA_DEBUG */
763 }
764 else {
765 glue = xcalloc(sizeof *glue);
766 glue->bit = differ_bit;
767 glue->prefix = NULL;
768 glue->parent = node->parent;
769 glue->data = NULL;
770 patricia->num_active_node++;
771 if (differ_bit < patricia->maxbits &&
772 BIT_TEST (addr[differ_bit >> 3], 0x80 >> (differ_bit & 0x07))) {
773 glue->r = new_node;
774 glue->l = node;
775 }
776 else {
777 glue->r = node;
778 glue->l = new_node;
779 }
780 new_node->parent = glue;
781
782 if (node->parent == NULL) {
783 assert (patricia->head == node);
784 patricia->head = glue;
785 }
786 else if (node->parent->r == node) {
787 node->parent->r = glue;
788 }
789 else {
790 node->parent->l = glue;
791 }
792 node->parent = glue;
793 #ifdef PATRICIA_DEBUG
794 fprintf (stderr, "patricia_lookup: new_node #4 %s/%d (glue+node)\n",
795 prefix_toa (prefix), prefix->bitlen);
796 #endif /* PATRICIA_DEBUG */
797 }
798 return (new_node);
799 }
800
801
802 void
803 patricia_remove (patricia_tree_t *patricia, patricia_node_t *node)
804 {
805 patricia_node_t *parent, *child;
806
807 assert (patricia);
808 assert (node);
809
810 if (node->r && node->l) {
811 #ifdef PATRICIA_DEBUG
812 fprintf (stderr, "patricia_remove: #0 %s/%d (r & l)\n",
813 prefix_toa (node->prefix), node->prefix->bitlen);
814 #endif /* PATRICIA_DEBUG */
815
816 /* this might be a placeholder node -- have to check and make sure
817 * there is a prefix aossciated with it ! */
818 if (node->prefix != NULL)
819 Deref_Prefix (node->prefix);
820 node->prefix = NULL;
821 /* Also I needed to clear data pointer -- masaki */
822 node->data = NULL;
823 return;
824 }
825
826 if (node->r == NULL && node->l == NULL) {
827 #ifdef PATRICIA_DEBUG
828 fprintf (stderr, "patricia_remove: #1 %s/%d (!r & !l)\n",
829 prefix_toa (node->prefix), node->prefix->bitlen);
830 #endif /* PATRICIA_DEBUG */
831 parent = node->parent;
832 Deref_Prefix (node->prefix);
833 xfree (node);
834 patricia->num_active_node--;
835
836 if (parent == NULL) {
837 assert (patricia->head == node);
838 patricia->head = NULL;
839 return;
840 }
841
842 if (parent->r == node) {
843 parent->r = NULL;
844 child = parent->l;
845 }
846 else {
847 assert (parent->l == node);
848 parent->l = NULL;
849 child = parent->r;
850 }
851
852 if (parent->prefix)
853 return;
854
855 /* we need to remove parent too */
856
857 if (parent->parent == NULL) {
858 assert (patricia->head == parent);
859 patricia->head = child;
860 }
861 else if (parent->parent->r == parent) {
862 parent->parent->r = child;
863 }
864 else {
865 assert (parent->parent->l == parent);
866 parent->parent->l = child;
867 }
868 child->parent = parent->parent;
869 xfree (parent);
870 patricia->num_active_node--;
871 return;
872 }
873
874 #ifdef PATRICIA_DEBUG
875 fprintf (stderr, "patricia_remove: #2 %s/%d (r ^ l)\n",
876 prefix_toa (node->prefix), node->prefix->bitlen);
877 #endif /* PATRICIA_DEBUG */
878 if (node->r) {
879 child = node->r;
880 }
881 else {
882 assert (node->l);
883 child = node->l;
884 }
885 parent = node->parent;
886 child->parent = parent;
887
888 Deref_Prefix (node->prefix);
889 free (node);
890 patricia->num_active_node--;
891
892 if (parent == NULL) {
893 assert (patricia->head == node);
894 patricia->head = child;
895 return;
896 }
897
898 if (parent->r == node) {
899 parent->r = child;
900 }
901 else {
902 assert (parent->l == node);
903 parent->l = child;
904 }
905 }
906
907 /* { from demo.c */
908
909 patricia_node_t *
910 make_and_lookup (patricia_tree_t *tree, const char *string)
911 {
912 prefix_t *prefix = ascii2prefix (0, string);
913 if (prefix)
914 {
915 patricia_node_t *node = patricia_lookup (tree, prefix);
916 Deref_Prefix (prefix);
917 return node;
918 }
919
920 return (NULL);
921 }
922
923 patricia_node_t *
924 try_search_exact (patricia_tree_t *tree, const char *string)
925 {
926 prefix_t *prefix = ascii2prefix (0, string);
927 if (prefix)
928 {
929 patricia_node_t *node = patricia_search_exact (tree, prefix);
930 Deref_Prefix (prefix);
931 return node;
932 }
933
934 return (NULL);
935 }
936
937 void
938 lookup_then_remove (patricia_tree_t *tree, const char *string)
939 {
940 patricia_node_t *node;
941
942 if ((node = try_search_exact (tree, string)))
943 patricia_remove (tree, node);
944 }
945
946 patricia_node_t *
947 try_search_best (patricia_tree_t *tree, const char *string)
948 {
949 prefix_t *prefix = ascii2prefix (0, string);
950 if (prefix)
951 {
952 patricia_node_t *node = patricia_search_best (tree, prefix);
953 Deref_Prefix (prefix);
954 return node;
955 }
956
957 return (NULL);
958 }
959
960 /* } */

Properties

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

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