4 * Manages a simple queue of timers, ordered by expiration time.
5 * Uses rbtrees for quick list adds and expiration.
7 * NOTE: All of the following functions need to be serialized
8 * to avoid races. No locking is done by this library code.
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.
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.
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
25 #include <linux/timerqueue.h>
26 #include <linux/rbtree.h>
27 #include <linux/module.h>
30 * timerqueue_add - Adds timer to timerqueue.
32 * @head: head of timerqueue
33 * @node: timer node to be added
35 * Adds the timer node to the timerqueue, sorted by the
36 * node's expires value.
38 void timerqueue_add(struct timerqueue_head
*head
, struct timerqueue_node
*node
)
40 struct rb_node
**p
= &head
->head
.rb_node
;
41 struct rb_node
*parent
= NULL
;
42 struct timerqueue_node
*ptr
;
44 /* Make sure we don't add nodes that are already added */
45 WARN_ON_ONCE(!RB_EMPTY_NODE(&node
->node
));
49 ptr
= rb_entry(parent
, struct timerqueue_node
, node
);
50 if (node
->expires
.tv64
< ptr
->expires
.tv64
)
55 rb_link_node(&node
->node
, parent
, p
);
56 rb_insert_color(&node
->node
, &head
->head
);
58 if (!head
->next
|| node
->expires
.tv64
< head
->next
->expires
.tv64
)
61 EXPORT_SYMBOL_GPL(timerqueue_add
);
64 * timerqueue_del - Removes a timer from the timerqueue.
66 * @head: head of timerqueue
67 * @node: timer node to be removed
69 * Removes the timer node from the timerqueue.
71 void timerqueue_del(struct timerqueue_head
*head
, struct timerqueue_node
*node
)
73 WARN_ON_ONCE(RB_EMPTY_NODE(&node
->node
));
75 /* update next pointer */
76 if (head
->next
== node
) {
77 struct rb_node
*rbn
= rb_next(&node
->node
);
80 rb_entry(rbn
, struct timerqueue_node
, node
) : NULL
;
82 rb_erase(&node
->node
, &head
->head
);
83 RB_CLEAR_NODE(&node
->node
);
85 EXPORT_SYMBOL_GPL(timerqueue_del
);
88 * timerqueue_iterate_next - Returns the timer after the provided timer
90 * @node: Pointer to a timer.
92 * Provides the timer that is after the given node. This is used, when
93 * necessary, to iterate through the list of timers in a timer list
94 * without modifying the list.
96 struct timerqueue_node
*timerqueue_iterate_next(struct timerqueue_node
*node
)
102 next
= rb_next(&node
->node
);
105 return container_of(next
, struct timerqueue_node
, node
);
107 EXPORT_SYMBOL_GPL(timerqueue_iterate_next
);
This page took 0.033529 seconds and 5 git commands to generate.