packages/compat/linux/v2_0/include/linux/rbtree.h

   1 #ifndef _LINUX_RBTREE_H
   2 #define _LINUX_RBTREE_H
   3
   4
   5 struct rb_node {
   6         struct rb_node *rb_left;        /* left element */
   7         struct rb_node *rb_right;       /* right element */
   8         struct rb_node *rb_parent;      /* parent element */
   9         int rb_color;                   /* node color */
  10 };
  11
  12 struct rb_root {
  13         struct rb_node *rb_node; /* root of the tree */
  14 };
  15 #define NULL ((void *)0)
  16 #define RB_ROOT ((struct rb_root){NULL})
  17 #define rb_entry(p, container, field)           \
  18         ((container *) ((char *)p - ((char *)&(((container *)0)->field))))
  19
  20 #define RB_BLACK        0
  21 #define RB_RED          1
  22
  23
  24 extern void rb_insert_color(struct rb_node *, struct rb_root *);
  25 extern void rb_erase(struct rb_node *, struct rb_root *);
  26
  27 /* Find logical next and previous nodes in a tree */
  28 extern struct rb_node *rb_next(struct rb_node *);
  29 extern struct rb_node *rb_prev(struct rb_node *);
  30 extern struct rb_node *rb_first(struct rb_root *);
  31
  32 /* Fast replacement of a single node without remove/rebalance/add/rebalance */
  33 extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
  34                             struct rb_root *root);
  35
  36 static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
  37                                 struct rb_node ** rb_link)
  38 {
  39         node->rb_parent = parent;
  40         node->rb_color = RB_RED;
  41         node->rb_left = node->rb_right = NULL;
  42
  43         *rb_link = node;
  44 }
  45
  46 #endif  /* _LINUX_RBTREE_H */