Annotation of libelwix/inc/elwix/apatricia.h, revision 1.5

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.5     ! misho       6: * $Id: apatricia.h,v 1.4.74.2 2024/01/22 15:15:46 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: 
1.4       misho      15: Copyright 2004 - 2015
1.1       misho      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: 
1.2       misho     106: patricia_tree_t *New_Patricia(int maxbits);
                    107: void Destroy_Patricia(patricia_tree_t *patricia, void_fn_t func);
                    108: void Clear_Patricia(patricia_tree_t *patricia, void_fn_t func);
                    109: prefix_t *Ref_Prefix(prefix_t *prefix);
                    110: void Deref_Prefix(prefix_t * prefix);
                    111: 
                    112: patricia_node_t *patricia_lookup(patricia_tree_t *patricia, prefix_t *prefix);
                    113: void patricia_remove(patricia_tree_t *patricia, patricia_node_t *node);
                    114: void patricia_process(patricia_tree_t *patricia, void_fn_t func);
                    115: 
                    116: patricia_node_t *patricia_search_exact(patricia_tree_t *patricia, prefix_t *prefix);
                    117: patricia_node_t *patricia_search_best(patricia_tree_t *patricia, prefix_t *prefix);
                    118: patricia_node_t *patricia_search_best2(patricia_tree_t *patricia, prefix_t *prefix, int inclusive);
1.1       misho     119: 
                    120: /* { from demo.c */
1.2       misho     121: char *prefix_toa(prefix_t *prefix);
                    122: prefix_t *ascii2prefix(int family, char *string);
1.1       misho     123: 
                    124: #define addroute make_and_lookup
1.2       misho     125: patricia_node_t *make_and_lookup(patricia_tree_t *tree, char *string);
1.1       misho     126: #define delroute lookup_then_remove
1.2       misho     127: void lookup_then_remove(patricia_tree_t *tree, char *string);
                    128: patricia_node_t *try_search_exact(patricia_tree_t *tree, char *string);
                    129: patricia_node_t *try_search_best(patricia_tree_t *tree, char *string);
1.1       misho     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>