Annotation of libelwix/src/patricia.c, revision 1.2.16.1

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

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>