Home | History | Annotate | Download | only in isc

Lines Matching defs:radix

1 /*	$NetBSD: radix.c,v 1.1 2024/02/18 20:57:50 christos Exp $	*/
18  * Id: radix.c,v 1.10.2.1 1999/11/29 05:16:24 masaki Exp
25 #include <isc/radix.h>
45 _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func);
138 	isc_radix_tree_t *radix;
142 	radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t));
144 	radix->mctx = NULL;
145 	isc_mem_attach(mctx, &radix->mctx);
146 	radix->maxbits = maxbits;
147 	radix->head = NULL;
148 	radix->num_active_node = 0;
149 	radix->num_added_node = 0;
151 	radix->magic = RADIX_TREE_MAGIC;
152 	*target = radix;
162 _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
163 	REQUIRE(radix != NULL);
165 	if (radix->head != NULL) {
168 		isc_radix_node_t *Xrn = radix->head;
184 			isc_mem_put(radix->mctx, Xrn, sizeof(*Xrn));
185 			radix->num_active_node--;
201 	RUNTIME_CHECK(radix->num_active_node == 0);
205 isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
206 	REQUIRE(radix != NULL);
207 	_clear_radix(radix, func);
208 	isc_mem_putanddetach(&radix->mctx, radix, sizeof(*radix));
215 isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func) {
220 	RADIX_WALK(radix->head, node) { func(node->prefix, node->data); }
225 isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target,
233 	REQUIRE(radix != NULL);
236 	RUNTIME_CHECK(prefix->bitlen <= radix->maxbits);
240 	node = radix->head;
296 isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target,
304 	REQUIRE(radix != NULL);
307 	RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits);
318 	if (radix->head == NULL) {
319 		node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
325 		result = _ref_prefix(radix->mctx, &node->prefix, prefix);
327 			isc_mem_put(radix->mctx, node,
336 			 * node from an existing radix tree.  To keep
345 						radix->num_added_node +
351 			int next = ++radix->num_added_node;
363 		radix->head = node;
364 		radix->num_active_node++;
370 	node = radix->head;
373 		if (node->bit < radix->maxbits &&
433 							radix->num_added_node +
441 					int next = radix->num_added_node + 1;
446 							radix->num_added_node =
454 							++radix->num_added_node;
461 			result = _ref_prefix(radix->mctx, &node->prefix,
474 				int cur = radix->num_added_node;
482 			int next = ++radix->num_added_node;
496 	new_node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
498 		glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
502 	result = _ref_prefix(radix->mctx, &new_node->prefix, prefix);
504 		isc_mem_put(radix->mctx, new_node, sizeof(isc_radix_node_t));
506 			isc_mem_put(radix->mctx, glue,
517 	radix->num_active_node++;
522 			int cur = radix->num_added_node;
530 		int next = ++radix->num_added_node;
545 		if (node->bit < radix->maxbits &&
560 		if (bitlen < radix->maxbits &&
569 			INSIST(radix->head == node);
570 			radix->head = new_node;
586 		radix->num_active_node++;
587 		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);
639 			INSIST(radix->head == node);
640 			radix->head = NULL;
641 			isc_mem_put(radix->mctx, node, sizeof(*node));
642 			radix->num_active_node--;
655 		isc_mem_put(radix->mctx, node, sizeof(*node));
656 		radix->num_active_node--;
664 			INSIST(radix->head == parent);
665 			radix->head = child;
674 		isc_mem_put(radix->mctx, parent, sizeof(*parent));
675 		radix->num_active_node--;
692 		INSIST(radix->head == node);
693 		radix->head = child;
694 		isc_mem_put(radix->mctx, node, sizeof(*node));
695 		radix->num_active_node--;
699 	isc_mem_put(radix->mctx, node, sizeof(*node));
700 	radix->num_active_node--;