sys/kern/subr_pctrie.c

124 pctrie_slot(uint64_t index, uint16_t level)
127 	return ((index >> (level * PCTRIE_WIDTH)) & PCTRIE_MASK);
132 pctrie_trimkey(uint64_t index, uint16_t level)
136 	ret = index;
188 pctrie_addval(struct pctrie_node *node, uint64_t index, uint16_t clev,
193 	slot = pctrie_slot(index, clev);
281 	uint64_t index, newind;
288 	index = *val;
303 			if (*m == index)
305 				    __func__, (uintmax_t)index);
306 			clev = pctrie_keydiff(*m, index);
308 			    pctrie_trimkey(index, clev + 1), 2, clev);
312 			pctrie_addval(tmp, index, clev, val);
315 		} else if (pctrie_keybarr(node, index))
317 		slot = pctrie_slot(index, node->pn_clev);
320 			pctrie_addval(node, index, node->pn_clev, val);
333 	clev = pctrie_keydiff(newind, index);
335 	    pctrie_trimkey(index, clev + 1), 2, clev);
339 	pctrie_addval(tmp, index, clev, val);
347  * Returns the value stored at the index.  If the index is not present,
351 pctrie_lookup(struct pctrie *ptree, uint64_t index)
361 			if (*m == index)
365 		} else if (pctrie_keybarr(node, index))
367 		slot = pctrie_slot(index, node->pn_clev);
374  * Look up the nearest entry at a position bigger than or equal to index.
377 pctrie_lookup_ge(struct pctrie *ptree, uint64_t index)
393 		if (*m >= index)
407 		if (pctrie_keybarr(node, index)) {
408 			if (index > node->pn_owner) {
422 				} while (pctrie_slot(index,
427 				 * because index's slot at the current level
430 				index = pctrie_trimkey(index,
432 				index += PCTRIE_UNITLEVEL(node->pn_clev);
434 				index = node->pn_owner;
435 			KASSERT(!pctrie_keybarr(node, index),
438 		slot = pctrie_slot(index, node->pn_clev);
442 			if (*m >= index)
453 			index = pctrie_trimkey(index, node->pn_clev);
455 				index += inc;
460 					if (*m >= index)
485  * Look up the nearest entry at a position less than or equal to index.
488 pctrie_lookup_le(struct pctrie *ptree, uint64_t index)
504 		if (*m <= index)
518 		if (pctrie_keybarr(node, index)) {
519 			if (index > node->pn_owner) {
520 				index = node->pn_owner + PCTRIE_COUNT *
536 				} while (pctrie_slot(index,
541 				 * because index's slot at the current level
544 				index = pctrie_trimkey(index,
547 			index--;
548 			KASSERT(!pctrie_keybarr(node, index),
551 		slot = pctrie_slot(index, node->pn_clev);
555 			if (*m <= index)
566 			index |= inc - 1;
568 				index -= inc;
573 					if (*m <= index)
598  * Remove the specified index from the tree.
602 pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn)
611 		if (*m != index)
620 		slot = pctrie_slot(index, node->pn_clev);
623 			if (*m != index)
637 				slot = pctrie_slot(index, parent->pn_clev);