Annotation of libelwix/src/patricia.c.bak, revision 1.1.2.1

1.1.2.1 ! misho       1: /*************************************************************************
        !             2: * (C) 2007 AITNET ltd - Sofia/Bulgaria - <misho@aitnet.org>
        !             3: *  by Michael Pounov <misho@elwix.org>
        !             4: *
        !             5: * $Author: misho $
        !             6: * $Id: patricia.c,v 1.5 2015/06/25 17:53:50 misho Exp $
        !             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 - 2015
        !            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: 
        !           216: char *prefix_toa(prefix_t * prefix)
        !           217: {
        !           218:     return prefix_toa2x(prefix, NULL, 0);
        !           219: }
        !           220: 
        !           221: prefix_t *ascii2prefix(int family, char *string)
        !           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;
        !           260:                if (bitlen > maxbitlen)
        !           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: 
        !           282: prefix_t *Ref_Prefix(prefix_t *prefix)
        !           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: 
        !           296: void Deref_Prefix(prefix_t *prefix)
        !           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 */
        !           312: patricia_tree_t *New_Patricia(int maxbits)
        !           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:  */
        !           333: void Clear_Patricia(patricia_tree_t *patricia, void_fn_t func)
        !           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: 
        !           371: void Destroy_Patricia(patricia_tree_t *patricia, void_fn_t func)
        !           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:  */
        !           382: void patricia_process(patricia_tree_t *patricia, void_fn_t func)
        !           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: 
        !           394: patricia_node_t *patricia_search_exact(patricia_tree_t *patricia, prefix_t *prefix)
        !           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 */
        !           462: patricia_node_t *patricia_search_best2(patricia_tree_t *patricia, prefix_t *prefix, int inclusive)
        !           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: 
        !           552: patricia_node_t *patricia_search_best(patricia_tree_t *patricia, prefix_t *prefix)
        !           553: {
        !           554:     return patricia_search_best2(patricia, prefix, 1);
        !           555: }
        !           556: 
        !           557: 
        !           558: patricia_node_t *patricia_lookup(patricia_tree_t *patricia, prefix_t *prefix)
        !           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: 
        !           762: void patricia_remove(patricia_tree_t *patricia, patricia_node_t *node)
        !           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: 
        !           863: void lookup_then_remove(patricia_tree_t *tree, char *string)
        !           864: {
        !           865:        patricia_node_t *node;
        !           866: 
        !           867:        if ((node = try_search_exact(tree, string)))
        !           868:                patricia_remove(tree, node);
        !           869: }
        !           870: 
        !           871: patricia_node_t *make_and_lookup(patricia_tree_t *tree, char *string)
        !           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: 
        !           886: patricia_node_t *try_search_exact(patricia_tree_t *tree, char *string)
        !           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: 
        !           907: patricia_node_t *try_search_best(patricia_tree_t *tree, char *string)
        !           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>