移去rt

hc

2023-12-08 01573e231f18eb2d99162747186f59511f56b64d

 kernel/tools/perf/util/rblist.c
..
..
@@ -1,8 +1,7 @@
1
+// SPDX-License-Identifier: GPL-2.0-only
1
2
 /*
2
3
  * Based on strlist.c by:
3
4
  * (c) 2009 Arnaldo Carvalho de Melo <acme@redhat.com>
4
- *
5
- * Licensed under the GPLv2.
6
5
  */
7
6
 
8
7
 #include <errno.h>
..
..
@@ -13,8 +12,9 @@
13
12
 
14
13
 int rblist__add_node(struct rblist *rblist, const void *new_entry)
15
14
 {
16
-	struct rb_node **p = &rblist->entries.rb_node;
15
+	struct rb_node **p = &rblist->entries.rb_root.rb_node;
17
16
 	struct rb_node *parent = NULL, *new_node;
17
+	bool leftmost = true;
18
18
 
19
19
 	while (*p != NULL) {
20
20
 		int rc;
..
..
@@ -24,8 +24,10 @@
24
24
 		rc = rblist->node_cmp(parent, new_entry);
25
25
 		if (rc > 0)
26
26
 			p = &(*p)->rb_left;
27
-		else if (rc < 0)
27
+		else if (rc < 0) {
28
28
 			p = &(*p)->rb_right;
29
+			leftmost = false;
30
+		}
29
31
 		else
30
32
 			return -EEXIST;
31
33
 	}
..
..
@@ -35,7 +37,7 @@
35
37
 		return -ENOMEM;
36
38
 
37
39
 	rb_link_node(new_node, parent, p);
38
-	rb_insert_color(new_node, &rblist->entries);
40
+	rb_insert_color_cached(new_node, &rblist->entries, leftmost);
39
41
 	++rblist->nr_entries;
40
42
 
41
43
 	return 0;
..
..
@@ -43,7 +45,7 @@
43
45
 
44
46
 void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node)
45
47
 {
46
-	rb_erase(rb_node, &rblist->entries);
48
+	rb_erase_cached(rb_node, &rblist->entries);
47
49
 	--rblist->nr_entries;
48
50
 	rblist->node_delete(rblist, rb_node);
49
51
 }
..
..
@@ -52,8 +54,9 @@
52
54
 					 const void *entry,
53
55
 					 bool create)
54
56
 {
55
-	struct rb_node **p = &rblist->entries.rb_node;
57
+	struct rb_node **p = &rblist->entries.rb_root.rb_node;
56
58
 	struct rb_node *parent = NULL, *new_node = NULL;
59
+	bool leftmost = true;
57
60
 
58
61
 	while (*p != NULL) {
59
62
 		int rc;
..
..
@@ -63,8 +66,10 @@
63
66
 		rc = rblist->node_cmp(parent, entry);
64
67
 		if (rc > 0)
65
68
 			p = &(*p)->rb_left;
66
-		else if (rc < 0)
69
+		else if (rc < 0) {
67
70
 			p = &(*p)->rb_right;
71
+			leftmost = false;
72
+		}
68
73
 		else
69
74
 			return parent;
70
75
 	}
..
..
@@ -73,7 +78,8 @@
73
78
 		new_node = rblist->node_new(rblist, entry);
74
79
 		if (new_node) {
75
80
 			rb_link_node(new_node, parent, p);
76
-			rb_insert_color(new_node, &rblist->entries);
81
+			rb_insert_color_cached(new_node,
82
+					       &rblist->entries, leftmost);
77
83
 			++rblist->nr_entries;
78
84
 		}
79
85
 	}
..
..
@@ -94,7 +100,7 @@
94
100
 void rblist__init(struct rblist *rblist)
95
101
 {
96
102
 	if (rblist != NULL) {
97
-		rblist->entries	 = RB_ROOT;
103
+		rblist->entries	 = RB_ROOT_CACHED;
98
104
 		rblist->nr_entries = 0;
99
105
 	}
100
106
 
..
..
@@ -103,7 +109,7 @@
103
109
 
104
110
 void rblist__exit(struct rblist *rblist)
105
111
 {
106
-	struct rb_node *pos, *next = rb_first(&rblist->entries);
112
+	struct rb_node *pos, *next = rb_first_cached(&rblist->entries);
107
113
 
108
114
 	while (next) {
109
115
 		pos = next;
..
..
@@ -124,7 +130,8 @@
124
130
 {
125
131
 	struct rb_node *node;
126
132
 
127
-	for (node = rb_first(&rblist->entries); node; node = rb_next(node)) {
133
+	for (node = rb_first_cached(&rblist->entries); node;
134
+	     node = rb_next(node)) {
128
135
 		if (!idx--)
129
136
 			return node;
130
137
 	}