1/* SPDX-License-Identifier: GPL-2.0-or-later */
2#ifndef _LINUX_RBTREE_TYPES_H
3#define _LINUX_RBTREE_TYPES_H
4
5struct 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
12struct 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 */
26struct 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