Return to patricia.c CVS log

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

version 3.7

/*************************************************************************
* (C) 2007 AITNET ltd - Sofia/Bulgaria - <misho@aitnet.org>
*  by Michael Pounov <misho@elwix.org>
*
* $Author: misho $
* $Id: patricia.c,v 1.5 2015/06/25 17:53:50 misho Exp $
*
**************************************************************************
The ELWIX and AITNET software is distributed under the following
terms:

All of the documentation and software included in the ELWIX and AITNET
Releases is copyrighted by ELWIX - Sofia/Bulgaria <info@elwix.org>

Copyright 2004 - 2015
	by Michael Pounov <misho@elwix.org>.  All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.
3. All advertising materials mentioning features or use of this software
   must display the following acknowledgement:
This product includes software developed by Michael Pounov <misho@elwix.org>
ELWIX - Embedded LightWeight unIX and its contributors.
4. Neither the name of AITNET nor the names of its contributors
   may be used to endorse or promote products derived from this software
   without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY AITNET AND CONTRIBUTORS ``AS IS'' AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.
*/
/*
 * This product includes software developed by the University of Michigan,
 * Merit Network, Inc., and their contributors. 
 *
 * This file had been called "radix.c" in the MRT sources.
 *
 * I renamed it to "patricia.c" since it's not an implementation of a general
 * radix trie.  Also I pulled in various requirements from "prefix.c" and
 * "demo.c" so that it could be used as a standalone API.
 *
 * Added and patched existing code by AITNET - Michael Pounov <misho@aitbg.com>
 */
#include "global.h"


static int num_active_patricia;


/* { from prefix.c */
static inline int comp_with_mask(void *addr, void *dest, u_int mask)
{
	int n, m;

	if (/* mask/8 == 0 || */ !memcmp(addr, dest, mask / 8)) {
		n = mask / 8;
		m = ((-1) << (8 - (mask % 8)));

		if (!(mask % 8) || (((u_char*) addr)[n] & m) == (((u_char*) dest)[n] & m))
			return 1;
	}

	return 0;
}

/* this allows imcomplete prefix */
static int my_inet_pton(int af, const char *src, void *dst)
{
	int i, c, val;
	u_char xp[4] = { 0, 0, 0, 0 };

	if (af == AF_INET) {
		for (i = 0;; i++) {
			c = *src++;
			if (!isdigit(c))
				return -1;
			val = 0;
			do {
				val = val * 10 + c - '0';
				if (val > 255)
					return 0;
				c = *src++;
			} while (c && isdigit(c));

			xp[i] = val;
			if (!c)
				break;
			if (c != '.' || i >= 3)
				return 0;
		}

		memcpy(dst, xp, 4);
		return 1;
#ifdef HAVE_IPV6
	} else
		if (af == AF_INET6) {
			return inet_pton(af, src, dst);
#endif /* HAVE_IPV6 */
		} else {
			errno = EAFNOSUPPORT;
			return -1;
		}
}

/* 
 * convert prefix information to ascii string with length
 * thread safe and (almost) re-entrant implementation
 */
static char *prefix_toa2x(prefix_t *prefix, char *buff, int with_len)
{
	struct buffer {
		char buffs[16][48 + 5];
		u_int i;
	} *buffp;
	u_char *a;

	if (!prefix)
		return "(Null)";
	assert(prefix->ref_count >= 0);
	if (!buff) {
#if 0
		THREAD_SPECIFIC_DATA(struct buffer, buffp, 1);
#else
		{ /* for scope only */
			static struct buffer local_buff;
			buffp = &local_buff;
		}
#endif
		if (!buffp) {
			/* XXX should we report an error? */
			return NULL;
		}

		buff = buffp->buffs[buffp->i++ % 16];
	}
	if (prefix->family == AF_INET) {
		assert (prefix->bitlen <= 32);
		a = prefix_touchar(prefix);
		if (with_len)
			snprintf(buff, with_len, "%d.%d.%d.%d/%d", a[0], a[1], a[2], 
					a[3], prefix->bitlen);
		else
			snprintf(buff, 16, "%d.%d.%d.%d", a[0], a[1], a[2], a[3]);
		return buff;
	}
#ifdef HAVE_IPV6
	else
		if (prefix->family == AF_INET6) {
			a = (char*) inet_ntop(AF_INET6, &prefix->add.sin6, buff, 48 /* a guess value */);
			if (a && with_len) {
				assert(prefix->bitlen <= 128);
				snprintf(buff + strlen(buff), with_len - strlen(buff), 
						"/%d", prefix->bitlen);
			}
			return buff;
		}
#endif /* HAVE_IPV6 */
		else
			return NULL;
}

static prefix_t *New_Prefix2(int family, void *dest, int bitlen, prefix_t *prefix)
{
	int dynamic_allocated = 0;
	int default_bitlen = 32;

#ifdef HAVE_IPV6
	if (family == AF_INET6) {
		default_bitlen = 128;
		if (!prefix) {
			prefix = e_calloc(1, sizeof(prefix6_t));
			dynamic_allocated++;
		}
		memcpy(&prefix->add.sin6, dest, 16);
	} else
#endif /* HAVE_IPV6 */
		if (family == AF_INET) {
			if (!prefix) {
				prefix = e_calloc(1, sizeof(prefix4_t));
				dynamic_allocated++;
			}
			memcpy(&prefix->add.sin, dest, 4);
		} else
			return NULL;

	prefix->bitlen = (bitlen >= 0) ? bitlen : default_bitlen;
	prefix->family = family;
	prefix->ref_count = 0;
	if (dynamic_allocated)
		prefix->ref_count++;

	return prefix;
}

static inline prefix_t *New_Prefix(int family, void *dest, int bitlen)
{
    return New_Prefix2(family, dest, bitlen, NULL);
}

// ------------------------------------------------------------------------------------

char *prefix_toa(prefix_t * prefix)
{
    return prefix_toa2x(prefix, NULL, 0);
}

prefix_t *ascii2prefix(int family, char *string)
{
	u_long bitlen, maxbitlen = 0;
	char *cp;
	struct in_addr sin;
#ifdef HAVE_IPV6
	struct in6_addr sin6;
#endif /* HAVE_IPV6 */
	int result;
	char save[MAXLINE];

	if (!string)
		return (NULL);

	/* easy way to handle both families */
	if (!family) {
		family = AF_INET;
#ifdef HAVE_IPV6
		if (strchr(string, ':'))
			family = AF_INET6;
#endif /* HAVE_IPV6 */
	}

	if (family == AF_INET)
		maxbitlen = 32;
#ifdef HAVE_IPV6
	else
		if (family == AF_INET6)
			maxbitlen = 128;
#endif /* HAVE_IPV6 */

	if ((cp = strchr(string, '/'))) {
		bitlen = atol(cp + 1);
		/* *cp = '\0'; */
		/* copy the string to save. Avoid destroying the string */
		assert(cp - string < MAXLINE);
		memcpy(save, string, cp - string);
		save[cp - string] = 0;
		string = save;
		if (bitlen > maxbitlen)
			bitlen = maxbitlen;
	} else
		bitlen = maxbitlen;

	if (family == AF_INET) {
		if ((result = my_inet_pton(AF_INET, string, &sin)) <= 0)
			return NULL;
		return New_Prefix(AF_INET, &sin, bitlen);
	}
#ifdef HAVE_IPV6
	else
		if (family == AF_INET6) {
			if ((result = inet_pton(AF_INET6, string, &sin6)) <= 0)
				return NULL;
			return New_Prefix(AF_INET6, &sin6, bitlen);
		}
#endif /* HAVE_IPV6 */
		else
			return NULL;
}

prefix_t *Ref_Prefix(prefix_t *prefix)
{
	if (!prefix)
		return NULL;

	if (!prefix->ref_count) {
		/* make a copy in case of a static prefix */
		return New_Prefix2(prefix->family, &prefix->add, prefix->bitlen, NULL);
	}
	prefix->ref_count++;

	return prefix;
}

void Deref_Prefix(prefix_t *prefix)
{
	if (!prefix)
		return;

	/* for secure programming, raise an assert. no static prefix can call this */
	assert(prefix->ref_count > 0);
	prefix->ref_count--;
	assert(prefix->ref_count >= 0);
	if (prefix->ref_count <= 0)
		Delete(prefix);
}

/* } */

/* these routines support continuous mask only */
patricia_tree_t *New_Patricia(int maxbits)
{
	patricia_tree_t *patricia;

	patricia = e_calloc(1, sizeof *patricia);

	patricia->maxbits = maxbits;
	patricia->head = NULL;
	patricia->num_active_node = 0;

	assert(maxbits <= PATRICIA_MAXBITS); /* XXX */
	num_active_patricia++;

	return patricia;
}


/*
 * if func is supplied, it will be called as func(node->data)
 * before deleting the node
 */
void Clear_Patricia(patricia_tree_t *patricia, void_fn_t func)
{
	assert(patricia);
	if (patricia->head) {
		patricia_node_t *Xstack[PATRICIA_MAXBITS+1];
		patricia_node_t **Xsp = Xstack;
		patricia_node_t *Xrn = patricia->head;

		while (Xrn) {
			patricia_node_t *l = Xrn->l;
			patricia_node_t *r = Xrn->r;

			if (Xrn->prefix) {
				Deref_Prefix(Xrn->prefix);
				if (Xrn->data && func)
					func(Xrn->data);
			} else
				assert(!Xrn->data);
			Delete(Xrn);
			patricia->num_active_node--;

			if (l) {
				if (r)
					*Xsp++ = r;
				Xrn = l;
			} else {
				if (r)
					Xrn = r;
				else
					Xrn = (Xsp != Xstack) ? *(--Xsp) : NULL;
			}
		}
	}

	assert (!patricia->num_active_node);
	/* Delete(patricia); */
}

void Destroy_Patricia(patricia_tree_t *patricia, void_fn_t func)
{
	Clear_Patricia(patricia, func);
	Delete(patricia);
	num_active_patricia--;
}


/*
 * if func is supplied, it will be called as func(node->prefix, node->data)
 */
void patricia_process(patricia_tree_t *patricia, void_fn_t func)
{
	patricia_node_t *node;

	assert(func);

	PATRICIA_WALK(patricia->head, node) {
		func(node->prefix, node->data);
	} PATRICIA_WALK_END;
}


patricia_node_t *patricia_search_exact(patricia_tree_t *patricia, prefix_t *prefix)
{
	patricia_node_t *node;
	u_char *addr;
	u_int bitlen;

	assert(patricia);
	assert(prefix);
	assert(prefix->bitlen <= patricia->maxbits);

	if (!patricia->head)
		return (NULL);

	node = patricia->head;
	addr = prefix_touchar(prefix);
	bitlen = prefix->bitlen;

	while (node->bit < bitlen) {
		if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
#ifdef PATRICIA_DEBUG
			if (node->prefix)
				fprintf(stderr, "patricia_search_exact: take right %s/%d\n", 
						prefix_toa(node->prefix), node->prefix->bitlen);
			else
				fprintf(stderr, "patricia_search_exact: take right at %d\n", 
						node->bit);
#endif /* PATRICIA_DEBUG */
			node = node->r;
		} else {
#ifdef PATRICIA_DEBUG
			if (node->prefix)
				fprintf(stderr, "patricia_search_exact: take left %s/%d\n", 
						prefix_toa(node->prefix), node->prefix->bitlen);
			else
				fprintf(stderr, "patricia_search_exact: take left at %d\n", 
						node->bit);
#endif /* PATRICIA_DEBUG */
			node = node->l;
		}

		if (!node)
			return NULL;
	}

#ifdef PATRICIA_DEBUG
	if (node->prefix)
		fprintf(stderr, "patricia_search_exact: stop at %s/%d\n", 
				prefix_toa(node->prefix), node->prefix->bitlen);
	else
		fprintf(stderr, "patricia_search_exact: stop at %d\n", node->bit);
#endif /* PATRICIA_DEBUG */
	if (node->bit > bitlen || !node->prefix)
		return NULL;
	assert(node->bit == bitlen);
	assert(node->bit == node->prefix->bitlen);
	if (comp_with_mask(prefix_touchar(node->prefix), prefix_touchar(prefix), bitlen)) {
#ifdef PATRICIA_DEBUG
		fprintf(stderr, "patricia_search_exact: found %s/%d\n", 
				prefix_toa(node->prefix), node->prefix->bitlen);
#endif /* PATRICIA_DEBUG */
		return node;
	}

	return NULL;
}


/* if inclusive != 0, "best" may be the given prefix itself */
patricia_node_t *patricia_search_best2(patricia_tree_t *patricia, prefix_t *prefix, int inclusive)
{
	patricia_node_t *node;
	patricia_node_t *stack[PATRICIA_MAXBITS + 1];
	u_char *addr;
	u_int bitlen;
	int cnt = 0;

	assert(patricia);
	assert(prefix);
	assert(prefix->bitlen <= patricia->maxbits);

	if (!patricia->head)
		return NULL;

	node = patricia->head;
	addr = prefix_touchar(prefix);
	bitlen = prefix->bitlen;

	while (node->bit < bitlen) {
		if (node->prefix) {
#ifdef PATRICIA_DEBUG
			fprintf(stderr, "patricia_search_best: push %s/%d\n", 
					prefix_toa(node->prefix), node->prefix->bitlen);
#endif /* PATRICIA_DEBUG */
			stack[cnt++] = node;
		}

		if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
#ifdef PATRICIA_DEBUG
			if (node->prefix)
				fprintf(stderr, "patricia_search_best: take right %s/%d\n", 
						prefix_toa(node->prefix), node->prefix->bitlen);
			else
				fprintf(stderr, "patricia_search_best: take right at %d\n", 
						node->bit);
#endif /* PATRICIA_DEBUG */
			node = node->r;
		} else {
#ifdef PATRICIA_DEBUG
			if (node->prefix)
				fprintf(stderr, "patricia_search_best: take left %s/%d\n", 
						prefix_toa(node->prefix), node->prefix->bitlen);
			else
				fprintf(stderr, "patricia_search_best: take left at %d\n", 
						node->bit);
#endif /* PATRICIA_DEBUG */
			node = node->l;
		}

		if (!node)
			break;
	}

	if (inclusive && node && node->prefix)
		stack[cnt++] = node;

#ifdef PATRICIA_DEBUG
	if (!node)
		fprintf(stderr, "patricia_search_best: stop at null\n");
	else
		if (node->prefix)
			fprintf(stderr, "patricia_search_best: stop at %s/%d\n", 
					prefix_toa(node->prefix), node->prefix->bitlen);
		else
			fprintf(stderr, "patricia_search_best: stop at %d\n", node->bit);
#endif /* PATRICIA_DEBUG */

	if (cnt <= 0)
		return NULL;

	while (--cnt >= 0) {
		node = stack[cnt];
#ifdef PATRICIA_DEBUG
		fprintf(stderr, "patricia_search_best: pop %s/%d\n", 
				prefix_toa(node->prefix), node->prefix->bitlen);
#endif /* PATRICIA_DEBUG */
		if (comp_with_mask(prefix_touchar(node->prefix), prefix_touchar(prefix), 
					node->prefix->bitlen)) {
#ifdef PATRICIA_DEBUG
			fprintf(stderr, "patricia_search_best: found %s/%d\n", 
					prefix_toa(node->prefix), node->prefix->bitlen);
#endif /* PATRICIA_DEBUG */
			return node;
		}
	}

	return NULL;
}

patricia_node_t *patricia_search_best(patricia_tree_t *patricia, prefix_t *prefix)
{
    return patricia_search_best2(patricia, prefix, 1);
}


patricia_node_t *patricia_lookup(patricia_tree_t *patricia, prefix_t *prefix)
{
	patricia_node_t *node, *new_node, *parent, *glue;
	u_char *addr, *test_addr;
	u_int bitlen, check_bit, differ_bit;
	int i, j, r;

	assert(patricia);
	assert(prefix);
	assert(prefix->bitlen <= patricia->maxbits);

	if (!patricia->head) {
		node = e_calloc(1, sizeof *node);
		node->bit = prefix->bitlen;
		node->prefix = Ref_Prefix(prefix);
		node->parent = NULL;
		node->l = node->r = NULL;
		node->data = NULL;
		patricia->head = node;
#ifdef PATRICIA_DEBUG
		fprintf(stderr, "patricia_lookup: new_node #0 %s/%d (head)\n", 
				prefix_toa(prefix), prefix->bitlen);
#endif /* PATRICIA_DEBUG */
		patricia->num_active_node++;
		return node;
	}

	addr = prefix_touchar(prefix);
	bitlen = prefix->bitlen;
	node = patricia->head;

	while (node->bit < bitlen || !node->prefix) {
		if (node->bit < patricia->maxbits &&
				BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
			if (!node->r)
				break;
#ifdef PATRICIA_DEBUG
			if (node->prefix)
				fprintf(stderr, "patricia_lookup: take right %s/%d\n", 
						prefix_toa(node->prefix), node->prefix->bitlen);
			else
				fprintf(stderr, "patricia_lookup: take right at %d\n", node->bit);
#endif /* PATRICIA_DEBUG */
			node = node->r;
		} else {
			if (!node->l)
				break;
#ifdef PATRICIA_DEBUG
			if (node->prefix)
				fprintf(stderr, "patricia_lookup: take left %s/%d\n", 
						prefix_toa(node->prefix), node->prefix->bitlen);
			else
				fprintf(stderr, "patricia_lookup: take left at %d\n", node->bit);
#endif /* PATRICIA_DEBUG */
			node = node->l;
		}

		assert(node);
	}

	assert(node->prefix);
#ifdef PATRICIA_DEBUG
	fprintf(stderr, "patricia_lookup: stop at %s/%d\n", 
			prefix_toa(node->prefix), node->prefix->bitlen);
#endif /* PATRICIA_DEBUG */

	test_addr = prefix_touchar(node->prefix);
	/* find the first bit different */
	check_bit = (node->bit < bitlen) ? node->bit : bitlen;
	differ_bit = 0;
	for (i = 0; i * 8 < check_bit; i++) {
		if (!(r = (addr[i] ^ test_addr[i]))) {
			differ_bit = (i + 1) * 8;
			continue;
		}
		/* I know the better way, but for now */
		for (j = 0; j < 8; j++) {
			if (BIT_TEST(r, (0x80 >> j)))
				break;
		}
		/* must be found */
		assert(j < 8);
		differ_bit = i * 8 + j;
		break;
	}

	if (differ_bit > check_bit)
		differ_bit = check_bit;
#ifdef PATRICIA_DEBUG
	fprintf(stderr, "patricia_lookup: differ_bit %d\n", differ_bit);
#endif /* PATRICIA_DEBUG */

	parent = node->parent;
	while (parent && parent->bit >= differ_bit) {
		node = parent;
		parent = node->parent;
#ifdef PATRICIA_DEBUG
		if (node->prefix)
			fprintf(stderr, "patricia_lookup: up to %s/%d\n", 
					prefix_toa(node->prefix), node->prefix->bitlen);
		else
			fprintf(stderr, "patricia_lookup: up to %d\n", node->bit);
#endif /* PATRICIA_DEBUG */
	}

	if (differ_bit == bitlen && node->bit == bitlen) {
		if (node->prefix) {
#ifdef PATRICIA_DEBUG 
			fprintf(stderr, "patricia_lookup: found %s/%d\n", 
					prefix_toa(node->prefix), node->prefix->bitlen);
#endif /* PATRICIA_DEBUG */
			return node;
		}
		node->prefix = Ref_Prefix(prefix);
#ifdef PATRICIA_DEBUG
		fprintf(stderr, "patricia_lookup: new node #1 %s/%d (glue mod)\n",
				prefix_toa(prefix), prefix->bitlen);
#endif /* PATRICIA_DEBUG */
		assert(!node->data);
		return node;
	}

	new_node = e_calloc(1, sizeof *new_node);
	new_node->bit = prefix->bitlen;
	new_node->prefix = Ref_Prefix (prefix);
	new_node->parent = NULL;
	new_node->l = new_node->r = NULL;
	new_node->data = NULL;
	patricia->num_active_node++;

	if (node->bit == differ_bit) {
		new_node->parent = node;
		if (node->bit < patricia->maxbits &&
				BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
			assert(!node->r);
			node->r = new_node;
		} else {
			assert(!node->l);
			node->l = new_node;
		}
#ifdef PATRICIA_DEBUG
		fprintf(stderr, "patricia_lookup: new_node #2 %s/%d (child)\n", 
				prefix_toa(prefix), prefix->bitlen);
#endif /* PATRICIA_DEBUG */
		return new_node;
	}

	if (bitlen == differ_bit) {
		if (bitlen < patricia->maxbits &&
				BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07)))
			new_node->r = node;
		else
			new_node->l = node;
		new_node->parent = node->parent;
		if (!node->parent) {
			assert(patricia->head == node);
			patricia->head = new_node;
		} else
			if (node->parent->r == node)
				node->parent->r = new_node;
			else
				node->parent->l = new_node;
		node->parent = new_node;
#ifdef PATRICIA_DEBUG
		fprintf(stderr, "patricia_lookup: new_node #3 %s/%d (parent)\n", 
				prefix_toa(prefix), prefix->bitlen);
#endif /* PATRICIA_DEBUG */
	} else {
		glue = e_calloc(1, sizeof *glue);
		glue->bit = differ_bit;
		glue->prefix = NULL;
		glue->parent = node->parent;
		glue->data = NULL;
		patricia->num_active_node++;

		if (differ_bit < patricia->maxbits &&
				BIT_TEST(addr[differ_bit >> 3], 0x80 >> (differ_bit & 0x07))) {
			glue->r = new_node;
			glue->l = node;
		} else {
			glue->r = node;
			glue->l = new_node;
		}
		new_node->parent = glue;

		if (!node->parent) {
			assert(patricia->head == node);
			patricia->head = glue;
		} else
			if (node->parent->r == node)
				node->parent->r = glue;
			else
				node->parent->l = glue;
		node->parent = glue;
#ifdef PATRICIA_DEBUG
		fprintf(stderr, "patricia_lookup: new_node #4 %s/%d (glue+node)\n", 
				prefix_toa(prefix), prefix->bitlen);
#endif /* PATRICIA_DEBUG */
	}

	return new_node;
}


void patricia_remove(patricia_tree_t *patricia, patricia_node_t *node)
{
	patricia_node_t *parent, *child;

	assert(patricia);
	assert(node);

	if (node->r && node->l) {
#ifdef PATRICIA_DEBUG
		fprintf(stderr, "patricia_remove: #0 %s/%d (r & l)\n", 
				prefix_toa(node->prefix), node->prefix->bitlen);
#endif /* PATRICIA_DEBUG */
	
		/* this might be a placeholder node -- have to check and make sure
		 * there is a prefix aossciated with it ! */
		if (node->prefix) 
			Deref_Prefix(node->prefix);
		node->prefix = NULL;
		/* Also I needed to clear data pointer -- masaki */
		node->data = NULL;
		return;
	}

	if (!node->r && !node->l) {
#ifdef PATRICIA_DEBUG
		fprintf(stderr, "patricia_remove: #1 %s/%d (!r & !l)\n", 
				prefix_toa(node->prefix), node->prefix->bitlen);
#endif /* PATRICIA_DEBUG */
		parent = node->parent;
		Deref_Prefix(node->prefix);
		Delete(node);
		patricia->num_active_node--;

		if (!parent) {
			assert(patricia->head == node);
			patricia->head = NULL;
			return;
		}

		if (parent->r == node) {
			parent->r = NULL;
			child = parent->l;
		} else {
			assert(parent->l == node);
			parent->l = NULL;
			child = parent->r;
		}

		if (parent->prefix)
			return;

		/* we need to remove parent too */
		if (!parent->parent) {
			assert(patricia->head == parent);
			patricia->head = child;
		} else
			if (parent->parent->r == parent)
				parent->parent->r = child;
			else {
				assert(parent->parent->l == parent);
				parent->parent->l = child;
			}
		child->parent = parent->parent;
		Delete(parent);
		patricia->num_active_node--;
		return;
	}

#ifdef PATRICIA_DEBUG
	fprintf(stderr, "patricia_remove: #2 %s/%d (r ^ l)\n", 
			prefix_toa(node->prefix), node->prefix->bitlen);
#endif /* PATRICIA_DEBUG */
	if (node->r)
		child = node->r;
	else {
		assert(node->l);
		child = node->l;
	}
	parent = node->parent;
	child->parent = parent;

	Deref_Prefix(node->prefix);
	Delete(node);
	patricia->num_active_node--;

	if (!parent) {
		assert(patricia->head == node);
		patricia->head = child;
		return;
	}

	if (parent->r == node)
		parent->r = child;
	else {
		assert(parent->l == node);
		parent->l = child;
	}
}

/* { from demo.c */

void lookup_then_remove(patricia_tree_t *tree, char *string)
{
	patricia_node_t *node;

	if ((node = try_search_exact(tree, string)))
		patricia_remove(tree, node);
}

patricia_node_t *make_and_lookup(patricia_tree_t *tree, char *string)
{
	prefix_t *prefix;
	patricia_node_t *node;

	prefix = ascii2prefix(AF_INET, string);
#ifdef PATRICIA_DEBUG
	printf("make_and_lookup: %s/%d\n", prefix_toa(prefix), prefix->bitlen);
#endif
	node = patricia_lookup(tree, prefix);
	Deref_Prefix(prefix);

	return node;
}

patricia_node_t *try_search_exact(patricia_tree_t *tree, char *string)
{
	prefix_t *prefix;
	patricia_node_t *node;

	prefix = ascii2prefix(AF_INET, string);
#ifdef PATRICIA_DEBUG
	printf("try_search_exact: %s/%d\n", prefix_toa(prefix), prefix->bitlen);
#endif
	node = patricia_search_exact(tree, prefix);
#ifdef PATRICIA_DEBUG
	if (!node)
		printf("try_search_exact: not found\n");
	else
		printf("try_search_exact: %s/%d found\n", prefix_toa(node->prefix), node->prefix->bitlen);
#endif
	Deref_Prefix(prefix);

	return node;
}

patricia_node_t *try_search_best(patricia_tree_t *tree, char *string)
{
	prefix_t *prefix;
	patricia_node_t *node;

	prefix = ascii2prefix(AF_INET, string);
#ifdef PATRICIA_DEBUG
	printf("try_search_best: %s/%d\n", prefix_toa(prefix), prefix->bitlen);
#endif
	node = patricia_search_best(tree, prefix);
#ifdef PATRICIA_DEBUG
	if (!node)
		printf("try_search_best: not found\n");
	else
		printf("try_search_best: %s/%d found\n", prefix_toa(node->prefix), node->prefix->bitlen);
#endif
	Deref_Prefix(prefix);

	return node;
}

/* } */