source: rtems/cpukit/score/include/rtems/score/rbtree.h @ 13c4f853

4.115
Last change on this file since 13c4f853 was 13c4f853, checked in by Joel Sherrill <joel.sherrill@…>, on 08/02/11 at 19:25:59

2011-08-02 Joel Sherrill <joel.sherrill@…>

PR 1877/cpukit

  • libfs/src/imfs/imfs_mknod.c, libfs/src/imfs/memfile.c, sapi/inline/rtems/rbtree.inl, score/include/rtems/score/rbtree.h, score/inline/rtems/score/rbtree.inl, score/src/rbtree.c, score/src/rbtreefind.c, score/src/rbtreeinsert.c: Add comparison function for RBTrees.
  • Property mode set to 100644
File size: 8.4 KB
Line 
1/**
2 *  @file  rtems/score/rbtree.h
3 *
4 *  This include file contains all the constants and structures associated
5 *  with the Red-Black Tree Handler.
6 */
7
8/*
9 *  Copyright (c) 2010 Gedare Bloom.
10 *
11 *  The license and distribution terms for this file may be
12 *  found in the file LICENSE in this distribution or at
13 *  http://www.rtems.com/license/LICENSE.
14 *
15 *  $Id$
16 */
17
18#ifndef _RTEMS_SCORE_RBTREE_H
19#define _RTEMS_SCORE_RBTREE_H
20
21/**
22 *  @defgroup ScoreRBTree Red-Black Tree Handler
23 *
24 *  @ingroup Score
25 *
26 *  The Red-Black Tree Handler is used to manage sets of entities.  This handler
27 *  provides two data structures.  The rbtree Node data structure is included
28 *  as the first part of every data structure that will be placed on
29 *  a RBTree.  The second data structure is rbtree Control which is used
30 *  to manage a set of rbtree Nodes.
31 */
32/**@{*/
33
34#ifdef __cplusplus
35extern "C" {
36#endif
37
38#include <rtems/score/address.h>
39
40/**
41 *  @typedef RBTree_Node
42 *
43 *  This type definition promotes the name for the RBTree Node used by
44 *  all RTEMS code.  It is a separate type definition because a forward
45 *  reference is required to define it.  See @ref RBTree_Node_struct for
46 *  detailed information.
47 */
48typedef struct RBTree_Node_struct RBTree_Node;
49
50/**
51 * This enum type defines the colors available for the RBTree Nodes
52 */
53typedef enum {
54  RBT_BLACK,
55  RBT_RED
56} RBTree_Color;
57
58/**
59 *  @struct RBTree_Node_struct
60 *
61 *  This is used to manage each element (node) which is placed
62 *  on a RBT.
63 *
64 *  @note Typically, a more complicated structure will use the
65 *        rbtree package.  The more complicated structure will
66 *        include a rbtree node as the first element in its
67 *        control structure.  It will then call the rbtree package
68 *        with a pointer to that node element.  The node pointer
69 *        and the higher level structure start at the same address
70 *        so the user can cast the pointers back and forth.
71 *
72 */
73struct RBTree_Node_struct {
74  /** This points to the node's parent */
75  RBTree_Node *parent;
76  /** child[0] points to the left child, child[1] points to the right child */
77  RBTree_Node *child[2];
78  /** The color of the node. Either red or black */
79  RBTree_Color color;
80};
81
82/**
83 * @brief macro to return the structure containing the @a node.
84 *
85 * This macro returns a pointer of type @a container_type that points
86 * to the structure containing @a node, where @a node_field_name is the
87 * field name of the RBTree_Node structure in @a container_type.
88 *
89 */
90#define _RBTree_Container_of(node,container_type, node_field_name) \
91((container_type*) \
92 ((size_t)node - ((size_t)(&((container_type *)0)->node_field_name))))
93
94/**
95 *  This type indicates the direction.
96 */
97typedef enum {
98  RBT_LEFT=0,
99  RBT_RIGHT=1
100} RBTree_Direction;
101
102/**
103 *  @struct RBTree_Control
104 *
105 * This is used to manage a RBT.  A rbtree consists of a tree of zero or more
106 * nodes.
107 *
108 * @note This implementation does not require special checks for
109 *   manipulating the root element of the RBT.
110 *   To accomplish this the @a RBTree_Control structure can be overlaid
111 *   with a @ref RBTree_Node structure to act as a "dummy root",
112 *   which has a NULL parent and its left child is the root.
113 */
114
115/* the RBTree_Control is actually part of the RBTree structure as an
116 * RBTree_Node. The mapping of fields from RBTree_Control to RBTree_Node are:
117 *   permanent_null == parent
118 *   root == left
119 *   first[0] == right
120 */
121typedef struct {
122  /** This points to a NULL. Useful for finding the root. */
123  RBTree_Node *permanent_null;
124  /** This points to the root node of the RBT. */
125  RBTree_Node *root;
126  /** This points to the min and max nodes of this RBT. */
127  RBTree_Node *first[2];
128  /**
129   * Comparison function pointer. Keys to compare has to be found
130   * inside to maintain generality. It has to return 1 if first node
131   * has higher key than second, -1 if lower, 0 if equal.
132   */
133  int (*compare_function) (RBTree_Node*, RBTree_Node*);
134} RBTree_Control;
135
136/**
137 *  @brief RBTree initializer for an empty rbtree with designator @a name.
138 */
139#define RBTREE_INITIALIZER_EMPTY(name) \
140{ \
141  .permanent_null = NULL, \
142  .root = NULL, \
143  .first[0] = NULL, \
144  .first[1] = NULL, \
145  .compare_function = NULL \
146}
147
148/**
149 *  @brief RBTree definition for an empty rbtree with designator @a name.
150 */
151#define RBTREE_DEFINE_EMPTY(name) \
152RBTree_Control name = RBTREE_INITIALIZER_EMPTY(name)
153
154/**
155 *  @brief RBTree_Node initializer for an empty node with designator @a name.
156 */
157#define RBTREE_NODE_INITIALIZER_EMPTY(name) \
158{ \
159  .parent = NULL, \
160  .child[0] = NULL, \
161  .child[1] = NULL, \
162  RBT_RED \
163}
164
165/**
166 *  @brief RBTree definition for an empty rbtree with designator @a name.
167 */
168#define RBTREE_NODE_DEFINE_EMPTY(name) \
169RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY(name)
170
171/**
172 *  @brief Initialize a RBTree Header
173 *
174 *  This routine initializes @a the_rbtree structure to manage the
175 *  contiguous array of @a number_nodes nodes which starts at
176 *  @a starting_address.  Each node is of @a node_size bytes.
177 */
178void _RBTree_Initialize(
179  RBTree_Control *the_rbtree,
180  void           *compare_function,
181  void           *starting_address,
182  size_t          number_nodes,
183  size_t          node_size
184);
185
186/**
187 *  @brief Obtain the min or max node of a rbtree
188 *
189 *  This function removes the min or max node from @a the_rbtree and returns
190 *  a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
191 *  @a dir specifies whether to return the min (0) or max (1).
192 *
193 *  @return This method returns a pointer to a node.  If a node was removed,
194 *          then a pointer to that node is returned.  If @a the_rbtree was
195 *          empty, then NULL is returned.
196 *
197 *  @note It disables interrupts to ensure the atomicity of the get operation.
198 */
199RBTree_Node *_RBTree_Get(
200  RBTree_Control *the_rbtree,
201  RBTree_Direction dir
202);
203
204/**
205 *  @brief Check the min or max node on a rbtree
206 *
207 *  This function returns a pointer to the min or max node of @a the_rbtree.
208 *  If @a the_rbtree is empty, then NULL is returned. @a dir specifies
209 *  whether to return the min (0) or max (1).
210 *
211 *  @return This method returns a pointer to a node.
212 *          If @a the_rbtree was empty, then NULL is returned.
213 *
214 *  @note It disables interrupts to ensure the atomicity of the get operation.
215 */
216RBTree_Node *_RBTree_Peek(
217  RBTree_Control *the_rbtree,
218  RBTree_Direction dir
219);
220
221/**
222 * @brief Find the node with given key in the tree
223 *
224 *  This function returns a pointer to the node with key equal to a key
225 *  of @a the_node if it exists in the Red-Black Tree @a the_rbtree,
226 *  and NULL if not.
227 */
228RBTree_Node *_RBTree_Find(
229  RBTree_Control *the_rbtree,
230  RBTree_Node *the_node
231);
232
233/**
234 * @brief Find the control structure of the tree containing the given node
235 *
236 *  This function returns a pointer to the control structure of the tree
237 *  containing @a the_node, if it exists, and NULL if not.
238 */
239RBTree_Control *_RBTree_Find_header(
240  RBTree_Node *the_node
241);
242
243/**
244 * @brief Insert a Node (unprotected)
245 *
246 *  This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
247 *
248 *  @retval 0 Successfully inserted.
249 *  @retval -1 NULL @a the_node.
250 *  @retval RBTree_Node* if one with equal value to @a the_node->value exists
251 *          in @a the_rbtree.
252 *
253 *  @note It does NOT disable interrupts to ensure the atomicity
254 *        of the extract operation.
255 */
256RBTree_Node *_RBTree_Insert_unprotected(
257  RBTree_Control *the_rbtree,
258  RBTree_Node *the_node
259);
260
261/**
262 *  @brief Insert a node on a rbtree
263 *
264 *  This routine inserts @a the_node on the tree @a the_rbtree.
265 *
266 *  @note It disables interrupts to ensure the atomicity
267 *  of the extract operation.
268 */
269void _RBTree_Insert(
270  RBTree_Control *the_rbtree,
271  RBTree_Node *the_node
272);
273
274
275/**
276 * @brief Extract a Node (unprotected)
277 *
278 *  This routine extracts (removes) @a the_node from @a the_rbtree.
279 *
280 *  @note It does NOT disable interrupts to ensure the atomicity
281 *        of the extract operation.
282 */
283void _RBTree_Extract_unprotected(
284  RBTree_Control *the_rbtree,
285  RBTree_Node *the_node
286);
287
288/**
289 *  @brief Delete a node from the rbtree
290 *
291 *  This routine deletes @a the_node from @a the_rbtree.
292 *
293 *  @note It disables interrupts to ensure the atomicity of the
294 *  append operation.
295 */
296void _RBTree_Extract(
297  RBTree_Control *the_rbtree,
298  RBTree_Node    *the_node
299);
300
301#ifndef __RTEMS_APPLICATION__
302#include <rtems/score/rbtree.inl>
303#endif
304
305#ifdef __cplusplus
306}
307#endif
308
309/**@}*/
310
311#endif
312/* end of include file */
Note: See TracBrowser for help on using the repository browser.