89  * Map index to an array position for the children of node,
92 pctrie_slot(struct pctrie_node *node, uint64_t index)  in pctrie_slot()  argument
94 	return ((index >> node->pn_clev) & (PCTRIE_COUNT - 1));  in pctrie_slot()
98  * Returns true if index does not belong to the specified node.  Otherwise,
102 pctrie_keybarr(struct pctrie_node *node, uint64_t index, int *slot)  in pctrie_keybarr()  argument
104 	index = (index - node->pn_owner) >> node->pn_clev;  in pctrie_keybarr()
105 	if (index >= PCTRIE_COUNT)  in pctrie_keybarr()
107 	*slot = index;  in pctrie_keybarr()
171 pctrie_child(struct pctrie *ptree, struct pctrie_node *node, uint64_t index)  in pctrie_child()  argument
174 	    &node->pn_child[pctrie_slot(node, index)]);  in pctrie_child()
235 pctrie_addnode(struct pctrie_node *node, uint64_t index,  in pctrie_addnode()  argument
240 	slot = pctrie_slot(node, index);  in pctrie_addnode()
282 	uint64_t index;  in pctrie_insert_lookup_compound()  local
286 	index = *val;  in pctrie_insert_lookup_compound()
301 					pctrie_addnode(parent, index,  in pctrie_insert_lookup_compound()
306 			if (*pctrie_toval(node) == index) {  in pctrie_insert_lookup_compound()
313 		if (pctrie_keybarr(node, index, &slot))  in pctrie_insert_lookup_compound()
372 	uint64_t index, newind;  in pctrie_insert_node()  local
391 	index = *val;  in pctrie_insert_node()
401 	 * compute the least index of this subtrie.  in pctrie_insert_node()
407 	child->pn_clev = rounddown(ilog2(index ^ newind), PCTRIE_WIDTH);  in pctrie_insert_node()
409 	child->pn_owner = index & -(child->pn_owner << child->pn_clev);  in pctrie_insert_node()
413 	pctrie_addnode(child, index, pctrie_toleaf(val), PCTRIE_UNSERIALIZED);  in pctrie_insert_node()
421  * the index; otherwise NULL.
424 pctrie_match_value(struct pctrie_node *node, uint64_t index)  in pctrie_match_value()  argument
429 	    *m != index)  in pctrie_match_value()
435  * Returns the value stored at the index.  If the index is not present,
439 _pctrie_lookup(struct pctrie *ptree, uint64_t index, smr_t smr,  in _pctrie_lookup()  argument
446 	/* Seek a node that matches index. */  in _pctrie_lookup()
447 	while (!pctrie_isleaf(node) && !pctrie_keybarr(node, index, &slot))  in _pctrie_lookup()
449 	return (pctrie_match_value(node, index));  in _pctrie_lookup()
453  * Returns the value stored at the index, assuming access is externally
456  * If the index is not present, NULL is returned.
459 pctrie_lookup(struct pctrie *ptree, uint64_t index)  in pctrie_lookup()  argument
461 	return (_pctrie_lookup(ptree, index, NULL, PCTRIE_LOCKED));  in pctrie_lookup()
465  * Returns the value stored at the index without requiring an external lock.
467  * If the index is not present, NULL is returned.
470 pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t index, smr_t smr)  in pctrie_lookup_unlocked()  argument
475 	res = _pctrie_lookup(ptree, index, smr, PCTRIE_SMR);  in pctrie_lookup_unlocked()
481  * Returns the last node examined in the search for the index, and sets the
486     uint64_t index, struct pctrie_node **parent_out,  in _pctrie_lookup_node()  argument
494 	 * search for a value matching 'index'.  in _pctrie_lookup_node()
499 		if (!pctrie_keybarr(node, index, &slot))  in _pctrie_lookup_node()
512 	/* Seek a node that matches index. */  in _pctrie_lookup_node()
513 	while (!pctrie_isleaf(node) && !pctrie_keybarr(node, index, &slot)) {  in _pctrie_lookup_node()
523  * Returns the value stored at a given index value, possibly NULL.
526 _pctrie_iter_lookup(struct pctrie_iter *it, uint64_t index, smr_t smr,  in _pctrie_iter_lookup()  argument
531 	it->index = index;  in _pctrie_iter_lookup()
532 	node = _pctrie_lookup_node(it->ptree, it->node, index, &it->node,  in _pctrie_iter_lookup()
534 	return (pctrie_match_value(node, index));  in _pctrie_iter_lookup()
538  * Returns the value stored at a given index value, possibly NULL.
541 pctrie_iter_lookup(struct pctrie_iter *it, uint64_t index)  in pctrie_iter_lookup()  argument
543 	return (_pctrie_iter_lookup(it, index, NULL, PCTRIE_LOCKED));  in pctrie_iter_lookup()
556 	it->index = *val;  in pctrie_iter_insert_lookup()
564 			pctrie_addnode(it->node, it->index,  in pctrie_iter_insert_lookup()
568 	if (__predict_false(pctrie_match_value(node, it->index) != NULL))  in pctrie_iter_insert_lookup()
570 		    (uintmax_t)it->index);  in pctrie_iter_insert_lookup()
577 	return (pctrie_child(it->ptree, it->node, it->index));  in pctrie_iter_insert_lookup()
581  * Returns the value stored at a fixed offset from the current index value,
588 	uint64_t index = it->index + stride;  in _pctrie_iter_stride()  local
591 	if ((stride > 0) != (index > it->index))  in _pctrie_iter_stride()
594 	if ((index < it->limit) != (it->index < it->limit))  in _pctrie_iter_stride()
597 	return (_pctrie_iter_lookup(it, index, smr, access));  in _pctrie_iter_stride()
601  * Returns the value stored at a fixed offset from the current index value,
611  * Returns the value stored at one more than the current index value, possibly
621  * Returns the value stored at one less than the current index value, possibly
631  * Find first leaf >= index, and fill iter with the path to the parent of that
636     uint64_t index, struct pctrie_node **parent_out, uint64_t limit)  in _pctrie_lookup_ge()  argument
642 	/* Seek a node that matches index. */  in _pctrie_lookup_ge()
643 	node = _pctrie_lookup_node(ptree, node, index, &parent,  in _pctrie_lookup_ge()
648 	 * < index, back up to find a subtrie with the least value > index.  in _pctrie_lookup_ge()
650 	if (node == PCTRIE_NULL || *pctrie_toval(node) < index) {  in _pctrie_lookup_ge()
651 		/* Climb the path to find a node with a descendant > index. */  in _pctrie_lookup_ge()
653 			slot = pctrie_slot(node, index) + 1;  in _pctrie_lookup_ge()
663 		/* Step to the least child with a descendant > index. */  in _pctrie_lookup_ge()
687 pctrie_lookup_ge(struct pctrie *ptree, uint64_t index)  in pctrie_lookup_ge()  argument
689 	return (_pctrie_lookup_ge(ptree, NULL, index, NULL, 0));  in pctrie_lookup_ge()
693  * Find first leaf >= index, and fill iter with the path to the parent of that
697 pctrie_iter_lookup_ge(struct pctrie_iter *it, uint64_t index)  in pctrie_iter_lookup_ge()  argument
701 	m = _pctrie_lookup_ge(it->ptree, it->node, index, &it->node, it->limit);  in pctrie_iter_lookup_ge()
703 		it->index = *m;  in pctrie_iter_lookup_ge()
714 	uint64_t index = it->index + jump;  in pctrie_iter_jump_ge()  local
717 	if ((jump > 0) != (index > it->index))  in pctrie_iter_jump_ge()
719 	if (it->limit != 0 && index >= it->limit)  in pctrie_iter_jump_ge()
721 	return (pctrie_iter_lookup_ge(it, index));  in pctrie_iter_jump_ge()
725  * Find first leaf <= index, and fill iter with the path to the parent of that
730     uint64_t index, struct pctrie_node **parent_out, uint64_t limit)  in _pctrie_lookup_le()  argument
736 	/* Seek a node that matches index. */  in _pctrie_lookup_le()
737 	node = _pctrie_lookup_node(ptree, node, index, &parent, NULL,  in _pctrie_lookup_le()
742 	 * > index, back up to find a subtrie with the greatest value < index.  in _pctrie_lookup_le()
744 	if (node == PCTRIE_NULL || *pctrie_toval(node) > index) {  in _pctrie_lookup_le()
745 		/* Climb the path to find a node with a descendant < index. */  in _pctrie_lookup_le()
747 			slot = pctrie_slot(node, index);  in _pctrie_lookup_le()
757 		/* Step to the greatest child with a descendant < index. */  in _pctrie_lookup_le()
782 pctrie_lookup_le(struct pctrie *ptree, uint64_t index)  in pctrie_lookup_le()  argument
784 	return (_pctrie_lookup_le(ptree, NULL, index, NULL, 0));  in pctrie_lookup_le()
789     uint64_t index)  in pctrie_subtree_lookup_lt()  argument
791 	if (index == 0)  in pctrie_subtree_lookup_lt()
793 	return (_pctrie_lookup_le(ptree, node, index - 1, NULL, 0));  in pctrie_subtree_lookup_lt()
797  * Find first leaf <= index, and fill iter with the path to the parent of that
801 pctrie_iter_lookup_le(struct pctrie_iter *it, uint64_t index)  in pctrie_iter_lookup_le()  argument
805 	m = _pctrie_lookup_le(it->ptree, it->node, index, &it->node, it->limit);  in pctrie_iter_lookup_le()
807 		it->index = *m;  in pctrie_iter_lookup_le()
818 	uint64_t index = it->index - jump;  in pctrie_iter_jump_le()  local
821 	if ((jump > 0) != (index < it->index))  in pctrie_iter_jump_le()
823 	if (it->limit != 0 && index <= it->limit)  in pctrie_iter_jump_le()
825 	return (pctrie_iter_lookup_le(it, index));  in pctrie_iter_jump_le()
829  * Remove the non-NULL child identified by 'index' from the set of children of
834 pctrie_remove(struct pctrie *ptree, struct pctrie_node *node, uint64_t index,  in pctrie_remove()  argument
842 	parentp = pctrie_child(ptree, node, index);  in pctrie_remove()
847 	slot = pctrie_slot(node, index);  in pctrie_remove()
866 	parentp = pctrie_child(ptree, node, index);  in pctrie_remove()
871  * Remove the specified index from the tree, and return the value stored at
872  * that index.  If the index is not present, return NULL.
875 pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,  in pctrie_remove_lookup()  argument
886 		slot = pctrie_slot(node, index);  in pctrie_remove_lookup()
890 	if ((m = pctrie_match_value(child, index)) != NULL)  in pctrie_remove_lookup()
891 		pctrie_remove(ptree, node, index, freenode);  in pctrie_remove_lookup()
905 	    it->ptree, it->node, it->index), NULL, PCTRIE_LOCKED), it->index),  in pctrie_iter_remove()
907 	    (uintmax_t)it->index));  in pctrie_iter_remove()
908 	pctrie_remove(it->ptree, it->node, it->index, freenode);  in pctrie_iter_remove()
922 	node = pctrie_node_load(pctrie_child(it->ptree, it->node, it->index),  in pctrie_iter_value()
1024  * Panics if there is not an old value in the trie at the new value's index.
1031 	uint64_t index;  in pctrie_replace()  local
1035 	index = *newval;  in pctrie_replace()
1040 			if ((m = pctrie_toval(node)) != NULL && *m == index) {  in pctrie_replace()
1052 		if (pctrie_keybarr(node, index, &slot))  in pctrie_replace()