1 |
michael |
5042 |
/* |
2 |
michael |
6259 |
* $Id$ |
3 |
michael |
5042 |
* Dave Plonka <plonka@doit.wisc.edu> |
4 |
|
|
* |
5 |
|
|
* This file had been called "radix.c" in the MRT sources. |
6 |
|
|
* |
7 |
|
|
* I renamed it to "patricia.c" since it's not an implementation of a general |
8 |
|
|
* radix trie. Also I pulled in various requirements from "prefix.c" and |
9 |
|
|
* "demo.c" so that 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 |
|
|
#include <assert.h> /* assert */ |
37 |
|
|
#include <ctype.h> /* isdigit */ |
38 |
|
|
#include <errno.h> /* errno */ |
39 |
|
|
#include <math.h> /* sin */ |
40 |
|
|
#include <stddef.h> /* NULL */ |
41 |
|
|
#include <stdio.h> /* sprintf, fprintf, stderr */ |
42 |
|
|
#include <stdlib.h> /* free, atol, calloc */ |
43 |
|
|
#include <string.h> /* memcpy, strchr, strlen */ |
44 |
|
|
#include <sys/types.h> /* BSD: for inet_addr */ |
45 |
|
|
#include <sys/socket.h> /* BSD, Linux: for inet_addr */ |
46 |
|
|
#include <netinet/in.h> /* BSD, Linux: for inet_addr */ |
47 |
|
|
#include <arpa/inet.h> /* BSD, Linux, Solaris: for inet_addr */ |
48 |
|
|
|
49 |
|
|
#include "patricia.h" |
50 |
michael |
5047 |
#include "memory.h" |
51 |
michael |
5042 |
|
52 |
|
|
/* { from prefix.c */ |
53 |
|
|
|
54 |
|
|
/* prefix_tochar |
55 |
|
|
* convert prefix information to bytes |
56 |
|
|
*/ |
57 |
michael |
5043 |
static u_char * |
58 |
michael |
5042 |
prefix_tochar (prefix_t * prefix) |
59 |
|
|
{ |
60 |
|
|
if (prefix == NULL) |
61 |
|
|
return (NULL); |
62 |
|
|
|
63 |
|
|
return ((u_char *) & prefix->add.sin); |
64 |
|
|
} |
65 |
|
|
|
66 |
michael |
5043 |
static int |
67 |
michael |
5042 |
comp_with_mask (void *addr, void *dest, u_int mask) |
68 |
|
|
{ |
69 |
|
|
|
70 |
|
|
if ( /* mask/8 == 0 || */ memcmp (addr, dest, mask / 8) == 0) { |
71 |
|
|
int n = mask / 8; |
72 |
|
|
int m = ((-1) << (8 - (mask % 8))); |
73 |
|
|
|
74 |
|
|
if (mask % 8 == 0 || (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m)) |
75 |
|
|
return (1); |
76 |
|
|
} |
77 |
|
|
return (0); |
78 |
|
|
} |
79 |
|
|
|
80 |
|
|
/* this allows imcomplete prefix */ |
81 |
michael |
5043 |
static int |
82 |
michael |
5042 |
my_inet_pton (int af, const char *src, void *dst) |
83 |
|
|
{ |
84 |
|
|
if (af == AF_INET) { |
85 |
|
|
int i, c, val; |
86 |
|
|
u_char xp[sizeof(struct in_addr)] = {0, 0, 0, 0}; |
87 |
|
|
|
88 |
|
|
for (i = 0; ; i++) { |
89 |
|
|
c = *src++; |
90 |
|
|
if (!isdigit (c)) |
91 |
|
|
return (-1); |
92 |
|
|
val = 0; |
93 |
|
|
do { |
94 |
|
|
val = val * 10 + c - '0'; |
95 |
|
|
if (val > 255) |
96 |
|
|
return (0); |
97 |
|
|
c = *src++; |
98 |
|
|
} while (c && isdigit (c)); |
99 |
|
|
xp[i] = val; |
100 |
|
|
if (c == '\0') |
101 |
|
|
break; |
102 |
|
|
if (c != '.') |
103 |
|
|
return (0); |
104 |
|
|
if (i >= 3) |
105 |
|
|
return (0); |
106 |
|
|
} |
107 |
|
|
memcpy (dst, xp, sizeof(struct in_addr)); |
108 |
|
|
return (1); |
109 |
|
|
} else if (af == AF_INET6) { |
110 |
|
|
return (inet_pton (af, src, dst)); |
111 |
|
|
} else { |
112 |
|
|
errno = EAFNOSUPPORT; |
113 |
|
|
return -1; |
114 |
|
|
} |
115 |
|
|
} |
116 |
|
|
|
117 |
|
|
#define PATRICIA_MAX_THREADS 16 |
118 |
|
|
|
119 |
|
|
/* |
120 |
|
|
* convert prefix information to ascii string with length |
121 |
|
|
* thread safe and (almost) re-entrant implementation |
122 |
|
|
*/ |
123 |
michael |
5043 |
static const char * |
124 |
michael |
5042 |
prefix_toa2x (prefix_t *prefix, char *buff, int with_len) |
125 |
|
|
{ |
126 |
|
|
if (prefix == NULL) |
127 |
|
|
return ("(Null)"); |
128 |
|
|
assert (prefix->ref_count >= 0); |
129 |
|
|
if (buff == NULL) { |
130 |
|
|
|
131 |
|
|
struct buffer { |
132 |
|
|
char buffs[PATRICIA_MAX_THREADS][48+5]; |
133 |
|
|
u_int i; |
134 |
|
|
} *buffp; |
135 |
|
|
|
136 |
|
|
# if 0 |
137 |
|
|
THREAD_SPECIFIC_DATA (struct buffer, buffp, 1); |
138 |
|
|
# else |
139 |
|
|
{ /* for scope only */ |
140 |
|
|
static struct buffer local_buff; |
141 |
|
|
buffp = &local_buff; |
142 |
|
|
} |
143 |
|
|
# endif |
144 |
|
|
if (buffp == NULL) { |
145 |
|
|
/* XXX should we report an error? */ |
146 |
|
|
return (NULL); |
147 |
|
|
} |
148 |
|
|
|
149 |
|
|
buff = buffp->buffs[buffp->i++%PATRICIA_MAX_THREADS]; |
150 |
|
|
} |
151 |
|
|
if (prefix->family == AF_INET) { |
152 |
|
|
u_char *a; |
153 |
|
|
assert (prefix->bitlen <= sizeof(struct in_addr) * 8); |
154 |
|
|
a = prefix_touchar (prefix); |
155 |
|
|
if (with_len) { |
156 |
|
|
sprintf (buff, "%d.%d.%d.%d/%d", a[0], a[1], a[2], a[3], |
157 |
|
|
prefix->bitlen); |
158 |
|
|
} |
159 |
|
|
else { |
160 |
|
|
sprintf (buff, "%d.%d.%d.%d", a[0], a[1], a[2], a[3]); |
161 |
|
|
} |
162 |
|
|
return (buff); |
163 |
|
|
} |
164 |
|
|
else if (prefix->family == AF_INET6) { |
165 |
michael |
5043 |
const char *r = inet_ntop(AF_INET6, &prefix->add.sin6, buff, 48 /* a guess value */ ); |
166 |
michael |
5042 |
if (r && with_len) { |
167 |
|
|
assert (prefix->bitlen <= sizeof(struct in6_addr) * 8); |
168 |
|
|
sprintf (buff + strlen (buff), "/%d", prefix->bitlen); |
169 |
|
|
} |
170 |
|
|
return (buff); |
171 |
|
|
} |
172 |
|
|
else |
173 |
|
|
return (NULL); |
174 |
|
|
} |
175 |
|
|
|
176 |
|
|
/* prefix_toa2 |
177 |
|
|
* convert prefix information to ascii string |
178 |
|
|
*/ |
179 |
michael |
5043 |
const char * |
180 |
michael |
5042 |
prefix_toa2 (prefix_t *prefix, char *buff) |
181 |
|
|
{ |
182 |
|
|
return (prefix_toa2x (prefix, buff, 0)); |
183 |
|
|
} |
184 |
|
|
|
185 |
|
|
/* prefix_toa |
186 |
|
|
*/ |
187 |
michael |
5043 |
const char * |
188 |
michael |
5042 |
prefix_toa (prefix_t * prefix) |
189 |
|
|
{ |
190 |
|
|
return (prefix_toa2 (prefix, (char *) NULL)); |
191 |
|
|
} |
192 |
|
|
|
193 |
|
|
prefix_t * |
194 |
|
|
New_Prefix2 (int family, void *dest, int bitlen, prefix_t *prefix) |
195 |
|
|
{ |
196 |
|
|
int dynamic_allocated = 0; |
197 |
|
|
int default_bitlen = sizeof(struct in_addr) * 8; |
198 |
|
|
|
199 |
|
|
if (family == AF_INET6) { |
200 |
|
|
default_bitlen = sizeof(struct in6_addr) * 8; |
201 |
|
|
if (prefix == NULL) { |
202 |
michael |
5047 |
prefix = MyCalloc(sizeof (prefix_t)); |
203 |
michael |
5042 |
dynamic_allocated++; |
204 |
|
|
} |
205 |
|
|
memcpy (&prefix->add.sin6, dest, sizeof(struct in6_addr)); |
206 |
|
|
} |
207 |
michael |
5044 |
else if (family == AF_INET) { |
208 |
michael |
5042 |
if (prefix == NULL) { |
209 |
michael |
5047 |
prefix = MyCalloc(sizeof (prefix4_t)); |
210 |
michael |
5042 |
dynamic_allocated++; |
211 |
|
|
} |
212 |
|
|
memcpy (&prefix->add.sin, dest, sizeof(struct in_addr)); |
213 |
|
|
} |
214 |
|
|
else { |
215 |
|
|
return (NULL); |
216 |
|
|
} |
217 |
|
|
|
218 |
|
|
prefix->bitlen = (bitlen >= 0)? bitlen: default_bitlen; |
219 |
|
|
prefix->family = family; |
220 |
|
|
prefix->ref_count = 0; |
221 |
|
|
if (dynamic_allocated) { |
222 |
|
|
prefix->ref_count++; |
223 |
|
|
} |
224 |
|
|
/* fprintf(stderr, "[C %s, %d]\n", prefix_toa (prefix), prefix->ref_count); */ |
225 |
|
|
return (prefix); |
226 |
|
|
} |
227 |
|
|
|
228 |
|
|
prefix_t * |
229 |
|
|
New_Prefix (int family, void *dest, int bitlen) |
230 |
|
|
{ |
231 |
|
|
return (New_Prefix2 (family, dest, bitlen, NULL)); |
232 |
|
|
} |
233 |
|
|
|
234 |
|
|
/* ascii2prefix |
235 |
|
|
*/ |
236 |
|
|
prefix_t * |
237 |
|
|
ascii2prefix (int family, char *string) |
238 |
|
|
{ |
239 |
|
|
u_long bitlen, maxbitlen = 0; |
240 |
|
|
char *cp; |
241 |
|
|
struct in_addr sin; |
242 |
|
|
struct in6_addr sin6; |
243 |
|
|
int result; |
244 |
|
|
char save[MAXLINE]; |
245 |
|
|
|
246 |
|
|
if (string == NULL) |
247 |
|
|
return (NULL); |
248 |
|
|
|
249 |
|
|
/* easy way to handle both families */ |
250 |
|
|
if (family == 0) { |
251 |
|
|
family = AF_INET; |
252 |
michael |
5044 |
|
253 |
michael |
5042 |
if (strchr (string, ':')) family = AF_INET6; |
254 |
|
|
} |
255 |
|
|
|
256 |
|
|
if (family == AF_INET) { |
257 |
|
|
maxbitlen = sizeof(struct in_addr) * 8; |
258 |
|
|
} |
259 |
|
|
else if (family == AF_INET6) { |
260 |
|
|
maxbitlen = sizeof(struct in6_addr) * 8; |
261 |
|
|
} |
262 |
|
|
|
263 |
|
|
if ((cp = strchr (string, '/')) != NULL) { |
264 |
|
|
bitlen = atol (cp + 1); |
265 |
|
|
/* *cp = '\0'; */ |
266 |
|
|
/* copy the string to save. Avoid destroying the string */ |
267 |
|
|
assert (cp - string < MAXLINE); |
268 |
|
|
memcpy (save, string, cp - string); |
269 |
|
|
save[cp - string] = '\0'; |
270 |
|
|
string = save; |
271 |
|
|
if (bitlen < 0 || bitlen > maxbitlen) |
272 |
|
|
bitlen = maxbitlen; |
273 |
|
|
} |
274 |
|
|
else { |
275 |
|
|
bitlen = maxbitlen; |
276 |
|
|
} |
277 |
|
|
|
278 |
|
|
if (family == AF_INET) { |
279 |
|
|
if ((result = my_inet_pton (AF_INET, string, &sin)) <= 0) |
280 |
|
|
return (NULL); |
281 |
|
|
return (New_Prefix (AF_INET, &sin, bitlen)); |
282 |
|
|
} |
283 |
|
|
else if (family == AF_INET6) { |
284 |
|
|
if ((result = inet_pton (AF_INET6, string, &sin6)) <= 0) |
285 |
|
|
return (NULL); |
286 |
michael |
5045 |
|
287 |
michael |
5042 |
return (New_Prefix (AF_INET6, &sin6, bitlen)); |
288 |
|
|
} |
289 |
|
|
else |
290 |
|
|
return (NULL); |
291 |
|
|
} |
292 |
|
|
|
293 |
michael |
5048 |
static prefix_t * |
294 |
michael |
5042 |
Ref_Prefix (prefix_t * prefix) |
295 |
|
|
{ |
296 |
|
|
if (prefix == NULL) |
297 |
|
|
return (NULL); |
298 |
|
|
if (prefix->ref_count == 0) { |
299 |
|
|
/* make a copy in case of a static prefix */ |
300 |
|
|
return (New_Prefix2 (prefix->family, &prefix->add, prefix->bitlen, NULL)); |
301 |
|
|
} |
302 |
|
|
prefix->ref_count++; |
303 |
|
|
/* fprintf(stderr, "[A %s, %d]\n", prefix_toa (prefix), prefix->ref_count); */ |
304 |
|
|
return (prefix); |
305 |
|
|
} |
306 |
|
|
|
307 |
michael |
5048 |
static void |
308 |
michael |
5042 |
Deref_Prefix (prefix_t * prefix) |
309 |
|
|
{ |
310 |
|
|
if (prefix == NULL) |
311 |
|
|
return; |
312 |
|
|
/* for secure programming, raise an assert. no static prefix can call this */ |
313 |
|
|
assert (prefix->ref_count > 0); |
314 |
|
|
|
315 |
|
|
prefix->ref_count--; |
316 |
|
|
assert (prefix->ref_count >= 0); |
317 |
|
|
if (prefix->ref_count <= 0) { |
318 |
michael |
5043 |
free (prefix); |
319 |
michael |
5042 |
return; |
320 |
|
|
} |
321 |
|
|
} |
322 |
|
|
|
323 |
|
|
/* } */ |
324 |
|
|
|
325 |
|
|
/* #define PATRICIA_DEBUG 1 */ |
326 |
|
|
|
327 |
|
|
static int num_active_patricia = 0; |
328 |
|
|
|
329 |
|
|
/* these routines support continuous mask only */ |
330 |
|
|
|
331 |
|
|
patricia_tree_t * |
332 |
|
|
New_Patricia (int maxbits) |
333 |
|
|
{ |
334 |
michael |
5047 |
patricia_tree_t *patricia = MyCalloc(sizeof *patricia); |
335 |
michael |
5042 |
|
336 |
|
|
patricia->maxbits = maxbits; |
337 |
|
|
patricia->head = NULL; |
338 |
|
|
patricia->num_active_node = 0; |
339 |
|
|
assert (maxbits <= PATRICIA_MAXBITS); /* XXX */ |
340 |
|
|
num_active_patricia++; |
341 |
|
|
return (patricia); |
342 |
|
|
} |
343 |
|
|
|
344 |
|
|
|
345 |
|
|
/* |
346 |
|
|
* if func is supplied, it will be called as func(node->data) |
347 |
|
|
* before deleting the node |
348 |
|
|
*/ |
349 |
|
|
|
350 |
|
|
void |
351 |
|
|
Clear_Patricia (patricia_tree_t *patricia, void_fn_t func) |
352 |
|
|
{ |
353 |
|
|
assert (patricia); |
354 |
|
|
if (patricia->head) { |
355 |
|
|
|
356 |
|
|
patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; |
357 |
|
|
patricia_node_t **Xsp = Xstack; |
358 |
|
|
patricia_node_t *Xrn = patricia->head; |
359 |
|
|
|
360 |
|
|
while (Xrn) { |
361 |
|
|
patricia_node_t *l = Xrn->l; |
362 |
|
|
patricia_node_t *r = Xrn->r; |
363 |
|
|
|
364 |
|
|
if (Xrn->prefix) { |
365 |
|
|
Deref_Prefix (Xrn->prefix); |
366 |
|
|
if (Xrn->data && func) |
367 |
|
|
func (Xrn->data); |
368 |
|
|
} |
369 |
|
|
else { |
370 |
|
|
assert (Xrn->data == NULL); |
371 |
|
|
} |
372 |
michael |
5047 |
MyFree (Xrn); |
373 |
michael |
5042 |
patricia->num_active_node--; |
374 |
|
|
|
375 |
|
|
if (l) { |
376 |
|
|
if (r) { |
377 |
|
|
*Xsp++ = r; |
378 |
|
|
} |
379 |
|
|
Xrn = l; |
380 |
|
|
} else if (r) { |
381 |
|
|
Xrn = r; |
382 |
|
|
} else if (Xsp != Xstack) { |
383 |
|
|
Xrn = *(--Xsp); |
384 |
|
|
} else { |
385 |
|
|
Xrn = NULL; |
386 |
|
|
} |
387 |
|
|
} |
388 |
|
|
} |
389 |
|
|
assert (patricia->num_active_node == 0); |
390 |
michael |
5047 |
/* MyFree (patricia); */ |
391 |
michael |
5042 |
} |
392 |
|
|
|
393 |
|
|
|
394 |
|
|
void |
395 |
|
|
Destroy_Patricia (patricia_tree_t *patricia, void_fn_t func) |
396 |
|
|
{ |
397 |
|
|
Clear_Patricia (patricia, func); |
398 |
michael |
5047 |
MyFree (patricia); |
399 |
michael |
5042 |
num_active_patricia--; |
400 |
|
|
} |
401 |
|
|
|
402 |
|
|
|
403 |
|
|
/* |
404 |
|
|
* if func is supplied, it will be called as func(node->prefix, node->data) |
405 |
|
|
*/ |
406 |
|
|
|
407 |
|
|
void |
408 |
|
|
patricia_process (patricia_tree_t *patricia, void_fn_t func) |
409 |
|
|
{ |
410 |
|
|
patricia_node_t *node; |
411 |
|
|
assert (func); |
412 |
|
|
|
413 |
|
|
PATRICIA_WALK (patricia->head, node) { |
414 |
|
|
func (node->prefix, node->data); |
415 |
|
|
} PATRICIA_WALK_END; |
416 |
|
|
} |
417 |
|
|
|
418 |
|
|
patricia_node_t * |
419 |
|
|
patricia_search_exact (patricia_tree_t *patricia, prefix_t *prefix) |
420 |
|
|
{ |
421 |
|
|
patricia_node_t *node; |
422 |
|
|
u_char *addr; |
423 |
|
|
u_int bitlen; |
424 |
|
|
|
425 |
|
|
assert (patricia); |
426 |
|
|
assert (prefix); |
427 |
|
|
assert (prefix->bitlen <= patricia->maxbits); |
428 |
|
|
|
429 |
|
|
if (patricia->head == NULL) |
430 |
|
|
return (NULL); |
431 |
|
|
|
432 |
|
|
node = patricia->head; |
433 |
|
|
addr = prefix_touchar (prefix); |
434 |
|
|
bitlen = prefix->bitlen; |
435 |
|
|
|
436 |
|
|
while (node->bit < bitlen) { |
437 |
|
|
|
438 |
|
|
if (BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) { |
439 |
|
|
#ifdef PATRICIA_DEBUG |
440 |
|
|
if (node->prefix) |
441 |
|
|
fprintf (stderr, "patricia_search_exact: take right %s/%d\n", |
442 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
443 |
|
|
else |
444 |
|
|
fprintf (stderr, "patricia_search_exact: take right at %u\n", |
445 |
|
|
node->bit); |
446 |
|
|
#endif /* PATRICIA_DEBUG */ |
447 |
|
|
node = node->r; |
448 |
|
|
} |
449 |
|
|
else { |
450 |
|
|
#ifdef PATRICIA_DEBUG |
451 |
|
|
if (node->prefix) |
452 |
|
|
fprintf (stderr, "patricia_search_exact: take left %s/%d\n", |
453 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
454 |
|
|
else |
455 |
|
|
fprintf (stderr, "patricia_search_exact: take left at %u\n", |
456 |
|
|
node->bit); |
457 |
|
|
#endif /* PATRICIA_DEBUG */ |
458 |
|
|
node = node->l; |
459 |
|
|
} |
460 |
|
|
|
461 |
|
|
if (node == NULL) |
462 |
|
|
return (NULL); |
463 |
|
|
} |
464 |
|
|
|
465 |
|
|
#ifdef PATRICIA_DEBUG |
466 |
|
|
if (node->prefix) |
467 |
|
|
fprintf (stderr, "patricia_search_exact: stop at %s/%d\n", |
468 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
469 |
|
|
else |
470 |
|
|
fprintf (stderr, "patricia_search_exact: stop at %u\n", node->bit); |
471 |
|
|
#endif /* PATRICIA_DEBUG */ |
472 |
|
|
if (node->bit > bitlen || node->prefix == NULL) |
473 |
|
|
return (NULL); |
474 |
|
|
assert (node->bit == bitlen); |
475 |
|
|
assert (node->bit == node->prefix->bitlen); |
476 |
|
|
if (comp_with_mask (prefix_tochar (node->prefix), prefix_tochar (prefix), |
477 |
|
|
bitlen)) { |
478 |
|
|
#ifdef PATRICIA_DEBUG |
479 |
|
|
fprintf (stderr, "patricia_search_exact: found %s/%d\n", |
480 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
481 |
|
|
#endif /* PATRICIA_DEBUG */ |
482 |
|
|
return (node); |
483 |
|
|
} |
484 |
|
|
return (NULL); |
485 |
|
|
} |
486 |
|
|
|
487 |
|
|
|
488 |
|
|
/* if inclusive != 0, "best" may be the given prefix itself */ |
489 |
|
|
patricia_node_t * |
490 |
|
|
patricia_search_best2 (patricia_tree_t *patricia, prefix_t *prefix, int inclusive) |
491 |
|
|
{ |
492 |
|
|
patricia_node_t *node; |
493 |
|
|
patricia_node_t *stack[PATRICIA_MAXBITS + 1]; |
494 |
|
|
u_char *addr; |
495 |
|
|
u_int bitlen; |
496 |
|
|
int cnt = 0; |
497 |
|
|
|
498 |
|
|
assert (patricia); |
499 |
|
|
assert (prefix); |
500 |
|
|
assert (prefix->bitlen <= patricia->maxbits); |
501 |
|
|
|
502 |
|
|
if (patricia->head == NULL) |
503 |
|
|
return (NULL); |
504 |
|
|
|
505 |
|
|
node = patricia->head; |
506 |
|
|
addr = prefix_touchar (prefix); |
507 |
|
|
bitlen = prefix->bitlen; |
508 |
|
|
|
509 |
|
|
while (node->bit < bitlen) { |
510 |
|
|
|
511 |
|
|
if (node->prefix) { |
512 |
|
|
#ifdef PATRICIA_DEBUG |
513 |
|
|
fprintf (stderr, "patricia_search_best: push %s/%d\n", |
514 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
515 |
|
|
#endif /* PATRICIA_DEBUG */ |
516 |
|
|
stack[cnt++] = node; |
517 |
|
|
} |
518 |
|
|
|
519 |
|
|
if (BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) { |
520 |
|
|
#ifdef PATRICIA_DEBUG |
521 |
|
|
if (node->prefix) |
522 |
|
|
fprintf (stderr, "patricia_search_best: take right %s/%d\n", |
523 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
524 |
|
|
else |
525 |
|
|
fprintf (stderr, "patricia_search_best: take right at %u\n", |
526 |
|
|
node->bit); |
527 |
|
|
#endif /* PATRICIA_DEBUG */ |
528 |
|
|
node = node->r; |
529 |
|
|
} |
530 |
|
|
else { |
531 |
|
|
#ifdef PATRICIA_DEBUG |
532 |
|
|
if (node->prefix) |
533 |
|
|
fprintf (stderr, "patricia_search_best: take left %s/%d\n", |
534 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
535 |
|
|
else |
536 |
|
|
fprintf (stderr, "patricia_search_best: take left at %u\n", |
537 |
|
|
node->bit); |
538 |
|
|
#endif /* PATRICIA_DEBUG */ |
539 |
|
|
node = node->l; |
540 |
|
|
} |
541 |
|
|
|
542 |
|
|
if (node == NULL) |
543 |
|
|
break; |
544 |
|
|
} |
545 |
|
|
|
546 |
|
|
if (inclusive && node && node->prefix) |
547 |
|
|
stack[cnt++] = node; |
548 |
|
|
|
549 |
|
|
#ifdef PATRICIA_DEBUG |
550 |
|
|
if (node == NULL) |
551 |
|
|
fprintf (stderr, "patricia_search_best: stop at null\n"); |
552 |
|
|
else if (node->prefix) |
553 |
|
|
fprintf (stderr, "patricia_search_best: stop at %s/%d\n", |
554 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
555 |
|
|
else |
556 |
|
|
fprintf (stderr, "patricia_search_best: stop at %u\n", node->bit); |
557 |
|
|
#endif /* PATRICIA_DEBUG */ |
558 |
|
|
|
559 |
|
|
if (cnt <= 0) |
560 |
|
|
return (NULL); |
561 |
|
|
|
562 |
|
|
while (--cnt >= 0) { |
563 |
|
|
node = stack[cnt]; |
564 |
|
|
#ifdef PATRICIA_DEBUG |
565 |
|
|
fprintf (stderr, "patricia_search_best: pop %s/%d\n", |
566 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
567 |
|
|
#endif /* PATRICIA_DEBUG */ |
568 |
|
|
if (comp_with_mask (prefix_tochar (node->prefix), |
569 |
|
|
prefix_tochar (prefix), |
570 |
|
|
node->prefix->bitlen) && node->prefix->bitlen <= bitlen) { |
571 |
|
|
#ifdef PATRICIA_DEBUG |
572 |
|
|
fprintf (stderr, "patricia_search_best: found %s/%d\n", |
573 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
574 |
|
|
#endif /* PATRICIA_DEBUG */ |
575 |
|
|
return (node); |
576 |
|
|
} |
577 |
|
|
} |
578 |
|
|
return (NULL); |
579 |
|
|
} |
580 |
|
|
|
581 |
|
|
|
582 |
|
|
patricia_node_t * |
583 |
|
|
patricia_search_best (patricia_tree_t *patricia, prefix_t *prefix) |
584 |
|
|
{ |
585 |
|
|
return (patricia_search_best2 (patricia, prefix, 1)); |
586 |
|
|
} |
587 |
|
|
|
588 |
|
|
|
589 |
|
|
patricia_node_t * |
590 |
|
|
patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix) |
591 |
|
|
{ |
592 |
|
|
patricia_node_t *node, *new_node, *parent, *glue; |
593 |
|
|
u_char *addr, *test_addr; |
594 |
|
|
u_int bitlen, check_bit, differ_bit; |
595 |
michael |
5049 |
int j, r; |
596 |
michael |
5042 |
|
597 |
|
|
assert (patricia); |
598 |
|
|
assert (prefix); |
599 |
|
|
assert (prefix->bitlen <= patricia->maxbits); |
600 |
|
|
|
601 |
|
|
if (patricia->head == NULL) { |
602 |
michael |
5047 |
node = MyCalloc(sizeof *node); |
603 |
michael |
5042 |
node->bit = prefix->bitlen; |
604 |
|
|
node->prefix = Ref_Prefix (prefix); |
605 |
|
|
node->parent = NULL; |
606 |
|
|
node->l = node->r = NULL; |
607 |
|
|
node->data = NULL; |
608 |
|
|
patricia->head = node; |
609 |
|
|
#ifdef PATRICIA_DEBUG |
610 |
|
|
fprintf (stderr, "patricia_lookup: new_node #0 %s/%d (head)\n", |
611 |
|
|
prefix_toa (prefix), prefix->bitlen); |
612 |
|
|
#endif /* PATRICIA_DEBUG */ |
613 |
|
|
patricia->num_active_node++; |
614 |
|
|
return (node); |
615 |
|
|
} |
616 |
|
|
|
617 |
|
|
addr = prefix_touchar (prefix); |
618 |
|
|
bitlen = prefix->bitlen; |
619 |
|
|
node = patricia->head; |
620 |
|
|
|
621 |
|
|
while (node->bit < bitlen || node->prefix == NULL) { |
622 |
|
|
|
623 |
|
|
if (node->bit < patricia->maxbits && |
624 |
|
|
BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) { |
625 |
|
|
if (node->r == NULL) |
626 |
|
|
break; |
627 |
|
|
#ifdef PATRICIA_DEBUG |
628 |
|
|
if (node->prefix) |
629 |
|
|
fprintf (stderr, "patricia_lookup: take right %s/%d\n", |
630 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
631 |
|
|
else |
632 |
|
|
fprintf (stderr, "patricia_lookup: take right at %u\n", node->bit); |
633 |
|
|
#endif /* PATRICIA_DEBUG */ |
634 |
|
|
node = node->r; |
635 |
|
|
} |
636 |
|
|
else { |
637 |
|
|
if (node->l == NULL) |
638 |
|
|
break; |
639 |
|
|
#ifdef PATRICIA_DEBUG |
640 |
|
|
if (node->prefix) |
641 |
|
|
fprintf (stderr, "patricia_lookup: take left %s/%d\n", |
642 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
643 |
|
|
else |
644 |
|
|
fprintf (stderr, "patricia_lookup: take left at %u\n", node->bit); |
645 |
|
|
#endif /* PATRICIA_DEBUG */ |
646 |
|
|
node = node->l; |
647 |
|
|
} |
648 |
|
|
|
649 |
|
|
assert (node); |
650 |
|
|
} |
651 |
|
|
|
652 |
|
|
assert (node->prefix); |
653 |
|
|
#ifdef PATRICIA_DEBUG |
654 |
|
|
fprintf (stderr, "patricia_lookup: stop at %s/%d\n", |
655 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
656 |
|
|
#endif /* PATRICIA_DEBUG */ |
657 |
|
|
|
658 |
|
|
test_addr = prefix_touchar (node->prefix); |
659 |
|
|
/* find the first bit different */ |
660 |
|
|
check_bit = (node->bit < bitlen)? node->bit: bitlen; |
661 |
|
|
differ_bit = 0; |
662 |
michael |
5049 |
for (unsigned int i = 0; i*8 < check_bit; i++) { |
663 |
michael |
5042 |
if ((r = (addr[i] ^ test_addr[i])) == 0) { |
664 |
|
|
differ_bit = (i + 1) * 8; |
665 |
|
|
continue; |
666 |
|
|
} |
667 |
|
|
/* I know the better way, but for now */ |
668 |
|
|
for (j = 0; j < 8; j++) { |
669 |
|
|
if (BIT_TEST (r, (0x80 >> j))) |
670 |
|
|
break; |
671 |
|
|
} |
672 |
|
|
/* must be found */ |
673 |
|
|
assert (j < 8); |
674 |
|
|
differ_bit = i * 8 + j; |
675 |
|
|
break; |
676 |
|
|
} |
677 |
|
|
if (differ_bit > check_bit) |
678 |
|
|
differ_bit = check_bit; |
679 |
|
|
#ifdef PATRICIA_DEBUG |
680 |
|
|
fprintf (stderr, "patricia_lookup: differ_bit %d\n", differ_bit); |
681 |
|
|
#endif /* PATRICIA_DEBUG */ |
682 |
|
|
|
683 |
|
|
parent = node->parent; |
684 |
|
|
while (parent && parent->bit >= differ_bit) { |
685 |
|
|
node = parent; |
686 |
|
|
parent = node->parent; |
687 |
|
|
#ifdef PATRICIA_DEBUG |
688 |
|
|
if (node->prefix) |
689 |
|
|
fprintf (stderr, "patricia_lookup: up to %s/%d\n", |
690 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
691 |
|
|
else |
692 |
|
|
fprintf (stderr, "patricia_lookup: up to %u\n", node->bit); |
693 |
|
|
#endif /* PATRICIA_DEBUG */ |
694 |
|
|
} |
695 |
|
|
|
696 |
|
|
if (differ_bit == bitlen && node->bit == bitlen) { |
697 |
|
|
if (node->prefix) { |
698 |
|
|
#ifdef PATRICIA_DEBUG |
699 |
|
|
fprintf (stderr, "patricia_lookup: found %s/%d\n", |
700 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
701 |
|
|
#endif /* PATRICIA_DEBUG */ |
702 |
|
|
return (node); |
703 |
|
|
} |
704 |
|
|
node->prefix = Ref_Prefix (prefix); |
705 |
|
|
#ifdef PATRICIA_DEBUG |
706 |
|
|
fprintf (stderr, "patricia_lookup: new node #1 %s/%d (glue mod)\n", |
707 |
|
|
prefix_toa (prefix), prefix->bitlen); |
708 |
|
|
#endif /* PATRICIA_DEBUG */ |
709 |
|
|
assert (node->data == NULL); |
710 |
|
|
return (node); |
711 |
|
|
} |
712 |
|
|
|
713 |
michael |
5047 |
new_node = MyCalloc(sizeof *new_node); |
714 |
michael |
5042 |
new_node->bit = prefix->bitlen; |
715 |
|
|
new_node->prefix = Ref_Prefix (prefix); |
716 |
|
|
new_node->parent = NULL; |
717 |
|
|
new_node->l = new_node->r = NULL; |
718 |
|
|
new_node->data = NULL; |
719 |
|
|
patricia->num_active_node++; |
720 |
|
|
|
721 |
|
|
if (node->bit == differ_bit) { |
722 |
|
|
new_node->parent = node; |
723 |
|
|
if (node->bit < patricia->maxbits && |
724 |
|
|
BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) { |
725 |
|
|
assert (node->r == NULL); |
726 |
|
|
node->r = new_node; |
727 |
|
|
} |
728 |
|
|
else { |
729 |
|
|
assert (node->l == NULL); |
730 |
|
|
node->l = new_node; |
731 |
|
|
} |
732 |
|
|
#ifdef PATRICIA_DEBUG |
733 |
|
|
fprintf (stderr, "patricia_lookup: new_node #2 %s/%d (child)\n", |
734 |
|
|
prefix_toa (prefix), prefix->bitlen); |
735 |
|
|
#endif /* PATRICIA_DEBUG */ |
736 |
|
|
return (new_node); |
737 |
|
|
} |
738 |
|
|
|
739 |
|
|
if (bitlen == differ_bit) { |
740 |
|
|
if (bitlen < patricia->maxbits && |
741 |
|
|
BIT_TEST (test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) { |
742 |
|
|
new_node->r = node; |
743 |
|
|
} |
744 |
|
|
else { |
745 |
|
|
new_node->l = node; |
746 |
|
|
} |
747 |
|
|
new_node->parent = node->parent; |
748 |
|
|
if (node->parent == NULL) { |
749 |
|
|
assert (patricia->head == node); |
750 |
|
|
patricia->head = new_node; |
751 |
|
|
} |
752 |
|
|
else if (node->parent->r == node) { |
753 |
|
|
node->parent->r = new_node; |
754 |
|
|
} |
755 |
|
|
else { |
756 |
|
|
node->parent->l = new_node; |
757 |
|
|
} |
758 |
|
|
node->parent = new_node; |
759 |
|
|
#ifdef PATRICIA_DEBUG |
760 |
|
|
fprintf (stderr, "patricia_lookup: new_node #3 %s/%d (parent)\n", |
761 |
|
|
prefix_toa (prefix), prefix->bitlen); |
762 |
|
|
#endif /* PATRICIA_DEBUG */ |
763 |
|
|
} |
764 |
|
|
else { |
765 |
michael |
5047 |
glue = MyCalloc(sizeof *glue); |
766 |
michael |
5042 |
glue->bit = differ_bit; |
767 |
|
|
glue->prefix = NULL; |
768 |
|
|
glue->parent = node->parent; |
769 |
|
|
glue->data = NULL; |
770 |
|
|
patricia->num_active_node++; |
771 |
|
|
if (differ_bit < patricia->maxbits && |
772 |
|
|
BIT_TEST (addr[differ_bit >> 3], 0x80 >> (differ_bit & 0x07))) { |
773 |
|
|
glue->r = new_node; |
774 |
|
|
glue->l = node; |
775 |
|
|
} |
776 |
|
|
else { |
777 |
|
|
glue->r = node; |
778 |
|
|
glue->l = new_node; |
779 |
|
|
} |
780 |
|
|
new_node->parent = glue; |
781 |
|
|
|
782 |
|
|
if (node->parent == NULL) { |
783 |
|
|
assert (patricia->head == node); |
784 |
|
|
patricia->head = glue; |
785 |
|
|
} |
786 |
|
|
else if (node->parent->r == node) { |
787 |
|
|
node->parent->r = glue; |
788 |
|
|
} |
789 |
|
|
else { |
790 |
|
|
node->parent->l = glue; |
791 |
|
|
} |
792 |
|
|
node->parent = glue; |
793 |
|
|
#ifdef PATRICIA_DEBUG |
794 |
|
|
fprintf (stderr, "patricia_lookup: new_node #4 %s/%d (glue+node)\n", |
795 |
|
|
prefix_toa (prefix), prefix->bitlen); |
796 |
|
|
#endif /* PATRICIA_DEBUG */ |
797 |
|
|
} |
798 |
|
|
return (new_node); |
799 |
|
|
} |
800 |
|
|
|
801 |
|
|
|
802 |
|
|
void |
803 |
|
|
patricia_remove (patricia_tree_t *patricia, patricia_node_t *node) |
804 |
|
|
{ |
805 |
|
|
patricia_node_t *parent, *child; |
806 |
|
|
|
807 |
|
|
assert (patricia); |
808 |
|
|
assert (node); |
809 |
|
|
|
810 |
|
|
if (node->r && node->l) { |
811 |
|
|
#ifdef PATRICIA_DEBUG |
812 |
|
|
fprintf (stderr, "patricia_remove: #0 %s/%d (r & l)\n", |
813 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
814 |
|
|
#endif /* PATRICIA_DEBUG */ |
815 |
|
|
|
816 |
|
|
/* this might be a placeholder node -- have to check and make sure |
817 |
|
|
* there is a prefix aossciated with it ! */ |
818 |
|
|
if (node->prefix != NULL) |
819 |
|
|
Deref_Prefix (node->prefix); |
820 |
|
|
node->prefix = NULL; |
821 |
|
|
/* Also I needed to clear data pointer -- masaki */ |
822 |
|
|
node->data = NULL; |
823 |
|
|
return; |
824 |
|
|
} |
825 |
|
|
|
826 |
|
|
if (node->r == NULL && node->l == NULL) { |
827 |
|
|
#ifdef PATRICIA_DEBUG |
828 |
|
|
fprintf (stderr, "patricia_remove: #1 %s/%d (!r & !l)\n", |
829 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
830 |
|
|
#endif /* PATRICIA_DEBUG */ |
831 |
|
|
parent = node->parent; |
832 |
|
|
Deref_Prefix (node->prefix); |
833 |
michael |
5047 |
MyFree (node); |
834 |
michael |
5042 |
patricia->num_active_node--; |
835 |
|
|
|
836 |
|
|
if (parent == NULL) { |
837 |
|
|
assert (patricia->head == node); |
838 |
|
|
patricia->head = NULL; |
839 |
|
|
return; |
840 |
|
|
} |
841 |
|
|
|
842 |
|
|
if (parent->r == node) { |
843 |
|
|
parent->r = NULL; |
844 |
|
|
child = parent->l; |
845 |
|
|
} |
846 |
|
|
else { |
847 |
|
|
assert (parent->l == node); |
848 |
|
|
parent->l = NULL; |
849 |
|
|
child = parent->r; |
850 |
|
|
} |
851 |
|
|
|
852 |
|
|
if (parent->prefix) |
853 |
|
|
return; |
854 |
|
|
|
855 |
|
|
/* we need to remove parent too */ |
856 |
|
|
|
857 |
|
|
if (parent->parent == NULL) { |
858 |
|
|
assert (patricia->head == parent); |
859 |
|
|
patricia->head = child; |
860 |
|
|
} |
861 |
|
|
else if (parent->parent->r == parent) { |
862 |
|
|
parent->parent->r = child; |
863 |
|
|
} |
864 |
|
|
else { |
865 |
|
|
assert (parent->parent->l == parent); |
866 |
|
|
parent->parent->l = child; |
867 |
|
|
} |
868 |
|
|
child->parent = parent->parent; |
869 |
michael |
5047 |
MyFree (parent); |
870 |
michael |
5042 |
patricia->num_active_node--; |
871 |
|
|
return; |
872 |
|
|
} |
873 |
|
|
|
874 |
|
|
#ifdef PATRICIA_DEBUG |
875 |
|
|
fprintf (stderr, "patricia_remove: #2 %s/%d (r ^ l)\n", |
876 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
877 |
|
|
#endif /* PATRICIA_DEBUG */ |
878 |
|
|
if (node->r) { |
879 |
|
|
child = node->r; |
880 |
|
|
} |
881 |
|
|
else { |
882 |
|
|
assert (node->l); |
883 |
|
|
child = node->l; |
884 |
|
|
} |
885 |
|
|
parent = node->parent; |
886 |
|
|
child->parent = parent; |
887 |
|
|
|
888 |
|
|
Deref_Prefix (node->prefix); |
889 |
michael |
5043 |
free (node); |
890 |
michael |
5042 |
patricia->num_active_node--; |
891 |
|
|
|
892 |
|
|
if (parent == NULL) { |
893 |
|
|
assert (patricia->head == node); |
894 |
|
|
patricia->head = child; |
895 |
|
|
return; |
896 |
|
|
} |
897 |
|
|
|
898 |
|
|
if (parent->r == node) { |
899 |
|
|
parent->r = child; |
900 |
|
|
} |
901 |
|
|
else { |
902 |
|
|
assert (parent->l == node); |
903 |
|
|
parent->l = child; |
904 |
|
|
} |
905 |
|
|
} |
906 |
|
|
|
907 |
|
|
/* { from demo.c */ |
908 |
|
|
|
909 |
|
|
patricia_node_t * |
910 |
|
|
make_and_lookup (patricia_tree_t *tree, char *string) |
911 |
|
|
{ |
912 |
|
|
prefix_t *prefix; |
913 |
|
|
patricia_node_t *node; |
914 |
|
|
|
915 |
|
|
prefix = ascii2prefix (AF_INET, string); |
916 |
|
|
printf ("make_and_lookup: %s/%d\n", prefix_toa (prefix), prefix->bitlen); |
917 |
|
|
node = patricia_lookup (tree, prefix); |
918 |
|
|
Deref_Prefix (prefix); |
919 |
|
|
return (node); |
920 |
|
|
} |
921 |
|
|
|
922 |
|
|
patricia_node_t * |
923 |
|
|
try_search_exact (patricia_tree_t *tree, char *string) |
924 |
|
|
{ |
925 |
|
|
prefix_t *prefix; |
926 |
|
|
patricia_node_t *node; |
927 |
|
|
|
928 |
|
|
prefix = ascii2prefix (AF_INET, string); |
929 |
|
|
printf ("try_search_exact: %s/%d\n", prefix_toa (prefix), prefix->bitlen); |
930 |
|
|
if ((node = patricia_search_exact (tree, prefix)) == NULL) { |
931 |
|
|
printf ("try_search_exact: not found\n"); |
932 |
|
|
} |
933 |
|
|
else { |
934 |
|
|
printf ("try_search_exact: %s/%d found\n", |
935 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
936 |
|
|
} |
937 |
|
|
Deref_Prefix (prefix); |
938 |
|
|
return (node); |
939 |
|
|
} |
940 |
|
|
|
941 |
|
|
void |
942 |
|
|
lookup_then_remove (patricia_tree_t *tree, char *string) |
943 |
|
|
{ |
944 |
|
|
patricia_node_t *node; |
945 |
|
|
|
946 |
|
|
if ((node = try_search_exact (tree, string))) |
947 |
|
|
patricia_remove (tree, node); |
948 |
|
|
} |
949 |
|
|
|
950 |
|
|
patricia_node_t * |
951 |
|
|
try_search_best (patricia_tree_t *tree, char *string) |
952 |
|
|
{ |
953 |
|
|
prefix_t *prefix; |
954 |
|
|
patricia_node_t *node; |
955 |
|
|
|
956 |
|
|
prefix = ascii2prefix (AF_INET, string); |
957 |
|
|
printf ("try_search_best: %s/%d\n", prefix_toa (prefix), prefix->bitlen); |
958 |
|
|
if ((node = patricia_search_best (tree, prefix)) == NULL) |
959 |
|
|
printf ("try_search_best: not found\n"); |
960 |
|
|
else |
961 |
|
|
printf ("try_search_best: %s/%d found\n", |
962 |
|
|
prefix_toa (node->prefix), node->prefix->bitlen); |
963 |
|
|
Deref_Prefix (prefix); |
964 |
|
|
return (node); |
965 |
|
|
} |
966 |
|
|
|
967 |
|
|
/* } */ |