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 */ |