libc/gen/ptree.c

81  * each node has two identities: its leaf identity and its branch identity.
82  * Each is separate from the other.  Every branch is tagged as to whether
83  * it points to a leaf or a branch.  This is not an attribute of the object
85  * the tag to determine whether it points to a leaf or branch identity, with
86  * branch identities having the low bit set.
88  * A node's branch identity has one rule: when traversing the tree from the
90  * the node's branch identity.  Of course, that has an exception: since to
91  * store N leaves, you need N-1 branches.  That one node whose branch identity
95  * which branch slot is used.  The bit length can be zero resulting in a
96  * one-way branch.  This happens in two special cases: the root and
102  * branch-node.  The mask becomes fixed in position in the tree.  The mask
191  * Move a branch identify from src to dst.  The leaves don't care since
200 	/* set branch bitlen and bitoff in one step.  */
211 	pt_node_t * const branch = PT_NODE(branch_node);
216 		    &PTN_BRANCH_SLOT(parent, ptree_testnode(pt, branch, parent));
248 		 * We need to find out who's pointing to mask's branch
250 		 * we must traverse the node's branch identity.
258 		 * Alas, mask was used as a branch.  Since the mask is becoming
259 		 * a one-way branch, we need make target take over mask's
284 	 * change mask from a leaf to a branch.
377 	 * In all likelyhood we are going simply going to insert a branch
397 		 * from a leaf to a one-way branch interior mask.
417 			 * branch interior mask node which has the other mask
430 			 * mask length, convert the left to a one-way branch
506 		 * If we aren't a leaf, we must be a branch.  Make sure we are
513 		 * Where is this branch?
527 		 * and the branch.  If the target's mask length is LEQ than
528 		 * this branch's bit offset, then this is where the mask needs
538 			 * both the target and the branch.  If the target's
541 			 * and the branch.
548 				 * one-way branch.
554 				 * They didn't match, so create a normal branch
703 	 * mask was a branch, that was done implicitly.
850 		 * If we are at the target, then we are looking at its branch
896 	 * If we didn't encounter target as branch, then target must be the
925 		 * branch identity.  We can't just move the target's branch
927 		 * to its own branch identity and that's fobidden.
936 		 * This gets so confusing.  The target's branch identity
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
952 			 * branch identiy.  This remove all references to his
953 			 * branch identity from the tree.  We then simply make
968 			 * If parent was a one-way branch, it must have been
997 		 * Parent was a one-way branch which is changing back to a leaf.
998 		 * Since parent is no longer a one-way branch, it can take over
1015 		 * branch identity with the surviving node.  This freeing
1031 		 * If target's branch identity contained its leaf identity, we
1033 		 * is no longer anything in the target's branch identiy that
1047 	 * If target wasn't used as a branch, then it must have been the
1048 	 * oddman-out of the tree (the one node that doesn't have a branch
1081 		const pt_node_t *branch;
1084 		branch = ptree_check_find_node2(pt, PT_NODE(node), target);
1085 		if (branch != NULL)
1086 			return branch;