diff options
Diffstat (limited to 'src/fnettrace/radix.c')
-rw-r--r-- | src/fnettrace/radix.c | 104 |
1 files changed, 10 insertions, 94 deletions
diff --git a/src/fnettrace/radix.c b/src/fnettrace/radix.c index 96d6bcf41..c800c8708 100644 --- a/src/fnettrace/radix.c +++ b/src/fnettrace/radix.c | |||
@@ -25,6 +25,12 @@ | |||
25 | #include "radix.h" | 25 | #include "radix.h" |
26 | #include "fnettrace.h" | 26 | #include "fnettrace.h" |
27 | 27 | ||
28 | typedef struct rnode_t { | ||
29 | struct rnode_t *zero; | ||
30 | struct rnode_t *one; | ||
31 | char *name; | ||
32 | } RNode; | ||
33 | |||
28 | RNode *head = 0; | 34 | RNode *head = 0; |
29 | int radix_nodes = 0; | 35 | int radix_nodes = 0; |
30 | 36 | ||
@@ -35,10 +41,7 @@ static inline RNode *addOne(RNode *ptr, uint32_t ip, uint32_t mask, char *name) | |||
35 | RNode *node = malloc(sizeof(RNode)); | 41 | RNode *node = malloc(sizeof(RNode)); |
36 | if (!node) | 42 | if (!node) |
37 | errExit("malloc"); | 43 | errExit("malloc"); |
38 | radix_nodes++; | ||
39 | memset(node, 0, sizeof(RNode)); | 44 | memset(node, 0, sizeof(RNode)); |
40 | node->ip = ip; | ||
41 | node->mask = mask; | ||
42 | if (name) { | 45 | if (name) { |
43 | node->name = strdup(name); | 46 | node->name = strdup(name); |
44 | if (!node->name) | 47 | if (!node->name) |
@@ -57,8 +60,6 @@ static inline RNode *addZero(RNode *ptr, uint32_t ip, uint32_t mask, char *name) | |||
57 | if (!node) | 60 | if (!node) |
58 | errExit("malloc"); | 61 | errExit("malloc"); |
59 | memset(node, 0, sizeof(RNode)); | 62 | memset(node, 0, sizeof(RNode)); |
60 | node->ip = ip; | ||
61 | node->mask = mask; | ||
62 | if (name) { | 63 | if (name) { |
63 | node->name = strdup(name); | 64 | node->name = strdup(name); |
64 | if (!node->name) | 65 | if (!node->name) |
@@ -71,7 +72,7 @@ static inline RNode *addZero(RNode *ptr, uint32_t ip, uint32_t mask, char *name) | |||
71 | 72 | ||
72 | 73 | ||
73 | // add to radix tree | 74 | // add to radix tree |
74 | void radix_add(uint32_t ip, uint32_t mask, char *name) { | 75 | char *radix_add(uint32_t ip, uint32_t mask, char *name) { |
75 | assert(name); | 76 | assert(name); |
76 | uint32_t m = 0x80000000; | 77 | uint32_t m = 0x80000000; |
77 | uint32_t lastm = 0; | 78 | uint32_t lastm = 0; |
@@ -80,6 +81,7 @@ void radix_add(uint32_t ip, uint32_t mask, char *name) { | |||
80 | memset(head, 0, sizeof(RNode)); | 81 | memset(head, 0, sizeof(RNode)); |
81 | } | 82 | } |
82 | RNode *ptr = head; | 83 | RNode *ptr = head; |
84 | radix_nodes++; | ||
83 | 85 | ||
84 | int i; | 86 | int i; |
85 | for (i = 0; i < 32; i++, m >>= 1) { | 87 | for (i = 0; i < 32; i++, m >>= 1) { |
@@ -99,32 +101,12 @@ void radix_add(uint32_t ip, uint32_t mask, char *name) { | |||
99 | if (!ptr->name) | 101 | if (!ptr->name) |
100 | errExit("strdup"); | 102 | errExit("strdup"); |
101 | } | 103 | } |
102 | } | ||
103 | |||
104 | // find first match | ||
105 | char *radix_find_first(uint32_t ip) { | ||
106 | if (!head) | ||
107 | return NULL; | ||
108 | 104 | ||
109 | uint32_t m = 0x80000000; | 105 | return ptr->name; |
110 | RNode *ptr = head; | ||
111 | |||
112 | int i; | ||
113 | for (i = 0; i < 32; i++, m >>= 1) { | ||
114 | if (m & ip) | ||
115 | ptr = ptr->one; | ||
116 | else | ||
117 | ptr = ptr->zero; | ||
118 | if (!ptr) | ||
119 | return NULL; | ||
120 | if (ptr->name) | ||
121 | return ptr->name; | ||
122 | } | ||
123 | return NULL; | ||
124 | } | 106 | } |
125 | 107 | ||
126 | // find last match | 108 | // find last match |
127 | char *radix_find_last(uint32_t ip) { | 109 | char *radix_longest_prefix_match(uint32_t ip) { |
128 | if (!head) | 110 | if (!head) |
129 | return NULL; | 111 | return NULL; |
130 | 112 | ||
@@ -147,69 +129,3 @@ char *radix_find_last(uint32_t ip) { | |||
147 | return (rv)? rv->name: NULL; | 129 | return (rv)? rv->name: NULL; |
148 | } | 130 | } |
149 | 131 | ||
150 | static void radix_print_node(RNode *ptr, int level) { | ||
151 | assert(ptr); | ||
152 | |||
153 | int i; | ||
154 | for (i = 0; i < level; i++) | ||
155 | printf(" "); | ||
156 | printf("%08x %08x", ptr->ip, ptr->mask); | ||
157 | if (ptr->name) | ||
158 | printf(" (%s)\n", ptr->name); | ||
159 | else | ||
160 | printf(" (NULL)\n"); | ||
161 | |||
162 | if (ptr->zero) | ||
163 | radix_print_node(ptr->zero, level + 1); | ||
164 | if (ptr->one) | ||
165 | radix_print_node(ptr->one, level + 1); | ||
166 | } | ||
167 | |||
168 | void radix_print(void) { | ||
169 | if (!head) { | ||
170 | printf("radix tree is empty\n"); | ||
171 | return; | ||
172 | } | ||
173 | |||
174 | printf("radix IPv4 tree\n"); | ||
175 | radix_print_node(head, 0); | ||
176 | } | ||
177 | |||
178 | |||
179 | static inline int mask2cidr(uint32_t mask) { | ||
180 | uint32_t m = 0x80000000; | ||
181 | int i; | ||
182 | int cnt = 0; | ||
183 | for (i = 0; i < 32; i++, m = m >> 1) { | ||
184 | if (mask & m) | ||
185 | cnt++; | ||
186 | } | ||
187 | |||
188 | return cnt; | ||
189 | } | ||
190 | |||
191 | static void radix_build_list_node(RNode *ptr) { | ||
192 | assert(ptr); | ||
193 | |||
194 | |||
195 | if (ptr->name) { | ||
196 | printf("%d.%d.%d.%d/%d %s\n", PRINT_IP(ptr->ip), mask2cidr(ptr->mask), ptr->name); | ||
197 | return; | ||
198 | } | ||
199 | else { | ||
200 | if (ptr->zero) | ||
201 | radix_build_list_node(ptr->zero); | ||
202 | if (ptr->one) | ||
203 | radix_build_list_node(ptr->one); | ||
204 | } | ||
205 | } | ||
206 | |||
207 | void radix_build_list(void) { | ||
208 | if (!head) { | ||
209 | printf("radix tree is empty\n"); | ||
210 | return; | ||
211 | } | ||
212 | |||
213 | radix_build_list_node(head); | ||
214 | } | ||
215 | |||