]>
Commit | Line | Data |
---|---|---|
db137867 AC |
1 | /* |
2 | * $Id: patricia.h 23020 2006-09-01 18:20:19Z androsyn $ | |
3 | * Dave Plonka <plonka@doit.wisc.edu> | |
4 | * | |
5 | * This product includes software developed by the University of Michigan, | |
55abcbb2 | 6 | * Merit Network, Inc., and their contributors. |
db137867 AC |
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 _RB_PATRICIA_H | |
16 | #define _RB_PATRICIA_H | |
17 | ||
18 | #ifndef FALSE | |
19 | #define FALSE 0 | |
20 | #endif | |
21 | #ifndef TRUE | |
22 | #define TRUE !(FALSE) | |
23 | #endif | |
24 | #ifndef INET6_ADDRSTRLEN | |
25 | #define INET6_ADDRSTRLEN 46 | |
26 | #endif | |
27 | ||
28 | /* typedef unsigned int u_int; */ | |
db137867 AC |
29 | #define rb_prefix_touchar(prefix) ((unsigned char *)&(prefix)->add.sin) |
30 | #define MAXLINE 1024 | |
31 | #define BIT_TEST(f, b) ((f) & (b)) | |
32 | ||
33 | typedef struct _rb_prefix_t | |
34 | { | |
3202e249 VY |
35 | unsigned short family; /* AF_INET | AF_INET6 */ |
36 | unsigned short bitlen; /* same as mask? */ | |
db137867 AC |
37 | int ref_count; /* reference count */ |
38 | union | |
39 | { | |
40 | struct in_addr sin; | |
41 | #ifdef RB_IPV6 | |
42 | struct in6_addr sin6; | |
43 | #endif /* RB_IPV6 */ | |
44 | } | |
45 | add; | |
46 | } | |
47 | rb_prefix_t; | |
48 | ||
49 | ||
50 | typedef struct _rb_patricia_node_t | |
51 | { | |
3202e249 | 52 | unsigned int bit; /* flag if this node used */ |
db137867 AC |
53 | rb_prefix_t *prefix; /* who we are in patricia tree */ |
54 | struct _rb_patricia_node_t *l, *r; /* left and right children */ | |
55 | struct _rb_patricia_node_t *parent; /* may be used */ | |
56 | void *data; | |
57 | } | |
58 | rb_patricia_node_t; | |
59 | ||
60 | typedef struct _rb_patricia_tree_t | |
61 | { | |
62 | rb_patricia_node_t *head; | |
3202e249 | 63 | unsigned int maxbits; /* for IP, 32 bit addresses */ |
db137867 AC |
64 | int num_active_node; /* for debug purpose */ |
65 | } | |
66 | rb_patricia_tree_t; | |
67 | ||
68 | ||
3202e249 VY |
69 | rb_patricia_node_t *rb_match_ip(rb_patricia_tree_t *tree, struct sockaddr *ip); |
70 | rb_patricia_node_t *rb_match_ip_exact(rb_patricia_tree_t *tree, struct sockaddr *ip, | |
71 | unsigned int len); | |
72 | rb_patricia_node_t *rb_match_string(rb_patricia_tree_t *tree, const char *string); | |
73 | rb_patricia_node_t *rb_match_exact_string(rb_patricia_tree_t *tree, const char *string); | |
74 | rb_patricia_node_t *rb_patricia_search_exact(rb_patricia_tree_t *patricia, rb_prefix_t *prefix); | |
75 | rb_patricia_node_t *rb_patricia_search_best(rb_patricia_tree_t *patricia, rb_prefix_t *prefix); | |
76 | rb_patricia_node_t *rb_patricia_search_best2(rb_patricia_tree_t *patricia, | |
77 | rb_prefix_t *prefix, int inclusive); | |
78 | rb_patricia_node_t *rb_patricia_lookup(rb_patricia_tree_t *patricia, rb_prefix_t *prefix); | |
db137867 | 79 | |
3202e249 | 80 | void rb_patricia_remove(rb_patricia_tree_t *patricia, rb_patricia_node_t *node); |
db137867 | 81 | rb_patricia_tree_t *rb_new_patricia(int maxbits); |
3202e249 VY |
82 | void rb_clear_patricia(rb_patricia_tree_t *patricia, void (*func) (void *)); |
83 | void rb_destroy_patricia(rb_patricia_tree_t *patricia, void (*func) (void *)); | |
84 | void rb_patricia_process(rb_patricia_tree_t *patricia, void (*func) (rb_prefix_t *, void *)); | |
db137867 AC |
85 | void rb_init_patricia(void); |
86 | ||
87 | ||
88 | #if 0 | |
89 | rb_prefix_t *ascii2prefix(int family, char *string); | |
90 | #endif | |
3202e249 VY |
91 | rb_patricia_node_t *make_and_lookup(rb_patricia_tree_t *tree, const char *string); |
92 | rb_patricia_node_t *make_and_lookup_ip(rb_patricia_tree_t *tree, struct sockaddr *, int bitlen); | |
db137867 AC |
93 | |
94 | ||
95 | #define RB_PATRICIA_MAXBITS 128 | |
96 | #define RB_PATRICIA_NBIT(x) (0x80 >> ((x) & 0x7f)) | |
97 | #define RB_PATRICIA_NBYTE(x) ((x) >> 3) | |
98 | ||
99 | #define RB_PATRICIA_DATA_GET(node, type) (type *)((node)->data) | |
100 | #define RB_PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value)) | |
101 | ||
102 | #define RB_PATRICIA_WALK(Xhead, Xnode) \ | |
103 | do { \ | |
104 | rb_patricia_node_t *Xstack[RB_PATRICIA_MAXBITS+1]; \ | |
105 | rb_patricia_node_t **Xsp = Xstack; \ | |
106 | rb_patricia_node_t *Xrn = (Xhead); \ | |
107 | while ((Xnode = Xrn)) { \ | |
108 | if (Xnode->prefix) | |
109 | ||
110 | #define RB_PATRICIA_WALK_ALL(Xhead, Xnode) \ | |
111 | do { \ | |
112 | rb_patricia_node_t *Xstack[RB_PATRICIA_MAXBITS+1]; \ | |
113 | rb_patricia_node_t **Xsp = Xstack; \ | |
114 | rb_patricia_node_t *Xrn = (Xhead); \ | |
115 | while ((Xnode = Xrn)) { \ | |
116 | if (1) | |
117 | ||
118 | #define RB_PATRICIA_WALK_BREAK { \ | |
119 | if (Xsp != Xstack) { \ | |
120 | Xrn = *(--Xsp); \ | |
121 | } else { \ | |
122 | Xrn = (rb_patricia_node_t *) 0; \ | |
123 | } \ | |
124 | continue; } | |
125 | ||
126 | #define RB_PATRICIA_WALK_END \ | |
127 | if (Xrn->l) { \ | |
128 | if (Xrn->r) { \ | |
129 | *Xsp++ = Xrn->r; \ | |
130 | } \ | |
131 | Xrn = Xrn->l; \ | |
132 | } else if (Xrn->r) { \ | |
133 | Xrn = Xrn->r; \ | |
134 | } else if (Xsp != Xstack) { \ | |
135 | Xrn = *(--Xsp); \ | |
136 | } else { \ | |
137 | Xrn = (rb_patricia_node_t *) 0; \ | |
138 | } \ | |
139 | } \ | |
140 | } while (0) | |
141 | ||
142 | #endif /* _RB_PATRICIA_H */ |