radix.c File Reference

#include <config.h>
#include <isc/mem.h>
#include <isc/types.h>
#include <isc/util.h>
#include <isc/radix.h>

Go to the source code of this file.

Functions
static isc_result_t	_new_prefix (isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest, int bitlen)
static void	_deref_prefix (isc_prefix_t *prefix)
static isc_result_t	_ref_prefix (isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix)
static int	_comp_with_mask (void *addr, void *dest, u_int mask)
static void	_clear_radix (isc_radix_tree_t *radix, isc_radix_destroyfunc_t func)
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.
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'.

---

Function Documentation

static isc_result_t _new_prefix	(	isc_mem_t *	mctx,
		isc_prefix_t **	target,
		int	family,
		void *	dest,
		int	bitlen
	)			[static]

Definition at line 49 of file radix.c.

References isc_prefix::add, AF_INET6, isc_prefix::bitlen, isc_prefix::ecs, isc_prefix::family, ISC_FALSE, isc_mem_attach(), isc_mem_get, ISC_R_NOMEMORY, ISC_R_NOTIMPLEMENTED, ISC_R_SUCCESS, isc_refcount_init(), isc_prefix::mctx, isc_prefix::refcount, REQUIRE, isc_prefix::sin, and isc_prefix::sin6.

Referenced by _ref_prefix().

static void _deref_prefix

(

isc_prefix_t *

prefix

)

[static]

Definition at line 84 of file radix.c.

References isc_mem_putanddetach, isc_refcount_decrement, isc_refcount_destroy, isc_prefix::mctx, and isc_prefix::refcount.

Referenced by _clear_radix(), and isc_radix_remove().

static isc_result_t _ref_prefix	(	isc_mem_t *	mctx,
		isc_prefix_t **	target,
		isc_prefix_t *	prefix
	)			[static]

Definition at line 100 of file radix.c.

References _new_prefix(), isc_prefix::add, AF_INET6, isc_prefix::bitlen, isc_prefix::family, INSIST, ISC_R_SUCCESS, isc_refcount_current, isc_refcount_increment, isc_prefix::refcount, and REQUIRE.

Referenced by isc_radix_insert().

static int _comp_with_mask	(	void *	addr,
		void *	dest,
		u_int	mask
	)			[static]

Definition at line 126 of file radix.c.

Referenced by isc_radix_search().

static void _clear_radix	(	isc_radix_tree_t *	radix,
		isc_radix_destroyfunc_t	func
	)			[static]

Definition at line 171 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::prefix, isc_radix_node::r, r, RADIX_MAXBITS, REQUIRE, and RUNTIME_CHECK.

Referenced by isc_radix_destroy().

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:

• 'mctx' to be valid.
• 'target' to be non NULL and '*target' to be NULL.
• 'maxbits' to be less than or equal to RADIX_MAXBITS.

Returns:

• ISC_R_NOMEMORY
• ISC_R_SUCCESS

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:

• 'radix' to be valid.

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:

• 'radix' to be valid.
• 'func' to point to a function.

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().

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:

• 'radix' to be valid.
• 'target' is not NULL and "*target" is NULL.
• 'prefix' to be valid.

Returns:

• ISC_R_NOTFOUND
• ISC_R_SUCCESS

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:

• 'radix' to be valid.
• 'target' is not NULL and "*target" is NULL.
• 'prefix' to be valid or 'source' to be non NULL and contain a valid prefix.

Returns:

• ISC_R_NOMEMORY
• ISC_R_SUCCESS

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:

• 'radix' to be valid.
• 'node' to be valid.

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.

---