![[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 XNU] / XNU / osfmk / ipc|
Return to ipc_splay.h 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: * Mach Operating System
27: * Copyright (c) 1991,1990,1989 Carnegie Mellon University
28: * All Rights Reserved.
29: *
30: * Permission to use, copy, modify and distribute this software and its
31: * documentation is hereby granted, provided that both the copyright
32: * notice and this permission notice appear in all copies of the
33: * software, derivative works or modified versions, and any portions
34: * thereof, and that both notices appear in supporting documentation.
35: *
36: * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
37: * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
38: * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
39: *
40: * Carnegie Mellon requests users of this software to return to
41: *
42: * Software Distribution Coordinator or [email protected]
43: * School of Computer Science
44: * Carnegie Mellon University
45: * Pittsburgh PA 15213-3890
46: *
47: * any improvements or extensions that they make and grant Carnegie Mellon
48: * the rights to redistribute these changes.
49: */
50: /*
51: */
52: /*
53: * File: ipc/ipc_splay.h
54: * Author: Rich Draves
55: * Date: 1989
56: *
57: * Declarations of primitive splay tree operations.
58: */
59:
60: #ifndef _IPC_IPC_SPLAY_H_
61: #define _IPC_IPC_SPLAY_H_
62:
63: #include <mach/port.h>
64: #include <kern/assert.h>
65: #include <kern/macro_help.h>
66: #include <ipc/ipc_entry.h>
67:
68: typedef struct ipc_splay_tree {
69: mach_port_name_t ist_name; /* name used in last lookup */
70: ipc_tree_entry_t ist_root; /* root of middle tree */
71: ipc_tree_entry_t ist_ltree; /* root of left tree */
72: ipc_tree_entry_t *ist_ltreep; /* pointer into left tree */
73: ipc_tree_entry_t ist_rtree; /* root of right tree */
74: ipc_tree_entry_t *ist_rtreep; /* pointer into right tree */
75: } *ipc_splay_tree_t;
76:
77: #define ist_lock(splay) /* no locking */
78: #define ist_unlock(splay) /* no locking */
79:
80: /* Initialize a raw splay tree */
81: extern void ipc_splay_tree_init(
82: ipc_splay_tree_t splay);
83:
84: /* Pick a random entry in a splay tree */
85: extern boolean_t ipc_splay_tree_pick(
86: ipc_splay_tree_t splay,
87: mach_port_name_t *namep,
88: ipc_tree_entry_t *entryp);
89:
90: /* Find an entry in a splay tree */
91: extern ipc_tree_entry_t ipc_splay_tree_lookup(
92: ipc_splay_tree_t splay,
93: mach_port_name_t name);
94:
95: /* Insert a new entry into a splay tree */
96: extern void ipc_splay_tree_insert(
97: ipc_splay_tree_t splay,
98: mach_port_name_t name,
99: ipc_tree_entry_t entry);
100:
101: /* Delete an entry from a splay tree */
102: extern void ipc_splay_tree_delete(
103: ipc_splay_tree_t splay,
104: mach_port_name_t name,
105: ipc_tree_entry_t entry);
106:
107: /* Split a splay tree */
108: extern void ipc_splay_tree_split(
109: ipc_splay_tree_t splay,
110: mach_port_name_t name,
111: ipc_splay_tree_t entry);
112:
113: /* Join two splay trees */
114: extern void ipc_splay_tree_join(
115: ipc_splay_tree_t splay,
116: ipc_splay_tree_t small);
117:
118: /* Do a bounded splay tree lookup */
119: extern void ipc_splay_tree_bounds(
120: ipc_splay_tree_t splay,
121: mach_port_name_t name,
122: mach_port_name_t *lowerp,
123: mach_port_name_t *upperp);
124:
125: /* Initialize a symmetric order traversal of a splay tree */
126: extern ipc_tree_entry_t ipc_splay_traverse_start(
127: ipc_splay_tree_t splay);
128:
129: /* Return the next entry in a symmetric order traversal of a splay tree */
130: extern ipc_tree_entry_t ipc_splay_traverse_next(
131: ipc_splay_tree_t splay,
132: boolean_t delete);
133:
134: /* Terminate a symmetric order traversal of a splay tree */
135: extern void ipc_splay_traverse_finish(
136: ipc_splay_tree_t splay);
137:
138: #endif /* _IPC_IPC_SPLAY_H_ */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.