Mirror of strace – the linux syscall tracer
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

list.h 8.9KB

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