source: rtems/cpukit/sapi/inline/rtems/rbtree.inl @ 7e4572f

Last change on this file since 7e4572f was 7e4572f, checked in by Sebastian Huber <sebastian.huber@…>, on 04/10/12 at 08:25:14

rbtree: PR1995: API change

New functions

o _RBTree_Next_unprotected(),
o _RBTree_Next(),
o _RBTree_Successor_unprotected(),
o _RBTree_Predecessor_unprotected(),
o rtems_rbtree_successor_unprotected(), and
o rtems_rbtree_predecessor_unprotected().

Change prototype of

o _RBTree_Successor(),
o _RBTree_Predecessor(),
o rtems_rbtree_successor(), and
o rtems_rbtree_predecessor().

  • Property mode set to 100644
File size: 10.9 KB
Line 
1/**
2 * @file rtems/rbtree.inl
3 *
4 *  This include file contains all the constants and structures associated
5 *  with the RBTree API in RTEMS. The rbtree is a Red Black Tree that
6 *  is part of the Super Core. This is the published interface to that
7 *  code.
8 *
9 */
10 
11/*
12 *  Copyright (c) 2010 Gedare Bloom.
13 *
14 *  The license and distribution terms for this file may be
15 *  found in the file LICENSE in this distribution or at
16 *  http://www.rtems.com/license/LICENSE.
17 *
18 *  $Id$
19 */
20
21#ifndef _RTEMS_RBTREE_H
22# error "Never use <rtems/rbtree.inl> directly; include <rtems/rbtree.h> instead."
23#endif
24
25#ifndef _RTEMS_RBTREE_INL
26#define _RTEMS_RBTREE_INL
27
28#include <rtems/score/rbtree.inl>
29
30/**
31 *  @brief Initialize a RBTree Header
32 *
33 *  This routine initializes @a the_rbtree structure to manage the
34 *  contiguous array of @a number_nodes nodes which starts at
35 *  @a starting_address.  Each node is of @a node_size bytes.
36 */
37RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
38  rtems_rbtree_control          *the_rbtree,
39  rtems_rbtree_compare_function  compare_function,
40  void                          *starting_address,
41  size_t                         number_nodes,
42  size_t                         node_size,
43  rtems_rbtree_unique            is_unique
44)
45{
46  _RBTree_Initialize( the_rbtree, compare_function, starting_address,
47    number_nodes, node_size, is_unique);
48}
49
50/**
51 *  @brief Initialize this RBTree as Empty
52 *
53 *  This routine initializes @a the_rbtree to contain zero nodes.
54 */
55RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty(
56  rtems_rbtree_control          *the_rbtree,
57  rtems_rbtree_compare_function  compare_function,
58  rtems_rbtree_unique            is_unique
59)
60{
61  _RBTree_Initialize_empty( the_rbtree, compare_function, is_unique );
62}
63
64/**
65 *  @brief Set off rbtree
66 *
67 *  This function sets the next and previous fields of the @a node to NULL
68 *  indicating the @a node is not part of any rbtree.
69 */
70RTEMS_INLINE_ROUTINE void rtems_rbtree_set_off_rbtree(
71  rtems_rbtree_node *node
72)
73{
74  _RBTree_Set_off_rbtree( node );
75}
76
77/**
78 *  @brief Is the Node off RBTree
79 *
80 *  This function returns true if the @a node is not on a rbtree. A @a node is
81 *  off rbtree if the next and previous fields are set to NULL.
82 */
83RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_node_off_rbtree(
84  const rtems_rbtree_node *node
85)
86{
87  return _RBTree_Is_node_off_rbtree( node );
88}
89
90/**
91 *  @brief Is the RBTree Node Pointer NULL
92 *
93 *  This function returns true if @a the_node is NULL and false otherwise.
94 */
95RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_null_node(
96  const rtems_rbtree_node *the_node
97)
98{
99  return _RBTree_Is_null_node( the_node );
100}
101
102/**
103 *  @brief Return pointer to RBTree Root
104 *
105 *  This function returns a pointer to the root node of @a the_rbtree.
106 */
107RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_root(
108  const rtems_rbtree_control *the_rbtree
109)
110{
111  return _RBTree_Root( the_rbtree );
112}
113
114/**
115 *  @brief Return pointer to RBTree Minimum
116 *
117 *  This function returns a pointer to the minimum node of @a the_rbtree.
118 */
119RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_min(
120  const rtems_rbtree_control *the_rbtree
121)
122{
123  return _RBTree_First( the_rbtree, RBT_LEFT );
124}
125
126/**
127 *  @brief Return pointer to RBTree Maximum
128 *
129 *  This function returns a pointer to the maximum node of @a the_rbtree.
130 */
131RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_max(
132  const rtems_rbtree_control *the_rbtree
133)
134{
135  return _RBTree_First( the_rbtree, RBT_RIGHT );
136}
137
138/**
139 *  @brief Return pointer to the left child node from this node
140 *
141 *  This function returns a pointer to the left child node of @a the_node.
142 */
143RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_left(
144  const rtems_rbtree_node *the_node
145)
146{
147  return _RBTree_Left( the_node );
148}
149
150/**
151 *  @brief Return pointer to the right child node from this node
152 *
153 *  This function returns a pointer to the right child node of @a the_node.
154 */
155RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_right(
156  const rtems_rbtree_node *the_node
157)
158{
159  return _RBTree_Right( the_node );
160}
161
162/**
163 *  @brief Return pointer to the parent child node from this node
164 *
165 *  This function returns a pointer to the parent node of @a the_node.
166 */
167RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_parent(
168  const rtems_rbtree_node *the_node
169)
170{
171  return _RBTree_Parent( the_node );
172}
173
174/**
175 *  @brief Are Two Nodes Equal
176 *
177 *  This function returns true if @a left and @a right are equal,
178 *  and false otherwise.
179 */
180RTEMS_INLINE_ROUTINE bool rtems_rbtree_are_nodes_equal(
181  const rtems_rbtree_node *left,
182  const rtems_rbtree_node *right
183)
184{
185  return _RBTree_Are_nodes_equal( left, right );
186}
187
188/**
189 *  @brief Is the RBTree Empty
190 *
191 *  This function returns true if there a no nodes on @a the_rbtree and
192 *  false otherwise.
193 */
194RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_empty(
195  const rtems_rbtree_control *the_rbtree
196)
197{
198  return _RBTree_Is_empty( the_rbtree );
199}
200
201/**
202 *  @brief Is this the Minimum Node on the RBTree
203 *
204 *  This function returns true if @a the_node is the min node on @a the_rbtree
205 *  and false otherwise.
206 */
207RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_min(
208  const rtems_rbtree_control *the_rbtree,
209  const rtems_rbtree_node *the_node
210)
211{
212  return _RBTree_Is_first( the_rbtree, the_node, RBT_LEFT );
213}
214
215/**
216 *  @brief Is this the Maximum Node on the RBTree
217 *
218 *  This function returns true if @a the_node is the max node on @a the_rbtree
219 *  and false otherwise.
220 */
221RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_max(
222  const rtems_rbtree_control *the_rbtree,
223  const rtems_rbtree_node *the_node
224)
225{
226  return _RBTree_Is_first( the_rbtree, the_node, RBT_RIGHT );
227}
228
229
230/**
231 *  @brief Does this RBTree have only One Node
232 *
233 *  This function returns true if there is only one node on @a the_rbtree and
234 *  false otherwise.
235 */
236RTEMS_INLINE_ROUTINE bool rtems_rbtree_has_only_one_node(
237  const rtems_rbtree_control *the_rbtree
238)
239{
240  return _RBTree_Has_only_one_node( the_rbtree );
241}
242
243/**
244 *  @brief Is this Node the RBTree Root
245 *
246 *  This function returns true if @a the_node is the root of @a the_rbtree and
247 *  false otherwise.
248 */
249RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root(
250  const rtems_rbtree_control *the_rbtree,
251  const rtems_rbtree_node *the_node
252)
253{
254  return _RBTree_Is_root( the_rbtree, the_node );
255}
256
257/** @brief Find the node with given key in the tree
258 *
259 *  This function returns a pointer to the node having key equal to the key
260 *  of @a the_node if it exists within @a the_rbtree, and NULL if not.
261 *  @a the_node has to be made up before a search.
262 *
263 *  @note If the tree is not unique and contains duplicate keys, the set
264 *        of duplicate keys acts as FIFO.
265 */
266RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
267  rtems_rbtree_control *the_rbtree,
268  rtems_rbtree_node *the_node
269)
270{
271  return _RBTree_Find( the_rbtree, the_node );
272}
273
274/**
275 * @copydoc _RBTree_Predecessor_unprotected()
276 */
277RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor_unprotected(
278  const rtems_rbtree_control *rbtree,
279  const rtems_rbtree_node *node
280)
281{
282  return _RBTree_Predecessor_unprotected( rbtree, node );
283}
284
285/**
286 * @copydoc _RBTree_Predecessor()
287 */
288RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor(
289  const rtems_rbtree_control *rbtree,
290  const rtems_rbtree_node *node
291)
292{
293  return _RBTree_Predecessor( rbtree, node );
294}
295
296/**
297 * @copydoc _RBTree_Successor_unprotected()
298 */
299RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor_unprotected(
300  const rtems_rbtree_control *rbtree,
301  const rtems_rbtree_node *node
302)
303{
304  return _RBTree_Successor_unprotected( rbtree, node );
305}
306
307/**
308 * @copydoc _RBTree_Successor()
309 */
310RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor(
311  const rtems_rbtree_control *rbtree,
312  const rtems_rbtree_node *node
313)
314{
315  return _RBTree_Successor( rbtree, node );
316}
317
318/**
319 *  @brief Extract the specified node from a rbtree
320 *
321 *  This routine extracts @a the_node from @a the_rbtree on which it resides.
322 *  It disables interrupts to ensure the atomicity of the extract operation.
323 */
324RTEMS_INLINE_ROUTINE void rtems_rbtree_extract(
325  rtems_rbtree_control *the_rbtree,
326  rtems_rbtree_node *the_node
327)
328{
329  _RBTree_Extract( the_rbtree, the_node );
330}
331
332/**
333 *  @brief Obtain the min node on a rbtree
334 *
335 *  This function removes the min node from @a the_rbtree and returns
336 *  a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
337 *  It disables interrupts to ensure the atomicity of the get operation.
338 */
339RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_min(
340  rtems_rbtree_control *the_rbtree
341)
342{
343  return _RBTree_Get( the_rbtree, RBT_LEFT );
344}
345
346/**
347 *  @brief Obtain the max node on a rbtree
348 *
349 *  This function removes the max node from @a the_rbtree and returns
350 *  a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
351 *  It disables interrupts to ensure the atomicity of the get operation.
352 */
353RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_max(
354  rtems_rbtree_control *the_rbtree
355)
356{
357  return _RBTree_Get( the_rbtree, RBT_RIGHT );
358}
359
360/**
361 *  @brief Peek at the min node on a rbtree
362 *
363 *  This function returns a pointer to the min node from @a the_rbtree
364 *  without changing the tree.  If @a the_rbtree is empty,
365 *  then NULL is returned.
366 *  It disables interrupts to ensure the atomicity of the peek operation.
367 */
368RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_min(
369  const rtems_rbtree_control *the_rbtree
370)
371{
372  return _RBTree_Peek( the_rbtree, RBT_LEFT );
373}
374
375/**
376 *  @brief Peek at the max node on a rbtree
377 *
378 *  This function returns a pointer to the max node from @a the_rbtree
379 *  without changing the tree.  If @a the_rbtree is empty,
380 *  then NULL is returned.
381 *  It disables interrupts to ensure the atomicity of the peek operation.
382 */
383RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_max(
384  const rtems_rbtree_control *the_rbtree
385)
386{
387  return _RBTree_Peek( the_rbtree, RBT_RIGHT );
388}
389
390
391/**
392 *  @brief Find the control header of the tree containing a given node.
393 *
394 *  This routine finds the rtems_rbtree_control structure of the tree
395 *  containing @a the_node.
396 *  It disables interrupts to ensure the atomicity of the find operation.
397 */
398RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_header(
399  rtems_rbtree_node *the_node
400)
401{
402  return(_RBTree_Find_header( the_node ));
403}
404
405/**
406 *  @brief Insert a node on a rbtree
407 *
408 *  This routine inserts @a the_node on @a the_rbtree.
409 *  It disables interrupts to ensure the atomicity of the insert operation.
410 *
411 *  @retval 0 Successfully inserted.
412 *  @retval -1 NULL @a the_node.
413 *  @retval RBTree_Node* if one with equal key to the key of @a the_node exists
414 *          in an unique @a the_rbtree.
415 */
416RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert(
417  rtems_rbtree_control *the_rbtree,
418  rtems_rbtree_node *the_node
419)
420{
421  return _RBTree_Insert( the_rbtree, the_node );
422}
423
424/** @brief Determines whether the tree is unique
425 */
426RTEMS_INLINE_ROUTINE rtems_rbtree_unique rtems_rbtree_is_unique(
427  const rtems_rbtree_control *the_rbtree
428)
429{
430  return( _RBTree_Is_unique(the_rbtree) );
431}
432
433#endif
434/* end of include file */
Note: See TracBrowser for help on using the repository browser.