diff options
author | Sebastian Andrzej Siewior <bigeasy@linutronix.de> | 2021-08-15 23:28:19 +0200 |
---|---|---|
committer | Ingo Molnar <mingo@kernel.org> | 2021-08-17 17:36:48 +0200 |
commit | 089050cafa10f408c9e18ad53965db839b894840 (patch) | |
tree | b70b0341a2371dcc54853fc1864c53055515c74d /include/linux/rbtree_types.h | |
parent | cbcebf5bd3d056d7a0ae332118888d867ac346c0 (diff) | |
download | linux-089050cafa10f408c9e18ad53965db839b894840.tar.bz2 |
rbtree: Split out the rbtree type definitions into <linux/rbtree_types.h>
So we have this header dependency problem on RT:
- <linux/rtmutex.h> needs the definition of 'struct rb_root_cached'.
- <linux/rbtree.h> includes <linux/kernel.h>, which includes <linux/spinlock.h>.
That works nicely for non-RT enabled kernels, but on RT enabled kernels
spinlocks are based on rtmutexes, which creates another circular header
dependency, as <linux/spinlocks.h> will require <linux/rtmutex.h>.
Split out the type definitions and move them into their own header file so
the rtmutex header can include just those.
Signed-off-by: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Link: https://lore.kernel.org/r/20210815211303.542123501@linutronix.de
Diffstat (limited to 'include/linux/rbtree_types.h')
-rw-r--r-- | include/linux/rbtree_types.h | 34 |
1 files changed, 34 insertions, 0 deletions
diff --git a/include/linux/rbtree_types.h b/include/linux/rbtree_types.h new file mode 100644 index 000000000000..45b6ecde3665 --- /dev/null +++ b/include/linux/rbtree_types.h @@ -0,0 +1,34 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +#ifndef _LINUX_RBTREE_TYPES_H +#define _LINUX_RBTREE_TYPES_H + +struct rb_node { + unsigned long __rb_parent_color; + struct rb_node *rb_right; + struct rb_node *rb_left; +} __attribute__((aligned(sizeof(long)))); +/* The alignment might seem pointless, but allegedly CRIS needs it */ + +struct rb_root { + struct rb_node *rb_node; +}; + +/* + * Leftmost-cached rbtrees. + * + * We do not cache the rightmost node based on footprint + * size vs number of potential users that could benefit + * from O(1) rb_last(). Just not worth it, users that want + * this feature can always implement the logic explicitly. + * Furthermore, users that want to cache both pointers may + * find it a bit asymmetric, but that's ok. + */ +struct rb_root_cached { + struct rb_root rb_root; + struct rb_node *rb_leftmost; +}; + +#define RB_ROOT (struct rb_root) { NULL, } +#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL } + +#endif |