1b2441318SGreg Kroah-Hartman/* SPDX-License-Identifier: GPL-2.0 */
2d1b39d41SJosh Poimboeuf#ifndef __TOOLS_LINUX_LIST_H
3d1b39d41SJosh Poimboeuf#define __TOOLS_LINUX_LIST_H
4d1b39d41SJosh Poimboeuf
5d944c4eeSBorislav Petkov#include <linux/types.h>
6d1b39d41SJosh Poimboeuf#include <linux/poison.h>
7d1b39d41SJosh Poimboeuf#include <linux/kernel.h>
8d1b39d41SJosh Poimboeuf#include <linux/compiler.h>
9d1b39d41SJosh Poimboeuf
10d1b39d41SJosh Poimboeuf/*
11d1b39d41SJosh Poimboeuf * Simple doubly linked list implementation.
12d1b39d41SJosh Poimboeuf *
13d1b39d41SJosh Poimboeuf * Some of the internal functions ("__xxx") are useful when
14d1b39d41SJosh Poimboeuf * manipulating whole lists rather than single entries, as
15d1b39d41SJosh Poimboeuf * sometimes we already know the next/prev entries and we can
16d1b39d41SJosh Poimboeuf * generate better code by using them directly rather than
17d1b39d41SJosh Poimboeuf * using the generic single-entry routines.
18d1b39d41SJosh Poimboeuf */
19d1b39d41SJosh Poimboeuf
20d1b39d41SJosh Poimboeuf#define LIST_HEAD_INIT(name) { &(name), &(name) }
21d1b39d41SJosh Poimboeuf
22d1b39d41SJosh Poimboeuf#define LIST_HEAD(name) \
23d1b39d41SJosh Poimboeuf	struct list_head name = LIST_HEAD_INIT(name)
24d1b39d41SJosh Poimboeuf
25d1b39d41SJosh Poimboeufstatic inline void INIT_LIST_HEAD(struct list_head *list)
26d1b39d41SJosh Poimboeuf{
27d1b39d41SJosh Poimboeuf	list->next = list;
28d1b39d41SJosh Poimboeuf	list->prev = list;
29d1b39d41SJosh Poimboeuf}
30d1b39d41SJosh Poimboeuf
31d1b39d41SJosh Poimboeuf/*
32d1b39d41SJosh Poimboeuf * Insert a new entry between two known consecutive entries.
33d1b39d41SJosh Poimboeuf *
34d1b39d41SJosh Poimboeuf * This is only for internal list manipulation where we know
35d1b39d41SJosh Poimboeuf * the prev/next entries already!
36d1b39d41SJosh Poimboeuf */
37d1b39d41SJosh Poimboeuf#ifndef CONFIG_DEBUG_LIST
38d1b39d41SJosh Poimboeufstatic inline void __list_add(struct list_head *new,
39d1b39d41SJosh Poimboeuf			      struct list_head *prev,
40d1b39d41SJosh Poimboeuf			      struct list_head *next)
41d1b39d41SJosh Poimboeuf{
42d1b39d41SJosh Poimboeuf	next->prev = new;
43d1b39d41SJosh Poimboeuf	new->next = next;
44d1b39d41SJosh Poimboeuf	new->prev = prev;
45d1b39d41SJosh Poimboeuf	prev->next = new;
46d1b39d41SJosh Poimboeuf}
47d1b39d41SJosh Poimboeuf#else
48d1b39d41SJosh Poimboeufextern void __list_add(struct list_head *new,
49d1b39d41SJosh Poimboeuf			      struct list_head *prev,
50d1b39d41SJosh Poimboeuf			      struct list_head *next);
51d1b39d41SJosh Poimboeuf#endif
52d1b39d41SJosh Poimboeuf
53d1b39d41SJosh Poimboeuf/**
54d1b39d41SJosh Poimboeuf * list_add - add a new entry
55d1b39d41SJosh Poimboeuf * @new: new entry to be added
56d1b39d41SJosh Poimboeuf * @head: list head to add it after
57d1b39d41SJosh Poimboeuf *
58d1b39d41SJosh Poimboeuf * Insert a new entry after the specified head.
59d1b39d41SJosh Poimboeuf * This is good for implementing stacks.
60d1b39d41SJosh Poimboeuf */
61d1b39d41SJosh Poimboeufstatic inline void list_add(struct list_head *new, struct list_head *head)
62d1b39d41SJosh Poimboeuf{
63d1b39d41SJosh Poimboeuf	__list_add(new, head, head->next);
64d1b39d41SJosh Poimboeuf}
65d1b39d41SJosh Poimboeuf
66d1b39d41SJosh Poimboeuf
67d1b39d41SJosh Poimboeuf/**
68d1b39d41SJosh Poimboeuf * list_add_tail - add a new entry
69d1b39d41SJosh Poimboeuf * @new: new entry to be added
70d1b39d41SJosh Poimboeuf * @head: list head to add it before
71d1b39d41SJosh Poimboeuf *
72d1b39d41SJosh Poimboeuf * Insert a new entry before the specified head.
73d1b39d41SJosh Poimboeuf * This is useful for implementing queues.
74d1b39d41SJosh Poimboeuf */
75d1b39d41SJosh Poimboeufstatic inline void list_add_tail(struct list_head *new, struct list_head *head)
76d1b39d41SJosh Poimboeuf{
77d1b39d41SJosh Poimboeuf	__list_add(new, head->prev, head);
78d1b39d41SJosh Poimboeuf}
79d1b39d41SJosh Poimboeuf
80d1b39d41SJosh Poimboeuf/*
81d1b39d41SJosh Poimboeuf * Delete a list entry by making the prev/next entries
82d1b39d41SJosh Poimboeuf * point to each other.
83d1b39d41SJosh Poimboeuf *
84d1b39d41SJosh Poimboeuf * This is only for internal list manipulation where we know
85d1b39d41SJosh Poimboeuf * the prev/next entries already!
86d1b39d41SJosh Poimboeuf */
87d1b39d41SJosh Poimboeufstatic inline void __list_del(struct list_head * prev, struct list_head * next)
88d1b39d41SJosh Poimboeuf{
89d1b39d41SJosh Poimboeuf	next->prev = prev;
90d1b39d41SJosh Poimboeuf	WRITE_ONCE(prev->next, next);
91d1b39d41SJosh Poimboeuf}
92d1b39d41SJosh Poimboeuf
93d1b39d41SJosh Poimboeuf/**
94d1b39d41SJosh Poimboeuf * list_del - deletes entry from list.
95d1b39d41SJosh Poimboeuf * @entry: the element to delete from the list.
96d1b39d41SJosh Poimboeuf * Note: list_empty() on entry does not return true after this, the entry is
97d1b39d41SJosh Poimboeuf * in an undefined state.
98d1b39d41SJosh Poimboeuf */
99d1b39d41SJosh Poimboeuf#ifndef CONFIG_DEBUG_LIST
100d1b39d41SJosh Poimboeufstatic inline void __list_del_entry(struct list_head *entry)
101d1b39d41SJosh Poimboeuf{
102d1b39d41SJosh Poimboeuf	__list_del(entry->prev, entry->next);
103d1b39d41SJosh Poimboeuf}
104d1b39d41SJosh Poimboeuf
105d1b39d41SJosh Poimboeufstatic inline void list_del(struct list_head *entry)
106d1b39d41SJosh Poimboeuf{
107d1b39d41SJosh Poimboeuf	__list_del(entry->prev, entry->next);
108d1b39d41SJosh Poimboeuf	entry->next = LIST_POISON1;
109d1b39d41SJosh Poimboeuf	entry->prev = LIST_POISON2;
110d1b39d41SJosh Poimboeuf}
111d1b39d41SJosh Poimboeuf#else
112d1b39d41SJosh Poimboeufextern void __list_del_entry(struct list_head *entry);
113d1b39d41SJosh Poimboeufextern void list_del(struct list_head *entry);
114d1b39d41SJosh Poimboeuf#endif
115d1b39d41SJosh Poimboeuf
116d1b39d41SJosh Poimboeuf/**
117d1b39d41SJosh Poimboeuf * list_replace - replace old entry by new one
118d1b39d41SJosh Poimboeuf * @old : the element to be replaced
119d1b39d41SJosh Poimboeuf * @new : the new element to insert
120d1b39d41SJosh Poimboeuf *
121d1b39d41SJosh Poimboeuf * If @old was empty, it will be overwritten.
122d1b39d41SJosh Poimboeuf */
123d1b39d41SJosh Poimboeufstatic inline void list_replace(struct list_head *old,
124d1b39d41SJosh Poimboeuf				struct list_head *new)
125d1b39d41SJosh Poimboeuf{
126d1b39d41SJosh Poimboeuf	new->next = old->next;
127d1b39d41SJosh Poimboeuf	new->next->prev = new;
128d1b39d41SJosh Poimboeuf	new->prev = old->prev;
129d1b39d41SJosh Poimboeuf	new->prev->next = new;
130d1b39d41SJosh Poimboeuf}
131d1b39d41SJosh Poimboeuf
132d1b39d41SJosh Poimboeufstatic inline void list_replace_init(struct list_head *old,
133d1b39d41SJosh Poimboeuf					struct list_head *new)
134d1b39d41SJosh Poimboeuf{
135d1b39d41SJosh Poimboeuf	list_replace(old, new);
136d1b39d41SJosh Poimboeuf	INIT_LIST_HEAD(old);
137d1b39d41SJosh Poimboeuf}
138d1b39d41SJosh Poimboeuf
139d1b39d41SJosh Poimboeuf/**
140d1b39d41SJosh Poimboeuf * list_del_init - deletes entry from list and reinitialize it.
141d1b39d41SJosh Poimboeuf * @entry: the element to delete from the list.
142d1b39d41SJosh Poimboeuf */
143d1b39d41SJosh Poimboeufstatic inline void list_del_init(struct list_head *entry)
144d1b39d41SJosh Poimboeuf{
145d1b39d41SJosh Poimboeuf	__list_del_entry(entry);
146d1b39d41SJosh Poimboeuf	INIT_LIST_HEAD(entry);
147d1b39d41SJosh Poimboeuf}
148d1b39d41SJosh Poimboeuf
149d1b39d41SJosh Poimboeuf/**
150d1b39d41SJosh Poimboeuf * list_move - delete from one list and add as another's head
151d1b39d41SJosh Poimboeuf * @list: the entry to move
152d1b39d41SJosh Poimboeuf * @head: the head that will precede our entry
153d1b39d41SJosh Poimboeuf */
154d1b39d41SJosh Poimboeufstatic inline void list_move(struct list_head *list, struct list_head *head)
155d1b39d41SJosh Poimboeuf{
156d1b39d41SJosh Poimboeuf	__list_del_entry(list);
157d1b39d41SJosh Poimboeuf	list_add(list, head);
158d1b39d41SJosh Poimboeuf}
159d1b39d41SJosh Poimboeuf
160d1b39d41SJosh Poimboeuf/**
161d1b39d41SJosh Poimboeuf * list_move_tail - delete from one list and add as another's tail
162d1b39d41SJosh Poimboeuf * @list: the entry to move
163d1b39d41SJosh Poimboeuf * @head: the head that will follow our entry
164d1b39d41SJosh Poimboeuf */
165d1b39d41SJosh Poimboeufstatic inline void list_move_tail(struct list_head *list,
166d1b39d41SJosh Poimboeuf				  struct list_head *head)
167d1b39d41SJosh Poimboeuf{
168d1b39d41SJosh Poimboeuf	__list_del_entry(list);
169d1b39d41SJosh Poimboeuf	list_add_tail(list, head);
170d1b39d41SJosh Poimboeuf}
171d1b39d41SJosh Poimboeuf
172d1b39d41SJosh Poimboeuf/**
173d1b39d41SJosh Poimboeuf * list_is_last - tests whether @list is the last entry in list @head
174d1b39d41SJosh Poimboeuf * @list: the entry to test
175d1b39d41SJosh Poimboeuf * @head: the head of the list
176d1b39d41SJosh Poimboeuf */
177d1b39d41SJosh Poimboeufstatic inline int list_is_last(const struct list_head *list,
178d1b39d41SJosh Poimboeuf				const struct list_head *head)
179d1b39d41SJosh Poimboeuf{
180d1b39d41SJosh Poimboeuf	return list->next == head;
181d1b39d41SJosh Poimboeuf}
182d1b39d41SJosh Poimboeuf
183d1b39d41SJosh Poimboeuf/**
184d1b39d41SJosh Poimboeuf * list_empty - tests whether a list is empty
185d1b39d41SJosh Poimboeuf * @head: the list to test.
186d1b39d41SJosh Poimboeuf */
187d1b39d41SJosh Poimboeufstatic inline int list_empty(const struct list_head *head)
188d1b39d41SJosh Poimboeuf{
189d1b39d41SJosh Poimboeuf	return head->next == head;
190d1b39d41SJosh Poimboeuf}
191d1b39d41SJosh Poimboeuf
192d1b39d41SJosh Poimboeuf/**
193d1b39d41SJosh Poimboeuf * list_empty_careful - tests whether a list is empty and not being modified
194d1b39d41SJosh Poimboeuf * @head: the list to test
195d1b39d41SJosh Poimboeuf *
196d1b39d41SJosh Poimboeuf * Description:
197d1b39d41SJosh Poimboeuf * tests whether a list is empty _and_ checks that no other CPU might be
198d1b39d41SJosh Poimboeuf * in the process of modifying either member (next or prev)
199d1b39d41SJosh Poimboeuf *
200d1b39d41SJosh Poimboeuf * NOTE: using list_empty_careful() without synchronization
201d1b39d41SJosh Poimboeuf * can only be safe if the only activity that can happen
202d1b39d41SJosh Poimboeuf * to the list entry is list_del_init(). Eg. it cannot be used
203d1b39d41SJosh Poimboeuf * if another CPU could re-list_add() it.
204d1b39d41SJosh Poimboeuf */
205d1b39d41SJosh Poimboeufstatic inline int list_empty_careful(const struct list_head *head)
206d1b39d41SJosh Poimboeuf{
207d1b39d41SJosh Poimboeuf	struct list_head *next = head->next;
208d1b39d41SJosh Poimboeuf	return (next == head) && (next == head->prev);
209d1b39d41SJosh Poimboeuf}
210d1b39d41SJosh Poimboeuf
211d1b39d41SJosh Poimboeuf/**
212d1b39d41SJosh Poimboeuf * list_rotate_left - rotate the list to the left
213d1b39d41SJosh Poimboeuf * @head: the head of the list
214d1b39d41SJosh Poimboeuf */
215d1b39d41SJosh Poimboeufstatic inline void list_rotate_left(struct list_head *head)
216d1b39d41SJosh Poimboeuf{
217d1b39d41SJosh Poimboeuf	struct list_head *first;
218d1b39d41SJosh Poimboeuf
219d1b39d41SJosh Poimboeuf	if (!list_empty(head)) {
220d1b39d41SJosh Poimboeuf		first = head->next;
221d1b39d41SJosh Poimboeuf		list_move_tail(first, head);
222d1b39d41SJosh Poimboeuf	}
223d1b39d41SJosh Poimboeuf}
224d1b39d41SJosh Poimboeuf
225d1b39d41SJosh Poimboeuf/**
226d1b39d41SJosh Poimboeuf * list_is_singular - tests whether a list has just one entry.
227d1b39d41SJosh Poimboeuf * @head: the list to test.
228d1b39d41SJosh Poimboeuf */
229d1b39d41SJosh Poimboeufstatic inline int list_is_singular(const struct list_head *head)
230d1b39d41SJosh Poimboeuf{
231d1b39d41SJosh Poimboeuf	return !list_empty(head) && (head->next == head->prev);
232d1b39d41SJosh Poimboeuf}
233d1b39d41SJosh Poimboeuf
234d1b39d41SJosh Poimboeufstatic inline void __list_cut_position(struct list_head *list,
235d1b39d41SJosh Poimboeuf		struct list_head *head, struct list_head *entry)
236d1b39d41SJosh Poimboeuf{
237d1b39d41SJosh Poimboeuf	struct list_head *new_first = entry->next;
238d1b39d41SJosh Poimboeuf	list->next = head->next;
239d1b39d41SJosh Poimboeuf	list->next->prev = list;
240d1b39d41SJosh Poimboeuf	list->prev = entry;
241d1b39d41SJosh Poimboeuf	entry->next = list;
242d1b39d41SJosh Poimboeuf	head->next = new_first;
243d1b39d41SJosh Poimboeuf	new_first->prev = head;
244d1b39d41SJosh Poimboeuf}
245d1b39d41SJosh Poimboeuf
246d1b39d41SJosh Poimboeuf/**
247d1b39d41SJosh Poimboeuf * list_cut_position - cut a list into two
248d1b39d41SJosh Poimboeuf * @list: a new list to add all removed entries
249d1b39d41SJosh Poimboeuf * @head: a list with entries
250d1b39d41SJosh Poimboeuf * @entry: an entry within head, could be the head itself
251d1b39d41SJosh Poimboeuf *	and if so we won't cut the list
252d1b39d41SJosh Poimboeuf *
253d1b39d41SJosh Poimboeuf * This helper moves the initial part of @head, up to and
254d1b39d41SJosh Poimboeuf * including @entry, from @head to @list. You should
255d1b39d41SJosh Poimboeuf * pass on @entry an element you know is on @head. @list
256d1b39d41SJosh Poimboeuf * should be an empty list or a list you do not care about
257d1b39d41SJosh Poimboeuf * losing its data.
258d1b39d41SJosh Poimboeuf *
259d1b39d41SJosh Poimboeuf */
260d1b39d41SJosh Poimboeufstatic inline void list_cut_position(struct list_head *list,