list.h 31 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074
  1. /* SPDX-License-Identifier: GPL-2.0 */
  2. #ifndef _LINUX_LIST_H
  3. #define _LINUX_LIST_H
  4. #include <linux/container_of.h>
  5. #include <linux/types.h>
  6. #include <linux/stddef.h>
  7. #include <linux/poison.h>
  8. #include <linux/const.h>
  9. #include <asm/barrier.h>
  10. /*
  11. * Circular doubly linked list implementation.
  12. *
  13. * Some of the internal functions ("__xxx") are useful when
  14. * manipulating whole lists rather than single entries, as
  15. * sometimes we already know the next/prev entries and we can
  16. * generate better code by using them directly rather than
  17. * using the generic single-entry routines.
  18. */
  19. #define LIST_HEAD_INIT(name) { &(name), &(name) }
  20. #define LIST_HEAD(name) \
  21. struct list_head name = LIST_HEAD_INIT(name)
  22. /**
  23. * INIT_LIST_HEAD - Initialize a list_head structure
  24. * @list: list_head structure to be initialized.
  25. *
  26. * Initializes the list_head to point to itself. If it is a list header,
  27. * the result is an empty list.
  28. */
  29. static inline void INIT_LIST_HEAD(struct list_head *list)
  30. {
  31. WRITE_ONCE(list->next, list);
  32. WRITE_ONCE(list->prev, list);
  33. }
  34. #ifdef CONFIG_DEBUG_LIST
  35. extern bool __list_add_valid(struct list_head *new,
  36. struct list_head *prev,
  37. struct list_head *next);
  38. extern bool __list_del_entry_valid(struct list_head *entry);
  39. #else
  40. static inline bool __list_add_valid(struct list_head *new,
  41. struct list_head *prev,
  42. struct list_head *next)
  43. {
  44. return true;
  45. }
  46. static inline bool __list_del_entry_valid(struct list_head *entry)
  47. {
  48. return true;
  49. }
  50. #endif
  51. /*
  52. * Insert a new entry between two known consecutive entries.
  53. *
  54. * This is only for internal list manipulation where we know
  55. * the prev/next entries already!
  56. */
  57. static inline void __list_add(struct list_head *new,
  58. struct list_head *prev,
  59. struct list_head *next)
  60. {
  61. if (!__list_add_valid(new, prev, next))
  62. return;
  63. next->prev = new;
  64. new->next = next;
  65. new->prev = prev;
  66. WRITE_ONCE(prev->next, new);
  67. }
  68. /**
  69. * list_add - add a new entry
  70. * @new: new entry to be added
  71. * @head: list head to add it after
  72. *
  73. * Insert a new entry after the specified head.
  74. * This is good for implementing stacks.
  75. */
  76. static inline void list_add(struct list_head *new, struct list_head *head)
  77. {
  78. __list_add(new, head, head->next);
  79. }
  80. /**
  81. * list_add_tail - add a new entry
  82. * @new: new entry to be added
  83. * @head: list head to add it before
  84. *
  85. * Insert a new entry before the specified head.
  86. * This is useful for implementing queues.
  87. */
  88. static inline void list_add_tail(struct list_head *new, struct list_head *head)
  89. {
  90. __list_add(new, head->prev, head);
  91. }
  92. /*
  93. * Delete a list entry by making the prev/next entries
  94. * point to each other.
  95. *
  96. * This is only for internal list manipulation where we know
  97. * the prev/next entries already!
  98. */
  99. static inline void __list_del(struct list_head * prev, struct list_head * next)
  100. {
  101. next->prev = prev;
  102. WRITE_ONCE(prev->next, next);
  103. }
  104. /*
  105. * Delete a list entry and clear the 'prev' pointer.
  106. *
  107. * This is a special-purpose list clearing method used in the networking code
  108. * for lists allocated as per-cpu, where we don't want to incur the extra
  109. * WRITE_ONCE() overhead of a regular list_del_init(). The code that uses this
  110. * needs to check the node 'prev' pointer instead of calling list_empty().
  111. */
  112. static inline void __list_del_clearprev(struct list_head *entry)
  113. {
  114. __list_del(entry->prev, entry->next);
  115. entry->prev = NULL;
  116. }
  117. static inline void __list_del_entry(struct list_head *entry)
  118. {
  119. if (!__list_del_entry_valid(entry))
  120. return;
  121. __list_del(entry->prev, entry->next);
  122. }
  123. /**
  124. * list_del - deletes entry from list.
  125. * @entry: the element to delete from the list.
  126. * Note: list_empty() on entry does not return true after this, the entry is
  127. * in an undefined state.
  128. */
  129. static inline void list_del(struct list_head *entry)
  130. {
  131. __list_del_entry(entry);
  132. entry->next = LIST_POISON1;
  133. entry->prev = LIST_POISON2;
  134. }
  135. /**
  136. * list_replace - replace old entry by new one
  137. * @old : the element to be replaced
  138. * @new : the new element to insert
  139. *
  140. * If @old was empty, it will be overwritten.
  141. */
  142. static inline void list_replace(struct list_head *old,
  143. struct list_head *new)
  144. {
  145. new->next = old->next;
  146. new->next->prev = new;
  147. new->prev = old->prev;
  148. new->prev->next = new;
  149. }
  150. /**
  151. * list_replace_init - replace old entry by new one and initialize the old one
  152. * @old : the element to be replaced
  153. * @new : the new element to insert
  154. *
  155. * If @old was empty, it will be overwritten.
  156. */
  157. static inline void list_replace_init(struct list_head *old,
  158. struct list_head *new)
  159. {
  160. list_replace(old, new);
  161. INIT_LIST_HEAD(old);
  162. }
  163. /**
  164. * list_swap - replace entry1 with entry2 and re-add entry1 at entry2's position
  165. * @entry1: the location to place entry2
  166. * @entry2: the location to place entry1
  167. */
  168. static inline void list_swap(struct list_head *entry1,
  169. struct list_head *entry2)
  170. {
  171. struct list_head *pos = entry2->prev;
  172. list_del(entry2);
  173. list_replace(entry1, entry2);
  174. if (pos == entry1)
  175. pos = entry2;
  176. list_add(entry1, pos);
  177. }
  178. /**
  179. * list_del_init - deletes entry from list and reinitialize it.
  180. * @entry: the element to delete from the list.
  181. */
  182. static inline void list_del_init(struct list_head *entry)
  183. {
  184. __list_del_entry(entry);
  185. INIT_LIST_HEAD(entry);
  186. }
  187. /**
  188. * list_move - delete from one list and add as another's head
  189. * @list: the entry to move
  190. * @head: the head that will precede our entry
  191. */
  192. static inline void list_move(struct list_head *list, struct list_head *head)
  193. {
  194. __list_del_entry(list);
  195. list_add(list, head);
  196. }
  197. /**
  198. * list_move_tail - delete from one list and add as another's tail
  199. * @list: the entry to move
  200. * @head: the head that will follow our entry
  201. */
  202. static inline void list_move_tail(struct list_head *list,
  203. struct list_head *head)
  204. {
  205. __list_del_entry(list);
  206. list_add_tail(list, head);
  207. }
  208. /**
  209. * list_bulk_move_tail - move a subsection of a list to its tail
  210. * @head: the head that will follow our entry
  211. * @first: first entry to move
  212. * @last: last entry to move, can be the same as first
  213. *
  214. * Move all entries between @first and including @last before @head.
  215. * All three entries must belong to the same linked list.
  216. */
  217. static inline void list_bulk_move_tail(struct list_head *head,
  218. struct list_head *first,
  219. struct list_head *last)
  220. {
  221. first->prev->next = last->next;
  222. last->next->prev = first->prev;
  223. head->prev->next = first;
  224. first->prev = head->prev;
  225. last->next = head;
  226. head->prev = last;
  227. }
  228. /**
  229. * list_is_first -- tests whether @list is the first entry in list @head
  230. * @list: the entry to test
  231. * @head: the head of the list
  232. */
  233. static inline int list_is_first(const struct list_head *list, const struct list_head *head)
  234. {
  235. return list->prev == head;
  236. }
  237. /**
  238. * list_is_last - tests whether @list is the last entry in list @head
  239. * @list: the entry to test
  240. * @head: the head of the list
  241. */
  242. static inline int list_is_last(const struct list_head *list, const struct list_head *head)
  243. {
  244. return list->next == head;
  245. }
  246. /**
  247. * list_is_head - tests whether @list is the list @head
  248. * @list: the entry to test
  249. * @head: the head of the list
  250. */
  251. static inline int list_is_head(const struct list_head *list, const struct list_head *head)
  252. {
  253. return list == head;
  254. }
  255. /**
  256. * list_empty - tests whether a list is empty
  257. * @head: the list to test.
  258. */
  259. static inline int list_empty(const struct list_head *head)
  260. {
  261. return READ_ONCE(head->next) == head;
  262. }
  263. /**
  264. * list_del_init_careful - deletes entry from list and reinitialize it.
  265. * @entry: the element to delete from the list.
  266. *
  267. * This is the same as list_del_init(), except designed to be used
  268. * together with list_empty_careful() in a way to guarantee ordering
  269. * of other memory operations.
  270. *
  271. * Any memory operations done before a list_del_init_careful() are
  272. * guaranteed to be visible after a list_empty_careful() test.
  273. */
  274. static inline void list_del_init_careful(struct list_head *entry)
  275. {
  276. __list_del_entry(entry);
  277. WRITE_ONCE(entry->prev, entry);
  278. smp_store_release(&entry->next, entry);
  279. }
  280. /**
  281. * list_empty_careful - tests whether a list is empty and not being modified
  282. * @head: the list to test
  283. *
  284. * Description:
  285. * tests whether a list is empty _and_ checks that no other CPU might be
  286. * in the process of modifying either member (next or prev)
  287. *
  288. * NOTE: using list_empty_careful() without synchronization
  289. * can only be safe if the only activity that can happen
  290. * to the list entry is list_del_init(). Eg. it cannot be used
  291. * if another CPU could re-list_add() it.
  292. */
  293. static inline int list_empty_careful(const struct list_head *head)
  294. {
  295. struct list_head *next = smp_load_acquire(&head->next);
  296. return list_is_head(next, head) && (next == READ_ONCE(head->prev));
  297. }
  298. /**
  299. * list_rotate_left - rotate the list to the left
  300. * @head: the head of the list
  301. */
  302. static inline void list_rotate_left(struct list_head *head)
  303. {
  304. struct list_head *first;
  305. if (!list_empty(head)) {
  306. first = head->next;
  307. list_move_tail(first, head);
  308. }
  309. }
  310. /**
  311. * list_rotate_to_front() - Rotate list to specific item.
  312. * @list: The desired new front of the list.
  313. * @head: The head of the list.
  314. *
  315. * Rotates list so that @list becomes the new front of the list.
  316. */
  317. static inline void list_rotate_to_front(struct list_head *list,
  318. struct list_head *head)
  319. {
  320. /*
  321. * Deletes the list head from the list denoted by @head and
  322. * places it as the tail of @list, this effectively rotates the
  323. * list so that @list is at the front.
  324. */
  325. list_move_tail(head, list);
  326. }
  327. /**
  328. * list_is_singular - tests whether a list has just one entry.
  329. * @head: the list to test.
  330. */
  331. static inline int list_is_singular(const struct list_head *head)
  332. {
  333. return !list_empty(head) && (head->next == head->prev);
  334. }
  335. static inline void __list_cut_position(struct list_head *list,
  336. struct list_head *head, struct list_head *entry)
  337. {
  338. struct list_head *new_first = entry->next;
  339. list->next = head->next;
  340. list->next->prev = list;
  341. list->prev = entry;
  342. entry->next = list;
  343. head->next = new_first;
  344. new_first->prev = head;
  345. }
  346. /**
  347. * list_cut_position - cut a list into two
  348. * @list: a new list to add all removed entries
  349. * @head: a list with entries
  350. * @entry: an entry within head, could be the head itself
  351. * and if so we won't cut the list
  352. *
  353. * This helper moves the initial part of @head, up to and
  354. * including @entry, from @head to @list. You should
  355. * pass on @entry an element you know is on @head. @list
  356. * should be an empty list or a list you do not care about
  357. * losing its data.
  358. *
  359. */
  360. static inline void list_cut_position(struct list_head *list,
  361. struct list_head *head, struct list_head *entry)
  362. {
  363. if (list_empty(head))
  364. return;
  365. if (list_is_singular(head) && !list_is_head(entry, head) && (entry != head->next))
  366. return;
  367. if (list_is_head(entry, head))
  368. INIT_LIST_HEAD(list);
  369. else
  370. __list_cut_position(list, head, entry);
  371. }
  372. /**
  373. * list_cut_before - cut a list into two, before given entry
  374. * @list: a new list to add all removed entries
  375. * @head: a list with entries
  376. * @entry: an entry within head, could be the head itself
  377. *
  378. * This helper moves the initial part of @head, up to but
  379. * excluding @entry, from @head to @list. You should pass
  380. * in @entry an element you know is on @head. @list should
  381. * be an empty list or a list you do not care about losing
  382. * its data.
  383. * If @entry == @head, all entries on @head are moved to
  384. * @list.
  385. */
  386. static inline void list_cut_before(struct list_head *list,
  387. struct list_head *head,
  388. struct list_head *entry)
  389. {
  390. if (head->next == entry) {
  391. INIT_LIST_HEAD(list);
  392. return;
  393. }
  394. list->next = head->next;
  395. list->next->prev = list;
  396. list->prev = entry->prev;
  397. list->prev->next = list;
  398. head->next = entry;
  399. entry->prev = head;
  400. }
  401. static inline void __list_splice(const struct list_head *list,
  402. struct list_head *prev,
  403. struct list_head *next)
  404. {
  405. struct list_head *first = list->next;
  406. struct list_head *last = list->prev;
  407. first->prev = prev;
  408. prev->next = first;
  409. last->next = next;
  410. next->prev = last;
  411. }
  412. /**
  413. * list_splice - join two lists, this is designed for stacks
  414. * @list: the new list to add.
  415. * @head: the place to add it in the first list.
  416. */
  417. static inline void list_splice(const struct list_head *list,
  418. struct list_head *head)
  419. {
  420. if (!list_empty(list))
  421. __list_splice(list, head, head->next);
  422. }
  423. /**
  424. * list_splice_tail - join two lists, each list being a queue
  425. * @list: the new list to add.
  426. * @head: the place to add it in the first list.
  427. */
  428. static inline void list_splice_tail(struct list_head *list,
  429. struct list_head *head)
  430. {
  431. if (!list_empty(list))
  432. __list_splice(list, head->prev, head);
  433. }
  434. /**
  435. * list_splice_init - join two lists and reinitialise the emptied list.
  436. * @list: the new list to add.
  437. * @head: the place to add it in the first list.
  438. *
  439. * The list at @list is reinitialised
  440. */
  441. static inline void list_splice_init(struct list_head *list,
  442. struct list_head *head)
  443. {
  444. if (!list_empty(list)) {
  445. __list_splice(list, head, head->next);
  446. INIT_LIST_HEAD(list);
  447. }
  448. }
  449. /**
  450. * list_splice_tail_init - join two lists and reinitialise the emptied list
  451. * @list: the new list to add.
  452. * @head: the place to add it in the first list.
  453. *
  454. * Each of the lists is a queue.
  455. * The list at @list is reinitialised
  456. */
  457. static inline void list_splice_tail_init(struct list_head *list,
  458. struct list_head *head)
  459. {
  460. if (!list_empty(list)) {
  461. __list_splice(list, head->prev, head);
  462. INIT_LIST_HEAD(list);
  463. }
  464. }
  465. /**
  466. * list_entry - get the struct for this entry
  467. * @ptr: the &struct list_head pointer.
  468. * @type: the type of the struct this is embedded in.
  469. * @member: the name of the list_head within the struct.
  470. */
  471. #define list_entry(ptr, type, member) \
  472. container_of(ptr, type, member)
  473. /**
  474. * list_first_entry - get the first element from a list
  475. * @ptr: the list head to take the element from.
  476. * @type: the type of the struct this is embedded in.
  477. * @member: the name of the list_head within the struct.
  478. *
  479. * Note, that list is expected to be not empty.
  480. */
  481. #define list_first_entry(ptr, type, member) \
  482. list_entry((ptr)->next, type, member)
  483. /**
  484. * list_last_entry - get the last element from a list
  485. * @ptr: the list head to take the element from.
  486. * @type: the type of the struct this is embedded in.
  487. * @member: the name of the list_head within the struct.
  488. *
  489. * Note, that list is expected to be not empty.
  490. */
  491. #define list_last_entry(ptr, type, member) \
  492. list_entry((ptr)->prev, type, member)
  493. /**
  494. * list_first_entry_or_null - get the first element from a list
  495. * @ptr: the list head to take the element from.
  496. * @type: the type of the struct this is embedded in.
  497. * @member: the name of the list_head within the struct.
  498. *
  499. * Note that if the list is empty, it returns NULL.
  500. */
  501. #define list_first_entry_or_null(ptr, type, member) ({ \
  502. struct list_head *head__ = (ptr); \
  503. struct list_head *pos__ = READ_ONCE(head__->next); \
  504. pos__ != head__ ? list_entry(pos__, type, member) : NULL; \
  505. })
  506. /**
  507. * list_next_entry - get the next element in list
  508. * @pos: the type * to cursor
  509. * @member: the name of the list_head within the struct.
  510. */
  511. #define list_next_entry(pos, member) \
  512. list_entry((pos)->member.next, typeof(*(pos)), member)
  513. /**
  514. * list_next_entry_circular - get the next element in list
  515. * @pos: the type * to cursor.
  516. * @head: the list head to take the element from.
  517. * @member: the name of the list_head within the struct.
  518. *
  519. * Wraparound if pos is the last element (return the first element).
  520. * Note, that list is expected to be not empty.
  521. */
  522. #define list_next_entry_circular(pos, head, member) \
  523. (list_is_last(&(pos)->member, head) ? \
  524. list_first_entry(head, typeof(*(pos)), member) : list_next_entry(pos, member))
  525. /**
  526. * list_prev_entry - get the prev element in list
  527. * @pos: the type * to cursor
  528. * @member: the name of the list_head within the struct.
  529. */
  530. #define list_prev_entry(pos, member) \
  531. list_entry((pos)->member.prev, typeof(*(pos)), member)
  532. /**
  533. * list_prev_entry_circular - get the prev element in list
  534. * @pos: the type * to cursor.
  535. * @head: the list head to take the element from.
  536. * @member: the name of the list_head within the struct.
  537. *
  538. * Wraparound if pos is the first element (return the last element).
  539. * Note, that list is expected to be not empty.
  540. */
  541. #define list_prev_entry_circular(pos, head, member) \
  542. (list_is_first(&(pos)->member, head) ? \
  543. list_last_entry(head, typeof(*(pos)), member) : list_prev_entry(pos, member))
  544. /**
  545. * list_for_each - iterate over a list
  546. * @pos: the &struct list_head to use as a loop cursor.
  547. * @head: the head for your list.
  548. */
  549. #define list_for_each(pos, head) \
  550. for (pos = (head)->next; !list_is_head(pos, (head)); pos = pos->next)
  551. /**
  552. * list_for_each_rcu - Iterate over a list in an RCU-safe fashion
  553. * @pos: the &struct list_head to use as a loop cursor.
  554. * @head: the head for your list.
  555. */
  556. #define list_for_each_rcu(pos, head) \
  557. for (pos = rcu_dereference((head)->next); \
  558. !list_is_head(pos, (head)); \
  559. pos = rcu_dereference(pos->next))
  560. /**
  561. * list_for_each_continue - continue iteration over a list
  562. * @pos: the &struct list_head to use as a loop cursor.
  563. * @head: the head for your list.
  564. *
  565. * Continue to iterate over a list, continuing after the current position.
  566. */
  567. #define list_for_each_continue(pos, head) \
  568. for (pos = pos->next; !list_is_head(pos, (head)); pos = pos->next)
  569. /**
  570. * list_for_each_prev - iterate over a list backwards
  571. * @pos: the &struct list_head to use as a loop cursor.
  572. * @head: the head for your list.
  573. */
  574. #define list_for_each_prev(pos, head) \
  575. for (pos = (head)->prev; !list_is_head(pos, (head)); pos = pos->prev)
  576. /**
  577. * list_for_each_safe - iterate over a list safe against removal of list entry
  578. * @pos: the &struct list_head to use as a loop cursor.
  579. * @n: another &struct list_head to use as temporary storage
  580. * @head: the head for your list.
  581. */
  582. #define list_for_each_safe(pos, n, head) \
  583. for (pos = (head)->next, n = pos->next; \
  584. !list_is_head(pos, (head)); \
  585. pos = n, n = pos->next)
  586. /**
  587. * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
  588. * @pos: the &struct list_head to use as a loop cursor.
  589. * @n: another &struct list_head to use as temporary storage
  590. * @head: the head for your list.
  591. */
  592. #define list_for_each_prev_safe(pos, n, head) \
  593. for (pos = (head)->prev, n = pos->prev; \
  594. !list_is_head(pos, (head)); \
  595. pos = n, n = pos->prev)
  596. /**
  597. * list_entry_is_head - test if the entry points to the head of the list
  598. * @pos: the type * to cursor
  599. * @head: the head for your list.
  600. * @member: the name of the list_head within the struct.
  601. */
  602. #define list_entry_is_head(pos, head, member) \
  603. (&pos->member == (head))
  604. /**
  605. * list_for_each_entry - iterate over list of given type
  606. * @pos: the type * to use as a loop cursor.
  607. * @head: the head for your list.
  608. * @member: the name of the list_head within the struct.
  609. */
  610. #define list_for_each_entry(pos, head, member) \
  611. for (pos = list_first_entry(head, typeof(*pos), member); \
  612. !list_entry_is_head(pos, head, member); \
  613. pos = list_next_entry(pos, member))
  614. /**
  615. * list_for_each_entry_reverse - iterate backwards over list of given type.
  616. * @pos: the type * to use as a loop cursor.
  617. * @head: the head for your list.
  618. * @member: the name of the list_head within the struct.
  619. */
  620. #define list_for_each_entry_reverse(pos, head, member) \
  621. for (pos = list_last_entry(head, typeof(*pos), member); \
  622. !list_entry_is_head(pos, head, member); \
  623. pos = list_prev_entry(pos, member))
  624. /**
  625. * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
  626. * @pos: the type * to use as a start point
  627. * @head: the head of the list
  628. * @member: the name of the list_head within the struct.
  629. *
  630. * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
  631. */
  632. #define list_prepare_entry(pos, head, member) \
  633. ((pos) ? : list_entry(head, typeof(*pos), member))
  634. /**
  635. * list_for_each_entry_continue - continue iteration over list of given type
  636. * @pos: the type * to use as a loop cursor.
  637. * @head: the head for your list.
  638. * @member: the name of the list_head within the struct.
  639. *
  640. * Continue to iterate over list of given type, continuing after
  641. * the current position.
  642. */
  643. #define list_for_each_entry_continue(pos, head, member) \
  644. for (pos = list_next_entry(pos, member); \
  645. !list_entry_is_head(pos, head, member); \
  646. pos = list_next_entry(pos, member))
  647. /**
  648. * list_for_each_entry_continue_reverse - iterate backwards from the given point
  649. * @pos: the type * to use as a loop cursor.
  650. * @head: the head for your list.
  651. * @member: the name of the list_head within the struct.
  652. *
  653. * Start to iterate over list of given type backwards, continuing after
  654. * the current position.
  655. */
  656. #define list_for_each_entry_continue_reverse(pos, head, member) \
  657. for (pos = list_prev_entry(pos, member); \
  658. !list_entry_is_head(pos, head, member); \
  659. pos = list_prev_entry(pos, member))
  660. /**
  661. * list_for_each_entry_from - iterate over list of given type from the current point
  662. * @pos: the type * to use as a loop cursor.
  663. * @head: the head for your list.
  664. * @member: the name of the list_head within the struct.
  665. *
  666. * Iterate over list of given type, continuing from current position.
  667. */
  668. #define list_for_each_entry_from(pos, head, member) \
  669. for (; !list_entry_is_head(pos, head, member); \
  670. pos = list_next_entry(pos, member))
  671. /**
  672. * list_for_each_entry_from_reverse - iterate backwards over list of given type
  673. * from the current point
  674. * @pos: the type * to use as a loop cursor.
  675. * @head: the head for your list.
  676. * @member: the name of the list_head within the struct.
  677. *
  678. * Iterate backwards over list of given type, continuing from current position.
  679. */
  680. #define list_for_each_entry_from_reverse(pos, head, member) \
  681. for (; !list_entry_is_head(pos, head, member); \
  682. pos = list_prev_entry(pos, member))
  683. /**
  684. * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
  685. * @pos: the type * to use as a loop cursor.
  686. * @n: another type * to use as temporary storage
  687. * @head: the head for your list.
  688. * @member: the name of the list_head within the struct.
  689. */
  690. #define list_for_each_entry_safe(pos, n, head, member) \
  691. for (pos = list_first_entry(head, typeof(*pos), member), \
  692. n = list_next_entry(pos, member); \
  693. !list_entry_is_head(pos, head, member); \
  694. pos = n, n = list_next_entry(n, member))
  695. /**
  696. * list_for_each_entry_safe_continue - continue list iteration safe against removal
  697. * @pos: the type * to use as a loop cursor.
  698. * @n: another type * to use as temporary storage
  699. * @head: the head for your list.
  700. * @member: the name of the list_head within the struct.
  701. *
  702. * Iterate over list of given type, continuing after current point,
  703. * safe against removal of list entry.
  704. */
  705. #define list_for_each_entry_safe_continue(pos, n, head, member) \
  706. for (pos = list_next_entry(pos, member), \
  707. n = list_next_entry(pos, member); \
  708. !list_entry_is_head(pos, head, member); \
  709. pos = n, n = list_next_entry(n, member))
  710. /**
  711. * list_for_each_entry_safe_from - iterate over list from current point safe against removal
  712. * @pos: the type * to use as a loop cursor.
  713. * @n: another type * to use as temporary storage
  714. * @head: the head for your list.
  715. * @member: the name of the list_head within the struct.
  716. *
  717. * Iterate over list of given type from current point, safe against
  718. * removal of list entry.
  719. */
  720. #define list_for_each_entry_safe_from(pos, n, head, member) \
  721. for (n = list_next_entry(pos, member); \
  722. !list_entry_is_head(pos, head, member); \
  723. pos = n, n = list_next_entry(n, member))
  724. /**
  725. * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
  726. * @pos: the type * to use as a loop cursor.
  727. * @n: another type * to use as temporary storage
  728. * @head: the head for your list.
  729. * @member: the name of the list_head within the struct.
  730. *
  731. * Iterate backwards over list of given type, safe against removal
  732. * of list entry.
  733. */
  734. #define list_for_each_entry_safe_reverse(pos, n, head, member) \
  735. for (pos = list_last_entry(head, typeof(*pos), member), \
  736. n = list_prev_entry(pos, member); \
  737. !list_entry_is_head(pos, head, member); \
  738. pos = n, n = list_prev_entry(n, member))
  739. /**
  740. * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
  741. * @pos: the loop cursor used in the list_for_each_entry_safe loop
  742. * @n: temporary storage used in list_for_each_entry_safe
  743. * @member: the name of the list_head within the struct.
  744. *
  745. * list_safe_reset_next is not safe to use in general if the list may be
  746. * modified concurrently (eg. the lock is dropped in the loop body). An
  747. * exception to this is if the cursor element (pos) is pinned in the list,
  748. * and list_safe_reset_next is called after re-taking the lock and before
  749. * completing the current iteration of the loop body.
  750. */
  751. #define list_safe_reset_next(pos, n, member) \
  752. n = list_next_entry(pos, member)
  753. /*
  754. * Double linked lists with a single pointer list head.
  755. * Mostly useful for hash tables where the two pointer list head is
  756. * too wasteful.
  757. * You lose the ability to access the tail in O(1).
  758. */
  759. #define HLIST_HEAD_INIT { .first = NULL }
  760. #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
  761. #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
  762. static inline void INIT_HLIST_NODE(struct hlist_node *h)
  763. {
  764. h->next = NULL;
  765. h->pprev = NULL;
  766. }
  767. /**
  768. * hlist_unhashed - Has node been removed from list and reinitialized?
  769. * @h: Node to be checked
  770. *
  771. * Not that not all removal functions will leave a node in unhashed
  772. * state. For example, hlist_nulls_del_init_rcu() does leave the
  773. * node in unhashed state, but hlist_nulls_del() does not.
  774. */
  775. static inline int hlist_unhashed(const struct hlist_node *h)
  776. {
  777. return !h->pprev;
  778. }
  779. /**
  780. * hlist_unhashed_lockless - Version of hlist_unhashed for lockless use
  781. * @h: Node to be checked
  782. *
  783. * This variant of hlist_unhashed() must be used in lockless contexts
  784. * to avoid potential load-tearing. The READ_ONCE() is paired with the
  785. * various WRITE_ONCE() in hlist helpers that are defined below.
  786. */
  787. static inline int hlist_unhashed_lockless(const struct hlist_node *h)
  788. {
  789. return !READ_ONCE(h->pprev);
  790. }
  791. /**
  792. * hlist_empty - Is the specified hlist_head structure an empty hlist?
  793. * @h: Structure to check.
  794. */
  795. static inline int hlist_empty(const struct hlist_head *h)
  796. {
  797. return !READ_ONCE(h->first);
  798. }
  799. static inline void __hlist_del(struct hlist_node *n)
  800. {
  801. struct hlist_node *next = n->next;
  802. struct hlist_node **pprev = n->pprev;
  803. WRITE_ONCE(*pprev, next);
  804. if (next)
  805. WRITE_ONCE(next->pprev, pprev);
  806. }
  807. /**
  808. * hlist_del - Delete the specified hlist_node from its list
  809. * @n: Node to delete.
  810. *
  811. * Note that this function leaves the node in hashed state. Use
  812. * hlist_del_init() or similar instead to unhash @n.
  813. */
  814. static inline void hlist_del(struct hlist_node *n)
  815. {
  816. __hlist_del(n);
  817. n->next = LIST_POISON1;
  818. n->pprev = LIST_POISON2;
  819. }
  820. /**
  821. * hlist_del_init - Delete the specified hlist_node from its list and initialize
  822. * @n: Node to delete.
  823. *
  824. * Note that this function leaves the node in unhashed state.
  825. */
  826. static inline void hlist_del_init(struct hlist_node *n)
  827. {
  828. if (!hlist_unhashed(n)) {
  829. __hlist_del(n);
  830. INIT_HLIST_NODE(n);
  831. }
  832. }
  833. /**
  834. * hlist_add_head - add a new entry at the beginning of the hlist
  835. * @n: new entry to be added
  836. * @h: hlist head to add it after
  837. *
  838. * Insert a new entry after the specified head.
  839. * This is good for implementing stacks.
  840. */
  841. static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
  842. {
  843. struct hlist_node *first = h->first;
  844. WRITE_ONCE(n->next, first);
  845. if (first)
  846. WRITE_ONCE(first->pprev, &n->next);
  847. WRITE_ONCE(h->first, n);
  848. WRITE_ONCE(n->pprev, &h->first);
  849. }
  850. /**
  851. * hlist_add_before - add a new entry before the one specified
  852. * @n: new entry to be added
  853. * @next: hlist node to add it before, which must be non-NULL
  854. */
  855. static inline void hlist_add_before(struct hlist_node *n,
  856. struct hlist_node *next)
  857. {
  858. WRITE_ONCE(n->pprev, next->pprev);
  859. WRITE_ONCE(n->next, next);
  860. WRITE_ONCE(next->pprev, &n->next);
  861. WRITE_ONCE(*(n->pprev), n);
  862. }
  863. /**
  864. * hlist_add_behind - add a new entry after the one specified
  865. * @n: new entry to be added
  866. * @prev: hlist node to add it after, which must be non-NULL
  867. */
  868. static inline void hlist_add_behind(struct hlist_node *n,
  869. struct hlist_node *prev)
  870. {
  871. WRITE_ONCE(n->next, prev->next);
  872. WRITE_ONCE(prev->next, n);
  873. WRITE_ONCE(n->pprev, &prev->next);
  874. if (n->next)
  875. WRITE_ONCE(n->next->pprev, &n->next);
  876. }
  877. /**
  878. * hlist_add_fake - create a fake hlist consisting of a single headless node
  879. * @n: Node to make a fake list out of
  880. *
  881. * This makes @n appear to be its own predecessor on a headless hlist.
  882. * The point of this is to allow things like hlist_del() to work correctly
  883. * in cases where there is no list.
  884. */
  885. static inline void hlist_add_fake(struct hlist_node *n)
  886. {
  887. n->pprev = &n->next;
  888. }
  889. /**
  890. * hlist_fake: Is this node a fake hlist?
  891. * @h: Node to check for being a self-referential fake hlist.
  892. */
  893. static inline bool hlist_fake(struct hlist_node *h)
  894. {
  895. return h->pprev == &h->next;
  896. }
  897. /**
  898. * hlist_is_singular_node - is node the only element of the specified hlist?
  899. * @n: Node to check for singularity.
  900. * @h: Header for potentially singular list.
  901. *
  902. * Check whether the node is the only node of the head without
  903. * accessing head, thus avoiding unnecessary cache misses.
  904. */
  905. static inline bool
  906. hlist_is_singular_node(struct hlist_node *n, struct hlist_head *h)
  907. {
  908. return !n->next && n->pprev == &h->first;
  909. }
  910. /**
  911. * hlist_move_list - Move an hlist
  912. * @old: hlist_head for old list.
  913. * @new: hlist_head for new list.
  914. *
  915. * Move a list from one list head to another. Fixup the pprev
  916. * reference of the first entry if it exists.
  917. */
  918. static inline void hlist_move_list(struct hlist_head *old,
  919. struct hlist_head *new)
  920. {
  921. new->first = old->first;
  922. if (new->first)
  923. new->first->pprev = &new->first;
  924. old->first = NULL;
  925. }
  926. #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
  927. #define hlist_for_each(pos, head) \
  928. for (pos = (head)->first; pos ; pos = pos->next)
  929. #define hlist_for_each_safe(pos, n, head) \
  930. for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
  931. pos = n)
  932. #define hlist_entry_safe(ptr, type, member) \
  933. ({ typeof(ptr) ____ptr = (ptr); \
  934. ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
  935. })
  936. /**
  937. * hlist_for_each_entry - iterate over list of given type
  938. * @pos: the type * to use as a loop cursor.
  939. * @head: the head for your list.
  940. * @member: the name of the hlist_node within the struct.
  941. */
  942. #define hlist_for_each_entry(pos, head, member) \
  943. for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
  944. pos; \
  945. pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
  946. /**
  947. * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
  948. * @pos: the type * to use as a loop cursor.
  949. * @member: the name of the hlist_node within the struct.
  950. */
  951. #define hlist_for_each_entry_continue(pos, member) \
  952. for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
  953. pos; \
  954. pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
  955. /**
  956. * hlist_for_each_entry_from - iterate over a hlist continuing from current point
  957. * @pos: the type * to use as a loop cursor.
  958. * @member: the name of the hlist_node within the struct.
  959. */
  960. #define hlist_for_each_entry_from(pos, member) \
  961. for (; pos; \
  962. pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
  963. /**
  964. * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
  965. * @pos: the type * to use as a loop cursor.
  966. * @n: a &struct hlist_node to use as temporary storage
  967. * @head: the head for your list.
  968. * @member: the name of the hlist_node within the struct.
  969. */
  970. #define hlist_for_each_entry_safe(pos, n, head, member) \
  971. for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
  972. pos && ({ n = pos->member.next; 1; }); \
  973. pos = hlist_entry_safe(n, typeof(*pos), member))
  974. #endif