source: rtems/cpukit/sapi/inline/rtems/rbtree.inl @ 74f1c73e

4.115
Last change on this file since 74f1c73e was 74f1c73e, checked in by Joel Sherrill <joel.sherrill@…>, on 08/21/11 at 20:07:11

2011-08-21 Petr Benes <benesp16@…>

PR 1886/cpukit

  • sapi/include/rtems/rbtree.h, sapi/inline/rtems/rbtree.inl, score/include/rtems/score/rbtree.h, score/inline/rtems/score/rbtree.inl, score/src/rbtree.c, score/src/rbtreeinsert.c: This patch enables inserting duplicate keys into rbtree. It is possible to turn on this feature when initializing the tree.
  • Property mode set to 100644
File size: 10.5 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  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  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  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  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  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  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  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  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  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  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/** @brief Find the node's in-order predecessor
275 *
276 * This function returns a pointer to the in-order predecessor
277 * of @a the_node if it exists, and NULL if not.
278 */
279RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor(
280  rtems_rbtree_node *the_node
281)
282{
283  return _RBTree_Predecessor( the_node );
284}
285
286/** @brief Find the node's in-order successor
287 *
288 *  This function returns a pointer to the in-order successor 
289 *  of @a the_node if it exists, and NULL if not.
290 */
291RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor(
292  rtems_rbtree_node *the_node
293)
294{
295  return _RBTree_Successor( the_node );
296}
297
298/**
299 *  @brief Extract the specified node from a rbtree
300 *
301 *  This routine extracts @a the_node from @a the_rbtree on which it resides.
302 *  It disables interrupts to ensure the atomicity of the extract operation.
303 */
304RTEMS_INLINE_ROUTINE void rtems_rbtree_extract(
305  rtems_rbtree_control *the_rbtree,
306  rtems_rbtree_node *the_node
307)
308{
309  _RBTree_Extract( the_rbtree, the_node );
310}
311
312/**
313 *  @brief Obtain the min node on a rbtree
314 *
315 *  This function removes the min node from @a the_rbtree and returns
316 *  a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
317 *  It disables interrupts to ensure the atomicity of the get operation.
318 */
319RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_min(
320  rtems_rbtree_control *the_rbtree
321)
322{
323  return _RBTree_Get( the_rbtree, RBT_LEFT );
324}
325
326/**
327 *  @brief Obtain the max node on a rbtree
328 *
329 *  This function removes the max node from @a the_rbtree and returns
330 *  a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
331 *  It disables interrupts to ensure the atomicity of the get operation.
332 */
333RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_max(
334  rtems_rbtree_control *the_rbtree
335)
336{
337  return _RBTree_Get( the_rbtree, RBT_RIGHT );
338}
339
340/**
341 *  @brief Peek at the min node on a rbtree
342 *
343 *  This function returns a pointer to the min node from @a the_rbtree
344 *  without changing the tree.  If @a the_rbtree is empty,
345 *  then NULL is returned.
346 *  It disables interrupts to ensure the atomicity of the peek operation.
347 */
348RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_min(
349  rtems_rbtree_control *the_rbtree
350)
351{
352  return _RBTree_Peek( the_rbtree, RBT_LEFT );
353}
354
355/**
356 *  @brief Peek at the max node on a rbtree
357 *
358 *  This function returns a pointer to the max node from @a the_rbtree
359 *  without changing the tree.  If @a the_rbtree is empty,
360 *  then NULL is returned.
361 *  It disables interrupts to ensure the atomicity of the peek operation.
362 */
363RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_max(
364  rtems_rbtree_control *the_rbtree
365)
366{
367  return _RBTree_Peek( the_rbtree, RBT_RIGHT );
368}
369
370
371/**
372 *  @brief Find the control header of the tree containing a given node.
373 *
374 *  This routine finds the rtems_rbtree_control structure of the tree
375 *  containing @a the_node.
376 *  It disables interrupts to ensure the atomicity of the find operation.
377 */
378RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_header(
379  rtems_rbtree_node *the_node
380)
381{
382  return(_RBTree_Find_header( the_node ));
383}
384
385/**
386 *  @brief Insert a node on a rbtree
387 *
388 *  This routine inserts @a the_node on @a the_rbtree.
389 *  It disables interrupts to ensure the atomicity of the insert operation.
390 *
391 *  @retval 0 Successfully inserted.
392 *  @retval -1 NULL @a the_node.
393 *  @retval RBTree_Node* if one with equal key to the key of @a the_node exists
394 *          in an unique @a the_rbtree.
395 */
396RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert(
397  rtems_rbtree_control *the_rbtree,
398  rtems_rbtree_node *the_node
399)
400{
401  return _RBTree_Insert( the_rbtree, the_node );
402}
403
404/** @brief Determines whether the tree is unique
405 */
406RTEMS_INLINE_ROUTINE rtems_rbtree_unique rtems_rbtree_is_unique(
407    rtems_rbtree_control *the_rbtree
408)
409{
410  return( _RBTree_Is_unique(the_rbtree) );
411}
412
413#endif
414/* end of include file */
Note: See TracBrowser for help on using the repository browser.