This file contains structures combining types and functions to manipulate those structures that help building DNS lookup trees. More...

#include "util/rbtree.h"

Data Structures
struct	name_tree_node
	Tree of domain names. More...
struct	addr_tree_node
	Tree of IP addresses. More...
Functions
void	name_tree_init (rbtree_t *tree)
	Init a name tree to be empty.
int	name_tree_insert (rbtree_t tree, struct name_tree_node node, uint8_t *name, size_t len, int labs, uint16_t dclass)
	insert element into name tree.
void	name_tree_init_parents (rbtree_t *tree)
	Initialize parent pointers in name tree.
struct name_tree_node *	name_tree_find (rbtree_t tree, uint8_t name, size_t len, int labs, uint16_t dclass)
	Lookup exact match in name tree.
struct name_tree_node *	name_tree_lookup (rbtree_t tree, uint8_t name, size_t len, int labs, uint16_t dclass)
	Lookup closest encloser in name tree.
int	name_tree_next_root (rbtree_t tree, uint16_t dclass)
	Find next root item in name tree.
void	addr_tree_init (rbtree_t *tree)
	Init addr tree to be empty.
int	addr_tree_insert (rbtree_t tree, struct addr_tree_node node, struct sockaddr_storage *addr, socklen_t addrlen, int net)
	insert element into addr tree.
void	addr_tree_init_parents (rbtree_t *tree)
	Initialize parent pointers in addr tree.
struct addr_tree_node *	addr_tree_lookup (rbtree_t tree, struct sockaddr_storage addr, socklen_t addrlen)
	Lookup closest encloser in addr tree.
int	name_tree_compare (const void k1, const void k2)
	compare name tree nodes
int	addr_tree_compare (const void k1, const void k2)
	compare addr tree nodes

Detailed Description

This file contains structures combining types and functions to manipulate those structures that help building DNS lookup trees.

Function Documentation

void name_tree_init ( rbtree_t * tree )

Init a name tree to be empty.

Parameters:

tree,: to init.

References name_tree_compare(), and rbtree_init().

Referenced by hints_apply_cfg(), priv_apply_cfg(), and priv_create().

int name_tree_insert	(	rbtree_t *	tree,
		struct name_tree_node *	node,
		uint8_t *	name,
		size_t	len,
		int	labs,
		uint16_t	dclass
	)

insert element into name tree.

Parameters:

tree,:	name tree
node,:	node element (at start of a structure that caller has allocated).
name,:	name to insert (wireformat) this node has been allocated by the caller and it itself inserted.
len,:	length of name
labs,:	labels in name
dclass,:	class of name

Returns:: false on error (duplicate element).

References name_tree_node::dclass, rbnode_t::key, name_tree_node::labs, name_tree_node::len, name_tree_node::name, name_tree_node::node, addr_tree_node::node, name_tree_node::parent, and rbtree_insert().

Referenced by hints_insert(), and read_names().

void name_tree_init_parents ( rbtree_t * tree )

Initialize parent pointers in name tree.

Should be performed after insertions are done, before lookups

Parameters:

tree,: name tree

References name_tree_node::dclass, dname_lab_cmp(), name_tree_node::labs, name_tree_node::name, name_tree_node::node, name_tree_node::parent, and RBTREE_FOR.

Referenced by hints_apply_cfg(), and priv_apply_cfg().

struct name_tree_node* name_tree_find	(	rbtree_t *	tree,
		uint8_t *	name,
		size_t	len,
		int	labs,
		uint16_t	dclass
	)		`[read]`

Lookup exact match in name tree.

Parameters:

tree,:	name tree
name,:	wireformat name
len,:	length of name
labs,:	labels in name
dclass,:	class of name

Returns:: node or NULL if not found.

References name_tree_node::dclass, rbnode_t::key, name_tree_node::labs, name_tree_node::len, name_tree_node::name, name_tree_node::node, and rbtree_search().

Referenced by hints_lookup_root().

struct name_tree_node* name_tree_lookup	(	rbtree_t *	tree,
		uint8_t *	name,
		size_t	len,
		int	labs,
		uint16_t	dclass
	)		`[read]`

Lookup closest encloser in name tree.

Parameters:

tree,:	name tree
name,:	wireformat name
len,:	length of name
labs,:	labels in name
dclass,:	class of name

Returns:: closest enclosing node (could be equal) or NULL if not found.

References name_tree_node::dclass, dname_lab_cmp(), rbnode_t::key, name_tree_node::labs, name_tree_node::len, name_tree_node::name, name_tree_node::node, name_tree_node::parent, and rbtree_find_less_equal().

Referenced by hints_lookup_stub(), and priv_lookup_name().

int name_tree_next_root	(	rbtree_t *	tree,
		uint16_t *	dclass
	)

Find next root item in name tree.

Parameters:

tree,:	the nametree.
dclass,:	the class to look for next (or higher).

Returns:: false if no classes found, true means class put into c.

References name_tree_node::dclass, dname_is_root(), rbnode_t::key, name_tree_node::labs, name_tree_node::len, name_tree_node::name, name_tree_next_root(), name_tree_node::node, rbtree_find_less_equal(), rbtree_first(), rbtree_next(), and RBTREE_NULL.

Referenced by hints_next_root(), and name_tree_next_root().

void addr_tree_init ( rbtree_t * tree )

Init addr tree to be empty.

Parameters:

tree,: to init.

References addr_tree_compare(), and rbtree_init().

Referenced by acl_list_apply_cfg(), donotq_apply_cfg(), priv_apply_cfg(), and priv_create().

int addr_tree_insert	(	rbtree_t *	tree,
		struct addr_tree_node *	node,
		struct sockaddr_storage *	addr,
		socklen_t	addrlen,
		int	net
	)

insert element into addr tree.

Parameters:

tree,:	addr tree
node,:	node element (at start of a structure that caller has allocated).
addr,:	to insert (copied).
addrlen,:	length of addr
net,:	size of subnet.