osfmk/ipc/ipc_splay.c

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