addrtree.h File Reference

The addrtree is a radix tree designed for edns subnet. More...

Data Structures
struct	addrtree
struct	addrnode
struct	addredge

Macros
#define	KEYWIDTH   8

Typedefs
typedef uint8_t	addrlen_t
typedef uint8_t	addrkey_t

Functions
size_t	addrtree_size (const struct addrtree *tree)
	Size of tree in bytes. More...
struct addrtree *	addrtree_create (addrlen_t max_depth, void(*delfunc)(void *, void *), size_t(*sizefunc)(void *), void *env, uint32_t max_node_count)
	Create a new tree. More...
void	addrtree_delete (struct addrtree *tree)
	Free tree and all nodes below. More...
void	addrtree_insert (struct addrtree *tree, const addrkey_t *addr, addrlen_t sourcemask, addrlen_t scope, void *elem, time_t ttl, time_t now, int only_match_scope_zero)
	Insert an element in the tree. More...
struct addrnode *	addrtree_find (struct addrtree *tree, const addrkey_t *addr, addrlen_t sourcemask, time_t now)
	Find a node containing an element in the tree. More...
int	unittest_wrapper_addrtree_cmpbit (const addrkey_t *key1, const addrkey_t *key2, addrlen_t n)
	Wrappers for static functions to unit test.
addrlen_t	unittest_wrapper_addrtree_bits_common (const addrkey_t *s1, addrlen_t l1, const addrkey_t *s2, addrlen_t l2, addrlen_t skip)
int	unittest_wrapper_addrtree_getbit (const addrkey_t *addr, addrlen_t addrlen, addrlen_t n)
int	unittest_wrapper_addrtree_issub (const addrkey_t *s1, addrlen_t l1, const addrkey_t *s2, addrlen_t l2, addrlen_t skip)

Detailed Description

The addrtree is a radix tree designed for edns subnet.

Most notable is the addition of 'scope' to a node. Scope is only relevant for nodes with elem set, it indicates the number of bits the authority desires.

For retrieving data one needs an address and address length (sourcemask). While traversing the tree the first matching node is returned. A node matches when node.scope<=sourcemask && node.elem!=NULL (This is the most specific answer the authority has.) or node.sourcemask==sourcemask && node.elem!=NULL (This is the most specific question the client can ask.)

Insertion needs an address, sourcemask and scope. The length of the address is capped by min(sourcemask, scope). While traversing the tree the scope of all visited nodes is updated. This ensures we are always able to find the most specific answer available.

Function Documentation

addrtree_size()

size_t addrtree_size ( const struct addrtree *  tree )

inline

Size of tree in bytes.

Parameters

tree

Tree.

Returns

size of tree in bytes.

References addrtree::size_bytes.

Referenced by addrtree_delete().

addrtree_create()

struct addrtree* addrtree_create	(	addrlen_t	max_depth,
		void(*)(void *, void *)	delfunc,
		size_t(*)(void *)	sizefunc,
		void *	env,
		uint32_t	max_node_count
	)

Create a new tree.

Parameters

max_depth	Tree will cap keys to this length.
delfunc	f(element, env) delete element.
sizefunc	f(element) returning the size of element.
env	Module environment for alloc information.
max_node_count	Maximum size of this data structure in nodes. 0 for unlimited.

Returns

new addrtree or NULL on failure.

References addrtree::delfunc, addrtree::env, addrtree::first, addrtree::last, log_assert, addrtree::max_depth, addrtree::max_node_count, addrtree::node_count, node_create(), addrtree::size_bytes, and addrtree::sizefunc.

addrtree_delete()

void addrtree_delete

(

struct addrtree *

tree

)

Free tree and all nodes below.

Parameters

tree	Tree to be freed.

References addrtree_size(), clean_node(), addrtree::first, log_assert, addrnode::next, node_size(), addrnode::parent_edge, addrtree::size_bytes, and addredge::str.

addrtree_insert()

void addrtree_insert	(	struct addrtree *	tree,
		const addrkey_t *	addr,
		addrlen_t	sourcemask,
		addrlen_t	scope,
		void *	elem,
		time_t	ttl,
		time_t	now,
		int	only_match_scope_zero
	)

Insert an element in the tree.

Failures are silent. Sourcemask and scope might be changed according to local policy. Caller should no longer access elem, it could be free'd now or later during future inserts.

Parameters

tree	Tree insert elem in.
addr	key for element lookup.
sourcemask	Length of addr in bits.
scope	Number of significant bits in addr.
elem	data to store in the tree.
ttl	elem is valid up to this time, seconds.
only_match_scope_zero	set for when query /0 has scope /0 answer.
now	Current time in seconds.

References bits_common(), clean_node(), addrnode::edge, edge_create(), addrnode::elem, getbit(), addredge::len, log_assert, lru_cleanup(), lru_push(), addrtree::max_depth, addredge::node, addrtree::node_count, node_create(), node_size(), addrnode::only_match_scope_zero, addredge::parent_index, addredge::parent_node, purge_node(), addrnode::scope, addrtree::size_bytes, addrtree::sizefunc, addredge::str, and addrnode::ttl.

addrtree_find()

struct addrnode* addrtree_find	(	struct addrtree *	tree,
		const addrkey_t *	addr,
		addrlen_t	sourcemask,
		time_t	now
	)

Find a node containing an element in the tree.

Parameters

tree	Tree to search.
addr	key for element lookup.
sourcemask	Length of addr in bits.
now	Current time in seconds.

Returns

addrnode or NULL on miss.

References addrnode::edge, addrnode::elem, getbit(), issub(), addredge::len, log_assert, lru_update(), addredge::node, addrnode::only_match_scope_zero, addrnode::scope, addredge::str, and addrnode::ttl.