rbt.h 33.7 KB
Newer Older
David Lawrence's avatar
David Lawrence committed
1
/*
Automatic Updater's avatar
Automatic Updater committed
2
 * Copyright (C) 2004-2009  Internet Systems Consortium, Inc. ("ISC")
Mark Andrews's avatar
Mark Andrews committed
3
 * Copyright (C) 1999-2002  Internet Software Consortium.
4
 *
Automatic Updater's avatar
Automatic Updater committed
5
 * Permission to use, copy, modify, and/or distribute this software for any
David Lawrence's avatar
David Lawrence committed
6 7
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
8
 *
Mark Andrews's avatar
Mark Andrews committed
9 10 11 12 13 14 15
 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
David Lawrence's avatar
David Lawrence committed
16 17
 */

Francis Dupont's avatar
Francis Dupont committed
18
/* $Id: rbt.h,v 1.74 2009/09/29 15:06:06 fdupont Exp $ */
David Lawrence's avatar
David Lawrence committed
19

20 21
#ifndef DNS_RBT_H
#define DNS_RBT_H 1
Bob Halley's avatar
Bob Halley committed
22

23
/*! \file dns/rbt.h */
24

Bob Halley's avatar
Bob Halley committed
25
#include <isc/lang.h>
26
#include <isc/magic.h>
27
#include <isc/refcount.h>
28 29 30

#include <dns/types.h>

Bob Halley's avatar
Bob Halley committed
31 32
ISC_LANG_BEGINDECLS

33
#define DNS_RBT_USEHASH 1
34

35 36
/*@{*/
/*%
Bob Halley's avatar
Bob Halley committed
37 38 39
 * Option values for dns_rbt_findnode() and dns_rbt_findname().
 * These are used to form a bitmask.
 */
40 41 42 43
#define DNS_RBTFIND_NOOPTIONS                   0x00
#define DNS_RBTFIND_EMPTYDATA                   0x01
#define DNS_RBTFIND_NOEXACT                     0x02
#define DNS_RBTFIND_NOPREDECESSOR               0x04
44
/*@}*/
Bob Halley's avatar
Bob Halley committed
45

46 47 48 49 50 51
#ifndef DNS_RBT_USEISCREFCOUNT
#ifdef ISC_REFCOUNT_HAVEATOMIC
#define DNS_RBT_USEISCREFCOUNT 1
#endif
#endif

52 53 54
/*
 * These should add up to 30.
 */
55 56
#define DNS_RBT_LOCKLENGTH                      10
#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 64
#endif

65
/*%
66 67
 * This is the structure that is used for each node in the red/black
 * tree of trees.  NOTE WELL:  the implementation manages this as a variable
Andreas Gustafsson's avatar
Andreas Gustafsson committed
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 73
typedef struct dns_rbtnode dns_rbtnode_t;
struct dns_rbtnode {
74
#if DNS_RBT_USEMAGIC
75
	unsigned int magic;
76
#endif
77 78 79 80
	dns_rbtnode_t *parent;
	dns_rbtnode_t *left;
	dns_rbtnode_t *right;
	dns_rbtnode_t *down;
81
#ifdef DNS_RBT_USEHASH
82
	dns_rbtnode_t *hashnext;
83
#endif
84

85 86 87 88 89 90 91 92 93 94 95
	/*%
	 * Used for LRU cache.  This linked list is used to mark nodes which
	 * have no data any longer, but we cannot unlink at that exact moment
	 * because we did not or could not obtain a write lock on the tree.
	 */
	ISC_LINK(dns_rbtnode_t) deadlink;

	/*@{*/
	/*!
	 * The following bitfields add up to a total bitwidth of 32.
	 * The range of values necessary for each item is indicated,
Francis Dupont's avatar
Francis Dupont committed
96
	 * but in the case of "attributes" the field is wider to accommodate
97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113
	 * possible future expansion.  "offsetlen" could be one bit
	 * narrower by always adjusting its value by 1 to find the real
	 * offsetlen, but doing so does not gain anything (except perhaps
	 * another bit for "attributes", which doesn't yet need any more).
	 *
	 * In each case below the "range" indicated is what's _necessary_ for
	 * the bitfield to hold, not what it actually _can_ hold.
	 */
	unsigned int is_root : 1;       /*%< range is 0..1 */
	unsigned int color : 1;         /*%< range is 0..1 */
	unsigned int find_callback : 1; /*%< range is 0..1 */
	unsigned int attributes : 3;    /*%< range is 0..2 */
	unsigned int nsec3 : 1;    	/*%< range is 0..1 */
	unsigned int namelen : 8;       /*%< range is 1..255 */
	unsigned int offsetlen : 8;     /*%< range is 1..128 */
	unsigned int padbytes : 9;      /*%< range is 0..380 */
	/*@}*/
114

115
#ifdef DNS_RBT_USEHASH
116
	unsigned int hashval;
117
#endif
118

119 120 121 122 123 124 125 126 127
	/*@{*/
	/*!
	 * These values are used in the RBT DB implementation.  The appropriate
	 * node lock must be held before accessing them.
	 */
	void *data;
	unsigned int dirty:1;
	unsigned int wild:1;
	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 138
					      dns_name_t *name,
					      void *callback_arg);
139

David Lawrence's avatar
David Lawrence committed
140
/*****
141
 *****  Chain Info
David Lawrence's avatar
David Lawrence committed
142 143
 *****/

144
/*!
David Lawrence's avatar
David Lawrence committed
145
 * A chain is used to keep track of the sequence of nodes to reach any given
146 147 148 149 150 151 152 153 154 155 156 157
 * node from the root of the tree.  Originally nodes did not have parent
 * pointers in them (for memory usage reasons) so there was no way to find
 * the path back to the root from any given node.  Now that nodes have parent
 * pointers, chains might be going away in a future release, though the
 * movement functionality would remain.
 *
 * In any event, parent information, whether via parent pointers or chains, is
 * necessary information for iterating through the tree or for basic internal
 * tree maintenance issues (ie, the rotations that are done to rebalance the
 * tree when a node is added).  The obvious implication of this is that for a
 * chain to remain valid, the tree has to be locked down against writes for the
 * duration of the useful life of the chain, because additions or removals can
Francis Dupont's avatar
Francis Dupont committed
158
 * change the path from the root to the node the chain has targeted.
David Lawrence's avatar
David Lawrence committed
159 160
 *
 * The dns_rbtnodechain_ functions _first, _last, _prev and _next all take
161 162 163 164 165 166 167 168 169
 * dns_name_t parameters for the name and the origin, which can be NULL.  If
 * non-NULL, 'name' will end up pointing to the name data and offsets that are
 * stored at the node (and thus it will be read-only), so it should be a
 * regular dns_name_t that has been initialized with dns_name_init.  When
 * 'origin' is non-NULL, it will get the name of the origin stored in it, so it
 * needs to have its own buffer space and offsets, which is most easily
 * accomplished with a dns_fixedname_t.  It is _not_ necessary to reinitialize
 * either 'name' or 'origin' between calls to the chain functions.
 *
170 171 172 173 174 175 176 177
 * NOTE WELL: even though the name data at the root of the tree of trees will
 * be absolute (typically just "."), it will will be made into a relative name
 * with an origin of "." -- an empty name when the node is ".".  This is
 * because a common on operation on 'name' and 'origin' is to use
 * dns_name_concatenate() on them to generate the complete name.  An empty name
 * can be detected when dns_name_countlabels == 0, and is printed by
 * dns_name_totext()/dns_name_format() as "@", consistent with RFC1035's
 * definition of "@" as the current origin.
178
 *
179
 * dns_rbtnodechain_current is similar to the _first, _last, _prev and _next
Mark Andrews's avatar
style  
Mark Andrews committed
180 181
 * functions but additionally can provide the node to which the chain points.
 */
David Lawrence's avatar
David Lawrence committed
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 187 188 189 190
 * revisions of this code might have a static initial block with dynamic
 * growth.  Allocating space for 256 levels when the tree is almost never that
 * deep is wasteful, but it's not clear that it matters, since the waste is
 * only 2MB for 1000 concurrently active chains on a system with 64-bit
 * pointers.
191 192 193 194
 */
#define DNS_RBT_LEVELBLOCK 254

typedef struct dns_rbtnodechain {
195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229
	unsigned int            magic;
	isc_mem_t *             mctx;
	/*%
	 * The terminal node of the chain.  It is not in levels[].
	 * This is ostensibly private ... but in a pinch it could be
	 * used tell that the chain points nowhere without needing to
	 * call dns_rbtnodechain_current().
	 */
	dns_rbtnode_t *         end;
	/*%
	 * The maximum number of labels in a name is 128; bitstrings mean
	 * a conceptually very large number (which I have not bothered to
	 * compute) of logical levels because splitting can potentially occur
	 * at each bit.  However, DNSSEC restricts the number of "logical"
	 * labels in a name to 255, meaning only 254 pointers are needed
	 * in the worst case.
	 */
	dns_rbtnode_t *         levels[DNS_RBT_LEVELBLOCK];
	/*%
	 * level_count indicates how deep the chain points into the
	 * tree of trees, and is the index into the levels[] array.
	 * Thus, levels[level_count - 1] is the last level node stored.
	 * A chain that points to the top level of the tree of trees has
	 * a level_count of 0, the first level has a level_count of 1, and
	 * so on.
	 */
	unsigned int            level_count;
	/*%
	 * level_matches tells how many levels matched above the node
	 * returned by dns_rbt_findnode().  A match (partial or exact) found
	 * in the first level thus results in level_matches being set to 1.
	 * This is used by the rbtdb to set the start point for a recursive
	 * search of superdomains until the RR it is looking for is found.
	 */
	unsigned int            level_matches;
230 231
} dns_rbtnodechain_t;

David Lawrence's avatar
David Lawrence committed
232 233 234
/*****
 ***** Public interfaces.
 *****/
235
isc_result_t
David Lawrence's avatar
David Lawrence committed
236
dns_rbt_create(isc_mem_t *mctx, void (*deleter)(void *, void *),
237
	       void *deleter_arg, dns_rbt_t **rbtp);
238
/*%<
David Lawrence's avatar
David Lawrence committed
239 240 241
 * Initialize a red-black tree of trees.
 *
 * Notes:
242 243 244 245 246
 *\li   The deleter argument, if non-null, points to a function that is
 *      responsible for cleaning up any memory associated with the data
 *      pointer of a node when the node is deleted.  It is passed the
 *      deleted node's data pointer as its first argument and deleter_arg
 *      as its second argument.
David Lawrence's avatar
David Lawrence committed
247 248
 *
 * Requires:
249 250 251
 * \li  mctx is a pointer to a valid memory context.
 *\li   rbtp != NULL && *rbtp == NULL
 *\li   arg == NULL iff deleter == NULL
David Lawrence's avatar
David Lawrence committed
252 253
 *
 * Ensures:
254 255
 *\li   If result is ISC_R_SUCCESS:
 *              *rbtp points to a valid red-black tree manager
David Lawrence's avatar
David Lawrence committed
256
 *
257 258
 *\li   If result is failure:
 *              *rbtp does not point to a valid red-black tree manager.
David Lawrence's avatar
David Lawrence committed
259 260
 *
 * Returns:
261 262
 *\li   #ISC_R_SUCCESS  Success
 *\li   #ISC_R_NOMEMORY Resource limit: Out of Memory
David Lawrence's avatar
David Lawrence committed
263 264
 */

265
isc_result_t
David Lawrence's avatar
David Lawrence committed
266
dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data);
267
/*%<
268 269 270
 * Add 'name' to the tree of trees, associated with 'data'.
 *
 * Notes:
271 272 273 274 275 276
 *\li   'data' is never required to be non-NULL, but specifying it
 *      when the name is added is faster than searching for 'name'
 *      again and then setting the data pointer.  The lack of a data pointer
 *      for a node also has other ramifications regarding whether
 *      dns_rbt_findname considers a node to exist, or dns_rbt_deletename
 *      joins nodes.
277 278
 *
 * Requires:
279 280
 *\li   rbt is a valid rbt manager.
 *\li   dns_name_isabsolute(name) == TRUE
281 282
 *
 * Ensures:
283
 *\li   'name' is not altered in any way.
284
 *
285 286
 *\li   Any external references to nodes in the tree are unaffected by
 *      node splits that are necessary to insert the new name.
David Lawrence's avatar
David Lawrence committed
287
 *
288 289 290
 *\li   If result is #ISC_R_SUCCESS:
 *              'name' is findable in the red/black tree of trees in O(log N).
 *              The data pointer of the node for 'name' is set to 'data'.
David Lawrence's avatar
David Lawrence committed
291
 *
292 293
 *\li   If result is #ISC_R_EXISTS or #ISC_R_NOSPACE:
 *              The tree of trees is unaltered.
David Lawrence's avatar
David Lawrence committed
294
 *
295 296
 *\li   If result is #ISC_R_NOMEMORY:
 *              No guarantees.
David Lawrence's avatar
David Lawrence committed
297
 *
298
 * Returns:
299 300 301 302
 *\li   #ISC_R_SUCCESS  Success
 *\li   #ISC_R_EXISTS   The name already exists with associated data.
 *\li   #ISC_R_NOSPACE  The name had more logical labels than are allowed.
 *\li   #ISC_R_NOMEMORY Resource Limit: Out of Memory
303 304
 */

305
isc_result_t
David Lawrence's avatar
David Lawrence committed
306
dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep);
David Lawrence's avatar
David Lawrence committed
307

308
/*%<
David Lawrence's avatar
David Lawrence committed
309
 * Just like dns_rbt_addname, but returns the address of the node.
310 311
 *
 * Requires:
312 313 314
 *\li   rbt is a valid rbt structure.
 *\li   dns_name_isabsolute(name) == TRUE
 *\li   nodep != NULL && *nodep == NULL
David Lawrence's avatar
David Lawrence committed
315 316
 *
 * Ensures:
317
 *\li   'name' is not altered in any way.
David Lawrence's avatar
David Lawrence committed
318
 *
319 320
 *\li   Any external references to nodes in the tree are unaffected by
 *      node splits that are necessary to insert the new name.
David Lawrence's avatar
David Lawrence committed
321
 *
322 323 324
 *\li   If result is ISC_R_SUCCESS:
 *              'name' is findable in the red/black tree of trees in O(log N).
 *              *nodep is the node that was added for 'name'.
David Lawrence's avatar
David Lawrence committed
325
 *
326 327 328
 *\li   If result is ISC_R_EXISTS:
 *              The tree of trees is unaltered.
 *              *nodep is the existing node for 'name'.
David Lawrence's avatar
David Lawrence committed
329
 *
330 331
 *\li   If result is ISC_R_NOMEMORY:
 *              No guarantees.
David Lawrence's avatar
David Lawrence committed
332 333
 *
 * Returns:
334 335 336
 *\li   #ISC_R_SUCCESS  Success
 *\li   #ISC_R_EXISTS   The name already exists, possibly without data.
 *\li   #ISC_R_NOMEMORY Resource Limit: Out of Memory
David Lawrence's avatar
David Lawrence committed
337 338
 */

339
isc_result_t
Bob Halley's avatar
Bob Halley committed
340
dns_rbt_findname(dns_rbt_t *rbt, dns_name_t *name, unsigned int options,
341
		 dns_name_t *foundname, void **data);
342
/*%<
David Lawrence's avatar
David Lawrence committed
343 344 345
 * Get the data pointer associated with 'name'.
 *
 * 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.
David Lawrence's avatar
David Lawrence committed
349
 *
350 351
 *\li   A node that has no data is considered not to exist for this function,
 *      unless the #DNS_RBTFIND_EMPTYDATA option is set.
Bob Halley's avatar
Bob Halley committed
352
 *
David Lawrence's avatar
David Lawrence committed
353
 * Requires:
354 355 356
 *\li   rbt is a valid rbt manager.
 *\li   dns_name_isabsolute(name) == TRUE
 *\li   data != NULL && *data == NULL
David Lawrence's avatar
David Lawrence committed
357 358
 *
 * Ensures:
359
 *\li   'name' and the tree are not altered in any way.
David Lawrence's avatar
David Lawrence committed
360
 *
361 362
 *\li   If result is ISC_R_SUCCESS:
 *              *data is the data associated with 'name'.
David Lawrence's avatar
David Lawrence committed
363
 *
364 365 366
 *\li   If result is DNS_R_PARTIALMATCH:
 *              *data is the data associated with the deepest superdomain
 *              of 'name' which has data.
David Lawrence's avatar
David Lawrence committed
367
 *
368 369
 *\li   If result is ISC_R_NOTFOUND:
 *              Neither the name nor a superdomain was found with data.
David Lawrence's avatar
David Lawrence committed
370 371
 *
 * Returns:
372 373 374 375
 *\li   #ISC_R_SUCCESS          Success
 *\li   #DNS_R_PARTIALMATCH     Superdomain found with data
 *\li   #ISC_R_NOTFOUND         No match
 *\li   #ISC_R_NOSPACE          Concatenating nodes to form foundname failed
David Lawrence's avatar
David Lawrence committed
376 377
 */

378
isc_result_t
379
dns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname,
380 381 382
		 dns_rbtnode_t **node, dns_rbtnodechain_t *chain,
		 unsigned int options, dns_rbtfindcallback_t callback,
		 void *callback_arg);
383
/*%<
David Lawrence's avatar
David Lawrence committed
384 385 386
 * Find the node for 'name'.
 *
 * Notes:
387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409
 *\li   A node that has no data is considered not to exist for this function,
 *      unless the DNS_RBTFIND_EMPTYDATA option is set.  This applies to both
 *      exact matches and partial matches.
 *
 *\li   If the chain parameter is non-NULL, then the path through the tree
 *      to the DNSSEC predecessor of the searched for name is maintained,
 *      unless the DNS_RBTFIND_NOPREDECESSOR or DNS_RBTFIND_NOEXACT option
 *      is used. (For more details on those options, see below.)
 *
 *\li   If there is no predecessor, then the chain will point to nowhere, as
 *      indicated by chain->end being NULL or dns_rbtnodechain_current
 *      returning ISC_R_NOTFOUND.  Note that in a normal Internet DNS RBT
 *      there will always be a predecessor for all names except the root
 *      name, because '.' will exist and '.' is the predecessor of
 *      everything.  But you can certainly construct a trivial tree and a
 *      search for it that has no predecessor.
 *
 *\li   Within the chain structure, the 'levels' member of the structure holds
 *      the root node of each level except the first.
 *
 *\li   The 'level_count' of the chain indicates how deep the chain to the
 *      predecessor name is, as an index into the 'levels[]' array.  It does
 *      not count name elements, per se, but only levels of the tree of trees,
Francis Dupont's avatar
Francis Dupont committed
410
 *      the distinction arising because multiple labels from a name can be
411 412 413 414 415 416 417 418 419 420
 *      stored on only one level.  It is also does not include the level
 *      that has the node, since that level is not stored in levels[].
 *
 *\li   The chain's 'level_matches' is not directly related to the predecessor.
 *      It is the number of levels above the level of the found 'node',
 *      regardless of whether it was a partial match or exact match.  When
 *      the node is found in the top level tree, or no node is found at all,
 *      level_matches is 0.
 *
 *\li   When DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is
Bob Halley's avatar
Bob Halley committed
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 424 425 426 427 428 429 430 431 432
 *      will not point to the DNSSEC predecessor, but will instead point
 *      to the exact match, if there was any.  Thus the preceding paragraphs
 *      should have "exact match" substituted for "predecessor" to describe
 *      how the various elements of the chain are set.  This was done to
 *      ensure that the chain's state was sane, and to prevent problems that
 *      occurred when running the predecessor location code under conditions
 *      it was not designed for.  It is not clear *where* the chain should
 *      point when DNS_RBTFIND_NOEXACT is set, so if you end up using a chain
 *      with this option because you want a particular node, let us know
 *      where you want the chain pointed, so this can be made more firm.
433
 *
David Lawrence's avatar
David Lawrence committed
434
 * Requires:
435 436 437
 *\li   rbt is a valid rbt manager.
 *\li   dns_name_isabsolute(name) == TRUE.
 *\li   node != NULL && *node == NULL.
Francis Dupont's avatar
Francis Dupont committed
438
 *\li   #DNS_RBTFIND_NOEXACT and DNS_RBTFIND_NOPREDECESSOR are mutually
439
 *              exclusive.
David Lawrence's avatar
David Lawrence committed
440 441
 *
 * Ensures:
442
 *\li   'name' and the tree are not altered in any way.
David Lawrence's avatar
David Lawrence committed
443
 *
444
 *\li   If result is ISC_R_SUCCESS:
445
 *\verbatim
446
 *              *node is the terminal node for 'name'.
447

448 449
 *              'foundname' and 'name' represent the same name (though not
 *              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 459
 *              *node is the data associated with the deepest superdomain
 *              of 'name' which has data.
David Lawrence's avatar
David Lawrence committed
460
 *
461 462
 *              'foundname' is the name of deepest superdomain (which has
 *              data, unless the DNS_RBTFIND_EMPTYDATA option is set).
463
 *
464
 *              'chain' points to the DNSSEC predecessor, if any, of 'name'.
465
 *\endverbatim
David Lawrence's avatar
David Lawrence committed
466
 *
467
 *\li   If result is ISC_R_NOTFOUND:
468
 *\verbatim
469
 *              Neither the name nor a superdomain was found.  *node is NULL.
David Lawrence's avatar
David Lawrence committed
470
 *
471
 *              'chain' points to the DNSSEC predecessor, if any, of 'name'.
472
 *
473
 *              chain->level_matches is 0.
474
 *\endverbatim
David Lawrence's avatar
David Lawrence committed
475 476
 *
 * Returns:
477 478 479 480
 *\li   #ISC_R_SUCCESS          Success
 *\li   #DNS_R_PARTIALMATCH     Superdomain found with data
 *\li   #ISC_R_NOTFOUND         No match, or superdomain with no data
 *\li   #ISC_R_NOSPACE Concatenating nodes to form foundname failed
481 482
 */

483
isc_result_t
David Lawrence's avatar
David Lawrence committed
484
dns_rbt_deletename(dns_rbt_t *rbt, dns_name_t *name, isc_boolean_t recurse);
485
/*%<
486 487 488
 * Delete 'name' from the tree of trees.
 *
 * 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 494
 *\li   rbt is a valid rbt manager.
 *\li   dns_name_isabsolute(name) == TRUE
495 496
 *
 * Ensures:
497
 *\li   'name' is not altered in any way.
498
 *
499 500
 *\li   Does NOT ensure that any external references to nodes in the tree
 *      are unaffected by node joins.
David Lawrence's avatar
David Lawrence committed
501
 *
502 503 504 505
 *\li   If result is ISC_R_SUCCESS:
 *              'name' does not appear in the tree with data; however,
 *              the node for the name might still exist which can be
 *              found with dns_rbt_findnode (but not dns_rbt_findname).
David Lawrence's avatar
David Lawrence committed
506
 *
507 508 509
 *\li   If result is ISC_R_NOTFOUND:
 *              'name' does not appear in the tree with data, because
 *              it did not appear in the tree before the function was called.
David Lawrence's avatar
David Lawrence committed
510
 *
511 512 513 514 515
 *\li   If result is something else:
 *              See result codes for dns_rbt_findnode (if it fails, the
 *              node is not deleted) or dns_rbt_deletenode (if it fails,
 *              the node is deleted, but the tree is not optimized when
 *              it could have been).
516 517
 *
 * Returns:
518 519 520 521 522 523
 *\li   #ISC_R_SUCCESS  Success
 *\li   #ISC_R_NOTFOUND No match
 *\li   something_else  Any return code from dns_rbt_findnode except
 *                      DNS_R_PARTIALMATCH (which causes ISC_R_NOTFOUND
 *                      to be returned instead), and any code from
 *                      dns_rbt_deletenode.
524 525 526 527
 */

isc_result_t
dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, isc_boolean_t recurse);
528
/*%<
529 530 531
 * Delete 'node' from the tree of trees.
 *
 * Notes:
532 533
 *\li   When 'node' is removed, if recurse is ISC_TRUE then all nodes
 *      in levels down from it are removed too.
534 535
 *
 * Requires:
536 537
 *\li   rbt is a valid rbt manager.
 *\li   node != NULL.
538 539
 *
 * Ensures:
540 541
 *\li   Does NOT ensure that any external references to nodes in the tree
 *      are unaffected by node joins.
542
 *
543 544 545 546
 *\li   If result is ISC_R_SUCCESS:
 *              'node' does not appear in the tree with data; however,
 *              the node might still exist if it serves as a pointer to
 *              a lower tree level as long as 'recurse' was false, hence
Francis Dupont's avatar
Francis Dupont committed
547
 *              the node could can be found with dns_rbt_findnode when
548
 *              that function's empty_data_ok parameter is true.
549
 *
550 551 552
 *\li   If result is ISC_R_NOMEMORY or ISC_R_NOSPACE:
 *              The node was deleted, but the tree structure was not
 *              optimized.
553 554
 *
 * Returns:
555 556 557
 *\li   #ISC_R_SUCCESS  Success
 *\li   #ISC_R_NOMEMORY Resource Limit: Out of Memory when joining nodes.
 *\li   #ISC_R_NOSPACE  dns_name_concatenate failed when joining nodes.
558 559
 */

David Lawrence's avatar
David Lawrence committed
560 561
void
dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name);
562
/*%<
563 564 565
 * Convert the sequence of labels stored at 'node' into a 'name'.
 *
 * Notes:
566 567
 *\li   This function does not return the full name, from the root, but
 *      just the labels at the indicated node.
David Lawrence's avatar
David Lawrence committed
568
 *
569 570 571
 *\li   The name data pointed to by 'name' is the information stored
 *      in the node, not a copy.  Altering the data at this pointer
 *      will likely cause grief.
572
 *
David Lawrence's avatar
David Lawrence committed
573
 * Requires:
574
 * \li  name->offsets == NULL
David Lawrence's avatar
David Lawrence committed
575 576
 *
 * Ensures:
577
 * \li  'name' is DNS_NAMEATTR_READONLY.
David Lawrence's avatar
David Lawrence committed
578
 *
579 580
 * \li  'name' will point directly to the labels stored after the
 *      dns_rbtnode_t struct.
David Lawrence's avatar
David Lawrence committed
581
 *
582 583
 * \li  'name' will have offsets that also point to the information stored
 *      as part of the node.
584 585
 */

586 587
isc_result_t
dns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name);
588
/*%<
589 590 591
 * Like dns_rbt_namefromnode, but returns the full name from the root.
 *
 * Notes:
592 593 594
 * \li  Unlike dns_rbt_namefromnode, the name will not point directly
 *      to node data.  Rather, dns_name_concatenate will be used to copy
 *      the name data from each node into the 'name' argument.
595 596
 *
 * Requires:
597 598
 * \li  name != NULL
 * \li  name has a dedicated buffer.
599 600
 *
 * Returns:
601 602 603
 * \li  ISC_R_SUCCESS
 * \li  ISC_R_NOSPACE           (possible via dns_name_concatenate)
 * \li  DNS_R_NAMETOOLONG       (possible via dns_name_concatenate)
604 605 606 607
 */

char *
dns_rbt_formatnodename(dns_rbtnode_t *node, char *printname,
608
		       unsigned int size);
609
/*%<
610 611 612
 * Format the full name of a node for printing, using dns_name_format().
 *
 * Notes:
613 614
 * \li  'size' is the length of the printname buffer.  This should be
 *      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 624
unsigned int
dns_rbt_nodecount(dns_rbt_t *rbt);
625
/*%<
Andreas Gustafsson's avatar
Andreas Gustafsson committed
626
 * Obtain the number of nodes in the tree of trees.
627 628
 *
 * Requires:
629
 * \li  rbt is a valid rbt manager.
630 631
 */

David Lawrence's avatar
David Lawrence committed
632 633
void
dns_rbt_destroy(dns_rbt_t **rbtp);
634 635
isc_result_t
dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum);
636
/*%<
637
 * Stop working with a red-black tree of trees.
638 639 640 641 642 643
 * If 'quantum' is zero then the entire tree will be destroyed.
 * If 'quantum' is non zero then up to 'quantum' nodes will be destroyed
 * allowing the rbt to be incrementally destroyed by repeated calls to
 * dns_rbt_destroy2().  Once dns_rbt_destroy2() has been called no other
 * operations than dns_rbt_destroy()/dns_rbt_destroy2() should be
 * performed on the tree of trees.
644
 *
David Lawrence's avatar
David Lawrence committed
645
 * Requires:
646
 * \li  *rbt is a valid rbt manager.
David Lawrence's avatar
David Lawrence committed
647
 *
648
 * Ensures on ISC_R_SUCCESS:
649
 * \li  All space allocated by the RBT library has been returned.
David Lawrence's avatar
David Lawrence committed
650
 *
651
 * \li  *rbt is invalidated as an rbt manager.
652 653
 *
 * Returns:
654 655
 * \li  ISC_R_SUCCESS
 * \li  ISC_R_QUOTA if 'quantum' nodes have been destroyed.
656 657
 */

David Lawrence's avatar
David Lawrence committed
658 659
void
dns_rbt_printall(dns_rbt_t *rbt);
660
/*%<
David Lawrence's avatar
David Lawrence committed
661 662
 * Print an ASCII representation of the internal structure of the red-black
 * tree of trees.
663 664
 *
 * Notes:
665 666 667 668
 * \li  The name stored at each node, along with the node's color, is printed.
 *      Then the down pointer, left and right pointers are displayed
 *      recursively in turn.  NULL down pointers are silently omitted;
 *      NULL left and right pointers are printed.
669
 */
David Lawrence's avatar
David Lawrence committed
670

David Lawrence's avatar
David Lawrence committed
671 672 673
/*****
 ***** Chain Functions
 *****/
674 675 676

void
dns_rbtnodechain_init(dns_rbtnodechain_t *chain, isc_mem_t *mctx);
677
/*%<
678 679 680
 * Initialize 'chain'.
 *
 * 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 690
 */

void
dns_rbtnodechain_reset(dns_rbtnodechain_t *chain);
691
/*%<
692 693 694 695
 * Free any dynamic storage associated with 'chain', and then reinitialize
 * 'chain'.
 *
 * Requires:
696
 *\li   'chain' is a valid pointer.
697 698
 *
 * Ensures:
699
 *\li   'chain' is suitable for use, and uses no dynamic storage.
David Lawrence's avatar
David Lawrence committed
700 701 702 703
 */

void
dns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain);
704
/*%<
David Lawrence's avatar
David Lawrence committed
705 706 707
 * Free any dynamic storage associated with 'chain', and then invalidates it.
 *
 * Notes:
708 709 710
 *\li   Future calls to any dns_rbtnodechain_ function will need to call
 *      dns_rbtnodechain_init on the chain first (except, of course,
 *      dns_rbtnodechain_init itself).
David Lawrence's avatar
David Lawrence committed
711 712
 *
 * Requires:
713
 *\li   'chain' is a valid chain.
David Lawrence's avatar
David Lawrence committed
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.
David Lawrence's avatar
David Lawrence committed
724 725
 *
 * Notes:
726 727 728
 *\li   The tree need not have be locked against additions for the chain
 *      to remain valid, however there are no guarantees if any deletion
 *      has been made since the chain was established.
David Lawrence's avatar
David Lawrence committed
729 730
 *
 * Requires:
731
 *\li   'chain' is a valid chain.
David Lawrence's avatar
David Lawrence committed
732 733
 *
 * Ensures:
734 735 736 737 738
 *\li   'node', if non-NULL, is the node to which the chain was pointed
 *      by dns_rbt_findnode, dns_rbtnodechain_first or dns_rbtnodechain_last.
 *      If none were called for the chain since it was initialized or reset,
 *      or if the was no predecessor to the name searched for with
 *      dns_rbt_findnode, then '*node' is NULL and ISC_R_NOTFOUND is returned.
739
 *
740 741 742 743 744 745 746
 *\li   'name', if non-NULL, is the name stored at the terminal level of
 *      the chain.  This is typically a single label, like the "www" of
 *      "www.isc.org", but need not be so.  At the root of the tree of trees,
 *      if the node is "." then 'name' is ".", otherwise it is relative to ".".
 *      (Minimalist and atypical case:  if the tree has just the name
 *      "isc.org." then the root node's stored name is "isc.org." but 'name'
 *      will be "isc.org".)
747
 *
748 749 750
 *\li   'origin', if non-NULL, is the sequence of labels in the levels
 *      above the terminal level, such as "isc.org." in the above example.
 *      'origin' is always "." for the root node.
751
 *
752 753
 *
 * Returns:
754 755 756
 *\li   #ISC_R_SUCCESS          name, origin & node were successfully set.
 *\li   #ISC_R_NOTFOUND         The chain does not point to any node.
 *\li   &lt;something_else>     Any error return from dns_name_concatenate.
David Lawrence's avatar
David Lawrence committed
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
/*%<
David Lawrence's avatar
David Lawrence committed
763 764 765
 * Set the chain to the lexically first node in the tree of trees.
 *
 * Notes:
766 767 768
 *\li   By the definition of ordering for DNS names, the root of the tree of
 *      trees is the very first node, since everything else in the megatree
 *      uses it as a common suffix.
David Lawrence's avatar
David Lawrence committed
769 770
 *
 * Requires:
771 772
 *\li   'chain' is a valid chain.
 *\li   'rbt' is a valid rbt manager.
David Lawrence's avatar
David Lawrence committed
773 774
 *
 * Ensures:
775
 *\li   The chain points to the very first node of the tree.
776
 *
777 778
 *\li   'name' and 'origin', if non-NULL, are set as described for
 *      dns_rbtnodechain_current.  Thus 'origin' will always be ".".
David Lawrence's avatar
David Lawrence committed
779 780
 *
 * Returns:
781 782
 *\li   #DNS_R_NEWORIGIN                The name & origin were successfully set.
 *\li   &lt;something_else>     Any error result from dns_rbtnodechain_current.
David Lawrence's avatar
David Lawrence committed
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
/*%<
David Lawrence's avatar
David Lawrence committed
789 790 791
 * Set the chain to the lexically last node in the tree of trees.
 *
 * Requires:
792 793
 *\li   'chain' is a valid chain.
 *\li   'rbt' is a valid rbt manager.
David Lawrence's avatar
David Lawrence committed
794 795
 *
 * Ensures:
796
 *\li   The chain points to the very last node of the tree.
797
 *
798 799
 *\li   'name' and 'origin', if non-NULL, are set as described for
 *      dns_rbtnodechain_current.
David Lawrence's avatar
David Lawrence committed
800 801
 *
 * Returns:
802 803 804
 *\li   #DNS_R_NEWORIGIN                The name & origin were successfully set.
 *\li   #ISC_R_NOMEMORY         Resource Limit: Out of Memory building chain.
 *\li   &lt;something_else>     Any error result from dns_name_concatenate.
David Lawrence's avatar
David Lawrence committed
805 806
 */

807
isc_result_t
David Lawrence's avatar
David Lawrence committed
808
dns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name,
809
		      dns_name_t *origin);
810
/*%<
811 812 813 814
 * Adjusts chain to point the DNSSEC predecessor of the name to which it
 * is currently pointed.
 *
 * Requires:
815 816 817 818 819
 *\li   'chain' is a valid chain.
 *\li   'chain' has been pointed somewhere in the tree with dns_rbt_findnode,
 *      dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that
 *      dns_rbt_findnode is not guaranteed to point the chain somewhere,
 *      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 825
 *\li   'name' and 'origin', if non-NULL, are set as described for
 *      dns_rbtnodechain_current.
826
 *
827
 *\li   'origin' is only if a new origin was found.
David Lawrence's avatar
David Lawrence committed
828
 *
829
 * Returns:
830 831 832 833 834
 *\li   #ISC_R_SUCCESS          The predecessor was found and 'name' was set.
 *\li   #DNS_R_NEWORIGIN                The predecessor was found with a different
 *                              origin and 'name' and 'origin' were set.
 *\li   #ISC_R_NOMORE           There was no predecessor.
 *\li   &lt;something_else>     Any error result from dns_rbtnodechain_current.
David Lawrence's avatar
David Lawrence committed
835 836
 */

837
isc_result_t
David Lawrence's avatar
David Lawrence committed
838
dns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name,
839
		      dns_name_t *origin);
840
/*%<
841 842 843 844
 * Adjusts chain to point the DNSSEC successor of the name to which it
 * is currently pointed.
 *
 * Requires:
845 846 847 848 849
 *\li   'chain' is a valid chain.
 *\li   'chain' has been pointed somewhere in the tree with dns_rbt_findnode,
 *      dns_rbtnodechain_first or dns_rbtnodechain_last -- and remember that
 *      dns_rbt_findnode is not guaranteed to point the chain somewhere,
 *      since there may have been no predecessor to the searched for name.