Commit | Line | Data |
---|---|---|
089050ca SAS |
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 |