forked from ~ljy/RK356X_SDK_RELEASE

blame | history | patch | commit | commitdiff
hc
2024-05-10 37f49e37ab4cb5d0bc4c60eb5c6d4dd57db767bb 
 kernel/include/linux/rbtree_augmented.h
....@@ -1,22 +1,10 @@
1
+/* SPDX-License-Identifier: GPL-2.0-or-later */
12 /*
23   Red Black Trees
34   (C) 1999  Andrea Arcangeli <andrea@suse.de>
45   (C) 2002  David Woodhouse <dwmw2@infradead.org>
56   (C) 2012  Michel Lespinasse <walken@google.com>
67 
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
208 
219   linux/include/linux/rbtree_augmented.h
2210 */
....@@ -33,7 +21,7 @@
3321  * rb_insert_augmented() and rb_erase_augmented() are intended to be public.
3422  * The rest are implementation details you are not expected to depend on.
3523  *
36
- * See Documentation/rbtree.txt for documentation and samples.
24
+ * See Documentation/core-api/rbtree.rst for documentation and samples.
3725  */
3826 
3927 struct rb_augment_callbacks {
....@@ -42,17 +30,16 @@
4230 	void (*rotate)(struct rb_node *old, struct rb_node *new);
4331 };
4432 
45
-extern void __rb_insert_augmented(struct rb_node *node,
46
-				  struct rb_root *root,
47
-				  bool newleft, struct rb_node **leftmost,
33
+extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
4834 	void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
35
+
4936 /*
5037  * Fixup the rbtree and update the augmented information when rebalancing.
5138  *
5239  * On insertion, the user must update the augmented information on the path
5340  * 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
41
+ * rb_insert_augmented() instead of the usual rb_insert_color() call.
42
+ * If rb_insert_augmented() rebalances the rbtree, it will callback into
5643  * a user provided function to update the augmented information on the
5744  * affected subtrees.
5845  */
....@@ -60,7 +47,7 @@
6047 rb_insert_augmented(struct rb_node *node, struct rb_root *root,
6148 		    const struct rb_augment_callbacks *augment)
6249 {
63
-	__rb_insert_augmented(node, root, false, NULL, augment->rotate);
50
+	__rb_insert_augmented(node, root, augment->rotate);
6451 }
6552 
6653 static inline void
....@@ -68,44 +55,91 @@
6855 			   struct rb_root_cached *root, bool newleft,
6956 			   const struct rb_augment_callbacks *augment)
7057 {
71
-	__rb_insert_augmented(node, &root->rb_root,
72
-			      newleft, &root->rb_leftmost, augment->rotate);
58
+	if (newleft)
59
+		root->rb_leftmost = node;
60
+	rb_insert_augmented(node, &root->rb_root, augment);
7361 }
7462 
75
-#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield,	\
76
-			     rbtype, rbaugmented, rbcompute)		\
63
+/*
64
+ * Template for declaring augmented rbtree callbacks (generic case)
65
+ *
66
+ * RBSTATIC:    'static' or empty
67
+ * RBNAME:      name of the rb_augment_callbacks structure
68
+ * RBSTRUCT:    struct type of the tree nodes
69
+ * RBFIELD:     name of struct rb_node field within RBSTRUCT
70
+ * RBAUGMENTED: name of field within RBSTRUCT holding data for subtree
71
+ * RBCOMPUTE:   name of function that recomputes the RBAUGMENTED data
72
+ */
73
+
74
+#define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME,				\
75
+			     RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE)	\
7776 static inline void							\
78
-rbname ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
77
+RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
7978 {									\
8079 	while (rb != stop) {						\
81
-		rbstruct *node = rb_entry(rb, rbstruct, rbfield);	\
82
-		rbtype augmented = rbcompute(node);			\
83
-		if (node->rbaugmented == augmented)			\
80
+		RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD);	\
81
+		if (RBCOMPUTE(node, true))				\
8482 			break;						\
85
-		node->rbaugmented = augmented;				\
86
-		rb = rb_parent(&node->rbfield);				\
83
+		rb = rb_parent(&node->RBFIELD);				\
8784 	}								\
8885 }									\
8986 static inline void							\
90
-rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
87
+RBNAME ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
9188 {									\
92
-	rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\
93
-	rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\
94
-	new->rbaugmented = old->rbaugmented;				\
89
+	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
90
+	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
91
+	new->RBAUGMENTED = old->RBAUGMENTED;				\
9592 }									\
9693 static void								\
97
-rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
94
+RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
9895 {									\
99
-	rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\
100
-	rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\
101
-	new->rbaugmented = old->rbaugmented;				\
102
-	old->rbaugmented = rbcompute(old);				\
96
+	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
97
+	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
98
+	new->RBAUGMENTED = old->RBAUGMENTED;				\
99
+	RBCOMPUTE(old, false);						\
103100 }									\
104
-rbstatic const struct rb_augment_callbacks rbname = {			\
105
-	.propagate = rbname ## _propagate,				\
106
-	.copy = rbname ## _copy,					\
107
-	.rotate = rbname ## _rotate					\
101
+RBSTATIC const struct rb_augment_callbacks RBNAME = {			\
102
+	.propagate = RBNAME ## _propagate,				\
103
+	.copy = RBNAME ## _copy,					\
104
+	.rotate = RBNAME ## _rotate					\
108105 };
106
+
107
+/*
108
+ * Template for declaring augmented rbtree callbacks,
109
+ * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
110
+ *
111
+ * RBSTATIC:    'static' or empty
112
+ * RBNAME:      name of the rb_augment_callbacks structure
113
+ * RBSTRUCT:    struct type of the tree nodes
114
+ * RBFIELD:     name of struct rb_node field within RBSTRUCT
115
+ * RBTYPE:      type of the RBAUGMENTED field
116
+ * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree
117
+ * RBCOMPUTE:   name of function that returns the per-node RBTYPE scalar
118
+ */
119
+
120
+#define RB_DECLARE_CALLBACKS_MAX(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD,	      \
121
+				 RBTYPE, RBAUGMENTED, RBCOMPUTE)	      \
122
+static inline bool RBNAME ## _compute_max(RBSTRUCT *node, bool exit)	      \
123
+{									      \
124
+	RBSTRUCT *child;						      \
125
+	RBTYPE max = RBCOMPUTE(node);					      \
126
+	if (node->RBFIELD.rb_left) {					      \
127
+		child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD);   \
128
+		if (child->RBAUGMENTED > max)				      \
129
+			max = child->RBAUGMENTED;			      \
130
+	}								      \
131
+	if (node->RBFIELD.rb_right) {					      \
132
+		child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD);  \
133
+		if (child->RBAUGMENTED > max)				      \
134
+			max = child->RBAUGMENTED;			      \
135
+	}								      \
136
+	if (exit && node->RBAUGMENTED == max)				      \
137
+		return true;						      \
138
+	node->RBAUGMENTED = max;					      \
139
+	return false;							      \
140
+}									      \
141
+RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME,					      \
142
+		     RBSTRUCT, RBFIELD, RBAUGMENTED, RBNAME ## _compute_max)
109143 
110144 
111145 #define	RB_RED		0
....@@ -162,16 +196,12 @@
162196 
163197 static __always_inline struct rb_node *
164198 __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
165
-		     struct rb_node **leftmost,
166199 		     const struct rb_augment_callbacks *augment)
167200 {
168201 	struct rb_node *child = node->rb_right;
169202 	struct rb_node *tmp = node->rb_left;
170203 	struct rb_node *parent, *rebalance;
171204 	unsigned long pc;
172
-
173
-	if (leftmost && node == *leftmost)
174
-		*leftmost = rb_next(node);
175205 
176206 	if (!tmp) {
177207 		/*
....@@ -253,14 +283,12 @@
253283 		__rb_change_child(node, successor, tmp, root);
254284 
255285 		if (child2) {
256
-			successor->__rb_parent_color = pc;
257286 			rb_set_parent_color(child2, parent, RB_BLACK);
258287 			rebalance = NULL;
259288 		} else {
260
-			unsigned long pc2 = successor->__rb_parent_color;
261
-			successor->__rb_parent_color = pc;
262
-			rebalance = __rb_is_black(pc2) ? parent : NULL;
289
+			rebalance = rb_is_black(successor) ? parent : NULL;
263290 		}
291
+		successor->__rb_parent_color = pc;
264292 		tmp = successor;
265293 	}
266294 
....@@ -272,8 +300,7 @@
272300 rb_erase_augmented(struct rb_node *node, struct rb_root *root,
273301 		   const struct rb_augment_callbacks *augment)
274302 {
275
-	struct rb_node *rebalance = __rb_erase_augmented(node, root,
276
-							 NULL, augment);
303
+	struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);
277304 	if (rebalance)
278305 		__rb_erase_color(rebalance, root, augment->rotate);
279306 }
....@@ -282,11 +309,9 @@
282309 rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root,
283310 			  const struct rb_augment_callbacks *augment)
284311 {
285
-	struct rb_node *rebalance = __rb_erase_augmented(node, &root->rb_root,
286
-							 &root->rb_leftmost,
287
-							 augment);
288
-	if (rebalance)
289
-		__rb_erase_color(rebalance, &root->rb_root, augment->rotate);
312
+	if (root->rb_leftmost == node)
313
+		root->rb_leftmost = rb_next(node);
314
+	rb_erase_augmented(node, &root->rb_root, augment);
290315 }
291316 
292317 #endif	/* _LINUX_RBTREE_AUGMENTED_H */