11a59d1b8SThomas Gleixner // SPDX-License-Identifier: GPL-2.0-or-later
21f5a2479SJohn Stultz /*
31f5a2479SJohn Stultz * Generic Timer-queue
41f5a2479SJohn Stultz *
51f5a2479SJohn Stultz * Manages a simple queue of timers, ordered by expiration time.
61f5a2479SJohn Stultz * Uses rbtrees for quick list adds and expiration.
71f5a2479SJohn Stultz *
81f5a2479SJohn Stultz * NOTE: All of the following functions need to be serialized
925985edcSLucas De Marchi * to avoid races. No locking is done by this library code.
101f5a2479SJohn Stultz */
111f5a2479SJohn Stultz
1250af5eadSPaul Gortmaker #include <linux/bug.h>
131f5a2479SJohn Stultz #include <linux/timerqueue.h>
141f5a2479SJohn Stultz #include <linux/rbtree.h>
158bc3bcc9SPaul Gortmaker #include <linux/export.h>
161f5a2479SJohn Stultz
17*798172b1SPeter Zijlstra #define __node_2_tq(_n) \
18*798172b1SPeter Zijlstra rb_entry((_n), struct timerqueue_node, node)
19*798172b1SPeter Zijlstra
__timerqueue_less(struct rb_node * a,const struct rb_node * b)20*798172b1SPeter Zijlstra static inline bool __timerqueue_less(struct rb_node *a, const struct rb_node *b)
21*798172b1SPeter Zijlstra {
22*798172b1SPeter Zijlstra return __node_2_tq(a)->expires < __node_2_tq(b)->expires;
23*798172b1SPeter Zijlstra }
24*798172b1SPeter Zijlstra
251f5a2479SJohn Stultz /**
261f5a2479SJohn Stultz * timerqueue_add - Adds timer to timerqueue.
271f5a2479SJohn Stultz *
281f5a2479SJohn Stultz * @head: head of timerqueue
291f5a2479SJohn Stultz * @node: timer node to be added
301f5a2479SJohn Stultz *
319f4533cdSThomas Gleixner * Adds the timer node to the timerqueue, sorted by the node's expires
329f4533cdSThomas Gleixner * value. Returns true if the newly added timer is the first expiring timer in
339f4533cdSThomas Gleixner * the queue.
341f5a2479SJohn Stultz */
timerqueue_add(struct timerqueue_head * head,struct timerqueue_node * node)35c320642eSThomas Gleixner bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
361f5a2479SJohn Stultz {
371f5a2479SJohn Stultz /* Make sure we don't add nodes that are already added */
381f5a2479SJohn Stultz WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node));
391f5a2479SJohn Stultz
40*798172b1SPeter Zijlstra return rb_add_cached(&node->node, &head->rb_root, __timerqueue_less);
411f5a2479SJohn Stultz }
429bb99b14SJohn Stultz EXPORT_SYMBOL_GPL(timerqueue_add);
431f5a2479SJohn Stultz
441f5a2479SJohn Stultz /**
451f5a2479SJohn Stultz * timerqueue_del - Removes a timer from the timerqueue.
461f5a2479SJohn Stultz *
471f5a2479SJohn Stultz * @head: head of timerqueue
481f5a2479SJohn Stultz * @node: timer node to be removed
491f5a2479SJohn Stultz *
509f4533cdSThomas Gleixner * Removes the timer node from the timerqueue. Returns true if the queue is
519f4533cdSThomas Gleixner * not empty after the remove.
521f5a2479SJohn Stultz */
timerqueue_del(struct timerqueue_head * head,struct timerqueue_node * node)53c320642eSThomas Gleixner bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node)
541f5a2479SJohn Stultz {
551f5a2479SJohn Stultz WARN_ON_ONCE(RB_EMPTY_NODE(&node->node));
561f5a2479SJohn Stultz
57511885d7SDavidlohr Bueso rb_erase_cached(&node->node, &head->rb_root);
581f5a2479SJohn Stultz RB_CLEAR_NODE(&node->node);
59511885d7SDavidlohr Bueso
60511885d7SDavidlohr Bueso return !RB_EMPTY_ROOT(&head->rb_root.rb_root);
611f5a2479SJohn Stultz }
629bb99b14SJohn Stultz EXPORT_SYMBOL_GPL(timerqueue_del);
631f5a2479SJohn Stultz
641f5a2479SJohn Stultz /**
651f5a2479SJohn Stultz * timerqueue_iterate_next - Returns the timer after the provided timer
661f5a2479SJohn Stultz *
671f5a2479SJohn Stultz * @node: Pointer to a timer.
681f5a2479SJohn Stultz *
691f5a2479SJohn Stultz * Provides the timer that is after the given node. This is used, when
701f5a2479SJohn Stultz * necessary, to iterate through the list of timers in a timer list
711f5a2479SJohn Stultz * without modifying the list.
721f5a2479SJohn Stultz */
timerqueue_iterate_next(struct timerqueue_node * node)731f5a2479SJohn Stultz struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node)
741f5a2479SJohn Stultz {
751f5a2479SJohn Stultz struct rb_node *next;
761f5a2479SJohn Stultz
771f5a2479SJohn Stultz if (!node)
781f5a2479SJohn Stultz return NULL;
791f5a2479SJohn Stultz next = rb_next(&node->node);
801f5a2479SJohn Stultz if (!next)
811f5a2479SJohn Stultz return NULL;
821f5a2479SJohn Stultz return container_of(next, struct timerqueue_node, node);
831f5a2479SJohn Stultz }
849bb99b14SJohn Stultz EXPORT_SYMBOL_GPL(timerqueue_iterate_next);
85