lib » isc » include » isc

radix.h File Reference

#include <isc/magic.h>
#include <isc/types.h>
#include <isc/mutex.h>
#include <isc/net.h>
#include <isc/refcount.h>
#include <string.h>

Go to the source code of this file.

Data Structures

struct  isc_prefix
struct  isc_radix_node
struct  isc_radix_tree

Defines

#define NETADDR_TO_PREFIX_T(na, pt, bits, is_ecs)
#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_RADIX_OFF(p)   ((((p)->family == AF_INET6) ? 1 : 0) + ((p)->ecs ? 2 : 0))
#define RADIX_TREE_MAGIC   ISC_MAGIC('R','d','x','T');
#define RADIX_TREE_VALID(a)   ISC_MAGIC_VALID(a, RADIX_TREE_MAGIC);
#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)
#define RADIX_WALK_ALL(Xhead, Xnode)
#define RADIX_WALK_BREAK
#define RADIX_WALK_END

Typedefs

typedef struct isc_prefix isc_prefix_t
typedef void(* isc_radix_destroyfunc_t )(void *)
typedef void(* isc_radix_processfunc_t )(isc_prefix_t *, void **)
typedef struct isc_radix_node isc_radix_node_t
typedef struct isc_radix_tree isc_radix_tree_t

Functions

isc_result_t isc_radix_search (isc_radix_tree_t *radix, isc_radix_node_t **target, isc_prefix_t *prefix)
 Search 'radix' for the best match to 'prefix'. Return the node found in '*target'.
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)
 Insert 'source' or 'prefix' into the radix tree 'radix'. Return the node added in 'target'.
void isc_radix_remove (isc_radix_tree_t *radix, isc_radix_node_t *node)
 Remove the node 'node' from the radix tree 'radix'.
isc_result_t isc_radix_create (isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits)
 Create a radix tree with a maximum depth of 'maxbits';.
void isc_radix_destroy (isc_radix_tree_t *radix, isc_radix_destroyfunc_t func)
 Destroy a radix tree optionally calling 'func' to clean up node data.
void isc_radix_process (isc_radix_tree_t *radix, isc_radix_processfunc_t func)
 Walk a radix tree calling 'func' to process node data.

Define Documentation

#define NETADDR_TO_PREFIX_T ( na,
pt,
bits,
is_ecs   ) 

Value:

do { \
                const void *p = na; \
                memset(&(pt), 0, sizeof(pt)); \
                if (p != NULL) { \
                        (pt).family = (na)->family; \
                        (pt).bitlen = (bits); \
                        if ((pt).family == AF_INET6) { \
                                memmove(&(pt).add.sin6, &(na)->type.in6, \
                                       ((bits)+7)/8); \
                        } else \
                                memmove(&(pt).add.sin, &(na)->type.in, \
                                       ((bits)+7)/8); \
                } else { \
                        (pt).family = AF_UNSPEC; \
                        (pt).bitlen = 0; \
                } \
                (pt).ecs = is_ecs; \
                isc_refcount_init(&(pt).refcount, 0); \
        } while(0)

Definition at line 35 of file radix.h.

Referenced by ATF_TC_BODY(), dns_acl_match2(), and dns_iptable_addprefix2().

#define isc_prefix_tochar ( prefix   )     ((char *)&(prefix)->add.sin)

Definition at line 71 of file radix.h.

Referenced by isc_radix_search().

#define isc_prefix_touchar ( prefix   )     ((u_char *)&(prefix)->add.sin)

Definition at line 72 of file radix.h.

Referenced by isc_radix_insert(), and isc_radix_search().

#define BIT_TEST ( f,
b   )     ((f) & (b))

Definition at line 74 of file radix.h.

Referenced by isc_radix_insert(), and isc_radix_search().

#define ISC_RADIX_OFF ( p   )     ((((p)->family == AF_INET6) ? 1 : 0) + ((p)->ecs ? 2 : 0))

Definition at line 100 of file radix.h.

Referenced by dns_acl_match2(), dns_iptable_addprefix2(), is_insecure(), isc_radix_insert(), and isc_radix_search().

#define RADIX_TREE_MAGIC   ISC_MAGIC('R','d','x','T');

Definition at line 114 of file radix.h.

Referenced by isc_radix_create().

#define RADIX_TREE_VALID ( a   )     ISC_MAGIC_VALID(a, RADIX_TREE_MAGIC);

Definition at line 115 of file radix.h.

#define RADIX_MAXBITS   128

Definition at line 205 of file radix.h.

Referenced by _clear_radix(), dns_iptable_create(), isc_radix_create(), and isc_radix_search().

#define RADIX_NBIT ( x   )     (0x80 >> ((x) & 0x7f))

Definition at line 206 of file radix.h.

#define RADIX_NBYTE ( x   )     ((x) >> 3)

Definition at line 207 of file radix.h.

#define RADIX_DATA_GET ( node,
type   )     (type *)((node)->data)

Definition at line 209 of file radix.h.

#define RADIX_DATA_SET ( node,
value   )     ((node)->data = (void *)(value))

Definition at line 210 of file radix.h.

#define RADIX_WALK ( Xhead,
Xnode   ) 

Value:

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)

Definition at line 212 of file radix.h.

Referenced by dns_iptable_merge(), and isc_radix_process().

#define RADIX_WALK_ALL ( Xhead,
Xnode   ) 

Value:

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)

Definition at line 220 of file radix.h.

#define RADIX_WALK_BREAK

Value:

{ \
            if (Xsp != Xstack) { \
                Xrn = *(--Xsp); \
             } else { \
                Xrn = (radix_node_t *) 0; \
            } \
            continue; }

Definition at line 228 of file radix.h.

#define RADIX_WALK_END

Value:

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)

Definition at line 236 of file radix.h.

Referenced by dns_iptable_merge(), and isc_radix_process().

Typedef Documentation

typedef struct isc_prefix isc_prefix_t

typedef void(* isc_radix_destroyfunc_t)(void *)

Definition at line 68 of file radix.h.

typedef void(* isc_radix_processfunc_t)(isc_prefix_t *, void **)

Definition at line 69 of file radix.h.

typedef struct isc_radix_node isc_radix_node_t

typedef struct isc_radix_tree isc_radix_tree_t

Function Documentation

isc_result_t isc_radix_search ( isc_radix_tree_t *  radix,
isc_radix_node_t **  target,
isc_prefix_t *  prefix 
)

Search 'radix' for the best match to 'prefix'. Return the node found in '*target'.

Requires:

Returns:

Definition at line 240 of file radix.c.

References _comp_with_mask(), isc_radix_node::bit, BIT_TEST, isc_prefix::bitlen, isc_radix_tree::head, isc_prefix_tochar, isc_prefix_touchar, ISC_R_NOTFOUND, ISC_R_SUCCESS, ISC_RADIX_OFF, isc_radix_node::l, isc_radix_tree::maxbits, isc_radix_node::node_num, isc_radix_node::prefix, isc_radix_node::r, RADIX_MAXBITS, REQUIRE, and RUNTIME_CHECK.

Referenced by ATF_TC_BODY(), ATF_TP_ADD_TCS(), and dns_acl_match2().

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 
)

Insert 'source' or 'prefix' into the radix tree 'radix'. Return the node added in 'target'.

Requires:

Returns:

Definition at line 309 of file radix.c.

References _ref_prefix(), isc_radix_node::bit, BIT_TEST, isc_prefix::bitlen, isc_radix_node::data, isc_prefix::family, isc_radix_tree::head, INSIST, isc_mem_get, isc_mem_put, isc_prefix_touchar, ISC_R_NOMEMORY, ISC_R_SUCCESS, ISC_RADIX_OFF, isc_radix_node::l, isc_radix_tree::maxbits, isc_radix_tree::mctx, new_node(), isc_radix_node::node_num, isc_radix_tree::num_active_node, isc_radix_tree::num_added_node, isc_radix_node::parent, isc_radix_node::prefix, isc_radix_node::r, r, REQUIRE, and RUNTIME_CHECK.

Referenced by ATF_TC_BODY(), dns_iptable_addprefix2(), and dns_iptable_merge().

void isc_radix_remove ( isc_radix_tree_t *  radix,
isc_radix_node_t *  node 
)

Remove the node 'node' from the radix tree 'radix'.

Requires:

Definition at line 619 of file radix.c.

References _deref_prefix(), isc_radix_node::data, isc_radix_tree::head, INSIST, isc_mem_put, isc_radix_node::l, isc_radix_tree::mctx, isc_radix_tree::num_active_node, isc_radix_node::parent, isc_radix_node::prefix, isc_radix_node::r, and REQUIRE.

isc_result_t isc_radix_create ( isc_mem_t *  mctx,
isc_radix_tree_t **  target,
int  maxbits 
)

Create a radix tree with a maximum depth of 'maxbits';.

Requires:

Returns:

Definition at line 144 of file radix.c.

References isc_radix_tree::head, isc_mem_attach(), isc_mem_get, ISC_R_NOMEMORY, ISC_R_SUCCESS, isc_radix_tree::magic, isc_radix_tree::maxbits, isc_radix_tree::mctx, isc_radix_tree::num_active_node, isc_radix_tree::num_added_node, RADIX_MAXBITS, RADIX_TREE_MAGIC, REQUIRE, and RUNTIME_CHECK.

Referenced by ATF_TC_BODY(), and dns_iptable_create().

void isc_radix_destroy ( isc_radix_tree_t *  radix,
isc_radix_destroyfunc_t  func 
)

Destroy a radix tree optionally calling 'func' to clean up node data.

Requires:

Definition at line 217 of file radix.c.

References _clear_radix(), isc_mem_putanddetach, isc_radix_tree::mctx, and REQUIRE.

Referenced by ATF_TC_BODY(), and destroy_iptable().

void isc_radix_process ( isc_radix_tree_t *  radix,
isc_radix_processfunc_t  func 
)

Walk a radix tree calling 'func' to process node data.

Requires:

Definition at line 228 of file radix.c.

References isc_radix_node::data, isc_radix_tree::head, isc_radix_node::prefix, RADIX_WALK, RADIX_WALK_END, and REQUIRE.

Referenced by dns_acl_isinsecure().

Generated on Tue Apr 28 17:41:15 2015 by Doxygen 1.5.4 for BIND9 Internals 9.11.0pre-alpha