]>
Commit | Line | Data |
---|---|---|
212380e3 AC |
1 | /* |
2 | * $Id: patricia.h 6 2005-09-10 01:02:21Z nenolod $ | |
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 | #include <stdlib.h> | |
18 | #include <string.h> | |
19 | #include <sys/types.h> | |
20 | #include <netinet/in.h> | |
21 | #include <arpa/inet.h> | |
22 | #include <assert.h> | |
23 | #ifndef TESTING | |
24 | #include "class.h" | |
25 | #include "client.h" | |
26 | #include "common.h" | |
27 | #include "irc_string.h" | |
28 | #include "ircd.h" | |
29 | #include "numeric.h" | |
30 | #include "send.h" | |
31 | #include "memory.h" | |
32 | #include "config.h" | |
33 | #endif | |
34 | ||
35 | ||
36 | #ifndef FALSE | |
37 | #define FALSE 0 | |
38 | #endif | |
39 | #ifndef TRUE | |
40 | #define TRUE !(FALSE) | |
41 | #endif | |
42 | #ifndef INET6_ADDRSTRLEN | |
43 | #define INET6_ADDRSTRLEN 46 | |
44 | #endif | |
45 | ||
46 | /* typedef unsigned int u_int; */ | |
47 | typedef void (*void_fn_t) (); | |
48 | #define prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin) | |
49 | #define MAXLINE 1024 | |
50 | #define BIT_TEST(f, b) ((f) & (b)) | |
51 | ||
52 | #include <netinet/in.h> | |
53 | #include <sys/socket.h> | |
54 | ||
55 | typedef struct _prefix_t | |
56 | { | |
57 | u_short family; /* AF_INET | AF_INET6 */ | |
58 | u_short bitlen; /* same as mask? */ | |
59 | int ref_count; /* reference count */ | |
60 | union | |
61 | { | |
62 | struct in_addr sin; | |
63 | #ifdef IPV6 | |
64 | struct in6_addr sin6; | |
65 | #endif /* IPV6 */ | |
66 | } | |
67 | add; | |
68 | } | |
69 | prefix_t; | |
70 | ||
71 | ||
72 | typedef struct _patricia_node_t | |
73 | { | |
74 | u_int bit; /* flag if this node used */ | |
75 | prefix_t *prefix; /* who we are in patricia tree */ | |
76 | struct _patricia_node_t *l, *r; /* left and right children */ | |
77 | struct _patricia_node_t *parent; /* may be used */ | |
78 | void *data; | |
79 | } | |
80 | patricia_node_t; | |
81 | ||
82 | typedef struct _patricia_tree_t | |
83 | { | |
84 | patricia_node_t *head; | |
85 | u_int maxbits; /* for IP, 32 bit addresses */ | |
86 | int num_active_node; /* for debug purpose */ | |
87 | } | |
88 | patricia_tree_t; | |
89 | ||
90 | ||
91 | patricia_node_t *match_ip(patricia_tree_t * tree, struct sockaddr *ip); | |
92 | patricia_node_t *match_string(patricia_tree_t * tree, const char *string); | |
93 | patricia_node_t *match_exact_string(patricia_tree_t * tree, const char *string); | |
94 | patricia_node_t *patricia_search_exact(patricia_tree_t * patricia, prefix_t * prefix); | |
95 | patricia_node_t *patricia_search_best(patricia_tree_t * patricia, prefix_t * prefix); | |
96 | patricia_node_t *patricia_search_best2(patricia_tree_t * patricia, | |
97 | prefix_t * prefix, int inclusive); | |
98 | patricia_node_t *patricia_lookup(patricia_tree_t * patricia, prefix_t * prefix); | |
99 | ||
100 | void patricia_remove(patricia_tree_t * patricia, patricia_node_t * node); | |
101 | patricia_tree_t *New_Patricia(int maxbits); | |
102 | void Clear_Patricia(patricia_tree_t * patricia, void_fn_t func); | |
103 | void Destroy_Patricia(patricia_tree_t * patricia, void_fn_t func); | |
104 | void patricia_process(patricia_tree_t * patricia, void_fn_t func); | |
105 | void init_patricia(void); | |
106 | ||
107 | ||
108 | #if 0 | |
109 | prefix_t *ascii2prefix(int family, char *string); | |
110 | #endif | |
111 | patricia_node_t *make_and_lookup(patricia_tree_t * tree, const char *string); | |
112 | patricia_node_t *make_and_lookup_ip(patricia_tree_t * tree, struct sockaddr *, int bitlen); | |
113 | ||
114 | ||
115 | #define PATRICIA_MAXBITS 128 | |
116 | #define PATRICIA_NBIT(x) (0x80 >> ((x) & 0x7f)) | |
117 | #define PATRICIA_NBYTE(x) ((x) >> 3) | |
118 | ||
119 | #define PATRICIA_DATA_GET(node, type) (type *)((node)->data) | |
120 | #define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value)) | |
121 | ||
122 | #define PATRICIA_WALK(Xhead, Xnode) \ | |
123 | do { \ | |
124 | patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \ | |
125 | patricia_node_t **Xsp = Xstack; \ | |
126 | patricia_node_t *Xrn = (Xhead); \ | |
127 | while ((Xnode = Xrn)) { \ | |
128 | if (Xnode->prefix) | |
129 | ||
130 | #define PATRICIA_WALK_ALL(Xhead, Xnode) \ | |
131 | do { \ | |
132 | patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \ | |
133 | patricia_node_t **Xsp = Xstack; \ | |
134 | patricia_node_t *Xrn = (Xhead); \ | |
135 | while ((Xnode = Xrn)) { \ | |
136 | if (1) | |
137 | ||
138 | #define PATRICIA_WALK_BREAK { \ | |
139 | if (Xsp != Xstack) { \ | |
140 | Xrn = *(--Xsp); \ | |
141 | } else { \ | |
142 | Xrn = (patricia_node_t *) 0; \ | |
143 | } \ | |
144 | continue; } | |
145 | ||
146 | #define PATRICIA_WALK_END \ | |
147 | if (Xrn->l) { \ | |
148 | if (Xrn->r) { \ | |
149 | *Xsp++ = Xrn->r; \ | |
150 | } \ | |
151 | Xrn = Xrn->l; \ | |
152 | } else if (Xrn->r) { \ | |
153 | Xrn = Xrn->r; \ | |
154 | } else if (Xsp != Xstack) { \ | |
155 | Xrn = *(--Xsp); \ | |
156 | } else { \ | |
157 | Xrn = (patricia_node_t *) 0; \ | |
158 | } \ | |
159 | } \ | |
160 | } while (0) | |
161 | ||
162 | #endif /* _PATRICIA_H */ |