diff options
Diffstat (limited to 'lib/timerqueue.c')
-rw-r--r-- | lib/timerqueue.c | 118 |
1 files changed, 118 insertions, 0 deletions
diff --git a/lib/timerqueue.c b/lib/timerqueue.c new file mode 100644 index 000000000000..f46de84d9467 --- /dev/null +++ b/lib/timerqueue.c | |||
@@ -0,0 +1,118 @@ | |||
1 | /* | ||
2 | * Generic Timer-queue | ||
3 | * | ||
4 | * Manages a simple queue of timers, ordered by expiration time. | ||
5 | * Uses rbtrees for quick list adds and expiration. | ||
6 | * | ||
7 | * NOTE: All of the following functions need to be serialized | ||
8 | * to avoid races. No locking is done by this libary 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 | */ | ||
24 | |||
25 | #include <linux/timerqueue.h> | ||
26 | #include <linux/rbtree.h> | ||
27 | |||
28 | /** | ||
29 | * timerqueue_add - Adds timer to timerqueue. | ||
30 | * | ||
31 | * @head: head of timerqueue | ||
32 | * @node: timer node to be added | ||
33 | * | ||
34 | * Adds the timer node to the timerqueue, sorted by the | ||
35 | * node's expires value. | ||
36 | */ | ||
37 | void timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) | ||
38 | { | ||
39 | struct rb_node **p = &head->head.rb_node; | ||
40 | struct rb_node *parent = NULL; | ||
41 | struct timerqueue_node *ptr; | ||
42 | |||
43 | /* Make sure we don't add nodes that are already added */ | ||
44 | WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); | ||
45 | |||
46 | while (*p) { | ||
47 | parent = *p; | ||
48 | ptr = rb_entry(parent, struct timerqueue_node, node); | ||
49 | if (node->expires.tv64 < ptr->expires.tv64) | ||
50 | p = &(*p)->rb_left; | ||
51 | else | ||
52 | p = &(*p)->rb_right; | ||
53 | } | ||
54 | rb_link_node(&node->node, parent, p); | ||
55 | rb_insert_color(&node->node, &head->head); | ||
56 | |||
57 | if (!head->next || node->expires.tv64 < head->next->expires.tv64) | ||
58 | head->next = node; | ||
59 | } | ||
60 | |||
61 | /** | ||
62 | * timerqueue_del - Removes a timer from the timerqueue. | ||
63 | * | ||
64 | * @head: head of timerqueue | ||
65 | * @node: timer node to be removed | ||
66 | * | ||
67 | * Removes the timer node from the timerqueue. | ||
68 | */ | ||
69 | void timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) | ||
70 | { | ||
71 | WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); | ||
72 | |||
73 | /* update next pointer */ | ||
74 | if (head->next == node) { | ||
75 | struct rb_node *rbn = rb_next(&node->node); | ||
76 | |||
77 | head->next = rbn ? | ||
78 | rb_entry(rbn, struct timerqueue_node, node) : NULL; | ||
79 | } | ||
80 | rb_erase(&node->node, &head->head); | ||
81 | RB_CLEAR_NODE(&node->node); | ||
82 | } | ||
83 | |||
84 | |||
85 | /** | ||
86 | * timerqueue_getnext - Returns the timer with the earlies expiration time | ||
87 | * | ||
88 | * @head: head of timerqueue | ||
89 | * | ||
90 | * Returns a pointer to the timer node that has the | ||
91 | * earliest expiration time. | ||
92 | */ | ||
93 | struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head) | ||
94 | { | ||
95 | return head->next; | ||
96 | } | ||
97 | |||
98 | |||
99 | /** | ||
100 | * timerqueue_iterate_next - Returns the timer after the provided timer | ||
101 | * | ||
102 | * @node: Pointer to a timer. | ||
103 | * | ||
104 | * Provides the timer that is after the given node. This is used, when | ||
105 | * necessary, to iterate through the list of timers in a timer list | ||
106 | * without modifying the list. | ||
107 | */ | ||
108 | struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node) | ||
109 | { | ||
110 | struct rb_node *next; | ||
111 | |||
112 | if (!node) | ||
113 | return NULL; | ||
114 | next = rb_next(&node->node); | ||
115 | if (!next) | ||
116 | return NULL; | ||
117 | return container_of(next, struct timerqueue_node, node); | ||
118 | } | ||