ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/svn/ircd-hybrid/trunk/src/patricia.c
Revision: 6259
Committed: Sat Jul 11 12:18:43 2015 UTC (8 years, 8 months ago) by michael
Content type: text/x-csrc
File size: 24788 byte(s)
Log Message:
- Set keyword and eol-style properties

File Contents

# User Rev Content
1 michael 5042 /*
2 michael 6259 * $Id$
3 michael 5042 * 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 michael 5046 *
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 michael 5042 */
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 michael 5047 #include "memory.h"
51 michael 5042
52     /* { from prefix.c */
53    
54     /* prefix_tochar
55     * convert prefix information to bytes
56     */
57 michael 5043 static u_char *
58 michael 5042 prefix_tochar (prefix_t * prefix)
59     {
60     if (prefix == NULL)
61     return (NULL);
62    
63     return ((u_char *) & prefix->add.sin);
64     }
65    
66 michael 5043 static int
67 michael 5042 comp_with_mask (void *addr, void *dest, u_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 || (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m))
75     return (1);
76     }
77     return (0);
78     }
79    
80     /* this allows imcomplete prefix */
81 michael 5043 static int
82 michael 5042 my_inet_pton (int af, const char *src, void *dst)
83     {
84     if (af == AF_INET) {
85     int i, c, val;
86     u_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 michael 5043 static const char *
124 michael 5042 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     u_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     u_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 michael 5043 const char *r = inet_ntop(AF_INET6, &prefix->add.sin6, buff, 48 /* a guess value */ );
166 michael 5042 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 michael 5043 const char *
180 michael 5042 prefix_toa2 (prefix_t *prefix, char *buff)
181     {
182     return (prefix_toa2x (prefix, buff, 0));
183     }
184    
185     /* prefix_toa
186     */
187 michael 5043 const char *
188 michael 5042 prefix_toa (prefix_t * prefix)
189     {
190     return (prefix_toa2 (prefix, (char *) NULL));
191     }
192    
193     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 michael 5047 prefix = MyCalloc(sizeof (prefix_t));
203 michael 5042 dynamic_allocated++;
204     }
205     memcpy (&prefix->add.sin6, dest, sizeof(struct in6_addr));
206     }
207 michael 5044 else if (family == AF_INET) {
208 michael 5042 if (prefix == NULL) {
209 michael 5047 prefix = MyCalloc(sizeof (prefix4_t));
210 michael 5042 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     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     prefix_t *
237     ascii2prefix (int family, char *string)
238     {
239     u_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 michael 5044
253 michael 5042 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 michael 5045
287 michael 5042 return (New_Prefix (AF_INET6, &sin6, bitlen));
288     }
289     else
290     return (NULL);
291     }
292    
293 michael 5048 static prefix_t *
294 michael 5042 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 michael 5048 static void
308 michael 5042 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 michael 5043 free (prefix);
319 michael 5042 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 michael 5047 patricia_tree_t *patricia = MyCalloc(sizeof *patricia);
335 michael 5042
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_fn_t func)
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 michael 5047 MyFree (Xrn);
373 michael 5042 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 michael 5047 /* MyFree (patricia); */
391 michael 5042 }
392    
393    
394     void
395     Destroy_Patricia (patricia_tree_t *patricia, void_fn_t func)
396     {
397     Clear_Patricia (patricia, func);
398 michael 5047 MyFree (patricia);
399 michael 5042 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_fn_t func)
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     u_char *addr;
423     u_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     u_char *addr;
495     u_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     u_char *addr, *test_addr;
594     u_int bitlen, check_bit, differ_bit;
595 michael 5049 int j, r;
596 michael 5042
597     assert (patricia);
598     assert (prefix);
599     assert (prefix->bitlen <= patricia->maxbits);
600    
601     if (patricia->head == NULL) {
602 michael 5047 node = MyCalloc(sizeof *node);
603 michael 5042 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 michael 5049 for (unsigned int i = 0; i*8 < check_bit; i++) {
663 michael 5042 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 michael 5047 new_node = MyCalloc(sizeof *new_node);
714 michael 5042 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 michael 5047 glue = MyCalloc(sizeof *glue);
766 michael 5042 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 michael 5047 MyFree (node);
834 michael 5042 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 michael 5047 MyFree (parent);
870 michael 5042 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 michael 5043 free (node);
890 michael 5042 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, char *string)
911     {
912     prefix_t *prefix;
913     patricia_node_t *node;
914    
915     prefix = ascii2prefix (AF_INET, string);
916     printf ("make_and_lookup: %s/%d\n", prefix_toa (prefix), prefix->bitlen);
917     node = patricia_lookup (tree, prefix);
918     Deref_Prefix (prefix);
919     return (node);
920     }
921    
922     patricia_node_t *
923     try_search_exact (patricia_tree_t *tree, char *string)
924     {
925     prefix_t *prefix;
926     patricia_node_t *node;
927    
928     prefix = ascii2prefix (AF_INET, string);
929     printf ("try_search_exact: %s/%d\n", prefix_toa (prefix), prefix->bitlen);
930     if ((node = patricia_search_exact (tree, prefix)) == NULL) {
931     printf ("try_search_exact: not found\n");
932     }
933     else {
934     printf ("try_search_exact: %s/%d found\n",
935     prefix_toa (node->prefix), node->prefix->bitlen);
936     }
937     Deref_Prefix (prefix);
938     return (node);
939     }
940    
941     void
942     lookup_then_remove (patricia_tree_t *tree, char *string)
943     {
944     patricia_node_t *node;
945    
946     if ((node = try_search_exact (tree, string)))
947     patricia_remove (tree, node);
948     }
949    
950     patricia_node_t *
951     try_search_best (patricia_tree_t *tree, char *string)
952     {
953     prefix_t *prefix;
954     patricia_node_t *node;
955    
956     prefix = ascii2prefix (AF_INET, string);
957     printf ("try_search_best: %s/%d\n", prefix_toa (prefix), prefix->bitlen);
958     if ((node = patricia_search_best (tree, prefix)) == NULL)
959     printf ("try_search_best: not found\n");
960     else
961     printf ("try_search_best: %s/%d found\n",
962     prefix_toa (node->prefix), node->prefix->bitlen);
963     Deref_Prefix (prefix);
964     return (node);
965     }
966    
967     /* } */

Properties

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