1 #if HAVE_CONFIG_H
2 #include "config.h"
3 #endif
4 
5 #include <ctype.h>
6 #include <errno.h>
7 #include <stdio.h>
8 #include <stdlib.h>
9 #include <string.h>
10 #include <strings.h>
11 
12 #include "sx_prefix.h"
13 #include "sx_report.h"
14 
15 int debug_aggregation=0;
16 extern int debug_expander;
17 
18 struct sx_prefix*
sx_prefix_alloc(struct sx_prefix * p)19 sx_prefix_alloc(struct sx_prefix* p)
20 {
21 	struct sx_prefix* sp=malloc(sizeof(struct sx_prefix));
22 	if(!sp) return NULL;
23 	if(p) {
24 		*sp=*p;
25 	} else {
26 		memset(sp,0,sizeof(struct sx_prefix));
27 	};
28 	return sp;
29 };
30 void
sx_prefix_destroy(struct sx_prefix * p)31 sx_prefix_destroy(struct sx_prefix* p)
32 {
33 	if(p) free(p);
34 };
35 
36 void
sx_prefix_adjust_masklen(struct sx_prefix * p)37 sx_prefix_adjust_masklen(struct sx_prefix* p)
38 {
39 	int nbytes=(p->family==AF_INET?4:16);
40 	int i;
41 	if(p->masklen==nbytes*8) return ; /* mask is all ones */
42 	for(i=nbytes-1;i>p->masklen/8;i--) {
43 		p->addr.addrs[i]=0;
44 	};
45 	for(i=1;i<=8-p->masklen%8;i++) {
46 		p->addr.addrs[p->masklen/8]&=(0xff<<i);
47 	};
48 };
49 
50 void
sx_prefix_mask(struct sx_prefix * p,struct sx_prefix * q)51 sx_prefix_mask(struct sx_prefix* p, struct sx_prefix* q)
52 {
53 	int i;
54 	memset(q->addr.addrs, 0, sizeof(q->addr.addrs));
55 	q->family=p->family;
56 	q->masklen=p->masklen;
57 	for(i=0;i<p->masklen/8;i++)
58 		q->addr.addrs[i]=0xff;
59 	for(i=1;i<=p->masklen%8;i++)
60 		q->addr.addrs[p->masklen/8]|=(1<<(8-i));
61 };
62 
63 void
sx_prefix_imask(struct sx_prefix * p,struct sx_prefix * q)64 sx_prefix_imask(struct sx_prefix* p, struct sx_prefix* q)
65 {
66 	int i;
67 	memset(q->addr.addrs, 0xff, sizeof(q->addr.addrs));
68 	q->family=p->family;
69 	q->masklen=p->masklen;
70 	for(i=0;i<p->masklen/8;i++)
71 		q->addr.addrs[i]=0;
72 	for(i=1;i<=p->masklen%8;i++)
73 		q->addr.addrs[p->masklen/8]&=~(1<<(8-i));
74 };
75 
76 
77 int
sx_prefix_parse(struct sx_prefix * p,int af,char * text)78 sx_prefix_parse(struct sx_prefix* p, int af, char* text)
79 {
80 	char* c=NULL;
81 	int masklen, ret;
82 	char mtext[INET6_ADDRSTRLEN+5];
83 	strlcpy(mtext, text, sizeof(mtext));
84 
85 	c=strchr(mtext,'/');
86 	if(c) {
87 		char* eod;
88 		*c=0;
89 		masklen=strtol(c+1,&eod,10);
90 		if(eod && eod[0] && !isspace(eod[0])) {
91 			*c='/';
92 			sx_report(SX_ERROR,"Invalid masklen in prefix %s\n", text);
93 			goto fixups;
94 		};
95 	} else {
96 		masklen=-1;
97 	};
98 
99 	if(!af) {
100 		if(strchr(mtext,':')) af=AF_INET6;
101 		else
102 			af=AF_INET;
103 	};
104 
105 	ret = inet_pton(af, mtext, &p->addr);
106 	if(ret != 1) {
107 		int aparts[4];
108 		/* contrary to documentation (man inet_ntop on FreeBSD),
109 		addresses with leading zeros are not parsed correctly. Try to
110 		workaround this issue manually */
111 		if (af==AF_INET && sscanf(mtext, "%i.%i.%i.%i", aparts,
112 			aparts+1, aparts+2, aparts+3) == 4 && aparts[0]>=0 &&
113 			aparts[0]<256 && aparts[1]>=0 && aparts[1]<256 &&
114 			aparts[2]>=0 && aparts[2]<256 && aparts[3]>=0 &&
115 			aparts[3]<256) {
116 			p->addr.addr.s_addr = htonl((aparts[0]<<24) +
117 				(aparts[1]<<16) + (aparts[2]<<8) + aparts[3]);
118 		} else {
119 			if(c) *c='/';
120 			sx_report(SX_ERROR,"Unable to parse prefix '%s', af=%i (%s), "
121 				"ret=%i\n", mtext, af, af==AF_INET ? "inet" : "inet6", ret);
122 			goto fixups;
123 		};
124 	};
125 
126 	if(af==AF_INET) {
127 		if(masklen==-1) p->masklen=32;
128 		else {
129 			if(masklen<0 || masklen>32) {
130 				p->masklen=32;
131 			} else {
132 				p->masklen=masklen;
133 			};
134 		};
135 	} else if(af==AF_INET6) {
136 		if(masklen==-1) p->masklen=128;
137 		else {
138 			if(masklen<0 || masklen>128) {
139 				p->masklen=128;
140 			} else {
141 				p->masklen=masklen;
142 			};
143 		};
144 	} else {
145 		sx_report(SX_ERROR,"Invalid address family %i\n", af);
146 		goto fixups;
147 	};
148 
149 	p->family=af;
150 	sx_prefix_adjust_masklen(p);
151 	if(c) *c='/';
152 
153 	return 1;
154 fixups:
155 	return 0;
156 };
157 
158 int
sx_prefix_isbitset(struct sx_prefix * p,int n)159 sx_prefix_isbitset(struct sx_prefix* p, int n)
160 {
161 	unsigned char s;
162 	/* bits outside the prefix considered unset */
163 	if(p->family==AF_INET && (n<0 || n>32)) return 0;
164 	else if(p->family==AF_INET6 && (n<0 || n>128)) return 0;
165 	s=p->addr.addrs[(n-1)/8];
166 	return (s&(0x80>>((n-1)%8)))?1:0;
167 };
168 
169 void
sx_prefix_setbit(struct sx_prefix * p,int n)170 sx_prefix_setbit(struct sx_prefix* p, int n)
171 {
172 	unsigned char* s;
173 	if (p->family == AF_INET && (n<0 || n>32)) return;
174 	else if (p->family == AF_INET6 && (n<0 || n>128)) return;
175 	s=p->addr.addrs+(n-1)/8;
176 	(*s)|=0x80>>((n-1)%8);
177 };
178 
179 
180 int
sx_radix_tree_insert_specifics(struct sx_radix_tree * t,struct sx_prefix p,unsigned min,unsigned max)181 sx_radix_tree_insert_specifics(struct sx_radix_tree* t, struct sx_prefix p,
182 	unsigned min, unsigned max)
183 {
184 	if (p.masklen >= min)
185 		sx_radix_tree_insert(t, &p);
186 	if (p.masklen+1 > max)
187 		return 1;
188 	p.masklen+=1;
189 	sx_radix_tree_insert_specifics(t, p, min, max);
190 	sx_prefix_setbit(&p, p.masklen);
191 	sx_radix_tree_insert_specifics(t, p, min, max);
192 	return 1;
193 };
194 
195 int
sx_prefix_range_parse(struct sx_radix_tree * tree,int af,int maxlen,char * text)196 sx_prefix_range_parse(struct sx_radix_tree* tree, int af, int maxlen,
197 	char* text)
198 {
199 	char* d=strchr(text, '^');
200 	struct sx_prefix p;
201 	unsigned long min, max;
202 
203 	if (!d || !d[1]) return 0;
204 	*d = 0;
205 
206 	if (!sx_prefix_parse(&p, 0, text)) {
207 		sx_report(SX_ERROR, "Unable to parse prefix %s^%s\n", text, d+1);
208 		return 0;
209 	};
210 	*d = '^';
211 	if (af && p.family != af) {
212 		SX_DEBUG(debug_expander, "Ignoring prefix %s, wrong af %i\n", text,
213 			p.family);
214 		return 0;
215 	};
216 	if (maxlen && p.masklen > maxlen) {
217 		SX_DEBUG(debug_expander, "Ignoring prefix %s, masklen %i > max "
218 			"masklen %u\n", text, p.masklen, maxlen);
219 		return 0;
220 	};
221 	if (d[1] == '-') {
222 		min=p.masklen+1;
223 		max=maxlen;
224 	} else if (d[1] == '+') {
225 		min=p.masklen;
226 		max=maxlen;
227 	} else if (isdigit(d[1])) {
228 		char* dm = NULL;
229 		min = strtoul(d+1, &dm, 10);
230 		if (dm && *dm == '-' && isdigit(dm[1])) {
231 			max = strtoul(dm+1, NULL, 10);
232 		} else if (dm && *dm) {
233 			sx_report(SX_ERROR, "Unable to parse prefix-range %s\n", text);
234 			return 0;
235 		};
236 	} else {
237 		sx_report(SX_ERROR, "Invalid prefix-range %s\n", text);
238 		return 0;
239 	};
240 	if (min < p.masklen) {
241 		sx_report(SX_ERROR, "Invalid prefix-range %s: min %lu < masklen %u\n",
242 			text, min, p.masklen);
243 		return 0;
244 	};
245 	if (af == AF_INET && max > 32) {
246 		sx_report(SX_ERROR, "Invalid prefix-range %s: max %lu > 32\n",
247 			text, max);
248 		return 0;
249 	} else if (af == AF_INET6 && max > 128) {
250 		sx_report(SX_ERROR, "Invalid ipv6 prefix-range %s: max %lu > 128\n",
251 			text, max);
252 		return 0;
253 	};
254 	if (max > maxlen)
255 		max = maxlen;
256 	SX_DEBUG(debug_expander, "parsed prefix-range %s as %lu-%lu (maxlen: %u)\n",
257 		text, min, max, maxlen);
258 	sx_radix_tree_insert_specifics(tree, p, min, max);
259 	return 1;
260 };
261 
262 struct sx_prefix*
sx_prefix_new(int af,char * text)263 sx_prefix_new(int af, char* text)
264 {
265 	struct sx_prefix* p=NULL;
266 
267 	if(!text) return NULL;
268 
269 	p=sx_prefix_alloc(NULL);
270 
271 	if(!p) return NULL;
272 	if(!sx_prefix_parse(p,af,text)) {
273 		sx_prefix_destroy(p);
274 		return NULL;
275 	};
276 	return p;
277 };
278 
279 int
sx_prefix_fprint(FILE * f,struct sx_prefix * p)280 sx_prefix_fprint(FILE* f, struct sx_prefix* p)
281 {
282 	char buffer[128];
283 	if(!p) {
284 		fprintf(f?f:stdout,"(null)");
285 		return 0;
286 	};
287 	inet_ntop(p->family,&p->addr,buffer,sizeof(buffer));
288 	return fprintf(f?f:stdout,"%s/%i",buffer,p->masklen);
289 };
290 
291 int
sx_prefix_snprintf_sep(struct sx_prefix * p,char * rbuffer,int srb,char * sep)292 sx_prefix_snprintf_sep(struct sx_prefix* p, char* rbuffer, int srb, char* sep)
293 {
294 	char buffer[128];
295 	if(!sep) sep="/";
296 	if(!p) {
297 		snprintf(rbuffer,srb,"(null)");
298 		return 0;
299 	};
300 	inet_ntop(p->family,&p->addr,buffer,sizeof(buffer));
301 	return snprintf(rbuffer,srb,"%s%s%i",buffer,sep,p->masklen);
302 };
303 
304 int
sx_prefix_snprintf(struct sx_prefix * p,char * rbuffer,int srb)305 sx_prefix_snprintf(struct sx_prefix* p, char* rbuffer, int srb)
306 {
307 	return sx_prefix_snprintf_sep(p, rbuffer, srb, "/");
308 };
309 
310 int
sx_prefix_snprintf_fmt(struct sx_prefix * p,char * buffer,int size,const char * name,const char * format)311 sx_prefix_snprintf_fmt(struct sx_prefix* p, char* buffer, int size,
312 	const char* name, const char* format)
313 {
314 	unsigned off=0;
315 	const char* c=format;
316 	struct sx_prefix q;
317 	while(*c) {
318 		if(*c=='%') {
319 			switch(*(c+1)) {
320 				case 'r':
321 				case 'n':
322 					inet_ntop(p->family,&p->addr,buffer+off,size-off);
323 					off=strlen(buffer);
324 					break;
325 				case 'l':
326 					off+=snprintf(buffer+off,size-off,"%i",p->masklen);
327 					break;
328 				case '%':
329 					buffer[off++]='%';
330 					break;
331 				case 'N':
332 					off+=snprintf(buffer+off,size-off,"%s",name);
333 					break;
334 				case 'm':
335 					sx_prefix_mask(p, &q);
336 					inet_ntop(p->family,&q.addr,buffer+off,size-off);
337 					off=strlen(buffer);
338 					break;
339 				case 'i':
340 					sx_prefix_imask(p, &q);
341 					inet_ntop(p->family,&q.addr,buffer+off,size-off);
342 					off=strlen(buffer);
343 					break;
344 				default :
345 					sx_report(SX_ERROR, "Unknown format char '%c'\n", *(c+1));
346 					return 0;
347 			};
348 			c+=2;
349 		} else if (*c=='\\') {
350 			switch(*(c+1)) {
351 				case 'n':
352 					buffer[off++]='\n'; break;
353 				case 't':
354 					buffer[off++]='\t'; break;
355 				case '\\':
356 					buffer[off++]='\\'; break;
357 				default:
358 					buffer[off++]=*(c+1);
359 					break;
360 			};
361 			c+=2;
362 		} else {
363 			buffer[off++]=*c;
364 			c++;
365 		};
366 	};
367 	return strlen(buffer);
368 };
369 
370 int
sx_prefix_jsnprintf(struct sx_prefix * p,char * rbuffer,int srb)371 sx_prefix_jsnprintf(struct sx_prefix* p, char* rbuffer, int srb)
372 {
373 	char buffer[128];
374 	if(!p) {
375 		snprintf(rbuffer,srb,"(null)");
376 		return 0;
377 	};
378 	inet_ntop(p->family,&p->addr,buffer,sizeof(buffer));
379 	return snprintf(rbuffer,srb,"%s\\/%i",buffer,p->masklen);
380 };
381 
382 struct sx_radix_tree*
sx_radix_tree_new(int af)383 sx_radix_tree_new(int af)
384 {
385 	struct sx_radix_tree* rt=malloc(sizeof(struct sx_radix_tree));
386 	if(!rt) {
387 		return NULL;
388 	};
389 	memset(rt,0,sizeof(struct sx_radix_tree));
390 	rt->family=af;
391 	return rt;
392 };
393 
394 int
sx_radix_tree_empty(struct sx_radix_tree * t)395 sx_radix_tree_empty(struct sx_radix_tree* t)
396 {
397 	return t->head == NULL;
398 };
399 
400 struct sx_radix_node*
sx_radix_node_new(struct sx_prefix * prefix)401 sx_radix_node_new(struct sx_prefix* prefix)
402 {
403 	struct sx_radix_node* rn=malloc(sizeof(struct sx_radix_node));
404 	if(!rn) return NULL;
405 	memset(rn,0,sizeof(struct sx_radix_node));
406 	if(prefix) {
407 		rn->prefix=*prefix; /* structure copy */
408 	};
409 	return rn;
410 };
411 
412 int
sx_prefix_eqbits(struct sx_prefix * a,struct sx_prefix * b)413 sx_prefix_eqbits(struct sx_prefix* a, struct sx_prefix* b)
414 {
415 	int i;
416 	int nbytes=(a->family==AF_INET?4:16);
417 	for(i=0;i<nbytes;i++) {
418 		if(a->addr.addrs[i]==b->addr.addrs[i]) continue;
419 		else {
420 			int j;
421 			for(j=0;j<8 && i*8+j<=a->masklen && i*8+j<=b->masklen;j++) {
422 				if((a->addr.addrs[i]&(0x80>>j))!=(b->addr.addrs[i]&(0x80>>j)))
423 					return i*8+j;
424 			};
425 		};
426 	};
427 	if(a->masklen<b->masklen) return a->masklen;
428 	return b->masklen;
429 };
430 
431 struct sx_prefix*
sx_prefix_overlay(struct sx_prefix * p,int n)432 sx_prefix_overlay(struct sx_prefix* p, int n)
433 {
434 	struct sx_prefix* sp=sx_prefix_alloc(p);
435 	sp->masklen=n;
436 	sx_prefix_adjust_masklen(sp);
437 	return sp;
438 };
439 
440 void
sx_radix_tree_unlink(struct sx_radix_tree * tree,struct sx_radix_node * node)441 sx_radix_tree_unlink(struct sx_radix_tree* tree, struct sx_radix_node* node)
442 {
443 next:
444 	if(node->r && node->l) {
445 		node->isGlue=1;
446 	} else if(node->r) {
447 		if(node->parent) {
448 			if(node->parent->r==node) {
449 				node->parent->r=node->r;
450 				node->r->parent=node->parent;
451 			} else if(node->parent->l==node) {
452 				node->parent->l=node->r;
453 				node->r->parent=node->parent;
454 			} else {
455 				sx_report(SX_ERROR,"Unlinking node which is not descendant "
456 					"of its parent\n");
457 			};
458 		} else if(tree->head==node) {
459 			/* only one case, really */
460 			tree->head=node->r;
461 			node->r->parent=NULL;
462 		} else {
463 			sx_report(SX_ERROR,"Unlinking node with no parent and not root\n");
464 		};
465 		return;
466 	} else if(node->l) {
467 		if(node->parent) {
468 			if(node->parent->r==node) {
469 				node->parent->r=node->l;
470 				node->l->parent=node->parent;
471 			} else if(node->parent->l==node) {
472 				node->parent->l=node->l;
473 				node->l->parent=node->parent;
474 			} else {
475 				sx_report(SX_ERROR,"Unlinking node which is not descendant "
476 					"of its parent\n");
477 			};
478 		} else if(tree->head==node) {
479 			tree->head=node->l;
480 			node->l->parent=NULL;
481 		} else {
482 			sx_report(SX_ERROR,"Unlinking node with no parent and not root\n");
483 		};
484 		return;
485 	} else {
486 		/* the only case - node does not have descendants */
487 		if(node->parent) {
488 			if(node->parent->l==node) node->parent->l=NULL;
489 			else if(node->parent->r==node) node->parent->r=NULL;
490 			else {
491 				sx_report(SX_ERROR,"Unlinking node which is not descendant "
492 					"of its parent\n");
493 			};
494 			if(node->parent->isGlue) {
495 				node=node->parent;
496 				goto next;
497 			};
498 		} else if(tree->head==node) {
499 			tree->head=NULL;
500 		} else {
501 			sx_report(SX_ERROR,"Unlinking node with no parent and not root\n");
502 		};
503 		return;
504 	};
505 };
506 
507 
508 struct sx_radix_node*
sx_radix_tree_lookup(struct sx_radix_tree * tree,struct sx_prefix * prefix)509 sx_radix_tree_lookup(struct sx_radix_tree* tree, struct sx_prefix* prefix)
510 {
511 	int eb;
512 	struct sx_radix_node* candidate=NULL, *chead;
513 
514 	if(!tree || !prefix) return NULL;
515 	if(tree->family!=prefix->family) return NULL;
516 	if(!tree->head) return NULL;
517 
518 	chead=tree->head;
519 
520 next:
521 	eb=sx_prefix_eqbits(&chead->prefix,prefix);
522 	if(eb==chead->prefix.masklen && eb==prefix->masklen) {
523 		/* they are equal */
524 		if(chead->isGlue) return candidate;
525 		return chead;
526 	} else if(eb<chead->prefix.masklen) {
527 		return candidate;
528 	} else if(eb<prefix->masklen) {
529 		/* it equals chead->masklen */
530 		if(sx_prefix_isbitset(prefix,eb+1)) {
531 			if(chead->r) {
532 				if(!chead->isGlue) {
533 					candidate=chead;
534 				};
535 				chead=chead->r;
536 				goto next;
537 			} else {
538 				if(chead->isGlue) return candidate;
539 				return chead;
540 			};
541 		} else {
542 			if(chead->l) {
543 				if(!chead->isGlue) {
544 					candidate=chead;
545 				};
546 				chead=chead->l;
547 				goto next;
548 			} else {
549 				if(chead->isGlue) return candidate;
550 				return chead;
551 			};
552 		};
553 	} else {
554 		char pbuffer[128], cbuffer[128];
555 		sx_prefix_snprintf(prefix,pbuffer,sizeof(pbuffer));
556 		sx_prefix_snprintf(&chead->prefix,cbuffer,sizeof(cbuffer));
557 		printf("Unreachible point... eb=%i, prefix=%s, chead=%s\n", eb,
558 			pbuffer, cbuffer);
559 		abort();
560 	};
561 };
562 
563 
564 struct sx_radix_node*
sx_radix_tree_insert(struct sx_radix_tree * tree,struct sx_prefix * prefix)565 sx_radix_tree_insert(struct sx_radix_tree* tree, struct sx_prefix* prefix)
566 {
567 	int eb;
568 	struct sx_radix_node** candidate=NULL, *chead;
569 
570 	if(!tree || !prefix) return NULL;
571 	if(tree->family!=prefix->family) {
572 		return NULL;
573 	};
574 	if(!tree->head) {
575 		tree->head=sx_radix_node_new(prefix);
576 		return tree->head;
577 	};
578 	candidate=&tree->head;
579 	chead=tree->head;
580 
581 next:
582 	eb=sx_prefix_eqbits(prefix,&chead->prefix);
583 	if(eb<prefix->masklen && eb<chead->prefix.masklen) {
584 		struct sx_prefix neoRoot=*prefix;
585 		struct sx_radix_node* rn, *ret=sx_radix_node_new(prefix);
586 		neoRoot.masklen=eb;
587 		sx_prefix_adjust_masklen(&neoRoot);
588 		rn=sx_radix_node_new(&neoRoot);
589 		if(!rn) {
590 			sx_report(SX_ERROR,"Unable to create node: %s\n", strerror(errno));
591 			return NULL;
592 		};
593 		if(sx_prefix_isbitset(prefix,eb+1)) {
594 			rn->l=chead;
595 			rn->r=ret;
596 		} else {
597 			rn->l=ret;
598 			rn->r=chead;
599 		};
600 		rn->parent=chead->parent;
601 		chead->parent=rn;
602 		ret->parent=rn;
603 		rn->isGlue=1;
604 		*candidate=rn;
605 		return ret;
606 	} else if(eb==prefix->masklen && eb<chead->prefix.masklen) {
607 		struct sx_radix_node* ret=sx_radix_node_new(prefix);
608 		if(sx_prefix_isbitset(&chead->prefix,eb+1)) {
609 			ret->r=chead;
610 		} else {
611 			ret->l=chead;
612 		};
613 		ret->parent=chead->parent;
614 		chead->parent=ret;
615 		*candidate=ret;
616 		return ret;
617 	} else if(eb==chead->prefix.masklen && eb<prefix->masklen) {
618 		if(sx_prefix_isbitset(prefix,eb+1)) {
619 			if(chead->r) {
620 				candidate=&chead->r;
621 				chead=chead->r;
622 				goto next;
623 			} else {
624 				chead->r=sx_radix_node_new(prefix);
625 				chead->r->parent=chead;
626 				return chead->r;
627 			};
628 		} else {
629 			if(chead->l) {
630 				candidate=&chead->l;
631 				chead=chead->l;
632 				goto next;
633 			} else {
634 				chead->l=sx_radix_node_new(prefix);
635 				chead->l->parent=chead;
636 				return chead->l;
637 			};
638 		};
639 	} else if(eb==chead->prefix.masklen && eb==prefix->masklen) {
640 		/* equal routes... */
641 		if(chead->isGlue) {
642 			chead->isGlue=0;
643 		};
644 		return chead;
645 	} else {
646 		char pbuffer[128], cbuffer[128];
647 		sx_prefix_snprintf(prefix,pbuffer,sizeof(pbuffer));
648 		sx_prefix_snprintf(&chead->prefix,cbuffer,sizeof(cbuffer));
649 		printf("Unreachible point... eb=%i, prefix=%s, chead=%s\n", eb,
650 			pbuffer, cbuffer);
651 		abort();
652 	};
653 };
654 
655 void
sx_radix_node_fprintf(struct sx_radix_node * node,void * udata)656 sx_radix_node_fprintf(struct sx_radix_node* node, void* udata)
657 {
658 	FILE* out=(udata?udata:stdout);
659 	char buffer[128];
660 	if(!node) {
661 		fprintf(out,"(null)\n");
662 	} else {
663 		sx_prefix_snprintf(&node->prefix,buffer,sizeof(buffer));
664 		fprintf(out,"%s %s\n", buffer, node->isGlue?"(glue)":"");
665 	};
666 };
667 
668 int
sx_radix_node_foreach(struct sx_radix_node * node,void (* func)(struct sx_radix_node *,void *),void * udata)669 sx_radix_node_foreach(struct sx_radix_node* node,
670 	void (*func)(struct sx_radix_node*, void*), void* udata)
671 {
672 	func(node,udata);
673 	if(node->l) sx_radix_node_foreach(node->l,func,udata);
674 	if(node->r) sx_radix_node_foreach(node->r,func,udata);
675 	return 0;
676 };
677 
678 int
sx_radix_tree_foreach(struct sx_radix_tree * tree,void (* func)(struct sx_radix_node *,void *),void * udata)679 sx_radix_tree_foreach(struct sx_radix_tree* tree,
680 	void (*func)(struct sx_radix_node*, void*), void* udata)
681 {
682 	if(!func || !tree || !tree->head) return 0;
683 	sx_radix_node_foreach(tree->head,func,udata);
684 	return 0;
685 };
686 
687 int
sx_radix_node_aggregate(struct sx_radix_node * node)688 sx_radix_node_aggregate(struct sx_radix_node* node)
689 {
690 	if(node->l)
691 		sx_radix_node_aggregate(node->l);
692 	if(node->r)
693 		sx_radix_node_aggregate(node->r);
694 
695 	if(debug_aggregation) {
696 		printf("Aggregating on node: ");
697 		sx_prefix_fprint(stdout,&node->prefix);
698 		printf(" %s%s%u,%u\n", node->isGlue?"Glue ":"",
699 			node->isAggregate?"Aggregate ":"",node->aggregateLow,
700 			node->aggregateHi);
701 		if(node->r) {
702 			printf("R-Tree: ");
703 			sx_prefix_fprint(stdout,&node->r->prefix);
704 			printf(" %s%s%u,%u\n", (node->r->isGlue)?"Glue ":"",
705 				(node->r->isAggregate)?"Aggregate ":"",
706 				node->r->aggregateLow,node->r->aggregateHi);
707 			if(node->r->son) {
708 			printf("R-Son: ");
709 			sx_prefix_fprint(stdout,&node->r->son->prefix);
710 			printf(" %s%s%u,%u\n",node->r->son->isGlue?"Glue ":"",
711 				node->r->son->isAggregate?"Aggregate ":"",
712 				node->r->son->aggregateLow,node->r->son->aggregateHi);
713 			};
714 		};
715 		if(node->l) {
716 			printf("L-Tree: ");
717 			sx_prefix_fprint(stdout,&node->l->prefix);
718 			printf(" %s%s%u,%u\n",node->l->isGlue?"Glue ":"",
719 				node->l->isAggregate?"Aggregate ":"",
720 				node->l->aggregateLow,node->l->aggregateHi);
721 			if(node->l->son) {
722 			printf("L-Son: ");
723 			sx_prefix_fprint(stdout,&node->l->son->prefix);
724 			printf(" %s%s%u,%u\n",node->l->son->isGlue?"Glue ":"",
725 				node->l->son->isAggregate?"Aggregate ":"",
726 				node->l->son->aggregateLow,node->l->son->aggregateHi);
727 			};
728 		};
729 	};
730 
731 	if(node->r && node->l) {
732 		if(!node->r->isAggregate && !node->l->isAggregate &&
733 			!node->r->isGlue && !node->l->isGlue &&
734 			node->r->prefix.masklen==node->l->prefix.masklen) {
735 			if(node->r->prefix.masklen==node->prefix.masklen+1) {
736 				node->isAggregate=1;
737 				node->r->isGlue=1;
738 				node->l->isGlue=1;
739 				node->aggregateHi=node->r->prefix.masklen;
740 				if(node->isGlue) {
741 					node->isGlue=0;
742 					node->aggregateLow=node->r->prefix.masklen;
743 				} else {
744 					node->aggregateLow=node->prefix.masklen;
745 				};
746 			};
747 			if(node->r->son && node->l->son &&
748 				node->r->son->isAggregate && node->l->son->isAggregate &&
749 				node->r->son->aggregateHi==node->l->son->aggregateHi &&
750 				node->r->son->aggregateLow==node->l->son->aggregateLow &&
751 				node->r->prefix.masklen==node->prefix.masklen+1 &&
752 				node->l->prefix.masklen==node->prefix.masklen+1)
753 			{
754 				node->son=sx_radix_node_new(&node->prefix);
755 				node->son->isGlue=0;
756 				node->son->isAggregate=1;
757 				node->son->aggregateHi=node->r->son->aggregateHi;
758 				node->son->aggregateLow=node->r->son->aggregateLow;
759 				node->r->son->isGlue=1;
760 				node->l->son->isGlue=1;
761 			};
762 		} else if(node->r->isAggregate && node->l->isAggregate &&
763 			node->r->aggregateHi==node->l->aggregateHi &&
764 			node->r->aggregateLow==node->l->aggregateLow) {
765 			if(node->r->prefix.masklen==node->prefix.masklen+1 &&
766 				node->l->prefix.masklen==node->prefix.masklen+1) {
767 				if(node->isGlue) {
768 					node->r->isGlue=1;
769 					node->l->isGlue=1;
770 					node->isAggregate=1;
771 					node->isGlue=0;
772 					node->aggregateHi=node->r->aggregateHi;
773 					node->aggregateLow=node->r->aggregateLow;
774 				} else if(node->r->prefix.masklen==node->r->aggregateLow) {
775 					node->r->isGlue=1;
776 					node->l->isGlue=1;
777 					node->isAggregate=1;
778 					node->aggregateHi=node->r->aggregateHi;
779 					node->aggregateLow=node->prefix.masklen;
780 				} else {
781 					node->son=sx_radix_node_new(&node->prefix);
782 					node->son->isGlue=0;
783 					node->son->isAggregate=1;
784 					node->son->aggregateHi=node->r->aggregateHi;
785 					node->son->aggregateLow=node->r->aggregateLow;
786 					node->r->isGlue=1;
787 					node->l->isGlue=1;
788 					if(node->r->son && node->l->son &&
789 						node->r->son->aggregateHi==node->l->son->aggregateHi &&
790 						node->r->son->aggregateLow==node->l->son->aggregateLow)
791 					{
792 						node->son->son=sx_radix_node_new(&node->prefix);
793 						node->son->son->isGlue=0;
794 						node->son->son->isAggregate=1;
795 						node->son->son->aggregateHi=node->r->son->aggregateHi;
796 						node->son->son->aggregateLow=node->r->son->aggregateLow;
797 						node->r->son->isGlue=1;
798 						node->l->son->isGlue=1;
799 					};
800 				};
801 			};
802 		} else if(node->l->son &&
803 			node->r->isAggregate && node->l->son->isAggregate &&
804 			node->r->aggregateHi==node->l->son->aggregateHi &&
805 			node->r->aggregateLow==node->l->son->aggregateLow) {
806 			if(node->r->prefix.masklen==node->prefix.masklen+1 &&
807 				node->l->prefix.masklen==node->prefix.masklen+1) {
808 				if(node->isGlue) {
809 					node->r->isGlue=1;
810 					node->l->son->isGlue=1;
811 					node->isAggregate=1;
812 					node->isGlue=0;
813 					node->aggregateHi=node->r->aggregateHi;
814 					node->aggregateLow=node->r->aggregateLow;
815 				} else {
816 					node->son=sx_radix_node_new(&node->prefix);
817 					node->son->isGlue=0;
818 					node->son->isAggregate=1;
819 					node->son->aggregateHi=node->r->aggregateHi;
820 					node->son->aggregateLow=node->r->aggregateLow;
821 					node->r->isGlue=1;
822 					node->l->son->isGlue=1;
823 				};
824 			};
825 		} else if(node->r->son &&
826 			node->l->isAggregate && node->r->son->isAggregate &&
827 			node->l->aggregateHi==node->r->son->aggregateHi &&
828 			node->l->aggregateLow==node->r->son->aggregateLow) {
829 			if(node->l->prefix.masklen==node->prefix.masklen+1 &&
830 				node->r->prefix.masklen==node->prefix.masklen+1) {
831 				if(node->isGlue) {
832 					node->l->isGlue=1;
833 					node->r->son->isGlue=1;
834 					node->isAggregate=1;
835 					node->isGlue=0;
836 					node->aggregateHi=node->l->aggregateHi;
837 					node->aggregateLow=node->l->aggregateLow;
838 				} else {
839 					node->son=sx_radix_node_new(&node->prefix);
840 					node->son->isGlue=0;
841 					node->son->isAggregate=1;
842 					node->son->aggregateHi=node->l->aggregateHi;
843 					node->son->aggregateLow=node->l->aggregateLow;
844 					node->l->isGlue=1;
845 					node->r->son->isGlue=1;
846 				};
847 			};
848 		};
849 	};
850 	return 0;
851 };
852 
853 int
sx_radix_tree_aggregate(struct sx_radix_tree * tree)854 sx_radix_tree_aggregate(struct sx_radix_tree* tree)
855 {
856 	if(tree && tree->head) return sx_radix_node_aggregate(tree->head);
857 	return 0;
858 };
859 
860 static void
setGlueUpTo(struct sx_radix_node * node,void * udata)861 setGlueUpTo(struct sx_radix_node* node, void* udata)
862 {
863 	unsigned refine=*(unsigned*)udata;
864 	if(node && node->prefix.masklen <= refine) {
865 		node->isGlue=1;
866 	};
867 };
868 
869 static void
sx_radix_node_hyperaggregate(struct sx_radix_node * node,unsigned max)870 sx_radix_node_hyperaggregate(struct sx_radix_node* node, unsigned max)
871 {
872 	if(!node->isGlue) {
873 		node->isAggregate=0;
874 		if(node->l)
875 			sx_radix_node_foreach(node->l, setGlueUpTo, &max);
876 		if(node->r)
877 			sx_radix_node_foreach(node->r, setGlueUpTo, &max);
878 	} else {
879 		if(node->l)
880 			sx_radix_node_hyperaggregate(node->l, max);
881 		if(node->r)
882 			sx_radix_node_hyperaggregate(node->r, max);
883 	};
884 };
885 
886 int
sx_radix_tree_hyperaggregate(struct sx_radix_tree * tree)887 sx_radix_tree_hyperaggregate(struct sx_radix_tree* tree)
888 {
889 	if(tree && tree->head) {
890 		unsigned max = tree->family == AF_INET ? 32 : 128;
891 		sx_radix_node_hyperaggregate(tree->head, max);
892 	};
893 	return 0;
894 };
895 
896 int
sx_radix_node_refine(struct sx_radix_node * node,unsigned refine)897 sx_radix_node_refine(struct sx_radix_node* node, unsigned refine)
898 {
899 	if(!node->isGlue && node->prefix.masklen<refine) {
900 		node->isAggregate=1;
901 		node->aggregateLow=node->prefix.masklen;
902 		node->aggregateHi=refine;
903 		if(node->l) {
904 			sx_radix_node_foreach(node->l, setGlueUpTo, &refine);
905 			sx_radix_node_refine(node->l, refine);
906 		};
907 		if(node->r) {
908 			sx_radix_node_foreach(node->r, setGlueUpTo, &refine);
909 			sx_radix_node_refine(node->r, refine);
910 		};
911 	} else if(!node->isGlue && node->prefix.masklen==refine) {
912 		/* not setting aggregate in this case */
913 		if(node->l) sx_radix_node_refine(node->l, refine);
914 		if(node->r) sx_radix_node_refine(node->r, refine);
915 	} else if(node->isGlue) {
916 		if(node->r) sx_radix_node_refine(node->r, refine);
917 		if(node->l) sx_radix_node_refine(node->l, refine);
918 	} else {
919 		/* node->prefix.masklen > refine */
920 		/* do nothing, should pass specifics 'as is'. Also, do not
921 		process any embedded routes, their masklen is bigger, too...
922 		node->isGlue=1;
923 		if(node->l) sx_radix_node_foreach(node->l, setGlue, NULL);
924 		if(node->r) sx_radix_node_foreach(node->r, setGlue, NULL);
925 		*/
926 	};
927 	return 0;
928 };
929 
930 int
sx_radix_tree_refine(struct sx_radix_tree * tree,unsigned refine)931 sx_radix_tree_refine(struct sx_radix_tree* tree, unsigned refine)
932 {
933 	if(tree && tree->head) return sx_radix_node_refine(tree->head, refine);
934 	return 0;
935 };
936 
937 static void
setGlueFrom(struct sx_radix_node * node,void * udata)938 setGlueFrom(struct sx_radix_node* node, void* udata)
939 {
940 	unsigned refine=*(unsigned*)udata;
941 	if(node && node->prefix.masklen <= refine) {
942 		node->isGlue=1;
943 	};
944 };
945 
946 static int
sx_radix_node_refineLow(struct sx_radix_node * node,unsigned refineLow)947 sx_radix_node_refineLow(struct sx_radix_node* node, unsigned refineLow)
948 {
949 	if(!node->isGlue && node->prefix.masklen<=refineLow) {
950 		if(!node->isAggregate) {
951 			node->isAggregate=1;
952 			node->aggregateLow=refineLow;
953 			if(node->prefix.family == AF_INET) {
954 				node->aggregateHi=32;
955 			} else {
956 				node->aggregateHi=128;
957 			}
958 		} else {
959 			node->aggregateLow=refineLow;
960 		};
961 		if(node->l) {
962 			sx_radix_node_foreach(node->l, setGlueFrom, &refineLow);
963 			sx_radix_node_refineLow(node->l, refineLow);
964 		};
965 		if(node->r) {
966 			sx_radix_node_foreach(node->r, setGlueFrom, &refineLow);
967 			sx_radix_node_refineLow(node->r, refineLow);
968 		};
969 	} else if(!node->isGlue && node->prefix.masklen==refineLow) {
970 		/* not setting aggregate in this case */
971 		if(node->l) sx_radix_node_refineLow(node->l, refineLow);
972 		if(node->r) sx_radix_node_refineLow(node->r, refineLow);
973 	} else if(node->isGlue) {
974 		if(node->r) sx_radix_node_refineLow(node->r, refineLow);
975 		if(node->l) sx_radix_node_refineLow(node->l, refineLow);
976 	} else {
977 		/* node->prefix.masklen > refine */
978 		/* do nothing, should pass specifics 'as is'. Also, do not
979 		process any embedded routes, their masklen is bigger, too...
980 		node->isGlue=1;
981 		if(node->l) sx_radix_node_foreach(node->l, setGlue, NULL);
982 		if(node->r) sx_radix_node_foreach(node->r, setGlue, NULL);
983 		*/
984 	};
985 	return 0;
986 };
987 
988 
989 int
sx_radix_tree_refineLow(struct sx_radix_tree * tree,unsigned refineLow)990 sx_radix_tree_refineLow(struct sx_radix_tree* tree, unsigned refineLow)
991 {
992 	if(tree && tree->head)
993 		return sx_radix_node_refineLow(tree->head, refineLow);
994 	return 0;
995 };
996 
997 
998 #if SX_PTREE_TEST
999 int
main()1000 main() {
1001 	struct sx_prefix* p;
1002 	int n;
1003 	struct sx_radix_tree* tree;
1004 	struct sx_radix_node* node;
1005 
1006 	p=sx_prefix_new(0,"10.11.12.13/24");
1007 	sx_prefix_fprint(stdout,p);
1008 	printf("\n");
1009 	p=sx_prefix_new(0,"10.11.12.13/33");
1010 	sx_prefix_fprint(stdout,p);
1011 	printf("\n");
1012 	p=sx_prefix_new(0,"10.11.12.13/-133");
1013 	sx_prefix_fprint(stdout,p);
1014 	printf("\n");
1015 
1016 	p=sx_prefix_new(AF_INET,"10.11.12.14/24");
1017 	sx_prefix_fprint(stdout,p);
1018 	printf("\n");
1019 	p=sx_prefix_new(AF_INET,"10.11.12.14/33");
1020 	sx_prefix_fprint(stdout,p);
1021 	printf("\n");
1022 	p=sx_prefix_new(AF_INET,"10.11.12.14/-133");
1023 	sx_prefix_fprint(stdout,p);
1024 	printf("\n");
1025 
1026 	p=sx_prefix_new(AF_INET6,"10.11.12.15/24");
1027 	sx_prefix_fprint(stdout,p);
1028 	printf("\n");
1029 	p=sx_prefix_new(AF_INET6,"10.11.12.15/33");
1030 	sx_prefix_fprint(stdout,p);
1031 	printf("\n");
1032 	p=sx_prefix_new(AF_INET6,"10.11.12.15/-133");
1033 	sx_prefix_fprint(stdout,p);
1034 	printf("\n");
1035 
1036 	p=sx_prefix_new(0,"2001:1b00::/24");
1037 	sx_prefix_fprint(stdout,p);
1038 	printf("\n");
1039 	p=sx_prefix_new(0,"2001:1b00::/33");
1040 	sx_prefix_fprint(stdout,p);
1041 	printf("\n");
1042 	p=sx_prefix_new(0,"2001:1b00::/-133");
1043 	sx_prefix_fprint(stdout,p);
1044 	printf("\n");
1045 
1046 	p=sx_prefix_new(AF_INET6,"2001:1b01::/24");
1047 	sx_prefix_fprint(stdout,p);
1048 	printf("\n");
1049 	p=sx_prefix_new(AF_INET6,"2001:1b01::/33");
1050 	sx_prefix_fprint(stdout,p);
1051 	printf("\n");
1052 	p=sx_prefix_new(AF_INET6,"2001:1b01::/-133");
1053 	sx_prefix_fprint(stdout,p);
1054 	printf("\n");
1055 
1056 #define SX_TEST_EBITS(a,b,susp) n=sx_prefix_eqbits(sx_prefix_new(0,a)),\
1057 		sx_prefix_new(0,b))); \
1058 		if(n!=susp) printf("FAILED: %s eqbits %s=%i, not %i\n", a, b, n, susp);\
1059 		else printf("OK, %s eqbits %s=%i, as suspected\n", a, b, n);
1060 	SX_TEST_EBITS("192.168.0.0/24","192.168.1.0/24",23);
1061 	SX_TEST_EBITS("192.168.0.0/32","192.168.0.1/32",31);
1062 #if SX_LIBPTREE_IPV6
1063 	SX_TEST_EBITS("2001:1b00::/32","2001:1b01::/32",31);
1064 #endif
1065 
1066 	p=sx_prefix_new(0,"10.11.12.255/32");
1067 	sx_prefix_fprint(stdout,p);
1068 	printf("\n31'th bit is %i\n",sx_prefix_isbitset(p,31));
1069 	printf("32'th bit is %i\n",sx_prefix_isbitset(p,32));
1070 	printf("33'th bit is %i\n",sx_prefix_isbitset(p,33));
1071 	p=sx_prefix_new(0,"10.11.12.255/31");
1072 	sx_prefix_fprint(stdout,p);
1073 	printf("\n31'th bit is %i\n",sx_prefix_isbitset(p,31));
1074 	printf("32'th bit is %i\n",sx_prefix_isbitset(p,32));
1075 	printf("33'th bit is %i\n",sx_prefix_isbitset(p,33));
1076 	p=sx_prefix_new(0,"10.11.12.255/30");
1077 	sx_prefix_fprint(stdout,p);
1078 	printf("\n31'th bit is %i\n",sx_prefix_isbitset(p,31));
1079 	p=sx_prefix_new(0,"10.11.12.255/29");
1080 	sx_prefix_fprint(stdout,p);
1081 	printf("\n");
1082 	p=sx_prefix_new(0,"10.11.12.255/28");
1083 	sx_prefix_fprint(stdout,p);
1084 	printf("\n");
1085 	p=sx_prefix_new(0,"10.11.12.255/27");
1086 	sx_prefix_fprint(stdout,p);
1087 	printf("\n");
1088 	p=sx_prefix_new(0,"10.11.12.255/26");
1089 	sx_prefix_fprint(stdout,p);
1090 	printf("\n");
1091 	p=sx_prefix_new(0,"10.11.12.255/25");
1092 	sx_prefix_fprint(stdout,p);
1093 	printf("\n25'th bit is %i\n",sx_prefix_isbitset(p,25));
1094 	p=sx_prefix_new(0,"10.11.12.255/24");
1095 	sx_prefix_fprint(stdout,p);
1096 	printf("\n25'th bit is %i\n",sx_prefix_isbitset(p,25));
1097 
1098 	tree=sx_radix_tree_new(AF_INET);
1099 	sx_radix_tree_insert(tree,sx_prefix_new(0,"81.9.100.10/32"));
1100 	sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.83/32"));
1101 
1102 	sx_radix_tree_foreach(tree,sx_radix_node_fprintf,NULL);
1103 
1104 	tree=sx_radix_tree_new(AF_INET);
1105 	sx_radix_tree_insert(tree,sx_prefix_new(0,"81.9.100.10/32"));
1106 	sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.83/32"));
1107 	sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.84/32"));
1108 	sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.85/32"));
1109 	sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.86/32"));
1110 	sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.87/32"));
1111 	sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.90/32"));
1112 	sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.90/32"));
1113 	sx_radix_tree_insert(tree,sx_prefix_new(0,"127.0.0.1/32"));
1114 	sx_radix_tree_insert(tree,sx_prefix_new(0,"127.0.0.1/24"));
1115 	sx_radix_tree_insert(tree,sx_prefix_new(0,"127.0.0.0/24"));
1116 	sx_radix_tree_insert(tree,sx_prefix_new(0,"128.0.0.0/1"));
1117 
1118 	sx_radix_tree_foreach(tree,sx_radix_node_fprintf,NULL);
1119 
1120 	printf("lookup 1.1.1.1: ");
1121 	node=sx_radix_tree_lookup(tree,sx_prefix_new(0,"1.1.1.1"));
1122 	sx_radix_node_fprintf(node,NULL);
1123 
1124 	printf("lookup 217.170.80.90: ");
1125 	node=sx_radix_tree_lookup(tree,sx_prefix_new(0,"217.170.80.90"));
1126 	sx_radix_node_fprintf(node,NULL);
1127 
1128 	sx_radix_tree_unlink(tree,node);
1129 	printf("lookup 217.170.80.90 after delete: ");
1130 	node=sx_radix_tree_lookup(tree,sx_prefix_new(0,"217.170.80.90"));
1131 	sx_radix_node_fprintf(node,NULL);
1132 
1133 	sx_radix_tree_insert(tree,sx_prefix_new(0,"217.170.80.90/32"));
1134 	printf("lookup 217.170.80.90 after reinsert: ");
1135 	node=sx_radix_tree_lookup(tree,sx_prefix_new(0,"217.170.80.90"));
1136 	sx_radix_node_fprintf(node,NULL);
1137 
1138 	printf("lookup 217.170.80.81: ");
1139 	node=sx_radix_tree_lookup(tree,sx_prefix_new(0,"217.170.80.81"));
1140 	sx_radix_node_fprintf(node,NULL);
1141 
1142 	printf("lookup 127.0.0.1/24: ");
1143 	node=sx_radix_tree_lookup(tree,sx_prefix_new(0,"127.0.0.1/24"));
1144 	sx_radix_node_fprintf(node,NULL);
1145 
1146 	printf("lookup 127.0.0.1/26: ");
1147 	node=sx_radix_tree_lookup(tree,sx_prefix_new(0,"127.0.0.1/26"));
1148 	sx_radix_node_fprintf(node,NULL);
1149 
1150 	printf("lookup 127.0.0.1/23: ");
1151 	node=sx_radix_tree_lookup(tree,sx_prefix_new(0,"127.0.0.1/23"));
1152 	sx_radix_node_fprintf(node,NULL);
1153 
1154 	tree=sx_radix_tree_new(AF_INET6);
1155 	sx_radix_tree_insert(tree,sx_prefix_new(0,"2100:1b00::/32"));
1156 	sx_radix_tree_insert(tree,sx_prefix_new(0,"2100:1b01::/32"));
1157 	sx_radix_tree_insert(tree,sx_prefix_new(0,"2100:1b00::/33"));
1158 	sx_radix_tree_insert(tree,sx_prefix_new(0,"2100:1b00::1/128"));
1159 	sx_radix_tree_foreach(tree,sx_radix_node_fprintf,NULL);
1160 
1161 	return 0;
1162 };
1163 
1164 #endif
1165