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