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 |
7834 |
#include <netinet/in.h> /* for struct in_addr */ |
46 |
|
|
#include <sys/socket.h> /* for AF_INET */ |
47 |
michael |
5042 |
|
48 |
|
|
/* { from mrt.h */ |
49 |
michael |
7834 |
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 |
michael |
5042 |
|
55 |
michael |
7834 |
union |
56 |
|
|
{ |
57 |
|
|
struct in_addr sin; |
58 |
|
|
struct in6_addr sin6; |
59 |
|
|
} add; |
60 |
michael |
5042 |
} prefix_t; |
61 |
|
|
/* } */ |
62 |
|
|
|
63 |
michael |
7834 |
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 |
michael |
5042 |
} patricia_node_t; |
72 |
|
|
|
73 |
michael |
7834 |
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 |
michael |
5042 |
} patricia_tree_t; |
79 |
|
|
|
80 |
|
|
|
81 |
michael |
7834 |
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 *New_Patricia(int); |
87 |
|
|
extern void Clear_Patricia(patricia_tree_t *, void (*)(void *)); |
88 |
|
|
extern void Destroy_Patricia(patricia_tree_t *, void (*)(void *)); |
89 |
|
|
extern void patricia_process(patricia_tree_t *, void (*)(prefix_t *, void *)); |
90 |
|
|
extern const char *prefix_toa(prefix_t *, int); |
91 |
michael |
7822 |
extern void lookup_then_remove(patricia_tree_t *, const char *); |
92 |
|
|
extern patricia_node_t *try_search_exact(patricia_tree_t *, const char *); |
93 |
michael |
7836 |
extern patricia_node_t *try_search_best(patricia_tree_t *, const char *); |
94 |
michael |
7834 |
|
95 |
michael |
5042 |
/* { from demo.c */ |
96 |
michael |
7834 |
extern patricia_node_t *make_and_lookup(patricia_tree_t *, const char *); |
97 |
michael |
5042 |
/* } */ |
98 |
|
|
|
99 |
michael |
7834 |
#define PATRICIA_MAXBITS (sizeof(struct in6_addr) * 8) |
100 |
|
|
#define PATRICIA_NBIT(x) (0x80 >> ((x) & 0x7f)) |
101 |
|
|
#define PATRICIA_NBYTE(x) ((x) >> 3) |
102 |
michael |
5042 |
|
103 |
|
|
#define PATRICIA_DATA_GET(node, type) (type *)((node)->data) |
104 |
|
|
#define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value)) |
105 |
|
|
|
106 |
|
|
#define PATRICIA_WALK(Xhead, Xnode) \ |
107 |
michael |
7834 |
do { \ |
108 |
|
|
patricia_node_t *Xstack[PATRICIA_MAXBITS + 1]; \ |
109 |
|
|
patricia_node_t **Xsp = Xstack; \ |
110 |
|
|
patricia_node_t *Xrn = (Xhead); \ |
111 |
|
|
while ((Xnode = Xrn)) { \ |
112 |
|
|
if (Xnode->prefix) |
113 |
michael |
5042 |
|
114 |
|
|
#define PATRICIA_WALK_ALL(Xhead, Xnode) \ |
115 |
michael |
7834 |
do { \ |
116 |
|
|
patricia_node_t *Xstack[PATRICIA_MAXBITS + 1]; \ |
117 |
|
|
patricia_node_t **Xsp = Xstack; \ |
118 |
|
|
patricia_node_t *Xrn = (Xhead); \ |
119 |
|
|
while ((Xnode = Xrn)) { \ |
120 |
|
|
if (1) |
121 |
michael |
5042 |
|
122 |
|
|
#define PATRICIA_WALK_BREAK { \ |
123 |
michael |
7834 |
if (Xsp != Xstack) { \ |
124 |
|
|
Xrn = *(--Xsp); \ |
125 |
|
|
} else { \ |
126 |
|
|
Xrn = (patricia_node_t *)0; \ |
127 |
|
|
} \ |
128 |
|
|
continue; } |
129 |
michael |
5042 |
|
130 |
|
|
#define PATRICIA_WALK_END \ |
131 |
michael |
7834 |
if (Xrn->l) { \ |
132 |
|
|
if (Xrn->r) { \ |
133 |
|
|
*Xsp++ = Xrn->r; \ |
134 |
|
|
} \ |
135 |
|
|
Xrn = Xrn->l; \ |
136 |
|
|
} else if (Xrn->r) { \ |
137 |
|
|
Xrn = Xrn->r; \ |
138 |
|
|
} else if (Xsp != Xstack) { \ |
139 |
|
|
Xrn = *(--Xsp); \ |
140 |
|
|
} else { \ |
141 |
|
|
Xrn = (patricia_node_t *)0; \ |
142 |
|
|
} \ |
143 |
|
|
} \ |
144 |
|
|
} while (0) |
145 |
michael |
5042 |
|
146 |
michael |
7834 |
#endif |