Lines Matching full:index
88 * Map index to an array position for the children of node,
91 pctrie_slot(struct pctrie_node *node, uint64_t index)
93 return ((index >> node->pn_clev) & (PCTRIE_COUNT - 1));
97 * Returns true if index does not belong to the specified node. Otherwise,
101 pctrie_keybarr(struct pctrie_node *node, uint64_t index, int *slot)
103 index = (index - node->pn_owner) >> node->pn_clev;
104 if (index >= PCTRIE_COUNT)
106 *slot = index;
228 pctrie_addnode(struct pctrie_node *node, uint64_t index,
233 slot = pctrie_slot(node, index);
290 uint64_t index;
294 index = *val;
309 pctrie_addnode(parent, index,
313 if (*pctrie_toval(node) == index) {
319 if (pctrie_keybarr(node, index, &slot))
344 if (*pctrie_toval(node) < index)
347 if (*pctrie_toval(node) > index)
428 uint64_t index, newind;
447 index = *val;
454 * compute the least index of this subtrie.
460 parent->pn_clev = rounddown(ilog2(index ^ newind), PCTRIE_WIDTH);
462 parent->pn_owner = index & -(parent->pn_owner << parent->pn_clev);
466 pctrie_addnode(parent, index, pctrie_toleaf(val), PCTRIE_UNSERIALIZED);
474 * the index; otherwise NULL.
477 pctrie_match_value(struct pctrie_node *node, uint64_t index)
482 *m != index)
488 * Returns the value stored at the index. If the index is not present,
492 _pctrie_lookup(struct pctrie *ptree, uint64_t index, smr_t smr,
499 /* Seek a node that matches index. */
500 while (!pctrie_isleaf(node) && !pctrie_keybarr(node, index, &slot))
502 return (pctrie_match_value(node, index));
506 * Returns the value stored at the index, assuming access is externally
509 * If the index is not present, NULL is returned.
512 pctrie_lookup(struct pctrie *ptree, uint64_t index)
514 return (_pctrie_lookup(ptree, index, NULL, PCTRIE_LOCKED));
518 * Returns the value stored at the index without requiring an external lock.
520 * If the index is not present, NULL is returned.
523 pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t index, smr_t smr)
528 res = _pctrie_lookup(ptree, index, smr, PCTRIE_SMR);
534 * Returns the last node examined in the search for the index, and updates the
538 _pctrie_iter_lookup_node(struct pctrie_iter *it, uint64_t index, smr_t smr,
546 * search for a value matching 'index'.
552 if (!pctrie_keybarr(node, index, &slot)) {
562 /* Seek a node that matches index. */
563 while (!pctrie_isleaf(node) && !pctrie_keybarr(node, index, &slot)) {
573 * Returns the value stored at a given index value, possibly NULL.
576 _pctrie_iter_lookup(struct pctrie_iter *it, uint64_t index, smr_t smr,
581 it->index = index;
582 node = _pctrie_iter_lookup_node(it, index, smr, access);
583 return (pctrie_match_value(node, index));
587 * Returns the value stored at a given index value, possibly NULL.
590 pctrie_iter_lookup(struct pctrie_iter *it, uint64_t index)
592 return (_pctrie_iter_lookup(it, index, NULL, PCTRIE_LOCKED));
605 it->index = *val;
612 pctrie_addnode(it->path[it->top - 1], it->index,
616 if (__predict_false(pctrie_match_value(node, it->index) != NULL))
618 (uintmax_t)it->index);
628 return (&node->pn_child[pctrie_slot(node, it->index)]);
632 * Returns the value stored at a fixed offset from the current index value,
639 uint64_t index = it->index + stride;
642 if ((stride > 0) != (index > it->index))
645 if ((index < it->limit) != (it->index < it->limit))
648 return (_pctrie_iter_lookup(it, index, smr, access));
652 * Returns the value stored at a fixed offset from the current index value,
662 * Returns the value stored at one more than the current index value, possibly
672 * Returns the value stored at one less than the current index value, possibly
682 * Returns the value with the least index that is greater than or equal to the
683 * specified index, or NULL if there are no such values.
688 pctrie_lookup_ge_node(struct pctrie_node *node, uint64_t index)
700 * index resides. (The node's popmap makes it fast and easy to
702 * yield a value that is greater than or equal to the specified index,
710 if ((m = pctrie_toval(node)) != NULL && *m >= index)
714 if (pctrie_keybarr(node, index, &slot)) {
716 * If all values in this subtree are > index, then the
719 if (node->pn_owner > index)
726 * values < index, check popmap to see if a next bigger step, to
727 * a subtree of all pages with values > index, is available. If
738 * included some values > index, if there was such a place.
745 * last time. In that subtree, all values > index.
747 slot = pctrie_slot(succ, index) + 1;
757 * Find the value in the subtree rooted at "succ" with the least index.
770 pctrie_lookup_ge(struct pctrie *ptree, uint64_t index)
773 pctrie_root_load(ptree, NULL, PCTRIE_LOCKED), index));
777 pctrie_subtree_lookup_gt(struct pctrie_node *node, uint64_t index)
779 if (node == NULL || index + 1 == 0)
781 return (pctrie_lookup_ge_node(node, index + 1));
785 * Find first leaf >= index, and fill iter with the path to the parent of that
789 pctrie_iter_lookup_ge(struct pctrie_iter *it, uint64_t index)
795 /* Seek a node that matches index. */
796 node = _pctrie_iter_lookup_node(it, index, NULL, PCTRIE_LOCKED);
800 * < index, back up to find a subtrie with the least value > index.
802 if (node == PCTRIE_NULL || *pctrie_toval(node) < index) {
803 /* Climb the path to find a node with a descendant > index. */
806 slot = pctrie_slot(node, index) + 1;
814 /* Step to the least child with a descendant > index. */
833 it->index = *m;
844 uint64_t index = it->index + jump;
847 if ((jump > 0) != (index > it->index))
849 if (it->limit != 0 && index >= it->limit)
851 return (pctrie_iter_lookup_ge(it, index));
856 pctrie_subtree_lookup_gt_assert(struct pctrie_node *node, uint64_t index,
861 if (index + 1 == 0)
864 expected = pctrie_lookup_ge(ptree, index + 1);
867 "ptree %p, index %ju, subtree %p, found %p, expected %p", ptree,
868 (uintmax_t)index, node, res, expected));
873 * Returns the value with the greatest index that is less than or equal to the
874 * specified index, or NULL if there are no such values.
879 pctrie_lookup_le_node(struct pctrie_node *node, uint64_t index)
891 if ((m = pctrie_toval(node)) != NULL && *m <= index)
895 if (pctrie_keybarr(node, index, &slot)) {
896 if (node->pn_owner < index)
908 slot = pctrie_slot(pred, index);
927 pctrie_lookup_le(struct pctrie *ptree, uint64_t index)
930 pctrie_root_load(ptree, NULL, PCTRIE_LOCKED), index));
934 pctrie_subtree_lookup_lt(struct pctrie_node *node, uint64_t index)
936 if (node == NULL || index == 0)
938 return (pctrie_lookup_le_node(node, index - 1));
942 * Find first leaf <= index, and fill iter with the path to the parent of that
946 pctrie_iter_lookup_le(struct pctrie_iter *it, uint64_t index)
952 /* Seek a node that matches index. */
953 node = _pctrie_iter_lookup_node(it, index, NULL, PCTRIE_LOCKED);
957 * > index, back up to find a subtrie with the greatest value < index.
959 if (node == PCTRIE_NULL || *pctrie_toval(node) > index) {
960 /* Climb the path to find a node with a descendant < index. */
963 slot = pctrie_slot(node, index);
971 /* Step to the greatest child with a descendant < index. */
991 it->index = *m;
1002 uint64_t index = it->index - jump;
1005 if ((jump > 0) != (index < it->index))
1007 if (it->limit != 0 && index <= it->limit)
1009 return (pctrie_iter_lookup_le(it, index));
1014 pctrie_subtree_lookup_lt_assert(struct pctrie_node *node, uint64_t index,
1019 if (index == 0)
1022 expected = pctrie_lookup_le(ptree, index - 1);
1025 "ptree %p, index %ju, subtree %p, found %p, expected %p", ptree,
1026 (uintmax_t)index, node, res, expected));
1031 pctrie_remove(struct pctrie *ptree, uint64_t index, struct pctrie_node *parent,
1042 slot = pctrie_slot(node, index);
1058 slot = pctrie_slot(parent, index);
1074 * Remove the specified index from the tree, and return the value stored at
1075 * that index. If the index is not present, return NULL.
1078 pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
1091 slot = pctrie_slot(node, index);
1095 m = pctrie_match_value(child, index);
1097 pctrie_remove(ptree, index, parent, node, freenode);
1117 slot = pctrie_slot(node, it->index);
1124 m = pctrie_match_value(child, it->index);
1126 pctrie_remove(it->ptree, it->index, parent, node, freenode);
1147 slot = pctrie_slot(node, it->index);
1259 * Panics if there is not an old value in the trie at the new value's index.
1266 uint64_t index;
1270 index = *newval;
1275 if ((m = pctrie_toval(node)) != NULL && *m == index) {
1287 if (pctrie_keybarr(node, index, &slot))