1 /*
2 * Copyright (c) 1999-2000
3 *
4 * The Regents of the University of Michigan ("The Regents") and
5 * Merit Network, Inc. All rights reserved. Redistribution and use
6 * in source and binary forms, with or without modification, are
7 * permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above
10 * copyright notice, this list of conditions and the
11 * following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the
15 * following disclaimer in the documentation and/or other
16 * materials provided with the distribution.
17 *
18 * 3. All advertising materials mentioning features or use of
19 * this software must display the following acknowledgement:
20 *
21 * This product includes software developed by the University of
22 * Michigan, Merit Network, Inc., and their contributors.
23 *
24 * 4. Neither the name of the University, Merit Network, nor the
25 * names of their contributors may be used to endorse or
26 * promote products derived from this software without
27 * specific prior written permission.
28 *
29 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS "AS IS"
30 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
31 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
32 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL TH E REGENTS
33 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
34 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
35 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
36 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HO WEVER CAUSED
37 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
38 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
39 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
40 * POSSIBILITY OF SUCH DAMAGE.
41 */
42 /*
43 * Portions Copyright (c) 2004,2005 Damien Miller <djm@mindrot.org>
44 *
45 * Permission to use, copy, modify, and distribute this software for any
46 * purpose with or without fee is hereby granted, provided that the above
47 * copyright notice and this permission notice appear in all copies.
48 *
49 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
50 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
51 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
52 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
53 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
54 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
55 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
56 */
57
58 #include "Python.h"
59
60 #include <sys/types.h>
61 #include <stdlib.h>
62 #include <stdio.h>
63 #include <string.h>
64
65 #include "radix.h"
66
67 /* $Id$ */
68
69 /*
70 * Originally from MRT include/defs.h
71 * $MRTId: defs.h,v 1.1.1.1 2000/08/14 18:46:10 labovit Exp $
72 */
73 #define BIT_TEST(f, b) ((f) & (b))
74 #define BIT_TEST_SEARCH_BIT(addr, bit) \
75 BIT_TEST((addr)[(bit) >> 3], 0x80 >> ((bit) & 0x07))
76 #define BIT_TEST_SEARCH(addr, node) BIT_TEST_SEARCH_BIT(addr, (node)->bit)
77
78 /*
79 * Originally from MRT include/mrt.h
80 * $MRTId: mrt.h,v 1.1.1.1 2000/08/14 18:46:10 labovit Exp $
81 */
82 #define prefix_tochar(prefix) ((char *)&(prefix)->add)
83 #define prefix_touchar(prefix) ((u_char *)&(prefix)->add)
84
85 #define RADIX_SEARCH_FOREACH(node, head, prefix) \
86 for ((node) = (head); \
87 (node) != NULL && (node)->bit < (prefix)->bitlen; \
88 (node) = BIT_TEST_SEARCH(prefix_touchar(prefix), node) ? (node)->r : (node)->l)
89
90 #define RADIX_SEARCH_FOREACH_INCLUSIVE(node, head, prefix) \
91 for ((node) = (head); \
92 (node) != NULL && (node)->bit <= (prefix)->bitlen; \
93 (node) = BIT_TEST_SEARCH(prefix_touchar(prefix), node) ? (node)->r : (node)->l)
94
95 #define RADIX_PHEAD_BY_PREFIX(tree, prefix) \
96 ((prefix)->family == AF_INET ? &(tree)->head_ipv4 : &(tree)->head_ipv6)
97 #define RADIX_HEAD_BY_PREFIX(tree, prefix) \
98 ((prefix)->family == AF_INET ? (tree)->head_ipv4 : (tree)->head_ipv6)
99 #define RADIX_MAXBITS_BY_PREFIX(prefix) \
100 ((prefix)->family == AF_INET ? 32 : 128)
101
102 #define RADIX_MIN(a, b) ((a) < (b) ? (a) : (b))
103
104 /*
105 * Originally from MRT lib/mrt/prefix.c
106 * $MRTId: prefix.c,v 1.1.1.1 2000/08/14 18:46:11 labovit Exp $
107 */
108
109 static int
comp_with_mask(u_char * addr,u_char * dest,u_int mask)110 comp_with_mask(u_char *addr, u_char *dest, u_int mask)
111 {
112 if (memcmp(addr, dest, mask / 8) == 0) {
113 u_int n = mask / 8;
114 u_int m = ((~0) << (8 - (mask % 8)));
115
116 if (mask % 8 == 0 || (addr[n] & m) == (dest[n] & m))
117 return (1);
118 }
119 return (0);
120 }
121
122 static prefix_t
New_Prefix2(int family,void * dest,int bitlen,prefix_t * prefix)123 *New_Prefix2(int family, void *dest, int bitlen, prefix_t *prefix)
124 {
125 int dynamic_allocated = 0;
126 int default_bitlen = 32;
127
128 if (family == AF_INET6) {
129 default_bitlen = 128;
130 if (prefix == NULL) {
131 if ((prefix = PyMem_Malloc(sizeof(*prefix))) == NULL)
132 return (NULL);
133 memset(prefix, '\0', sizeof(*prefix));
134 dynamic_allocated++;
135 }
136 memcpy(&prefix->add.sin6, dest, 16);
137 } else if (family == AF_INET) {
138 if (prefix == NULL) {
139 if ((prefix = PyMem_Malloc(sizeof(*prefix))) == NULL)
140 return (NULL);
141 memset(prefix, '\0', sizeof(*prefix));
142 dynamic_allocated++;
143 }
144 memcpy(&prefix->add.sin, dest, 4);
145 } else
146 return (NULL);
147
148 prefix->bitlen = (bitlen >= 0) ? bitlen : default_bitlen;
149 prefix->family = family;
150 prefix->ref_count = 0;
151 if (dynamic_allocated)
152 prefix->ref_count++;
153 return (prefix);
154 }
155
156
157 static prefix_t
Ref_Prefix(prefix_t * prefix)158 *Ref_Prefix(prefix_t *prefix)
159 {
160 if (prefix == NULL)
161 return (NULL);
162 if (prefix->ref_count == 0) {
163 /* make a copy in case of a static prefix */
164 return (New_Prefix2(prefix->family, &prefix->add,
165 prefix->bitlen, NULL));
166 }
167 prefix->ref_count++;
168 return (prefix);
169 }
170
171
172 void
Deref_Prefix(prefix_t * prefix)173 Deref_Prefix(prefix_t *prefix)
174 {
175 if (prefix == NULL)
176 return;
177 prefix->ref_count--;
178 if (prefix->ref_count <= 0) {
179 PyMem_Free(prefix);
180 return;
181 }
182 }
183
184 /*
185 * Originally from MRT lib/radix/radix.c
186 * $MRTId: radix.c,v 1.1.1.1 2000/08/14 18:46:13 labovit Exp $
187 */
188
189 /* these routines support continuous mask only */
190
191 radix_tree_t
New_Radix(void)192 *New_Radix(void)
193 {
194 radix_tree_t *radix;
195
196 if ((radix = PyMem_Malloc(sizeof(*radix))) == NULL)
197 return (NULL);
198 memset(radix, '\0', sizeof(*radix));
199
200 radix->head_ipv4 = NULL;
201 radix->head_ipv6 = NULL;
202 radix->num_active_node = 0;
203 return (radix);
204 }
205
206 /*
207 * if func is supplied, it will be called as func(node->data)
208 * before deleting the node
209 */
210 static void
radix_clear_head(radix_tree_t * radix,radix_node_t * head,rdx_cb_t func,void * cbctx)211 radix_clear_head(radix_tree_t *radix, radix_node_t *head, rdx_cb_t func, void *cbctx)
212 {
213 if (head) {
214 radix_node_t *Xstack[RADIX_MAXBITS + 1];
215 radix_node_t **Xsp = Xstack;
216 radix_node_t *Xrn = head;
217
218 while (Xrn) {
219 radix_node_t *l = Xrn->l;
220 radix_node_t *r = Xrn->r;
221
222 if (Xrn->prefix) {
223 Deref_Prefix(Xrn->prefix);
224 if (Xrn->data && func)
225 func(Xrn, cbctx);
226 }
227 PyMem_Free(Xrn);
228 radix->num_active_node--;
229
230 if (l) {
231 if (r)
232 *Xsp++ = r;
233 Xrn = l;
234 } else if (r) {
235 Xrn = r;
236 } else if (Xsp != Xstack) {
237 Xrn = *(--Xsp);
238 } else {
239 Xrn = (radix_node_t *) 0;
240 }
241 }
242 }
243 }
244
245 void
Clear_Radix(radix_tree_t * radix,rdx_cb_t func,void * cbctx)246 Clear_Radix(radix_tree_t *radix, rdx_cb_t func, void *cbctx)
247 {
248 radix_clear_head(radix, radix->head_ipv4, func, cbctx);
249 radix_clear_head(radix, radix->head_ipv6, func, cbctx);
250 }
251
252 void
Destroy_Radix(radix_tree_t * radix,rdx_cb_t func,void * cbctx)253 Destroy_Radix(radix_tree_t *radix, rdx_cb_t func, void *cbctx)
254 {
255 Clear_Radix(radix, func, cbctx);
256 PyMem_Free(radix);
257 }
258
259 /*
260 * if func is supplied, it will be called as func(node->prefix, node->data)
261 */
262 void
radix_process(radix_tree_t * radix,rdx_cb_t func,void * cbctx)263 radix_process(radix_tree_t *radix, rdx_cb_t func, void *cbctx)
264 {
265 radix_node_t *node;
266
267 RADIX_TREE_WALK(radix, node) {
268 func(node, cbctx);
269 } RADIX_TREE_WALK_END;
270 }
271
272 radix_node_t
radix_search_exact(radix_tree_t * radix,prefix_t * prefix)273 *radix_search_exact(radix_tree_t *radix, prefix_t *prefix)
274 {
275 radix_node_t *node, *head;
276 u_int bitlen;
277
278 if ((head = RADIX_HEAD_BY_PREFIX(radix, prefix)) == NULL)
279 return (NULL);
280
281 bitlen = prefix->bitlen;
282
283 RADIX_SEARCH_FOREACH(node, head, prefix);
284
285 if (node == NULL || node->bit > bitlen || node->prefix == NULL)
286 return (NULL);
287
288 if (comp_with_mask(prefix_touchar(node->prefix),
289 prefix_touchar(prefix), bitlen))
290 return (node);
291
292 return (NULL);
293 }
294
295
296 /* seach for a node without checking if it is a "real" node */
297 radix_node_t
radix_search_node(radix_tree_t * radix,prefix_t * prefix)298 *radix_search_node(radix_tree_t *radix, prefix_t *prefix)
299 {
300 radix_node_t *node, *head, *node_iter;
301 int right_mismatch = 0;
302 int left_mismatch = 0;
303 u_int bitlen;
304
305 if ((head = RADIX_HEAD_BY_PREFIX(radix, prefix)) == NULL)
306 return (NULL);
307
308 bitlen = prefix->bitlen;
309
310 RADIX_SEARCH_FOREACH(node, head, prefix);
311
312 if (node == NULL)
313 return (NULL);
314
315 // if the node has a prefix we can (and must to avoid false negatives) check directly
316 if (node->prefix) {
317 if (comp_with_mask(prefix_touchar(node->prefix), prefix_touchar(prefix), bitlen))
318 return (node);
319 else
320 return (NULL);
321 }
322
323 // We can risk landing on an intermediate node (no set prefix), that doesn't match the wanted prefix
324 // When this happens we have to check the two subtrees, if a subtree does not match, that part should
325 // not be returned. If both match the entire node should be returned. If none match, null is returned.
326
327
328 RADIX_WALK(node->r, node_iter) {
329 if (node_iter->data != NULL) {
330 if ( ! comp_with_mask(prefix_touchar(node_iter->prefix), prefix_touchar(prefix), bitlen)) {
331 right_mismatch = 1;
332 break;
333 }
334 }
335 } RADIX_WALK_END;
336
337 RADIX_WALK(node->l, node_iter) {
338 if (node_iter->data != NULL) {
339 if ( ! comp_with_mask(prefix_touchar(node_iter->prefix), prefix_touchar(prefix), bitlen)) {
340 left_mismatch = 1;
341 break;
342 }
343 }
344 } RADIX_WALK_END;
345
346 if (right_mismatch && left_mismatch) {
347 return (NULL);
348 }
349 if (right_mismatch) {
350 return node->l;
351 }
352 if (left_mismatch) {
353 return node->r;
354 }
355 return node;
356
357 }
358
359
360 /* if inclusive != 0, "best" may be the given prefix itself */
361 radix_node_t
radix_search_best2(radix_tree_t * radix,prefix_t * prefix,int inclusive)362 *radix_search_best2(radix_tree_t *radix, prefix_t *prefix, int inclusive)
363 {
364 radix_node_t *node, *head;
365 radix_node_t *stack[RADIX_MAXBITS + 1];
366 u_int bitlen;
367 int cnt = 0;
368
369 if ((head = RADIX_HEAD_BY_PREFIX(radix, prefix)) == NULL)
370 return (NULL);
371
372 bitlen = prefix->bitlen;
373
374 RADIX_SEARCH_FOREACH_INCLUSIVE(node, head, prefix) {
375 if (node->prefix && (inclusive || node->bit != bitlen))
376 stack[cnt++] = node;
377 }
378
379 if (cnt <= 0)
380 return (NULL);
381
382 while (--cnt >= 0) {
383 node = stack[cnt];
384 if (comp_with_mask(prefix_touchar(node->prefix),
385 prefix_touchar(prefix), node->prefix->bitlen) &&
386 node->prefix->bitlen <= bitlen)
387 return (node);
388 }
389 return (NULL);
390 }
391
392
393 radix_node_t
radix_search_best(radix_tree_t * radix,prefix_t * prefix)394 *radix_search_best(radix_tree_t *radix, prefix_t *prefix)
395 {
396 return (radix_search_best2(radix, prefix, 1));
397 }
398
399 /* if inclusive != 0, "worst" may be the given prefix itself */
400 radix_node_t
radix_search_worst2(radix_tree_t * radix,prefix_t * prefix,int inclusive)401 *radix_search_worst2(radix_tree_t *radix, prefix_t *prefix, int inclusive)
402 {
403 radix_node_t *node, *head;
404 radix_node_t *stack[RADIX_MAXBITS + 1];
405 u_int bitlen;
406 int cnt = 0;
407 int iterator;
408
409 if ((head = RADIX_HEAD_BY_PREFIX(radix, prefix)) == NULL)
410 return (NULL);
411
412 bitlen = prefix->bitlen;
413
414 RADIX_SEARCH_FOREACH_INCLUSIVE(node, head, prefix) {
415 if (node->prefix && (inclusive || node->bit != bitlen))
416 stack[cnt++] = node;
417 }
418
419 if (cnt <= 0)
420 return (NULL);
421
422 for (iterator = 0; iterator < cnt; ++iterator) {
423 node = stack[iterator];
424 if (comp_with_mask(prefix_touchar(node->prefix),
425 prefix_touchar(prefix), node->prefix->bitlen))
426 return (node);
427 }
428 return (NULL);
429 }
430
431
432 radix_node_t
radix_search_worst(radix_tree_t * radix,prefix_t * prefix)433 *radix_search_worst(radix_tree_t *radix, prefix_t *prefix)
434 {
435 return (radix_search_worst2(radix, prefix, 1));
436 }
437
438
439 int
radix_search_covering(radix_tree_t * radix,prefix_t * prefix,rdx_search_cb_t func,void * cbctx)440 radix_search_covering(radix_tree_t *radix, prefix_t *prefix, rdx_search_cb_t func, void *cbctx)
441 {
442 radix_node_t *node;
443 int rc = 0;
444
445 node = radix_search_best(radix, prefix);
446 if (node == NULL)
447 return (0);
448
449 do {
450 if (!node->prefix)
451 continue;
452 if ((rc = func(node, cbctx)) != 0)
453 break;
454 } while ((node = node->parent) != NULL);
455
456 return (rc);
457 }
458
459 int
radix_search_covered(radix_tree_t * radix,prefix_t * prefix,rdx_search_cb_t func,void * cbctx,int inclusive)460 radix_search_covered(radix_tree_t *radix, prefix_t *prefix, rdx_search_cb_t func, void *cbctx, int inclusive)
461 {
462 radix_node_t *node, *prefixed_node, *prev_node;
463 struct {
464 radix_node_t *node;
465 enum {
466 RADIX_STATE_LEFT = 0,
467 RADIX_STATE_RIGHT,
468 RADIX_STATE_SELF,
469 } state;
470 int checked;
471 } stack[RADIX_MAXBITS + 1], *pst;
472 int stackpos;
473 int rc;
474
475 #define COMP_NODE_PREFIX(node, prefix_) \
476 comp_with_mask(prefix_touchar((node)->prefix), \
477 prefix_touchar(prefix_), \
478 RADIX_MIN((node)->prefix->bitlen, (prefix_)->bitlen))
479
480 prev_node = NULL;
481 prefixed_node = NULL;
482 RADIX_SEARCH_FOREACH_INCLUSIVE(
483 node, RADIX_HEAD_BY_PREFIX(radix, prefix), prefix) {
484
485 prev_node = node;
486 if (node->bit == prefix->bitlen)
487 break;
488 if (node->prefix != NULL)
489 prefixed_node = node;
490 }
491
492 if (node == NULL) {
493 if (prev_node == NULL)
494 return (0);
495 node = prev_node;
496 } else {
497 /* node->bit >= prefix->bitlen */
498
499 if (node->prefix != NULL)
500 prefixed_node = node;
501 }
502 if (prefixed_node != NULL && !COMP_NODE_PREFIX(prefixed_node, prefix))
503 return (0);
504
505 stack[0].state = RADIX_STATE_LEFT;
506 stack[0].node = node;
507 stack[0].checked = (node == prefixed_node && node->bit >= prefix->bitlen);
508 stackpos = 0;
509
510 while (stackpos >= 0) {
511 pst = stack + stackpos;
512
513 switch (pst->state) {
514 case RADIX_STATE_LEFT:
515 case RADIX_STATE_RIGHT:
516 if (pst->state == RADIX_STATE_LEFT) {
517 pst->state = RADIX_STATE_RIGHT;
518 node = pst->node->l;
519 } else {
520 pst->state = RADIX_STATE_SELF;
521 node = pst->node->r;
522 }
523 if (node == NULL)
524 continue;
525
526 /* skip foreign nodes */
527 if (!pst->checked && node->prefix != NULL &&
528 !COMP_NODE_PREFIX(node, prefix))
529 continue;
530 stackpos++;
531 pst = stack + stackpos;
532 pst->state = RADIX_STATE_LEFT;
533 pst->node = node;
534 pst->checked = (pst[-1].checked || node->prefix != NULL);
535 break;
536 case RADIX_STATE_SELF:
537 if (stackpos > 0 || (inclusive ?
538 pst->node->bit >= prefix->bitlen:
539 pst->node->bit > prefix->bitlen)) {
540 if (pst->node->prefix != NULL &&
541 (rc = func(pst->node, cbctx)) != 0)
542 return (rc);
543 }
544
545 stackpos--;
546 break;
547 }
548 }
549 #undef COMP_NODE_PREFIX
550 return (0);
551 }
552
553 int
radix_search_intersect(radix_tree_t * radix,prefix_t * prefix,rdx_search_cb_t func,void * cbctx)554 radix_search_intersect(radix_tree_t *radix, prefix_t *prefix, rdx_search_cb_t func, void *cbctx)
555 {
556 int rc;
557
558 if ((rc = radix_search_covering(radix, prefix, func, cbctx)) == 0)
559 rc = radix_search_covered(radix, prefix, func, cbctx, 0);
560
561 return (rc);
562 }
563
564 radix_node_t
radix_lookup(radix_tree_t * radix,prefix_t * prefix)565 *radix_lookup(radix_tree_t *radix, prefix_t *prefix)
566 {
567 radix_node_t **phead, *node, *new_node, *parent, *glue;
568 u_char *addr, *test_addr;
569 u_int bitlen, check_bit, differ_bit, maxbits;
570 u_int i, j, r;
571
572 maxbits = RADIX_MAXBITS_BY_PREFIX(prefix);
573 phead = RADIX_PHEAD_BY_PREFIX(radix, prefix);
574 if (*phead == NULL) {
575 if ((node = PyMem_Malloc(sizeof(*node))) == NULL)
576 return (NULL);
577 memset(node, '\0', sizeof(*node));
578 node->bit = prefix->bitlen;
579 node->prefix = Ref_Prefix(prefix);
580 node->parent = NULL;
581 node->l = node->r = NULL;
582 node->data = NULL;
583 *phead = node;
584 radix->num_active_node++;
585 return (node);
586 }
587 addr = prefix_touchar(prefix);
588 bitlen = prefix->bitlen;
589 node = *phead;
590
591 while (node->bit < bitlen || node->prefix == NULL) {
592 if (node->bit < maxbits && BIT_TEST_SEARCH(addr, node)) {
593 if (node->r == NULL)
594 break;
595 node = node->r;
596 } else {
597 if (node->l == NULL)
598 break;
599 node = node->l;
600 }
601 }
602
603 test_addr = prefix_touchar(node->prefix);
604 /* find the first bit different */
605 check_bit = (node->bit < bitlen) ? node->bit : bitlen;
606 differ_bit = 0;
607 for (i = 0; i * 8 < check_bit; i++) {
608 if ((r = (addr[i] ^ test_addr[i])) == 0) {
609 differ_bit = (i + 1) * 8;
610 continue;
611 }
612 /* I know the better way, but for now */
613 for (j = 0; j < 8; j++) {
614 if (BIT_TEST(r, (0x80 >> j)))
615 break;
616 }
617 /* must be found */
618 differ_bit = i * 8 + j;
619 break;
620 }
621 if (differ_bit > check_bit)
622 differ_bit = check_bit;
623
624 parent = node->parent;
625 while (parent && parent->bit >= differ_bit) {
626 node = parent;
627 parent = node->parent;
628 }
629
630 if (differ_bit == bitlen && node->bit == bitlen) {
631 if (node->prefix == NULL)
632 node->prefix = Ref_Prefix(prefix);
633 return (node);
634 }
635 if ((new_node = PyMem_Malloc(sizeof(*new_node))) == NULL)
636 return (NULL);
637 memset(new_node, '\0', sizeof(*new_node));
638 new_node->bit = prefix->bitlen;
639 new_node->prefix = Ref_Prefix(prefix);
640 new_node->parent = NULL;
641 new_node->l = new_node->r = NULL;
642 new_node->data = NULL;
643 radix->num_active_node++;
644
645 if (node->bit == differ_bit) {
646 new_node->parent = node;
647 if (node->bit < maxbits && BIT_TEST_SEARCH(addr, node))
648 node->r = new_node;
649 else
650 node->l = new_node;
651
652 return (new_node);
653 }
654 if (bitlen == differ_bit) {
655 if (bitlen < maxbits &&
656 BIT_TEST_SEARCH_BIT(test_addr, bitlen))
657 new_node->r = node;
658 else
659 new_node->l = node;
660
661 new_node->parent = node->parent;
662 if (node->parent == NULL)
663 *phead = new_node;
664 else if (node->parent->r == node)
665 node->parent->r = new_node;
666 else
667 node->parent->l = new_node;
668
669 node->parent = new_node;
670 } else {
671 if ((glue = PyMem_Malloc(sizeof(*glue))) == NULL)
672 return (NULL);
673 memset(glue, '\0', sizeof(*glue));
674 glue->bit = differ_bit;
675 glue->prefix = NULL;
676 glue->parent = node->parent;
677 glue->data = NULL;
678 radix->num_active_node++;
679 if (differ_bit < maxbits &&
680 BIT_TEST_SEARCH_BIT(addr, differ_bit)) {
681 glue->r = new_node;
682 glue->l = node;
683 } else {
684 glue->r = node;
685 glue->l = new_node;
686 }
687 new_node->parent = glue;
688
689 if (node->parent == NULL)
690 *phead = glue;
691 else if (node->parent->r == node)
692 node->parent->r = glue;
693 else
694 node->parent->l = glue;
695
696 node->parent = glue;
697 }
698 return (new_node);
699 }
700
701
702 void
radix_remove(radix_tree_t * radix,radix_node_t * node)703 radix_remove(radix_tree_t *radix, radix_node_t *node)
704 {
705 radix_node_t **phead, *parent, *child;
706
707 phead = RADIX_PHEAD_BY_PREFIX(radix, node->prefix);
708
709 if (node->r && node->l) {
710 /*
711 * this might be a placeholder node -- have to check and make
712 * sure there is a prefix aossciated with it !
713 */
714 if (node->prefix != NULL)
715 Deref_Prefix(node->prefix);
716 node->prefix = NULL;
717 /* Also I needed to clear data pointer -- masaki */
718 node->data = NULL;
719 return;
720 }
721 if (node->r == NULL && node->l == NULL) {
722 parent = node->parent;
723 Deref_Prefix(node->prefix);
724 PyMem_Free(node);
725 radix->num_active_node--;
726
727 if (parent == NULL) {
728 *phead = NULL;
729 return;
730 }
731 if (parent->r == node) {
732 parent->r = NULL;
733 child = parent->l;
734 } else {
735 parent->l = NULL;
736 child = parent->r;
737 }
738
739 if (parent->prefix)
740 return;
741
742 /* we need to remove parent too */
743 if (parent->parent == NULL)
744 *phead = child;
745 else if (parent->parent->r == parent)
746 parent->parent->r = child;
747 else
748 parent->parent->l = child;
749
750 child->parent = parent->parent;
751 PyMem_Free(parent);
752 radix->num_active_node--;
753 return;
754 }
755 if (node->r)
756 child = node->r;
757 else
758 child = node->l;
759
760 parent = node->parent;
761 child->parent = parent;
762
763 Deref_Prefix(node->prefix);
764 PyMem_Free(node);
765 radix->num_active_node--;
766
767 if (parent == NULL) {
768 *phead = child;
769 return;
770 }
771 if (parent->r == node)
772 parent->r = child;
773 else
774 parent->l = child;
775 }
776
777 /* Local additions */
778 static void
sanitise_mask(u_char * addr,u_int masklen,u_int maskbits)779 sanitise_mask(u_char *addr, u_int masklen, u_int maskbits)
780 {
781 u_int i = masklen / 8;
782 u_int j = masklen % 8;
783
784 if (j != 0) {
785 addr[i] &= (~0) << (8 - j);
786 i++;
787 }
788 for (; i < maskbits / 8; i++)
789 addr[i] = 0;
790 }
791
792 prefix_t
prefix_pton_ex(prefix_t * ret,const char * string,long len,const char ** errmsg)793 *prefix_pton_ex(prefix_t *ret, const char *string, long len, const char **errmsg)
794 {
795 char save[256], *cp, *ep;
796 struct addrinfo hints, *ai;
797 void *addr;
798 size_t slen;
799 int r;
800
801 /* Copy the string to parse, because we modify it */
802 if ((slen = strlen(string) + 1) > sizeof(save)) {
803 *errmsg = "string too long";
804 return (NULL);
805 }
806 memcpy(save, string, slen);
807
808 if ((cp = strchr(save, '/')) != NULL) {
809 if (len != -1 ) {
810 *errmsg = "masklen specified twice";
811 return (NULL);
812 }
813 *cp++ = '\0';
814 len = strtol(cp, &ep, 10);
815 if (*cp == '\0' || *ep != '\0' || len < 0) {
816 *errmsg = "could not parse masklen";
817 return (NULL);
818 }
819 /* More checks below */
820 }
821 memset(&hints, '\0', sizeof(hints));
822 hints.ai_flags = AI_NUMERICHOST;
823
824 if ((r = getaddrinfo(save, NULL, &hints, &ai)) != 0) {
825 *errmsg = gai_strerror(r);
826 return NULL;
827 }
828 if (ai == NULL || ai->ai_addr == NULL) {
829 *errmsg = "getaddrinfo returned no result";
830 goto out;
831 }
832 switch (ai->ai_addr->sa_family) {
833 case AF_INET:
834 if (len == -1)
835 len = 32;
836 else if (len < 0 || len > 32) {
837 *errmsg = "invalid prefix length";
838 goto out;
839 }
840 addr = &((struct sockaddr_in *) ai->ai_addr)->sin_addr;
841 sanitise_mask(addr, len, 32);
842 break;
843 case AF_INET6:
844 if (len == -1)
845 len = 128;
846 else if (len < 0 || len > 128) {
847 *errmsg = "invalid prefix length";
848 goto out;
849 }
850 addr = &((struct sockaddr_in6 *) ai->ai_addr)->sin6_addr;
851 sanitise_mask(addr, len, 128);
852 break;
853 default:
854 goto out;
855 }
856
857 ret = New_Prefix2(ai->ai_addr->sa_family, addr, len, ret);
858 if (ret == NULL)
859 *errmsg = "New_Prefix2 failed";
860 out:
861 freeaddrinfo(ai);
862 return (ret);
863 }
864
865 prefix_t
prefix_pton(const char * string,long len,const char ** errmsg)866 *prefix_pton(const char *string, long len, const char **errmsg)
867 {
868 return (prefix_pton_ex(NULL, string, len, errmsg));
869 }
870
871 prefix_t
prefix_from_blob_ex(prefix_t * ret,u_char * blob,int len,int prefixlen)872 *prefix_from_blob_ex(prefix_t *ret, u_char *blob, int len, int prefixlen)
873 {
874 int family, maxprefix;
875
876 switch (len) {
877 case 4:
878 /* Assume AF_INET */
879 family = AF_INET;
880 maxprefix = 32;
881 break;
882 case 16:
883 /* Assume AF_INET6 */
884 family = AF_INET6;
885 maxprefix = 128;
886 break;
887 default:
888 /* Who knows? */
889 return NULL;
890 }
891 if (prefixlen == -1)
892 prefixlen = maxprefix;
893 if (prefixlen < 0 || prefixlen > maxprefix)
894 return NULL;
895 return (New_Prefix2(family, blob, prefixlen, ret));
896 }
897
898 prefix_t
prefix_from_blob(u_char * blob,int len,int prefixlen)899 *prefix_from_blob(u_char *blob, int len, int prefixlen)
900 {
901 return (prefix_from_blob_ex(NULL, blob, len, prefixlen));
902 }
903
904 const char *
prefix_addr_ntop(prefix_t * prefix,char * buf,size_t len)905 prefix_addr_ntop(prefix_t *prefix, char *buf, size_t len)
906 {
907 return (inet_ntop(prefix->family, &prefix->add, buf, len));
908 }
909
910 const char *
prefix_ntop(prefix_t * prefix,char * buf,size_t len)911 prefix_ntop(prefix_t *prefix, char *buf, size_t len)
912 {
913 char addrbuf[128];
914
915 if (prefix_addr_ntop(prefix, addrbuf, sizeof(addrbuf)) == NULL)
916 return (NULL);
917 snprintf(buf, len, "%s/%d", addrbuf, prefix->bitlen);
918
919 return (buf);
920 }
921