Version:  2.0.40 2.2.26 2.4.37 3.13 3.14 3.15 3.16 3.17 3.18 3.19 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10

Linux/lib/timerqueue.c

  1 /*
  2  *  Generic Timer-queue
  3  *
  4  *  Manages a simple queue of timers, ordered by expiration time.
  5  *  Uses rbtrees for quick list adds and expiration.
  6  *
  7  *  NOTE: All of the following functions need to be serialized
  8  *  to avoid races. No locking is done by this library code.
  9  *
 10  *  This program is free software; you can redistribute it and/or modify
 11  *  it under the terms of the GNU General Public License as published by
 12  *  the Free Software Foundation; either version 2 of the License, or
 13  *  (at your option) any later version.
 14  *
 15  *  This program is distributed in the hope that it will be useful,
 16  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 17  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 18  *  GNU General Public License for more details.
 19  *
 20  *  You should have received a copy of the GNU General Public License
 21  *  along with this program; if not, write to the Free Software
 22  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 23  */
 24 
 25 #include <linux/bug.h>
 26 #include <linux/timerqueue.h>
 27 #include <linux/rbtree.h>
 28 #include <linux/export.h>
 29 
 30 /**
 31  * timerqueue_add - Adds timer to timerqueue.
 32  *
 33  * @head: head of timerqueue
 34  * @node: timer node to be added
 35  *
 36  * Adds the timer node to the timerqueue, sorted by the
 37  * node's expires value.
 38  */
 39 bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
 40 {
 41         struct rb_node **p = &head->head.rb_node;
 42         struct rb_node *parent = NULL;
 43         struct timerqueue_node  *ptr;
 44 
 45         /* Make sure we don't add nodes that are already added */
 46         WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node));
 47 
 48         while (*p) {
 49                 parent = *p;
 50                 ptr = rb_entry(parent, struct timerqueue_node, node);
 51                 if (node->expires < ptr->expires)
 52                         p = &(*p)->rb_left;
 53                 else
 54                         p = &(*p)->rb_right;
 55         }
 56         rb_link_node(&node->node, parent, p);
 57         rb_insert_color(&node->node, &head->head);
 58 
 59         if (!head->next || node->expires < head->next->expires) {
 60                 head->next = node;
 61                 return true;
 62         }
 63         return false;
 64 }
 65 EXPORT_SYMBOL_GPL(timerqueue_add);
 66 
 67 /**
 68  * timerqueue_del - Removes a timer from the timerqueue.
 69  *
 70  * @head: head of timerqueue
 71  * @node: timer node to be removed
 72  *
 73  * Removes the timer node from the timerqueue.
 74  */
 75 bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node)
 76 {
 77         WARN_ON_ONCE(RB_EMPTY_NODE(&node->node));
 78 
 79         /* update next pointer */
 80         if (head->next == node) {
 81                 struct rb_node *rbn = rb_next(&node->node);
 82 
 83                 head->next = rbn ?
 84                         rb_entry(rbn, struct timerqueue_node, node) : NULL;
 85         }
 86         rb_erase(&node->node, &head->head);
 87         RB_CLEAR_NODE(&node->node);
 88         return head->next != NULL;
 89 }
 90 EXPORT_SYMBOL_GPL(timerqueue_del);
 91 
 92 /**
 93  * timerqueue_iterate_next - Returns the timer after the provided timer
 94  *
 95  * @node: Pointer to a timer.
 96  *
 97  * Provides the timer that is after the given node. This is used, when
 98  * necessary, to iterate through the list of timers in a timer list
 99  * without modifying the list.
100  */
101 struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node)
102 {
103         struct rb_node *next;
104 
105         if (!node)
106                 return NULL;
107         next = rb_next(&node->node);
108         if (!next)
109                 return NULL;
110         return container_of(next, struct timerqueue_node, node);
111 }
112 EXPORT_SYMBOL_GPL(timerqueue_iterate_next);
113 

This page was automatically generated by LXR 0.3.1 (source).  •  Linux is a registered trademark of Linus Torvalds  •  Contact us