lib » dns

rbt.c File Reference

#include <config.h>
#include <sys/stat.h>
#include <isc/crc64.h>
#include <isc/file.h>
#include <isc/hex.h>
#include <isc/mem.h>
#include <isc/platform.h>
#include <isc/print.h>
#include <isc/refcount.h>
#include <isc/socket.h>
#include <isc/stdio.h>
#include <isc/string.h>
#include <isc/util.h>
#include <dns/fixedname.h>
#include <dns/log.h>
#include <dns/rbt.h>
#include <dns/result.h>
#include <dns/version.h>
#include <unistd.h>

Go to the source code of this file.

Data Structures

struct dns_rbt

struct file_header

Defines

#define DNS_NAME_USEINLINE   1

This define is so dns/name.h (included by dns/fixedname.h) uses more efficient macro calls instead of functions for a few operations.

#define CHECK(x)

#define RBT_MAGIC   ISC_MAGIC('R', 'B', 'T', '+')

#define VALID_RBT(rbt)   ISC_MAGIC_VALID(rbt, RBT_MAGIC)

#define CHAIN_MAGIC   ISC_MAGIC('0', '-', '0', '-')

#define VALID_CHAIN(chain)   ISC_MAGIC_VALID(chain, CHAIN_MAGIC)

#define RBT_HASH_SIZE   64

#define RED   0

#define BLACK   1

#define HEADER_LENGTH   1024

#define PARENT(node)   ((node)->parent)

Elements of the rbtnode structure.

#define LEFT(node)   ((node)->left)

#define RIGHT(node)   ((node)->right)

#define DOWN(node)   ((node)->down)

#define DATA(node)   ((node)->data)

#define IS_EMPTY(node)   ((node)->data == NULL)

#define HASHNEXT(node)   ((node)->hashnext)

#define HASHVAL(node)   ((node)->hashval)

#define COLOR(node)   ((node)->color)

#define NAMELEN(node)   ((node)->namelen)

#define OLDNAMELEN(node)   ((node)->oldnamelen)

#define OFFSETLEN(node)   ((node)->offsetlen)

#define ATTRS(node)   ((node)->attributes)

#define IS_ROOT(node)   ISC_TF((node)->is_root == 1)

#define FINDCALLBACK(node)   ISC_TF((node)->find_callback == 1)

#define DIRTY(node)   ((node)->dirty)

Structure elements from the rbtdb.c, not used as part of the rbt.c algorithms.

#define WILD(node)   ((node)->wild)

#define LOCKNUM(node)   ((node)->locknum)

#define NAME(node)   ((unsigned char *)((node) + 1))

The variable length stuff stored after the node has the following structure.

#define OFFSETS(node)   (NAME(node) + OLDNAMELEN(node) + 1)

#define OLDOFFSETLEN(node)   (OFFSETS(node)[-1])

#define NODE_SIZE(node)

#define IS_RED(node)   ((node) != NULL && (node)->color == RED)

Color management.

#define IS_BLACK(node)   ((node) == NULL || (node)->color == BLACK)

#define MAKE_RED(node)   ((node)->color = RED)

#define MAKE_BLACK(node)   ((node)->color = BLACK)

#define ADD_LEVEL(chain, node)

Chain management.

#define hash_node(rbt, node, name)

#define unhash_node(rbt, node)

#define rehash(rbt, newcount)

#define CONFIRM(a)

Typedefs

typedef struct file_header file_header_t

Functions

static isc_result_t dns_rbt_zero_header (FILE *file)

static isc_result_t write_header (FILE *file, dns_rbt_t *rbt, isc_uint64_t first_node_offset, isc_uint64_t crc)

static isc_result_t serialize_node (FILE *file, dns_rbtnode_t *node, uintptr_t left, uintptr_t right, uintptr_t down, uintptr_t parent, uintptr_t data, isc_uint64_t *crc)

static isc_result_t serialize_nodes (FILE *file, dns_rbtnode_t *node, uintptr_t parent, dns_rbtdatawriter_t datawriter, void *writer_arg, uintptr_t *where, isc_uint64_t *crc)

static dns_rbtnode_t * getparent (dns_rbtnode_t *node, file_header_t *header)

static dns_rbtnode_t * getleft (dns_rbtnode_t *node, file_header_t *header)

static dns_rbtnode_t * getright (dns_rbtnode_t *node, file_header_t *header)

static dns_rbtnode_t * getdown (dns_rbtnode_t *node, file_header_t *header)

static dns_rbtnode_t * getdata (dns_rbtnode_t *node, file_header_t *header)

static void NODENAME (dns_rbtnode_t *node, dns_name_t *name)

The following macros directly access normally private name variables. These macros are used to avoid a lot of function calls in the critical path of the tree traversal code.

void dns_rbtnode_nodename (dns_rbtnode_t *node, dns_name_t *name)

dns_rbtnode_t * dns_rbt_root (dns_rbt_t *rbt)

static dns_rbtnode_t * get_subtree_root (dns_rbtnode_t *node)

static dns_rbtnode_t * get_upper_node (dns_rbtnode_t *node)

size_t dns__rbtnode_getdistance (dns_rbtnode_t *node)

Return the distance (in nodes) from the node to its upper node of its subtree. The root node has a distance of 1. A child of the root node has a distance of 2.

static isc_result_t create_node (isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep)

static void rotate_left (dns_rbtnode_t *node, dns_rbtnode_t **rootp)

static void rotate_right (dns_rbtnode_t *node, dns_rbtnode_t **rootp)

static void addonlevel (dns_rbtnode_t *node, dns_rbtnode_t *current, int order, dns_rbtnode_t **rootp)

static void deletefromlevel (dns_rbtnode_t *delete, dns_rbtnode_t **rootp)

static isc_result_t treefix (dns_rbt_t *rbt, void *base, size_t size, dns_rbtnode_t *n, dns_name_t *name, dns_rbtdatafixer_t datafixer, void *fixer_arg, isc_uint64_t *crc)

static isc_result_t deletetree (dns_rbt_t *rbt, dns_rbtnode_t *node)

static void deletetreeflat (dns_rbt_t *rbt, unsigned int quantum, dns_rbtnode_t **nodep)

static void printnodename (dns_rbtnode_t *node, isc_boolean_t quoted, FILE *f)

static void freenode (dns_rbt_t *rbt, dns_rbtnode_t **nodep)

off_t dns_rbt_serialize_align (off_t target)

Align the provided integer to a pointer-size boundary. This should be used if, during serialization of data to a will-be mmap()ed file, a pointer alignment is needed for some data.

isc_result_t dns_rbt_serialize_tree (FILE *file, dns_rbt_t *rbt, dns_rbtdatawriter_t datawriter, void *writer_arg, off_t *offset)

Write out the RBT structure and its data to a file.

isc_result_t dns_rbt_deserialize_tree (void *base_address, size_t filesize, off_t header_offset, isc_mem_t *mctx, dns_rbtdeleter_t deleter, void *deleter_arg, dns_rbtdatafixer_t datafixer, void *fixer_arg, dns_rbtnode_t **originp, dns_rbt_t **rbtp)

Read a RBT structure and its data from a file.

isc_result_t dns_rbt_create (isc_mem_t *mctx, dns_rbtdeleter_t deleter, void *deleter_arg, dns_rbt_t **rbtp)

Initialize a red-black tree of trees.

void dns_rbt_destroy (dns_rbt_t **rbtp)

isc_result_t dns_rbt_destroy2 (dns_rbt_t **rbtp, unsigned int quantum)

Stop working with a red-black tree of trees. If 'quantum' is zero then the entire tree will be destroyed. If 'quantum' is non zero then up to 'quantum' nodes will be destroyed allowing the rbt to be incrementally destroyed by repeated calls to dns_rbt_destroy2(). Once dns_rbt_destroy2() has been called no other operations than dns_rbt_destroy()/dns_rbt_destroy2() should be performed on the tree of trees.

unsigned int dns_rbt_nodecount (dns_rbt_t *rbt)

Obtain the number of nodes in the tree of trees.

unsigned int dns_rbt_hashsize (dns_rbt_t *rbt)

Obtain the current number of buckets in the 'rbt' hash table.

static isc_result_t chain_name (dns_rbtnodechain_t *chain, dns_name_t *name, isc_boolean_t include_chain_end)

static isc_result_t move_chain_to_last (dns_rbtnodechain_t *chain, dns_rbtnode_t *node)

isc_result_t dns_rbt_addnode (dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep)

Just like dns_rbt_addname, but returns the address of the node.

isc_result_t dns_rbt_addname (dns_rbt_t *rbt, dns_name_t *name, void *data)

Add 'name' to the tree of trees, associated with 'data'.

isc_result_t dns_rbt_findnode (dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname, dns_rbtnode_t **node, dns_rbtnodechain_t *chain, unsigned int options, dns_rbtfindcallback_t callback, void *callback_arg)

Find the node for 'name'.

isc_result_t dns_rbt_findname (dns_rbt_t *rbt, dns_name_t *name, unsigned int options, dns_name_t *foundname, void **data)

Get the data pointer associated with 'name'.

isc_result_t dns_rbt_deletename (dns_rbt_t *rbt, dns_name_t *name, isc_boolean_t recurse)

Delete 'name' from the tree of trees.

isc_result_t dns_rbt_deletenode (dns_rbt_t *rbt, dns_rbtnode_t *node, isc_boolean_t recurse)

Delete 'node' from the tree of trees.

void dns_rbt_namefromnode (dns_rbtnode_t *node, dns_name_t *name)

Convert the sequence of labels stored at 'node' into a 'name'.

isc_result_t dns_rbt_fullnamefromnode (dns_rbtnode_t *node, dns_name_t *name)

Like dns_rbt_namefromnode, but returns the full name from the root.

char * dns_rbt_formatnodename (dns_rbtnode_t *node, char *printname, unsigned int size)

Format the full name of a node for printing, using dns_name_format().

static size_t getheight_helper (dns_rbtnode_t *node)

size_t dns__rbt_getheight (dns_rbt_t *rbt)

Return the maximum height of sub-root nodes found in the red-black forest.

static isc_boolean_t check_properties_helper (dns_rbtnode_t *node)

static isc_boolean_t check_black_distance_helper (dns_rbtnode_t *node, size_t *distance)

isc_boolean_t dns__rbt_checkproperties (dns_rbt_t *rbt)

Check red-black properties of the forest.

static void dns_rbt_indent (FILE *f, int depth)

void dns_rbt_printnodeinfo (dns_rbtnode_t *n, FILE *f)

Print out various information about a node.

static void print_text_helper (dns_rbtnode_t *root, dns_rbtnode_t *parent, int depth, const char *direction, void(*data_printer)(FILE *, void *), FILE *f)

void dns_rbt_printtext (dns_rbt_t *rbt, void(*data_printer)(FILE *, void *), FILE *f)

Print an ASCII representation of the internal structure of the red-black tree of trees to the passed stream.

static int print_dot_helper (dns_rbtnode_t *node, unsigned int *nodecount, isc_boolean_t show_pointers, FILE *f)

void dns_rbt_printdot (dns_rbt_t *rbt, isc_boolean_t show_pointers, FILE *f)

Print a GraphViz dot representation of the internal structure of the red-black tree of trees to the passed stream.

void dns_rbtnodechain_init (dns_rbtnodechain_t *chain, isc_mem_t *mctx)

Initialize 'chain'.

isc_result_t dns_rbtnodechain_current (dns_rbtnodechain_t *chain, dns_name_t *name, dns_name_t *origin, dns_rbtnode_t **node)

Provide the name, origin and node to which the chain is currently pointed.

isc_result_t dns_rbtnodechain_prev (dns_rbtnodechain_t *chain, dns_name_t *name, dns_name_t *origin)

Adjusts chain to point the DNSSEC predecessor of the name to which it is currently pointed.

isc_result_t dns_rbtnodechain_down (dns_rbtnodechain_t *chain, dns_name_t *name, dns_name_t *origin)

Descend down if possible.

isc_result_t dns_rbtnodechain_nextflat (dns_rbtnodechain_t *chain, dns_name_t *name)

Find the next node at the current depth in DNSSEC order.

isc_result_t dns_rbtnodechain_next (dns_rbtnodechain_t *chain, dns_name_t *name, dns_name_t *origin)

Adjusts chain to point the DNSSEC successor of the name to which it is currently pointed.

isc_result_t dns_rbtnodechain_first (dns_rbtnodechain_t *chain, dns_rbt_t *rbt, dns_name_t *name, dns_name_t *origin)

Set the chain to the lexically first node in the tree of trees.

isc_result_t dns_rbtnodechain_last (dns_rbtnodechain_t *chain, dns_rbt_t *rbt, dns_name_t *name, dns_name_t *origin)

Set the chain to the lexically last node in the tree of trees.

void dns_rbtnodechain_reset (dns_rbtnodechain_t *chain)

Free any dynamic storage associated with 'chain', and then reinitialize 'chain'.

void dns_rbtnodechain_invalidate (dns_rbtnodechain_t *chain)

Free any dynamic storage associated with 'chain', and then invalidates it.

Variables

static char FILE_VERSION [32] = "\0"

Detailed Description

Definition in file rbt.c.

Define Documentation

#define DNS_NAME_USEINLINE 1

This define is so dns/name.h (included by dns/fixedname.h) uses more efficient macro calls instead of functions for a few operations.

Definition at line 45 of file rbt.c.

#define CHECK ( x )

Value:

do { \
                result = (x); \
                if (result != ISC_R_SUCCESS) \
                        goto cleanup; \
        } while (0)

Definition at line 55 of file rbt.c.

#define RBT_MAGIC ISC_MAGIC('R', 'B', 'T', '+')

Definition at line 62 of file rbt.c.

Referenced by dns_rbt_create().

#define VALID_RBT ( rbt ) ISC_MAGIC_VALID(rbt, RBT_MAGIC)

Definition at line 63 of file rbt.c.

Referenced by deletetree(), deletetreeflat(), dns_rbt_addname(), dns_rbt_addnode(), dns_rbt_deletename(), dns_rbt_deletenode(), dns_rbt_destroy2(), dns_rbt_findnode(), dns_rbt_hashsize(), dns_rbt_nodecount(), dns_rbt_printdot(), dns_rbt_printtext(), dns_rbtnodechain_first(), and dns_rbtnodechain_last().

#define CHAIN_MAGIC ISC_MAGIC('0', '-', '0', '-')

Definition at line 70 of file rbt.c.

Referenced by dns_rbtnodechain_init().

#define VALID_CHAIN ( chain ) ISC_MAGIC_VALID(chain, CHAIN_MAGIC)

Definition at line 71 of file rbt.c.

Referenced by dns_rbtnodechain_current(), dns_rbtnodechain_down(), dns_rbtnodechain_first(), dns_rbtnodechain_last(), dns_rbtnodechain_next(), dns_rbtnodechain_nextflat(), dns_rbtnodechain_prev(), and dns_rbtnodechain_reset().

#define RBT_HASH_SIZE 64

Definition at line 73 of file rbt.c.

#define RED 0

Definition at line 92 of file rbt.c.

#define BLACK 1

Definition at line 93 of file rbt.c.

#define HEADER_LENGTH 1024

Definition at line 107 of file rbt.c.

Referenced by dns_rbt_serialize_tree(), and dns_rbt_zero_header().

#define PARENT ( node ) ((node)->parent)

Elements of the rbtnode structure.

Definition at line 207 of file rbt.c.

Referenced by addonlevel(), check_properties_helper(), create_node(), deletefromlevel(), deletetreeflat(), dns__rbtnode_getdistance(), dns_rbt_addnode(), dns_rbt_findnode(), dns_rbtnodechain_next(), dns_rbtnodechain_nextflat(), dns_rbtnodechain_prev(), get_subtree_root(), get_upper_node(), print_dot_helper(), print_text_helper(), rotate_left(), and rotate_right().

#define LEFT ( node ) ((node)->left)

#define RIGHT ( node ) ((node)->right)

#define DOWN ( node ) ((node)->down)

Definition at line 210 of file rbt.c.

Referenced by check_black_distance_helper(), check_properties_helper(), create_node(), deletetree(), deletetreeflat(), dns_rbt_addnode(), dns_rbt_deletenode(), dns_rbt_findnode(), dns_rbtnodechain_down(), dns_rbtnodechain_next(), dns_rbtnodechain_prev(), getheight_helper(), move_chain_to_last(), print_dot_helper(), and print_text_helper().

#define DATA ( node ) ((node)->data)

Definition at line 211 of file rbt.c.

Referenced by create_node(), deletetree(), deletetreeflat(), dns_rbt_addname(), dns_rbt_deletename(), dns_rbt_deletenode(), dns_rbt_findname(), and dns_rbt_findnode().

#define IS_EMPTY ( node ) ((node)->data == NULL)

Definition at line 212 of file rbt.c.

Referenced by print_dot_helper().

#define HASHNEXT ( node ) ((node)->hashnext)

Definition at line 213 of file rbt.c.

Referenced by create_node().

#define HASHVAL ( node ) ((node)->hashval)

Definition at line 214 of file rbt.c.

Referenced by create_node(), and dns_rbt_findnode().

#define COLOR ( node ) ((node)->color)

Definition at line 215 of file rbt.c.

Referenced by deletefromlevel(), and dns_rbt_addnode().

#define NAMELEN ( node ) ((node)->namelen)

Definition at line 216 of file rbt.c.

Referenced by create_node(), dns_rbt_addnode(), dns_rbtnode_nodename(), NODENAME(), and printnodename().

#define OLDNAMELEN ( node ) ((node)->oldnamelen)

Definition at line 217 of file rbt.c.

Referenced by create_node().

#define OFFSETLEN ( node ) ((node)->offsetlen)

Definition at line 218 of file rbt.c.

Referenced by create_node(), dns_rbt_addnode(), dns_rbtnode_nodename(), dns_rbtnodechain_down(), dns_rbtnodechain_next(), dns_rbtnodechain_prev(), and NODENAME().

#define ATTRS ( node ) ((node)->attributes)

Definition at line 219 of file rbt.c.

Referenced by create_node(), dns_rbt_addnode(), dns_rbtnode_nodename(), and NODENAME().

#define IS_ROOT ( node ) ISC_TF((node)->is_root == 1)

Definition at line 220 of file rbt.c.

Referenced by addonlevel(), check_properties_helper(), deletefromlevel(), dns__rbtnode_getdistance(), dns_rbt_addnode(), dns_rbtnodechain_next(), dns_rbtnodechain_nextflat(), dns_rbtnodechain_prev(), get_subtree_root(), print_dot_helper(), print_text_helper(), rotate_left(), and rotate_right().

#define FINDCALLBACK ( node ) ISC_TF((node)->find_callback == 1)

Definition at line 221 of file rbt.c.

Referenced by dns_rbt_findnode().

#define DIRTY ( node ) ((node)->dirty)

Structure elements from the rbtdb.c, not used as part of the rbt.c algorithms.

Definition at line 227 of file rbt.c.

Referenced by create_node().

#define WILD ( node ) ((node)->wild)

Definition at line 228 of file rbt.c.

Referenced by create_node().

#define LOCKNUM ( node ) ((node)->locknum)

Definition at line 229 of file rbt.c.

Referenced by create_node().

#define NAME ( node ) ((unsigned char *)((node) + 1))

The variable length stuff stored after the node has the following structure.

<name_data>{1..255}<oldoffsetlen>{1}<offsets>{1..128}

<name_data> contains the name of the node when it was created. <oldoffsetlen> contains the length of <offsets> when the node was created. <offsets> contains the offets into name for each label when the node was created.

Definition at line 243 of file rbt.c.

#define OFFSETS ( node ) (NAME(node) + OLDNAMELEN(node) + 1)

Definition at line 244 of file rbt.c.

Referenced by create_node(), dns_rbtnode_nodename(), and NODENAME().

#define OLDOFFSETLEN ( node ) (OFFSETS(node)[-1])

Definition at line 245 of file rbt.c.

Referenced by create_node().

#define NODE_SIZE ( node )

Value:

(sizeof(*node) + \
                         OLDNAMELEN(node) + OLDOFFSETLEN(node) + 1)

Definition at line 247 of file rbt.c.

Referenced by freenode(), serialize_node(), serialize_nodes(), and treefix().

#define IS_RED ( node ) ((node) != NULL && (node)->color == RED)

Color management.

Definition at line 253 of file rbt.c.

Referenced by addonlevel(), check_properties_helper(), deletefromlevel(), print_dot_helper(), and print_text_helper().

#define IS_BLACK ( node ) ((node) == NULL || (node)->color == BLACK)

Definition at line 254 of file rbt.c.

Referenced by check_black_distance_helper(), and deletefromlevel().

#define MAKE_RED ( node ) ((node)->color = RED)

Definition at line 255 of file rbt.c.

Referenced by addonlevel(), and deletefromlevel().

#define MAKE_BLACK ( node ) ((node)->color = BLACK)

Definition at line 256 of file rbt.c.

Referenced by addonlevel(), create_node(), deletefromlevel(), and dns_rbt_addnode().

#define ADD_LEVEL	(	chain,
		node		)

Value:

do { \
                INSIST((chain)->level_count < DNS_RBT_LEVELBLOCK); \
                (chain)->levels[(chain)->level_count++] = (node); \
        } while (0)

Chain management.

The "ancestors" member of chains were removed, with their job now being wholly handled by parent pointers (which didn't exist, because of memory concerns, when chains were first implemented).

Definition at line 265 of file rbt.c.

Referenced by dns_rbt_addnode(), dns_rbt_findnode(), dns_rbtnodechain_down(), dns_rbtnodechain_next(), dns_rbtnodechain_prev(), and move_chain_to_last().

#define hash_node	(	rbt,
		node,
		name	)

Definition at line 400 of file rbt.c.

Referenced by dns_rbt_addnode(), and treefix().

#define unhash_node	(	rbt,
		node		)

Definition at line 401 of file rbt.c.

Referenced by deletetree(), and dns_rbt_deletenode().

#define rehash	(	rbt,
		newcount		)

Definition at line 402 of file rbt.c.

Referenced by dns_rbt_deserialize_tree().

#define CONFIRM ( a )

Value:

do { \
        if (! (a)) { \
                result = ISC_R_INVALIDFILE; \
                goto cleanup; \
        } \
} while(0);

Definition at line 711 of file rbt.c.

Referenced by treefix().

Typedef Documentation

typedef struct file_header file_header_t

Definition at line 101 of file rbt.c.

Function Documentation

static isc_result_t dns_rbt_zero_header ( FILE * file ) [static]

Definition at line 436 of file rbt.c.

References buffer, HEADER_LENGTH, ISC_R_SUCCESS, and isc_stdio_write().

Referenced by dns_rbt_serialize_tree().

static isc_result_t write_header	(	FILE *	file,
		dns_rbt_t *	rbt,
		isc_uint64_t	first_node_offset,
		isc_uint64_t	crc
	)			`[static]`

Definition at line 465 of file rbt.c.

References file_header::bigendian, CHECK, cleanup(), file_header::crc, dns_major, dns_mapapi, dns_rbt_serialize_align(), FILE_VERSION, file_header::first_node_offset, header, isc_stdio_seek(), isc_stdio_tell(), isc_stdio_write(), dns_rbt::nodecount, file_header::nodecount, file_header::ptrsize, file_header::rdataset_fixed, file_header::version1, and file_header::version2.

Referenced by dns_rbt_serialize_tree().

static isc_result_t serialize_node	(	FILE *	file,
		dns_rbtnode_t *	node,
		uintptr_t	left,
		uintptr_t	right,
		uintptr_t	down,
		uintptr_t	parent,
		uintptr_t	data,
		isc_uint64_t *	crc
	)			`[static]`

static isc_result_t serialize_nodes	(	FILE *	file,
		dns_rbtnode_t *	node,
		uintptr_t	parent,
		dns_rbtdatawriter_t	datawriter,
		void *	writer_arg,
		uintptr_t *	where,
		isc_uint64_t *	crc
	)			`[static]`

Definition at line 590 of file rbt.c.

References CHECK, cleanup(), dns_rbtnode::data, dns_rbt_serialize_align(), getdown(), getleft(), getright(), ISC_R_SUCCESS, isc_stdio_seek(), isc_stdio_tell(), NODE_SIZE, and serialize_node().

Referenced by dns_rbt_serialize_tree().

static dns_rbtnode_t* getparent	(	dns_rbtnode_t *	node,
		file_header_t *	header
	)			`[inline, static]`

Definition at line 165 of file rbt.c.

References dns_rbtnode::parent, and dns_rbtnode::parent_is_relative.

Referenced by treefix().

static dns_rbtnode_t* getleft	(	dns_rbtnode_t *	node,
		file_header_t *	header
	)			`[inline, static]`

Definition at line 173 of file rbt.c.

References dns_rbtnode::left, and dns_rbtnode::left_is_relative.

Referenced by serialize_nodes(), and treefix().

static dns_rbtnode_t* getright	(	dns_rbtnode_t *	node,
		file_header_t *	header
	)			`[inline, static]`

Definition at line 181 of file rbt.c.

References dns_rbtnode::right, and dns_rbtnode::right_is_relative.

Referenced by serialize_nodes(), and treefix().

static dns_rbtnode_t* getdown	(	dns_rbtnode_t *	node,
		file_header_t *	header
	)			`[inline, static]`

Definition at line 189 of file rbt.c.

References dns_rbtnode::down, and dns_rbtnode::down_is_relative.

Referenced by serialize_nodes(), and treefix().

static dns_rbtnode_t* getdata	(	dns_rbtnode_t *	node,
		file_header_t *	header
	)			`[inline, static]`

Definition at line 197 of file rbt.c.

References dns_rbtnode::data, and dns_rbtnode::data_is_relative.

Referenced by treefix().

static void NODENAME	(	dns_rbtnode_t *	node,
		dns_name_t *	name
	)			`[inline, static]`

The following macros directly access normally private name variables. These macros are used to avoid a lot of function calls in the critical path of the tree traversal code.

Definition at line 278 of file rbt.c.

References dns_name::attributes, ATTRS, DNS_NAMEATTR_READONLY, dns_name::labels, dns_name::length, NAME, NAMELEN, dns_name::ndata, OFFSETLEN, OFFSETS, and dns_name::offsets.

void dns_rbtnode_nodename	(	dns_rbtnode_t *	node,
		dns_name_t *	name
	)

Definition at line 288 of file rbt.c.

References dns_name::attributes, ATTRS, DNS_NAMEATTR_READONLY, dns_name::labels, dns_name::length, NAME, NAMELEN, dns_name::ndata, OFFSETLEN, OFFSETS, and dns_name::offsets.

Referenced by checkandaddsoa().

dns_rbtnode_t* dns_rbt_root ( dns_rbt_t * rbt )

Definition at line 298 of file rbt.c.

References dns_rbt::root.

static dns_rbtnode_t* get_subtree_root ( dns_rbtnode_t * node ) [inline, static]

Definition at line 349 of file rbt.c.

References IS_ROOT, and PARENT.

Referenced by get_upper_node().

static dns_rbtnode_t* get_upper_node ( dns_rbtnode_t * node ) [inline, static]

Definition at line 361 of file rbt.c.

References get_subtree_root(), PARENT, and root.

Referenced by dns_rbt_deletenode(), dns_rbt_findnode(), and dns_rbt_fullnamefromnode().

size_t dns__rbtnode_getdistance ( dns_rbtnode_t * node )

Return the distance (in nodes) from the node to its upper node of its subtree. The root node has a distance of 1. A child of the root node has a distance of 2.

Definition at line 373 of file rbt.c.

References IS_ROOT, and PARENT.

Referenced by ATF_TC_BODY().

static isc_result_t create_node	(	isc_mem_t *	mctx,
		dns_name_t *	name,
		dns_rbtnode_t **	nodep
	)			`[static]`

static void rotate_left	(	dns_rbtnode_t *	node,
		dns_rbtnode_t **	rootp
	)			`[inline, static]`

Definition at line 2341 of file rbt.c.

References DNS_RBTNODE_VALID, INSIST, dns_rbtnode::is_root, IS_ROOT, LEFT, PARENT, REQUIRE, and RIGHT.

Referenced by addonlevel(), and deletefromlevel().

static void rotate_right	(	dns_rbtnode_t *	node,
		dns_rbtnode_t **	rootp
	)			`[inline, static]`

Definition at line 2374 of file rbt.c.

References DNS_RBTNODE_VALID, INSIST, dns_rbtnode::is_root, IS_ROOT, LEFT, PARENT, REQUIRE, and RIGHT.

Referenced by addonlevel(), and deletefromlevel().

static void addonlevel	(	dns_rbtnode_t *	node,
		dns_rbtnode_t *	current,
		int	order,
		dns_rbtnode_t **	rootp
	)			`[static]`

Definition at line 2411 of file rbt.c.

References add_name(), dns_name_init(), DNS_RBTNODE_VALID, ENSURE, INSIST, IS_RED, IS_ROOT, dns_rbtnode::is_root, LEFT, MAKE_BLACK, MAKE_RED, NODENAME, PARENT, POST, REQUIRE, RIGHT, root, rotate_left(), and rotate_right().

Referenced by dns_rbt_addnode().

static void deletefromlevel	(	dns_rbtnode_t *	delete,
		dns_rbtnode_t **	rootp
	)			`[static]`

Definition at line 2518 of file rbt.c.

References COLOR, INSIST, IS_BLACK, IS_RED, dns_rbtnode::is_root, IS_ROOT, ISC_FALSE, ISC_TRUE, LEFT, MAKE_BLACK, MAKE_RED, PARENT, REQUIRE, RIGHT, rotate_left(), and rotate_right().

Referenced by dns_rbt_deletenode().

static isc_result_t treefix	(	dns_rbt_t *	rbt,
		void *	base,
		size_t	size,
		dns_rbtnode_t *	n,
		dns_name_t *	name,
		dns_rbtdatafixer_t	datafixer,
		void *	fixer_arg,
		isc_uint64_t *	crc
	)			`[static]`

static isc_result_t deletetree	(	dns_rbt_t *	rbt,
		dns_rbtnode_t *	node
	)			`[static]`

Definition at line 2767 of file rbt.c.

References DATA, dns_rbt::data_deleter, dns_rbt::deleter_arg, DOWN, freenode(), ISC_R_SUCCESS, LEFT, dns_rbtnode::magic, REQUIRE, RIGHT, unhash_node, and VALID_RBT.

Referenced by dns_rbt_deletenode().

static void deletetreeflat	(	dns_rbt_t *	rbt,
		unsigned int	quantum,
		dns_rbtnode_t **	nodep
	)			`[static]`

Definition at line 2822 of file rbt.c.

References DATA, dns_rbt::data_deleter, dns_rbt::deleter_arg, DOWN, freenode(), LEFT, dns_rbtnode::magic, PARENT, REQUIRE, RIGHT, and VALID_RBT.

Referenced by dns_rbt_destroy2().

static void printnodename	(	dns_rbtnode_t *	node,
		isc_boolean_t	quoted,
		FILE *	f
	)			`[static]`

Definition at line 3008 of file rbt.c.

References isc_region::base, buffer, dns_name_format(), DNS_NAME_FORMATSIZE, dns_name_fromregion(), dns_name_init(), isc_region::length, NAME, and NAMELEN.

Referenced by dns_rbt_printnodeinfo(), print_dot_helper(), and print_text_helper().

static void freenode	(	dns_rbt_t *	rbt,
		dns_rbtnode_t **	nodep
	)			`[static]`

Definition at line 2810 of file rbt.c.

References dns_rbtnode::is_mmapped, isc_mem_put, dns_rbt::mctx, NODE_SIZE, and dns_rbt::nodecount.

Referenced by deletetree(), deletetreeflat(), dns_db_createsoatuple(), dns_db_getsoaserial(), and dns_rbt_deletenode().

off_t dns_rbt_serialize_align ( off_t target )

Align the provided integer to a pointer-size boundary. This should be used if, during serialization of data to a will-be mmap()ed file, a pointer alignment is needed for some data.

Definition at line 653 of file rbt.c.

Referenced by ATF_TC_BODY(), dns_rbt_serialize_tree(), rbt_datafixer(), rbt_datawriter(), serialize_node(), serialize_nodes(), and write_header().

isc_result_t dns_rbt_serialize_tree	(	FILE *	file,
		dns_rbt_t *	rbt,
		dns_rbtdatawriter_t	datawriter,
		void *	writer_arg,
		off_t *	offset
	)

Write out the RBT structure and its data to a file.

Notes:

The file must be an actual file which allows seek() calls, so it cannot be a stream. Returns ISC_R_INVALIDFILE if not.

Definition at line 663 of file rbt.c.

References CHECK, cleanup(), dns_rbt_serialize_align(), dns_rbt_zero_header(), HEADER_LENGTH, isc_crc64_final(), isc_crc64_init(), isc_file_isplainfilefd(), ISC_R_SUCCESS, isc_stdio_seek(), isc_stdio_tell(), REQUIRE, dns_rbt::root, serialize_nodes(), and write_header().

Referenced by ATF_TC_BODY(), and serialize().

isc_result_t dns_rbt_deserialize_tree	(	void *	base_address,
		size_t	filesize,
		off_t	header_offset,
		isc_mem_t *	mctx,
		dns_rbtdeleter_t	deleter,
		void *	deleter_arg,
		dns_rbtdatafixer_t	datafixer,
		void *	fixer_arg,
		dns_rbtnode_t **	originp,
		dns_rbt_t **	rbtp
	)

Read a RBT structure and its data from a file.

If 'originp' is not NULL, then it is pointed to the root node of the RBT.

Notes:

The file must be an actual file which allows seek() calls, so it cannot be a stream. This condition is not checked in the code.

Definition at line 832 of file rbt.c.

References file_header::bigendian, CHECK, cleanup(), file_header::crc, dns_rbt_create(), dns_rbt_destroy(), dns_rootname, file_header::first_node_offset, header, isc_crc64_final(), isc_crc64_init(), ISC_R_INVALIDFILE, ISC_R_SUCCESS, dns_rbt::mmap_location, dns_rbt::nodecount, file_header::nodecount, file_header::ptrsize, file_header::rdataset_fixed, rehash, REQUIRE, dns_rbt::root, and treefix().

Referenced by ATF_TC_BODY(), and deserialize32().

isc_result_t dns_rbt_create	(	isc_mem_t *	mctx,
		dns_rbtdeleter_t	deleter,
		void *	deleter_arg,
		dns_rbt_t **	rbtp
	)

Initialize a red-black tree of trees.

Notes:

The deleter argument, if non-null, points to a function that is responsible for cleaning up any memory associated with the data pointer of a node when the node is deleted. It is passed the deleted node's data pointer as its first argument and deleter_arg as its second argument.

Requires:

mctx is a pointer to a valid memory context.
rbtp != NULL && *rbtp == NULL
arg == NULL iff deleter == NULL

Ensures:

If result is ISC_R_SUCCESS: *rbtp points to a valid red-black tree manager

If result is failure: *rbtp does not point to a valid red-black tree manager.

Returns:

ISC_R_SUCCESS Success
ISC_R_NOMEMORY Resource limit: Out of Memory

Definition at line 921 of file rbt.c.

References dns_rbt::data_deleter, dns_rbt::deleter_arg, dns_rbt::hashsize, dns_rbt::hashtable, isc_mem_attach(), isc_mem_get, isc_mem_putanddetach, ISC_R_NOMEMORY, ISC_R_SUCCESS, dns_rbt::magic, dns_rbt::mctx, dns_rbt::mmap_location, dns_rbt::nodecount, RBT_MAGIC, REQUIRE, and dns_rbt::root.

Referenced by ATF_TC_BODY(), configure_view_nametable(), dns_dbtable_create(), dns_fwdtable_create(), dns_keytable_create(), dns_ntatable_create(), dns_rbt_deserialize_tree(), dns_rbtdb_create(), dns_resolver_disable_algorithm(), dns_resolver_disable_ds_digest(), dns_resolver_setmustbesecure(), dns_rpz_new_zones(), dns_tsigkeyring_create(), dns_zt_create(), and test_context_setup().

void dns_rbt_destroy ( dns_rbt_t ** rbtp )

isc_result_t dns_rbt_destroy2	(	dns_rbt_t **	rbtp,
		unsigned int	quantum
	)

Stop working with a red-black tree of trees. If 'quantum' is zero then the entire tree will be destroyed. If 'quantum' is non zero then up to 'quantum' nodes will be destroyed allowing the rbt to be incrementally destroyed by repeated calls to dns_rbt_destroy2(). Once dns_rbt_destroy2() has been called no other operations than dns_rbt_destroy()/dns_rbt_destroy2() should be performed on the tree of trees.

Requires:

*rbt is a valid rbt manager.

Ensures on ISC_R_SUCCESS:

All space allocated by the RBT library has been returned.

*rbt is invalidated as an rbt manager.

Returns:

ISC_R_SUCCESS
ISC_R_QUOTA if 'quantum' nodes have been destroyed.

Definition at line 971 of file rbt.c.

References deletetreeflat(), dns_rbt::hashsize, dns_rbt::hashtable, INSIST, isc_mem_put, isc_mem_putanddetach, ISC_R_QUOTA, ISC_R_SUCCESS, dns_rbt::magic, dns_rbt::mctx, dns_rbt::mmap_location, dns_rbt::nodecount, REQUIRE, dns_rbt::root, and VALID_RBT.

Referenced by dns_rbt_destroy(), and free_rbtdb().

unsigned int dns_rbt_nodecount ( dns_rbt_t * rbt )

Obtain the number of nodes in the tree of trees.

Requires:

rbt is a valid rbt manager.

Definition at line 998 of file rbt.c.

References dns_rbt::nodecount, REQUIRE, and VALID_RBT.

Referenced by ATF_TC_BODY(), check_tree(), flush_deletions(), and nodecount().

unsigned int dns_rbt_hashsize ( dns_rbt_t * rbt )

Obtain the current number of buckets in the 'rbt' hash table.

Requires:

rbt is a valid rbt manager.

Definition at line 1006 of file rbt.c.

References dns_rbt::hashsize, REQUIRE, and VALID_RBT.

Referenced by hashsize().

static isc_result_t chain_name	(	dns_rbtnodechain_t *	chain,
		dns_name_t *	name,
		isc_boolean_t	include_chain_end
	)			`[inline, static]`

Definition at line 1014 of file rbt.c.

References dns_name_concatenate(), dns_name_copy(), dns_name_init(), dns_name_reset(), dns_rbtnodechain::end, ISC_R_SUCCESS, dns_rbtnodechain::level_count, dns_rbtnodechain::levels, and NODENAME.

Referenced by dns_rbt_findnode(), dns_rbtnodechain_current(), dns_rbtnodechain_down(), and dns_rbtnodechain_next().

static isc_result_t move_chain_to_last	(	dns_rbtnodechain_t *	chain,
		dns_rbtnode_t *	node
	)			`[inline, static]`

Definition at line 1042 of file rbt.c.

References ADD_LEVEL, DOWN, dns_rbtnodechain::end, ISC_R_SUCCESS, and RIGHT.

Referenced by dns_rbt_findnode(), and dns_rbtnodechain_last().

isc_result_t dns_rbt_addnode	(	dns_rbt_t *	rbt,
		dns_name_t *	name,
		dns_rbtnode_t **	nodep
	)

Just like dns_rbt_addname, but returns the address of the node.

Requires:

rbt is a valid rbt structure.
dns_name_isabsolute(name) == TRUE
nodep != NULL && *nodep == NULL

Ensures:

'name' is not altered in any way.

Any external references to nodes in the tree are unaffected by node splits that are necessary to insert the new name.

If result is ISC_R_SUCCESS: 'name' is findable in the red/black tree of trees in O(log N). *nodep is the node that was added for 'name'.

If result is ISC_R_EXISTS: The tree of trees is unaltered. *nodep is the existing node for 'name'.

If result is ISC_R_NOMEMORY: No guarantees.

Returns:

ISC_R_SUCCESS Success
ISC_R_EXISTS The name already exists, possibly without data.
ISC_R_NOMEMORY Resource Limit: Out of Memory

Definition at line 1068 of file rbt.c.

References ADD_LEVEL, add_name(), addonlevel(), ATTRS, COLOR, create_node(), dns_fixedname_init, dns_fixedname_name, dns_name_clone(), dns_name_countlabels(), dns_name_fullcompare(), dns_name_getlabelsequence(), dns_name_init(), dns_name_isabsolute(), dns_name_split(), DNS_NAMEATTR_ABSOLUTE, dns_namereln_commonancestor, dns_namereln_contains, dns_namereln_equal, dns_namereln_none, dns_namereln_subdomain, DNS_RBT_NSEC_HAS_NSEC, DNS_RBT_NSEC_NORMAL, dns_rbtnodechain_init(), DOWN, hash_node, INSIST, IS_ROOT, dns_rbtnode::is_root, ISC_R_EXISTS, ISC_R_NOSPACE, ISC_R_SUCCESS, dns_name::labels, LEFT, dns_name::length, dns_rbtnodechain::level_count, dns_rbtnodechain::levels, MAKE_BLACK, dns_rbt::mctx, NAMELEN, dns_rbt::nodecount, NODENAME, dns_rbtnode::nsec, OFFSETLEN, PARENT, REQUIRE, RIGHT, dns_rbt::root, root, and VALID_RBT.

Referenced by add_empty_wildcards(), add_nm(), add_wildcard_magic(), addrdataset(), dns_ntatable_add(), dns_rbt_addname(), dns_rbtdb_create(), dns_resolver_disable_algorithm(), dns_resolver_disable_ds_digest(), findnodeintree(), insert(), insert_helper(), loading_addrdataset(), and loadnode().

isc_result_t dns_rbt_addname	(	dns_rbt_t *	rbt,
		dns_name_t *	name,
		void *	data
	)

Add 'name' to the tree of trees, associated with 'data'.

Notes:

'data' is never required to be non-NULL, but specifying it when the name is added is faster than searching for 'name' again and then setting the data pointer. The lack of a data pointer for a node also has other ramifications regarding whether dns_rbt_findname considers a node to exist, or dns_rbt_deletename joins nodes.

Requires:

rbt is a valid rbt manager.
dns_name_isabsolute(name) == TRUE

Ensures:

'name' is not altered in any way.

Any external references to nodes in the tree are unaffected by node splits that are necessary to insert the new name.

If result is ISC_R_SUCCESS: 'name' is findable in the red/black tree of trees in O(log N). The data pointer of the node for 'name' is set to 'data'.

If result is ISC_R_EXISTS or ISC_R_NOSPACE: The tree of trees is unaltered.

If result is ISC_R_NOMEMORY: No guarantees.

Returns:

ISC_R_SUCCESS Success
ISC_R_EXISTS The name already exists with associated data.
ISC_R_NOSPACE The name had more logical labels than are allowed.
ISC_R_NOMEMORY Resource Limit: Out of Memory

Definition at line 1349 of file rbt.c.

References DATA, dns_name_isabsolute(), dns_rbt_addnode(), ISC_R_EXISTS, ISC_R_SUCCESS, REQUIRE, and VALID_RBT.

Referenced by add_test_data(), ATF_TC_BODY(), configure_view_nametable(), dns_dbtable_add(), dns_fwdtable_add(), dns_fwdtable_addfwd(), dns_resolver_setmustbesecure(), dns_zt_mount(), insert_nodes(), keyring_add(), and test_context_setup().

isc_result_t dns_rbt_findnode	(	dns_rbt_t *	rbt,
		dns_name_t *	name,
		dns_name_t *	foundname,
		dns_rbtnode_t **	node,
		dns_rbtnodechain_t *	chain,
		unsigned int	options,
		dns_rbtfindcallback_t	callback,
		void *	callback_arg
	)

Find the node for 'name'.

Notes:

A node that has no data is considered not to exist for this function, unless the DNS_RBTFIND_EMPTYDATA option is set. This applies to both exact matches and partial matches.

If the chain parameter is non-NULL, then the path through the tree to the DNSSEC predecessor of the searched for name is maintained, unless the DNS_RBTFIND_NOPREDECESSOR or DNS_RBTFIND_NOEXACT option is used. (For more details on those options, see below.)

If there is no predecessor, then the chain will point to nowhere, as indicated by chain->end being NULL or dns_rbtnodechain_current returning ISC_R_NOTFOUND. Note that in a normal Internet DNS RBT there will always be a predecessor for all names except the root name, because '.' will exist and '.' is the predecessor of everything. But you can certainly construct a trivial tree and a search for it that has no predecessor.

Within the chain structure, the 'levels' member of the structure holds the root node of each level except the first.

The 'level_count' of the chain indicates how deep the chain to the predecessor name is, as an index into the 'levels[]' array. It does not count name elements, per se, but only levels of the tree of trees, the distinction arising because multiple labels from a name can be stored on only one level. It is also does not include the level that has the node, since that level is not stored in levels[].

The chain's 'level_matches' is not directly related to the predecessor. It is the number of levels above the level of the found 'node', regardless of whether it was a partial match or exact match. When the node is found in the top level tree, or no node is found at all, level_matches is 0.

When DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is returned (also subject to DNS_RBTFIND_EMPTYDATA), even when there is an exact match in the tree. In this case, the chain will not point to the DNSSEC predecessor, but will instead point to the exact match, if there was any. Thus the preceding paragraphs should have "exact match" substituted for "predecessor" to describe how the various elements of the chain are set. This was done to ensure that the chain's state was sane, and to prevent problems that occurred when running the predecessor location code under conditions it was not designed for. It is not clear *where* the chain should point when DNS_RBTFIND_NOEXACT is set, so if you end up using a chain with this option because you want a particular node, let us know where you want the chain pointed, so this can be made more firm.

Requires:

rbt is a valid rbt manager.
dns_name_isabsolute(name) == TRUE.
node != NULL && *node == NULL.
DNS_RBTFIND_NOEXACT and DNS_RBTFIND_NOPREDECESSOR are mutually exclusive.

Ensures:

'name' and the tree are not altered in any way.

If result is ISC_R_SUCCESS:

 *              *node is the terminal node for 'name'.

 *              'foundname' and 'name' represent the same name (though not
 *              the same memory).

 *              'chain' points to the DNSSEC predecessor, if any, of 'name'.
 *
 *              chain->level_matches and chain->level_count are equal.
 *

If result is DNS_R_PARTIALMATCH:

 *              *node is the data associated with the deepest superdomain
 *              of 'name' which has data.
 *
 *              'foundname' is the name of deepest superdomain (which has
 *              data, unless the DNS_RBTFIND_EMPTYDATA option is set).
 *
 *              'chain' points to the DNSSEC predecessor, if any, of 'name'.
 *

If result is ISC_R_NOTFOUND:

 *              Neither the name nor a superdomain was found.  *node is NULL.
 *
 *              'chain' points to the DNSSEC predecessor, if any, of 'name'.
 *
 *              chain->level_matches is 0.
 *

Returns:

ISC_R_SUCCESS Success
DNS_R_PARTIALMATCH Superdomain found with data
ISC_R_NOTFOUND No match, or superdomain with no data
ISC_R_NOSPACE Concatenating nodes to form foundname failed

Definition at line 1379 of file rbt.c.

References ADD_LEVEL, chain_name(), DATA, dns_fixedname_init, dns_fixedname_name, dns_name_clone(), dns_name_countlabels(), dns_name_equal(), dns_name_fullcompare(), dns_name_fullhash(), dns_name_getlabelsequence(), dns_name_init(), dns_name_isabsolute(), dns_name_split(), dns_namereln_commonancestor, dns_namereln_contains, dns_namereln_equal, dns_namereln_none, dns_namereln_subdomain, DNS_R_CONTINUE, DNS_R_NEWORIGIN, DNS_R_PARTIALMATCH, DNS_RBTFIND_EMPTYDATA, DNS_RBTFIND_NOEXACT, DNS_RBTFIND_NOPREDECESSOR, DNS_RBTNODE_VALID, dns_rbtnodechain_init(), dns_rbtnodechain_prev(), dns_rbtnodechain_reset(), DOWN, dns_rbtnodechain::end, ENSURE, FINDCALLBACK, get_upper_node(), hash, dns_rbtnode::hashnext, dns_rbt::hashsize, dns_rbt::hashtable, HASHVAL, INSIST, ISC_FALSE, ISC_R_NOMORE, ISC_R_NOTFOUND, ISC_R_SUCCESS, ISC_TRUE, LEFT, dns_rbtnodechain::level_count, dns_rbtnodechain::level_matches, dns_rbtnodechain::levels, dns_rbt::mctx, move_chain_to_last(), NODENAME, PARENT, POST, REQUIRE, RIGHT, dns_rbt::root, and VALID_RBT.

Referenced by ATF_TC_BODY(), cache_find(), cache_findzonecut(), dbiterator_seek(), del_name(), delete(), delete_node(), dns_keytable_delete(), dns_keytable_deletekeynode(), dns_keytable_find(), dns_keytable_issecuredomain(), dns_ntatable_covered(), dns_rbt_deletename(), dns_rbt_findname(), dns_rpz_find_name(), find_wildcard(), findnodeintree(), is_answeraddress_allowed(), is_answertarget_allowed(), previous_closest_nsec(), and zone_find().

isc_result_t dns_rbt_findname	(	dns_rbt_t *	rbt,
		dns_name_t *	name,
		unsigned int	options,
		dns_name_t *	foundname,
		void **	data
	)

Get the data pointer associated with 'name'.

Notes:

When DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is returned (also subject to DNS_RBTFIND_EMPTYDATA), even when there is an exact match in the tree.

A node that has no data is considered not to exist for this function, unless the DNS_RBTFIND_EMPTYDATA option is set.

Requires:

rbt is a valid rbt manager.
dns_name_isabsolute(name) == TRUE
data != NULL && *data == NULL

Ensures:

'name' and the tree are not altered in any way.

If result is ISC_R_SUCCESS: *data is the data associated with 'name'.

If result is DNS_R_PARTIALMATCH: *data is the data associated with the deepest superdomain of 'name' which has data.

If result is ISC_R_NOTFOUND: Neither the name nor a superdomain was found with data.

Returns:

ISC_R_SUCCESS Success
DNS_R_PARTIALMATCH Superdomain found with data
ISC_R_NOTFOUND No match
ISC_R_NOSPACE Concatenating nodes to form foundname failed

Definition at line 1916 of file rbt.c.

References DATA, dns_rbt_findnode(), DNS_RBTFIND_EMPTYDATA, ISC_R_NOTFOUND, and REQUIRE.

Referenced by check_test_data(), dns_dbtable_find(), dns_dbtable_remove(), dns_fwdtable_find2(), dns_keytable_finddeepestmatch(), dns_keytable_findkeynode(), dns_resolver_algorithm_supported(), dns_resolver_ds_digest_supported(), dns_resolver_getmustbesecure(), dns_tsigkey_find(), and dns_zt_find().

isc_result_t dns_rbt_deletename	(	dns_rbt_t *	rbt,
		dns_name_t *	name,
		isc_boolean_t	recurse
	)

Delete 'name' from the tree of trees.

Notes:

When 'name' is removed, if recurse is ISC_TRUE then all of its subnames are removed too.

Requires:

rbt is a valid rbt manager.
dns_name_isabsolute(name) == TRUE

Ensures:

'name' is not altered in any way.

Does NOT ensure that any external references to nodes in the tree are unaffected by node joins.

If result is ISC_R_SUCCESS: 'name' does not appear in the tree with data; however, the node for the name might still exist which can be found with dns_rbt_findnode (but not dns_rbt_findname).

If result is ISC_R_NOTFOUND: 'name' does not appear in the tree with data, because it did not appear in the tree before the function was called.

If result is something else: See result codes for dns_rbt_findnode (if it fails, the node is not deleted) or dns_rbt_deletenode (if it fails, the node is deleted, but the tree is not optimized when it could have been).

Returns:

ISC_R_SUCCESS Success
ISC_R_NOTFOUND No match
something_else Any return code from dns_rbt_findnode except DNS_R_PARTIALMATCH (which causes ISC_R_NOTFOUND to be returned instead), and any code from dns_rbt_deletenode.

Definition at line 1939 of file rbt.c.

References DATA, dns_name_isabsolute(), DNS_R_PARTIALMATCH, dns_rbt_deletenode(), dns_rbt_findnode(), DNS_RBTFIND_NOOPTIONS, ISC_R_NOTFOUND, ISC_R_SUCCESS, REQUIRE, and VALID_RBT.

Referenced by ATF_TC_BODY(), delete_keynames(), dns_dbtable_remove(), dns_fwdtable_delete(), dns_zt_unmount(), remove_fromring(), and remove_nodes().

isc_result_t dns_rbt_deletenode	(	dns_rbt_t *	rbt,
		dns_rbtnode_t *	node,
		isc_boolean_t	recurse
	)

Delete 'node' from the tree of trees.

Notes:

When 'node' is removed, if recurse is ISC_TRUE then all nodes in levels down from it are removed too.

Requires:

rbt is a valid rbt manager.
node != NULL.

Ensures:

Does NOT ensure that any external references to nodes in the tree are unaffected by node joins.

If result is ISC_R_SUCCESS: 'node' does not appear in the tree with data; however, the node might still exist if it serves as a pointer to a lower tree level as long as 'recurse' was false, hence the node could can be found with dns_rbt_findnode when that function's empty_data_ok parameter is true.

If result is ISC_R_NOMEMORY or ISC_R_NOSPACE: The node was deleted, but the tree structure was not optimized.

Returns:

ISC_R_SUCCESS Success
ISC_R_NOMEMORY Resource Limit: Out of Memory when joining nodes.
ISC_R_NOSPACE dns_name_concatenate failed when joining nodes.

Definition at line 2012 of file rbt.c.

References DATA, dns_rbt::data_deleter, deletefromlevel(), dns_rbt::deleter_arg, deletetree(), dns_rbtnode_refdestroy, DNS_RBTNODE_VALID, DOWN, freenode(), get_upper_node(), INSIST, ISC_R_SUCCESS, dns_rbtnode::magic, dns_rbt::nodecount, REQUIRE, dns_rbt::root, RUNTIME_CHECK, unhash_node, and VALID_RBT.

Referenced by ATF_TC_BODY(), del_name(), delete(), delete_node(), dns_keytable_delete(), dns_keytable_deletekeynode(), dns_rbt_deletename(), and loadnode().

void dns_rbt_namefromnode	(	dns_rbtnode_t *	node,
		dns_name_t *	name
	)

Convert the sequence of labels stored at 'node' into a 'name'.

Notes:

This function does not return the full name, from the root, but just the labels at the indicated node.

The name data pointed to by 'name' is the information stored in the node, not a copy. Altering the data at this pointer will likely cause grief.

Requires:

name->offsets == NULL

Ensures:

'name' is DNS_NAMEATTR_READONLY.

'name' will point directly to the labels stored after the dns_rbtnode_t struct.

'name' will have offsets that also point to the information stored as part of the node.

Definition at line 2096 of file rbt.c.

References DNS_RBTNODE_VALID, NODENAME, dns_name::offsets, and REQUIRE.

Referenced by compare_labelsequences(), dns_rbtdb_create(), find_deepest_zonecut(), find_wildcard(), findnodeintree(), and loading_addrdataset().

isc_result_t dns_rbt_fullnamefromnode	(	dns_rbtnode_t *	node,
		dns_name_t *	name
	)

Like dns_rbt_namefromnode, but returns the full name from the root.

Notes:

Unlike dns_rbt_namefromnode, the name will not point directly to node data. Rather, dns_name_concatenate will be used to copy the name data from each node into the 'name' argument.

Requires:

name != NULL
name has a dedicated buffer.

Returns:

ISC_R_SUCCESS
ISC_R_NOSPACE (possible via dns_name_concatenate)
DNS_R_NAMETOOLONG (possible via dns_name_concatenate)

Definition at line 2106 of file rbt.c.

References dns_name::buffer, dns_name_concatenate(), dns_name_init(), dns_name_isabsolute(), dns_name_reset(), DNS_RBTNODE_VALID, get_upper_node(), INSIST, ISC_R_SUCCESS, NODENAME, and REQUIRE.

Referenced by addrdataset(), delete_node(), dns_ntatable_save(), dns_ntatable_totext(), dns_rbt_formatnodename(), findnodeintree(), and getsigningtime().

char* dns_rbt_formatnodename	(	dns_rbtnode_t *	node,
		char *	printname,
		unsigned int	size
	)

Format the full name of a node for printing, using dns_name_format().

Notes:

'size' is the length of the printname buffer. This should be DNS_NAME_FORMATSIZE or larger.

Requires:

node and printname are not NULL.

Returns:

The 'printname' pointer.

Definition at line 2133 of file rbt.c.

References dns_fixedname_init, dns_fixedname_name, dns_name_format(), dns_rbt_fullnamefromnode(), DNS_RBTNODE_VALID, dns_result_totext(), ISC_R_SUCCESS, and REQUIRE.

Referenced by decrement_reference(), and expirenode().

static size_t getheight_helper ( dns_rbtnode_t * node ) [static]

Definition at line 2876 of file rbt.c.

References DOWN, ISC_MAX, LEFT, and RIGHT.

Referenced by dns__rbt_getheight().

size_t dns__rbt_getheight ( dns_rbt_t * rbt )

Return the maximum height of sub-root nodes found in the red-black forest.

The height of a node is defined as the number of nodes in the longest path from the node to a leaf. For each subtree in the forest, this function determines the height of its root node. Then it returns the maximum such height in the forest.

Note: This function exists for testing purposes. Non-test code must not use it.

Requires:

rbt is a valid rbt manager.

Definition at line 2893 of file rbt.c.

References getheight_helper(), and dns_rbt::root.

Referenced by ATF_TC_BODY(), and check_tree().

static isc_boolean_t check_properties_helper ( dns_rbtnode_t * node ) [static]

Definition at line 2898 of file rbt.c.

References DOWN, IS_RED, IS_ROOT, ISC_FALSE, ISC_TRUE, LEFT, PARENT, and RIGHT.

Referenced by dns__rbt_checkproperties().

static isc_boolean_t check_black_distance_helper	(	dns_rbtnode_t *	node,
		size_t *	distance
	)			`[static]`

Definition at line 2929 of file rbt.c.

References DOWN, IS_BLACK, ISC_FALSE, ISC_TRUE, LEFT, and RIGHT.

Referenced by dns__rbt_checkproperties().

isc_boolean_t dns__rbt_checkproperties ( dns_rbt_t * rbt )

Check red-black properties of the forest.

Note: This function exists for testing purposes. Non-test code must not use it.

Requires:

rbt is a valid rbt manager.

Definition at line 2959 of file rbt.c.

References check_black_distance_helper(), check_properties_helper(), ISC_FALSE, and dns_rbt::root.

Referenced by ATF_TC_BODY(), and check_tree().

static void dns_rbt_indent	(	FILE *	f,
		int	depth
	)			`[static]`

Definition at line 2974 of file rbt.c.

Referenced by print_text_helper().

void dns_rbt_printnodeinfo	(	dns_rbtnode_t *	n,
		FILE *	f
	)

Print out various information about a node.

Requires:

'n' is a valid pointer.

'f' points to a valid open FILE structure that allows writing.

Definition at line 2984 of file rbt.c.

References dns_rbtnode::data, dns_rbtnode::data_is_relative, dns_rbtnode::down, dns_rbtnode::down_is_relative, ISC_TRUE, dns_rbtnode::left, dns_rbtnode::left_is_relative, dns_rbtnode::locknum, dns_rbtnode::parent, dns_rbtnode::parent_is_relative, printnodename(), dns_rbtnode::right, and dns_rbtnode::right_is_relative.

static void print_text_helper	(	dns_rbtnode_t *	root,
		dns_rbtnode_t *	parent,
		int	depth,
		const char *	direction,
		void()(FILE , void *)	data_printer,
		FILE *	f
	)			`[static]`

Definition at line 3029 of file rbt.c.

References dns_rbtnode::data, data_printer(), dns_rbt_indent(), DOWN, IS_RED, IS_ROOT, ISC_TRUE, LEFT, PARENT, printnodename(), and RIGHT.

Referenced by dns_rbt_printtext().

void dns_rbt_printtext	(	dns_rbt_t *	rbt,
		void()(FILE , void *)	data_printer,
		FILE *	f
	)

Print an ASCII representation of the internal structure of the red-black tree of trees to the passed stream.

data_printer is a callback function that is called to print the data in a node. It should print it to the passed FILE stream.

Notes:

The name stored at each node, along with the node's color, is printed. Then the down pointer, left and right pointers are displayed recursively in turn. NULL down pointers are silently omitted; NULL left and right pointers are printed.

Definition at line 3080 of file rbt.c.

References data_printer(), print_text_helper(), REQUIRE, dns_rbt::root, and VALID_RBT.

Referenced by ATF_TC_BODY().

static int print_dot_helper	(	dns_rbtnode_t *	node,
		unsigned int *	nodecount,
		isc_boolean_t	show_pointers,
		FILE *	f
	)			`[static]`

Definition at line 3089 of file rbt.c.

References DOWN, IS_EMPTY, IS_RED, IS_ROOT, ISC_FALSE, LEFT, PARENT, printnodename(), and RIGHT.

Referenced by dns_rbt_printdot().

void dns_rbt_printdot	(	dns_rbt_t *	rbt,
		isc_boolean_t	show_pointers,
		FILE *	f
	)

Print a GraphViz dot representation of the internal structure of the red-black tree of trees to the passed stream.

If show_pointers is TRUE, pointers are also included in the generated graph.

Notes:

The name stored at each node, along with the node's color is displayed. Then the down pointer, left and right pointers are displayed recursively in turn. NULL left, right and down pointers are silently omitted.

Definition at line 3142 of file rbt.c.

References nodecount(), print_dot_helper(), REQUIRE, dns_rbt::root, and VALID_RBT.

void dns_rbtnodechain_init	(	dns_rbtnodechain_t *	chain,
		isc_mem_t *	mctx
	)

Initialize 'chain'.

Requires:

'chain' is a valid pointer.

'mctx' is a valid memory context.

Ensures:

'chain' is suitable for use.

Definition at line 3158 of file rbt.c.

References CHAIN_MAGIC, dns_rbtnodechain::end, dns_rbtnodechain::level_count, dns_rbtnodechain::level_matches, dns_rbtnodechain::levels, dns_rbtnodechain::magic, dns_rbtnodechain::mctx, and REQUIRE.

Referenced by ATF_TC_BODY(), cache_find(), cache_findzonecut(), cleanup_ring(), createiterator(), delete_keynames(), dns_keytable_totext(), dns_ntatable_save(), dns_ntatable_totext(), dns_rbt_addnode(), dns_rbt_findnode(), dns_rpz_ready(), dns_tsigkeyring_dumpanddetach(), dns_zt_apply2(), find_wildcard(), list_keynames(), previous_closest_nsec(), sync_keyzone(), and zone_find().

isc_result_t dns_rbtnodechain_current	(	dns_rbtnodechain_t *	chain,
		dns_name_t *	name,
		dns_name_t *	origin,
		dns_rbtnode_t **	node
	)

Provide the name, origin and node to which the chain is currently pointed.

Notes:

The tree need not have be locked against additions for the chain to remain valid, however there are no guarantees if any deletion has been made since the chain was established.

Requires:

'chain' is a valid chain.

Ensures:

'node', if non-NULL, is the node to which the chain was pointed by dns_rbt_findnode, dns_rbtnodechain_first or dns_rbtnodechain_last. If none were called for the chain since it was initialized or reset, or if the was no predecessor to the name searched for with dns_rbt_findnode, then '*node' is NULL and ISC_R_NOTFOUND is returned.

'name', if non-NULL, is the name stored at the terminal level of the chain. This is typically a single label, like the "www" of "www.isc.org", but need not be so. At the root of the tree of trees, if the node is "." then 'name' is ".", otherwise it is relative to ".". (Minimalist and atypical case: if the tree has just the name "isc.org." then the root node's stored name is "isc.org." but 'name' will be "isc.org".)

'origin', if non-NULL, is the sequence of labels in the levels above the terminal level, such as "isc.org." in the above example. 'origin' is always "." for the root node.

Returns:

ISC_R_SUCCESS name, origin & node were successfully set.
ISC_R_NOTFOUND The chain does not point to any node.
<something_else> Any error return from dns_name_concatenate.

Definition at line 3175 of file rbt.c.

References dns_name::attributes, chain_name(), dns_name_copy(), dns_name_isabsolute(), DNS_NAMEATTR_ABSOLUTE, dns_rootname, dns_rbtnodechain::end, INSIST, ISC_FALSE, ISC_R_NOTFOUND, ISC_R_SUCCESS, dns_name::labels, dns_name::length, dns_rbtnodechain::level_count, NODENAME, REQUIRE, and VALID_CHAIN.

Referenced by activeempty(), activeemtpynode(), ATF_TC_BODY(), cleanup_ring(), dbiterator_first(), dbiterator_last(), dbiterator_next(), dbiterator_prev(), dbiterator_seek(), delete_keynames(), dns_keytable_totext(), dns_ntatable_save(), dns_ntatable_totext(), dns_rbtnodechain_first(), dns_rbtnodechain_last(), dns_rbtnodechain_prev(), dns_rpz_ready(), dns_tsigkeyring_dumpanddetach(), dns_zt_apply2(), find_closest_nsec(), find_coveringnsec(), list_keynames(), previous_closest_nsec(), and sync_keyzone().

isc_result_t dns_rbtnodechain_prev	(	dns_rbtnodechain_t *	chain,
		dns_name_t *	name,
		dns_name_t *	origin
	)

Adjusts chain to point the DNSSEC predecessor of the name to which it is currently pointed.

Requires:

'chain' is a valid chain.
'chain' has been pointed somewhere in the tree with dns_rbt_findnode, dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that dns_rbt_findnode is not guaranteed to point the chain somewhere, since there may have been no predecessor to the searched for name.

Ensures:

The chain is pointed to the predecessor of its current target.

'name' and 'origin', if non-NULL, are set as described for dns_rbtnodechain_current.

'origin' is only if a new origin was found.

Returns:

ISC_R_SUCCESS The predecessor was found and 'name' was set.
DNS_R_NEWORIGIN The predecessor was found with a different origin and 'name' and 'origin' were set.
ISC_R_NOMORE There was no predecessor.
<something_else> Any error result from dns_rbtnodechain_current.

Definition at line 3218 of file rbt.c.

References ADD_LEVEL, DNS_R_NEWORIGIN, dns_rbtnodechain_current(), DOWN, dns_rbtnodechain::end, INSIST, IS_ROOT, ISC_FALSE, ISC_R_NOMORE, ISC_R_SUCCESS, ISC_TRUE, LEFT, dns_rbtnodechain::level_count, dns_rbtnodechain::levels, OFFSETLEN, PARENT, REQUIRE, RIGHT, and VALID_CHAIN.

Referenced by activeemtpynode(), dbiterator_prev(), dns_rbt_findnode(), find_coveringnsec(), and previous_closest_nsec().

isc_result_t dns_rbtnodechain_down	(	dns_rbtnodechain_t *	chain,
		dns_name_t *	name,
		dns_name_t *	origin
	)

Descend down if possible.

Definition at line 3335 of file rbt.c.

References ADD_LEVEL, chain_name(), DNS_R_NEWORIGIN, DOWN, dns_rbtnodechain::end, ISC_FALSE, ISC_R_NOMORE, ISC_R_SUCCESS, ISC_TRUE, LEFT, dns_rbtnodechain::level_count, NODENAME, OFFSETLEN, REQUIRE, and VALID_CHAIN.

isc_result_t dns_rbtnodechain_nextflat	(	dns_rbtnodechain_t *	chain,
		dns_name_t *	name
	)

Find the next node at the current depth in DNSSEC order.

Definition at line 3399 of file rbt.c.

References dns_rbtnodechain::end, IS_ROOT, ISC_R_NOMORE, ISC_R_SUCCESS, LEFT, NODENAME, PARENT, REQUIRE, RIGHT, and VALID_CHAIN.

isc_result_t dns_rbtnodechain_next	(	dns_rbtnodechain_t *	chain,
		dns_name_t *	name,
		dns_name_t *	origin
	)

Adjusts chain to point the DNSSEC successor of the name to which it is currently pointed.

Requires:

'chain' is a valid chain.
'chain' has been pointed somewhere in the tree with dns_rbt_findnode, dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that dns_rbt_findnode is not guaranteed to point the chain somewhere, since there may have been no predecessor to the searched for name.

Ensures:

The chain is pointed to the successor of its current target.

'name' and 'origin', if non-NULL, are set as described for dns_rbtnodechain_current.

'origin' is only if a new origin was found.

Returns:

ISC_R_SUCCESS The successor was found and 'name' was set.
DNS_R_NEWORIGIN The successor was found with a different origin and 'name' and 'origin' were set.
ISC_R_NOMORE There was no successor.
<something_else> Any error result from dns_name_concatenate.

Definition at line 3442 of file rbt.c.

References ADD_LEVEL, chain_name(), DNS_R_NEWORIGIN, DOWN, dns_rbtnodechain::end, IS_ROOT, ISC_FALSE, ISC_R_NOMORE, ISC_R_SUCCESS, ISC_TRUE, LEFT, dns_rbtnodechain::level_count, dns_rbtnodechain::levels, NODENAME, OFFSETLEN, PARENT, REQUIRE, RIGHT, and VALID_CHAIN.

Referenced by activeempty(), activeemtpynode(), ATF_TC_BODY(), cleanup_ring(), dbiterator_next(), delete_keynames(), dns_keytable_totext(), dns_ntatable_save(), dns_ntatable_totext(), dns_rpz_ready(), dns_tsigkeyring_dumpanddetach(), dns_zt_apply2(), list_keynames(), and sync_keyzone().

isc_result_t dns_rbtnodechain_first	(	dns_rbtnodechain_t *	chain,
		dns_rbt_t *	rbt,
		dns_name_t *	name,
		dns_name_t *	origin
	)

Set the chain to the lexically first node in the tree of trees.

Notes:

By the definition of ordering for DNS names, the root of the tree of trees is the very first node, since everything else in the megatree uses it as a common suffix.

Requires:

'chain' is a valid chain.
'rbt' is a valid rbt manager.

Ensures:

The chain points to the very first node of the tree.

'name' and 'origin', if non-NULL, are set as described for dns_rbtnodechain_current. Thus 'origin' will always be ".".

Returns:

DNS_R_NEWORIGIN The name & origin were successfully set.
<something_else> Any error result from dns_rbtnodechain_current.

Definition at line 3557 of file rbt.c.

References DNS_R_NEWORIGIN, dns_rbtnodechain_current(), dns_rbtnodechain_reset(), dns_rbtnodechain::end, ISC_R_SUCCESS, REQUIRE, dns_rbt::root, VALID_CHAIN, and VALID_RBT.

Referenced by cleanup_ring(), dbiterator_first(), dbiterator_next(), delete_keynames(), dns_keytable_totext(), dns_ntatable_save(), dns_ntatable_totext(), dns_rpz_ready(), dns_tsigkeyring_dumpanddetach(), dns_zt_apply2(), list_keynames(), and sync_keyzone().

isc_result_t dns_rbtnodechain_last	(	dns_rbtnodechain_t *	chain,
		dns_rbt_t *	rbt,
		dns_name_t *	name,
		dns_name_t *	origin
	)

Set the chain to the lexically last node in the tree of trees.

Requires:

'chain' is a valid chain.
'rbt' is a valid rbt manager.

Ensures:

The chain points to the very last node of the tree.

'name' and 'origin', if non-NULL, are set as described for dns_rbtnodechain_current.

Returns:

DNS_R_NEWORIGIN The name & origin were successfully set.
ISC_R_NOMEMORY Resource Limit: Out of Memory building chain.
<something_else> Any error result from dns_name_concatenate.

Definition at line 3579 of file rbt.c.

References DNS_R_NEWORIGIN, dns_rbtnodechain_current(), dns_rbtnodechain_reset(), ISC_R_SUCCESS, move_chain_to_last(), REQUIRE, dns_rbt::root, VALID_CHAIN, and VALID_RBT.

Referenced by dbiterator_last(), dbiterator_prev(), and find_closest_nsec().

void dns_rbtnodechain_reset ( dns_rbtnodechain_t * chain )

Free any dynamic storage associated with 'chain', and then reinitialize 'chain'.

Requires:

'chain' is a valid pointer.

Ensures:

'chain' is suitable for use, and uses no dynamic storage.

Definition at line 3604 of file rbt.c.

References dns_rbtnodechain::end, dns_rbtnodechain::level_count, dns_rbtnodechain::level_matches, REQUIRE, and VALID_CHAIN.

Referenced by cache_find(), cache_findzonecut(), dbiterator_destroy(), dbiterator_first(), dbiterator_last(), dbiterator_next(), dbiterator_prev(), dbiterator_seek(), dns_rbt_findnode(), dns_rbtnodechain_first(), dns_rbtnodechain_invalidate(), dns_rbtnodechain_last(), and zone_find().

void dns_rbtnodechain_invalidate ( dns_rbtnodechain_t * chain )

Free any dynamic storage associated with 'chain', and then invalidates it.

Notes:

Future calls to any dns_rbtnodechain_ function will need to call dns_rbtnodechain_init on the chain first (except, of course, dns_rbtnodechain_init itself).

Requires:

'chain' is a valid chain.

Ensures:

'chain' is no longer suitable for use, and uses no dynamic storage.

Definition at line 3618 of file rbt.c.

References dns_rbtnodechain_reset(), and dns_rbtnodechain::magic.

Referenced by ATF_TC_BODY(), cleanup_ring(), delete_keynames(), dns_keytable_totext(), dns_ntatable_save(), dns_ntatable_totext(), dns_tsigkeyring_dumpanddetach(), dns_zt_apply2(), find_closest_nsec(), and list_keynames().

Variable Documentation

char FILE_VERSION[32] = "\0" [static]

Definition at line 104 of file rbt.c.

Referenced by init_file_version(), rbtdb_write_header(), and write_header().

Generated on Tue Apr 28 17:41:12 2015 by Doxygen 1.5.4 for BIND9 Internals 9.11.0pre-alpha


Data Structures
struct	dns_rbt
struct	file_header
Defines
#define	DNS_NAME_USEINLINE 1
	This define is so dns/name.h (included by dns/fixedname.h) uses more efficient macro calls instead of functions for a few operations.
#define	CHECK(x)
#define	RBT_MAGIC ISC_MAGIC('R', 'B', 'T', '+')
#define	VALID_RBT(rbt) ISC_MAGIC_VALID(rbt, RBT_MAGIC)
#define	CHAIN_MAGIC ISC_MAGIC('0', '-', '0', '-')
#define	VALID_CHAIN(chain) ISC_MAGIC_VALID(chain, CHAIN_MAGIC)
#define	RBT_HASH_SIZE 64
#define	RED 0
#define	BLACK 1
#define	HEADER_LENGTH 1024
#define	PARENT(node) ((node)->parent)
	Elements of the rbtnode structure.
#define	LEFT(node) ((node)->left)
#define	RIGHT(node) ((node)->right)
#define	DOWN(node) ((node)->down)
#define	DATA(node) ((node)->data)
#define	IS_EMPTY(node) ((node)->data == NULL)
#define	HASHNEXT(node) ((node)->hashnext)
#define	HASHVAL(node) ((node)->hashval)
#define	COLOR(node) ((node)->color)
#define	NAMELEN(node) ((node)->namelen)
#define	OLDNAMELEN(node) ((node)->oldnamelen)
#define	OFFSETLEN(node) ((node)->offsetlen)
#define	ATTRS(node) ((node)->attributes)
#define	IS_ROOT(node) ISC_TF((node)->is_root == 1)
#define	FINDCALLBACK(node) ISC_TF((node)->find_callback == 1)
#define	DIRTY(node) ((node)->dirty)
	Structure elements from the rbtdb.c, not used as part of the rbt.c algorithms.
#define	WILD(node) ((node)->wild)
#define	LOCKNUM(node) ((node)->locknum)
#define	NAME(node) ((unsigned char *)((node) + 1))
	The variable length stuff stored after the node has the following structure.
#define	OFFSETS(node) (NAME(node) + OLDNAMELEN(node) + 1)
#define	OLDOFFSETLEN(node) (OFFSETS(node)[-1])
#define	NODE_SIZE(node)
#define	IS_RED(node) ((node) != NULL && (node)->color == RED)
	Color management.
#define	IS_BLACK(node) ((node) == NULL \|\| (node)->color == BLACK)
#define	MAKE_RED(node) ((node)->color = RED)
#define	MAKE_BLACK(node) ((node)->color = BLACK)
#define	ADD_LEVEL(chain, node)
	Chain management.
#define	hash_node(rbt, node, name)
#define	unhash_node(rbt, node)
#define	rehash(rbt, newcount)
#define	CONFIRM(a)
Typedefs
typedef struct file_header	file_header_t
Functions
static isc_result_t	dns_rbt_zero_header (FILE *file)
static isc_result_t	write_header (FILE file, dns_rbt_t rbt, isc_uint64_t first_node_offset, isc_uint64_t crc)
static isc_result_t	serialize_node (FILE file, dns_rbtnode_t node, uintptr_t left, uintptr_t right, uintptr_t down, uintptr_t parent, uintptr_t data, isc_uint64_t *crc)
static isc_result_t	serialize_nodes (FILE file, dns_rbtnode_t node, uintptr_t parent, dns_rbtdatawriter_t datawriter, void writer_arg, uintptr_t where, isc_uint64_t *crc)
static dns_rbtnode_t *	getparent (dns_rbtnode_t node, file_header_t header)
static dns_rbtnode_t *	getleft (dns_rbtnode_t node, file_header_t header)
static dns_rbtnode_t *	getright (dns_rbtnode_t node, file_header_t header)
static dns_rbtnode_t *	getdown (dns_rbtnode_t node, file_header_t header)
static dns_rbtnode_t *	getdata (dns_rbtnode_t node, file_header_t header)
static void	NODENAME (dns_rbtnode_t node, dns_name_t name)
	The following macros directly access normally private name variables. These macros are used to avoid a lot of function calls in the critical path of the tree traversal code.
void	dns_rbtnode_nodename (dns_rbtnode_t node, dns_name_t name)
dns_rbtnode_t *	dns_rbt_root (dns_rbt_t *rbt)
static dns_rbtnode_t *	get_subtree_root (dns_rbtnode_t *node)
static dns_rbtnode_t *	get_upper_node (dns_rbtnode_t *node)
size_t	dns__rbtnode_getdistance (dns_rbtnode_t *node)
	Return the distance (in nodes) from the node to its upper node of its subtree. The root node has a distance of 1. A child of the root node has a distance of 2.
static isc_result_t	create_node (isc_mem_t mctx, dns_name_t name, dns_rbtnode_t **nodep)
static void	rotate_left (dns_rbtnode_t node, dns_rbtnode_t *rootp)
static void	rotate_right (dns_rbtnode_t node, dns_rbtnode_t *rootp)
static void	addonlevel (dns_rbtnode_t node, dns_rbtnode_t current, int order, dns_rbtnode_t **rootp)
static void	deletefromlevel (dns_rbtnode_t delete, dns_rbtnode_t *rootp)
static isc_result_t	treefix (dns_rbt_t rbt, void base, size_t size, dns_rbtnode_t n, dns_name_t name, dns_rbtdatafixer_t datafixer, void fixer_arg, isc_uint64_t crc)
static isc_result_t	deletetree (dns_rbt_t rbt, dns_rbtnode_t node)
static void	deletetreeflat (dns_rbt_t rbt, unsigned int quantum, dns_rbtnode_t *nodep)
static void	printnodename (dns_rbtnode_t node, isc_boolean_t quoted, FILE f)
static void	freenode (dns_rbt_t rbt, dns_rbtnode_t *nodep)
off_t	dns_rbt_serialize_align (off_t target)
	Align the provided integer to a pointer-size boundary. This should be used if, during serialization of data to a will-be mmap()ed file, a pointer alignment is needed for some data.
isc_result_t	dns_rbt_serialize_tree (FILE file, dns_rbt_t rbt, dns_rbtdatawriter_t datawriter, void writer_arg, off_t offset)
	Write out the RBT structure and its data to a file.
isc_result_t	dns_rbt_deserialize_tree (void base_address, size_t filesize, off_t header_offset, isc_mem_t mctx, dns_rbtdeleter_t deleter, void deleter_arg, dns_rbtdatafixer_t datafixer, void fixer_arg, dns_rbtnode_t originp, dns_rbt_t rbtp)
	Read a RBT structure and its data from a file.
isc_result_t	dns_rbt_create (isc_mem_t mctx, dns_rbtdeleter_t deleter, void deleter_arg, dns_rbt_t **rbtp)
	Initialize a red-black tree of trees.
void	dns_rbt_destroy (dns_rbt_t **rbtp)
isc_result_t	dns_rbt_destroy2 (dns_rbt_t **rbtp, unsigned int quantum)
	Stop working with a red-black tree of trees. If 'quantum' is zero then the entire tree will be destroyed. If 'quantum' is non zero then up to 'quantum' nodes will be destroyed allowing the rbt to be incrementally destroyed by repeated calls to dns_rbt_destroy2(). Once dns_rbt_destroy2() has been called no other operations than dns_rbt_destroy()/dns_rbt_destroy2() should be performed on the tree of trees.
unsigned int	dns_rbt_nodecount (dns_rbt_t *rbt)
	Obtain the number of nodes in the tree of trees.
unsigned int	dns_rbt_hashsize (dns_rbt_t *rbt)
	Obtain the current number of buckets in the 'rbt' hash table.
static isc_result_t	chain_name (dns_rbtnodechain_t chain, dns_name_t name, isc_boolean_t include_chain_end)
static isc_result_t	move_chain_to_last (dns_rbtnodechain_t chain, dns_rbtnode_t node)
isc_result_t	dns_rbt_addnode (dns_rbt_t rbt, dns_name_t name, dns_rbtnode_t **nodep)
	Just like dns_rbt_addname, but returns the address of the node.
isc_result_t	dns_rbt_addname (dns_rbt_t rbt, dns_name_t name, void *data)
	Add 'name' to the tree of trees, associated with 'data'.
isc_result_t	dns_rbt_findnode (dns_rbt_t rbt, dns_name_t name, dns_name_t foundname, dns_rbtnode_t node, dns_rbtnodechain_t chain, unsigned int options, dns_rbtfindcallback_t callback, void *callback_arg)
	Find the node for 'name'.
isc_result_t	dns_rbt_findname (dns_rbt_t rbt, dns_name_t name, unsigned int options, dns_name_t foundname, void *data)
	Get the data pointer associated with 'name'.
isc_result_t	dns_rbt_deletename (dns_rbt_t rbt, dns_name_t name, isc_boolean_t recurse)
	Delete 'name' from the tree of trees.
isc_result_t	dns_rbt_deletenode (dns_rbt_t rbt, dns_rbtnode_t node, isc_boolean_t recurse)
	Delete 'node' from the tree of trees.
void	dns_rbt_namefromnode (dns_rbtnode_t node, dns_name_t name)
	Convert the sequence of labels stored at 'node' into a 'name'.
isc_result_t	dns_rbt_fullnamefromnode (dns_rbtnode_t node, dns_name_t name)
	Like dns_rbt_namefromnode, but returns the full name from the root.
char *	dns_rbt_formatnodename (dns_rbtnode_t node, char printname, unsigned int size)
	Format the full name of a node for printing, using dns_name_format().
static size_t	getheight_helper (dns_rbtnode_t *node)
size_t	dns__rbt_getheight (dns_rbt_t *rbt)
	Return the maximum height of sub-root nodes found in the red-black forest.
static isc_boolean_t	check_properties_helper (dns_rbtnode_t *node)
static isc_boolean_t	check_black_distance_helper (dns_rbtnode_t node, size_t distance)
isc_boolean_t	dns__rbt_checkproperties (dns_rbt_t *rbt)
	Check red-black properties of the forest.
static void	dns_rbt_indent (FILE *f, int depth)
void	dns_rbt_printnodeinfo (dns_rbtnode_t n, FILE f)
	Print out various information about a node.
static void	print_text_helper (dns_rbtnode_t root, dns_rbtnode_t parent, int depth, const char direction, void(data_printer)(FILE , void ), FILE *f)
void	dns_rbt_printtext (dns_rbt_t rbt, void(data_printer)(FILE , void ), FILE *f)
	Print an ASCII representation of the internal structure of the red-black tree of trees to the passed stream.
static int	print_dot_helper (dns_rbtnode_t node, unsigned int nodecount, isc_boolean_t show_pointers, FILE *f)
void	dns_rbt_printdot (dns_rbt_t rbt, isc_boolean_t show_pointers, FILE f)
	Print a GraphViz dot representation of the internal structure of the red-black tree of trees to the passed stream.
void	dns_rbtnodechain_init (dns_rbtnodechain_t chain, isc_mem_t mctx)
	Initialize 'chain'.
isc_result_t	dns_rbtnodechain_current (dns_rbtnodechain_t chain, dns_name_t name, dns_name_t origin, dns_rbtnode_t *node)
	Provide the name, origin and node to which the chain is currently pointed.
isc_result_t	dns_rbtnodechain_prev (dns_rbtnodechain_t chain, dns_name_t name, dns_name_t *origin)
	Adjusts chain to point the DNSSEC predecessor of the name to which it is currently pointed.
isc_result_t	dns_rbtnodechain_down (dns_rbtnodechain_t chain, dns_name_t name, dns_name_t *origin)
	Descend down if possible.
isc_result_t	dns_rbtnodechain_nextflat (dns_rbtnodechain_t chain, dns_name_t name)
	Find the next node at the current depth in DNSSEC order.
isc_result_t	dns_rbtnodechain_next (dns_rbtnodechain_t chain, dns_name_t name, dns_name_t *origin)
	Adjusts chain to point the DNSSEC successor of the name to which it is currently pointed.
isc_result_t	dns_rbtnodechain_first (dns_rbtnodechain_t chain, dns_rbt_t rbt, dns_name_t name, dns_name_t origin)
	Set the chain to the lexically first node in the tree of trees.
isc_result_t	dns_rbtnodechain_last (dns_rbtnodechain_t chain, dns_rbt_t rbt, dns_name_t name, dns_name_t origin)
	Set the chain to the lexically last node in the tree of trees.
void	dns_rbtnodechain_reset (dns_rbtnodechain_t *chain)
	Free any dynamic storage associated with 'chain', and then reinitialize 'chain'.
void	dns_rbtnodechain_invalidate (dns_rbtnodechain_t *chain)
	Free any dynamic storage associated with 'chain', and then invalidates it.
Variables
static char	FILE_VERSION [32] = "\0"