Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
kernel
os
linux
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_node_linked {
13 struct rb_node node;
14 struct rb_node_linked *prev;
15 struct rb_node_linked *next;
16};
17
18struct 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 */
32struct 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 */
41struct 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