Lines Matching refs: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()
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()
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()
181 pctrie_isleaf(struct pctrie_node *node) in pctrie_isleaf() argument
183 return (((uintptr_t)node & PCTRIE_ISLEAF) != 0); in pctrie_isleaf()
199 pctrie_toval(struct pctrie_node *node) in pctrie_toval() argument
201 return ((uint64_t *)((uintptr_t)node & ~PCTRIE_FLAGS)); in pctrie_toval()
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()
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()
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()
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()
371 struct pctrie_node *node; in pctrie_insert_node() local
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()
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()
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()
485 _pctrie_lookup_node(struct pctrie *ptree, struct pctrie_node *node, in _pctrie_lookup_node() argument
496 while (node != NULL) { in _pctrie_lookup_node()
497 KASSERT(!powerof2(node->pn_popmap), 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()
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()
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()
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
643 node = _pctrie_lookup_node(ptree, node, index, &parent, in _pctrie_lookup_ge()
650 if (node == PCTRIE_NULL || *pctrie_toval(node) < 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
737 node = _pctrie_lookup_node(ptree, node, index, &parent, NULL, in _pctrie_lookup_le()
744 if (node == PCTRIE_NULL || *pctrie_toval(node) > 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()
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()
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()
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()
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()
1067 struct pctrie_node *node, *tmp; in DB_SHOW_COMMAND() local
1073 node = (struct pctrie_node *)addr; 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()