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