Initial source

1 files changed, 920 insertions, 0 deletions

diff --git a/ipc/ipc_splay.c b/ipc/ipc_splay.c
new file mode 100644
index 0000000..6fb5bcb
--- /dev/null
+++ b/ipc/ipc_splay.c
@@ -0,0 +1,920 @@
+/* 
+ * Mach Operating System
+ * Copyright (c) 1991,1990,1989 Carnegie Mellon University
+ * All Rights Reserved.
+ * 
+ * Permission to use, copy, modify and distribute this software and its
+ * documentation is hereby granted, provided that both the copyright
+ * notice and this permission notice appear in all copies of the
+ * software, derivative works or modified versions, and any portions
+ * thereof, and that both notices appear in supporting documentation.
+ * 
+ * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
+ * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
+ * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
+ * 
+ * Carnegie Mellon requests users of this software to return to
+ * 
+ *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
+ *  School of Computer Science
+ *  Carnegie Mellon University
+ *  Pittsburgh PA 15213-3890
+ * 
+ * any improvements or extensions that they make and grant Carnegie Mellon
+ * the rights to redistribute these changes.
+ */
+/*
+ */
+/*
+ *	File:	ipc/ipc_splay.c
+ *	Author:	Rich Draves
+ *	Date:	1989
+ *
+ *	Primitive splay tree operations.
+ */
+
+#include <mach/port.h>
+#include <kern/assert.h>
+#include <kern/macro_help.h>
+#include <ipc/ipc_entry.h>
+#include <ipc/ipc_splay.h>
+
+/*
+ *	Splay trees are self-adjusting binary search trees.
+ *	They have the following attractive properties:
+ *		1) Space efficient; only two pointers per entry.
+ *		2) Robust performance; amortized O(log n) per operation.
+ *		3) Recursion not needed.
+ *	This makes them a good fall-back data structure for those
+ *	entries that don't fit into the lookup table.
+ *
+ *	The paper by Sleator and Tarjan, JACM v. 32, no. 3, pp. 652-686,
+ *	describes the splaying operation.  ipc_splay_prim_lookup
+ *	and ipc_splay_prim_assemble implement the top-down splay
+ *	described on p. 669.
+ *
+ *	The tree is stored in an unassembled form.  If ist_root is null,
+ *	then the tree has no entries.  Otherwise, ist_name records
+ *	the value used for the last lookup.  ist_root points to the
+ *	middle tree obtained from the top-down splay.  ist_ltree and
+ *	ist_rtree point to left and right subtrees, whose entries
+ *	are all smaller (larger) than those in the middle tree.
+ *	ist_ltreep and ist_rtreep are pointers to fields in the
+ *	left and right subtrees.  ist_ltreep points to the rchild field
+ *	of the largest entry in ltree, and ist_rtreep points to the
+ *	lchild field of the smallest entry in rtree.  The pointed-to
+ *	fields aren't initialized.  If the left (right) subtree is null,
+ *	then ist_ltreep (ist_rtreep) points to the ist_ltree (ist_rtree)
+ *	field in the splay structure itself.
+ *
+ *	The primary advantage of the unassembled form is that repeated
+ *	unsuccessful lookups are efficient.  In particular, an unsuccessful
+ *	lookup followed by an insert only requires one splaying operation.
+ *
+ *	The traversal algorithm works via pointer inversion.
+ *	When descending down the tree, child pointers are reversed
+ *	to point back to the parent entry.  When ascending,
+ *	the pointers are restored to their original value.
+ *
+ *	The biggest potential problem with the splay tree implementation
+ *	is that the operations, even lookup, require an exclusive lock.
+ *	If IPC spaces are protected with exclusive locks, then
+ *	the splay tree doesn't require its own lock, and ist_lock/ist_unlock
+ *	needn't do anything.  If IPC spaces are protected with read/write
+ *	locks then ist_lock/ist_unlock should provide exclusive access.
+ *
+ *	If it becomes important to let lookups run in parallel,
+ *	or if the restructuring makes lookups too expensive, then
+ *	there is hope.  Use a read/write lock on the splay tree.
+ *	Keep track of the number of entries in the tree.  When doing
+ *	a lookup, first try a non-restructuring lookup with a read lock held,
+ *	with a bound (based on log of size of the tree) on the number of
+ *	entries to traverse.  If the lookup runs up against the bound,
+ *	then take a write lock and do a reorganizing lookup.
+ *	This way, if lookups only access roughly balanced parts
+ *	of the tree, then lookups run in parallel and do no restructuring.
+ *
+ *	The traversal algorithm currently requires an exclusive lock.
+ *	If that is a problem, the tree could be changed from an lchild/rchild
+ *	representation to a leftmost child/right sibling representation.
+ *	In conjunction with non-restructing lookups, this would let
+ *	lookups and traversals all run in parallel.  But this representation
+ *	is more complicated and would slow down the operations.
+ */
+
+/*
+ *	Boundary values to hand to ipc_splay_prim_lookup:
+ */
+
+#define	MACH_PORT_SMALLEST	((mach_port_t) 0)
+#define MACH_PORT_LARGEST	((mach_port_t) ~0)
+
+/*
+ *	Routine:	ipc_splay_prim_lookup
+ *	Purpose:
+ *		Searches for the node labeled name in the splay tree.
+ *		Returns three nodes (treep, ltreep, rtreep) and
+ *		two pointers to nodes (ltreepp, rtreepp).
+ *
+ *		ipc_splay_prim_lookup splits the supplied tree into
+ *		three subtrees, left, middle, and right, returned
+ *		in ltreep, treep, and rtreep.
+ *
+ *		If name is present in the tree, then it is at
+ *		the root of the middle tree.  Otherwise, the root
+ *		of the middle tree is the last node traversed.
+ *
+ *		ipc_splay_prim_lookup returns a pointer into
+ *		the left subtree, to the rchild field of its
+ *		largest node, in ltreepp.  It returns a pointer
+ *		into the right subtree, to the lchild field of its
+ *		smallest node, in rtreepp.
+ */
+
+static void
+ipc_splay_prim_lookup(
+	mach_port_t		name,
+	ipc_tree_entry_t	tree,
+	ipc_tree_entry_t	*treep,
+	ipc_tree_entry_t	*ltreep,
+	ipc_tree_entry_t	**ltreepp,
+	ipc_tree_entry_t	*rtreep,
+	ipc_tree_entry_t	**rtreepp)
+{
+	mach_port_t tname;			/* temp name */
+	ipc_tree_entry_t lchild, rchild;	/* temp child pointers */
+
+	assert(tree != ITE_NULL);
+
+#define	link_left					\
+MACRO_BEGIN						\
+	*ltreep = tree;					\
+	ltreep = &tree->ite_rchild;			\
+	tree = *ltreep;					\
+MACRO_END
+
+#define	link_right					\
+MACRO_BEGIN						\
+	*rtreep = tree;					\
+	rtreep = &tree->ite_lchild;			\
+	tree = *rtreep;					\
+MACRO_END
+
+#define rotate_left					\
+MACRO_BEGIN						\
+	ipc_tree_entry_t temp = tree;			\
+							\
+	tree = temp->ite_rchild;			\
+	temp->ite_rchild = tree->ite_lchild;		\
+	tree->ite_lchild = temp;			\
+MACRO_END
+
+#define rotate_right					\
+MACRO_BEGIN						\
+	ipc_tree_entry_t temp = tree;			\
+							\
+	tree = temp->ite_lchild;			\
+	temp->ite_lchild = tree->ite_rchild;		\
+	tree->ite_rchild = temp;			\
+MACRO_END
+
+	while (name != (tname = tree->ite_name)) {
+		if (name < tname) {
+			/* descend to left */
+
+			lchild = tree->ite_lchild;
+			if (lchild == ITE_NULL)
+				break;
+			tname = lchild->ite_name;
+
+			if ((name < tname) &&
+			    (lchild->ite_lchild != ITE_NULL))
+				rotate_right;
+			link_right;
+			if ((name > tname) &&
+			    (lchild->ite_rchild != ITE_NULL))
+				link_left;
+		} else {
+			/* descend to right */
+
+			rchild = tree->ite_rchild;
+			if (rchild == ITE_NULL)
+				break;
+			tname = rchild->ite_name;
+
+			if ((name > tname) &&
+			    (rchild->ite_rchild != ITE_NULL))
+				rotate_left;
+			link_left;
+			if ((name < tname) &&
+			    (rchild->ite_lchild != ITE_NULL))
+				link_right;
+		}
+
+		assert(tree != ITE_NULL);
+	}
+
+	*treep = tree;
+	*ltreepp = ltreep;
+	*rtreepp = rtreep;
+
+#undef	link_left
+#undef	link_right
+#undef	rotate_left
+#undef	rotate_right
+}
+
+/*
+ *	Routine:	ipc_splay_prim_assemble
+ *	Purpose:
+ *		Assembles the results of ipc_splay_prim_lookup
+ *		into a splay tree with the found node at the root.
+ *
+ *		ltree and rtree are by-reference so storing
+ *		through ltreep and rtreep can change them.
+ */
+
+static void
+ipc_splay_prim_assemble(
+	ipc_tree_entry_t	tree,
+	ipc_tree_entry_t	*ltree,
+	ipc_tree_entry_t	*ltreep,
+	ipc_tree_entry_t	*rtree,
+	ipc_tree_entry_t	*rtreep)
+{
+	assert(tree != ITE_NULL);
+
+	*ltreep = tree->ite_lchild;
+	*rtreep = tree->ite_rchild;
+
+	tree->ite_lchild = *ltree;
+	tree->ite_rchild = *rtree;
+}
+
+/*
+ *	Routine:	ipc_splay_tree_init
+ *	Purpose:
+ *		Initialize a raw splay tree for use.
+ */
+
+void
+ipc_splay_tree_init(
+	ipc_splay_tree_t	splay)
+{
+	splay->ist_root = ITE_NULL;
+}
+
+/*
+ *	Routine:	ipc_splay_tree_pick
+ *	Purpose:
+ *		Picks and returns a random entry in a splay tree.
+ *		Returns FALSE if the splay tree is empty.
+ */
+
+boolean_t
+ipc_splay_tree_pick(
+	ipc_splay_tree_t	splay,
+	mach_port_t		*namep,
+	ipc_tree_entry_t	*entryp)
+{
+	ipc_tree_entry_t root;
+
+	ist_lock(splay);
+
+	root = splay->ist_root;
+	if (root != ITE_NULL) {
+		*namep = root->ite_name;
+		*entryp = root;
+	}
+
+	ist_unlock(splay);
+
+	return root != ITE_NULL;
+}
+
+/*
+ *	Routine:	ipc_splay_tree_lookup
+ *	Purpose:
+ *		Finds an entry in a splay tree.
+ *		Returns ITE_NULL if not found.
+ */
+
+ipc_tree_entry_t
+ipc_splay_tree_lookup(
+	ipc_splay_tree_t	splay,
+	mach_port_t		name)
+{
+	ipc_tree_entry_t root;
+
+	ist_lock(splay);
+
+	root = splay->ist_root;
+	if (root != ITE_NULL) {
+		if (splay->ist_name != name) {
+			ipc_splay_prim_assemble(root,
+				&splay->ist_ltree, splay->ist_ltreep,
+				&splay->ist_rtree, splay->ist_rtreep);
+			ipc_splay_prim_lookup(name, root, &root,
+				&splay->ist_ltree, &splay->ist_ltreep,
+				&splay->ist_rtree, &splay->ist_rtreep);
+			splay->ist_name = name;
+			splay->ist_root = root;
+		}
+
+		if (name != root->ite_name)
+			root = ITE_NULL;
+	}
+
+	ist_unlock(splay);
+
+	return root;
+}
+
+/*
+ *	Routine:	ipc_splay_tree_insert
+ *	Purpose:
+ *		Inserts a new entry into a splay tree.
+ *		The caller supplies a new entry.
+ *		The name can't already be present in the tree.
+ */
+
+void
+ipc_splay_tree_insert(
+	ipc_splay_tree_t	splay,
+	mach_port_t		name,
+	ipc_tree_entry_t	entry)
+{
+	ipc_tree_entry_t root;
+
+	assert(entry != ITE_NULL);
+
+	ist_lock(splay);
+
+	root = splay->ist_root;
+	if (root == ITE_NULL) {
+		entry->ite_lchild = ITE_NULL;
+		entry->ite_rchild = ITE_NULL;
+	} else {
+		if (splay->ist_name != name) {
+			ipc_splay_prim_assemble(root,
+				&splay->ist_ltree, splay->ist_ltreep,
+				&splay->ist_rtree, splay->ist_rtreep);
+			ipc_splay_prim_lookup(name, root, &root,
+				&splay->ist_ltree, &splay->ist_ltreep,
+				&splay->ist_rtree, &splay->ist_rtreep);
+		}
+
+		assert(root->ite_name != name);
+
+		if (name < root->ite_name) {
+			assert(root->ite_lchild == ITE_NULL);
+
+			*splay->ist_ltreep = ITE_NULL;
+			*splay->ist_rtreep = root;
+		} else {
+			assert(root->ite_rchild == ITE_NULL);
+
+			*splay->ist_ltreep = root;
+			*splay->ist_rtreep = ITE_NULL;
+		}
+
+		entry->ite_lchild = splay->ist_ltree;
+		entry->ite_rchild = splay->ist_rtree;
+	}
+
+	entry->ite_name = name;
+	splay->ist_root = entry;
+	splay->ist_name = name;
+	splay->ist_ltreep = &splay->ist_ltree;
+	splay->ist_rtreep = &splay->ist_rtree;
+
+	ist_unlock(splay);
+}
+
+/*
+ *	Routine:	ipc_splay_tree_delete
+ *	Purpose:
+ *		Deletes an entry from a splay tree.
+ *		The name must be present in the tree.
+ *		Frees the entry.
+ *
+ *		The "entry" argument isn't currently used.
+ *		Other implementations might want it, though.
+ */
+
+void
+ipc_splay_tree_delete(
+	ipc_splay_tree_t	splay,
+	mach_port_t		name,
+	ipc_tree_entry_t	entry)
+{
+	ipc_tree_entry_t root, saved;
+
+	ist_lock(splay);
+
+	root = splay->ist_root;
+	assert(root != ITE_NULL);
+
+	if (splay->ist_name != name) {
+		ipc_splay_prim_assemble(root,
+			&splay->ist_ltree, splay->ist_ltreep,
+			&splay->ist_rtree, splay->ist_rtreep);
+		ipc_splay_prim_lookup(name, root, &root,
+			&splay->ist_ltree, &splay->ist_ltreep,
+			&splay->ist_rtree, &splay->ist_rtreep);
+	}
+
+	assert(root->ite_name == name);
+	assert(root == entry);
+
+	*splay->ist_ltreep = root->ite_lchild;
+	*splay->ist_rtreep = root->ite_rchild;
+	ite_free(root);
+
+	root = splay->ist_ltree;
+	saved = splay->ist_rtree;
+
+	if (root == ITE_NULL)
+		root = saved;
+	else if (saved != ITE_NULL) {
+		/*
+		 *	Find the largest node in the left subtree, and splay it
+		 *	to the root.  Then add the saved right subtree.
+		 */
+
+		ipc_splay_prim_lookup(MACH_PORT_LARGEST, root, &root,
+			&splay->ist_ltree, &splay->ist_ltreep,
+			&splay->ist_rtree, &splay->ist_rtreep);
+		ipc_splay_prim_assemble(root,
+			&splay->ist_ltree, splay->ist_ltreep,
+			&splay->ist_rtree, splay->ist_rtreep);
+
+		assert(root->ite_rchild == ITE_NULL);
+		root->ite_rchild = saved;
+	}
+
+	splay->ist_root = root;
+	if (root != ITE_NULL) {
+		splay->ist_name = root->ite_name;
+		splay->ist_ltreep = &splay->ist_ltree;
+		splay->ist_rtreep = &splay->ist_rtree;
+	}
+
+	ist_unlock(splay);
+}
+
+/*
+ *	Routine:	ipc_splay_tree_split
+ *	Purpose:
+ *		Split a splay tree.  Puts all entries smaller than "name"
+ *		into a new tree, "small".
+ *
+ *		Doesn't do locking on "small", because nobody else
+ *		should be fiddling with the uninitialized tree.
+ */
+
+void
+ipc_splay_tree_split(
+	ipc_splay_tree_t	splay,
+	mach_port_t		name,
+	ipc_splay_tree_t	small)
+{
+	ipc_tree_entry_t root;
+
+	ipc_splay_tree_init(small);
+
+	ist_lock(splay);
+
+	root = splay->ist_root;
+	if (root != ITE_NULL) {
+		/* lookup name, to get it (or last traversed) to the top */
+
+		if (splay->ist_name != name) {
+			ipc_splay_prim_assemble(root,
+				&splay->ist_ltree, splay->ist_ltreep,
+				&splay->ist_rtree, splay->ist_rtreep);
+			ipc_splay_prim_lookup(name, root, &root,
+				&splay->ist_ltree, &splay->ist_ltreep,
+				&splay->ist_rtree, &splay->ist_rtreep);
+		}
+
+		if (root->ite_name < name) {
+			/* root goes into small */
+
+			*splay->ist_ltreep = root->ite_lchild;
+			*splay->ist_rtreep = ITE_NULL;
+			root->ite_lchild = splay->ist_ltree;
+			assert(root->ite_rchild == ITE_NULL);
+
+			small->ist_root = root;
+			small->ist_name = root->ite_name;
+			small->ist_ltreep = &small->ist_ltree;
+			small->ist_rtreep = &small->ist_rtree;
+
+			/* rtree goes into splay */
+
+			root = splay->ist_rtree;
+			splay->ist_root = root;
+			if (root != ITE_NULL) {
+				splay->ist_name = root->ite_name;
+				splay->ist_ltreep = &splay->ist_ltree;
+				splay->ist_rtreep = &splay->ist_rtree;
+			}
+		} else {
+			/* root stays in splay */
+
+			*splay->ist_ltreep = root->ite_lchild;
+			root->ite_lchild = ITE_NULL;
+
+			splay->ist_root = root;
+			splay->ist_name = name;
+			splay->ist_ltreep = &splay->ist_ltree;
+
+			/* ltree goes into small */
+
+			root = splay->ist_ltree;
+			small->ist_root = root;
+			if (root != ITE_NULL) {
+				small->ist_name = root->ite_name;
+				small->ist_ltreep = &small->ist_ltree;
+				small->ist_rtreep = &small->ist_rtree;
+			}
+		}		
+	}
+
+	ist_unlock(splay);
+}
+
+/*
+ *	Routine:	ipc_splay_tree_join
+ *	Purpose:
+ *		Joins two splay trees.  Merges the entries in "small",
+ *		which must all be smaller than the entries in "splay",
+ *		into "splay".
+ */
+
+void
+ipc_splay_tree_join(
+	ipc_splay_tree_t	splay,
+	ipc_splay_tree_t	small)
+{
+	ipc_tree_entry_t sroot;
+
+	/* pull entries out of small */
+
+	ist_lock(small);
+
+	sroot = small->ist_root;
+	if (sroot != ITE_NULL) {
+		ipc_splay_prim_assemble(sroot,
+			&small->ist_ltree, small->ist_ltreep,
+			&small->ist_rtree, small->ist_rtreep);
+		small->ist_root = ITE_NULL;
+	}
+
+	ist_unlock(small);
+
+	/* put entries, if any, into splay */
+
+	if (sroot != ITE_NULL) {
+		ipc_tree_entry_t root;
+
+		ist_lock(splay);
+
+		root = splay->ist_root;
+		if (root == ITE_NULL) {
+			root = sroot;
+		} else {
+			/* get smallest entry in splay tree to top */
+
+			if (splay->ist_name != MACH_PORT_SMALLEST) {
+				ipc_splay_prim_assemble(root,
+					&splay->ist_ltree, splay->ist_ltreep,
+					&splay->ist_rtree, splay->ist_rtreep);
+				ipc_splay_prim_lookup(MACH_PORT_SMALLEST,
+					root, &root,
+					&splay->ist_ltree, &splay->ist_ltreep,
+					&splay->ist_rtree, &splay->ist_rtreep);
+			}
+
+			ipc_splay_prim_assemble(root,
+				&splay->ist_ltree, splay->ist_ltreep,
+				&splay->ist_rtree, splay->ist_rtreep);
+
+			assert(root->ite_lchild == ITE_NULL);
+			assert(sroot->ite_name < root->ite_name);
+			root->ite_lchild = sroot;
+		}
+
+		splay->ist_root = root;
+		splay->ist_name = root->ite_name;
+		splay->ist_ltreep = &splay->ist_ltree;
+		splay->ist_rtreep = &splay->ist_rtree;
+
+		ist_unlock(splay);
+	}
+}
+
+/*
+ *	Routine:	ipc_splay_tree_bounds
+ *	Purpose:
+ *		Given a name, returns the largest value present
+ *		in the tree that is smaller than or equal to the name,
+ *		or ~0 if no such value exists.  Similarly, returns
+ *		the smallest value present that is greater than or
+ *		equal to the name, or 0 if no such value exists.
+ *
+ *		Hence, if
+ *		lower = upper, then lower = name = upper
+ *				and name is present in the tree
+ *		lower = ~0 and upper = 0,
+ *				then the tree is empty
+ *		lower = ~0 and upper > 0, then name < upper
+ *				and upper is smallest value in tree
+ *		lower < ~0 and upper = 0, then lower < name
+ *				and lower is largest value in tree
+ *		lower < ~0 and upper > 0, then lower < name < upper
+ *				and they are tight bounds on name
+ *
+ *		(Note MACH_PORT_SMALLEST = 0 and MACH_PORT_LARGEST = ~0.)
+ */
+
+void
+ipc_splay_tree_bounds(
+	ipc_splay_tree_t	splay,
+	mach_port_t		name,
+	mach_port_t		*lowerp, 
+	mach_port_t		*upperp)
+{
+	ipc_tree_entry_t root;
+
+	ist_lock(splay);
+
+	root = splay->ist_root;
+	if (root == ITE_NULL) {
+		*lowerp = MACH_PORT_LARGEST;
+		*upperp = MACH_PORT_SMALLEST;
+	} else {
+		mach_port_t rname;
+
+		if (splay->ist_name != name) {
+			ipc_splay_prim_assemble(root,
+				&splay->ist_ltree, splay->ist_ltreep,
+				&splay->ist_rtree, splay->ist_rtreep);
+			ipc_splay_prim_lookup(name, root, &root,
+				&splay->ist_ltree, &splay->ist_ltreep,
+				&splay->ist_rtree, &splay->ist_rtreep);
+			splay->ist_name = name;
+			splay->ist_root = root;
+		}
+
+		rname = root->ite_name;
+
+		/*
+		 *	OK, it's a hack.  We convert the ltreep and rtreep
+		 *	pointers back into real entry pointers,
+		 *	so we can pick the names out of the entries.
+		 */
+
+		if (rname <= name)
+			*lowerp = rname;
+		else if (splay->ist_ltreep == &splay->ist_ltree)
+			*lowerp = MACH_PORT_LARGEST;
+		else {
+			ipc_tree_entry_t entry;
+
+			entry = (ipc_tree_entry_t)
+				((char *)splay->ist_ltreep -
+				 ((char *)&root->ite_rchild -
+				  (char *)root));
+			*lowerp = entry->ite_name;
+		}
+
+		if (rname >= name)
+			*upperp = rname;
+		else if (splay->ist_rtreep == &splay->ist_rtree)
+			*upperp = MACH_PORT_SMALLEST;
+		else {
+			ipc_tree_entry_t entry;
+
+			entry = (ipc_tree_entry_t)
+				((char *)splay->ist_rtreep -
+				 ((char *)&root->ite_lchild -
+				  (char *)root));
+			*upperp = entry->ite_name;
+		}
+	}
+
+	ist_unlock(splay);
+}
+
+/*
+ *	Routine:	ipc_splay_traverse_start
+ *	Routine:	ipc_splay_traverse_next
+ *	Routine:	ipc_splay_traverse_finish
+ *	Purpose:
+ *		Perform a symmetric order traversal of a splay tree.
+ *	Usage:
+ *		for (entry = ipc_splay_traverse_start(splay);
+ *		     entry != ITE_NULL;
+ *		     entry = ipc_splay_traverse_next(splay, delete)) {
+ *			do something with entry
+ *		}
+ *		ipc_splay_traverse_finish(splay);
+ *
+ *		If "delete" is TRUE, then the current entry
+ *		is removed from the tree and deallocated.
+ *
+ *		During the traversal, the splay tree is locked.
+ */
+
+ipc_tree_entry_t
+ipc_splay_traverse_start(
+	ipc_splay_tree_t	splay)
+{
+	ipc_tree_entry_t current, parent;
+
+	ist_lock(splay);
+
+	current = splay->ist_root;
+	if (current != ITE_NULL) {
+		ipc_splay_prim_assemble(current,
+			&splay->ist_ltree, splay->ist_ltreep,
+			&splay->ist_rtree, splay->ist_rtreep);
+
+		parent = ITE_NULL;
+
+		while (current->ite_lchild != ITE_NULL) {
+			ipc_tree_entry_t next;
+
+			next = current->ite_lchild;
+			current->ite_lchild = parent;
+			parent = current;
+			current = next;
+		}
+
+		splay->ist_ltree = current;
+		splay->ist_rtree = parent;
+	}
+
+	return current;
+}
+
+ipc_tree_entry_t
+ipc_splay_traverse_next(
+	ipc_splay_tree_t	splay,
+	boolean_t		delete)
+{
+	ipc_tree_entry_t current, parent;
+
+	/* pick up where traverse_entry left off */
+
+	current = splay->ist_ltree;
+	parent = splay->ist_rtree;
+	assert(current != ITE_NULL);
+
+	if (!delete)
+		goto traverse_right;
+
+	/* we must delete current and patch the tree */
+
+	if (current->ite_lchild == ITE_NULL) {
+		if (current->ite_rchild == ITE_NULL) {
+			/* like traverse_back, but with deletion */
+
+			if (parent == ITE_NULL) {
+				ite_free(current);
+
+				splay->ist_root = ITE_NULL;
+				return ITE_NULL;
+			}
+
+			if (current->ite_name < parent->ite_name) {
+				ite_free(current);
+
+				current = parent;
+				parent = current->ite_lchild;
+				current->ite_lchild = ITE_NULL;
+				goto traverse_entry;
+			} else {
+				ite_free(current);
+
+				current = parent;
+				parent = current->ite_rchild;
+				current->ite_rchild = ITE_NULL;
+				goto traverse_back;
+			}
+		} else {
+			ipc_tree_entry_t prev;
+
+			prev = current;
+			current = current->ite_rchild;
+			ite_free(prev);
+			goto traverse_left;
+		}
+	} else {
+		if (current->ite_rchild == ITE_NULL) {
+			ipc_tree_entry_t prev;
+
+			prev = current;
+			current = current->ite_lchild;
+			ite_free(prev);
+			goto traverse_back;
+		} else {
+			ipc_tree_entry_t prev;
+			ipc_tree_entry_t ltree, rtree;
+			ipc_tree_entry_t *ltreep, *rtreep;
+
+			/* replace current with largest of left children */
+
+			prev = current;
+			ipc_splay_prim_lookup(MACH_PORT_LARGEST,
+				current->ite_lchild, &current,
+				&ltree, &ltreep, &rtree, &rtreep);
+			ipc_splay_prim_assemble(current,
+				&ltree, ltreep, &rtree, rtreep);
+
+			assert(current->ite_rchild == ITE_NULL);
+			current->ite_rchild = prev->ite_rchild;
+			ite_free(prev);
+			goto traverse_right;
+		}
+	}
+	/*NOTREACHED*/
+
+	/*
+	 *	A state machine:  for each entry, we
+	 *		1) traverse left subtree
+	 *		2) traverse the entry
+	 *		3) traverse right subtree
+	 *		4) traverse back to parent
+	 */
+
+    traverse_left:
+	if (current->ite_lchild != ITE_NULL) {
+		ipc_tree_entry_t next;
+
+		next = current->ite_lchild;
+		current->ite_lchild = parent;
+		parent = current;
+		current = next;
+		goto traverse_left;
+	}
+
+    traverse_entry:
+	splay->ist_ltree = current;
+	splay->ist_rtree = parent;
+	return current;
+
+    traverse_right:
+	if (current->ite_rchild != ITE_NULL) {
+		ipc_tree_entry_t next;
+
+		next = current->ite_rchild;
+		current->ite_rchild = parent;
+		parent = current;
+		current = next;
+		goto traverse_left;
+	}
+
+    traverse_back:
+	if (parent == ITE_NULL) {
+		splay->ist_root = current;
+		return ITE_NULL;
+	}
+
+	if (current->ite_name < parent->ite_name) {
+		ipc_tree_entry_t prev;
+
+		prev = current;
+		current = parent;
+		parent = current->ite_lchild;
+		current->ite_lchild = prev;
+		goto traverse_entry;
+	} else {
+		ipc_tree_entry_t prev;
+
+		prev = current;
+		current = parent;
+		parent = current->ite_rchild;
+		current->ite_rchild = prev;
+		goto traverse_back;
+	}
+}
+
+void
+ipc_splay_traverse_finish(
+	ipc_splay_tree_t	splay)
+{
+	ipc_tree_entry_t root;
+
+	root = splay->ist_root;
+	if (root != ITE_NULL) {
+		splay->ist_name = root->ite_name;
+		splay->ist_ltreep = &splay->ist_ltree;
+		splay->ist_rtreep = &splay->ist_rtree;
+	}
+
+	ist_unlock(splay);
+}
+