source: rtems/cpukit/include/linux/rbtree.h @ c5b7942

5
Last change on this file since c5b7942 was c5b7942, checked in by Chris Johns <chrisj@…>, on 08/19/22 at 05:22:17

cpukit/include: Fix including in C++

Closes #4709

  • 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#ifdef __cplusplus
21extern "C" {
22#endif
23
24#define rb_node RBTree_Node
25
26#define rb_left Node.rbe_left
27
28#define rb_right Node.rbe_right
29
30/*
31 * Getting rid of this placeholder structure is a bit difficult.  The use of
32 * this placeholder struct may lead to bugs with link-time optimization due to
33 * a strict aliasing violation.
34 *
35 * A common use of this API is a direct access of the rb_node member to get the
36 * root node of the tree. So, this cannot be changed.
37 *
38 * The red-black tree implementation is provided by <sys/tree.h> and we have
39 *
40 * struct RBTree_Control {
41 *   struct RBTree_Node *rbh_root;
42 * };
43 *
44 * The member name rbh_root is fixed by the <sys/tree.h> API.  To use
45 * RBTree_Control directly we would need two defines:
46 *
47 * #define rb_root RBTree_Control
48 * #define rb_node rbh_root
49 *
50 * We already have an rb_node define to RBTree_Node, see above.
51 */
52struct rb_root {
53  RBTree_Node *rb_node;
54};
55
56RTEMS_STATIC_ASSERT(
57  sizeof( struct rb_root ) == sizeof( RBTree_Control ),
58  rb_root_size
59);
60
61RTEMS_STATIC_ASSERT(
62  offsetof( struct rb_root, rb_node ) == offsetof( RBTree_Control, rbh_root ),
63  rb_root_node
64);
65
66#undef RB_ROOT
67#define RB_ROOT ( (struct rb_root) { NULL } )
68
69#define rb_entry( p, container, field ) RTEMS_CONTAINER_OF( p, container, field )
70
71static inline void rb_insert_color( struct rb_node *node, struct rb_root *root)
72{
73  _RBTree_Insert_color( (RBTree_Control *) root, node );
74}
75
76static inline void rb_erase( struct rb_node *node, struct rb_root *root )
77{
78  _RBTree_Extract( (RBTree_Control *) root, node );
79}
80
81static inline struct rb_node *rb_next( struct rb_node *node )
82{
83  return _RBTree_Successor( node );
84}
85
86static inline struct rb_node *rb_prev( struct rb_node *node )
87{
88  return _RBTree_Predecessor( node );
89}
90
91static inline struct rb_node *rb_first( struct rb_root *root )
92{
93  return _RBTree_Minimum( (RBTree_Control *) root );
94}
95
96static inline struct rb_node *rb_last( struct rb_root *root )
97{
98  return _RBTree_Maximum( (RBTree_Control *) root );
99}
100
101static inline void rb_replace_node(
102  struct rb_node *victim,
103  struct rb_node *replacement,
104  struct rb_root *root
105)
106{
107  _RBTree_Replace_node(
108    (RBTree_Control *) root,
109    victim,
110    replacement
111  );
112}
113
114static inline void rb_link_node(
115  struct rb_node *node,
116  struct rb_node *parent,
117  struct rb_node **link
118)
119{
120  _RBTree_Initialize_node( node );
121  _RBTree_Add_child( node, parent, link );
122}
123
124static inline struct rb_node *rb_parent( struct rb_node *node )
125{
126  return _RBTree_Parent( node );
127}
128
129#define rbtree_postorder_for_each_entry_safe( node, next, root, field ) \
130  for ( \
131    node = _RBTree_Postorder_first( \
132      (RBTree_Control *) root, \
133      offsetof( __typeof__( *node ), field ) \
134    ); \
135    node != NULL && ( \
136      next = _RBTree_Postorder_next( \
137        &node->field, \
138        offsetof( __typeof__( *node ), field ) \
139      ), \
140      node != NULL \
141    ); \
142    node = next \
143  )
144
145#ifdef __cplusplus
146}
147#endif
148
149#endif /* _LINUX_RBTREE_H */
Note: See TracBrowser for help on using the repository browser.