1 /**************************************************************************** 2 **************************************************************************** 3 *** 4 *** This header was automatically generated from a Linux kernel header 5 *** of the same name, to make information necessary for userspace to 6 *** call into the kernel available to libc. It contains only constants, 7 *** structures, and macros generated from the original header, and thus, 8 *** contains no copyrightable information. 9 *** 10 **************************************************************************** 11 ****************************************************************************/ 12 #ifndef _LINUX_RBTREE_H 13 #define _LINUX_RBTREE_H 14 15 #include <linux/kernel.h> 16 #include <linux/stddef.h> 17 18 struct rb_node 19 { 20 unsigned long rb_parent_color; 21 #define RB_RED 0 22 #define RB_BLACK 1 23 struct rb_node *rb_right; 24 struct rb_node *rb_left; 25 } __attribute__((aligned(sizeof(long)))); 26 27 struct rb_root 28 { 29 struct rb_node *rb_node; 30 }; 31 32 #define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) 33 #define rb_color(r) ((r)->rb_parent_color & 1) 34 #define rb_is_red(r) (!rb_color(r)) 35 #define rb_is_black(r) rb_color(r) 36 #define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0) 37 #define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0) 38 39 #define RB_ROOT (struct rb_root) { NULL, } 40 #define rb_entry(ptr, type, member) container_of(ptr, type, member) 41 #define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) 42 #define RB_EMPTY_NODE(node) (rb_parent(node) != node) 43 #define RB_CLEAR_NODE(node) (rb_set_parent(node, node)) 44 45 #endif 46
