source: rtems/cpukit/score/include/rtems/score/rbtree.h @ 60fe374

4.115
Last change on this file since 60fe374 was 60fe374, checked in by Sebastian Huber <sebastian.huber@…>, on 08/03/14 at 11:02:58

rbtree: Add and use RBTree_Compare_result

  • Property mode set to 100644
File size: 14.1 KB
Line 
1/**
2 *  @file  rtems/score/rbtree.h
3 *
4 *  @brief Constants and Structures Associated with the Red-Black Tree Handler
5 *
6 *  This include file contains all the constants and structures associated
7 *  with the Red-Black Tree Handler.
8 */
9
10/*
11 *  Copyright (c) 2010 Gedare Bloom.
12 *
13 *  The license and distribution terms for this file may be
14 *  found in the file LICENSE in this distribution or at
15 *  http://www.rtems.org/license/LICENSE.
16 */
17
18#ifndef _RTEMS_SCORE_RBTREE_H
19#define _RTEMS_SCORE_RBTREE_H
20
21#include <stddef.h>
22
23#include <rtems/score/address.h>
24
25#ifdef __cplusplus
26extern "C" {
27#endif
28
29/**
30 *  @defgroup ScoreRBTree Red-Black Tree Handler
31 *
32 *  @ingroup Score
33 *
34 *  The Red-Black Tree Handler is used to manage sets of entities.  This handler
35 *  provides two data structures.  The rbtree Node data structure is included
36 *  as the first part of every data structure that will be placed on
37 *  a RBTree.  The second data structure is rbtree Control which is used
38 *  to manage a set of rbtree Nodes.
39 */
40/**@{*/
41
42/**
43 *  @typedef RBTree_Node
44 *
45 *  This type definition promotes the name for the RBTree Node used by
46 *  all RTEMS code.  It is a separate type definition because a forward
47 *  reference is required to define it.  See @ref RBTree_Node_struct for
48 *  detailed information.
49 */
50typedef struct RBTree_Node_struct RBTree_Node;
51
52/**
53 * This enum type defines the colors available for the RBTree Nodes
54 */
55typedef enum {
56  RBT_BLACK,
57  RBT_RED
58} RBTree_Color;
59
60/**
61 *  @struct RBTree_Node_struct
62 *
63 *  This is used to manage each element (node) which is placed
64 *  on a RBT.
65 *
66 *  @note Typically, a more complicated structure will use the
67 *        rbtree package.  The more complicated structure will
68 *        include a rbtree node as the first element in its
69 *        control structure.  It will then call the rbtree package
70 *        with a pointer to that node element.  The node pointer
71 *        and the higher level structure start at the same address
72 *        so the user can cast the pointers back and forth.
73 *
74 */
75struct RBTree_Node_struct {
76  /** This points to the node's parent */
77  RBTree_Node *parent;
78  /** child[0] points to the left child, child[1] points to the right child */
79  RBTree_Node *child[2];
80  /** The color of the node. Either red or black */
81  RBTree_Color color;
82};
83
84/**
85 *  This type indicates the direction.
86 */
87typedef enum {
88  RBT_LEFT=0,
89  RBT_RIGHT=1
90} RBTree_Direction;
91
92/**
93 * @brief Integer type for compare results.
94 *
95 * The type is large enough to represent pointers and 32-bit signed integers.
96 *
97 * @see RBTree_Compare.
98 */
99typedef long RBTree_Compare_result;
100
101/**
102 * @brief Compares two red-black tree nodes.
103 *
104 * @param[in] first The first node.
105 * @param[in] second The second node.
106 *
107 * @retval positive The key value of the first node is greater than the one of
108 *   the second node.
109 * @retval 0 The key value of the first node is equal to the one of the second
110 *   node.
111 * @retval negative The key value of the first node is less than the one of the
112 *   second node.
113 */
114typedef RBTree_Compare_result ( *RBTree_Compare )(
115  const RBTree_Node *first,
116  const RBTree_Node *second
117);
118
119/**
120 *  @struct RBTree_Control
121 *
122 * This is used to manage a RBT.  A rbtree consists of a tree of zero or more
123 * nodes.
124 *
125 * @note This implementation does not require special checks for
126 *   manipulating the root element of the RBT.
127 *   To accomplish this the @a RBTree_Control structure can be overlaid
128 *   with a @ref RBTree_Node structure to act as a "dummy root",
129 *   which has a NULL parent and its left child is the root.
130 */
131
132/* the RBTree_Control is actually part of the RBTree structure as an
133 * RBTree_Node. The mapping of fields from RBTree_Control to RBTree_Node are:
134 *   permanent_null == parent
135 *   root == left
136 *   first[0] == right
137 */
138typedef struct {
139  /** This points to a NULL. Useful for finding the root. */
140  RBTree_Node *permanent_null;
141  /** This points to the root node of the RBT. */
142  RBTree_Node *root;
143  /** This points to the min and max nodes of this RBT. */
144  RBTree_Node *first[2];
145} RBTree_Control;
146
147/**
148 *  @brief RBTree initializer for an empty rbtree with designator @a name.
149 */
150#define RBTREE_INITIALIZER_EMPTY( name ) \
151  { NULL, NULL, { NULL, NULL } }
152
153/**
154 *  @brief RBTree definition for an empty rbtree with designator @a name.
155 */
156#define RBTREE_DEFINE_EMPTY( name ) \
157  RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name )
158
159/**
160 *  @brief RBTree_Node initializer for an empty node with designator @a name.
161 */
162#define RBTREE_NODE_INITIALIZER_EMPTY( name ) \
163  { NULL, { NULL, NULL }, RBT_RED }
164
165/**
166 *  @brief RBTree definition for an empty rbtree with designator @a name.
167 */
168#define RBTREE_NODE_DEFINE_EMPTY( name ) \
169  RBTree_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 *
178 *  @param[in] the_rbtree is the pointer to rbtree header
179 *  @param[in] compare The node compare function.
180 *  @param[in] starting_address is the starting address of first node
181 *  @param[in] number_nodes is the number of nodes in rbtree
182 *  @param[in] node_size is the size of node in bytes
183 *  @param[in] is_unique If true, then reject nodes with a duplicate key, else
184 *    otherwise.
185 */
186void _RBTree_Initialize(
187  RBTree_Control *the_rbtree,
188  RBTree_Compare  compare,
189  void           *starting_address,
190  size_t          number_nodes,
191  size_t          node_size,
192  bool            is_unique
193);
194
195/**
196 * @brief Tries to find a node for the specified key in the tree.
197 *
198 * @param[in] the_rbtree The red-black tree control.
199 * @param[in] the_node A node specifying the key.
200 * @param[in] compare The node compare function.
201 * @param[in] is_unique If true, then return the first node with a key equal to
202 *   the one of the node specified if it exits, else return the last node if it
203 *   exists.
204 *
205 * @retval node A node corresponding to the key.  If the tree is not unique
206 * and contains duplicate keys, the set of duplicate keys acts as FIFO.
207 * @retval NULL No node exists in the tree for the key.
208 */
209RBTree_Node *_RBTree_Find(
210  const RBTree_Control *the_rbtree,
211  const RBTree_Node    *the_node,
212  RBTree_Compare        compare,
213  bool                  is_unique
214);
215
216/**
217 * @brief Inserts the node into the red-black tree.
218 *
219 * In case the node is already a node of a tree, then this function yields
220 * unpredictable results.
221 *
222 * @param[in] the_rbtree The red-black tree control.
223 * @param[in] the_node The node to insert.
224 * @param[in] compare The node compare function.
225 * @param[in] is_unique If true, then reject nodes with a duplicate key, else
226 *   insert nodes in FIFO order in case the key value is equal to existing nodes.
227 *
228 * @retval NULL Successfully inserted.
229 * @retval existing_node This is a unique insert and there exists a node with
230 *   an equal key in the tree already.
231 */
232RBTree_Node *_RBTree_Insert(
233  RBTree_Control *the_rbtree,
234  RBTree_Node    *the_node,
235  RBTree_Compare  compare,
236  bool            is_unique
237);
238
239/**
240 * @brief Extracts (removes) the node from the red-black tree.
241 *
242 * This function does not set the node off-tree.  In case this is desired, then
243 * call _RBTree_Set_off_tree() after the extraction.
244 *
245 * In case the node to extract is not a node of the tree, then this function
246 * yields unpredictable results.
247 *
248 * @param[in] the_rbtree The red-black tree control.
249 * @param[in] the_node The node to extract.
250 */
251void _RBTree_Extract(
252  RBTree_Control *the_rbtree,
253  RBTree_Node *the_node
254);
255
256/**
257 * @brief Returns the in-order next node of a node.
258 *
259 * @param[in] node The node.
260 * @param[in] dir The direction.
261 *
262 * @retval NULL The in-order next node does not exist.
263 * @retval otherwise The next node.
264 */
265RBTree_Node *_RBTree_Next(
266  const RBTree_Node *node,
267  RBTree_Direction dir
268);
269
270/**
271 * @brief Sets a red-black tree node as off-tree.
272 *
273 * Do not use this function on nodes which are a part of a tree.
274 *
275 * @param[in] the_node The node to set off-tree.
276 *
277 * @see _RBTree_Is_node_off_tree().
278 */
279RTEMS_INLINE_ROUTINE void _RBTree_Set_off_tree( RBTree_Node *the_node )
280{
281  the_node->parent = NULL;
282}
283
284/**
285 * @brief Returns true, if this red-black tree node is off-tree, and false
286 * otherwise.
287 *
288 * @param[in] the_node The node to test.
289 *
290 * @retval true The node is not a part of a tree (off-tree).
291 * @retval false Otherwise.
292 *
293 * @see _RBTree_Set_off_tree().
294 */
295RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_tree(
296  const RBTree_Node *the_node
297)
298{
299  return the_node->parent == NULL;
300}
301
302/**
303 * @brief Return pointer to RBTree's root node.
304 *
305 * This function returns a pointer to the root node of @a the_rbtree.
306 */
307RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
308  const RBTree_Control *the_rbtree
309)
310{
311  return the_rbtree->root;
312}
313
314/**
315 * @brief Return pointer to RBTree's first node.
316 *
317 * This function returns a pointer to the first node on @a the_rbtree,
318 * where @a dir specifies whether to return the minimum (0) or maximum (1).
319 */
320RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First(
321  const RBTree_Control *the_rbtree,
322  RBTree_Direction dir
323)
324{
325  return the_rbtree->first[dir];
326}
327
328/**
329 * @brief Return pointer to the parent of this node.
330 *
331 * This function returns a pointer to the parent node of @a the_node.
332 */
333RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
334  const RBTree_Node *the_node
335)
336{
337  if (!the_node->parent->parent) return NULL;
338  return the_node->parent;
339}
340
341/**
342 * @brief Return pointer to the left of this node.
343 *
344 * This function returns a pointer to the left node of this node.
345 *
346 * @param[in] the_node is the node to be operated upon.
347 *
348 * @return This method returns the left node on the rbtree.
349 */
350RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left(
351  const RBTree_Node *the_node
352)
353{
354  return the_node->child[RBT_LEFT];
355}
356
357/**
358 * @brief Return pointer to the right of this node.
359 *
360 * This function returns a pointer to the right node of this node.
361 *
362 * @param[in] the_node is the node to be operated upon.
363 *
364 * @return This method returns the right node on the rbtree.
365 */
366RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right(
367  const RBTree_Node *the_node
368)
369{
370  return the_node->child[RBT_RIGHT];
371}
372
373/**
374 * @brief Is the RBTree empty.
375 *
376 * This function returns true if there are no nodes on @a the_rbtree and
377 * false otherwise.
378 *
379 * @param[in] the_rbtree is the rbtree to be operated upon.
380 *
381 * @retval true There are no nodes on @a the_rbtree.
382 * @retval false There are nodes on @a the_rbtree.
383 */
384RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
385  const RBTree_Control *the_rbtree
386)
387{
388  return (the_rbtree->root == NULL);
389}
390
391/**
392 * @brief Is this the first node on the RBTree.
393 *
394 * This function returns true if @a the_node is the first node on
395 * @a the_rbtree and false otherwise. @a dir specifies whether first means
396 * minimum (0) or maximum (1).
397 *
398 * @retval true @a the_node is the first node on @a the_rbtree.
399 * @retval false @a the_node is not the first node on @a the_rbtree.
400 *
401 */
402RTEMS_INLINE_ROUTINE bool _RBTree_Is_first(
403  const RBTree_Control *the_rbtree,
404  const RBTree_Node *the_node,
405  RBTree_Direction dir
406)
407{
408  return (the_node == _RBTree_First(the_rbtree, dir));
409}
410
411/**
412 * @brief Is this node the RBTree root.
413 *
414 * This function returns true if @a the_node is the root of @a the_rbtree and
415 * false otherwise.
416 *
417 * @retval true @a the_node is the root of @a the_rbtree.
418 * @retval false @a the_node is not the root of @a the_rbtree.
419 */
420RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
421  const RBTree_Control *the_rbtree,
422  const RBTree_Node    *the_node
423)
424{
425  return (the_node == _RBTree_Root(the_rbtree));
426}
427
428/**
429 * @brief Finds the red-black tree control given a node in the tree.
430 *
431 * In case the node is not a node of a tree, then this function yields
432 * unpredictable results.
433 *
434 * @param[in] the_node The node of interest.
435 *
436 * @return The red-black tree control of the node.
437 */
438RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_control(
439  const RBTree_Node *the_node
440)
441{
442  RBTree_Node    *parent = the_node->parent;
443  RBTree_Control *rbtree;
444
445  do {
446    rbtree = (RBTree_Control *) parent;
447    parent = parent->parent;
448  } while ( parent != NULL );
449
450  return rbtree;
451}
452
453/**
454 * @brief Initialize this RBTree as empty.
455 *
456 * This routine initializes @a the_rbtree to contain zero nodes.
457 */
458RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
459  RBTree_Control *the_rbtree
460)
461{
462  the_rbtree->permanent_null   = NULL;
463  the_rbtree->root             = NULL;
464  the_rbtree->first[RBT_LEFT]  = NULL;
465  the_rbtree->first[RBT_RIGHT] = NULL;
466}
467
468/**
469 * @brief Returns the predecessor of a node.
470 *
471 * @param[in] node is the node.
472 *
473 * @retval NULL The predecessor does not exist.  Otherwise it returns
474 *         the predecessor node.
475 */
476RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
477  const RBTree_Node *node
478)
479{
480  return _RBTree_Next( node, RBT_LEFT );
481}
482
483/**
484 * @brief Returns the successor of a node.
485 *
486 * @param[in] node is the node.
487 *
488 * @retval NULL The successor does not exist.  Otherwise the successor node.
489 */
490RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor(
491  const RBTree_Node *node
492)
493{
494  return _RBTree_Next( node, RBT_RIGHT );
495}
496
497/**
498 * @brief Gets a node with an extremal key value from the red-black tree.
499 *
500 * This function extracts a node with the minimum or maximum key value from
501 * tree and returns a pointer to that node if it exists.  In case multiple
502 * nodes with a minimum key value exist, then they are extracted in FIFO order.
503 * In case multiple nodes with a maximum key value exist, then they are
504 * extracted in LIFO order.
505 *
506 * @param[in] the_rbtree The red-black tree control.
507 * @param[in] dir Specifies whether to get a node with the minimum (RBT_LEFT)
508 *   or maximum (RBT_RIGHT) key value.
509 *
510 * @retval NULL The tree is empty.
511 * @retval extremal_node A node with a minimal or maximal key value on the
512 *   tree.
513 */
514RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get(
515  RBTree_Control *the_rbtree,
516  RBTree_Direction dir
517)
518{
519  RBTree_Node *the_node = the_rbtree->first[ dir ];
520
521  if ( the_node != NULL ) {
522    _RBTree_Extract( the_rbtree, the_node );
523  }
524
525  return the_node;
526}
527
528/**@}*/
529
530#ifdef __cplusplus
531}
532#endif
533
534#endif
535/* end of include file */
Note: See TracBrowser for help on using the repository browser.