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