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