rbt.h 27.8 KB
Newer Older
David Lawrence's avatar
David Lawrence committed
1
/*
Bob Halley's avatar
Bob Halley committed
2
 * Copyright (C) 1999, 2000  Internet Software Consortium.
David Lawrence's avatar
David Lawrence committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 * 
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS
 * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE
 * CONSORTIUM 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.
 */

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

#include <isc/lang.h>
22
23
24

#include <dns/types.h>

Bob Halley's avatar
Bob Halley committed
25
26
ISC_LANG_BEGINDECLS

Bob Halley's avatar
Bob Halley committed
27
28
29
30
/*
 * Option values for dns_rbt_findnode() and dns_rbt_findname().
 * These are used to form a bitmask.
 */
31
#define DNS_RBTFIND_NOOPTIONS			0x00
Bob Halley's avatar
Bob Halley committed
32
33
#define DNS_RBTFIND_EMPTYDATA			0x01
#define DNS_RBTFIND_NOEXACT			0x02
34
#define DNS_RBTFIND_NOPREDECESSOR		0x04
Bob Halley's avatar
Bob Halley committed
35

36
37
38
39
40
41
/*
 * These should add up to 30.
 */
#define DNS_RBT_LOCKLENGTH			10
#define DNS_RBT_REFLENGTH			20

42
43
44
/*
 * 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
45
46
 * length structure, with the actual wire-format name and other data appended
 * appended to this structure.  Allocating a contiguous block of memory for
47
 * multiple dns_rbtnode structures will not work.
48
 */
49
typedef struct dns_rbtnode {
50
	struct dns_rbtnode *parent;
51
52
53
	struct dns_rbtnode *left;
	struct dns_rbtnode *right;
	struct dns_rbtnode *down;
54
	/*
55
56
57
58
59
60
61
	 * The following bitfields add up to a total bitwidth of 32.
	 * The range of values necessary for each item is indicated,
	 * but in the case of "attributes" the field is wider to accomodate
	 * possible future expansion.  "offsetlen" could be one bit
	 * narrower by always adjusting its value by 1 to find the real
	 * offsetlen, but doing so does not gain anything (except perhaps
	 * another bit for "attributes", which doesn't yet need any more).
62
63
64
	 *
	 * In each case below the "range" indicated is what's _necessary_ for
	 * the bitfield to hold, not what it actually _can_ hold.
65
	 */
66
67
68
69
70
71
72
	unsigned int is_root : 1;	/* range is 0..1 */
	unsigned int color : 1;		/* range is 0..1 */
	unsigned int find_callback : 1;	/* range is 0..1 */
	unsigned int attributes : 4;	/* range is 0..2 */
	unsigned int namelen : 8;	/* range is 1..255 */
	unsigned int offsetlen : 8;	/* range is 1..128 */
	unsigned int padbytes : 9;	/* range is 0..380 */
73
74
75
76
	/*
	 * These values are used in the RBT DB implementation.  The appropriate
	 * node lock must be held before accessing them.
	 */
77
	void *data;
Bob Halley's avatar
Bob Halley committed
78
	unsigned int dirty:1;
Bob Halley's avatar
Bob Halley committed
79
	unsigned int wild:1;
Bob Halley's avatar
Bob Halley committed
80
81
	unsigned int locknum:DNS_RBT_LOCKLENGTH;
	unsigned int references:DNS_RBT_REFLENGTH;
David Lawrence's avatar
David Lawrence committed
82
} dns_rbtnode_t;
83

84
typedef isc_result_t (*dns_rbtfindcallback_t)(dns_rbtnode_t *node,
85
86
87
					      dns_name_t *name,
					      void *callback_arg);

David Lawrence's avatar
David Lawrence committed
88
89
90
91
92
93
/*****
 *****	Chain Info
 *****/

/*
 * A chain is used to keep track of the sequence of nodes to reach any given
94
95
96
97
98
99
100
101
102
103
104
105
106
 * 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
 * change the path from the root to the node the chain has targetted.
David Lawrence's avatar
David Lawrence committed
107
108
 *
 * The dns_rbtnodechain_ functions _first, _last, _prev and _next all take
109
110
111
112
113
114
115
116
117
 * 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.
 *
118
119
120
121
122
123
124
125
126
127
128
129
 * NOTE WELL: the above rule means that when a chain points to the root of the
 * tree of trees and that root stores only the root label, ".", it means that
 * BOTH 'name' *and* 'origin' will be ".".  As a common operation on
 * 'name' and 'origin' is to dns_name_concatenate them after they have been
 * set, special care must be taken to not concatenate 'name' if it is
 * dns_name_isabsolute(), which is only true in this special circumstance.
 * The logic behind having both 'name' and 'origin' be "." had to do with
 * zone file dumping.  It is likely that dumping of "." will be handled
 * differently in the future and that the chain API will be changed such that
 * in the case of ".", only 'origin' will be "." and name will be set to
 * have zero labels.
 *
130
131
 * dns_rbtnodechain_current is similar to the _first, _last, _prev and _next
 * functions but additionally can provide the node to which the chain points.
David Lawrence's avatar
David Lawrence committed
132
133
 */

134
135
136
137
138
139
140
141
142
143
144
145
/*
 * For use in allocating space for the chain of ancestor nodes.
 *
 * The maximum number of ancestors is theoretically not limited by the
 * data tree.  This initial value of 24 ancestors would be able to scan
 * the full height of a single level of 16,777,216 nodes, more than double
 * the current size of .com.
 */
#define DNS_RBT_ANCESTORBLOCK 24

/*
 * The number of level blocks to allocate at a time.  Currently the maximum
146
147
148
149
150
151
 * number of levels is allocated directly in the structure, but future
 * revisions of this code might treat levels like ancestors -- that is, 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.
152
153
154
155
 */
#define DNS_RBT_LEVELBLOCK 254

typedef struct dns_rbtnodechain {
156
	unsigned int		magic;
157
	isc_mem_t *		mctx;
158
159
160
161
162
163
	/*
	 * The terminal node of the chain.  It is not in levels[] or
	 * ancestors[].  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().
	 */
164
	dns_rbtnode_t *		end;
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
	dns_rbtnode_t **	ancestors;
	/*
	 * ancestor_block avoids doing any memory allocation (a MP
	 * bottleneck) in 99%+ of the real-world cases.
	 */
	dns_rbtnode_t *		ancestor_block[DNS_RBT_ANCESTORBLOCK];
	unsigned int		ancestor_count;
	unsigned int		ancestor_maxitems;
	/*
	 * 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];
182
	/*
183
184
185
186
187
188
	 * 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.
189
	 */
190
	unsigned int		level_count;
191
	/*
192
193
194
195
196
	 * 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.
197
198
	 */
	unsigned int		level_matches;
199
200
} dns_rbtnodechain_t;

David Lawrence's avatar
David Lawrence committed
201
202
203
/*****
 ***** Public interfaces.
 *****/
204

205
isc_result_t
David Lawrence's avatar
David Lawrence committed
206
207
dns_rbt_create(isc_mem_t *mctx, void (*deleter)(void *, void *),
	       void *deleter_arg, dns_rbt_t **rbtp);
David Lawrence's avatar
David Lawrence committed
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
/*
 * Initialize a red-black tree of trees.
 *
 * Notes:
 *	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.  
 *
 * Requires:
 * 	mctx is a pointer to a valid memory context.
 *	rbtp != NULL && *rbtp == NULL
 *	arg == NULL iff deleter == NULL
 *
 * Ensures:
224
 *	If result is ISC_R_SUCCESS:
David Lawrence's avatar
David Lawrence committed
225
226
227
228
229
230
 *		*rbtp points to a valid red-black tree manager
 *
 *	If result is failure:
 *		*rbtp does not point to a valid red-black tree manager.
 *
 * Returns:
231
232
 *	ISC_R_SUCCESS	Success
 *	ISC_R_NOMEMORY	Resource limit: Out of Memory
David Lawrence's avatar
David Lawrence committed
233
234
 */

235
isc_result_t
David Lawrence's avatar
David Lawrence committed
236
dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data);
237
238
239
240
241
242
/*
 * Add 'name' to the tree of trees, associated with 'data'.
 *
 * Notes:
 *	'data' is never required to be non-NULL, but specifying it
 *	when the name is added is faster than searching for 'name'
David Lawrence's avatar
David Lawrence committed
243
244
245
246
 *	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.
247
248
 *
 * Requires:
David Lawrence's avatar
David Lawrence committed
249
 *	rbt is a valid rbt manager.
250
251
252
253
254
 *	dns_name_isabsolute(name) == TRUE
 *
 * Ensures:
 *	'name' is not altered in any way.
 *
David Lawrence's avatar
David Lawrence committed
255
256
257
 *	Any external references to nodes in the tree are unaffected by
 *	node splits that are necessary to insert the new name.
 *
258
 *	If result is ISC_R_SUCCESS:
259
260
 *		'name' is findable in the red/black tree of trees in O(log N).
 *
David Lawrence's avatar
David Lawrence committed
261
262
 *		The data pointer of the node for 'name' is set to 'data'.
 *
263
 *	If result is ISC_R_EXISTS or ISC_R_NOSPACE:
David Lawrence's avatar
David Lawrence committed
264
265
 *		The tree of trees is unaltered.
 *
266
 *	If result is ISC_R_NOMEMORY:
David Lawrence's avatar
David Lawrence committed
267
268
 *		No guarantees.
 *
269
 * Returns:
270
271
272
273
 *	ISC_R_SUCCESS	Success
 *	ISC_R_EXISTS	The name already exists with associated data.
 *	ISC_R_NOSPACE 	The name had more logical labels than are allowed.
 *	ISC_R_NOMEMORY	Resource Limit: Out of Memory
274
275
 */

276
isc_result_t
David Lawrence's avatar
David Lawrence committed
277
dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep);
David Lawrence's avatar
David Lawrence committed
278

279
/*
David Lawrence's avatar
David Lawrence committed
280
 * Just like dns_rbt_addname, but returns the address of the node.
281
282
283
284
285
 *
 * Requires:
 *	rbt is a valid rbt structure.
 *	dns_name_isabsolute(name) == TRUE
 *	nodep != NULL && *nodep == NULL
David Lawrence's avatar
David Lawrence committed
286
287
288
289
290
291
292
 *
 * Ensures:
 *	'name' is not altered in any way.
 *
 *	Any external references to nodes in the tree are unaffected by
 *	node splits that are necessary to insert the new name.
 *
293
 *	If result is ISC_R_SUCCESS:
David Lawrence's avatar
David Lawrence committed
294
295
296
297
 *		'name' is findable in the red/black tree of trees in O(log N).
 *
 *		*nodep is the node that was added for 'name'.
 *
298
 *	If result is ISC_R_EXISTS:
David Lawrence's avatar
David Lawrence committed
299
300
301
302
 *		The tree of trees is unaltered.
 *
 *		*nodep is the existing node for 'name'.
 *
303
 *	If result is ISC_R_NOMEMORY:
David Lawrence's avatar
David Lawrence committed
304
305
306
 *		No guarantees.
 *
 * Returns:
307
308
309
 *	ISC_R_SUCCESS	Success
 *	ISC_R_EXISTS	The name already exists, possibly without data.
 *	ISC_R_NOMEMORY	Resource Limit: Out of Memory
David Lawrence's avatar
David Lawrence committed
310
311
 */

312
isc_result_t
Bob Halley's avatar
Bob Halley committed
313
dns_rbt_findname(dns_rbt_t *rbt, dns_name_t *name, unsigned int options,
David Lawrence's avatar
David Lawrence committed
314
		 dns_name_t *foundname, void **data);
David Lawrence's avatar
David Lawrence committed
315
316
317
318
/*
 * Get the data pointer associated with 'name'.
 *
 * Notes:
319
320
321
 *	When DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is
 *      returned (also subject to DNS_RBTFIND_EMPTYDATA), even when there is
 *	an exact match in the tree.
David Lawrence's avatar
David Lawrence committed
322
 *
Bob Halley's avatar
Bob Halley committed
323
 *      A node that has no data is considered not to exist for this function,
324
 *      unless the DNS_RBTFIND_EMPTYDATA option is set.
Bob Halley's avatar
Bob Halley committed
325
 *
David Lawrence's avatar
David Lawrence committed
326
327
328
329
330
331
332
333
 * Requires:
 *	rbt is a valid rbt manager.
 *	dns_name_isabsolute(name) == TRUE
 *	data != NULL && *data == NULL
 *
 * Ensures:
 *	'name' and the tree are not altered in any way.
 *
334
 *	If result is ISC_R_SUCCESS:
David Lawrence's avatar
David Lawrence committed
335
336
337
338
339
340
 *		*data is the data associated with 'name'.
 *
 *	If result is DNS_R_PARTIALMATCH:
 *		*data is the data associated with the deepest superdomain
 * 		of 'name' which has data.
 *
341
 *	If result is ISC_R_NOTFOUND:
David Lawrence's avatar
David Lawrence committed
342
343
344
 *		Neither the name nor a superdomain was found with data.
 *
 * Returns:
345
 *	ISC_R_SUCCESS		Success
David Lawrence's avatar
David Lawrence committed
346
 *	DNS_R_PARTIALMATCH	Superdomain found with data
347
348
 *	ISC_R_NOTFOUND		No match
 *	ISC_R_NOSPACE		Concatenating nodes to form foundname failed
David Lawrence's avatar
David Lawrence committed
349
350
 */

351
isc_result_t
352
353
dns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname,
		 dns_rbtnode_t **node, dns_rbtnodechain_t *chain,
Bob Halley's avatar
Bob Halley committed
354
		 unsigned int options, dns_rbtfindcallback_t callback,
355
		 void *callback_arg);
David Lawrence's avatar
David Lawrence committed
356
357
358
359
/*
 * Find the node for 'name'.
 *
 * Notes:
360
361
 *	It is _not_ required that the node associated with 'name' has a
 *	non-NULL data pointer for an exact match.  A partial match must
Bob Halley's avatar
Bob Halley committed
362
 *	have associated data, unless the DNS_RBTFIND_EMPTYDATA option is set.
David Lawrence's avatar
David Lawrence committed
363
 *
364
 *	If the chain parameter is non-NULL, then the path through the tree
365
366
367
368
 *	to the DNSSEC predecessor of the searched for name is maintained,
 *	unless the DNS_RBT_NOPREDECESSOR or DNS_RBT_NOEXACT option is used.
 *	(For more details on those options, see below.)
 *
369
370
 *	If there is no predecessor, then the chain will point to nowhere, as
 *	indicated by chain->end being NULL or dns_rbtnodechain_current
371
 *	returning ISC_R_NOTFOUND.  Note that in a normal Internet DNS RBT
372
373
374
375
 *	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.
376
377
 *
 *	Within the chain structure, 'ancestors' will point
David Lawrence's avatar
David Lawrence committed
378
379
380
381
382
383
384
385
386
387
 *	to each successive node encountered in the search, with the root
 *	of each level searched indicated by a NULL.  ancestor_count
 *	indicates how many node pointers are in the ancestor list.  The
 *	'levels' member of the structure holds the root node of each level
 *	except the first; it corresponds with the NULL pointers in
 *	'ancestors' (except the first).  That is, for the [n+1]'th NULL
 *	'ancestors' pointer, the [n]'th 'levels' pointer is the node with
 *	the down pointer to the next level.  That node is not stored
 *	at all in the 'ancestors' list.
 *
388
389
390
391
392
393
394
395
396
397
398
399
400
 *	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,
 *	the distinction arrising because multiple labels from a name can be
 *	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[].
 *
 *	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.
 *
David Lawrence's avatar
David Lawrence committed
401
 *	If any space was allocated to hold 'ancestors' in the chain,
402
403
 *	the 'ancestor_maxitems' member will be greater than
 *	DNS_RBT_ANCESTORBLOCK and will indicate how many ancestors
David Lawrence's avatar
David Lawrence committed
404
405
406
 *	could have been stored; the amount to be freed from the rbt->mctx
 *	is ancestor_maxitems * sizeof(dns_rbtnode_t *).
 *
407
 *	When DNS_RBTFIND_NOEXACT is set, the closest matching superdomain is
Bob Halley's avatar
Bob Halley committed
408
 *      returned (also subject to DNS_RBTFIND_EMPTYDATA), even when
409
410
411
412
413
414
415
416
417
418
419
420
421
422
 *      there is an exact match in the tree.  In this case, the chain
 *	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 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.
 *
 *      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
423
 *
David Lawrence's avatar
David Lawrence committed
424
425
 * Requires:
 *	rbt is a valid rbt manager.
426
427
428
429
 *	dns_name_isabsolute(name) == TRUE.
 *	node != NULL && *node == NULL.
 *	DNS_RBTFIND_NOEXACT and DNS_RBTFIND_NOPREDECESSOR are mutally
 *		exclusive.
David Lawrence's avatar
David Lawrence committed
430
431
432
433
 *
 * Ensures:
 *	'name' and the tree are not altered in any way.
 *
434
 *	If result is ISC_R_SUCCESS:
David Lawrence's avatar
David Lawrence committed
435
436
 *		*node is the terminal node for 'name'.
 *
437
438
439
440
441
442
 *		'foundname' and 'name' represent the same name (though not
 *		the same memory).
 *
 *		'chain' points to the DNSSEC predecessor, if any, of 'name'.
 *
 *		chain->level_matches and chain->level_count are equal.
443
 *
David Lawrence's avatar
David Lawrence committed
444
445
446
447
 * 	If result is DNS_R_PARTIALMATCH:
 *		*node is the data associated with the deepest superdomain
 * 		of 'name' which has data.
 *
448
 *		'foundname' is the name of deepest superdomain (which has
Bob Halley's avatar
Bob Halley committed
449
 *		data, unless the DNS_RBTFIND_EMPTYDATA option is set).
450
451
 *
 *		'chain' points to the DNSSEC predecessor, if any, of 'name'.
David Lawrence's avatar
David Lawrence committed
452
 *
453
 *	If result is ISC_R_NOTFOUND:
454
 *		Neither the name nor a superdomain was found.  *node is NULL.
David Lawrence's avatar
David Lawrence committed
455
 *
456
457
458
 *		'chain' points to the DNSSEC predecessor, if any, of 'name'.
 *
 *		chain->level_matches is 0.
David Lawrence's avatar
David Lawrence committed
459
 *
460
 *	If result is ISC_R_NOMEMORY:
David Lawrence's avatar
David Lawrence committed
461
462
463
 *		The function could not complete because memory could not
 *		be allocated to maintain the chain.  However, it
 *		is possible that some memory was allocated;
464
465
 *		the chain's ancestor_maxitems will be greater than
 *		DNS_RBT_ANCESTORBLOCK if so.
David Lawrence's avatar
David Lawrence committed
466
467
 *
 * Returns:
468
 *	ISC_R_SUCCESS		Success
David Lawrence's avatar
David Lawrence committed
469
 *	DNS_R_PARTIALMATCH	Superdomain found with data
470
471
472
 *	ISC_R_NOTFOUND		No match, or superdomain with no data
 *	ISC_R_NOMEMORY		Resource Limit: Out of Memory building chain
 *	ISC_R_NOSPACE 		Concatenating nodes to form foundname failed
473
474
 */

475
isc_result_t
David Lawrence's avatar
David Lawrence committed
476
dns_rbt_deletename(dns_rbt_t *rbt, dns_name_t *name, isc_boolean_t recurse);
477
478
479
480
/*
 * Delete 'name' from the tree of trees.
 *
 * Notes:
David Lawrence's avatar
David Lawrence committed
481
 *	When 'name' is removed, if recurse is ISC_TRUE then all of its
482
 *      subnames are removed too.
483
484
 *
 * Requires:
David Lawrence's avatar
David Lawrence committed
485
 *	rbt is a valid rbt manager.
486
487
488
489
490
 *	dns_name_isabsolute(name) == TRUE
 *
 * Ensures:
 *	'name' is not altered in any way.
 *
David Lawrence's avatar
David Lawrence committed
491
492
493
 *	Does NOT ensure that any external references to nodes in the tree
 *	are unaffected by node joins.
 *
494
 *	If result is ISC_R_SUCCESS:
David Lawrence's avatar
David Lawrence committed
495
496
497
498
 *		'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).
 *
499
 *	If result is ISC_R_NOTFOUND:
David Lawrence's avatar
David Lawrence committed
500
501
502
 *		'name' does not appear in the tree with data, because
 *		it did not appear in the tree before the function was called.
 *
503
504
505
506
507
 *	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).
508
509
 *
 * Returns:
510
511
 *	ISC_R_SUCCESS	Success
 *	ISC_R_NOTFOUND	No match
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
 *	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.
 */

isc_result_t
dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, isc_boolean_t recurse);
/*
 * Delete 'node' from the tree of trees.
 *
 * Notes:
 *	When 'node' is removed, if recurse is ISC_TRUE then all nodes
 *	in levels down from it are removed too.
 *
 * Requires:
 *	rbt is a valid rbt manager.
 *	node != NULL.
 *
 * Ensures:
 *	Does NOT ensure that any external references to nodes in the tree
 *	are unaffected by node joins.
 *
 *	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
 *		the node could can be found with dns_rbt_findnode whem
 *		that function's empty_data_ok parameter is true.
 *
 *	If result is ISC_R_NOMEMORY or ISC_R_NOSPACE:
 *		The node was deleted, but the tree structure was not
 *		optimized.
 *
 * Returns:
 *	ISC_R_SUCCESS	Success
 *	ISC_R_NOMEMORY	Resource Limit: Out of Memory when joining nodes.
 *	ISC_R_NOSPACE	dns_name_concatenate failed when joining nodes.
550
551
 */

David Lawrence's avatar
David Lawrence committed
552
553
void
dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name);
554
555
556
557
/*
 * Convert the sequence of labels stored at 'node' into a 'name'.
 *
 * Notes:
David Lawrence's avatar
David Lawrence committed
558
559
560
 *	This function does not return the full name, from the root, but
 *	just the labels at the indicated node.
 *
561
562
563
564
 *	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.
 *
David Lawrence's avatar
David Lawrence committed
565
566
567
568
569
570
571
572
573
574
575
 * Requires:
 *	name->offsets == NULL
 *
 * Ensures:
 *	'name' is DNS_NAMEATTR_READONLY.
 *
 *	'name' will point directly to the labels stored after the
 *	dns_rbtnode_t struct.
 *
 *	'name' will have offsets that also point to the information stored
 *	as part of the node.
576
577
 */

David Lawrence's avatar
David Lawrence committed
578
579
void
dns_rbt_destroy(dns_rbt_t **rbtp);
580
/*
David Lawrence's avatar
David Lawrence committed
581
 * Stop working with a red-black tree of trees.
582
 *
David Lawrence's avatar
David Lawrence committed
583
584
585
586
587
588
589
 * Requires:
 * 	*rbt is a valid rbt manager.
 *
 * Ensures:
 *	All space allocated by the RBT library has been returned.
 *
 *	*rbt is invalidated as an rbt manager.
590
591
 */

David Lawrence's avatar
David Lawrence committed
592
593
void
dns_rbt_printall(dns_rbt_t *rbt);
594
/*
David Lawrence's avatar
David Lawrence committed
595
596
 * Print an ASCII representation of the internal structure of the red-black
 * tree of trees.
597
598
 *
 * Notes:
David Lawrence's avatar
David Lawrence committed
599
600
601
602
 *	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.
603
 */
David Lawrence's avatar
David Lawrence committed
604

David Lawrence's avatar
David Lawrence committed
605
606
607
/*****
 ***** Chain Functions
 *****/
608
609
610
611
612
613
614
615
616
617
618
619

void
dns_rbtnodechain_init(dns_rbtnodechain_t *chain, isc_mem_t *mctx);
/*
 * Initialize 'chain'.
 *
 * Requires:
 *	'chain' is a valid pointer.
 *
 *	'mctx' is a valid memory context.
 *
 * Ensures:
David Lawrence's avatar
David Lawrence committed
620
 *	'chain' is suitable for use.
621
622
623
624
625
626
627
628
629
630
631
632
 */

void
dns_rbtnodechain_reset(dns_rbtnodechain_t *chain);
/*
 * Free any dynamic storage associated with 'chain', and then reinitialize
 * 'chain'.
 *
 * Requires:
 *	'chain' is a valid pointer.
 *
 * Ensures:
David Lawrence's avatar
David Lawrence committed
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
 *	'chain' is suitable for use, and uses no dynamic storage.
 */

void
dns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain);
/*
 * Free any dynamic storage associated with 'chain', and then invalidates it.
 *
 * Notes:
 * 	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).
 *
 * Requires:
 *	'chain' is a valid chain.
 *
 * Ensures:
 *	'chain' is no longer suitable for use, and uses no dynamic storage.
651
652
 */

653
isc_result_t
654
655
dns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name,
			 dns_name_t *origin, dns_rbtnode_t **node);
David Lawrence's avatar
David Lawrence committed
656
/*
657
 * Provide the name, origin and node to which the chain is currently pointed.
David Lawrence's avatar
David Lawrence committed
658
659
 *
 * Notes:
660
661
662
 *	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
663
664
665
666
667
 *
 * Requires:
 *	'chain' is a valid chain.
 *
 * Ensures:
668
669
670
671
 *	'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
672
 *	dns_rbt_findnode, then '*node' is NULL and ISC_R_NOTFOUND is returned.
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
 *
 *	'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".)
 *
 *	'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.
 *	
 *
 * Returns:
688
689
 *	ISC_R_SUCCESS		name, origin & node were successfully set.
 *	ISC_R_NOTFOUND		The chain does not point to any node.
690
 *	<something_else>	Any error return from dns_name_concatenate.
David Lawrence's avatar
David Lawrence committed
691
 */
692

693
isc_result_t
694
695
dns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
		       dns_name_t *name, dns_name_t *origin);
David Lawrence's avatar
David Lawrence committed
696
697
698
699
700
/*
 * Set the chain to the lexically first node in the tree of trees.
 *
 * Notes:
 *	By the definition of ordering for DNS names, the root of the tree of
701
702
 *	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
703
704
705
706
707
708
 *
 * Requires:
 *	'chain' is a valid chain.
 *	'rbt' is a valid rbt manager.
 *
 * Ensures:
709
710
711
712
 *	The chain points to the very first node of the tree.
 *
 *	'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
713
714
 *
 * Returns:
715
716
 *	DNS_R_NEWORIGIN		The name & origin were successfully set.
 *	<something_else>	Any error result from dns_rbtnodechain_current.
David Lawrence's avatar
David Lawrence committed
717
718
 */

719
isc_result_t
720
721
dns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
		       dns_name_t *name, dns_name_t *origin);
David Lawrence's avatar
David Lawrence committed
722
723
724
725
726
727
728
729
/*
 * Set the chain to the lexically last node in the tree of trees.
 *
 * Requires:
 *	'chain' is a valid chain.
 *	'rbt' is a valid rbt manager.
 *
 * Ensures:
730
731
732
733
 *	The chain points to the very last node of the tree.
 *
 *	'name' and 'origin', if non-NULL, are set as described for
 *	dns_rbtnodechain_current.
David Lawrence's avatar
David Lawrence committed
734
735
 *
 * Returns:
736
 *	DNS_R_NEWORIGIN		The name & origin were successfully set.
737
 *	ISC_R_NOMEMORY		Resource Limit: Out of Memory building chain.
738
 *	<something_else>	Any error result from dns_name_concatenate.
David Lawrence's avatar
David Lawrence committed
739
740
 */

741
isc_result_t
David Lawrence's avatar
David Lawrence committed
742
743
744
dns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name,
		      dns_name_t *origin);
/*
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
 * Adjusts chain to point the DNSSEC predecessor of the name to which it
 * is currently pointed.
 *
 * Requires:
 *	'chain' is a valid chain.
 *	'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.
 *
 * Ensures:
 *	The chain is pointed to the predecessor of its current target.
 *
 *	'name' and 'origin', if non-NULL, are set as described for
 *	dns_rbtnodechain_current.
 *
 *	'origin' is only if a new origin was found.
David Lawrence's avatar
David Lawrence committed
762
 *
763
 * Returns:
764
 *	ISC_R_SUCCESS		The predecessor was found and 'name' was set.
765
766
 *	DNS_R_NEWORIGIN		The predecessor was found with a different
 *				origin and 'name' and 'origin' were set.
767
 *	ISC_R_NOMORE		There was no predecessor.
768
 *	<something_else>	Any error result from dns_rbtnodechain_current.
David Lawrence's avatar
David Lawrence committed
769
770
 */

771
isc_result_t
David Lawrence's avatar
David Lawrence committed
772
773
774
dns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name,
		      dns_name_t *origin);
/*
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
 * Adjusts chain to point the DNSSEC successor of the name to which it
 * is currently pointed.
 *
 * Requires:
 *	'chain' is a valid chain.
 *	'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.
 *
 * Ensures:
 *	The chain is pointed to the successor of its current target.
 *
 *	'name' and 'origin', if non-NULL, are set as described for
 *	dns_rbtnodechain_current.
 *
 *	'origin' is only if a new origin was found.
David Lawrence's avatar
David Lawrence committed
792
 *
793
 * Returns:
794
 *	ISC_R_SUCCESS		The successor was found and 'name' was set.
795
796
 *	DNS_R_NEWORIGIN		The successor was found with a different
 *				origin and 'name' and 'origin' were set.
797
 *	ISC_R_NOMORE		There was no successor.
798
 *	<something_else>	Any error result from dns_name_concatenate.
David Lawrence's avatar
David Lawrence committed
799
800
 */

Bob Halley's avatar
Bob Halley committed
801
802
ISC_LANG_ENDDECLS

Bob Halley's avatar
lint    
Bob Halley committed
803
#endif /* DNS_RBT_H */