dnstree.h File Reference

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_type *tree)
 Init a name 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...
 
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...
 
int name_tree_next_root (rbtree_type *tree, uint16_t *dclass)
 Find next root item in name tree. More...
 
void addr_tree_init (rbtree_type *tree)
 Init addr tree to be empty. More...
 
void addr_tree_addrport_init (rbtree_type *tree)
 Init addr tree to be empty. 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 addr_tree_init_parents_node (struct addr_tree_node *node)
 Initialize parent pointers in partial addr 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_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
 
int addr_tree_addrport_compare (const void *k1, const void *k2)
 compare addr tree nodes (address and port only)
 

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 dns64_init(), priv_apply_cfg(), priv_create(), and setup_domain_limits().

◆ 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 rbnode_type::key, addr_tree_node::node, rbnode_type::parent, and rbtree_insert().

Referenced by caps_white_apply_cfg(), domain_limit_findcreate(), hints_insert(), and read_names().

◆ 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, rbnode_type::parent, name_tree_node::parent, and RBTREE_FOR.

Referenced by caps_white_apply_cfg(), dns64_apply_cfg(), priv_apply_cfg(), and setup_domain_limits().

◆ 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 domain_limit_findcreate(), hints_add_stub(), hints_delete_stub(), and hints_find().

◆ 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 dns64_always_synth_for_qname(), hints_lookup_stub(), infra_find_ratelimit(), is_caps_whitelisted(), and priv_lookup_name().

◆ 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_node::node, rbtree_find_less_equal(), rbtree_first(), rbtree_next(), and RBTREE_NULL.

Referenced by hints_next_root().

◆ addr_tree_init()

void addr_tree_init ( rbtree_type tree)

◆ addr_tree_addrport_init()

void addr_tree_addrport_init ( rbtree_type tree)

Init addr tree to be empty.

The comparison function to be used is addr_tree_addrport_compare.

Parameters
treeto init.

References addr_tree_addrport_compare(), and rbtree_init().

Referenced by acl_interface_init().

◆ 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, rbnode_type::parent, and rbtree_insert().

Referenced by acl_list_insert(), donotq_insert(), lz_enter_override(), read_addrs(), respip_sockaddr_find_or_create(), and tcl_list_insert().

◆ 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_init_parents_node(), and rbtree_first().

Referenced by acl_list_apply_cfg(), donotq_apply_cfg(), priv_apply_cfg(), respip_sockaddr_delete(), rpz_finish_config(), setup_wait_limits(), and tcl_list_apply_cfg().

◆ addr_tree_init_parents_node()

void addr_tree_init_parents_node ( struct addr_tree_node node)

Initialize parent pointers in partial addr tree.

Reinitialize pointer for part of tree, used after node deletion

Parameters
nodenode to start parent pointer initialization for.

References addr_tree_node::addr, addr_in_common(), addr_tree_node::addrlen, addr_tree_node::net, addr_tree_node::node, rbnode_type::parent, addr_tree_node::parent, rbtree_next(), and RBTREE_NULL.

Referenced by addr_tree_init_parents(), and respip_sockaddr_delete().

◆ 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(), edns_string_addr_lookup(), infra_wait_limit_allowed(), priv_lookup_addr(), respip_addr_lookup(), and tcl_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_sockaddr_find_or_create(), rpz_clientip_remove_trigger_rr(), verify_respip_set_actions(), and verify_rrset().