source: rtems/cpukit/score/include/rtems/score/rbtree.h @ 64939bc

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

rbtree: Reduce RBTree_Control size

Remove compare function and is unique indicator from the control
structure. Rename RBTree_Compare_function to RBTree_Compare. Rename
rtems_rbtree_compare_function to rtems_rbtree_compare. Provide C++
compatible initializers. Add compare function and is unique indicator
to _RBTree_Find(), _RBTree_Insert(), rtems_rbtree_find() and
rtems_rbtree_insert(). Remove _RBTree_Is_unique() and
rtems_rbtree_is_unique(). Remove compare function and is unique
indicator from _RBTree_Initialize_empty() and
rtems_rbtree_initialize_empty().

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