Return to apatricia.h CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / libelwix / inc / elwix

version 3.7

    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.4 2015/06/25 17:53:49 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.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: 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);
  119: 
  120: /* { from demo.c */
  121: char *prefix_toa(prefix_t *prefix);
  122: prefix_t *ascii2prefix(int family, char *string);
  123: 
  124: #define addroute make_and_lookup
  125: patricia_node_t *make_and_lookup(patricia_tree_t *tree, char *string);
  126: #define delroute lookup_then_remove
  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);
  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 */