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