/[svn]/hopm/trunk/src/patricia.h
ViewVC logotype

Contents of /hopm/trunk/src/patricia.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 7852 - (show annotations)
Sun Nov 6 18:20:25 2016 UTC (4 years ago) by michael
File MIME type: text/x-csrc
File size: 5181 byte(s)
- Import patricia.h

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 /* { from defs.h */
40 #define prefix_touchar(prefix) ((unsigned char *)&(prefix)->add.sin)
41 #define MAXLINE 1024
42 #define BIT_TEST(f, b) ((f) & (b))
43 /* } */
44
45 #include <netinet/in.h> /* for struct in_addr */
46 #include <sys/socket.h> /* for AF_INET */
47
48 /* { from mrt.h */
49 typedef struct _prefix_t
50 {
51 unsigned short family; /* AF_INET | AF_INET6 */
52 unsigned short bitlen; /* same as mask? */
53 int ref_count; /* reference count */
54
55 union
56 {
57 struct in_addr sin;
58 struct in6_addr sin6;
59 } add;
60 } prefix_t;
61 /* } */
62
63 typedef struct _patricia_node_t
64 {
65 unsigned int bit; /* flag if this node used */
66 prefix_t *prefix; /* who we are in patricia tree */
67 struct _patricia_node_t *l, *r; /* left and right children */
68 struct _patricia_node_t *parent; /* may be used */
69 void *data; /* pointer to data */
70 void *user1; /* pointer to usr data (ex. route flap info) */
71 } patricia_node_t;
72
73 typedef struct _patricia_tree_t
74 {
75 patricia_node_t *head;
76 unsigned int maxbits; /* for IP, 32 bit addresses */
77 int num_active_node; /* for debug purpose */
78 } patricia_tree_t;
79
80
81 extern patricia_node_t *patricia_search_exact(patricia_tree_t *, prefix_t *);
82 extern patricia_node_t *patricia_search_best(patricia_tree_t *, prefix_t *);
83 extern patricia_node_t *patricia_search_best2(patricia_tree_t *, prefix_t *, int);
84 extern patricia_node_t *patricia_lookup(patricia_tree_t *, prefix_t *);
85 extern void patricia_remove(patricia_tree_t *, patricia_node_t *);
86 extern patricia_tree_t *patricia_new(unsigned int);
87 extern void patricia_clear(patricia_tree_t *, void (*)(void *));
88 extern void patricia_destroy(patricia_tree_t *, void (*)(void *));
89 extern void patricia_process(patricia_tree_t *, void (*)(prefix_t *, void *));
90 extern const char *patricia_prefix_toa(const prefix_t *, int);
91 extern void patricia_lookup_then_remove(patricia_tree_t *, const char *);
92 extern patricia_node_t *patricia_try_search_exact(patricia_tree_t *, const char *);
93 extern patricia_node_t *patricia_try_search_best(patricia_tree_t *, const char *);
94 extern patricia_node_t *patricia_try_search_exact_addr(patricia_tree_t *, struct sockaddr *, int);
95 extern patricia_node_t *patricia_try_search_best_addr(patricia_tree_t *, struct sockaddr *, int);
96
97 /* { from demo.c */
98 extern patricia_node_t *patricia_make_and_lookup(patricia_tree_t *, const char *);
99 /* } */
100
101 #define PATRICIA_MAXBITS (sizeof(struct in6_addr) * 8)
102 #define PATRICIA_NBIT(x) (0x80 >> ((x) & 0x7f))
103 #define PATRICIA_NBYTE(x) ((x) >> 3)
104
105 #define PATRICIA_DATA_GET(node, type) (type *)((node)->data)
106 #define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))
107
108 #define PATRICIA_WALK(Xhead, Xnode) \
109 do { \
110 patricia_node_t *Xstack[PATRICIA_MAXBITS + 1]; \
111 patricia_node_t **Xsp = Xstack; \
112 patricia_node_t *Xrn = (Xhead); \
113 while ((Xnode = Xrn)) { \
114 if (Xnode->prefix)
115
116 #define PATRICIA_WALK_ALL(Xhead, Xnode) \
117 do { \
118 patricia_node_t *Xstack[PATRICIA_MAXBITS + 1]; \
119 patricia_node_t **Xsp = Xstack; \
120 patricia_node_t *Xrn = (Xhead); \
121 while ((Xnode = Xrn)) { \
122 if (1)
123
124 #define PATRICIA_WALK_BREAK { \
125 if (Xsp != Xstack) { \
126 Xrn = *(--Xsp); \
127 } else { \
128 Xrn = (patricia_node_t *)0; \
129 } \
130 continue; }
131
132 #define PATRICIA_WALK_END \
133 if (Xrn->l) { \
134 if (Xrn->r) { \
135 *Xsp++ = Xrn->r; \
136 } \
137 Xrn = Xrn->l; \
138 } else if (Xrn->r) { \
139 Xrn = Xrn->r; \
140 } else if (Xsp != Xstack) { \
141 Xrn = *(--Xsp); \
142 } else { \
143 Xrn = (patricia_node_t *)0; \
144 } \
145 } \
146 } while (0)
147
148 #endif

Properties

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

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