Changeset f8202273 in rtems


Ignore:
Timestamp:
Aug 31, 2015, 9:30:36 AM (4 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
master
Children:
7def219
Parents:
edf640f
git-author:
Sebastian Huber <sebastian.huber@…> (08/31/15 09:30:36)
git-committer:
Sebastian Huber <sebastian.huber@…> (09/03/15 12:00:26)
Message:

JFFS2: Use RTEMS red-black tree implementation

Location:
cpukit/libfs
Files:
1 deleted
2 edited

Legend:

Unmodified
Added
Removed
  • cpukit/libfs/Makefile.am

    redf640f rf8202273  
    114114libjffs2_a_SOURCES += src/jffs2/src/build.c
    115115libjffs2_a_SOURCES += src/jffs2/src/compat-crc32.c
    116 libjffs2_a_SOURCES += src/jffs2/src/compat-rbtree.c
    117116libjffs2_a_SOURCES += src/jffs2/src/compr.c
    118117libjffs2_a_SOURCES += src/jffs2/src/compr_rtime.c
  • cpukit/libfs/src/jffs2/include/linux/rbtree.h

    redf640f rf8202273  
    1 #ifndef _LINUX_RBTREE_H
    2 #define _LINUX_RBTREE_H
     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 */
    314
    4 #include <stddef.h>
     15#ifndef _LINUX_RBTREE_H
     16#define _LINUX_RBTREE_H
     17
     18#include <rtems/score/rbtree.h>
    519
    620struct rb_node {
    7         struct rb_node *rb_left;
    8         struct rb_node *rb_right;
    9         struct rb_node *rb_parent;
    10         int rb_color;
     21  struct rb_node *rb_left;
     22  struct rb_node *rb_right;
     23  struct rb_node *rb_parent;
     24  int rb_color;
    1125};
    1226
     27RTEMS_STATIC_ASSERT(
     28  sizeof( struct rb_node ) == sizeof( RBTree_Node ),
     29  rb_node_size
     30);
     31
     32RTEMS_STATIC_ASSERT(
     33  offsetof( struct rb_node, rb_left ) == offsetof( RBTree_Node, Node.rbe_left ),
     34  rb_node_left
     35);
     36
     37RTEMS_STATIC_ASSERT(
     38  offsetof( struct rb_node, rb_right ) == offsetof( RBTree_Node, Node.rbe_right ),
     39  rb_node_right
     40);
     41
     42RTEMS_STATIC_ASSERT(
     43  offsetof( struct rb_node, rb_parent ) == offsetof( RBTree_Node, Node.rbe_parent ),
     44  rb_node_parent
     45);
     46
     47RTEMS_STATIC_ASSERT(
     48  offsetof( struct rb_node, rb_color ) == offsetof( RBTree_Node, Node.rbe_color ),
     49  rb_node_color
     50);
     51
    1352struct rb_root {
    14         struct rb_node *rb_node;
     53  struct rb_node *rb_node;
    1554};
    16 #define RB_ROOT ((struct rb_root){0})
    17 #define rb_entry(p, container, field)           \
    18         ((container *) ((char *)p - offsetof(container, field)))
    1955
    20 #define RB_BLACK        0
    21 #define RB_RED          1
     56RTEMS_STATIC_ASSERT(
     57  sizeof( struct rb_root ) == sizeof( RBTree_Control ),
     58  rb_root_size
     59);
    2260
     61RTEMS_STATIC_ASSERT(
     62  offsetof( struct rb_root, rb_node ) == offsetof( RBTree_Control, rbh_root ),
     63  rb_root_node
     64);
    2365
    24 extern void rb_insert_color(struct rb_node *, struct rb_root *);
    25 extern void rb_erase(struct rb_node *, struct rb_root *);
     66#undef RB_ROOT
     67#define RB_ROOT ( (struct rb_root) { NULL } )
    2668
    27 extern struct rb_node *rb_next(struct rb_node *);
    28 extern struct rb_node *rb_prev(struct rb_node *);
    29 extern struct rb_node *rb_first(struct rb_root *);
    30 extern struct rb_node *rb_last(struct rb_root *);
     69#define rb_entry( p, container, field ) RTEMS_CONTAINER_OF( p, container, field )
    3170
    32 extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
    33                             struct rb_root *root);
    34 
    35 static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
    36                                 struct rb_node ** rb_link)
     71static inline void rb_insert_color( struct rb_node *node, struct rb_root *root)
    3772{
    38         node->rb_parent = parent;
    39         node->rb_color = RB_RED;
    40         node->rb_left = node->rb_right = NULL;
    41 
    42         *rb_link = node;
     73  _RBTree_Insert_color( (RBTree_Control *) root, (RBTree_Node *) node );
    4374}
    4475
    45 static inline struct rb_node *rb_parent(struct rb_node * node)
     76static inline void rb_erase( struct rb_node *node, struct rb_root *root )
    4677{
    47         return node->rb_parent;
     78  _RBTree_Extract( (RBTree_Control *) root, (RBTree_Node *) node );
    4879}
    4980
    50 #endif  /* _LINUX_RBTREE_H */
     81static inline struct rb_node *rb_next( struct rb_node *node )
     82{
     83  return (struct rb_node *) _RBTree_Successor( (RBTree_Node *) node );
     84}
     85
     86static inline struct rb_node *rb_prev( struct rb_node *node )
     87{
     88  return (struct rb_node *) _RBTree_Predecessor( (RBTree_Node *) node );
     89}
     90
     91static inline struct rb_node *rb_first( struct rb_root *root )
     92{
     93  return (struct rb_node *) _RBTree_Minimum( (RBTree_Control *) root );
     94}
     95
     96static inline struct rb_node *rb_last( struct rb_root *root )
     97{
     98  return (struct rb_node *) _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    (RBTree_Node *) victim,
     110    (RBTree_Node *) 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_Add_child(
     121    (RBTree_Node *) node,
     122    (RBTree_Node *) parent,
     123    (RBTree_Node **) link
     124  );
     125}
     126
     127static inline struct rb_node *rb_parent( struct rb_node *node )
     128{
     129  return (struct rb_node *) _RBTree_Parent( (RBTree_Node *) node );
     130}
     131
     132#endif /* _LINUX_RBTREE_H */
Note: See TracChangeset for help on using the changeset viewer.