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.6 2025/08/21 15:43:00 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 - 2024
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: #ifdef __cplusplus
106: extern "C" {
107: #endif
108:
109: patricia_tree_t *New_Patricia(int maxbits);
110: void Destroy_Patricia(patricia_tree_t *patricia, void_fn_t func);
111: void Clear_Patricia(patricia_tree_t *patricia, void_fn_t func);
112: prefix_t *Ref_Prefix(prefix_t *prefix);
113: void Deref_Prefix(prefix_t * prefix);
114:
115: patricia_node_t *patricia_lookup(patricia_tree_t *patricia, prefix_t *prefix);
116: void patricia_remove(patricia_tree_t *patricia, patricia_node_t *node);
117: void patricia_process(patricia_tree_t *patricia, void_fn_t func);
118:
119: patricia_node_t *patricia_search_exact(patricia_tree_t *patricia, prefix_t *prefix);
120: patricia_node_t *patricia_search_best(patricia_tree_t *patricia, prefix_t *prefix);
121: patricia_node_t *patricia_search_best2(patricia_tree_t *patricia, prefix_t *prefix, int inclusive);
122:
123: /* { from demo.c */
124: char *prefix_toa(prefix_t *prefix);
125: prefix_t *ascii2prefix(int family, char *string);
126:
127: #define addroute make_and_lookup
128: patricia_node_t *make_and_lookup(patricia_tree_t *tree, char *string);
129: #define delroute lookup_then_remove
130: void lookup_then_remove(patricia_tree_t *tree, char *string);
131: patricia_node_t *try_search_exact(patricia_tree_t *tree, char *string);
132: patricia_node_t *try_search_best(patricia_tree_t *tree, char *string);
133: /* } */
134:
135: /* { from defs.h */
136: #define prefix_touchar(prefix) ((u_char *) &(prefix)->add.sin)
137:
138: #define Delete free
139:
140: #define MAXLINE 1024
141: #define BIT_TEST(f, b) ((f) & (b))
142: /* } */
143:
144: #define PATRICIA_MAXBITS 128
145: #define PATRICIA_NBIT(x) (0x80 >> ((x) & 0x7f))
146: #define PATRICIA_NBYTE(x) ((x) >> 3)
147:
148: #define PATRICIA_DATA_GET(node, type) (type *)((node)->data)
149: #define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))
150:
151: #define PATRICIA_WALK(Xhead, Xnode) \
152: do { \
153: patricia_node_t *Xstack[PATRICIA_MAXBITS + 1]; \
154: patricia_node_t **Xsp = Xstack; \
155: patricia_node_t *Xrn = (Xhead); \
156: while ((Xnode = Xrn)) { \
157: if (Xnode->prefix)
158:
159: #define PATRICIA_WALK_ALL(Xhead, Xnode) \
160: do { \
161: patricia_node_t *Xstack[PATRICIA_MAXBITS + 1]; \
162: patricia_node_t **Xsp = Xstack; \
163: patricia_node_t *Xrn = (Xhead); \
164: while ((Xnode = Xrn)) { \
165: if (42)
166:
167: #define PATRICIA_WALK_BREAK { \
168: if (Xsp != Xstack) { \
169: Xrn = *(--Xsp); \
170: } else { \
171: Xrn = (patricia_node_t *) 0; \
172: } \
173: continue; }
174:
175: #define PATRICIA_WALK_END \
176: if (Xrn->l) { \
177: if (Xrn->r) { \
178: *Xsp++ = Xrn->r; \
179: } \
180: Xrn = Xrn->l; \
181: } else if (Xrn->r) { \
182: Xrn = Xrn->r; \
183: } else if (Xsp != Xstack) { \
184: Xrn = *(--Xsp); \
185: } else { \
186: Xrn = (patricia_node_t *) 0; \
187: } \
188: } \
189: } while (0)
190:
191: #ifdef __cplusplus
192: }
193: #endif
194:
195: #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