source: rtems/cpukit/sapi/include/rtems/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: 8.9 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 * @copydoc RBTree_Compare_result
59 */
60typedef RBTree_Compare_result rtems_rbtree_compare_result;
61
62/**
63 * @copydoc RBTree_Compare
64 */
65typedef RBTree_Compare rtems_rbtree_compare;
66
67/**
68 * @brief RBTree initializer for an empty rbtree with designator @a name.
69 */
70#define RTEMS_RBTREE_INITIALIZER_EMPTY(name) \
71  RBTREE_INITIALIZER_EMPTY(name)
72
73/**
74 * @brief RBTree definition for an empty rbtree with designator @a name.
75 */
76#define RTEMS_RBTREE_DEFINE_EMPTY(name) \
77  RBTREE_DEFINE_EMPTY(name)
78
79/**
80 * @brief Initialize a RBTree header.
81 *
82 * This routine initializes @a the_rbtree structure to manage the
83 * contiguous array of @a number_nodes nodes which starts at
84 * @a starting_address.  Each node is of @a node_size bytes.
85 */
86RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
87  rtems_rbtree_control *the_rbtree,
88  rtems_rbtree_compare  compare,
89  void                 *starting_address,
90  size_t                number_nodes,
91  size_t                node_size,
92  bool                  is_unique
93)
94{
95  _RBTree_Initialize( the_rbtree, compare, starting_address,
96    number_nodes, node_size, is_unique);
97}
98
99/**
100 * @brief Initialize this RBTree as Empty
101 *
102 * This routine initializes @a the_rbtree to contain zero nodes.
103 */
104RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty(
105  rtems_rbtree_control *the_rbtree
106)
107{
108  _RBTree_Initialize_empty( the_rbtree );
109}
110
111/**
112 * @brief Set off RBtree.
113 *
114 * This function sets the next and previous fields of the @a node to NULL
115 * indicating the @a node is not part of any rbtree.
116 */
117RTEMS_INLINE_ROUTINE void rtems_rbtree_set_off_tree(
118  rtems_rbtree_node *node
119)
120{
121  _RBTree_Set_off_tree( node );
122}
123
124/**
125 * @brief Is the Node off RBTree.
126 *
127 * This function returns true if the @a node is not on a rbtree. A @a node is
128 * off rbtree if the next and previous fields are set to NULL.
129 */
130RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_node_off_tree(
131  const rtems_rbtree_node *node
132)
133{
134  return _RBTree_Is_node_off_tree( node );
135}
136
137/**
138 * @brief Return pointer to RBTree root.
139 *
140 * This function returns a pointer to the root node of @a the_rbtree.
141 */
142RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_root(
143  const rtems_rbtree_control *the_rbtree
144)
145{
146  return _RBTree_Root( the_rbtree );
147}
148
149/**
150 * @brief Return pointer to RBTree Minimum
151 *
152 * This function returns a pointer to the minimum node of @a the_rbtree.
153 */
154RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_min(
155  const rtems_rbtree_control *the_rbtree
156)
157{
158  return _RBTree_First( the_rbtree, RBT_LEFT );
159}
160
161/**
162 * @brief Return pointer to RBTree maximum.
163 *
164 * This function returns a pointer to the maximum node of @a the_rbtree.
165 */
166RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_max(
167  const rtems_rbtree_control *the_rbtree
168)
169{
170  return _RBTree_First( the_rbtree, RBT_RIGHT );
171}
172
173/**
174 * @brief Return pointer to the left child node from this node.
175 *
176 * This function returns a pointer to the left child node of @a the_node.
177 */
178RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_left(
179  const rtems_rbtree_node *the_node
180)
181{
182  return _RBTree_Left( the_node );
183}
184
185/**
186 * @brief Return pointer to the right child node from this node.
187 *
188 * This function returns a pointer to the right child node of @a the_node.
189 */
190RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_right(
191  const rtems_rbtree_node *the_node
192)
193{
194  return _RBTree_Right( the_node );
195}
196
197/**
198 * @brief Return pointer to the parent child node from this node.
199 *
200 * This function returns a pointer to the parent node of @a the_node.
201 */
202RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_parent(
203  const rtems_rbtree_node *the_node
204)
205{
206  return _RBTree_Parent( the_node );
207}
208
209/**
210 * @brief Is the RBTree empty.
211 *
212 * This function returns true if there a no nodes on @a the_rbtree and
213 * false otherwise.
214 */
215RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_empty(
216  const rtems_rbtree_control *the_rbtree
217)
218{
219  return _RBTree_Is_empty( the_rbtree );
220}
221
222/**
223 * @brief Is this the minimum node on the RBTree.
224 *
225 * This function returns true if @a the_node is the min node on @a the_rbtree
226 * and false otherwise.
227 */
228RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_min(
229  const rtems_rbtree_control *the_rbtree,
230  const rtems_rbtree_node *the_node
231)
232{
233  return _RBTree_Is_first( the_rbtree, the_node, RBT_LEFT );
234}
235
236/**
237 * @brief Is this the maximum node on the RBTree.
238 *
239 * This function returns true if @a the_node is the max node on @a the_rbtree
240 * and false otherwise.
241 */
242RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_max(
243  const rtems_rbtree_control *the_rbtree,
244  const rtems_rbtree_node *the_node
245)
246{
247  return _RBTree_Is_first( the_rbtree, the_node, RBT_RIGHT );
248}
249
250/**
251 * @brief Is this node the RBTree root.
252 *
253 * This function returns true if @a the_node is the root of @a the_rbtree and
254 * false otherwise.
255 */
256RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root(
257  const rtems_rbtree_control *the_rbtree,
258  const rtems_rbtree_node *the_node
259)
260{
261  return _RBTree_Is_root( the_rbtree, the_node );
262}
263
264/**
265 * @copydoc _RBTree_Find()
266 */
267RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
268  const rtems_rbtree_control *the_rbtree,
269  const rtems_rbtree_node    *the_node,
270  rtems_rbtree_compare        compare,
271  bool                        is_unique
272)
273{
274  return _RBTree_Find( the_rbtree, the_node, compare, is_unique );
275}
276
277/**
278 * @copydoc _RBTree_Predecessor()
279 */
280RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor(
281  const rtems_rbtree_node *node
282)
283{
284  return _RBTree_Predecessor( node );
285}
286
287/**
288 * @copydoc _RBTree_Successor()
289 */
290RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor(
291  const rtems_rbtree_node *node
292)
293{
294  return _RBTree_Successor( node );
295}
296
297/**
298 * @copydoc _RBTree_Extract()
299 */
300RTEMS_INLINE_ROUTINE void rtems_rbtree_extract(
301  rtems_rbtree_control *the_rbtree,
302  rtems_rbtree_node *the_node
303)
304{
305  _RBTree_Extract( the_rbtree, the_node );
306}
307
308/**
309 * @brief Obtain the min node on a rbtree.
310 *
311 * This function removes the min node from @a the_rbtree and returns
312 * a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
313 */
314
315RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_min(
316  rtems_rbtree_control *the_rbtree
317)
318{
319  return _RBTree_Get( the_rbtree, RBT_LEFT );
320}
321
322/**
323 * @brief Obtain the max node on a rbtree.
324 *
325 * This function removes the max node from @a the_rbtree and returns
326 * a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
327 */
328
329RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_max(
330  rtems_rbtree_control *the_rbtree
331)
332{
333  return _RBTree_Get( the_rbtree, RBT_RIGHT );
334}
335
336/**
337 * @brief Peek at the min node on a rbtree.
338 *
339 * This function returns a pointer to the min node from @a the_rbtree
340 * without changing the tree.  If @a the_rbtree is empty,
341 * then NULL is returned.
342 */
343RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_min(
344  const rtems_rbtree_control *the_rbtree
345)
346{
347  return _RBTree_First( the_rbtree, RBT_LEFT );
348}
349
350/**
351 * @brief Peek at the max node on a rbtree.
352 *
353 * This function returns a pointer to the max node from @a the_rbtree
354 * without changing the tree.  If @a the_rbtree is empty,
355 * then NULL is returned.
356 */
357RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_max(
358  const rtems_rbtree_control *the_rbtree
359)
360{
361  return _RBTree_First( the_rbtree, RBT_RIGHT );
362}
363
364/**
365 * @copydoc _RBTree_Find_control()
366 */
367RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_control(
368  const rtems_rbtree_node *the_node
369)
370{
371  return _RBTree_Find_control( the_node );
372}
373
374/**
375 * @copydoc _RBTree_Insert()
376 */
377RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert(
378  rtems_rbtree_control *the_rbtree,
379  rtems_rbtree_node    *the_node,
380  rtems_rbtree_compare  compare,
381  bool                  is_unique
382)
383{
384  return _RBTree_Insert( the_rbtree, the_node, compare, is_unique );
385}
386
387/** @} */
388
389#ifdef __cplusplus
390}
391#endif
392
393#endif
394/* end of include file */
Note: See TracBrowser for help on using the repository browser.