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