![[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 XNU] / XNU / osfmk / ipc|
Return to ipc_splay.c CVS log | Up to [Apple XNU] / XNU / osfmk / ipc |
1.1 ! root 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 [email protected] ! 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, ¤t, ! 907: <ree, <reep, &rtree, &rtreep); ! 908: ipc_splay_prim_assemble(current, ! 909: <ree, 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:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.