1*00b67f09SDavid van Moolenbroek /* $NetBSD: rbt.c,v 1.10 2015/07/08 17:28:59 christos Exp $ */
2*00b67f09SDavid van Moolenbroek
3*00b67f09SDavid van Moolenbroek /*
4*00b67f09SDavid van Moolenbroek * Copyright (C) 2004, 2005, 2007-2009, 2011-2015 Internet Systems Consortium, Inc. ("ISC")
5*00b67f09SDavid van Moolenbroek * Copyright (C) 1999-2003 Internet Software Consortium.
6*00b67f09SDavid van Moolenbroek *
7*00b67f09SDavid van Moolenbroek * Permission to use, copy, modify, and/or distribute this software for any
8*00b67f09SDavid van Moolenbroek * purpose with or without fee is hereby granted, provided that the above
9*00b67f09SDavid van Moolenbroek * copyright notice and this permission notice appear in all copies.
10*00b67f09SDavid van Moolenbroek *
11*00b67f09SDavid van Moolenbroek * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
12*00b67f09SDavid van Moolenbroek * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
13*00b67f09SDavid van Moolenbroek * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
14*00b67f09SDavid van Moolenbroek * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
15*00b67f09SDavid van Moolenbroek * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
16*00b67f09SDavid van Moolenbroek * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
17*00b67f09SDavid van Moolenbroek * PERFORMANCE OF THIS SOFTWARE.
18*00b67f09SDavid van Moolenbroek */
19*00b67f09SDavid van Moolenbroek
20*00b67f09SDavid van Moolenbroek /*! \file */
21*00b67f09SDavid van Moolenbroek
22*00b67f09SDavid van Moolenbroek /* Principal Authors: DCL */
23*00b67f09SDavid van Moolenbroek
24*00b67f09SDavid van Moolenbroek #include <config.h>
25*00b67f09SDavid van Moolenbroek
26*00b67f09SDavid van Moolenbroek #include <sys/stat.h>
27*00b67f09SDavid van Moolenbroek #ifdef HAVE_INTTYPES_H
28*00b67f09SDavid van Moolenbroek #include <inttypes.h> /* uintptr_t */
29*00b67f09SDavid van Moolenbroek #endif
30*00b67f09SDavid van Moolenbroek
31*00b67f09SDavid van Moolenbroek #include <isc/crc64.h>
32*00b67f09SDavid van Moolenbroek #include <isc/file.h>
33*00b67f09SDavid van Moolenbroek #include <isc/hex.h>
34*00b67f09SDavid van Moolenbroek #include <isc/mem.h>
35*00b67f09SDavid van Moolenbroek #include <isc/platform.h>
36*00b67f09SDavid van Moolenbroek #include <isc/print.h>
37*00b67f09SDavid van Moolenbroek #include <isc/refcount.h>
38*00b67f09SDavid van Moolenbroek #include <isc/socket.h>
39*00b67f09SDavid van Moolenbroek #include <isc/stdio.h>
40*00b67f09SDavid van Moolenbroek #include <isc/string.h>
41*00b67f09SDavid van Moolenbroek #include <isc/util.h>
42*00b67f09SDavid van Moolenbroek
43*00b67f09SDavid van Moolenbroek /*%
44*00b67f09SDavid van Moolenbroek * This define is so dns/name.h (included by dns/fixedname.h) uses more
45*00b67f09SDavid van Moolenbroek * efficient macro calls instead of functions for a few operations.
46*00b67f09SDavid van Moolenbroek */
47*00b67f09SDavid van Moolenbroek #define DNS_NAME_USEINLINE 1
48*00b67f09SDavid van Moolenbroek
49*00b67f09SDavid van Moolenbroek #include <dns/fixedname.h>
50*00b67f09SDavid van Moolenbroek #include <dns/log.h>
51*00b67f09SDavid van Moolenbroek #include <dns/rbt.h>
52*00b67f09SDavid van Moolenbroek #include <dns/result.h>
53*00b67f09SDavid van Moolenbroek #include <dns/version.h>
54*00b67f09SDavid van Moolenbroek
55*00b67f09SDavid van Moolenbroek #include <unistd.h>
56*00b67f09SDavid van Moolenbroek
57*00b67f09SDavid van Moolenbroek #define CHECK(x) \
58*00b67f09SDavid van Moolenbroek do { \
59*00b67f09SDavid van Moolenbroek result = (x); \
60*00b67f09SDavid van Moolenbroek if (result != ISC_R_SUCCESS) \
61*00b67f09SDavid van Moolenbroek goto cleanup; \
62*00b67f09SDavid van Moolenbroek } while (/*CONSTCOND*/0)
63*00b67f09SDavid van Moolenbroek
64*00b67f09SDavid van Moolenbroek #define RBT_MAGIC ISC_MAGIC('R', 'B', 'T', '+')
65*00b67f09SDavid van Moolenbroek #define VALID_RBT(rbt) ISC_MAGIC_VALID(rbt, RBT_MAGIC)
66*00b67f09SDavid van Moolenbroek
67*00b67f09SDavid van Moolenbroek /*
68*00b67f09SDavid van Moolenbroek * XXXDCL Since parent pointers were added in again, I could remove all of the
69*00b67f09SDavid van Moolenbroek * chain junk, and replace with dns_rbt_firstnode, _previousnode, _nextnode,
70*00b67f09SDavid van Moolenbroek * _lastnode. This would involve pretty major change to the API.
71*00b67f09SDavid van Moolenbroek */
72*00b67f09SDavid van Moolenbroek #define CHAIN_MAGIC ISC_MAGIC('0', '-', '0', '-')
73*00b67f09SDavid van Moolenbroek #define VALID_CHAIN(chain) ISC_MAGIC_VALID(chain, CHAIN_MAGIC)
74*00b67f09SDavid van Moolenbroek
75*00b67f09SDavid van Moolenbroek #define RBT_HASH_SIZE 64
76*00b67f09SDavid van Moolenbroek
77*00b67f09SDavid van Moolenbroek #ifdef RBT_MEM_TEST
78*00b67f09SDavid van Moolenbroek #undef RBT_HASH_SIZE
79*00b67f09SDavid van Moolenbroek #define RBT_HASH_SIZE 2 /*%< To give the reallocation code a workout. */
80*00b67f09SDavid van Moolenbroek #endif
81*00b67f09SDavid van Moolenbroek
82*00b67f09SDavid van Moolenbroek struct dns_rbt {
83*00b67f09SDavid van Moolenbroek unsigned int magic;
84*00b67f09SDavid van Moolenbroek isc_mem_t * mctx;
85*00b67f09SDavid van Moolenbroek dns_rbtnode_t * root;
86*00b67f09SDavid van Moolenbroek void (*data_deleter)(void *, void *);
87*00b67f09SDavid van Moolenbroek void * deleter_arg;
88*00b67f09SDavid van Moolenbroek unsigned int nodecount;
89*00b67f09SDavid van Moolenbroek unsigned int hashsize;
90*00b67f09SDavid van Moolenbroek dns_rbtnode_t ** hashtable;
91*00b67f09SDavid van Moolenbroek void * mmap_location;
92*00b67f09SDavid van Moolenbroek };
93*00b67f09SDavid van Moolenbroek
94*00b67f09SDavid van Moolenbroek #define RED 0
95*00b67f09SDavid van Moolenbroek #define BLACK 1
96*00b67f09SDavid van Moolenbroek
97*00b67f09SDavid van Moolenbroek /*
98*00b67f09SDavid van Moolenbroek * This is the header for map-format RBT images. It is populated,
99*00b67f09SDavid van Moolenbroek * and then written, as the LAST thing done to the file before returning.
100*00b67f09SDavid van Moolenbroek * Writing this last (with zeros in the header area initially) will ensure
101*00b67f09SDavid van Moolenbroek * that the header is only valid when the RBT image is also valid.
102*00b67f09SDavid van Moolenbroek */
103*00b67f09SDavid van Moolenbroek typedef struct file_header file_header_t;
104*00b67f09SDavid van Moolenbroek
105*00b67f09SDavid van Moolenbroek /* Pad to 32 bytes */
106*00b67f09SDavid van Moolenbroek static char FILE_VERSION[32] = "\0";
107*00b67f09SDavid van Moolenbroek
108*00b67f09SDavid van Moolenbroek /* Header length, always the same size regardless of structure size */
109*00b67f09SDavid van Moolenbroek #define HEADER_LENGTH 1024
110*00b67f09SDavid van Moolenbroek
111*00b67f09SDavid van Moolenbroek struct file_header {
112*00b67f09SDavid van Moolenbroek char version1[32];
113*00b67f09SDavid van Moolenbroek isc_uint64_t first_node_offset; /* usually 1024 */
114*00b67f09SDavid van Moolenbroek /*
115*00b67f09SDavid van Moolenbroek * information about the system on which the map file was generated
116*00b67f09SDavid van Moolenbroek * will be used to tell if we can load the map file or not
117*00b67f09SDavid van Moolenbroek */
118*00b67f09SDavid van Moolenbroek isc_uint32_t ptrsize;
119*00b67f09SDavid van Moolenbroek unsigned int bigendian:1; /* big or little endian system */
120*00b67f09SDavid van Moolenbroek unsigned int rdataset_fixed:1; /* compiled with --enable-rrset-fixed */
121*00b67f09SDavid van Moolenbroek unsigned int nodecount; /* shadow from rbt structure */
122*00b67f09SDavid van Moolenbroek isc_uint64_t crc;
123*00b67f09SDavid van Moolenbroek char version2[32]; /* repeated; must match version1 */
124*00b67f09SDavid van Moolenbroek };
125*00b67f09SDavid van Moolenbroek
126*00b67f09SDavid van Moolenbroek /*
127*00b67f09SDavid van Moolenbroek * The following declarations are for the serialization of an RBT:
128*00b67f09SDavid van Moolenbroek *
129*00b67f09SDavid van Moolenbroek * step one: write out a zeroed header of 1024 bytes
130*00b67f09SDavid van Moolenbroek * step two: walk the tree in a depth-first, left-right-down order, writing
131*00b67f09SDavid van Moolenbroek * out the nodes, reserving space as we go, correcting addresses to point
132*00b67f09SDavid van Moolenbroek * at the proper offset in the file, and setting a flag for each pointer to
133*00b67f09SDavid van Moolenbroek * indicate that it is a reference to a location in the file, rather than in
134*00b67f09SDavid van Moolenbroek * memory.
135*00b67f09SDavid van Moolenbroek * step three: write out the header, adding the information that will be
136*00b67f09SDavid van Moolenbroek * needed to re-create the tree object itself.
137*00b67f09SDavid van Moolenbroek *
138*00b67f09SDavid van Moolenbroek * The RBTDB object will do this three times, once for each of the three
139*00b67f09SDavid van Moolenbroek * RBT objects it contains.
140*00b67f09SDavid van Moolenbroek *
141*00b67f09SDavid van Moolenbroek * Note: 'file' must point an actual open file that can be mmapped
142*00b67f09SDavid van Moolenbroek * and fseeked, not to a pipe or stream
143*00b67f09SDavid van Moolenbroek */
144*00b67f09SDavid van Moolenbroek
145*00b67f09SDavid van Moolenbroek static isc_result_t
146*00b67f09SDavid van Moolenbroek dns_rbt_zero_header(FILE *file);
147*00b67f09SDavid van Moolenbroek
148*00b67f09SDavid van Moolenbroek static isc_result_t
149*00b67f09SDavid van Moolenbroek write_header(FILE *file, dns_rbt_t *rbt, isc_uint64_t first_node_offset,
150*00b67f09SDavid van Moolenbroek isc_uint64_t crc);
151*00b67f09SDavid van Moolenbroek
152*00b67f09SDavid van Moolenbroek static isc_result_t
153*00b67f09SDavid van Moolenbroek serialize_node(FILE *file, dns_rbtnode_t *node, uintptr_t left,
154*00b67f09SDavid van Moolenbroek uintptr_t right, uintptr_t down, uintptr_t parent,
155*00b67f09SDavid van Moolenbroek uintptr_t data, isc_uint64_t *crc);
156*00b67f09SDavid van Moolenbroek
157*00b67f09SDavid van Moolenbroek static isc_result_t
158*00b67f09SDavid van Moolenbroek serialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,
159*00b67f09SDavid van Moolenbroek dns_rbtdatawriter_t datawriter, void *writer_arg,
160*00b67f09SDavid van Moolenbroek uintptr_t *where, isc_uint64_t *crc);
161*00b67f09SDavid van Moolenbroek /*
162*00b67f09SDavid van Moolenbroek * The following functions allow you to get the actual address of a pointer
163*00b67f09SDavid van Moolenbroek * without having to use an if statement to check to see if that address is
164*00b67f09SDavid van Moolenbroek * relative or not
165*00b67f09SDavid van Moolenbroek */
166*00b67f09SDavid van Moolenbroek static inline dns_rbtnode_t *
getparent(dns_rbtnode_t * node,file_header_t * header)167*00b67f09SDavid van Moolenbroek getparent(dns_rbtnode_t *node, file_header_t *header) {
168*00b67f09SDavid van Moolenbroek char *adjusted_address = (char *)(node->parent);
169*00b67f09SDavid van Moolenbroek adjusted_address += node->parent_is_relative * (uintptr_t)header;
170*00b67f09SDavid van Moolenbroek
171*00b67f09SDavid van Moolenbroek return ((dns_rbtnode_t *)adjusted_address);
172*00b67f09SDavid van Moolenbroek }
173*00b67f09SDavid van Moolenbroek
174*00b67f09SDavid van Moolenbroek static inline dns_rbtnode_t *
getleft(dns_rbtnode_t * node,file_header_t * header)175*00b67f09SDavid van Moolenbroek getleft(dns_rbtnode_t *node, file_header_t *header) {
176*00b67f09SDavid van Moolenbroek char *adjusted_address = (char *)(node->left);
177*00b67f09SDavid van Moolenbroek adjusted_address += node->left_is_relative * (uintptr_t)header;
178*00b67f09SDavid van Moolenbroek
179*00b67f09SDavid van Moolenbroek return ((dns_rbtnode_t *)adjusted_address);
180*00b67f09SDavid van Moolenbroek }
181*00b67f09SDavid van Moolenbroek
182*00b67f09SDavid van Moolenbroek static inline dns_rbtnode_t *
getright(dns_rbtnode_t * node,file_header_t * header)183*00b67f09SDavid van Moolenbroek getright(dns_rbtnode_t *node, file_header_t *header) {
184*00b67f09SDavid van Moolenbroek char *adjusted_address = (char *)(node->right);
185*00b67f09SDavid van Moolenbroek adjusted_address += node->right_is_relative * (uintptr_t)header;
186*00b67f09SDavid van Moolenbroek
187*00b67f09SDavid van Moolenbroek return ((dns_rbtnode_t *)adjusted_address);
188*00b67f09SDavid van Moolenbroek }
189*00b67f09SDavid van Moolenbroek
190*00b67f09SDavid van Moolenbroek static inline dns_rbtnode_t *
getdown(dns_rbtnode_t * node,file_header_t * header)191*00b67f09SDavid van Moolenbroek getdown(dns_rbtnode_t *node, file_header_t *header) {
192*00b67f09SDavid van Moolenbroek char *adjusted_address = (char *)(node->down);
193*00b67f09SDavid van Moolenbroek adjusted_address += node->down_is_relative * (uintptr_t)header;
194*00b67f09SDavid van Moolenbroek
195*00b67f09SDavid van Moolenbroek return ((dns_rbtnode_t *)adjusted_address);
196*00b67f09SDavid van Moolenbroek }
197*00b67f09SDavid van Moolenbroek
198*00b67f09SDavid van Moolenbroek static inline dns_rbtnode_t *
getdata(dns_rbtnode_t * node,file_header_t * header)199*00b67f09SDavid van Moolenbroek getdata(dns_rbtnode_t *node, file_header_t *header) {
200*00b67f09SDavid van Moolenbroek char *adjusted_address = (char *)(node->data);
201*00b67f09SDavid van Moolenbroek adjusted_address += node->data_is_relative * (uintptr_t)header;
202*00b67f09SDavid van Moolenbroek
203*00b67f09SDavid van Moolenbroek return ((dns_rbtnode_t *)adjusted_address);
204*00b67f09SDavid van Moolenbroek }
205*00b67f09SDavid van Moolenbroek
206*00b67f09SDavid van Moolenbroek /*%
207*00b67f09SDavid van Moolenbroek * Elements of the rbtnode structure.
208*00b67f09SDavid van Moolenbroek */
209*00b67f09SDavid van Moolenbroek #define PARENT(node) ((node)->parent)
210*00b67f09SDavid van Moolenbroek #define LEFT(node) ((node)->left)
211*00b67f09SDavid van Moolenbroek #define RIGHT(node) ((node)->right)
212*00b67f09SDavid van Moolenbroek #define DOWN(node) ((node)->down)
213*00b67f09SDavid van Moolenbroek #define DATA(node) ((node)->data)
214*00b67f09SDavid van Moolenbroek #define IS_EMPTY(node) ((node)->data == NULL)
215*00b67f09SDavid van Moolenbroek #define HASHNEXT(node) ((node)->hashnext)
216*00b67f09SDavid van Moolenbroek #define HASHVAL(node) ((node)->hashval)
217*00b67f09SDavid van Moolenbroek #define COLOR(node) ((node)->color)
218*00b67f09SDavid van Moolenbroek #define NAMELEN(node) ((node)->namelen)
219*00b67f09SDavid van Moolenbroek #define OLDNAMELEN(node) ((node)->oldnamelen)
220*00b67f09SDavid van Moolenbroek #define OFFSETLEN(node) ((node)->offsetlen)
221*00b67f09SDavid van Moolenbroek #define ATTRS(node) ((node)->attributes)
222*00b67f09SDavid van Moolenbroek #define IS_ROOT(node) ISC_TF((node)->is_root == 1)
223*00b67f09SDavid van Moolenbroek #define FINDCALLBACK(node) ISC_TF((node)->find_callback == 1)
224*00b67f09SDavid van Moolenbroek
225*00b67f09SDavid van Moolenbroek /*%
226*00b67f09SDavid van Moolenbroek * Structure elements from the rbtdb.c, not
227*00b67f09SDavid van Moolenbroek * used as part of the rbt.c algorithms.
228*00b67f09SDavid van Moolenbroek */
229*00b67f09SDavid van Moolenbroek #define DIRTY(node) ((node)->dirty)
230*00b67f09SDavid van Moolenbroek #define WILD(node) ((node)->wild)
231*00b67f09SDavid van Moolenbroek #define LOCKNUM(node) ((node)->locknum)
232*00b67f09SDavid van Moolenbroek
233*00b67f09SDavid van Moolenbroek /*%
234*00b67f09SDavid van Moolenbroek * The variable length stuff stored after the node has the following
235*00b67f09SDavid van Moolenbroek * structure.
236*00b67f09SDavid van Moolenbroek *
237*00b67f09SDavid van Moolenbroek * <name_data>{1..255}<oldoffsetlen>{1}<offsets>{1..128}
238*00b67f09SDavid van Moolenbroek *
239*00b67f09SDavid van Moolenbroek * <name_data> contains the name of the node when it was created.
240*00b67f09SDavid van Moolenbroek * <oldoffsetlen> contains the length of <offsets> when the node was created.
241*00b67f09SDavid van Moolenbroek * <offsets> contains the offets into name for each label when the node was
242*00b67f09SDavid van Moolenbroek * created.
243*00b67f09SDavid van Moolenbroek */
244*00b67f09SDavid van Moolenbroek
245*00b67f09SDavid van Moolenbroek #define NAME(node) ((unsigned char *)((node) + 1))
246*00b67f09SDavid van Moolenbroek #define OFFSETS(node) (NAME(node) + OLDNAMELEN(node) + 1)
247*00b67f09SDavid van Moolenbroek #define OLDOFFSETLEN(node) (OFFSETS(node)[-1])
248*00b67f09SDavid van Moolenbroek
249*00b67f09SDavid van Moolenbroek #define NODE_SIZE(node) (sizeof(*node) + \
250*00b67f09SDavid van Moolenbroek OLDNAMELEN(node) + OLDOFFSETLEN(node) + 1)
251*00b67f09SDavid van Moolenbroek
252*00b67f09SDavid van Moolenbroek /*%
253*00b67f09SDavid van Moolenbroek * Color management.
254*00b67f09SDavid van Moolenbroek */
255*00b67f09SDavid van Moolenbroek #define IS_RED(node) ((node) != NULL && (node)->color == RED)
256*00b67f09SDavid van Moolenbroek #define IS_BLACK(node) ((node) == NULL || (node)->color == BLACK)
257*00b67f09SDavid van Moolenbroek #define MAKE_RED(node) ((node)->color = RED)
258*00b67f09SDavid van Moolenbroek #define MAKE_BLACK(node) ((node)->color = BLACK)
259*00b67f09SDavid van Moolenbroek
260*00b67f09SDavid van Moolenbroek /*%
261*00b67f09SDavid van Moolenbroek * Chain management.
262*00b67f09SDavid van Moolenbroek *
263*00b67f09SDavid van Moolenbroek * The "ancestors" member of chains were removed, with their job now
264*00b67f09SDavid van Moolenbroek * being wholly handled by parent pointers (which didn't exist, because
265*00b67f09SDavid van Moolenbroek * of memory concerns, when chains were first implemented).
266*00b67f09SDavid van Moolenbroek */
267*00b67f09SDavid van Moolenbroek #define ADD_LEVEL(chain, node) \
268*00b67f09SDavid van Moolenbroek do { \
269*00b67f09SDavid van Moolenbroek INSIST((chain)->level_count < DNS_RBT_LEVELBLOCK); \
270*00b67f09SDavid van Moolenbroek (chain)->levels[(chain)->level_count++] = (node); \
271*00b67f09SDavid van Moolenbroek } while (0)
272*00b67f09SDavid van Moolenbroek
273*00b67f09SDavid van Moolenbroek /*%
274*00b67f09SDavid van Moolenbroek * The following macros directly access normally private name variables.
275*00b67f09SDavid van Moolenbroek * These macros are used to avoid a lot of function calls in the critical
276*00b67f09SDavid van Moolenbroek * path of the tree traversal code.
277*00b67f09SDavid van Moolenbroek */
278*00b67f09SDavid van Moolenbroek
279*00b67f09SDavid van Moolenbroek static inline void
NODENAME(dns_rbtnode_t * node,dns_name_t * name)280*00b67f09SDavid van Moolenbroek NODENAME(dns_rbtnode_t *node, dns_name_t *name) {
281*00b67f09SDavid van Moolenbroek name->length = NAMELEN(node);
282*00b67f09SDavid van Moolenbroek name->labels = OFFSETLEN(node);
283*00b67f09SDavid van Moolenbroek name->ndata = NAME(node);
284*00b67f09SDavid van Moolenbroek name->offsets = OFFSETS(node);
285*00b67f09SDavid van Moolenbroek name->attributes = ATTRS(node);
286*00b67f09SDavid van Moolenbroek name->attributes |= DNS_NAMEATTR_READONLY;
287*00b67f09SDavid van Moolenbroek }
288*00b67f09SDavid van Moolenbroek
289*00b67f09SDavid van Moolenbroek void
dns_rbtnode_nodename(dns_rbtnode_t * node,dns_name_t * name)290*00b67f09SDavid van Moolenbroek dns_rbtnode_nodename(dns_rbtnode_t *node, dns_name_t *name) {
291*00b67f09SDavid van Moolenbroek name->length = NAMELEN(node);
292*00b67f09SDavid van Moolenbroek name->labels = OFFSETLEN(node);
293*00b67f09SDavid van Moolenbroek name->ndata = NAME(node);
294*00b67f09SDavid van Moolenbroek name->offsets = OFFSETS(node);
295*00b67f09SDavid van Moolenbroek name->attributes = ATTRS(node);
296*00b67f09SDavid van Moolenbroek name->attributes |= DNS_NAMEATTR_READONLY;
297*00b67f09SDavid van Moolenbroek }
298*00b67f09SDavid van Moolenbroek
299*00b67f09SDavid van Moolenbroek dns_rbtnode_t *
dns_rbt_root(dns_rbt_t * rbt)300*00b67f09SDavid van Moolenbroek dns_rbt_root(dns_rbt_t *rbt) {
301*00b67f09SDavid van Moolenbroek return rbt->root;
302*00b67f09SDavid van Moolenbroek }
303*00b67f09SDavid van Moolenbroek
304*00b67f09SDavid van Moolenbroek #ifdef DNS_RBT_USEHASH
305*00b67f09SDavid van Moolenbroek static isc_result_t
306*00b67f09SDavid van Moolenbroek inithash(dns_rbt_t *rbt);
307*00b67f09SDavid van Moolenbroek #endif
308*00b67f09SDavid van Moolenbroek
309*00b67f09SDavid van Moolenbroek #ifdef DEBUG
310*00b67f09SDavid van Moolenbroek #define inline
311*00b67f09SDavid van Moolenbroek /*
312*00b67f09SDavid van Moolenbroek * A little something to help out in GDB.
313*00b67f09SDavid van Moolenbroek */
314*00b67f09SDavid van Moolenbroek dns_name_t Name(dns_rbtnode_t *node);
315*00b67f09SDavid van Moolenbroek dns_name_t
Name(dns_rbtnode_t * node)316*00b67f09SDavid van Moolenbroek Name(dns_rbtnode_t *node) {
317*00b67f09SDavid van Moolenbroek dns_name_t name;
318*00b67f09SDavid van Moolenbroek
319*00b67f09SDavid van Moolenbroek dns_name_init(&name, NULL);
320*00b67f09SDavid van Moolenbroek if (node != NULL)
321*00b67f09SDavid van Moolenbroek NODENAME(node, &name);
322*00b67f09SDavid van Moolenbroek
323*00b67f09SDavid van Moolenbroek return (name);
324*00b67f09SDavid van Moolenbroek }
325*00b67f09SDavid van Moolenbroek
326*00b67f09SDavid van Moolenbroek static void
hexdump(const char * desc,void * blob,size_t size)327*00b67f09SDavid van Moolenbroek hexdump(const char *desc, void *blob, size_t size) {
328*00b67f09SDavid van Moolenbroek char hexdump[BUFSIZ * 2 + 1];
329*00b67f09SDavid van Moolenbroek isc_buffer_t b;
330*00b67f09SDavid van Moolenbroek isc_region_t r;
331*00b67f09SDavid van Moolenbroek isc_result_t result;
332*00b67f09SDavid van Moolenbroek size_t bytes;
333*00b67f09SDavid van Moolenbroek isc_uint8_t *data = blob;
334*00b67f09SDavid van Moolenbroek
335*00b67f09SDavid van Moolenbroek fprintf(stderr, "%s: ", desc);
336*00b67f09SDavid van Moolenbroek do {
337*00b67f09SDavid van Moolenbroek isc_buffer_init(&b, hexdump, sizeof(hexdump));
338*00b67f09SDavid van Moolenbroek r.base = data;
339*00b67f09SDavid van Moolenbroek r.length = bytes = (size > BUFSIZ) ? BUFSIZ : size;
340*00b67f09SDavid van Moolenbroek result = isc_hex_totext(&r, 0, "", &b);
341*00b67f09SDavid van Moolenbroek RUNTIME_CHECK(result == ISC_R_SUCCESS);
342*00b67f09SDavid van Moolenbroek isc_buffer_putuint8(&b, 0);
343*00b67f09SDavid van Moolenbroek fprintf(stderr, "%s", hexdump);
344*00b67f09SDavid van Moolenbroek data += bytes;
345*00b67f09SDavid van Moolenbroek size -= bytes;
346*00b67f09SDavid van Moolenbroek } while (size > 0);
347*00b67f09SDavid van Moolenbroek fprintf(stderr, "\n");
348*00b67f09SDavid van Moolenbroek }
349*00b67f09SDavid van Moolenbroek #endif /* DEBUG */
350*00b67f09SDavid van Moolenbroek
351*00b67f09SDavid van Moolenbroek /* The passed node must not be NULL. */
352*00b67f09SDavid van Moolenbroek static inline dns_rbtnode_t *
get_subtree_root(dns_rbtnode_t * node)353*00b67f09SDavid van Moolenbroek get_subtree_root(dns_rbtnode_t *node) {
354*00b67f09SDavid van Moolenbroek while (!IS_ROOT(node)) {
355*00b67f09SDavid van Moolenbroek node = PARENT(node);
356*00b67f09SDavid van Moolenbroek }
357*00b67f09SDavid van Moolenbroek
358*00b67f09SDavid van Moolenbroek return (node);
359*00b67f09SDavid van Moolenbroek }
360*00b67f09SDavid van Moolenbroek
361*00b67f09SDavid van Moolenbroek /* Upper node is the parent of the root of the passed node's
362*00b67f09SDavid van Moolenbroek * subtree. The passed node must not be NULL.
363*00b67f09SDavid van Moolenbroek */
364*00b67f09SDavid van Moolenbroek static inline dns_rbtnode_t *
get_upper_node(dns_rbtnode_t * node)365*00b67f09SDavid van Moolenbroek get_upper_node(dns_rbtnode_t *node) {
366*00b67f09SDavid van Moolenbroek dns_rbtnode_t *root = get_subtree_root(node);
367*00b67f09SDavid van Moolenbroek
368*00b67f09SDavid van Moolenbroek /*
369*00b67f09SDavid van Moolenbroek * Return the node in the level above the argument node that points
370*00b67f09SDavid van Moolenbroek * to the level the argument node is in. If the argument node is in
371*00b67f09SDavid van Moolenbroek * the top level, the return value is NULL.
372*00b67f09SDavid van Moolenbroek */
373*00b67f09SDavid van Moolenbroek return (PARENT(root));
374*00b67f09SDavid van Moolenbroek }
375*00b67f09SDavid van Moolenbroek
376*00b67f09SDavid van Moolenbroek size_t
dns__rbtnode_getdistance(dns_rbtnode_t * node)377*00b67f09SDavid van Moolenbroek dns__rbtnode_getdistance(dns_rbtnode_t *node) {
378*00b67f09SDavid van Moolenbroek size_t nodes = 1;
379*00b67f09SDavid van Moolenbroek
380*00b67f09SDavid van Moolenbroek while (node != NULL) {
381*00b67f09SDavid van Moolenbroek if (IS_ROOT(node))
382*00b67f09SDavid van Moolenbroek break;
383*00b67f09SDavid van Moolenbroek nodes++;
384*00b67f09SDavid van Moolenbroek node = PARENT(node);
385*00b67f09SDavid van Moolenbroek }
386*00b67f09SDavid van Moolenbroek
387*00b67f09SDavid van Moolenbroek return (nodes);
388*00b67f09SDavid van Moolenbroek }
389*00b67f09SDavid van Moolenbroek
390*00b67f09SDavid van Moolenbroek /*
391*00b67f09SDavid van Moolenbroek * Forward declarations.
392*00b67f09SDavid van Moolenbroek */
393*00b67f09SDavid van Moolenbroek static isc_result_t
394*00b67f09SDavid van Moolenbroek create_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep);
395*00b67f09SDavid van Moolenbroek
396*00b67f09SDavid van Moolenbroek #ifdef DNS_RBT_USEHASH
397*00b67f09SDavid van Moolenbroek static inline void
398*00b67f09SDavid van Moolenbroek hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name);
399*00b67f09SDavid van Moolenbroek static inline void
400*00b67f09SDavid van Moolenbroek unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
401*00b67f09SDavid van Moolenbroek static void
402*00b67f09SDavid van Moolenbroek rehash(dns_rbt_t *rbt, unsigned int newcount);
403*00b67f09SDavid van Moolenbroek #else
404*00b67f09SDavid van Moolenbroek #define hash_node(rbt, node, name)
405*00b67f09SDavid van Moolenbroek #define unhash_node(rbt, node)
406*00b67f09SDavid van Moolenbroek #define rehash(rbt, newcount)
407*00b67f09SDavid van Moolenbroek #endif
408*00b67f09SDavid van Moolenbroek
409*00b67f09SDavid van Moolenbroek static inline void
410*00b67f09SDavid van Moolenbroek rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
411*00b67f09SDavid van Moolenbroek static inline void
412*00b67f09SDavid van Moolenbroek rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
413*00b67f09SDavid van Moolenbroek
414*00b67f09SDavid van Moolenbroek static void
415*00b67f09SDavid van Moolenbroek addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
416*00b67f09SDavid van Moolenbroek dns_rbtnode_t **rootp);
417*00b67f09SDavid van Moolenbroek
418*00b67f09SDavid van Moolenbroek static void
419*00b67f09SDavid van Moolenbroek deletefromlevel(dns_rbtnode_t *delete, dns_rbtnode_t **rootp);
420*00b67f09SDavid van Moolenbroek
421*00b67f09SDavid van Moolenbroek static isc_result_t
422*00b67f09SDavid van Moolenbroek treefix(dns_rbt_t *rbt, void *base, size_t size,
423*00b67f09SDavid van Moolenbroek dns_rbtnode_t *n, dns_name_t *name,
424*00b67f09SDavid van Moolenbroek dns_rbtdatafixer_t datafixer, void *fixer_arg,
425*00b67f09SDavid van Moolenbroek isc_uint64_t *crc);
426*00b67f09SDavid van Moolenbroek
427*00b67f09SDavid van Moolenbroek static isc_result_t
428*00b67f09SDavid van Moolenbroek deletetree(dns_rbt_t *rbt, dns_rbtnode_t *node);
429*00b67f09SDavid van Moolenbroek
430*00b67f09SDavid van Moolenbroek static void
431*00b67f09SDavid van Moolenbroek deletetreeflat(dns_rbt_t *rbt, unsigned int quantum, dns_rbtnode_t **nodep);
432*00b67f09SDavid van Moolenbroek
433*00b67f09SDavid van Moolenbroek static void
434*00b67f09SDavid van Moolenbroek printnodename(dns_rbtnode_t *node, isc_boolean_t quoted, FILE *f);
435*00b67f09SDavid van Moolenbroek
436*00b67f09SDavid van Moolenbroek static void
437*00b67f09SDavid van Moolenbroek freenode(dns_rbt_t *rbt, dns_rbtnode_t **nodep);
438*00b67f09SDavid van Moolenbroek
439*00b67f09SDavid van Moolenbroek static isc_result_t
dns_rbt_zero_header(FILE * file)440*00b67f09SDavid van Moolenbroek dns_rbt_zero_header(FILE *file) {
441*00b67f09SDavid van Moolenbroek /*
442*00b67f09SDavid van Moolenbroek * Write out a zeroed header as a placeholder. Doing this ensures
443*00b67f09SDavid van Moolenbroek * that the file will not read while it is partially written, should
444*00b67f09SDavid van Moolenbroek * writing fail or be interrupted.
445*00b67f09SDavid van Moolenbroek */
446*00b67f09SDavid van Moolenbroek char buffer[HEADER_LENGTH];
447*00b67f09SDavid van Moolenbroek isc_result_t result;
448*00b67f09SDavid van Moolenbroek
449*00b67f09SDavid van Moolenbroek memset(buffer, 0, HEADER_LENGTH);
450*00b67f09SDavid van Moolenbroek result = isc_stdio_write(buffer, 1, HEADER_LENGTH, file, NULL);
451*00b67f09SDavid van Moolenbroek if (result != ISC_R_SUCCESS)
452*00b67f09SDavid van Moolenbroek return (result);
453*00b67f09SDavid van Moolenbroek
454*00b67f09SDavid van Moolenbroek result = fflush(file);
455*00b67f09SDavid van Moolenbroek if (result != ISC_R_SUCCESS)
456*00b67f09SDavid van Moolenbroek return (result);
457*00b67f09SDavid van Moolenbroek
458*00b67f09SDavid van Moolenbroek return (ISC_R_SUCCESS);
459*00b67f09SDavid van Moolenbroek }
460*00b67f09SDavid van Moolenbroek
461*00b67f09SDavid van Moolenbroek /*
462*00b67f09SDavid van Moolenbroek * Write out the real header, including NodeDump version information
463*00b67f09SDavid van Moolenbroek * and the offset of the first node.
464*00b67f09SDavid van Moolenbroek *
465*00b67f09SDavid van Moolenbroek * Any information stored in the rbt object itself should be stored
466*00b67f09SDavid van Moolenbroek * here.
467*00b67f09SDavid van Moolenbroek */
468*00b67f09SDavid van Moolenbroek static isc_result_t
write_header(FILE * file,dns_rbt_t * rbt,isc_uint64_t first_node_offset,isc_uint64_t crc)469*00b67f09SDavid van Moolenbroek write_header(FILE *file, dns_rbt_t *rbt, isc_uint64_t first_node_offset,
470*00b67f09SDavid van Moolenbroek isc_uint64_t crc)
471*00b67f09SDavid van Moolenbroek {
472*00b67f09SDavid van Moolenbroek file_header_t header;
473*00b67f09SDavid van Moolenbroek isc_result_t result;
474*00b67f09SDavid van Moolenbroek off_t location;
475*00b67f09SDavid van Moolenbroek
476*00b67f09SDavid van Moolenbroek if (FILE_VERSION[0] == '\0') {
477*00b67f09SDavid van Moolenbroek memset(FILE_VERSION, 0, sizeof(FILE_VERSION));
478*00b67f09SDavid van Moolenbroek snprintf(FILE_VERSION, sizeof(FILE_VERSION),
479*00b67f09SDavid van Moolenbroek "RBT Image %s %s", dns_major, dns_mapapi);
480*00b67f09SDavid van Moolenbroek }
481*00b67f09SDavid van Moolenbroek
482*00b67f09SDavid van Moolenbroek memset(&header, 0, sizeof(file_header_t));
483*00b67f09SDavid van Moolenbroek memmove(header.version1, FILE_VERSION, sizeof(header.version1));
484*00b67f09SDavid van Moolenbroek memmove(header.version2, FILE_VERSION, sizeof(header.version2));
485*00b67f09SDavid van Moolenbroek header.first_node_offset = first_node_offset;
486*00b67f09SDavid van Moolenbroek header.ptrsize = (isc_uint32_t) sizeof(void *);
487*00b67f09SDavid van Moolenbroek header.bigendian = (1 == htonl(1)) ? 1 : 0;
488*00b67f09SDavid van Moolenbroek
489*00b67f09SDavid van Moolenbroek #ifdef DNS_RDATASET_FIXED
490*00b67f09SDavid van Moolenbroek header.rdataset_fixed = 1;
491*00b67f09SDavid van Moolenbroek #else
492*00b67f09SDavid van Moolenbroek header.rdataset_fixed = 0;
493*00b67f09SDavid van Moolenbroek #endif
494*00b67f09SDavid van Moolenbroek
495*00b67f09SDavid van Moolenbroek header.nodecount = rbt->nodecount;
496*00b67f09SDavid van Moolenbroek
497*00b67f09SDavid van Moolenbroek header.crc = crc;
498*00b67f09SDavid van Moolenbroek
499*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_tell(file, &location));
500*00b67f09SDavid van Moolenbroek location = dns_rbt_serialize_align(location);
501*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_seek(file, location, SEEK_SET));
502*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_write(&header, 1, sizeof(file_header_t), file, NULL));
503*00b67f09SDavid van Moolenbroek CHECK(fflush(file));
504*00b67f09SDavid van Moolenbroek
505*00b67f09SDavid van Moolenbroek /* Ensure we are always at the end of the file. */
506*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_seek(file, 0, SEEK_END));
507*00b67f09SDavid van Moolenbroek
508*00b67f09SDavid van Moolenbroek cleanup:
509*00b67f09SDavid van Moolenbroek return (result);
510*00b67f09SDavid van Moolenbroek }
511*00b67f09SDavid van Moolenbroek
512*00b67f09SDavid van Moolenbroek static isc_result_t
serialize_node(FILE * file,dns_rbtnode_t * node,uintptr_t left,uintptr_t right,uintptr_t down,uintptr_t parent,uintptr_t data,isc_uint64_t * crc)513*00b67f09SDavid van Moolenbroek serialize_node(FILE *file, dns_rbtnode_t *node, uintptr_t left,
514*00b67f09SDavid van Moolenbroek uintptr_t right, uintptr_t down, uintptr_t parent,
515*00b67f09SDavid van Moolenbroek uintptr_t data, isc_uint64_t *crc)
516*00b67f09SDavid van Moolenbroek {
517*00b67f09SDavid van Moolenbroek dns_rbtnode_t temp_node;
518*00b67f09SDavid van Moolenbroek off_t file_position;
519*00b67f09SDavid van Moolenbroek unsigned char *node_data;
520*00b67f09SDavid van Moolenbroek size_t datasize;
521*00b67f09SDavid van Moolenbroek isc_result_t result;
522*00b67f09SDavid van Moolenbroek #ifdef DEBUG
523*00b67f09SDavid van Moolenbroek dns_name_t nodename;
524*00b67f09SDavid van Moolenbroek #endif
525*00b67f09SDavid van Moolenbroek
526*00b67f09SDavid van Moolenbroek INSIST(node != NULL);
527*00b67f09SDavid van Moolenbroek
528*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_tell(file, &file_position));
529*00b67f09SDavid van Moolenbroek file_position = dns_rbt_serialize_align(file_position);
530*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_seek(file, file_position, SEEK_SET));
531*00b67f09SDavid van Moolenbroek
532*00b67f09SDavid van Moolenbroek temp_node = *node;
533*00b67f09SDavid van Moolenbroek temp_node.down_is_relative = 0;
534*00b67f09SDavid van Moolenbroek temp_node.left_is_relative = 0;
535*00b67f09SDavid van Moolenbroek temp_node.right_is_relative = 0;
536*00b67f09SDavid van Moolenbroek temp_node.parent_is_relative = 0;
537*00b67f09SDavid van Moolenbroek temp_node.data_is_relative = 0;
538*00b67f09SDavid van Moolenbroek temp_node.is_mmapped = 1;
539*00b67f09SDavid van Moolenbroek
540*00b67f09SDavid van Moolenbroek /*
541*00b67f09SDavid van Moolenbroek * If the next node is not NULL, calculate the next node's location
542*00b67f09SDavid van Moolenbroek * in the file. Note that this will have to change when the data
543*00b67f09SDavid van Moolenbroek * structure changes, and it also assumes that we always write the
544*00b67f09SDavid van Moolenbroek * nodes out in list order (which we currently do.)
545*00b67f09SDavid van Moolenbroek */
546*00b67f09SDavid van Moolenbroek if (temp_node.parent != NULL) {
547*00b67f09SDavid van Moolenbroek temp_node.parent = (dns_rbtnode_t *)(parent);
548*00b67f09SDavid van Moolenbroek temp_node.parent_is_relative = 1;
549*00b67f09SDavid van Moolenbroek }
550*00b67f09SDavid van Moolenbroek if (temp_node.left != NULL) {
551*00b67f09SDavid van Moolenbroek temp_node.left = (dns_rbtnode_t *)(left);
552*00b67f09SDavid van Moolenbroek temp_node.left_is_relative = 1;
553*00b67f09SDavid van Moolenbroek }
554*00b67f09SDavid van Moolenbroek if (temp_node.right != NULL) {
555*00b67f09SDavid van Moolenbroek temp_node.right = (dns_rbtnode_t *)(right);
556*00b67f09SDavid van Moolenbroek temp_node.right_is_relative = 1;
557*00b67f09SDavid van Moolenbroek }
558*00b67f09SDavid van Moolenbroek if (temp_node.down != NULL) {
559*00b67f09SDavid van Moolenbroek temp_node.down = (dns_rbtnode_t *)(down);
560*00b67f09SDavid van Moolenbroek temp_node.down_is_relative = 1;
561*00b67f09SDavid van Moolenbroek }
562*00b67f09SDavid van Moolenbroek if (temp_node.data != NULL) {
563*00b67f09SDavid van Moolenbroek temp_node.data = (dns_rbtnode_t *)(data);
564*00b67f09SDavid van Moolenbroek temp_node.data_is_relative = 1;
565*00b67f09SDavid van Moolenbroek }
566*00b67f09SDavid van Moolenbroek
567*00b67f09SDavid van Moolenbroek node_data = (unsigned char *) node + sizeof(dns_rbtnode_t);
568*00b67f09SDavid van Moolenbroek datasize = NODE_SIZE(node) - sizeof(dns_rbtnode_t);
569*00b67f09SDavid van Moolenbroek
570*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_write(&temp_node, 1, sizeof(dns_rbtnode_t),
571*00b67f09SDavid van Moolenbroek file, NULL));
572*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_write(node_data, 1, datasize, file, NULL));
573*00b67f09SDavid van Moolenbroek
574*00b67f09SDavid van Moolenbroek #ifdef DEBUG
575*00b67f09SDavid van Moolenbroek dns_name_init(&nodename, NULL);
576*00b67f09SDavid van Moolenbroek NODENAME(node, &nodename);
577*00b67f09SDavid van Moolenbroek fprintf(stderr, "serialize ");
578*00b67f09SDavid van Moolenbroek dns_name_print(&nodename, stderr);
579*00b67f09SDavid van Moolenbroek fprintf(stderr, "\n");
580*00b67f09SDavid van Moolenbroek hexdump("node header", &temp_node,
581*00b67f09SDavid van Moolenbroek sizeof(dns_rbtnode_t));
582*00b67f09SDavid van Moolenbroek hexdump("node data", node_data, datasize);
583*00b67f09SDavid van Moolenbroek #endif
584*00b67f09SDavid van Moolenbroek
585*00b67f09SDavid van Moolenbroek isc_crc64_update(crc, (const isc_uint8_t *) &temp_node,
586*00b67f09SDavid van Moolenbroek sizeof(dns_rbtnode_t));
587*00b67f09SDavid van Moolenbroek isc_crc64_update(crc, (const isc_uint8_t *) node_data, datasize);
588*00b67f09SDavid van Moolenbroek
589*00b67f09SDavid van Moolenbroek cleanup:
590*00b67f09SDavid van Moolenbroek return (result);
591*00b67f09SDavid van Moolenbroek }
592*00b67f09SDavid van Moolenbroek
593*00b67f09SDavid van Moolenbroek static isc_result_t
serialize_nodes(FILE * file,dns_rbtnode_t * node,uintptr_t parent,dns_rbtdatawriter_t datawriter,void * writer_arg,uintptr_t * where,isc_uint64_t * crc)594*00b67f09SDavid van Moolenbroek serialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,
595*00b67f09SDavid van Moolenbroek dns_rbtdatawriter_t datawriter, void *writer_arg,
596*00b67f09SDavid van Moolenbroek uintptr_t *where, isc_uint64_t *crc)
597*00b67f09SDavid van Moolenbroek {
598*00b67f09SDavid van Moolenbroek uintptr_t left = 0, right = 0, down = 0, data = 0;
599*00b67f09SDavid van Moolenbroek off_t location = 0, offset_adjust;
600*00b67f09SDavid van Moolenbroek isc_result_t result;
601*00b67f09SDavid van Moolenbroek
602*00b67f09SDavid van Moolenbroek if (node == NULL) {
603*00b67f09SDavid van Moolenbroek if (where != NULL)
604*00b67f09SDavid van Moolenbroek *where = 0;
605*00b67f09SDavid van Moolenbroek return (ISC_R_SUCCESS);
606*00b67f09SDavid van Moolenbroek }
607*00b67f09SDavid van Moolenbroek
608*00b67f09SDavid van Moolenbroek /* Reserve space for current node. */
609*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_tell(file, &location));
610*00b67f09SDavid van Moolenbroek location = dns_rbt_serialize_align(location);
611*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_seek(file, location, SEEK_SET));
612*00b67f09SDavid van Moolenbroek
613*00b67f09SDavid van Moolenbroek offset_adjust = dns_rbt_serialize_align(location + NODE_SIZE(node));
614*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_seek(file, offset_adjust, SEEK_SET));
615*00b67f09SDavid van Moolenbroek
616*00b67f09SDavid van Moolenbroek /*
617*00b67f09SDavid van Moolenbroek * Serialize the rest of the tree.
618*00b67f09SDavid van Moolenbroek *
619*00b67f09SDavid van Moolenbroek * WARNING: A change in the order (from left, right, down)
620*00b67f09SDavid van Moolenbroek * will break the way the crc hash is computed.
621*00b67f09SDavid van Moolenbroek */
622*00b67f09SDavid van Moolenbroek CHECK(serialize_nodes(file, getleft(node, NULL), location,
623*00b67f09SDavid van Moolenbroek datawriter, writer_arg, &left, crc));
624*00b67f09SDavid van Moolenbroek CHECK(serialize_nodes(file, getright(node, NULL), location,
625*00b67f09SDavid van Moolenbroek datawriter, writer_arg, &right, crc));
626*00b67f09SDavid van Moolenbroek CHECK(serialize_nodes(file, getdown(node, NULL), location,
627*00b67f09SDavid van Moolenbroek datawriter, writer_arg, &down, crc));
628*00b67f09SDavid van Moolenbroek
629*00b67f09SDavid van Moolenbroek if (node->data != NULL) {
630*00b67f09SDavid van Moolenbroek off_t ret;
631*00b67f09SDavid van Moolenbroek
632*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_tell(file, &ret));
633*00b67f09SDavid van Moolenbroek ret = dns_rbt_serialize_align(ret);
634*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_seek(file, ret, SEEK_SET));
635*00b67f09SDavid van Moolenbroek data = ret;
636*00b67f09SDavid van Moolenbroek
637*00b67f09SDavid van Moolenbroek datawriter(file, node->data, writer_arg, crc);
638*00b67f09SDavid van Moolenbroek }
639*00b67f09SDavid van Moolenbroek
640*00b67f09SDavid van Moolenbroek /* Seek back to reserved space. */
641*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_seek(file, location, SEEK_SET));
642*00b67f09SDavid van Moolenbroek
643*00b67f09SDavid van Moolenbroek /* Serialize the current node. */
644*00b67f09SDavid van Moolenbroek CHECK(serialize_node(file, node, left, right, down, parent, data, crc));
645*00b67f09SDavid van Moolenbroek
646*00b67f09SDavid van Moolenbroek /* Ensure we are always at the end of the file. */
647*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_seek(file, 0, SEEK_END));
648*00b67f09SDavid van Moolenbroek
649*00b67f09SDavid van Moolenbroek if (where != NULL)
650*00b67f09SDavid van Moolenbroek *where = (uintptr_t) location;
651*00b67f09SDavid van Moolenbroek
652*00b67f09SDavid van Moolenbroek cleanup:
653*00b67f09SDavid van Moolenbroek return (result);
654*00b67f09SDavid van Moolenbroek }
655*00b67f09SDavid van Moolenbroek
656*00b67f09SDavid van Moolenbroek off_t
dns_rbt_serialize_align(off_t target)657*00b67f09SDavid van Moolenbroek dns_rbt_serialize_align(off_t target) {
658*00b67f09SDavid van Moolenbroek off_t offset = target % 8;
659*00b67f09SDavid van Moolenbroek
660*00b67f09SDavid van Moolenbroek if (offset == 0)
661*00b67f09SDavid van Moolenbroek return (target);
662*00b67f09SDavid van Moolenbroek else
663*00b67f09SDavid van Moolenbroek return (target + 8 - offset);
664*00b67f09SDavid van Moolenbroek }
665*00b67f09SDavid van Moolenbroek
666*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbt_serialize_tree(FILE * file,dns_rbt_t * rbt,dns_rbtdatawriter_t datawriter,void * writer_arg,off_t * offset)667*00b67f09SDavid van Moolenbroek dns_rbt_serialize_tree(FILE *file, dns_rbt_t *rbt,
668*00b67f09SDavid van Moolenbroek dns_rbtdatawriter_t datawriter,
669*00b67f09SDavid van Moolenbroek void *writer_arg, off_t *offset)
670*00b67f09SDavid van Moolenbroek {
671*00b67f09SDavid van Moolenbroek isc_result_t result;
672*00b67f09SDavid van Moolenbroek off_t header_position, node_position, end_position;
673*00b67f09SDavid van Moolenbroek isc_uint64_t crc;
674*00b67f09SDavid van Moolenbroek
675*00b67f09SDavid van Moolenbroek REQUIRE(file != NULL);
676*00b67f09SDavid van Moolenbroek
677*00b67f09SDavid van Moolenbroek CHECK(isc_file_isplainfilefd(fileno(file)));
678*00b67f09SDavid van Moolenbroek
679*00b67f09SDavid van Moolenbroek isc_crc64_init(&crc);
680*00b67f09SDavid van Moolenbroek
681*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_tell(file, &header_position));
682*00b67f09SDavid van Moolenbroek
683*00b67f09SDavid van Moolenbroek /* Write dummy header */
684*00b67f09SDavid van Moolenbroek CHECK(dns_rbt_zero_header(file));
685*00b67f09SDavid van Moolenbroek
686*00b67f09SDavid van Moolenbroek /* Serialize nodes */
687*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_tell(file, &node_position));
688*00b67f09SDavid van Moolenbroek CHECK(serialize_nodes(file, rbt->root, 0, datawriter,
689*00b67f09SDavid van Moolenbroek writer_arg, NULL, &crc));
690*00b67f09SDavid van Moolenbroek
691*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_tell(file, &end_position));
692*00b67f09SDavid van Moolenbroek if (node_position == end_position) {
693*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_seek(file, header_position, SEEK_SET));
694*00b67f09SDavid van Moolenbroek *offset = 0;
695*00b67f09SDavid van Moolenbroek return (ISC_R_SUCCESS);
696*00b67f09SDavid van Moolenbroek }
697*00b67f09SDavid van Moolenbroek
698*00b67f09SDavid van Moolenbroek isc_crc64_final(&crc);
699*00b67f09SDavid van Moolenbroek #ifdef DEBUG
700*00b67f09SDavid van Moolenbroek hexdump("serializing CRC", &crc, sizeof(crc));
701*00b67f09SDavid van Moolenbroek #endif
702*00b67f09SDavid van Moolenbroek
703*00b67f09SDavid van Moolenbroek /* Serialize header */
704*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_seek(file, header_position, SEEK_SET));
705*00b67f09SDavid van Moolenbroek CHECK(write_header(file, rbt, HEADER_LENGTH, crc));
706*00b67f09SDavid van Moolenbroek
707*00b67f09SDavid van Moolenbroek /* Ensure we are always at the end of the file. */
708*00b67f09SDavid van Moolenbroek CHECK(isc_stdio_seek(file, 0, SEEK_END));
709*00b67f09SDavid van Moolenbroek *offset = dns_rbt_serialize_align(header_position);
710*00b67f09SDavid van Moolenbroek
711*00b67f09SDavid van Moolenbroek cleanup:
712*00b67f09SDavid van Moolenbroek return (result);
713*00b67f09SDavid van Moolenbroek }
714*00b67f09SDavid van Moolenbroek
715*00b67f09SDavid van Moolenbroek #define CONFIRM(a) do { \
716*00b67f09SDavid van Moolenbroek if (! (a)) { \
717*00b67f09SDavid van Moolenbroek result = ISC_R_INVALIDFILE; \
718*00b67f09SDavid van Moolenbroek goto cleanup; \
719*00b67f09SDavid van Moolenbroek } \
720*00b67f09SDavid van Moolenbroek } while(/*CONSTCOND*/0);
721*00b67f09SDavid van Moolenbroek
722*00b67f09SDavid van Moolenbroek static isc_result_t
treefix(dns_rbt_t * rbt,void * base,size_t filesize,dns_rbtnode_t * n,dns_name_t * name,dns_rbtdatafixer_t datafixer,void * fixer_arg,isc_uint64_t * crc)723*00b67f09SDavid van Moolenbroek treefix(dns_rbt_t *rbt, void *base, size_t filesize, dns_rbtnode_t *n,
724*00b67f09SDavid van Moolenbroek dns_name_t *name, dns_rbtdatafixer_t datafixer,
725*00b67f09SDavid van Moolenbroek void *fixer_arg, isc_uint64_t *crc)
726*00b67f09SDavid van Moolenbroek {
727*00b67f09SDavid van Moolenbroek isc_result_t result = ISC_R_SUCCESS;
728*00b67f09SDavid van Moolenbroek dns_fixedname_t fixed;
729*00b67f09SDavid van Moolenbroek dns_name_t nodename, *fullname;
730*00b67f09SDavid van Moolenbroek unsigned char *node_data;
731*00b67f09SDavid van Moolenbroek dns_rbtnode_t header;
732*00b67f09SDavid van Moolenbroek size_t datasize, nodemax = filesize - sizeof(dns_rbtnode_t);
733*00b67f09SDavid van Moolenbroek
734*00b67f09SDavid van Moolenbroek if (n == NULL)
735*00b67f09SDavid van Moolenbroek return (ISC_R_SUCCESS);
736*00b67f09SDavid van Moolenbroek
737*00b67f09SDavid van Moolenbroek CONFIRM((void *) n >= base);
738*00b67f09SDavid van Moolenbroek CONFIRM((char *) n - (char *) base <= (int) nodemax);
739*00b67f09SDavid van Moolenbroek CONFIRM(DNS_RBTNODE_VALID(n));
740*00b67f09SDavid van Moolenbroek
741*00b67f09SDavid van Moolenbroek dns_name_init(&nodename, NULL);
742*00b67f09SDavid van Moolenbroek NODENAME(n, &nodename);
743*00b67f09SDavid van Moolenbroek
744*00b67f09SDavid van Moolenbroek fullname = &nodename;
745*00b67f09SDavid van Moolenbroek CONFIRM(dns_name_isvalid(fullname));
746*00b67f09SDavid van Moolenbroek
747*00b67f09SDavid van Moolenbroek if (!dns_name_isabsolute(&nodename)) {
748*00b67f09SDavid van Moolenbroek dns_fixedname_init(&fixed);
749*00b67f09SDavid van Moolenbroek fullname = dns_fixedname_name(&fixed);
750*00b67f09SDavid van Moolenbroek CHECK(dns_name_concatenate(&nodename, name, fullname, NULL));
751*00b67f09SDavid van Moolenbroek }
752*00b67f09SDavid van Moolenbroek
753*00b67f09SDavid van Moolenbroek /* memorize header contents prior to fixup */
754*00b67f09SDavid van Moolenbroek memmove(&header, n, sizeof(header));
755*00b67f09SDavid van Moolenbroek
756*00b67f09SDavid van Moolenbroek if (n->left_is_relative) {
757*00b67f09SDavid van Moolenbroek CONFIRM(n->left <= (dns_rbtnode_t *) nodemax);
758*00b67f09SDavid van Moolenbroek n->left = getleft(n, rbt->mmap_location);
759*00b67f09SDavid van Moolenbroek n->left_is_relative = 0;
760*00b67f09SDavid van Moolenbroek CONFIRM(DNS_RBTNODE_VALID(n->left));
761*00b67f09SDavid van Moolenbroek } else
762*00b67f09SDavid van Moolenbroek CONFIRM(n->left == NULL);
763*00b67f09SDavid van Moolenbroek
764*00b67f09SDavid van Moolenbroek if (n->right_is_relative) {
765*00b67f09SDavid van Moolenbroek CONFIRM(n->right <= (dns_rbtnode_t *) nodemax);
766*00b67f09SDavid van Moolenbroek n->right = getright(n, rbt->mmap_location);
767*00b67f09SDavid van Moolenbroek n->right_is_relative = 0;
768*00b67f09SDavid van Moolenbroek CONFIRM(DNS_RBTNODE_VALID(n->right));
769*00b67f09SDavid van Moolenbroek } else
770*00b67f09SDavid van Moolenbroek CONFIRM(n->right == NULL);
771*00b67f09SDavid van Moolenbroek
772*00b67f09SDavid van Moolenbroek if (n->down_is_relative) {
773*00b67f09SDavid van Moolenbroek CONFIRM(n->down <= (dns_rbtnode_t *) nodemax);
774*00b67f09SDavid van Moolenbroek n->down = getdown(n, rbt->mmap_location);
775*00b67f09SDavid van Moolenbroek n->down_is_relative = 0;
776*00b67f09SDavid van Moolenbroek CONFIRM(n->down > (dns_rbtnode_t *) n);
777*00b67f09SDavid van Moolenbroek CONFIRM(DNS_RBTNODE_VALID(n->down));
778*00b67f09SDavid van Moolenbroek } else
779*00b67f09SDavid van Moolenbroek CONFIRM(n->down == NULL);
780*00b67f09SDavid van Moolenbroek
781*00b67f09SDavid van Moolenbroek if (n->parent_is_relative) {
782*00b67f09SDavid van Moolenbroek CONFIRM(n->parent <= (dns_rbtnode_t *) nodemax);
783*00b67f09SDavid van Moolenbroek n->parent = getparent(n, rbt->mmap_location);
784*00b67f09SDavid van Moolenbroek n->parent_is_relative = 0;
785*00b67f09SDavid van Moolenbroek CONFIRM(n->parent < (dns_rbtnode_t *) n);
786*00b67f09SDavid van Moolenbroek CONFIRM(DNS_RBTNODE_VALID(n->parent));
787*00b67f09SDavid van Moolenbroek } else
788*00b67f09SDavid van Moolenbroek CONFIRM(n->parent == NULL);
789*00b67f09SDavid van Moolenbroek
790*00b67f09SDavid van Moolenbroek if (n->data_is_relative) {
791*00b67f09SDavid van Moolenbroek CONFIRM(n->data <= (void *) filesize);
792*00b67f09SDavid van Moolenbroek n->data = getdata(n, rbt->mmap_location);
793*00b67f09SDavid van Moolenbroek n->data_is_relative = 0;
794*00b67f09SDavid van Moolenbroek CONFIRM(n->data > (void *) n);
795*00b67f09SDavid van Moolenbroek } else
796*00b67f09SDavid van Moolenbroek CONFIRM(n->data == NULL);
797*00b67f09SDavid van Moolenbroek
798*00b67f09SDavid van Moolenbroek hash_node(rbt, n, fullname);
799*00b67f09SDavid van Moolenbroek
800*00b67f09SDavid van Moolenbroek /* a change in the order (from left, right, down) will break hashing*/
801*00b67f09SDavid van Moolenbroek if (n->left != NULL)
802*00b67f09SDavid van Moolenbroek CHECK(treefix(rbt, base, filesize, n->left, name,
803*00b67f09SDavid van Moolenbroek datafixer, fixer_arg, crc));
804*00b67f09SDavid van Moolenbroek if (n->right != NULL)
805*00b67f09SDavid van Moolenbroek CHECK(treefix(rbt, base, filesize, n->right, name,
806*00b67f09SDavid van Moolenbroek datafixer, fixer_arg, crc));
807*00b67f09SDavid van Moolenbroek if (n->down != NULL)
808*00b67f09SDavid van Moolenbroek CHECK(treefix(rbt, base, filesize, n->down, fullname,
809*00b67f09SDavid van Moolenbroek datafixer, fixer_arg, crc));
810*00b67f09SDavid van Moolenbroek
811*00b67f09SDavid van Moolenbroek if (datafixer != NULL && n->data != NULL)
812*00b67f09SDavid van Moolenbroek CHECK(datafixer(n, base, filesize, fixer_arg, crc));
813*00b67f09SDavid van Moolenbroek
814*00b67f09SDavid van Moolenbroek rbt->nodecount++;
815*00b67f09SDavid van Moolenbroek node_data = (unsigned char *) n + sizeof(dns_rbtnode_t);
816*00b67f09SDavid van Moolenbroek datasize = NODE_SIZE(n) - sizeof(dns_rbtnode_t);
817*00b67f09SDavid van Moolenbroek
818*00b67f09SDavid van Moolenbroek #ifdef DEBUG
819*00b67f09SDavid van Moolenbroek fprintf(stderr, "deserialize ");
820*00b67f09SDavid van Moolenbroek dns_name_print(&nodename, stderr);
821*00b67f09SDavid van Moolenbroek fprintf(stderr, "\n");
822*00b67f09SDavid van Moolenbroek hexdump("node header", &header,
823*00b67f09SDavid van Moolenbroek sizeof(dns_rbtnode_t));
824*00b67f09SDavid van Moolenbroek hexdump("node data", node_data, datasize);
825*00b67f09SDavid van Moolenbroek #endif
826*00b67f09SDavid van Moolenbroek isc_crc64_update(crc, (const isc_uint8_t *) &header,
827*00b67f09SDavid van Moolenbroek sizeof(dns_rbtnode_t));
828*00b67f09SDavid van Moolenbroek isc_crc64_update(crc, (const isc_uint8_t *) node_data,
829*00b67f09SDavid van Moolenbroek datasize);
830*00b67f09SDavid van Moolenbroek
831*00b67f09SDavid van Moolenbroek cleanup:
832*00b67f09SDavid van Moolenbroek return (result);
833*00b67f09SDavid van Moolenbroek }
834*00b67f09SDavid van Moolenbroek
835*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbt_deserialize_tree(void * base_address,size_t filesize,off_t header_offset,isc_mem_t * mctx,dns_rbtdeleter_t deleter,void * deleter_arg,dns_rbtdatafixer_t datafixer,void * fixer_arg,dns_rbtnode_t ** originp,dns_rbt_t ** rbtp)836*00b67f09SDavid van Moolenbroek dns_rbt_deserialize_tree(void *base_address, size_t filesize,
837*00b67f09SDavid van Moolenbroek off_t header_offset, isc_mem_t *mctx,
838*00b67f09SDavid van Moolenbroek dns_rbtdeleter_t deleter, void *deleter_arg,
839*00b67f09SDavid van Moolenbroek dns_rbtdatafixer_t datafixer, void *fixer_arg,
840*00b67f09SDavid van Moolenbroek dns_rbtnode_t **originp, dns_rbt_t **rbtp)
841*00b67f09SDavid van Moolenbroek {
842*00b67f09SDavid van Moolenbroek isc_result_t result = ISC_R_SUCCESS;
843*00b67f09SDavid van Moolenbroek file_header_t *header;
844*00b67f09SDavid van Moolenbroek dns_rbt_t *rbt = NULL;
845*00b67f09SDavid van Moolenbroek isc_uint64_t crc;
846*00b67f09SDavid van Moolenbroek
847*00b67f09SDavid van Moolenbroek REQUIRE(originp == NULL || *originp == NULL);
848*00b67f09SDavid van Moolenbroek REQUIRE(rbtp != NULL && *rbtp == NULL);
849*00b67f09SDavid van Moolenbroek
850*00b67f09SDavid van Moolenbroek isc_crc64_init(&crc);
851*00b67f09SDavid van Moolenbroek
852*00b67f09SDavid van Moolenbroek CHECK(dns_rbt_create(mctx, deleter, deleter_arg, &rbt));
853*00b67f09SDavid van Moolenbroek
854*00b67f09SDavid van Moolenbroek rbt->mmap_location = base_address;
855*00b67f09SDavid van Moolenbroek
856*00b67f09SDavid van Moolenbroek header = (file_header_t *)((char *)base_address + header_offset);
857*00b67f09SDavid van Moolenbroek
858*00b67f09SDavid van Moolenbroek #ifdef DNS_RDATASET_FIXED
859*00b67f09SDavid van Moolenbroek if (header->rdataset_fixed != 1) {
860*00b67f09SDavid van Moolenbroek result = ISC_R_INVALIDFILE;
861*00b67f09SDavid van Moolenbroek goto cleanup;
862*00b67f09SDavid van Moolenbroek }
863*00b67f09SDavid van Moolenbroek
864*00b67f09SDavid van Moolenbroek #else
865*00b67f09SDavid van Moolenbroek if (header->rdataset_fixed != 0) {
866*00b67f09SDavid van Moolenbroek result = ISC_R_INVALIDFILE;
867*00b67f09SDavid van Moolenbroek goto cleanup;
868*00b67f09SDavid van Moolenbroek }
869*00b67f09SDavid van Moolenbroek #endif
870*00b67f09SDavid van Moolenbroek
871*00b67f09SDavid van Moolenbroek if (header->ptrsize != (isc_uint32_t) sizeof(void *)) {
872*00b67f09SDavid van Moolenbroek result = ISC_R_INVALIDFILE;
873*00b67f09SDavid van Moolenbroek goto cleanup;
874*00b67f09SDavid van Moolenbroek }
875*00b67f09SDavid van Moolenbroek if (header->bigendian != (1 == htonl(1)) ? 1 : 0) {
876*00b67f09SDavid van Moolenbroek result = ISC_R_INVALIDFILE;
877*00b67f09SDavid van Moolenbroek goto cleanup;
878*00b67f09SDavid van Moolenbroek }
879*00b67f09SDavid van Moolenbroek
880*00b67f09SDavid van Moolenbroek /* Copy other data items from the header into our rbt. */
881*00b67f09SDavid van Moolenbroek rbt->root = (dns_rbtnode_t *)((char *)base_address +
882*00b67f09SDavid van Moolenbroek header_offset + header->first_node_offset);
883*00b67f09SDavid van Moolenbroek
884*00b67f09SDavid van Moolenbroek if ((header->nodecount * sizeof(dns_rbtnode_t)) > filesize) {
885*00b67f09SDavid van Moolenbroek result = ISC_R_INVALIDFILE;
886*00b67f09SDavid van Moolenbroek goto cleanup;
887*00b67f09SDavid van Moolenbroek }
888*00b67f09SDavid van Moolenbroek rehash(rbt, header->nodecount);
889*00b67f09SDavid van Moolenbroek
890*00b67f09SDavid van Moolenbroek CHECK(treefix(rbt, base_address, filesize, rbt->root,
891*00b67f09SDavid van Moolenbroek dns_rootname, datafixer, fixer_arg, &crc));
892*00b67f09SDavid van Moolenbroek
893*00b67f09SDavid van Moolenbroek isc_crc64_final(&crc);
894*00b67f09SDavid van Moolenbroek #ifdef DEBUG
895*00b67f09SDavid van Moolenbroek hexdump("deserializing CRC", &crc, sizeof(crc));
896*00b67f09SDavid van Moolenbroek #endif
897*00b67f09SDavid van Moolenbroek
898*00b67f09SDavid van Moolenbroek /* Check file hash */
899*00b67f09SDavid van Moolenbroek if (header->crc != crc) {
900*00b67f09SDavid van Moolenbroek result = ISC_R_INVALIDFILE;
901*00b67f09SDavid van Moolenbroek goto cleanup;
902*00b67f09SDavid van Moolenbroek }
903*00b67f09SDavid van Moolenbroek
904*00b67f09SDavid van Moolenbroek *rbtp = rbt;
905*00b67f09SDavid van Moolenbroek if (originp != NULL)
906*00b67f09SDavid van Moolenbroek *originp = rbt->root;
907*00b67f09SDavid van Moolenbroek
908*00b67f09SDavid van Moolenbroek if (header->nodecount != rbt->nodecount)
909*00b67f09SDavid van Moolenbroek result = ISC_R_INVALIDFILE;
910*00b67f09SDavid van Moolenbroek
911*00b67f09SDavid van Moolenbroek cleanup:
912*00b67f09SDavid van Moolenbroek if (result != ISC_R_SUCCESS && rbt != NULL) {
913*00b67f09SDavid van Moolenbroek rbt->root = NULL;
914*00b67f09SDavid van Moolenbroek rbt->nodecount = 0;
915*00b67f09SDavid van Moolenbroek dns_rbt_destroy(&rbt);
916*00b67f09SDavid van Moolenbroek }
917*00b67f09SDavid van Moolenbroek
918*00b67f09SDavid van Moolenbroek return (result);
919*00b67f09SDavid van Moolenbroek }
920*00b67f09SDavid van Moolenbroek
921*00b67f09SDavid van Moolenbroek /*
922*00b67f09SDavid van Moolenbroek * Initialize a red/black tree of trees.
923*00b67f09SDavid van Moolenbroek */
924*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbt_create(isc_mem_t * mctx,dns_rbtdeleter_t deleter,void * deleter_arg,dns_rbt_t ** rbtp)925*00b67f09SDavid van Moolenbroek dns_rbt_create(isc_mem_t *mctx, dns_rbtdeleter_t deleter,
926*00b67f09SDavid van Moolenbroek void *deleter_arg, dns_rbt_t **rbtp)
927*00b67f09SDavid van Moolenbroek {
928*00b67f09SDavid van Moolenbroek #ifdef DNS_RBT_USEHASH
929*00b67f09SDavid van Moolenbroek isc_result_t result;
930*00b67f09SDavid van Moolenbroek #endif
931*00b67f09SDavid van Moolenbroek dns_rbt_t *rbt;
932*00b67f09SDavid van Moolenbroek
933*00b67f09SDavid van Moolenbroek REQUIRE(mctx != NULL);
934*00b67f09SDavid van Moolenbroek REQUIRE(rbtp != NULL && *rbtp == NULL);
935*00b67f09SDavid van Moolenbroek REQUIRE(deleter == NULL ? deleter_arg == NULL : 1);
936*00b67f09SDavid van Moolenbroek
937*00b67f09SDavid van Moolenbroek rbt = (dns_rbt_t *)isc_mem_get(mctx, sizeof(*rbt));
938*00b67f09SDavid van Moolenbroek if (rbt == NULL)
939*00b67f09SDavid van Moolenbroek return (ISC_R_NOMEMORY);
940*00b67f09SDavid van Moolenbroek
941*00b67f09SDavid van Moolenbroek rbt->mctx = NULL;
942*00b67f09SDavid van Moolenbroek isc_mem_attach(mctx, &rbt->mctx);
943*00b67f09SDavid van Moolenbroek rbt->data_deleter = deleter;
944*00b67f09SDavid van Moolenbroek rbt->deleter_arg = deleter_arg;
945*00b67f09SDavid van Moolenbroek rbt->root = NULL;
946*00b67f09SDavid van Moolenbroek rbt->nodecount = 0;
947*00b67f09SDavid van Moolenbroek rbt->hashtable = NULL;
948*00b67f09SDavid van Moolenbroek rbt->hashsize = 0;
949*00b67f09SDavid van Moolenbroek rbt->mmap_location = NULL;
950*00b67f09SDavid van Moolenbroek
951*00b67f09SDavid van Moolenbroek #ifdef DNS_RBT_USEHASH
952*00b67f09SDavid van Moolenbroek result = inithash(rbt);
953*00b67f09SDavid van Moolenbroek if (result != ISC_R_SUCCESS) {
954*00b67f09SDavid van Moolenbroek isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));
955*00b67f09SDavid van Moolenbroek return (result);
956*00b67f09SDavid van Moolenbroek }
957*00b67f09SDavid van Moolenbroek #endif
958*00b67f09SDavid van Moolenbroek
959*00b67f09SDavid van Moolenbroek rbt->magic = RBT_MAGIC;
960*00b67f09SDavid van Moolenbroek
961*00b67f09SDavid van Moolenbroek *rbtp = rbt;
962*00b67f09SDavid van Moolenbroek
963*00b67f09SDavid van Moolenbroek return (ISC_R_SUCCESS);
964*00b67f09SDavid van Moolenbroek }
965*00b67f09SDavid van Moolenbroek
966*00b67f09SDavid van Moolenbroek /*
967*00b67f09SDavid van Moolenbroek * Deallocate a red/black tree of trees.
968*00b67f09SDavid van Moolenbroek */
969*00b67f09SDavid van Moolenbroek void
dns_rbt_destroy(dns_rbt_t ** rbtp)970*00b67f09SDavid van Moolenbroek dns_rbt_destroy(dns_rbt_t **rbtp) {
971*00b67f09SDavid van Moolenbroek RUNTIME_CHECK(dns_rbt_destroy2(rbtp, 0) == ISC_R_SUCCESS);
972*00b67f09SDavid van Moolenbroek }
973*00b67f09SDavid van Moolenbroek
974*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbt_destroy2(dns_rbt_t ** rbtp,unsigned int quantum)975*00b67f09SDavid van Moolenbroek dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum) {
976*00b67f09SDavid van Moolenbroek dns_rbt_t *rbt;
977*00b67f09SDavid van Moolenbroek
978*00b67f09SDavid van Moolenbroek REQUIRE(rbtp != NULL && VALID_RBT(*rbtp));
979*00b67f09SDavid van Moolenbroek
980*00b67f09SDavid van Moolenbroek rbt = *rbtp;
981*00b67f09SDavid van Moolenbroek
982*00b67f09SDavid van Moolenbroek deletetreeflat(rbt, quantum, &rbt->root);
983*00b67f09SDavid van Moolenbroek if (rbt->root != NULL)
984*00b67f09SDavid van Moolenbroek return (ISC_R_QUOTA);
985*00b67f09SDavid van Moolenbroek
986*00b67f09SDavid van Moolenbroek INSIST(rbt->nodecount == 0);
987*00b67f09SDavid van Moolenbroek
988*00b67f09SDavid van Moolenbroek rbt->mmap_location = NULL;
989*00b67f09SDavid van Moolenbroek
990*00b67f09SDavid van Moolenbroek if (rbt->hashtable != NULL)
991*00b67f09SDavid van Moolenbroek isc_mem_put(rbt->mctx, rbt->hashtable,
992*00b67f09SDavid van Moolenbroek rbt->hashsize * sizeof(dns_rbtnode_t *));
993*00b67f09SDavid van Moolenbroek
994*00b67f09SDavid van Moolenbroek rbt->magic = 0;
995*00b67f09SDavid van Moolenbroek
996*00b67f09SDavid van Moolenbroek isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));
997*00b67f09SDavid van Moolenbroek *rbtp = NULL;
998*00b67f09SDavid van Moolenbroek return (ISC_R_SUCCESS);
999*00b67f09SDavid van Moolenbroek }
1000*00b67f09SDavid van Moolenbroek
1001*00b67f09SDavid van Moolenbroek unsigned int
dns_rbt_nodecount(dns_rbt_t * rbt)1002*00b67f09SDavid van Moolenbroek dns_rbt_nodecount(dns_rbt_t *rbt) {
1003*00b67f09SDavid van Moolenbroek
1004*00b67f09SDavid van Moolenbroek REQUIRE(VALID_RBT(rbt));
1005*00b67f09SDavid van Moolenbroek
1006*00b67f09SDavid van Moolenbroek return (rbt->nodecount);
1007*00b67f09SDavid van Moolenbroek }
1008*00b67f09SDavid van Moolenbroek
1009*00b67f09SDavid van Moolenbroek unsigned int
dns_rbt_hashsize(dns_rbt_t * rbt)1010*00b67f09SDavid van Moolenbroek dns_rbt_hashsize(dns_rbt_t *rbt) {
1011*00b67f09SDavid van Moolenbroek
1012*00b67f09SDavid van Moolenbroek REQUIRE(VALID_RBT(rbt));
1013*00b67f09SDavid van Moolenbroek
1014*00b67f09SDavid van Moolenbroek return (rbt->hashsize);
1015*00b67f09SDavid van Moolenbroek }
1016*00b67f09SDavid van Moolenbroek
1017*00b67f09SDavid van Moolenbroek static inline isc_result_t
chain_name(dns_rbtnodechain_t * chain,dns_name_t * name,isc_boolean_t include_chain_end)1018*00b67f09SDavid van Moolenbroek chain_name(dns_rbtnodechain_t *chain, dns_name_t *name,
1019*00b67f09SDavid van Moolenbroek isc_boolean_t include_chain_end)
1020*00b67f09SDavid van Moolenbroek {
1021*00b67f09SDavid van Moolenbroek dns_name_t nodename;
1022*00b67f09SDavid van Moolenbroek isc_result_t result = ISC_R_SUCCESS;
1023*00b67f09SDavid van Moolenbroek int i;
1024*00b67f09SDavid van Moolenbroek
1025*00b67f09SDavid van Moolenbroek dns_name_init(&nodename, NULL);
1026*00b67f09SDavid van Moolenbroek
1027*00b67f09SDavid van Moolenbroek if (include_chain_end && chain->end != NULL) {
1028*00b67f09SDavid van Moolenbroek NODENAME(chain->end, &nodename);
1029*00b67f09SDavid van Moolenbroek result = dns_name_copy(&nodename, name, NULL);
1030*00b67f09SDavid van Moolenbroek if (result != ISC_R_SUCCESS)
1031*00b67f09SDavid van Moolenbroek return (result);
1032*00b67f09SDavid van Moolenbroek } else
1033*00b67f09SDavid van Moolenbroek dns_name_reset(name);
1034*00b67f09SDavid van Moolenbroek
1035*00b67f09SDavid van Moolenbroek for (i = (int)chain->level_count - 1; i >= 0; i--) {
1036*00b67f09SDavid van Moolenbroek NODENAME(chain->levels[i], &nodename);
1037*00b67f09SDavid van Moolenbroek result = dns_name_concatenate(name, &nodename, name, NULL);
1038*00b67f09SDavid van Moolenbroek
1039*00b67f09SDavid van Moolenbroek if (result != ISC_R_SUCCESS)
1040*00b67f09SDavid van Moolenbroek return (result);
1041*00b67f09SDavid van Moolenbroek }
1042*00b67f09SDavid van Moolenbroek return (result);
1043*00b67f09SDavid van Moolenbroek }
1044*00b67f09SDavid van Moolenbroek
1045*00b67f09SDavid van Moolenbroek static inline isc_result_t
move_chain_to_last(dns_rbtnodechain_t * chain,dns_rbtnode_t * node)1046*00b67f09SDavid van Moolenbroek move_chain_to_last(dns_rbtnodechain_t *chain, dns_rbtnode_t *node) {
1047*00b67f09SDavid van Moolenbroek do {
1048*00b67f09SDavid van Moolenbroek /*
1049*00b67f09SDavid van Moolenbroek * Go as far right and then down as much as possible,
1050*00b67f09SDavid van Moolenbroek * as long as the rightmost node has a down pointer.
1051*00b67f09SDavid van Moolenbroek */
1052*00b67f09SDavid van Moolenbroek while (RIGHT(node) != NULL)
1053*00b67f09SDavid van Moolenbroek node = RIGHT(node);
1054*00b67f09SDavid van Moolenbroek
1055*00b67f09SDavid van Moolenbroek if (DOWN(node) == NULL)
1056*00b67f09SDavid van Moolenbroek break;
1057*00b67f09SDavid van Moolenbroek
1058*00b67f09SDavid van Moolenbroek ADD_LEVEL(chain, node);
1059*00b67f09SDavid van Moolenbroek node = DOWN(node);
1060*00b67f09SDavid van Moolenbroek } while (1);
1061*00b67f09SDavid van Moolenbroek
1062*00b67f09SDavid van Moolenbroek chain->end = node;
1063*00b67f09SDavid van Moolenbroek
1064*00b67f09SDavid van Moolenbroek return (ISC_R_SUCCESS);
1065*00b67f09SDavid van Moolenbroek }
1066*00b67f09SDavid van Moolenbroek
1067*00b67f09SDavid van Moolenbroek /*
1068*00b67f09SDavid van Moolenbroek * Add 'name' to tree, initializing its data pointer with 'data'.
1069*00b67f09SDavid van Moolenbroek */
1070*00b67f09SDavid van Moolenbroek
1071*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbt_addnode(dns_rbt_t * rbt,dns_name_t * name,dns_rbtnode_t ** nodep)1072*00b67f09SDavid van Moolenbroek dns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep) {
1073*00b67f09SDavid van Moolenbroek /*
1074*00b67f09SDavid van Moolenbroek * Does this thing have too many variables or what?
1075*00b67f09SDavid van Moolenbroek */
1076*00b67f09SDavid van Moolenbroek dns_rbtnode_t **root, *parent, *child, *current, *new_current;
1077*00b67f09SDavid van Moolenbroek dns_name_t *add_name, *new_name, current_name, *prefix, *suffix;
1078*00b67f09SDavid van Moolenbroek dns_fixedname_t fixedcopy, fixedprefix, fixedsuffix, fnewname;
1079*00b67f09SDavid van Moolenbroek dns_offsets_t current_offsets;
1080*00b67f09SDavid van Moolenbroek dns_namereln_t compared;
1081*00b67f09SDavid van Moolenbroek isc_result_t result = ISC_R_SUCCESS;
1082*00b67f09SDavid van Moolenbroek dns_rbtnodechain_t chain;
1083*00b67f09SDavid van Moolenbroek unsigned int common_labels;
1084*00b67f09SDavid van Moolenbroek unsigned int nlabels, hlabels;
1085*00b67f09SDavid van Moolenbroek int order;
1086*00b67f09SDavid van Moolenbroek
1087*00b67f09SDavid van Moolenbroek REQUIRE(VALID_RBT(rbt));
1088*00b67f09SDavid van Moolenbroek REQUIRE(dns_name_isabsolute(name));
1089*00b67f09SDavid van Moolenbroek REQUIRE(nodep != NULL && *nodep == NULL);
1090*00b67f09SDavid van Moolenbroek
1091*00b67f09SDavid van Moolenbroek /*
1092*00b67f09SDavid van Moolenbroek * Create a copy of the name so the original name structure is
1093*00b67f09SDavid van Moolenbroek * not modified.
1094*00b67f09SDavid van Moolenbroek */
1095*00b67f09SDavid van Moolenbroek dns_fixedname_init(&fixedcopy);
1096*00b67f09SDavid van Moolenbroek add_name = dns_fixedname_name(&fixedcopy);
1097*00b67f09SDavid van Moolenbroek dns_name_clone(name, add_name);
1098*00b67f09SDavid van Moolenbroek
1099*00b67f09SDavid van Moolenbroek if (rbt->root == NULL) {
1100*00b67f09SDavid van Moolenbroek result = create_node(rbt->mctx, add_name, &new_current);
1101*00b67f09SDavid van Moolenbroek if (result == ISC_R_SUCCESS) {
1102*00b67f09SDavid van Moolenbroek rbt->nodecount++;
1103*00b67f09SDavid van Moolenbroek new_current->is_root = 1;
1104*00b67f09SDavid van Moolenbroek rbt->root = new_current;
1105*00b67f09SDavid van Moolenbroek *nodep = new_current;
1106*00b67f09SDavid van Moolenbroek hash_node(rbt, new_current, name);
1107*00b67f09SDavid van Moolenbroek }
1108*00b67f09SDavid van Moolenbroek return (result);
1109*00b67f09SDavid van Moolenbroek }
1110*00b67f09SDavid van Moolenbroek
1111*00b67f09SDavid van Moolenbroek dns_rbtnodechain_init(&chain, rbt->mctx);
1112*00b67f09SDavid van Moolenbroek
1113*00b67f09SDavid van Moolenbroek dns_fixedname_init(&fixedprefix);
1114*00b67f09SDavid van Moolenbroek dns_fixedname_init(&fixedsuffix);
1115*00b67f09SDavid van Moolenbroek prefix = dns_fixedname_name(&fixedprefix);
1116*00b67f09SDavid van Moolenbroek suffix = dns_fixedname_name(&fixedsuffix);
1117*00b67f09SDavid van Moolenbroek
1118*00b67f09SDavid van Moolenbroek root = &rbt->root;
1119*00b67f09SDavid van Moolenbroek INSIST(IS_ROOT(*root));
1120*00b67f09SDavid van Moolenbroek parent = NULL;
1121*00b67f09SDavid van Moolenbroek current = NULL;
1122*00b67f09SDavid van Moolenbroek child = *root;
1123*00b67f09SDavid van Moolenbroek dns_name_init(¤t_name, current_offsets);
1124*00b67f09SDavid van Moolenbroek dns_fixedname_init(&fnewname);
1125*00b67f09SDavid van Moolenbroek new_name = dns_fixedname_name(&fnewname);
1126*00b67f09SDavid van Moolenbroek nlabels = dns_name_countlabels(name);
1127*00b67f09SDavid van Moolenbroek hlabels = 0;
1128*00b67f09SDavid van Moolenbroek
1129*00b67f09SDavid van Moolenbroek do {
1130*00b67f09SDavid van Moolenbroek current = child;
1131*00b67f09SDavid van Moolenbroek
1132*00b67f09SDavid van Moolenbroek NODENAME(current, ¤t_name);
1133*00b67f09SDavid van Moolenbroek compared = dns_name_fullcompare(add_name, ¤t_name,
1134*00b67f09SDavid van Moolenbroek &order, &common_labels);
1135*00b67f09SDavid van Moolenbroek
1136*00b67f09SDavid van Moolenbroek if (compared == dns_namereln_equal) {
1137*00b67f09SDavid van Moolenbroek *nodep = current;
1138*00b67f09SDavid van Moolenbroek result = ISC_R_EXISTS;
1139*00b67f09SDavid van Moolenbroek break;
1140*00b67f09SDavid van Moolenbroek
1141*00b67f09SDavid van Moolenbroek }
1142*00b67f09SDavid van Moolenbroek
1143*00b67f09SDavid van Moolenbroek if (compared == dns_namereln_none) {
1144*00b67f09SDavid van Moolenbroek
1145*00b67f09SDavid van Moolenbroek if (order < 0) {
1146*00b67f09SDavid van Moolenbroek parent = current;
1147*00b67f09SDavid van Moolenbroek child = LEFT(current);
1148*00b67f09SDavid van Moolenbroek
1149*00b67f09SDavid van Moolenbroek } else if (order > 0) {
1150*00b67f09SDavid van Moolenbroek parent = current;
1151*00b67f09SDavid van Moolenbroek child = RIGHT(current);
1152*00b67f09SDavid van Moolenbroek
1153*00b67f09SDavid van Moolenbroek }
1154*00b67f09SDavid van Moolenbroek
1155*00b67f09SDavid van Moolenbroek } else {
1156*00b67f09SDavid van Moolenbroek /*
1157*00b67f09SDavid van Moolenbroek * This name has some suffix in common with the
1158*00b67f09SDavid van Moolenbroek * name at the current node. If the name at
1159*00b67f09SDavid van Moolenbroek * the current node is shorter, that means the
1160*00b67f09SDavid van Moolenbroek * new name should be in a subtree. If the
1161*00b67f09SDavid van Moolenbroek * name at the current node is longer, that means
1162*00b67f09SDavid van Moolenbroek * the down pointer to this tree should point
1163*00b67f09SDavid van Moolenbroek * to a new tree that has the common suffix, and
1164*00b67f09SDavid van Moolenbroek * the non-common parts of these two names should
1165*00b67f09SDavid van Moolenbroek * start a new tree.
1166*00b67f09SDavid van Moolenbroek */
1167*00b67f09SDavid van Moolenbroek hlabels += common_labels;
1168*00b67f09SDavid van Moolenbroek if (compared == dns_namereln_subdomain) {
1169*00b67f09SDavid van Moolenbroek /*
1170*00b67f09SDavid van Moolenbroek * All of the existing labels are in common,
1171*00b67f09SDavid van Moolenbroek * so the new name is in a subtree.
1172*00b67f09SDavid van Moolenbroek * Whack off the common labels for the
1173*00b67f09SDavid van Moolenbroek * not-in-common part to be searched for
1174*00b67f09SDavid van Moolenbroek * in the next level.
1175*00b67f09SDavid van Moolenbroek */
1176*00b67f09SDavid van Moolenbroek dns_name_split(add_name, common_labels,
1177*00b67f09SDavid van Moolenbroek add_name, NULL);
1178*00b67f09SDavid van Moolenbroek
1179*00b67f09SDavid van Moolenbroek /*
1180*00b67f09SDavid van Moolenbroek * Follow the down pointer (possibly NULL).
1181*00b67f09SDavid van Moolenbroek */
1182*00b67f09SDavid van Moolenbroek root = &DOWN(current);
1183*00b67f09SDavid van Moolenbroek
1184*00b67f09SDavid van Moolenbroek INSIST(*root == NULL ||
1185*00b67f09SDavid van Moolenbroek (IS_ROOT(*root) &&
1186*00b67f09SDavid van Moolenbroek PARENT(*root) == current));
1187*00b67f09SDavid van Moolenbroek
1188*00b67f09SDavid van Moolenbroek parent = NULL;
1189*00b67f09SDavid van Moolenbroek child = DOWN(current);
1190*00b67f09SDavid van Moolenbroek ADD_LEVEL(&chain, current);
1191*00b67f09SDavid van Moolenbroek
1192*00b67f09SDavid van Moolenbroek } else {
1193*00b67f09SDavid van Moolenbroek /*
1194*00b67f09SDavid van Moolenbroek * The number of labels in common is fewer
1195*00b67f09SDavid van Moolenbroek * than the number of labels at the current
1196*00b67f09SDavid van Moolenbroek * node, so the current node must be adjusted
1197*00b67f09SDavid van Moolenbroek * to have just the common suffix, and a down
1198*00b67f09SDavid van Moolenbroek * pointer made to a new tree.
1199*00b67f09SDavid van Moolenbroek */
1200*00b67f09SDavid van Moolenbroek
1201*00b67f09SDavid van Moolenbroek INSIST(compared == dns_namereln_commonancestor
1202*00b67f09SDavid van Moolenbroek || compared == dns_namereln_contains);
1203*00b67f09SDavid van Moolenbroek
1204*00b67f09SDavid van Moolenbroek /*
1205*00b67f09SDavid van Moolenbroek * Ensure the number of levels in the tree
1206*00b67f09SDavid van Moolenbroek * does not exceed the number of logical
1207*00b67f09SDavid van Moolenbroek * levels allowed by DNSSEC.
1208*00b67f09SDavid van Moolenbroek *
1209*00b67f09SDavid van Moolenbroek * XXXDCL need a better error result?
1210*00b67f09SDavid van Moolenbroek *
1211*00b67f09SDavid van Moolenbroek * XXXDCL Since chain ancestors were removed,
1212*00b67f09SDavid van Moolenbroek * no longer used by addonlevel(),
1213*00b67f09SDavid van Moolenbroek * this is the only real use of chains in the
1214*00b67f09SDavid van Moolenbroek * function. It could be done instead with
1215*00b67f09SDavid van Moolenbroek * a simple integer variable, but I am pressed
1216*00b67f09SDavid van Moolenbroek * for time.
1217*00b67f09SDavid van Moolenbroek */
1218*00b67f09SDavid van Moolenbroek if (chain.level_count ==
1219*00b67f09SDavid van Moolenbroek (sizeof(chain.levels) /
1220*00b67f09SDavid van Moolenbroek sizeof(*chain.levels))) {
1221*00b67f09SDavid van Moolenbroek result = ISC_R_NOSPACE;
1222*00b67f09SDavid van Moolenbroek break;
1223*00b67f09SDavid van Moolenbroek }
1224*00b67f09SDavid van Moolenbroek
1225*00b67f09SDavid van Moolenbroek /*
1226*00b67f09SDavid van Moolenbroek * Split the name into two parts, a prefix
1227*00b67f09SDavid van Moolenbroek * which is the not-in-common parts of the
1228*00b67f09SDavid van Moolenbroek * two names and a suffix that is the common
1229*00b67f09SDavid van Moolenbroek * parts of them.
1230*00b67f09SDavid van Moolenbroek */
1231*00b67f09SDavid van Moolenbroek dns_name_split(¤t_name, common_labels,
1232*00b67f09SDavid van Moolenbroek prefix, suffix);
1233*00b67f09SDavid van Moolenbroek result = create_node(rbt->mctx, suffix,
1234*00b67f09SDavid van Moolenbroek &new_current);
1235*00b67f09SDavid van Moolenbroek
1236*00b67f09SDavid van Moolenbroek if (result != ISC_R_SUCCESS)
1237*00b67f09SDavid van Moolenbroek break;
1238*00b67f09SDavid van Moolenbroek
1239*00b67f09SDavid van Moolenbroek /*
1240*00b67f09SDavid van Moolenbroek * Reproduce the tree attributes of the
1241*00b67f09SDavid van Moolenbroek * current node.
1242*00b67f09SDavid van Moolenbroek */
1243*00b67f09SDavid van Moolenbroek new_current->is_root = current->is_root;
1244*00b67f09SDavid van Moolenbroek if (current->nsec == DNS_RBT_NSEC_HAS_NSEC)
1245*00b67f09SDavid van Moolenbroek new_current->nsec = DNS_RBT_NSEC_NORMAL;
1246*00b67f09SDavid van Moolenbroek else
1247*00b67f09SDavid van Moolenbroek new_current->nsec = current->nsec;
1248*00b67f09SDavid van Moolenbroek PARENT(new_current) = PARENT(current);
1249*00b67f09SDavid van Moolenbroek LEFT(new_current) = LEFT(current);
1250*00b67f09SDavid van Moolenbroek RIGHT(new_current) = RIGHT(current);
1251*00b67f09SDavid van Moolenbroek COLOR(new_current) = COLOR(current);
1252*00b67f09SDavid van Moolenbroek
1253*00b67f09SDavid van Moolenbroek /*
1254*00b67f09SDavid van Moolenbroek * Fix pointers that were to the current node.
1255*00b67f09SDavid van Moolenbroek */
1256*00b67f09SDavid van Moolenbroek if (parent != NULL) {
1257*00b67f09SDavid van Moolenbroek if (LEFT(parent) == current)
1258*00b67f09SDavid van Moolenbroek LEFT(parent) = new_current;
1259*00b67f09SDavid van Moolenbroek else
1260*00b67f09SDavid van Moolenbroek RIGHT(parent) = new_current;
1261*00b67f09SDavid van Moolenbroek }
1262*00b67f09SDavid van Moolenbroek if (LEFT(new_current) != NULL)
1263*00b67f09SDavid van Moolenbroek PARENT(LEFT(new_current)) =
1264*00b67f09SDavid van Moolenbroek new_current;
1265*00b67f09SDavid van Moolenbroek if (RIGHT(new_current) != NULL)
1266*00b67f09SDavid van Moolenbroek PARENT(RIGHT(new_current)) =
1267*00b67f09SDavid van Moolenbroek new_current;
1268*00b67f09SDavid van Moolenbroek if (*root == current)
1269*00b67f09SDavid van Moolenbroek *root = new_current;
1270*00b67f09SDavid van Moolenbroek
1271*00b67f09SDavid van Moolenbroek NAMELEN(current) = prefix->length;
1272*00b67f09SDavid van Moolenbroek OFFSETLEN(current) = prefix->labels;
1273*00b67f09SDavid van Moolenbroek
1274*00b67f09SDavid van Moolenbroek /*
1275*00b67f09SDavid van Moolenbroek * Set up the new root of the next level.
1276*00b67f09SDavid van Moolenbroek * By definition it will not be the top
1277*00b67f09SDavid van Moolenbroek * level tree, so clear DNS_NAMEATTR_ABSOLUTE.
1278*00b67f09SDavid van Moolenbroek */
1279*00b67f09SDavid van Moolenbroek current->is_root = 1;
1280*00b67f09SDavid van Moolenbroek PARENT(current) = new_current;
1281*00b67f09SDavid van Moolenbroek DOWN(new_current) = current;
1282*00b67f09SDavid van Moolenbroek root = &DOWN(new_current);
1283*00b67f09SDavid van Moolenbroek
1284*00b67f09SDavid van Moolenbroek ADD_LEVEL(&chain, new_current);
1285*00b67f09SDavid van Moolenbroek
1286*00b67f09SDavid van Moolenbroek LEFT(current) = NULL;
1287*00b67f09SDavid van Moolenbroek RIGHT(current) = NULL;
1288*00b67f09SDavid van Moolenbroek
1289*00b67f09SDavid van Moolenbroek MAKE_BLACK(current);
1290*00b67f09SDavid van Moolenbroek ATTRS(current) &= ~DNS_NAMEATTR_ABSOLUTE;
1291*00b67f09SDavid van Moolenbroek
1292*00b67f09SDavid van Moolenbroek rbt->nodecount++;
1293*00b67f09SDavid van Moolenbroek dns_name_getlabelsequence(name,
1294*00b67f09SDavid van Moolenbroek nlabels - hlabels,
1295*00b67f09SDavid van Moolenbroek hlabels, new_name);
1296*00b67f09SDavid van Moolenbroek hash_node(rbt, new_current, new_name);
1297*00b67f09SDavid van Moolenbroek
1298*00b67f09SDavid van Moolenbroek if (common_labels ==
1299*00b67f09SDavid van Moolenbroek dns_name_countlabels(add_name)) {
1300*00b67f09SDavid van Moolenbroek /*
1301*00b67f09SDavid van Moolenbroek * The name has been added by pushing
1302*00b67f09SDavid van Moolenbroek * the not-in-common parts down to
1303*00b67f09SDavid van Moolenbroek * a new level.
1304*00b67f09SDavid van Moolenbroek */
1305*00b67f09SDavid van Moolenbroek *nodep = new_current;
1306*00b67f09SDavid van Moolenbroek return (ISC_R_SUCCESS);
1307*00b67f09SDavid van Moolenbroek
1308*00b67f09SDavid van Moolenbroek } else {
1309*00b67f09SDavid van Moolenbroek /*
1310*00b67f09SDavid van Moolenbroek * The current node has no data,
1311*00b67f09SDavid van Moolenbroek * because it is just a placeholder.
1312*00b67f09SDavid van Moolenbroek * Its data pointer is already NULL
1313*00b67f09SDavid van Moolenbroek * from create_node()), so there's
1314*00b67f09SDavid van Moolenbroek * nothing more to do to it.
1315*00b67f09SDavid van Moolenbroek */
1316*00b67f09SDavid van Moolenbroek
1317*00b67f09SDavid van Moolenbroek /*
1318*00b67f09SDavid van Moolenbroek * The not-in-common parts of the new
1319*00b67f09SDavid van Moolenbroek * name will be inserted into the new
1320*00b67f09SDavid van Moolenbroek * level following this loop (unless
1321*00b67f09SDavid van Moolenbroek * result != ISC_R_SUCCESS, which
1322*00b67f09SDavid van Moolenbroek * is tested after the loop ends).
1323*00b67f09SDavid van Moolenbroek */
1324*00b67f09SDavid van Moolenbroek dns_name_split(add_name, common_labels,
1325*00b67f09SDavid van Moolenbroek add_name, NULL);
1326*00b67f09SDavid van Moolenbroek
1327*00b67f09SDavid van Moolenbroek break;
1328*00b67f09SDavid van Moolenbroek }
1329*00b67f09SDavid van Moolenbroek
1330*00b67f09SDavid van Moolenbroek }
1331*00b67f09SDavid van Moolenbroek
1332*00b67f09SDavid van Moolenbroek }
1333*00b67f09SDavid van Moolenbroek
1334*00b67f09SDavid van Moolenbroek } while (child != NULL);
1335*00b67f09SDavid van Moolenbroek
1336*00b67f09SDavid van Moolenbroek if (result == ISC_R_SUCCESS)
1337*00b67f09SDavid van Moolenbroek result = create_node(rbt->mctx, add_name, &new_current);
1338*00b67f09SDavid van Moolenbroek
1339*00b67f09SDavid van Moolenbroek if (result == ISC_R_SUCCESS) {
1340*00b67f09SDavid van Moolenbroek addonlevel(new_current, current, order, root);
1341*00b67f09SDavid van Moolenbroek rbt->nodecount++;
1342*00b67f09SDavid van Moolenbroek *nodep = new_current;
1343*00b67f09SDavid van Moolenbroek hash_node(rbt, new_current, name);
1344*00b67f09SDavid van Moolenbroek }
1345*00b67f09SDavid van Moolenbroek
1346*00b67f09SDavid van Moolenbroek return (result);
1347*00b67f09SDavid van Moolenbroek }
1348*00b67f09SDavid van Moolenbroek
1349*00b67f09SDavid van Moolenbroek /*
1350*00b67f09SDavid van Moolenbroek * Add a name to the tree of trees, associating it with some data.
1351*00b67f09SDavid van Moolenbroek */
1352*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbt_addname(dns_rbt_t * rbt,dns_name_t * name,void * data)1353*00b67f09SDavid van Moolenbroek dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data) {
1354*00b67f09SDavid van Moolenbroek isc_result_t result;
1355*00b67f09SDavid van Moolenbroek dns_rbtnode_t *node;
1356*00b67f09SDavid van Moolenbroek
1357*00b67f09SDavid van Moolenbroek REQUIRE(VALID_RBT(rbt));
1358*00b67f09SDavid van Moolenbroek REQUIRE(dns_name_isabsolute(name));
1359*00b67f09SDavid van Moolenbroek
1360*00b67f09SDavid van Moolenbroek node = NULL;
1361*00b67f09SDavid van Moolenbroek
1362*00b67f09SDavid van Moolenbroek result = dns_rbt_addnode(rbt, name, &node);
1363*00b67f09SDavid van Moolenbroek
1364*00b67f09SDavid van Moolenbroek /*
1365*00b67f09SDavid van Moolenbroek * dns_rbt_addnode will report the node exists even when
1366*00b67f09SDavid van Moolenbroek * it does not have data associated with it, but the
1367*00b67f09SDavid van Moolenbroek * dns_rbt_*name functions all behave depending on whether
1368*00b67f09SDavid van Moolenbroek * there is data associated with a node.
1369*00b67f09SDavid van Moolenbroek */
1370*00b67f09SDavid van Moolenbroek if (result == ISC_R_SUCCESS ||
1371*00b67f09SDavid van Moolenbroek (result == ISC_R_EXISTS && DATA(node) == NULL)) {
1372*00b67f09SDavid van Moolenbroek DATA(node) = data;
1373*00b67f09SDavid van Moolenbroek result = ISC_R_SUCCESS;
1374*00b67f09SDavid van Moolenbroek }
1375*00b67f09SDavid van Moolenbroek
1376*00b67f09SDavid van Moolenbroek return (result);
1377*00b67f09SDavid van Moolenbroek }
1378*00b67f09SDavid van Moolenbroek
1379*00b67f09SDavid van Moolenbroek /*
1380*00b67f09SDavid van Moolenbroek * Find the node for "name" in the tree of trees.
1381*00b67f09SDavid van Moolenbroek */
1382*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbt_findnode(dns_rbt_t * rbt,dns_name_t * name,dns_name_t * foundname,dns_rbtnode_t ** node,dns_rbtnodechain_t * chain,unsigned int options,dns_rbtfindcallback_t callback,void * callback_arg)1383*00b67f09SDavid van Moolenbroek dns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname,
1384*00b67f09SDavid van Moolenbroek dns_rbtnode_t **node, dns_rbtnodechain_t *chain,
1385*00b67f09SDavid van Moolenbroek unsigned int options, dns_rbtfindcallback_t callback,
1386*00b67f09SDavid van Moolenbroek void *callback_arg)
1387*00b67f09SDavid van Moolenbroek {
1388*00b67f09SDavid van Moolenbroek dns_rbtnode_t *current, *last_compared, *current_root;
1389*00b67f09SDavid van Moolenbroek dns_rbtnodechain_t localchain;
1390*00b67f09SDavid van Moolenbroek dns_name_t *search_name, current_name, *callback_name;
1391*00b67f09SDavid van Moolenbroek dns_fixedname_t fixedcallbackname, fixedsearchname;
1392*00b67f09SDavid van Moolenbroek dns_namereln_t compared;
1393*00b67f09SDavid van Moolenbroek isc_result_t result, saved_result;
1394*00b67f09SDavid van Moolenbroek unsigned int common_labels;
1395*00b67f09SDavid van Moolenbroek unsigned int hlabels = 0;
1396*00b67f09SDavid van Moolenbroek int order;
1397*00b67f09SDavid van Moolenbroek
1398*00b67f09SDavid van Moolenbroek REQUIRE(VALID_RBT(rbt));
1399*00b67f09SDavid van Moolenbroek REQUIRE(dns_name_isabsolute(name));
1400*00b67f09SDavid van Moolenbroek REQUIRE(node != NULL && *node == NULL);
1401*00b67f09SDavid van Moolenbroek REQUIRE((options & (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR))
1402*00b67f09SDavid van Moolenbroek != (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR));
1403*00b67f09SDavid van Moolenbroek
1404*00b67f09SDavid van Moolenbroek /*
1405*00b67f09SDavid van Moolenbroek * If there is a chain it needs to appear to be in a sane state,
1406*00b67f09SDavid van Moolenbroek * otherwise a chain is still needed to generate foundname and
1407*00b67f09SDavid van Moolenbroek * callback_name.
1408*00b67f09SDavid van Moolenbroek */
1409*00b67f09SDavid van Moolenbroek if (chain == NULL) {
1410*00b67f09SDavid van Moolenbroek options |= DNS_RBTFIND_NOPREDECESSOR;
1411*00b67f09SDavid van Moolenbroek chain = &localchain;
1412*00b67f09SDavid van Moolenbroek dns_rbtnodechain_init(chain, rbt->mctx);
1413*00b67f09SDavid van Moolenbroek } else
1414*00b67f09SDavid van Moolenbroek dns_rbtnodechain_reset(chain);
1415*00b67f09SDavid van Moolenbroek
1416*00b67f09SDavid van Moolenbroek if (rbt->root == NULL)
1417*00b67f09SDavid van Moolenbroek return (ISC_R_NOTFOUND);
1418*00b67f09SDavid van Moolenbroek
1419*00b67f09SDavid van Moolenbroek /*
1420*00b67f09SDavid van Moolenbroek * Appease GCC about variables it incorrectly thinks are
1421*00b67f09SDavid van Moolenbroek * possibly used uninitialized.
1422*00b67f09SDavid van Moolenbroek */
1423*00b67f09SDavid van Moolenbroek compared = dns_namereln_none;
1424*00b67f09SDavid van Moolenbroek last_compared = NULL;
1425*00b67f09SDavid van Moolenbroek order = 0;
1426*00b67f09SDavid van Moolenbroek
1427*00b67f09SDavid van Moolenbroek dns_fixedname_init(&fixedcallbackname);
1428*00b67f09SDavid van Moolenbroek callback_name = dns_fixedname_name(&fixedcallbackname);
1429*00b67f09SDavid van Moolenbroek
1430*00b67f09SDavid van Moolenbroek /*
1431*00b67f09SDavid van Moolenbroek * search_name is the name segment being sought in each tree level.
1432*00b67f09SDavid van Moolenbroek * By using a fixedname, the search_name will definitely have offsets
1433*00b67f09SDavid van Moolenbroek * for use by any splitting.
1434*00b67f09SDavid van Moolenbroek * By using dns_name_clone, no name data should be copied thanks to
1435*00b67f09SDavid van Moolenbroek * the lack of bitstring labels.
1436*00b67f09SDavid van Moolenbroek */
1437*00b67f09SDavid van Moolenbroek dns_fixedname_init(&fixedsearchname);
1438*00b67f09SDavid van Moolenbroek search_name = dns_fixedname_name(&fixedsearchname);
1439*00b67f09SDavid van Moolenbroek dns_name_clone(name, search_name);
1440*00b67f09SDavid van Moolenbroek
1441*00b67f09SDavid van Moolenbroek dns_name_init(¤t_name, NULL);
1442*00b67f09SDavid van Moolenbroek
1443*00b67f09SDavid van Moolenbroek saved_result = ISC_R_SUCCESS;
1444*00b67f09SDavid van Moolenbroek current = rbt->root;
1445*00b67f09SDavid van Moolenbroek current_root = rbt->root;
1446*00b67f09SDavid van Moolenbroek
1447*00b67f09SDavid van Moolenbroek while (current != NULL) {
1448*00b67f09SDavid van Moolenbroek NODENAME(current, ¤t_name);
1449*00b67f09SDavid van Moolenbroek compared = dns_name_fullcompare(search_name, ¤t_name,
1450*00b67f09SDavid van Moolenbroek &order, &common_labels);
1451*00b67f09SDavid van Moolenbroek /*
1452*00b67f09SDavid van Moolenbroek * last_compared is used as a shortcut to start (or
1453*00b67f09SDavid van Moolenbroek * continue rather) finding the stop-node of the search
1454*00b67f09SDavid van Moolenbroek * when hashing was used (see much below in this
1455*00b67f09SDavid van Moolenbroek * function).
1456*00b67f09SDavid van Moolenbroek */
1457*00b67f09SDavid van Moolenbroek last_compared = current;
1458*00b67f09SDavid van Moolenbroek
1459*00b67f09SDavid van Moolenbroek if (compared == dns_namereln_equal)
1460*00b67f09SDavid van Moolenbroek break;
1461*00b67f09SDavid van Moolenbroek
1462*00b67f09SDavid van Moolenbroek if (compared == dns_namereln_none) {
1463*00b67f09SDavid van Moolenbroek #ifdef DNS_RBT_USEHASH
1464*00b67f09SDavid van Moolenbroek /*
1465*00b67f09SDavid van Moolenbroek * Here, current is pointing at a subtree root
1466*00b67f09SDavid van Moolenbroek * node. We try to find a matching node using
1467*00b67f09SDavid van Moolenbroek * the hashtable. We can get one of 3 results
1468*00b67f09SDavid van Moolenbroek * here: (a) we locate the matching node, (b) we
1469*00b67f09SDavid van Moolenbroek * find a node to which the current node has a
1470*00b67f09SDavid van Moolenbroek * subdomain relation, (c) we fail to find (a)
1471*00b67f09SDavid van Moolenbroek * or (b).
1472*00b67f09SDavid van Moolenbroek */
1473*00b67f09SDavid van Moolenbroek
1474*00b67f09SDavid van Moolenbroek dns_name_t hash_name;
1475*00b67f09SDavid van Moolenbroek dns_rbtnode_t *hnode;
1476*00b67f09SDavid van Moolenbroek dns_rbtnode_t *up_current;
1477*00b67f09SDavid van Moolenbroek unsigned int nlabels;
1478*00b67f09SDavid van Moolenbroek unsigned int tlabels = 1;
1479*00b67f09SDavid van Moolenbroek unsigned int hash;
1480*00b67f09SDavid van Moolenbroek
1481*00b67f09SDavid van Moolenbroek /*
1482*00b67f09SDavid van Moolenbroek * If there is no hash table, hashing can't be done.
1483*00b67f09SDavid van Moolenbroek */
1484*00b67f09SDavid van Moolenbroek if (rbt->hashtable == NULL)
1485*00b67f09SDavid van Moolenbroek goto nohash;
1486*00b67f09SDavid van Moolenbroek
1487*00b67f09SDavid van Moolenbroek /*
1488*00b67f09SDavid van Moolenbroek * The case of current != current_root, that
1489*00b67f09SDavid van Moolenbroek * means a left or right pointer was followed,
1490*00b67f09SDavid van Moolenbroek * only happens when the algorithm fell through to
1491*00b67f09SDavid van Moolenbroek * the traditional binary search because of a
1492*00b67f09SDavid van Moolenbroek * bitstring label. Since we dropped the bitstring
1493*00b67f09SDavid van Moolenbroek * support, this should not happen.
1494*00b67f09SDavid van Moolenbroek */
1495*00b67f09SDavid van Moolenbroek INSIST(current == current_root);
1496*00b67f09SDavid van Moolenbroek
1497*00b67f09SDavid van Moolenbroek nlabels = dns_name_countlabels(search_name);
1498*00b67f09SDavid van Moolenbroek
1499*00b67f09SDavid van Moolenbroek /*
1500*00b67f09SDavid van Moolenbroek * current_root is the root of the current level, so
1501*00b67f09SDavid van Moolenbroek * it's parent is the same as it's "up" pointer.
1502*00b67f09SDavid van Moolenbroek */
1503*00b67f09SDavid van Moolenbroek up_current = PARENT(current_root);
1504*00b67f09SDavid van Moolenbroek dns_name_init(&hash_name, NULL);
1505*00b67f09SDavid van Moolenbroek
1506*00b67f09SDavid van Moolenbroek hashagain:
1507*00b67f09SDavid van Moolenbroek /*
1508*00b67f09SDavid van Moolenbroek * Compute the hash over the full absolute
1509*00b67f09SDavid van Moolenbroek * name. Look for the smallest suffix match at
1510*00b67f09SDavid van Moolenbroek * this tree level (hlevel), and then at every
1511*00b67f09SDavid van Moolenbroek * iteration, look for the next smallest suffix
1512*00b67f09SDavid van Moolenbroek * match (add another subdomain label to the
1513*00b67f09SDavid van Moolenbroek * absolute name being hashed).
1514*00b67f09SDavid van Moolenbroek */
1515*00b67f09SDavid van Moolenbroek dns_name_getlabelsequence(name,
1516*00b67f09SDavid van Moolenbroek nlabels - tlabels,
1517*00b67f09SDavid van Moolenbroek hlabels + tlabels,
1518*00b67f09SDavid van Moolenbroek &hash_name);
1519*00b67f09SDavid van Moolenbroek hash = dns_name_fullhash(&hash_name, ISC_FALSE);
1520*00b67f09SDavid van Moolenbroek dns_name_getlabelsequence(search_name,
1521*00b67f09SDavid van Moolenbroek nlabels - tlabels,
1522*00b67f09SDavid van Moolenbroek tlabels, &hash_name);
1523*00b67f09SDavid van Moolenbroek
1524*00b67f09SDavid van Moolenbroek /*
1525*00b67f09SDavid van Moolenbroek * Walk all the nodes in the hash bucket pointed
1526*00b67f09SDavid van Moolenbroek * by the computed hash value.
1527*00b67f09SDavid van Moolenbroek */
1528*00b67f09SDavid van Moolenbroek for (hnode = rbt->hashtable[hash % rbt->hashsize];
1529*00b67f09SDavid van Moolenbroek hnode != NULL;
1530*00b67f09SDavid van Moolenbroek hnode = hnode->hashnext)
1531*00b67f09SDavid van Moolenbroek {
1532*00b67f09SDavid van Moolenbroek dns_name_t hnode_name;
1533*00b67f09SDavid van Moolenbroek
1534*00b67f09SDavid van Moolenbroek if (hash != HASHVAL(hnode))
1535*00b67f09SDavid van Moolenbroek continue;
1536*00b67f09SDavid van Moolenbroek /*
1537*00b67f09SDavid van Moolenbroek * This checks that the hashed label
1538*00b67f09SDavid van Moolenbroek * sequence being looked up is at the
1539*00b67f09SDavid van Moolenbroek * same tree level, so that we don't
1540*00b67f09SDavid van Moolenbroek * match a labelsequence from some other
1541*00b67f09SDavid van Moolenbroek * subdomain.
1542*00b67f09SDavid van Moolenbroek */
1543*00b67f09SDavid van Moolenbroek if (get_upper_node(hnode) != up_current)
1544*00b67f09SDavid van Moolenbroek continue;
1545*00b67f09SDavid van Moolenbroek
1546*00b67f09SDavid van Moolenbroek dns_name_init(&hnode_name, NULL);
1547*00b67f09SDavid van Moolenbroek NODENAME(hnode, &hnode_name);
1548*00b67f09SDavid van Moolenbroek if (dns_name_equal(&hnode_name, &hash_name))
1549*00b67f09SDavid van Moolenbroek break;
1550*00b67f09SDavid van Moolenbroek }
1551*00b67f09SDavid van Moolenbroek
1552*00b67f09SDavid van Moolenbroek if (hnode != NULL) {
1553*00b67f09SDavid van Moolenbroek current = hnode;
1554*00b67f09SDavid van Moolenbroek /*
1555*00b67f09SDavid van Moolenbroek * This is an optimization. If hashing found
1556*00b67f09SDavid van Moolenbroek * the right node, the next call to
1557*00b67f09SDavid van Moolenbroek * dns_name_fullcompare() would obviously
1558*00b67f09SDavid van Moolenbroek * return _equal or _subdomain. Determine
1559*00b67f09SDavid van Moolenbroek * which of those would be the case by
1560*00b67f09SDavid van Moolenbroek * checking if the full name was hashed. Then
1561*00b67f09SDavid van Moolenbroek * make it look like dns_name_fullcompare
1562*00b67f09SDavid van Moolenbroek * was called and jump to the right place.
1563*00b67f09SDavid van Moolenbroek */
1564*00b67f09SDavid van Moolenbroek if (tlabels == nlabels) {
1565*00b67f09SDavid van Moolenbroek compared = dns_namereln_equal;
1566*00b67f09SDavid van Moolenbroek break;
1567*00b67f09SDavid van Moolenbroek } else {
1568*00b67f09SDavid van Moolenbroek common_labels = tlabels;
1569*00b67f09SDavid van Moolenbroek compared = dns_namereln_subdomain;
1570*00b67f09SDavid van Moolenbroek goto subdomain;
1571*00b67f09SDavid van Moolenbroek }
1572*00b67f09SDavid van Moolenbroek }
1573*00b67f09SDavid van Moolenbroek
1574*00b67f09SDavid van Moolenbroek if (tlabels++ < nlabels)
1575*00b67f09SDavid van Moolenbroek goto hashagain;
1576*00b67f09SDavid van Moolenbroek
1577*00b67f09SDavid van Moolenbroek /*
1578*00b67f09SDavid van Moolenbroek * All of the labels have been tried against the hash
1579*00b67f09SDavid van Moolenbroek * table. Since we dropped the support of bitstring
1580*00b67f09SDavid van Moolenbroek * labels, the name isn't in the table.
1581*00b67f09SDavid van Moolenbroek */
1582*00b67f09SDavid van Moolenbroek current = NULL;
1583*00b67f09SDavid van Moolenbroek continue;
1584*00b67f09SDavid van Moolenbroek
1585*00b67f09SDavid van Moolenbroek nohash:
1586*00b67f09SDavid van Moolenbroek #endif /* DNS_RBT_USEHASH */
1587*00b67f09SDavid van Moolenbroek /*
1588*00b67f09SDavid van Moolenbroek * Standard binary search tree movement.
1589*00b67f09SDavid van Moolenbroek */
1590*00b67f09SDavid van Moolenbroek if (order < 0)
1591*00b67f09SDavid van Moolenbroek current = LEFT(current);
1592*00b67f09SDavid van Moolenbroek else
1593*00b67f09SDavid van Moolenbroek current = RIGHT(current);
1594*00b67f09SDavid van Moolenbroek
1595*00b67f09SDavid van Moolenbroek } else {
1596*00b67f09SDavid van Moolenbroek /*
1597*00b67f09SDavid van Moolenbroek * The names have some common suffix labels.
1598*00b67f09SDavid van Moolenbroek *
1599*00b67f09SDavid van Moolenbroek * If the number in common are equal in length to
1600*00b67f09SDavid van Moolenbroek * the current node's name length, then follow the
1601*00b67f09SDavid van Moolenbroek * down pointer and search in the new tree.
1602*00b67f09SDavid van Moolenbroek */
1603*00b67f09SDavid van Moolenbroek if (compared == dns_namereln_subdomain) {
1604*00b67f09SDavid van Moolenbroek #ifdef DNS_RBT_USEHASH
1605*00b67f09SDavid van Moolenbroek subdomain:
1606*00b67f09SDavid van Moolenbroek #endif
1607*00b67f09SDavid van Moolenbroek /*
1608*00b67f09SDavid van Moolenbroek * Whack off the current node's common parts
1609*00b67f09SDavid van Moolenbroek * for the name to search in the next level.
1610*00b67f09SDavid van Moolenbroek */
1611*00b67f09SDavid van Moolenbroek dns_name_split(search_name, common_labels,
1612*00b67f09SDavid van Moolenbroek search_name, NULL);
1613*00b67f09SDavid van Moolenbroek hlabels += common_labels;
1614*00b67f09SDavid van Moolenbroek /*
1615*00b67f09SDavid van Moolenbroek * This might be the closest enclosing name.
1616*00b67f09SDavid van Moolenbroek */
1617*00b67f09SDavid van Moolenbroek if (DATA(current) != NULL ||
1618*00b67f09SDavid van Moolenbroek (options & DNS_RBTFIND_EMPTYDATA) != 0)
1619*00b67f09SDavid van Moolenbroek *node = current;
1620*00b67f09SDavid van Moolenbroek
1621*00b67f09SDavid van Moolenbroek /*
1622*00b67f09SDavid van Moolenbroek * Point the chain to the next level. This
1623*00b67f09SDavid van Moolenbroek * needs to be done before 'current' is pointed
1624*00b67f09SDavid van Moolenbroek * there because the callback in the next
1625*00b67f09SDavid van Moolenbroek * block of code needs the current 'current',
1626*00b67f09SDavid van Moolenbroek * but in the event the callback requests that
1627*00b67f09SDavid van Moolenbroek * the search be stopped then the
1628*00b67f09SDavid van Moolenbroek * DNS_R_PARTIALMATCH code at the end of this
1629*00b67f09SDavid van Moolenbroek * function needs the chain pointed to the
1630*00b67f09SDavid van Moolenbroek * next level.
1631*00b67f09SDavid van Moolenbroek */
1632*00b67f09SDavid van Moolenbroek ADD_LEVEL(chain, current);
1633*00b67f09SDavid van Moolenbroek
1634*00b67f09SDavid van Moolenbroek /*
1635*00b67f09SDavid van Moolenbroek * The caller may want to interrupt the
1636*00b67f09SDavid van Moolenbroek * downward search when certain special nodes
1637*00b67f09SDavid van Moolenbroek * are traversed. If this is a special node,
1638*00b67f09SDavid van Moolenbroek * the callback is used to learn what the
1639*00b67f09SDavid van Moolenbroek * caller wants to do.
1640*00b67f09SDavid van Moolenbroek */
1641*00b67f09SDavid van Moolenbroek if (callback != NULL &&
1642*00b67f09SDavid van Moolenbroek FINDCALLBACK(current)) {
1643*00b67f09SDavid van Moolenbroek result = chain_name(chain,
1644*00b67f09SDavid van Moolenbroek callback_name,
1645*00b67f09SDavid van Moolenbroek ISC_FALSE);
1646*00b67f09SDavid van Moolenbroek if (result != ISC_R_SUCCESS) {
1647*00b67f09SDavid van Moolenbroek dns_rbtnodechain_reset(chain);
1648*00b67f09SDavid van Moolenbroek return (result);
1649*00b67f09SDavid van Moolenbroek }
1650*00b67f09SDavid van Moolenbroek
1651*00b67f09SDavid van Moolenbroek result = (callback)(current,
1652*00b67f09SDavid van Moolenbroek callback_name,
1653*00b67f09SDavid van Moolenbroek callback_arg);
1654*00b67f09SDavid van Moolenbroek if (result != DNS_R_CONTINUE) {
1655*00b67f09SDavid van Moolenbroek saved_result = result;
1656*00b67f09SDavid van Moolenbroek /*
1657*00b67f09SDavid van Moolenbroek * Treat this node as if it
1658*00b67f09SDavid van Moolenbroek * had no down pointer.
1659*00b67f09SDavid van Moolenbroek */
1660*00b67f09SDavid van Moolenbroek current = NULL;
1661*00b67f09SDavid van Moolenbroek break;
1662*00b67f09SDavid van Moolenbroek }
1663*00b67f09SDavid van Moolenbroek }
1664*00b67f09SDavid van Moolenbroek
1665*00b67f09SDavid van Moolenbroek /*
1666*00b67f09SDavid van Moolenbroek * Finally, head to the next tree level.
1667*00b67f09SDavid van Moolenbroek */
1668*00b67f09SDavid van Moolenbroek current = DOWN(current);
1669*00b67f09SDavid van Moolenbroek current_root = current;
1670*00b67f09SDavid van Moolenbroek
1671*00b67f09SDavid van Moolenbroek } else {
1672*00b67f09SDavid van Moolenbroek /*
1673*00b67f09SDavid van Moolenbroek * Though there are labels in common, the
1674*00b67f09SDavid van Moolenbroek * entire name at this node is not common
1675*00b67f09SDavid van Moolenbroek * with the search name so the search
1676*00b67f09SDavid van Moolenbroek * name does not exist in the tree.
1677*00b67f09SDavid van Moolenbroek */
1678*00b67f09SDavid van Moolenbroek INSIST(compared == dns_namereln_commonancestor
1679*00b67f09SDavid van Moolenbroek || compared == dns_namereln_contains);
1680*00b67f09SDavid van Moolenbroek
1681*00b67f09SDavid van Moolenbroek current = NULL;
1682*00b67f09SDavid van Moolenbroek }
1683*00b67f09SDavid van Moolenbroek }
1684*00b67f09SDavid van Moolenbroek }
1685*00b67f09SDavid van Moolenbroek
1686*00b67f09SDavid van Moolenbroek /*
1687*00b67f09SDavid van Moolenbroek * If current is not NULL, NOEXACT is not disallowing exact matches,
1688*00b67f09SDavid van Moolenbroek * and either the node has data or an empty node is ok, return
1689*00b67f09SDavid van Moolenbroek * ISC_R_SUCCESS to indicate an exact match.
1690*00b67f09SDavid van Moolenbroek */
1691*00b67f09SDavid van Moolenbroek if (current != NULL && (options & DNS_RBTFIND_NOEXACT) == 0 &&
1692*00b67f09SDavid van Moolenbroek (DATA(current) != NULL ||
1693*00b67f09SDavid van Moolenbroek (options & DNS_RBTFIND_EMPTYDATA) != 0)) {
1694*00b67f09SDavid van Moolenbroek /*
1695*00b67f09SDavid van Moolenbroek * Found an exact match.
1696*00b67f09SDavid van Moolenbroek */
1697*00b67f09SDavid van Moolenbroek chain->end = current;
1698*00b67f09SDavid van Moolenbroek chain->level_matches = chain->level_count;
1699*00b67f09SDavid van Moolenbroek
1700*00b67f09SDavid van Moolenbroek if (foundname != NULL)
1701*00b67f09SDavid van Moolenbroek result = chain_name(chain, foundname, ISC_TRUE);
1702*00b67f09SDavid van Moolenbroek else
1703*00b67f09SDavid van Moolenbroek result = ISC_R_SUCCESS;
1704*00b67f09SDavid van Moolenbroek
1705*00b67f09SDavid van Moolenbroek if (result == ISC_R_SUCCESS) {
1706*00b67f09SDavid van Moolenbroek *node = current;
1707*00b67f09SDavid van Moolenbroek result = saved_result;
1708*00b67f09SDavid van Moolenbroek } else
1709*00b67f09SDavid van Moolenbroek *node = NULL;
1710*00b67f09SDavid van Moolenbroek } else {
1711*00b67f09SDavid van Moolenbroek /*
1712*00b67f09SDavid van Moolenbroek * Did not find an exact match (or did not want one).
1713*00b67f09SDavid van Moolenbroek */
1714*00b67f09SDavid van Moolenbroek if (*node != NULL) {
1715*00b67f09SDavid van Moolenbroek /*
1716*00b67f09SDavid van Moolenbroek * ... but found a partially matching superdomain.
1717*00b67f09SDavid van Moolenbroek * Unwind the chain to the partial match node
1718*00b67f09SDavid van Moolenbroek * to set level_matches to the level above the node,
1719*00b67f09SDavid van Moolenbroek * and then to derive the name.
1720*00b67f09SDavid van Moolenbroek *
1721*00b67f09SDavid van Moolenbroek * chain->level_count is guaranteed to be at least 1
1722*00b67f09SDavid van Moolenbroek * here because by definition of finding a superdomain,
1723*00b67f09SDavid van Moolenbroek * the chain is pointed to at least the first subtree.
1724*00b67f09SDavid van Moolenbroek */
1725*00b67f09SDavid van Moolenbroek chain->level_matches = chain->level_count - 1;
1726*00b67f09SDavid van Moolenbroek
1727*00b67f09SDavid van Moolenbroek while (chain->levels[chain->level_matches] != *node) {
1728*00b67f09SDavid van Moolenbroek INSIST(chain->level_matches > 0);
1729*00b67f09SDavid van Moolenbroek chain->level_matches--;
1730*00b67f09SDavid van Moolenbroek }
1731*00b67f09SDavid van Moolenbroek
1732*00b67f09SDavid van Moolenbroek if (foundname != NULL) {
1733*00b67f09SDavid van Moolenbroek unsigned int saved_count = chain->level_count;
1734*00b67f09SDavid van Moolenbroek
1735*00b67f09SDavid van Moolenbroek chain->level_count = chain->level_matches + 1;
1736*00b67f09SDavid van Moolenbroek
1737*00b67f09SDavid van Moolenbroek result = chain_name(chain, foundname,
1738*00b67f09SDavid van Moolenbroek ISC_FALSE);
1739*00b67f09SDavid van Moolenbroek
1740*00b67f09SDavid van Moolenbroek chain->level_count = saved_count;
1741*00b67f09SDavid van Moolenbroek } else
1742*00b67f09SDavid van Moolenbroek result = ISC_R_SUCCESS;
1743*00b67f09SDavid van Moolenbroek
1744*00b67f09SDavid van Moolenbroek if (result == ISC_R_SUCCESS)
1745*00b67f09SDavid van Moolenbroek result = DNS_R_PARTIALMATCH;
1746*00b67f09SDavid van Moolenbroek
1747*00b67f09SDavid van Moolenbroek } else
1748*00b67f09SDavid van Moolenbroek result = ISC_R_NOTFOUND;
1749*00b67f09SDavid van Moolenbroek
1750*00b67f09SDavid van Moolenbroek if (current != NULL) {
1751*00b67f09SDavid van Moolenbroek /*
1752*00b67f09SDavid van Moolenbroek * There was an exact match but either
1753*00b67f09SDavid van Moolenbroek * DNS_RBTFIND_NOEXACT was set, or
1754*00b67f09SDavid van Moolenbroek * DNS_RBTFIND_EMPTYDATA was set and the node had no
1755*00b67f09SDavid van Moolenbroek * data. A policy decision was made to set the
1756*00b67f09SDavid van Moolenbroek * chain to the exact match, but this is subject
1757*00b67f09SDavid van Moolenbroek * to change if it becomes apparent that something
1758*00b67f09SDavid van Moolenbroek * else would be more useful. It is important that
1759*00b67f09SDavid van Moolenbroek * this case is handled here, because the predecessor
1760*00b67f09SDavid van Moolenbroek * setting code below assumes the match was not exact.
1761*00b67f09SDavid van Moolenbroek */
1762*00b67f09SDavid van Moolenbroek INSIST(((options & DNS_RBTFIND_NOEXACT) != 0) ||
1763*00b67f09SDavid van Moolenbroek ((options & DNS_RBTFIND_EMPTYDATA) == 0 &&
1764*00b67f09SDavid van Moolenbroek DATA(current) == NULL));
1765*00b67f09SDavid van Moolenbroek chain->end = current;
1766*00b67f09SDavid van Moolenbroek
1767*00b67f09SDavid van Moolenbroek } else if ((options & DNS_RBTFIND_NOPREDECESSOR) != 0) {
1768*00b67f09SDavid van Moolenbroek /*
1769*00b67f09SDavid van Moolenbroek * Ensure the chain points nowhere.
1770*00b67f09SDavid van Moolenbroek */
1771*00b67f09SDavid van Moolenbroek chain->end = NULL;
1772*00b67f09SDavid van Moolenbroek
1773*00b67f09SDavid van Moolenbroek } else {
1774*00b67f09SDavid van Moolenbroek /*
1775*00b67f09SDavid van Moolenbroek * Since there was no exact match, the chain argument
1776*00b67f09SDavid van Moolenbroek * needs to be pointed at the DNSSEC predecessor of
1777*00b67f09SDavid van Moolenbroek * the search name.
1778*00b67f09SDavid van Moolenbroek */
1779*00b67f09SDavid van Moolenbroek if (compared == dns_namereln_subdomain) {
1780*00b67f09SDavid van Moolenbroek /*
1781*00b67f09SDavid van Moolenbroek * Attempted to follow a down pointer that was
1782*00b67f09SDavid van Moolenbroek * NULL, which means the searched for name was
1783*00b67f09SDavid van Moolenbroek * a subdomain of a terminal name in the tree.
1784*00b67f09SDavid van Moolenbroek * Since there are no existing subdomains to
1785*00b67f09SDavid van Moolenbroek * order against, the terminal name is the
1786*00b67f09SDavid van Moolenbroek * predecessor.
1787*00b67f09SDavid van Moolenbroek */
1788*00b67f09SDavid van Moolenbroek INSIST(chain->level_count > 0);
1789*00b67f09SDavid van Moolenbroek INSIST(chain->level_matches <
1790*00b67f09SDavid van Moolenbroek chain->level_count);
1791*00b67f09SDavid van Moolenbroek chain->end =
1792*00b67f09SDavid van Moolenbroek chain->levels[--chain->level_count];
1793*00b67f09SDavid van Moolenbroek
1794*00b67f09SDavid van Moolenbroek } else {
1795*00b67f09SDavid van Moolenbroek isc_result_t result2;
1796*00b67f09SDavid van Moolenbroek
1797*00b67f09SDavid van Moolenbroek /*
1798*00b67f09SDavid van Moolenbroek * Point current to the node that stopped
1799*00b67f09SDavid van Moolenbroek * the search.
1800*00b67f09SDavid van Moolenbroek *
1801*00b67f09SDavid van Moolenbroek * With the hashing modification that has been
1802*00b67f09SDavid van Moolenbroek * added to the algorithm, the stop node of a
1803*00b67f09SDavid van Moolenbroek * standard binary search is not known. So it
1804*00b67f09SDavid van Moolenbroek * has to be found. There is probably a more
1805*00b67f09SDavid van Moolenbroek * clever way of doing this.
1806*00b67f09SDavid van Moolenbroek *
1807*00b67f09SDavid van Moolenbroek * The assignment of current to NULL when
1808*00b67f09SDavid van Moolenbroek * the relationship is *not* dns_namereln_none,
1809*00b67f09SDavid van Moolenbroek * even though it later gets set to the same
1810*00b67f09SDavid van Moolenbroek * last_compared anyway, is simply to not push
1811*00b67f09SDavid van Moolenbroek * the while loop in one more level of
1812*00b67f09SDavid van Moolenbroek * indentation.
1813*00b67f09SDavid van Moolenbroek */
1814*00b67f09SDavid van Moolenbroek if (compared == dns_namereln_none)
1815*00b67f09SDavid van Moolenbroek current = last_compared;
1816*00b67f09SDavid van Moolenbroek else
1817*00b67f09SDavid van Moolenbroek current = NULL;
1818*00b67f09SDavid van Moolenbroek
1819*00b67f09SDavid van Moolenbroek while (current != NULL) {
1820*00b67f09SDavid van Moolenbroek NODENAME(current, ¤t_name);
1821*00b67f09SDavid van Moolenbroek compared = dns_name_fullcompare(
1822*00b67f09SDavid van Moolenbroek search_name,
1823*00b67f09SDavid van Moolenbroek ¤t_name,
1824*00b67f09SDavid van Moolenbroek &order,
1825*00b67f09SDavid van Moolenbroek &common_labels);
1826*00b67f09SDavid van Moolenbroek POST(compared);
1827*00b67f09SDavid van Moolenbroek
1828*00b67f09SDavid van Moolenbroek last_compared = current;
1829*00b67f09SDavid van Moolenbroek
1830*00b67f09SDavid van Moolenbroek /*
1831*00b67f09SDavid van Moolenbroek * Standard binary search movement.
1832*00b67f09SDavid van Moolenbroek */
1833*00b67f09SDavid van Moolenbroek if (order < 0)
1834*00b67f09SDavid van Moolenbroek current = LEFT(current);
1835*00b67f09SDavid van Moolenbroek else
1836*00b67f09SDavid van Moolenbroek current = RIGHT(current);
1837*00b67f09SDavid van Moolenbroek
1838*00b67f09SDavid van Moolenbroek }
1839*00b67f09SDavid van Moolenbroek
1840*00b67f09SDavid van Moolenbroek current = last_compared;
1841*00b67f09SDavid van Moolenbroek
1842*00b67f09SDavid van Moolenbroek /*
1843*00b67f09SDavid van Moolenbroek * Reached a point within a level tree that
1844*00b67f09SDavid van Moolenbroek * positively indicates the name is not
1845*00b67f09SDavid van Moolenbroek * present, but the stop node could be either
1846*00b67f09SDavid van Moolenbroek * less than the desired name (order > 0) or
1847*00b67f09SDavid van Moolenbroek * greater than the desired name (order < 0).
1848*00b67f09SDavid van Moolenbroek *
1849*00b67f09SDavid van Moolenbroek * If the stop node is less, it is not
1850*00b67f09SDavid van Moolenbroek * necessarily the predecessor. If the stop
1851*00b67f09SDavid van Moolenbroek * node has a down pointer, then the real
1852*00b67f09SDavid van Moolenbroek * predecessor is at the end of a level below
1853*00b67f09SDavid van Moolenbroek * (not necessarily the next level).
1854*00b67f09SDavid van Moolenbroek * Move down levels until the rightmost node
1855*00b67f09SDavid van Moolenbroek * does not have a down pointer.
1856*00b67f09SDavid van Moolenbroek *
1857*00b67f09SDavid van Moolenbroek * When the stop node is greater, it is
1858*00b67f09SDavid van Moolenbroek * the successor. All the logic for finding
1859*00b67f09SDavid van Moolenbroek * the predecessor is handily encapsulated
1860*00b67f09SDavid van Moolenbroek * in dns_rbtnodechain_prev. In the event
1861*00b67f09SDavid van Moolenbroek * that the search name is less than anything
1862*00b67f09SDavid van Moolenbroek * else in the tree, the chain is reset.
1863*00b67f09SDavid van Moolenbroek * XXX DCL What is the best way for the caller
1864*00b67f09SDavid van Moolenbroek * to know that the search name has
1865*00b67f09SDavid van Moolenbroek * no predecessor?
1866*00b67f09SDavid van Moolenbroek */
1867*00b67f09SDavid van Moolenbroek
1868*00b67f09SDavid van Moolenbroek
1869*00b67f09SDavid van Moolenbroek if (order > 0) {
1870*00b67f09SDavid van Moolenbroek if (DOWN(current) != NULL) {
1871*00b67f09SDavid van Moolenbroek ADD_LEVEL(chain, current);
1872*00b67f09SDavid van Moolenbroek
1873*00b67f09SDavid van Moolenbroek result2 =
1874*00b67f09SDavid van Moolenbroek move_chain_to_last(chain,
1875*00b67f09SDavid van Moolenbroek DOWN(current));
1876*00b67f09SDavid van Moolenbroek
1877*00b67f09SDavid van Moolenbroek if (result2 != ISC_R_SUCCESS)
1878*00b67f09SDavid van Moolenbroek result = result2;
1879*00b67f09SDavid van Moolenbroek } else
1880*00b67f09SDavid van Moolenbroek /*
1881*00b67f09SDavid van Moolenbroek * Ah, the pure and simple
1882*00b67f09SDavid van Moolenbroek * case. The stop node is the
1883*00b67f09SDavid van Moolenbroek * predecessor.
1884*00b67f09SDavid van Moolenbroek */
1885*00b67f09SDavid van Moolenbroek chain->end = current;
1886*00b67f09SDavid van Moolenbroek
1887*00b67f09SDavid van Moolenbroek } else {
1888*00b67f09SDavid van Moolenbroek INSIST(order < 0);
1889*00b67f09SDavid van Moolenbroek
1890*00b67f09SDavid van Moolenbroek chain->end = current;
1891*00b67f09SDavid van Moolenbroek
1892*00b67f09SDavid van Moolenbroek result2 = dns_rbtnodechain_prev(chain,
1893*00b67f09SDavid van Moolenbroek NULL,
1894*00b67f09SDavid van Moolenbroek NULL);
1895*00b67f09SDavid van Moolenbroek if (result2 == ISC_R_SUCCESS ||
1896*00b67f09SDavid van Moolenbroek result2 == DNS_R_NEWORIGIN)
1897*00b67f09SDavid van Moolenbroek ; /* Nothing. */
1898*00b67f09SDavid van Moolenbroek else if (result2 == ISC_R_NOMORE)
1899*00b67f09SDavid van Moolenbroek /*
1900*00b67f09SDavid van Moolenbroek * There is no predecessor.
1901*00b67f09SDavid van Moolenbroek */
1902*00b67f09SDavid van Moolenbroek dns_rbtnodechain_reset(chain);
1903*00b67f09SDavid van Moolenbroek else
1904*00b67f09SDavid van Moolenbroek result = result2;
1905*00b67f09SDavid van Moolenbroek }
1906*00b67f09SDavid van Moolenbroek
1907*00b67f09SDavid van Moolenbroek }
1908*00b67f09SDavid van Moolenbroek }
1909*00b67f09SDavid van Moolenbroek }
1910*00b67f09SDavid van Moolenbroek
1911*00b67f09SDavid van Moolenbroek ENSURE(*node == NULL || DNS_RBTNODE_VALID(*node));
1912*00b67f09SDavid van Moolenbroek
1913*00b67f09SDavid van Moolenbroek return (result);
1914*00b67f09SDavid van Moolenbroek }
1915*00b67f09SDavid van Moolenbroek
1916*00b67f09SDavid van Moolenbroek /*
1917*00b67f09SDavid van Moolenbroek * Get the data pointer associated with 'name'.
1918*00b67f09SDavid van Moolenbroek */
1919*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbt_findname(dns_rbt_t * rbt,dns_name_t * name,unsigned int options,dns_name_t * foundname,void ** data)1920*00b67f09SDavid van Moolenbroek dns_rbt_findname(dns_rbt_t *rbt, dns_name_t *name, unsigned int options,
1921*00b67f09SDavid van Moolenbroek dns_name_t *foundname, void **data) {
1922*00b67f09SDavid van Moolenbroek dns_rbtnode_t *node = NULL;
1923*00b67f09SDavid van Moolenbroek isc_result_t result;
1924*00b67f09SDavid van Moolenbroek
1925*00b67f09SDavid van Moolenbroek REQUIRE(data != NULL && *data == NULL);
1926*00b67f09SDavid van Moolenbroek
1927*00b67f09SDavid van Moolenbroek result = dns_rbt_findnode(rbt, name, foundname, &node, NULL,
1928*00b67f09SDavid van Moolenbroek options, NULL, NULL);
1929*00b67f09SDavid van Moolenbroek
1930*00b67f09SDavid van Moolenbroek if (node != NULL &&
1931*00b67f09SDavid van Moolenbroek (DATA(node) != NULL || (options & DNS_RBTFIND_EMPTYDATA) != 0))
1932*00b67f09SDavid van Moolenbroek *data = DATA(node);
1933*00b67f09SDavid van Moolenbroek else
1934*00b67f09SDavid van Moolenbroek result = ISC_R_NOTFOUND;
1935*00b67f09SDavid van Moolenbroek
1936*00b67f09SDavid van Moolenbroek return (result);
1937*00b67f09SDavid van Moolenbroek }
1938*00b67f09SDavid van Moolenbroek
1939*00b67f09SDavid van Moolenbroek /*
1940*00b67f09SDavid van Moolenbroek * Delete a name from the tree of trees.
1941*00b67f09SDavid van Moolenbroek */
1942*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbt_deletename(dns_rbt_t * rbt,dns_name_t * name,isc_boolean_t recurse)1943*00b67f09SDavid van Moolenbroek dns_rbt_deletename(dns_rbt_t *rbt, dns_name_t *name, isc_boolean_t recurse) {
1944*00b67f09SDavid van Moolenbroek dns_rbtnode_t *node = NULL;
1945*00b67f09SDavid van Moolenbroek isc_result_t result;
1946*00b67f09SDavid van Moolenbroek
1947*00b67f09SDavid van Moolenbroek REQUIRE(VALID_RBT(rbt));
1948*00b67f09SDavid van Moolenbroek REQUIRE(dns_name_isabsolute(name));
1949*00b67f09SDavid van Moolenbroek
1950*00b67f09SDavid van Moolenbroek /*
1951*00b67f09SDavid van Moolenbroek * First, find the node.
1952*00b67f09SDavid van Moolenbroek *
1953*00b67f09SDavid van Moolenbroek * When searching, the name might not have an exact match:
1954*00b67f09SDavid van Moolenbroek * consider a.b.a.com, b.b.a.com and c.b.a.com as the only
1955*00b67f09SDavid van Moolenbroek * elements of a tree, which would make layer 1 a single
1956*00b67f09SDavid van Moolenbroek * node tree of "b.a.com" and layer 2 a three node tree of
1957*00b67f09SDavid van Moolenbroek * a, b, and c. Deleting a.com would find only a partial depth
1958*00b67f09SDavid van Moolenbroek * match in the first layer. Should it be a requirement that
1959*00b67f09SDavid van Moolenbroek * that the name to be deleted have data? For now, it is.
1960*00b67f09SDavid van Moolenbroek *
1961*00b67f09SDavid van Moolenbroek * ->dirty, ->locknum and ->references are ignored; they are
1962*00b67f09SDavid van Moolenbroek * solely the province of rbtdb.c.
1963*00b67f09SDavid van Moolenbroek */
1964*00b67f09SDavid van Moolenbroek result = dns_rbt_findnode(rbt, name, NULL, &node, NULL,
1965*00b67f09SDavid van Moolenbroek DNS_RBTFIND_NOOPTIONS, NULL, NULL);
1966*00b67f09SDavid van Moolenbroek
1967*00b67f09SDavid van Moolenbroek if (result == ISC_R_SUCCESS) {
1968*00b67f09SDavid van Moolenbroek if (DATA(node) != NULL)
1969*00b67f09SDavid van Moolenbroek result = dns_rbt_deletenode(rbt, node, recurse);
1970*00b67f09SDavid van Moolenbroek else
1971*00b67f09SDavid van Moolenbroek result = ISC_R_NOTFOUND;
1972*00b67f09SDavid van Moolenbroek
1973*00b67f09SDavid van Moolenbroek } else if (result == DNS_R_PARTIALMATCH)
1974*00b67f09SDavid van Moolenbroek result = ISC_R_NOTFOUND;
1975*00b67f09SDavid van Moolenbroek
1976*00b67f09SDavid van Moolenbroek return (result);
1977*00b67f09SDavid van Moolenbroek }
1978*00b67f09SDavid van Moolenbroek
1979*00b67f09SDavid van Moolenbroek /*
1980*00b67f09SDavid van Moolenbroek * Remove a node from the tree of trees.
1981*00b67f09SDavid van Moolenbroek *
1982*00b67f09SDavid van Moolenbroek * NOTE WELL: deletion is *not* symmetric with addition; that is, reversing
1983*00b67f09SDavid van Moolenbroek * a sequence of additions to be deletions will not generally get the
1984*00b67f09SDavid van Moolenbroek * tree back to the state it started in. For example, if the addition
1985*00b67f09SDavid van Moolenbroek * of "b.c" caused the node "a.b.c" to be split, pushing "a" to its own level,
1986*00b67f09SDavid van Moolenbroek * then the subsequent deletion of "b.c" will not cause "a" to be pulled up,
1987*00b67f09SDavid van Moolenbroek * restoring "a.b.c". The RBT *used* to do this kind of rejoining, but it
1988*00b67f09SDavid van Moolenbroek * turned out to be a bad idea because it could corrupt an active nodechain
1989*00b67f09SDavid van Moolenbroek * that had "b.c" as one of its levels -- and the RBT has no idea what
1990*00b67f09SDavid van Moolenbroek * nodechains are in use by callers, so it can't even *try* to helpfully
1991*00b67f09SDavid van Moolenbroek * fix them up (which would probably be doomed to failure anyway).
1992*00b67f09SDavid van Moolenbroek *
1993*00b67f09SDavid van Moolenbroek * Similarly, it is possible to leave the tree in a state where a supposedly
1994*00b67f09SDavid van Moolenbroek * deleted node still exists. The first case of this is obvious; take
1995*00b67f09SDavid van Moolenbroek * the tree which has "b.c" on one level, pointing to "a". Now deleted "b.c".
1996*00b67f09SDavid van Moolenbroek * It was just established in the previous paragraph why we can't pull "a"
1997*00b67f09SDavid van Moolenbroek * back up to its parent level. But what happens when "a" then gets deleted?
1998*00b67f09SDavid van Moolenbroek * "b.c" is left hanging around without data or children. This condition
1999*00b67f09SDavid van Moolenbroek * is actually pretty easy to detect, but ... should it really be removed?
2000*00b67f09SDavid van Moolenbroek * Is a chain pointing to it? An iterator? Who knows! (Note that the
2001*00b67f09SDavid van Moolenbroek * references structure member cannot be looked at because it is private to
2002*00b67f09SDavid van Moolenbroek * rbtdb.) This is ugly and makes me unhappy, but after hours of trying to
2003*00b67f09SDavid van Moolenbroek * make it more aesthetically proper and getting nowhere, this is the way it
2004*00b67f09SDavid van Moolenbroek * is going to stay until such time as it proves to be a *real* problem.
2005*00b67f09SDavid van Moolenbroek *
2006*00b67f09SDavid van Moolenbroek * Finally, for reference, note that the original routine that did node
2007*00b67f09SDavid van Moolenbroek * joining was called join_nodes(). It has been excised, living now only
2008*00b67f09SDavid van Moolenbroek * in the CVS history, but comments have been left behind that point to it just
2009*00b67f09SDavid van Moolenbroek * in case someone wants to muck with this some more.
2010*00b67f09SDavid van Moolenbroek *
2011*00b67f09SDavid van Moolenbroek * The one positive aspect of all of this is that joining used to have a
2012*00b67f09SDavid van Moolenbroek * case where it might fail. Without trying to join, now this function always
2013*00b67f09SDavid van Moolenbroek * succeeds. It still returns isc_result_t, though, so the API wouldn't change.
2014*00b67f09SDavid van Moolenbroek */
2015*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbt_deletenode(dns_rbt_t * rbt,dns_rbtnode_t * node,isc_boolean_t recurse)2016*00b67f09SDavid van Moolenbroek dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, isc_boolean_t recurse)
2017*00b67f09SDavid van Moolenbroek {
2018*00b67f09SDavid van Moolenbroek dns_rbtnode_t *parent;
2019*00b67f09SDavid van Moolenbroek
2020*00b67f09SDavid van Moolenbroek REQUIRE(VALID_RBT(rbt));
2021*00b67f09SDavid van Moolenbroek REQUIRE(DNS_RBTNODE_VALID(node));
2022*00b67f09SDavid van Moolenbroek INSIST(rbt->nodecount != 0);
2023*00b67f09SDavid van Moolenbroek
2024*00b67f09SDavid van Moolenbroek if (DOWN(node) != NULL) {
2025*00b67f09SDavid van Moolenbroek if (recurse)
2026*00b67f09SDavid van Moolenbroek RUNTIME_CHECK(deletetree(rbt, DOWN(node))
2027*00b67f09SDavid van Moolenbroek == ISC_R_SUCCESS);
2028*00b67f09SDavid van Moolenbroek else {
2029*00b67f09SDavid van Moolenbroek if (DATA(node) != NULL && rbt->data_deleter != NULL)
2030*00b67f09SDavid van Moolenbroek rbt->data_deleter(DATA(node), rbt->deleter_arg);
2031*00b67f09SDavid van Moolenbroek DATA(node) = NULL;
2032*00b67f09SDavid van Moolenbroek
2033*00b67f09SDavid van Moolenbroek /*
2034*00b67f09SDavid van Moolenbroek * Since there is at least one node below this one and
2035*00b67f09SDavid van Moolenbroek * no recursion was requested, the deletion is
2036*00b67f09SDavid van Moolenbroek * complete. The down node from this node might be all
2037*00b67f09SDavid van Moolenbroek * by itself on a single level, so join_nodes() could
2038*00b67f09SDavid van Moolenbroek * be used to collapse the tree (with all the caveats
2039*00b67f09SDavid van Moolenbroek * of the comment at the start of this function).
2040*00b67f09SDavid van Moolenbroek */
2041*00b67f09SDavid van Moolenbroek return (ISC_R_SUCCESS);
2042*00b67f09SDavid van Moolenbroek }
2043*00b67f09SDavid van Moolenbroek }
2044*00b67f09SDavid van Moolenbroek
2045*00b67f09SDavid van Moolenbroek /*
2046*00b67f09SDavid van Moolenbroek * Note the node that points to the level of the node that is being
2047*00b67f09SDavid van Moolenbroek * deleted. If the deleted node is the top level, parent will be set
2048*00b67f09SDavid van Moolenbroek * to NULL.
2049*00b67f09SDavid van Moolenbroek */
2050*00b67f09SDavid van Moolenbroek parent = get_upper_node(node);
2051*00b67f09SDavid van Moolenbroek
2052*00b67f09SDavid van Moolenbroek /*
2053*00b67f09SDavid van Moolenbroek * This node now has no down pointer (either because it didn't
2054*00b67f09SDavid van Moolenbroek * have one to start, or because it was recursively removed).
2055*00b67f09SDavid van Moolenbroek * So now the node needs to be removed from this level.
2056*00b67f09SDavid van Moolenbroek */
2057*00b67f09SDavid van Moolenbroek deletefromlevel(node, parent == NULL ? &rbt->root : &DOWN(parent));
2058*00b67f09SDavid van Moolenbroek
2059*00b67f09SDavid van Moolenbroek if (DATA(node) != NULL && rbt->data_deleter != NULL)
2060*00b67f09SDavid van Moolenbroek rbt->data_deleter(DATA(node), rbt->deleter_arg);
2061*00b67f09SDavid van Moolenbroek
2062*00b67f09SDavid van Moolenbroek unhash_node(rbt, node);
2063*00b67f09SDavid van Moolenbroek #if DNS_RBT_USEMAGIC
2064*00b67f09SDavid van Moolenbroek node->magic = 0;
2065*00b67f09SDavid van Moolenbroek #endif
2066*00b67f09SDavid van Moolenbroek dns_rbtnode_refdestroy(node);
2067*00b67f09SDavid van Moolenbroek
2068*00b67f09SDavid van Moolenbroek freenode(rbt, &node);
2069*00b67f09SDavid van Moolenbroek
2070*00b67f09SDavid van Moolenbroek /*
2071*00b67f09SDavid van Moolenbroek * There are now two special cases that can exist that would
2072*00b67f09SDavid van Moolenbroek * not have existed if the tree had been created using only
2073*00b67f09SDavid van Moolenbroek * the names that now exist in it. (This is all related to
2074*00b67f09SDavid van Moolenbroek * join_nodes() as described in this function's introductory comment.)
2075*00b67f09SDavid van Moolenbroek * Both cases exist when the deleted node's parent (the node
2076*00b67f09SDavid van Moolenbroek * that pointed to the deleted node's level) is not null but
2077*00b67f09SDavid van Moolenbroek * it has no data: parent != NULL && DATA(parent) == NULL.
2078*00b67f09SDavid van Moolenbroek *
2079*00b67f09SDavid van Moolenbroek * The first case is that the deleted node was the last on its level:
2080*00b67f09SDavid van Moolenbroek * DOWN(parent) == NULL. This case can only exist if the parent was
2081*00b67f09SDavid van Moolenbroek * previously deleted -- and so now, apparently, the parent should go
2082*00b67f09SDavid van Moolenbroek * away. That can't be done though because there might be external
2083*00b67f09SDavid van Moolenbroek * references to it, such as through a nodechain.
2084*00b67f09SDavid van Moolenbroek *
2085*00b67f09SDavid van Moolenbroek * The other case also involves a parent with no data, but with the
2086*00b67f09SDavid van Moolenbroek * deleted node being the next-to-last node instead of the last:
2087*00b67f09SDavid van Moolenbroek * LEFT(DOWN(parent)) == NULL && RIGHT(DOWN(parent)) == NULL.
2088*00b67f09SDavid van Moolenbroek * Presumably now the remaining node on the level should be joined
2089*00b67f09SDavid van Moolenbroek * with the parent, but it's already been described why that can't be
2090*00b67f09SDavid van Moolenbroek * done.
2091*00b67f09SDavid van Moolenbroek */
2092*00b67f09SDavid van Moolenbroek
2093*00b67f09SDavid van Moolenbroek /*
2094*00b67f09SDavid van Moolenbroek * This function never fails.
2095*00b67f09SDavid van Moolenbroek */
2096*00b67f09SDavid van Moolenbroek return (ISC_R_SUCCESS);
2097*00b67f09SDavid van Moolenbroek }
2098*00b67f09SDavid van Moolenbroek
2099*00b67f09SDavid van Moolenbroek void
dns_rbt_namefromnode(dns_rbtnode_t * node,dns_name_t * name)2100*00b67f09SDavid van Moolenbroek dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name) {
2101*00b67f09SDavid van Moolenbroek
2102*00b67f09SDavid van Moolenbroek REQUIRE(DNS_RBTNODE_VALID(node));
2103*00b67f09SDavid van Moolenbroek REQUIRE(name != NULL);
2104*00b67f09SDavid van Moolenbroek REQUIRE(name->offsets == NULL);
2105*00b67f09SDavid van Moolenbroek
2106*00b67f09SDavid van Moolenbroek NODENAME(node, name);
2107*00b67f09SDavid van Moolenbroek }
2108*00b67f09SDavid van Moolenbroek
2109*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbt_fullnamefromnode(dns_rbtnode_t * node,dns_name_t * name)2110*00b67f09SDavid van Moolenbroek dns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name) {
2111*00b67f09SDavid van Moolenbroek dns_name_t current;
2112*00b67f09SDavid van Moolenbroek isc_result_t result;
2113*00b67f09SDavid van Moolenbroek
2114*00b67f09SDavid van Moolenbroek REQUIRE(DNS_RBTNODE_VALID(node));
2115*00b67f09SDavid van Moolenbroek REQUIRE(name != NULL);
2116*00b67f09SDavid van Moolenbroek REQUIRE(name->buffer != NULL);
2117*00b67f09SDavid van Moolenbroek
2118*00b67f09SDavid van Moolenbroek dns_name_init(¤t, NULL);
2119*00b67f09SDavid van Moolenbroek dns_name_reset(name);
2120*00b67f09SDavid van Moolenbroek
2121*00b67f09SDavid van Moolenbroek do {
2122*00b67f09SDavid van Moolenbroek INSIST(node != NULL);
2123*00b67f09SDavid van Moolenbroek
2124*00b67f09SDavid van Moolenbroek NODENAME(node, ¤t);
2125*00b67f09SDavid van Moolenbroek
2126*00b67f09SDavid van Moolenbroek result = dns_name_concatenate(name, ¤t, name, NULL);
2127*00b67f09SDavid van Moolenbroek if (result != ISC_R_SUCCESS)
2128*00b67f09SDavid van Moolenbroek break;
2129*00b67f09SDavid van Moolenbroek
2130*00b67f09SDavid van Moolenbroek node = get_upper_node(node);
2131*00b67f09SDavid van Moolenbroek } while (! dns_name_isabsolute(name));
2132*00b67f09SDavid van Moolenbroek
2133*00b67f09SDavid van Moolenbroek return (result);
2134*00b67f09SDavid van Moolenbroek }
2135*00b67f09SDavid van Moolenbroek
2136*00b67f09SDavid van Moolenbroek char *
dns_rbt_formatnodename(dns_rbtnode_t * node,char * printname,unsigned int size)2137*00b67f09SDavid van Moolenbroek dns_rbt_formatnodename(dns_rbtnode_t *node, char *printname, unsigned int size)
2138*00b67f09SDavid van Moolenbroek {
2139*00b67f09SDavid van Moolenbroek dns_fixedname_t fixedname;
2140*00b67f09SDavid van Moolenbroek dns_name_t *name;
2141*00b67f09SDavid van Moolenbroek isc_result_t result;
2142*00b67f09SDavid van Moolenbroek
2143*00b67f09SDavid van Moolenbroek REQUIRE(DNS_RBTNODE_VALID(node));
2144*00b67f09SDavid van Moolenbroek REQUIRE(printname != NULL);
2145*00b67f09SDavid van Moolenbroek
2146*00b67f09SDavid van Moolenbroek dns_fixedname_init(&fixedname);
2147*00b67f09SDavid van Moolenbroek name = dns_fixedname_name(&fixedname);
2148*00b67f09SDavid van Moolenbroek result = dns_rbt_fullnamefromnode(node, name);
2149*00b67f09SDavid van Moolenbroek if (result == ISC_R_SUCCESS)
2150*00b67f09SDavid van Moolenbroek dns_name_format(name, printname, size);
2151*00b67f09SDavid van Moolenbroek else
2152*00b67f09SDavid van Moolenbroek snprintf(printname, size, "<error building name: %s>",
2153*00b67f09SDavid van Moolenbroek dns_result_totext(result));
2154*00b67f09SDavid van Moolenbroek
2155*00b67f09SDavid van Moolenbroek return (printname);
2156*00b67f09SDavid van Moolenbroek }
2157*00b67f09SDavid van Moolenbroek
2158*00b67f09SDavid van Moolenbroek static isc_result_t
create_node(isc_mem_t * mctx,dns_name_t * name,dns_rbtnode_t ** nodep)2159*00b67f09SDavid van Moolenbroek create_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep) {
2160*00b67f09SDavid van Moolenbroek dns_rbtnode_t *node;
2161*00b67f09SDavid van Moolenbroek isc_region_t region;
2162*00b67f09SDavid van Moolenbroek unsigned int labels;
2163*00b67f09SDavid van Moolenbroek size_t nodelen;
2164*00b67f09SDavid van Moolenbroek
2165*00b67f09SDavid van Moolenbroek REQUIRE(name->offsets != NULL);
2166*00b67f09SDavid van Moolenbroek
2167*00b67f09SDavid van Moolenbroek dns_name_toregion(name, ®ion);
2168*00b67f09SDavid van Moolenbroek labels = dns_name_countlabels(name);
2169*00b67f09SDavid van Moolenbroek ENSURE(labels > 0);
2170*00b67f09SDavid van Moolenbroek
2171*00b67f09SDavid van Moolenbroek /*
2172*00b67f09SDavid van Moolenbroek * Allocate space for the node structure, the name, and the offsets.
2173*00b67f09SDavid van Moolenbroek */
2174*00b67f09SDavid van Moolenbroek nodelen = sizeof(dns_rbtnode_t) + region.length + labels + 1;
2175*00b67f09SDavid van Moolenbroek node = (dns_rbtnode_t *)isc_mem_get(mctx, nodelen);
2176*00b67f09SDavid van Moolenbroek if (node == NULL)
2177*00b67f09SDavid van Moolenbroek return (ISC_R_NOMEMORY);
2178*00b67f09SDavid van Moolenbroek memset(node, 0, nodelen);
2179*00b67f09SDavid van Moolenbroek
2180*00b67f09SDavid van Moolenbroek node->is_root = 0;
2181*00b67f09SDavid van Moolenbroek PARENT(node) = NULL;
2182*00b67f09SDavid van Moolenbroek RIGHT(node) = NULL;
2183*00b67f09SDavid van Moolenbroek LEFT(node) = NULL;
2184*00b67f09SDavid van Moolenbroek DOWN(node) = NULL;
2185*00b67f09SDavid van Moolenbroek DATA(node) = NULL;
2186*00b67f09SDavid van Moolenbroek node->is_mmapped = 0;
2187*00b67f09SDavid van Moolenbroek node->down_is_relative = 0;
2188*00b67f09SDavid van Moolenbroek node->left_is_relative = 0;
2189*00b67f09SDavid van Moolenbroek node->right_is_relative = 0;
2190*00b67f09SDavid van Moolenbroek node->parent_is_relative = 0;
2191*00b67f09SDavid van Moolenbroek node->data_is_relative = 0;
2192*00b67f09SDavid van Moolenbroek node->rpz = 0;
2193*00b67f09SDavid van Moolenbroek
2194*00b67f09SDavid van Moolenbroek #ifdef DNS_RBT_USEHASH
2195*00b67f09SDavid van Moolenbroek HASHNEXT(node) = NULL;
2196*00b67f09SDavid van Moolenbroek HASHVAL(node) = 0;
2197*00b67f09SDavid van Moolenbroek #endif
2198*00b67f09SDavid van Moolenbroek
2199*00b67f09SDavid van Moolenbroek ISC_LINK_INIT(node, deadlink);
2200*00b67f09SDavid van Moolenbroek
2201*00b67f09SDavid van Moolenbroek LOCKNUM(node) = 0;
2202*00b67f09SDavid van Moolenbroek WILD(node) = 0;
2203*00b67f09SDavid van Moolenbroek DIRTY(node) = 0;
2204*00b67f09SDavid van Moolenbroek dns_rbtnode_refinit(node, 0);
2205*00b67f09SDavid van Moolenbroek node->find_callback = 0;
2206*00b67f09SDavid van Moolenbroek node->nsec = DNS_RBT_NSEC_NORMAL;
2207*00b67f09SDavid van Moolenbroek
2208*00b67f09SDavid van Moolenbroek MAKE_BLACK(node);
2209*00b67f09SDavid van Moolenbroek
2210*00b67f09SDavid van Moolenbroek /*
2211*00b67f09SDavid van Moolenbroek * The following is stored to make reconstructing a name from the
2212*00b67f09SDavid van Moolenbroek * stored value in the node easy: the length of the name, the number
2213*00b67f09SDavid van Moolenbroek * of labels, whether the name is absolute or not, the name itself,
2214*00b67f09SDavid van Moolenbroek * and the name's offsets table.
2215*00b67f09SDavid van Moolenbroek *
2216*00b67f09SDavid van Moolenbroek * XXX RTH
2217*00b67f09SDavid van Moolenbroek * The offsets table could be made smaller by eliminating the
2218*00b67f09SDavid van Moolenbroek * first offset, which is always 0. This requires changes to
2219*00b67f09SDavid van Moolenbroek * lib/dns/name.c.
2220*00b67f09SDavid van Moolenbroek *
2221*00b67f09SDavid van Moolenbroek * Note: OLDOFFSETLEN *must* be assigned *after* OLDNAMELEN is assigned
2222*00b67f09SDavid van Moolenbroek * as it uses OLDNAMELEN.
2223*00b67f09SDavid van Moolenbroek */
2224*00b67f09SDavid van Moolenbroek OLDNAMELEN(node) = NAMELEN(node) = region.length;
2225*00b67f09SDavid van Moolenbroek OLDOFFSETLEN(node) = OFFSETLEN(node) = labels;
2226*00b67f09SDavid van Moolenbroek ATTRS(node) = name->attributes;
2227*00b67f09SDavid van Moolenbroek
2228*00b67f09SDavid van Moolenbroek memmove(NAME(node), region.base, region.length);
2229*00b67f09SDavid van Moolenbroek memmove(OFFSETS(node), name->offsets, labels);
2230*00b67f09SDavid van Moolenbroek
2231*00b67f09SDavid van Moolenbroek #if DNS_RBT_USEMAGIC
2232*00b67f09SDavid van Moolenbroek node->magic = DNS_RBTNODE_MAGIC;
2233*00b67f09SDavid van Moolenbroek #endif
2234*00b67f09SDavid van Moolenbroek *nodep = node;
2235*00b67f09SDavid van Moolenbroek
2236*00b67f09SDavid van Moolenbroek return (ISC_R_SUCCESS);
2237*00b67f09SDavid van Moolenbroek }
2238*00b67f09SDavid van Moolenbroek
2239*00b67f09SDavid van Moolenbroek #ifdef DNS_RBT_USEHASH
2240*00b67f09SDavid van Moolenbroek static inline void
hash_add_node(dns_rbt_t * rbt,dns_rbtnode_t * node,dns_name_t * name)2241*00b67f09SDavid van Moolenbroek hash_add_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name) {
2242*00b67f09SDavid van Moolenbroek unsigned int hash;
2243*00b67f09SDavid van Moolenbroek
2244*00b67f09SDavid van Moolenbroek REQUIRE(name != NULL);
2245*00b67f09SDavid van Moolenbroek
2246*00b67f09SDavid van Moolenbroek HASHVAL(node) = dns_name_fullhash(name, ISC_FALSE);
2247*00b67f09SDavid van Moolenbroek
2248*00b67f09SDavid van Moolenbroek hash = HASHVAL(node) % rbt->hashsize;
2249*00b67f09SDavid van Moolenbroek HASHNEXT(node) = rbt->hashtable[hash];
2250*00b67f09SDavid van Moolenbroek
2251*00b67f09SDavid van Moolenbroek rbt->hashtable[hash] = node;
2252*00b67f09SDavid van Moolenbroek }
2253*00b67f09SDavid van Moolenbroek
2254*00b67f09SDavid van Moolenbroek static isc_result_t
inithash(dns_rbt_t * rbt)2255*00b67f09SDavid van Moolenbroek inithash(dns_rbt_t *rbt) {
2256*00b67f09SDavid van Moolenbroek unsigned int bytes;
2257*00b67f09SDavid van Moolenbroek
2258*00b67f09SDavid van Moolenbroek rbt->hashsize = RBT_HASH_SIZE;
2259*00b67f09SDavid van Moolenbroek bytes = rbt->hashsize * sizeof(dns_rbtnode_t *);
2260*00b67f09SDavid van Moolenbroek rbt->hashtable = isc_mem_get(rbt->mctx, bytes);
2261*00b67f09SDavid van Moolenbroek
2262*00b67f09SDavid van Moolenbroek if (rbt->hashtable == NULL)
2263*00b67f09SDavid van Moolenbroek return (ISC_R_NOMEMORY);
2264*00b67f09SDavid van Moolenbroek
2265*00b67f09SDavid van Moolenbroek memset(rbt->hashtable, 0, bytes);
2266*00b67f09SDavid van Moolenbroek
2267*00b67f09SDavid van Moolenbroek return (ISC_R_SUCCESS);
2268*00b67f09SDavid van Moolenbroek }
2269*00b67f09SDavid van Moolenbroek
2270*00b67f09SDavid van Moolenbroek static void
rehash(dns_rbt_t * rbt,unsigned int newcount)2271*00b67f09SDavid van Moolenbroek rehash(dns_rbt_t *rbt, unsigned int newcount) {
2272*00b67f09SDavid van Moolenbroek unsigned int oldsize;
2273*00b67f09SDavid van Moolenbroek dns_rbtnode_t **oldtable;
2274*00b67f09SDavid van Moolenbroek dns_rbtnode_t *node;
2275*00b67f09SDavid van Moolenbroek unsigned int hash;
2276*00b67f09SDavid van Moolenbroek unsigned int i;
2277*00b67f09SDavid van Moolenbroek
2278*00b67f09SDavid van Moolenbroek oldsize = rbt->hashsize;
2279*00b67f09SDavid van Moolenbroek oldtable = rbt->hashtable;
2280*00b67f09SDavid van Moolenbroek do {
2281*00b67f09SDavid van Moolenbroek rbt->hashsize = rbt->hashsize * 2 + 1;
2282*00b67f09SDavid van Moolenbroek } while (newcount >= (rbt->hashsize * 3));
2283*00b67f09SDavid van Moolenbroek rbt->hashtable = isc_mem_get(rbt->mctx,
2284*00b67f09SDavid van Moolenbroek rbt->hashsize * sizeof(dns_rbtnode_t *));
2285*00b67f09SDavid van Moolenbroek if (rbt->hashtable == NULL) {
2286*00b67f09SDavid van Moolenbroek rbt->hashtable = oldtable;
2287*00b67f09SDavid van Moolenbroek rbt->hashsize = oldsize;
2288*00b67f09SDavid van Moolenbroek return;
2289*00b67f09SDavid van Moolenbroek }
2290*00b67f09SDavid van Moolenbroek
2291*00b67f09SDavid van Moolenbroek INSIST(rbt->hashsize > 0);
2292*00b67f09SDavid van Moolenbroek
2293*00b67f09SDavid van Moolenbroek for (i = 0; i < rbt->hashsize; i++)
2294*00b67f09SDavid van Moolenbroek rbt->hashtable[i] = NULL;
2295*00b67f09SDavid van Moolenbroek
2296*00b67f09SDavid van Moolenbroek for (i = 0; i < oldsize; i++) {
2297*00b67f09SDavid van Moolenbroek node = oldtable[i];
2298*00b67f09SDavid van Moolenbroek while (node != NULL) {
2299*00b67f09SDavid van Moolenbroek hash = HASHVAL(node) % rbt->hashsize;
2300*00b67f09SDavid van Moolenbroek oldtable[i] = HASHNEXT(node);
2301*00b67f09SDavid van Moolenbroek HASHNEXT(node) = rbt->hashtable[hash];
2302*00b67f09SDavid van Moolenbroek rbt->hashtable[hash] = node;
2303*00b67f09SDavid van Moolenbroek node = oldtable[i];
2304*00b67f09SDavid van Moolenbroek }
2305*00b67f09SDavid van Moolenbroek }
2306*00b67f09SDavid van Moolenbroek
2307*00b67f09SDavid van Moolenbroek isc_mem_put(rbt->mctx, oldtable, oldsize * sizeof(dns_rbtnode_t *));
2308*00b67f09SDavid van Moolenbroek }
2309*00b67f09SDavid van Moolenbroek
2310*00b67f09SDavid van Moolenbroek static inline void
hash_node(dns_rbt_t * rbt,dns_rbtnode_t * node,dns_name_t * name)2311*00b67f09SDavid van Moolenbroek hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name) {
2312*00b67f09SDavid van Moolenbroek REQUIRE(DNS_RBTNODE_VALID(node));
2313*00b67f09SDavid van Moolenbroek
2314*00b67f09SDavid van Moolenbroek if (rbt->nodecount >= (rbt->hashsize * 3))
2315*00b67f09SDavid van Moolenbroek rehash(rbt, rbt->nodecount);
2316*00b67f09SDavid van Moolenbroek
2317*00b67f09SDavid van Moolenbroek hash_add_node(rbt, node, name);
2318*00b67f09SDavid van Moolenbroek }
2319*00b67f09SDavid van Moolenbroek
2320*00b67f09SDavid van Moolenbroek static inline void
unhash_node(dns_rbt_t * rbt,dns_rbtnode_t * node)2321*00b67f09SDavid van Moolenbroek unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node) {
2322*00b67f09SDavid van Moolenbroek unsigned int bucket;
2323*00b67f09SDavid van Moolenbroek dns_rbtnode_t *bucket_node;
2324*00b67f09SDavid van Moolenbroek
2325*00b67f09SDavid van Moolenbroek REQUIRE(DNS_RBTNODE_VALID(node));
2326*00b67f09SDavid van Moolenbroek
2327*00b67f09SDavid van Moolenbroek if (rbt->hashtable != NULL) {
2328*00b67f09SDavid van Moolenbroek bucket = HASHVAL(node) % rbt->hashsize;
2329*00b67f09SDavid van Moolenbroek bucket_node = rbt->hashtable[bucket];
2330*00b67f09SDavid van Moolenbroek
2331*00b67f09SDavid van Moolenbroek if (bucket_node == node)
2332*00b67f09SDavid van Moolenbroek rbt->hashtable[bucket] = HASHNEXT(node);
2333*00b67f09SDavid van Moolenbroek else {
2334*00b67f09SDavid van Moolenbroek while (HASHNEXT(bucket_node) != node) {
2335*00b67f09SDavid van Moolenbroek INSIST(HASHNEXT(bucket_node) != NULL);
2336*00b67f09SDavid van Moolenbroek bucket_node = HASHNEXT(bucket_node);
2337*00b67f09SDavid van Moolenbroek }
2338*00b67f09SDavid van Moolenbroek HASHNEXT(bucket_node) = HASHNEXT(node);
2339*00b67f09SDavid van Moolenbroek }
2340*00b67f09SDavid van Moolenbroek }
2341*00b67f09SDavid van Moolenbroek }
2342*00b67f09SDavid van Moolenbroek #endif /* DNS_RBT_USEHASH */
2343*00b67f09SDavid van Moolenbroek
2344*00b67f09SDavid van Moolenbroek static inline void
rotate_left(dns_rbtnode_t * node,dns_rbtnode_t ** rootp)2345*00b67f09SDavid van Moolenbroek rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
2346*00b67f09SDavid van Moolenbroek dns_rbtnode_t *child;
2347*00b67f09SDavid van Moolenbroek
2348*00b67f09SDavid van Moolenbroek REQUIRE(DNS_RBTNODE_VALID(node));
2349*00b67f09SDavid van Moolenbroek REQUIRE(rootp != NULL);
2350*00b67f09SDavid van Moolenbroek
2351*00b67f09SDavid van Moolenbroek child = RIGHT(node);
2352*00b67f09SDavid van Moolenbroek INSIST(child != NULL);
2353*00b67f09SDavid van Moolenbroek
2354*00b67f09SDavid van Moolenbroek RIGHT(node) = LEFT(child);
2355*00b67f09SDavid van Moolenbroek if (LEFT(child) != NULL)
2356*00b67f09SDavid van Moolenbroek PARENT(LEFT(child)) = node;
2357*00b67f09SDavid van Moolenbroek LEFT(child) = node;
2358*00b67f09SDavid van Moolenbroek
2359*00b67f09SDavid van Moolenbroek if (child != NULL)
2360*00b67f09SDavid van Moolenbroek PARENT(child) = PARENT(node);
2361*00b67f09SDavid van Moolenbroek
2362*00b67f09SDavid van Moolenbroek if (IS_ROOT(node)) {
2363*00b67f09SDavid van Moolenbroek *rootp = child;
2364*00b67f09SDavid van Moolenbroek child->is_root = 1;
2365*00b67f09SDavid van Moolenbroek node->is_root = 0;
2366*00b67f09SDavid van Moolenbroek
2367*00b67f09SDavid van Moolenbroek } else {
2368*00b67f09SDavid van Moolenbroek if (LEFT(PARENT(node)) == node)
2369*00b67f09SDavid van Moolenbroek LEFT(PARENT(node)) = child;
2370*00b67f09SDavid van Moolenbroek else
2371*00b67f09SDavid van Moolenbroek RIGHT(PARENT(node)) = child;
2372*00b67f09SDavid van Moolenbroek }
2373*00b67f09SDavid van Moolenbroek
2374*00b67f09SDavid van Moolenbroek PARENT(node) = child;
2375*00b67f09SDavid van Moolenbroek }
2376*00b67f09SDavid van Moolenbroek
2377*00b67f09SDavid van Moolenbroek static inline void
rotate_right(dns_rbtnode_t * node,dns_rbtnode_t ** rootp)2378*00b67f09SDavid van Moolenbroek rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
2379*00b67f09SDavid van Moolenbroek dns_rbtnode_t *child;
2380*00b67f09SDavid van Moolenbroek
2381*00b67f09SDavid van Moolenbroek REQUIRE(DNS_RBTNODE_VALID(node));
2382*00b67f09SDavid van Moolenbroek REQUIRE(rootp != NULL);
2383*00b67f09SDavid van Moolenbroek
2384*00b67f09SDavid van Moolenbroek child = LEFT(node);
2385*00b67f09SDavid van Moolenbroek INSIST(child != NULL);
2386*00b67f09SDavid van Moolenbroek
2387*00b67f09SDavid van Moolenbroek LEFT(node) = RIGHT(child);
2388*00b67f09SDavid van Moolenbroek if (RIGHT(child) != NULL)
2389*00b67f09SDavid van Moolenbroek PARENT(RIGHT(child)) = node;
2390*00b67f09SDavid van Moolenbroek RIGHT(child) = node;
2391*00b67f09SDavid van Moolenbroek
2392*00b67f09SDavid van Moolenbroek if (child != NULL)
2393*00b67f09SDavid van Moolenbroek PARENT(child) = PARENT(node);
2394*00b67f09SDavid van Moolenbroek
2395*00b67f09SDavid van Moolenbroek if (IS_ROOT(node)) {
2396*00b67f09SDavid van Moolenbroek *rootp = child;
2397*00b67f09SDavid van Moolenbroek child->is_root = 1;
2398*00b67f09SDavid van Moolenbroek node->is_root = 0;
2399*00b67f09SDavid van Moolenbroek
2400*00b67f09SDavid van Moolenbroek } else {
2401*00b67f09SDavid van Moolenbroek if (LEFT(PARENT(node)) == node)
2402*00b67f09SDavid van Moolenbroek LEFT(PARENT(node)) = child;
2403*00b67f09SDavid van Moolenbroek else
2404*00b67f09SDavid van Moolenbroek RIGHT(PARENT(node)) = child;
2405*00b67f09SDavid van Moolenbroek }
2406*00b67f09SDavid van Moolenbroek
2407*00b67f09SDavid van Moolenbroek PARENT(node) = child;
2408*00b67f09SDavid van Moolenbroek }
2409*00b67f09SDavid van Moolenbroek
2410*00b67f09SDavid van Moolenbroek /*
2411*00b67f09SDavid van Moolenbroek * This is the real workhorse of the insertion code, because it does the
2412*00b67f09SDavid van Moolenbroek * true red/black tree on a single level.
2413*00b67f09SDavid van Moolenbroek */
2414*00b67f09SDavid van Moolenbroek static void
addonlevel(dns_rbtnode_t * node,dns_rbtnode_t * current,int order,dns_rbtnode_t ** rootp)2415*00b67f09SDavid van Moolenbroek addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
2416*00b67f09SDavid van Moolenbroek dns_rbtnode_t **rootp)
2417*00b67f09SDavid van Moolenbroek {
2418*00b67f09SDavid van Moolenbroek dns_rbtnode_t *child, *root, *parent, *grandparent;
2419*00b67f09SDavid van Moolenbroek dns_name_t add_name, current_name;
2420*00b67f09SDavid van Moolenbroek dns_offsets_t add_offsets, current_offsets;
2421*00b67f09SDavid van Moolenbroek
2422*00b67f09SDavid van Moolenbroek REQUIRE(rootp != NULL);
2423*00b67f09SDavid van Moolenbroek REQUIRE(DNS_RBTNODE_VALID(node) && LEFT(node) == NULL &&
2424*00b67f09SDavid van Moolenbroek RIGHT(node) == NULL);
2425*00b67f09SDavid van Moolenbroek REQUIRE(current != NULL);
2426*00b67f09SDavid van Moolenbroek
2427*00b67f09SDavid van Moolenbroek root = *rootp;
2428*00b67f09SDavid van Moolenbroek if (root == NULL) {
2429*00b67f09SDavid van Moolenbroek /*
2430*00b67f09SDavid van Moolenbroek * First node of a level.
2431*00b67f09SDavid van Moolenbroek */
2432*00b67f09SDavid van Moolenbroek MAKE_BLACK(node);
2433*00b67f09SDavid van Moolenbroek node->is_root = 1;
2434*00b67f09SDavid van Moolenbroek PARENT(node) = current;
2435*00b67f09SDavid van Moolenbroek *rootp = node;
2436*00b67f09SDavid van Moolenbroek return;
2437*00b67f09SDavid van Moolenbroek }
2438*00b67f09SDavid van Moolenbroek
2439*00b67f09SDavid van Moolenbroek child = root;
2440*00b67f09SDavid van Moolenbroek POST(child);
2441*00b67f09SDavid van Moolenbroek
2442*00b67f09SDavid van Moolenbroek dns_name_init(&add_name, add_offsets);
2443*00b67f09SDavid van Moolenbroek NODENAME(node, &add_name);
2444*00b67f09SDavid van Moolenbroek
2445*00b67f09SDavid van Moolenbroek dns_name_init(¤t_name, current_offsets);
2446*00b67f09SDavid van Moolenbroek NODENAME(current, ¤t_name);
2447*00b67f09SDavid van Moolenbroek
2448*00b67f09SDavid van Moolenbroek if (order < 0) {
2449*00b67f09SDavid van Moolenbroek INSIST(LEFT(current) == NULL);
2450*00b67f09SDavid van Moolenbroek LEFT(current) = node;
2451*00b67f09SDavid van Moolenbroek } else {
2452*00b67f09SDavid van Moolenbroek INSIST(RIGHT(current) == NULL);
2453*00b67f09SDavid van Moolenbroek RIGHT(current) = node;
2454*00b67f09SDavid van Moolenbroek }
2455*00b67f09SDavid van Moolenbroek
2456*00b67f09SDavid van Moolenbroek INSIST(PARENT(node) == NULL);
2457*00b67f09SDavid van Moolenbroek PARENT(node) = current;
2458*00b67f09SDavid van Moolenbroek
2459*00b67f09SDavid van Moolenbroek MAKE_RED(node);
2460*00b67f09SDavid van Moolenbroek
2461*00b67f09SDavid van Moolenbroek while (node != root && IS_RED(PARENT(node))) {
2462*00b67f09SDavid van Moolenbroek /*
2463*00b67f09SDavid van Moolenbroek * XXXDCL could do away with separate parent and grandparent
2464*00b67f09SDavid van Moolenbroek * variables. They are vestiges of the days before parent
2465*00b67f09SDavid van Moolenbroek * pointers. However, they make the code a little clearer.
2466*00b67f09SDavid van Moolenbroek */
2467*00b67f09SDavid van Moolenbroek
2468*00b67f09SDavid van Moolenbroek parent = PARENT(node);
2469*00b67f09SDavid van Moolenbroek grandparent = PARENT(parent);
2470*00b67f09SDavid van Moolenbroek
2471*00b67f09SDavid van Moolenbroek if (parent == LEFT(grandparent)) {
2472*00b67f09SDavid van Moolenbroek child = RIGHT(grandparent);
2473*00b67f09SDavid van Moolenbroek if (child != NULL && IS_RED(child)) {
2474*00b67f09SDavid van Moolenbroek MAKE_BLACK(parent);
2475*00b67f09SDavid van Moolenbroek MAKE_BLACK(child);
2476*00b67f09SDavid van Moolenbroek MAKE_RED(grandparent);
2477*00b67f09SDavid van Moolenbroek node = grandparent;
2478*00b67f09SDavid van Moolenbroek } else {
2479*00b67f09SDavid van Moolenbroek if (node == RIGHT(parent)) {
2480*00b67f09SDavid van Moolenbroek rotate_left(parent, &root);
2481*00b67f09SDavid van Moolenbroek node = parent;
2482*00b67f09SDavid van Moolenbroek parent = PARENT(node);
2483*00b67f09SDavid van Moolenbroek grandparent = PARENT(parent);
2484*00b67f09SDavid van Moolenbroek }
2485*00b67f09SDavid van Moolenbroek MAKE_BLACK(parent);
2486*00b67f09SDavid van Moolenbroek MAKE_RED(grandparent);
2487*00b67f09SDavid van Moolenbroek rotate_right(grandparent, &root);
2488*00b67f09SDavid van Moolenbroek }
2489*00b67f09SDavid van Moolenbroek } else {
2490*00b67f09SDavid van Moolenbroek child = LEFT(grandparent);
2491*00b67f09SDavid van Moolenbroek if (child != NULL && IS_RED(child)) {
2492*00b67f09SDavid van Moolenbroek MAKE_BLACK(parent);
2493*00b67f09SDavid van Moolenbroek MAKE_BLACK(child);
2494*00b67f09SDavid van Moolenbroek MAKE_RED(grandparent);
2495*00b67f09SDavid van Moolenbroek node = grandparent;
2496*00b67f09SDavid van Moolenbroek } else {
2497*00b67f09SDavid van Moolenbroek if (node == LEFT(parent)) {
2498*00b67f09SDavid van Moolenbroek rotate_right(parent, &root);
2499*00b67f09SDavid van Moolenbroek node = parent;
2500*00b67f09SDavid van Moolenbroek parent = PARENT(node);
2501*00b67f09SDavid van Moolenbroek grandparent = PARENT(parent);
2502*00b67f09SDavid van Moolenbroek }
2503*00b67f09SDavid van Moolenbroek MAKE_BLACK(parent);
2504*00b67f09SDavid van Moolenbroek MAKE_RED(grandparent);
2505*00b67f09SDavid van Moolenbroek rotate_left(grandparent, &root);
2506*00b67f09SDavid van Moolenbroek }
2507*00b67f09SDavid van Moolenbroek }
2508*00b67f09SDavid van Moolenbroek }
2509*00b67f09SDavid van Moolenbroek
2510*00b67f09SDavid van Moolenbroek MAKE_BLACK(root);
2511*00b67f09SDavid van Moolenbroek ENSURE(IS_ROOT(root));
2512*00b67f09SDavid van Moolenbroek *rootp = root;
2513*00b67f09SDavid van Moolenbroek
2514*00b67f09SDavid van Moolenbroek return;
2515*00b67f09SDavid van Moolenbroek }
2516*00b67f09SDavid van Moolenbroek
2517*00b67f09SDavid van Moolenbroek /*
2518*00b67f09SDavid van Moolenbroek * This is the real workhorse of the deletion code, because it does the
2519*00b67f09SDavid van Moolenbroek * true red/black tree on a single level.
2520*00b67f09SDavid van Moolenbroek */
2521*00b67f09SDavid van Moolenbroek static void
deletefromlevel(dns_rbtnode_t * delete,dns_rbtnode_t ** rootp)2522*00b67f09SDavid van Moolenbroek deletefromlevel(dns_rbtnode_t *delete, dns_rbtnode_t **rootp) {
2523*00b67f09SDavid van Moolenbroek dns_rbtnode_t *child, *sibling, *parent;
2524*00b67f09SDavid van Moolenbroek dns_rbtnode_t *successor;
2525*00b67f09SDavid van Moolenbroek
2526*00b67f09SDavid van Moolenbroek REQUIRE(delete != NULL);
2527*00b67f09SDavid van Moolenbroek
2528*00b67f09SDavid van Moolenbroek /*
2529*00b67f09SDavid van Moolenbroek * Verify that the parent history is (apparently) correct.
2530*00b67f09SDavid van Moolenbroek */
2531*00b67f09SDavid van Moolenbroek INSIST((IS_ROOT(delete) && *rootp == delete) ||
2532*00b67f09SDavid van Moolenbroek (! IS_ROOT(delete) &&
2533*00b67f09SDavid van Moolenbroek (LEFT(PARENT(delete)) == delete ||
2534*00b67f09SDavid van Moolenbroek RIGHT(PARENT(delete)) == delete)));
2535*00b67f09SDavid van Moolenbroek
2536*00b67f09SDavid van Moolenbroek child = NULL;
2537*00b67f09SDavid van Moolenbroek
2538*00b67f09SDavid van Moolenbroek if (LEFT(delete) == NULL) {
2539*00b67f09SDavid van Moolenbroek if (RIGHT(delete) == NULL) {
2540*00b67f09SDavid van Moolenbroek if (IS_ROOT(delete)) {
2541*00b67f09SDavid van Moolenbroek /*
2542*00b67f09SDavid van Moolenbroek * This is the only item in the tree.
2543*00b67f09SDavid van Moolenbroek */
2544*00b67f09SDavid van Moolenbroek *rootp = NULL;
2545*00b67f09SDavid van Moolenbroek return;
2546*00b67f09SDavid van Moolenbroek }
2547*00b67f09SDavid van Moolenbroek } else
2548*00b67f09SDavid van Moolenbroek /*
2549*00b67f09SDavid van Moolenbroek * This node has one child, on the right.
2550*00b67f09SDavid van Moolenbroek */
2551*00b67f09SDavid van Moolenbroek child = RIGHT(delete);
2552*00b67f09SDavid van Moolenbroek
2553*00b67f09SDavid van Moolenbroek } else if (RIGHT(delete) == NULL)
2554*00b67f09SDavid van Moolenbroek /*
2555*00b67f09SDavid van Moolenbroek * This node has one child, on the left.
2556*00b67f09SDavid van Moolenbroek */
2557*00b67f09SDavid van Moolenbroek child = LEFT(delete);
2558*00b67f09SDavid van Moolenbroek else {
2559*00b67f09SDavid van Moolenbroek dns_rbtnode_t holder, *tmp = &holder;
2560*00b67f09SDavid van Moolenbroek
2561*00b67f09SDavid van Moolenbroek /*
2562*00b67f09SDavid van Moolenbroek * This node has two children, so it cannot be directly
2563*00b67f09SDavid van Moolenbroek * deleted. Find its immediate in-order successor and
2564*00b67f09SDavid van Moolenbroek * move it to this location, then do the deletion at the
2565*00b67f09SDavid van Moolenbroek * old site of the successor.
2566*00b67f09SDavid van Moolenbroek */
2567*00b67f09SDavid van Moolenbroek successor = RIGHT(delete);
2568*00b67f09SDavid van Moolenbroek while (LEFT(successor) != NULL)
2569*00b67f09SDavid van Moolenbroek successor = LEFT(successor);
2570*00b67f09SDavid van Moolenbroek
2571*00b67f09SDavid van Moolenbroek /*
2572*00b67f09SDavid van Moolenbroek * The successor cannot possibly have a left child;
2573*00b67f09SDavid van Moolenbroek * if there is any child, it is on the right.
2574*00b67f09SDavid van Moolenbroek */
2575*00b67f09SDavid van Moolenbroek if (RIGHT(successor) != NULL)
2576*00b67f09SDavid van Moolenbroek child = RIGHT(successor);
2577*00b67f09SDavid van Moolenbroek
2578*00b67f09SDavid van Moolenbroek /*
2579*00b67f09SDavid van Moolenbroek * Swap the two nodes; it would be simpler to just replace
2580*00b67f09SDavid van Moolenbroek * the value being deleted with that of the successor,
2581*00b67f09SDavid van Moolenbroek * but this rigamarole is done so the caller has complete
2582*00b67f09SDavid van Moolenbroek * control over the pointers (and memory allocation) of
2583*00b67f09SDavid van Moolenbroek * all of nodes. If just the key value were removed from
2584*00b67f09SDavid van Moolenbroek * the tree, the pointer to the node would be unchanged.
2585*00b67f09SDavid van Moolenbroek */
2586*00b67f09SDavid van Moolenbroek
2587*00b67f09SDavid van Moolenbroek /*
2588*00b67f09SDavid van Moolenbroek * First, put the successor in the tree location of the
2589*00b67f09SDavid van Moolenbroek * node to be deleted. Save its existing tree pointer
2590*00b67f09SDavid van Moolenbroek * information, which will be needed when linking up
2591*00b67f09SDavid van Moolenbroek * delete to the successor's old location.
2592*00b67f09SDavid van Moolenbroek */
2593*00b67f09SDavid van Moolenbroek memmove(tmp, successor, sizeof(dns_rbtnode_t));
2594*00b67f09SDavid van Moolenbroek
2595*00b67f09SDavid van Moolenbroek if (IS_ROOT(delete)) {
2596*00b67f09SDavid van Moolenbroek *rootp = successor;
2597*00b67f09SDavid van Moolenbroek successor->is_root = ISC_TRUE;
2598*00b67f09SDavid van Moolenbroek delete->is_root = ISC_FALSE;
2599*00b67f09SDavid van Moolenbroek
2600*00b67f09SDavid van Moolenbroek } else
2601*00b67f09SDavid van Moolenbroek if (LEFT(PARENT(delete)) == delete)
2602*00b67f09SDavid van Moolenbroek LEFT(PARENT(delete)) = successor;
2603*00b67f09SDavid van Moolenbroek else
2604*00b67f09SDavid van Moolenbroek RIGHT(PARENT(delete)) = successor;
2605*00b67f09SDavid van Moolenbroek
2606*00b67f09SDavid van Moolenbroek PARENT(successor) = PARENT(delete);
2607*00b67f09SDavid van Moolenbroek LEFT(successor) = LEFT(delete);
2608*00b67f09SDavid van Moolenbroek RIGHT(successor) = RIGHT(delete);
2609*00b67f09SDavid van Moolenbroek COLOR(successor) = COLOR(delete);
2610*00b67f09SDavid van Moolenbroek
2611*00b67f09SDavid van Moolenbroek if (LEFT(successor) != NULL)
2612*00b67f09SDavid van Moolenbroek PARENT(LEFT(successor)) = successor;
2613*00b67f09SDavid van Moolenbroek if (RIGHT(successor) != successor)
2614*00b67f09SDavid van Moolenbroek PARENT(RIGHT(successor)) = successor;
2615*00b67f09SDavid van Moolenbroek
2616*00b67f09SDavid van Moolenbroek /*
2617*00b67f09SDavid van Moolenbroek * Now relink the node to be deleted into the
2618*00b67f09SDavid van Moolenbroek * successor's previous tree location. PARENT(tmp)
2619*00b67f09SDavid van Moolenbroek * is the successor's original parent.
2620*00b67f09SDavid van Moolenbroek */
2621*00b67f09SDavid van Moolenbroek INSIST(! IS_ROOT(delete));
2622*00b67f09SDavid van Moolenbroek
2623*00b67f09SDavid van Moolenbroek if (PARENT(tmp) == delete) {
2624*00b67f09SDavid van Moolenbroek /*
2625*00b67f09SDavid van Moolenbroek * Node being deleted was successor's parent.
2626*00b67f09SDavid van Moolenbroek */
2627*00b67f09SDavid van Moolenbroek RIGHT(successor) = delete;
2628*00b67f09SDavid van Moolenbroek PARENT(delete) = successor;
2629*00b67f09SDavid van Moolenbroek
2630*00b67f09SDavid van Moolenbroek } else {
2631*00b67f09SDavid van Moolenbroek LEFT(PARENT(tmp)) = delete;
2632*00b67f09SDavid van Moolenbroek PARENT(delete) = PARENT(tmp);
2633*00b67f09SDavid van Moolenbroek }
2634*00b67f09SDavid van Moolenbroek
2635*00b67f09SDavid van Moolenbroek /*
2636*00b67f09SDavid van Moolenbroek * Original location of successor node has no left.
2637*00b67f09SDavid van Moolenbroek */
2638*00b67f09SDavid van Moolenbroek LEFT(delete) = NULL;
2639*00b67f09SDavid van Moolenbroek RIGHT(delete) = RIGHT(tmp);
2640*00b67f09SDavid van Moolenbroek COLOR(delete) = COLOR(tmp);
2641*00b67f09SDavid van Moolenbroek }
2642*00b67f09SDavid van Moolenbroek
2643*00b67f09SDavid van Moolenbroek /*
2644*00b67f09SDavid van Moolenbroek * Remove the node by removing the links from its parent.
2645*00b67f09SDavid van Moolenbroek */
2646*00b67f09SDavid van Moolenbroek if (! IS_ROOT(delete)) {
2647*00b67f09SDavid van Moolenbroek if (LEFT(PARENT(delete)) == delete)
2648*00b67f09SDavid van Moolenbroek LEFT(PARENT(delete)) = child;
2649*00b67f09SDavid van Moolenbroek else
2650*00b67f09SDavid van Moolenbroek RIGHT(PARENT(delete)) = child;
2651*00b67f09SDavid van Moolenbroek
2652*00b67f09SDavid van Moolenbroek if (child != NULL)
2653*00b67f09SDavid van Moolenbroek PARENT(child) = PARENT(delete);
2654*00b67f09SDavid van Moolenbroek
2655*00b67f09SDavid van Moolenbroek } else {
2656*00b67f09SDavid van Moolenbroek /*
2657*00b67f09SDavid van Moolenbroek * This is the root being deleted, and at this point
2658*00b67f09SDavid van Moolenbroek * it is known to have just one child.
2659*00b67f09SDavid van Moolenbroek */
2660*00b67f09SDavid van Moolenbroek *rootp = child;
2661*00b67f09SDavid van Moolenbroek child->is_root = 1;
2662*00b67f09SDavid van Moolenbroek PARENT(child) = PARENT(delete);
2663*00b67f09SDavid van Moolenbroek }
2664*00b67f09SDavid van Moolenbroek
2665*00b67f09SDavid van Moolenbroek /*
2666*00b67f09SDavid van Moolenbroek * Fix color violations.
2667*00b67f09SDavid van Moolenbroek */
2668*00b67f09SDavid van Moolenbroek if (IS_BLACK(delete)) {
2669*00b67f09SDavid van Moolenbroek parent = PARENT(delete);
2670*00b67f09SDavid van Moolenbroek
2671*00b67f09SDavid van Moolenbroek while (child != *rootp && IS_BLACK(child)) {
2672*00b67f09SDavid van Moolenbroek INSIST(child == NULL || ! IS_ROOT(child));
2673*00b67f09SDavid van Moolenbroek
2674*00b67f09SDavid van Moolenbroek if (LEFT(parent) == child) {
2675*00b67f09SDavid van Moolenbroek sibling = RIGHT(parent);
2676*00b67f09SDavid van Moolenbroek
2677*00b67f09SDavid van Moolenbroek if (IS_RED(sibling)) {
2678*00b67f09SDavid van Moolenbroek MAKE_BLACK(sibling);
2679*00b67f09SDavid van Moolenbroek MAKE_RED(parent);
2680*00b67f09SDavid van Moolenbroek rotate_left(parent, rootp);
2681*00b67f09SDavid van Moolenbroek sibling = RIGHT(parent);
2682*00b67f09SDavid van Moolenbroek }
2683*00b67f09SDavid van Moolenbroek
2684*00b67f09SDavid van Moolenbroek INSIST(sibling != NULL);
2685*00b67f09SDavid van Moolenbroek
2686*00b67f09SDavid van Moolenbroek if (IS_BLACK(LEFT(sibling)) &&
2687*00b67f09SDavid van Moolenbroek IS_BLACK(RIGHT(sibling))) {
2688*00b67f09SDavid van Moolenbroek MAKE_RED(sibling);
2689*00b67f09SDavid van Moolenbroek child = parent;
2690*00b67f09SDavid van Moolenbroek
2691*00b67f09SDavid van Moolenbroek } else {
2692*00b67f09SDavid van Moolenbroek
2693*00b67f09SDavid van Moolenbroek if (IS_BLACK(RIGHT(sibling))) {
2694*00b67f09SDavid van Moolenbroek MAKE_BLACK(LEFT(sibling));
2695*00b67f09SDavid van Moolenbroek MAKE_RED(sibling);
2696*00b67f09SDavid van Moolenbroek rotate_right(sibling, rootp);
2697*00b67f09SDavid van Moolenbroek sibling = RIGHT(parent);
2698*00b67f09SDavid van Moolenbroek }
2699*00b67f09SDavid van Moolenbroek
2700*00b67f09SDavid van Moolenbroek COLOR(sibling) = COLOR(parent);
2701*00b67f09SDavid van Moolenbroek MAKE_BLACK(parent);
2702*00b67f09SDavid van Moolenbroek INSIST(RIGHT(sibling) != NULL);
2703*00b67f09SDavid van Moolenbroek MAKE_BLACK(RIGHT(sibling));
2704*00b67f09SDavid van Moolenbroek rotate_left(parent, rootp);
2705*00b67f09SDavid van Moolenbroek child = *rootp;
2706*00b67f09SDavid van Moolenbroek }
2707*00b67f09SDavid van Moolenbroek
2708*00b67f09SDavid van Moolenbroek } else {
2709*00b67f09SDavid van Moolenbroek /*
2710*00b67f09SDavid van Moolenbroek * Child is parent's right child.
2711*00b67f09SDavid van Moolenbroek * Everything is done the same as above,
2712*00b67f09SDavid van Moolenbroek * except mirrored.
2713*00b67f09SDavid van Moolenbroek */
2714*00b67f09SDavid van Moolenbroek sibling = LEFT(parent);
2715*00b67f09SDavid van Moolenbroek
2716*00b67f09SDavid van Moolenbroek if (IS_RED(sibling)) {
2717*00b67f09SDavid van Moolenbroek MAKE_BLACK(sibling);
2718*00b67f09SDavid van Moolenbroek MAKE_RED(parent);
2719*00b67f09SDavid van Moolenbroek rotate_right(parent, rootp);
2720*00b67f09SDavid van Moolenbroek sibling = LEFT(parent);
2721*00b67f09SDavid van Moolenbroek }
2722*00b67f09SDavid van Moolenbroek
2723*00b67f09SDavid van Moolenbroek INSIST(sibling != NULL);
2724*00b67f09SDavid van Moolenbroek
2725*00b67f09SDavid van Moolenbroek if (IS_BLACK(LEFT(sibling)) &&
2726*00b67f09SDavid van Moolenbroek IS_BLACK(RIGHT(sibling))) {
2727*00b67f09SDavid van Moolenbroek MAKE_RED(sibling);
2728*00b67f09SDavid van Moolenbroek child = parent;
2729*00b67f09SDavid van Moolenbroek
2730*00b67f09SDavid van Moolenbroek } else {
2731*00b67f09SDavid van Moolenbroek if (IS_BLACK(LEFT(sibling))) {
2732*00b67f09SDavid van Moolenbroek MAKE_BLACK(RIGHT(sibling));
2733*00b67f09SDavid van Moolenbroek MAKE_RED(sibling);
2734*00b67f09SDavid van Moolenbroek rotate_left(sibling, rootp);
2735*00b67f09SDavid van Moolenbroek sibling = LEFT(parent);
2736*00b67f09SDavid van Moolenbroek }
2737*00b67f09SDavid van Moolenbroek
2738*00b67f09SDavid van Moolenbroek COLOR(sibling) = COLOR(parent);
2739*00b67f09SDavid van Moolenbroek MAKE_BLACK(parent);
2740*00b67f09SDavid van Moolenbroek INSIST(LEFT(sibling) != NULL);
2741*00b67f09SDavid van Moolenbroek MAKE_BLACK(LEFT(sibling));
2742*00b67f09SDavid van Moolenbroek rotate_right(parent, rootp);
2743*00b67f09SDavid van Moolenbroek child = *rootp;
2744*00b67f09SDavid van Moolenbroek }
2745*00b67f09SDavid van Moolenbroek }
2746*00b67f09SDavid van Moolenbroek
2747*00b67f09SDavid van Moolenbroek parent = PARENT(child);
2748*00b67f09SDavid van Moolenbroek }
2749*00b67f09SDavid van Moolenbroek
2750*00b67f09SDavid van Moolenbroek if (IS_RED(child))
2751*00b67f09SDavid van Moolenbroek MAKE_BLACK(child);
2752*00b67f09SDavid van Moolenbroek }
2753*00b67f09SDavid van Moolenbroek }
2754*00b67f09SDavid van Moolenbroek
2755*00b67f09SDavid van Moolenbroek /*
2756*00b67f09SDavid van Moolenbroek * This should only be used on the root of a tree, because no color fixup
2757*00b67f09SDavid van Moolenbroek * is done at all.
2758*00b67f09SDavid van Moolenbroek *
2759*00b67f09SDavid van Moolenbroek * NOTE: No root pointer maintenance is done, because the function is only
2760*00b67f09SDavid van Moolenbroek * used for two cases:
2761*00b67f09SDavid van Moolenbroek * + deleting everything DOWN from a node that is itself being deleted, and
2762*00b67f09SDavid van Moolenbroek * + deleting the entire tree of trees from dns_rbt_destroy.
2763*00b67f09SDavid van Moolenbroek * In each case, the root pointer is no longer relevant, so there
2764*00b67f09SDavid van Moolenbroek * is no need for a root parameter to this function.
2765*00b67f09SDavid van Moolenbroek *
2766*00b67f09SDavid van Moolenbroek * If the function is ever intended to be used to delete something where
2767*00b67f09SDavid van Moolenbroek * a pointer needs to be told that this tree no longer exists,
2768*00b67f09SDavid van Moolenbroek * this function would need to adjusted accordingly.
2769*00b67f09SDavid van Moolenbroek */
2770*00b67f09SDavid van Moolenbroek static isc_result_t
deletetree(dns_rbt_t * rbt,dns_rbtnode_t * node)2771*00b67f09SDavid van Moolenbroek deletetree(dns_rbt_t *rbt, dns_rbtnode_t *node) {
2772*00b67f09SDavid van Moolenbroek isc_result_t result = ISC_R_SUCCESS;
2773*00b67f09SDavid van Moolenbroek
2774*00b67f09SDavid van Moolenbroek REQUIRE(VALID_RBT(rbt));
2775*00b67f09SDavid van Moolenbroek
2776*00b67f09SDavid van Moolenbroek if (node == NULL)
2777*00b67f09SDavid van Moolenbroek return (result);
2778*00b67f09SDavid van Moolenbroek
2779*00b67f09SDavid van Moolenbroek if (LEFT(node) != NULL) {
2780*00b67f09SDavid van Moolenbroek result = deletetree(rbt, LEFT(node));
2781*00b67f09SDavid van Moolenbroek if (result != ISC_R_SUCCESS)
2782*00b67f09SDavid van Moolenbroek goto done;
2783*00b67f09SDavid van Moolenbroek LEFT(node) = NULL;
2784*00b67f09SDavid van Moolenbroek }
2785*00b67f09SDavid van Moolenbroek if (RIGHT(node) != NULL) {
2786*00b67f09SDavid van Moolenbroek result = deletetree(rbt, RIGHT(node));
2787*00b67f09SDavid van Moolenbroek if (result != ISC_R_SUCCESS)
2788*00b67f09SDavid van Moolenbroek goto done;
2789*00b67f09SDavid van Moolenbroek RIGHT(node) = NULL;
2790*00b67f09SDavid van Moolenbroek }
2791*00b67f09SDavid van Moolenbroek if (DOWN(node) != NULL) {
2792*00b67f09SDavid van Moolenbroek result = deletetree(rbt, DOWN(node));
2793*00b67f09SDavid van Moolenbroek if (result != ISC_R_SUCCESS)
2794*00b67f09SDavid van Moolenbroek goto done;
2795*00b67f09SDavid van Moolenbroek DOWN(node) = NULL;
2796*00b67f09SDavid van Moolenbroek }
2797*00b67f09SDavid van Moolenbroek done:
2798*00b67f09SDavid van Moolenbroek if (result != ISC_R_SUCCESS)
2799*00b67f09SDavid van Moolenbroek return (result);
2800*00b67f09SDavid van Moolenbroek
2801*00b67f09SDavid van Moolenbroek if (DATA(node) != NULL && rbt->data_deleter != NULL)
2802*00b67f09SDavid van Moolenbroek rbt->data_deleter(DATA(node), rbt->deleter_arg);
2803*00b67f09SDavid van Moolenbroek
2804*00b67f09SDavid van Moolenbroek unhash_node(rbt, node);
2805*00b67f09SDavid van Moolenbroek #if DNS_RBT_USEMAGIC
2806*00b67f09SDavid van Moolenbroek node->magic = 0;
2807*00b67f09SDavid van Moolenbroek #endif
2808*00b67f09SDavid van Moolenbroek
2809*00b67f09SDavid van Moolenbroek freenode(rbt, &node);
2810*00b67f09SDavid van Moolenbroek return (result);
2811*00b67f09SDavid van Moolenbroek }
2812*00b67f09SDavid van Moolenbroek
2813*00b67f09SDavid van Moolenbroek static void
freenode(dns_rbt_t * rbt,dns_rbtnode_t ** nodep)2814*00b67f09SDavid van Moolenbroek freenode(dns_rbt_t *rbt, dns_rbtnode_t **nodep) {
2815*00b67f09SDavid van Moolenbroek dns_rbtnode_t *node = *nodep;
2816*00b67f09SDavid van Moolenbroek
2817*00b67f09SDavid van Moolenbroek if (node->is_mmapped == 0) {
2818*00b67f09SDavid van Moolenbroek isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
2819*00b67f09SDavid van Moolenbroek }
2820*00b67f09SDavid van Moolenbroek *nodep = NULL;
2821*00b67f09SDavid van Moolenbroek
2822*00b67f09SDavid van Moolenbroek rbt->nodecount--;
2823*00b67f09SDavid van Moolenbroek }
2824*00b67f09SDavid van Moolenbroek
2825*00b67f09SDavid van Moolenbroek static void
deletetreeflat(dns_rbt_t * rbt,unsigned int quantum,dns_rbtnode_t ** nodep)2826*00b67f09SDavid van Moolenbroek deletetreeflat(dns_rbt_t *rbt, unsigned int quantum, dns_rbtnode_t **nodep) {
2827*00b67f09SDavid van Moolenbroek dns_rbtnode_t *parent;
2828*00b67f09SDavid van Moolenbroek dns_rbtnode_t *node = *nodep;
2829*00b67f09SDavid van Moolenbroek
2830*00b67f09SDavid van Moolenbroek REQUIRE(VALID_RBT(rbt));
2831*00b67f09SDavid van Moolenbroek
2832*00b67f09SDavid van Moolenbroek again:
2833*00b67f09SDavid van Moolenbroek if (node == NULL) {
2834*00b67f09SDavid van Moolenbroek *nodep = NULL;
2835*00b67f09SDavid van Moolenbroek return;
2836*00b67f09SDavid van Moolenbroek }
2837*00b67f09SDavid van Moolenbroek
2838*00b67f09SDavid van Moolenbroek traverse:
2839*00b67f09SDavid van Moolenbroek if (LEFT(node) != NULL) {
2840*00b67f09SDavid van Moolenbroek node = LEFT(node);
2841*00b67f09SDavid van Moolenbroek goto traverse;
2842*00b67f09SDavid van Moolenbroek }
2843*00b67f09SDavid van Moolenbroek if (DOWN(node) != NULL) {
2844*00b67f09SDavid van Moolenbroek node = DOWN(node);
2845*00b67f09SDavid van Moolenbroek goto traverse;
2846*00b67f09SDavid van Moolenbroek }
2847*00b67f09SDavid van Moolenbroek
2848*00b67f09SDavid van Moolenbroek if (DATA(node) != NULL && rbt->data_deleter != NULL)
2849*00b67f09SDavid van Moolenbroek rbt->data_deleter(DATA(node), rbt->deleter_arg);
2850*00b67f09SDavid van Moolenbroek
2851*00b67f09SDavid van Moolenbroek /*
2852*00b67f09SDavid van Moolenbroek * Note: we don't call unhash_node() here as we are destroying
2853*00b67f09SDavid van Moolenbroek * the complete rbt tree.
2854*00b67f09SDavid van Moolenbroek */
2855*00b67f09SDavid van Moolenbroek #if DNS_RBT_USEMAGIC
2856*00b67f09SDavid van Moolenbroek node->magic = 0;
2857*00b67f09SDavid van Moolenbroek #endif
2858*00b67f09SDavid van Moolenbroek parent = PARENT(node);
2859*00b67f09SDavid van Moolenbroek if (RIGHT(node) != NULL)
2860*00b67f09SDavid van Moolenbroek PARENT(RIGHT(node)) = parent;
2861*00b67f09SDavid van Moolenbroek if (parent != NULL) {
2862*00b67f09SDavid van Moolenbroek if (LEFT(parent) == node)
2863*00b67f09SDavid van Moolenbroek LEFT(parent) = RIGHT(node);
2864*00b67f09SDavid van Moolenbroek else if (DOWN(parent) == node)
2865*00b67f09SDavid van Moolenbroek DOWN(parent) = RIGHT(node);
2866*00b67f09SDavid van Moolenbroek } else
2867*00b67f09SDavid van Moolenbroek parent = RIGHT(node);
2868*00b67f09SDavid van Moolenbroek
2869*00b67f09SDavid van Moolenbroek freenode(rbt, &node);
2870*00b67f09SDavid van Moolenbroek
2871*00b67f09SDavid van Moolenbroek node = parent;
2872*00b67f09SDavid van Moolenbroek if (quantum != 0 && --quantum == 0) {
2873*00b67f09SDavid van Moolenbroek *nodep = node;
2874*00b67f09SDavid van Moolenbroek return;
2875*00b67f09SDavid van Moolenbroek }
2876*00b67f09SDavid van Moolenbroek goto again;
2877*00b67f09SDavid van Moolenbroek }
2878*00b67f09SDavid van Moolenbroek
2879*00b67f09SDavid van Moolenbroek static size_t
getheight_helper(dns_rbtnode_t * node)2880*00b67f09SDavid van Moolenbroek getheight_helper(dns_rbtnode_t *node) {
2881*00b67f09SDavid van Moolenbroek size_t dl, dr;
2882*00b67f09SDavid van Moolenbroek size_t this_height, down_height;
2883*00b67f09SDavid van Moolenbroek
2884*00b67f09SDavid van Moolenbroek if (node == NULL)
2885*00b67f09SDavid van Moolenbroek return (0);
2886*00b67f09SDavid van Moolenbroek
2887*00b67f09SDavid van Moolenbroek dl = getheight_helper(LEFT(node));
2888*00b67f09SDavid van Moolenbroek dr = getheight_helper(RIGHT(node));
2889*00b67f09SDavid van Moolenbroek
2890*00b67f09SDavid van Moolenbroek this_height = ISC_MAX(dl + 1, dr + 1);
2891*00b67f09SDavid van Moolenbroek down_height = getheight_helper(DOWN(node));
2892*00b67f09SDavid van Moolenbroek
2893*00b67f09SDavid van Moolenbroek return (ISC_MAX(this_height, down_height));
2894*00b67f09SDavid van Moolenbroek }
2895*00b67f09SDavid van Moolenbroek
2896*00b67f09SDavid van Moolenbroek size_t
dns__rbt_getheight(dns_rbt_t * rbt)2897*00b67f09SDavid van Moolenbroek dns__rbt_getheight(dns_rbt_t *rbt) {
2898*00b67f09SDavid van Moolenbroek return (getheight_helper(rbt->root));
2899*00b67f09SDavid van Moolenbroek }
2900*00b67f09SDavid van Moolenbroek
2901*00b67f09SDavid van Moolenbroek static isc_boolean_t
check_properties_helper(dns_rbtnode_t * node)2902*00b67f09SDavid van Moolenbroek check_properties_helper(dns_rbtnode_t *node) {
2903*00b67f09SDavid van Moolenbroek if (node == NULL)
2904*00b67f09SDavid van Moolenbroek return (ISC_TRUE);
2905*00b67f09SDavid van Moolenbroek
2906*00b67f09SDavid van Moolenbroek if (IS_RED(node)) {
2907*00b67f09SDavid van Moolenbroek /* Root nodes must be BLACK. */
2908*00b67f09SDavid van Moolenbroek if (IS_ROOT(node))
2909*00b67f09SDavid van Moolenbroek return (ISC_FALSE);
2910*00b67f09SDavid van Moolenbroek
2911*00b67f09SDavid van Moolenbroek /* Both children of RED nodes must be BLACK. */
2912*00b67f09SDavid van Moolenbroek if (IS_RED(LEFT(node)) || IS_RED(RIGHT(node)))
2913*00b67f09SDavid van Moolenbroek return (ISC_FALSE);
2914*00b67f09SDavid van Moolenbroek }
2915*00b67f09SDavid van Moolenbroek
2916*00b67f09SDavid van Moolenbroek /* If node is assigned to the down_ pointer of its parent, it is
2917*00b67f09SDavid van Moolenbroek * a subtree root and must have the flag set.
2918*00b67f09SDavid van Moolenbroek */
2919*00b67f09SDavid van Moolenbroek if (((!PARENT(node)) ||
2920*00b67f09SDavid van Moolenbroek (DOWN(PARENT(node)) == node)) &&
2921*00b67f09SDavid van Moolenbroek (!IS_ROOT(node)))
2922*00b67f09SDavid van Moolenbroek {
2923*00b67f09SDavid van Moolenbroek return (ISC_FALSE);
2924*00b67f09SDavid van Moolenbroek }
2925*00b67f09SDavid van Moolenbroek
2926*00b67f09SDavid van Moolenbroek /* Repeat tests with this node's children. */
2927*00b67f09SDavid van Moolenbroek return (check_properties_helper(LEFT(node)) &&
2928*00b67f09SDavid van Moolenbroek check_properties_helper(RIGHT(node)) &&
2929*00b67f09SDavid van Moolenbroek check_properties_helper(DOWN(node)));
2930*00b67f09SDavid van Moolenbroek }
2931*00b67f09SDavid van Moolenbroek
2932*00b67f09SDavid van Moolenbroek static isc_boolean_t
check_black_distance_helper(dns_rbtnode_t * node,size_t * distance)2933*00b67f09SDavid van Moolenbroek check_black_distance_helper(dns_rbtnode_t *node, size_t *distance) {
2934*00b67f09SDavid van Moolenbroek size_t dl, dr, dd;
2935*00b67f09SDavid van Moolenbroek
2936*00b67f09SDavid van Moolenbroek if (node == NULL) {
2937*00b67f09SDavid van Moolenbroek *distance = 1;
2938*00b67f09SDavid van Moolenbroek return (ISC_TRUE);
2939*00b67f09SDavid van Moolenbroek }
2940*00b67f09SDavid van Moolenbroek
2941*00b67f09SDavid van Moolenbroek if (!check_black_distance_helper(LEFT(node), &dl))
2942*00b67f09SDavid van Moolenbroek return (ISC_FALSE);
2943*00b67f09SDavid van Moolenbroek
2944*00b67f09SDavid van Moolenbroek if (!check_black_distance_helper(RIGHT(node), &dr))
2945*00b67f09SDavid van Moolenbroek return (ISC_FALSE);
2946*00b67f09SDavid van Moolenbroek
2947*00b67f09SDavid van Moolenbroek if (!check_black_distance_helper(DOWN(node), &dd))
2948*00b67f09SDavid van Moolenbroek return (ISC_FALSE);
2949*00b67f09SDavid van Moolenbroek
2950*00b67f09SDavid van Moolenbroek /* Left and right side black node counts must match. */
2951*00b67f09SDavid van Moolenbroek if (dl != dr)
2952*00b67f09SDavid van Moolenbroek return (ISC_FALSE);
2953*00b67f09SDavid van Moolenbroek
2954*00b67f09SDavid van Moolenbroek if (IS_BLACK(node))
2955*00b67f09SDavid van Moolenbroek dl++;
2956*00b67f09SDavid van Moolenbroek
2957*00b67f09SDavid van Moolenbroek *distance = dl;
2958*00b67f09SDavid van Moolenbroek
2959*00b67f09SDavid van Moolenbroek return (ISC_TRUE);
2960*00b67f09SDavid van Moolenbroek }
2961*00b67f09SDavid van Moolenbroek
2962*00b67f09SDavid van Moolenbroek isc_boolean_t
dns__rbt_checkproperties(dns_rbt_t * rbt)2963*00b67f09SDavid van Moolenbroek dns__rbt_checkproperties(dns_rbt_t *rbt) {
2964*00b67f09SDavid van Moolenbroek size_t dd;
2965*00b67f09SDavid van Moolenbroek
2966*00b67f09SDavid van Moolenbroek if (!check_properties_helper(rbt->root))
2967*00b67f09SDavid van Moolenbroek return (ISC_FALSE);
2968*00b67f09SDavid van Moolenbroek
2969*00b67f09SDavid van Moolenbroek /* Path from a given node to all its leaves must contain the
2970*00b67f09SDavid van Moolenbroek * same number of BLACK child nodes. This is done separately
2971*00b67f09SDavid van Moolenbroek * here instead of inside check_properties_helper() as
2972*00b67f09SDavid van Moolenbroek * it would take (n log n) complexity otherwise.
2973*00b67f09SDavid van Moolenbroek */
2974*00b67f09SDavid van Moolenbroek return (check_black_distance_helper(rbt->root, &dd));
2975*00b67f09SDavid van Moolenbroek }
2976*00b67f09SDavid van Moolenbroek
2977*00b67f09SDavid van Moolenbroek static void
dns_rbt_indent(FILE * f,int depth)2978*00b67f09SDavid van Moolenbroek dns_rbt_indent(FILE *f, int depth) {
2979*00b67f09SDavid van Moolenbroek int i;
2980*00b67f09SDavid van Moolenbroek
2981*00b67f09SDavid van Moolenbroek fprintf(f, "%4d ", depth);
2982*00b67f09SDavid van Moolenbroek
2983*00b67f09SDavid van Moolenbroek for (i = 0; i < depth; i++)
2984*00b67f09SDavid van Moolenbroek fprintf(f, "- ");
2985*00b67f09SDavid van Moolenbroek }
2986*00b67f09SDavid van Moolenbroek
2987*00b67f09SDavid van Moolenbroek void
dns_rbt_printnodeinfo(dns_rbtnode_t * n,FILE * f)2988*00b67f09SDavid van Moolenbroek dns_rbt_printnodeinfo(dns_rbtnode_t *n, FILE *f) {
2989*00b67f09SDavid van Moolenbroek fprintf(f, "Node info for nodename: ");
2990*00b67f09SDavid van Moolenbroek printnodename(n, ISC_TRUE, f);
2991*00b67f09SDavid van Moolenbroek fprintf(f, "\n");
2992*00b67f09SDavid van Moolenbroek
2993*00b67f09SDavid van Moolenbroek fprintf(f, "n = %p\n", n);
2994*00b67f09SDavid van Moolenbroek
2995*00b67f09SDavid van Moolenbroek fprintf(f, "Relative pointers: %s%s%s%s%s\n",
2996*00b67f09SDavid van Moolenbroek (n->parent_is_relative == 1 ? " P" : ""),
2997*00b67f09SDavid van Moolenbroek (n->right_is_relative == 1 ? " R" : ""),
2998*00b67f09SDavid van Moolenbroek (n->left_is_relative == 1 ? " L" : ""),
2999*00b67f09SDavid van Moolenbroek (n->down_is_relative == 1 ? " D" : ""),
3000*00b67f09SDavid van Moolenbroek (n->data_is_relative == 1 ? " T" : ""));
3001*00b67f09SDavid van Moolenbroek
3002*00b67f09SDavid van Moolenbroek fprintf(f, "node lock address = %d\n", n->locknum);
3003*00b67f09SDavid van Moolenbroek
3004*00b67f09SDavid van Moolenbroek fprintf(f, "Parent: %p\n", n->parent);
3005*00b67f09SDavid van Moolenbroek fprintf(f, "Right: %p\n", n->right);
3006*00b67f09SDavid van Moolenbroek fprintf(f, "Left: %p\n", n->left);
3007*00b67f09SDavid van Moolenbroek fprintf(f, "Down: %p\n", n->down);
3008*00b67f09SDavid van Moolenbroek fprintf(f, "daTa: %p\n", n->data);
3009*00b67f09SDavid van Moolenbroek }
3010*00b67f09SDavid van Moolenbroek
3011*00b67f09SDavid van Moolenbroek static void
printnodename(dns_rbtnode_t * node,isc_boolean_t quoted,FILE * f)3012*00b67f09SDavid van Moolenbroek printnodename(dns_rbtnode_t *node, isc_boolean_t quoted, FILE *f) {
3013*00b67f09SDavid van Moolenbroek isc_region_t r;
3014*00b67f09SDavid van Moolenbroek dns_name_t name;
3015*00b67f09SDavid van Moolenbroek char buffer[DNS_NAME_FORMATSIZE];
3016*00b67f09SDavid van Moolenbroek dns_offsets_t offsets;
3017*00b67f09SDavid van Moolenbroek
3018*00b67f09SDavid van Moolenbroek r.length = NAMELEN(node);
3019*00b67f09SDavid van Moolenbroek r.base = NAME(node);
3020*00b67f09SDavid van Moolenbroek
3021*00b67f09SDavid van Moolenbroek dns_name_init(&name, offsets);
3022*00b67f09SDavid van Moolenbroek dns_name_fromregion(&name, &r);
3023*00b67f09SDavid van Moolenbroek
3024*00b67f09SDavid van Moolenbroek dns_name_format(&name, buffer, sizeof(buffer));
3025*00b67f09SDavid van Moolenbroek
3026*00b67f09SDavid van Moolenbroek if (quoted)
3027*00b67f09SDavid van Moolenbroek fprintf(f, "\"%s\"", buffer);
3028*00b67f09SDavid van Moolenbroek else
3029*00b67f09SDavid van Moolenbroek fprintf(f, "%s", buffer);
3030*00b67f09SDavid van Moolenbroek }
3031*00b67f09SDavid van Moolenbroek
3032*00b67f09SDavid van Moolenbroek static void
print_text_helper(dns_rbtnode_t * root,dns_rbtnode_t * parent,int depth,const char * direction,void (* data_printer)(FILE *,void *),FILE * f)3033*00b67f09SDavid van Moolenbroek print_text_helper(dns_rbtnode_t *root, dns_rbtnode_t *parent,
3034*00b67f09SDavid van Moolenbroek int depth, const char *direction,
3035*00b67f09SDavid van Moolenbroek void (*data_printer)(FILE *, void *), FILE *f)
3036*00b67f09SDavid van Moolenbroek {
3037*00b67f09SDavid van Moolenbroek dns_rbt_indent(f, depth);
3038*00b67f09SDavid van Moolenbroek
3039*00b67f09SDavid van Moolenbroek if (root != NULL) {
3040*00b67f09SDavid van Moolenbroek printnodename(root, ISC_TRUE, f);
3041*00b67f09SDavid van Moolenbroek fprintf(f, " (%s, %s", direction,
3042*00b67f09SDavid van Moolenbroek IS_RED(root) ? "RED" : "BLACK");
3043*00b67f09SDavid van Moolenbroek
3044*00b67f09SDavid van Moolenbroek if ((! IS_ROOT(root) && PARENT(root) != parent) ||
3045*00b67f09SDavid van Moolenbroek ( IS_ROOT(root) && depth > 0 &&
3046*00b67f09SDavid van Moolenbroek DOWN(PARENT(root)) != root)) {
3047*00b67f09SDavid van Moolenbroek
3048*00b67f09SDavid van Moolenbroek fprintf(f, " (BAD parent pointer! -> ");
3049*00b67f09SDavid van Moolenbroek if (PARENT(root) != NULL)
3050*00b67f09SDavid van Moolenbroek printnodename(PARENT(root), ISC_TRUE, f);
3051*00b67f09SDavid van Moolenbroek else
3052*00b67f09SDavid van Moolenbroek fprintf(f, "NULL");
3053*00b67f09SDavid van Moolenbroek fprintf(f, ")");
3054*00b67f09SDavid van Moolenbroek }
3055*00b67f09SDavid van Moolenbroek
3056*00b67f09SDavid van Moolenbroek fprintf(f, ")");
3057*00b67f09SDavid van Moolenbroek
3058*00b67f09SDavid van Moolenbroek if (root->data != NULL && data_printer != NULL) {
3059*00b67f09SDavid van Moolenbroek fprintf(f, " data@%p: ", root->data);
3060*00b67f09SDavid van Moolenbroek data_printer(f, root->data);
3061*00b67f09SDavid van Moolenbroek }
3062*00b67f09SDavid van Moolenbroek fprintf(f, "\n");
3063*00b67f09SDavid van Moolenbroek
3064*00b67f09SDavid van Moolenbroek depth++;
3065*00b67f09SDavid van Moolenbroek
3066*00b67f09SDavid van Moolenbroek if (IS_RED(root) && IS_RED(LEFT(root)))
3067*00b67f09SDavid van Moolenbroek fprintf(f, "** Red/Red color violation on left\n");
3068*00b67f09SDavid van Moolenbroek print_text_helper(LEFT(root), root, depth, "left",
3069*00b67f09SDavid van Moolenbroek data_printer, f);
3070*00b67f09SDavid van Moolenbroek
3071*00b67f09SDavid van Moolenbroek if (IS_RED(root) && IS_RED(RIGHT(root)))
3072*00b67f09SDavid van Moolenbroek fprintf(f, "** Red/Red color violation on right\n");
3073*00b67f09SDavid van Moolenbroek print_text_helper(RIGHT(root), root, depth, "right",
3074*00b67f09SDavid van Moolenbroek data_printer, f);
3075*00b67f09SDavid van Moolenbroek
3076*00b67f09SDavid van Moolenbroek print_text_helper(DOWN(root), NULL, depth, "down",
3077*00b67f09SDavid van Moolenbroek data_printer, f);
3078*00b67f09SDavid van Moolenbroek } else {
3079*00b67f09SDavid van Moolenbroek fprintf(f, "NULL (%s)\n", direction);
3080*00b67f09SDavid van Moolenbroek }
3081*00b67f09SDavid van Moolenbroek }
3082*00b67f09SDavid van Moolenbroek
3083*00b67f09SDavid van Moolenbroek void
dns_rbt_printtext(dns_rbt_t * rbt,void (* data_printer)(FILE *,void *),FILE * f)3084*00b67f09SDavid van Moolenbroek dns_rbt_printtext(dns_rbt_t *rbt,
3085*00b67f09SDavid van Moolenbroek void (*data_printer)(FILE *, void *), FILE *f)
3086*00b67f09SDavid van Moolenbroek {
3087*00b67f09SDavid van Moolenbroek REQUIRE(VALID_RBT(rbt));
3088*00b67f09SDavid van Moolenbroek
3089*00b67f09SDavid van Moolenbroek print_text_helper(rbt->root, NULL, 0, "root", data_printer, f);
3090*00b67f09SDavid van Moolenbroek }
3091*00b67f09SDavid van Moolenbroek
3092*00b67f09SDavid van Moolenbroek static int
print_dot_helper(dns_rbtnode_t * node,unsigned int * nodecount,isc_boolean_t show_pointers,FILE * f)3093*00b67f09SDavid van Moolenbroek print_dot_helper(dns_rbtnode_t *node, unsigned int *nodecount,
3094*00b67f09SDavid van Moolenbroek isc_boolean_t show_pointers, FILE *f)
3095*00b67f09SDavid van Moolenbroek {
3096*00b67f09SDavid van Moolenbroek unsigned int l, r, d;
3097*00b67f09SDavid van Moolenbroek
3098*00b67f09SDavid van Moolenbroek if (node == NULL)
3099*00b67f09SDavid van Moolenbroek return (0);
3100*00b67f09SDavid van Moolenbroek
3101*00b67f09SDavid van Moolenbroek l = print_dot_helper(LEFT(node), nodecount, show_pointers, f);
3102*00b67f09SDavid van Moolenbroek r = print_dot_helper(RIGHT(node), nodecount, show_pointers, f);
3103*00b67f09SDavid van Moolenbroek d = print_dot_helper(DOWN(node), nodecount, show_pointers, f);
3104*00b67f09SDavid van Moolenbroek
3105*00b67f09SDavid van Moolenbroek *nodecount += 1;
3106*00b67f09SDavid van Moolenbroek
3107*00b67f09SDavid van Moolenbroek fprintf(f, "node%u[label = \"<f0> |<f1> ", *nodecount);
3108*00b67f09SDavid van Moolenbroek printnodename(node, ISC_FALSE, f);
3109*00b67f09SDavid van Moolenbroek fprintf(f, "|<f2>");
3110*00b67f09SDavid van Moolenbroek
3111*00b67f09SDavid van Moolenbroek if (show_pointers)
3112*00b67f09SDavid van Moolenbroek fprintf(f, "|<f3> n=%p|<f4> p=%p", node, PARENT(node));
3113*00b67f09SDavid van Moolenbroek
3114*00b67f09SDavid van Moolenbroek fprintf(f, "\"] [");
3115*00b67f09SDavid van Moolenbroek
3116*00b67f09SDavid van Moolenbroek if (IS_RED(node))
3117*00b67f09SDavid van Moolenbroek fprintf(f, "color=red");
3118*00b67f09SDavid van Moolenbroek else
3119*00b67f09SDavid van Moolenbroek fprintf(f, "color=black");
3120*00b67f09SDavid van Moolenbroek
3121*00b67f09SDavid van Moolenbroek /* XXXMUKS: verify that IS_ROOT() indicates subtree root and not
3122*00b67f09SDavid van Moolenbroek * forest root.
3123*00b67f09SDavid van Moolenbroek */
3124*00b67f09SDavid van Moolenbroek if (IS_ROOT(node))
3125*00b67f09SDavid van Moolenbroek fprintf(f, ",penwidth=3");
3126*00b67f09SDavid van Moolenbroek
3127*00b67f09SDavid van Moolenbroek if (IS_EMPTY(node))
3128*00b67f09SDavid van Moolenbroek fprintf(f, ",style=filled,fillcolor=lightgrey");
3129*00b67f09SDavid van Moolenbroek
3130*00b67f09SDavid van Moolenbroek fprintf(f, "];\n");
3131*00b67f09SDavid van Moolenbroek
3132*00b67f09SDavid van Moolenbroek if (LEFT(node) != NULL)
3133*00b67f09SDavid van Moolenbroek fprintf(f, "\"node%u\":f0 -> \"node%u\":f1;\n", *nodecount, l);
3134*00b67f09SDavid van Moolenbroek
3135*00b67f09SDavid van Moolenbroek if (DOWN(node) != NULL)
3136*00b67f09SDavid van Moolenbroek fprintf(f, "\"node%u\":f1 -> \"node%u\":f1 [penwidth=5];\n",
3137*00b67f09SDavid van Moolenbroek *nodecount, d);
3138*00b67f09SDavid van Moolenbroek
3139*00b67f09SDavid van Moolenbroek if (RIGHT(node) != NULL)
3140*00b67f09SDavid van Moolenbroek fprintf(f, "\"node%u\":f2 -> \"node%u\":f1;\n", *nodecount, r);
3141*00b67f09SDavid van Moolenbroek
3142*00b67f09SDavid van Moolenbroek return (*nodecount);
3143*00b67f09SDavid van Moolenbroek }
3144*00b67f09SDavid van Moolenbroek
3145*00b67f09SDavid van Moolenbroek void
dns_rbt_printdot(dns_rbt_t * rbt,isc_boolean_t show_pointers,FILE * f)3146*00b67f09SDavid van Moolenbroek dns_rbt_printdot(dns_rbt_t *rbt, isc_boolean_t show_pointers, FILE *f) {
3147*00b67f09SDavid van Moolenbroek unsigned int nodecount = 0;
3148*00b67f09SDavid van Moolenbroek
3149*00b67f09SDavid van Moolenbroek REQUIRE(VALID_RBT(rbt));
3150*00b67f09SDavid van Moolenbroek
3151*00b67f09SDavid van Moolenbroek fprintf(f, "digraph g {\n");
3152*00b67f09SDavid van Moolenbroek fprintf(f, "node [shape = record,height=.1];\n");
3153*00b67f09SDavid van Moolenbroek print_dot_helper(rbt->root, &nodecount, show_pointers, f);
3154*00b67f09SDavid van Moolenbroek fprintf(f, "}\n");
3155*00b67f09SDavid van Moolenbroek }
3156*00b67f09SDavid van Moolenbroek
3157*00b67f09SDavid van Moolenbroek /*
3158*00b67f09SDavid van Moolenbroek * Chain Functions
3159*00b67f09SDavid van Moolenbroek */
3160*00b67f09SDavid van Moolenbroek
3161*00b67f09SDavid van Moolenbroek void
dns_rbtnodechain_init(dns_rbtnodechain_t * chain,isc_mem_t * mctx)3162*00b67f09SDavid van Moolenbroek dns_rbtnodechain_init(dns_rbtnodechain_t *chain, isc_mem_t *mctx) {
3163*00b67f09SDavid van Moolenbroek
3164*00b67f09SDavid van Moolenbroek REQUIRE(chain != NULL);
3165*00b67f09SDavid van Moolenbroek
3166*00b67f09SDavid van Moolenbroek /*
3167*00b67f09SDavid van Moolenbroek * Initialize 'chain'.
3168*00b67f09SDavid van Moolenbroek */
3169*00b67f09SDavid van Moolenbroek chain->mctx = mctx;
3170*00b67f09SDavid van Moolenbroek chain->end = NULL;
3171*00b67f09SDavid van Moolenbroek chain->level_count = 0;
3172*00b67f09SDavid van Moolenbroek chain->level_matches = 0;
3173*00b67f09SDavid van Moolenbroek memset(chain->levels, 0, sizeof(chain->levels));
3174*00b67f09SDavid van Moolenbroek
3175*00b67f09SDavid van Moolenbroek chain->magic = CHAIN_MAGIC;
3176*00b67f09SDavid van Moolenbroek }
3177*00b67f09SDavid van Moolenbroek
3178*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbtnodechain_current(dns_rbtnodechain_t * chain,dns_name_t * name,dns_name_t * origin,dns_rbtnode_t ** node)3179*00b67f09SDavid van Moolenbroek dns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name,
3180*00b67f09SDavid van Moolenbroek dns_name_t *origin, dns_rbtnode_t **node)
3181*00b67f09SDavid van Moolenbroek {
3182*00b67f09SDavid van Moolenbroek isc_result_t result = ISC_R_SUCCESS;
3183*00b67f09SDavid van Moolenbroek
3184*00b67f09SDavid van Moolenbroek REQUIRE(VALID_CHAIN(chain));
3185*00b67f09SDavid van Moolenbroek
3186*00b67f09SDavid van Moolenbroek if (node != NULL)
3187*00b67f09SDavid van Moolenbroek *node = chain->end;
3188*00b67f09SDavid van Moolenbroek
3189*00b67f09SDavid van Moolenbroek if (chain->end == NULL)
3190*00b67f09SDavid van Moolenbroek return (ISC_R_NOTFOUND);
3191*00b67f09SDavid van Moolenbroek
3192*00b67f09SDavid van Moolenbroek if (name != NULL) {
3193*00b67f09SDavid van Moolenbroek NODENAME(chain->end, name);
3194*00b67f09SDavid van Moolenbroek
3195*00b67f09SDavid van Moolenbroek if (chain->level_count == 0) {
3196*00b67f09SDavid van Moolenbroek /*
3197*00b67f09SDavid van Moolenbroek * Names in the top level tree are all absolute.
3198*00b67f09SDavid van Moolenbroek * Always make 'name' relative.
3199*00b67f09SDavid van Moolenbroek */
3200*00b67f09SDavid van Moolenbroek INSIST(dns_name_isabsolute(name));
3201*00b67f09SDavid van Moolenbroek
3202*00b67f09SDavid van Moolenbroek /*
3203*00b67f09SDavid van Moolenbroek * This is cheaper than dns_name_getlabelsequence().
3204*00b67f09SDavid van Moolenbroek */
3205*00b67f09SDavid van Moolenbroek name->labels--;
3206*00b67f09SDavid van Moolenbroek name->length--;
3207*00b67f09SDavid van Moolenbroek name->attributes &= ~DNS_NAMEATTR_ABSOLUTE;
3208*00b67f09SDavid van Moolenbroek }
3209*00b67f09SDavid van Moolenbroek }
3210*00b67f09SDavid van Moolenbroek
3211*00b67f09SDavid van Moolenbroek if (origin != NULL) {
3212*00b67f09SDavid van Moolenbroek if (chain->level_count > 0)
3213*00b67f09SDavid van Moolenbroek result = chain_name(chain, origin, ISC_FALSE);
3214*00b67f09SDavid van Moolenbroek else
3215*00b67f09SDavid van Moolenbroek result = dns_name_copy(dns_rootname, origin, NULL);
3216*00b67f09SDavid van Moolenbroek }
3217*00b67f09SDavid van Moolenbroek
3218*00b67f09SDavid van Moolenbroek return (result);
3219*00b67f09SDavid van Moolenbroek }
3220*00b67f09SDavid van Moolenbroek
3221*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbtnodechain_prev(dns_rbtnodechain_t * chain,dns_name_t * name,dns_name_t * origin)3222*00b67f09SDavid van Moolenbroek dns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name,
3223*00b67f09SDavid van Moolenbroek dns_name_t *origin)
3224*00b67f09SDavid van Moolenbroek {
3225*00b67f09SDavid van Moolenbroek dns_rbtnode_t *current, *previous, *predecessor;
3226*00b67f09SDavid van Moolenbroek isc_result_t result = ISC_R_SUCCESS;
3227*00b67f09SDavid van Moolenbroek isc_boolean_t new_origin = ISC_FALSE;
3228*00b67f09SDavid van Moolenbroek
3229*00b67f09SDavid van Moolenbroek REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
3230*00b67f09SDavid van Moolenbroek
3231*00b67f09SDavid van Moolenbroek predecessor = NULL;
3232*00b67f09SDavid van Moolenbroek
3233*00b67f09SDavid van Moolenbroek current = chain->end;
3234*00b67f09SDavid van Moolenbroek
3235*00b67f09SDavid van Moolenbroek if (LEFT(current) != NULL) {
3236*00b67f09SDavid van Moolenbroek /*
3237*00b67f09SDavid van Moolenbroek * Moving left one then right as far as possible is the
3238*00b67f09SDavid van Moolenbroek * previous node, at least for this level.
3239*00b67f09SDavid van Moolenbroek */
3240*00b67f09SDavid van Moolenbroek current = LEFT(current);
3241*00b67f09SDavid van Moolenbroek
3242*00b67f09SDavid van Moolenbroek while (RIGHT(current) != NULL)
3243*00b67f09SDavid van Moolenbroek current = RIGHT(current);
3244*00b67f09SDavid van Moolenbroek
3245*00b67f09SDavid van Moolenbroek predecessor = current;
3246*00b67f09SDavid van Moolenbroek
3247*00b67f09SDavid van Moolenbroek } else {
3248*00b67f09SDavid van Moolenbroek /*
3249*00b67f09SDavid van Moolenbroek * No left links, so move toward the root. If at any point on
3250*00b67f09SDavid van Moolenbroek * the way there the link from parent to child is a right
3251*00b67f09SDavid van Moolenbroek * link, then the parent is the previous node, at least
3252*00b67f09SDavid van Moolenbroek * for this level.
3253*00b67f09SDavid van Moolenbroek */
3254*00b67f09SDavid van Moolenbroek while (! IS_ROOT(current)) {
3255*00b67f09SDavid van Moolenbroek previous = current;
3256*00b67f09SDavid van Moolenbroek current = PARENT(current);
3257*00b67f09SDavid van Moolenbroek
3258*00b67f09SDavid van Moolenbroek if (RIGHT(current) == previous) {
3259*00b67f09SDavid van Moolenbroek predecessor = current;
3260*00b67f09SDavid van Moolenbroek break;
3261*00b67f09SDavid van Moolenbroek }
3262*00b67f09SDavid van Moolenbroek }
3263*00b67f09SDavid van Moolenbroek }
3264*00b67f09SDavid van Moolenbroek
3265*00b67f09SDavid van Moolenbroek if (predecessor != NULL) {
3266*00b67f09SDavid van Moolenbroek /*
3267*00b67f09SDavid van Moolenbroek * Found a predecessor node in this level. It might not
3268*00b67f09SDavid van Moolenbroek * really be the predecessor, however.
3269*00b67f09SDavid van Moolenbroek */
3270*00b67f09SDavid van Moolenbroek if (DOWN(predecessor) != NULL) {
3271*00b67f09SDavid van Moolenbroek /*
3272*00b67f09SDavid van Moolenbroek * The predecessor is really down at least one level.
3273*00b67f09SDavid van Moolenbroek * Go down and as far right as possible, and repeat
3274*00b67f09SDavid van Moolenbroek * as long as the rightmost node has a down pointer.
3275*00b67f09SDavid van Moolenbroek */
3276*00b67f09SDavid van Moolenbroek do {
3277*00b67f09SDavid van Moolenbroek /*
3278*00b67f09SDavid van Moolenbroek * XXX DCL Need to do something about origins
3279*00b67f09SDavid van Moolenbroek * here. See whether to go down, and if so
3280*00b67f09SDavid van Moolenbroek * whether it is truly what Bob calls a
3281*00b67f09SDavid van Moolenbroek * new origin.
3282*00b67f09SDavid van Moolenbroek */
3283*00b67f09SDavid van Moolenbroek ADD_LEVEL(chain, predecessor);
3284*00b67f09SDavid van Moolenbroek predecessor = DOWN(predecessor);
3285*00b67f09SDavid van Moolenbroek
3286*00b67f09SDavid van Moolenbroek /* XXX DCL duplicated from above; clever
3287*00b67f09SDavid van Moolenbroek * way to unduplicate? */
3288*00b67f09SDavid van Moolenbroek
3289*00b67f09SDavid van Moolenbroek while (RIGHT(predecessor) != NULL)
3290*00b67f09SDavid van Moolenbroek predecessor = RIGHT(predecessor);
3291*00b67f09SDavid van Moolenbroek } while (DOWN(predecessor) != NULL);
3292*00b67f09SDavid van Moolenbroek
3293*00b67f09SDavid van Moolenbroek /* XXX DCL probably needs work on the concept */
3294*00b67f09SDavid van Moolenbroek if (origin != NULL)
3295*00b67f09SDavid van Moolenbroek new_origin = ISC_TRUE;
3296*00b67f09SDavid van Moolenbroek }
3297*00b67f09SDavid van Moolenbroek
3298*00b67f09SDavid van Moolenbroek } else if (chain->level_count > 0) {
3299*00b67f09SDavid van Moolenbroek /*
3300*00b67f09SDavid van Moolenbroek * Dang, didn't find a predecessor in this level.
3301*00b67f09SDavid van Moolenbroek * Got to the root of this level without having traversed
3302*00b67f09SDavid van Moolenbroek * any right links. Ascend the tree one level; the
3303*00b67f09SDavid van Moolenbroek * node that points to this tree is the predecessor.
3304*00b67f09SDavid van Moolenbroek */
3305*00b67f09SDavid van Moolenbroek INSIST(chain->level_count > 0 && IS_ROOT(current));
3306*00b67f09SDavid van Moolenbroek predecessor = chain->levels[--chain->level_count];
3307*00b67f09SDavid van Moolenbroek
3308*00b67f09SDavid van Moolenbroek /* XXX DCL probably needs work on the concept */
3309*00b67f09SDavid van Moolenbroek /*
3310*00b67f09SDavid van Moolenbroek * Don't declare an origin change when the new origin is "."
3311*00b67f09SDavid van Moolenbroek * at the top level tree, because "." is declared as the origin
3312*00b67f09SDavid van Moolenbroek * for the second level tree.
3313*00b67f09SDavid van Moolenbroek */
3314*00b67f09SDavid van Moolenbroek if (origin != NULL &&
3315*00b67f09SDavid van Moolenbroek (chain->level_count > 0 || OFFSETLEN(predecessor) > 1))
3316*00b67f09SDavid van Moolenbroek new_origin = ISC_TRUE;
3317*00b67f09SDavid van Moolenbroek }
3318*00b67f09SDavid van Moolenbroek
3319*00b67f09SDavid van Moolenbroek if (predecessor != NULL) {
3320*00b67f09SDavid van Moolenbroek chain->end = predecessor;
3321*00b67f09SDavid van Moolenbroek
3322*00b67f09SDavid van Moolenbroek if (new_origin) {
3323*00b67f09SDavid van Moolenbroek result = dns_rbtnodechain_current(chain, name, origin,
3324*00b67f09SDavid van Moolenbroek NULL);
3325*00b67f09SDavid van Moolenbroek if (result == ISC_R_SUCCESS)
3326*00b67f09SDavid van Moolenbroek result = DNS_R_NEWORIGIN;
3327*00b67f09SDavid van Moolenbroek
3328*00b67f09SDavid van Moolenbroek } else
3329*00b67f09SDavid van Moolenbroek result = dns_rbtnodechain_current(chain, name, NULL,
3330*00b67f09SDavid van Moolenbroek NULL);
3331*00b67f09SDavid van Moolenbroek
3332*00b67f09SDavid van Moolenbroek } else
3333*00b67f09SDavid van Moolenbroek result = ISC_R_NOMORE;
3334*00b67f09SDavid van Moolenbroek
3335*00b67f09SDavid van Moolenbroek return (result);
3336*00b67f09SDavid van Moolenbroek }
3337*00b67f09SDavid van Moolenbroek
3338*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbtnodechain_down(dns_rbtnodechain_t * chain,dns_name_t * name,dns_name_t * origin)3339*00b67f09SDavid van Moolenbroek dns_rbtnodechain_down(dns_rbtnodechain_t *chain, dns_name_t *name,
3340*00b67f09SDavid van Moolenbroek dns_name_t *origin)
3341*00b67f09SDavid van Moolenbroek {
3342*00b67f09SDavid van Moolenbroek dns_rbtnode_t *current, *successor;
3343*00b67f09SDavid van Moolenbroek isc_result_t result = ISC_R_SUCCESS;
3344*00b67f09SDavid van Moolenbroek isc_boolean_t new_origin = ISC_FALSE;
3345*00b67f09SDavid van Moolenbroek
3346*00b67f09SDavid van Moolenbroek REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
3347*00b67f09SDavid van Moolenbroek
3348*00b67f09SDavid van Moolenbroek successor = NULL;
3349*00b67f09SDavid van Moolenbroek
3350*00b67f09SDavid van Moolenbroek current = chain->end;
3351*00b67f09SDavid van Moolenbroek
3352*00b67f09SDavid van Moolenbroek if (DOWN(current) != NULL) {
3353*00b67f09SDavid van Moolenbroek /*
3354*00b67f09SDavid van Moolenbroek * Don't declare an origin change when the new origin is "."
3355*00b67f09SDavid van Moolenbroek * at the second level tree, because "." is already declared
3356*00b67f09SDavid van Moolenbroek * as the origin for the top level tree.
3357*00b67f09SDavid van Moolenbroek */
3358*00b67f09SDavid van Moolenbroek if (chain->level_count > 0 ||
3359*00b67f09SDavid van Moolenbroek OFFSETLEN(current) > 1)
3360*00b67f09SDavid van Moolenbroek new_origin = ISC_TRUE;
3361*00b67f09SDavid van Moolenbroek
3362*00b67f09SDavid van Moolenbroek ADD_LEVEL(chain, current);
3363*00b67f09SDavid van Moolenbroek current = DOWN(current);
3364*00b67f09SDavid van Moolenbroek
3365*00b67f09SDavid van Moolenbroek while (LEFT(current) != NULL)
3366*00b67f09SDavid van Moolenbroek current = LEFT(current);
3367*00b67f09SDavid van Moolenbroek
3368*00b67f09SDavid van Moolenbroek successor = current;
3369*00b67f09SDavid van Moolenbroek }
3370*00b67f09SDavid van Moolenbroek
3371*00b67f09SDavid van Moolenbroek if (successor != NULL) {
3372*00b67f09SDavid van Moolenbroek chain->end = successor;
3373*00b67f09SDavid van Moolenbroek
3374*00b67f09SDavid van Moolenbroek /*
3375*00b67f09SDavid van Moolenbroek * It is not necessary to use dns_rbtnodechain_current like
3376*00b67f09SDavid van Moolenbroek * the other functions because this function will never
3377*00b67f09SDavid van Moolenbroek * find a node in the topmost level. This is because the
3378*00b67f09SDavid van Moolenbroek * root level will never be more than one name, and everything
3379*00b67f09SDavid van Moolenbroek * in the megatree is a successor to that node, down at
3380*00b67f09SDavid van Moolenbroek * the second level or below.
3381*00b67f09SDavid van Moolenbroek */
3382*00b67f09SDavid van Moolenbroek
3383*00b67f09SDavid van Moolenbroek if (name != NULL)
3384*00b67f09SDavid van Moolenbroek NODENAME(chain->end, name);
3385*00b67f09SDavid van Moolenbroek
3386*00b67f09SDavid van Moolenbroek if (new_origin) {
3387*00b67f09SDavid van Moolenbroek if (origin != NULL)
3388*00b67f09SDavid van Moolenbroek result = chain_name(chain, origin, ISC_FALSE);
3389*00b67f09SDavid van Moolenbroek
3390*00b67f09SDavid van Moolenbroek if (result == ISC_R_SUCCESS)
3391*00b67f09SDavid van Moolenbroek result = DNS_R_NEWORIGIN;
3392*00b67f09SDavid van Moolenbroek
3393*00b67f09SDavid van Moolenbroek } else
3394*00b67f09SDavid van Moolenbroek result = ISC_R_SUCCESS;
3395*00b67f09SDavid van Moolenbroek
3396*00b67f09SDavid van Moolenbroek } else
3397*00b67f09SDavid van Moolenbroek result = ISC_R_NOMORE;
3398*00b67f09SDavid van Moolenbroek
3399*00b67f09SDavid van Moolenbroek return (result);
3400*00b67f09SDavid van Moolenbroek }
3401*00b67f09SDavid van Moolenbroek
3402*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbtnodechain_nextflat(dns_rbtnodechain_t * chain,dns_name_t * name)3403*00b67f09SDavid van Moolenbroek dns_rbtnodechain_nextflat(dns_rbtnodechain_t *chain, dns_name_t *name) {
3404*00b67f09SDavid van Moolenbroek dns_rbtnode_t *current, *previous, *successor;
3405*00b67f09SDavid van Moolenbroek isc_result_t result = ISC_R_SUCCESS;
3406*00b67f09SDavid van Moolenbroek
3407*00b67f09SDavid van Moolenbroek REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
3408*00b67f09SDavid van Moolenbroek
3409*00b67f09SDavid van Moolenbroek successor = NULL;
3410*00b67f09SDavid van Moolenbroek
3411*00b67f09SDavid van Moolenbroek current = chain->end;
3412*00b67f09SDavid van Moolenbroek
3413*00b67f09SDavid van Moolenbroek if (RIGHT(current) == NULL) {
3414*00b67f09SDavid van Moolenbroek while (! IS_ROOT(current)) {
3415*00b67f09SDavid van Moolenbroek previous = current;
3416*00b67f09SDavid van Moolenbroek current = PARENT(current);
3417*00b67f09SDavid van Moolenbroek
3418*00b67f09SDavid van Moolenbroek if (LEFT(current) == previous) {
3419*00b67f09SDavid van Moolenbroek successor = current;
3420*00b67f09SDavid van Moolenbroek break;
3421*00b67f09SDavid van Moolenbroek }
3422*00b67f09SDavid van Moolenbroek }
3423*00b67f09SDavid van Moolenbroek } else {
3424*00b67f09SDavid van Moolenbroek current = RIGHT(current);
3425*00b67f09SDavid van Moolenbroek
3426*00b67f09SDavid van Moolenbroek while (LEFT(current) != NULL)
3427*00b67f09SDavid van Moolenbroek current = LEFT(current);
3428*00b67f09SDavid van Moolenbroek
3429*00b67f09SDavid van Moolenbroek successor = current;
3430*00b67f09SDavid van Moolenbroek }
3431*00b67f09SDavid van Moolenbroek
3432*00b67f09SDavid van Moolenbroek if (successor != NULL) {
3433*00b67f09SDavid van Moolenbroek chain->end = successor;
3434*00b67f09SDavid van Moolenbroek
3435*00b67f09SDavid van Moolenbroek if (name != NULL)
3436*00b67f09SDavid van Moolenbroek NODENAME(chain->end, name);
3437*00b67f09SDavid van Moolenbroek
3438*00b67f09SDavid van Moolenbroek result = ISC_R_SUCCESS;
3439*00b67f09SDavid van Moolenbroek } else
3440*00b67f09SDavid van Moolenbroek result = ISC_R_NOMORE;
3441*00b67f09SDavid van Moolenbroek
3442*00b67f09SDavid van Moolenbroek return (result);
3443*00b67f09SDavid van Moolenbroek }
3444*00b67f09SDavid van Moolenbroek
3445*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbtnodechain_next(dns_rbtnodechain_t * chain,dns_name_t * name,dns_name_t * origin)3446*00b67f09SDavid van Moolenbroek dns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name,
3447*00b67f09SDavid van Moolenbroek dns_name_t *origin)
3448*00b67f09SDavid van Moolenbroek {
3449*00b67f09SDavid van Moolenbroek dns_rbtnode_t *current, *previous, *successor;
3450*00b67f09SDavid van Moolenbroek isc_result_t result = ISC_R_SUCCESS;
3451*00b67f09SDavid van Moolenbroek isc_boolean_t new_origin = ISC_FALSE;
3452*00b67f09SDavid van Moolenbroek
3453*00b67f09SDavid van Moolenbroek REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
3454*00b67f09SDavid van Moolenbroek
3455*00b67f09SDavid van Moolenbroek successor = NULL;
3456*00b67f09SDavid van Moolenbroek
3457*00b67f09SDavid van Moolenbroek current = chain->end;
3458*00b67f09SDavid van Moolenbroek
3459*00b67f09SDavid van Moolenbroek /*
3460*00b67f09SDavid van Moolenbroek * If there is a level below this node, the next node is the leftmost
3461*00b67f09SDavid van Moolenbroek * node of the next level.
3462*00b67f09SDavid van Moolenbroek */
3463*00b67f09SDavid van Moolenbroek if (DOWN(current) != NULL) {
3464*00b67f09SDavid van Moolenbroek /*
3465*00b67f09SDavid van Moolenbroek * Don't declare an origin change when the new origin is "."
3466*00b67f09SDavid van Moolenbroek * at the second level tree, because "." is already declared
3467*00b67f09SDavid van Moolenbroek * as the origin for the top level tree.
3468*00b67f09SDavid van Moolenbroek */
3469*00b67f09SDavid van Moolenbroek if (chain->level_count > 0 ||
3470*00b67f09SDavid van Moolenbroek OFFSETLEN(current) > 1)
3471*00b67f09SDavid van Moolenbroek new_origin = ISC_TRUE;
3472*00b67f09SDavid van Moolenbroek
3473*00b67f09SDavid van Moolenbroek ADD_LEVEL(chain, current);
3474*00b67f09SDavid van Moolenbroek current = DOWN(current);
3475*00b67f09SDavid van Moolenbroek
3476*00b67f09SDavid van Moolenbroek while (LEFT(current) != NULL)
3477*00b67f09SDavid van Moolenbroek current = LEFT(current);
3478*00b67f09SDavid van Moolenbroek
3479*00b67f09SDavid van Moolenbroek successor = current;
3480*00b67f09SDavid van Moolenbroek
3481*00b67f09SDavid van Moolenbroek } else if (RIGHT(current) == NULL) {
3482*00b67f09SDavid van Moolenbroek /*
3483*00b67f09SDavid van Moolenbroek * The successor is up, either in this level or a previous one.
3484*00b67f09SDavid van Moolenbroek * Head back toward the root of the tree, looking for any path
3485*00b67f09SDavid van Moolenbroek * that was via a left link; the successor is the node that has
3486*00b67f09SDavid van Moolenbroek * that left link. In the event the root of the level is
3487*00b67f09SDavid van Moolenbroek * reached without having traversed any left links, ascend one
3488*00b67f09SDavid van Moolenbroek * level and look for either a right link off the point of
3489*00b67f09SDavid van Moolenbroek * ascent, or search for a left link upward again, repeating
3490*00b67f09SDavid van Moolenbroek * ascends until either case is true.
3491*00b67f09SDavid van Moolenbroek */
3492*00b67f09SDavid van Moolenbroek do {
3493*00b67f09SDavid van Moolenbroek while (! IS_ROOT(current)) {
3494*00b67f09SDavid van Moolenbroek previous = current;
3495*00b67f09SDavid van Moolenbroek current = PARENT(current);
3496*00b67f09SDavid van Moolenbroek
3497*00b67f09SDavid van Moolenbroek if (LEFT(current) == previous) {
3498*00b67f09SDavid van Moolenbroek successor = current;
3499*00b67f09SDavid van Moolenbroek break;
3500*00b67f09SDavid van Moolenbroek }
3501*00b67f09SDavid van Moolenbroek }
3502*00b67f09SDavid van Moolenbroek
3503*00b67f09SDavid van Moolenbroek if (successor == NULL) {
3504*00b67f09SDavid van Moolenbroek /*
3505*00b67f09SDavid van Moolenbroek * Reached the root without having traversed
3506*00b67f09SDavid van Moolenbroek * any left pointers, so this level is done.
3507*00b67f09SDavid van Moolenbroek */
3508*00b67f09SDavid van Moolenbroek if (chain->level_count == 0)
3509*00b67f09SDavid van Moolenbroek break;
3510*00b67f09SDavid van Moolenbroek
3511*00b67f09SDavid van Moolenbroek current = chain->levels[--chain->level_count];
3512*00b67f09SDavid van Moolenbroek new_origin = ISC_TRUE;
3513*00b67f09SDavid van Moolenbroek
3514*00b67f09SDavid van Moolenbroek if (RIGHT(current) != NULL)
3515*00b67f09SDavid van Moolenbroek break;
3516*00b67f09SDavid van Moolenbroek }
3517*00b67f09SDavid van Moolenbroek } while (successor == NULL);
3518*00b67f09SDavid van Moolenbroek }
3519*00b67f09SDavid van Moolenbroek
3520*00b67f09SDavid van Moolenbroek if (successor == NULL && RIGHT(current) != NULL) {
3521*00b67f09SDavid van Moolenbroek current = RIGHT(current);
3522*00b67f09SDavid van Moolenbroek
3523*00b67f09SDavid van Moolenbroek while (LEFT(current) != NULL)
3524*00b67f09SDavid van Moolenbroek current = LEFT(current);
3525*00b67f09SDavid van Moolenbroek
3526*00b67f09SDavid van Moolenbroek successor = current;
3527*00b67f09SDavid van Moolenbroek }
3528*00b67f09SDavid van Moolenbroek
3529*00b67f09SDavid van Moolenbroek if (successor != NULL) {
3530*00b67f09SDavid van Moolenbroek chain->end = successor;
3531*00b67f09SDavid van Moolenbroek
3532*00b67f09SDavid van Moolenbroek /*
3533*00b67f09SDavid van Moolenbroek * It is not necessary to use dns_rbtnodechain_current like
3534*00b67f09SDavid van Moolenbroek * the other functions because this function will never
3535*00b67f09SDavid van Moolenbroek * find a node in the topmost level. This is because the
3536*00b67f09SDavid van Moolenbroek * root level will never be more than one name, and everything
3537*00b67f09SDavid van Moolenbroek * in the megatree is a successor to that node, down at
3538*00b67f09SDavid van Moolenbroek * the second level or below.
3539*00b67f09SDavid van Moolenbroek */
3540*00b67f09SDavid van Moolenbroek
3541*00b67f09SDavid van Moolenbroek if (name != NULL)
3542*00b67f09SDavid van Moolenbroek NODENAME(chain->end, name);
3543*00b67f09SDavid van Moolenbroek
3544*00b67f09SDavid van Moolenbroek if (new_origin) {
3545*00b67f09SDavid van Moolenbroek if (origin != NULL)
3546*00b67f09SDavid van Moolenbroek result = chain_name(chain, origin, ISC_FALSE);
3547*00b67f09SDavid van Moolenbroek
3548*00b67f09SDavid van Moolenbroek if (result == ISC_R_SUCCESS)
3549*00b67f09SDavid van Moolenbroek result = DNS_R_NEWORIGIN;
3550*00b67f09SDavid van Moolenbroek
3551*00b67f09SDavid van Moolenbroek } else
3552*00b67f09SDavid van Moolenbroek result = ISC_R_SUCCESS;
3553*00b67f09SDavid van Moolenbroek
3554*00b67f09SDavid van Moolenbroek } else
3555*00b67f09SDavid van Moolenbroek result = ISC_R_NOMORE;
3556*00b67f09SDavid van Moolenbroek
3557*00b67f09SDavid van Moolenbroek return (result);
3558*00b67f09SDavid van Moolenbroek }
3559*00b67f09SDavid van Moolenbroek
3560*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbtnodechain_first(dns_rbtnodechain_t * chain,dns_rbt_t * rbt,dns_name_t * name,dns_name_t * origin)3561*00b67f09SDavid van Moolenbroek dns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
3562*00b67f09SDavid van Moolenbroek dns_name_t *name, dns_name_t *origin)
3563*00b67f09SDavid van Moolenbroek
3564*00b67f09SDavid van Moolenbroek {
3565*00b67f09SDavid van Moolenbroek isc_result_t result;
3566*00b67f09SDavid van Moolenbroek
3567*00b67f09SDavid van Moolenbroek REQUIRE(VALID_RBT(rbt));
3568*00b67f09SDavid van Moolenbroek REQUIRE(VALID_CHAIN(chain));
3569*00b67f09SDavid van Moolenbroek
3570*00b67f09SDavid van Moolenbroek dns_rbtnodechain_reset(chain);
3571*00b67f09SDavid van Moolenbroek
3572*00b67f09SDavid van Moolenbroek chain->end = rbt->root;
3573*00b67f09SDavid van Moolenbroek
3574*00b67f09SDavid van Moolenbroek result = dns_rbtnodechain_current(chain, name, origin, NULL);
3575*00b67f09SDavid van Moolenbroek
3576*00b67f09SDavid van Moolenbroek if (result == ISC_R_SUCCESS)
3577*00b67f09SDavid van Moolenbroek result = DNS_R_NEWORIGIN;
3578*00b67f09SDavid van Moolenbroek
3579*00b67f09SDavid van Moolenbroek return (result);
3580*00b67f09SDavid van Moolenbroek }
3581*00b67f09SDavid van Moolenbroek
3582*00b67f09SDavid van Moolenbroek isc_result_t
dns_rbtnodechain_last(dns_rbtnodechain_t * chain,dns_rbt_t * rbt,dns_name_t * name,dns_name_t * origin)3583*00b67f09SDavid van Moolenbroek dns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
3584*00b67f09SDavid van Moolenbroek dns_name_t *name, dns_name_t *origin)
3585*00b67f09SDavid van Moolenbroek
3586*00b67f09SDavid van Moolenbroek {
3587*00b67f09SDavid van Moolenbroek isc_result_t result;
3588*00b67f09SDavid van Moolenbroek
3589*00b67f09SDavid van Moolenbroek REQUIRE(VALID_RBT(rbt));
3590*00b67f09SDavid van Moolenbroek REQUIRE(VALID_CHAIN(chain));
3591*00b67f09SDavid van Moolenbroek
3592*00b67f09SDavid van Moolenbroek dns_rbtnodechain_reset(chain);
3593*00b67f09SDavid van Moolenbroek
3594*00b67f09SDavid van Moolenbroek result = move_chain_to_last(chain, rbt->root);
3595*00b67f09SDavid van Moolenbroek if (result != ISC_R_SUCCESS)
3596*00b67f09SDavid van Moolenbroek return (result);
3597*00b67f09SDavid van Moolenbroek
3598*00b67f09SDavid van Moolenbroek result = dns_rbtnodechain_current(chain, name, origin, NULL);
3599*00b67f09SDavid van Moolenbroek
3600*00b67f09SDavid van Moolenbroek if (result == ISC_R_SUCCESS)
3601*00b67f09SDavid van Moolenbroek result = DNS_R_NEWORIGIN;
3602*00b67f09SDavid van Moolenbroek
3603*00b67f09SDavid van Moolenbroek return (result);
3604*00b67f09SDavid van Moolenbroek }
3605*00b67f09SDavid van Moolenbroek
3606*00b67f09SDavid van Moolenbroek
3607*00b67f09SDavid van Moolenbroek void
dns_rbtnodechain_reset(dns_rbtnodechain_t * chain)3608*00b67f09SDavid van Moolenbroek dns_rbtnodechain_reset(dns_rbtnodechain_t *chain) {
3609*00b67f09SDavid van Moolenbroek
3610*00b67f09SDavid van Moolenbroek REQUIRE(VALID_CHAIN(chain));
3611*00b67f09SDavid van Moolenbroek
3612*00b67f09SDavid van Moolenbroek /*
3613*00b67f09SDavid van Moolenbroek * Free any dynamic storage associated with 'chain', and then
3614*00b67f09SDavid van Moolenbroek * reinitialize 'chain'.
3615*00b67f09SDavid van Moolenbroek */
3616*00b67f09SDavid van Moolenbroek chain->end = NULL;
3617*00b67f09SDavid van Moolenbroek chain->level_count = 0;
3618*00b67f09SDavid van Moolenbroek chain->level_matches = 0;
3619*00b67f09SDavid van Moolenbroek }
3620*00b67f09SDavid van Moolenbroek
3621*00b67f09SDavid van Moolenbroek void
dns_rbtnodechain_invalidate(dns_rbtnodechain_t * chain)3622*00b67f09SDavid van Moolenbroek dns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain) {
3623*00b67f09SDavid van Moolenbroek /*
3624*00b67f09SDavid van Moolenbroek * Free any dynamic storage associated with 'chain', and then
3625*00b67f09SDavid van Moolenbroek * invalidate 'chain'.
3626*00b67f09SDavid van Moolenbroek */
3627*00b67f09SDavid van Moolenbroek
3628*00b67f09SDavid van Moolenbroek dns_rbtnodechain_reset(chain);
3629*00b67f09SDavid van Moolenbroek
3630*00b67f09SDavid van Moolenbroek chain->magic = 0;
3631*00b67f09SDavid van Moolenbroek }
3632*00b67f09SDavid van Moolenbroek
3633*00b67f09SDavid van Moolenbroek /* XXXMUKS:
3634*00b67f09SDavid van Moolenbroek *
3635*00b67f09SDavid van Moolenbroek * - worth removing inline as static functions are inlined automatically
3636*00b67f09SDavid van Moolenbroek * where suitable by modern compilers.
3637*00b67f09SDavid van Moolenbroek * - bump the size of dns_rbt.nodecount to size_t.
3638*00b67f09SDavid van Moolenbroek * - the dumpfile header also contains a nodecount that is unsigned
3639*00b67f09SDavid van Moolenbroek * int. If large files (> 2^32 nodes) are to be supported, the
3640*00b67f09SDavid van Moolenbroek * allocation for this field should be increased.
3641*00b67f09SDavid van Moolenbroek */
3642