Lines Matching full:node
84 smr_pctnode_t pn_parent; /* Parent node. */
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()
114 * Fetch a node pointer from a slot.
159 * Get the root node for a tree.
168 * Get the child of a node.
171 pctrie_child(struct pctrie *ptree, struct pctrie_node *node, uint64_t index) in pctrie_child() argument
173 return (node == NULL ? pctrie_root(ptree) : in pctrie_child()
174 &node->pn_child[pctrie_slot(node, index)]); in pctrie_child()
178 * Returns TRUE if the specified node is a leaf and FALSE otherwise.
181 pctrie_isleaf(struct pctrie_node *node) in pctrie_isleaf() argument
183 return (((uintptr_t)node & PCTRIE_ISLEAF) != 0); in pctrie_isleaf()
196 * Returns the associated val extracted from node.
199 pctrie_toval(struct pctrie_node *node) in pctrie_toval() argument
201 return ((uint64_t *)((uintptr_t)node & ~PCTRIE_FLAGS)); in pctrie_toval()
205 * Returns the associated pointer extracted from node and field offset.
208 pctrie_toptr(struct pctrie_node *node, int keyoff) in pctrie_toptr() argument
210 return ((void *)(((uintptr_t)node & ~PCTRIE_FLAGS) - keyoff)); in pctrie_toptr()
223 * Return the parent of 'node'.
226 pctrie_parent(struct pctrie_node *node) in pctrie_parent() argument
228 return (pctrie_node_load(&node->pn_parent, NULL, PCTRIE_UNSERIALIZED)); in pctrie_parent()
232 * Make 'child' a child of 'node'.
235 pctrie_addnode(struct pctrie_node *node, uint64_t index, in pctrie_addnode() argument
240 slot = pctrie_slot(node, index); in pctrie_addnode()
241 pctrie_node_store(&node->pn_child[slot], child, access); in pctrie_addnode()
242 node->pn_popmap ^= 1 << slot; in pctrie_addnode()
243 KASSERT((node->pn_popmap & (1 << slot)) != 0, in pctrie_addnode()
244 ("%s: bad popmap slot %d in node %p", __func__, slot, node)); in pctrie_addnode()
248 * pctrie node zone initializer.
253 struct pctrie_node *node; in pctrie_zone_init() local
255 node = mem; in pctrie_zone_init()
256 node->pn_popmap = 0; in pctrie_zone_init()
257 for (int i = 0; i < nitems(node->pn_child); i++) in pctrie_zone_init()
258 pctrie_node_store(&node->pn_child[i], PCTRIE_NULL, in pctrie_zone_init()
283 struct pctrie_node *node, *parent; in pctrie_insert_lookup_compound() local
292 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); in pctrie_insert_lookup_compound()
295 if (pctrie_isleaf(node)) { in pctrie_insert_lookup_compound()
296 if (node == PCTRIE_NULL) { in pctrie_insert_lookup_compound()
306 if (*pctrie_toval(node) == index) { in pctrie_insert_lookup_compound()
307 *found_out = pctrie_toval(node); in pctrie_insert_lookup_compound()
313 if (pctrie_keybarr(node, index, &slot)) in pctrie_insert_lookup_compound()
315 parent = node; in pctrie_insert_lookup_compound()
316 node = pctrie_node_load(&node->pn_child[slot], NULL, in pctrie_insert_lookup_compound()
321 * 'node' must be replaced in the tree with a new branch node, with in pctrie_insert_lookup_compound()
322 * children 'node' and 'val'. Return the place that points to 'node' in pctrie_insert_lookup_compound()
323 * now, and will point to to the new branching node later. in pctrie_insert_lookup_compound()
363 * Inserts newly allocated node 'child' into trie at location 'parentp', with
364 * parent 'parent' and two children, 'val' and whatever non-NULL node or leaf
371 struct pctrie_node *node; in pctrie_insert_node() local
387 * Recover the values of the two children of the new child node. If in pctrie_insert_node()
388 * 'node' is not a leaf, this stores into 'newind' the 'owner' field, in pctrie_insert_node()
389 * which must be first in the node. in pctrie_insert_node()
392 node = pctrie_node_load(parentp, NULL, PCTRIE_UNSERIALIZED); in pctrie_insert_node()
394 if (!pctrie_isleaf(node)) in pctrie_insert_node()
395 pctrie_setparent(node, child); in pctrie_insert_node()
396 newind = *pctrie_toval(node); in pctrie_insert_node()
414 pctrie_addnode(child, newind, node, PCTRIE_UNSERIALIZED); in pctrie_insert_node()
420 * Return the value associated with the node, if the node is a leaf that matches
424 pctrie_match_value(struct pctrie_node *node, uint64_t index) in pctrie_match_value() argument
428 if (!pctrie_isleaf(node) || (m = pctrie_toval(node)) == NULL || in pctrie_match_value()
442 struct pctrie_node *node; in _pctrie_lookup() local
445 node = pctrie_root_load(ptree, smr, access); in _pctrie_lookup()
446 /* Seek a node that matches index. */ in _pctrie_lookup()
447 while (!pctrie_isleaf(node) && !pctrie_keybarr(node, index, &slot)) in _pctrie_lookup()
448 node = pctrie_node_load(&node->pn_child[slot], smr, access); in _pctrie_lookup()
449 return (pctrie_match_value(node, index)); in _pctrie_lookup()
481 * Returns the last node examined in the search for the index, and sets the
482 * parent of that node.
485 _pctrie_lookup_node(struct pctrie *ptree, struct pctrie_node *node, in _pctrie_lookup_node() argument
493 * Climb the search path to find the lowest node from which to start the in _pctrie_lookup_node()
496 while (node != NULL) { in _pctrie_lookup_node()
497 KASSERT(!powerof2(node->pn_popmap), in _pctrie_lookup_node()
498 ("%s: freed node in iter path", __func__)); in _pctrie_lookup_node()
499 if (!pctrie_keybarr(node, index, &slot)) in _pctrie_lookup_node()
501 node = pctrie_parent(node); in _pctrie_lookup_node()
504 if (node == NULL) { in _pctrie_lookup_node()
506 node = pctrie_root_load(ptree, smr, access); in _pctrie_lookup_node()
508 parent = node; in _pctrie_lookup_node()
509 node = pctrie_node_load(&node->pn_child[slot], smr, access); 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()
514 parent = node; in _pctrie_lookup_node()
515 node = pctrie_node_load(&node->pn_child[slot], smr, access); in _pctrie_lookup_node()
519 return (node); in _pctrie_lookup_node()
529 struct pctrie_node *node; in _pctrie_iter_lookup() local
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()
548 * to indicate where a new node must be allocated to complete insertion.
554 struct pctrie_node *node; in pctrie_iter_insert_lookup() local
557 node = _pctrie_lookup_node(it->ptree, it->node, *val, &it->node, in pctrie_iter_insert_lookup()
559 if (node == PCTRIE_NULL) { in pctrie_iter_insert_lookup()
560 if (it->node == NULL) 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()
573 * 'node' must be replaced in the tree with a new branch node, with in pctrie_iter_insert_lookup()
574 * children 'node' and 'val'. Return the place that points to 'node' in pctrie_iter_insert_lookup()
575 * now, and will point to to the new branching node later. in pctrie_iter_insert_lookup()
577 return (pctrie_child(it->ptree, it->node, it->index)); in pctrie_iter_insert_lookup()
635 _pctrie_lookup_ge(struct pctrie *ptree, struct pctrie_node *node, 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()
647 * If no such node was found, and instead this path leads only to nodes 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()
652 for (node = parent; node != NULL; node = pctrie_parent(node)) { in _pctrie_lookup_ge()
653 slot = pctrie_slot(node, index) + 1; in _pctrie_lookup_ge()
654 if ((node->pn_popmap >> slot) != 0) in _pctrie_lookup_ge()
657 if (node == NULL) { in _pctrie_lookup_ge()
664 slot += ffs(node->pn_popmap >> slot) - 1; in _pctrie_lookup_ge()
665 parent = node; in _pctrie_lookup_ge()
666 node = pctrie_node_load(&node->pn_child[slot], NULL, in _pctrie_lookup_ge()
670 while (!pctrie_isleaf(node)) { in _pctrie_lookup_ge()
671 if (limit != 0 && node->pn_owner >= limit) in _pctrie_lookup_ge()
673 slot = ffs(node->pn_popmap) - 1; in _pctrie_lookup_ge()
674 parent = node; in _pctrie_lookup_ge()
675 node = pctrie_node_load(&node->pn_child[slot], NULL, in _pctrie_lookup_ge()
680 m = pctrie_toval(node); in _pctrie_lookup_ge()
701 m = _pctrie_lookup_ge(it->ptree, it->node, index, &it->node, it->limit); in pctrie_iter_lookup_ge()
729 _pctrie_lookup_le(struct pctrie *ptree, struct pctrie_node *node, 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()
741 * If no such node was found, and instead this path leads only to nodes 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()
746 for (node = parent; node != NULL; node = pctrie_parent(node)) { in _pctrie_lookup_le()
747 slot = pctrie_slot(node, index); in _pctrie_lookup_le()
748 if ((node->pn_popmap & ((1 << slot) - 1)) != 0) in _pctrie_lookup_le()
751 if (node == NULL) { in _pctrie_lookup_le()
758 slot = ilog2(node->pn_popmap & ((1 << slot) - 1)); in _pctrie_lookup_le()
759 parent = node; in _pctrie_lookup_le()
760 node = pctrie_node_load(&node->pn_child[slot], NULL, in _pctrie_lookup_le()
764 while (!pctrie_isleaf(node)) { in _pctrie_lookup_le()
765 if (limit != 0 && limit >= node->pn_owner + in _pctrie_lookup_le()
766 ((uint64_t)PCTRIE_COUNT << node->pn_clev) - 1) in _pctrie_lookup_le()
768 slot = ilog2(node->pn_popmap); in _pctrie_lookup_le()
769 parent = node; in _pctrie_lookup_le()
770 node = pctrie_node_load(&node->pn_child[slot], NULL, in _pctrie_lookup_le()
775 m = pctrie_toval(node); in _pctrie_lookup_le()
788 pctrie_subtree_lookup_lt(struct pctrie *ptree, struct pctrie_node *node, in pctrie_subtree_lookup_lt() argument
793 return (_pctrie_lookup_le(ptree, node, index - 1, NULL, 0)); in pctrie_subtree_lookup_lt()
805 m = _pctrie_lookup_le(it->ptree, it->node, index, &it->node, it->limit); in pctrie_iter_lookup_le()
830 * 'node'. If doing so causes 'node' to have only one child, purge it from the
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()
843 if (node == NULL) { in pctrie_remove()
847 slot = pctrie_slot(node, index); in pctrie_remove()
848 KASSERT((node->pn_popmap & (1 << slot)) != 0, in pctrie_remove()
849 ("%s: bad popmap slot %d in node %p", in pctrie_remove()
850 __func__, slot, node)); in pctrie_remove()
851 node->pn_popmap ^= 1 << slot; in pctrie_remove()
852 if (!powerof2(node->pn_popmap)) { in pctrie_remove()
857 KASSERT(node->pn_popmap != 0, ("%s: bad popmap all zeroes", __func__)); in pctrie_remove()
858 slot = ffs(node->pn_popmap) - 1; in pctrie_remove()
859 *freenode = node; in pctrie_remove()
860 child = pctrie_node_load(&node->pn_child[slot], NULL, PCTRIE_LOCKED); in pctrie_remove()
862 ("%s: bad popmap slot %d in node %p", __func__, slot, node)); in pctrie_remove()
863 node = pctrie_parent(node); in pctrie_remove()
865 pctrie_setparent(child, node); in pctrie_remove()
866 parentp = pctrie_child(ptree, node, index); in pctrie_remove()
878 struct pctrie_node *child, *node; in pctrie_remove_lookup() local
882 node = NULL; in pctrie_remove_lookup()
885 node = child; in pctrie_remove_lookup()
886 slot = pctrie_slot(node, index); in pctrie_remove_lookup()
887 child = pctrie_node_load(&node->pn_child[slot], 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()
908 pctrie_remove(it->ptree, it->node, it->index, freenode); in pctrie_iter_remove()
910 it->node = pctrie_parent(it->node); in pctrie_iter_remove()
920 struct pctrie_node *node; in pctrie_iter_value() local
922 node = pctrie_node_load(pctrie_child(it->ptree, it->node, it->index), in pctrie_iter_value()
924 return (pctrie_toval(node)); in pctrie_iter_value()
929 * until an interior node is stripped of all children, and returned for
930 * deallocation, with *pnode left pointing to the parent of that node.
936 struct pctrie_node *child, *node; in pctrie_reclaim_prune() local
939 node = *pnode; in pctrie_reclaim_prune()
940 while (node->pn_popmap != 0) { in pctrie_reclaim_prune()
941 slot = ffs(node->pn_popmap) - 1; in pctrie_reclaim_prune()
942 node->pn_popmap ^= 1 << slot; in pctrie_reclaim_prune()
943 child = pctrie_node_load(&node->pn_child[slot], NULL, in pctrie_reclaim_prune()
945 pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL, in pctrie_reclaim_prune()
953 parent = node; in pctrie_reclaim_prune()
954 node = child; in pctrie_reclaim_prune()
957 return (node); in pctrie_reclaim_prune()
961 * Recover the node parent from its first child and continue pruning.
982 struct pctrie_node *node; in pctrie_reclaim_begin_compound() local
984 node = pctrie_root_load(ptree, NULL, PCTRIE_UNSERIALIZED); in pctrie_reclaim_begin_compound()
986 if (pctrie_isleaf(node)) { in pctrie_reclaim_begin_compound()
987 if (callback != NULL && node != PCTRIE_NULL) in pctrie_reclaim_begin_compound()
988 callback(pctrie_toptr(node, keyoff), arg); in pctrie_reclaim_begin_compound()
991 *pnode = node; in pctrie_reclaim_begin_compound()
1029 struct pctrie_node *leaf, *parent, *node; in pctrie_replace() local
1036 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); in pctrie_replace()
1039 if (pctrie_isleaf(node)) { 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()
1054 parent = node; in pctrie_replace()
1055 node = pctrie_node_load(&node->pn_child[slot], NULL, in pctrie_replace()
1063 * Show details about the given node.
1067 struct pctrie_node *node, *tmp; in DB_SHOW_COMMAND() local
1073 node = (struct pctrie_node *)addr; in DB_SHOW_COMMAND()
1074 db_printf("node %p, owner %jx, children popmap %04x, level %u:\n", in DB_SHOW_COMMAND()
1075 (void *)node, (uintmax_t)node->pn_owner, node->pn_popmap, in DB_SHOW_COMMAND()
1076 node->pn_clev / PCTRIE_WIDTH); in DB_SHOW_COMMAND()
1077 for (popmap = node->pn_popmap; popmap != 0; popmap ^= 1 << slot) { in DB_SHOW_COMMAND()
1079 tmp = pctrie_node_load(&node->pn_child[slot], NULL, in DB_SHOW_COMMAND()
1084 node->pn_clev / PCTRIE_WIDTH); in DB_SHOW_COMMAND()