libc/gen/ptree.c

213 	pt_node_t *parent;
215 	for (parent = &pt->pt_rootnode;;) {
217 		    &PTN_BRANCH_SLOT(parent, ptree_testnode(pt, branch, parent));
222 		parent = PT_NODE(*nodep);
266 		 * However, it's possible that mask's parent is itself.  If
638 	pt_node_t *ptn, *parent;
646 	parent = &pt->pt_rootnode;
649 		const uintptr_t node = PTN_BRANCH_SLOT(parent, parent_slot);
679 		parent = ptn;
680 		parent_slot = ptree_testkey(pt, key, parent);
681 		bitoff += PTN_BRANCH_BITLEN(parent);
684 	KASSERT(PTN_ISROOT_P(pt, parent) || PTN_BRANCH_BITOFF(parent) + PTN_BRANCH_BITLEN(parent) == bitoff);
820 	pt_node_t *ptn, *parent;
838 	parent = &pt->pt_rootnode;
841 		node = PTN_BRANCH_SLOT(parent, parent_slot);
862 				PTN_BRANCH_SLOT(parent, parent_slot) =
869 			nodep = &PTN_BRANCH_SLOT(parent, parent_slot);
873 		 * We need also need to know who's pointing at our parent.
874 		 * After we remove ourselves from our parent, he'll only
876 		 * the pointer to the parent with our abadoned sibling.
878 		removep = &PTN_BRANCH_SLOT(parent, parent_slot);
883 		parent = ptn;
884 		parent_slot = ptree_testnode(pt, target, parent);
885 		bitoff += PTN_BRANCH_BITLEN(parent);
906 	KASSERT((removep == NULL) == (parent == &pt->pt_rootnode));
912 	if (__predict_false(PTN_ISROOT_P(pt, parent))) {
914 		KASSERT(parent == &pt->pt_rootnode);
922 	KASSERT((parent == target) == (removep == nodep));
923 	if (PTN_BRANCH(parent) == PTN_BRANCH_SLOT(target, PTN_BRANCH_POSITION(parent))) {
925 		 * The pointer to the parent actually lives in the target's
927 		 * identity since that would result in the parent pointing
930 		const pt_slot_t slot = PTN_BRANCH_POSITION(parent);
932 		const pt_bitlen_t parent_bitlen = PTN_BRANCH_BITLEN(parent);
934 		KASSERT(PTN_BRANCH_BITOFF(target) < PTN_BRANCH_BITOFF(parent));
938 		 * points to the branch identity of the parent of the target's
944 		 * So we can't move the target's branch identity to the parent
949 			 * The parent is a two-way branch.  We have to have
952 			 * our parent to where we are pointing to parent's
955 			 * the parent assume the target's branching duties.
963 			    PTN_BRANCH_SLOT(parent, parent_slot ^ PT_SLOT_OTHER);
964 			*nodep = ptree_move_branch(pt, parent, target);
969 			 * If parent was a one-way branch, it must have been
972 			 * parent back to a leaf node.  So in the same
973 			 * position that target pointed to parent, we place
974 			 * leaf pointer to parent.  In the other position,
979 			KASSERT(PTN_ISMASK_P(parent));
980 			KASSERT(slot == ptree_testnode(pt, parent, target));
981 			PTN_BRANCH_SLOT(parent, slot) = PTN_LEAF(parent);
982 			PTN_BRANCH_SLOT(parent, other_slot) =
984 			PTN_SET_LEAF_POSITION(parent,slot);
985 			PTN_SET_BRANCH_BITLEN(parent, 1);
987 		PTN_SET_BRANCH_BITOFF(parent, PTN_BRANCH_BITOFF(target));
988 		PTN_SET_BRANCH_POSITION(parent, PTN_BRANCH_POSITION(target));
990 		*nodep = PTN_BRANCH(parent);
996 	if (__predict_false(PTN_BRANCH_BITLEN(parent) == 0)) {
999 		 * Since parent is no longer a one-way branch, it can take over
1005 		KASSERT(PTN_ISMASK_P(parent));
1006 		KASSERT(parent != target);
1007 		*removep = PTN_LEAF(parent);
1013 		 * target's leaf identity is removed from the its parent,
1014 		 * that parent will only have one decendent.  So we can
1015 		 * just as easily replace the node that has the parent's
1017 		 * parent from its branching duties which means it can
1024 		uintptr_t other_node = PTN_BRANCH_SLOT(parent, other_slot);
1025 		const pt_slot_t target_slot = (parent == target ? branch_slot : leaf_slot);
1037 		if (parent == target) {
1050 	 * identity).  This makes parent the new oddman-out.
1054 		PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) = PTN_LEAF(parent);
1060 	 * Finally move the target's branching duties to the parent.
1062 	KASSERT(PTN_BRANCH_BITOFF(parent) > PTN_BRANCH_BITOFF(target));
1063 	*nodep = ptree_move_branch(pt, parent, target);
1069 ptree_check_find_node2(const pt_tree_t *pt, const pt_node_t *parent,
1072 	const pt_bitlen_t slots = 1 << PTN_BRANCH_BITLEN(parent);
1076 		const uintptr_t node = PTN_BRANCH_SLOT(parent, slot);
1077 		if (PTN_BRANCH_SLOT(parent, slot) == node)
1078 			return parent;
1081 		const uintptr_t node = PTN_BRANCH_SLOT(parent, slot);
1094 ptree_check_leaf(const pt_tree_t *pt, const pt_node_t *parent,
1101 	const bool is_parent_root = (parent == &pt->pt_rootnode);
1106 		ok = ok && PTN_BRANCH_ODDMAN_SLOT(parent) == leaf_node;
1111 	if (is_mask && PTN_ISMASK_P(parent) && PTN_BRANCH_BITLEN(parent) == 0) {
1112 		ok = ok && PTN_MASK_BITLEN(parent) < mask_len;
1114 		ok = ok && PTN_BRANCH_BITOFF(parent) < mask_len;
1117 	ok = ok && PTN_BRANCH_SLOT(parent, leaf_position) == leaf_node;
1119 	ok = ok && leaf_position == ptree_testnode(pt, ptn, parent);
1131 ptree_check_branch(const pt_tree_t *pt, const pt_node_t *parent,
1134 	const bool is_parent_root = (parent == &pt->pt_rootnode);
1138 	const pt_bitoff_t parent_bitoff = PTN_BRANCH_BITOFF(parent);
1139 	const pt_bitoff_t parent_bitlen = PTN_BRANCH_BITLEN(parent);
1140 	const bool is_parent_mask = PTN_ISMASK_P(parent) && parent_bitlen == 0;
1142 	const pt_bitoff_t parent_mask_len = PTN_MASK_BITLEN(parent);
1148 	ok = ok && PTN_BRANCH_SLOT(parent, branch_slot) == PTN_BRANCH(ptn);
1150 	ok = ok && branch_slot == ptree_testnode(pt, ptn, parent);
1200 	const pt_node_t * const parent = &pt->pt_rootnode;
1204 	ok = ok && PTN_BRANCH_BITOFF(parent) == 0;
1205 	ok = ok && !PTN_ISMASK_P(parent);
1211 		ok = ok && ptree_check_leaf(pt, parent, ptn);
1213 		ok = ok && ptree_check_branch(pt, parent, ptn);