]>
Commit | Line | Data |
---|---|---|
1 | /* | |
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 product includes software developed by the University of Michigan, | |
6 | * Merit Network, Inc., and their contributors. | |
7 | * | |
8 | * This file had been called "radix.h" in the MRT sources. | |
9 | * | |
10 | * I renamed it to "patricia.h" since it's not an implementation of a general | |
11 | * radix trie. Also, pulled in various requirements from "mrt.h" and added | |
12 | * some other things it could be used as a standalone API. | |
13 | */ | |
14 | ||
15 | #ifndef _PATRICIA_H | |
16 | #define _PATRICIA_H | |
17 | ||
18 | #include "../lib/irc_ipv6.h" | |
19 | ||
20 | typedef unsigned short u_short; | |
21 | typedef unsigned int u_int; | |
22 | typedef unsigned char u_char; | |
23 | ||
24 | /* typedef unsigned int u_int; */ | |
25 | typedef void (*void_fn_t)(); | |
26 | /* { from defs.h */ | |
27 | #define prefix_touchar(prefix) ((u_char *)&(prefix)->sin) | |
28 | #define MAXLINE 1024 | |
29 | /* } */ | |
30 | ||
31 | #include <sys/types.h> /* for u_* definitions (on FreeBSD 5) */ | |
32 | ||
33 | #include <errno.h> /* for EAFNOSUPPORT */ | |
34 | #ifndef EAFNOSUPPORT | |
35 | # defined EAFNOSUPPORT WSAEAFNOSUPPORT | |
36 | # include <winsock.h> | |
37 | #else | |
38 | # include <netinet/in.h> /* for struct in_addr */ | |
39 | #endif | |
40 | ||
41 | #include <sys/socket.h> /* for AF_INET */ | |
42 | ||
43 | /* { from mrt.h */ | |
44 | ||
45 | #define PATRICIA_MAXSLOTS 7 | |
46 | ||
47 | ||
48 | typedef struct _prefix_t { | |
49 | u_short bitlen; /* same as mask? */ | |
50 | int ref_count; /* reference count */ | |
51 | struct irc_in_addr sin; | |
52 | } prefix_t; | |
53 | ||
54 | union prefixes { | |
55 | struct _prefix_t prefix; | |
56 | union prefixes *next; | |
57 | }; | |
58 | ||
59 | /* } */ | |
60 | ||
61 | typedef struct _patricia_node_t { | |
62 | unsigned char bit; /* flag if this node used */ | |
63 | int usercount; /* number of users on a given node */ | |
64 | prefix_t *prefix; /* who we are in patricia tree */ | |
65 | struct _patricia_node_t *l, *r; /* left and right children */ | |
66 | struct _patricia_node_t *parent;/* may be used */ | |
67 | void *exts[PATRICIA_MAXSLOTS]; | |
68 | } patricia_node_t; | |
69 | ||
70 | typedef struct _patricia_tree_t { | |
71 | patricia_node_t *head; | |
72 | u_int maxbits; /* for IPv6, 128 bit addresses */ | |
73 | int num_active_node; /* for debug purpose */ | |
74 | } patricia_tree_t; | |
75 | ||
76 | extern patricia_tree_t *iptree; | |
77 | ||
78 | prefix_t *patricia_new_prefix (struct irc_in_addr *dest, int bitlen); | |
79 | prefix_t * patricia_ref_prefix (prefix_t * prefix); | |
80 | void patricia_deref_prefix (prefix_t * prefix); | |
81 | ||
82 | patricia_node_t *patricia_search_exact (patricia_tree_t *patricia, struct irc_in_addr *sin, unsigned char bitlen); | |
83 | patricia_node_t *patricia_search_best (patricia_tree_t *patricia, struct irc_in_addr *sin, unsigned char bitlen); | |
84 | patricia_node_t * patricia_search_best2 (patricia_tree_t *patricia, struct irc_in_addr *sin, unsigned char bitlen, | |
85 | int inclusive); | |
86 | patricia_node_t *patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix); | |
87 | void patricia_remove (patricia_tree_t *patricia, patricia_node_t *node); | |
88 | patricia_tree_t *patricia_new_tree (int maxbits); | |
89 | void patricia_clear_tree (patricia_tree_t *patricia, void_fn_t func); | |
90 | void patricia_destroy_tree (patricia_tree_t *patricia, void_fn_t func); | |
91 | void patricia_process (patricia_tree_t *patricia, void_fn_t func); | |
92 | ||
93 | patricia_node_t *patricia_new_node(patricia_tree_t *patricia, unsigned char bit,prefix_t *prefix); | |
94 | ||
95 | int registernodeext(const char *name); | |
96 | int findnodeext(const char *name); | |
97 | void releasenodeext(int index); | |
98 | ||
99 | void node_increment_usercount( patricia_node_t *node); | |
100 | void node_decrement_usercount( patricia_node_t *node); | |
101 | int is_normalized_ipmask( struct irc_in_addr *sin, unsigned char bitlen ); | |
102 | ||
103 | /* alloc */ | |
104 | void freeprefix (prefix_t *prefix); | |
105 | prefix_t *newprefix(); | |
106 | patricia_node_t *newnode(); | |
107 | void freenode (patricia_node_t *node); | |
108 | ||
109 | /* } */ | |
110 | ||
111 | patricia_node_t *refnode(patricia_tree_t *tree, struct irc_in_addr *sin, int bitlen); | |
112 | void derefnode(patricia_tree_t *tree, patricia_node_t *node); | |
113 | ||
114 | #define get_byte_for_bit(base, nr) (base)[(nr) >> 3] | |
115 | #define bigendian_bitfor(nr) (0x80 >> ((nr) & 0x07)) | |
116 | #define is_bit_set(base, nr) (get_byte_for_bit(base, nr) & bigendian_bitfor(nr)) | |
117 | ||
118 | #define PATRICIA_MAXBITS 128 | |
119 | ||
120 | #define PATRICIA_WALK(Xhead, Xnode) \ | |
121 | do { \ | |
122 | patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \ | |
123 | patricia_node_t **Xsp = Xstack; \ | |
124 | patricia_node_t *Xrn = (Xhead); \ | |
125 | while ((Xnode = Xrn)) { \ | |
126 | if (Xnode->prefix) | |
127 | ||
128 | #define PATRICIA_WALK_ALL(Xhead, Xnode) \ | |
129 | do { \ | |
130 | patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \ | |
131 | patricia_node_t **Xsp = Xstack; \ | |
132 | patricia_node_t *Xrn = (Xhead); \ | |
133 | while ((Xnode = Xrn)) { \ | |
134 | if (1) | |
135 | ||
136 | #define PATRICIA_WALK_BREAK { \ | |
137 | if (Xsp != Xstack) { \ | |
138 | Xrn = *(--Xsp); \ | |
139 | } else { \ | |
140 | Xrn = (patricia_node_t *) 0; \ | |
141 | } \ | |
142 | continue; } | |
143 | ||
144 | #define PATRICIA_WALK_END \ | |
145 | if (Xrn->l) { \ | |
146 | if (Xrn->r) { \ | |
147 | *Xsp++ = Xrn->r; \ | |
148 | } \ | |
149 | Xrn = Xrn->l; \ | |
150 | } else if (Xrn->r) { \ | |
151 | Xrn = Xrn->r; \ | |
152 | } else if (Xsp != Xstack) { \ | |
153 | Xrn = *(--Xsp); \ | |
154 | } else { \ | |
155 | Xrn = (patricia_node_t *) 0; \ | |
156 | } \ | |
157 | } \ | |
158 | } while (0) | |
159 | ||
160 | #define PATRICIA_WALK_CLEAR(Xhead, Xnode) \ | |
161 | patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \ | |
162 | patricia_node_t **Xsp = Xstack; \ | |
163 | patricia_node_t *Xrn = (Xhead); \ | |
164 | while ((Xnode = Xrn)) { \ | |
165 | patricia_node_t *l = Xrn->l; \ | |
166 | patricia_node_t *r = Xrn->r; \ | |
167 | ||
168 | #define PATRICIA_WALK_CLEAR_END \ | |
169 | if (l) { \ | |
170 | if (r) { \ | |
171 | *Xsp++ = r; \ | |
172 | } \ | |
173 | Xrn = l; \ | |
174 | } else if (r) { \ | |
175 | Xrn = r; \ | |
176 | } else if (Xsp != Xstack) { \ | |
177 | Xrn = *(--Xsp); \ | |
178 | } else { \ | |
179 | Xrn = (patricia_node_t *) 0; \ | |
180 | } \ | |
181 | } | |
182 | ||
183 | #endif /* _PATRICIA_H */ |