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 libary 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/timerqueue.h> 26 #include <linux/rbtree.h> 27 28 /** 29 * timerqueue_add - Adds timer to timerqueue. 30 * 31 * @head: head of timerqueue 32 * @node: timer node to be added 33 * 34 * Adds the timer node to the timerqueue, sorted by the 35 * node's expires value. 36 */ 37 void timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) 38 { 39 struct rb_node **p = &head->head.rb_node; 40 struct rb_node *parent = NULL; 41 struct timerqueue_node *ptr; 42 43 /* Make sure we don't add nodes that are already added */ 44 WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); 45 46 while (*p) { 47 parent = *p; 48 ptr = rb_entry(parent, struct timerqueue_node, node); 49 if (node->expires.tv64 < ptr->expires.tv64) 50 p = &(*p)->rb_left; 51 else 52 p = &(*p)->rb_right; 53 } 54 rb_link_node(&node->node, parent, p); 55 rb_insert_color(&node->node, &head->head); 56 57 if (!head->next || node->expires.tv64 < head->next->expires.tv64) 58 head->next = node; 59 } 60 61 /** 62 * timerqueue_del - Removes a timer from the timerqueue. 63 * 64 * @head: head of timerqueue 65 * @node: timer node to be removed 66 * 67 * Removes the timer node from the timerqueue. 68 */ 69 void timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) 70 { 71 WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); 72 73 /* update next pointer */ 74 if (head->next == node) { 75 struct rb_node *rbn = rb_next(&node->node); 76 77 head->next = rbn ? 78 rb_entry(rbn, struct timerqueue_node, node) : NULL; 79 } 80 rb_erase(&node->node, &head->head); 81 RB_CLEAR_NODE(&node->node); 82 } 83 84 85 /** 86 * timerqueue_getnext - Returns the timer with the earlies expiration time 87 * 88 * @head: head of timerqueue 89 * 90 * Returns a pointer to the timer node that has the 91 * earliest expiration time. 92 */ 93 struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head) 94 { 95 return head->next; 96 } 97 98 99 /** 100 * timerqueue_iterate_next - Returns the timer after the provided timer 101 * 102 * @node: Pointer to a timer. 103 * 104 * Provides the timer that is after the given node. This is used, when 105 * necessary, to iterate through the list of timers in a timer list 106 * without modifying the list. 107 */ 108 struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node) 109 { 110 struct rb_node *next; 111 112 if (!node) 113 return NULL; 114 next = rb_next(&node->node); 115 if (!next) 116 return NULL; 117 return container_of(next, struct timerqueue_node, node); 118 } 119