source: rtems/cpukit/score/include/rtems/score/rbtree.h @ 7e119990

4.11
Last change on this file since 7e119990 was 7e119990, checked in by Sebastian Huber <sebastian.huber@…>, on Jul 12, 2014 at 7:22:21 PM

rbtree: Delete unused functions

  • Property mode set to 100644
File size: 13.5 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 * @brief Macro to return the structure containing the @a node.
86 *
87 * This macro returns a pointer of type @a container_type that points
88 * to the structure containing @a node, where @a node_field_name is the
89 * field name of the RBTree_Node structure in @a container_type.
90 *
91 */
92#define _RBTree_Container_of(node, container_type, node_field_name) \
93( \
94  (container_type*) \
95    ( (uintptr_t)(node) - offsetof(container_type, node_field_name) ) \
96)
97
98/**
99 *  This type indicates the direction.
100 */
101typedef enum {
102  RBT_LEFT=0,
103  RBT_RIGHT=1
104} RBTree_Direction;
105
106/**
107 * This type defines function pointers for user-provided comparison
108 * function. The function compares two nodes in order to determine
109 * the order in a red-black tree.
110 */
111typedef int (*RBTree_Compare_function)(
112  const RBTree_Node *node1,
113  const RBTree_Node *node2
114);
115
116/**
117 *  @struct RBTree_Control
118 *
119 * This is used to manage a RBT.  A rbtree consists of a tree of zero or more
120 * nodes.
121 *
122 * @note This implementation does not require special checks for
123 *   manipulating the root element of the RBT.
124 *   To accomplish this the @a RBTree_Control structure can be overlaid
125 *   with a @ref RBTree_Node structure to act as a "dummy root",
126 *   which has a NULL parent and its left child is the root.
127 */
128
129/* the RBTree_Control is actually part of the RBTree structure as an
130 * RBTree_Node. The mapping of fields from RBTree_Control to RBTree_Node are:
131 *   permanent_null == parent
132 *   root == left
133 *   first[0] == right
134 */
135typedef struct {
136  /** This points to a NULL. Useful for finding the root. */
137  RBTree_Node *permanent_null;
138  /** This points to the root node of the RBT. */
139  RBTree_Node *root;
140  /** This points to the min and max nodes of this RBT. */
141  RBTree_Node *first[2];
142  /**
143   * Comparison function pointer. Keys to compare have to be found
144   * inside to maintain generality. It has to return 1 if first node
145   * has higher key than second, -1 if lower, 0 if equal.
146   */
147  RBTree_Compare_function compare_function;
148  /** Determines whether the tree accepts duplicate keys. */
149  bool is_unique;
150} RBTree_Control;
151
152/**
153 *  @brief RBTree initializer for an empty rbtree with designator @a name.
154 */
155#define RBTREE_INITIALIZER_EMPTY(name) \
156{ \
157  .permanent_null = NULL, \
158  .root = NULL, \
159  .first[0] = NULL, \
160  .first[1] = NULL, \
161  .compare_function = NULL, \
162  .is_unique = 0 \
163}
164
165/**
166 *  @brief RBTree definition for an empty rbtree with designator @a name.
167 */
168#define RBTREE_DEFINE_EMPTY(name) \
169RBTree_Control name = RBTREE_INITIALIZER_EMPTY(name)
170
171/**
172 *  @brief RBTree_Node initializer for an empty node with designator @a name.
173 */
174#define RBTREE_NODE_INITIALIZER_EMPTY(name) \
175{ \
176  .parent = NULL, \
177  .child[0] = NULL, \
178  .child[1] = NULL, \
179  RBT_RED \
180}
181
182/**
183 *  @brief RBTree definition for an empty rbtree with designator @a name.
184 */
185#define RBTREE_NODE_DEFINE_EMPTY(name) \
186RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY(name)
187
188/**
189 *  @brief Initialize a RBTree Header.
190 *
191 *  This routine initializes @a the_rbtree structure to manage the
192 *  contiguous array of @a number_nodes nodes which starts at
193 *  @a starting_address.  Each node is of @a node_size bytes.
194 *
195 *  @param[in] the_rbtree is the pointer to rbtree header
196 *  @param[in] starting_address is the starting address of first node
197 *  @param[in] number_nodes is the number of nodes in rbtree
198 *  @param[in] node_size is the size of node in bytes
199 */
200void _RBTree_Initialize(
201  RBTree_Control          *the_rbtree,
202  RBTree_Compare_function  compare_function,
203  void                    *starting_address,
204  size_t                   number_nodes,
205  size_t                   node_size,
206  bool                     is_unique
207);
208
209/**
210 * @brief Tries to find a node for the specified key in the tree.
211 *
212 * @param[in] the_rbtree The red-black tree control.
213 * @param[in] the_node A node specifying the key.
214 *
215 * @retval node A node corresponding to the key.  If the tree is not unique
216 * and contains duplicate keys, the set of duplicate keys acts as FIFO.
217 * @retval NULL No node exists in the tree for the key.
218 */
219RBTree_Node *_RBTree_Find(
220  const RBTree_Control *the_rbtree,
221  const RBTree_Node *the_node
222);
223
224/**
225 *  @brief Insert @a the_node on the Red-Black Tree @a the_rbtree.
226 *
227 *  This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
228 *
229 *  @retval 0 Successfully inserted.
230 *  @retval -1 NULL @a the_node.
231 *  @retval RBTree_Node* if one with equal value to @a the_node 's key exists
232 *          in an unique @a the_rbtree.
233 */
234RBTree_Node *_RBTree_Insert(
235  RBTree_Control *the_rbtree,
236  RBTree_Node *the_node
237);
238
239/**
240 *  @brief Extracts (removes) @a the_node from @a the_rbtree.
241 *
242 *  This routine extracts (removes) @a the_node from @a the_rbtree.
243 */
244void _RBTree_Extract(
245  RBTree_Control *the_rbtree,
246  RBTree_Node *the_node
247);
248
249/**
250 * @brief Returns the in-order next node of a node.
251 *
252 * @param[in] node The node.
253 * @param[in] dir The direction.
254 *
255 * @retval NULL The in-order next node does not exist.
256 * @retval otherwise The next node.
257 */
258RBTree_Node *_RBTree_Next(
259  const RBTree_Node *node,
260  RBTree_Direction dir
261);
262
263/**
264 * @brief Set off RBtree.
265 *
266 * This function sets the parent and child fields of the @a node to NULL
267 * indicating the @a node is not part of a rbtree.
268 *
269 */
270RTEMS_INLINE_ROUTINE void _RBTree_Set_off_rbtree(
271    RBTree_Node *node
272    )
273{
274  node->parent = node->child[RBT_LEFT] = node->child[RBT_RIGHT] = NULL;
275}
276
277/**
278 * @brief Is the node off RBTree.
279 *
280 * This function returns true if the @a node is not on a rbtree. A @a node is
281 * off rbtree if the parent and child fields are set to NULL.
282 */
283RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_rbtree(
284    const RBTree_Node *node
285    )
286{
287  return (node->parent == NULL) &&
288         (node->child[RBT_LEFT] == NULL) &&
289         (node->child[RBT_RIGHT] == NULL);
290}
291
292/**
293 * @brief Return pointer to RBTree's root node.
294 *
295 * This function returns a pointer to the root node of @a the_rbtree.
296 */
297RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root(
298  const RBTree_Control *the_rbtree
299)
300{
301  return the_rbtree->root;
302}
303
304/**
305 * @brief Return pointer to RBTree's first node.
306 *
307 * This function returns a pointer to the first node on @a the_rbtree,
308 * where @a dir specifies whether to return the minimum (0) or maximum (1).
309 */
310RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First(
311  const RBTree_Control *the_rbtree,
312  RBTree_Direction dir
313)
314{
315  return the_rbtree->first[dir];
316}
317
318/**
319 * @brief Return pointer to the parent of this node.
320 *
321 * This function returns a pointer to the parent node of @a the_node.
322 */
323RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent(
324  const RBTree_Node *the_node
325)
326{
327  if (!the_node->parent->parent) return NULL;
328  return the_node->parent;
329}
330
331/**
332 * @brief Return pointer to the left of this node.
333 *
334 * This function returns a pointer to the left node of this node.
335 *
336 * @param[in] the_node is the node to be operated upon.
337 *
338 * @return This method returns the left node on the rbtree.
339 */
340RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left(
341  const RBTree_Node *the_node
342)
343{
344  return the_node->child[RBT_LEFT];
345}
346
347/**
348 * @brief Return pointer to the right of this node.
349 *
350 * This function returns a pointer to the right node of this node.
351 *
352 * @param[in] the_node is the node to be operated upon.
353 *
354 * @return This method returns the right node on the rbtree.
355 */
356RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right(
357  const RBTree_Node *the_node
358)
359{
360  return the_node->child[RBT_RIGHT];
361}
362
363/**
364 * @brief Is the RBTree empty.
365 *
366 * This function returns true if there are no nodes on @a the_rbtree and
367 * false otherwise.
368 *
369 * @param[in] the_rbtree is the rbtree to be operated upon.
370 *
371 * @retval true There are no nodes on @a the_rbtree.
372 * @retval false There are nodes on @a the_rbtree.
373 */
374RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty(
375  const RBTree_Control *the_rbtree
376)
377{
378  return (the_rbtree->root == NULL);
379}
380
381/**
382 * @brief Is this the first node on the RBTree.
383 *
384 * This function returns true if @a the_node is the first node on
385 * @a the_rbtree and false otherwise. @a dir specifies whether first means
386 * minimum (0) or maximum (1).
387 *
388 * @retval true @a the_node is the first node on @a the_rbtree.
389 * @retval false @a the_node is not the first node on @a the_rbtree.
390 *
391 */
392RTEMS_INLINE_ROUTINE bool _RBTree_Is_first(
393  const RBTree_Control *the_rbtree,
394  const RBTree_Node *the_node,
395  RBTree_Direction dir
396)
397{
398  return (the_node == _RBTree_First(the_rbtree, dir));
399}
400
401/**
402 * @brief Is this node the RBTree root.
403 *
404 * This function returns true if @a the_node is the root of @a the_rbtree and
405 * false otherwise.
406 *
407 * @retval true @a the_node is the root of @a the_rbtree.
408 * @retval false @a the_node is not the root of @a the_rbtree.
409 */
410RTEMS_INLINE_ROUTINE bool _RBTree_Is_root(
411  const RBTree_Control *the_rbtree,
412  const RBTree_Node    *the_node
413)
414{
415  return (the_node == _RBTree_Root(the_rbtree));
416}
417
418/**
419 * @brief Find the RBTree_Control header given a node in the tree.
420 *
421 * This function returns a pointer to the header of the Red Black
422 * Tree containing @a the_node if it exists, and NULL if not.
423 */
424RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_header(
425    RBTree_Node *the_node
426    )
427{
428  if(!the_node) return NULL;
429  if(!(the_node->parent)) return NULL;
430  while(the_node->parent) the_node = the_node->parent;
431  return (RBTree_Control*)the_node;
432}
433
434/**
435 * @brief Initialize this RBTree as empty.
436 *
437 * This routine initializes @a the_rbtree to contain zero nodes.
438 */
439RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty(
440    RBTree_Control          *the_rbtree,
441    RBTree_Compare_function  compare_function,
442    bool                     is_unique
443    )
444{
445  the_rbtree->permanent_null   = NULL;
446  the_rbtree->root             = NULL;
447  the_rbtree->first[0]         = NULL;
448  the_rbtree->first[1]         = NULL;
449  the_rbtree->compare_function = compare_function;
450  the_rbtree->is_unique        = is_unique;
451}
452
453/**
454 * @brief Returns the predecessor of a node.
455 *
456 * @param[in] node is the node.
457 *
458 * @retval NULL The predecessor does not exist.  Otherwise it returns
459 *         the predecessor node.
460 */
461RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor(
462  const RBTree_Node *node
463)
464{
465  return _RBTree_Next( node, RBT_LEFT );
466}
467
468/**
469 * @brief Returns the successor of a node.
470 *
471 * @param[in] node is the node.
472 *
473 * @retval NULL The successor does not exist.  Otherwise the successor node.
474 */
475RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor(
476  const RBTree_Node *node
477)
478{
479  return _RBTree_Next( node, RBT_RIGHT );
480}
481
482/**
483 * @brief Get the first node.
484 *
485 * This function removes the minimum or maximum node from the_rbtree and
486 * returns a pointer to that node.
487 *
488 * @param[in] the_rbtree is the rbtree to attempt to get the min node from.
489 * @param[in] dir specifies whether to get minimum (0) or maximum (1)
490 *
491 * @return This method returns the min or max node on the rbtree, or NULL.
492 *
493 * @note This routine may return NULL if the RBTree is empty.
494 */
495RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get(
496    RBTree_Control *the_rbtree,
497    RBTree_Direction dir
498    )
499{
500  RBTree_Node *the_node = the_rbtree->first[dir];
501  _RBTree_Extract(the_rbtree, the_node);
502  return the_node;
503}
504
505/**
506 * @brief Determines whether the tree is unique.
507 */
508RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique(
509  const RBTree_Control *the_rbtree
510)
511{
512  return( the_rbtree && the_rbtree->is_unique );
513}
514
515/**@}*/
516
517#ifdef __cplusplus
518}
519#endif
520
521#endif
522/* end of include file */
Note: See TracBrowser for help on using the repository browser.