Lines Matching refs:node
99 pctrie_slot(struct pctrie_node *node, uint64_t index) in pctrie_slot() argument
101 return ((index >> node->pn_clev) & PCTRIE_MASK); in pctrie_slot()
109 pctrie_keybarr(struct pctrie_node *node, uint64_t index, int *slot) in pctrie_keybarr() argument
111 index = (index - node->pn_owner) >> node->pn_clev; in pctrie_keybarr()
122 pctrie_node_put(struct pctrie_node *node) in pctrie_node_put() argument
127 KASSERT(powerof2(node->pn_popmap), in pctrie_node_put()
128 ("pctrie_node_put: node %p has too many children %04x", node, in pctrie_node_put()
129 node->pn_popmap)); in pctrie_node_put()
131 if ((node->pn_popmap & (1 << slot)) != 0) in pctrie_node_put()
133 KASSERT(smr_unserialized_load(&node->pn_child[slot], true) == in pctrie_node_put()
135 ("pctrie_node_put: node %p has a child", node)); in pctrie_node_put()
189 pctrie_root_store(struct pctrie *ptree, struct pctrie_node *node, in pctrie_root_store() argument
192 pctrie_node_store((smr_pctnode_t *)&ptree->pt_root, node, access); in pctrie_root_store()
199 pctrie_isleaf(struct pctrie_node *node) in pctrie_isleaf() argument
202 return (((uintptr_t)node & PCTRIE_ISLEAF) != 0); in pctrie_isleaf()
218 pctrie_toval(struct pctrie_node *node) in pctrie_toval() argument
221 return ((uint64_t *)((uintptr_t)node & ~PCTRIE_FLAGS)); in pctrie_toval()
228 pctrie_addnode(struct pctrie_node *node, uint64_t index, in pctrie_addnode() argument
233 slot = pctrie_slot(node, index); in pctrie_addnode()
234 pctrie_node_store(&node->pn_child[slot], child, access); in pctrie_addnode()
235 node->pn_popmap ^= 1 << slot; in pctrie_addnode()
236 KASSERT((node->pn_popmap & (1 << slot)) != 0, in pctrie_addnode()
237 ("%s: bad popmap slot %d in node %p", __func__, slot, node)); in pctrie_addnode()
246 struct pctrie_node *node; in pctrie_zone_init() local
248 node = mem; in pctrie_zone_init()
249 node->pn_popmap = 0; in pctrie_zone_init()
250 for (int i = 0; i < nitems(node->pn_child); i++) in pctrie_zone_init()
251 pctrie_node_store(&node->pn_child[i], PCTRIE_NULL, in pctrie_zone_init()
272 struct pctrie_node *node, *parent; in pctrie_insert_lookup() local
281 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); in pctrie_insert_lookup()
284 if (pctrie_isleaf(node)) { in pctrie_insert_lookup()
285 if (node == PCTRIE_NULL) { in pctrie_insert_lookup()
293 if (*pctrie_toval(node) == index) in pctrie_insert_lookup()
298 if (pctrie_keybarr(node, index, &slot)) in pctrie_insert_lookup()
300 parent = node; in pctrie_insert_lookup()
301 node = pctrie_node_load(&node->pn_child[slot], NULL, in pctrie_insert_lookup()
320 struct pctrie_node *node; in pctrie_insert_node() local
341 node = pctrie_node_load(parentp, NULL, PCTRIE_UNSERIALIZED); in pctrie_insert_node()
342 newind = *pctrie_toval(node); in pctrie_insert_node()
360 pctrie_addnode(parent, newind, node, PCTRIE_UNSERIALIZED); in pctrie_insert_node()
373 struct pctrie_node *node; in _pctrie_lookup() local
377 node = pctrie_root_load(ptree, smr, access); in _pctrie_lookup()
379 if (pctrie_isleaf(node)) { in _pctrie_lookup()
380 if ((m = pctrie_toval(node)) != NULL && *m == index) in _pctrie_lookup()
384 if (pctrie_keybarr(node, index, &slot)) in _pctrie_lookup()
386 node = pctrie_node_load(&node->pn_child[slot], smr, access); in _pctrie_lookup()
428 struct pctrie_node *node, *succ; in pctrie_lookup_ge() local
445 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); in pctrie_lookup_ge()
448 if (pctrie_isleaf(node)) { in pctrie_lookup_ge()
449 if ((m = pctrie_toval(node)) != NULL && *m >= index) in pctrie_lookup_ge()
453 if (pctrie_keybarr(node, index, &slot)) { in pctrie_lookup_ge()
458 if (node->pn_owner > index) in pctrie_lookup_ge()
459 succ = node; in pctrie_lookup_ge()
469 if ((node->pn_popmap >> slot) > 1) in pctrie_lookup_ge()
470 succ = node; in pctrie_lookup_ge()
471 node = pctrie_node_load(&node->pn_child[slot], NULL, in pctrie_lookup_ge()
481 if (succ != node) { in pctrie_lookup_ge()
517 struct pctrie_node *node, *pred; in pctrie_lookup_le() local
524 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); in pctrie_lookup_le()
527 if (pctrie_isleaf(node)) { in pctrie_lookup_le()
528 if ((m = pctrie_toval(node)) != NULL && *m <= index) in pctrie_lookup_le()
532 if (pctrie_keybarr(node, index, &slot)) { in pctrie_lookup_le()
533 if (node->pn_owner < index) in pctrie_lookup_le()
534 pred = node; in pctrie_lookup_le()
537 if ((node->pn_popmap & ((1 << slot) - 1)) != 0) in pctrie_lookup_le()
538 pred = node; in pctrie_lookup_le()
539 node = pctrie_node_load(&node->pn_child[slot], NULL, in pctrie_lookup_le()
544 if (pred != node) { in pctrie_lookup_le()
571 struct pctrie_node *child, *node, *parent; in pctrie_remove_lookup() local
575 *freenode = node = NULL; in pctrie_remove_lookup()
580 parent = node; in pctrie_remove_lookup()
581 node = child; in pctrie_remove_lookup()
582 slot = pctrie_slot(node, index); in pctrie_remove_lookup()
583 child = pctrie_node_load(&node->pn_child[slot], NULL, in pctrie_remove_lookup()
588 if (node == NULL) { in pctrie_remove_lookup()
592 KASSERT((node->pn_popmap & (1 << slot)) != 0, in pctrie_remove_lookup()
594 __func__, slot, node)); in pctrie_remove_lookup()
595 node->pn_popmap ^= 1 << slot; in pctrie_remove_lookup()
596 pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL, PCTRIE_LOCKED); in pctrie_remove_lookup()
597 if (!powerof2(node->pn_popmap)) in pctrie_remove_lookup()
599 KASSERT(node->pn_popmap != 0, ("%s: bad popmap all zeroes", __func__)); in pctrie_remove_lookup()
600 slot = ffs(node->pn_popmap) - 1; in pctrie_remove_lookup()
601 child = pctrie_node_load(&node->pn_child[slot], NULL, PCTRIE_LOCKED); in pctrie_remove_lookup()
603 ("%s: bad popmap slot %d in node %p", __func__, slot, node)); in pctrie_remove_lookup()
608 KASSERT(node == in pctrie_remove_lookup()
618 pctrie_node_put(node); in pctrie_remove_lookup()
619 *freenode = node; in pctrie_remove_lookup()
633 struct pctrie_node *child, *node; in pctrie_reclaim_prune() local
636 node = *pnode; in pctrie_reclaim_prune()
637 while (node->pn_popmap != 0) { in pctrie_reclaim_prune()
638 slot = ffs(node->pn_popmap) - 1; in pctrie_reclaim_prune()
639 node->pn_popmap ^= 1 << slot; in pctrie_reclaim_prune()
640 child = pctrie_node_load(&node->pn_child[slot], NULL, in pctrie_reclaim_prune()
642 pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL, in pctrie_reclaim_prune()
647 pctrie_node_store(&node->pn_child[0], parent, in pctrie_reclaim_prune()
649 parent = node; in pctrie_reclaim_prune()
650 node = child; in pctrie_reclaim_prune()
653 return (node); in pctrie_reclaim_prune()
662 struct pctrie_node *parent, *node; in pctrie_reclaim_resume() local
664 node = *pnode; in pctrie_reclaim_resume()
665 if (node == NULL) in pctrie_reclaim_resume()
668 parent = pctrie_node_load(&node->pn_child[0], NULL, in pctrie_reclaim_resume()
670 pctrie_node_store(&node->pn_child[0], PCTRIE_NULL, PCTRIE_UNSERIALIZED); in pctrie_reclaim_resume()
681 struct pctrie_node *node; in pctrie_reclaim_begin() local
683 node = pctrie_root_load(ptree, NULL, PCTRIE_UNSERIALIZED); in pctrie_reclaim_begin()
685 if (pctrie_isleaf(node)) in pctrie_reclaim_begin()
687 *pnode = node; in pctrie_reclaim_begin()
698 struct pctrie_node *leaf, *parent, *node; in pctrie_replace() local
705 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); in pctrie_replace()
708 if (pctrie_isleaf(node)) { in pctrie_replace()
709 if ((m = pctrie_toval(node)) != NULL && *m == index) { in pctrie_replace()
720 if (pctrie_keybarr(node, index, &slot)) in pctrie_replace()
722 parent = node; in pctrie_replace()
723 node = pctrie_node_load(&node->pn_child[slot], NULL, in pctrie_replace()
735 struct pctrie_node *node, *tmp; in DB_SHOW_COMMAND() local
741 node = (struct pctrie_node *)addr; in DB_SHOW_COMMAND()
743 (void *)node, (uintmax_t)node->pn_owner, node->pn_popmap, in DB_SHOW_COMMAND()
744 node->pn_clev / PCTRIE_WIDTH); in DB_SHOW_COMMAND()
745 for (popmap = node->pn_popmap; popmap != 0; popmap ^= 1 << slot) { in DB_SHOW_COMMAND()
747 tmp = pctrie_node_load(&node->pn_child[slot], NULL, in DB_SHOW_COMMAND()
752 node->pn_clev / PCTRIE_WIDTH); in DB_SHOW_COMMAND()