1135446Strhodes/* 2193149Sdougb * Copyright (C) 2004-2009 Internet Systems Consortium, Inc. ("ISC") 3135446Strhodes * Copyright (C) 1999-2002 Internet Software Consortium. 4135446Strhodes * 5193149Sdougb * Permission to use, copy, modify, and/or distribute this software for any 6135446Strhodes * purpose with or without fee is hereby granted, provided that the above 7135446Strhodes * copyright notice and this permission notice appear in all copies. 8135446Strhodes * 9135446Strhodes * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10135446Strhodes * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11135446Strhodes * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12135446Strhodes * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13135446Strhodes * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14135446Strhodes * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15135446Strhodes * PERFORMANCE OF THIS SOFTWARE. 16135446Strhodes */ 17135446Strhodes 18234010Sdougb/* $Id: rbt.h,v 1.77 2009/11/04 01:18:19 marka Exp $ */ 19135446Strhodes 20135446Strhodes#ifndef DNS_RBT_H 21135446Strhodes#define DNS_RBT_H 1 22135446Strhodes 23193149Sdougb/*! \file dns/rbt.h */ 24170222Sdougb 25135446Strhodes#include <isc/lang.h> 26135446Strhodes#include <isc/magic.h> 27170222Sdougb#include <isc/refcount.h> 28135446Strhodes 29135446Strhodes#include <dns/types.h> 30135446Strhodes 31135446StrhodesISC_LANG_BEGINDECLS 32135446Strhodes 33135446Strhodes#define DNS_RBT_USEHASH 1 34135446Strhodes 35170222Sdougb/*@{*/ 36170222Sdougb/*% 37135446Strhodes * Option values for dns_rbt_findnode() and dns_rbt_findname(). 38135446Strhodes * These are used to form a bitmask. 39135446Strhodes */ 40193149Sdougb#define DNS_RBTFIND_NOOPTIONS 0x00 41193149Sdougb#define DNS_RBTFIND_EMPTYDATA 0x01 42193149Sdougb#define DNS_RBTFIND_NOEXACT 0x02 43193149Sdougb#define DNS_RBTFIND_NOPREDECESSOR 0x04 44170222Sdougb/*@}*/ 45135446Strhodes 46170222Sdougb#ifndef DNS_RBT_USEISCREFCOUNT 47170222Sdougb#ifdef ISC_REFCOUNT_HAVEATOMIC 48170222Sdougb#define DNS_RBT_USEISCREFCOUNT 1 49170222Sdougb#endif 50170222Sdougb#endif 51170222Sdougb 52135446Strhodes/* 53135446Strhodes * These should add up to 30. 54135446Strhodes */ 55193149Sdougb#define DNS_RBT_LOCKLENGTH 10 56193149Sdougb#define DNS_RBT_REFLENGTH 20 57135446Strhodes 58193149Sdougb#define DNS_RBTNODE_MAGIC ISC_MAGIC('R','B','N','O') 59135446Strhodes#if DNS_RBT_USEMAGIC 60193149Sdougb#define DNS_RBTNODE_VALID(n) ISC_MAGIC_VALID(n, DNS_RBTNODE_MAGIC) 61135446Strhodes#else 62193149Sdougb#define DNS_RBTNODE_VALID(n) ISC_TRUE 63135446Strhodes#endif 64135446Strhodes 65170222Sdougb/*% 66135446Strhodes * This is the structure that is used for each node in the red/black 67135446Strhodes * tree of trees. NOTE WELL: the implementation manages this as a variable 68135446Strhodes * length structure, with the actual wire-format name and other data 69135446Strhodes * appended to this structure. Allocating a contiguous block of memory for 70135446Strhodes * multiple dns_rbtnode structures will not work. 71135446Strhodes */ 72193149Sdougbtypedef struct dns_rbtnode dns_rbtnode_t; 73224092Sdougbenum { 74224092Sdougb DNS_RBT_NSEC_NORMAL=0, /* in main tree */ 75224092Sdougb DNS_RBT_NSEC_HAS_NSEC=1, /* also has node in nsec tree */ 76224092Sdougb DNS_RBT_NSEC_NSEC=2, /* in nsec tree */ 77224092Sdougb DNS_RBT_NSEC_NSEC3=3 /* in nsec3 tree */ 78224092Sdougb}; 79193149Sdougbstruct dns_rbtnode { 80135446Strhodes#if DNS_RBT_USEMAGIC 81135446Strhodes unsigned int magic; 82135446Strhodes#endif 83193149Sdougb dns_rbtnode_t *parent; 84193149Sdougb dns_rbtnode_t *left; 85193149Sdougb dns_rbtnode_t *right; 86193149Sdougb dns_rbtnode_t *down; 87135446Strhodes#ifdef DNS_RBT_USEHASH 88193149Sdougb dns_rbtnode_t *hashnext; 89135446Strhodes#endif 90193149Sdougb 91193149Sdougb /*% 92193149Sdougb * Used for LRU cache. This linked list is used to mark nodes which 93193149Sdougb * have no data any longer, but we cannot unlink at that exact moment 94193149Sdougb * because we did not or could not obtain a write lock on the tree. 95193149Sdougb */ 96193149Sdougb ISC_LINK(dns_rbtnode_t) deadlink; 97193149Sdougb 98170222Sdougb /*@{*/ 99170222Sdougb /*! 100135446Strhodes * The following bitfields add up to a total bitwidth of 32. 101135446Strhodes * The range of values necessary for each item is indicated, 102193149Sdougb * but in the case of "attributes" the field is wider to accommodate 103224092Sdougb * possible future expansion. 104135446Strhodes * 105135446Strhodes * In each case below the "range" indicated is what's _necessary_ for 106135446Strhodes * the bitfield to hold, not what it actually _can_ hold. 107135446Strhodes */ 108193149Sdougb unsigned int is_root : 1; /*%< range is 0..1 */ 109193149Sdougb unsigned int color : 1; /*%< range is 0..1 */ 110193149Sdougb unsigned int find_callback : 1; /*%< range is 0..1 */ 111224092Sdougb unsigned int attributes : 3; /*%< range is 0..2 */ 112224092Sdougb unsigned int nsec : 2; /*%< range is 0..3 */ 113193149Sdougb unsigned int namelen : 8; /*%< range is 1..255 */ 114193149Sdougb unsigned int offsetlen : 8; /*%< range is 1..128 */ 115204619Sdougb unsigned int oldnamelen : 8; /*%< range is 1..255 */ 116170222Sdougb /*@}*/ 117135446Strhodes 118135446Strhodes#ifdef DNS_RBT_USEHASH 119135446Strhodes unsigned int hashval; 120135446Strhodes#endif 121135446Strhodes 122170222Sdougb /*@{*/ 123170222Sdougb /*! 124135446Strhodes * These values are used in the RBT DB implementation. The appropriate 125135446Strhodes * node lock must be held before accessing them. 126135446Strhodes */ 127135446Strhodes void *data; 128135446Strhodes unsigned int dirty:1; 129135446Strhodes unsigned int wild:1; 130135446Strhodes unsigned int locknum:DNS_RBT_LOCKLENGTH; 131170222Sdougb#ifndef DNS_RBT_USEISCREFCOUNT 132135446Strhodes unsigned int references:DNS_RBT_REFLENGTH; 133170222Sdougb#else 134170222Sdougb isc_refcount_t references; /* note that this is not in the bitfield */ 135170222Sdougb#endif 136170222Sdougb /*@}*/ 137193149Sdougb}; 138135446Strhodes 139135446Strhodestypedef isc_result_t (*dns_rbtfindcallback_t)(dns_rbtnode_t *node, 140135446Strhodes dns_name_t *name, 141135446Strhodes void *callback_arg); 142135446Strhodes 143135446Strhodes/***** 144193149Sdougb ***** Chain Info 145135446Strhodes *****/ 146135446Strhodes 147170222Sdougb/*! 148135446Strhodes * A chain is used to keep track of the sequence of nodes to reach any given 149135446Strhodes * node from the root of the tree. Originally nodes did not have parent 150135446Strhodes * pointers in them (for memory usage reasons) so there was no way to find 151135446Strhodes * the path back to the root from any given node. Now that nodes have parent 152135446Strhodes * pointers, chains might be going away in a future release, though the 153135446Strhodes * movement functionality would remain. 154135446Strhodes * 155135446Strhodes * In any event, parent information, whether via parent pointers or chains, is 156135446Strhodes * necessary information for iterating through the tree or for basic internal 157135446Strhodes * tree maintenance issues (ie, the rotations that are done to rebalance the 158135446Strhodes * tree when a node is added). The obvious implication of this is that for a 159135446Strhodes * chain to remain valid, the tree has to be locked down against writes for the 160135446Strhodes * duration of the useful life of the chain, because additions or removals can 161193149Sdougb * change the path from the root to the node the chain has targeted. 162135446Strhodes * 163135446Strhodes * The dns_rbtnodechain_ functions _first, _last, _prev and _next all take 164135446Strhodes * dns_name_t parameters for the name and the origin, which can be NULL. If 165135446Strhodes * non-NULL, 'name' will end up pointing to the name data and offsets that are 166135446Strhodes * stored at the node (and thus it will be read-only), so it should be a 167135446Strhodes * regular dns_name_t that has been initialized with dns_name_init. When 168135446Strhodes * 'origin' is non-NULL, it will get the name of the origin stored in it, so it 169135446Strhodes * needs to have its own buffer space and offsets, which is most easily 170135446Strhodes * accomplished with a dns_fixedname_t. It is _not_ necessary to reinitialize 171135446Strhodes * either 'name' or 'origin' between calls to the chain functions. 172135446Strhodes * 173135446Strhodes * NOTE WELL: even though the name data at the root of the tree of trees will 174135446Strhodes * be absolute (typically just "."), it will will be made into a relative name 175135446Strhodes * with an origin of "." -- an empty name when the node is ".". This is 176135446Strhodes * because a common on operation on 'name' and 'origin' is to use 177135446Strhodes * dns_name_concatenate() on them to generate the complete name. An empty name 178135446Strhodes * can be detected when dns_name_countlabels == 0, and is printed by 179135446Strhodes * dns_name_totext()/dns_name_format() as "@", consistent with RFC1035's 180135446Strhodes * definition of "@" as the current origin. 181135446Strhodes * 182135446Strhodes * dns_rbtnodechain_current is similar to the _first, _last, _prev and _next 183135446Strhodes * functions but additionally can provide the node to which the chain points. 184135446Strhodes */ 185135446Strhodes 186170222Sdougb/*% 187135446Strhodes * The number of level blocks to allocate at a time. Currently the maximum 188135446Strhodes * number of levels is allocated directly in the structure, but future 189135446Strhodes * revisions of this code might have a static initial block with dynamic 190135446Strhodes * growth. Allocating space for 256 levels when the tree is almost never that 191135446Strhodes * deep is wasteful, but it's not clear that it matters, since the waste is 192135446Strhodes * only 2MB for 1000 concurrently active chains on a system with 64-bit 193135446Strhodes * pointers. 194135446Strhodes */ 195135446Strhodes#define DNS_RBT_LEVELBLOCK 254 196135446Strhodes 197135446Strhodestypedef struct dns_rbtnodechain { 198193149Sdougb unsigned int magic; 199193149Sdougb isc_mem_t * mctx; 200170222Sdougb /*% 201135446Strhodes * The terminal node of the chain. It is not in levels[]. 202135446Strhodes * This is ostensibly private ... but in a pinch it could be 203135446Strhodes * used tell that the chain points nowhere without needing to 204135446Strhodes * call dns_rbtnodechain_current(). 205135446Strhodes */ 206193149Sdougb dns_rbtnode_t * end; 207170222Sdougb /*% 208135446Strhodes * The maximum number of labels in a name is 128; bitstrings mean 209135446Strhodes * a conceptually very large number (which I have not bothered to 210135446Strhodes * compute) of logical levels because splitting can potentially occur 211135446Strhodes * at each bit. However, DNSSEC restricts the number of "logical" 212135446Strhodes * labels in a name to 255, meaning only 254 pointers are needed 213135446Strhodes * in the worst case. 214135446Strhodes */ 215193149Sdougb dns_rbtnode_t * levels[DNS_RBT_LEVELBLOCK]; 216170222Sdougb /*% 217135446Strhodes * level_count indicates how deep the chain points into the 218135446Strhodes * tree of trees, and is the index into the levels[] array. 219135446Strhodes * Thus, levels[level_count - 1] is the last level node stored. 220135446Strhodes * A chain that points to the top level of the tree of trees has 221135446Strhodes * a level_count of 0, the first level has a level_count of 1, and 222135446Strhodes * so on. 223135446Strhodes */ 224193149Sdougb unsigned int level_count; 225170222Sdougb /*% 226135446Strhodes * level_matches tells how many levels matched above the node 227135446Strhodes * returned by dns_rbt_findnode(). A match (partial or exact) found 228135446Strhodes * in the first level thus results in level_matches being set to 1. 229135446Strhodes * This is used by the rbtdb to set the start point for a recursive 230135446Strhodes * search of superdomains until the RR it is looking for is found. 231135446Strhodes */ 232193149Sdougb unsigned int level_matches; 233135446Strhodes} dns_rbtnodechain_t; 234135446Strhodes 235135446Strhodes/***** 236135446Strhodes ***** Public interfaces. 237135446Strhodes *****/ 238135446Strhodesisc_result_t 239135446Strhodesdns_rbt_create(isc_mem_t *mctx, void (*deleter)(void *, void *), 240135446Strhodes void *deleter_arg, dns_rbt_t **rbtp); 241170222Sdougb/*%< 242135446Strhodes * Initialize a red-black tree of trees. 243135446Strhodes * 244135446Strhodes * Notes: 245193149Sdougb *\li The deleter argument, if non-null, points to a function that is 246193149Sdougb * responsible for cleaning up any memory associated with the data 247193149Sdougb * pointer of a node when the node is deleted. It is passed the 248193149Sdougb * deleted node's data pointer as its first argument and deleter_arg 249193149Sdougb * as its second argument. 250135446Strhodes * 251135446Strhodes * Requires: 252193149Sdougb * \li mctx is a pointer to a valid memory context. 253193149Sdougb *\li rbtp != NULL && *rbtp == NULL 254193149Sdougb *\li arg == NULL iff deleter == NULL 255135446Strhodes * 256135446Strhodes * Ensures: 257193149Sdougb *\li If result is ISC_R_SUCCESS: 258193149Sdougb * *rbtp points to a valid red-black tree manager 259135446Strhodes * 260193149Sdougb *\li If result is failure: 261193149Sdougb * *rbtp does not point to a valid red-black tree manager. 262135446Strhodes * 263135446Strhodes * Returns: 264193149Sdougb *\li #ISC_R_SUCCESS Success 265193149Sdougb *\li #ISC_R_NOMEMORY Resource limit: Out of Memory 266135446Strhodes */ 267135446Strhodes 268135446Strhodesisc_result_t 269135446Strhodesdns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data); 270170222Sdougb/*%< 271135446Strhodes * Add 'name' to the tree of trees, associated with 'data'. 272135446Strhodes * 273135446Strhodes * Notes: 274193149Sdougb *\li 'data' is never required to be non-NULL, but specifying it 275193149Sdougb * when the name is added is faster than searching for 'name' 276193149Sdougb * again and then setting the data pointer. The lack of a data pointer 277193149Sdougb * for a node also has other ramifications regarding whether 278193149Sdougb * dns_rbt_findname considers a node to exist, or dns_rbt_deletename 279193149Sdougb * joins nodes. 280135446Strhodes * 281135446Strhodes * Requires: 282193149Sdougb *\li rbt is a valid rbt manager. 283193149Sdougb *\li dns_name_isabsolute(name) == TRUE 284135446Strhodes * 285135446Strhodes * Ensures: 286193149Sdougb *\li 'name' is not altered in any way. 287135446Strhodes * 288193149Sdougb *\li Any external references to nodes in the tree are unaffected by 289193149Sdougb * node splits that are necessary to insert the new name. 290135446Strhodes * 291193149Sdougb *\li If result is #ISC_R_SUCCESS: 292193149Sdougb * 'name' is findable in the red/black tree of trees in O(log N). 293193149Sdougb * The data pointer of the node for 'name' is set to 'data'. 294135446Strhodes * 295193149Sdougb *\li If result is #ISC_R_EXISTS or #ISC_R_NOSPACE: 296193149Sdougb * The tree of trees is unaltered. 297135446Strhodes * 298193149Sdougb *\li If result is #ISC_R_NOMEMORY: 299193149Sdougb * No guarantees. 300135446Strhodes * 301135446Strhodes * Returns: 302193149Sdougb *\li #ISC_R_SUCCESS Success 303193149Sdougb *\li #ISC_R_EXISTS The name already exists with associated data. 304193149Sdougb *\li #ISC_R_NOSPACE The name had more logical labels than are allowed. 305193149Sdougb *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory 306135446Strhodes */ 307135446Strhodes 308135446Strhodesisc_result_t 309135446Strhodesdns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep); 310135446Strhodes 311170222Sdougb/*%< 312135446Strhodes * Just like dns_rbt_addname, but returns the address of the node. 313135446Strhodes * 314135446Strhodes * Requires: 315193149Sdougb *\li rbt is a valid rbt structure. 316193149Sdougb *\li dns_name_isabsolute(name) == TRUE 317193149Sdougb *\li nodep != NULL && *nodep == NULL 318135446Strhodes * 319135446Strhodes * Ensures: 320193149Sdougb *\li 'name' is not altered in any way. 321135446Strhodes * 322193149Sdougb *\li Any external references to nodes in the tree are unaffected by 323193149Sdougb * node splits that are necessary to insert the new name. 324135446Strhodes * 325193149Sdougb *\li If result is ISC_R_SUCCESS: 326193149Sdougb * 'name' is findable in the red/black tree of trees in O(log N). 327193149Sdougb * *nodep is the node that was added for 'name'. 328135446Strhodes * 329193149Sdougb *\li If result is ISC_R_EXISTS: 330193149Sdougb * The tree of trees is unaltered. 331193149Sdougb * *nodep is the existing node for 'name'. 332135446Strhodes * 333193149Sdougb *\li If result is ISC_R_NOMEMORY: 334193149Sdougb * No guarantees. 335135446Strhodes * 336135446Strhodes * Returns: 337193149Sdougb *\li #ISC_R_SUCCESS Success 338193149Sdougb *\li #ISC_R_EXISTS The name already exists, possibly without data. 339193149Sdougb *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory 340135446Strhodes */ 341135446Strhodes 342135446Strhodesisc_result_t 343135446Strhodesdns_rbt_findname(dns_rbt_t *rbt, dns_name_t *name, unsigned int options, 344135446Strhodes dns_name_t *foundname, void **data); 345170222Sdougb/*%< 346135446Strhodes * Get the data pointer associated with 'name'. 347135446Strhodes * 348135446Strhodes * Notes: 349193149Sdougb *\li When #DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is 350170222Sdougb * returned (also subject to #DNS_RBTFIND_EMPTYDATA), even when there is 351193149Sdougb * an exact match in the tree. 352135446Strhodes * 353170222Sdougb *\li A node that has no data is considered not to exist for this function, 354170222Sdougb * unless the #DNS_RBTFIND_EMPTYDATA option is set. 355135446Strhodes * 356135446Strhodes * Requires: 357193149Sdougb *\li rbt is a valid rbt manager. 358193149Sdougb *\li dns_name_isabsolute(name) == TRUE 359193149Sdougb *\li data != NULL && *data == NULL 360135446Strhodes * 361135446Strhodes * Ensures: 362193149Sdougb *\li 'name' and the tree are not altered in any way. 363135446Strhodes * 364193149Sdougb *\li If result is ISC_R_SUCCESS: 365193149Sdougb * *data is the data associated with 'name'. 366135446Strhodes * 367193149Sdougb *\li If result is DNS_R_PARTIALMATCH: 368193149Sdougb * *data is the data associated with the deepest superdomain 369193149Sdougb * of 'name' which has data. 370135446Strhodes * 371193149Sdougb *\li If result is ISC_R_NOTFOUND: 372193149Sdougb * Neither the name nor a superdomain was found with data. 373135446Strhodes * 374135446Strhodes * Returns: 375193149Sdougb *\li #ISC_R_SUCCESS Success 376193149Sdougb *\li #DNS_R_PARTIALMATCH Superdomain found with data 377193149Sdougb *\li #ISC_R_NOTFOUND No match 378193149Sdougb *\li #ISC_R_NOSPACE Concatenating nodes to form foundname failed 379135446Strhodes */ 380135446Strhodes 381135446Strhodesisc_result_t 382135446Strhodesdns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname, 383135446Strhodes dns_rbtnode_t **node, dns_rbtnodechain_t *chain, 384135446Strhodes unsigned int options, dns_rbtfindcallback_t callback, 385135446Strhodes void *callback_arg); 386170222Sdougb/*%< 387135446Strhodes * Find the node for 'name'. 388135446Strhodes * 389135446Strhodes * Notes: 390193149Sdougb *\li A node that has no data is considered not to exist for this function, 391193149Sdougb * unless the DNS_RBTFIND_EMPTYDATA option is set. This applies to both 392193149Sdougb * exact matches and partial matches. 393135446Strhodes * 394193149Sdougb *\li If the chain parameter is non-NULL, then the path through the tree 395193149Sdougb * to the DNSSEC predecessor of the searched for name is maintained, 396193149Sdougb * unless the DNS_RBTFIND_NOPREDECESSOR or DNS_RBTFIND_NOEXACT option 397193149Sdougb * is used. (For more details on those options, see below.) 398135446Strhodes * 399193149Sdougb *\li If there is no predecessor, then the chain will point to nowhere, as 400193149Sdougb * indicated by chain->end being NULL or dns_rbtnodechain_current 401193149Sdougb * returning ISC_R_NOTFOUND. Note that in a normal Internet DNS RBT 402193149Sdougb * there will always be a predecessor for all names except the root 403193149Sdougb * name, because '.' will exist and '.' is the predecessor of 404193149Sdougb * everything. But you can certainly construct a trivial tree and a 405193149Sdougb * search for it that has no predecessor. 406135446Strhodes * 407193149Sdougb *\li Within the chain structure, the 'levels' member of the structure holds 408193149Sdougb * the root node of each level except the first. 409135446Strhodes * 410193149Sdougb *\li The 'level_count' of the chain indicates how deep the chain to the 411193149Sdougb * predecessor name is, as an index into the 'levels[]' array. It does 412193149Sdougb * not count name elements, per se, but only levels of the tree of trees, 413193149Sdougb * the distinction arising because multiple labels from a name can be 414193149Sdougb * stored on only one level. It is also does not include the level 415193149Sdougb * that has the node, since that level is not stored in levels[]. 416135446Strhodes * 417193149Sdougb *\li The chain's 'level_matches' is not directly related to the predecessor. 418193149Sdougb * It is the number of levels above the level of the found 'node', 419193149Sdougb * regardless of whether it was a partial match or exact match. When 420193149Sdougb * the node is found in the top level tree, or no node is found at all, 421193149Sdougb * level_matches is 0. 422135446Strhodes * 423193149Sdougb *\li When DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is 424135446Strhodes * returned (also subject to DNS_RBTFIND_EMPTYDATA), even when 425135446Strhodes * there is an exact match in the tree. In this case, the chain 426193149Sdougb * will not point to the DNSSEC predecessor, but will instead point 427193149Sdougb * to the exact match, if there was any. Thus the preceding paragraphs 428193149Sdougb * should have "exact match" substituted for "predecessor" to describe 429193149Sdougb * how the various elements of the chain are set. This was done to 430193149Sdougb * ensure that the chain's state was sane, and to prevent problems that 431193149Sdougb * occurred when running the predecessor location code under conditions 432193149Sdougb * it was not designed for. It is not clear *where* the chain should 433193149Sdougb * point when DNS_RBTFIND_NOEXACT is set, so if you end up using a chain 434193149Sdougb * with this option because you want a particular node, let us know 435193149Sdougb * where you want the chain pointed, so this can be made more firm. 436135446Strhodes * 437135446Strhodes * Requires: 438193149Sdougb *\li rbt is a valid rbt manager. 439193149Sdougb *\li dns_name_isabsolute(name) == TRUE. 440193149Sdougb *\li node != NULL && *node == NULL. 441193149Sdougb *\li #DNS_RBTFIND_NOEXACT and DNS_RBTFIND_NOPREDECESSOR are mutually 442193149Sdougb * exclusive. 443135446Strhodes * 444135446Strhodes * Ensures: 445193149Sdougb *\li 'name' and the tree are not altered in any way. 446135446Strhodes * 447193149Sdougb *\li If result is ISC_R_SUCCESS: 448170222Sdougb *\verbatim 449193149Sdougb * *node is the terminal node for 'name'. 450170222Sdougb 451193149Sdougb * 'foundname' and 'name' represent the same name (though not 452193149Sdougb * the same memory). 453170222Sdougb 454193149Sdougb * 'chain' points to the DNSSEC predecessor, if any, of 'name'. 455135446Strhodes * 456193149Sdougb * chain->level_matches and chain->level_count are equal. 457170222Sdougb *\endverbatim 458135446Strhodes * 459193149Sdougb * If result is DNS_R_PARTIALMATCH: 460170222Sdougb *\verbatim 461193149Sdougb * *node is the data associated with the deepest superdomain 462193149Sdougb * of 'name' which has data. 463135446Strhodes * 464193149Sdougb * 'foundname' is the name of deepest superdomain (which has 465193149Sdougb * data, unless the DNS_RBTFIND_EMPTYDATA option is set). 466135446Strhodes * 467193149Sdougb * 'chain' points to the DNSSEC predecessor, if any, of 'name'. 468170222Sdougb *\endverbatim 469135446Strhodes * 470193149Sdougb *\li If result is ISC_R_NOTFOUND: 471170222Sdougb *\verbatim 472193149Sdougb * Neither the name nor a superdomain was found. *node is NULL. 473135446Strhodes * 474193149Sdougb * 'chain' points to the DNSSEC predecessor, if any, of 'name'. 475135446Strhodes * 476193149Sdougb * chain->level_matches is 0. 477170222Sdougb *\endverbatim 478135446Strhodes * 479135446Strhodes * Returns: 480193149Sdougb *\li #ISC_R_SUCCESS Success 481193149Sdougb *\li #DNS_R_PARTIALMATCH Superdomain found with data 482193149Sdougb *\li #ISC_R_NOTFOUND No match, or superdomain with no data 483193149Sdougb *\li #ISC_R_NOSPACE Concatenating nodes to form foundname failed 484135446Strhodes */ 485135446Strhodes 486135446Strhodesisc_result_t 487135446Strhodesdns_rbt_deletename(dns_rbt_t *rbt, dns_name_t *name, isc_boolean_t recurse); 488170222Sdougb/*%< 489135446Strhodes * Delete 'name' from the tree of trees. 490135446Strhodes * 491135446Strhodes * Notes: 492193149Sdougb *\li When 'name' is removed, if recurse is ISC_TRUE then all of its 493135446Strhodes * subnames are removed too. 494135446Strhodes * 495135446Strhodes * Requires: 496193149Sdougb *\li rbt is a valid rbt manager. 497193149Sdougb *\li dns_name_isabsolute(name) == TRUE 498135446Strhodes * 499135446Strhodes * Ensures: 500193149Sdougb *\li 'name' is not altered in any way. 501135446Strhodes * 502193149Sdougb *\li Does NOT ensure that any external references to nodes in the tree 503193149Sdougb * are unaffected by node joins. 504135446Strhodes * 505193149Sdougb *\li If result is ISC_R_SUCCESS: 506193149Sdougb * 'name' does not appear in the tree with data; however, 507193149Sdougb * the node for the name might still exist which can be 508193149Sdougb * found with dns_rbt_findnode (but not dns_rbt_findname). 509135446Strhodes * 510193149Sdougb *\li If result is ISC_R_NOTFOUND: 511193149Sdougb * 'name' does not appear in the tree with data, because 512193149Sdougb * it did not appear in the tree before the function was called. 513135446Strhodes * 514193149Sdougb *\li If result is something else: 515193149Sdougb * See result codes for dns_rbt_findnode (if it fails, the 516193149Sdougb * node is not deleted) or dns_rbt_deletenode (if it fails, 517193149Sdougb * the node is deleted, but the tree is not optimized when 518193149Sdougb * it could have been). 519135446Strhodes * 520135446Strhodes * Returns: 521193149Sdougb *\li #ISC_R_SUCCESS Success 522193149Sdougb *\li #ISC_R_NOTFOUND No match 523193149Sdougb *\li something_else Any return code from dns_rbt_findnode except 524193149Sdougb * DNS_R_PARTIALMATCH (which causes ISC_R_NOTFOUND 525193149Sdougb * to be returned instead), and any code from 526193149Sdougb * dns_rbt_deletenode. 527135446Strhodes */ 528135446Strhodes 529135446Strhodesisc_result_t 530135446Strhodesdns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, isc_boolean_t recurse); 531170222Sdougb/*%< 532135446Strhodes * Delete 'node' from the tree of trees. 533135446Strhodes * 534135446Strhodes * Notes: 535193149Sdougb *\li When 'node' is removed, if recurse is ISC_TRUE then all nodes 536193149Sdougb * in levels down from it are removed too. 537135446Strhodes * 538135446Strhodes * Requires: 539193149Sdougb *\li rbt is a valid rbt manager. 540193149Sdougb *\li node != NULL. 541135446Strhodes * 542135446Strhodes * Ensures: 543193149Sdougb *\li Does NOT ensure that any external references to nodes in the tree 544193149Sdougb * are unaffected by node joins. 545135446Strhodes * 546193149Sdougb *\li If result is ISC_R_SUCCESS: 547193149Sdougb * 'node' does not appear in the tree with data; however, 548193149Sdougb * the node might still exist if it serves as a pointer to 549193149Sdougb * a lower tree level as long as 'recurse' was false, hence 550193149Sdougb * the node could can be found with dns_rbt_findnode when 551193149Sdougb * that function's empty_data_ok parameter is true. 552135446Strhodes * 553193149Sdougb *\li If result is ISC_R_NOMEMORY or ISC_R_NOSPACE: 554193149Sdougb * The node was deleted, but the tree structure was not 555193149Sdougb * optimized. 556135446Strhodes * 557135446Strhodes * Returns: 558193149Sdougb *\li #ISC_R_SUCCESS Success 559193149Sdougb *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory when joining nodes. 560193149Sdougb *\li #ISC_R_NOSPACE dns_name_concatenate failed when joining nodes. 561135446Strhodes */ 562135446Strhodes 563135446Strhodesvoid 564135446Strhodesdns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name); 565170222Sdougb/*%< 566135446Strhodes * Convert the sequence of labels stored at 'node' into a 'name'. 567135446Strhodes * 568135446Strhodes * Notes: 569193149Sdougb *\li This function does not return the full name, from the root, but 570193149Sdougb * just the labels at the indicated node. 571135446Strhodes * 572193149Sdougb *\li The name data pointed to by 'name' is the information stored 573193149Sdougb * in the node, not a copy. Altering the data at this pointer 574193149Sdougb * will likely cause grief. 575135446Strhodes * 576135446Strhodes * Requires: 577193149Sdougb * \li name->offsets == NULL 578135446Strhodes * 579135446Strhodes * Ensures: 580193149Sdougb * \li 'name' is DNS_NAMEATTR_READONLY. 581135446Strhodes * 582193149Sdougb * \li 'name' will point directly to the labels stored after the 583193149Sdougb * dns_rbtnode_t struct. 584135446Strhodes * 585193149Sdougb * \li 'name' will have offsets that also point to the information stored 586193149Sdougb * as part of the node. 587135446Strhodes */ 588135446Strhodes 589135446Strhodesisc_result_t 590135446Strhodesdns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name); 591170222Sdougb/*%< 592135446Strhodes * Like dns_rbt_namefromnode, but returns the full name from the root. 593135446Strhodes * 594135446Strhodes * Notes: 595193149Sdougb * \li Unlike dns_rbt_namefromnode, the name will not point directly 596193149Sdougb * to node data. Rather, dns_name_concatenate will be used to copy 597193149Sdougb * the name data from each node into the 'name' argument. 598135446Strhodes * 599135446Strhodes * Requires: 600193149Sdougb * \li name != NULL 601193149Sdougb * \li name has a dedicated buffer. 602135446Strhodes * 603135446Strhodes * Returns: 604193149Sdougb * \li ISC_R_SUCCESS 605193149Sdougb * \li ISC_R_NOSPACE (possible via dns_name_concatenate) 606193149Sdougb * \li DNS_R_NAMETOOLONG (possible via dns_name_concatenate) 607135446Strhodes */ 608135446Strhodes 609135446Strhodeschar * 610135446Strhodesdns_rbt_formatnodename(dns_rbtnode_t *node, char *printname, 611135446Strhodes unsigned int size); 612170222Sdougb/*%< 613135446Strhodes * Format the full name of a node for printing, using dns_name_format(). 614135446Strhodes * 615135446Strhodes * Notes: 616193149Sdougb * \li 'size' is the length of the printname buffer. This should be 617193149Sdougb * DNS_NAME_FORMATSIZE or larger. 618135446Strhodes * 619135446Strhodes * Requires: 620193149Sdougb * \li node and printname are not NULL. 621135446Strhodes * 622135446Strhodes * Returns: 623193149Sdougb * \li The 'printname' pointer. 624135446Strhodes */ 625135446Strhodes 626135446Strhodesunsigned int 627135446Strhodesdns_rbt_nodecount(dns_rbt_t *rbt); 628170222Sdougb/*%< 629135446Strhodes * Obtain the number of nodes in the tree of trees. 630135446Strhodes * 631135446Strhodes * Requires: 632193149Sdougb * \li rbt is a valid rbt manager. 633135446Strhodes */ 634135446Strhodes 635135446Strhodesvoid 636135446Strhodesdns_rbt_destroy(dns_rbt_t **rbtp); 637135446Strhodesisc_result_t 638135446Strhodesdns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum); 639170222Sdougb/*%< 640193149Sdougb * Stop working with a red-black tree of trees. 641143731Sdougb * If 'quantum' is zero then the entire tree will be destroyed. 642143731Sdougb * If 'quantum' is non zero then up to 'quantum' nodes will be destroyed 643143731Sdougb * allowing the rbt to be incrementally destroyed by repeated calls to 644143731Sdougb * dns_rbt_destroy2(). Once dns_rbt_destroy2() has been called no other 645143731Sdougb * operations than dns_rbt_destroy()/dns_rbt_destroy2() should be 646143731Sdougb * performed on the tree of trees. 647193149Sdougb * 648135446Strhodes * Requires: 649193149Sdougb * \li *rbt is a valid rbt manager. 650135446Strhodes * 651143731Sdougb * Ensures on ISC_R_SUCCESS: 652193149Sdougb * \li All space allocated by the RBT library has been returned. 653135446Strhodes * 654193149Sdougb * \li *rbt is invalidated as an rbt manager. 655135446Strhodes * 656135446Strhodes * Returns: 657193149Sdougb * \li ISC_R_SUCCESS 658193149Sdougb * \li ISC_R_QUOTA if 'quantum' nodes have been destroyed. 659135446Strhodes */ 660135446Strhodes 661135446Strhodesvoid 662135446Strhodesdns_rbt_printall(dns_rbt_t *rbt); 663170222Sdougb/*%< 664135446Strhodes * Print an ASCII representation of the internal structure of the red-black 665135446Strhodes * tree of trees. 666135446Strhodes * 667135446Strhodes * Notes: 668193149Sdougb * \li The name stored at each node, along with the node's color, is printed. 669193149Sdougb * Then the down pointer, left and right pointers are displayed 670193149Sdougb * recursively in turn. NULL down pointers are silently omitted; 671193149Sdougb * NULL left and right pointers are printed. 672135446Strhodes */ 673135446Strhodes 674135446Strhodes/***** 675135446Strhodes ***** Chain Functions 676135446Strhodes *****/ 677135446Strhodes 678135446Strhodesvoid 679135446Strhodesdns_rbtnodechain_init(dns_rbtnodechain_t *chain, isc_mem_t *mctx); 680170222Sdougb/*%< 681135446Strhodes * Initialize 'chain'. 682135446Strhodes * 683135446Strhodes * Requires: 684193149Sdougb *\li 'chain' is a valid pointer. 685135446Strhodes * 686193149Sdougb *\li 'mctx' is a valid memory context. 687135446Strhodes * 688135446Strhodes * Ensures: 689193149Sdougb *\li 'chain' is suitable for use. 690135446Strhodes */ 691135446Strhodes 692135446Strhodesvoid 693135446Strhodesdns_rbtnodechain_reset(dns_rbtnodechain_t *chain); 694170222Sdougb/*%< 695135446Strhodes * Free any dynamic storage associated with 'chain', and then reinitialize 696135446Strhodes * 'chain'. 697135446Strhodes * 698135446Strhodes * Requires: 699193149Sdougb *\li 'chain' is a valid pointer. 700135446Strhodes * 701135446Strhodes * Ensures: 702193149Sdougb *\li 'chain' is suitable for use, and uses no dynamic storage. 703135446Strhodes */ 704135446Strhodes 705135446Strhodesvoid 706135446Strhodesdns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain); 707170222Sdougb/*%< 708135446Strhodes * Free any dynamic storage associated with 'chain', and then invalidates it. 709135446Strhodes * 710135446Strhodes * Notes: 711193149Sdougb *\li Future calls to any dns_rbtnodechain_ function will need to call 712193149Sdougb * dns_rbtnodechain_init on the chain first (except, of course, 713193149Sdougb * dns_rbtnodechain_init itself). 714135446Strhodes * 715135446Strhodes * Requires: 716193149Sdougb *\li 'chain' is a valid chain. 717135446Strhodes * 718135446Strhodes * Ensures: 719193149Sdougb *\li 'chain' is no longer suitable for use, and uses no dynamic storage. 720135446Strhodes */ 721135446Strhodes 722135446Strhodesisc_result_t 723135446Strhodesdns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name, 724135446Strhodes dns_name_t *origin, dns_rbtnode_t **node); 725170222Sdougb/*%< 726135446Strhodes * Provide the name, origin and node to which the chain is currently pointed. 727135446Strhodes * 728135446Strhodes * Notes: 729193149Sdougb *\li The tree need not have be locked against additions for the chain 730193149Sdougb * to remain valid, however there are no guarantees if any deletion 731193149Sdougb * has been made since the chain was established. 732135446Strhodes * 733135446Strhodes * Requires: 734193149Sdougb *\li 'chain' is a valid chain. 735135446Strhodes * 736135446Strhodes * Ensures: 737193149Sdougb *\li 'node', if non-NULL, is the node to which the chain was pointed 738193149Sdougb * by dns_rbt_findnode, dns_rbtnodechain_first or dns_rbtnodechain_last. 739193149Sdougb * If none were called for the chain since it was initialized or reset, 740193149Sdougb * or if the was no predecessor to the name searched for with 741193149Sdougb * dns_rbt_findnode, then '*node' is NULL and ISC_R_NOTFOUND is returned. 742135446Strhodes * 743193149Sdougb *\li 'name', if non-NULL, is the name stored at the terminal level of 744193149Sdougb * the chain. This is typically a single label, like the "www" of 745193149Sdougb * "www.isc.org", but need not be so. At the root of the tree of trees, 746193149Sdougb * if the node is "." then 'name' is ".", otherwise it is relative to ".". 747193149Sdougb * (Minimalist and atypical case: if the tree has just the name 748193149Sdougb * "isc.org." then the root node's stored name is "isc.org." but 'name' 749193149Sdougb * will be "isc.org".) 750135446Strhodes * 751193149Sdougb *\li 'origin', if non-NULL, is the sequence of labels in the levels 752193149Sdougb * above the terminal level, such as "isc.org." in the above example. 753193149Sdougb * 'origin' is always "." for the root node. 754135446Strhodes * 755135446Strhodes * 756135446Strhodes * Returns: 757193149Sdougb *\li #ISC_R_SUCCESS name, origin & node were successfully set. 758193149Sdougb *\li #ISC_R_NOTFOUND The chain does not point to any node. 759193149Sdougb *\li <something_else> Any error return from dns_name_concatenate. 760135446Strhodes */ 761135446Strhodes 762135446Strhodesisc_result_t 763135446Strhodesdns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt, 764135446Strhodes dns_name_t *name, dns_name_t *origin); 765170222Sdougb/*%< 766135446Strhodes * Set the chain to the lexically first node in the tree of trees. 767135446Strhodes * 768135446Strhodes * Notes: 769193149Sdougb *\li By the definition of ordering for DNS names, the root of the tree of 770193149Sdougb * trees is the very first node, since everything else in the megatree 771193149Sdougb * uses it as a common suffix. 772135446Strhodes * 773135446Strhodes * Requires: 774193149Sdougb *\li 'chain' is a valid chain. 775193149Sdougb *\li 'rbt' is a valid rbt manager. 776135446Strhodes * 777135446Strhodes * Ensures: 778193149Sdougb *\li The chain points to the very first node of the tree. 779135446Strhodes * 780193149Sdougb *\li 'name' and 'origin', if non-NULL, are set as described for 781193149Sdougb * dns_rbtnodechain_current. Thus 'origin' will always be ".". 782135446Strhodes * 783135446Strhodes * Returns: 784193149Sdougb *\li #DNS_R_NEWORIGIN The name & origin were successfully set. 785193149Sdougb *\li <something_else> Any error result from dns_rbtnodechain_current. 786135446Strhodes */ 787135446Strhodes 788135446Strhodesisc_result_t 789135446Strhodesdns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt, 790135446Strhodes dns_name_t *name, dns_name_t *origin); 791170222Sdougb/*%< 792135446Strhodes * Set the chain to the lexically last node in the tree of trees. 793135446Strhodes * 794135446Strhodes * Requires: 795193149Sdougb *\li 'chain' is a valid chain. 796193149Sdougb *\li 'rbt' is a valid rbt manager. 797135446Strhodes * 798135446Strhodes * Ensures: 799193149Sdougb *\li The chain points to the very last node of the tree. 800135446Strhodes * 801193149Sdougb *\li 'name' and 'origin', if non-NULL, are set as described for 802193149Sdougb * dns_rbtnodechain_current. 803135446Strhodes * 804135446Strhodes * Returns: 805193149Sdougb *\li #DNS_R_NEWORIGIN The name & origin were successfully set. 806193149Sdougb *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory building chain. 807193149Sdougb *\li <something_else> Any error result from dns_name_concatenate. 808135446Strhodes */ 809135446Strhodes 810135446Strhodesisc_result_t 811135446Strhodesdns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name, 812135446Strhodes dns_name_t *origin); 813170222Sdougb/*%< 814135446Strhodes * Adjusts chain to point the DNSSEC predecessor of the name to which it 815135446Strhodes * is currently pointed. 816135446Strhodes * 817135446Strhodes * Requires: 818193149Sdougb *\li 'chain' is a valid chain. 819193149Sdougb *\li 'chain' has been pointed somewhere in the tree with dns_rbt_findnode, 820193149Sdougb * dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that 821193149Sdougb * dns_rbt_findnode is not guaranteed to point the chain somewhere, 822193149Sdougb * since there may have been no predecessor to the searched for name. 823135446Strhodes * 824135446Strhodes * Ensures: 825193149Sdougb *\li The chain is pointed to the predecessor of its current target. 826135446Strhodes * 827193149Sdougb *\li 'name' and 'origin', if non-NULL, are set as described for 828193149Sdougb * dns_rbtnodechain_current. 829135446Strhodes * 830193149Sdougb *\li 'origin' is only if a new origin was found. 831135446Strhodes * 832135446Strhodes * Returns: 833193149Sdougb *\li #ISC_R_SUCCESS The predecessor was found and 'name' was set. 834193149Sdougb *\li #DNS_R_NEWORIGIN The predecessor was found with a different 835193149Sdougb * origin and 'name' and 'origin' were set. 836193149Sdougb *\li #ISC_R_NOMORE There was no predecessor. 837193149Sdougb *\li <something_else> Any error result from dns_rbtnodechain_current. 838135446Strhodes */ 839135446Strhodes 840135446Strhodesisc_result_t 841135446Strhodesdns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name, 842135446Strhodes dns_name_t *origin); 843170222Sdougb/*%< 844135446Strhodes * Adjusts chain to point the DNSSEC successor of the name to which it 845135446Strhodes * is currently pointed. 846135446Strhodes * 847135446Strhodes * Requires: 848193149Sdougb *\li 'chain' is a valid chain. 849193149Sdougb *\li 'chain' has been pointed somewhere in the tree with dns_rbt_findnode, 850193149Sdougb * dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that 851193149Sdougb * dns_rbt_findnode is not guaranteed to point the chain somewhere, 852193149Sdougb * since there may have been no predecessor to the searched for name. 853135446Strhodes * 854135446Strhodes * Ensures: 855193149Sdougb *\li The chain is pointed to the successor of its current target. 856135446Strhodes * 857193149Sdougb *\li 'name' and 'origin', if non-NULL, are set as described for 858193149Sdougb * dns_rbtnodechain_current. 859135446Strhodes * 860193149Sdougb *\li 'origin' is only if a new origin was found. 861135446Strhodes * 862135446Strhodes * Returns: 863193149Sdougb *\li #ISC_R_SUCCESS The successor was found and 'name' was set. 864193149Sdougb *\li #DNS_R_NEWORIGIN The successor was found with a different 865193149Sdougb * origin and 'name' and 'origin' were set. 866193149Sdougb *\li #ISC_R_NOMORE There was no successor. 867193149Sdougb *\li <something_else> Any error result from dns_name_concatenate. 868135446Strhodes */ 869135446Strhodes 870193149Sdougbisc_result_t 871193149Sdougbdns_rbtnodechain_down(dns_rbtnodechain_t *chain, dns_name_t *name, 872193149Sdougb dns_name_t *origin); 873193149Sdougb/*%< 874193149Sdougb * Descend down if possible. 875193149Sdougb */ 876193149Sdougb 877193149Sdougbisc_result_t 878193149Sdougbdns_rbtnodechain_nextflat(dns_rbtnodechain_t *chain, dns_name_t *name); 879193149Sdougb/*%< 880193149Sdougb * Find the next node at the current depth in DNSSEC order. 881193149Sdougb */ 882193149Sdougb 883170222Sdougb/* 884170222Sdougb * Wrapper macros for manipulating the rbtnode reference counter: 885170222Sdougb * Since we selectively use isc_refcount_t for the reference counter of 886170222Sdougb * a rbtnode, operations on the counter depend on the actual type of it. 887170222Sdougb * The following macros provide a common interface to these operations, 888170222Sdougb * hiding the back-end. The usage is the same as that of isc_refcount_xxx(). 889170222Sdougb */ 890170222Sdougb#ifdef DNS_RBT_USEISCREFCOUNT 891193149Sdougb#define dns_rbtnode_refinit(node, n) \ 892193149Sdougb do { \ 893193149Sdougb isc_refcount_init(&(node)->references, (n)); \ 894193149Sdougb } while (0) 895193149Sdougb#define dns_rbtnode_refdestroy(node) \ 896193149Sdougb do { \ 897193149Sdougb isc_refcount_destroy(&(node)->references); \ 898193149Sdougb } while (0) 899193149Sdougb#define dns_rbtnode_refcurrent(node) \ 900170222Sdougb isc_refcount_current(&(node)->references) 901193149Sdougb#define dns_rbtnode_refincrement0(node, refs) \ 902193149Sdougb do { \ 903170222Sdougb isc_refcount_increment0(&(node)->references, (refs)); \ 904193149Sdougb } while (0) 905193149Sdougb#define dns_rbtnode_refincrement(node, refs) \ 906193149Sdougb do { \ 907170222Sdougb isc_refcount_increment(&(node)->references, (refs)); \ 908193149Sdougb } while (0) 909193149Sdougb#define dns_rbtnode_refdecrement(node, refs) \ 910193149Sdougb do { \ 911170222Sdougb isc_refcount_decrement(&(node)->references, (refs)); \ 912193149Sdougb } while (0) 913170222Sdougb#else /* DNS_RBT_USEISCREFCOUNT */ 914193149Sdougb#define dns_rbtnode_refinit(node, n) ((node)->references = (n)) 915224092Sdougb#define dns_rbtnode_refdestroy(node) REQUIRE((node)->references == 0) 916193149Sdougb#define dns_rbtnode_refcurrent(node) ((node)->references) 917193149Sdougb#define dns_rbtnode_refincrement0(node, refs) \ 918193149Sdougb do { \ 919193149Sdougb unsigned int *_tmp = (unsigned int *)(refs); \ 920193149Sdougb (node)->references++; \ 921193149Sdougb if ((_tmp) != NULL) \ 922193149Sdougb (*_tmp) = (node)->references; \ 923193149Sdougb } while (0) 924193149Sdougb#define dns_rbtnode_refincrement(node, refs) \ 925193149Sdougb do { \ 926193149Sdougb REQUIRE((node)->references > 0); \ 927193149Sdougb (node)->references++; \ 928193149Sdougb if ((refs) != NULL) \ 929193149Sdougb (*refs) = (node)->references; \ 930193149Sdougb } while (0) 931193149Sdougb#define dns_rbtnode_refdecrement(node, refs) \ 932193149Sdougb do { \ 933193149Sdougb REQUIRE((node)->references > 0); \ 934193149Sdougb (node)->references--; \ 935193149Sdougb if ((refs) != NULL) \ 936193149Sdougb (*refs) = (node)->references; \ 937193149Sdougb } while (0) 938170222Sdougb#endif /* DNS_RBT_USEISCREFCOUNT */ 939170222Sdougb 940135446StrhodesISC_LANG_ENDDECLS 941135446Strhodes 942135446Strhodes#endif /* DNS_RBT_H */ 943