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