Blame view
lib/timerqueue.c
3.13 KB
87de5ac78
|
1 |
/* |
1f5a24794
|
2 |
* Generic Timer-queue |
87de5ac78
|
3 |
* |
1f5a24794
|
4 |
* Manages a simple queue of timers, ordered by expiration time. |
87de5ac78
|
5 6 7 |
* Uses rbtrees for quick list adds and expiration. * * NOTE: All of the following functions need to be serialized |
25985edce
|
8 |
* to avoid races. No locking is done by this library code. |
87de5ac78
|
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
|
24 |
#include <linux/bug.h> |
1f5a24794
|
25 |
#include <linux/timerqueue.h> |
87de5ac78
|
26 |
#include <linux/rbtree.h> |
8bc3bcc93
|
27 |
#include <linux/export.h> |
87de5ac78
|
28 29 |
/** |
1f5a24794
|
30 |
* timerqueue_add - Adds timer to timerqueue. |
87de5ac78
|
31 |
* |
1f5a24794
|
32 |
* @head: head of timerqueue |
87de5ac78
|
33 34 |
* @node: timer node to be added * |
1f5a24794
|
35 |
* Adds the timer node to the timerqueue, sorted by the |
87de5ac78
|
36 37 |
* node's expires value. */ |
c320642e1
|
38 |
bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) |
87de5ac78
|
39 40 41 |
{ struct rb_node **p = &head->head.rb_node; struct rb_node *parent = NULL; |
1f5a24794
|
42 |
struct timerqueue_node *ptr; |
87de5ac78
|
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
|
49 |
ptr = rb_entry(parent, struct timerqueue_node, node); |
2456e8553
|
50 |
if (node->expires < ptr->expires) |
87de5ac78
|
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
|
57 |
if (!head->next || node->expires < head->next->expires) { |
87de5ac78
|
58 |
head->next = node; |
c320642e1
|
59 60 61 |
return true; } return false; |
87de5ac78
|
62 |
} |
9bb99b147
|
63 |
EXPORT_SYMBOL_GPL(timerqueue_add); |
87de5ac78
|
64 65 |
/** |
1f5a24794
|
66 |
* timerqueue_del - Removes a timer from the timerqueue. |
87de5ac78
|
67 |
* |
1f5a24794
|
68 |
* @head: head of timerqueue |
87de5ac78
|
69 70 |
* @node: timer node to be removed * |
1f5a24794
|
71 |
* Removes the timer node from the timerqueue. |
87de5ac78
|
72 |
*/ |
c320642e1
|
73 |
bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) |
87de5ac78
|
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
|
80 |
head->next = rb_entry_safe(rbn, struct timerqueue_node, node); |
87de5ac78
|
81 82 83 |
} rb_erase(&node->node, &head->head); RB_CLEAR_NODE(&node->node); |
c320642e1
|
84 |
return head->next != NULL; |
87de5ac78
|
85 |
} |
9bb99b147
|
86 |
EXPORT_SYMBOL_GPL(timerqueue_del); |
87de5ac78
|
87 88 |
/** |
1f5a24794
|
89 |
* timerqueue_iterate_next - Returns the timer after the provided timer |
87de5ac78
|
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
|
97 |
struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node) |
87de5ac78
|
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
|
106 |
return container_of(next, struct timerqueue_node, node); |
87de5ac78
|
107 |
} |
9bb99b147
|
108 |
EXPORT_SYMBOL_GPL(timerqueue_iterate_next); |