From 6778948f9de86c3cfaf36725a7c87dcff9ba247f Mon Sep 17 00:00:00 2001
From: hc <hc@nodka.com>
Date: Mon, 11 Dec 2023 08:20:59 +0000
Subject: [PATCH] kernel_5.10 no rt
---
kernel/include/linux/rbtree.h | 27 ++++++++++++++++++++++++++-
1 files changed, 26 insertions(+), 1 deletions(-)
diff --git a/kernel/include/linux/rbtree.h b/kernel/include/linux/rbtree.h
index c33b0e1..d7db179 100644
--- a/kernel/include/linux/rbtree.h
+++ b/kernel/include/linux/rbtree.h
@@ -19,8 +19,18 @@
#include <linux/kernel.h>
#include <linux/stddef.h>
-#include <linux/rbtree_type.h>
#include <linux/rcupdate.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;
+};
#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
@@ -102,6 +112,21 @@
typeof(*pos), field); 1; }); \
pos = n)
+/*
+ * 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_CACHED (struct rb_root_cached) { {NULL, }, NULL }
/* Same as rb_first(), but O(1) */
--
Gitblit v1.6.2