/[svn]/ircd-hybrid/trunk/include/patricia.h
ViewVC logotype

Contents of /ircd-hybrid/trunk/include/patricia.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 6259 - (show annotations)
Sat Jul 11 12:18:43 2015 UTC (7 years, 7 months ago) by michael
File MIME type: text/x-csrc
File size: 5589 byte(s)
- Set keyword and eol-style properties

1 /*
2 * $Id$
3 * Dave Plonka <plonka@doit.wisc.edu>
4 *
5 * This file had been called "radix.h" in the MRT sources.
6 *
7 * I renamed it to "patricia.h" since it's not an implementation of a general
8 * radix trie. Also, pulled in various requirements from "mrt.h" and added
9 * some other things it could be used as a standalone API.
10 *
11 * Copyright (c) 1999-2013
12 *
13 * The Regents of the University of Michigan ("The Regents") and Merit
14 * Network, Inc.
15 *
16 * Redistributions of source code must retain the above copyright notice,
17 * this list of conditions and the following disclaimer.
18 *
19 * Redistributions in binary form must reproduce the above copyright
20 * notice, this list of conditions and the following disclaimer in the
21 * documentation and/or other materials provided with the distribution.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
29 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
30 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
31 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
33 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 */
35
36 #ifndef _PATRICIA_H
37 #define _PATRICIA_H
38
39 /* typedef unsigned int u_int; */
40 typedef void (*void_fn_t)();
41 /* { from defs.h */
42 #define prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin)
43 #define MAXLINE 1024
44 #define BIT_TEST(f, b) ((f) & (b))
45 /* } */
46
47 #define addroute make_and_lookup
48
49 #include <sys/types.h> /* for u_* definitions (on FreeBSD 5) */
50
51 #include <errno.h> /* for EAFNOSUPPORT */
52 #include <netinet/in.h> /* for struct in_addr */
53 #include <sys/socket.h> /* for AF_INET */
54
55 /* { from mrt.h */
56
57 typedef struct _prefix4_t {
58 u_short family; /* AF_INET | AF_INET6 */
59 u_short bitlen; /* same as mask? */
60 int ref_count; /* reference count */
61 struct in_addr sin;
62 } prefix4_t;
63
64 typedef struct _prefix_t {
65 u_short family; /* AF_INET | AF_INET6 */
66 u_short bitlen; /* same as mask? */
67 int ref_count; /* reference count */
68 union {
69 struct in_addr sin;
70 struct in6_addr sin6;
71 } add;
72 } prefix_t;
73
74 /* } */
75
76 typedef struct _patricia_node_t {
77 u_int bit; /* flag if this node used */
78 prefix_t *prefix; /* who we are in patricia tree */
79 struct _patricia_node_t *l, *r; /* left and right children */
80 struct _patricia_node_t *parent;/* may be used */
81 void *data; /* pointer to data */
82 void *user1; /* pointer to usr data (ex. route flap info) */
83 } patricia_node_t;
84
85 typedef struct _patricia_tree_t {
86 patricia_node_t *head;
87 u_int maxbits; /* for IP, 32 bit addresses */
88 int num_active_node; /* for debug purpose */
89 } patricia_tree_t;
90
91
92 extern patricia_node_t *patricia_search_exact (patricia_tree_t *patricia, prefix_t *prefix);
93 extern patricia_node_t *patricia_search_best (patricia_tree_t *patricia, prefix_t *prefix);
94 extern patricia_node_t * patricia_search_best2 (patricia_tree_t *patricia, prefix_t *prefix,
95 int inclusive);
96 extern patricia_node_t *patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix);
97 extern void patricia_remove (patricia_tree_t *patricia, patricia_node_t *node);
98 extern patricia_tree_t *New_Patricia (int maxbits);
99 extern void Clear_Patricia (patricia_tree_t *patricia, void_fn_t func);
100 extern void Destroy_Patricia (patricia_tree_t *patricia, void_fn_t func);
101
102 extern void patricia_process (patricia_tree_t *patricia, void_fn_t func);
103
104 extern const char *prefix_toa (prefix_t * prefix);
105 extern void lookup_then_remove(patricia_tree_t *, char *);
106 extern patricia_node_t *try_search_exact(patricia_tree_t *, char *);
107 /* { from demo.c */
108
109 extern prefix_t *
110 ascii2prefix (int family, char *string);
111
112 extern patricia_node_t *
113 make_and_lookup (patricia_tree_t *tree, char *string);
114
115 /* } */
116
117 #define PATRICIA_MAXBITS (sizeof(struct in6_addr) * 8)
118 #define PATRICIA_NBIT(x) (0x80 >> ((x) & 0x7f))
119 #define PATRICIA_NBYTE(x) ((x) >> 3)
120
121 #define PATRICIA_DATA_GET(node, type) (type *)((node)->data)
122 #define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))
123
124 #define PATRICIA_WALK(Xhead, Xnode) \
125 do { \
126 patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
127 patricia_node_t **Xsp = Xstack; \
128 patricia_node_t *Xrn = (Xhead); \
129 while ((Xnode = Xrn)) { \
130 if (Xnode->prefix)
131
132 #define PATRICIA_WALK_ALL(Xhead, Xnode) \
133 do { \
134 patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
135 patricia_node_t **Xsp = Xstack; \
136 patricia_node_t *Xrn = (Xhead); \
137 while ((Xnode = Xrn)) { \
138 if (1)
139
140 #define PATRICIA_WALK_BREAK { \
141 if (Xsp != Xstack) { \
142 Xrn = *(--Xsp); \
143 } else { \
144 Xrn = (patricia_node_t *) 0; \
145 } \
146 continue; }
147
148 #define PATRICIA_WALK_END \
149 if (Xrn->l) { \
150 if (Xrn->r) { \
151 *Xsp++ = Xrn->r; \
152 } \
153 Xrn = Xrn->l; \
154 } else if (Xrn->r) { \
155 Xrn = Xrn->r; \
156 } else if (Xsp != Xstack) { \
157 Xrn = *(--Xsp); \
158 } else { \
159 Xrn = (patricia_node_t *) 0; \
160 } \
161 } \
162 } while (0)
163
164 #endif /* _PATRICIA_H */

Properties

Name Value
svn:eol-style native
svn:keywords Id Revision

svnadmin@ircd-hybrid.org
ViewVC Help
Powered by ViewVC 1.1.30