]>
Commit | Line | Data |
---|---|---|
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 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 | */ | |
24 | ||
25 | #include <linux/bug.h> | |
26 | #include <linux/timerqueue.h> | |
27 | #include <linux/rbtree.h> | |
28 | #include <linux/export.h> | |
29 | ||
30 | /** | |
31 | * timerqueue_add - Adds timer to timerqueue. | |
32 | * | |
33 | * @head: head of timerqueue | |
34 | * @node: timer node to be added | |
35 | * | |
36 | * Adds the timer node to the timerqueue, sorted by the | |
37 | * node's expires value. | |
38 | */ | |
39 | bool 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 | /* Make sure we don't add nodes that are already added */ | |
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 < ptr->expires) | |
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 < head->next->expires) { | |
60 | head->next = node; | |
61 | return true; | |
62 | } | |
63 | return false; | |
64 | } | |
65 | EXPORT_SYMBOL_GPL(timerqueue_add); | |
66 | ||
67 | /** | |
68 | * timerqueue_del - Removes a timer from the timerqueue. | |
69 | * | |
70 | * @head: head of timerqueue | |
71 | * @node: timer node to be removed | |
72 | * | |
73 | * Removes the timer node from the timerqueue. | |
74 | */ | |
75 | bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) | |
76 | { | |
77 | WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); | |
78 | ||
79 | /* update next pointer */ | |
80 | if (head->next == node) { | |
81 | struct rb_node *rbn = rb_next(&node->node); | |
82 | ||
83 | head->next = rb_entry_safe(rbn, struct timerqueue_node, node); | |
84 | } | |
85 | rb_erase(&node->node, &head->head); | |
86 | RB_CLEAR_NODE(&node->node); | |
87 | return head->next != NULL; | |
88 | } | |
89 | EXPORT_SYMBOL_GPL(timerqueue_del); | |
90 | ||
91 | /** | |
92 | * timerqueue_iterate_next - Returns the timer after the provided timer | |
93 | * | |
94 | * @node: Pointer to a timer. | |
95 | * | |
96 | * Provides the timer that is after the given node. This is used, when | |
97 | * necessary, to iterate through the list of timers in a timer list | |
98 | * without modifying the list. | |
99 | */ | |
100 | struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node) | |
101 | { | |
102 | struct rb_node *next; | |
103 | ||
104 | if (!node) | |
105 | return NULL; | |
106 | next = rb_next(&node->node); | |
107 | if (!next) | |
108 | return NULL; | |
109 | return container_of(next, struct timerqueue_node, node); | |
110 | } | |
111 | EXPORT_SYMBOL_GPL(timerqueue_iterate_next); |