list.h 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339
  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. #ifdef DEBUG
  112. #include <assert.h>
  113. #define LIST_ASSERT(cond) assert(cond)
  114. #else
  115. #define LIST_ASSERT(cond)
  116. #endif
  117. /* For these macros, do not include the string 'struct' */
  118. #define LIST_TYPE(STRUCT) struct list_head ##_## STRUCT
  119. #define LISTP_TYPE(STRUCT) struct listp ##_## STRUCT
  120. /* Declare the enclosing struct for convenience, on
  121. * the assumption that this is primarily used in structure
  122. * definitions, and harmless if duplicated. */
  123. #define DEFINE_LIST(STRUCT) \
  124. struct STRUCT; \
  125. LIST_TYPE(STRUCT) { \
  126. struct STRUCT *next, *prev; \
  127. }
  128. /* We use LISTP for pointers to a list. This project only really needs
  129. * doubly-linked lists. We used hlists to get a single pointer for more
  130. * efficient hash tables, but they were still effectively doubly-linked
  131. * lists. */
  132. #define DEFINE_LISTP(STRUCT) \
  133. LISTP_TYPE(STRUCT) { \
  134. struct STRUCT * first; \
  135. }
  136. #define LISTP_INIT {NULL}
  137. /* A node not on a list uses NULL; on a list, you
  138. * store self pointers */
  139. #define INIT_LIST_HEAD(OBJECT, FIELD) do { \
  140. (OBJECT)->FIELD.next = NULL; \
  141. (OBJECT)->FIELD.prev = NULL; \
  142. } while (0)
  143. #define INIT_LISTP(OBJECT) do { \
  144. (OBJECT)->first = NULL; \
  145. } while (0)
  146. #define listp_empty(HEAD) ((HEAD)->first == NULL)
  147. #define list_empty(NODE, FIELD) \
  148. ((NODE)->FIELD.next == NULL)
  149. /* This helper takes 3 arguments - all should be containing structures,
  150. * and the field to use for the offset to the list node */
  151. #define __list_add(NEW, NEXT, PREV, FIELD) do { \
  152. typeof(NEW) __tmp_next = (NEXT); \
  153. typeof(NEW) __tmp_prev = (PREV); \
  154. __tmp_prev->FIELD.next = (NEW); \
  155. __tmp_next->FIELD.prev = (NEW); \
  156. (NEW)->FIELD.next = __tmp_next; \
  157. (NEW)->FIELD.prev = __tmp_prev; \
  158. } while (0)
  159. #define list_add(NEW, HEAD, FIELD) \
  160. __list_add(NEW, (HEAD)->FIELD.next, HEAD, FIELD)
  161. #define listp_add(NEW, HEAD, FIELD) do { \
  162. if ((HEAD)->first == NULL) { \
  163. (HEAD)->first = (NEW); \
  164. (NEW)->FIELD.next = (NEW); \
  165. (NEW)->FIELD.prev = (NEW); \
  166. } else { \
  167. __list_add(NEW, (HEAD)->first, (HEAD)->first->FIELD.prev, FIELD); \
  168. (HEAD)->first = (NEW); \
  169. } \
  170. } while (0)
  171. /* If NODE is defined, add NEW after NODE; if not,
  172. * put NEW at the front of the list */
  173. #define listp_add_after(NEW, NODE, HEAD, FIELD) do { \
  174. if (NODE) \
  175. list_add(NEW, NODE, FIELD); \
  176. else \
  177. listp_add(NEW, HEAD, FIELD); \
  178. } while(0)
  179. #define list_add_tail(NEW, HEAD, FIELD) \
  180. __list_add(NEW, HEAD, (HEAD)->FIELD.prev, FIELD)
  181. #define listp_add_tail(NEW, HEAD, FIELD) do { \
  182. if ((HEAD)->first == NULL) { \
  183. (HEAD)->first = (NEW); \
  184. (NEW)->FIELD.next = (NEW); \
  185. (NEW)->FIELD.prev = (NEW); \
  186. } else \
  187. list_add_tail(NEW, (HEAD)->first, FIELD); \
  188. } while (0)
  189. /* Or deletion needs to know the list root */
  190. #define listp_del(NODE, HEAD, FIELD) do { \
  191. if ((HEAD)->first == (NODE)) { \
  192. if ((NODE)->FIELD.next == NODE) { \
  193. (HEAD)->first = NULL; \
  194. } else { \
  195. (HEAD)->first = (NODE)->FIELD.next; \
  196. } \
  197. } \
  198. LIST_ASSERT((NODE)->FIELD.prev->FIELD.next == (NODE)); \
  199. LIST_ASSERT((NODE)->FIELD.next->FIELD.prev == (NODE)); \
  200. (NODE)->FIELD.prev->FIELD.next = (NODE)->FIELD.next; \
  201. (NODE)->FIELD.next->FIELD.prev = (NODE)->FIELD.prev; \
  202. } while(0)
  203. #define listp_del_init(NODE, HEAD, FIELD) do { \
  204. listp_del(NODE, HEAD, FIELD); \
  205. INIT_LIST_HEAD(NODE, FIELD); \
  206. } while(0)
  207. /* Keep vestigial TYPE and FIELD parameters to minimize disruption
  208. * when switching from Linux list implementation */
  209. #define listp_first_entry(LISTP, TYPE, FIELD) ((LISTP)->first)
  210. /* New API: return last entry in list */
  211. #define listp_last_entry(LISTP, TYPE, FIELD) ((LISTP)->first->FIELD.prev)
  212. /* Vestigial - for compat with Linux list code; rename to listp?
  213. */
  214. #define list_entry(LISTP, TYPE, FIELD) (LISTP)
  215. #define listp_for_each_entry(CURSOR, HEAD, FIELD) \
  216. for(int first_iter = ({ (CURSOR) = (HEAD)->first; \
  217. (HEAD)->first ? 1 : 0; }); \
  218. first_iter || (CURSOR) != (HEAD)->first; \
  219. (CURSOR) = (CURSOR)->FIELD.next, first_iter = 0)
  220. #define listp_for_each_entry_reverse(CURSOR, HEAD, FIELD) \
  221. for(int first_iter = ({(CURSOR) = ((HEAD)->first \
  222. ? (HEAD)->first->FIELD.prev : \
  223. (HEAD)->first); (HEAD)->first ? 1 : 0; }); \
  224. first_iter || ((CURSOR) && (CURSOR)->FIELD.next != (HEAD)->first); \
  225. (CURSOR) = (CURSOR)->FIELD.prev, first_iter = 0)
  226. #define listp_for_each_entry_safe(CURSOR, TMP, HEAD, FIELD) \
  227. for(int first_iter = ({(CURSOR) = (HEAD)->first; \
  228. (TMP) = ((CURSOR) ? (CURSOR)->FIELD.next : (CURSOR)); \
  229. (HEAD)->first ? 1 : 0; }); \
  230. (first_iter || (CURSOR) != (HEAD)->first) && (HEAD)->first; \
  231. first_iter = (first_iter && (TMP) != (CURSOR) && (HEAD)->first == (TMP) ? \
  232. 1: 0), \
  233. (CURSOR) = (TMP), (TMP) = (TMP)->FIELD.next)
  234. /* Continue safe iteration with CURSOR->next */
  235. #define listp_for_each_entry_safe_continue(CURSOR, TMP, HEAD, FIELD) \
  236. for((CURSOR) = (CURSOR)->FIELD.next, \
  237. (TMP) = (CURSOR)->FIELD.next; \
  238. (CURSOR) != (HEAD)->first && (HEAD)->first; \
  239. (CURSOR) = (TMP), (TMP) = (TMP)->FIELD.next)
  240. /* Assertion code written in Graphene project */
  241. #define check_list_head(TYPE, head, FIELD) \
  242. do { \
  243. TYPE pos; \
  244. listp_for_each_entry(pos, head, FIELD) { \
  245. assert((pos->FIELD.prev != pos && pos->FIELD.next != pos) \
  246. || (pos->FIELD.prev == pos && pos->FIELD.next == pos)); \
  247. assert(pos->FIELD.prev->FIELD.next == pos); \
  248. assert(pos->FIELD.next->FIELD.prev == pos); \
  249. } \
  250. } while (0)
  251. // Add NEW to OLD at position first (assuming first is all we need for now)
  252. // Can probably drop TYPE with some preprocessor smarts
  253. #define listp_splice(NEW, OLD, FIELD, TYPE) do { \
  254. if(!listp_empty(NEW)) { \
  255. if(listp_empty(OLD)) { \
  256. (OLD)->first = (NEW)->first; \
  257. } else { \
  258. struct TYPE *last_old = (OLD)->first->FIELD.prev; \
  259. (OLD)->first->FIELD.prev->FIELD.next = (NEW)->first; \
  260. (OLD)->first->FIELD.prev = (NEW)->first->FIELD.prev; \
  261. (NEW)->first->FIELD.prev->FIELD.next = (OLD)->first; \
  262. (NEW)->first->FIELD.prev = last_old; \
  263. (OLD)->first = (NEW)->first; \
  264. } \
  265. } \
  266. } while (0)
  267. // Add NEW to OLD at last position
  268. // Can probably drop TYPE with some preprocessor smarts
  269. #define listp_splice_tail(NEW, OLD, FIELD, TYPE) do { \
  270. if(!listp_empty(NEW)) { \
  271. if(listp_empty(OLD)) { \
  272. (OLD)->first = (NEW)->first; \
  273. } else { \
  274. struct TYPE *last_old = (OLD)->first->FIELD.prev; \
  275. last_old->FIELD.next = (NEW)->first; \
  276. (OLD)->first->FIELD.prev = (NEW)->first->FIELD.prev; \
  277. (NEW)->first->FIELD.prev->FIELD.next = (OLD)->first; \
  278. (NEW)->first->FIELD.prev = last_old; \
  279. } \
  280. } \
  281. } while (0)
  282. #define listp_splice_init(NEW, OLD, FIELD, TYPE) do { \
  283. listp_splice(NEW, OLD, FIELD, TYPE); \
  284. INIT_LISTP(NEW); \
  285. } while(0);
  286. #define listp_splice_tail_init(NEW, OLD, FIELD, TYPE) do { \
  287. listp_splice_tail(NEW, OLD, FIELD, TYPE); \
  288. INIT_LISTP(NEW); \
  289. } while(0);
  290. // list_move_tail - delete from OLD, make tail of NEW
  291. #define listp_move_tail(NODE, NEW, OLD, FIELD) do { \
  292. listp_del_init(NODE, OLD, FIELD); \
  293. listp_add_tail(NODE, NEW, FIELD); \
  294. } while (0)
  295. #endif // LIST_H