Annotation of libaitio/inc/apatricia.h, revision 1.2
1.2 ! 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.1.2.1 2011/06/07 11:37:13 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
! 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>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to apatricia.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / libaitio / inc