source: mainline/kernel/generic/include/adt/list.h@ 901b302

ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 901b302 was 69511176, checked in by Martin Decky <martin@…>, 4 years ago

Avoid undefined behavior even more

While the previous implementation no longer suffers from undefined
behavior due to unaligned pointer value, it is still problematic due to
indexing beyond a hypothetical array bound. The assignment of
sizeof(itype) is both an aligned value and does not violate any bounds.

  • Property mode set to 100644
File size: 10.8 KB
Line 
1/*
2 * Copyright (c) 2001-2004 Jakub Jermar
3 * Copyright (c) 2013 Jiri Svoboda
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * - Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * - Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * - The name of the author may not be used to endorse or promote products
16 * derived from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30/** @addtogroup kernel_generic_adt
31 * @{
32 */
33/** @file
34 */
35
36#ifndef KERN_LIST_H_
37#define KERN_LIST_H_
38
39#include <assert.h>
40#include <macros.h>
41#include <member.h>
42#include <stdbool.h>
43#include <stddef.h>
44#include <stdint.h>
45#include <trace.h>
46
47/** Doubly linked list link. */
48typedef struct link {
49 struct link *prev; /**< Pointer to the previous item in the list. */
50 struct link *next; /**< Pointer to the next item in the list. */
51} link_t;
52
53/** Doubly linked list. */
54typedef struct list {
55 link_t head; /**< List head. Does not have any data. */
56} list_t;
57
58extern bool list_member(const link_t *, const list_t *);
59extern void list_splice(list_t *, link_t *);
60extern unsigned long list_count(const list_t *);
61
62/** Declare and initialize statically allocated list.
63 *
64 * @param name Name of the new statically allocated list.
65 *
66 */
67#define LIST_INITIALIZE(name) \
68 list_t name = LIST_INITIALIZER(name)
69
70/** Initializer for statically allocated list.
71 *
72 * @code
73 * struct named_list {
74 * const char *name;
75 * list_t list;
76 * } var = {
77 * .name = "default name",
78 * .list = LIST_INITIALIZER(name_list.list)
79 * };
80 * @endcode
81 *
82 * @param name Name of the new statically allocated list.
83 *
84 */
85#define LIST_INITIALIZER(name) \
86 { \
87 .head = { \
88 .prev = &(name).head, \
89 .next = &(name).head \
90 } \
91 }
92
93#define list_get_instance(link, type, member) \
94 member_to_inst(link, type, member)
95
96#define list_foreach(list, member, itype, iterator) \
97 for (itype *iterator = NULL; iterator == NULL; iterator = (itype *) sizeof(itype)) \
98 for (link_t *_link = (list).head.next; \
99 iterator = list_get_instance(_link, itype, member), \
100 _link != &(list).head; _link = _link->next)
101
102#define list_foreach_rev(list, member, itype, iterator) \
103 for (itype *iterator = NULL; iterator == NULL; iterator = (itype *) sizeof(itype)) \
104 for (link_t *_link = (list).head.prev; \
105 iterator = list_get_instance(_link, itype, member), \
106 _link != &(list).head; _link = _link->prev)
107
108/** Unlike list_foreach(), allows removing items while traversing a list.
109 *
110 * @code
111 * list_t mylist;
112 * typedef struct item {
113 * int value;
114 * link_t item_link;
115 * } item_t;
116 *
117 * //..
118 *
119 * // Print each list element's value and remove the element from the list.
120 * list_foreach_safe(mylist, cur_link, next_link) {
121 * item_t *cur_item = list_get_instance(cur_link, item_t, item_link);
122 * printf("%d\n", cur_item->value);
123 * list_remove(cur_link);
124 * }
125 * @endcode
126 *
127 * @param list List to traverse.
128 * @param iterator Iterator to the current element of the list.
129 * The item this iterator points may be safely removed
130 * from the list.
131 * @param next_iter Iterator to the next element of the list.
132 */
133#define list_foreach_safe(list, iterator, next_iter) \
134 for (link_t *iterator = (list).head.next, \
135 *next_iter = iterator->next; \
136 iterator != &(list).head; \
137 iterator = next_iter, next_iter = iterator->next)
138
139#define assert_link_not_used(link) \
140 assert(!link_used(link))
141
142/** Returns true if the link is definitely part of a list. False if not sure. */
143static inline bool link_in_use(const link_t *link)
144{
145 return link->prev != NULL && link->next != NULL;
146}
147
148/** Initialize doubly-linked circular list link
149 *
150 * Initialize doubly-linked list link.
151 *
152 * @param link Pointer to link_t structure to be initialized.
153 *
154 */
155_NO_TRACE static inline void link_initialize(link_t *link)
156{
157 link->prev = NULL;
158 link->next = NULL;
159}
160
161/** Initialize doubly-linked circular list
162 *
163 * Initialize doubly-linked circular list.
164 *
165 * @param list Pointer to list_t structure.
166 *
167 */
168_NO_TRACE static inline void list_initialize(list_t *list)
169{
170 list->head.prev = &list->head;
171 list->head.next = &list->head;
172}
173
174/** Insert item before another item in doubly-linked circular list.
175 *
176 */
177static inline void list_insert_before(link_t *lnew, link_t *lold)
178{
179 lnew->next = lold;
180 lnew->prev = lold->prev;
181 lold->prev->next = lnew;
182 lold->prev = lnew;
183}
184
185/** Insert item after another item in doubly-linked circular list.
186 *
187 */
188static inline void list_insert_after(link_t *lnew, link_t *lold)
189{
190 lnew->prev = lold;
191 lnew->next = lold->next;
192 lold->next->prev = lnew;
193 lold->next = lnew;
194}
195
196/** Add item to the beginning of doubly-linked circular list
197 *
198 * Add item to the beginning of doubly-linked circular list.
199 *
200 * @param link Pointer to link_t structure to be added.
201 * @param list Pointer to list_t structure.
202 *
203 */
204_NO_TRACE static inline void list_prepend(link_t *link, list_t *list)
205{
206 list_insert_after(link, &list->head);
207}
208
209/** Add item to the end of doubly-linked circular list
210 *
211 * Add item to the end of doubly-linked circular list.
212 *
213 * @param link Pointer to link_t structure to be added.
214 * @param list Pointer to list_t structure.
215 *
216 */
217_NO_TRACE static inline void list_append(link_t *link, list_t *list)
218{
219 list_insert_before(link, &list->head);
220}
221
222/** Remove item from doubly-linked circular list
223 *
224 * Remove item from doubly-linked circular list.
225 *
226 * @param link Pointer to link_t structure to be removed from the list
227 * it is contained in.
228 *
229 */
230_NO_TRACE static inline void list_remove(link_t *link)
231{
232 if ((link->prev != NULL) && (link->next != NULL)) {
233 link->next->prev = link->prev;
234 link->prev->next = link->next;
235 }
236
237 link_initialize(link);
238}
239
240/** Query emptiness of doubly-linked circular list
241 *
242 * Query emptiness of doubly-linked circular list.
243 *
244 * @param list Pointer to lins_t structure.
245 *
246 */
247_NO_TRACE static inline bool list_empty(const list_t *list)
248{
249 return (list->head.next == &list->head);
250}
251
252/** Get first item in list.
253 *
254 * @param list Pointer to list_t structure.
255 *
256 * @return Head item of the list.
257 * @return NULL if the list is empty.
258 *
259 */
260static inline link_t *list_first(const list_t *list)
261{
262 return ((list->head.next == &list->head) ? NULL : list->head.next);
263}
264
265/** Get last item in list.
266 *
267 * @param list Pointer to list_t structure.
268 *
269 * @return Head item of the list.
270 * @return NULL if the list is empty.
271 *
272 */
273static inline link_t *list_last(const list_t *list)
274{
275 return (list->head.prev == &list->head) ? NULL : list->head.prev;
276}
277
278/** Get next item in list.
279 *
280 * @param link Current item link
281 * @param list List containing @a link
282 *
283 * @return Next item or NULL if @a link is the last item.
284 */
285static inline link_t *list_next(const link_t *link, const list_t *list)
286{
287 return (link->next == &list->head) ? NULL : link->next;
288}
289
290/** Get previous item in list.
291 *
292 * @param link Current item link
293 * @param list List containing @a link
294 *
295 * @return Previous item or NULL if @a link is the first item.
296 */
297static inline link_t *list_prev(const link_t *link, const list_t *list)
298{
299 return (link->prev == &list->head) ? NULL : link->prev;
300}
301
302/** Split or concatenate headless doubly-linked circular list
303 *
304 * Split or concatenate headless doubly-linked circular list.
305 *
306 * Note that the algorithm works both directions:
307 * concatenates splitted lists and splits concatenated lists.
308 *
309 * @param part1 Pointer to link_t structure leading the first
310 * (half of the headless) list.
311 * @param part2 Pointer to link_t structure leading the second
312 * (half of the headless) list.
313 *
314 */
315_NO_TRACE static inline void headless_list_split_or_concat(link_t *part1, link_t *part2)
316{
317 part1->prev->next = part2;
318 part2->prev->next = part1;
319
320 link_t *hlp = part1->prev;
321
322 part1->prev = part2->prev;
323 part2->prev = hlp;
324}
325
326/** Split headless doubly-linked circular list
327 *
328 * Split headless doubly-linked circular list.
329 *
330 * @param part1 Pointer to link_t structure leading
331 * the first half of the headless list.
332 * @param part2 Pointer to link_t structure leading
333 * the second half of the headless list.
334 *
335 */
336_NO_TRACE static inline void headless_list_split(link_t *part1, link_t *part2)
337{
338 headless_list_split_or_concat(part1, part2);
339}
340
341/** Concatenate two headless doubly-linked circular lists
342 *
343 * Concatenate two headless doubly-linked circular lists.
344 *
345 * @param part1 Pointer to link_t structure leading
346 * the first headless list.
347 * @param part2 Pointer to link_t structure leading
348 * the second headless list.
349 *
350 */
351_NO_TRACE static inline void headless_list_concat(link_t *part1, link_t *part2)
352{
353 headless_list_split_or_concat(part1, part2);
354}
355
356/** Concatenate two lists
357 *
358 * Concatenate lists @a list1 and @a list2, producing a single
359 * list @a list1 containing items from both (in @a list1, @a list2
360 * order) and empty list @a list2.
361 *
362 * @param list1 First list and concatenated output
363 * @param list2 Second list and empty output.
364 *
365 */
366_NO_TRACE static inline void list_concat(list_t *list1, list_t *list2)
367{
368 list_splice(list2, list1->head.prev);
369}
370
371/** Get n-th item in a list.
372 *
373 * @param list Pointer to link_t structure representing the list.
374 * @param n Item number (indexed from zero).
375 *
376 * @return n-th item of the list.
377 * @return NULL if no n-th item found.
378 *
379 */
380static inline link_t *list_nth(const list_t *list, size_t n)
381{
382 size_t cnt = 0;
383
384 link_t *link = list_first(list);
385 while (link != NULL) {
386 if (cnt == n)
387 return link;
388
389 cnt++;
390 link = list_next(link, list);
391 }
392
393 return NULL;
394}
395
396/** Determine if link is used.
397 *
398 * @param link Link
399 * @return @c true if link is used, @c false if not.
400 */
401static inline bool link_used(link_t *link)
402{
403 if (link->prev == NULL && link->next == NULL)
404 return false;
405
406 assert(link->prev != NULL && link->next != NULL);
407 return true;
408}
409
410#endif
411
412/** @}
413 */
Note: See TracBrowser for help on using the repository browser.