summaryrefslogtreecommitdiff
path: root/ipc/ipc_splay.c
diff options
context:
space:
mode:
Diffstat (limited to 'ipc/ipc_splay.c')
-rw-r--r--ipc/ipc_splay.c920
1 files changed, 0 insertions, 920 deletions
diff --git a/ipc/ipc_splay.c b/ipc/ipc_splay.c
deleted file mode 100644
index 062a69f8..00000000
--- a/ipc/ipc_splay.c
+++ /dev/null
@@ -1,920 +0,0 @@
-/*
- * 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/macros.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);
-}
-
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-23 08:41:30 +0000