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