FreeBSD/sys/kern/subr_pctrie.c
/*
 * Remove the specified index from the tree.
 * Panics if the key is not present.
 */
Remove the specified index from the tree.
Panics if the key is not present.
Remove the specified index from the tree . Panics if the key is not present .
void
pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn)
{
	struct pctrie_node *node, *parent;
	uint64_t *m;
	int i, slot;
	node = pctrie_getroot(ptree);
	if (pctrie_isleaf(node)) {
		m = pctrie_toval(node);
		if (*m != index)
			panic("%s: invalid key found", __func__);
		pctrie_setroot(ptree, NULL);
		return;
	}
	parent = NULL;
	for (;;) {
		if (node == NULL)
			panic("pctrie_remove: impossible to locate the key");
		slot = pctrie_slot(index, node->pn_clev);
		if (pctrie_isleaf(node->pn_child[slot])) {
			m = pctrie_toval(node->pn_child[slot]);
			if (*m != index)
				panic("%s: invalid key found", __func__);
			node->pn_child[slot] = NULL;
			node->pn_count--;
			if (node->pn_count > 1)
				break;
			for (i = 0; i < PCTRIE_COUNT; i++)
				if (node->pn_child[i] != NULL)
					break;
			KASSERT(i != PCTRIE_COUNT,
			    ("%s: invalid node configuration", __func__));
			if (parent == NULL)
				pctrie_setroot(ptree, node->pn_child[i]);
			else {
				slot = pctrie_slot(index, parent->pn_clev);
				KASSERT(parent->pn_child[slot] == node,
				    ("%s: invalid child value", __func__));
				parent->pn_child[slot] = node->pn_child[i];
			}
			node->pn_count--;
			node->pn_child[i] = NULL;
			pctrie_node_put(ptree, node, freefn);
			break;
		}
		parent = node;
		node = node->pn_child[slot];
	}
}
void pctrie_remove ( struct pctrie * ptree , uint64_t index , pctrie_free_t freefn ) { struct pctrie_node * node , * parent ; uint64_t * m ; int i , slot ; node = pctrie_getroot ( ptree ) ; if ( pctrie_isleaf ( node ) ) { m = pctrie_toval ( node ) ; if ( * m != index ) panic ( " " , __func__ ) ; pctrie_setroot ( ptree , NULL ) ; return ; } parent = NULL ; for ( ; ; ) { if ( node == NULL ) panic ( " " ) ; slot = pctrie_slot ( index , node -> pn_clev ) ; if ( pctrie_isleaf ( node -> pn_child [ slot ] ) ) { m = pctrie_toval ( node -> pn_child [ slot ] ) ; if ( * m != index ) panic ( " " , __func__ ) ; node -> pn_child [ slot ] = NULL ; node -> pn_count -- ; if ( node -> pn_count > 1 ) break ; for ( i = 0 ; i < PCTRIE_COUNT ; i ++ ) if ( node -> pn_child [ i ] != NULL ) break ; KASSERT ( i != PCTRIE_COUNT , ( " " , __func__ ) ) ; if ( parent == NULL ) pctrie_setroot ( ptree , node -> pn_child [ i ] ) ; else { slot = pctrie_slot ( index , parent -> pn_clev ) ; KASSERT ( parent -> pn_child [ slot ] == node , ( " " , __func__ ) ) ; parent -> pn_child [ slot ] = node -> pn_child [ i ] ; } node -> pn_count -- ; node -> pn_child [ i ] = NULL ; pctrie_node_put ( ptree , node , freefn ) ; break ; } parent = node ; node = node -> pn_child [ slot ] ; } }
Remove the specified index from the tree.
Remove the specified index from the tree .