osfmk/ipc/ipc_splay.c

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