1 |
michael |
5042 |
/* |
2 |
|
|
* $Id: patricia.h,v 1.6 2005/12/07 20:53:01 dplonka Exp $ |
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 |
michael |
5046 |
* |
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 |
michael |
5042 |
*/ |
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 |
michael |
5792 |
#include <netinet/in.h> /* for struct in_addr */ |
53 |
michael |
5042 |
#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 |
michael |
5043 |
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 |
michael |
5042 |
int inclusive); |
96 |
michael |
5043 |
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 |
michael |
5042 |
|
102 |
michael |
5043 |
extern void patricia_process (patricia_tree_t *patricia, void_fn_t func); |
103 |
michael |
5042 |
|
104 |
michael |
5043 |
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 |
michael |
5042 |
/* { from demo.c */ |
108 |
|
|
|
109 |
michael |
5043 |
extern prefix_t * |
110 |
michael |
5042 |
ascii2prefix (int family, char *string); |
111 |
|
|
|
112 |
michael |
5043 |
extern patricia_node_t * |
113 |
michael |
5042 |
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 */ |