1 /*
2 * Some simple implementation of lists similar to the one used in the kernel.
3 *
4 * Copyright (c) 2016-2021 The strace developers.
5 * All rights reserved.
6 *
7 * SPDX-License-Identifier: LGPL-2.1-or-later
8 */
9
10 #ifndef STRACE_LIST_H
11 # define STRACE_LIST_H
12
13 /*
14 * struct list_item and related macros and functions provide an interface
15 * for manipulating and iterating linked lists. In order to have list
16 * associated with its payload, struct list_item has to be embedded into
17 * a structure type representing payload, and (optionally) an additional
18 * struct list_item should be added somewhere as a starting point for list
19 * iteration (creating a list with a designated head). A situation where
20 * no designated head exists, and each embedded struct list_head is considered
21 * a head (i.e. starting point for list iteration), is also possible.
22 *
23 * List head has to be initialised with list_init() call. Statically allocated
24 * list heads can also be defined with an EMPTY_LIST() macro.
25 *
26 * In order to get a pointer to list item from a struct list_item, list_elem
27 * macro is used.
28 *
29 * When a designated head is used, list_head() and list_tail() can be used
30 * for getting pointer to the first and the last list item, respectively.
31 *
32 * list_next() and list_prev() macros can be used for obtaining pointers
33 * to the next and the previous items in the list, respectively. Note that
34 * they do not perform additional checks for the validity of these pointers,
35 * so they have to be guarded with respective list_head/list_tail checks in case
36 * of lists with designated heads (where the list's head is not embedded within
37 * a list item.
38 *
39 * list_{insert,append,remove,remove_tail,remove_head,replace} provide some
40 * basic means of list manipulation.
41 *
42 * list_foreach() and list_foreach_safe() are wrapper macros for simplifying
43 * iteration over a list, with the latter having an additional argument
44 * for storing temporary pointer, thus allowing list manipulations during
45 * its iteration.
46 *
47 * A simple example:
48 *
49 * struct my_struct {
50 * int a;
51 * struct list_item l1;
52 * struct list_item l2;
53 * };
54 *
55 * EMPTY_LIST(list_1); <--- Defining a designated head for list
56 *
57 * struct my_struct *item =
58 * calloc(1, sizeof(*item));
59 * list_init(&item->l2); <--- Initialising structure field that
60 * is used for lists without designated
61 * head.
62 * list_insert(&list_1, &item->l1); <--- Inserting an item into the list
63 *
64 * item = calloc(1, sizeof(*item));
65 * list_init(&item->l2);
66 *
67 * list_append(&(list_head(list_1, struct my_struct, l1)->l2), &item->l2);
68 *
69 * struct my_struct *cur = item; <--- Iteration over a headless list
70 * do {
71 * printf("%d\n", cur->a);
72 * } while ((cur = list_next(&cur, l2)) != item);
73 *
74 * struct my_struct *i;
75 * list_foreach(i, list_1, l1) { <--- Iteration over list_1 without list
76 * printf("%d\n", i->a); modification
77 * }
78 *
79 * struct my_struct *tmp; <--- Iteration with modification
80 * list_foreach_safe(i, list_1, l1, tmp) {
81 * list_remove(&i->l1);
82 * free(i);
83 * }
84 *
85 * See also:
86 * "Linux kernel design patterns - part 2", section "Linked Lists"
87 * https://lwn.net/Articles/336255/
88 */
89
90 # include "macros.h"
91
92 struct list_item {
93 struct list_item *prev;
94 struct list_item *next;
95 };
96
97 /**
98 * Define an empty list head.
99 *
100 * @param l_ List head variable name.
101 */
102 # define EMPTY_LIST(l_) struct list_item l_ = { &l_, &l_ }
103
104 /** Initialise an empty list. */
105 static inline void
106 list_init(struct list_item *l)
107 {
108 l->prev = l;
109 l->next = l;
110 }
111
112 /** Check whether list is empty. */
113 static inline bool
114 list_is_empty(const struct list_item *l)
115 {
116 return ((l->next == l) && (l->prev == l))
117 /*
118 * XXX This could be the case when struct list_item hasn't been
119 * initialised at all; we should probably also call some
120 * errror_func_msg() in that case, as it looks like sloppy
121 * programming.
122 */
123 || (!l->next && !l->prev);
124 }
125
126 /**
127 * Convert a pointer to a struct list_item to a pointer to a list item.
128 *
129 * @param var Pointer to struct list_item.
130 * @param type Type of the list's item.
131 * @param field Name of the field that holds the respective struct list_item.
132 */
133 # define list_elem(var, type, field) containerof((var), type, field)
134
135 /**
136 * Get the first element in a list.
137 *
138 * @param head Pointer to the list's head.
139 * @param type Type of the list's item.
140 * @param field Name of the field that holds the respective struct list_item.
141 */
142 # define list_head(head, type, field) \
143 (list_is_empty(head) ? NULL : list_elem((head)->next, type, field))
144 /**
145 * Get the last element in a list.
146 *
147 * @param head Pointer to the list's head.
148 * @param type Type of the list's item.
149 * @param field Name of the field that holds the respective struct list_item.
150 */
151 # define list_tail(head, type, field) \
152 (list_is_empty(head) ? NULL : list_elem((head)->prev, type, field))
153
154 /**
155 * Get the next element in a list.
156 *
157 * @param var Pointer to a list item.
158 * @param field Name of the field that holds the respective struct list_item.
159 */
160 # define list_next(var, field) \
161 list_elem((var)->field.next, typeof(*(var)), field)
162 /**
163 * Get the previous element in a list.
164 *
165 * @param var Pointer to a list item.
166 * @param field Name of the field that holds the respective struct list_item.
167 */
168 # define list_prev(var, field) \
169 list_elem((var)->field.prev, typeof(*(var)), field)
170
171 /**
172 * Insert an item into a list. The item is placed as the next list item
173 * to the head.
174 */
175 static inline void
176 list_insert(struct list_item *head, struct list_item *item)
177 {
178 item->next = head->next;
179 item->prev = head;
180 head->next->prev = item;
181 head->next = item;
182 }
183
184 /**
185 * Insert an item into a list. The item is placed as the previous list item
186 * to the head.
187 */
188 static inline void
189 list_append(struct list_item *head, struct list_item *item)
190 {
191 item->next = head;
192 item->prev = head->prev;
193 head->prev->next = item;
194 head->prev = item;
195 }
196
197 /**
198 * Remove an item from a list.
199 *
200 * @param item Pointer to struct list_item of the item to be removed.
201 * @return Whether the action has been performed.
202 */
203 static inline bool
204 list_remove(struct list_item *item)
205 {
206 if (!item->next || !item->prev || list_is_empty(item))
207 return false;
208
209 item->prev->next = item->next;
210 item->next->prev = item->prev;
211 item->next = item->prev = item;
212
213 return true;
214 }
215
216 /**
217 * Remove the last element of a list.
218 *
219 * @param head Pointer to the list's head.
220 * @return Pointer to struct list_item removed from the list;
221 * or NULL, if the list is empty.
222 */
223 static inline struct list_item *
224 list_remove_tail(struct list_item *head)
225 {
226 struct list_item *t = list_is_empty(head) ? NULL : head->prev;
227
228 if (t)
229 list_remove(t);
230
231 return t;
232 }
233
234 /**
235 * Remove the first element of a list.
236 *
237 * @param head Pointer to the list's head.
238 * @return Pointer to struct list_item removed from the list;
239 * or NULL, if the list is empty.
240 */
241 static inline struct list_item *
242 list_remove_head(struct list_item *head)
243 {
244 struct list_item *h = list_is_empty(head) ? NULL : head->next;
245
246 if (h)
247 list_remove(h);
248
249 return h;
250 }
251
252 /**
253 * Replace an old struct list_item in a list with the new one.
254 *
255 * @param old Pointer to struct list_item of the item to be replaced.
256 * @param new Pointer to struct list_item of the item to be replaced with.
257 * @return Whether the replacement has been performed.
258 */
259 static inline bool
260 list_replace(struct list_item *old, struct list_item *new)
261 {
262 if (!old->next || !old->prev || list_is_empty(old))
263 return false;
264
265 new->next = old->next;
266 new->prev = old->prev;
267 old->prev->next = new;
268 old->next->prev = new;
269 old->next = old->prev = old;
270
271 return true;
272 }
273
274 /**
275 * List iteration wrapper for non-destructive operations.
276 *
277 * @param var_ Variable holding pointer to a current list item.
278 * @param head_ Pointer to the list's head.
279 * @param field_ Name of the field containing the respective struct list_item
280 * inside list items.
281 */
282 # define list_foreach(var_, head_, field_) \
283 for (var_ = list_elem((head_)->next, typeof(*var_), field_); \
284 &(var_->field_) != (head_); var_ = list_next(var_, field_))
285
286 /**
287 * List iteration wrapper for destructive operations.
288 *
289 * @param var_ Variable holding pointer to a current list item.
290 * @param head_ Pointer to the list's head.
291 * @param field_ Name of the field containing the respective struct list_item
292 * inside list items.
293 * @param _tmp Temporary variable for storing pointer to the next item.
294 */
295 # define list_foreach_safe(var_, head_, field_, _tmp) \
296 for (var_ = list_elem((head_)->next, typeof(*var_), field_), \
297 _tmp = list_elem((var_)->field_.next, typeof(*var_), field_); \
298 &var_->field_ != head_; var_ = _tmp, _tmp = list_next(_tmp, field_))
299
300 #endif /* !STRACE_LIST_H */