Annotation of libelwix/inc/elwix/apatricia.h, revision 1.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 $
        !             6: * $Id: apatricia.h,v 1.2 2011/06/07 11:49:39 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, 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.h" in the MRT sources.
        !            51:  *
        !            52:  * I renamed it to "apatricia.h" since it's not an implementation of a general
        !            53:  * radix trie.  Also, pulled in various requirements from "mrt.h" and added
        !            54:  * some other things it could be used as a standalone API.
        !            55:  *
        !            56:  * Added and patched existing code by AITNET - Michael Pounov <misho@aitbg.com>
        !            57:  */
        !            58: #ifndef __APATRICIA_H
        !            59: #define __APATRICIA_H
        !            60: 
        !            61: #include <netinet/in.h> /* for struct in_addr */
        !            62: #include <sys/socket.h> /* for AF_INET */
        !            63: 
        !            64: /* typedef unsigned int u_int; in most cases is NULL for functions parameter */
        !            65: typedef void (*void_fn_t)();
        !            66: 
        !            67: /* { from mrt.h */
        !            68: 
        !            69: typedef struct _prefix4_t {
        !            70:     u_short            family;         /* AF_INET | AF_INET6 */
        !            71:     u_short            bitlen;         /* same as mask? */
        !            72:     int                        ref_count;      /* reference count */
        !            73:     struct in_addr     sin;
        !            74: } prefix4_t;
        !            75: 
        !            76: typedef struct _prefix_t {
        !            77:     u_short            family;         /* AF_INET | AF_INET6 */
        !            78:     u_short            bitlen;         /* same as mask? */
        !            79:     int                        ref_count;      /* reference count */
        !            80:     union {
        !            81:                struct in_addr  sin;
        !            82: #ifdef HAVE_IPV6
        !            83:                struct in6_addr sin6;
        !            84: #endif /* IPV6 */
        !            85:     } add;
        !            86: } prefix_t;
        !            87: 
        !            88: /* } */
        !            89: 
        !            90: typedef struct _patricia_node_t {
        !            91:    u_int                       bit;            /* flag if this node used */
        !            92:    prefix_t                    *prefix;        /* who we are in patricia tree */
        !            93:    struct _patricia_node_t     *l, *r;         /* left and right children */
        !            94:    struct _patricia_node_t     *parent;        /* may be used */
        !            95:    void                                *data;          /* pointer to data */
        !            96:    void                                *user1;         /* pointer to usr data (ex. route flap info) */
        !            97: } patricia_node_t;
        !            98: 
        !            99: typedef struct _patricia_tree_t {
        !           100:    patricia_node_t     *head;
        !           101:    u_int               maxbits;                /* for IP, 32 bit addresses */
        !           102:    int                 num_active_node;        /* for debug purpose */
        !           103: } patricia_tree_t;
        !           104: 
        !           105: 
        !           106: inline patricia_tree_t *New_Patricia(int maxbits);
        !           107: inline void Destroy_Patricia(patricia_tree_t *patricia, void_fn_t func);
        !           108: inline void Clear_Patricia(patricia_tree_t *patricia, void_fn_t func);
        !           109: inline prefix_t *Ref_Prefix(prefix_t *prefix);
        !           110: inline void Deref_Prefix(prefix_t * prefix);
        !           111: 
        !           112: inline patricia_node_t *patricia_lookup(patricia_tree_t *patricia, prefix_t *prefix);
        !           113: inline void patricia_remove(patricia_tree_t *patricia, patricia_node_t *node);
        !           114: inline void patricia_process(patricia_tree_t *patricia, void_fn_t func);
        !           115: 
        !           116: inline patricia_node_t *patricia_search_exact(patricia_tree_t *patricia, prefix_t *prefix);
        !           117: inline patricia_node_t *patricia_search_best(patricia_tree_t *patricia, prefix_t *prefix);
        !           118: inline patricia_node_t *patricia_search_best2(patricia_tree_t *patricia, prefix_t *prefix, int inclusive);
        !           119: 
        !           120: /* { from demo.c */
        !           121: inline char *prefix_toa(prefix_t *prefix);
        !           122: inline prefix_t *ascii2prefix(int family, char *string);
        !           123: 
        !           124: #define addroute make_and_lookup
        !           125: inline patricia_node_t *make_and_lookup(patricia_tree_t *tree, char *string);
        !           126: #define delroute lookup_then_remove
        !           127: inline void lookup_then_remove(patricia_tree_t *tree, char *string);
        !           128: inline patricia_node_t *try_search_exact(patricia_tree_t *tree, char *string);
        !           129: inline patricia_node_t *try_search_best(patricia_tree_t *tree, char *string);
        !           130: /* } */
        !           131: 
        !           132: /* { from defs.h */
        !           133: #define prefix_touchar(prefix) ((u_char *) &(prefix)->add.sin)
        !           134: 
        !           135: #define Delete free
        !           136: 
        !           137: #define MAXLINE                        1024
        !           138: #define BIT_TEST(f, b)         ((f) & (b))
        !           139: /* } */
        !           140: 
        !           141: #define PATRICIA_MAXBITS       128
        !           142: #define PATRICIA_NBIT(x)       (0x80 >> ((x) & 0x7f))
        !           143: #define PATRICIA_NBYTE(x)      ((x) >> 3)
        !           144: 
        !           145: #define PATRICIA_DATA_GET(node, type)  (type *)((node)->data)
        !           146: #define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))
        !           147: 
        !           148: #define PATRICIA_WALK(Xhead, Xnode) \
        !           149:     do { \
        !           150:         patricia_node_t *Xstack[PATRICIA_MAXBITS + 1]; \
        !           151:         patricia_node_t **Xsp = Xstack; \
        !           152:         patricia_node_t *Xrn = (Xhead); \
        !           153:         while ((Xnode = Xrn)) { \
        !           154:             if (Xnode->prefix)
        !           155: 
        !           156: #define PATRICIA_WALK_ALL(Xhead, Xnode) \
        !           157: do { \
        !           158:         patricia_node_t *Xstack[PATRICIA_MAXBITS + 1]; \
        !           159:         patricia_node_t **Xsp = Xstack; \
        !           160:         patricia_node_t *Xrn = (Xhead); \
        !           161:         while ((Xnode = Xrn)) { \
        !           162:            if (42)
        !           163: 
        !           164: #define PATRICIA_WALK_BREAK { \
        !           165:            if (Xsp != Xstack) { \
        !           166:                Xrn = *(--Xsp); \
        !           167:             } else { \
        !           168:                Xrn = (patricia_node_t *) 0; \
        !           169:            } \
        !           170:            continue; }
        !           171: 
        !           172: #define PATRICIA_WALK_END \
        !           173:             if (Xrn->l) { \
        !           174:                 if (Xrn->r) { \
        !           175:                     *Xsp++ = Xrn->r; \
        !           176:                 } \
        !           177:                 Xrn = Xrn->l; \
        !           178:             } else if (Xrn->r) { \
        !           179:                 Xrn = Xrn->r; \
        !           180:             } else if (Xsp != Xstack) { \
        !           181:                 Xrn = *(--Xsp); \
        !           182:             } else { \
        !           183:                 Xrn = (patricia_node_t *) 0; \
        !           184:             } \
        !           185:         } \
        !           186: } while (0)
        !           187: 
        !           188: #endif /* __APATRICIA_H */

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