aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--include/linux/timerlist.h37
-rw-r--r--include/linux/timerqueue.h37
-rw-r--r--lib/Makefile2
-rw-r--r--lib/timerqueue.c (renamed from lib/timerlist.c)40
4 files changed, 58 insertions, 58 deletions
diff --git a/include/linux/timerlist.h b/include/linux/timerlist.h
deleted file mode 100644
index c46b28ae6e4d..000000000000
--- a/include/linux/timerlist.h
+++ /dev/null
@@ -1,37 +0,0 @@
1#ifndef _LINUX_TIMERLIST_H
2#define _LINUX_TIMERLIST_H
3
4#include <linux/rbtree.h>
5#include <linux/ktime.h>
6
7
8struct timerlist_node {
9 struct rb_node node;
10 ktime_t expires;
11};
12
13struct timerlist_head {
14 struct rb_root head;
15 struct timerlist_node *next;
16};
17
18
19extern void timerlist_add(struct timerlist_head *head,
20 struct timerlist_node *node);
21extern void timerlist_del(struct timerlist_head *head,
22 struct timerlist_node *node);
23extern struct timerlist_node *timerlist_getnext(struct timerlist_head *head);
24extern struct timerlist_node *timerlist_iterate_next(
25 struct timerlist_node *node);
26
27static inline void timerlist_init(struct timerlist_node *node)
28{
29 RB_CLEAR_NODE(&node->node);
30}
31
32static inline void timerlist_init_head(struct timerlist_head *head)
33{
34 head->head = RB_ROOT;
35 head->next = NULL;
36}
37#endif /* _LINUX_TIMERLIST_H */
diff --git a/include/linux/timerqueue.h b/include/linux/timerqueue.h
new file mode 100644
index 000000000000..406b103894bd
--- /dev/null
+++ b/include/linux/timerqueue.h
@@ -0,0 +1,37 @@
1#ifndef _LINUX_TIMERQUEUE_H
2#define _LINUX_TIMERQUEUE_H
3
4#include <linux/rbtree.h>
5#include <linux/ktime.h>
6
7
8struct timerqueue_node {
9 struct rb_node node;
10 ktime_t expires;
11};
12
13struct timerqueue_head {
14 struct rb_root head;
15 struct timerqueue_node *next;
16};
17
18
19extern void timerqueue_add(struct timerqueue_head *head,
20 struct timerqueue_node *node);
21extern void timerqueue_del(struct timerqueue_head *head,
22 struct timerqueue_node *node);
23extern struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head);
24extern struct timerqueue_node *timerqueue_iterate_next(
25 struct timerqueue_node *node);
26
27static inline void timerqueue_init(struct timerqueue_node *node)
28{
29 RB_CLEAR_NODE(&node->node);
30}
31
32static inline void timerqueue_init_head(struct timerqueue_head *head)
33{
34 head->head = RB_ROOT;
35 head->next = NULL;
36}
37#endif /* _LINUX_TIMERQUEUE_H */
diff --git a/lib/Makefile b/lib/Makefile
index 8b475cfb8195..9e2db72d128e 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -8,7 +8,7 @@ KBUILD_CFLAGS = $(subst -pg,,$(ORIG_CFLAGS))
8endif 8endif
9 9
10lib-y := ctype.o string.o vsprintf.o cmdline.o \ 10lib-y := ctype.o string.o vsprintf.o cmdline.o \
11 rbtree.o radix-tree.o dump_stack.o timerlist.o\ 11 rbtree.o radix-tree.o dump_stack.o timerqueue.o\
12 idr.o int_sqrt.o extable.o prio_tree.o \ 12 idr.o int_sqrt.o extable.o prio_tree.o \
13 sha1.o irq_regs.o reciprocal_div.o argv_split.o \ 13 sha1.o irq_regs.o reciprocal_div.o argv_split.o \
14 proportions.o prio_heap.o ratelimit.o show_mem.o \ 14 proportions.o prio_heap.o ratelimit.o show_mem.o \
diff --git a/lib/timerlist.c b/lib/timerqueue.c
index 9101b42fd13d..f46de84d9467 100644
--- a/lib/timerlist.c
+++ b/lib/timerqueue.c
@@ -1,7 +1,7 @@
1/* 1/*
2 * Generic Timer-list 2 * Generic Timer-queue
3 * 3 *
4 * Manages a simple list of timers, ordered by expiration time. 4 * Manages a simple queue of timers, ordered by expiration time.
5 * Uses rbtrees for quick list adds and expiration. 5 * Uses rbtrees for quick list adds and expiration.
6 * 6 *
7 * NOTE: All of the following functions need to be serialized 7 * NOTE: All of the following functions need to be serialized
@@ -22,30 +22,30 @@
22 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 22 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23 */ 23 */
24 24
25#include <linux/timerlist.h> 25#include <linux/timerqueue.h>
26#include <linux/rbtree.h> 26#include <linux/rbtree.h>
27 27
28/** 28/**
29 * timerlist_add - Adds timer to timerlist. 29 * timerqueue_add - Adds timer to timerqueue.
30 * 30 *
31 * @head: head of timerlist 31 * @head: head of timerqueue
32 * @node: timer node to be added 32 * @node: timer node to be added
33 * 33 *
34 * Adds the timer node to the timerlist, sorted by the 34 * Adds the timer node to the timerqueue, sorted by the
35 * node's expires value. 35 * node's expires value.
36 */ 36 */
37void timerlist_add(struct timerlist_head *head, struct timerlist_node *node) 37void timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
38{ 38{
39 struct rb_node **p = &head->head.rb_node; 39 struct rb_node **p = &head->head.rb_node;
40 struct rb_node *parent = NULL; 40 struct rb_node *parent = NULL;
41 struct timerlist_node *ptr; 41 struct timerqueue_node *ptr;
42 42
43 /* Make sure we don't add nodes that are already added */ 43 /* Make sure we don't add nodes that are already added */
44 WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); 44 WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node));
45 45
46 while (*p) { 46 while (*p) {
47 parent = *p; 47 parent = *p;
48 ptr = rb_entry(parent, struct timerlist_node, node); 48 ptr = rb_entry(parent, struct timerqueue_node, node);
49 if (node->expires.tv64 < ptr->expires.tv64) 49 if (node->expires.tv64 < ptr->expires.tv64)
50 p = &(*p)->rb_left; 50 p = &(*p)->rb_left;
51 else 51 else
@@ -59,14 +59,14 @@ void timerlist_add(struct timerlist_head *head, struct timerlist_node *node)
59} 59}
60 60
61/** 61/**
62 * timerlist_del - Removes a timer from the timerlist. 62 * timerqueue_del - Removes a timer from the timerqueue.
63 * 63 *
64 * @head: head of timerlist 64 * @head: head of timerqueue
65 * @node: timer node to be removed 65 * @node: timer node to be removed
66 * 66 *
67 * Removes the timer node from the timerlist. 67 * Removes the timer node from the timerqueue.
68 */ 68 */
69void timerlist_del(struct timerlist_head *head, struct timerlist_node *node) 69void timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node)
70{ 70{
71 WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); 71 WARN_ON_ONCE(RB_EMPTY_NODE(&node->node));
72 72
@@ -75,7 +75,7 @@ void timerlist_del(struct timerlist_head *head, struct timerlist_node *node)
75 struct rb_node *rbn = rb_next(&node->node); 75 struct rb_node *rbn = rb_next(&node->node);
76 76
77 head->next = rbn ? 77 head->next = rbn ?
78 rb_entry(rbn, struct timerlist_node, node) : NULL; 78 rb_entry(rbn, struct timerqueue_node, node) : NULL;
79 } 79 }
80 rb_erase(&node->node, &head->head); 80 rb_erase(&node->node, &head->head);
81 RB_CLEAR_NODE(&node->node); 81 RB_CLEAR_NODE(&node->node);
@@ -83,21 +83,21 @@ void timerlist_del(struct timerlist_head *head, struct timerlist_node *node)
83 83
84 84
85/** 85/**
86 * timerlist_getnext - Returns the timer with the earlies expiration time 86 * timerqueue_getnext - Returns the timer with the earlies expiration time
87 * 87 *
88 * @head: head of timerlist 88 * @head: head of timerqueue
89 * 89 *
90 * Returns a pointer to the timer node that has the 90 * Returns a pointer to the timer node that has the
91 * earliest expiration time. 91 * earliest expiration time.
92 */ 92 */
93struct timerlist_node *timerlist_getnext(struct timerlist_head *head) 93struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head)
94{ 94{
95 return head->next; 95 return head->next;
96} 96}
97 97
98 98
99/** 99/**
100 * timerlist_iterate_next - Returns the timer after the provided timer 100 * timerqueue_iterate_next - Returns the timer after the provided timer
101 * 101 *
102 * @node: Pointer to a timer. 102 * @node: Pointer to a timer.
103 * 103 *
@@ -105,7 +105,7 @@ struct timerlist_node *timerlist_getnext(struct timerlist_head *head)
105 * necessary, to iterate through the list of timers in a timer list 105 * necessary, to iterate through the list of timers in a timer list
106 * without modifying the list. 106 * without modifying the list.
107 */ 107 */
108struct timerlist_node *timerlist_iterate_next(struct timerlist_node *node) 108struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node)
109{ 109{
110 struct rb_node *next; 110 struct rb_node *next;
111 111
@@ -114,5 +114,5 @@ struct timerlist_node *timerlist_iterate_next(struct timerlist_node *node)
114 next = rb_next(&node->node); 114 next = rb_next(&node->node);
115 if (!next) 115 if (!next)
116 return NULL; 116 return NULL;
117 return container_of(next, struct timerlist_node, node); 117 return container_of(next, struct timerqueue_node, node);
118} 118}