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