osfmk/ipc/ipc_splay.c

   1 /*
   2  * Copyright (c) 2000-2004 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_OSREFERENCE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License.  The rights granted to you under the
  10  * License may not be used to create, or enable the creation or
  11  * redistribution of, unlawful or unlicensed copies of an Apple operating
  12  * system, or to circumvent, violate, or enable the circumvention or
  13  * violation of, any terms of an Apple operating system software license
  14  * agreement.
  15  *
  16  * Please obtain a copy of the License at
  17  * http://www.opensource.apple.com/apsl/ and read it before using this
  18  * file.
  19  *
  20  * The Original Code and all software distributed under the License are
  21  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  22  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  23  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  24  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  25  * Please see the License for the specific language governing rights and
  26  * limitations under the License.
  27  *
  28  * @APPLE_LICENSE_OSREFERENCE_HEADER_END@
  29  */
  30 /*
  31  * @OSF_COPYRIGHT@
  32  */
  33 /*
  34  * Mach Operating System
  35  * Copyright (c) 1991,1990,1989 Carnegie Mellon University
  36  * All Rights Reserved.
  37  *
  38  * Permission to use, copy, modify and distribute this software and its
  39  * documentation is hereby granted, provided that both the copyright
  40  * notice and this permission notice appear in all copies of the
  41  * software, derivative works or modified versions, and any portions
  42  * thereof, and that both notices appear in supporting documentation.
  43  *
  44  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
  45  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
  46  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  47  *
  48  * Carnegie Mellon requests users of this software to return to
  49  *
  50  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
  51  *  School of Computer Science
  52  *  Carnegie Mellon University
  53  *  Pittsburgh PA 15213-3890
  54  *
  55  * any improvements or extensions that they make and grant Carnegie Mellon
  56  * the rights to redistribute these changes.
  57  */
  58 /*
  59  */
  60 /*
  61  *      File:   ipc/ipc_splay.c
  62  *      Author: Rich Draves
  63  *      Date:   1989
  64  *
  65  *      Primitive splay tree operations.
  66  */
  67
  68 #include <mach/port.h>
  69 #include <kern/assert.h>
  70 #include <kern/macro_help.h>
  71 #include <ipc/ipc_entry.h>
  72 #include <ipc/ipc_splay.h>
  73
  74 /*
  75  *      Splay trees are self-adjusting binary search trees.
  76  *      They have the following attractive properties:
  77  *              1) Space efficient; only two pointers per entry.
  78  *              2) Robust performance; amortized O(log n) per operation.
  79  *              3) Recursion not needed.
  80  *      This makes them a good fall-back data structure for those
  81  *      entries that don't fit into the lookup table.
  82  *
  83  *      The paper by Sleator and Tarjan, JACM v. 32, no. 3, pp. 652-686,
  84  *      describes the splaying operation.  ipc_splay_prim_lookup
  85  *      and ipc_splay_prim_assemble implement the top-down splay
  86  *      described on p. 669.
  87  *
  88  *      The tree is stored in an unassembled form.  If ist_root is null,
  89  *      then the tree has no entries.  Otherwise, ist_name records
  90  *      the value used for the last lookup.  ist_root points to the
  91  *      middle tree obtained from the top-down splay.  ist_ltree and
  92  *      ist_rtree point to left and right subtrees, whose entries
  93  *      are all smaller (larger) than those in the middle tree.
  94  *      ist_ltreep and ist_rtreep are pointers to fields in the
  95  *      left and right subtrees.  ist_ltreep points to the rchild field
  96  *      of the largest entry in ltree, and ist_rtreep points to the
  97  *      lchild field of the smallest entry in rtree.  The pointed-to
  98  *      fields aren't initialized.  If the left (right) subtree is null,
  99  *      then ist_ltreep (ist_rtreep) points to the ist_ltree (ist_rtree)
 100  *      field in the splay structure itself.
 101  *
 102  *      The primary advantage of the unassembled form is that repeated
 103  *      unsuccessful lookups are efficient.  In particular, an unsuccessful
 104  *      lookup followed by an insert only requires one splaying operation.
 105  *
 106  *      The traversal algorithm works via pointer inversion.
 107  *      When descending down the tree, child pointers are reversed
 108  *      to point back to the parent entry.  When ascending,
 109  *      the pointers are restored to their original value.
 110  *
 111  *      The biggest potential problem with the splay tree implementation
 112  *      is that the operations, even lookup, require an exclusive lock.
 113  *      If IPC spaces are protected with exclusive locks, then
 114  *      the splay tree doesn't require its own lock, and ist_lock/ist_unlock
 115  *      needn't do anything.  If IPC spaces are protected with read/write
 116  *      locks then ist_lock/ist_unlock should provide exclusive access.
 117  *
 118  *      If it becomes important to let lookups run in parallel,
 119  *      or if the restructuring makes lookups too expensive, then
 120  *      there is hope.  Use a read/write lock on the splay tree.
 121  *      Keep track of the number of entries in the tree.  When doing
 122  *      a lookup, first try a non-restructuring lookup with a read lock held,
 123  *      with a bound (based on log of size of the tree) on the number of
 124  *      entries to traverse.  If the lookup runs up against the bound,
 125  *      then take a write lock and do a reorganizing lookup.
 126  *      This way, if lookups only access roughly balanced parts
 127  *      of the tree, then lookups run in parallel and do no restructuring.
 128  *
 129  *      The traversal algorithm currently requires an exclusive lock.
 130  *      If that is a problem, the tree could be changed from an lchild/rchild
 131  *      representation to a leftmost child/right sibling representation.
 132  *      In conjunction with non-restructing lookups, this would let
 133  *      lookups and traversals all run in parallel.  But this representation
 134  *      is more complicated and would slow down the operations.
 135  */
 136
 137 /*
 138  *      Boundary values to hand to ipc_splay_prim_lookup:
 139  */
 140
 141 #define MACH_PORT_SMALLEST      ((mach_port_name_t) 0)
 142 #define MACH_PORT_LARGEST       ((mach_port_name_t) ~0)
 143
 144 /*
 145  *      Routine:        ipc_splay_prim_lookup
 146  *      Purpose:
 147  *              Searches for the node labeled name in the splay tree.
 148  *              Returns three nodes (treep, ltreep, rtreep) and
 149  *              two pointers to nodes (ltreepp, rtreepp).
 150  *
 151  *              ipc_splay_prim_lookup splits the supplied tree into
 152  *              three subtrees, left, middle, and right, returned
 153  *              in ltreep, treep, and rtreep.
 154  *
 155  *              If name is present in the tree, then it is at
 156  *              the root of the middle tree.  Otherwise, the root
 157  *              of the middle tree is the last node traversed.
 158  *
 159  *              ipc_splay_prim_lookup returns a pointer into
 160  *              the left subtree, to the rchild field of its
 161  *              largest node, in ltreepp.  It returns a pointer
 162  *              into the right subtree, to the lchild field of its
 163  *              smallest node, in rtreepp.
 164  */
 165
 166 static void
 167 ipc_splay_prim_lookup(
 168         mach_port_name_t        name,
 169         ipc_tree_entry_t        tree,
 170         ipc_tree_entry_t        *treep,
 171         ipc_tree_entry_t        *ltreep,
 172         ipc_tree_entry_t        **ltreepp,
 173         ipc_tree_entry_t        *rtreep,
 174         ipc_tree_entry_t        **rtreepp)
 175 {
 176         mach_port_name_t tname;                 /* temp name */
 177         ipc_tree_entry_t lchild, rchild;        /* temp child pointers */
 178
 179         assert(tree != ITE_NULL);
 180
 181 #define link_left                                       \
 182 MACRO_BEGIN                                             \
 183         *ltreep = tree;                                 \
 184         ltreep = &tree->ite_rchild;                     \
 185         tree = *ltreep;                                 \
 186 MACRO_END
 187
 188 #define link_right                                      \
 189 MACRO_BEGIN                                             \
 190         *rtreep = tree;                                 \
 191         rtreep = &tree->ite_lchild;                     \
 192         tree = *rtreep;                                 \
 193 MACRO_END
 194
 195 #define rotate_left                                     \
 196 MACRO_BEGIN                                             \
 197         ipc_tree_entry_t temp = tree;                   \
 198                                                         \
 199         tree = temp->ite_rchild;                        \
 200         temp->ite_rchild = tree->ite_lchild;            \
 201         tree->ite_lchild = temp;                        \
 202 MACRO_END
 203
 204 #define rotate_right                                    \
 205 MACRO_BEGIN                                             \
 206         ipc_tree_entry_t temp = tree;                   \
 207                                                         \
 208         tree = temp->ite_lchild;                        \
 209         temp->ite_lchild = tree->ite_rchild;            \
 210         tree->ite_rchild = temp;                        \
 211 MACRO_END
 212
 213         while (name != (tname = tree->ite_name)) {
 214                 if (name < tname) {
 215                         /* descend to left */
 216
 217                         lchild = tree->ite_lchild;
 218                         if (lchild == ITE_NULL)
 219                                 break;
 220                         tname = lchild->ite_name;
 221
 222                         if ((name < tname) &&
 223                             (lchild->ite_lchild != ITE_NULL))
 224                                 rotate_right;
 225                         link_right;
 226                         if ((name > tname) &&
 227                             (lchild->ite_rchild != ITE_NULL))
 228                                 link_left;
 229                 } else {
 230                         /* descend to right */
 231
 232                         rchild = tree->ite_rchild;
 233                         if (rchild == ITE_NULL)
 234                                 break;
 235                         tname = rchild->ite_name;
 236
 237                         if ((name > tname) &&
 238                             (rchild->ite_rchild != ITE_NULL))
 239                                 rotate_left;
 240                         link_left;
 241                         if ((name < tname) &&
 242                             (rchild->ite_lchild != ITE_NULL))
 243                                 link_right;
 244                 }
 245
 246                 assert(tree != ITE_NULL);
 247         }
 248
 249         *treep = tree;
 250         *ltreepp = ltreep;
 251         *rtreepp = rtreep;
 252
 253 #undef  link_left
 254 #undef  link_right
 255 #undef  rotate_left
 256 #undef  rotate_right
 257 }
 258
 259 /*
 260  *      Routine:        ipc_splay_prim_assemble
 261  *      Purpose:
 262  *              Assembles the results of ipc_splay_prim_lookup
 263  *              into a splay tree with the found node at the root.
 264  *
 265  *              ltree and rtree are by-reference so storing
 266  *              through ltreep and rtreep can change them.
 267  */
 268
 269 static void
 270 ipc_splay_prim_assemble(
 271         ipc_tree_entry_t        tree,
 272         ipc_tree_entry_t        *ltree,
 273         ipc_tree_entry_t        *ltreep,
 274         ipc_tree_entry_t        *rtree,
 275         ipc_tree_entry_t        *rtreep)
 276 {
 277         assert(tree != ITE_NULL);
 278
 279         *ltreep = tree->ite_lchild;
 280         *rtreep = tree->ite_rchild;
 281
 282         tree->ite_lchild = *ltree;
 283         tree->ite_rchild = *rtree;
 284 }
 285
 286 /*
 287  *      Routine:        ipc_splay_tree_init
 288  *      Purpose:
 289  *              Initialize a raw splay tree for use.
 290  */
 291
 292 void
 293 ipc_splay_tree_init(
 294         ipc_splay_tree_t        splay)
 295 {
 296         splay->ist_root = ITE_NULL;
 297 }
 298
 299 /*
 300  *      Routine:        ipc_splay_tree_pick
 301  *      Purpose:
 302  *              Picks and returns a random entry in a splay tree.
 303  *              Returns FALSE if the splay tree is empty.
 304  */
 305
 306 boolean_t
 307 ipc_splay_tree_pick(
 308         ipc_splay_tree_t        splay,
 309         mach_port_name_t        *namep,
 310         ipc_tree_entry_t        *entryp)
 311 {
 312         ipc_tree_entry_t root;
 313
 314         ist_lock(splay);
 315
 316         root = splay->ist_root;
 317         if (root != ITE_NULL) {
 318                 *namep = root->ite_name;
 319                 *entryp = root;
 320         }
 321
 322         ist_unlock(splay);
 323
 324         return root != ITE_NULL;
 325 }
 326
 327 /*
 328  *      Routine:        ipc_splay_tree_lookup
 329  *      Purpose:
 330  *              Finds an entry in a splay tree.
 331  *              Returns ITE_NULL if not found.
 332  */
 333
 334 ipc_tree_entry_t
 335 ipc_splay_tree_lookup(
 336         ipc_splay_tree_t        splay,
 337         mach_port_name_t        name)
 338 {
 339         ipc_tree_entry_t root;
 340
 341         ist_lock(splay);
 342
 343         root = splay->ist_root;
 344         if (root != ITE_NULL) {
 345                 if (splay->ist_name != name) {
 346                         ipc_splay_prim_assemble(root,
 347                                 &splay->ist_ltree, splay->ist_ltreep,
 348                                 &splay->ist_rtree, splay->ist_rtreep);
 349                         ipc_splay_prim_lookup(name, root, &root,
 350                                 &splay->ist_ltree, &splay->ist_ltreep,
 351                                 &splay->ist_rtree, &splay->ist_rtreep);
 352                         splay->ist_name = name;
 353                         splay->ist_root = root;
 354                 }
 355
 356                 if (name != root->ite_name)
 357                         root = ITE_NULL;
 358         }
 359
 360         ist_unlock(splay);
 361
 362         return root;
 363 }
 364
 365 /*
 366  *      Routine:        ipc_splay_tree_insert
 367  *      Purpose:
 368  *              Inserts a new entry into a splay tree.
 369  *              The caller supplies a new entry.
 370  *              The name can't already be present in the tree.
 371  */
 372
 373 void
 374 ipc_splay_tree_insert(
 375         ipc_splay_tree_t        splay,
 376         mach_port_name_t        name,
 377         ipc_tree_entry_t        entry)
 378 {
 379         ipc_tree_entry_t root;
 380
 381         assert(entry != ITE_NULL);
 382
 383         ist_lock(splay);
 384
 385         root = splay->ist_root;
 386         if (root == ITE_NULL) {
 387                 entry->ite_lchild = ITE_NULL;
 388                 entry->ite_rchild = ITE_NULL;
 389         } else {
 390                 if (splay->ist_name != name) {
 391                         ipc_splay_prim_assemble(root,
 392                                 &splay->ist_ltree, splay->ist_ltreep,
 393                                 &splay->ist_rtree, splay->ist_rtreep);
 394                         ipc_splay_prim_lookup(name, root, &root,
 395                                 &splay->ist_ltree, &splay->ist_ltreep,
 396                                 &splay->ist_rtree, &splay->ist_rtreep);
 397                 }
 398
 399                 assert(root->ite_name != name);
 400
 401                 if (name < root->ite_name) {
 402                         assert(root->ite_lchild == ITE_NULL);
 403
 404                         *splay->ist_ltreep = ITE_NULL;
 405                         *splay->ist_rtreep = root;
 406                 } else {
 407                         assert(root->ite_rchild == ITE_NULL);
 408
 409                         *splay->ist_ltreep = root;
 410                         *splay->ist_rtreep = ITE_NULL;
 411                 }
 412
 413                 entry->ite_lchild = splay->ist_ltree;
 414                 entry->ite_rchild = splay->ist_rtree;
 415         }
 416
 417         entry->ite_name = name;
 418         splay->ist_root = entry;
 419         splay->ist_name = name;
 420         splay->ist_ltreep = &splay->ist_ltree;
 421         splay->ist_rtreep = &splay->ist_rtree;
 422
 423         ist_unlock(splay);
 424 }
 425
 426 /*
 427  *      Routine:        ipc_splay_tree_delete
 428  *      Purpose:
 429  *              Deletes an entry from a splay tree.
 430  *              The name must be present in the tree.
 431  *              Frees the entry.
 432  *
 433  *              The "entry" argument isn't currently used.
 434  *              Other implementations might want it, though.
 435  */
 436
 437 void
 438 ipc_splay_tree_delete(
 439         ipc_splay_tree_t                        splay,
 440         mach_port_name_t                        name,
 441         __assert_only ipc_tree_entry_t  entry)
 442 {
 443         ipc_tree_entry_t root, saved;
 444
 445         ist_lock(splay);
 446
 447         root = splay->ist_root;
 448         assert(root != ITE_NULL);
 449
 450         if (splay->ist_name != name) {
 451                 ipc_splay_prim_assemble(root,
 452                         &splay->ist_ltree, splay->ist_ltreep,
 453                         &splay->ist_rtree, splay->ist_rtreep);
 454                 ipc_splay_prim_lookup(name, root, &root,
 455                         &splay->ist_ltree, &splay->ist_ltreep,
 456                         &splay->ist_rtree, &splay->ist_rtreep);
 457         }
 458
 459         assert(root->ite_name == name);
 460         assert(root == entry);
 461
 462         *splay->ist_ltreep = root->ite_lchild;
 463         *splay->ist_rtreep = root->ite_rchild;
 464         ite_free(root);
 465
 466         root = splay->ist_ltree;
 467         saved = splay->ist_rtree;
 468
 469         if (root == ITE_NULL)
 470                 root = saved;
 471         else if (saved != ITE_NULL) {
 472                 /*
 473                  *      Find the largest node in the left subtree, and splay it
 474                  *      to the root.  Then add the saved right subtree.
 475                  */
 476
 477                 ipc_splay_prim_lookup(MACH_PORT_LARGEST, root, &root,
 478                         &splay->ist_ltree, &splay->ist_ltreep,
 479                         &splay->ist_rtree, &splay->ist_rtreep);
 480                 ipc_splay_prim_assemble(root,
 481                         &splay->ist_ltree, splay->ist_ltreep,
 482                         &splay->ist_rtree, splay->ist_rtreep);
 483
 484                 assert(root->ite_rchild == ITE_NULL);
 485                 root->ite_rchild = saved;
 486         }
 487
 488         splay->ist_root = root;
 489         if (root != ITE_NULL) {
 490                 splay->ist_name = root->ite_name;
 491                 splay->ist_ltreep = &splay->ist_ltree;
 492                 splay->ist_rtreep = &splay->ist_rtree;
 493         }
 494
 495         ist_unlock(splay);
 496 }
 497
 498 /*
 499  *      Routine:        ipc_splay_tree_split
 500  *      Purpose:
 501  *              Split a splay tree.  Puts all entries smaller than "name"
 502  *              into a new tree, "small".
 503  *
 504  *              Doesn't do locking on "small", because nobody else
 505  *              should be fiddling with the uninitialized tree.
 506  */
 507
 508 void
 509 ipc_splay_tree_split(
 510         ipc_splay_tree_t        splay,
 511         mach_port_name_t        name,
 512         ipc_splay_tree_t        small)
 513 {
 514         ipc_tree_entry_t root;
 515
 516         ipc_splay_tree_init(small);
 517
 518         ist_lock(splay);
 519
 520         root = splay->ist_root;
 521         if (root != ITE_NULL) {
 522                 /* lookup name, to get it (or last traversed) to the top */
 523
 524                 if (splay->ist_name != name) {
 525                         ipc_splay_prim_assemble(root,
 526                                 &splay->ist_ltree, splay->ist_ltreep,
 527                                 &splay->ist_rtree, splay->ist_rtreep);
 528                         ipc_splay_prim_lookup(name, root, &root,
 529                                 &splay->ist_ltree, &splay->ist_ltreep,
 530                                 &splay->ist_rtree, &splay->ist_rtreep);
 531                 }
 532
 533                 if (root->ite_name < name) {
 534                         /* root goes into small */
 535
 536                         *splay->ist_ltreep = root->ite_lchild;
 537                         *splay->ist_rtreep = ITE_NULL;
 538                         root->ite_lchild = splay->ist_ltree;
 539                         assert(root->ite_rchild == ITE_NULL);
 540
 541                         small->ist_root = root;
 542                         small->ist_name = root->ite_name;
 543                         small->ist_ltreep = &small->ist_ltree;
 544                         small->ist_rtreep = &small->ist_rtree;
 545
 546                         /* rtree goes into splay */
 547
 548                         root = splay->ist_rtree;
 549                         splay->ist_root = root;
 550                         if (root != ITE_NULL) {
 551                                 splay->ist_name = root->ite_name;
 552                                 splay->ist_ltreep = &splay->ist_ltree;
 553                                 splay->ist_rtreep = &splay->ist_rtree;
 554                         }
 555                 } else {
 556                         /* root stays in splay */
 557
 558                         *splay->ist_ltreep = root->ite_lchild;
 559                         root->ite_lchild = ITE_NULL;
 560
 561                         splay->ist_root = root;
 562                         splay->ist_name = name;
 563                         splay->ist_ltreep = &splay->ist_ltree;
 564
 565                         /* ltree goes into small */
 566
 567                         root = splay->ist_ltree;
 568                         small->ist_root = root;
 569                         if (root != ITE_NULL) {
 570                                 small->ist_name = root->ite_name;
 571                                 small->ist_ltreep = &small->ist_ltree;
 572                                 small->ist_rtreep = &small->ist_rtree;
 573                         }
 574                 }
 575         }
 576
 577         ist_unlock(splay);
 578 }
 579
 580 /*
 581  *      Routine:        ipc_splay_tree_join
 582  *      Purpose:
 583  *              Joins two splay trees.  Merges the entries in "small",
 584  *              which must all be smaller than the entries in "splay",
 585  *              into "splay".
 586  */
 587
 588 void
 589 ipc_splay_tree_join(
 590         ipc_splay_tree_t        splay,
 591         ipc_splay_tree_t        small)
 592 {
 593         ipc_tree_entry_t sroot;
 594
 595         /* pull entries out of small */
 596
 597         ist_lock(small);
 598
 599         sroot = small->ist_root;
 600         if (sroot != ITE_NULL) {
 601                 ipc_splay_prim_assemble(sroot,
 602                         &small->ist_ltree, small->ist_ltreep,
 603                         &small->ist_rtree, small->ist_rtreep);
 604                 small->ist_root = ITE_NULL;
 605         }
 606
 607         ist_unlock(small);
 608
 609         /* put entries, if any, into splay */
 610
 611         if (sroot != ITE_NULL) {
 612                 ipc_tree_entry_t root;
 613
 614                 ist_lock(splay);
 615
 616                 root = splay->ist_root;
 617                 if (root == ITE_NULL) {
 618                         root = sroot;
 619                 } else {
 620                         /* get smallest entry in splay tree to top */
 621
 622                         if (splay->ist_name != MACH_PORT_SMALLEST) {
 623                                 ipc_splay_prim_assemble(root,
 624                                         &splay->ist_ltree, splay->ist_ltreep,
 625                                         &splay->ist_rtree, splay->ist_rtreep);
 626                                 ipc_splay_prim_lookup(MACH_PORT_SMALLEST,
 627                                         root, &root,
 628                                         &splay->ist_ltree, &splay->ist_ltreep,
 629                                         &splay->ist_rtree, &splay->ist_rtreep);
 630                         }
 631
 632                         ipc_splay_prim_assemble(root,
 633                                 &splay->ist_ltree, splay->ist_ltreep,
 634                                 &splay->ist_rtree, splay->ist_rtreep);
 635
 636                         assert(root->ite_lchild == ITE_NULL);
 637                         assert(sroot->ite_name < root->ite_name);
 638                         root->ite_lchild = sroot;
 639                 }
 640
 641                 splay->ist_root = root;
 642                 splay->ist_name = root->ite_name;
 643                 splay->ist_ltreep = &splay->ist_ltree;
 644                 splay->ist_rtreep = &splay->ist_rtree;
 645
 646                 ist_unlock(splay);
 647         }
 648 }
 649
 650 /*
 651  *      Routine:        ipc_splay_tree_bounds
 652  *      Purpose:
 653  *              Given a name, returns the largest value present
 654  *              in the tree that is smaller than or equal to the name,
 655  *              or ~0 if no such value exists.  Similarly, returns
 656  *              the smallest value present that is greater than or
 657  *              equal to the name, or 0 if no such value exists.
 658  *
 659  *              Hence, if
 660  *              lower = upper, then lower = name = upper
 661  *                              and name is present in the tree
 662  *              lower = ~0 and upper = 0,
 663  *                              then the tree is empty
 664  *              lower = ~0 and upper > 0, then name < upper
 665  *                              and upper is smallest value in tree
 666  *              lower < ~0 and upper = 0, then lower < name
 667  *                              and lower is largest value in tree
 668  *              lower < ~0 and upper > 0, then lower < name < upper
 669  *                              and they are tight bounds on name
 670  *
 671  *              (Note MACH_PORT_SMALLEST = 0 and MACH_PORT_LARGEST = ~0.)
 672  */
 673
 674 void
 675 ipc_splay_tree_bounds(
 676         ipc_splay_tree_t        splay,
 677         mach_port_name_t        name,
 678         mach_port_name_t        *lowerp,
 679         mach_port_name_t        *upperp)
 680 {
 681         ipc_tree_entry_t root;
 682
 683         ist_lock(splay);
 684
 685         root = splay->ist_root;
 686         if (root == ITE_NULL) {
 687                 *lowerp = MACH_PORT_LARGEST;
 688                 *upperp = MACH_PORT_SMALLEST;
 689         } else {
 690                 mach_port_name_t rname;
 691
 692                 if (splay->ist_name != name) {
 693                         ipc_splay_prim_assemble(root,
 694                                 &splay->ist_ltree, splay->ist_ltreep,
 695                                 &splay->ist_rtree, splay->ist_rtreep);
 696                         ipc_splay_prim_lookup(name, root, &root,
 697                                 &splay->ist_ltree, &splay->ist_ltreep,
 698                                 &splay->ist_rtree, &splay->ist_rtreep);
 699                         splay->ist_name = name;
 700                         splay->ist_root = root;
 701                 }
 702
 703                 rname = root->ite_name;
 704
 705                 /*
 706                  *      OK, it's a hack.  We convert the ltreep and rtreep
 707                  *      pointers back into real entry pointers,
 708                  *      so we can pick the names out of the entries.
 709                  */
 710
 711                 if (rname <= name)
 712                         *lowerp = rname;
 713                 else if (splay->ist_ltreep == &splay->ist_ltree)
 714                         *lowerp = MACH_PORT_LARGEST;
 715                 else {
 716                         ipc_tree_entry_t entry;
 717
 718                         entry = (ipc_tree_entry_t)
 719                                 ((char *)splay->ist_ltreep -
 720                                  ((char *)&root->ite_rchild -
 721                                   (char *)root));
 722                         *lowerp = entry->ite_name;
 723                 }
 724
 725                 if (rname >= name)
 726                         *upperp = rname;
 727                 else if (splay->ist_rtreep == &splay->ist_rtree)
 728                         *upperp = MACH_PORT_SMALLEST;
 729                 else {
 730                         ipc_tree_entry_t entry;
 731
 732                         entry = (ipc_tree_entry_t)
 733                                 ((char *)splay->ist_rtreep -
 734                                  ((char *)&root->ite_lchild -
 735                                   (char *)root));
 736                         *upperp = entry->ite_name;
 737                 }
 738         }
 739
 740         ist_unlock(splay);
 741 }
 742
 743 /*
 744  *      Routine:        ipc_splay_traverse_start
 745  *      Routine:        ipc_splay_traverse_next
 746  *      Routine:        ipc_splay_traverse_finish
 747  *      Purpose:
 748  *              Perform a symmetric order traversal of a splay tree.
 749  *      Usage:
 750  *              for (entry = ipc_splay_traverse_start(splay);
 751  *                   entry != ITE_NULL;
 752  *                   entry = ipc_splay_traverse_next(splay, delete)) {
 753  *                      do something with entry
 754  *              }
 755  *              ipc_splay_traverse_finish(splay);
 756  *
 757  *              If "delete" is TRUE, then the current entry
 758  *              is removed from the tree and deallocated.
 759  *
 760  *              During the traversal, the splay tree is locked.
 761  */
 762
 763 ipc_tree_entry_t
 764 ipc_splay_traverse_start(
 765         ipc_splay_tree_t        splay)
 766 {
 767         ipc_tree_entry_t current, parent;
 768
 769         ist_lock(splay);
 770
 771         current = splay->ist_root;
 772         if (current != ITE_NULL) {
 773                 ipc_splay_prim_assemble(current,
 774                         &splay->ist_ltree, splay->ist_ltreep,
 775                         &splay->ist_rtree, splay->ist_rtreep);
 776
 777                 parent = ITE_NULL;
 778
 779                 while (current->ite_lchild != ITE_NULL) {
 780                         ipc_tree_entry_t next;
 781
 782                         next = current->ite_lchild;
 783                         current->ite_lchild = parent;
 784                         parent = current;
 785                         current = next;
 786                 }
 787
 788                 splay->ist_ltree = current;
 789                 splay->ist_rtree = parent;
 790         }
 791
 792         return current;
 793 }
 794
 795 ipc_tree_entry_t
 796 ipc_splay_traverse_next(
 797         ipc_splay_tree_t        splay,
 798         boolean_t               delete)
 799 {
 800         ipc_tree_entry_t current, parent;
 801
 802         /* pick up where traverse_entry left off */
 803
 804         current = splay->ist_ltree;
 805         parent = splay->ist_rtree;
 806         assert(current != ITE_NULL);
 807
 808         if (!delete)
 809                 goto traverse_right;
 810
 811         /* we must delete current and patch the tree */
 812
 813         if (current->ite_lchild == ITE_NULL) {
 814                 if (current->ite_rchild == ITE_NULL) {
 815                         /* like traverse_back, but with deletion */
 816
 817                         if (parent == ITE_NULL) {
 818                                 ite_free(current);
 819
 820                                 splay->ist_root = ITE_NULL;
 821                                 return ITE_NULL;
 822                         }
 823
 824                         if (current->ite_name < parent->ite_name) {
 825                                 ite_free(current);
 826
 827                                 current = parent;
 828                                 parent = current->ite_lchild;
 829                                 current->ite_lchild = ITE_NULL;
 830                                 goto traverse_entry;
 831                         } else {
 832                                 ite_free(current);
 833
 834                                 current = parent;
 835                                 parent = current->ite_rchild;
 836                                 current->ite_rchild = ITE_NULL;
 837                                 goto traverse_back;
 838                         }
 839                 } else {
 840                         ipc_tree_entry_t prev;
 841
 842                         prev = current;
 843                         current = current->ite_rchild;
 844                         ite_free(prev);
 845                         goto traverse_left;
 846                 }
 847         } else {
 848                 if (current->ite_rchild == ITE_NULL) {
 849                         ipc_tree_entry_t prev;
 850
 851                         prev = current;
 852                         current = current->ite_lchild;
 853                         ite_free(prev);
 854                         goto traverse_back;
 855                 } else {
 856                         ipc_tree_entry_t prev;
 857                         ipc_tree_entry_t ltree, rtree;
 858                         ipc_tree_entry_t *ltreep, *rtreep;
 859
 860                         /* replace current with largest of left children */
 861
 862                         prev = current;
 863                         ipc_splay_prim_lookup(MACH_PORT_LARGEST,
 864                                 current->ite_lchild, &current,
 865                                 &ltree, &ltreep, &rtree, &rtreep);
 866                         ipc_splay_prim_assemble(current,
 867                                 &ltree, ltreep, &rtree, rtreep);
 868
 869                         assert(current->ite_rchild == ITE_NULL);
 870                         current->ite_rchild = prev->ite_rchild;
 871                         ite_free(prev);
 872                         goto traverse_right;
 873                 }
 874         }
 875         /*NOTREACHED*/
 876
 877         /*
 878          *      A state machine:  for each entry, we
 879          *              1) traverse left subtree
 880          *              2) traverse the entry
 881          *              3) traverse right subtree
 882          *              4) traverse back to parent
 883          */
 884
 885     traverse_left:
 886         if (current->ite_lchild != ITE_NULL) {
 887                 ipc_tree_entry_t next;
 888
 889                 next = current->ite_lchild;
 890                 current->ite_lchild = parent;
 891                 parent = current;
 892                 current = next;
 893                 goto traverse_left;
 894         }
 895
 896     traverse_entry:
 897         splay->ist_ltree = current;
 898         splay->ist_rtree = parent;
 899         return current;
 900
 901     traverse_right:
 902         if (current->ite_rchild != ITE_NULL) {
 903                 ipc_tree_entry_t next;
 904
 905                 next = current->ite_rchild;
 906                 current->ite_rchild = parent;
 907                 parent = current;
 908                 current = next;
 909                 goto traverse_left;
 910         }
 911
 912     traverse_back:
 913         if (parent == ITE_NULL) {
 914                 splay->ist_root = current;
 915                 return ITE_NULL;
 916         }
 917
 918         if (current->ite_name < parent->ite_name) {
 919                 ipc_tree_entry_t prev;
 920
 921                 prev = current;
 922                 current = parent;
 923                 parent = current->ite_lchild;
 924                 current->ite_lchild = prev;
 925                 goto traverse_entry;
 926         } else {
 927                 ipc_tree_entry_t prev;
 928
 929                 prev = current;
 930                 current = parent;
 931                 parent = current->ite_rchild;
 932                 current->ite_rchild = prev;
 933                 goto traverse_back;
 934         }
 935 }
 936
 937 void
 938 ipc_splay_traverse_finish(
 939         ipc_splay_tree_t        splay)
 940 {
 941         ipc_tree_entry_t root;
 942
 943         root = splay->ist_root;
 944         if (root != ITE_NULL) {
 945                 splay->ist_name = root->ite_name;
 946                 splay->ist_ltreep = &splay->ist_ltree;
 947                 splay->ist_rtreep = &splay->ist_rtree;
 948         }
 949
 950         ist_unlock(splay);
 951 }
 952