Lines Matching refs:pt
107 #define NODETOITEM(pt, ptn) \
108 ((void *)((uintptr_t)(ptn) - (pt)->pt_node_offset))
109 #define NODETOKEY(pt, ptn) \
110 ((void *)((uintptr_t)(ptn) - (pt)->pt_node_offset + pt->pt_key_offset))
111 #define ITEMTONODE(pt, ptn) \
112 ((pt_node_t *)((uintptr_t)(ptn) + (pt)->pt_node_offset))
115 #define PTREE_CHECK(pt) ptree_check(pt)
117 #define PTREE_CHECK(pt) do { } while (0)
121 ptree_matchnode(const pt_tree_t *pt, const pt_node_t *target,
125 return (*pt->pt_ops->ptto_matchnode)(NODETOKEY(pt, target),
126 (ptn != NULL ? NODETOKEY(pt, ptn) : NULL),
127 max_bitoff, bitoff_p, slots_p, pt->pt_context);
131 ptree_testnode(const pt_tree_t *pt, const pt_node_t *target,
137 return (*pt->pt_ops->ptto_testnode)(NODETOKEY(pt, target),
138 PTN_BRANCH_BITOFF(ptn), bitlen, pt->pt_context);
142 ptree_matchkey(const pt_tree_t *pt, const void *key,
145 return (*pt->pt_ops->ptto_matchkey)(key, NODETOKEY(pt, ptn),
146 bitoff, bitlen, pt->pt_context);
150 ptree_testkey(const pt_tree_t *pt, const void *key, const pt_node_t *ptn)
155 return (*pt->pt_ops->ptto_testkey)(key, PTN_BRANCH_BITOFF(ptn),
156 PTN_BRANCH_BITLEN(ptn), pt->pt_context);
169 ptree_init(pt_tree_t *pt, const pt_tree_ops_t *ops, void *context,
172 memset(pt, 0, sizeof(*pt));
173 pt->pt_node_offset = node_offset;
174 pt->pt_key_offset = key_offset;
175 pt->pt_context = context;
176 pt->pt_ops = ops;
196 ptree_move_branch(pt_tree_t * const pt, pt_node_t * const dst,
209 ptree_find_branch(pt_tree_t * const pt, uintptr_t branch_node)
214 for (parent = &pt->pt_rootnode;;) {
216 &PTN_BRANCH_SLOT(parent, ptree_testnode(pt, branch, parent));
226 ptree_insert_leaf_after_mask(pt_tree_t * const pt, pt_node_t * const target,
240 if (mask_node == PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode)) {
245 PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) = target_node;
252 uintptr_t * const mask_nodep = ptree_find_branch(pt, PTN_BRANCH(mask));
262 *mask_nodep = ptree_move_branch(pt, target, mask);
287 PTREE_CHECK(pt);
293 ptree_insert_mask_before_node(pt_tree_t * const pt, pt_node_t * const target,
321 PTREE_CHECK(pt);
328 ptree_insert_branch_at_node(pt_tree_t * const pt, pt_node_t * const target,
337 KASSERT((node == pt->pt_root) == (id->id_parent == &pt->pt_rootnode));
341 KASSERT(node == pt->pt_root || PTN_BRANCH_BITOFF(id->id_parent) + PTN_BRANCH_BITLEN(id->id_parent) <= id->id_bitoff);
354 PTREE_CHECK(pt);
359 ptree_insert_leaf(pt_tree_t * const pt, pt_node_t * const target,
382 matched = ptree_matchnode(pt, target, leaf, UINT_MAX,
446 return (*insertfunc)(pt, target, id);
450 ptree_insert_node_common(pt_tree_t *pt, void *item)
452 pt_node_t * const target = ITEMTONODE(pt, item);
463 if (target == PT_NODE(pt->pt_root))
470 if (__predict_false(PT_NULL_P(pt->pt_root))) {
471 PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode) = PTN_LEAF(target);
472 PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) = PTN_LEAF(target);
474 PTREE_CHECK(pt);
479 id.id_parent = &pt->pt_rootnode;
532 && (PTN_ISROOT_P(pt, id.id_parent)
544 || ptree_matchnode(pt, target, ptn, target_masklen,
570 && !ptree_matchnode(pt, target, ptn, branch_bitoff,
587 id.id_parent_slot = ptree_testnode(pt, target, id.id_parent);
595 return (*insertfunc)(pt, target, &id);
599 ptree_insert_node(pt_tree_t *pt, void *item)
601 pt_node_t * const target = ITEMTONODE(pt, item);
604 return ptree_insert_node_common(pt, target);
609 ptree_insert_mask_node(pt_tree_t *pt, void *item, pt_bitlen_t mask_len)
611 pt_node_t * const target = ITEMTONODE(pt, item);
621 if (!ptree_matchnode(pt, target, NULL, UINT_MAX, &bitoff, &slot))
625 return ptree_insert_node_common(pt, target);
630 ptree_find_filtered_node(pt_tree_t *pt, const void *key, pt_filter_t filter,
641 if (PT_NULL_P(PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode)))
645 parent = &pt->pt_rootnode;
660 if (!ptree_matchkey(pt, key, ptn, bitoff, branch_bitoff - bitoff)) {
663 return NODETOITEM(pt, mask);
673 || (*filter)(filter_arg, NODETOITEM(pt, ptn),
679 parent_slot = ptree_testkey(pt, key, parent);
683 KASSERT(PTN_ISROOT_P(pt, parent) || PTN_BRANCH_BITOFF(parent) + PTN_BRANCH_BITLEN(parent) == bitoff);
684 if (!filter || (*filter)(filter_arg, NODETOITEM(pt, ptn), at_mask ? PT_FILTER_MASK : 0)) {
689 return NODETOITEM(pt, ptn);
690 if (ptree_matchkey(pt, key, ptn, bitoff, mask_len - bitoff))
691 return NODETOITEM(pt, ptn);
694 if (ptree_matchkey(pt, key, ptn, bitoff, UINT_MAX))
695 return NODETOITEM(pt, ptn);
706 KASSERT(ptree_matchkey(pt, key, mask, 0, PTN_MASK_BITLEN(mask)));
707 return NODETOITEM(pt, mask);
718 ptree_iterate(pt_tree_t *pt, const void *item, pt_direction_t direction)
720 const pt_node_t * const target = ITEMTONODE(pt, item);
726 node = PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode);
734 return NODETOITEM(pt, ptn);
754 slot = ptree_testnode(pt, target, ptn);
785 return NODETOITEM(pt, PT_NODE(mask_node));
802 return NODETOITEM(pt, ptn);
810 return NODETOITEM(pt, PT_NODE(node));
814 ptree_remove_node(pt_tree_t *pt, void *item)
816 pt_node_t * const target = ITEMTONODE(pt, item);
829 if (PT_NULL_P(PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode))) {
830 KASSERT(!PT_NULL_P(PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode)));
837 parent = &pt->pt_rootnode;
864 PTREE_CHECK(pt);
883 parent_slot = ptree_testnode(pt, target, parent);
900 KASSERT(PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) == PTN_LEAF(target));
902 nodep = &PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode);
905 KASSERT((removep == NULL) == (parent == &pt->pt_rootnode));
911 if (__predict_false(PTN_ISROOT_P(pt, parent))) {
913 KASSERT(parent == &pt->pt_rootnode);
914 KASSERT(nodep == &PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode));
916 PTN_BRANCH_ROOT_SLOT(&pt->pt_rootnode) = PT_NULL;
917 PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) = PT_NULL;
963 *nodep = ptree_move_branch(pt, parent, target);
964 PTREE_CHECK(pt);
979 KASSERT(slot == ptree_testnode(pt, parent, target));
990 PTREE_CHECK(pt);
1041 PTREE_CHECK(pt);
1052 KASSERT(nodep == &PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode));
1053 PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) = PTN_LEAF(parent);
1054 PTREE_CHECK(pt);
1062 *nodep = ptree_move_branch(pt, parent, target);
1063 PTREE_CHECK(pt);
1068 ptree_check_find_node2(const pt_tree_t *pt, const pt_node_t *parent,
1084 branch = ptree_check_find_node2(pt, PT_NODE(node), target);
1093 ptree_check_leaf(const pt_tree_t *pt, const pt_node_t *parent,
1100 const bool is_parent_root = (parent == &pt->pt_rootnode);
1118 ok = ok && leaf_position == ptree_testnode(pt, ptn, parent);
1120 if (PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) != leaf_node) {
1123 ok = ok && ptn == ptree_check_find_node2(pt, ptn, PTN_LEAF(ptn));
1130 ptree_check_branch(const pt_tree_t *pt, const pt_node_t *parent,
1133 const bool is_parent_root = (parent == &pt->pt_rootnode);
1149 ok = ok && branch_slot == ptree_testnode(pt, ptn, parent);
1177 ok = ok && ptree_matchnode(pt, PT_NODE(node), ptn, bitoff, &tmp_bitoff, &tmp_slot);
1179 tmp_slot = ptree_testnode(pt, PT_NODE(node), ptn);
1184 ok = ok && ptree_check_leaf(pt, ptn, PT_NODE(node));
1186 ok = ok && ptree_check_branch(pt, ptn, PT_NODE(node));
1195 ptree_check(const pt_tree_t *pt)
1199 const pt_node_t * const parent = &pt->pt_rootnode;
1200 const uintptr_t node = pt->pt_root;
1210 ok = ok && ptree_check_leaf(pt, parent, ptn);
1212 ok = ok && ptree_check_branch(pt, parent, ptn);
1218 ptree_mask_node_p(pt_tree_t *pt, const void *item, pt_bitlen_t *lenp)
1220 const pt_node_t * const mask = ITEMTONODE(pt, item);
Indexes created Wed Oct 29 20:09:47 GMT 2025