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