list.h 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354
  1. /* -*- mode:c; c-file-style:"k&r"; c-basic-offset: 4; tab-width:4; indent-tabs-mode:nil; mode:auto-fill; fill-column:78; -*- */
  2. /* vim: set ts=4 sw=4 et tw=78 fo=cqt wm=0: */
  3. /* Copyright (C) 2017 University of North Carolina at Chapel Hill and
  4. Fortanix, Inc.
  5. This file is part of Graphene Library OS.
  6. Graphene Library OS is free software: you can redistribute it and/or
  7. modify it under the terms of the GNU Lesser General Public License
  8. as published by the Free Software Foundation, either version 3 of the
  9. License, or (at your option) any later version.
  10. Graphene Library OS is distributed in the hope that it will be useful,
  11. but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13. GNU Lesser General Public License for more details.
  14. You should have received a copy of the GNU Lesser General Public License
  15. along with this program. If not, see <http://www.gnu.org/licenses/>. */
  16. /*
  17. * list.h
  18. *
  19. * This file defines the list API for the PAL and Library OS.
  20. */
  21. #ifndef LIST_H
  22. #define LIST_H
  23. // Use a new list implementation
  24. /* This list implementation stores a pointer to the next object and casts to
  25. * the object, rather than using offsetof(). We try to encapsulate this
  26. * change in a macro for declarations, which generates a type declaration for
  27. * each list object (giving marginally more help from the compiler
  28. * in detecting bugs.
  29. *
  30. * In particular, there is a small trade-off in that the association between
  31. * list heads and nodes is more explicit and a few more casting errors can be
  32. * caught by the compiler, but we add a parameter to some functions (well,
  33. * macros) to pass the field of the struct.
  34. */
  35. /* How-to:
  36. *
  37. * Each list has a pointer (listp) type, and a node (list)type. We assume
  38. * list nodes are embedded in a larger structure; the name of this structure
  39. * is used as part of the list type.
  40. *
  41. * To define a listp/list pair for a struct foo:
  42. *
  43. * DEFINE_LIST(foo);
  44. * struct foo {
  45. * int x;
  46. * LIST_TYPE(foo) list; // The list node
  47. * };
  48. *
  49. * DEFINE_LISTP(foo);
  50. * static LISTP_TYPE(foo) the_list = LISTP_INIT;
  51. *
  52. * -----
  53. *
  54. * From here, you can use listp_add variants to add an object from the list:
  55. *
  56. * struct foo *f = malloc(sizeof(struct foo));
  57. * f->x = 1;
  58. * INIT_LIST_HEAD(f, list); // The second parameter is the structure member
  59. * listp_add(f, &the_list, list);
  60. *
  61. * -----
  62. *
  63. * There are a number of add variants, some that add in a given position,
  64. * others that add to the head or the tail.
  65. *
  66. * You can search for an object using a variant of listp_for_each_entry. The
  67. * safe variants are safe against deletion.
  68. *
  69. * You can remove an object from a list using listp_del.
  70. *
  71. * In this example, we delete everything with a key bigger than 5.
  72. *
  73. * LIST_TYPE(foo) *f, *n; // n is not used, just for scratch space
  74. * listp_for_each_entry_safe(f, n, &the_list, list) {
  75. * if (f->x > 4) {
  76. * listp_del(f, &the_list, list);
  77. * free(f);
  78. * }
  79. * }
  80. *
  81. *
  82. * listp_splice moves an entire listp onto another, and list_move_tail takes
  83. * an element off of one list and places it on another.
  84. *
  85. * static LISTP_TYPE(foo) other_list; // Assume it is full of goodies
  86. * // Move everything on other_list to the_list
  87. * listp_splice_tail(&other_list, &the_list, list, foo); // the third argument
  88. * // is the field; the
  89. * // fourth is the type
  90. * // of the nodes (not
  91. * // the head pointer).
  92. *
  93. * // Use listp_empty to test for emptiness of the list
  94. * assert(listp_empty(&other_ist));
  95. *
  96. * // Now move back anythign less than 6 back to other_list
  97. * listp_for_each_entry_safe(f, n, &the_list, list) {
  98. * if (f->x < 6)
  99. * listp_move_tail(f, &other_list, &the_list, list);
  100. * }
  101. *
  102. */
  103. // Maybe TODO?
  104. //
  105. // Change the order of (node, head, field) -> (head, node, field)
  106. // drop the listp type to reduce code changes?
  107. // Cleaner way to express types
  108. // Add assertion to delete (in debugging mode) that item is on list
  109. // There are a few places where knowing the listp for deletion is cumbersome;
  110. // maybe drop this requirement?
  111. #include <stdbool.h>
  112. #ifdef DEBUG
  113. #include <assert.h>
  114. #define LIST_ASSERT(cond) assert(cond)
  115. #else
  116. #define LIST_ASSERT(cond)
  117. #endif
  118. /* For these macros, do not include the string 'struct' */
  119. #define LIST_TYPE(STRUCT) struct list_head ##_## STRUCT
  120. #define LISTP_TYPE(STRUCT) struct listp ##_## STRUCT
  121. /* Declare the enclosing struct for convenience, on
  122. * the assumption that this is primarily used in structure
  123. * definitions, and harmless if duplicated. */
  124. #define DEFINE_LIST(STRUCT) \
  125. struct STRUCT; \
  126. LIST_TYPE(STRUCT) { \
  127. struct STRUCT *next, *prev; \
  128. }
  129. /* We use LISTP for pointers to a list. This project only really needs
  130. * doubly-linked lists. We used hlists to get a single pointer for more
  131. * efficient hash tables, but they were still effectively doubly-linked
  132. * lists. */
  133. #define DEFINE_LISTP(STRUCT) \
  134. LISTP_TYPE(STRUCT) { \
  135. struct STRUCT * first; \
  136. }
  137. #define LISTP_INIT {NULL}
  138. /* A node not on a list uses NULL; on a list, you
  139. * store self pointers */
  140. #define INIT_LIST_HEAD(OBJECT, FIELD) do { \
  141. (OBJECT)->FIELD.next = NULL; \
  142. (OBJECT)->FIELD.prev = NULL; \
  143. } while (0)
  144. #define INIT_LISTP(OBJECT) do { \
  145. (OBJECT)->first = NULL; \
  146. } while (0)
  147. #define listp_empty(HEAD) ((HEAD)->first == NULL)
  148. #define list_empty(NODE, FIELD) \
  149. ((NODE)->FIELD.next == NULL)
  150. /* This helper takes 3 arguments - all should be containing structures,
  151. * and the field to use for the offset to the list node */
  152. #define __list_add(NEW, NEXT, PREV, FIELD) do { \
  153. __typeof__(NEW) __tmp_next = (NEXT); \
  154. __typeof__(NEW) __tmp_prev = (PREV); \
  155. __tmp_prev->FIELD.next = (NEW); \
  156. __tmp_next->FIELD.prev = (NEW); \
  157. (NEW)->FIELD.next = __tmp_next; \
  158. (NEW)->FIELD.prev = __tmp_prev; \
  159. } while (0)
  160. #define list_add(NEW, HEAD, FIELD) \
  161. __list_add(NEW, (HEAD)->FIELD.next, HEAD, FIELD)
  162. #define listp_add(NEW, HEAD, FIELD) do { \
  163. if ((HEAD)->first == NULL) { \
  164. (HEAD)->first = (NEW); \
  165. (NEW)->FIELD.next = (NEW); \
  166. (NEW)->FIELD.prev = (NEW); \
  167. } else { \
  168. __list_add(NEW, (HEAD)->first, (HEAD)->first->FIELD.prev, FIELD); \
  169. (HEAD)->first = (NEW); \
  170. } \
  171. } while (0)
  172. /* If NODE is defined, add NEW after NODE; if not,
  173. * put NEW at the front of the list */
  174. #define listp_add_after(NEW, NODE, HEAD, FIELD) do { \
  175. if (NODE) \
  176. list_add(NEW, NODE, FIELD); \
  177. else \
  178. listp_add(NEW, HEAD, FIELD); \
  179. } while(0)
  180. #define list_add_tail(NEW, HEAD, FIELD) \
  181. __list_add(NEW, HEAD, (HEAD)->FIELD.prev, FIELD)
  182. #define listp_add_tail(NEW, HEAD, FIELD) do { \
  183. if ((HEAD)->first == NULL) { \
  184. (HEAD)->first = (NEW); \
  185. (NEW)->FIELD.next = (NEW); \
  186. (NEW)->FIELD.prev = (NEW); \
  187. } else \
  188. list_add_tail(NEW, (HEAD)->first, FIELD); \
  189. } while (0)
  190. /* Or deletion needs to know the list root */
  191. #define listp_del(NODE, HEAD, FIELD) do { \
  192. if ((HEAD)->first == (NODE)) { \
  193. if ((NODE)->FIELD.next == (NODE)) { \
  194. (HEAD)->first = NULL; \
  195. } else { \
  196. (HEAD)->first = (NODE)->FIELD.next; \
  197. } \
  198. } \
  199. LIST_ASSERT((NODE)->FIELD.prev->FIELD.next == (NODE)); \
  200. LIST_ASSERT((NODE)->FIELD.next->FIELD.prev == (NODE)); \
  201. (NODE)->FIELD.prev->FIELD.next = (NODE)->FIELD.next; \
  202. (NODE)->FIELD.next->FIELD.prev = (NODE)->FIELD.prev; \
  203. } while(0)
  204. #define listp_del_init(NODE, HEAD, FIELD) do { \
  205. listp_del(NODE, HEAD, FIELD); \
  206. INIT_LIST_HEAD(NODE, FIELD); \
  207. } while(0)
  208. /* Keep vestigial TYPE and FIELD parameters to minimize disruption
  209. * when switching from Linux list implementation */
  210. #define listp_first_entry(LISTP, TYPE, FIELD) ((LISTP)->first)
  211. /* New API: return last entry in list */
  212. #define listp_last_entry(LISTP, TYPE, FIELD) ((LISTP)->first->FIELD.prev)
  213. /* New API: return next entry in list */
  214. #define listp_next_entry(NODE, LISTP, FIELD) \
  215. ((NODE) == (LISTP)->first->FIELD.prev ? NULL : (NODE)->FIELD.next)
  216. /* New API: return previous entry in list */
  217. #define listp_prev_entry(NODE, LISTP, FIELD) \
  218. ((NODE) == (LISTP)->first ? NULL : (NODE)->FIELD.prev)
  219. /* Vestigial - for compat with Linux list code; rename to listp?
  220. */
  221. #define list_entry(LISTP, TYPE, FIELD) (LISTP)
  222. #define listp_for_each_entry(CURSOR, HEAD, FIELD) \
  223. for (bool first_iter = ((CURSOR) = (HEAD)->first, \
  224. !!(HEAD)->first); \
  225. first_iter || (CURSOR) != (HEAD)->first; \
  226. (CURSOR) = (CURSOR)->FIELD.next, first_iter = false)
  227. #define listp_for_each_entry_reverse(CURSOR, HEAD, FIELD) \
  228. for (bool first_iter = ((CURSOR) = ((HEAD)->first \
  229. ? (HEAD)->first->FIELD.prev \
  230. : (HEAD)->first), \
  231. !!(HEAD)->first); \
  232. first_iter || ((CURSOR) && (CURSOR)->FIELD.next != (HEAD)->first); \
  233. (CURSOR) = (CURSOR)->FIELD.prev, first_iter = false)
  234. #define listp_for_each_entry_safe(CURSOR, TMP, HEAD, FIELD) \
  235. for (bool first_iter = ((CURSOR) = (HEAD)->first, \
  236. (TMP) = ((CURSOR) \
  237. ? (CURSOR)->FIELD.next \
  238. : (CURSOR)), \
  239. !!(HEAD)->first); \
  240. (HEAD)->first && (first_iter || (CURSOR) != (HEAD)->first); \
  241. /* Handle the case where the first element was removed. */ \
  242. first_iter = first_iter && (TMP) != (CURSOR) && (HEAD)->first == (TMP), \
  243. (CURSOR) = (TMP), \
  244. (TMP) = (TMP)->FIELD.next)
  245. /* Continue safe iteration with CURSOR->next */
  246. #define listp_for_each_entry_safe_continue(CURSOR, TMP, HEAD, FIELD) \
  247. for ((CURSOR) = (CURSOR)->FIELD.next, \
  248. (TMP) = (CURSOR)->FIELD.next; \
  249. (CURSOR) != (HEAD)->first && (HEAD)->first; \
  250. (CURSOR) = (TMP), \
  251. (TMP) = (TMP)->FIELD.next)
  252. /* Assertion code written in Graphene project */
  253. #define check_list_head(TYPE, head, FIELD) \
  254. do { \
  255. TYPE pos; \
  256. listp_for_each_entry(pos, head, FIELD) { \
  257. assert((pos->FIELD.prev != pos && pos->FIELD.next != pos) \
  258. || (pos->FIELD.prev == pos && pos->FIELD.next == pos)); \
  259. assert(pos->FIELD.prev->FIELD.next == pos); \
  260. assert(pos->FIELD.next->FIELD.prev == pos); \
  261. } \
  262. } while (0)
  263. // Add NEW to OLD at position first (assuming first is all we need for now)
  264. // Can probably drop TYPE with some preprocessor smarts
  265. #define listp_splice(NEW, OLD, FIELD, TYPE) do { \
  266. if(!listp_empty(NEW)) { \
  267. if(listp_empty(OLD)) { \
  268. (OLD)->first = (NEW)->first; \
  269. } else { \
  270. struct TYPE *last_old = (OLD)->first->FIELD.prev; \
  271. (OLD)->first->FIELD.prev->FIELD.next = (NEW)->first; \
  272. (OLD)->first->FIELD.prev = (NEW)->first->FIELD.prev; \
  273. (NEW)->first->FIELD.prev->FIELD.next = (OLD)->first; \
  274. (NEW)->first->FIELD.prev = last_old; \
  275. (OLD)->first = (NEW)->first; \
  276. } \
  277. } \
  278. } while (0)
  279. // Add NEW to OLD at last position
  280. // Can probably drop TYPE with some preprocessor smarts
  281. #define listp_splice_tail(NEW, OLD, FIELD, TYPE) do { \
  282. if(!listp_empty(NEW)) { \
  283. if(listp_empty(OLD)) { \
  284. (OLD)->first = (NEW)->first; \
  285. } else { \
  286. struct TYPE *last_old = (OLD)->first->FIELD.prev; \
  287. last_old->FIELD.next = (NEW)->first; \
  288. (OLD)->first->FIELD.prev = (NEW)->first->FIELD.prev; \
  289. (NEW)->first->FIELD.prev->FIELD.next = (OLD)->first; \
  290. (NEW)->first->FIELD.prev = last_old; \
  291. } \
  292. } \
  293. } while (0)
  294. #define listp_splice_init(NEW, OLD, FIELD, TYPE) do { \
  295. listp_splice(NEW, OLD, FIELD, TYPE); \
  296. INIT_LISTP(NEW); \
  297. } while(0);
  298. #define listp_splice_tail_init(NEW, OLD, FIELD, TYPE) do { \
  299. listp_splice_tail(NEW, OLD, FIELD, TYPE); \
  300. INIT_LISTP(NEW); \
  301. } while(0);
  302. // list_move_tail - delete from OLD, make tail of NEW
  303. #define listp_move_tail(NODE, NEW, OLD, FIELD) do { \
  304. listp_del_init(NODE, OLD, FIELD); \
  305. listp_add_tail(NODE, NEW, FIELD); \
  306. } while (0)
  307. #endif // LIST_H