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