radix.c 16.8 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
 */

Automatic Updater's avatar
Automatic Updater committed
12

13
14
15
16
17
18
/*
 * 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
 */

19
20
#include <config.h>

21
22
#include <inttypes.h>

23
24
25
26
27
#include <isc/mem.h>
#include <isc/types.h>
#include <isc/util.h>
#include <isc/radix.h>

28
29
#define BIT_TEST(f, b)  (((f) & (b)) != 0)

30
31
32
33
34
static isc_result_t
_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family,
	    void *dest, int bitlen);

static void
35
_deref_prefix(isc_prefix_t *prefix);
36
37
38
39
40
41
42
43

static isc_result_t
_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix);

static int
_comp_with_mask(void *addr, void *dest, u_int mask);

static void
Mark Andrews's avatar
Mark Andrews committed
44
_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func);
45
46
47
48
49
50
51

static isc_result_t
_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest,
	    int bitlen)
{
	isc_prefix_t *prefix;

Mark Andrews's avatar
Mark Andrews committed
52
53
	REQUIRE(target != NULL);

54
	if (family != AF_INET6 && family != AF_INET && family != AF_UNSPEC)
55
56
57
58
59
60
61
62
		return (ISC_R_NOTIMPLEMENTED);

	prefix = isc_mem_get(mctx, sizeof(isc_prefix_t));
	if (prefix == NULL)
		return (ISC_R_NOMEMORY);

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

	prefix->family = family;
71
	prefix->ecs = false;
72
73
	prefix->mctx = NULL;
	isc_mem_attach(mctx, &prefix->mctx);
74
75
76
77
78
79
80

	isc_refcount_init(&prefix->refcount, 1);

	*target = prefix;
	return (ISC_R_SUCCESS);
}

Automatic Updater's avatar
Automatic Updater committed
81
static void
82
_deref_prefix(isc_prefix_t *prefix) {
83
84
85
86
87
88
89
90
91
	int refs;

	if (prefix == NULL)
		return;

	isc_refcount_decrement(&prefix->refcount, &refs);

	if (refs <= 0) {
		isc_refcount_destroy(&prefix->refcount);
92
93
		isc_mem_putanddetach(&prefix->mctx, prefix,
				     sizeof(isc_prefix_t));
94
95
96
97
98
	}
}

static isc_result_t
_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix) {
Mark Andrews's avatar
Mark Andrews committed
99
100
	INSIST(prefix != NULL);
	INSIST((prefix->family == AF_INET && prefix->bitlen <= 32) ||
101
102
	       (prefix->family == AF_INET6 && prefix->bitlen <= 128) ||
	       (prefix->family == AF_UNSPEC && prefix->bitlen == 0));
103
	REQUIRE(target != NULL && *target == NULL);
Mark Andrews's avatar
Mark Andrews committed
104

105
106
107
108
109
	/*
	 * 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
110
111
112
113
	if (isc_refcount_current(&prefix->refcount) == 0) {
		isc_result_t ret;
		ret = _new_prefix(mctx, target, prefix->family,
				  &prefix->add, prefix->bitlen);
114
		return (ret);
115
116
	}

Mark Andrews's avatar
Mark Andrews committed
117
118
	isc_refcount_increment(&prefix->refcount, NULL);

119
120
121
122
	*target = prefix;
	return (ISC_R_SUCCESS);
}

Automatic Updater's avatar
Automatic Updater committed
123
static int
124
125
_comp_with_mask(void *addr, void *dest, u_int mask) {

126
127
128
	/* Mask length of zero matches everything */
	if (mask == 0)
		return (1);
129

130
	if (memcmp(addr, dest, mask / 8) == 0) {
131
132
		u_int n = mask / 8;
		u_int m = ((~0U) << (8 - (mask % 8)));
133
134
135
136
137
138
139
140
141
142
143
144

		if ((mask % 8) == 0 ||
		    (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m))
			return (1);
	}
	return (0);
}

isc_result_t
isc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits) {
	isc_radix_tree_t *radix;

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

147
148
149
150
	radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t));
	if (radix == NULL)
		return (ISC_R_NOMEMORY);

151
152
	radix->mctx = NULL;
	isc_mem_attach(mctx, &radix->mctx);
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
	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
Mark Andrews's avatar
Mark Andrews committed
169
170
_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
	REQUIRE(radix != NULL);
171

Mark Andrews's avatar
Mark Andrews committed
172
	if (radix->head != NULL) {
173
174
175
176
177
178
179
180
		isc_radix_node_t *Xstack[RADIX_MAXBITS+1];
		isc_radix_node_t **Xsp = Xstack;
		isc_radix_node_t *Xrn = radix->head;

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

Mark Andrews's avatar
Mark Andrews committed
181
			if (Xrn->prefix != NULL) {
182
				_deref_prefix(Xrn->prefix);
Evan Hunt's avatar
Evan Hunt committed
183
				if (func != NULL)
184
185
					func(Xrn->data);
			} else {
Evan Hunt's avatar
Evan Hunt committed
186
187
188
189
				INSIST(Xrn->data[RADIX_V4] == NULL &&
				       Xrn->data[RADIX_V6] == NULL &&
				       Xrn->data[RADIX_V4_ECS] == NULL &&
				       Xrn->data[RADIX_V6_ECS] == NULL);
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
			}

			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
214
isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
Mark Andrews's avatar
Mark Andrews committed
215
	REQUIRE(radix != NULL);
216
	_clear_radix(radix, func);
217
	isc_mem_putanddetach(&radix->mctx, radix, sizeof(*radix));
218
219
220
221
222
223
224
}


/*
 * func will be called as func(node->prefix, node->data)
 */
void
225
isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func) {
226
227
	isc_radix_node_t *node;

Mark Andrews's avatar
Mark Andrews committed
228
	REQUIRE(func != NULL);
229
230
231
232
233
234
235
236
237

	RADIX_WALK(radix->head, node) {
		func(node->prefix, node->data);
	} RADIX_WALK_END;
}


isc_result_t
isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target,
238
239
		 isc_prefix_t *prefix)
{
240
241
242
	isc_radix_node_t *node;
	isc_radix_node_t *stack[RADIX_MAXBITS + 1];
	u_char *addr;
243
	uint32_t bitlen;
Evan Hunt's avatar
Evan Hunt committed
244
	int tfam = -1, cnt = 0;
245
246
247

	REQUIRE(radix != NULL);
	REQUIRE(prefix != NULL);
248
	REQUIRE(target != NULL && *target == NULL);
249
250
251
252
	RUNTIME_CHECK(prefix->bitlen <= radix->maxbits);

	*target = NULL;

253
254
255
	node = radix->head;

	if (node == NULL) {
256
257
258
259
260
261
		return (ISC_R_NOTFOUND);
	}

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

262
263
	while (node != NULL && node->bit < bitlen) {
		if (node->prefix) {
264
			stack[cnt++] = node;
265
		}
266
267

		if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
268
		{
269
			node = node->r;
270
		} else {
271
			node = node->l;
272
		}
273
274
	}

275
	if (node != NULL && node->prefix) {
276
		stack[cnt++] = node;
277
	}
278

279
	while (cnt-- > 0) {
280
281
		node = stack[cnt];

282
		if (prefix->bitlen < node->bit) {
283
			continue;
284
		}
285

Automatic Updater's avatar
Automatic Updater committed
286
		if (_comp_with_mask(isc_prefix_tochar(node->prefix),
287
				    isc_prefix_tochar(prefix),
Evan Hunt's avatar
Evan Hunt committed
288
289
				    node->prefix->bitlen))
		{
Evan Hunt's avatar
Evan Hunt committed
290
291
			int fam = ISC_RADIX_FAMILY(prefix);
			if (node->node_num[fam] != -1 &&
Evan Hunt's avatar
Evan Hunt committed
292
			    ((*target == NULL) ||
Evan Hunt's avatar
Evan Hunt committed
293
			     (*target)->node_num[tfam] > node->node_num[fam]))
Evan Hunt's avatar
Evan Hunt committed
294
			{
Mark Andrews's avatar
Mark Andrews committed
295
				*target = node;
Evan Hunt's avatar
Evan Hunt committed
296
				tfam = fam;
297
			}
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
		}
	}

	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,
		 isc_radix_node_t *source, isc_prefix_t *prefix)
{
	isc_radix_node_t *node, *new_node, *parent, *glue = NULL;
	u_char *addr, *test_addr;
314
315
	uint32_t bitlen, fam, check_bit, differ_bit;
	uint32_t i, j, r;
316
317
	isc_result_t result;

318
	REQUIRE(radix != NULL);
319
	REQUIRE(target != NULL && *target == NULL);
320
321
	REQUIRE(prefix != NULL || (source != NULL && source->prefix != NULL));
	RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits);
322

323
	if (prefix == NULL)
Mark Andrews's avatar
Mark Andrews committed
324
		prefix = source->prefix;
325

326
	INSIST(prefix != NULL);
327
328

	bitlen = prefix->bitlen;
329
	fam = prefix->family;
330

331
332
333
334
	if (radix->head == NULL) {
		node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
		if (node == NULL)
			return (ISC_R_NOMEMORY);
335
		node->bit = bitlen;
Evan Hunt's avatar
Evan Hunt committed
336
		for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
337
			node->node_num[i] = -1;
Evan Hunt's avatar
Evan Hunt committed
338
		}
339
		node->prefix = NULL;
340
341
342
343
344
345
346
347
		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;
348
349
350
351
352
353
354
355
356
		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
357
358
			for (i = 0; i < RADIX_FAMILIES; i++) {
				if (source->node_num[i] != -1) {
Evan Hunt's avatar
Evan Hunt committed
359
360
361
					node->node_num[i] =
						radix->num_added_node +
						source->node_num[i];
Evan Hunt's avatar
Evan Hunt committed
362
				}
Evan Hunt's avatar
Evan Hunt committed
363
364
				node->data[i] = source->data[i];
			}
365
		} else {
Evan Hunt's avatar
Evan Hunt committed
366
			int next = ++radix->num_added_node;
367
368
			if (fam == AF_UNSPEC) {
				/* "any" or "none" */
Evan Hunt's avatar
Evan Hunt committed
369
				for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
370
					node->node_num[i] = next;
Evan Hunt's avatar
Evan Hunt committed
371
				}
372
			} else {
Evan Hunt's avatar
Evan Hunt committed
373
				node->node_num[ISC_RADIX_FAMILY(prefix)] = next;
374
			}
Evan Hunt's avatar
Evan Hunt committed
375
376

			memset(node->data, 0, sizeof(node->data));
377
		}
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
		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 &&
		    BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
		{
			if (node->r == NULL)
				break;
			node = node->r;
		} else {
			if (node->l == NULL)
				break;
			node = node->l;
		}

		INSIST(node != NULL);
	}

403
	INSIST(node->prefix != NULL);
404
405
406
407
408

	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
409
	for (i = 0; i * 8 < check_bit; i++) {
410
411
412
413
414
415
		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++) {
Evan Hunt's avatar
Evan Hunt committed
416
			if (BIT_TEST(r, (0x80 >> j)))
417
418
419
420
421
422
423
424
425
426
427
428
				break;
		}
		/* Must be found. */
		INSIST(j < 8);
		differ_bit = i * 8 + j;
		break;
	}

	if (differ_bit > check_bit)
		differ_bit = check_bit;

	parent = node->parent;
429
	while (parent != NULL && parent->bit >= differ_bit) {
430
431
432
433
434
		node = parent;
		parent = node->parent;
	}

	if (differ_bit == bitlen && node->bit == bitlen) {
435
		if (node->prefix != NULL) {
436
			/* Set node_num only if it hasn't been set before */
Automatic Updater's avatar
Automatic Updater committed
437
			if (source != NULL) {
Evan Hunt's avatar
Evan Hunt committed
438
				/* Merging nodes */
Evan Hunt's avatar
Evan Hunt committed
439
				for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
440
441
442
443
444
445
446
					if (node->node_num[i] == -1 &&
					    source->node_num[i] != -1) {
						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
447
448
				}
			} else {
449
450
451
				if (fam == AF_UNSPEC) {
					/* "any" or "none" */
					int next = radix->num_added_node + 1;
Evan Hunt's avatar
Evan Hunt committed
452
					for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
453
454
455
456
457
458
						if (node->node_num[i] == -1) {
							node->node_num[i] =
								next;
							radix->num_added_node =
								next;
						}
459
460
					}
				} else {
Evan Hunt's avatar
Evan Hunt committed
461
462
463
					int foff = ISC_RADIX_FAMILY(prefix);
					if (node->node_num[foff] == -1) {
						node->node_num[foff] =
Evan Hunt's avatar
Evan Hunt committed
464
							++radix->num_added_node;
Evan Hunt's avatar
Evan Hunt committed
465
					}
466
				}
Automatic Updater's avatar
Automatic Updater committed
467
			}
468
469
			*target = node;
			return (ISC_R_SUCCESS);
Automatic Updater's avatar
Automatic Updater committed
470
		} else {
471
472
			result = _ref_prefix(radix->mctx,
					     &node->prefix, prefix);
Automatic Updater's avatar
Automatic Updater committed
473
474
475
			if (result != ISC_R_SUCCESS)
				return (result);
		}
Evan Hunt's avatar
Evan Hunt committed
476
477
478
479
480
481
482
483
484
485
486

		/* Check everything is null and empty before we proceed */
		INSIST(node->data[RADIX_V4] == NULL &&
		       node->node_num[RADIX_V4] == -1 &&
		       node->data[RADIX_V6] == NULL &&
		       node->node_num[RADIX_V6] == -1 &&
		       node->data[RADIX_V4_ECS] == NULL &&
		       node->node_num[RADIX_V4_ECS] == -1 &&
		       node->data[RADIX_V6_ECS] == NULL &&
		       node->node_num[RADIX_V6_ECS] == -1);

487
488
		if (source != NULL) {
			/* Merging node */
Evan Hunt's avatar
Evan Hunt committed
489
			for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
490
491
492
493
494
495
				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
496
			}
497
		} else {
Evan Hunt's avatar
Evan Hunt committed
498
			int next = ++radix->num_added_node;
499
500
			if (fam == AF_UNSPEC) {
				/* "any" or "none" */
Evan Hunt's avatar
Evan Hunt committed
501
				for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
502
					node->node_num[i] = next;
Evan Hunt's avatar
Evan Hunt committed
503
				}
504
			} else {
Evan Hunt's avatar
Evan Hunt committed
505
				node->node_num[ISC_RADIX_FAMILY(prefix)] = next;
506
			}
507
		}
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
		*target = node;
		return (ISC_R_SUCCESS);
	}

	new_node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
	if (new_node == NULL)
		return (ISC_R_NOMEMORY);
	if (node->bit != differ_bit && bitlen != differ_bit) {
		glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
		if (glue == NULL) {
			isc_mem_put(radix->mctx, new_node,
				    sizeof(isc_radix_node_t));
			return (ISC_R_NOMEMORY);
		}
	}
523
	new_node->bit = bitlen;
524
	new_node->prefix = NULL;
525
526
527
528
529
530
531
532
533
534
	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));
		if (glue != NULL)
			isc_mem_put(radix->mctx, glue,
				    sizeof(isc_radix_node_t));
		return (result);
	}
	new_node->parent = NULL;
	new_node->l = new_node->r = NULL;
Evan Hunt's avatar
Evan Hunt committed
535
	for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
536
		new_node->node_num[i] = -1;
537
538
		new_node->data[i] = NULL;
	}
539
540
	radix->num_active_node++;

541
	if (source != NULL) {
542
		/* Merging node */
Evan Hunt's avatar
Evan Hunt committed
543
		for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
544
545
546
547
548
549
550
			int cur = radix->num_added_node;
			if (source->node_num[i] != -1) {
				new_node->node_num[i] =
					source->node_num[i] + cur;
				new_node->data[i] = source->data[i];
			}
		}
Mark Andrews's avatar
Mark Andrews committed
551
	} else {
Evan Hunt's avatar
Evan Hunt committed
552
		int next = ++radix->num_added_node;
553
554
		if (fam == AF_UNSPEC) {
			/* "any" or "none" */
Evan Hunt's avatar
Evan Hunt committed
555
			for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
556
				new_node->node_num[i] = next;
Evan Hunt's avatar
Evan Hunt committed
557
			}
558
		} else {
Evan Hunt's avatar
Evan Hunt committed
559
			new_node->node_num[ISC_RADIX_FAMILY(prefix)] = next;
560
		}
Evan Hunt's avatar
Evan Hunt committed
561
		memset(new_node->data, 0, sizeof(new_node->data));
Mark Andrews's avatar
Mark Andrews committed
562
	}
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602

	if (node->bit == differ_bit) {
		INSIST(glue == NULL);
		new_node->parent = node;
		if (node->bit < radix->maxbits &&
		    BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
		{
			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 &&
		    BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) {
			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
603
		for (i = 0; i < RADIX_FAMILIES; i++) {
Evan Hunt's avatar
Evan Hunt committed
604
605
606
			glue->data[i] = NULL;
			glue->node_num[i] = -1;
		}
607
608
		radix->num_active_node++;
		if (differ_bit < radix->maxbits &&
609
		    BIT_TEST(addr[differ_bit>>3], 0x80 >> (differ_bit & 07))) {
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
			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
isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) {
	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
643
		 * make sure there is a prefix associated with it!
644
		 */
Automatic Updater's avatar
Automatic Updater committed
645
		if (node->prefix != NULL)
646
			_deref_prefix(node->prefix);
647
648

		node->prefix = NULL;
Evan Hunt's avatar
Evan Hunt committed
649
		memset(node->data, 0, sizeof(node->data));
650
651
652
653
654
		return;
	}

	if (node->r == NULL && node->l == NULL) {
		parent = node->parent;
655
		_deref_prefix(node->prefix);
656
657
658
659

		if (parent == NULL) {
			INSIST(radix->head == node);
			radix->head = NULL;
660
661
			isc_mem_put(radix->mctx, node, sizeof(*node));
			radix->num_active_node--;
662
663
664
665
666
667
668
669
670
671
672
673
			return;
		}

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

674
675
676
		isc_mem_put(radix->mctx, node, sizeof(*node));
		radix->num_active_node--;

677
678
679
680
681
682
683
684
685
686
687
688
689
		if (parent->prefix)
			return;

		/* 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;
		}
690

691
692
693
694
695
696
697
698
699
700
701
702
		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;
	}
703

704
705
706
	parent = node->parent;
	child->parent = parent;

707
	_deref_prefix(node->prefix);
708
709
710
711

	if (parent == NULL) {
		INSIST(radix->head == node);
		radix->head = child;
712
713
		isc_mem_put(radix->mctx, node, sizeof(*node));
		radix->num_active_node--;
714
715
716
		return;
	}

717
718
719
	isc_mem_put(radix->mctx, node, sizeof(*node));
	radix->num_active_node--;

720
721
722
723
724
725
726
727
728
729
730
731
732
733
	if (parent->r == node) {
		parent->r = child;
	} else {
		INSIST(parent->l == node);
		parent->l = child;
	}
}

/*
Local Variables:
c-basic-offset: 4
indent-tabs-mode: t
End:
*/