Cross Reference: /src/common/lib/libc/gen/ptree.c

Lines Matching refs:parent
212 	pt_node_t *parent;
214 	for (parent = &pt->pt_rootnode;;) {
216 		    &PTN_BRANCH_SLOT(parent, ptree_testnode(pt, branch, parent));
221 		parent = PT_NODE(*nodep);
265 		 * However, it's possible that mask's parent is itself.  If
637 	pt_node_t *ptn, *parent;
645 	parent = &pt->pt_rootnode;
648 		const uintptr_t node = PTN_BRANCH_SLOT(parent, parent_slot);
678 		parent = ptn;
679 		parent_slot = ptree_testkey(pt, key, parent);
680 		bitoff += PTN_BRANCH_BITLEN(parent);
683 	KASSERT(PTN_ISROOT_P(pt, parent) || PTN_BRANCH_BITOFF(parent) + PTN_BRANCH_BITLEN(parent) == bitoff);
819 	pt_node_t *ptn, *parent;
837 	parent = &pt->pt_rootnode;
840 		node = PTN_BRANCH_SLOT(parent, parent_slot);
861 				PTN_BRANCH_SLOT(parent, parent_slot) =
868 			nodep = &PTN_BRANCH_SLOT(parent, parent_slot);
872 		 * We need also need to know who's pointing at our parent.
873 		 * After we remove ourselves from our parent, he'll only
875 		 * the pointer to the parent with our abandoned sibling.
877 		removep = &PTN_BRANCH_SLOT(parent, parent_slot);
882 		parent = ptn;
883 		parent_slot = ptree_testnode(pt, target, parent);
884 		bitoff += PTN_BRANCH_BITLEN(parent);
905 	KASSERT((removep == NULL) == (parent == &pt->pt_rootnode));
911 	if (__predict_false(PTN_ISROOT_P(pt, parent))) {
913 		KASSERT(parent == &pt->pt_rootnode);
921 	KASSERT((parent == target) == (removep == nodep));
922 	if (PTN_BRANCH(parent) == PTN_BRANCH_SLOT(target, PTN_BRANCH_POSITION(parent))) {
924 		 * The pointer to the parent actually lives in the target's
926 		 * identity since that would result in the parent pointing
929 		const pt_slot_t slot = PTN_BRANCH_POSITION(parent);
931 		const pt_bitlen_t parent_bitlen = PTN_BRANCH_BITLEN(parent);
933 		KASSERT(PTN_BRANCH_BITOFF(target) < PTN_BRANCH_BITOFF(parent));
937 		 * points to the branch identity of the parent of the target's
943 		 * So we can't move the target's branch identity to the parent
948 			 * The parent is a two-way branch.  We have to have
951 			 * our parent to where we are pointing to parent's
954 			 * the parent assume the target's branching duties.
962 			    PTN_BRANCH_SLOT(parent, parent_slot ^ PT_SLOT_OTHER);
963 			*nodep = ptree_move_branch(pt, parent, target);
968 			 * If parent was a one-way branch, it must have been
971 			 * parent back to a leaf node.  So in the same
972 			 * position that target pointed to parent, we place
973 			 * leaf pointer to parent.  In the other position,
978 			KASSERT(PTN_ISMASK_P(parent));
979 			KASSERT(slot == ptree_testnode(pt, parent, target));
980 			PTN_BRANCH_SLOT(parent, slot) = PTN_LEAF(parent);
981 			PTN_BRANCH_SLOT(parent, other_slot) =
983 			PTN_SET_LEAF_POSITION(parent,slot);
984 			PTN_SET_BRANCH_BITLEN(parent, 1);
986 		PTN_SET_BRANCH_BITOFF(parent, PTN_BRANCH_BITOFF(target));
987 		PTN_SET_BRANCH_POSITION(parent, PTN_BRANCH_POSITION(target));
989 		*nodep = PTN_BRANCH(parent);
995 	if (__predict_false(PTN_BRANCH_BITLEN(parent) == 0)) {
998 		 * Since parent is no longer a one-way branch, it can take over
1004 		KASSERT(PTN_ISMASK_P(parent));
1005 		KASSERT(parent != target);
1006 		*removep = PTN_LEAF(parent);
1012 		 * target's leaf identity is removed from the its parent,
1013 		 * that parent will only have one descendant.  So we can
1014 		 * just as easily replace the node that has the parent's
1016 		 * parent from its branching duties which means it can
1023 		uintptr_t other_node = PTN_BRANCH_SLOT(parent, other_slot);
1024 		const pt_slot_t target_slot = (parent == target ? branch_slot : leaf_slot);
1036 		if (parent == target) {
1049 	 * identity).  This makes parent the new oddman-out.
1053 		PTN_BRANCH_ODDMAN_SLOT(&pt->pt_rootnode) = PTN_LEAF(parent);
1059 	 * Finally move the target's branching duties to the parent.
1061 	KASSERT(PTN_BRANCH_BITOFF(parent) > PTN_BRANCH_BITOFF(target));
1062 	*nodep = ptree_move_branch(pt, parent, target);
1068 ptree_check_find_node2(const pt_tree_t *pt, const pt_node_t *parent,
1071 	const pt_bitlen_t slots = 1 << PTN_BRANCH_BITLEN(parent);
1075 		const uintptr_t node = PTN_BRANCH_SLOT(parent, slot);
1076 		if (PTN_BRANCH_SLOT(parent, slot) == node)
1077 			return parent;
1080 		const uintptr_t node = PTN_BRANCH_SLOT(parent, slot);
1093 ptree_check_leaf(const pt_tree_t *pt, const pt_node_t *parent,
1100 	const bool is_parent_root = (parent == &pt->pt_rootnode);
1105 		ok = ok && PTN_BRANCH_ODDMAN_SLOT(parent) == leaf_node;
1110 	if (is_mask && PTN_ISMASK_P(parent) && PTN_BRANCH_BITLEN(parent) == 0) {
1111 		ok = ok && PTN_MASK_BITLEN(parent) < mask_len;
1113 		ok = ok && PTN_BRANCH_BITOFF(parent) < mask_len;
1116 	ok = ok && PTN_BRANCH_SLOT(parent, leaf_position) == leaf_node;
1118 	ok = ok && leaf_position == ptree_testnode(pt, ptn, parent);
1130 ptree_check_branch(const pt_tree_t *pt, const pt_node_t *parent,
1133 	const bool is_parent_root = (parent == &pt->pt_rootnode);
1137 	const pt_bitoff_t parent_bitoff = PTN_BRANCH_BITOFF(parent);
1138 	const pt_bitoff_t parent_bitlen = PTN_BRANCH_BITLEN(parent);
1139 	const bool is_parent_mask = PTN_ISMASK_P(parent) && parent_bitlen == 0;
1141 	const pt_bitoff_t parent_mask_len = PTN_MASK_BITLEN(parent);
1147 	ok = ok && PTN_BRANCH_SLOT(parent, branch_slot) == PTN_BRANCH(ptn);
1149 	ok = ok && branch_slot == ptree_testnode(pt, ptn, parent);
1199 	const pt_node_t * const parent = &pt->pt_rootnode;
1203 	ok = ok && PTN_BRANCH_BITOFF(parent) == 0;
1204 	ok = ok && !PTN_ISMASK_P(parent);
1210 		ok = ok && ptree_check_leaf(pt, parent, ptn);
1212 		ok = ok && ptree_check_branch(pt, parent, ptn);