add boot partition size

hc

2023-12-11 d2ccde1c8e90d38cee87a1b0309ad2827f3fd30d

 kernel/include/linux/rbtree.h
..
..
@@ -1,20 +1,8 @@
1
+/* SPDX-License-Identifier: GPL-2.0-or-later */
1
2
 /*
2
3
   Red Black Trees
3
4
   (C) 1999  Andrea Arcangeli <andrea@suse.de>
4
5
   
5
-  This program is free software; you can redistribute it and/or modify
6
-  it under the terms of the GNU General Public License as published by
7
-  the Free Software Foundation; either version 2 of the License, or
8
-  (at your option) any later version.
9
-
10
-  This program is distributed in the hope that it will be useful,
11
-  but WITHOUT ANY WARRANTY; without even the implied warranty of
12
-  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13
-  GNU General Public License for more details.
14
-
15
-  You should have received a copy of the GNU General Public License
16
-  along with this program; if not, write to the Free Software
17
-  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18
6
 
19
7
   linux/include/linux/rbtree.h
20
8
 
..
..
@@ -23,7 +11,7 @@
23
11
   I know it's not the cleaner way,  but in C (not in C++) to get
24
12
   performances and genericity...
25
13
 
26
-  See Documentation/rbtree.txt for documentation and samples.
14
+  See Documentation/core-api/rbtree.rst for documentation and samples.
27
15
 */
28
16
 
29
17
 #ifndef	_LINUX_RBTREE_H
..
..
@@ -31,38 +19,12 @@
31
19
 
32
20
 #include <linux/kernel.h>
33
21
 #include <linux/stddef.h>
34
-#include <linux/rcu_assign_pointer.h>
35
-
36
-struct rb_node {
37
-	unsigned long  __rb_parent_color;
38
-	struct rb_node *rb_right;
39
-	struct rb_node *rb_left;
40
-} __attribute__((aligned(sizeof(long))));
41
-    /* The alignment might seem pointless, but allegedly CRIS needs it */
42
-
43
-struct rb_root {
44
-	struct rb_node *rb_node;
45
-};
46
-
47
-/*
48
- * Leftmost-cached rbtrees.
49
- *
50
- * We do not cache the rightmost node based on footprint
51
- * size vs number of potential users that could benefit
52
- * from O(1) rb_last(). Just not worth it, users that want
53
- * this feature can always implement the logic explicitly.
54
- * Furthermore, users that want to cache both pointers may
55
- * find it a bit asymmetric, but that's ok.
56
- */
57
-struct rb_root_cached {
58
-	struct rb_root rb_root;
59
-	struct rb_node *rb_leftmost;
60
-};
22
+#include <linux/rbtree_type.h>
23
+#include <linux/rcupdate.h>
61
24
 
62
25
 #define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
63
26
 
64
27
 #define RB_ROOT	(struct rb_root) { NULL, }
65
-#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
66
28
 #define	rb_entry(ptr, type, member) container_of(ptr, type, member)
67
29
 
68
30
 #define RB_EMPTY_ROOT(root)  (READ_ONCE((root)->rb_node) == NULL)
..
..
@@ -84,12 +46,6 @@
84
46
 extern struct rb_node *rb_first(const struct rb_root *);
85
47
 extern struct rb_node *rb_last(const struct rb_root *);
86
48
 
87
-extern void rb_insert_color_cached(struct rb_node *,
88
-				   struct rb_root_cached *, bool);
89
-extern void rb_erase_cached(struct rb_node *node, struct rb_root_cached *);
90
-/* Same as rb_first(), but O(1) */
91
-#define rb_first_cached(root) (root)->rb_leftmost
92
-
93
49
 /* Postorder iteration - always visit the parent after its children */
94
50
 extern struct rb_node *rb_first_postorder(const struct rb_root *);
95
51
 extern struct rb_node *rb_next_postorder(const struct rb_node *);
..
..
@@ -99,8 +55,6 @@
99
55
 			    struct rb_root *root);
100
56
 extern void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,
101
57
 				struct rb_root *root);
102
-extern void rb_replace_node_cached(struct rb_node *victim, struct rb_node *new,
103
-				   struct rb_root_cached *root);
104
58
 
105
59
 static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
106
60
 				struct rb_node **rb_link)
..
..
@@ -148,4 +102,35 @@
148
102
 			typeof(*pos), field); 1; }); \
149
103
 	     pos = n)
150
104
 
105
+#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
106
+
107
+/* Same as rb_first(), but O(1) */
108
+#define rb_first_cached(root) (root)->rb_leftmost
109
+
110
+static inline void rb_insert_color_cached(struct rb_node *node,
111
+					  struct rb_root_cached *root,
112
+					  bool leftmost)
113
+{
114
+	if (leftmost)
115
+		root->rb_leftmost = node;
116
+	rb_insert_color(node, &root->rb_root);
117
+}
118
+
119
+static inline void rb_erase_cached(struct rb_node *node,
120
+				   struct rb_root_cached *root)
121
+{
122
+	if (root->rb_leftmost == node)
123
+		root->rb_leftmost = rb_next(node);
124
+	rb_erase(node, &root->rb_root);
125
+}
126
+
127
+static inline void rb_replace_node_cached(struct rb_node *victim,
128
+					  struct rb_node *new,
129
+					  struct rb_root_cached *root)
130
+{
131
+	if (root->rb_leftmost == victim)
132
+		root->rb_leftmost = new;
133
+	rb_replace_node(victim, new, &root->rb_root);
134
+}
135
+
151
136
 #endif	/* _LINUX_RBTREE_H */