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