source: rtems/cpukit/sapi/include/rtems/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: 9.4 KB
Line 
1/**
2 * @file
3 *
4 * @brief Constants and Structures Associated with the RBTree API in RTEMS
5 *
6 * This include file contains all the constants and structures associated
7 * with the RBTree API in RTEMS. The rbtree is a Red Black Tree that
8 * is part of the Super Core. This is the published interface to that
9 * code.
10 */
11
12/*
13 *  Copyright (c) 2010 Gedare Bloom.
14 *
15 *  The license and distribution terms for this file may be
16 *  found in the file LICENSE in this distribution or at
17 *  http://www.rtems.org/license/LICENSE.
18 */
19
20#ifndef _RTEMS_RBTREE_H
21#define _RTEMS_RBTREE_H
22
23#include <rtems/score/rbtree.h>
24
25#ifdef __cplusplus
26extern "C" {
27#endif
28
29/**
30 * @defgroup ClassicRBTrees Red-Black Trees
31 *
32 * @ingroup ClassicRTEMS
33 *
34 * @brief A Red-Black Tree container.
35 *
36 * The red-black tree container offers no internal protection against
37 * concurrent access.  The user must ensure that at most one thread at once can
38 * access a red-black tree instance.
39 *
40 * @{
41 */
42
43/**
44 * @typedef rtems_rbtree_node
45 *
46 * A node that can be manipulated in the rbtree.
47 */
48typedef RBTree_Node rtems_rbtree_node;
49
50/**
51 * @typedef rtems_rbtree_control
52 *
53 * The rbtree's control anchors the rbtree.
54 */
55typedef RBTree_Control rtems_rbtree_control;
56
57/**
58 * This type defines function pointers for user-provided comparison
59 * function. The function compares two nodes in order to determine
60 * the order in a red-black tree.
61 */
62typedef RBTree_Compare rtems_rbtree_compare;
63
64/**
65 * @brief RBTree initializer for an empty rbtree with designator @a name.
66 */
67#define RTEMS_RBTREE_INITIALIZER_EMPTY(name) \
68  RBTREE_INITIALIZER_EMPTY(name)
69
70/**
71 * @brief RBTree definition for an empty rbtree with designator @a name.
72 */
73#define RTEMS_RBTREE_DEFINE_EMPTY(name) \
74  RBTREE_DEFINE_EMPTY(name)
75
76/**
77  * @brief macro to return the structure containing the @a node.
78  *
79  * This macro returns a pointer of type @a object_type that points
80  * to the structure containing @a node, where @a object_member is the
81  * field name of the rtems_rbtree_node structure in objects of @a object_type.
82  */
83#define rtems_rbtree_container_of(node,object_type, object_member) \
84  _RBTree_Container_of(node,object_type,object_member)
85
86/**
87 * @brief Initialize a RBTree header.
88 *
89 * This routine initializes @a the_rbtree structure to manage the
90 * contiguous array of @a number_nodes nodes which starts at
91 * @a starting_address.  Each node is of @a node_size bytes.
92 */
93RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
94  rtems_rbtree_control *the_rbtree,
95  rtems_rbtree_compare  compare,
96  void                 *starting_address,
97  size_t                number_nodes,
98  size_t                node_size,
99  bool                  is_unique
100)
101{
102  _RBTree_Initialize( the_rbtree, compare, starting_address,
103    number_nodes, node_size, is_unique);
104}
105
106/**
107 * @brief Initialize this RBTree as Empty
108 *
109 * This routine initializes @a the_rbtree to contain zero nodes.
110 */
111RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty(
112  rtems_rbtree_control *the_rbtree
113)
114{
115  _RBTree_Initialize_empty( the_rbtree );
116}
117
118/**
119 * @brief Set off RBtree.
120 *
121 * This function sets the next and previous fields of the @a node to NULL
122 * indicating the @a node is not part of any rbtree.
123 */
124RTEMS_INLINE_ROUTINE void rtems_rbtree_set_off_rbtree(
125  rtems_rbtree_node *node
126)
127{
128  _RBTree_Set_off_rbtree( node );
129}
130
131/**
132 * @brief Is the Node off RBTree.
133 *
134 * This function returns true if the @a node is not on a rbtree. A @a node is
135 * off rbtree if the next and previous fields are set to NULL.
136 */
137RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_node_off_rbtree(
138  const rtems_rbtree_node *node
139)
140{
141  return _RBTree_Is_node_off_rbtree( node );
142}
143
144/**
145 * @brief Return pointer to RBTree root.
146 *
147 * This function returns a pointer to the root node of @a the_rbtree.
148 */
149RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_root(
150  const rtems_rbtree_control *the_rbtree
151)
152{
153  return _RBTree_Root( the_rbtree );
154}
155
156/**
157 * @brief Return pointer to RBTree Minimum
158 *
159 * This function returns a pointer to the minimum node of @a the_rbtree.
160 */
161RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_min(
162  const rtems_rbtree_control *the_rbtree
163)
164{
165  return _RBTree_First( the_rbtree, RBT_LEFT );
166}
167
168/**
169 * @brief Return pointer to RBTree maximum.
170 *
171 * This function returns a pointer to the maximum node of @a the_rbtree.
172 */
173RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_max(
174  const rtems_rbtree_control *the_rbtree
175)
176{
177  return _RBTree_First( the_rbtree, RBT_RIGHT );
178}
179
180/**
181 * @brief Return pointer to the left child node from this node.
182 *
183 * This function returns a pointer to the left child node of @a the_node.
184 */
185RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_left(
186  const rtems_rbtree_node *the_node
187)
188{
189  return _RBTree_Left( the_node );
190}
191
192/**
193 * @brief Return pointer to the right child node from this node.
194 *
195 * This function returns a pointer to the right child node of @a the_node.
196 */
197RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_right(
198  const rtems_rbtree_node *the_node
199)
200{
201  return _RBTree_Right( the_node );
202}
203
204/**
205 * @brief Return pointer to the parent child node from this node.
206 *
207 * This function returns a pointer to the parent node of @a the_node.
208 */
209RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_parent(
210  const rtems_rbtree_node *the_node
211)
212{
213  return _RBTree_Parent( the_node );
214}
215
216/**
217 * @brief Is the RBTree empty.
218 *
219 * This function returns true if there a no nodes on @a the_rbtree and
220 * false otherwise.
221 */
222RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_empty(
223  const rtems_rbtree_control *the_rbtree
224)
225{
226  return _RBTree_Is_empty( the_rbtree );
227}
228
229/**
230 * @brief Is this the minimum node on the RBTree.
231 *
232 * This function returns true if @a the_node is the min node on @a the_rbtree
233 * and false otherwise.
234 */
235RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_min(
236  const rtems_rbtree_control *the_rbtree,
237  const rtems_rbtree_node *the_node
238)
239{
240  return _RBTree_Is_first( the_rbtree, the_node, RBT_LEFT );
241}
242
243/**
244 * @brief Is this the maximum node on the RBTree.
245 *
246 * This function returns true if @a the_node is the max node on @a the_rbtree
247 * and false otherwise.
248 */
249RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_max(
250  const rtems_rbtree_control *the_rbtree,
251  const rtems_rbtree_node *the_node
252)
253{
254  return _RBTree_Is_first( the_rbtree, the_node, RBT_RIGHT );
255}
256
257/**
258 * @brief Is this node the RBTree root.
259 *
260 * This function returns true if @a the_node is the root of @a the_rbtree and
261 * false otherwise.
262 */
263RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root(
264  const rtems_rbtree_control *the_rbtree,
265  const rtems_rbtree_node *the_node
266)
267{
268  return _RBTree_Is_root( the_rbtree, the_node );
269}
270
271/**
272 * @copydoc _RBTree_Find()
273 */
274RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
275  const rtems_rbtree_control *the_rbtree,
276  const rtems_rbtree_node    *the_node,
277  rtems_rbtree_compare        compare,
278  bool                        is_unique
279)
280{
281  return _RBTree_Find( the_rbtree, the_node, compare, is_unique );
282}
283
284/**
285 * @copydoc _RBTree_Predecessor()
286 */
287RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor(
288  const rtems_rbtree_node *node
289)
290{
291  return _RBTree_Predecessor( node );
292}
293
294/**
295 * @copydoc _RBTree_Successor()
296 */
297RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor(
298  const rtems_rbtree_node *node
299)
300{
301  return _RBTree_Successor( node );
302}
303
304/**
305 * @copydoc _RBTree_Extract()
306 */
307RTEMS_INLINE_ROUTINE void rtems_rbtree_extract(
308  rtems_rbtree_control *the_rbtree,
309  rtems_rbtree_node *the_node
310)
311{
312  _RBTree_Extract( the_rbtree, the_node );
313}
314
315/**
316 * @brief Obtain the min node on a rbtree.
317 *
318 * This function removes the min node from @a the_rbtree and returns
319 * a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
320 */
321
322RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_min(
323  rtems_rbtree_control *the_rbtree
324)
325{
326  return _RBTree_Get( the_rbtree, RBT_LEFT );
327}
328
329/**
330 * @brief Obtain the max node on a rbtree.
331 *
332 * This function removes the max node from @a the_rbtree and returns
333 * a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
334 */
335
336RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_max(
337  rtems_rbtree_control *the_rbtree
338)
339{
340  return _RBTree_Get( the_rbtree, RBT_RIGHT );
341}
342
343/**
344 * @brief Peek at the min node on a rbtree.
345 *
346 * This function returns a pointer to the min node from @a the_rbtree
347 * without changing the tree.  If @a the_rbtree is empty,
348 * then NULL is returned.
349 */
350RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_min(
351  const rtems_rbtree_control *the_rbtree
352)
353{
354  return _RBTree_First( the_rbtree, RBT_LEFT );
355}
356
357/**
358 * @brief Peek at the max node on a rbtree.
359 *
360 * This function returns a pointer to the max node from @a the_rbtree
361 * without changing the tree.  If @a the_rbtree is empty,
362 * then NULL is returned.
363 */
364RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_max(
365  const rtems_rbtree_control *the_rbtree
366)
367{
368  return _RBTree_First( the_rbtree, RBT_RIGHT );
369}
370
371/**
372 * @copydoc _RBTree_Find_header()
373 */
374RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_header(
375  rtems_rbtree_node *the_node
376)
377{
378  return _RBTree_Find_header( the_node );
379}
380
381/**
382 * @copydoc _RBTree_Insert()
383 */
384RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert(
385  rtems_rbtree_control *the_rbtree,
386  rtems_rbtree_node    *the_node,
387  rtems_rbtree_compare  compare,
388  bool                  is_unique
389)
390{
391  return _RBTree_Insert( the_rbtree, the_node, compare, is_unique );
392}
393
394/** @} */
395
396#ifdef __cplusplus
397}
398#endif
399
400#endif
401/* end of include file */
Note: See TracBrowser for help on using the repository browser.