osfmk/ipc/ipc_splay.c

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