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