From 1f5a24794a54588ea3a9efd521be31d826e0b9d7 Mon Sep 17 00:00:00 2001 From: John Stultz Date: Thu, 9 Dec 2010 12:02:18 -0800 Subject: timers: Rename timerlist infrastructure to timerqueue Thomas pointed out a namespace collision between the new timerlist infrastructure I introduced and the existing timer_list.c So to avoid confusion, I've renamed the timerlist infrastructure to timerqueue. Reported-by: Thomas Gleixner Signed-off-by: John Stultz --- lib/timerqueue.c | 118 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 118 insertions(+) create mode 100644 lib/timerqueue.c (limited to 'lib/timerqueue.c') diff --git a/lib/timerqueue.c b/lib/timerqueue.c new file mode 100644 index 00000000000..f46de84d946 --- /dev/null +++ b/lib/timerqueue.c @@ -0,0 +1,118 @@ +/* + * Generic Timer-queue + * + * Manages a simple queue of timers, ordered by expiration time. + * Uses rbtrees for quick list adds and expiration. + * + * NOTE: All of the following functions need to be serialized + * to avoid races. No locking is done by this libary code. + * + * 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 + */ + +#include +#include + +/** + * timerqueue_add - Adds timer to timerqueue. + * + * @head: head of timerqueue + * @node: timer node to be added + * + * Adds the timer node to the timerqueue, sorted by the + * node's expires value. + */ +void timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) +{ + struct rb_node **p = &head->head.rb_node; + struct rb_node *parent = NULL; + struct timerqueue_node *ptr; + + /* Make sure we don't add nodes that are already added */ + WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); + + while (*p) { + parent = *p; + ptr = rb_entry(parent, struct timerqueue_node, node); + if (node->expires.tv64 < ptr->expires.tv64) + p = &(*p)->rb_left; + else + p = &(*p)->rb_right; + } + rb_link_node(&node->node, parent, p); + rb_insert_color(&node->node, &head->head); + + if (!head->next || node->expires.tv64 < head->next->expires.tv64) + head->next = node; +} + +/** + * timerqueue_del - Removes a timer from the timerqueue. + * + * @head: head of timerqueue + * @node: timer node to be removed + * + * Removes the timer node from the timerqueue. + */ +void timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) +{ + WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); + + /* update next pointer */ + if (head->next == node) { + struct rb_node *rbn = rb_next(&node->node); + + head->next = rbn ? + rb_entry(rbn, struct timerqueue_node, node) : NULL; + } + rb_erase(&node->node, &head->head); + RB_CLEAR_NODE(&node->node); +} + + +/** + * timerqueue_getnext - Returns the timer with the earlies expiration time + * + * @head: head of timerqueue + * + * Returns a pointer to the timer node that has the + * earliest expiration time. + */ +struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head) +{ + return head->next; +} + + +/** + * timerqueue_iterate_next - Returns the timer after the provided timer + * + * @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. + */ +struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node) +{ + struct rb_node *next; + + if (!node) + return NULL; + next = rb_next(&node->node); + if (!next) + return NULL; + return container_of(next, struct timerqueue_node, node); +} -- cgit v1.2.3-70-g09d2 From 9bb99b147018945366c763b3d4d7008927dc8557 Mon Sep 17 00:00:00 2001 From: John Stultz Date: Mon, 6 Dec 2010 13:32:12 -0800 Subject: timers: Fixup allmodconfig build issue Adds missed EXPORT_SYMBOL lines that cause the following build failures with allmodconfig: ERROR: "timerqueue_add" [drivers/rtc/rtc-core.ko] undefined! ERROR: "timerqueue_getnext" [drivers/rtc/rtc-core.ko] undefined! ERROR: "timerqueue_del" [drivers/rtc/rtc-core.ko] undefined! Reported-by: Ingo Molnar Reported-by: Thomas Gleixner Signed-off-by: John Stultz --- lib/timerqueue.c | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) (limited to 'lib/timerqueue.c') diff --git a/lib/timerqueue.c b/lib/timerqueue.c index f46de84d946..444b0934af9 100644 --- a/lib/timerqueue.c +++ b/lib/timerqueue.c @@ -24,6 +24,7 @@ #include #include +#include /** * timerqueue_add - Adds timer to timerqueue. @@ -57,6 +58,7 @@ void timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) if (!head->next || node->expires.tv64 < head->next->expires.tv64) head->next = node; } +EXPORT_SYMBOL_GPL(timerqueue_add); /** * timerqueue_del - Removes a timer from the timerqueue. @@ -80,7 +82,7 @@ void timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) rb_erase(&node->node, &head->head); RB_CLEAR_NODE(&node->node); } - +EXPORT_SYMBOL_GPL(timerqueue_del); /** * timerqueue_getnext - Returns the timer with the earlies expiration time @@ -94,7 +96,7 @@ struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head) { return head->next; } - +EXPORT_SYMBOL_GPL(timerqueue_getnext); /** * timerqueue_iterate_next - Returns the timer after the provided timer @@ -116,3 +118,4 @@ struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node) return NULL; return container_of(next, struct timerqueue_node, node); } +EXPORT_SYMBOL_GPL(timerqueue_iterate_next); -- cgit v1.2.3-70-g09d2 From 45f74264e18449cf3c93cccaf098ee6e9524ab78 Mon Sep 17 00:00:00 2001 From: Thomas Gleixner Date: Sat, 11 Dec 2010 12:34:34 +0100 Subject: timerqueue: Make timerqueue_getnext() static inline No point in calling a function just to dereference a pointer. Signed-off-by: Thomas Gleixner Cc: John Stultz --- include/linux/timerqueue.h | 15 ++++++++++++++- lib/timerqueue.c | 14 -------------- 2 files changed, 14 insertions(+), 15 deletions(-) (limited to 'lib/timerqueue.c') diff --git a/include/linux/timerqueue.h b/include/linux/timerqueue.h index 406b103894b..d24aabaca47 100644 --- a/include/linux/timerqueue.h +++ b/include/linux/timerqueue.h @@ -20,10 +20,23 @@ extern void timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node); extern void timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node); -extern struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head); extern struct timerqueue_node *timerqueue_iterate_next( struct timerqueue_node *node); +/** + * timerqueue_getnext - Returns the timer with the earlies expiration time + * + * @head: head of timerqueue + * + * Returns a pointer to the timer node that has the + * earliest expiration time. + */ +static inline +struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head) +{ + return head->next; +} + static inline void timerqueue_init(struct timerqueue_node *node) { RB_CLEAR_NODE(&node->node); diff --git a/lib/timerqueue.c b/lib/timerqueue.c index 444b0934af9..e3a1050e682 100644 --- a/lib/timerqueue.c +++ b/lib/timerqueue.c @@ -84,20 +84,6 @@ void timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) } EXPORT_SYMBOL_GPL(timerqueue_del); -/** - * timerqueue_getnext - Returns the timer with the earlies expiration time - * - * @head: head of timerqueue - * - * Returns a pointer to the timer node that has the - * earliest expiration time. - */ -struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head) -{ - return head->next; -} -EXPORT_SYMBOL_GPL(timerqueue_getnext); - /** * timerqueue_iterate_next - Returns the timer after the provided timer * -- cgit v1.2.3-70-g09d2