LXR linux/lib/timerqueue.c

   1// SPDX-License-Identifier: GPL-2.0-or-later
   2/*
   3 *  Generic Timer-queue
   4 *
   5 *  Manages a simple queue of timers, ordered by expiration time.
   6 *  Uses rbtrees for quick list adds and expiration.
   7 *
   8 *  NOTE: All of the following functions need to be serialized
   9 *  to avoid races. No locking is done by this library code.
  10 */
  11
  12#include <linux/bug.h>
  13#include <linux/timerqueue.h>
  14#include <linux/rbtree.h>
  15#include <linux/export.h>
  16
  17/**
  18 * timerqueue_add - Adds timer to timerqueue.
  19 *
  20 * @head: head of timerqueue
  21 * @node: timer node to be added
  22 *
  23 * Adds the timer node to the timerqueue, sorted by the node's expires
  24 * value. Returns true if the newly added timer is the first expiring timer in
  25 * the queue.
  26 */
  27bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
  28{
  29        struct rb_node **p = &head->head.rb_node;
  30        struct rb_node *parent = NULL;
  31        struct timerqueue_node  *ptr;
  32
  33        /* Make sure we don't add nodes that are already added */
  34        WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node));
  35
  36        while (*p) {
  37                parent = *p;
  38                ptr = rb_entry(parent, struct timerqueue_node, node);
  39                if (node->expires < ptr->expires)
  40                        p = &(*p)->rb_left;
  41                else
  42                        p = &(*p)->rb_right;
  43        }
  44        rb_link_node(&node->node, parent, p);
  45        rb_insert_color(&node->node, &head->head);
  46
  47        if (!head->next || node->expires < head->next->expires) {
  48                head->next = node;
  49                return true;
  50        }
  51        return false;
  52}
  53EXPORT_SYMBOL_GPL(timerqueue_add);
  54
  55/**
  56 * timerqueue_del - Removes a timer from the timerqueue.
  57 *
  58 * @head: head of timerqueue
  59 * @node: timer node to be removed
  60 *
  61 * Removes the timer node from the timerqueue. Returns true if the queue is
  62 * not empty after the remove.
  63 */
  64bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node)
  65{
  66        WARN_ON_ONCE(RB_EMPTY_NODE(&node->node));
  67
  68        /* update next pointer */
  69        if (head->next == node) {
  70                struct rb_node *rbn = rb_next(&node->node);
  71
  72                head->next = rb_entry_safe(rbn, struct timerqueue_node, node);
  73        }
  74        rb_erase(&node->node, &head->head);
  75        RB_CLEAR_NODE(&node->node);
  76        return head->next != NULL;
  77}
  78EXPORT_SYMBOL_GPL(timerqueue_del);
  79
  80/**
  81 * timerqueue_iterate_next - Returns the timer after the provided timer
  82 *
  83 * @node: Pointer to a timer.
  84 *
  85 * Provides the timer that is after the given node. This is used, when
  86 * necessary, to iterate through the list of timers in a timer list
  87 * without modifying the list.
  88 */
  89struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node)
  90{
  91        struct rb_node *next;
  92
  93        if (!node)
  94                return NULL;
  95        next = rb_next(&node->node);
  96        if (!next)
  97                return NULL;
  98        return container_of(next, struct timerqueue_node, node);
  99}
 100EXPORT_SYMBOL_GPL(timerqueue_iterate_next);
 101