Return to patricia.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / libelwix / src

version 3.7

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