rbt.h 38.5 KB
Newer Older
David Lawrence's avatar
David Lawrence committed
1
/*
2
 * Copyright (C) 2004-2009, 2012-2015  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
 */

18
/* $Id: rbt.h,v 1.77.666.4 2012/02/08 19:53:30 each 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

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

#include <dns/types.h>

Bob Halley's avatar
Bob Halley committed
32
33
ISC_LANG_BEGINDECLS

34
#define DNS_RBT_USEHASH 1
35

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

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

53
54
#define DNS_RBT_USEMAGIC 1

55
56
57
/*
 * These should add up to 30.
 */
58
59
#define DNS_RBT_LOCKLENGTH                      10
#define DNS_RBT_REFLENGTH                       20
60

61
#define DNS_RBTNODE_MAGIC               ISC_MAGIC('R','B','N','O')
62
#if DNS_RBT_USEMAGIC
63
#define DNS_RBTNODE_VALID(n)            ISC_MAGIC_VALID(n, DNS_RBTNODE_MAGIC)
64
#else
65
#define DNS_RBTNODE_VALID(n)            ISC_TRUE
66
67
#endif

68
/*%
69
70
 * 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
71
 * length structure, with the actual wire-format name and other data
72
 * appended to this structure.  Allocating a contiguous block of memory for
73
 * multiple dns_rbtnode structures will not work.
74
 */
75
typedef struct dns_rbtnode dns_rbtnode_t;
76
77
78
79
80
81
enum {
	DNS_RBT_NSEC_NORMAL=0,      /* in main tree */
	DNS_RBT_NSEC_HAS_NSEC=1,    /* also has node in nsec tree */
	DNS_RBT_NSEC_NSEC=2,        /* in nsec tree */
	DNS_RBT_NSEC_NSEC3=3        /* in nsec3 tree */
};
82
struct dns_rbtnode {
83
#if DNS_RBT_USEMAGIC
84
	unsigned int magic;
85
#endif
86
87
88
89
	/*@{*/
	/*!
	 * 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
90
	 * but in the case of "attributes" the field is wider to accommodate
91
	 * possible future expansion.
92
93
94
95
96
97
98
	 *
	 * 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 */
99
	unsigned int attributes : 3;    /*%< range is 0..2 */
100
	unsigned int nsec : 2;          /*%< range is 0..3 */
101
102
	unsigned int namelen : 8;       /*%< range is 1..255 */
	unsigned int offsetlen : 8;     /*%< range is 1..128 */
103
	unsigned int oldnamelen : 8;    /*%< range is 1..255 */
104
	/*@}*/
Tinderbox User's avatar
Tinderbox User committed
105

106
107
108
109
110
111
112
	/* flags needed for serialization to file*/
	unsigned int is_mmapped : 1;
	unsigned int parent_is_relative : 1;
	unsigned int left_is_relative : 1;
	unsigned int right_is_relative : 1;
	unsigned int down_is_relative : 1;
	unsigned int data_is_relative : 1;
113

114
115
116
	/* node needs to be cleaned from rpz */
	unsigned int rpz : 1;

117
118
119
120
121
122
123
124
125
126
	/*@{*/
	/*!
	 * These values are used in the RBT DB implementation.  The appropriate
	 * node lock must be held before accessing them.
	 */
	unsigned int dirty:1;
	unsigned int wild:1;
	unsigned int locknum:DNS_RBT_LOCKLENGTH;
	/*@}*/

127
#ifdef DNS_RBT_USEHASH
128
	unsigned int hashval;
129
130
	dns_rbtnode_t *uppernode;
	dns_rbtnode_t *hashnext;
131
#endif
132
133
134
135
136
137
138
139
140
141
142
	dns_rbtnode_t *parent;
	dns_rbtnode_t *left;
	dns_rbtnode_t *right;
	dns_rbtnode_t *down;

	/*%
	 * 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;
143

144
145
146
147
148
149
	/*@{*/
	/*!
	 * These values are used in the RBT DB implementation.  The appropriate
	 * node lock must be held before accessing them.
	 */
	void *data;
150
#ifndef DNS_RBT_USEISCREFCOUNT
151
	unsigned int references:DNS_RBT_REFLENGTH;
152
#else
153
	isc_refcount_t references; /* note that this is not in the bitfield */
154
#endif
155
	/*@}*/
156
};
157

158
typedef isc_result_t (*dns_rbtfindcallback_t)(dns_rbtnode_t *node,
159
160
					      dns_name_t *name,
					      void *callback_arg);
161

162
163
typedef isc_result_t (*dns_rbtdatawriter_t)(FILE *file,
					    unsigned char *data,
164
					    void *arg,
165
					    isc_uint64_t *crc);
Evan Hunt's avatar
Evan Hunt committed
166

167
168
typedef isc_result_t (*dns_rbtdatafixer_t)(dns_rbtnode_t *rbtnode,
					   void *base, size_t offset,
169
170
171
					   void *arg, isc_uint64_t *crc);

typedef void (*dns_rbtdeleter_t)(void *, void *);
172

David Lawrence's avatar
David Lawrence committed
173
/*****
174
 *****  Chain Info
David Lawrence's avatar
David Lawrence committed
175
176
 *****/

177
/*!
David Lawrence's avatar
David Lawrence committed
178
 * A chain is used to keep track of the sequence of nodes to reach any given
179
180
181
182
183
184
185
186
187
188
189
190
 * 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
191
 * change the path from the root to the node the chain has targeted.
David Lawrence's avatar
David Lawrence committed
192
193
 *
 * The dns_rbtnodechain_ functions _first, _last, _prev and _next all take
194
195
196
197
198
199
200
201
202
 * 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.
 *
203
204
205
206
207
208
209
210
 * 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.
211
 *
212
 * dns_rbtnodechain_current is similar to the _first, _last, _prev and _next
Mark Andrews's avatar
style    
Mark Andrews committed
213
214
 * functions but additionally can provide the node to which the chain points.
 */
David Lawrence's avatar
David Lawrence committed
215

216
/*%
217
 * The number of level blocks to allocate at a time.  Currently the maximum
218
 * number of levels is allocated directly in the structure, but future
219
220
221
222
223
 * 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.
224
225
226
227
 */
#define DNS_RBT_LEVELBLOCK 254

typedef struct dns_rbtnodechain {
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
	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;
263
264
} dns_rbtnodechain_t;

David Lawrence's avatar
David Lawrence committed
265
266
267
/*****
 ***** Public interfaces.
 *****/
268
isc_result_t
269
dns_rbt_create(isc_mem_t *mctx, dns_rbtdeleter_t deleter,
270
	       void *deleter_arg, dns_rbt_t **rbtp);
271
/*%<
David Lawrence's avatar
David Lawrence committed
272
273
274
 * Initialize a red-black tree of trees.
 *
 * Notes:
275
276
277
278
279
 *\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
280
281
 *
 * Requires:
282
283
284
 * \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
285
286
 *
 * Ensures:
287
288
 *\li   If result is ISC_R_SUCCESS:
 *              *rbtp points to a valid red-black tree manager
David Lawrence's avatar
David Lawrence committed
289
 *
290
291
 *\li   If result is failure:
 *              *rbtp does not point to a valid red-black tree manager.
David Lawrence's avatar
David Lawrence committed
292
293
 *
 * Returns:
294
295
 *\li   #ISC_R_SUCCESS  Success
 *\li   #ISC_R_NOMEMORY Resource limit: Out of Memory
David Lawrence's avatar
David Lawrence committed
296
297
 */

298
isc_result_t
David Lawrence's avatar
David Lawrence committed
299
dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data);
300
/*%<
301
302
303
 * Add 'name' to the tree of trees, associated with 'data'.
 *
 * Notes:
304
305
306
307
308
309
 *\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.
310
311
 *
 * Requires:
312
313
 *\li   rbt is a valid rbt manager.
 *\li   dns_name_isabsolute(name) == TRUE
314
315
 *
 * Ensures:
316
 *\li   'name' is not altered in any way.
317
 *
318
319
 *\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
320
 *
321
322
323
 *\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
324
 *
325
326
 *\li   If result is #ISC_R_EXISTS or #ISC_R_NOSPACE:
 *              The tree of trees is unaltered.
David Lawrence's avatar
David Lawrence committed
327
 *
328
329
 *\li   If result is #ISC_R_NOMEMORY:
 *              No guarantees.
David Lawrence's avatar
David Lawrence committed
330
 *
331
 * Returns:
332
333
334
335
 *\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
336
337
 */

338
isc_result_t
David Lawrence's avatar
David Lawrence committed
339
dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep);
David Lawrence's avatar
David Lawrence committed
340

341
/*%<
David Lawrence's avatar
David Lawrence committed
342
 * Just like dns_rbt_addname, but returns the address of the node.
343
344
 *
 * Requires:
345
346
347
 *\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
348
349
 *
 * Ensures:
350
 *\li   'name' is not altered in any way.
David Lawrence's avatar
David Lawrence committed
351
 *
352
353
 *\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
354
 *
355
356
357
 *\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
358
 *
359
360
361
 *\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
362
 *
363
364
 *\li   If result is ISC_R_NOMEMORY:
 *              No guarantees.
David Lawrence's avatar
David Lawrence committed
365
366
 *
 * Returns:
367
368
369
 *\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
370
371
 */

372
isc_result_t
Bob Halley's avatar
Bob Halley committed
373
dns_rbt_findname(dns_rbt_t *rbt, dns_name_t *name, unsigned int options,
374
		 dns_name_t *foundname, void **data);
375
/*%<
David Lawrence's avatar
David Lawrence committed
376
377
378
 * Get the data pointer associated with 'name'.
 *
 * Notes:
379
 *\li   When #DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is
380
 *      returned (also subject to #DNS_RBTFIND_EMPTYDATA), even when there is
381
 *      an exact match in the tree.
David Lawrence's avatar
David Lawrence committed
382
 *
383
384
 *\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
385
 *
David Lawrence's avatar
David Lawrence committed
386
 * Requires:
387
388
389
 *\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
390
391
 *
 * Ensures:
392
 *\li   'name' and the tree are not altered in any way.
David Lawrence's avatar
David Lawrence committed
393
 *
394
395
 *\li   If result is ISC_R_SUCCESS:
 *              *data is the data associated with 'name'.
David Lawrence's avatar
David Lawrence committed
396
 *
397
398
399
 *\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
400
 *
401
402
 *\li   If result is ISC_R_NOTFOUND:
 *              Neither the name nor a superdomain was found with data.
David Lawrence's avatar
David Lawrence committed
403
404
 *
 * Returns:
405
406
407
408
 *\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
409
410
 */

411
isc_result_t
412
dns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname,
413
414
415
		 dns_rbtnode_t **node, dns_rbtnodechain_t *chain,
		 unsigned int options, dns_rbtfindcallback_t callback,
		 void *callback_arg);
416
/*%<
David Lawrence's avatar
David Lawrence committed
417
418
419
 * Find the node for 'name'.
 *
 * Notes:
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
 *\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
443
 *      the distinction arising because multiple labels from a name can be
444
445
446
447
448
449
450
451
452
453
 *      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
454
 *      returned (also subject to DNS_RBTFIND_EMPTYDATA), even when
455
 *      there is an exact match in the tree.  In this case, the chain
456
457
458
459
460
461
462
463
464
465
 *      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.
466
 *
David Lawrence's avatar
David Lawrence committed
467
 * Requires:
468
469
470
 *\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
471
 *\li   #DNS_RBTFIND_NOEXACT and DNS_RBTFIND_NOPREDECESSOR are mutually
472
 *              exclusive.
David Lawrence's avatar
David Lawrence committed
473
474
 *
 * Ensures:
475
 *\li   'name' and the tree are not altered in any way.
David Lawrence's avatar
David Lawrence committed
476
 *
477
 *\li   If result is ISC_R_SUCCESS:
478
 *\verbatim
479
 *              *node is the terminal node for 'name'.
480

481
482
 *              'foundname' and 'name' represent the same name (though not
 *              the same memory).
483

484
 *              'chain' points to the DNSSEC predecessor, if any, of 'name'.
485
 *
486
 *              chain->level_matches and chain->level_count are equal.
487
 *\endverbatim
488
 *
489
 *      If result is DNS_R_PARTIALMATCH:
490
 *\verbatim
491
492
 *              *node is the data associated with the deepest superdomain
 *              of 'name' which has data.
David Lawrence's avatar
David Lawrence committed
493
 *
494
495
 *              'foundname' is the name of deepest superdomain (which has
 *              data, unless the DNS_RBTFIND_EMPTYDATA option is set).
496
 *
497
 *              'chain' points to the DNSSEC predecessor, if any, of 'name'.
498
 *\endverbatim
David Lawrence's avatar
David Lawrence committed
499
 *
500
 *\li   If result is ISC_R_NOTFOUND:
501
 *\verbatim
502
 *              Neither the name nor a superdomain was found.  *node is NULL.
David Lawrence's avatar
David Lawrence committed
503
 *
504
 *              'chain' points to the DNSSEC predecessor, if any, of 'name'.
505
 *
506
 *              chain->level_matches is 0.
507
 *\endverbatim
David Lawrence's avatar
David Lawrence committed
508
509
 *
 * Returns:
510
511
512
513
 *\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
514
515
 */

516
isc_result_t
David Lawrence's avatar
David Lawrence committed
517
dns_rbt_deletename(dns_rbt_t *rbt, dns_name_t *name, isc_boolean_t recurse);
518
/*%<
519
520
521
 * Delete 'name' from the tree of trees.
 *
 * Notes:
522
 *\li   When 'name' is removed, if recurse is ISC_TRUE then all of its
523
 *      subnames are removed too.
524
525
 *
 * Requires:
526
527
 *\li   rbt is a valid rbt manager.
 *\li   dns_name_isabsolute(name) == TRUE
528
529
 *
 * Ensures:
530
 *\li   'name' is not altered in any way.
531
 *
532
533
 *\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
534
 *
535
536
537
538
 *\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
539
 *
540
541
542
 *\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
543
 *
544
545
546
547
548
 *\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).
549
550
 *
 * Returns:
551
552
553
554
555
556
 *\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.
557
558
559
560
 */

isc_result_t
dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, isc_boolean_t recurse);
561
/*%<
562
563
564
 * Delete 'node' from the tree of trees.
 *
 * Notes:
565
566
 *\li   When 'node' is removed, if recurse is ISC_TRUE then all nodes
 *      in levels down from it are removed too.
567
568
 *
 * Requires:
569
570
 *\li   rbt is a valid rbt manager.
 *\li   node != NULL.
571
572
 *
 * Ensures:
573
574
 *\li   Does NOT ensure that any external references to nodes in the tree
 *      are unaffected by node joins.
575
 *
576
577
578
579
 *\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
580
 *              the node could can be found with dns_rbt_findnode when
581
 *              that function's empty_data_ok parameter is true.
582
 *
583
584
585
 *\li   If result is ISC_R_NOMEMORY or ISC_R_NOSPACE:
 *              The node was deleted, but the tree structure was not
 *              optimized.
586
587
 *
 * Returns:
588
589
590
 *\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.
591
592
 */

David Lawrence's avatar
David Lawrence committed
593
594
void
dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name);
595
/*%<
596
597
598
 * Convert the sequence of labels stored at 'node' into a 'name'.
 *
 * Notes:
599
600
 *\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
601
 *
602
603
604
 *\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.
605
 *
David Lawrence's avatar
David Lawrence committed
606
 * Requires:
607
 * \li  name->offsets == NULL
David Lawrence's avatar
David Lawrence committed
608
609
 *
 * Ensures:
610
 * \li  'name' is DNS_NAMEATTR_READONLY.
David Lawrence's avatar
David Lawrence committed
611
 *
612
613
 * \li  'name' will point directly to the labels stored after the
 *      dns_rbtnode_t struct.
David Lawrence's avatar
David Lawrence committed
614
 *
615
616
 * \li  'name' will have offsets that also point to the information stored
 *      as part of the node.
617
618
 */

619
620
isc_result_t
dns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name);
621
/*%<
622
623
624
 * Like dns_rbt_namefromnode, but returns the full name from the root.
 *
 * Notes:
625
626
627
 * \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.
628
629
 *
 * Requires:
630
631
 * \li  name != NULL
 * \li  name has a dedicated buffer.
632
633
 *
 * Returns:
634
635
636
 * \li  ISC_R_SUCCESS
 * \li  ISC_R_NOSPACE           (possible via dns_name_concatenate)
 * \li  DNS_R_NAMETOOLONG       (possible via dns_name_concatenate)
637
638
639
640
 */

char *
dns_rbt_formatnodename(dns_rbtnode_t *node, char *printname,
641
		       unsigned int size);
642
/*%<
643
644
645
 * Format the full name of a node for printing, using dns_name_format().
 *
 * Notes:
646
647
 * \li  'size' is the length of the printname buffer.  This should be
 *      DNS_NAME_FORMATSIZE or larger.
648
649
 *
 * Requires:
650
 * \li  node and printname are not NULL.
651
652
 *
 * Returns:
653
 * \li  The 'printname' pointer.
654
655
 */

656
657
unsigned int
dns_rbt_nodecount(dns_rbt_t *rbt);
658
/*%<
Andreas Gustafsson's avatar
Andreas Gustafsson committed
659
 * Obtain the number of nodes in the tree of trees.
660
661
 *
 * Requires:
662
 * \li  rbt is a valid rbt manager.
663
664
 */

665
size_t
666
667
668
669
670
671
dns_rbt_hashsize(dns_rbt_t *rbt);
/*%<
 * Obtain the current number of buckets in the 'rbt' hash table.
 *
 * Requires:
 * \li  rbt is a valid rbt manager.
672
673
 */

David Lawrence's avatar
David Lawrence committed
674
675
void
dns_rbt_destroy(dns_rbt_t **rbtp);
676
677
isc_result_t
dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum);
678
/*%<
679
 * Stop working with a red-black tree of trees.
680
681
682
683
684
685
 * 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.
686
 *
David Lawrence's avatar
David Lawrence committed
687
 * Requires:
688
 * \li  *rbt is a valid rbt manager.
David Lawrence's avatar
David Lawrence committed
689
 *
690
 * Ensures on ISC_R_SUCCESS:
691
 * \li  All space allocated by the RBT library has been returned.
David Lawrence's avatar
David Lawrence committed
692
 *
693
 * \li  *rbt is invalidated as an rbt manager.
694
695
 *
 * Returns:
696
697
 * \li  ISC_R_SUCCESS
 * \li  ISC_R_QUOTA if 'quantum' nodes have been destroyed.
698
699
 */

700
701
off_t
dns_rbt_serialize_align(off_t target);
702
703
704
705
706
707
708
709
710
/*%<
 * Align the provided integer to a pointer-size boundary.
 * This should be used if, during serialization of data to a will-be
 * mmap()ed file, a pointer alignment is needed for some data.
 */

isc_result_t
dns_rbt_serialize_tree(FILE *file, dns_rbt_t *rbt,
		       dns_rbtdatawriter_t datawriter,
711
		       void *writer_arg, off_t *offset);
712
713
714
715
716
717
718
/*%<
 * Write out the RBT structure and its data to a file.
 *
 * Notes:
 * \li  The file must be an actual file which allows seek() calls, so it cannot
 *      be a stream.  Returns ISC_R_INVALIDFILE if not.
 */
Tinderbox User's avatar
Tinderbox User committed
719

720
isc_result_t
721
722
dns_rbt_deserialize_tree(void *base_address, size_t filesize,
			 off_t header_offset, isc_mem_t *mctx,
723
724
			 dns_rbtdeleter_t deleter, void *deleter_arg,
			 dns_rbtdatafixer_t datafixer, void *fixer_arg,
725
726
727
728
729
730
731
732
733
734
			 dns_rbtnode_t **originp, dns_rbt_t **rbtp);
/*%<
 * Read a RBT structure and its data from a file.
 *
 * If 'originp' is not NULL, then it is pointed to the root node of the RBT.
 *
 * Notes:
 * \li  The file must be an actual file which allows seek() calls, so it cannot
 *      be a stream.  This condition is not checked in the code.
 */
Tinderbox User's avatar
Tinderbox User committed
735

David Lawrence's avatar
David Lawrence committed
736
void
737
738
dns_rbt_printtext(dns_rbt_t *rbt,
		  void (*data_printer)(FILE *, void *), FILE *f);
739
/*%<
David Lawrence's avatar
David Lawrence committed
740
 * Print an ASCII representation of the internal structure of the red-black
741
742
743
744
 * tree of trees to the passed stream.
 *
 * data_printer is a callback function that is called to print the data
 * in a node. It should print it to the passed FILE stream.
745
746
 *
 * Notes:
747
748
749
750
 * \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.
751
 */
David Lawrence's avatar
David Lawrence committed
752

753
void
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
dns_rbt_printdot(dns_rbt_t *rbt, isc_boolean_t show_pointers, FILE *f);
/*%<
 * Print a GraphViz dot representation of the internal structure of the
 * red-black tree of trees to the passed stream.
 *
 * If show_pointers is TRUE, pointers are also included in the generated
 * graph.
 *
 * Notes:
 * \li	The name stored at each node, along with the node's color is displayed.
 *	Then the down pointer, left and right pointers are displayed
 *	recursively in turn.  NULL left, right and down pointers are
 *	silently omitted.
 */

void
dns_rbt_printnodeinfo(dns_rbtnode_t *n, FILE *f);
771
772
/*%<
 * Print out various information about a node
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
 *
 * Requires:
 *\li	'n' is a valid pointer.
 *
 *\li	'f' points to a valid open FILE structure that allows writing.
 */


size_t
dns__rbt_getheight(dns_rbt_t *rbt);
/*%<
 * Return the maximum height of sub-root nodes found in the red-black
 * forest.
 *
 * The height of a node is defined as the number of nodes in the longest
 * path from the node to a leaf. For each subtree in the forest, this
 * function determines the height of its root node. Then it returns the
 * maximum such height in the forest.
 *
 * Note: This function exists for testing purposes. Non-test code must
 * not use it.
 *
 * Requires:
 * \li  rbt is a valid rbt manager.
 */

isc_boolean_t
dns__rbt_checkproperties(dns_rbt_t *rbt);
/*%<
 * Check red-black properties of the forest.
 *
 * Note: This function exists for testing purposes. Non-test code must
 * not use it.
 *
 * Requires:
 * \li  rbt is a valid rbt manager.
 */

size_t
dns__rbtnode_getdistance(dns_rbtnode_t *node);
/*%<
 * Return the distance (in nodes) from the node to its upper node of its
 * subtree. The root node has a distance of 1. A child of the root node
 * has a distance of 2.
817
 */
Tinderbox User's avatar
Tinderbox User committed
818

David Lawrence's avatar
David Lawrence committed
819
820
821
/*****
 ***** Chain Functions
 *****/
822
823
824

void
dns_rbtnodechain_init(dns_rbtnodechain_t *chain, isc_mem_t *mctx);
825
/*%<
826
827
828
 * Initialize 'chain'.
 *
 * Requires:
829
 *\li   'chain' is a valid pointer.
830
 *
831
 *\li   'mctx' is a valid memory context.
832
833
 *
 * Ensures:
834
 *\li   'chain' is suitable for use.
835
836
837
838
 */

void
dns_rbtnodechain_reset(dns_rbtnodechain_t *chain);
839
/*%<
840
841
842
843
 * Free any dynamic storage associated with 'chain', and then reinitialize
 * 'chain'.
 *
 * Requires:
844
 *\li   'chain' is a valid pointer.
845
846
 *
 * Ensures:
847
 *\li   'chain' is suitable for use, and uses no dynamic storage.
David Lawrence's avatar
David Lawrence committed
848
849
850
851
 */

void
dns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain);
852
/*%<
David Lawrence's avatar
David Lawrence committed
853
854
855
 * Free any dynamic storage associated with 'chain', and then invalidates it.
 *
 * Notes:
856
857
858
 *\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
859
860
 *
 * Requires:
861
 *\li   'chain' is a valid chain.
David Lawrence's avatar
David Lawrence committed
862
863
 *
 * Ensures:
864
 *\li   'chain' is no longer suitable for use, and uses no dynamic storage.
865
866
 */

867
isc_result_t
868
dns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name,
869
			 dns_name_t *origin, dns_rbtnode_t **node);
870
/*%<
871
 * Provide the name, origin and node to which the chain is currently pointed.
David Lawrence's avatar
David Lawrence committed
872
873
 *
 * Notes:
874
875
876
 *\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
877
878
 *
 * Requires:
879
 *\li   'chain' is a valid chain.
David Lawrence's avatar
David Lawrence committed
880
881
 *
 * Ensures:
882
883
884
885
886
 *\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.
887
 *
888
889
890
891
892
893
894
 *\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".)
895
 *
896
897
898
 *\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.
899
 *
900
901
 *
 * Returns:
902
903
904
 *\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
905
 */
906

907
isc_result_t
908
dns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
909
		       dns_name_t *name, dns_name_t *origin);
910
/*%<
David Lawrence's avatar
David Lawrence committed
911
912
913
 * Set the chain to the lexically first node in the tree of trees.
 *
 * Notes:
914
915
916
 *\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
917
918
 *
 * Requires:
919
920
 *\li   'chain' is a valid chain.
 *\li   'rbt' is a valid rbt manager.
David Lawrence's avatar
David Lawrence committed
921
922
 *
 * Ensures:
923
 *\li   The chain points to the very first node of the tree.
924
 *
925
926
 *\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
927
928
 *
 * Returns:
929
930
 *\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
931
932
 */

933
isc_result_t
934
dns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
935
		       dns_name_t *name, dns_name_t *origin);
936
/*%<
David Lawrence's avatar
David Lawrence committed
937
938
939
 * Set the chain to the lexically last node in the tree of trees.
 *
 * Requires:
940
941
 *\li   'chain' is a valid chain.
 *\li   'rbt' is a valid rbt manager.
David Lawrence's avatar
David Lawrence committed
942
943
 *
 * Ensures:
944
 *\li   The chain points to the very last node of the tree.
945
 *
946
947
 *\li   'name' and 'origin', if non-NULL, are set as described for
 *      dns_rbtnodechain_current.
David Lawrence's avatar
David Lawrence committed
948
949
 *
 * Returns:
950
951
952
 *\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
953
954
 */

955
isc_result_t
David Lawrence's avatar
David Lawrence committed
956
dns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name,
957
		      dns_name_t *origin);
958
/*%<
959
960
961
962
 * Adjusts chain to point the DNSSEC predecessor of the name to which it
 * is currently pointed.
 *
 * Requires:
963
964
965
966
967
 *\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.
968
969
 *
 * Ensures:
970
 *\li   The chain is pointed to the predecessor of its current target.
971
 *
972
973
 *\li   'name' and 'origin', if non-NULL, are set as described for
 *      dns_rbtnodechain_current.
974
 *
975
 *\li   'origin' is only if a new origin was found.
David Lawrence's avatar
David Lawrence committed
976
 *
977
 * Returns:
978
979
980
981
982
 *\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
983
984
 */

985
isc_result_t
David Lawrence's avatar
David Lawrence committed
986
dns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name,
987
		      dns_name_t *origin);
988
/*%<
989
990
991
992
 * Adjusts chain to point the DNSSEC successor of the name to which it
 * is currently pointed.
 *
 * Requires:
993
994
995
996
997
 *\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.
998
999
 *
 * Ensures:
1000
 *\li   The chain is pointed to the successor of its current target.
1001
 *
1002
1003
 *\li   'name' and 'origin', if non-NULL, are set as described for
 *      dns_rbtnodechain_current.
1004
 *
1005
 *\li   'origin' is only if a new origin was found.
David Lawrence's avatar
David Lawrence committed
1006
 *
1007
 * Returns:
1008
1009
1010
1011
1012
 *\li   #ISC_R_SUCCESS          The successor was found and 'name' was set.
 *\li   #DNS_R_NEWORIGIN                The successor was found with a different
 *                              origin and 'name' and 'origin' were set.
 *\li   #ISC_R_NOMORE           There was no successor.
 *\li   &lt;something_else>     Any error result from dns_name_concatenate.
David Lawrence's avatar
David Lawrence committed
1013
1014
 */

1015
1016
1017
1018
isc_result_t
dns_rbtnodechain_down(dns_rbtnodechain_t *chain, dns_name_t *name,
		      dns_name_t *origin);
/*%<
Francis Dupont's avatar
Francis Dupont committed
1019
 * Descend down if possible.
1020
1021
1022
1023
1024
1025
1026
1027
 */

isc_result_t
dns_rbtnodechain_nextflat(dns_rbtnodechain_t *chain, dns_name_t *name);
/*%<
 * Find the next node at the current depth in DNSSEC order.
 */

1028
1029
1030
1031
1032
1033
1034
1035
/*
 * Wrapper macros for manipulating the rbtnode reference counter:
 *   Since we selectively use isc_refcount_t for the reference counter of
 *   a rbtnode, operations on the counter depend on the actual type of it.
 *   The following macros provide a common interface to these operations,
 *   hiding the back-end.  The usage is the same as that of isc_refcount_xxx().
 */
#ifdef DNS_RBT_USEISCREFCOUNT
1036
#define dns_rbtnode_refinit(node, n)                            \
1037
1038
1039
	do {                                                    \
		isc_refcount_init(&(node)->references, (n));    \
	} while (0)
1040
#define dns_rbtnode_refdestroy(node)                            \
1041
1042
1043
	do {                                                    \
		isc_refcount_destroy(&(node)->references);      \
	} while (0)
Michael Graff's avatar