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