1/* 2 * Copyright (C) 2004-2009 Internet Systems Consortium, Inc. ("ISC") 3 * Copyright (C) 1999-2002 Internet Software Consortium. 4 * 5 * Permission to use, copy, modify, and/or distribute this software for any 6 * purpose with or without fee is hereby granted, provided that the above 7 * copyright notice and this permission notice appear in all copies. 8 * 9 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15 * PERFORMANCE OF THIS SOFTWARE. 16 */ 17 18/* $Id: rbt.h,v 1.77 2009/11/04 01:18:19 marka Exp $ */ 19 20#ifndef DNS_RBT_H 21#define DNS_RBT_H 1 22 23/*! \file dns/rbt.h */ 24 25#include <isc/lang.h> 26#include <isc/magic.h> 27#include <isc/refcount.h> 28 29#include <dns/types.h> 30 31ISC_LANG_BEGINDECLS 32 33#define DNS_RBT_USEHASH 1 34 35/*@{*/ 36/*% 37 * Option values for dns_rbt_findnode() and dns_rbt_findname(). 38 * These are used to form a bitmask. 39 */ 40#define DNS_RBTFIND_NOOPTIONS 0x00 41#define DNS_RBTFIND_EMPTYDATA 0x01 42#define DNS_RBTFIND_NOEXACT 0x02 43#define DNS_RBTFIND_NOPREDECESSOR 0x04 44/*@}*/ 45 46#ifndef DNS_RBT_USEISCREFCOUNT 47#ifdef ISC_REFCOUNT_HAVEATOMIC 48#define DNS_RBT_USEISCREFCOUNT 1 49#endif 50#endif 51 52/* 53 * These should add up to 30. 54 */ 55#define DNS_RBT_LOCKLENGTH 10 56#define DNS_RBT_REFLENGTH 20 57 58#define DNS_RBTNODE_MAGIC ISC_MAGIC('R','B','N','O') 59#if DNS_RBT_USEMAGIC 60#define DNS_RBTNODE_VALID(n) ISC_MAGIC_VALID(n, DNS_RBTNODE_MAGIC) 61#else 62#define DNS_RBTNODE_VALID(n) ISC_TRUE 63#endif 64 65/*% 66 * This is the structure that is used for each node in the red/black 67 * tree of trees. NOTE WELL: the implementation manages this as a variable 68 * length structure, with the actual wire-format name and other data 69 * appended to this structure. Allocating a contiguous block of memory for 70 * multiple dns_rbtnode structures will not work. 71 */ 72typedef struct dns_rbtnode dns_rbtnode_t; 73enum { 74 DNS_RBT_NSEC_NORMAL=0, /* in main tree */ 75 DNS_RBT_NSEC_HAS_NSEC=1, /* also has node in nsec tree */ 76 DNS_RBT_NSEC_NSEC=2, /* in nsec tree */ 77 DNS_RBT_NSEC_NSEC3=3 /* in nsec3 tree */ 78}; 79struct dns_rbtnode { 80#if DNS_RBT_USEMAGIC 81 unsigned int magic; 82#endif 83 dns_rbtnode_t *parent; 84 dns_rbtnode_t *left; 85 dns_rbtnode_t *right; 86 dns_rbtnode_t *down; 87#ifdef DNS_RBT_USEHASH 88 dns_rbtnode_t *hashnext; 89#endif 90 91 /*% 92 * Used for LRU cache. This linked list is used to mark nodes which 93 * have no data any longer, but we cannot unlink at that exact moment 94 * because we did not or could not obtain a write lock on the tree. 95 */ 96 ISC_LINK(dns_rbtnode_t) deadlink; 97 98 /*@{*/ 99 /*! 100 * The following bitfields add up to a total bitwidth of 32. 101 * The range of values necessary for each item is indicated, 102 * but in the case of "attributes" the field is wider to accommodate 103 * possible future expansion. 104 * 105 * In each case below the "range" indicated is what's _necessary_ for 106 * the bitfield to hold, not what it actually _can_ hold. 107 */ 108 unsigned int is_root : 1; /*%< range is 0..1 */ 109 unsigned int color : 1; /*%< range is 0..1 */ 110 unsigned int find_callback : 1; /*%< range is 0..1 */ 111 unsigned int attributes : 3; /*%< range is 0..2 */ 112 unsigned int nsec : 2; /*%< range is 0..3 */ 113 unsigned int namelen : 8; /*%< range is 1..255 */ 114 unsigned int offsetlen : 8; /*%< range is 1..128 */ 115 unsigned int oldnamelen : 8; /*%< range is 1..255 */ 116 /*@}*/ 117 118#ifdef DNS_RBT_USEHASH 119 unsigned int hashval; 120#endif 121 122 /*@{*/ 123 /*! 124 * These values are used in the RBT DB implementation. The appropriate 125 * node lock must be held before accessing them. 126 */ 127 void *data; 128 unsigned int dirty:1; 129 unsigned int wild:1; 130 unsigned int locknum:DNS_RBT_LOCKLENGTH; 131#ifndef DNS_RBT_USEISCREFCOUNT 132 unsigned int references:DNS_RBT_REFLENGTH; 133#else 134 isc_refcount_t references; /* note that this is not in the bitfield */ 135#endif 136 /*@}*/ 137}; 138 139typedef isc_result_t (*dns_rbtfindcallback_t)(dns_rbtnode_t *node, 140 dns_name_t *name, 141 void *callback_arg); 142 143/***** 144 ***** Chain Info 145 *****/ 146 147/*! 148 * A chain is used to keep track of the sequence of nodes to reach any given 149 * node from the root of the tree. Originally nodes did not have parent 150 * pointers in them (for memory usage reasons) so there was no way to find 151 * the path back to the root from any given node. Now that nodes have parent 152 * pointers, chains might be going away in a future release, though the 153 * movement functionality would remain. 154 * 155 * In any event, parent information, whether via parent pointers or chains, is 156 * necessary information for iterating through the tree or for basic internal 157 * tree maintenance issues (ie, the rotations that are done to rebalance the 158 * tree when a node is added). The obvious implication of this is that for a 159 * chain to remain valid, the tree has to be locked down against writes for the 160 * duration of the useful life of the chain, because additions or removals can 161 * change the path from the root to the node the chain has targeted. 162 * 163 * The dns_rbtnodechain_ functions _first, _last, _prev and _next all take 164 * dns_name_t parameters for the name and the origin, which can be NULL. If 165 * non-NULL, 'name' will end up pointing to the name data and offsets that are 166 * stored at the node (and thus it will be read-only), so it should be a 167 * regular dns_name_t that has been initialized with dns_name_init. When 168 * 'origin' is non-NULL, it will get the name of the origin stored in it, so it 169 * needs to have its own buffer space and offsets, which is most easily 170 * accomplished with a dns_fixedname_t. It is _not_ necessary to reinitialize 171 * either 'name' or 'origin' between calls to the chain functions. 172 * 173 * NOTE WELL: even though the name data at the root of the tree of trees will 174 * be absolute (typically just "."), it will will be made into a relative name 175 * with an origin of "." -- an empty name when the node is ".". This is 176 * because a common on operation on 'name' and 'origin' is to use 177 * dns_name_concatenate() on them to generate the complete name. An empty name 178 * can be detected when dns_name_countlabels == 0, and is printed by 179 * dns_name_totext()/dns_name_format() as "@", consistent with RFC1035's 180 * definition of "@" as the current origin. 181 * 182 * dns_rbtnodechain_current is similar to the _first, _last, _prev and _next 183 * functions but additionally can provide the node to which the chain points. 184 */ 185 186/*% 187 * The number of level blocks to allocate at a time. Currently the maximum 188 * number of levels is allocated directly in the structure, but future 189 * revisions of this code might have a static initial block with dynamic 190 * growth. Allocating space for 256 levels when the tree is almost never that 191 * deep is wasteful, but it's not clear that it matters, since the waste is 192 * only 2MB for 1000 concurrently active chains on a system with 64-bit 193 * pointers. 194 */ 195#define DNS_RBT_LEVELBLOCK 254 196 197typedef struct dns_rbtnodechain { 198 unsigned int magic; 199 isc_mem_t * mctx; 200 /*% 201 * The terminal node of the chain. It is not in levels[]. 202 * This is ostensibly private ... but in a pinch it could be 203 * used tell that the chain points nowhere without needing to 204 * call dns_rbtnodechain_current(). 205 */ 206 dns_rbtnode_t * end; 207 /*% 208 * The maximum number of labels in a name is 128; bitstrings mean 209 * a conceptually very large number (which I have not bothered to 210 * compute) of logical levels because splitting can potentially occur 211 * at each bit. However, DNSSEC restricts the number of "logical" 212 * labels in a name to 255, meaning only 254 pointers are needed 213 * in the worst case. 214 */ 215 dns_rbtnode_t * levels[DNS_RBT_LEVELBLOCK]; 216 /*% 217 * level_count indicates how deep the chain points into the 218 * tree of trees, and is the index into the levels[] array. 219 * Thus, levels[level_count - 1] is the last level node stored. 220 * A chain that points to the top level of the tree of trees has 221 * a level_count of 0, the first level has a level_count of 1, and 222 * so on. 223 */ 224 unsigned int level_count; 225 /*% 226 * level_matches tells how many levels matched above the node 227 * returned by dns_rbt_findnode(). A match (partial or exact) found 228 * in the first level thus results in level_matches being set to 1. 229 * This is used by the rbtdb to set the start point for a recursive 230 * search of superdomains until the RR it is looking for is found. 231 */ 232 unsigned int level_matches; 233} dns_rbtnodechain_t; 234 235/***** 236 ***** Public interfaces. 237 *****/ 238isc_result_t 239dns_rbt_create(isc_mem_t *mctx, void (*deleter)(void *, void *), 240 void *deleter_arg, dns_rbt_t **rbtp); 241/*%< 242 * Initialize a red-black tree of trees. 243 * 244 * Notes: 245 *\li The deleter argument, if non-null, points to a function that is 246 * responsible for cleaning up any memory associated with the data 247 * pointer of a node when the node is deleted. It is passed the 248 * deleted node's data pointer as its first argument and deleter_arg 249 * as its second argument. 250 * 251 * Requires: 252 * \li mctx is a pointer to a valid memory context. 253 *\li rbtp != NULL && *rbtp == NULL 254 *\li arg == NULL iff deleter == NULL 255 * 256 * Ensures: 257 *\li If result is ISC_R_SUCCESS: 258 * *rbtp points to a valid red-black tree manager 259 * 260 *\li If result is failure: 261 * *rbtp does not point to a valid red-black tree manager. 262 * 263 * Returns: 264 *\li #ISC_R_SUCCESS Success 265 *\li #ISC_R_NOMEMORY Resource limit: Out of Memory 266 */ 267 268isc_result_t 269dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data); 270/*%< 271 * Add 'name' to the tree of trees, associated with 'data'. 272 * 273 * Notes: 274 *\li 'data' is never required to be non-NULL, but specifying it 275 * when the name is added is faster than searching for 'name' 276 * again and then setting the data pointer. The lack of a data pointer 277 * for a node also has other ramifications regarding whether 278 * dns_rbt_findname considers a node to exist, or dns_rbt_deletename 279 * joins nodes. 280 * 281 * Requires: 282 *\li rbt is a valid rbt manager. 283 *\li dns_name_isabsolute(name) == TRUE 284 * 285 * Ensures: 286 *\li 'name' is not altered in any way. 287 * 288 *\li Any external references to nodes in the tree are unaffected by 289 * node splits that are necessary to insert the new name. 290 * 291 *\li If result is #ISC_R_SUCCESS: 292 * 'name' is findable in the red/black tree of trees in O(log N). 293 * The data pointer of the node for 'name' is set to 'data'. 294 * 295 *\li If result is #ISC_R_EXISTS or #ISC_R_NOSPACE: 296 * The tree of trees is unaltered. 297 * 298 *\li If result is #ISC_R_NOMEMORY: 299 * No guarantees. 300 * 301 * Returns: 302 *\li #ISC_R_SUCCESS Success 303 *\li #ISC_R_EXISTS The name already exists with associated data. 304 *\li #ISC_R_NOSPACE The name had more logical labels than are allowed. 305 *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory 306 */ 307 308isc_result_t 309dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep); 310 311/*%< 312 * Just like dns_rbt_addname, but returns the address of the node. 313 * 314 * Requires: 315 *\li rbt is a valid rbt structure. 316 *\li dns_name_isabsolute(name) == TRUE 317 *\li nodep != NULL && *nodep == NULL 318 * 319 * Ensures: 320 *\li 'name' is not altered in any way. 321 * 322 *\li Any external references to nodes in the tree are unaffected by 323 * node splits that are necessary to insert the new name. 324 * 325 *\li If result is ISC_R_SUCCESS: 326 * 'name' is findable in the red/black tree of trees in O(log N). 327 * *nodep is the node that was added for 'name'. 328 * 329 *\li If result is ISC_R_EXISTS: 330 * The tree of trees is unaltered. 331 * *nodep is the existing node for 'name'. 332 * 333 *\li If result is ISC_R_NOMEMORY: 334 * No guarantees. 335 * 336 * Returns: 337 *\li #ISC_R_SUCCESS Success 338 *\li #ISC_R_EXISTS The name already exists, possibly without data. 339 *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory 340 */ 341 342isc_result_t 343dns_rbt_findname(dns_rbt_t *rbt, dns_name_t *name, unsigned int options, 344 dns_name_t *foundname, void **data); 345/*%< 346 * Get the data pointer associated with 'name'. 347 * 348 * Notes: 349 *\li When #DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is 350 * returned (also subject to #DNS_RBTFIND_EMPTYDATA), even when there is 351 * an exact match in the tree. 352 * 353 *\li A node that has no data is considered not to exist for this function, 354 * unless the #DNS_RBTFIND_EMPTYDATA option is set. 355 * 356 * Requires: 357 *\li rbt is a valid rbt manager. 358 *\li dns_name_isabsolute(name) == TRUE 359 *\li data != NULL && *data == NULL 360 * 361 * Ensures: 362 *\li 'name' and the tree are not altered in any way. 363 * 364 *\li If result is ISC_R_SUCCESS: 365 * *data is the data associated with 'name'. 366 * 367 *\li If result is DNS_R_PARTIALMATCH: 368 * *data is the data associated with the deepest superdomain 369 * of 'name' which has data. 370 * 371 *\li If result is ISC_R_NOTFOUND: 372 * Neither the name nor a superdomain was found with data. 373 * 374 * Returns: 375 *\li #ISC_R_SUCCESS Success 376 *\li #DNS_R_PARTIALMATCH Superdomain found with data 377 *\li #ISC_R_NOTFOUND No match 378 *\li #ISC_R_NOSPACE Concatenating nodes to form foundname failed 379 */ 380 381isc_result_t 382dns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname, 383 dns_rbtnode_t **node, dns_rbtnodechain_t *chain, 384 unsigned int options, dns_rbtfindcallback_t callback, 385 void *callback_arg); 386/*%< 387 * Find the node for 'name'. 388 * 389 * Notes: 390 *\li A node that has no data is considered not to exist for this function, 391 * unless the DNS_RBTFIND_EMPTYDATA option is set. This applies to both 392 * exact matches and partial matches. 393 * 394 *\li If the chain parameter is non-NULL, then the path through the tree 395 * to the DNSSEC predecessor of the searched for name is maintained, 396 * unless the DNS_RBTFIND_NOPREDECESSOR or DNS_RBTFIND_NOEXACT option 397 * is used. (For more details on those options, see below.) 398 * 399 *\li If there is no predecessor, then the chain will point to nowhere, as 400 * indicated by chain->end being NULL or dns_rbtnodechain_current 401 * returning ISC_R_NOTFOUND. Note that in a normal Internet DNS RBT 402 * there will always be a predecessor for all names except the root 403 * name, because '.' will exist and '.' is the predecessor of 404 * everything. But you can certainly construct a trivial tree and a 405 * search for it that has no predecessor. 406 * 407 *\li Within the chain structure, the 'levels' member of the structure holds 408 * the root node of each level except the first. 409 * 410 *\li The 'level_count' of the chain indicates how deep the chain to the 411 * predecessor name is, as an index into the 'levels[]' array. It does 412 * not count name elements, per se, but only levels of the tree of trees, 413 * the distinction arising because multiple labels from a name can be 414 * stored on only one level. It is also does not include the level 415 * that has the node, since that level is not stored in levels[]. 416 * 417 *\li The chain's 'level_matches' is not directly related to the predecessor. 418 * It is the number of levels above the level of the found 'node', 419 * regardless of whether it was a partial match or exact match. When 420 * the node is found in the top level tree, or no node is found at all, 421 * level_matches is 0. 422 * 423 *\li When DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is 424 * returned (also subject to DNS_RBTFIND_EMPTYDATA), even when 425 * there is an exact match in the tree. In this case, the chain 426 * will not point to the DNSSEC predecessor, but will instead point 427 * to the exact match, if there was any. Thus the preceding paragraphs 428 * should have "exact match" substituted for "predecessor" to describe 429 * how the various elements of the chain are set. This was done to 430 * ensure that the chain's state was sane, and to prevent problems that 431 * occurred when running the predecessor location code under conditions 432 * it was not designed for. It is not clear *where* the chain should 433 * point when DNS_RBTFIND_NOEXACT is set, so if you end up using a chain 434 * with this option because you want a particular node, let us know 435 * where you want the chain pointed, so this can be made more firm. 436 * 437 * Requires: 438 *\li rbt is a valid rbt manager. 439 *\li dns_name_isabsolute(name) == TRUE. 440 *\li node != NULL && *node == NULL. 441 *\li #DNS_RBTFIND_NOEXACT and DNS_RBTFIND_NOPREDECESSOR are mutually 442 * exclusive. 443 * 444 * Ensures: 445 *\li 'name' and the tree are not altered in any way. 446 * 447 *\li If result is ISC_R_SUCCESS: 448 *\verbatim 449 * *node is the terminal node for 'name'. 450 451 * 'foundname' and 'name' represent the same name (though not 452 * the same memory). 453 454 * 'chain' points to the DNSSEC predecessor, if any, of 'name'. 455 * 456 * chain->level_matches and chain->level_count are equal. 457 *\endverbatim 458 * 459 * If result is DNS_R_PARTIALMATCH: 460 *\verbatim 461 * *node is the data associated with the deepest superdomain 462 * of 'name' which has data. 463 * 464 * 'foundname' is the name of deepest superdomain (which has 465 * data, unless the DNS_RBTFIND_EMPTYDATA option is set). 466 * 467 * 'chain' points to the DNSSEC predecessor, if any, of 'name'. 468 *\endverbatim 469 * 470 *\li If result is ISC_R_NOTFOUND: 471 *\verbatim 472 * Neither the name nor a superdomain was found. *node is NULL. 473 * 474 * 'chain' points to the DNSSEC predecessor, if any, of 'name'. 475 * 476 * chain->level_matches is 0. 477 *\endverbatim 478 * 479 * Returns: 480 *\li #ISC_R_SUCCESS Success 481 *\li #DNS_R_PARTIALMATCH Superdomain found with data 482 *\li #ISC_R_NOTFOUND No match, or superdomain with no data 483 *\li #ISC_R_NOSPACE Concatenating nodes to form foundname failed 484 */ 485 486isc_result_t 487dns_rbt_deletename(dns_rbt_t *rbt, dns_name_t *name, isc_boolean_t recurse); 488/*%< 489 * Delete 'name' from the tree of trees. 490 * 491 * Notes: 492 *\li When 'name' is removed, if recurse is ISC_TRUE then all of its 493 * subnames are removed too. 494 * 495 * Requires: 496 *\li rbt is a valid rbt manager. 497 *\li dns_name_isabsolute(name) == TRUE 498 * 499 * Ensures: 500 *\li 'name' is not altered in any way. 501 * 502 *\li Does NOT ensure that any external references to nodes in the tree 503 * are unaffected by node joins. 504 * 505 *\li If result is ISC_R_SUCCESS: 506 * 'name' does not appear in the tree with data; however, 507 * the node for the name might still exist which can be 508 * found with dns_rbt_findnode (but not dns_rbt_findname). 509 * 510 *\li If result is ISC_R_NOTFOUND: 511 * 'name' does not appear in the tree with data, because 512 * it did not appear in the tree before the function was called. 513 * 514 *\li If result is something else: 515 * See result codes for dns_rbt_findnode (if it fails, the 516 * node is not deleted) or dns_rbt_deletenode (if it fails, 517 * the node is deleted, but the tree is not optimized when 518 * it could have been). 519 * 520 * Returns: 521 *\li #ISC_R_SUCCESS Success 522 *\li #ISC_R_NOTFOUND No match 523 *\li something_else Any return code from dns_rbt_findnode except 524 * DNS_R_PARTIALMATCH (which causes ISC_R_NOTFOUND 525 * to be returned instead), and any code from 526 * dns_rbt_deletenode. 527 */ 528 529isc_result_t 530dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, isc_boolean_t recurse); 531/*%< 532 * Delete 'node' from the tree of trees. 533 * 534 * Notes: 535 *\li When 'node' is removed, if recurse is ISC_TRUE then all nodes 536 * in levels down from it are removed too. 537 * 538 * Requires: 539 *\li rbt is a valid rbt manager. 540 *\li node != NULL. 541 * 542 * Ensures: 543 *\li Does NOT ensure that any external references to nodes in the tree 544 * are unaffected by node joins. 545 * 546 *\li If result is ISC_R_SUCCESS: 547 * 'node' does not appear in the tree with data; however, 548 * the node might still exist if it serves as a pointer to 549 * a lower tree level as long as 'recurse' was false, hence 550 * the node could can be found with dns_rbt_findnode when 551 * that function's empty_data_ok parameter is true. 552 * 553 *\li If result is ISC_R_NOMEMORY or ISC_R_NOSPACE: 554 * The node was deleted, but the tree structure was not 555 * optimized. 556 * 557 * Returns: 558 *\li #ISC_R_SUCCESS Success 559 *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory when joining nodes. 560 *\li #ISC_R_NOSPACE dns_name_concatenate failed when joining nodes. 561 */ 562 563void 564dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name); 565/*%< 566 * Convert the sequence of labels stored at 'node' into a 'name'. 567 * 568 * Notes: 569 *\li This function does not return the full name, from the root, but 570 * just the labels at the indicated node. 571 * 572 *\li The name data pointed to by 'name' is the information stored 573 * in the node, not a copy. Altering the data at this pointer 574 * will likely cause grief. 575 * 576 * Requires: 577 * \li name->offsets == NULL 578 * 579 * Ensures: 580 * \li 'name' is DNS_NAMEATTR_READONLY. 581 * 582 * \li 'name' will point directly to the labels stored after the 583 * dns_rbtnode_t struct. 584 * 585 * \li 'name' will have offsets that also point to the information stored 586 * as part of the node. 587 */ 588 589isc_result_t 590dns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name); 591/*%< 592 * Like dns_rbt_namefromnode, but returns the full name from the root. 593 * 594 * Notes: 595 * \li Unlike dns_rbt_namefromnode, the name will not point directly 596 * to node data. Rather, dns_name_concatenate will be used to copy 597 * the name data from each node into the 'name' argument. 598 * 599 * Requires: 600 * \li name != NULL 601 * \li name has a dedicated buffer. 602 * 603 * Returns: 604 * \li ISC_R_SUCCESS 605 * \li ISC_R_NOSPACE (possible via dns_name_concatenate) 606 * \li DNS_R_NAMETOOLONG (possible via dns_name_concatenate) 607 */ 608 609char * 610dns_rbt_formatnodename(dns_rbtnode_t *node, char *printname, 611 unsigned int size); 612/*%< 613 * Format the full name of a node for printing, using dns_name_format(). 614 * 615 * Notes: 616 * \li 'size' is the length of the printname buffer. This should be 617 * DNS_NAME_FORMATSIZE or larger. 618 * 619 * Requires: 620 * \li node and printname are not NULL. 621 * 622 * Returns: 623 * \li The 'printname' pointer. 624 */ 625 626unsigned int 627dns_rbt_nodecount(dns_rbt_t *rbt); 628/*%< 629 * Obtain the number of nodes in the tree of trees. 630 * 631 * Requires: 632 * \li rbt is a valid rbt manager. 633 */ 634 635void 636dns_rbt_destroy(dns_rbt_t **rbtp); 637isc_result_t 638dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum); 639/*%< 640 * Stop working with a red-black tree of trees. 641 * If 'quantum' is zero then the entire tree will be destroyed. 642 * If 'quantum' is non zero then up to 'quantum' nodes will be destroyed 643 * allowing the rbt to be incrementally destroyed by repeated calls to 644 * dns_rbt_destroy2(). Once dns_rbt_destroy2() has been called no other 645 * operations than dns_rbt_destroy()/dns_rbt_destroy2() should be 646 * performed on the tree of trees. 647 * 648 * Requires: 649 * \li *rbt is a valid rbt manager. 650 * 651 * Ensures on ISC_R_SUCCESS: 652 * \li All space allocated by the RBT library has been returned. 653 * 654 * \li *rbt is invalidated as an rbt manager. 655 * 656 * Returns: 657 * \li ISC_R_SUCCESS 658 * \li ISC_R_QUOTA if 'quantum' nodes have been destroyed. 659 */ 660 661void 662dns_rbt_printall(dns_rbt_t *rbt); 663/*%< 664 * Print an ASCII representation of the internal structure of the red-black 665 * tree of trees. 666 * 667 * Notes: 668 * \li The name stored at each node, along with the node's color, is printed. 669 * Then the down pointer, left and right pointers are displayed 670 * recursively in turn. NULL down pointers are silently omitted; 671 * NULL left and right pointers are printed. 672 */ 673 674/***** 675 ***** Chain Functions 676 *****/ 677 678void 679dns_rbtnodechain_init(dns_rbtnodechain_t *chain, isc_mem_t *mctx); 680/*%< 681 * Initialize 'chain'. 682 * 683 * Requires: 684 *\li 'chain' is a valid pointer. 685 * 686 *\li 'mctx' is a valid memory context. 687 * 688 * Ensures: 689 *\li 'chain' is suitable for use. 690 */ 691 692void 693dns_rbtnodechain_reset(dns_rbtnodechain_t *chain); 694/*%< 695 * Free any dynamic storage associated with 'chain', and then reinitialize 696 * 'chain'. 697 * 698 * Requires: 699 *\li 'chain' is a valid pointer. 700 * 701 * Ensures: 702 *\li 'chain' is suitable for use, and uses no dynamic storage. 703 */ 704 705void 706dns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain); 707/*%< 708 * Free any dynamic storage associated with 'chain', and then invalidates it. 709 * 710 * Notes: 711 *\li Future calls to any dns_rbtnodechain_ function will need to call 712 * dns_rbtnodechain_init on the chain first (except, of course, 713 * dns_rbtnodechain_init itself). 714 * 715 * Requires: 716 *\li 'chain' is a valid chain. 717 * 718 * Ensures: 719 *\li 'chain' is no longer suitable for use, and uses no dynamic storage. 720 */ 721 722isc_result_t 723dns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name, 724 dns_name_t *origin, dns_rbtnode_t **node); 725/*%< 726 * Provide the name, origin and node to which the chain is currently pointed. 727 * 728 * Notes: 729 *\li The tree need not have be locked against additions for the chain 730 * to remain valid, however there are no guarantees if any deletion 731 * has been made since the chain was established. 732 * 733 * Requires: 734 *\li 'chain' is a valid chain. 735 * 736 * Ensures: 737 *\li 'node', if non-NULL, is the node to which the chain was pointed 738 * by dns_rbt_findnode, dns_rbtnodechain_first or dns_rbtnodechain_last. 739 * If none were called for the chain since it was initialized or reset, 740 * or if the was no predecessor to the name searched for with 741 * dns_rbt_findnode, then '*node' is NULL and ISC_R_NOTFOUND is returned. 742 * 743 *\li 'name', if non-NULL, is the name stored at the terminal level of 744 * the chain. This is typically a single label, like the "www" of 745 * "www.isc.org", but need not be so. At the root of the tree of trees, 746 * if the node is "." then 'name' is ".", otherwise it is relative to ".". 747 * (Minimalist and atypical case: if the tree has just the name 748 * "isc.org." then the root node's stored name is "isc.org." but 'name' 749 * will be "isc.org".) 750 * 751 *\li 'origin', if non-NULL, is the sequence of labels in the levels 752 * above the terminal level, such as "isc.org." in the above example. 753 * 'origin' is always "." for the root node. 754 * 755 * 756 * Returns: 757 *\li #ISC_R_SUCCESS name, origin & node were successfully set. 758 *\li #ISC_R_NOTFOUND The chain does not point to any node. 759 *\li <something_else> Any error return from dns_name_concatenate. 760 */ 761 762isc_result_t 763dns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt, 764 dns_name_t *name, dns_name_t *origin); 765/*%< 766 * Set the chain to the lexically first node in the tree of trees. 767 * 768 * Notes: 769 *\li By the definition of ordering for DNS names, the root of the tree of 770 * trees is the very first node, since everything else in the megatree 771 * uses it as a common suffix. 772 * 773 * Requires: 774 *\li 'chain' is a valid chain. 775 *\li 'rbt' is a valid rbt manager. 776 * 777 * Ensures: 778 *\li The chain points to the very first node of the tree. 779 * 780 *\li 'name' and 'origin', if non-NULL, are set as described for 781 * dns_rbtnodechain_current. Thus 'origin' will always be ".". 782 * 783 * Returns: 784 *\li #DNS_R_NEWORIGIN The name & origin were successfully set. 785 *\li <something_else> Any error result from dns_rbtnodechain_current. 786 */ 787 788isc_result_t 789dns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt, 790 dns_name_t *name, dns_name_t *origin); 791/*%< 792 * Set the chain to the lexically last node in the tree of trees. 793 * 794 * Requires: 795 *\li 'chain' is a valid chain. 796 *\li 'rbt' is a valid rbt manager. 797 * 798 * Ensures: 799 *\li The chain points to the very last node of the tree. 800 * 801 *\li 'name' and 'origin', if non-NULL, are set as described for 802 * dns_rbtnodechain_current. 803 * 804 * Returns: 805 *\li #DNS_R_NEWORIGIN The name & origin were successfully set. 806 *\li #ISC_R_NOMEMORY Resource Limit: Out of Memory building chain. 807 *\li <something_else> Any error result from dns_name_concatenate. 808 */ 809 810isc_result_t 811dns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name, 812 dns_name_t *origin); 813/*%< 814 * Adjusts chain to point the DNSSEC predecessor of the name to which it 815 * is currently pointed. 816 * 817 * Requires: 818 *\li 'chain' is a valid chain. 819 *\li 'chain' has been pointed somewhere in the tree with dns_rbt_findnode, 820 * dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that 821 * dns_rbt_findnode is not guaranteed to point the chain somewhere, 822 * since there may have been no predecessor to the searched for name. 823 * 824 * Ensures: 825 *\li The chain is pointed to the predecessor of its current target. 826 * 827 *\li 'name' and 'origin', if non-NULL, are set as described for 828 * dns_rbtnodechain_current. 829 * 830 *\li 'origin' is only if a new origin was found. 831 * 832 * Returns: 833 *\li #ISC_R_SUCCESS The predecessor was found and 'name' was set. 834 *\li #DNS_R_NEWORIGIN The predecessor was found with a different 835 * origin and 'name' and 'origin' were set. 836 *\li #ISC_R_NOMORE There was no predecessor. 837 *\li <something_else> Any error result from dns_rbtnodechain_current. 838 */ 839 840isc_result_t 841dns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name, 842 dns_name_t *origin); 843/*%< 844 * Adjusts chain to point the DNSSEC successor of the name to which it 845 * is currently pointed. 846 * 847 * Requires: 848 *\li 'chain' is a valid chain. 849 *\li 'chain' has been pointed somewhere in the tree with dns_rbt_findnode, 850 * dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that 851 * dns_rbt_findnode is not guaranteed to point the chain somewhere, 852 * since there may have been no predecessor to the searched for name. 853 * 854 * Ensures: 855 *\li The chain is pointed to the successor of its current target. 856 * 857 *\li 'name' and 'origin', if non-NULL, are set as described for 858 * dns_rbtnodechain_current. 859 * 860 *\li 'origin' is only if a new origin was found. 861 * 862 * Returns: 863 *\li #ISC_R_SUCCESS The successor was found and 'name' was set. 864 *\li #DNS_R_NEWORIGIN The successor was found with a different 865 * origin and 'name' and 'origin' were set. 866 *\li #ISC_R_NOMORE There was no successor. 867 *\li <something_else> Any error result from dns_name_concatenate. 868 */ 869 870isc_result_t 871dns_rbtnodechain_down(dns_rbtnodechain_t *chain, dns_name_t *name, 872 dns_name_t *origin); 873/*%< 874 * Descend down if possible. 875 */ 876 877isc_result_t 878dns_rbtnodechain_nextflat(dns_rbtnodechain_t *chain, dns_name_t *name); 879/*%< 880 * Find the next node at the current depth in DNSSEC order. 881 */ 882 883/* 884 * Wrapper macros for manipulating the rbtnode reference counter: 885 * Since we selectively use isc_refcount_t for the reference counter of 886 * a rbtnode, operations on the counter depend on the actual type of it. 887 * The following macros provide a common interface to these operations, 888 * hiding the back-end. The usage is the same as that of isc_refcount_xxx(). 889 */ 890#ifdef DNS_RBT_USEISCREFCOUNT 891#define dns_rbtnode_refinit(node, n) \ 892 do { \ 893 isc_refcount_init(&(node)->references, (n)); \ 894 } while (0) 895#define dns_rbtnode_refdestroy(node) \ 896 do { \ 897 isc_refcount_destroy(&(node)->references); \ 898 } while (0) 899#define dns_rbtnode_refcurrent(node) \ 900 isc_refcount_current(&(node)->references) 901#define dns_rbtnode_refincrement0(node, refs) \ 902 do { \ 903 isc_refcount_increment0(&(node)->references, (refs)); \ 904 } while (0) 905#define dns_rbtnode_refincrement(node, refs) \ 906 do { \ 907 isc_refcount_increment(&(node)->references, (refs)); \ 908 } while (0) 909#define dns_rbtnode_refdecrement(node, refs) \ 910 do { \ 911 isc_refcount_decrement(&(node)->references, (refs)); \ 912 } while (0) 913#else /* DNS_RBT_USEISCREFCOUNT */ 914#define dns_rbtnode_refinit(node, n) ((node)->references = (n)) 915#define dns_rbtnode_refdestroy(node) REQUIRE((node)->references == 0) 916#define dns_rbtnode_refcurrent(node) ((node)->references) 917#define dns_rbtnode_refincrement0(node, refs) \ 918 do { \ 919 unsigned int *_tmp = (unsigned int *)(refs); \ 920 (node)->references++; \ 921 if ((_tmp) != NULL) \ 922 (*_tmp) = (node)->references; \ 923 } while (0) 924#define dns_rbtnode_refincrement(node, refs) \ 925 do { \ 926 REQUIRE((node)->references > 0); \ 927 (node)->references++; \ 928 if ((refs) != NULL) \ 929 (*refs) = (node)->references; \ 930 } while (0) 931#define dns_rbtnode_refdecrement(node, refs) \ 932 do { \ 933 REQUIRE((node)->references > 0); \ 934 (node)->references--; \ 935 if ((refs) != NULL) \ 936 (*refs) = (node)->references; \ 937 } while (0) 938#endif /* DNS_RBT_USEISCREFCOUNT */ 939 940ISC_LANG_ENDDECLS 941 942#endif /* DNS_RBT_H */ 943