Cross Reference: /bind-9.6-ESV-R11/lib/isc/radix.c

Lines Matching defs:radix
21  * Id: radix.c,v 1.10.2.1 1999/11/29 05:16:24 masaki Exp
30 #include <isc/radix.h>
46 _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func);
141 	isc_radix_tree_t *radix;
145 	radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t));
146 	if (radix == NULL)
149 	radix->mctx = mctx;
150 	radix->maxbits = maxbits;
151 	radix->head = NULL;
152 	radix->num_active_node = 0;
153 	radix->num_added_node = 0;
155 	radix->magic = RADIX_TREE_MAGIC;
156 	*target = radix;
166 _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
168 	REQUIRE(radix != NULL);
170 	if (radix->head != NULL) {
174 		isc_radix_node_t *Xrn = radix->head;
181 				_deref_prefix(radix->mctx, Xrn->prefix);
190 			isc_mem_put(radix->mctx, Xrn, sizeof(*Xrn));
191 			radix->num_active_node--;
207 	RUNTIME_CHECK(radix->num_active_node == 0);
212 isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func)
214 	REQUIRE(radix != NULL);
215 	_clear_radix(radix, func);
216 	isc_mem_put(radix->mctx, radix, sizeof(*radix));
224 isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func)
230 	RADIX_WALK(radix->head, node) {
237 isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target,
247 	REQUIRE(radix != NULL);
250 	RUNTIME_CHECK(prefix->bitlen <= radix->maxbits);
254 	if (radix->head == NULL) {
258 	node = radix->head;
302 isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target,
311 	REQUIRE(radix != NULL);
314 	RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits);
324 	if (radix->head == NULL) {
325 		node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
331 		result = _ref_prefix(radix->mctx, &node->prefix, prefix);
333 			isc_mem_put(radix->mctx, node,
342 			 * node from an existing radix tree.  To keep
349 				node->node_num[0] = radix->num_added_node +
352 				node->node_num[1] = radix->num_added_node +
360 					++radix->num_added_node;
363 					++radix->num_added_node;
368 		radix->head = node;
369 		radix->num_active_node++;
375 	node = radix->head;
378 		if (node->bit < radix->maxbits &&
432 						radix->num_added_node +
439 						radix->num_added_node +
446 					int next = radix->num_added_node + 1;
449 						radix->num_added_node = next;
453 						radix->num_added_node = next;
458 						   = ++radix->num_added_node;
465 				_ref_prefix(radix->mctx, &node->prefix, prefix);
474 				node->node_num[0] = radix->num_added_node +
479 				node->node_num[1] = radix->num_added_node +
487 					++radix->num_added_node;
490 					++radix->num_added_node;
497 	new_node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
501 		glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
503 			isc_mem_put(radix->mctx, new_node,
510 	result = _ref_prefix(radix->mctx, &new_node->prefix, prefix);
512 		isc_mem_put(radix->mctx, new_node, sizeof(isc_radix_node_t));
514 			isc_mem_put(radix->mctx, glue,
521 	radix->num_active_node++;
526 			new_node->node_num[0] = radix->num_added_node +
529 			new_node->node_num[1] = radix->num_added_node +
537 				++radix->num_added_node;
540 				++radix->num_added_node;
549 		if (node->bit < radix->maxbits &&
564 		if (bitlen < radix->maxbits &&
572 			INSIST(radix->head == node);
573 			radix->head = new_node;
587 		radix->num_active_node++;
588 		if (differ_bit < radix->maxbits &&
599 			INSIST(radix->head == node);
600 			radix->head = glue;
614 isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) {
617 	REQUIRE(radix != NULL);
626 			_deref_prefix(radix->mctx, node->prefix);
635 		_deref_prefix(radix->mctx, node->prefix);
636 		isc_mem_put(radix->mctx, node, sizeof(*node));
637 		radix->num_active_node--;
640 			INSIST(radix->head == node);
641 			radix->head = NULL;
660 			INSIST(radix->head == parent);
661 			radix->head = child;
669 		isc_mem_put(radix->mctx, parent, sizeof(*parent));
670 		radix->num_active_node--;
683 	_deref_prefix(radix->mctx, node->prefix);
684 	isc_mem_put(radix->mctx, node, sizeof(*node));
685 	radix->num_active_node--;
688 		INSIST(radix->head == node);
689 		radix->head = child;