#include <isc/magic.h>
#include <isc/types.h>
#include <isc/mutex.h>
#include <isc/net.h>
#include <isc/refcount.h>
#include <string.h>
#ifndef _RADIX_H
#define _RADIX_H
#define NETADDR_TO_PREFIX_T(na,pt,bits) \
do { \
memset(&(pt), 0, sizeof(pt)); \
if((na) != NULL) { \
(pt).family = (na)->family; \
(pt).bitlen = (bits); \
if ((pt).family == AF_INET6) { \
memcpy(&(pt).add.sin6, &(na)->type.in6, \
((bits)+7)/8); \
} else \
memcpy(&(pt).add.sin, &(na)->type.in, \
((bits)+7)/8); \
} else { \
(pt).family = AF_UNSPEC; \
(pt).bitlen = 0; \
} \
isc_refcount_init(&(pt).refcount, 0); \
} while(0)
typedef struct isc_prefix {
unsigned int family;
unsigned int bitlen;
isc_refcount_t refcount;
union {
struct in_addr sin;
struct in6_addr sin6;
} add;
} isc_prefix_t;
typedef void (*isc_radix_destroyfunc_t)(void *);
typedef void (*isc_radix_processfunc_t)(isc_prefix_t *, void **);
#define isc_prefix_tochar(prefix) ((char *)&(prefix)->add.sin)
#define isc_prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin)
#define BIT_TEST(f, b) ((f) & (b))
#define ISC_IS6(family) ((family) == AF_INET6 ? 1 : 0)
typedef struct isc_radix_node {
isc_uint32_t bit;
isc_prefix_t *prefix;
struct isc_radix_node *l, *r;
struct isc_radix_node *parent;
void *data[2];
int node_num[2];
} isc_radix_node_t;
#define RADIX_TREE_MAGIC ISC_MAGIC('R','d','x','T');
#define RADIX_TREE_VALID(a) ISC_MAGIC_VALID(a, RADIX_TREE_MAGIC);
typedef struct isc_radix_tree {
unsigned int magic;
isc_mem_t *mctx;
isc_radix_node_t *head;
isc_uint32_t maxbits;
int num_active_node;
int num_added_node;
} isc_radix_tree_t;
isc_result_t
isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target, isc_prefix_t *prefix);
isc_result_t
isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target, isc_radix_node_t *source, isc_prefix_t *prefix);
void
isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node);
isc_result_t
isc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits);
void
isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func);
void
isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func);
#define RADIX_MAXBITS 128
#define RADIX_NBIT(x) (0x80 >> ((x) & 0x7f))
#define RADIX_NBYTE(x) ((x) >> 3)
#define RADIX_DATA_GET(node, type) (type *)((node)->data)
#define RADIX_DATA_SET(node, value) ((node)->data = (void *)(value))
#define RADIX_WALK(Xhead, Xnode) \
do { \
isc_radix_node_t *Xstack[RADIX_MAXBITS+1]; \
isc_radix_node_t **Xsp = Xstack; \
isc_radix_node_t *Xrn = (Xhead); \
while ((Xnode = Xrn)) { \
if (Xnode->prefix)
#define RADIX_WALK_ALL(Xhead, Xnode) \
do { \
isc_radix_node_t *Xstack[RADIX_MAXBITS+1]; \
isc_radix_node_t **Xsp = Xstack; \
isc_radix_node_t *Xrn = (Xhead); \
while ((Xnode = Xrn)) { \
if (1)
#define RADIX_WALK_BREAK { \
if (Xsp != Xstack) { \
Xrn = *(--Xsp); \
} else { \
Xrn = (radix_node_t *) 0; \
} \
continue; }
#define RADIX_WALK_END \
if (Xrn->l) { \
if (Xrn->r) { \
*Xsp++ = Xrn->r; \
} \
Xrn = Xrn->l; \
} else if (Xrn->r) { \
Xrn = Xrn->r; \
} else if (Xsp != Xstack) { \
Xrn = *(--Xsp); \
} else { \
Xrn = (isc_radix_node_t *) 0; \
} \
} \
} while (0)
#endif