Function pctrie_remove

freebsd/kern/subr_pctrie.c:713–774

* Remove the specified index from the tree. * Panics if the key is not present. */

 * 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, *tmp;
	uint64_t *m;
	int i, slot;

	node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
	if (pctrie_isleaf(node)) {
		m = pctrie_toval(node);
		if (*m != index)
			panic("%s: invalid key found", __func__);
		pctrie_root_store(ptree, NULL, PCTRIE_LOCKED);
		return;
	}
	parent = NULL;
	for (;;) {
		if (node == NULL)
			panic("pctrie_remove: impossible to locate the key");
		slot = pctrie_slot(index, node->pn_clev);
		tmp = pctrie_node_load(&node->pn_child[slot], NULL,
		    PCTRIE_LOCKED);
		if (pctrie_isleaf(tmp)) {
			m = pctrie_toval(tmp);
			if (*m != index)
				panic("%s: invalid key found", __func__);
			pctrie_node_store(&node->pn_child[slot], NULL,
			    PCTRIE_LOCKED);
			node->pn_count--;
			if (node->pn_count > 1)
				break;
			for (i = 0; i < PCTRIE_COUNT; i++) {
				tmp = pctrie_node_load(&node->pn_child[i],
				    NULL, PCTRIE_LOCKED);
				if (tmp != NULL)
					break;
			}
			KASSERT(i != PCTRIE_COUNT,
			    ("%s: invalid node configuration", __func__));
			if (parent == NULL)
				pctrie_root_store(ptree, tmp, PCTRIE_LOCKED);
			else {
				slot = pctrie_slot(index, parent->pn_clev);
				KASSERT(pctrie_node_load(
					&parent->pn_child[slot], NULL,
					PCTRIE_LOCKED) == node,
				    ("%s: invalid child value", __func__));
				pctrie_node_store(&parent->pn_child[slot], tmp,
				    PCTRIE_LOCKED);
			}
			/*
			 * The child is still valid and we can not zero the
			 * pointer until all SMR references are gone.
			 */
			node->pn_count--;
			pctrie_node_put(ptree, node, freefn, i);
			break;
		}