contrib/bind9/lib/dns/include/dns/rbt.h

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