kernel_5.10 no rt

hc

2023-12-11 6778948f9de86c3cfaf36725a7c87dcff9ba247f

 kernel/include/linux/rbtree.h
..
..
@@ -19,8 +19,18 @@
19
19
 
20
20
 #include <linux/kernel.h>
21
21
 #include <linux/stddef.h>
22
-#include <linux/rbtree_type.h>
23
22
 #include <linux/rcupdate.h>
23
+
24
+struct rb_node {
25
+	unsigned long  __rb_parent_color;
26
+	struct rb_node *rb_right;
27
+	struct rb_node *rb_left;
28
+} __attribute__((aligned(sizeof(long))));
29
+    /* The alignment might seem pointless, but allegedly CRIS needs it */
30
+
31
+struct rb_root {
32
+	struct rb_node *rb_node;
33
+};
24
34
 
25
35
 #define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
26
36
 
..
..
@@ -102,6 +112,21 @@
102
112
 			typeof(*pos), field); 1; }); \
103
113
 	     pos = n)
104
114
 
115
+/*
116
+ * Leftmost-cached rbtrees.
117
+ *
118
+ * We do not cache the rightmost node based on footprint
119
+ * size vs number of potential users that could benefit
120
+ * from O(1) rb_last(). Just not worth it, users that want
121
+ * this feature can always implement the logic explicitly.
122
+ * Furthermore, users that want to cache both pointers may
123
+ * find it a bit asymmetric, but that's ok.
124
+ */
125
+struct rb_root_cached {
126
+	struct rb_root rb_root;
127
+	struct rb_node *rb_leftmost;
128
+};
129
+
105
130
 #define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
106
131
 
107
132
 /* Same as rb_first(), but O(1) */