1aded9cb8SThomas Gleixner /* SPDX-License-Identifier: GPL-2.0-or-later */
277ba89c5SIngo Molnar /*
377ba89c5SIngo Molnar * Descending-priority-sorted double-linked list
477ba89c5SIngo Molnar *
577ba89c5SIngo Molnar * (C) 2002-2003 Intel Corp
677ba89c5SIngo Molnar * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
777ba89c5SIngo Molnar *
877ba89c5SIngo Molnar * 2001-2005 (c) MontaVista Software, Inc.
977ba89c5SIngo Molnar * Daniel Walker <dwalker@mvista.com>
1077ba89c5SIngo Molnar *
1177ba89c5SIngo Molnar * (C) 2005 Thomas Gleixner <tglx@linutronix.de>
1277ba89c5SIngo Molnar *
1377ba89c5SIngo Molnar * Simplifications of the original code by
1477ba89c5SIngo Molnar * Oleg Nesterov <oleg@tv-sign.ru>
1577ba89c5SIngo Molnar *
1677ba89c5SIngo Molnar * Based on simple lists (include/linux/list.h).
1777ba89c5SIngo Molnar *
1877ba89c5SIngo Molnar * This is a priority-sorted list of nodes; each node has a
1977ba89c5SIngo Molnar * priority from INT_MIN (highest) to INT_MAX (lowest).
2077ba89c5SIngo Molnar *
2177ba89c5SIngo Molnar * Addition is O(K), removal is O(1), change of priority of a node is
2277ba89c5SIngo Molnar * O(K) and K is the number of RT priority levels used in the system.
2377ba89c5SIngo Molnar * (1 <= K <= 99)
2477ba89c5SIngo Molnar *
2577ba89c5SIngo Molnar * This list is really a list of lists:
2677ba89c5SIngo Molnar *
2777ba89c5SIngo Molnar * - The tier 1 list is the prio_list, different priority nodes.
2877ba89c5SIngo Molnar *
2977ba89c5SIngo Molnar * - The tier 2 list is the node_list, serialized nodes.
3077ba89c5SIngo Molnar *
3177ba89c5SIngo Molnar * Simple ASCII art explanation:
3277ba89c5SIngo Molnar *
33bf6a9b83SLai Jiangshan * pl:prio_list (only for plist_node)
34bf6a9b83SLai Jiangshan * nl:node_list
35bf6a9b83SLai Jiangshan * HEAD| NODE(S)
36bf6a9b83SLai Jiangshan * |
37bf6a9b83SLai Jiangshan * ||------------------------------------|
38bf6a9b83SLai Jiangshan * ||->|pl|<->|pl|<--------------->|pl|<-|
39bf6a9b83SLai Jiangshan * | |10| |21| |21| |21| |40| (prio)
40bf6a9b83SLai Jiangshan * | | | | | | | | | | |
41bf6a9b83SLai Jiangshan * | | | | | | | | | | |
42bf6a9b83SLai Jiangshan * |->|nl|<->|nl|<->|nl|<->|nl|<->|nl|<->|nl|<-|
43bf6a9b83SLai Jiangshan * |-------------------------------------------|
4477ba89c5SIngo Molnar *
4577ba89c5SIngo Molnar * The nodes on the prio_list list are sorted by priority to simplify
4677ba89c5SIngo Molnar * the insertion of new nodes. There are no nodes with duplicate
4777ba89c5SIngo Molnar * priorites on the list.
4877ba89c5SIngo Molnar *
499ca94d7cSJohn Kacur * The nodes on the node_list are ordered by priority and can contain
5077ba89c5SIngo Molnar * entries which have the same priority. Those entries are ordered
5177ba89c5SIngo Molnar * FIFO
5277ba89c5SIngo Molnar *
5377ba89c5SIngo Molnar * Addition means: look for the prio_list node in the prio_list
5477ba89c5SIngo Molnar * for the priority of the node and insert it before the node_list
5577ba89c5SIngo Molnar * entry of the next prio_list node. If it is the first node of
5677ba89c5SIngo Molnar * that priority, add it to the prio_list in the right position and
5777ba89c5SIngo Molnar * insert it into the serialized node_list list
5877ba89c5SIngo Molnar *
5977ba89c5SIngo Molnar * Removal means remove it from the node_list and remove it from
6077ba89c5SIngo Molnar * the prio_list if the node_list list_head is non empty. In case
6177ba89c5SIngo Molnar * of removal from the prio_list it must be checked whether other
6277ba89c5SIngo Molnar * entries of the same priority are on the list or not. If there
6377ba89c5SIngo Molnar * is another entry of the same priority then this entry has to
6477ba89c5SIngo Molnar * replace the removed entry on the prio_list. If the entry which
6577ba89c5SIngo Molnar * is removed is the only entry of this priority then a simple
6677ba89c5SIngo Molnar * remove from both list is sufficient.
6777ba89c5SIngo Molnar *
6877ba89c5SIngo Molnar * INT_MIN is the highest priority, 0 is the medium highest, INT_MAX
6977ba89c5SIngo Molnar * is lowest priority.
7077ba89c5SIngo Molnar *
7177ba89c5SIngo Molnar * No locking is done, up to the caller.
7277ba89c5SIngo Molnar */
7377ba89c5SIngo Molnar #ifndef _LINUX_PLIST_H_
7477ba89c5SIngo Molnar #define _LINUX_PLIST_H_
7577ba89c5SIngo Molnar
76*c540f959SAndy Shevchenko #include <linux/container_of.h>
7777ba89c5SIngo Molnar #include <linux/list.h>
78*c540f959SAndy Shevchenko #include <linux/types.h>
79*c540f959SAndy Shevchenko
80*c540f959SAndy Shevchenko #include <asm/bug.h>
8177ba89c5SIngo Molnar
8277ba89c5SIngo Molnar struct plist_head {
8377ba89c5SIngo Molnar struct list_head node_list;
8477ba89c5SIngo Molnar };
8577ba89c5SIngo Molnar
8677ba89c5SIngo Molnar struct plist_node {
8777ba89c5SIngo Molnar int prio;
88bf6a9b83SLai Jiangshan struct list_head prio_list;
89bf6a9b83SLai Jiangshan struct list_head node_list;
9077ba89c5SIngo Molnar };
9177ba89c5SIngo Molnar
9277ba89c5SIngo Molnar /**
9311265420SRandy Dunlap * PLIST_HEAD_INIT - static struct plist_head initializer
9477ba89c5SIngo Molnar * @head: struct plist_head variable name
9577ba89c5SIngo Molnar */
96732375c6SDima Zavin #define PLIST_HEAD_INIT(head) \
9777ba89c5SIngo Molnar { \
98732375c6SDima Zavin .node_list = LIST_HEAD_INIT((head).node_list) \
99a2672459SThomas Gleixner }
100a2672459SThomas Gleixner
101a2672459SThomas Gleixner /**
102fd16618eSDan Streetman * PLIST_HEAD - declare and init plist_head
103fd16618eSDan Streetman * @head: name for struct plist_head variable
104fd16618eSDan Streetman */
105fd16618eSDan Streetman #define PLIST_HEAD(head) \
106fd16618eSDan Streetman struct plist_head head = PLIST_HEAD_INIT(head)
107fd16618eSDan Streetman
108fd16618eSDan Streetman /**
10911265420SRandy Dunlap * PLIST_NODE_INIT - static struct plist_node initializer
11077ba89c5SIngo Molnar * @node: struct plist_node variable name
11177ba89c5SIngo Molnar * @__prio: initial node priority
11277ba89c5SIngo Molnar */
11377ba89c5SIngo Molnar #define PLIST_NODE_INIT(node, __prio) \
11477ba89c5SIngo Molnar { \
11577ba89c5SIngo Molnar .prio = (__prio), \
116bf6a9b83SLai Jiangshan .prio_list = LIST_HEAD_INIT((node).prio_list), \
117bf6a9b83SLai Jiangshan .node_list = LIST_HEAD_INIT((node).node_list), \
11877ba89c5SIngo Molnar }
11977ba89c5SIngo Molnar
12077ba89c5SIngo Molnar /**
12177ba89c5SIngo Molnar * plist_head_init - dynamic struct plist_head initializer
12277ba89c5SIngo Molnar * @head: &struct plist_head pointer
12377ba89c5SIngo Molnar */
12477ba89c5SIngo Molnar static inline void
plist_head_init(struct plist_head * head)125732375c6SDima Zavin plist_head_init(struct plist_head *head)
12677ba89c5SIngo Molnar {
12777ba89c5SIngo Molnar INIT_LIST_HEAD(&head->node_list);
12877ba89c5SIngo Molnar }
12977ba89c5SIngo Molnar
13077ba89c5SIngo Molnar /**
13177ba89c5SIngo Molnar * plist_node_init - Dynamic struct plist_node initializer
13277ba89c5SIngo Molnar * @node: &struct plist_node pointer
13377ba89c5SIngo Molnar * @prio: initial node priority
13477ba89c5SIngo Molnar */
plist_node_init(struct plist_node * node,int prio)13577ba89c5SIngo Molnar static inline void plist_node_init(struct plist_node *node, int prio)
13677ba89c5SIngo Molnar {
13777ba89c5SIngo Molnar node->prio = prio;
138bf6a9b83SLai Jiangshan INIT_LIST_HEAD(&node->prio_list);
139bf6a9b83SLai Jiangshan INIT_LIST_HEAD(&node->node_list);
14077ba89c5SIngo Molnar }
14177ba89c5SIngo Molnar
14277ba89c5SIngo Molnar extern void plist_add(struct plist_node *node, struct plist_head *head);
14377ba89c5SIngo Molnar extern void plist_del(struct plist_node *node, struct plist_head *head);
14477ba89c5SIngo Molnar
145a75f232cSDan Streetman extern void plist_requeue(struct plist_node *node, struct plist_head *head);
146a75f232cSDan Streetman
14777ba89c5SIngo Molnar /**
14877ba89c5SIngo Molnar * plist_for_each - iterate over the plist
14911265420SRandy Dunlap * @pos: the type * to use as a loop counter
15011265420SRandy Dunlap * @head: the head for your list
15177ba89c5SIngo Molnar */
15277ba89c5SIngo Molnar #define plist_for_each(pos, head) \
153bf6a9b83SLai Jiangshan list_for_each_entry(pos, &(head)->node_list, node_list)
15477ba89c5SIngo Molnar
15577ba89c5SIngo Molnar /**
156fd16618eSDan Streetman * plist_for_each_continue - continue iteration over the plist
157fd16618eSDan Streetman * @pos: the type * to use as a loop cursor
158fd16618eSDan Streetman * @head: the head for your list
159fd16618eSDan Streetman *
160fd16618eSDan Streetman * Continue to iterate over plist, continuing after the current position.
161fd16618eSDan Streetman */
162fd16618eSDan Streetman #define plist_for_each_continue(pos, head) \
163fd16618eSDan Streetman list_for_each_entry_continue(pos, &(head)->node_list, node_list)
164fd16618eSDan Streetman
165fd16618eSDan Streetman /**
16611265420SRandy Dunlap * plist_for_each_safe - iterate safely over a plist of given type
16711265420SRandy Dunlap * @pos: the type * to use as a loop counter
16811265420SRandy Dunlap * @n: another type * to use as temporary storage
16911265420SRandy Dunlap * @head: the head for your list
17077ba89c5SIngo Molnar *
17111265420SRandy Dunlap * Iterate over a plist of given type, safe against removal of list entry.
17277ba89c5SIngo Molnar */
17377ba89c5SIngo Molnar #define plist_for_each_safe(pos, n, head) \
174bf6a9b83SLai Jiangshan list_for_each_entry_safe(pos, n, &(head)->node_list, node_list)
17577ba89c5SIngo Molnar
17677ba89c5SIngo Molnar /**
17777ba89c5SIngo Molnar * plist_for_each_entry - iterate over list of given type
17811265420SRandy Dunlap * @pos: the type * to use as a loop counter
17911265420SRandy Dunlap * @head: the head for your list
1803943f42cSAndrey Utkin * @mem: the name of the list_head within the struct
18177ba89c5SIngo Molnar */
18277ba89c5SIngo Molnar #define plist_for_each_entry(pos, head, mem) \
183bf6a9b83SLai Jiangshan list_for_each_entry(pos, &(head)->node_list, mem.node_list)
18477ba89c5SIngo Molnar
18577ba89c5SIngo Molnar /**
186fd16618eSDan Streetman * plist_for_each_entry_continue - continue iteration over list of given type
187fd16618eSDan Streetman * @pos: the type * to use as a loop cursor
188fd16618eSDan Streetman * @head: the head for your list
1893943f42cSAndrey Utkin * @m: the name of the list_head within the struct
190fd16618eSDan Streetman *
191fd16618eSDan Streetman * Continue to iterate over list of given type, continuing after
192fd16618eSDan Streetman * the current position.
193fd16618eSDan Streetman */
194fd16618eSDan Streetman #define plist_for_each_entry_continue(pos, head, m) \
195fd16618eSDan Streetman list_for_each_entry_continue(pos, &(head)->node_list, m.node_list)
196fd16618eSDan Streetman
197fd16618eSDan Streetman /**
19811265420SRandy Dunlap * plist_for_each_entry_safe - iterate safely over list of given type
19911265420SRandy Dunlap * @pos: the type * to use as a loop counter
20077ba89c5SIngo Molnar * @n: another type * to use as temporary storage
20111265420SRandy Dunlap * @head: the head for your list
2023943f42cSAndrey Utkin * @m: the name of the list_head within the struct
20311265420SRandy Dunlap *
20411265420SRandy Dunlap * Iterate over list of given type, safe against removal of list entry.
20577ba89c5SIngo Molnar */
20677ba89c5SIngo Molnar #define plist_for_each_entry_safe(pos, n, head, m) \
207bf6a9b83SLai Jiangshan list_for_each_entry_safe(pos, n, &(head)->node_list, m.node_list)
20877ba89c5SIngo Molnar
20977ba89c5SIngo Molnar /**
21077ba89c5SIngo Molnar * plist_head_empty - return !0 if a plist_head is empty
21177ba89c5SIngo Molnar * @head: &struct plist_head pointer
21277ba89c5SIngo Molnar */
plist_head_empty(const struct plist_head * head)21377ba89c5SIngo Molnar static inline int plist_head_empty(const struct plist_head *head)
21477ba89c5SIngo Molnar {
21577ba89c5SIngo Molnar return list_empty(&head->node_list);
21677ba89c5SIngo Molnar }
21777ba89c5SIngo Molnar
21877ba89c5SIngo Molnar /**
21977ba89c5SIngo Molnar * plist_node_empty - return !0 if plist_node is not on a list
22077ba89c5SIngo Molnar * @node: &struct plist_node pointer
22177ba89c5SIngo Molnar */
plist_node_empty(const struct plist_node * node)22277ba89c5SIngo Molnar static inline int plist_node_empty(const struct plist_node *node)
22377ba89c5SIngo Molnar {
224bf6a9b83SLai Jiangshan return list_empty(&node->node_list);
22577ba89c5SIngo Molnar }
22677ba89c5SIngo Molnar
22777ba89c5SIngo Molnar /* All functions below assume the plist_head is not empty. */
22877ba89c5SIngo Molnar
22977ba89c5SIngo Molnar /**
23077ba89c5SIngo Molnar * plist_first_entry - get the struct for the first entry
23111265420SRandy Dunlap * @head: the &struct plist_head pointer
23211265420SRandy Dunlap * @type: the type of the struct this is embedded in
2333943f42cSAndrey Utkin * @member: the name of the list_head within the struct
23477ba89c5SIngo Molnar */
2358e18faeaSDavidlohr Bueso #ifdef CONFIG_DEBUG_PLIST
23677ba89c5SIngo Molnar # define plist_first_entry(head, type, member) \
23777ba89c5SIngo Molnar ({ \
23877ba89c5SIngo Molnar WARN_ON(plist_head_empty(head)); \
23977ba89c5SIngo Molnar container_of(plist_first(head), type, member); \
24077ba89c5SIngo Molnar })
24177ba89c5SIngo Molnar #else
24277ba89c5SIngo Molnar # define plist_first_entry(head, type, member) \
24377ba89c5SIngo Molnar container_of(plist_first(head), type, member)
24477ba89c5SIngo Molnar #endif
24577ba89c5SIngo Molnar
24677ba89c5SIngo Molnar /**
24712e4d0ccSJames Bottomley * plist_last_entry - get the struct for the last entry
24812e4d0ccSJames Bottomley * @head: the &struct plist_head pointer
24912e4d0ccSJames Bottomley * @type: the type of the struct this is embedded in
2503943f42cSAndrey Utkin * @member: the name of the list_head within the struct
25112e4d0ccSJames Bottomley */
2528e18faeaSDavidlohr Bueso #ifdef CONFIG_DEBUG_PLIST
25312e4d0ccSJames Bottomley # define plist_last_entry(head, type, member) \
25412e4d0ccSJames Bottomley ({ \
25512e4d0ccSJames Bottomley WARN_ON(plist_head_empty(head)); \
25612e4d0ccSJames Bottomley container_of(plist_last(head), type, member); \
25712e4d0ccSJames Bottomley })
25812e4d0ccSJames Bottomley #else
25912e4d0ccSJames Bottomley # define plist_last_entry(head, type, member) \
26012e4d0ccSJames Bottomley container_of(plist_last(head), type, member)
26112e4d0ccSJames Bottomley #endif
26212e4d0ccSJames Bottomley
26312e4d0ccSJames Bottomley /**
264fd16618eSDan Streetman * plist_next - get the next entry in list
265fd16618eSDan Streetman * @pos: the type * to cursor
266fd16618eSDan Streetman */
267fd16618eSDan Streetman #define plist_next(pos) \
268fd16618eSDan Streetman list_next_entry(pos, node_list)
269fd16618eSDan Streetman
270fd16618eSDan Streetman /**
271fd16618eSDan Streetman * plist_prev - get the prev entry in list
272fd16618eSDan Streetman * @pos: the type * to cursor
273fd16618eSDan Streetman */
274fd16618eSDan Streetman #define plist_prev(pos) \
275fd16618eSDan Streetman list_prev_entry(pos, node_list)
276fd16618eSDan Streetman
277fd16618eSDan Streetman /**
27877ba89c5SIngo Molnar * plist_first - return the first node (and thus, highest priority)
27977ba89c5SIngo Molnar * @head: the &struct plist_head pointer
28077ba89c5SIngo Molnar *
28177ba89c5SIngo Molnar * Assumes the plist is _not_ empty.
28277ba89c5SIngo Molnar */
plist_first(const struct plist_head * head)28377ba89c5SIngo Molnar static inline struct plist_node *plist_first(const struct plist_head *head)
28477ba89c5SIngo Molnar {
28577ba89c5SIngo Molnar return list_entry(head->node_list.next,
286bf6a9b83SLai Jiangshan struct plist_node, node_list);
28777ba89c5SIngo Molnar }
28877ba89c5SIngo Molnar
28912e4d0ccSJames Bottomley /**
29012e4d0ccSJames Bottomley * plist_last - return the last node (and thus, lowest priority)
29112e4d0ccSJames Bottomley * @head: the &struct plist_head pointer
29212e4d0ccSJames Bottomley *
29312e4d0ccSJames Bottomley * Assumes the plist is _not_ empty.
29412e4d0ccSJames Bottomley */
plist_last(const struct plist_head * head)29512e4d0ccSJames Bottomley static inline struct plist_node *plist_last(const struct plist_head *head)
29612e4d0ccSJames Bottomley {
29712e4d0ccSJames Bottomley return list_entry(head->node_list.prev,
298bf6a9b83SLai Jiangshan struct plist_node, node_list);
29912e4d0ccSJames Bottomley }
30012e4d0ccSJames Bottomley
30177ba89c5SIngo Molnar #endif
302