// SPDX-License-Identifier: GPL-2.0-or-later
/*
 *  Generic Timer-queue
 *
 *  Manages a simple queue of timers, ordered by expiration time.
 *  Uses rbtrees for quick list adds and expiration.
 *
 *  NOTE: All of the following functions need to be serialized
 *  to avoid races. No locking is done by this library code.
 */

#include <linux/bug.h>
#include <linux/timerqueue.h>
#include <linux/rbtree.h>
#include <linux/export.h>

/**
 * timerqueue_add - Adds timer to timerqueue.
 *
 * @head: head of timerqueue
 * @node: timer node to be added
 *
 * Adds the timer node to the timerqueue, sorted by the node's expires
 * value. Returns true if the newly added timer is the first expiring timer in
 * the queue.
 */
bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
{
	struct rb_node **p = &head->rb_root.rb_root.rb_node;
	struct rb_node *parent = NULL;
	struct timerqueue_node *ptr;
	bool leftmost = true;

	/* Make sure we don't add nodes that are already added */
	WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node));

	while (*p) {
		parent = *p;
		ptr = rb_entry(parent, struct timerqueue_node, node);
		if (node->expires < ptr->expires) {
			p = &(*p)->rb_left;
		} else {
			p = &(*p)->rb_right;
			leftmost = false;
		}
	}
	rb_link_node(&node->node, parent, p);
	rb_insert_color_cached(&node->node, &head->rb_root, leftmost);

	return leftmost;
}
EXPORT_SYMBOL_GPL(timerqueue_add);

/**
 * timerqueue_del - Removes a timer from the timerqueue.
 *
 * @head: head of timerqueue
 * @node: timer node to be removed
 *
 * Removes the timer node from the timerqueue. Returns true if the queue is
 * not empty after the remove.
 */
bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node)
{
	WARN_ON_ONCE(RB_EMPTY_NODE(&node->node));

	rb_erase_cached(&node->node, &head->rb_root);
	RB_CLEAR_NODE(&node->node);

	return !RB_EMPTY_ROOT(&head->rb_root.rb_root);
}
EXPORT_SYMBOL_GPL(timerqueue_del);

/**
 * timerqueue_iterate_next - Returns the timer after the provided timer
 *
 * @node: Pointer to a timer.
 *
 * Provides the timer that is after the given node. This is used, when
 * necessary, to iterate through the list of timers in a timer list
 * without modifying the list.
 */
struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node)
{
	struct rb_node *next;

	if (!node)
		return NULL;
	next = rb_next(&node->node);
	if (!next)
		return NULL;
	return container_of(next, struct timerqueue_node, node);
}
EXPORT_SYMBOL_GPL(timerqueue_iterate_next);
7.y</option>
<option value='linux-2.6.38.y'>linux-2.6.38.y</option>
<option value='linux-2.6.39.y'>linux-2.6.39.y</option>
<option value='linux-3.0.y'>linux-3.0.y</option>
<option value='linux-3.1.y'>linux-3.1.y</option>
<option value='linux-3.10.y'>linux-3.10.y</option>
<option value='linux-3.11.y'>linux-3.11.y</option>
<option value='linux-3.12.y'>linux-3.12.y</option>
<option value='linux-3.13.y'>linux-3.13.y</option>
<option value='linux-3.14.y'>linux-3.14.y</option>
<option value='linux-3.15.y'>linux-3.15.y</option>
<option value='linux-3.16.y'>linux-3.16.y</option>
<option value='linux-3.17.y'>linux-3.17.y</option>
<option value='linux-3.18.y'>linux-3.18.y</option>
<option value='linux-3.19.y'>linux-3.19.y</option>
<option value='linux-3.2.y'>linux-3.2.y</option>
<option value='linux-3.3.y'>linux-3.3.y</option>
<option value='linux-3.4.y'>linux-3.4.y</option>
<option value='linux-3.5.y'>linux-3.5.y</option>
<option value='linux-3.6.y'>linux-3.6.y</option>
<option value='linux-3.7.y'>linux-3.7.y</option>
<option value='linux-3.8.y'>linux-3.8.y</option>
<option value='linux-3.9.y'>linux-3.9.y</option>
<option value='linux-4.0.y'>linux-4.0.y</option>
<option value='linux-4.1.y'>linux-4.1.y</option>
<option value='linux-4.10.y'>linux-4.10.y</option>
<option value='linux-4.11.y'>linux-4.11.y</option>
<option value='linux-4.12.y'>linux-4.12.y</option>
<option value='linux-4.13.y'>linux-4.13.y</option>
<option value='linux-4.14.y'>linux-4.14.y</option>
<option value='linux-4.15.y'>linux-4.15.y</option>
<option value='linux-4.16.y'>linux-4.16.y</option>
<option value='linux-4.17.y'>linux-4.17.y</option>
<option value='linux-4.18.y'>linux-4.18.y</option>
<option value='linux-4.19.y'>linux-4.19.y</option>
<option value='linux-4.2.y'>linux-4.2.y</option>
<option value='linux-4.20.y'>linux-4.20.y</option>
<option value='linux-4.3.y'>linux-4.3.y</option>
<option value='linux-4.4.y'>linux-4.4.y</option>
<option value='linux-4.5.y'>linux-4.5.y</option>
<option value='linux-4.6.y'>linux-4.6.y</option>
<option value='linux-4.7.y'>linux-4.7.y</option>
<option value='linux-4.8.y'>linux-4.8.y</option>
<option value='linux-4.9.y'>linux-4.9.y</option>
<option value='linux-5.0.y'>linux-5.0.y</option>
<option value='linux-5.1.y'>linux-5.1.y</option>
<option value='linux-5.10.y'>linux-5.10.y</option>
<option value='linux-5.11.y'>linux-5.11.y</option>
<option value='linux-5.12.y'>linux-5.12.y</option>
<option value='linux-5.13.y'>linux-5.13.y</option>
<option value='linux-5.14.y'>linux-5.14.y</option>
<option value='linux-5.15.y'>linux-5.15.y</option>
<option value='linux-5.16.y'>linux-5.16.y</option>
<option value='linux-5.17.y'>linux-5.17.y</option>
<option value='linux-5.18.y'>linux-5.18.y</option>
<option value='linux-5.19.y'>linux-5.19.y</option>
<option value='linux-5.2.y'>linux-5.2.y</option>
<option value='linux-5.3.y'>linux-5.3.y</option>
<option value='linux-5.4.y'>linux-5.4.y</option>
<option value='linux-5.5.y'>linux-5.5.y</option>
<option value='linux-5.6.y'>linux-5.6.y</option>
<option value='linux-5.7.y'>linux-5.7.y</option>
<option value='linux-5.8.y'>linux-5.8.y</option>
<option value='linux-5.9.y'>linux-5.9.y</option>
<option value='linux-6.0.y'>linux-6.0.y</option>
<option value='linux-6.1.y'>linux-6.1.y</option>
<option value='linux-6.10.y'>linux-6.10.y</option>
<option value='linux-6.11.y'>linux-6.11.y</option>
<option value='linux-6.12.y'>linux-6.12.y</option>
<option value='linux-6.13.y'>linux-6.13.y</option>
<option value='linux-6.14.y'>linux-6.14.y</option>
<option value='linux-6.15.y'>linux-6.15.y</option>
<option value='linux-6.16.y'>linux-6.16.y</option>
<option value='linux-6.17.y'>linux-6.17.y</option>
<option value='linux-6.18.y'>linux-6.18.y</option>
<option value='linux-6.19.y'>linux-6.19.y</option>
<option value='linux-6.2.y'>linux-6.2.y</option>
<option value='linux-6.3.y'>linux-6.3.y</option>
<option value='linux-6.4.y'>linux-6.4.y</option>
<option value='linux-6.5.y'>linux-6.5.y</option>
<option value='linux-6.6.y' selected='selected'>linux-6.6.y</option>
<option value='linux-6.7.y'>linux-6.7.y</option>
<option value='linux-6.8.y'>linux-6.8.y</option>
<option value='linux-6.9.y'>linux-6.9.y</option>
<option value='linux-rolling-lts'>linux-rolling-lts</option>
<option value='linux-rolling-stable'>linux-rolling-stable</option>
<option value='master'>master</option>
</select> <input type='submit' value='switch'/></form></td></tr>
<tr><td class='sub'>Hosts the 0x221E linux distro kernel.</td><td class='sub right'>Ubuntu</td></tr></table>
<table class='tabs'><tr><td>
<a href='/distro/kernel/?h=linux-6.6.y'>summary</a><a href='/distro/kernel/refs/?h=linux-6.6.y&amp;id=d10c98949d1a1fff14d750fe5162213bb5b39e11'>refs</a><a class='active' href='/distro/kernel/log/drivers/media/platform/exynos4-is/fimc-is-sensor.h?h=linux-6.6.y'>log</a><a href='/distro/kernel/tree/drivers/media/platform/exynos4-is/fimc-is-sensor.h?h=linux-6.6.y&amp;id=d10c98949d1a1fff14d750fe5162213bb5b39e11'>tree</a><a href='/distro/kernel/commit/drivers/media/platform/exynos4-is/fimc-is-sensor.h?h=linux-6.6.y&amp;id=d10c98949d1a1fff14d750fe5162213bb5b39e11'>commit</a><a href='/distro/kernel/diff/drivers/media/platform/exynos4-is/fimc-is-sensor.h?h=linux-6.6.y&amp;id=d10c98949d1a1fff14d750fe5162213bb5b39e11'>diff</a></td><td class='form'><form class='right' method='get' action='/distro/kernel/log/drivers/media/platform/exynos4-is/fimc-is-sensor.h'>
<input type='hidden' name='h' value='linux-6.6.y'/><input type='hidden' name='id' value='d10c98949d1a1fff14d750fe5162213bb5b39e11'/><select name='qt'>
<option value='grep'>log msg</option>
<option value='author'>author</option>
<option value='committer'>committer</option>
<option value='range'>range</option>
</select>
<input class='txt' type='search' size='10' name='q' value=''/>
<input type='submit' value='search'/>
</form>
</td></tr></table>
<div class='path'>path: <a href='/distro/kernel/log/?h=linux-6.6.y&amp;id=d10c98949d1a1fff14d750fe5162213bb5b39e11'>root</a>/<a href='/distro/kernel/log/drivers?h=linux-6.6.y&amp;id=d10c98949d1a1fff14d750fe5162213bb5b39e11'>drivers</a>/<a href='/distro/kernel/log/drivers/media?h=linux-6.6.y&amp;id=d10c98949d1a1fff14d750fe5162213bb5b39e11'>media</a>/<a href='/distro/kernel/log/drivers/media/platform?h=linux-6.6.y&amp;id=d10c98949d1a1fff14d750fe5162213bb5b39e11'>platform</a>/<a href='/distro/kernel/log/drivers/media/platform/exynos4-is?h=linux-6.6.y&amp;id=d10c98949d1a1fff14d750fe5162213bb5b39e11'>exynos4-is</a>/<a href='/distro/kernel/log/drivers/media/platform/exynos4-is/fimc-is-sensor.h?h=linux-6.6.y&amp;id=d10c98949d1a1fff14d750fe5162213bb5b39e11'>fimc-is-sensor.h</a></div><div class='content'><table class='list nowrap'><tr class='nohover'><th class='left'>Age</th><th class='left'>Commit message (<a href='/distro/kernel/log/drivers/media/platform/exynos4-is/fimc-is-sensor.h?h=linux-6.6.y&amp;id=d10c98949d1a1fff14d750fe5162213bb5b39e11&amp;showmsg=1'>Expand</a>)</th><th class='left'>Author</th></tr>
<tr><td><span title='2014-03-14 10:34:13 -0300'>2014-03-14</span></td><td><a href='/distro/kernel/commit/drivers/media/platform/exynos4-is/fimc-is-sensor.h?h=linux-6.6.y&amp;id=d265d9ac6c7c3201f0fea737cdf9c74e50415178'>[media] exynos4-is: Use external s5k6a3 sensor driver</a></td><td>Sylwester Nawrocki</td></tr>
der'><td><span title='2017-02-03 13:01:38 +0100'>2017-02-03</span></td><td class='logsubject'><a href='/distro/kernel/commit/drivers/staging/lustre/lnet/libcfs/workitem.c?h=linux-6.12.y&amp;id=69d3990cfdac8e1e5bd0ec89120cef2dbf889637'>staging: lustre: libcfs: fix error messages</a></td><td>Dmitry Eremin</td></tr>
<tr class='nohover-highlight'><td/><td colspan='3' class='logmsg'>
Don't treat unability to set CPU partition affinity as error.
Improve those warning messages.

Signed-off-by: Dmitry Eremin &lt;dmitry.eremin@intel.com&gt;
Intel-bug-id: https://jira.hpdd.intel.com/browse/LU-8703
Reviewed-on: https://review.whamcloud.com/23307
Reviewed-by: Patrick Farrell &lt;paf@cray.com&gt;
Reviewed-by: Doug Oucharek &lt;doug.s.oucharek@intel.com&gt;
Reviewed-by: Oleg Drokin &lt;oleg.drokin@intel.com&gt;
Signed-off-by: James Simmons &lt;jsimmons@infradead.org&gt;
Signed-off-by: Greg Kroah-Hartman &lt;gregkh@linuxfoundation.org&gt;


</td></tr>
<tr class='logheader'><td><span title='2016-11-18 08:47:32 +0100'>2016-11-18</span></td><td class='logsubject'><a href='/distro/kernel/commit/drivers/staging/lustre/lnet/libcfs/workitem.c?h=linux-6.12.y&amp;id=715475ae4224b188ed1639db4aa291414bbf968d'>staging: lustre: libcfs: white space cleanup</a></td><td>James Simmons</td></tr>
<tr class='nohover-highlight'><td/><td colspan='3' class='logmsg'>
Remove white space present for variable declarations
or initialization. Cleanup structs was strange
alignments due to white spacing.

Signed-off-by: James Simmons &lt;jsimmons@infradead.org&gt;
Signed-off-by: Greg Kroah-Hartman &lt;gregkh@linuxfoundation.org&gt;


</td></tr>
<tr class='logheader'><td><span title='2016-11-18 08:47:32 +0100'>2016-11-18</span></td><td class='logsubject'><a href='/distro/kernel/commit/drivers/staging/lustre/lnet/libcfs/workitem.c?h=linux-6.12.y&amp;id=6fc68ea5f38fb50ad22ae34777e0ab6111e3e749'>staging: lustre: libcfs: remove == 0 testing</a></td><td>James Simmons</td></tr>
<tr class='nohover-highlight'><td/><td colspan='3' class='logmsg'>
Testing == 0 is not kernel style so remove this
type of testing from libcfs.

Signed-off-by: James Simmons &lt;jsimmons@infradead.org&gt;
Signed-off-by: Greg Kroah-Hartman &lt;gregkh@linuxfoundation.org&gt;


</td></tr>
<tr class='logheader'><td><span title='2016-11-18 08:47:32 +0100'>2016-11-18</span></td><td class='logsubject'><a href='/distro/kernel/commit/drivers/staging/lustre/lnet/libcfs/workitem.c?h=linux-6.12.y&amp;id=d95531fc06431945a1e7a984a3146fb667fae87e'>staging: lustre: libcfs: remove != 0 testing</a></td><td>James Simmons</td></tr>
<tr class='nohover-highlight'><td/><td colspan='3' class='logmsg'>
Testing != 0 is not kernel style so remove this
type of testing from libcfs.

Signed-off-by: James Simmons &lt;jsimmons@infradead.org&gt;
Signed-off-by: Greg Kroah-Hartman &lt;gregkh@linuxfoundation.org&gt;


</td></tr>
<tr class='logheader'><td><span title='2016-11-18 08:47:31 +0100'>2016-11-18</span></td><td class='logsubject'><a href='/distro/kernel/commit/drivers/staging/lustre/lnet/libcfs/workitem.c?h=linux-6.12.y&amp;id=20d63a7adfd15dbf7a58fec4be8203345720bd6d'>staging: lustre: libcfs: fix aligment issue</a></td><td>James Simmons</td></tr>
<tr class='nohover-highlight'><td/><td colspan='3' class='logmsg'>
Make alignment match open parenthesis for
parameters to wait_event_interruptible_exclusive()
call.

Signed-off-by: James Simmons &lt;jsimmons@infradead.org&gt;
Signed-off-by: Greg Kroah-Hartman &lt;gregkh@linuxfoundation.org&gt;


</td></tr>
<tr class='logheader'><td><span title='2016-06-17 20:37:21 -0700'>2016-06-17</span></td><td class='logsubject'><a href='/distro/kernel/commit/drivers/staging/lustre/lnet/libcfs/workitem.c?h=linux-6.12.y&amp;id=6a5b99a46bedc2cfbba96dec6d255c4b90af9ff8'>staging/lustre: Replace sun.com GPLv2 URL with gnu.org one.</a></td><td>Oleg Drokin</td></tr>
<tr class='nohover-highlight'><td/><td colspan='3' class='logmsg'>
http://www.sun.com/software/products/lustre/docs/GPLv2.pdf is no
longer around, so replae it with (hopefully more permanent)
http://http://www.gnu.org/licenses/gpl-2.0.html

Signed-off-by: Oleg Drokin &lt;green@linuxhacker.ru&gt;
Reported-by: Xose Vazquez Perez &lt;xose.vazquez@gmail.com&gt;
Signed-off-by: Greg Kroah-Hartman &lt;gregkh@linuxfoundation.org&gt;


</td></tr>
<tr class='logheader'><td><span title='2016-06-17 20:37:21 -0700'>2016-06-17</span></td><td class='logsubject'><a href='/distro/kernel/commit/drivers/staging/lustre/lnet/libcfs/workitem.c?h=linux-6.12.y&amp;id=ed4df35478b84c8873b1d3f50f23eecacd22d859'>staging/lustre: Remove the "Please contact SUN for GPL" from headers</a></td><td>Oleg Drokin</td></tr>
<tr class='nohover-highlight'><td/><td colspan='3' class='logmsg'>
Since SUN is no longer around and there's no point in contacting them,
just remove that whole thing. Copy of GPL is available online anyway
(URLs to be updated in next patch).

This patch was generated with:
find drivers/staging/lustre -name "*.[ch]" -exec perl -0777 -i -pe 's/ \* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,\n \* CA 95054 USA or visit www.sun.com if you need additional information or\n \* have any questions.\n \*\n//igs' {} \;

Signed-off-by: Oleg Drokin &lt;green@linuxhacker.ru&gt;
Reported-by: Xose Vazquez Perez &lt;xose.vazquez@gmail.com&gt;
Signed-off-by: Greg Kroah-Hartman &lt;gregkh@linuxfoundation.org&gt;


</td></tr>
<tr class='logheader'><td><span title='2016-03-29 12:10:20 -0700'>2016-03-29</span></td><td class='logsubject'><a href='/distro/kernel/commit/drivers/staging/lustre/lnet/libcfs/workitem.c?h=linux-6.12.y&amp;id=5d145b1ad404e8cb260283d8a8b0747261698c73'>staging: lustre: libcfs: remove cfs_workitem_t typedefs</a></td><td>James Simmons</td></tr>
<tr class='nohover-highlight'><td/><td colspan='3' class='logmsg'>
Convert cfs_workitem_t to proper structure.

Signed-off-by: James Simmons &lt;uja.ornl@yahoo.com&gt;
Intel-bug-id: https://jira.hpdd.intel.com/browse/LU-6245
Reviewed-on: http://review.whamcloud.com/17202
Reviewed-by: John L. Hammond &lt;john.hammond@intel.com&gt;
Reviewed-by: Dmitry Eremin &lt;dmitry.eremin@intel.com&gt;
Reviewed-by: Oleg Drokin &lt;oleg.drokin@intel.com&gt;
Signed-off-by: Greg Kroah-Hartman &lt;gregkh@linuxfoundation.org&gt;


</td></tr>
<tr class='logheader'><td><span title='2016-03-11 22:09:09 -0800'>2016-03-11</span></td><td class='logsubject'><a href='/distro/kernel/commit/drivers/staging/lustre/lnet/libcfs/workitem.c?h=linux-6.12.y&amp;id=74cb7e3f65044ac6038874ffff9abde6d8c926a5'>staging: lustre: libcfs: Use list_for_each_entry_safe</a></td><td>Bhaktipriya Shridhar</td></tr>
<tr class='nohover-highlight'><td/><td colspan='3' class='logmsg'>
Doubly linked lists which are  iterated  using list_empty
and list_entry macros have been replaced with list_for_each_entry_safe
macro.
This makes the iteration simpler and more readable.

This patch replaces the while loop containing list_empty and list_entry
with list_for_each_entry_safe.

This was done with Coccinelle.

@@
expression E1;
identifier I1, I2;
type T;
iterator name list_for_each_entry_safe;
@@

T *I1;
+ T *tmp;
...
- while (list_empty(&amp;E1) == 0)
+ list_for_each_entry_safe (I1, tmp, &amp;E1, I2)
{
...when != T *I1;
- I1 = list_entry(E1.next, T, I2);
...
}

Signed-off-by: Bhaktipriya Shridhar &lt;bhaktipriya96@gmail.com&gt;
Signed-off-by: Greg Kroah-Hartman &lt;gregkh@linuxfoundation.org&gt;


</td></tr>
<tr class='logheader'><td><span title='2016-03-10 17:48:53 -0800'>2016-03-10</span></td><td class='logsubject'><a href='/distro/kernel/commit/drivers/staging/lustre/lnet/libcfs/workitem.c?h=linux-6.12.y&amp;id=71bf3883ae5723f7895226c4b5fafa452c0cd00f'>staging: lustre: move libcfs to lnet layer</a></td><td>James Simmons</td></tr>
<tr class='nohover-highlight'><td/><td colspan='3' class='logmsg'>
The lustre file system has a layered architecture with
libcfs as the lowest layer and LNet layered on top. Then
on top of LNet we run the lustre client. This patch moves
the libcfs module code out of lustre into the lnet tree.
This fits into the long term goal of eventually merging
libcfs into LNet.

Signed-off-by: James Simmons &lt;jsimmons@infradead.org&gt;
Signed-off-by: Greg Kroah-Hartman &lt;gregkh@linuxfoundation.org&gt;


</td></tr>