Annotation of libelwix/inc/elwix/apatricia.h, revision 1.1.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>
![[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 -] / libelwix / inc / elwix