modify sin led gpio

hc

2024-05-13 9d77db3c730780c8ef5ccd4b66403ff5675cfe4e

 kernel/tools/include/linux/rbtree_augmented.h
..
..
@@ -1,22 +1,10 @@
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
   (C) 2002  David Woodhouse <dwmw2@infradead.org>
5
6
   (C) 2012  Michel Lespinasse <walken@google.com>
6
7
 
7
-  This program is free software; you can redistribute it and/or modify
8
-  it under the terms of the GNU General Public License as published by
9
-  the Free Software Foundation; either version 2 of the License, or
10
-  (at your option) any later version.
11
-
12
-  This program is distributed in the hope that it will be useful,
13
-  but WITHOUT ANY WARRANTY; without even the implied warranty of
14
-  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
-  GNU General Public License for more details.
16
-
17
-  You should have received a copy of the GNU General Public License
18
-  along with this program; if not, write to the Free Software
19
-  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
20
8
 
21
9
   tools/linux/include/linux/rbtree_augmented.h
22
10
 
..
..
@@ -35,7 +23,7 @@
35
23
  * rb_insert_augmented() and rb_erase_augmented() are intended to be public.
36
24
  * The rest are implementation details you are not expected to depend on.
37
25
  *
38
- * See Documentation/rbtree.txt for documentation and samples.
26
+ * See Documentation/core-api/rbtree.rst for documentation and samples.
39
27
  */
40
28
 
41
29
 struct rb_augment_callbacks {
..
..
@@ -46,13 +34,14 @@
46
34
 
47
35
 extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
48
36
 	void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
37
+
49
38
 /*
50
39
  * Fixup the rbtree and update the augmented information when rebalancing.
51
40
  *
52
41
  * On insertion, the user must update the augmented information on the path
53
42
  * leading to the inserted node, then call rb_link_node() as usual and
54
- * rb_augment_inserted() instead of the usual rb_insert_color() call.
55
- * If rb_augment_inserted() rebalances the rbtree, it will callback into
43
+ * rb_insert_augmented() instead of the usual rb_insert_color() call.
44
+ * If rb_insert_augmented() rebalances the rbtree, it will callback into
56
45
  * a user provided function to update the augmented information on the
57
46
  * affected subtrees.
58
47
  */
..
..
@@ -63,38 +52,96 @@
63
52
 	__rb_insert_augmented(node, root, augment->rotate);
64
53
 }
65
54
 
66
-#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield,	\
67
-			     rbtype, rbaugmented, rbcompute)		\
55
+static inline void
56
+rb_insert_augmented_cached(struct rb_node *node,
57
+			   struct rb_root_cached *root, bool newleft,
58
+			   const struct rb_augment_callbacks *augment)
59
+{
60
+	if (newleft)
61
+		root->rb_leftmost = node;
62
+	rb_insert_augmented(node, &root->rb_root, augment);
63
+}
64
+
65
+/*
66
+ * Template for declaring augmented rbtree callbacks (generic case)
67
+ *
68
+ * RBSTATIC:    'static' or empty
69
+ * RBNAME:      name of the rb_augment_callbacks structure
70
+ * RBSTRUCT:    struct type of the tree nodes
71
+ * RBFIELD:     name of struct rb_node field within RBSTRUCT
72
+ * RBAUGMENTED: name of field within RBSTRUCT holding data for subtree
73
+ * RBCOMPUTE:   name of function that recomputes the RBAUGMENTED data
74
+ */
75
+
76
+#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME,				\
77
+			     RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE)	\
68
78
 static inline void							\
69
-rbname ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
79
+RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
70
80
 {									\
71
81
 	while (rb != stop) {						\
72
-		rbstruct *node = rb_entry(rb, rbstruct, rbfield);	\
73
-		rbtype augmented = rbcompute(node);			\
74
-		if (node->rbaugmented == augmented)			\
82
+		RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD);	\
83
+		if (RBCOMPUTE(node, true))				\
75
84
 			break;						\
76
-		node->rbaugmented = augmented;				\
77
-		rb = rb_parent(&node->rbfield);				\
85
+		rb = rb_parent(&node->RBFIELD);				\
78
86
 	}								\
79
87
 }									\
80
88
 static inline void							\
81
-rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
89
+RBNAME ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
82
90
 {									\
83
-	rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\
84
-	rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\
85
-	new->rbaugmented = old->rbaugmented;				\
91
+	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
92
+	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
93
+	new->RBAUGMENTED = old->RBAUGMENTED;				\
86
94
 }									\
87
95
 static void								\
88
-rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
96
+RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
89
97
 {									\
90
-	rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\
91
-	rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\
92
-	new->rbaugmented = old->rbaugmented;				\
93
-	old->rbaugmented = rbcompute(old);				\
98
+	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
99
+	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
100
+	new->RBAUGMENTED = old->RBAUGMENTED;				\
101
+	RBCOMPUTE(old, false);						\
94
102
 }									\
95
-rbstatic const struct rb_augment_callbacks rbname = {			\
96
-	rbname ## _propagate, rbname ## _copy, rbname ## _rotate	\
103
+RBSTATIC const struct rb_augment_callbacks RBNAME = {			\
104
+	.propagate = RBNAME ## _propagate,				\
105
+	.copy = RBNAME ## _copy,					\
106
+	.rotate = RBNAME ## _rotate					\
97
107
 };
108
+
109
+/*
110
+ * Template for declaring augmented rbtree callbacks,
111
+ * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
112
+ *
113
+ * RBSTATIC:    'static' or empty
114
+ * RBNAME:      name of the rb_augment_callbacks structure
115
+ * RBSTRUCT:    struct type of the tree nodes
116
+ * RBFIELD:     name of struct rb_node field within RBSTRUCT
117
+ * RBTYPE:      type of the RBAUGMENTED field
118
+ * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree
119
+ * RBCOMPUTE:   name of function that returns the per-node RBTYPE scalar
120
+ */
121
+
122
+#define RB_DECLARE_CALLBACKS_MAX(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD,	      \
123
+				 RBTYPE, RBAUGMENTED, RBCOMPUTE)	      \
124
+static inline bool RBNAME ## _compute_max(RBSTRUCT *node, bool exit)	      \
125
+{									      \
126
+	RBSTRUCT *child;						      \
127
+	RBTYPE max = RBCOMPUTE(node);					      \
128
+	if (node->RBFIELD.rb_left) {					      \
129
+		child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD);   \
130
+		if (child->RBAUGMENTED > max)				      \
131
+			max = child->RBAUGMENTED;			      \
132
+	}								      \
133
+	if (node->RBFIELD.rb_right) {					      \
134
+		child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD);  \
135
+		if (child->RBAUGMENTED > max)				      \
136
+			max = child->RBAUGMENTED;			      \
137
+	}								      \
138
+	if (exit && node->RBAUGMENTED == max)				      \
139
+		return true;						      \
140
+	node->RBAUGMENTED = max;					      \
141
+	return false;							      \
142
+}									      \
143
+RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME,					      \
144
+		     RBSTRUCT, RBFIELD, RBAUGMENTED, RBNAME ## _compute_max)
98
145
 
99
146
 
100
147
 #define	RB_RED		0
..
..
@@ -126,11 +173,11 @@
126
173
 {
127
174
 	if (parent) {
128
175
 		if (parent->rb_left == old)
129
-			parent->rb_left = new;
176
+			WRITE_ONCE(parent->rb_left, new);
130
177
 		else
131
-			parent->rb_right = new;
178
+			WRITE_ONCE(parent->rb_right, new);
132
179
 	} else
133
-		root->rb_node = new;
180
+		WRITE_ONCE(root->rb_node, new);
134
181
 }
135
182
 
136
183
 extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
..
..
@@ -140,7 +187,8 @@
140
187
 __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
141
188
 		     const struct rb_augment_callbacks *augment)
142
189
 {
143
-	struct rb_node *child = node->rb_right, *tmp = node->rb_left;
190
+	struct rb_node *child = node->rb_right;
191
+	struct rb_node *tmp = node->rb_left;
144
192
 	struct rb_node *parent, *rebalance;
145
193
 	unsigned long pc;
146
194
 
..
..
@@ -170,6 +218,7 @@
170
218
 		tmp = parent;
171
219
 	} else {
172
220
 		struct rb_node *successor = child, *child2;
221
+
173
222
 		tmp = child->rb_left;
174
223
 		if (!tmp) {
175
224
 			/*
..
..
@@ -183,6 +232,7 @@
183
232
 			 */
184
233
 			parent = successor;
185
234
 			child2 = successor->rb_right;
235
+
186
236
 			augment->copy(node, successor);
187
237
 		} else {
188
238
 			/*
..
..
@@ -204,19 +254,23 @@
204
254
 				successor = tmp;
205
255
 				tmp = tmp->rb_left;
206
256
 			} while (tmp);
207
-			parent->rb_left = child2 = successor->rb_right;
208
-			successor->rb_right = child;
257
+			child2 = successor->rb_right;
258
+			WRITE_ONCE(parent->rb_left, child2);
259
+			WRITE_ONCE(successor->rb_right, child);
209
260
 			rb_set_parent(child, successor);
261
+
210
262
 			augment->copy(node, successor);
211
263
 			augment->propagate(parent, successor);
212
264
 		}
213
265
 
214
-		successor->rb_left = tmp = node->rb_left;
266
+		tmp = node->rb_left;
267
+		WRITE_ONCE(successor->rb_left, tmp);
215
268
 		rb_set_parent(tmp, successor);
216
269
 
217
270
 		pc = node->__rb_parent_color;
218
271
 		tmp = __rb_parent(pc);
219
272
 		__rb_change_child(node, successor, tmp, root);
273
+
220
274
 		if (child2) {
221
275
 			successor->__rb_parent_color = pc;
222
276
 			rb_set_parent_color(child2, parent, RB_BLACK);
..
..
@@ -242,4 +296,13 @@
242
296
 		__rb_erase_color(rebalance, root, augment->rotate);
243
297
 }
244
298
 
245
-#endif	/* _TOOLS_LINUX_RBTREE_AUGMENTED_H */
299
+static __always_inline void
300
+rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root,
301
+			  const struct rb_augment_callbacks *augment)
302
+{
303
+	if (root->rb_leftmost == node)
304
+		root->rb_leftmost = rb_next(node);
305
+	rb_erase_augmented(node, &root->rb_root, augment);
306
+}
307
+
308
+#endif /* _TOOLS_LINUX_RBTREE_AUGMENTED_H */