source: rtems/cpukit/include/linux/rbtree.h @ 05b5f9c0

5
Last change on this file since 05b5f9c0 was 4a7c6867, checked in by Sebastian Huber <sebastian.huber@…>, on 10/05/18 at 07:37:44

Fix rbtree_postorder_for_each_entry_safe()

Use the non-standard typeof operator to avoid code generation errors
with clang and use of uninitialized variable warnings with GCC and
Coverity Scan.

Update #3465.

  • Property mode set to 100644
File size: 3.3 KB
Line 
1/*
2 * Copyright (c) 2015 embedded brains GmbH.  All rights reserved.
3 *
4 *  embedded brains GmbH
5 *  Dornierstr. 4
6 *  82178 Puchheim
7 *  Germany
8 *  <rtems@embedded-brains.de>
9 *
10 * The license and distribution terms for this file may be
11 * found in the file LICENSE in this distribution or at
12 * http://www.rtems.org/license/LICENSE.
13 */
14
15#ifndef _LINUX_RBTREE_H
16#define _LINUX_RBTREE_H
17
18#include <rtems/score/rbtree.h>
19
20#define rb_node RBTree_Node
21
22#define rb_left Node.rbe_left
23
24#define rb_right Node.rbe_right
25
26/*
27 * Getting rid of this placeholder structure is a bit difficult.  The use of
28 * this placeholder struct may lead to bugs with link-time optimization due to
29 * a strict aliasing violation.
30 *
31 * A common use of this API is a direct access of the rb_node member to get the
32 * root node of the tree. So, this cannot be changed.
33 *
34 * The red-black tree implementation is provided by <sys/tree.h> and we have
35 *
36 * struct RBTree_Control {
37 *   struct RBTree_Node *rbh_root;
38 * };
39 *
40 * The member name rbh_root is fixed by the <sys/tree.h> API.  To use
41 * RBTree_Control directly we would need two defines:
42 *
43 * #define rb_root RBTree_Control
44 * #define rb_node rbh_root
45 *
46 * We already have an rb_node define to RBTree_Node, see above.
47 */
48struct rb_root {
49  RBTree_Node *rb_node;
50};
51
52RTEMS_STATIC_ASSERT(
53  sizeof( struct rb_root ) == sizeof( RBTree_Control ),
54  rb_root_size
55);
56
57RTEMS_STATIC_ASSERT(
58  offsetof( struct rb_root, rb_node ) == offsetof( RBTree_Control, rbh_root ),
59  rb_root_node
60);
61
62#undef RB_ROOT
63#define RB_ROOT ( (struct rb_root) { NULL } )
64
65#define rb_entry( p, container, field ) RTEMS_CONTAINER_OF( p, container, field )
66
67static inline void rb_insert_color( struct rb_node *node, struct rb_root *root)
68{
69  _RBTree_Insert_color( (RBTree_Control *) root, node );
70}
71
72static inline void rb_erase( struct rb_node *node, struct rb_root *root )
73{
74  _RBTree_Extract( (RBTree_Control *) root, node );
75}
76
77static inline struct rb_node *rb_next( struct rb_node *node )
78{
79  return _RBTree_Successor( node );
80}
81
82static inline struct rb_node *rb_prev( struct rb_node *node )
83{
84  return _RBTree_Predecessor( node );
85}
86
87static inline struct rb_node *rb_first( struct rb_root *root )
88{
89  return _RBTree_Minimum( (RBTree_Control *) root );
90}
91
92static inline struct rb_node *rb_last( struct rb_root *root )
93{
94  return _RBTree_Maximum( (RBTree_Control *) root );
95}
96
97static inline void rb_replace_node(
98  struct rb_node *victim,
99  struct rb_node *replacement,
100  struct rb_root *root
101)
102{
103  _RBTree_Replace_node(
104    (RBTree_Control *) root,
105    victim,
106    replacement
107  );
108}
109
110static inline void rb_link_node(
111  struct rb_node *node,
112  struct rb_node *parent,
113  struct rb_node **link
114)
115{
116  _RBTree_Initialize_node( node );
117  _RBTree_Add_child( node, parent, link );
118}
119
120static inline struct rb_node *rb_parent( struct rb_node *node )
121{
122  return _RBTree_Parent( node );
123}
124
125#define rbtree_postorder_for_each_entry_safe( node, next, root, field ) \
126  for ( \
127    node = _RBTree_Postorder_first( \
128      (RBTree_Control *) root, \
129      offsetof( __typeof__( *node ), field ) \
130    ); \
131    node != NULL && ( \
132      next = _RBTree_Postorder_next( \
133        &node->field, \
134        offsetof( __typeof__( *node ), field ) \
135      ), \
136      node != NULL \
137    ); \
138    node = next \
139  )
140
141#endif /* _LINUX_RBTREE_H */
Note: See TracBrowser for help on using the repository browser.