radix.c 16.1 KB
Newer Older
1
/*
2
 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
Automatic Updater's avatar
Automatic Updater committed
3
 *
4
5
6
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7
8
9
 *
 * See the COPYRIGHT file distributed with this work for additional
 * information regarding copyright ownership.
10
11
12
13
14
15
16
17
 */

/*
 * This source was adapted from MRT's RCS Ids:
 * Id: radix.c,v 1.10.2.1 1999/11/29 05:16:24 masaki Exp
 * Id: prefix.c,v 1.37.2.9 2000/03/10 02:53:19 labovit Exp
 */

18
19
#include <inttypes.h>

20
#include <isc/mem.h>
21
#include <isc/radix.h>
22
23
24
#include <isc/types.h>
#include <isc/util.h>

25
#define BIT_TEST(f, b) (((f) & (b)) != 0)
26

Ondřej Surý's avatar
Ondřej Surý committed
27
28
29
static isc_result_t
_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest,
	    int bitlen);
30

Ondřej Surý's avatar
Ondřej Surý committed
31
32
static void
_deref_prefix(isc_prefix_t *prefix);
33

Ondřej Surý's avatar
Ondřej Surý committed
34
35
static isc_result_t
_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix);
36

Ondřej Surý's avatar
Ondřej Surý committed
37
38
static int
_comp_with_mask(void *addr, void *dest, u_int mask);
39

Ondřej Surý's avatar
Ondřej Surý committed
40
41
static void
_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func);
42
43
44

static isc_result_t
_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest,
Evan Hunt's avatar
Evan Hunt committed
45
	    int bitlen) {
46
47
	isc_prefix_t *prefix;

Mark Andrews's avatar
Mark Andrews committed
48
49
	REQUIRE(target != NULL);

50
	if (family != AF_INET6 && family != AF_INET && family != AF_UNSPEC) {
51
		return (ISC_R_NOTIMPLEMENTED);
52
	}
53
54
55
56
57

	prefix = isc_mem_get(mctx, sizeof(isc_prefix_t));

	if (family == AF_INET6) {
		prefix->bitlen = (bitlen >= 0) ? bitlen : 128;
58
		memmove(&prefix->add.sin6, dest, 16);
59
	} else {
60
		/* AF_UNSPEC is "any" or "none"--treat it as AF_INET */
61
		prefix->bitlen = (bitlen >= 0) ? bitlen : 32;
62
		memmove(&prefix->add.sin, dest, 4);
63
64
65
	}

	prefix->family = family;
66
67
	prefix->mctx = NULL;
	isc_mem_attach(mctx, &prefix->mctx);
68
69
70
71
72
73
74

	isc_refcount_init(&prefix->refcount, 1);

	*target = prefix;
	return (ISC_R_SUCCESS);
}

Automatic Updater's avatar
Automatic Updater committed
75
static void
Evan Hunt's avatar
Evan Hunt committed
76
_deref_prefix(isc_prefix_t *prefix) {
77
78
79
80
81
82
	if (prefix != NULL) {
		if (isc_refcount_decrement(&prefix->refcount) == 1) {
			isc_refcount_destroy(&prefix->refcount);
			isc_mem_putanddetach(&prefix->mctx, prefix,
					     sizeof(isc_prefix_t));
		}
83
84
85
86
	}
}

static isc_result_t
Evan Hunt's avatar
Evan Hunt committed
87
_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix) {
Mark Andrews's avatar
Mark Andrews committed
88
89
	INSIST(prefix != NULL);
	INSIST((prefix->family == AF_INET && prefix->bitlen <= 32) ||
90
91
	       (prefix->family == AF_INET6 && prefix->bitlen <= 128) ||
	       (prefix->family == AF_UNSPEC && prefix->bitlen == 0));
92
	REQUIRE(target != NULL && *target == NULL);
Mark Andrews's avatar
Mark Andrews committed
93

94
95
96
97
98
	/*
	 * If this prefix is a static allocation, copy it into new memory.
	 * (Note, the refcount still has to be destroyed by the calling
	 * routine.)
	 */
Mark Andrews's avatar
Mark Andrews committed
99
100
	if (isc_refcount_current(&prefix->refcount) == 0) {
		isc_result_t ret;
101
102
		ret = _new_prefix(mctx, target, prefix->family, &prefix->add,
				  prefix->bitlen);
103
		return (ret);
104
105
	}

106
	isc_refcount_increment(&prefix->refcount);
Mark Andrews's avatar
Mark Andrews committed
107

108
109
110
111
	*target = prefix;
	return (ISC_R_SUCCESS);
}

Automatic Updater's avatar
Automatic Updater committed
112
static int
Evan Hunt's avatar
Evan Hunt committed
113
_comp_with_mask(void *addr, void *dest, u_int mask) {
114
	/* Mask length of zero matches everything */
115
	if (mask == 0) {
116
		return (1);
117
	}
118

119
	if (memcmp(addr, dest, mask / 8) == 0) {
120
121
		u_int n = mask / 8;
		u_int m = ((~0U) << (8 - (mask % 8)));
122
123

		if ((mask % 8) == 0 ||
124
		    (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m)) {
125
			return (1);
126
		}
127
128
129
130
131
	}
	return (0);
}

isc_result_t
Evan Hunt's avatar
Evan Hunt committed
132
isc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits) {
133
134
	isc_radix_tree_t *radix;

135
	REQUIRE(target != NULL && *target == NULL);
Mark Andrews's avatar
Mark Andrews committed
136

137
138
	radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t));

139
140
	radix->mctx = NULL;
	isc_mem_attach(mctx, &radix->mctx);
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
	radix->maxbits = maxbits;
	radix->head = NULL;
	radix->num_active_node = 0;
	radix->num_added_node = 0;
	RUNTIME_CHECK(maxbits <= RADIX_MAXBITS); /* XXX */
	radix->magic = RADIX_TREE_MAGIC;
	*target = radix;
	return (ISC_R_SUCCESS);
}

/*
 * if func is supplied, it will be called as func(node->data)
 * before deleting the node
 */

static void
Evan Hunt's avatar
Evan Hunt committed
157
_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
Mark Andrews's avatar
Mark Andrews committed
158
	REQUIRE(radix != NULL);
159

Mark Andrews's avatar
Mark Andrews committed
160
	if (radix->head != NULL) {
Evan Hunt's avatar
Evan Hunt committed
161
		isc_radix_node_t *Xstack[RADIX_MAXBITS + 1];
162
		isc_radix_node_t **Xsp = Xstack;
Evan Hunt's avatar
Evan Hunt committed
163
		isc_radix_node_t *Xrn = radix->head;
164
165
166
167
168

		while (Xrn != NULL) {
			isc_radix_node_t *l = Xrn->l;
			isc_radix_node_t *r = Xrn->r;

Mark Andrews's avatar
Mark Andrews committed
169
			if (Xrn->prefix != NULL) {
170
				_deref_prefix(Xrn->prefix);
171
				if (func != NULL) {
172
					func(Xrn->data);
173
				}
174
			} else {
Evan Hunt's avatar
Evan Hunt committed
175
176
				INSIST(Xrn->data[RADIX_V4] == NULL &&
				       Xrn->data[RADIX_V6] == NULL);
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
			}

			isc_mem_put(radix->mctx, Xrn, sizeof(*Xrn));
			radix->num_active_node--;

			if (l != NULL) {
				if (r != NULL) {
					*Xsp++ = r;
				}
				Xrn = l;
			} else if (r != NULL) {
				Xrn = r;
			} else if (Xsp != Xstack) {
				Xrn = *(--Xsp);
			} else {
				Xrn = NULL;
			}
		}
	}
	RUNTIME_CHECK(radix->num_active_node == 0);
}

void
Evan Hunt's avatar
Evan Hunt committed
200
isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
Mark Andrews's avatar
Mark Andrews committed
201
	REQUIRE(radix != NULL);
202
	_clear_radix(radix, func);
203
	isc_mem_putanddetach(&radix->mctx, radix, sizeof(*radix));
204
205
206
207
208
209
}

/*
 * func will be called as func(node->prefix, node->data)
 */
void
Evan Hunt's avatar
Evan Hunt committed
210
isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func) {
211
212
	isc_radix_node_t *node;

Mark Andrews's avatar
Mark Andrews committed
213
	REQUIRE(func != NULL);
214

215
216
	RADIX_WALK(radix->head, node) { func(node->prefix, node->data); }
	RADIX_WALK_END;
217
218
219
220
}

isc_result_t
isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target,
Evan Hunt's avatar
Evan Hunt committed
221
		 isc_prefix_t *prefix) {
222
223
	isc_radix_node_t *node;
	isc_radix_node_t *stack[RADIX_MAXBITS + 1];
Evan Hunt's avatar
Evan Hunt committed
224
225
226
	u_char *addr;
	uint32_t bitlen;
	int tfam = -1, cnt = 0;
227
228
229

	REQUIRE(radix != NULL);
	REQUIRE(prefix != NULL);
230
	REQUIRE(target != NULL && *target == NULL);
231
232
233
234
	RUNTIME_CHECK(prefix->bitlen <= radix->maxbits);

	*target = NULL;

235
236
237
	node = radix->head;

	if (node == NULL) {
238
239
240
241
242
243
		return (ISC_R_NOTFOUND);
	}

	addr = isc_prefix_touchar(prefix);
	bitlen = prefix->bitlen;

244
	while (node != NULL && node->bit < bitlen) {
245
		if (node->prefix) {
246
			stack[cnt++] = node;
247
		}
248

Evan Hunt's avatar
Evan Hunt committed
249
250
		if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
		{
251
			node = node->r;
252
		} else {
253
			node = node->l;
254
		}
255
256
	}

257
	if (node != NULL && node->prefix) {
258
		stack[cnt++] = node;
259
	}
260

261
	while (cnt-- > 0) {
262
263
		node = stack[cnt];

264
		if (prefix->bitlen < node->bit) {
265
			continue;
266
		}
267

Automatic Updater's avatar
Automatic Updater committed
268
		if (_comp_with_mask(isc_prefix_tochar(node->prefix),
269
				    isc_prefix_tochar(prefix),
Evan Hunt's avatar
Evan Hunt committed
270
271
				    node->prefix->bitlen))
		{
Evan Hunt's avatar
Evan Hunt committed
272
273
			int fam = ISC_RADIX_FAMILY(prefix);
			if (node->node_num[fam] != -1 &&
Evan Hunt's avatar
Evan Hunt committed
274
			    ((*target == NULL) ||
Evan Hunt's avatar
Evan Hunt committed
275
276
			     (*target)->node_num[tfam] > node->node_num[fam]))
			{
Mark Andrews's avatar
Mark Andrews committed
277
				*target = node;
Evan Hunt's avatar
Evan Hunt committed
278
				tfam = fam;
279
			}
280
281
282
283
284
285
286
287
288
289
290
291
		}
	}

	if (*target == NULL) {
		return (ISC_R_NOTFOUND);
	} else {
		return (ISC_R_SUCCESS);
	}
}

isc_result_t
isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target,
Evan Hunt's avatar
Evan Hunt committed
292
		 isc_radix_node_t *source, isc_prefix_t *prefix) {
293
	isc_radix_node_t *node, *new_node, *parent, *glue = NULL;
Evan Hunt's avatar
Evan Hunt committed
294
295
296
297
	u_char *addr, *test_addr;
	uint32_t bitlen, fam, check_bit, differ_bit;
	uint32_t i, j, r;
	isc_result_t result;
298

299
	REQUIRE(radix != NULL);
300
	REQUIRE(target != NULL && *target == NULL);
301
302
	REQUIRE(prefix != NULL || (source != NULL && source->prefix != NULL));
	RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits);
303

304
	if (prefix == NULL) {
Mark Andrews's avatar
Mark Andrews committed
305
		prefix = source->prefix;
306
	}
307

308
	INSIST(prefix != NULL);
309
310

	bitlen = prefix->bitlen;
311
	fam = prefix->family;
312

313
314
	if (radix->head == NULL) {
		node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
315
		node->bit = bitlen;
Evan Hunt's avatar
Evan Hunt committed
316
		for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
317
			node->node_num[i] = -1;
318
		}
319
		node->prefix = NULL;
320
321
322
323
324
325
326
327
		result = _ref_prefix(radix->mctx, &node->prefix, prefix);
		if (result != ISC_R_SUCCESS) {
			isc_mem_put(radix->mctx, node,
				    sizeof(isc_radix_node_t));
			return (result);
		}
		node->parent = NULL;
		node->l = node->r = NULL;
328
329
330
331
332
333
334
335
336
		if (source != NULL) {
			/*
			 * If source is non-NULL, then we're merging in a
			 * node from an existing radix tree.  To keep
			 * the node_num values consistent, the calling
			 * function will add the total number of nodes
			 * added to num_added_node at the end of
			 * the merge operation--we don't do it here.
			 */
Evan Hunt's avatar
Evan Hunt committed
337
338
			for (i = 0; i < RADIX_FAMILIES; i++) {
				if (source->node_num[i] != -1) {
Evan Hunt's avatar
Evan Hunt committed
339
340
341
					node->node_num[i] =
						radix->num_added_node +
						source->node_num[i];
Evan Hunt's avatar
Evan Hunt committed
342
				}
Evan Hunt's avatar
Evan Hunt committed
343
344
				node->data[i] = source->data[i];
			}
345
		} else {
Evan Hunt's avatar
Evan Hunt committed
346
			int next = ++radix->num_added_node;
347
348
			if (fam == AF_UNSPEC) {
				/* "any" or "none" */
Evan Hunt's avatar
Evan Hunt committed
349
				for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
350
					node->node_num[i] = next;
351
				}
352
			} else {
Evan Hunt's avatar
Evan Hunt committed
353
				node->node_num[ISC_RADIX_FAMILY(prefix)] = next;
354
			}
Evan Hunt's avatar
Evan Hunt committed
355
356

			memset(node->data, 0, sizeof(node->data));
357
		}
358
359
360
361
362
363
364
365
366
367
368
		radix->head = node;
		radix->num_active_node++;
		*target = node;
		return (ISC_R_SUCCESS);
	}

	addr = isc_prefix_touchar(prefix);
	node = radix->head;

	while (node->bit < bitlen || node->prefix == NULL) {
		if (node->bit < radix->maxbits &&
Evan Hunt's avatar
Evan Hunt committed
369
370
		    BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
		{
371
			if (node->r == NULL) {
372
				break;
373
			}
374
375
			node = node->r;
		} else {
376
			if (node->l == NULL) {
377
				break;
378
			}
379
380
381
382
383
384
			node = node->l;
		}

		INSIST(node != NULL);
	}

385
	INSIST(node->prefix != NULL);
386
387
388
389
390

	test_addr = isc_prefix_touchar(node->prefix);
	/* Find the first bit different. */
	check_bit = (node->bit < bitlen) ? node->bit : bitlen;
	differ_bit = 0;
Evan Hunt's avatar
Evan Hunt committed
391
	for (i = 0; i * 8 < check_bit; i++) {
392
393
394
395
396
397
		if ((r = (addr[i] ^ test_addr[i])) == 0) {
			differ_bit = (i + 1) * 8;
			continue;
		}
		/* I know the better way, but for now. */
		for (j = 0; j < 8; j++) {
398
			if (BIT_TEST(r, (0x80 >> j))) {
399
				break;
400
			}
401
402
403
404
405
406
407
		}
		/* Must be found. */
		INSIST(j < 8);
		differ_bit = i * 8 + j;
		break;
	}

408
	if (differ_bit > check_bit) {
409
		differ_bit = check_bit;
410
	}
411
412

	parent = node->parent;
413
	while (parent != NULL && parent->bit >= differ_bit) {
414
415
416
417
418
		node = parent;
		parent = node->parent;
	}

	if (differ_bit == bitlen && node->bit == bitlen) {
419
		if (node->prefix != NULL) {
420
			/* Set node_num only if it hasn't been set before */
Automatic Updater's avatar
Automatic Updater committed
421
			if (source != NULL) {
Evan Hunt's avatar
Evan Hunt committed
422
				/* Merging nodes */
Evan Hunt's avatar
Evan Hunt committed
423
				for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
424
					if (node->node_num[i] == -1 &&
425
					    source->node_num[i] != -1) {
Evan Hunt's avatar
Evan Hunt committed
426
427
428
429
430
						node->node_num[i] =
							radix->num_added_node +
							source->node_num[i];
						node->data[i] = source->data[i];
					}
Automatic Updater's avatar
Automatic Updater committed
431
432
				}
			} else {
433
434
435
				if (fam == AF_UNSPEC) {
					/* "any" or "none" */
					int next = radix->num_added_node + 1;
436
					for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
437
438
439
440
441
442
						if (node->node_num[i] == -1) {
							node->node_num[i] =
								next;
							radix->num_added_node =
								next;
						}
443
444
					}
				} else {
Evan Hunt's avatar
Evan Hunt committed
445
446
447
					int foff = ISC_RADIX_FAMILY(prefix);
					if (node->node_num[foff] == -1) {
						node->node_num[foff] =
Evan Hunt's avatar
Evan Hunt committed
448
							++radix->num_added_node;
Evan Hunt's avatar
Evan Hunt committed
449
					}
450
				}
Automatic Updater's avatar
Automatic Updater committed
451
			}
452
453
			*target = node;
			return (ISC_R_SUCCESS);
Automatic Updater's avatar
Automatic Updater committed
454
		} else {
Evan Hunt's avatar
Evan Hunt committed
455
456
			result = _ref_prefix(radix->mctx, &node->prefix,
					     prefix);
457
			if (result != ISC_R_SUCCESS) {
Automatic Updater's avatar
Automatic Updater committed
458
				return (result);
459
			}
Automatic Updater's avatar
Automatic Updater committed
460
		}
Evan Hunt's avatar
Evan Hunt committed
461
462
463
464
		INSIST(node->data[RADIX_V4] == NULL &&
		       node->node_num[RADIX_V4] == -1 &&
		       node->data[RADIX_V4] == NULL &&
		       node->node_num[RADIX_V4] == -1);
465
466
		if (source != NULL) {
			/* Merging node */
Evan Hunt's avatar
Evan Hunt committed
467
			for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
468
469
470
471
472
473
				int cur = radix->num_added_node;
				if (source->node_num[i] != -1) {
					node->node_num[i] =
						source->node_num[i] + cur;
					node->data[i] = source->data[i];
				}
Automatic Updater's avatar
Automatic Updater committed
474
			}
475
		} else {
Evan Hunt's avatar
Evan Hunt committed
476
			int next = ++radix->num_added_node;
477
478
			if (fam == AF_UNSPEC) {
				/* "any" or "none" */
Evan Hunt's avatar
Evan Hunt committed
479
				for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
480
					node->node_num[i] = next;
481
				}
482
			} else {
Evan Hunt's avatar
Evan Hunt committed
483
				node->node_num[ISC_RADIX_FAMILY(prefix)] = next;
484
			}
485
		}
486
487
488
489
490
491
492
493
		*target = node;
		return (ISC_R_SUCCESS);
	}

	new_node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
	if (node->bit != differ_bit && bitlen != differ_bit) {
		glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
	}
494
	new_node->bit = bitlen;
495
	new_node->prefix = NULL;
496
497
498
	result = _ref_prefix(radix->mctx, &new_node->prefix, prefix);
	if (result != ISC_R_SUCCESS) {
		isc_mem_put(radix->mctx, new_node, sizeof(isc_radix_node_t));
499
		if (glue != NULL) {
500
501
			isc_mem_put(radix->mctx, glue,
				    sizeof(isc_radix_node_t));
502
		}
503
504
505
506
		return (result);
	}
	new_node->parent = NULL;
	new_node->l = new_node->r = NULL;
Evan Hunt's avatar
Evan Hunt committed
507
	for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
508
		new_node->node_num[i] = -1;
509
510
		new_node->data[i] = NULL;
	}
511
512
	radix->num_active_node++;

513
	if (source != NULL) {
514
		/* Merging node */
Evan Hunt's avatar
Evan Hunt committed
515
		for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
516
517
			int cur = radix->num_added_node;
			if (source->node_num[i] != -1) {
Evan Hunt's avatar
Evan Hunt committed
518
519
				new_node->node_num[i] = source->node_num[i] +
							cur;
Evan Hunt's avatar
Evan Hunt committed
520
521
522
				new_node->data[i] = source->data[i];
			}
		}
Mark Andrews's avatar
Mark Andrews committed
523
	} else {
Evan Hunt's avatar
Evan Hunt committed
524
		int next = ++radix->num_added_node;
525
526
		if (fam == AF_UNSPEC) {
			/* "any" or "none" */
527
			for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
528
				new_node->node_num[i] = next;
529
			}
530
		} else {
Evan Hunt's avatar
Evan Hunt committed
531
			new_node->node_num[ISC_RADIX_FAMILY(prefix)] = next;
532
		}
Evan Hunt's avatar
Evan Hunt committed
533
		memset(new_node->data, 0, sizeof(new_node->data));
Mark Andrews's avatar
Mark Andrews committed
534
	}
535
536
537
538
539

	if (node->bit == differ_bit) {
		INSIST(glue == NULL);
		new_node->parent = node;
		if (node->bit < radix->maxbits &&
Evan Hunt's avatar
Evan Hunt committed
540
541
		    BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
		{
542
543
544
545
546
547
548
549
550
551
552
553
554
			INSIST(node->r == NULL);
			node->r = new_node;
		} else {
			INSIST(node->l == NULL);
			node->l = new_node;
		}
		*target = new_node;
		return (ISC_R_SUCCESS);
	}

	if (bitlen == differ_bit) {
		INSIST(glue == NULL);
		if (bitlen < radix->maxbits &&
Evan Hunt's avatar
Evan Hunt committed
555
556
		    BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07)))
		{
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
			new_node->r = node;
		} else {
			new_node->l = node;
		}
		new_node->parent = node->parent;
		if (node->parent == NULL) {
			INSIST(radix->head == node);
			radix->head = new_node;
		} else if (node->parent->r == node) {
			node->parent->r = new_node;
		} else {
			node->parent->l = new_node;
		}
		node->parent = new_node;
	} else {
		INSIST(glue != NULL);
		glue->bit = differ_bit;
		glue->prefix = NULL;
		glue->parent = node->parent;
Evan Hunt's avatar
Evan Hunt committed
576
		for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
577
578
579
			glue->data[i] = NULL;
			glue->node_num[i] = -1;
		}
580
581
		radix->num_active_node++;
		if (differ_bit < radix->maxbits &&
Evan Hunt's avatar
Evan Hunt committed
582
583
		    BIT_TEST(addr[differ_bit >> 3], 0x80 >> (differ_bit & 07)))
		{
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
			glue->r = new_node;
			glue->l = node;
		} else {
			glue->r = node;
			glue->l = new_node;
		}
		new_node->parent = glue;

		if (node->parent == NULL) {
			INSIST(radix->head == node);
			radix->head = glue;
		} else if (node->parent->r == node) {
			node->parent->r = glue;
		} else {
			node->parent->l = glue;
		}
		node->parent = glue;
	}

	*target = new_node;
	return (ISC_R_SUCCESS);
}

void
Evan Hunt's avatar
Evan Hunt committed
608
isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) {
609
610
611
612
613
614
615
616
	isc_radix_node_t *parent, *child;

	REQUIRE(radix != NULL);
	REQUIRE(node != NULL);

	if (node->r && node->l) {
		/*
		 * This might be a placeholder node -- have to check and
Francis Dupont's avatar
Francis Dupont committed
617
		 * make sure there is a prefix associated with it!
618
		 */
619
		if (node->prefix != NULL) {
620
			_deref_prefix(node->prefix);
621
		}
622
623

		node->prefix = NULL;
Evan Hunt's avatar
Evan Hunt committed
624
		memset(node->data, 0, sizeof(node->data));
625
626
627
628
629
		return;
	}

	if (node->r == NULL && node->l == NULL) {
		parent = node->parent;
630
		_deref_prefix(node->prefix);
631
632
633
634

		if (parent == NULL) {
			INSIST(radix->head == node);
			radix->head = NULL;
635
636
			isc_mem_put(radix->mctx, node, sizeof(*node));
			radix->num_active_node--;
637
638
639
640
641
642
643
644
645
646
647
648
			return;
		}

		if (parent->r == node) {
			parent->r = NULL;
			child = parent->l;
		} else {
			INSIST(parent->l == node);
			parent->l = NULL;
			child = parent->r;
		}

649
650
651
		isc_mem_put(radix->mctx, node, sizeof(*node));
		radix->num_active_node--;

652
		if (parent->prefix) {
653
			return;
654
		}
655
656
657
658
659
660
661
662
663
664
665

		/* We need to remove parent too. */
		if (parent->parent == NULL) {
			INSIST(radix->head == parent);
			radix->head = child;
		} else if (parent->parent->r == parent) {
			parent->parent->r = child;
		} else {
			INSIST(parent->parent->l == parent);
			parent->parent->l = child;
		}
666

667
668
669
670
671
672
673
674
675
676
677
678
		child->parent = parent->parent;
		isc_mem_put(radix->mctx, parent, sizeof(*parent));
		radix->num_active_node--;
		return;
	}

	if (node->r) {
		child = node->r;
	} else {
		INSIST(node->l != NULL);
		child = node->l;
	}
679

680
681
682
	parent = node->parent;
	child->parent = parent;

683
	_deref_prefix(node->prefix);
684
685
686
687

	if (parent == NULL) {
		INSIST(radix->head == node);
		radix->head = child;
688
689
		isc_mem_put(radix->mctx, node, sizeof(*node));
		radix->num_active_node--;
690
691
692
		return;
	}

693
694
695
	isc_mem_put(radix->mctx, node, sizeof(*node));
	radix->num_active_node--;

696
697
698
699
700
701
702
	if (parent->r == node) {
		parent->r = child;
	} else {
		INSIST(parent->l == node);
		parent->l = child;
	}
}