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 node's expires 37 * value. Returns true if the newly added timer is the first expiring timer in 38 * the queue. 39 */ 40 bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) 41 { 42 struct rb_node **p = &head->head.rb_node; 43 struct rb_node *parent = NULL; 44 struct timerqueue_node *ptr; 45 46 /* Make sure we don't add nodes that are already added */ 47 WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); 48 49 while (*p) { 50 parent = *p; 51 ptr = rb_entry(parent, struct timerqueue_node, node); 52 if (node->expires < ptr->expires) 53 p = &(*p)->rb_left; 54 else 55 p = &(*p)->rb_right; 56 } 57 rb_link_node(&node->node, parent, p); 58 rb_insert_color(&node->node, &head->head); 59 60 if (!head->next || node->expires < head->next->expires) { 61 head->next = node; 62 return true; 63 } 64 return false; 65 } 66 EXPORT_SYMBOL_GPL(timerqueue_add); 67 68 /** 69 * timerqueue_del - Removes a timer from the timerqueue. 70 * 71 * @head: head of timerqueue 72 * @node: timer node to be removed 73 * 74 * Removes the timer node from the timerqueue. Returns true if the queue is 75 * not empty after the remove. 76 */ 77 bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) 78 { 79 WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); 80 81 /* update next pointer */ 82 if (head->next == node) { 83 struct rb_node *rbn = rb_next(&node->node); 84 85 head->next = rb_entry_safe(rbn, struct timerqueue_node, node); 86 } 87 rb_erase(&node->node, &head->head); 88 RB_CLEAR_NODE(&node->node); 89 return head->next != NULL; 90 } 91 EXPORT_SYMBOL_GPL(timerqueue_del); 92 93 /** 94 * timerqueue_iterate_next - Returns the timer after the provided timer 95 * 96 * @node: Pointer to a timer. 97 * 98 * Provides the timer that is after the given node. This is used, when 99 * necessary, to iterate through the list of timers in a timer list 100 * without modifying the list. 101 */ 102 struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node) 103 { 104 struct rb_node *next; 105 106 if (!node) 107 return NULL; 108 next = rb_next(&node->node); 109 if (!next) 110 return NULL; 111 return container_of(next, struct timerqueue_node, node); 112 } 113 EXPORT_SYMBOL_GPL(timerqueue_iterate_next); 114