1 | /* SPDX-License-Identifier: GPL-2.0-or-later */ |
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 | /* The alignment might seem pointless, but allegedly CRIS needs it */ |
11 | |
12 | struct rb_root { |
13 | struct rb_node *rb_node; |
14 | }; |
15 | |
16 | /* |
17 | * Leftmost-cached rbtrees. |
18 | * |
19 | * We do not cache the rightmost node based on footprint |
20 | * size vs number of potential users that could benefit |
21 | * from O(1) rb_last(). Just not worth it, users that want |
22 | * this feature can always implement the logic explicitly. |
23 | * Furthermore, users that want to cache both pointers may |
24 | * find it a bit asymmetric, but that's ok. |
25 | */ |
26 | struct rb_root_cached { |
27 | struct rb_root rb_root; |
28 | struct rb_node *rb_leftmost; |
29 | }; |
30 | |
31 | #define RB_ROOT (struct rb_root) { NULL, } |
32 | #define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL } |
33 | |
34 | #endif |
35 | |