Back to home page

LXR

 
 

    


0001 /*
0002  *  Generic Timer-queue
0003  *
0004  *  Manages a simple queue of timers, ordered by expiration time.
0005  *  Uses rbtrees for quick list adds and expiration.
0006  *
0007  *  NOTE: All of the following functions need to be serialized
0008  *  to avoid races. No locking is done by this library code.
0009  *
0010  *  This program is free software; you can redistribute it and/or modify
0011  *  it under the terms of the GNU General Public License as published by
0012  *  the Free Software Foundation; either version 2 of the License, or
0013  *  (at your option) any later version.
0014  *
0015  *  This program is distributed in the hope that it will be useful,
0016  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
0017  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
0018  *  GNU General Public License for more details.
0019  *
0020  *  You should have received a copy of the GNU General Public License
0021  *  along with this program; if not, write to the Free Software
0022  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
0023  */
0024 
0025 #include <linux/bug.h>
0026 #include <linux/timerqueue.h>
0027 #include <linux/rbtree.h>
0028 #include <linux/export.h>
0029 
0030 /**
0031  * timerqueue_add - Adds timer to timerqueue.
0032  *
0033  * @head: head of timerqueue
0034  * @node: timer node to be added
0035  *
0036  * Adds the timer node to the timerqueue, sorted by the
0037  * node's expires value.
0038  */
0039 bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
0040 {
0041     struct rb_node **p = &head->head.rb_node;
0042     struct rb_node *parent = NULL;
0043     struct timerqueue_node  *ptr;
0044 
0045     /* Make sure we don't add nodes that are already added */
0046     WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node));
0047 
0048     while (*p) {
0049         parent = *p;
0050         ptr = rb_entry(parent, struct timerqueue_node, node);
0051         if (node->expires < ptr->expires)
0052             p = &(*p)->rb_left;
0053         else
0054             p = &(*p)->rb_right;
0055     }
0056     rb_link_node(&node->node, parent, p);
0057     rb_insert_color(&node->node, &head->head);
0058 
0059     if (!head->next || node->expires < head->next->expires) {
0060         head->next = node;
0061         return true;
0062     }
0063     return false;
0064 }
0065 EXPORT_SYMBOL_GPL(timerqueue_add);
0066 
0067 /**
0068  * timerqueue_del - Removes a timer from the timerqueue.
0069  *
0070  * @head: head of timerqueue
0071  * @node: timer node to be removed
0072  *
0073  * Removes the timer node from the timerqueue.
0074  */
0075 bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node)
0076 {
0077     WARN_ON_ONCE(RB_EMPTY_NODE(&node->node));
0078 
0079     /* update next pointer */
0080     if (head->next == node) {
0081         struct rb_node *rbn = rb_next(&node->node);
0082 
0083         head->next = rbn ?
0084             rb_entry(rbn, struct timerqueue_node, node) : NULL;
0085     }
0086     rb_erase(&node->node, &head->head);
0087     RB_CLEAR_NODE(&node->node);
0088     return head->next != NULL;
0089 }
0090 EXPORT_SYMBOL_GPL(timerqueue_del);
0091 
0092 /**
0093  * timerqueue_iterate_next - Returns the timer after the provided timer
0094  *
0095  * @node: Pointer to a timer.
0096  *
0097  * Provides the timer that is after the given node. This is used, when
0098  * necessary, to iterate through the list of timers in a timer list
0099  * without modifying the list.
0100  */
0101 struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node)
0102 {
0103     struct rb_node *next;
0104 
0105     if (!node)
0106         return NULL;
0107     next = rb_next(&node->node);
0108     if (!next)
0109         return NULL;
0110     return container_of(next, struct timerqueue_node, node);
0111 }
0112 EXPORT_SYMBOL_GPL(timerqueue_iterate_next);