![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to ipc_splay.h 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.h 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.h
75: * Author: Rich Draves
76: * Date: 1989
77: *
78: * Declarations of primitive splay tree operations.
79: */
80:
81: #ifndef _IPC_IPC_SPLAY_H_
82: #define _IPC_IPC_SPLAY_H_
83:
84: #include <mach/port.h>
85: #include <kern/assert.h>
86: #include <kern/macro_help.h>
87: #include <ipc/ipc_entry.h>
88:
89: typedef struct ipc_splay_tree {
90: mach_port_t ist_name; /* name used in last lookup */
91: ipc_tree_entry_t ist_root; /* root of middle tree */
92: ipc_tree_entry_t ist_ltree; /* root of left tree */
93: ipc_tree_entry_t *ist_ltreep; /* pointer into left tree */
94: ipc_tree_entry_t ist_rtree; /* root of right tree */
95: ipc_tree_entry_t *ist_rtreep; /* pointer into right tree */
96: } *ipc_splay_tree_t;
97:
98: #define ist_lock(splay) /* no locking */
99: #define ist_unlock(splay) /* no locking */
100:
101: /* Initialize a raw splay tree */
102: extern void ipc_splay_tree_init(
103: ipc_splay_tree_t splay);
104:
105: /* Pick a random entry in a splay tree */
106: extern boolean_t ipc_splay_tree_pick(
107: ipc_splay_tree_t splay,
108: mach_port_t *namep,
109: ipc_tree_entry_t *entryp);
110:
111: /* Find an entry in a splay tree */
112: extern ipc_tree_entry_t ipc_splay_tree_lookup(
113: ipc_splay_tree_t splay,
114: mach_port_t name);
115:
116: /* Insert a new entry into a splay tree */
117: extern void ipc_splay_tree_insert(
118: ipc_splay_tree_t splay,
119: mach_port_t name,
120: ipc_tree_entry_t entry);
121:
122: /* Delete an entry from a splay tree */
123: extern void ipc_splay_tree_delete(
124: ipc_splay_tree_t splay,
125: mach_port_t name,
126: ipc_tree_entry_t entry);
127:
128: /* Split a splay tree */
129: extern void ipc_splay_tree_split(
130: ipc_splay_tree_t splay,
131: mach_port_t name,
132: ipc_splay_tree_t entry);
133:
134: /* Join two splay trees */
135: extern void ipc_splay_tree_join(
136: ipc_splay_tree_t splay,
137: ipc_splay_tree_t small);
138:
139: /* Do a bounded splay tree lookup */
140: extern void ipc_splay_tree_bounds(
141: ipc_splay_tree_t splay,
142: mach_port_t name,
143: mach_port_t *lowerp,
144: mach_port_t *upperp);
145:
146: /* Initialize a symmetric order traversal of a splay tree */
147: extern ipc_tree_entry_t ipc_splay_traverse_start(
148: ipc_splay_tree_t splay);
149:
150: /* Return the next entry in a symmetric order traversal of a splay tree */
151: extern ipc_tree_entry_t ipc_splay_traverse_next(
152: ipc_splay_tree_t splay,
153: boolean_t delete);
154:
155: /* Terminate a symmetric order traversal of a splay tree */
156: extern void ipc_splay_traverse_finish(
157: ipc_splay_tree_t splay);
158:
159: #endif /* _IPC_IPC_SPLAY_H_ */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.