Lines Matching +full:child +full:- +full:node
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_child[PCTRIE_COUNT]; /* Child nodes. */
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;
111 * Check radix node.
114 pctrie_node_put(struct pctrie_node *node)
119 KASSERT(powerof2(node->pn_popmap),
120 ("pctrie_node_put: node %p has too many children %04x", node,
121 node->pn_popmap));
123 if ((node->pn_popmap & (1 << slot)) != 0)
125 KASSERT(smr_unserialized_load(&node->pn_child[slot], true) ==
127 ("pctrie_node_put: node %p has a child", node));
135 * Fetch a node pointer from a slot.
176 return ((smr_pctnode_t *)&ptree->pt_root);
180 * Get the root node for a tree.
189 * Returns TRUE if the specified node is a leaf and FALSE otherwise.
192 pctrie_isleaf(struct pctrie_node *node)
194 return (((uintptr_t)node & PCTRIE_ISLEAF) != 0);
207 * Returns the associated val extracted from node.
210 pctrie_toval(struct pctrie_node *node)
212 return ((uint64_t *)((uintptr_t)node & ~PCTRIE_FLAGS));
216 * Returns the associated pointer extracted from node and field offset.
219 pctrie_toptr(struct pctrie_node *node, int keyoff)
221 return ((void *)(((uintptr_t)node & ~PCTRIE_FLAGS) - keyoff));
225 * Make 'child' a child of 'node'.
228 pctrie_addnode(struct pctrie_node *node, uint64_t index,
229 struct pctrie_node *child, enum pctrie_access access)
233 slot = pctrie_slot(node, index);
234 pctrie_node_store(&node->pn_child[slot], child, access);
235 node->pn_popmap ^= 1 << slot;
236 KASSERT((node->pn_popmap & (1 << slot)) != 0,
237 ("%s: bad popmap slot %d in node %p", __func__, slot, node));
241 * pctrie node zone initializer.
246 struct pctrie_node *node;
248 node = mem;
249 node->pn_popmap = 0;
250 for (int i = 0; i < nitems(node->pn_child); i++)
251 pctrie_node_store(&node->pn_child[i], PCTRIE_NULL,
270 * Look for where to insert the key-value pair into the trie. Complete the
278 * *neighbor_out to the lowest level node we encounter during the insert lookup
282 * Note that mode is expected to be a compile-time constant, and this procedure
291 struct pctrie_node *node, *parent;
300 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
303 if (pctrie_isleaf(node)) {
304 if (node == PCTRIE_NULL) {
313 if (*pctrie_toval(node) == index) {
314 *found_out = pctrie_toval(node);
319 if (pctrie_keybarr(node, index, &slot))
322 * Descend. If we're tracking the next neighbor and this node
327 if ((node->pn_popmap & ((1 << slot) - 1)) != 0)
328 *neighbor_out = node;
330 if ((node->pn_popmap >> slot) > 1)
331 *neighbor_out = node;
333 parent = node;
334 node = pctrie_node_load(&node->pn_child[slot], NULL,
339 * The caller will split this node. If we're tracking the next
340 * neighbor, record the old node if the old entry is in the right
344 if (*pctrie_toval(node) < index)
345 *neighbor_out = node;
347 if (*pctrie_toval(node) > index)
348 *neighbor_out = node;
352 * 'node' must be replaced in the tree with a new branch node, with
353 * children 'node' and 'val'. Return the place that points to 'node'
354 * now, and will point to to the new branching node later.
356 return ((parent == NULL) ? pctrie_root(ptree): &parent->pn_child[slot]);
379 * Wrap pctrie_insert_lookup_compound to implement find-or-insert. Do not look
394 * newly-inserted or to-be-inserted entry.
409 * newly-inserted or to-be-inserted entry.
422 * Uses new node to insert key-value pair into the trie at given location.
427 struct pctrie_node *node;
431 * Clear the last child pointer of the newly allocated parent. We want
434 * cache-cold in the dtor callback.
436 if (parent->pn_popmap != 0) {
437 pctrie_node_store(&parent->pn_child[ffs(parent->pn_popmap) - 1],
439 parent->pn_popmap = 0;
443 * Recover the values of the two children of the new parent node. If
444 * 'node' is not a leaf, this stores into 'newind' the 'owner' field,
445 * which must be first in the node.
448 node = pctrie_node_load(parentp, NULL, PCTRIE_UNSERIALIZED);
449 newind = *pctrie_toval(node);
452 * From the highest-order bit where the indexes differ,
459 (1 << (sizeof(parent->pn_clev) * NBBY)), "pn_clev too narrow");
460 parent->pn_clev = rounddown(ilog2(index ^ newind), PCTRIE_WIDTH);
461 parent->pn_owner = PCTRIE_COUNT;
462 parent->pn_owner = index & -(parent->pn_owner << parent->pn_clev);
467 pctrie_addnode(parent, newind, node, PCTRIE_UNSERIALIZED);
473 * Return the value associated with the node, if the node is a leaf that matches
477 pctrie_match_value(struct pctrie_node *node, uint64_t index)
481 if (!pctrie_isleaf(node) || (m = pctrie_toval(node)) == NULL ||
495 struct pctrie_node *node;
498 node = pctrie_root_load(ptree, smr, access);
499 /* Seek a node that matches index. */
500 while (!pctrie_isleaf(node) && !pctrie_keybarr(node, index, &slot))
501 node = pctrie_node_load(&node->pn_child[slot], smr, access);
502 return (pctrie_match_value(node, index));
534 * Returns the last node examined in the search for the index, and updates the
535 * search path to that node.
541 struct pctrie_node *node;
545 * Climb the search path to find the lowest node from which to start the
548 while (it->top != 0) {
549 node = it->path[it->top - 1];
550 KASSERT(!powerof2(node->pn_popmap),
551 ("%s: freed node in iter path", __func__));
552 if (!pctrie_keybarr(node, index, &slot)) {
553 node = pctrie_node_load(
554 &node->pn_child[slot], smr, access);
557 --it->top;
559 if (it->top == 0)
560 node = pctrie_root_load(it->ptree, smr, access);
562 /* Seek a node that matches index. */
563 while (!pctrie_isleaf(node) && !pctrie_keybarr(node, index, &slot)) {
564 KASSERT(it->top < nitems(it->path),
565 ("%s: path overflow in trie %p", __func__, it->ptree));
566 it->path[it->top++] = node;
567 node = pctrie_node_load(&node->pn_child[slot], smr, access);
569 return (node);
579 struct pctrie_node *node;
581 it->index = index;
582 node = _pctrie_iter_lookup_node(it, index, smr, access);
583 return (pctrie_match_value(node, index));
597 * to indicate where a new node must be allocated to complete insertion.
603 struct pctrie_node *node;
605 it->index = *val;
606 node = _pctrie_iter_lookup_node(it, *val, NULL, PCTRIE_LOCKED);
607 if (node == PCTRIE_NULL) {
608 if (it->top == 0)
609 pctrie_node_store(pctrie_root(it->ptree),
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);
621 * 'node' must be replaced in the tree with a new branch node, with
622 * children 'node' and 'val'. Return the place that points to 'node'
623 * now, and will point to to the new branching node later.
625 if (it->top == 0)
626 return (pctrie_root(it->ptree));
627 node = it->path[it->top - 1];
628 return (&node->pn_child[pctrie_slot(node, it->index)]);
639 uint64_t index = it->index + stride;
642 if ((stride > 0) != (index > it->index))
645 if ((index < it->limit) != (it->index < it->limit))
678 return (_pctrie_iter_stride(it, -1, NULL, PCTRIE_LOCKED));
688 pctrie_lookup_ge_node(struct pctrie_node *node, uint64_t index)
697 * the trie, we use "succ" to remember the last branching-off point,
698 * that is, the interior node under which the least value that is both
700 * index resides. (The node's popmap makes it fast and easy to
701 * recognize a branching-off point.) If our ordinary lookup fails to
709 if (pctrie_isleaf(node)) {
710 if ((m = pctrie_toval(node)) != NULL && *m >= index)
714 if (pctrie_keybarr(node, index, &slot)) {
719 if (node->pn_owner > index)
720 succ = node;
730 if ((node->pn_popmap >> slot) > 1)
731 succ = node;
732 node = pctrie_node_load(&node->pn_child[slot], NULL,
742 if (succ != node) {
744 * Take a step to the next bigger sibling of the node chosen
748 KASSERT((succ->pn_popmap >> slot) != 0,
749 ("%s: no popmap siblings past slot %d in node %p",
751 slot += ffs(succ->pn_popmap >> slot) - 1;
752 succ = pctrie_node_load(&succ->pn_child[slot], NULL,
760 KASSERT(succ->pn_popmap != 0,
761 ("%s: no popmap children in node %p", __func__, succ));
762 slot = ffs(succ->pn_popmap) - 1;
763 succ = pctrie_node_load(&succ->pn_child[slot], NULL,
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));
791 struct pctrie_node *node;
795 /* Seek a node that matches index. */
796 node = _pctrie_iter_lookup_node(it, index, NULL, PCTRIE_LOCKED);
799 * If no such node was found, and instead this path leads only to nodes
802 if (node == PCTRIE_NULL || *pctrie_toval(node) < index) {
803 /* Climb the path to find a node with a descendant > index. */
804 while (it->top != 0) {
805 node = it->path[it->top - 1];
806 slot = pctrie_slot(node, index) + 1;
807 if ((node->pn_popmap >> slot) != 0)
809 --it->top;
811 if (it->top == 0)
814 /* Step to the least child with a descendant > index. */
815 slot += ffs(node->pn_popmap >> slot) - 1;
816 node = pctrie_node_load(&node->pn_child[slot], NULL,
820 while (!pctrie_isleaf(node)) {
821 if (it->limit != 0 && node->pn_owner >= it->limit)
823 slot = ffs(node->pn_popmap) - 1;
824 KASSERT(it->top < nitems(it->path),
825 ("%s: path overflow in trie %p", __func__, it->ptree));
826 it->path[it->top++] = node;
827 node = pctrie_node_load(&node->pn_child[slot], NULL,
830 m = pctrie_toval(node);
831 if (it->limit != 0 && *m >= it->limit)
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)
856 pctrie_subtree_lookup_gt_assert(struct pctrie_node *node, uint64_t index,
868 (uintmax_t)index, node, res, expected));
879 pctrie_lookup_le_node(struct pctrie_node *node, uint64_t index)
890 if (pctrie_isleaf(node)) {
891 if ((m = pctrie_toval(node)) != NULL && *m <= index)
895 if (pctrie_keybarr(node, index, &slot)) {
896 if (node->pn_owner < index)
897 pred = node;
900 if ((node->pn_popmap & ((1 << slot) - 1)) != 0)
901 pred = node;
902 node = pctrie_node_load(&node->pn_child[slot], NULL,
907 if (pred != node) {
909 KASSERT((pred->pn_popmap & ((1 << slot) - 1)) != 0,
910 ("%s: no popmap siblings before slot %d in node %p",
912 slot = ilog2(pred->pn_popmap & ((1 << slot) - 1));
913 pred = pctrie_node_load(&pred->pn_child[slot], NULL,
917 KASSERT(pred->pn_popmap != 0,
918 ("%s: no popmap children in node %p", __func__, pred));
919 slot = ilog2(pred->pn_popmap);
920 pred = pctrie_node_load(&pred->pn_child[slot], NULL,
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));
948 struct pctrie_node *node;
952 /* Seek a node that matches index. */
953 node = _pctrie_iter_lookup_node(it, index, NULL, PCTRIE_LOCKED);
956 * If no such node was found, and instead this path leads only to nodes
959 if (node == PCTRIE_NULL || *pctrie_toval(node) > index) {
960 /* Climb the path to find a node with a descendant < index. */
961 while (it->top != 0) {
962 node = it->path[it->top - 1];
963 slot = pctrie_slot(node, index);
964 if ((node->pn_popmap & ((1 << slot) - 1)) != 0)
966 --it->top;
968 if (it->top == 0)
971 /* Step to the greatest child with a descendant < index. */
972 slot = ilog2(node->pn_popmap & ((1 << slot) - 1));
973 node = pctrie_node_load(&node->pn_child[slot], NULL,
977 while (!pctrie_isleaf(node)) {
978 if (it->limit != 0 && it->limit >=
979 node->pn_owner + (PCTRIE_COUNT << node->pn_clev) - 1)
981 slot = ilog2(node->pn_popmap);
982 KASSERT(it->top < nitems(it->path),
983 ("%s: path overflow in trie %p", __func__, it->ptree));
984 it->path[it->top++] = node;
985 node = pctrie_node_load(&node->pn_child[slot], NULL,
988 m = pctrie_toval(node);
989 if (it->limit != 0 && *m <= it->limit)
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)
1014 pctrie_subtree_lookup_lt_assert(struct pctrie_node *node, uint64_t index,
1022 expected = pctrie_lookup_le(ptree, index - 1);
1026 (uintmax_t)index, node, res, expected));
1032 struct pctrie_node *node, struct pctrie_node **freenode)
1034 struct pctrie_node *child;
1037 if (node == NULL) {
1042 slot = pctrie_slot(node, index);
1043 KASSERT((node->pn_popmap & (1 << slot)) != 0,
1044 ("%s: bad popmap slot %d in node %p",
1045 __func__, slot, node));
1046 node->pn_popmap ^= 1 << slot;
1047 pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL, PCTRIE_LOCKED);
1048 if (!powerof2(node->pn_popmap))
1050 KASSERT(node->pn_popmap != 0, ("%s: bad popmap all zeroes", __func__));
1051 slot = ffs(node->pn_popmap) - 1;
1052 child = pctrie_node_load(&node->pn_child[slot], NULL, PCTRIE_LOCKED);
1053 KASSERT(child != PCTRIE_NULL,
1054 ("%s: bad popmap slot %d in node %p", __func__, slot, node));
1056 pctrie_node_store(pctrie_root(ptree), child, PCTRIE_LOCKED);
1059 KASSERT(node ==
1060 pctrie_node_load(&parent->pn_child[slot], NULL,
1061 PCTRIE_LOCKED), ("%s: invalid child value", __func__));
1062 pctrie_node_store(&parent->pn_child[slot], child,
1066 * The child is still valid and we can not zero the
1069 pctrie_node_put(node);
1070 *freenode = node;
1081 struct pctrie_node *child, *node, *parent;
1086 *freenode = node = NULL;
1087 child = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
1088 while (!pctrie_isleaf(child)) {
1089 parent = node;
1090 node = child;
1091 slot = pctrie_slot(node, index);
1092 child = pctrie_node_load(&node->pn_child[slot], NULL,
1095 m = pctrie_match_value(child, index);
1097 pctrie_remove(ptree, index, parent, node, freenode);
1108 struct pctrie_node *child, *node, *parent;
1114 if (it->top >= 1) {
1115 parent = (it->top >= 2) ? it->path[it->top - 2] : NULL;
1116 node = it->path[it->top - 1];
1117 slot = pctrie_slot(node, it->index);
1118 child = pctrie_node_load(&node->pn_child[slot], NULL,
1121 node = NULL;
1122 child = pctrie_root_load(it->ptree, NULL, PCTRIE_LOCKED);
1124 m = pctrie_match_value(child, it->index);
1126 pctrie_remove(it->ptree, it->index, parent, node, freenode);
1128 --it->top;
1139 struct pctrie_node *node;
1142 if (it->top == 0)
1143 node = pctrie_root_load(it->ptree, NULL,
1146 node = it->path[it->top - 1];
1147 slot = pctrie_slot(node, it->index);
1148 node = pctrie_node_load(&node->pn_child[slot], NULL,
1151 return (pctrie_toval(node));
1156 * using the leftmost child pointer for path reversal, until an interior node
1158 * pointing to the parent of that node.
1164 struct pctrie_node *child, *node;
1167 node = *pnode;
1168 while (node->pn_popmap != 0) {
1169 slot = ffs(node->pn_popmap) - 1;
1170 node->pn_popmap ^= 1 << slot;
1171 child = pctrie_node_load(&node->pn_child[slot], NULL,
1173 pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL,
1175 if (pctrie_isleaf(child)) {
1177 callback(pctrie_toptr(child, keyoff), arg);
1181 pctrie_node_store(&node->pn_child[0], parent,
1183 parent = node;
1184 node = child;
1187 return (node);
1191 * Recover the node parent from its first child and continue pruning.
1197 struct pctrie_node *parent, *node;
1199 node = *pnode;
1200 if (node == NULL)
1203 parent = pctrie_node_load(&node->pn_child[0], NULL,
1205 pctrie_node_store(&node->pn_child[0], PCTRIE_NULL, PCTRIE_UNSERIALIZED);
1217 struct pctrie_node *node;
1219 node = pctrie_root_load(ptree, NULL, PCTRIE_UNSERIALIZED);
1221 if (pctrie_isleaf(node)) {
1222 if (callback != NULL && node != PCTRIE_NULL)
1223 callback(pctrie_toptr(node, keyoff), arg);
1226 *pnode = node;
1264 struct pctrie_node *leaf, *parent, *node;
1271 node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED);
1274 if (pctrie_isleaf(node)) {
1275 if ((m = pctrie_toval(node)) != NULL && *m == index) {
1281 &parent->pn_child[slot], leaf,
1287 if (pctrie_keybarr(node, index, &slot))
1289 parent = node;
1290 node = pctrie_node_load(&node->pn_child[slot], NULL,
1298 * Show details about the given node.
1302 struct pctrie_node *node, *tmp;
1308 node = (struct pctrie_node *)addr;
1309 db_printf("node %p, owner %jx, children popmap %04x, level %u:\n",
1310 (void *)node, (uintmax_t)node->pn_owner, node->pn_popmap,
1311 node->pn_clev / PCTRIE_WIDTH);
1312 for (popmap = node->pn_popmap; popmap != 0; popmap ^= 1 << slot) {
1313 slot = ffs(popmap) - 1;
1314 tmp = pctrie_node_load(&node->pn_child[slot], NULL,
1319 node->pn_clev / PCTRIE_WIDTH);