[apple/xnu.git] / osfmk / ipc / ipc_splay.h

/*
 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_OSREFERENCE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code 
 * as defined in and that are subject to the Apple Public Source License 
 * Version 2.0 (the 'License'). You may not use this file except in 
 * compliance with the License.  The rights granted to you under the 
 * License may not be used to create, or enable the creation or 
 * redistribution of, unlawful or unlicensed copies of an Apple operating 
 * system, or to circumvent, violate, or enable the circumvention or 
 * violation of, any terms of an Apple operating system software license 
 * agreement.
 *
 * Please obtain a copy of the License at 
 * http://www.opensource.apple.com/apsl/ and read it before using this 
 * file.
 *
 * The Original Code and all software distributed under the License are 
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 
 * Please see the License for the specific language governing rights and 
 * limitations under the License.
 *
 * @APPLE_LICENSE_OSREFERENCE_HEADER_END@
 */
/*
 * @OSF_COPYRIGHT@
 */
/* 
 * Mach Operating System
 * Copyright (c) 1991,1990,1989 Carnegie Mellon University
 * All Rights Reserved.
 * 
 * Permission to use, copy, modify and distribute this software and its
 * documentation is hereby granted, provided that both the copyright
 * notice and this permission notice appear in all copies of the
 * software, derivative works or modified versions, and any portions
 * thereof, and that both notices appear in supporting documentation.
 * 
 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
 * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
 * 
 * Carnegie Mellon requests users of this software to return to
 * 
 *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
 *  School of Computer Science
 *  Carnegie Mellon University
 *  Pittsburgh PA 15213-3890
 * 
 * any improvements or extensions that they make and grant Carnegie Mellon
 * the rights to redistribute these changes.
 */
/*
 */
/*
 *	File:	ipc/ipc_splay.h
 *	Author:	Rich Draves
 *	Date:	1989
 *
 *	Declarations of primitive splay tree operations.
 */

#ifndef	_IPC_IPC_SPLAY_H_
#define _IPC_IPC_SPLAY_H_

#include <mach/port.h>
#include <kern/assert.h>
#include <kern/macro_help.h>
#include <ipc/ipc_entry.h>

typedef struct ipc_splay_tree {
	mach_port_name_t ist_name;	/* name used in last lookup */
	ipc_tree_entry_t ist_root;	/* root of middle tree */
	ipc_tree_entry_t ist_ltree;	/* root of left tree */
	ipc_tree_entry_t *ist_ltreep;	/* pointer into left tree */
	ipc_tree_entry_t ist_rtree;	/* root of right tree */
	ipc_tree_entry_t *ist_rtreep;	/* pointer into right tree */
} *ipc_splay_tree_t;

#define	ist_lock(splay)		/* no locking */
#define ist_unlock(splay)	/* no locking */

/* Initialize a raw splay tree */
extern void ipc_splay_tree_init(
	ipc_splay_tree_t	splay);

/* Pick a random entry in a splay tree */
extern boolean_t ipc_splay_tree_pick(
	ipc_splay_tree_t	splay,
	mach_port_name_t	*namep,
	ipc_tree_entry_t	*entryp);

/* Find an entry in a splay tree */
extern ipc_tree_entry_t ipc_splay_tree_lookup(
	ipc_splay_tree_t	splay,
	mach_port_name_t	name);

/* Insert a new entry into a splay tree */
extern void ipc_splay_tree_insert(
	ipc_splay_tree_t	splay,
	mach_port_name_t	name,
	ipc_tree_entry_t	entry);

/* Delete an entry from a splay tree */
extern void ipc_splay_tree_delete(
	ipc_splay_tree_t	splay,
	mach_port_name_t	name,
	ipc_tree_entry_t	entry);

/* Split a splay tree */
extern void ipc_splay_tree_split(
	ipc_splay_tree_t	splay,
	mach_port_name_t	name,
	ipc_splay_tree_t	entry);

/* Join two splay trees */
extern void ipc_splay_tree_join(
	ipc_splay_tree_t	splay,
	ipc_splay_tree_t	small);

/* Do a bounded splay tree lookup */
extern void ipc_splay_tree_bounds(
	ipc_splay_tree_t	splay,
	mach_port_name_t	name,
	mach_port_name_t	*lowerp, 
	mach_port_name_t	*upperp);

/* Initialize a symmetric order traversal of a splay tree */
extern ipc_tree_entry_t ipc_splay_traverse_start(
	ipc_splay_tree_t	splay);

/* Return the next entry in a symmetric order traversal of a splay tree */
extern ipc_tree_entry_t ipc_splay_traverse_next(
	ipc_splay_tree_t	splay,
	boolean_t		delete);

/* Terminate a symmetric order traversal of a splay tree */
extern void ipc_splay_traverse_finish(
	ipc_splay_tree_t	splay);

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