| 1 |
|
| 2 | #ifndef _LINUX_RBTREE_TYPES_H
|
| 3 | #define _LINUX_RBTREE_TYPES_H
|
| 4 |
|
| 5 | struct rb_node {
|
| 6 | unsigned long __rb_parent_color;
|
| 7 | struct rb_node *rb_right;
|
| 8 | struct rb_node *rb_left;
|
| 9 | } __attribute__((aligned(sizeof(long))));
|
| 10 |
|
| 11 |
|
| 12 | struct rb_node_linked {
|
| 13 | struct rb_node node;
|
| 14 | struct rb_node_linked *prev;
|
| 15 | struct rb_node_linked *next;
|
| 16 | };
|
| 17 |
|
| 18 | struct rb_root {
|
| 19 | struct rb_node *rb_node;
|
| 20 | };
|
| 21 |
|
| 22 | |
| 23 | * Leftmost-cached rbtrees.
|
| 24 | *
|
| 25 | * We do not cache the rightmost node based on footprint
|
| 26 | * size vs number of potential users that could benefit
|
| 27 | * from O(1) rb_last(). Just not worth it, users that want
|
| 28 | * this feature can always implement the logic explicitly.
|
| 29 | * Furthermore, users that want to cache both pointers may
|
| 30 | * find it a bit asymmetric, but that's ok.
|
| 31 |
|
| 32 | struct rb_root_cached {
|
| 33 | struct rb_root rb_root;
|
| 34 | struct rb_node *rb_leftmost;
|
| 35 | };
|
| 36 |
|
| 37 | |
| 38 | * Leftmost tree with links. This would allow a trivial rb_rightmost update,
|
| 39 | * but that has been omitted due to the lack of users.
|
| 40 |
|
| 41 | struct rb_root_linked {
|
| 42 | struct rb_root rb_root;
|
| 43 | struct rb_node_linked *rb_leftmost;
|
| 44 | };
|
| 45 |
|
| 46 | #define RB_ROOT (struct rb_root) { NULL, }
|
| 47 | #define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
|
| 48 | #define RB_ROOT_LINKED (struct rb_root_linked) { {NULL, }, NULL }
|
| 49 |
|
| 50 | #endif
|