File:
[ELWIX - Embedded LightWeight unIX -] /
libaitio /
src /
Attic /
patricia.c
Revision
1.4:
download - view:
text,
annotated -
select for diffs -
revision graph
Thu Mar 29 01:31:34 2012 UTC (12 years, 5 months ago) by
misho
Branches:
MAIN
CVS tags:
io3_1,
io2_8,
io2_7,
io2_6,
IO3_0,
IO2_7,
IO2_6,
IO2_5,
HEAD
version 2.5
/*************************************************************************
* (C) 2007 AITNET ltd - Sofia/Bulgaria - <misho@aitnet.org>
* by Michael Pounov <misho@elwix.org>
*
* $Author: misho $
* $Id: patricia.c,v 1.4 2012/03/29 01:31:34 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, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
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 = calloc(1, sizeof(prefix6_t));
dynamic_allocated++;
}
memcpy(&prefix->add.sin6, dest, 16);
} else
#endif /* HAVE_IPV6 */
if (family == AF_INET) {
if (!prefix) {
prefix = 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);
}
// ------------------------------------------------------------------------------------
inline char *prefix_toa(prefix_t * prefix)
{
return prefix_toa2x(prefix, NULL, 0);
}
inline 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 < 0 || 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;
}
inline 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;
}
inline 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 */
inline patricia_tree_t *New_Patricia(int maxbits)
{
patricia_tree_t *patricia;
patricia = 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
*/
inline 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); */
}
inline 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)
*/
inline 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;
}
inline 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 */
inline 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;
}
inline patricia_node_t *patricia_search_best(patricia_tree_t *patricia, prefix_t *prefix)
{
return patricia_search_best2(patricia, prefix, 1);
}
inline 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 = 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 = 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 = 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;
}
inline 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 */
inline 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);
}
inline 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;
}
inline 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;
}
inline 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;
}
/* } */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>