Function pctrie_lookup_le

freebsd/kern/subr_pctrie.c:596–707

* Look up the nearest entry at a position less than or equal to index, * assuming access is externally synchronized by a lock. */

 * assuming access is externally synchronized by a lock.
 */
uint64_t *
pctrie_lookup_le(struct pctrie *ptree, uint64_t index)
{
	struct pctrie_node *stack[PCTRIE_LIMIT];
	uint64_t inc;
	uint64_t *m;
	struct pctrie_node *child, *node;
#ifdef INVARIANTS
	int loops = 0;
#endif
	unsigned tos;
	int slot;

	node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
	if (node == NULL)
		return (NULL);
	else if (pctrie_isleaf(node)) {
		m = pctrie_toval(node);
		if (*m <= index)
			return (m);
		else
			return (NULL);
	}
	tos = 0;
	for (;;) {
		/*
		 * If the keys differ before the current bisection node,
		 * then the search key might rollback to the earliest
		 * available bisection node or to the largest key
		 * in the current node (if the owner is smaller than the
		 * search key).
		 */
		if (pctrie_keybarr(node, index)) {
			if (index > node->pn_owner) {
				index = node->pn_owner + PCTRIE_COUNT *
				    PCTRIE_UNITLEVEL(node->pn_clev);
			} else {
ascend:
				KASSERT(++loops < 1000,
				    ("pctrie_lookup_le: too many loops"));

				/*
				 * Pop nodes from the stack until either the
				 * stack is empty or a node that could have a
				 * matching descendant is found.
				 */
				do {
					if (tos == 0)
						return (NULL);
					node = stack[--tos];
				} while (pctrie_slot(index,
				    node->pn_clev) == 0);

				/*
				 * The following computation cannot overflow
				 * because index's slot at the current level
				 * is greater than 0.
				 */