Changeset 0cb4257 in rtems


Ignore:
Timestamp:
Jul 3, 2018, 6:32:31 PM (10 months ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
master
Children:
22d9575
Parents:
877aeab
git-author:
Sebastian Huber <sebastian.huber@…> (07/03/18 18:32:31)
git-committer:
Sebastian Huber <sebastian.huber@…> (07/16/18 05:22:11)
Message:

linux: Simplify <linux/rbtree.h>

Remove the placeholder struct rb_node and use RBTree_Node directly via
some C pre-processor defines to adjust the member names.

Update #3465.

Location:
cpukit
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • cpukit/include/linux/rbtree.h

    r877aeab r0cb4257  
    1818#include <rtems/score/rbtree.h>
    1919
    20 struct rb_node {
    21   struct rb_node *rb_left;
    22   struct rb_node *rb_right;
    23   struct rb_node *rb_parent;
    24   int rb_color;
    25 };
     20#define rb_node RBTree_Node
    2621
    27 RTEMS_STATIC_ASSERT(
    28   sizeof( struct rb_node ) == sizeof( RBTree_Node ),
    29   rb_node_size
    30 );
     22#define rb_left Node.rbe_left
    3123
    32 RTEMS_STATIC_ASSERT(
    33   offsetof( struct rb_node, rb_left ) == offsetof( RBTree_Node, Node.rbe_left ),
    34   rb_node_left
    35 );
     24#define rb_right Node.rbe_right
    3625
    37 RTEMS_STATIC_ASSERT(
    38   offsetof( struct rb_node, rb_right ) == offsetof( RBTree_Node, Node.rbe_right ),
    39   rb_node_right
    40 );
    41 
    42 RTEMS_STATIC_ASSERT(
    43   offsetof( struct rb_node, rb_parent ) == offsetof( RBTree_Node, Node.rbe_parent ),
    44   rb_node_parent
    45 );
    46 
    47 RTEMS_STATIC_ASSERT(
    48   offsetof( struct rb_node, rb_color ) == offsetof( RBTree_Node, Node.rbe_color ),
    49   rb_node_color
    50 );
    51 
     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 */
    5248struct rb_root {
    53   struct rb_node *rb_node;
     49  RBTree_Node *rb_node;
    5450};
    5551
     
    7167static inline void rb_insert_color( struct rb_node *node, struct rb_root *root)
    7268{
    73   _RBTree_Insert_color( (RBTree_Control *) root, (RBTree_Node *) node );
     69  _RBTree_Insert_color( (RBTree_Control *) root, node );
    7470}
    7571
    7672static inline void rb_erase( struct rb_node *node, struct rb_root *root )
    7773{
    78   _RBTree_Extract( (RBTree_Control *) root, (RBTree_Node *) node );
     74  _RBTree_Extract( (RBTree_Control *) root, node );
    7975}
    8076
    8177static inline struct rb_node *rb_next( struct rb_node *node )
    8278{
    83   return (struct rb_node *) _RBTree_Successor( (RBTree_Node *) node );
     79  return _RBTree_Successor( node );
    8480}
    8581
    8682static inline struct rb_node *rb_prev( struct rb_node *node )
    8783{
    88   return (struct rb_node *) _RBTree_Predecessor( (RBTree_Node *) node );
     84  return _RBTree_Predecessor( node );
    8985}
    9086
    9187static inline struct rb_node *rb_first( struct rb_root *root )
    9288{
    93   return (struct rb_node *) _RBTree_Minimum( (RBTree_Control *) root );
     89  return _RBTree_Minimum( (RBTree_Control *) root );
    9490}
    9591
    9692static inline struct rb_node *rb_last( struct rb_root *root )
    9793{
    98   return (struct rb_node *) _RBTree_Maximum( (RBTree_Control *) root );
     94  return _RBTree_Maximum( (RBTree_Control *) root );
    9995}
    10096
     
    107103  _RBTree_Replace_node(
    108104    (RBTree_Control *) root,
    109     (RBTree_Node *) victim,
    110     (RBTree_Node *) replacement
     105    victim,
     106    replacement
    111107  );
    112108}
     
    118114)
    119115{
    120   _RBTree_Initialize_node( (RBTree_Node *) node );
    121   _RBTree_Add_child(
    122     (RBTree_Node *) node,
    123     (RBTree_Node *) parent,
    124     (RBTree_Node **) link
    125   );
     116  _RBTree_Initialize_node( node );
     117  _RBTree_Add_child( node, parent, link );
    126118}
    127119
    128120static inline struct rb_node *rb_parent( struct rb_node *node )
    129121{
    130   return (struct rb_node *) _RBTree_Parent( (RBTree_Node *) node );
     122  return _RBTree_Parent( node );
    131123}
    132124
  • cpukit/libfs/src/jffs2/src/readinode.c

    r877aeab r0cb4257  
    423423#else /* __rtems__ */
    424424        {
    425                 node->rb_left->rb_parent = node->rb_parent;
    426                 node->rb_left->rb_color = node->rb_color;
     425                node->rb_left->Node.rbe_parent = node->Node.rbe_parent;
     426                node->rb_left->Node.rbe_color = node->Node.rbe_color;
    427427        }
    428428#endif /* __rtems__ */
Note: See TracChangeset for help on using the changeset viewer.