contrib/bind-9.2.4rc7/lib/dns/include/dns/rbt.h

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