123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924 |
- /*
- * 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.
- */
-
- #pragma GCC diagnostic error "-Wundef"
- #include <glue/gnulinux.h>
- #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, ¤t,
- <ree, <reep, &rtree, &rtreep);
- ipc_splay_prim_assemble(current,
- <ree, 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);
- }
|