/* * 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 #include #include #include #include /* * 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); }