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