mk-rootfs.sh

hc

2023-12-11 072de836f53be56a70cecf70b43ae43b7ce17376

 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
..
..
@@ -44,25 +32,9 @@
44
32
 	struct rb_node *rb_node;
45
33
 };
46
34
 
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
-};
61
-
62
35
 #define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
63
36
 
64
37
 #define RB_ROOT	(struct rb_root) { NULL, }
65
-#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
66
38
 #define	rb_entry(ptr, type, member) container_of(ptr, type, member)
67
39
 
68
40
 #define RB_EMPTY_ROOT(root)  (READ_ONCE((root)->rb_node) == NULL)
..
..
@@ -84,12 +56,6 @@
84
56
 extern struct rb_node *rb_first(const struct rb_root *);
85
57
 extern struct rb_node *rb_last(const struct rb_root *);
86
58
 
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
59
 /* Postorder iteration - always visit the parent after its children */
94
60
 extern struct rb_node *rb_first_postorder(const struct rb_root *);
95
61
 extern struct rb_node *rb_next_postorder(const struct rb_node *);
..
..
@@ -99,8 +65,6 @@
99
65
 			    struct rb_root *root);
100
66
 extern void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,
101
67
 				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
68
 
105
69
 static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
106
70
 				struct rb_node **rb_link)
..
..
@@ -148,4 +112,50 @@
148
112
 			typeof(*pos), field); 1; }); \
149
113
 	     pos = n)
150
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
+
130
+#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
131
+
132
+/* Same as rb_first(), but O(1) */
133
+#define rb_first_cached(root) (root)->rb_leftmost
134
+
135
+static inline void rb_insert_color_cached(struct rb_node *node,
136
+					  struct rb_root_cached *root,
137
+					  bool leftmost)
138
+{
139
+	if (leftmost)
140
+		root->rb_leftmost = node;
141
+	rb_insert_color(node, &root->rb_root);
142
+}
143
+
144
+static inline void rb_erase_cached(struct rb_node *node,
145
+				   struct rb_root_cached *root)
146
+{
147
+	if (root->rb_leftmost == node)
148
+		root->rb_leftmost = rb_next(node);
149
+	rb_erase(node, &root->rb_root);
150
+}
151
+
152
+static inline void rb_replace_node_cached(struct rb_node *victim,
153
+					  struct rb_node *new,
154
+					  struct rb_root_cached *root)
155
+{
156
+	if (root->rb_leftmost == victim)
157
+		root->rb_leftmost = new;
158
+	rb_replace_node(victim, new, &root->rb_root);
159
+}
160
+
151
161
 #endif	/* _LINUX_RBTREE_H */