diff options
author | John Stultz <john.stultz@linaro.org> | 2010-09-20 17:42:46 -0700 |
---|---|---|
committer | John Stultz <john.stultz@linaro.org> | 2010-12-02 16:41:39 -0800 |
commit | 87de5ac782761a3ebf806e434e8c9cc205a87274 (patch) | |
tree | 8186969d00da5d0daea37fcb92538bbc72c8f086 /lib | |
parent | 5e4f083f78d03e9f8d2e327daccde16976f9bb00 (diff) | |
download | kernel_samsung_smdk4412-87de5ac782761a3ebf806e434e8c9cc205a87274.zip kernel_samsung_smdk4412-87de5ac782761a3ebf806e434e8c9cc205a87274.tar.gz kernel_samsung_smdk4412-87de5ac782761a3ebf806e434e8c9cc205a87274.tar.bz2 |
timers: Introduce timerlist infrastructure.
The timerlist infrastructure is a thin layer over the rbtree
code that implements a simple list of timers sorted by an
expires value, and a getnext function that provides a pointer
to the earliest timer.
This infrastructure allows drivers and other kernel infrastructure
to easily implement timers without duplicating code.
Signed-off-by: John Stultz <john.stultz@linaro.org>
LKML Reference: <1290136329-18291-2-git-send-email-john.stultz@linaro.org>
Reviewed-by: Thomas Gleixner <tglx@linutronix.de>
CC: Alessandro Zummo <a.zummo@towertech.it>
CC: Thomas Gleixner <tglx@linutronix.de>
CC: Richard Cochran <richardcochran@gmail.com>
Diffstat (limited to 'lib')
-rw-r--r-- | lib/Makefile | 2 | ||||
-rw-r--r-- | lib/timerlist.c | 118 |
2 files changed, 119 insertions, 1 deletions
diff --git a/lib/Makefile b/lib/Makefile index e6a3763..8b475cf 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -8,7 +8,7 @@ KBUILD_CFLAGS = $(subst -pg,,$(ORIG_CFLAGS)) endif lib-y := ctype.o string.o vsprintf.o cmdline.o \ - rbtree.o radix-tree.o dump_stack.o \ + rbtree.o radix-tree.o dump_stack.o timerlist.o\ idr.o int_sqrt.o extable.o prio_tree.o \ sha1.o irq_regs.o reciprocal_div.o argv_split.o \ proportions.o prio_heap.o ratelimit.o show_mem.o \ diff --git a/lib/timerlist.c b/lib/timerlist.c new file mode 100644 index 0000000..9101b42 --- /dev/null +++ b/lib/timerlist.c @@ -0,0 +1,118 @@ +/* + * Generic Timer-list + * + * Manages a simple list 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 <linux/timerlist.h> +#include <linux/rbtree.h> + +/** + * timerlist_add - Adds timer to timerlist. + * + * @head: head of timerlist + * @node: timer node to be added + * + * Adds the timer node to the timerlist, sorted by the + * node's expires value. + */ +void timerlist_add(struct timerlist_head *head, struct timerlist_node *node) +{ + struct rb_node **p = &head->head.rb_node; + struct rb_node *parent = NULL; + struct timerlist_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 timerlist_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; +} + +/** + * timerlist_del - Removes a timer from the timerlist. + * + * @head: head of timerlist + * @node: timer node to be removed + * + * Removes the timer node from the timerlist. + */ +void timerlist_del(struct timerlist_head *head, struct timerlist_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 timerlist_node, node) : NULL; + } + rb_erase(&node->node, &head->head); + RB_CLEAR_NODE(&node->node); +} + + +/** + * timerlist_getnext - Returns the timer with the earlies expiration time + * + * @head: head of timerlist + * + * Returns a pointer to the timer node that has the + * earliest expiration time. + */ +struct timerlist_node *timerlist_getnext(struct timerlist_head *head) +{ + return head->next; +} + + +/** + * timerlist_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 timerlist_node *timerlist_iterate_next(struct timerlist_node *node) +{ + struct rb_node *next; + + if (!node) + return NULL; + next = rb_next(&node->node); + if (!next) + return NULL; + return container_of(next, struct timerlist_node, node); +} |