Blame view
lib/timerqueue.c
3.13 KB
87de5ac78 timers: Introduce... |
1 |
/* |
1f5a24794 timers: Rename ti... |
2 |
* Generic Timer-queue |
87de5ac78 timers: Introduce... |
3 |
* |
1f5a24794 timers: Rename ti... |
4 |
* Manages a simple queue of timers, ordered by expiration time. |
87de5ac78 timers: Introduce... |
5 6 7 |
* Uses rbtrees for quick list adds and expiration. * * NOTE: All of the following functions need to be serialized |
25985edce Fix common misspe... |
8 |
* to avoid races. No locking is done by this library code. |
87de5ac78 timers: Introduce... |
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
* * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ |
50af5ead3 bug.h: add includ... |
24 |
#include <linux/bug.h> |
1f5a24794 timers: Rename ti... |
25 |
#include <linux/timerqueue.h> |
87de5ac78 timers: Introduce... |
26 |
#include <linux/rbtree.h> |
8bc3bcc93 lib: reduce the u... |
27 |
#include <linux/export.h> |
87de5ac78 timers: Introduce... |
28 29 |
/** |
1f5a24794 timers: Rename ti... |
30 |
* timerqueue_add - Adds timer to timerqueue. |
87de5ac78 timers: Introduce... |
31 |
* |
1f5a24794 timers: Rename ti... |
32 |
* @head: head of timerqueue |
87de5ac78 timers: Introduce... |
33 34 |
* @node: timer node to be added * |
1f5a24794 timers: Rename ti... |
35 |
* Adds the timer node to the timerqueue, sorted by the |
87de5ac78 timers: Introduce... |
36 37 |
* node's expires value. */ |
c320642e1 timerqueue: Let t... |
38 |
bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) |
87de5ac78 timers: Introduce... |
39 40 41 |
{ struct rb_node **p = &head->head.rb_node; struct rb_node *parent = NULL; |
1f5a24794 timers: Rename ti... |
42 |
struct timerqueue_node *ptr; |
87de5ac78 timers: Introduce... |
43 44 45 46 47 48 |
/* Make sure we don't add nodes that are already added */ WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); while (*p) { parent = *p; |
1f5a24794 timers: Rename ti... |
49 |
ptr = rb_entry(parent, struct timerqueue_node, node); |
2456e8553 ktime: Get rid of... |
50 |
if (node->expires < ptr->expires) |
87de5ac78 timers: Introduce... |
51 52 53 54 55 56 |
p = &(*p)->rb_left; else p = &(*p)->rb_right; } rb_link_node(&node->node, parent, p); rb_insert_color(&node->node, &head->head); |
2456e8553 ktime: Get rid of... |
57 |
if (!head->next || node->expires < head->next->expires) { |
87de5ac78 timers: Introduce... |
58 |
head->next = node; |
c320642e1 timerqueue: Let t... |
59 60 61 |
return true; } return false; |
87de5ac78 timers: Introduce... |
62 |
} |
9bb99b147 timers: Fixup all... |
63 |
EXPORT_SYMBOL_GPL(timerqueue_add); |
87de5ac78 timers: Introduce... |
64 65 |
/** |
1f5a24794 timers: Rename ti... |
66 |
* timerqueue_del - Removes a timer from the timerqueue. |
87de5ac78 timers: Introduce... |
67 |
* |
1f5a24794 timers: Rename ti... |
68 |
* @head: head of timerqueue |
87de5ac78 timers: Introduce... |
69 70 |
* @node: timer node to be removed * |
1f5a24794 timers: Rename ti... |
71 |
* Removes the timer node from the timerqueue. |
87de5ac78 timers: Introduce... |
72 |
*/ |
c320642e1 timerqueue: Let t... |
73 |
bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) |
87de5ac78 timers: Introduce... |
74 75 76 77 78 79 |
{ WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); /* update next pointer */ if (head->next == node) { struct rb_node *rbn = rb_next(&node->node); |
d852d3943 timerqueue: Use r... |
80 |
head->next = rb_entry_safe(rbn, struct timerqueue_node, node); |
87de5ac78 timers: Introduce... |
81 82 83 |
} rb_erase(&node->node, &head->head); RB_CLEAR_NODE(&node->node); |
c320642e1 timerqueue: Let t... |
84 |
return head->next != NULL; |
87de5ac78 timers: Introduce... |
85 |
} |
9bb99b147 timers: Fixup all... |
86 |
EXPORT_SYMBOL_GPL(timerqueue_del); |
87de5ac78 timers: Introduce... |
87 88 |
/** |
1f5a24794 timers: Rename ti... |
89 |
* timerqueue_iterate_next - Returns the timer after the provided timer |
87de5ac78 timers: Introduce... |
90 91 92 93 94 95 96 |
* * @node: Pointer to a timer. * * Provides the timer that is after the given node. This is used, when * necessary, to iterate through the list of timers in a timer list * without modifying the list. */ |
1f5a24794 timers: Rename ti... |
97 |
struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node) |
87de5ac78 timers: Introduce... |
98 99 100 101 102 103 104 105 |
{ struct rb_node *next; if (!node) return NULL; next = rb_next(&node->node); if (!next) return NULL; |
1f5a24794 timers: Rename ti... |
106 |
return container_of(next, struct timerqueue_node, node); |
87de5ac78 timers: Introduce... |
107 |
} |
9bb99b147 timers: Fixup all... |
108 |
EXPORT_SYMBOL_GPL(timerqueue_iterate_next); |