Lines Matching +full:parent +full:- +full:child
1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause
33 * Path-compressed radix trie implementation.
36 * - Size of the nodes should be as small as possible but still big enough
41 * - There is not a huge bias toward the number of lookup operations over
45 * - On average not many nodes are expected to be fully populated, hence
84 smr_pctnode_t pn_parent; /* Parent node. */
85 smr_pctnode_t pn_child[PCTRIE_COUNT]; /* Child nodes. */
94 return ((index >> node->pn_clev) & (PCTRIE_COUNT - 1)); in pctrie_slot()
104 index = (index - node->pn_owner) >> node->pn_clev; in pctrie_keybarr()
155 return ((smr_pctnode_t *)&ptree->pt_root); in pctrie_root()
168 * Get the child of a node.
174 &node->pn_child[pctrie_slot(node, index)]); in pctrie_child()
210 return ((void *)(((uintptr_t)node & ~PCTRIE_FLAGS) - keyoff)); in pctrie_toptr()
214 * Make 'parent' a parent of 'child'.
217 pctrie_setparent(struct pctrie_node *child, struct pctrie_node *parent) in pctrie_setparent() argument
219 pctrie_node_store(&child->pn_parent, parent, PCTRIE_UNSERIALIZED); in pctrie_setparent()
223 * Return the parent of 'node'.
228 return (pctrie_node_load(&node->pn_parent, NULL, PCTRIE_UNSERIALIZED)); in pctrie_parent()
232 * Make 'child' a child of 'node'.
236 struct pctrie_node *child, enum pctrie_access access) in pctrie_addnode() argument
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()
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()
287 * parent of that node.
294 struct pctrie_node *parent; in _pctrie_lookup_node() local
297 parent = node; in _pctrie_lookup_node()
298 if (parent == NULL) in _pctrie_lookup_node()
305 while (parent != NULL) { in _pctrie_lookup_node()
306 KASSERT(access == PCTRIE_SMR || !powerof2(parent->pn_popmap), in _pctrie_lookup_node()
308 node = parent; in _pctrie_lookup_node()
311 parent = pctrie_parent(node); in _pctrie_lookup_node()
316 parent = node; in _pctrie_lookup_node()
317 KASSERT(access == PCTRIE_SMR || !powerof2(parent->pn_popmap), in _pctrie_lookup_node()
319 node = pctrie_node_load(&node->pn_child[slot], smr, access); in _pctrie_lookup_node()
321 *parent_out = parent; in _pctrie_lookup_node()
334 struct pctrie_node *node, *parent; in pctrie_lookup() local
336 node = _pctrie_lookup_node(ptree, NULL, index, &parent, NULL, in pctrie_lookup()
349 struct pctrie_node *node, *parent; in pctrie_lookup_unlocked() local
353 node = _pctrie_lookup_node(ptree, NULL, index, &parent, smr, in pctrie_lookup_unlocked()
369 node = _pctrie_lookup_node(it->ptree, it->node, index, &it->node, in pctrie_iter_lookup()
371 it->index = index; in pctrie_iter_lookup()
376 * Look for where to insert the key-value pair into the trie. Complete the
384 _pctrie_insert_lookup(struct pctrie *ptree, struct pctrie_node *parent, in _pctrie_insert_lookup() argument
389 node = _pctrie_lookup_node(ptree, parent, *val, parent_out, NULL, in _pctrie_insert_lookup()
433 * Wrap _pctrie_insert_lookup to implement find-or-insert. Do not look
454 it->index = *val; in pctrie_iter_insert_lookup()
455 res = _pctrie_insert_lookup(it->ptree, it->node, val, &it->node, in pctrie_iter_insert_lookup()
459 (uintmax_t)it->index); in pctrie_iter_insert_lookup()
464 * Inserts newly allocated node 'child' into trie at location 'parentp', with
465 * parent 'parent' and two children, 'val' and whatever non-NULL node or leaf
469 pctrie_insert_node(uint64_t *val, struct pctrie_node *parent, void *parentp, in pctrie_insert_node() argument
470 struct pctrie_node *child) in pctrie_insert_node() argument
476 * Clear the last child pointer of the newly allocated child. We want in pctrie_insert_node()
479 * cache-cold in the dtor callback. in pctrie_insert_node()
481 if (child->pn_popmap != 0) { in pctrie_insert_node()
482 pctrie_node_store(&child->pn_child[ffs(child->pn_popmap) - 1], in pctrie_insert_node()
484 child->pn_popmap = 0; in pctrie_insert_node()
488 * Recover the values of the two children of the new child node. If in pctrie_insert_node()
494 pctrie_setparent(child, parent); in pctrie_insert_node()
496 pctrie_setparent(node, child); in pctrie_insert_node()
500 * From the highest-order bit where the indexes differ, in pctrie_insert_node()
507 (1 << (sizeof(child->pn_clev) * NBBY)), "pn_clev too narrow"); in pctrie_insert_node()
508 child->pn_clev = rounddown(ilog2(index ^ newind), PCTRIE_WIDTH); in pctrie_insert_node()
509 child->pn_owner = PCTRIE_COUNT; in pctrie_insert_node()
510 child->pn_owner = index & -(child->pn_owner << child->pn_clev); in pctrie_insert_node()
514 pctrie_addnode(child, index, pctrie_toleaf(val), PCTRIE_UNSERIALIZED); in pctrie_insert_node()
515 pctrie_addnode(child, newind, node, PCTRIE_UNSERIALIZED); in pctrie_insert_node()
517 pctrie_node_store(parentp, child, PCTRIE_LOCKED); in pctrie_insert_node()
527 uint64_t index = it->index + stride; in pctrie_iter_stride()
530 if ((stride > 0) != (index > it->index)) in pctrie_iter_stride()
533 if ((index < it->limit) != (it->index < it->limit)) in pctrie_iter_stride()
556 return (pctrie_iter_stride(it, -1)); in pctrie_iter_prev()
560 * Returns the number of contiguous, non-NULL entries read into the value[]
568 struct pctrie_node *parent; in _pctrie_lookup_range() local
572 parent = node; in _pctrie_lookup_range()
574 node = _pctrie_lookup_node(ptree, parent, index + i, &parent, in _pctrie_lookup_range()
580 if (base == 0 || parent == NULL || parent->pn_clev != 0) in _pctrie_lookup_range()
585 * children of this parent left to examine. For PCTRIE_LOCKED, in _pctrie_lookup_range()
586 * compute the number of non-NULL children from base up to the in _pctrie_lookup_range()
587 * first NULL child, if any, using the fact that pn_popmap has in _pctrie_lookup_range()
588 * bits set for only the non-NULL children. in _pctrie_lookup_range()
594 * child pointers, enforced by memory barriers on the writing of in _pctrie_lookup_range()
596 * the popmap bit for a child page may, for an instant, in _pctrie_lookup_range()
597 * misrepresent the nullness of the child page because an in _pctrie_lookup_range()
600 end = (access == PCTRIE_SMR) ? PCTRIE_COUNT - base : in _pctrie_lookup_range()
601 ffs((parent->pn_popmap >> base) + 1) - 1; in _pctrie_lookup_range()
604 node = pctrie_node_load(&parent->pn_child[base++], in _pctrie_lookup_range()
611 ("%s: null child written to range", __func__)); in _pctrie_lookup_range()
622 *parent_out = parent; in _pctrie_lookup_range()
627 * Returns the number of contiguous, non-NULL entries read into the value[]
640 * Returns the number of contiguous, non-NULL entries read into the value[]
660 * Returns the number of contiguous, non-NULL entries read into the value[]
668 return (_pctrie_lookup_range(it->ptree, it->node, index, value, count, in pctrie_iter_lookup_range()
669 &it->node, NULL, PCTRIE_LOCKED)); in pctrie_iter_lookup_range()
673 * Find first leaf >= index, and fill iter with the path to the parent of that
680 struct pctrie_node *parent; in _pctrie_lookup_ge() local
685 node = _pctrie_lookup_node(ptree, node, index, &parent, in _pctrie_lookup_ge()
695 while (parent != NULL) { in _pctrie_lookup_ge()
696 slot = pctrie_slot(parent, index) + 1; in _pctrie_lookup_ge()
697 if ((parent->pn_popmap >> slot) != 0) in _pctrie_lookup_ge()
699 node = parent; in _pctrie_lookup_ge()
700 parent = pctrie_parent(node); in _pctrie_lookup_ge()
702 if (parent == NULL) { in _pctrie_lookup_ge()
708 /* Step to the least child with a descendant > index. */ in _pctrie_lookup_ge()
709 slot += ffs(parent->pn_popmap >> slot) - 1; in _pctrie_lookup_ge()
710 node = pctrie_node_load(&parent->pn_child[slot], NULL, in _pctrie_lookup_ge()
715 if (limit != 0 && node->pn_owner >= limit) in _pctrie_lookup_ge()
717 slot = ffs(node->pn_popmap) - 1; in _pctrie_lookup_ge()
718 parent = node; in _pctrie_lookup_ge()
719 node = pctrie_node_load(&node->pn_child[slot], NULL, in _pctrie_lookup_ge()
723 *parent_out = parent; in _pctrie_lookup_ge()
737 * Find first leaf >= index, and fill iter with the path to the parent of that
745 m = _pctrie_lookup_ge(it->ptree, it->node, index, &it->node, it->limit); in pctrie_iter_lookup_ge()
747 it->index = *m; in pctrie_iter_lookup_ge()
758 uint64_t index = it->index + jump; in pctrie_iter_jump_ge()
761 if ((jump > 0) != (index > it->index)) in pctrie_iter_jump_ge()
763 if (it->limit != 0 && index >= it->limit) in pctrie_iter_jump_ge()
769 * Find first leaf <= index, and fill iter with the path to the parent of that
776 struct pctrie_node *parent; in _pctrie_lookup_le() local
781 node = _pctrie_lookup_node(ptree, node, index, &parent, NULL, in _pctrie_lookup_le()
791 while (parent != NULL) { in _pctrie_lookup_le()
792 slot = pctrie_slot(parent, index); in _pctrie_lookup_le()
793 if ((parent->pn_popmap & ((1 << slot) - 1)) != 0) in _pctrie_lookup_le()
795 node = parent; in _pctrie_lookup_le()
796 parent = pctrie_parent(node); in _pctrie_lookup_le()
798 if (parent == NULL) { in _pctrie_lookup_le()
804 /* Step to the greatest child with a descendant < index. */ in _pctrie_lookup_le()
805 slot = ilog2(parent->pn_popmap & ((1 << slot) - 1)); in _pctrie_lookup_le()
806 node = pctrie_node_load(&parent->pn_child[slot], NULL, in _pctrie_lookup_le()
811 if (limit != 0 && limit >= node->pn_owner + in _pctrie_lookup_le()
812 ((uint64_t)PCTRIE_COUNT << node->pn_clev) - 1) in _pctrie_lookup_le()
814 slot = ilog2(node->pn_popmap); in _pctrie_lookup_le()
815 parent = node; in _pctrie_lookup_le()
816 node = pctrie_node_load(&node->pn_child[slot], NULL, in _pctrie_lookup_le()
820 *parent_out = parent; in _pctrie_lookup_le()
839 return (_pctrie_lookup_le(ptree, node, index - 1, NULL, 0)); in pctrie_subtree_lookup_lt()
843 * Find first leaf <= index, and fill iter with the path to the parent of that
851 m = _pctrie_lookup_le(it->ptree, it->node, index, &it->node, it->limit); in pctrie_iter_lookup_le()
853 it->index = *m; in pctrie_iter_lookup_le()
864 uint64_t index = it->index - jump; in pctrie_iter_jump_le()
867 if ((jump > 0) != (index < it->index)) in pctrie_iter_jump_le()
869 if (it->limit != 0 && index <= it->limit) in pctrie_iter_jump_le()
875 * Remove the non-NULL child identified by 'index' from the set of children of
876 * 'node'. If doing so causes 'node' to have only one child, purge it from the
883 struct pctrie_node *child; in pctrie_remove() local
892 KASSERT((node->pn_popmap & (1 << slot)) != 0, in pctrie_remove()
895 node->pn_popmap ^= 1 << slot; in pctrie_remove()
896 if (!powerof2(node->pn_popmap)) { in pctrie_remove()
901 KASSERT(node->pn_popmap != 0, ("%s: bad popmap all zeroes", __func__)); in pctrie_remove()
902 slot = ffs(node->pn_popmap) - 1; in pctrie_remove()
903 child = pctrie_node_load(&node->pn_child[slot], NULL, PCTRIE_LOCKED); in pctrie_remove()
904 KASSERT(child != PCTRIE_NULL, in pctrie_remove()
907 if (!pctrie_isleaf(child)) in pctrie_remove()
908 pctrie_setparent(child, node); in pctrie_remove()
910 pctrie_node_store(parentp, child, PCTRIE_LOCKED); in pctrie_remove()
922 struct pctrie_node *node, *parent; in pctrie_remove_lookup() local
925 node = _pctrie_lookup_node(ptree, NULL, index, &parent, NULL, in pctrie_remove_lookup()
928 if (m != NULL && pctrie_remove(ptree, parent, index)) in pctrie_remove_lookup()
929 *freenode = parent; in pctrie_remove_lookup()
943 it->ptree, it->node, it->index), NULL, PCTRIE_LOCKED), it->index), in pctrie_iter_remove()
945 (uintmax_t)it->index)); in pctrie_iter_remove()
946 if (pctrie_remove(it->ptree, it->node, it->index)) { in pctrie_iter_remove()
947 *freenode = it->node; in pctrie_iter_remove()
948 it->node = pctrie_parent(it->node); in pctrie_iter_remove()
962 node = pctrie_node_load(pctrie_child(it->ptree, it->node, it->index), in pctrie_iter_value()
970 * deallocation, with *pnode left pointing to the parent of that node.
973 pctrie_reclaim_prune(struct pctrie_node **pnode, struct pctrie_node *parent, in pctrie_reclaim_prune() argument
976 struct pctrie_node *child, *node; in pctrie_reclaim_prune() local
980 while (node->pn_popmap != 0) { in pctrie_reclaim_prune()
981 slot = ffs(node->pn_popmap) - 1; in pctrie_reclaim_prune()
982 node->pn_popmap ^= 1 << slot; in pctrie_reclaim_prune()
983 child = pctrie_node_load(&node->pn_child[slot], NULL, in pctrie_reclaim_prune()
985 pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL, in pctrie_reclaim_prune()
987 if (pctrie_isleaf(child)) { in pctrie_reclaim_prune()
989 callback(pctrie_toptr(child, keyoff), arg); in pctrie_reclaim_prune()
993 parent = node; in pctrie_reclaim_prune()
994 node = child; in pctrie_reclaim_prune()
996 *pnode = parent; in pctrie_reclaim_prune()
1001 * Recover the node parent from its first child and continue pruning.
1015 * Find the trie root, and start pruning with a NULL parent.
1069 struct pctrie_node *node, *parent; in pctrie_replace() local
1072 node = _pctrie_lookup_node(ptree, NULL, *newval, &parent, NULL, in pctrie_replace()
1077 pctrie_node_store(pctrie_child(ptree, parent, *newval), in pctrie_replace()
1096 (void *)node, (uintmax_t)node->pn_owner, node->pn_popmap, in DB_SHOW_COMMAND()
1097 node->pn_clev / PCTRIE_WIDTH); in DB_SHOW_COMMAND()
1098 for (popmap = node->pn_popmap; popmap != 0; popmap ^= 1 << slot) { in DB_SHOW_COMMAND()
1099 slot = ffs(popmap) - 1; in DB_SHOW_COMMAND()
1100 tmp = pctrie_node_load(&node->pn_child[slot], NULL, in DB_SHOW_COMMAND()
1105 node->pn_clev / PCTRIE_WIDTH); in DB_SHOW_COMMAND()