| | 1 | /* |
| | 2 | * Copyright (c) 2000 Apple Computer, Inc. All rights reserved. |
| | 3 | * |
| | 4 | * @APPLE_LICENSE_HEADER_START@ |
| | 5 | * |
| | 6 | * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved. |
| | 7 | * |
| | 8 | * This file contains Original Code and/or Modifications of Original Code |
| | 9 | * as defined in and that are subject to the Apple Public Source License |
| | 10 | * Version 2.0 (the 'License'). You may not use this file except in |
| | 11 | * compliance with the License. Please obtain a copy of the License at |
| | 12 | * http://www.opensource.apple.com/apsl/ and read it before using this |
| | 13 | * file. |
| | 14 | * |
| | 15 | * The Original Code and all software distributed under the License are |
| | 16 | * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER |
| | 17 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, |
| | 18 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, |
| | 19 | * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. |
| | 20 | * Please see the License for the specific language governing rights and |
| | 21 | * limitations under the License. |
| | 22 | * |
| | 23 | * @APPLE_LICENSE_HEADER_END@ |
| | 24 | */ |
| | 25 | /* |
| | 26 | * @OSF_COPYRIGHT@ |
| | 27 | */ |
| | 28 | /* |
| | 29 | * Mach Operating System |
| | 30 | * Copyright (c) 1991,1990,1989 Carnegie Mellon University |
| | 31 | * All Rights Reserved. |
| | 32 | * |
| | 33 | * Permission to use, copy, modify and distribute this software and its |
| | 34 | * documentation is hereby granted, provided that both the copyright |
| | 35 | * notice and this permission notice appear in all copies of the |
| | 36 | * software, derivative works or modified versions, and any portions |
| | 37 | * thereof, and that both notices appear in supporting documentation. |
| | 38 | * |
| | 39 | * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" |
| | 40 | * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR |
| | 41 | * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. |
| | 42 | * |
| | 43 | * Carnegie Mellon requests users of this software to return to |
| | 44 | * |
| | 45 | * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU |
| | 46 | * School of Computer Science |
| | 47 | * Carnegie Mellon University |
| | 48 | * Pittsburgh PA 15213-3890 |
| | 49 | * |
| | 50 | * any improvements or extensions that they make and grant Carnegie Mellon |
| | 51 | * the rights to redistribute these changes. |
| | 52 | */ |
| | 53 | /* |
| | 54 | */ |
| | 55 | /* |
| | 56 | * File: ipc/ipc_splay.h |
| | 57 | * Author: Rich Draves |
| | 58 | * Date: 1989 |
| | 59 | * |
| | 60 | * Declarations of primitive splay tree operations. |
| | 61 | */ |
| | 62 | |
| | 63 | #ifndef _IPC_IPC_SPLAY_H_ |
| | 64 | #define _IPC_IPC_SPLAY_H_ |
| | 65 | |
| | 66 | #include <mach/port.h> |
| | 67 | #include <kern/assert.h> |
| | 68 | #include <kern/macro_help.h> |
| | 69 | #include <ipc/ipc_entry.h> |
| | 70 | |
| | 71 | typedef struct ipc_splay_tree { |
| | 72 | mach_port_name_t ist_name; /* name used in last lookup */ |
| | 73 | ipc_tree_entry_t ist_root; /* root of middle tree */ |
| | 74 | ipc_tree_entry_t ist_ltree; /* root of left tree */ |
| | 75 | ipc_tree_entry_t *ist_ltreep; /* pointer into left tree */ |
| | 76 | ipc_tree_entry_t ist_rtree; /* root of right tree */ |
| | 77 | ipc_tree_entry_t *ist_rtreep; /* pointer into right tree */ |
| | 78 | } *ipc_splay_tree_t; |
| | 79 | |
| | 80 | #define ist_lock(splay) /* no locking */ |
| | 81 | #define ist_unlock(splay) /* no locking */ |
| | 82 | |
| | 83 | /* Initialize a raw splay tree */ |
| | 84 | extern void ipc_splay_tree_init( |
| | 85 | ipc_splay_tree_t splay); |
| | 86 | |
| | 87 | /* Pick a random entry in a splay tree */ |
| | 88 | extern boolean_t ipc_splay_tree_pick( |
| | 89 | ipc_splay_tree_t splay, |
| | 90 | mach_port_name_t *namep, |
| | 91 | ipc_tree_entry_t *entryp); |
| | 92 | |
| | 93 | /* Find an entry in a splay tree */ |
| | 94 | extern ipc_tree_entry_t ipc_splay_tree_lookup( |
| | 95 | ipc_splay_tree_t splay, |
| | 96 | mach_port_name_t name); |
| | 97 | |
| | 98 | /* Insert a new entry into a splay tree */ |
| | 99 | extern void ipc_splay_tree_insert( |
| | 100 | ipc_splay_tree_t splay, |
| | 101 | mach_port_name_t name, |
| | 102 | ipc_tree_entry_t entry); |
| | 103 | |
| | 104 | /* Delete an entry from a splay tree */ |
| | 105 | extern void ipc_splay_tree_delete( |
| | 106 | ipc_splay_tree_t splay, |
| | 107 | mach_port_name_t name, |
| | 108 | ipc_tree_entry_t entry); |
| | 109 | |
| | 110 | /* Split a splay tree */ |
| | 111 | extern void ipc_splay_tree_split( |
| | 112 | ipc_splay_tree_t splay, |
| | 113 | mach_port_name_t name, |
| | 114 | ipc_splay_tree_t entry); |
| | 115 | |
| | 116 | /* Join two splay trees */ |
| | 117 | extern void ipc_splay_tree_join( |
| | 118 | ipc_splay_tree_t splay, |
| | 119 | ipc_splay_tree_t small); |
| | 120 | |
| | 121 | /* Do a bounded splay tree lookup */ |
| | 122 | extern void ipc_splay_tree_bounds( |
| | 123 | ipc_splay_tree_t splay, |
| | 124 | mach_port_name_t name, |
| | 125 | mach_port_name_t *lowerp, |
| | 126 | mach_port_name_t *upperp); |
| | 127 | |
| | 128 | /* Initialize a symmetric order traversal of a splay tree */ |
| | 129 | extern ipc_tree_entry_t ipc_splay_traverse_start( |
| | 130 | ipc_splay_tree_t splay); |
| | 131 | |
| | 132 | /* Return the next entry in a symmetric order traversal of a splay tree */ |
| | 133 | extern ipc_tree_entry_t ipc_splay_traverse_next( |
| | 134 | ipc_splay_tree_t splay, |
| | 135 | boolean_t delete); |
| | 136 | |
| | 137 | /* Terminate a symmetric order traversal of a splay tree */ |
| | 138 | extern void ipc_splay_traverse_finish( |
| | 139 | ipc_splay_tree_t splay); |
| | 140 | |
| | 141 | #endif /* _IPC_IPC_SPLAY_H_ */ |
projects / apple / xnu.git / blame_incremental