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_tgetparent (dns_rbtnode_t *node, file_header_t *header)
static dns_rbtnode_tgetleft (dns_rbtnode_t *node, file_header_t *header)
static dns_rbtnode_tgetright (dns_rbtnode_t *node, file_header_t *header)
static dns_rbtnode_tgetdown (dns_rbtnode_t *node, file_header_t *header)
static dns_rbtnode_tgetdata (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_tdns_rbt_root (dns_rbt_t *rbt)
static dns_rbtnode_tget_subtree_root (dns_rbtnode_t *node)
static dns_rbtnode_tget_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 (  ) 

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)

Definition at line 208 of file rbt.c.

Referenced by addonlevel(), check_black_distance_helper(), check_properties_helper(), create_node(), deletefromlevel(), deletetree(), deletetreeflat(), dns_rbt_addnode(), dns_rbt_findnode(), dns_rbtnodechain_down(), dns_rbtnodechain_next(), dns_rbtnodechain_nextflat(), dns_rbtnodechain_prev(), getheight_helper(), print_dot_helper(), print_text_helper(), rotate_left(), and rotate_right().

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

Definition at line 209 of file rbt.c.

Referenced by addonlevel(), check_black_distance_helper(), check_properties_helper(), create_node(), deletefromlevel(), deletetree(), deletetreeflat(), dns_rbt_addnode(), dns_rbt_findnode(), dns_rbtnodechain_next(), dns_rbtnodechain_nextflat(), dns_rbtnodechain_prev(), getheight_helper(), move_chain_to_last(), print_dot_helper(), print_text_helper(), rotate_left(), and rotate_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 (  ) 

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]

Definition at line 509 of file rbt.c.

References CHECK, cleanup(), dns_rbtnode::data, dns_rbtnode::data_is_relative, dns_name_init(), dns_name_print(), dns_rbt_serialize_align(), dns_rbtnode::down, dns_rbtnode::down_is_relative, INSIST, dns_rbtnode::is_mmapped, isc_crc64_update(), isc_stdio_seek(), isc_stdio_tell(), isc_stdio_write(), dns_rbtnode::left, dns_rbtnode::left_is_relative, NODE_SIZE, NODENAME, dns_rbtnode::parent, dns_rbtnode::parent_is_relative, dns_rbtnode::right, and dns_rbtnode::right_is_relative.

Referenced by serialize_nodes().

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]

Definition at line 2155 of file rbt.c.

References dns_name::attributes, ATTRS, isc_region::base, DATA, dns_rbtnode::data_is_relative, DIRTY, dns_name_countlabels(), dns_name_toregion(), DNS_RBT_NSEC_NORMAL, DNS_RBTNODE_MAGIC, dns_rbtnode_refinit, DOWN, dns_rbtnode::down_is_relative, ENSURE, dns_rbtnode::find_callback, HASHNEXT, HASHVAL, dns_rbtnode::is_mmapped, dns_rbtnode::is_root, ISC_LINK_INIT, isc_mem_get, ISC_R_NOMEMORY, ISC_R_SUCCESS, LEFT, dns_rbtnode::left_is_relative, isc_region::length, LOCKNUM, dns_rbtnode::magic, MAKE_BLACK, NAME, NAMELEN, dns_rbtnode::nsec, OFFSETLEN, OFFSETS, dns_name::offsets, OLDNAMELEN, OLDOFFSETLEN, PARENT, dns_rbtnode::parent_is_relative, REQUIRE, RIGHT, dns_rbtnode::right_is_relative, dns_rbtnode::rpz, and WILD.

Referenced by dns_rbt_addnode().

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]

Definition at line 719 of file rbt.c.

References CHECK, cleanup(), CONFIRM, dns_rbtnode::data, dns_rbtnode::data_is_relative, dns_fixedname_init, dns_fixedname_name, dns_name_concatenate(), dns_name_init(), dns_name_isabsolute(), dns_name_isvalid(), dns_name_print(), DNS_RBTNODE_VALID, dns_rbtnode::down, dns_rbtnode::down_is_relative, fixed, getdata(), getdown(), getleft(), getparent(), getright(), hash_node, header, isc_crc64_update(), ISC_R_SUCCESS, dns_rbtnode::left, dns_rbtnode::left_is_relative, dns_rbt::mmap_location, NODE_SIZE, dns_rbt::nodecount, NODENAME, dns_rbtnode::parent, dns_rbtnode::parent_is_relative, dns_rbtnode::right, and dns_rbtnode::right_is_relative.

Referenced by dns_rbt_deserialize_tree().

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:

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:

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:

Requires: Ensures: Returns:

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  ) 

Definition at line 966 of file rbt.c.

References dns_rbt_destroy2(), ISC_R_SUCCESS, and RUNTIME_CHECK.

Referenced by ATF_TC_BODY(), configure_view_nametable(), dbtable_free(), deserialize32(), destroy(), destroyring(), dns_dbtable_create(), dns_fwdtable_create(), dns_fwdtable_destroy(), dns_keytable_create(), dns_keytable_detach(), dns_ntatable_create(), dns_ntatable_detach(), dns_rbt_deserialize_tree(), dns_resolver_reset_algorithms(), dns_resolver_reset_ds_digests(), dns_resolver_resetmustbesecure(), dns_rpz_detach_rpzs(), dns_zt_create(), test_context_teardown(), and zt_destroy().

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:

Ensures on ISC_R_SUCCESS: Returns:

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:

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:

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:

Ensures: Returns:

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:

Requires: Ensures: Returns:

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:

Requires: Ensures: 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'.
 *

Returns:

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:

Requires: Ensures: Returns:

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:

Requires: Ensures: Returns:

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:

Requires: Ensures: Returns:

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:

Requires: Ensures:

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:

Requires: Returns:

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:

Requires: Returns:

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:

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:

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:

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:

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:

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:

Ensures:

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:

Requires: Ensures: Returns:

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:

Ensures: Returns:

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:

Ensures: Returns:

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:

Requires: Ensures: Returns:

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:

Ensures: Returns:

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:

Ensures:

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:

Requires: Ensures:

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