Blame view
lib/timerqueue.c
2.61 KB
1a59d1b8e
|
1 |
// SPDX-License-Identifier: GPL-2.0-or-later |
87de5ac78
|
2 |
/* |
1f5a24794
|
3 |
* Generic Timer-queue |
87de5ac78
|
4 |
* |
1f5a24794
|
5 |
* Manages a simple queue of timers, ordered by expiration time. |
87de5ac78
|
6 7 8 |
* Uses rbtrees for quick list adds and expiration. * * NOTE: All of the following functions need to be serialized |
25985edce
|
9 |
* to avoid races. No locking is done by this library code. |
87de5ac78
|
10 |
*/ |
50af5ead3
|
11 |
#include <linux/bug.h> |
1f5a24794
|
12 |
#include <linux/timerqueue.h> |
87de5ac78
|
13 |
#include <linux/rbtree.h> |
8bc3bcc93
|
14 |
#include <linux/export.h> |
87de5ac78
|
15 16 |
/** |
1f5a24794
|
17 |
* timerqueue_add - Adds timer to timerqueue. |
87de5ac78
|
18 |
* |
1f5a24794
|
19 |
* @head: head of timerqueue |
87de5ac78
|
20 21 |
* @node: timer node to be added * |
9f4533cd7
|
22 23 24 |
* Adds the timer node to the timerqueue, sorted by the node's expires * value. Returns true if the newly added timer is the first expiring timer in * the queue. |
87de5ac78
|
25 |
*/ |
c320642e1
|
26 |
bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) |
87de5ac78
|
27 28 29 |
{ struct rb_node **p = &head->head.rb_node; struct rb_node *parent = NULL; |
1f5a24794
|
30 |
struct timerqueue_node *ptr; |
87de5ac78
|
31 32 33 34 35 36 |
/* Make sure we don't add nodes that are already added */ WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); while (*p) { parent = *p; |
1f5a24794
|
37 |
ptr = rb_entry(parent, struct timerqueue_node, node); |
2456e8553
|
38 |
if (node->expires < ptr->expires) |
87de5ac78
|
39 40 41 42 43 44 |
p = &(*p)->rb_left; else p = &(*p)->rb_right; } rb_link_node(&node->node, parent, p); rb_insert_color(&node->node, &head->head); |
2456e8553
|
45 |
if (!head->next || node->expires < head->next->expires) { |
87de5ac78
|
46 |
head->next = node; |
c320642e1
|
47 48 49 |
return true; } return false; |
87de5ac78
|
50 |
} |
9bb99b147
|
51 |
EXPORT_SYMBOL_GPL(timerqueue_add); |
87de5ac78
|
52 53 |
/** |
1f5a24794
|
54 |
* timerqueue_del - Removes a timer from the timerqueue. |
87de5ac78
|
55 |
* |
1f5a24794
|
56 |
* @head: head of timerqueue |
87de5ac78
|
57 58 |
* @node: timer node to be removed * |
9f4533cd7
|
59 60 |
* Removes the timer node from the timerqueue. Returns true if the queue is * not empty after the remove. |
87de5ac78
|
61 |
*/ |
c320642e1
|
62 |
bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) |
87de5ac78
|
63 64 65 66 67 68 |
{ WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); /* update next pointer */ if (head->next == node) { struct rb_node *rbn = rb_next(&node->node); |
d852d3943
|
69 |
head->next = rb_entry_safe(rbn, struct timerqueue_node, node); |
87de5ac78
|
70 71 72 |
} rb_erase(&node->node, &head->head); RB_CLEAR_NODE(&node->node); |
c320642e1
|
73 |
return head->next != NULL; |
87de5ac78
|
74 |
} |
9bb99b147
|
75 |
EXPORT_SYMBOL_GPL(timerqueue_del); |
87de5ac78
|
76 77 |
/** |
1f5a24794
|
78 |
* timerqueue_iterate_next - Returns the timer after the provided timer |
87de5ac78
|
79 80 81 82 83 84 85 |
* * @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
|
86 |
struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node) |
87de5ac78
|
87 88 89 90 91 92 93 94 |
{ struct rb_node *next; if (!node) return NULL; next = rb_next(&node->node); if (!next) return NULL; |
1f5a24794
|
95 |
return container_of(next, struct timerqueue_node, node); |
87de5ac78
|
96 |
} |
9bb99b147
|
97 |
EXPORT_SYMBOL_GPL(timerqueue_iterate_next); |