osfmk/ipc/ipc_splay.h

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_OSREFERENCE_HEADER_START@
   5  *
   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@
  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_ */