/*
* Copyright (C) 2007, 2008, 2012, 2014 Internet Systems Consortium, Inc. ("ISC")
*
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
* REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
* AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
* INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
* LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
* OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
* PERFORMANCE OF THIS SOFTWARE.
*/
/* $Id$ */
/*
* This source was adapted from MRT's RCS Ids:
* Id: radix.h,v 1.6 1999/08/03 03:32:53 masaki Exp
* Id: mrt.h,v 1.57.2.6 1999/12/28 23:41:27 labovit Exp
* Id: defs.h,v 1.5.2.2 2000/01/15 14:19:16 masaki Exp
*/
#include <isc/refcount.h>
#include <string.h>
#ifndef _RADIX_H
#define _RADIX_H
do { \
} else \
} else { \
} \
} while(0)
typedef struct isc_prefix {
union {
} add;
} isc_prefix_t;
typedef void (*isc_radix_destroyfunc_t)(void *);
#define BIT_TEST(f, b) ((f) & (b))
/*
* We need "first match" when we search the radix tree to preserve
* compatibility with the existing ACL implementation. Radix trees
* naturally lend themselves to "best match". In order to get "first match"
* behavior, we keep track of the order in which entries are added to the
* tree--and when a search is made, we find all matching entries, and
* return the one that was added first.
*
* An IPv4 prefix and an IPv6 prefix may share a radix tree node if they
* have the same length and bit pattern (e.g., 127/8 and 7f::/8). To
* disambiguate between them, node_num and data are two-element arrays;
* node_num[0] and data[0] are used for IPv4 addresses, node_num[1]
* and data[1] for IPv6 addresses. The only exception is a prefix of
* 0/0 (aka "any" or "none"), which is always stored as IPv4 but matches
* IPv6 addresses too.
*/
typedef struct isc_radix_node {
struct isc_radix_node *l, *r; /* left and right children */
or -1 for glue nodes */
typedef struct isc_radix_tree {
unsigned int magic;
/*%<
* Search 'radix' for the best match to 'prefix'.
* Return the node found in '*target'.
*
* Requires:
* \li 'radix' to be valid.
* \li 'target' is not NULL and "*target" is NULL.
* \li 'prefix' to be valid.
*
* Returns:
* \li ISC_R_NOTFOUND
* \li ISC_R_SUCCESS
*/
/*%<
* Insert 'source' or 'prefix' into the radix tree 'radix'.
* Return the node added in 'target'.
*
* Requires:
* \li 'radix' to be valid.
* \li 'target' is not NULL and "*target" is NULL.
* \li 'prefix' to be valid or 'source' to be non NULL and contain
* a valid prefix.
*
* Returns:
* \li ISC_R_NOMEMORY
* \li ISC_R_SUCCESS
*/
void
/*%<
* Remove the node 'node' from the radix tree 'radix'.
*
* Requires:
* \li 'radix' to be valid.
* \li 'node' to be valid.
*/
/*%<
* Create a radix tree with a maximum depth of 'maxbits';
*
* Requires:
* \li 'mctx' to be valid.
* \li 'target' to be non NULL and '*target' to be NULL.
* \li 'maxbits' to be less than or equal to RADIX_MAXBITS.
*
* Returns:
* \li ISC_R_NOMEMORY
* \li ISC_R_SUCCESS
*/
void
/*%<
* Destroy a radix tree optionally calling 'func' to clean up node data.
*
* Requires:
* \li 'radix' to be valid.
*/
void
/*%<
* Walk a radix tree calling 'func' to process node data.
*
* Requires:
* \li 'radix' to be valid.
* \li 'func' to point to a function.
*/
do { \
do { \
if (1)
#define RADIX_WALK_BREAK { \
} else { \
Xrn = (radix_node_t *) 0; \
} \
continue; }
#define RADIX_WALK_END \
if (Xrn->l) { \
if (Xrn->r) { \
} \
} else if (Xrn->r) { \
} else { \
Xrn = (isc_radix_node_t *) 0; \
} \
} \
} while (0)
#endif /* _RADIX_H */