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