source: mainline/uspace/lib/c/include/adt/list.h@ d5ed54b

serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since d5ed54b 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: 11.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 libc
31 * @{
32 */
33/** @file
34 */
35
36#ifndef _LIBC_LIST_H_
37#define _LIBC_LIST_H_
38
39#include <assert.h>
40#include <member.h>
41#include <stdbool.h>
42#include <stddef.h>
43#include <stdint.h>
44#include <trace.h>
45#include <_bits/decls.h>
46
47#ifndef __cplusplus
48
49/**
50 * We don't define the macros in C++ to avoid polluting headers with
51 * namespaceless names. We don't actually need them, so this is fine.
52 * We still allow including the rest of the file (in `helenos` namespace)
53 * so that we can expose publicly visible types that have list_t members.
54 */
55
56/** Declare and initialize statically allocated list.
57 *
58 * @param name Name of the new statically allocated list.
59 *
60 */
61#define LIST_INITIALIZE(name) \
62 list_t name = LIST_INITIALIZER(name)
63
64/** Initializer for statically allocated list.
65 *
66 * @code
67 * struct named_list {
68 * const char *name;
69 * list_t list;
70 * } var = {
71 * .name = "default name",
72 * .list = LIST_INITIALIZER(name_list.list)
73 * };
74 * @endcode
75 *
76 * @param name Name of the new statically allocated list.
77 *
78 */
79#define LIST_INITIALIZER(name) \
80 { \
81 .head = { \
82 .prev = &(name).head, \
83 .next = &(name).head \
84 } \
85 }
86
87#define list_get_instance(link, type, member) \
88 member_to_inst(link, type, member)
89
90#define list_foreach(list, member, itype, iterator) \
91 for (itype *iterator = NULL; iterator == NULL; iterator = (itype *) sizeof(itype)) \
92 for (link_t *_link = (list).head.next; \
93 iterator = list_get_instance(_link, itype, member), \
94 _link != &(list).head; _link = _link->next)
95
96#define list_foreach_rev(list, member, itype, iterator) \
97 for (itype *iterator = NULL; iterator == NULL; iterator = (itype *) sizeof(itype)) \
98 for (link_t *_link = (list).head.prev; \
99 iterator = list_get_instance(_link, itype, member), \
100 _link != &(list).head; _link = _link->prev)
101
102/** Unlike list_foreach(), allows removing items while traversing a list.
103 *
104 * @code
105 * list_t mylist;
106 * typedef struct item {
107 * int value;
108 * link_t item_link;
109 * } item_t;
110 *
111 * //..
112 *
113 * // Print each list element's value and remove the element from the list.
114 * list_foreach_safe(mylist, cur_link, next_link) {
115 * item_t *cur_item = list_get_instance(cur_link, item_t, item_link);
116 * printf("%d\n", cur_item->value);
117 * list_remove(cur_link);
118 * }
119 * @endcode
120 *
121 * @param list List to traverse.
122 * @param iterator Iterator to the current element of the list.
123 * The item this iterator points may be safely removed
124 * from the list.
125 * @param next_iter Iterator to the next element of the list.
126 */
127#define list_foreach_safe(list, iterator, next_iter) \
128 for (link_t *iterator = (list).head.next, \
129 *next_iter = iterator->next; \
130 iterator != &(list).head; \
131 iterator = next_iter, next_iter = iterator->next)
132
133#define assert_link_not_used(link) \
134 assert(!link_used(link))
135
136#define list_pop(list, type, member) \
137 ((type *) list_pop_internal(list, \
138 (list_link_to_void(&(((type *) NULL)->member)) - NULL)))
139
140#endif /* !__cplusplus */
141
142__HELENOS_DECLS_BEGIN;
143
144/** Doubly linked list link. */
145typedef struct __adt_list_link {
146 struct __adt_list_link *prev; /**< Pointer to the previous item in the list. */
147 struct __adt_list_link *next; /**< Pointer to the next item in the list. */
148} link_t;
149
150/** Doubly linked list. */
151typedef struct {
152 link_t head; /**< List head. Does not have any data. */
153} list_t;
154
155extern bool list_member(const link_t *, const list_t *);
156extern void list_splice(list_t *, link_t *);
157extern size_t list_count(const list_t *);
158
159/** Returns true if the link is definitely part of a list. False if not sure. */
160static inline bool link_in_use(const link_t *link)
161{
162 return link->prev != NULL && link->next != NULL;
163}
164
165/** Initialize doubly-linked circular list link
166 *
167 * Initialize doubly-linked list link.
168 *
169 * @param link Pointer to link_t structure to be initialized.
170 *
171 */
172_NO_TRACE static inline void link_initialize(link_t *link)
173{
174 link->prev = NULL;
175 link->next = NULL;
176}
177
178/** Initialize doubly-linked circular list
179 *
180 * Initialize doubly-linked circular list.
181 *
182 * @param list Pointer to list_t structure.
183 *
184 */
185_NO_TRACE static inline void list_initialize(list_t *list)
186{
187 list->head.prev = &list->head;
188 list->head.next = &list->head;
189}
190
191/** Insert item before another item in doubly-linked circular list.
192 *
193 */
194static inline void list_insert_before(link_t *lnew, link_t *lold)
195{
196 lnew->next = lold;
197 lnew->prev = lold->prev;
198 lold->prev->next = lnew;
199 lold->prev = lnew;
200}
201
202/** Insert item after another item in doubly-linked circular list.
203 *
204 */
205static inline void list_insert_after(link_t *lnew, link_t *lold)
206{
207 lnew->prev = lold;
208 lnew->next = lold->next;
209 lold->next->prev = lnew;
210 lold->next = lnew;
211}
212
213/** Add item to the beginning of doubly-linked circular list
214 *
215 * Add item to the beginning of doubly-linked circular list.
216 *
217 * @param link Pointer to link_t structure to be added.
218 * @param list Pointer to list_t structure.
219 *
220 */
221_NO_TRACE static inline void list_prepend(link_t *link, list_t *list)
222{
223 list_insert_after(link, &list->head);
224}
225
226/** Add item to the end of doubly-linked circular list
227 *
228 * Add item to the end of doubly-linked circular list.
229 *
230 * @param link Pointer to link_t structure to be added.
231 * @param list Pointer to list_t structure.
232 *
233 */
234_NO_TRACE static inline void list_append(link_t *link, list_t *list)
235{
236 list_insert_before(link, &list->head);
237}
238
239/** Remove item from doubly-linked circular list
240 *
241 * Remove item from doubly-linked circular list.
242 *
243 * @param link Pointer to link_t structure to be removed from the list
244 * it is contained in.
245 *
246 */
247_NO_TRACE static inline void list_remove(link_t *link)
248{
249 if ((link->prev != NULL) && (link->next != NULL)) {
250 link->next->prev = link->prev;
251 link->prev->next = link->next;
252 }
253
254 link_initialize(link);
255}
256
257/** Query emptiness of doubly-linked circular list
258 *
259 * Query emptiness of doubly-linked circular list.
260 *
261 * @param list Pointer to lins_t structure.
262 *
263 */
264_NO_TRACE static inline bool list_empty(const list_t *list)
265{
266 return (list->head.next == &list->head);
267}
268
269/** Get first item in list.
270 *
271 * @param list Pointer to list_t structure.
272 *
273 * @return Head item of the list.
274 * @return NULL if the list is empty.
275 *
276 */
277static inline link_t *list_first(const list_t *list)
278{
279 return ((list->head.next == &list->head) ? NULL : list->head.next);
280}
281
282/** Get last item in list.
283 *
284 * @param list Pointer to list_t structure.
285 *
286 * @return Head item of the list.
287 * @return NULL if the list is empty.
288 *
289 */
290static inline link_t *list_last(const list_t *list)
291{
292 return (list->head.prev == &list->head) ? NULL : list->head.prev;
293}
294
295/** Get next item in list.
296 *
297 * @param link Current item link
298 * @param list List containing @a link
299 *
300 * @return Next item or NULL if @a link is the last item.
301 */
302static inline link_t *list_next(const link_t *link, const list_t *list)
303{
304 return (link->next == &list->head) ? NULL : link->next;
305}
306
307/** Get previous item in list.
308 *
309 * @param link Current item link
310 * @param list List containing @a link
311 *
312 * @return Previous item or NULL if @a link is the first item.
313 */
314static inline link_t *list_prev(const link_t *link, const list_t *list)
315{
316 return (link->prev == &list->head) ? NULL : link->prev;
317}
318
319/** Split or concatenate headless doubly-linked circular list
320 *
321 * Split or concatenate headless doubly-linked circular list.
322 *
323 * Note that the algorithm works both directions:
324 * concatenates splitted lists and splits concatenated lists.
325 *
326 * @param part1 Pointer to link_t structure leading the first
327 * (half of the headless) list.
328 * @param part2 Pointer to link_t structure leading the second
329 * (half of the headless) list.
330 *
331 */
332_NO_TRACE static inline void headless_list_split_or_concat(link_t *part1, link_t *part2)
333{
334 part1->prev->next = part2;
335 part2->prev->next = part1;
336
337 link_t *hlp = part1->prev;
338
339 part1->prev = part2->prev;
340 part2->prev = hlp;
341}
342
343/** Split headless doubly-linked circular list
344 *
345 * Split headless doubly-linked circular list.
346 *
347 * @param part1 Pointer to link_t structure leading
348 * the first half of the headless list.
349 * @param part2 Pointer to link_t structure leading
350 * the second half of the headless list.
351 *
352 */
353_NO_TRACE static inline void headless_list_split(link_t *part1, link_t *part2)
354{
355 headless_list_split_or_concat(part1, part2);
356}
357
358/** Concatenate two headless doubly-linked circular lists
359 *
360 * Concatenate two headless doubly-linked circular lists.
361 *
362 * @param part1 Pointer to link_t structure leading
363 * the first headless list.
364 * @param part2 Pointer to link_t structure leading
365 * the second headless list.
366 *
367 */
368_NO_TRACE static inline void headless_list_concat(link_t *part1, link_t *part2)
369{
370 headless_list_split_or_concat(part1, part2);
371}
372
373/** Concatenate two lists
374 *
375 * Concatenate lists @a list1 and @a list2, producing a single
376 * list @a list1 containing items from both (in @a list1, @a list2
377 * order) and empty list @a list2.
378 *
379 * @param list1 First list and concatenated output
380 * @param list2 Second list and empty output.
381 *
382 */
383_NO_TRACE static inline void list_concat(list_t *list1, list_t *list2)
384{
385 list_splice(list2, list1->head.prev);
386}
387
388/** Get n-th item in a list.
389 *
390 * @param list Pointer to link_t structure representing the list.
391 * @param n Item number (indexed from zero).
392 *
393 * @return n-th item of the list.
394 * @return NULL if no n-th item found.
395 *
396 */
397static inline link_t *list_nth(const list_t *list, size_t n)
398{
399 size_t cnt = 0;
400
401 link_t *link = list_first(list);
402 while (link != NULL) {
403 if (cnt == n)
404 return link;
405
406 cnt++;
407 link = list_next(link, list);
408 }
409
410 return NULL;
411}
412
413/** Verify that argument type is a pointer to link_t (at compile time).
414 *
415 * This can be used to check argument type in a macro.
416 */
417static inline const void *list_link_to_void(const link_t *link)
418{
419 return link;
420}
421
422/** Determine if link is used.
423 *
424 * @param link Link
425 * @return @c true if link is used, @c false if not.
426 */
427static inline bool link_used(link_t *link)
428{
429 if (link->prev == NULL && link->next == NULL)
430 return false;
431
432 assert(link->prev != NULL && link->next != NULL);
433 return true;
434}
435
436static inline void *list_pop_internal(list_t *list, ptrdiff_t offset)
437{
438 link_t *tmp = list_first(list);
439 if (tmp == NULL)
440 return NULL;
441
442 list_remove(tmp);
443 return (void *) (((uint8_t *) tmp) - offset);
444}
445
446__HELENOS_DECLS_END;
447
448#endif
449
450/** @}
451 */
Note: See TracBrowser for help on using the repository browser.