11f5a2479SJohn Stultz /* 21f5a2479SJohn Stultz * Generic Timer-queue 31f5a2479SJohn Stultz * 41f5a2479SJohn Stultz * Manages a simple queue of timers, ordered by expiration time. 51f5a2479SJohn Stultz * Uses rbtrees for quick list adds and expiration. 61f5a2479SJohn Stultz * 71f5a2479SJohn Stultz * NOTE: All of the following functions need to be serialized 8*25985edcSLucas De Marchi * to avoid races. No locking is done by this library code. 91f5a2479SJohn Stultz * 101f5a2479SJohn Stultz * This program is free software; you can redistribute it and/or modify 111f5a2479SJohn Stultz * it under the terms of the GNU General Public License as published by 121f5a2479SJohn Stultz * the Free Software Foundation; either version 2 of the License, or 131f5a2479SJohn Stultz * (at your option) any later version. 141f5a2479SJohn Stultz * 151f5a2479SJohn Stultz * This program is distributed in the hope that it will be useful, 161f5a2479SJohn Stultz * but WITHOUT ANY WARRANTY; without even the implied warranty of 171f5a2479SJohn Stultz * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 181f5a2479SJohn Stultz * GNU General Public License for more details. 191f5a2479SJohn Stultz * 201f5a2479SJohn Stultz * You should have received a copy of the GNU General Public License 211f5a2479SJohn Stultz * along with this program; if not, write to the Free Software 221f5a2479SJohn Stultz * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 231f5a2479SJohn Stultz */ 241f5a2479SJohn Stultz 251f5a2479SJohn Stultz #include <linux/timerqueue.h> 261f5a2479SJohn Stultz #include <linux/rbtree.h> 279bb99b14SJohn Stultz #include <linux/module.h> 281f5a2479SJohn Stultz 291f5a2479SJohn Stultz /** 301f5a2479SJohn Stultz * timerqueue_add - Adds timer to timerqueue. 311f5a2479SJohn Stultz * 321f5a2479SJohn Stultz * @head: head of timerqueue 331f5a2479SJohn Stultz * @node: timer node to be added 341f5a2479SJohn Stultz * 351f5a2479SJohn Stultz * Adds the timer node to the timerqueue, sorted by the 361f5a2479SJohn Stultz * node's expires value. 371f5a2479SJohn Stultz */ 381f5a2479SJohn Stultz void timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) 391f5a2479SJohn Stultz { 401f5a2479SJohn Stultz struct rb_node **p = &head->head.rb_node; 411f5a2479SJohn Stultz struct rb_node *parent = NULL; 421f5a2479SJohn Stultz struct timerqueue_node *ptr; 431f5a2479SJohn Stultz 441f5a2479SJohn Stultz /* Make sure we don't add nodes that are already added */ 451f5a2479SJohn Stultz WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); 461f5a2479SJohn Stultz 471f5a2479SJohn Stultz while (*p) { 481f5a2479SJohn Stultz parent = *p; 491f5a2479SJohn Stultz ptr = rb_entry(parent, struct timerqueue_node, node); 501f5a2479SJohn Stultz if (node->expires.tv64 < ptr->expires.tv64) 511f5a2479SJohn Stultz p = &(*p)->rb_left; 521f5a2479SJohn Stultz else 531f5a2479SJohn Stultz p = &(*p)->rb_right; 541f5a2479SJohn Stultz } 551f5a2479SJohn Stultz rb_link_node(&node->node, parent, p); 561f5a2479SJohn Stultz rb_insert_color(&node->node, &head->head); 571f5a2479SJohn Stultz 581f5a2479SJohn Stultz if (!head->next || node->expires.tv64 < head->next->expires.tv64) 591f5a2479SJohn Stultz head->next = node; 601f5a2479SJohn Stultz } 619bb99b14SJohn Stultz EXPORT_SYMBOL_GPL(timerqueue_add); 621f5a2479SJohn Stultz 631f5a2479SJohn Stultz /** 641f5a2479SJohn Stultz * timerqueue_del - Removes a timer from the timerqueue. 651f5a2479SJohn Stultz * 661f5a2479SJohn Stultz * @head: head of timerqueue 671f5a2479SJohn Stultz * @node: timer node to be removed 681f5a2479SJohn Stultz * 691f5a2479SJohn Stultz * Removes the timer node from the timerqueue. 701f5a2479SJohn Stultz */ 711f5a2479SJohn Stultz void timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) 721f5a2479SJohn Stultz { 731f5a2479SJohn Stultz WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); 741f5a2479SJohn Stultz 751f5a2479SJohn Stultz /* update next pointer */ 761f5a2479SJohn Stultz if (head->next == node) { 771f5a2479SJohn Stultz struct rb_node *rbn = rb_next(&node->node); 781f5a2479SJohn Stultz 791f5a2479SJohn Stultz head->next = rbn ? 801f5a2479SJohn Stultz rb_entry(rbn, struct timerqueue_node, node) : NULL; 811f5a2479SJohn Stultz } 821f5a2479SJohn Stultz rb_erase(&node->node, &head->head); 831f5a2479SJohn Stultz RB_CLEAR_NODE(&node->node); 841f5a2479SJohn Stultz } 859bb99b14SJohn Stultz EXPORT_SYMBOL_GPL(timerqueue_del); 861f5a2479SJohn Stultz 871f5a2479SJohn Stultz /** 881f5a2479SJohn Stultz * timerqueue_iterate_next - Returns the timer after the provided timer 891f5a2479SJohn Stultz * 901f5a2479SJohn Stultz * @node: Pointer to a timer. 911f5a2479SJohn Stultz * 921f5a2479SJohn Stultz * Provides the timer that is after the given node. This is used, when 931f5a2479SJohn Stultz * necessary, to iterate through the list of timers in a timer list 941f5a2479SJohn Stultz * without modifying the list. 951f5a2479SJohn Stultz */ 961f5a2479SJohn Stultz struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node) 971f5a2479SJohn Stultz { 981f5a2479SJohn Stultz struct rb_node *next; 991f5a2479SJohn Stultz 1001f5a2479SJohn Stultz if (!node) 1011f5a2479SJohn Stultz return NULL; 1021f5a2479SJohn Stultz next = rb_next(&node->node); 1031f5a2479SJohn Stultz if (!next) 1041f5a2479SJohn Stultz return NULL; 1051f5a2479SJohn Stultz return container_of(next, struct timerqueue_node, node); 1061f5a2479SJohn Stultz } 1079bb99b14SJohn Stultz EXPORT_SYMBOL_GPL(timerqueue_iterate_next); 108