123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300 |
- /*
- * Some simple implementation of lists similar to the one used in the kernel.
- *
- * Copyright (c) 2016-2019 The strace developers.
- * All rights reserved.
- *
- * SPDX-License-Identifier: LGPL-2.1-or-later
- */
-
- #ifndef STRACE_LIST_H
- # define STRACE_LIST_H
-
- /*
- * struct list_item and related macros and functions provide an interface
- * for manipulating and iterating linked lists. In order to have list
- * associated with its payload, struct list_item has to be embedded into
- * a structure type representing payload, and (optionally) an additional
- * struct list_item should be added somewhere as a starting point for list
- * iteration (creating a list with a designated head). A situation where
- * no designated head exists, and each embedded struct list_head is considered
- * a head (i.e. starting point for list iteration), is also possible.
- *
- * List head has to be initialised with list_init() call. Statically allocated
- * list heads can also be defined with an EMPTY_LIST() macro.
- *
- * In order to get a pointer to list item from a struct list_item, list_elem
- * macro is used.
- *
- * When a designated head is used, list_head() and list_tail() can be used
- * for getting pointer to the first and the last list item, respectively.
- *
- * list_next() and list_prev() macros can be used for obtaining pointers
- * to the next and the previous items in the list, respectively. Note that
- * they do not perform additional checks for the validity of these pointers,
- * so they have to be guarded with respective list_head/list_tail checks in case
- * of lists with designated heads (where the list's head is not embedded withing
- * a list item.
- *
- * list_{insert,append,remove,remove_tail,remove_head,replace} provide some
- * basic means of list manipulation.
- *
- * list_foreach() and list_foreach_safe() are wrapper macros for simplifying
- * iteration over a list, with the latter having an additional argument
- * for storing temporary pointer, thus allowing list manipulations during
- * its iteration.
- *
- * A simple example:
- *
- * struct my_struct {
- * int a;
- * struct list_item l1;
- * struct list_item l2;
- * };
- *
- * EMPTY_LIST(list_1); <--- Defining a designated head for list
- *
- * struct my_struct *item =
- * calloc(1, sizeof(*item));
- * list_init(&item->l2); <--- Initialising structure field that
- * is used for lists without designated
- * head.
- * list_insert(&list_1, &item->l1); <--- Inserting an item into the list
- *
- * item = calloc(1, sizeof(*item));
- * list_init(&item->l2);
- *
- * list_append(&(list_head(list_1, struct my_struct, l1)->l2), &item->l2);
- *
- * struct my_struct *cur = item; <--- Iteration over a headless list
- * do {
- * printf("%d\n", cur->a);
- * } while ((cur = list_next(&cur, l2)) != item);
- *
- * struct my_struct *i;
- * list_foreach(i, list_1, l1) { <--- Iteration over list_1 without list
- * printf("%d\n", i->a); modification
- * }
- *
- * struct my_struct *tmp; <--- Iteration with modification
- * list_foreach_safe(i, list_1, l1, tmp) {
- * list_remove(&i->l1);
- * free(i);
- * }
- *
- * See also:
- * "Linux kernel design patterns - part 2", section "Linked Lists"
- * https://lwn.net/Articles/336255/
- */
-
- # include "macros.h"
-
- struct list_item {
- struct list_item *prev;
- struct list_item *next;
- };
-
- /**
- * Define an empty list head.
- *
- * @param l_ List head variable name.
- */
- # define EMPTY_LIST(l_) struct list_item l_ = { &l_, &l_ }
-
- /** Initialise an empty list. */
- static inline void
- list_init(struct list_item *l)
- {
- l->prev = l;
- l->next = l;
- }
-
- /** Check whether list is empty. */
- static inline bool
- list_is_empty(const struct list_item *l)
- {
- return ((l->next == l) && (l->prev == l))
- /*
- * XXX This could be the case when struct list_item hasn't been
- * initialised at all; we should probably also call some
- * errror_func_msg() in that case, as it looks like sloppy
- * programming.
- */
- || (!l->next && !l->prev);
- }
-
- /**
- * Convert a pointer to a struct list_item to a pointer to a list item.
- *
- * @param var Pointer to struct list_item.
- * @param type Type of the list's item.
- * @param field Name of the field that holds the respective struct list_item.
- */
- # define list_elem(var, type, field) containerof((var), type, field)
-
- /**
- * Get the first element in a list.
- *
- * @param head Pointer to the list's head.
- * @param type Type of the list's item.
- * @param field Name of the field that holds the respective struct list_item.
- */
- # define list_head(head, type, field) \
- (list_is_empty(head) ? NULL : list_elem((head)->next, type, field))
- /**
- * Get the last element in a list.
- *
- * @param head Pointer to the list's head.
- * @param type Type of the list's item.
- * @param field Name of the field that holds the respective struct list_item.
- */
- # define list_tail(head, type, field) \
- (list_is_empty(head) ? NULL : list_elem((head)->prev, type, field))
-
- /**
- * Get the next element in a list.
- *
- * @param var Pointer to a list item.
- * @param field Name of the field that holds the respective struct list_item.
- */
- # define list_next(var, field) \
- list_elem((var)->field.next, typeof(*(var)), field)
- /**
- * Get the previous element in a list.
- *
- * @param var Pointer to a list item.
- * @param field Name of the field that holds the respective struct list_item.
- */
- # define list_prev(var, field) \
- list_elem((var)->field.prev, typeof(*(var)), field)
-
- /**
- * Insert an item into a list. The item is placed as the next list item
- * to the head.
- */
- static inline void
- list_insert(struct list_item *head, struct list_item *item)
- {
- item->next = head->next;
- item->prev = head;
- head->next->prev = item;
- head->next = item;
- }
-
- /**
- * Insert an item into a list. The item is placed as the previous list item
- * to the head.
- */
- static inline void
- list_append(struct list_item *head, struct list_item *item)
- {
- item->next = head;
- item->prev = head->prev;
- head->prev->next = item;
- head->prev = item;
- }
-
- /**
- * Remove an item from a list.
- *
- * @param item Pointer to struct list_item of the item to be removed.
- * @return Whether the action has been performed.
- */
- static inline bool
- list_remove(struct list_item *item)
- {
- if (!item->next || !item->prev || list_is_empty(item))
- return false;
-
- item->prev->next = item->next;
- item->next->prev = item->prev;
- item->next = item->prev = item;
-
- return true;
- }
-
- /**
- * Remove the last element of a list.
- *
- * @param head Pointer to the list's head.
- * @return Pointer to struct list_item removed from the list;
- * or NULL, if the list is empty.
- */
- static inline struct list_item *
- list_remove_tail(struct list_item *head)
- {
- struct list_item *t = list_is_empty(head) ? NULL : head->prev;
-
- if (t)
- list_remove(t);
-
- return t;
- }
-
- /**
- * Remove the first element of a list.
- *
- * @param head Pointer to the list's head.
- * @return Pointer to struct list_item removed from the list;
- * or NULL, if the list is empty.
- */
- static inline struct list_item *
- list_remove_head(struct list_item *head)
- {
- struct list_item *h = list_is_empty(head) ? NULL : head->next;
-
- if (h)
- list_remove(h);
-
- return h;
- }
-
- /**
- * Replace an old struct list_item in a list with the new one.
- *
- * @param old Pointer to struct list_item of the item to be replaced.
- * @param new Pointer to struct list_item of the item to be replaced with.
- * @return Whether the replacement has been performed.
- */
- static inline bool
- list_replace(struct list_item *old, struct list_item *new)
- {
- if (!old->next || !old->prev || list_is_empty(old))
- return false;
-
- new->next = old->next;
- new->prev = old->prev;
- old->prev->next = new;
- old->next->prev = new;
- old->next = old->prev = old;
-
- return true;
- }
-
- /**
- * List iteration wrapper for non-destructive operations.
- *
- * @param var_ Variable holding pointer to a current list item.
- * @param head_ Pointer to the list's head.
- * @param field_ Name of the field containing the respective struct list_item
- * inside list items.
- */
- # define list_foreach(var_, head_, field_) \
- for (var_ = list_elem((head_)->next, typeof(*var_), field_); \
- &(var_->field_) != (head_); var_ = list_next(var_, field_))
-
- /**
- * List iteration wrapper for destructive operations.
- *
- * @param var_ Variable holding pointer to a current list item.
- * @param head_ Pointer to the list's head.
- * @param field_ Name of the field containing the respective struct list_item
- * inside list items.
- * @param _tmp Temporary variable for storing pointer to the next item.
- */
- # define list_foreach_safe(var_, head_, field_, _tmp) \
- for (var_ = list_elem((head_)->next, typeof(*var_), field_), \
- _tmp = list_elem((var_)->field_.next, typeof(*var_), field_); \
- &var_->field_ != head_; var_ = _tmp, _tmp = list_next(_tmp, field_))
-
- #endif /* !STRACE_LIST_H */
|