Function pctrie_lookup_ge

freebsd/kern/subr_pctrie.c:481–590

* Look up the nearest entry at a position bigger 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_ge(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 smallest key
		 * in the current node (if the owner is greater than the
		 * search key).
		 */
		if (pctrie_keybarr(node, index)) {
			if (index > node->pn_owner) {
ascend:
				KASSERT(++loops < 1000,
				    ("pctrie_lookup_ge: 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) == (PCTRIE_COUNT - 1));

				/*
				 * The following computation cannot overflow
				 * because index's slot at the current level
				 * is less than PCTRIE_COUNT - 1.
				 */
				index = pctrie_trimkey(index,
				    node->pn_clev);
				index += PCTRIE_UNITLEVEL(node->pn_clev);