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

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