1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#include <linux/bug.h>
26#include <linux/timerqueue.h>
27#include <linux/rbtree.h>
28#include <linux/export.h>
29
30
31
32
33
34
35
36
37
38
39bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
40{
41 struct rb_node **p = &head->head.rb_node;
42 struct rb_node *parent = NULL;
43 struct timerqueue_node *ptr;
44
45
46 WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node));
47
48 while (*p) {
49 parent = *p;
50 ptr = rb_entry(parent, struct timerqueue_node, node);
51 if (node->expires.tv64 < ptr->expires.tv64)
52 p = &(*p)->rb_left;
53 else
54 p = &(*p)->rb_right;
55 }
56 rb_link_node(&node->node, parent, p);
57 rb_insert_color(&node->node, &head->head);
58
59 if (!head->next || node->expires.tv64 < head->next->expires.tv64) {
60 head->next = node;
61 return true;
62 }
63 return false;
64}
65EXPORT_SYMBOL_GPL(timerqueue_add);
66
67
68
69
70
71
72
73
74
75bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node)
76{
77 WARN_ON_ONCE(RB_EMPTY_NODE(&node->node));
78
79
80 if (head->next == node) {
81 struct rb_node *rbn = rb_next(&node->node);
82
83 head->next = rbn ?
84 rb_entry(rbn, struct timerqueue_node, node) : NULL;
85 }
86 rb_erase(&node->node, &head->head);
87 RB_CLEAR_NODE(&node->node);
88 return head->next != NULL;
89}
90EXPORT_SYMBOL_GPL(timerqueue_del);
91
92
93
94
95
96
97
98
99
100
101struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node)
102{
103 struct rb_node *next;
104
105 if (!node)
106 return NULL;
107 next = rb_next(&node->node);
108 if (!next)
109 return NULL;
110 return container_of(next, struct timerqueue_node, node);
111}
112EXPORT_SYMBOL_GPL(timerqueue_iterate_next);
113