write in 30M

hc

2024-02-20 ea08eeccae9297f7aabd2ef7f0c2517ac4549acc

 kernel/lib/timerqueue.c
..
..
@@ -1,3 +1,4 @@
1
+// SPDX-License-Identifier: GPL-2.0-or-later
1
2
 /*
2
3
  *  Generic Timer-queue
3
4
  *
..
..
@@ -6,20 +7,6 @@
6
7
  *
7
8
  *  NOTE: All of the following functions need to be serialized
8
9
  *  to avoid races. No locking is done by this library code.
9
- *
10
- *  This program is free software; you can redistribute it and/or modify
11
- *  it under the terms of the GNU General Public License as published by
12
- *  the Free Software Foundation; either version 2 of the License, or
13
- *  (at your option) any later version.
14
- *
15
- *  This program is distributed in the hope that it will be useful,
16
- *  but WITHOUT ANY WARRANTY; without even the implied warranty of
17
- *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18
- *  GNU General Public License for more details.
19
- *
20
- *  You should have received a copy of the GNU General Public License
21
- *  along with this program; if not, write to the Free Software
22
- *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
23
10
  */
24
11
 
25
12
 #include <linux/bug.h>
..
..
@@ -39,9 +26,10 @@
39
26
  */
40
27
 bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
41
28
 {
42
-	struct rb_node **p = &head->head.rb_node;
29
+	struct rb_node **p = &head->rb_root.rb_root.rb_node;
43
30
 	struct rb_node *parent = NULL;
44
-	struct timerqueue_node  *ptr;
31
+	struct timerqueue_node *ptr;
32
+	bool leftmost = true;
45
33
 
46
34
 	/* Make sure we don't add nodes that are already added */
47
35
 	WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node));
..
..
@@ -49,19 +37,17 @@
49
37
 	while (*p) {
50
38
 		parent = *p;
51
39
 		ptr = rb_entry(parent, struct timerqueue_node, node);
52
-		if (node->expires < ptr->expires)
40
+		if (node->expires < ptr->expires) {
53
41
 			p = &(*p)->rb_left;
54
-		else
42
+		} else {
55
43
 			p = &(*p)->rb_right;
44
+			leftmost = false;
45
+		}
56
46
 	}
57
47
 	rb_link_node(&node->node, parent, p);
58
-	rb_insert_color(&node->node, &head->head);
48
+	rb_insert_color_cached(&node->node, &head->rb_root, leftmost);
59
49
 
60
-	if (!head->next || node->expires < head->next->expires) {
61
-		head->next = node;
62
-		return true;
63
-	}
64
-	return false;
50
+	return leftmost;
65
51
 }
66
52
 EXPORT_SYMBOL_GPL(timerqueue_add);
67
53
 
..
..
@@ -78,15 +64,10 @@
78
64
 {
79
65
 	WARN_ON_ONCE(RB_EMPTY_NODE(&node->node));
80
66
 
81
-	/* update next pointer */
82
-	if (head->next == node) {
83
-		struct rb_node *rbn = rb_next(&node->node);
84
-
85
-		head->next = rb_entry_safe(rbn, struct timerqueue_node, node);
86
-	}
87
-	rb_erase(&node->node, &head->head);
67
+	rb_erase_cached(&node->node, &head->rb_root);
88
68
 	RB_CLEAR_NODE(&node->node);
89
-	return head->next != NULL;
69
+
70
+	return !RB_EMPTY_ROOT(&head->rb_root.rb_root);
90
71
 }
91
72
 EXPORT_SYMBOL_GPL(timerqueue_del);
92
73