Maintained by: NLnet Labs
Functions
dnstree.c File Reference

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

#include "config.h"
#include "util/storage/dnstree.h"
#include "util/data/dname.h"
#include "util/net_help.h"

Functions

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
 
void name_tree_init (rbtree_type *tree)
 Init a name tree to be empty. More...
 
void addr_tree_init (rbtree_type *tree)
 Init addr tree to be empty. More...
 
int name_tree_insert (rbtree_type *tree, struct name_tree_node *node, uint8_t *name, size_t len, int labs, uint16_t dclass)
 insert element into name tree. More...
 
int addr_tree_insert (rbtree_type *tree, struct addr_tree_node *node, struct sockaddr_storage *addr, socklen_t addrlen, int net)
 insert element into addr tree. More...
 
void addr_tree_init_parents (rbtree_type *tree)
 Initialize parent pointers in addr tree. More...
 
void name_tree_init_parents (rbtree_type *tree)
 Initialize parent pointers in name tree. More...
 
struct name_tree_nodename_tree_find (rbtree_type *tree, uint8_t *name, size_t len, int labs, uint16_t dclass)
 Lookup exact match in name tree. More...
 
struct name_tree_nodename_tree_lookup (rbtree_type *tree, uint8_t *name, size_t len, int labs, uint16_t dclass)
 Lookup closest encloser in name tree. More...
 
struct addr_tree_nodeaddr_tree_lookup (rbtree_type *tree, struct sockaddr_storage *addr, socklen_t addrlen)
 Lookup closest encloser in addr tree. More...
 
struct addr_tree_nodeaddr_tree_find (rbtree_type *tree, struct sockaddr_storage *addr, socklen_t addrlen, int net)
 Find element in addr tree. More...
 
int name_tree_next_root (rbtree_type *tree, uint16_t *dclass)
 Find next root item in name tree. More...
 

Detailed Description

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

Function Documentation

◆ name_tree_init()

void name_tree_init ( rbtree_type tree)

Init a name tree to be empty.

Parameters
treeto init.

References name_tree_compare(), and rbtree_init().

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

◆ addr_tree_init()

void addr_tree_init ( rbtree_type tree)

Init addr tree to be empty.

Parameters
treeto init.

References addr_tree_compare(), and rbtree_init().

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

◆ name_tree_insert()

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

insert element into name tree.

Parameters
treename tree
nodenode element (at start of a structure that caller has allocated).
namename to insert (wireformat) this node has been allocated by the caller and it itself inserted.
lenlength of name
labslabels in name
dclassclass of name
Returns
false on error (duplicate element).

References name_tree_node::dclass, rbnode_type::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 caps_white_apply_cfg(), domain_limit_findcreate(), hints_insert(), and read_names().

◆ addr_tree_insert()

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

insert element into addr tree.

Parameters
treeaddr tree
nodenode element (at start of a structure that caller has allocated).
addrto insert (copied).
addrlenlength of addr
netsize of subnet.
Returns
false on error (duplicate element).

References addr_tree_node::addr, addr_tree_node::addrlen, rbnode_type::key, addr_tree_node::net, addr_tree_node::node, addr_tree_node::parent, and rbtree_insert().

Referenced by acl_list_insert(), donotq_insert(), lz_enter_override(), read_addrs(), and respip_find_or_create().

◆ addr_tree_init_parents()

void addr_tree_init_parents ( rbtree_type tree)

Initialize parent pointers in addr tree.

Should be performed after insertions are done, before lookups

Parameters
treeaddr tree

References addr_tree_node::addr, addr_in_common(), addr_tree_node::addrlen, addr_tree_node::net, addr_tree_node::node, addr_tree_node::parent, and RBTREE_FOR.

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

◆ name_tree_init_parents()

void name_tree_init_parents ( rbtree_type tree)

Initialize parent pointers in name tree.

Should be performed after insertions are done, before lookups

Parameters
treename 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 caps_white_apply_cfg(), infra_create(), and priv_apply_cfg().

◆ name_tree_find()

struct name_tree_node* name_tree_find ( rbtree_type tree,
uint8_t *  name,
size_t  len,
int  labs,
uint16_t  dclass 
)

Lookup exact match in name tree.

Parameters
treename tree
namewireformat name
lenlength of name
labslabels in name
dclassclass of name
Returns
node or NULL if not found.

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

Referenced by can_have_last_resort(), domain_limit_findcreate(), hints_add_stub(), hints_delete_stub(), and hints_lookup_root().

◆ name_tree_lookup()

struct name_tree_node* name_tree_lookup ( rbtree_type tree,
uint8_t *  name,
size_t  len,
int  labs,
uint16_t  dclass 
)

Lookup closest encloser in name tree.

Parameters
treename tree
namewireformat name
lenlength of name
labslabels in name
dclassclass of name
Returns
closest enclosing node (could be equal) or NULL if not found.

References name_tree_node::dclass, dname_lab_cmp(), rbnode_type::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(), infra_find_ratelimit(), is_caps_whitelisted(), and priv_lookup_name().

◆ addr_tree_lookup()

struct addr_tree_node* addr_tree_lookup ( rbtree_type tree,
struct sockaddr_storage *  addr,
socklen_t  addrlen 
)

Lookup closest encloser in addr tree.

Parameters
treeaddr tree
addrto lookup.
addrlenlength of addr
Returns
closest enclosing node (could be equal) or NULL if not found.

References addr_tree_node::addr, addr_in_common(), addr_is_ip6(), addr_tree_node::addrlen, rbnode_type::key, addr_tree_node::net, addr_tree_node::node, addr_tree_node::parent, and rbtree_find_less_equal().

Referenced by acl_addr_lookup(), donotq_lookup(), priv_lookup_addr(), and respip_addr_lookup().

◆ addr_tree_find()

struct addr_tree_node* addr_tree_find ( rbtree_type tree,
struct sockaddr_storage *  addr,
socklen_t  addrlen,
int  net 
)

Find element in addr tree.

(search a netblock, not a match for an address)

Parameters
treeaddr tree
addrnetblock to lookup.
addrlenlength of addr
netsize of subnet
Returns
addr tree element, or NULL if not found.

References addr_tree_node::addr, addr_tree_node::addrlen, rbnode_type::key, addr_tree_node::net, addr_tree_node::node, and rbtree_search().

Referenced by acl_find_or_create(), respip_find_or_create(), verify_respip_set_actions(), and verify_rrset().

◆ name_tree_next_root()

int name_tree_next_root ( rbtree_type tree,
uint16_t *  dclass 
)

Find next root item in name tree.

Parameters
treethe nametree.
dclassthe 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_type::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().