plist.h 8.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298
  1. /* SPDX-License-Identifier: GPL-2.0-or-later */
  2. /*
  3. * Descending-priority-sorted double-linked list
  4. *
  5. * (C) 2002-2003 Intel Corp
  6. * Inaky Perez-Gonzalez <inaky.perez-gonzalez@intel.com>.
  7. *
  8. * 2001-2005 (c) MontaVista Software, Inc.
  9. * Daniel Walker <dwalker@mvista.com>
  10. *
  11. * (C) 2005 Thomas Gleixner <tglx@linutronix.de>
  12. *
  13. * Simplifications of the original code by
  14. * Oleg Nesterov <oleg@tv-sign.ru>
  15. *
  16. * Based on simple lists (include/linux/list.h).
  17. *
  18. * This is a priority-sorted list of nodes; each node has a
  19. * priority from INT_MIN (highest) to INT_MAX (lowest).
  20. *
  21. * Addition is O(K), removal is O(1), change of priority of a node is
  22. * O(K) and K is the number of RT priority levels used in the system.
  23. * (1 <= K <= 99)
  24. *
  25. * This list is really a list of lists:
  26. *
  27. * - The tier 1 list is the prio_list, different priority nodes.
  28. *
  29. * - The tier 2 list is the node_list, serialized nodes.
  30. *
  31. * Simple ASCII art explanation:
  32. *
  33. * pl:prio_list (only for plist_node)
  34. * nl:node_list
  35. * HEAD| NODE(S)
  36. * |
  37. * ||------------------------------------|
  38. * ||->|pl|<->|pl|<--------------->|pl|<-|
  39. * | |10| |21| |21| |21| |40| (prio)
  40. * | | | | | | | | | | |
  41. * | | | | | | | | | | |
  42. * |->|nl|<->|nl|<->|nl|<->|nl|<->|nl|<->|nl|<-|
  43. * |-------------------------------------------|
  44. *
  45. * The nodes on the prio_list list are sorted by priority to simplify
  46. * the insertion of new nodes. There are no nodes with duplicate
  47. * priorites on the list.
  48. *
  49. * The nodes on the node_list are ordered by priority and can contain
  50. * entries which have the same priority. Those entries are ordered
  51. * FIFO
  52. *
  53. * Addition means: look for the prio_list node in the prio_list
  54. * for the priority of the node and insert it before the node_list
  55. * entry of the next prio_list node. If it is the first node of
  56. * that priority, add it to the prio_list in the right position and
  57. * insert it into the serialized node_list list
  58. *
  59. * Removal means remove it from the node_list and remove it from
  60. * the prio_list if the node_list list_head is non empty. In case
  61. * of removal from the prio_list it must be checked whether other
  62. * entries of the same priority are on the list or not. If there
  63. * is another entry of the same priority then this entry has to
  64. * replace the removed entry on the prio_list. If the entry which
  65. * is removed is the only entry of this priority then a simple
  66. * remove from both list is sufficient.
  67. *
  68. * INT_MIN is the highest priority, 0 is the medium highest, INT_MAX
  69. * is lowest priority.
  70. *
  71. * No locking is done, up to the caller.
  72. */
  73. #ifndef _LINUX_PLIST_H_
  74. #define _LINUX_PLIST_H_
  75. #include <linux/kernel.h>
  76. #include <linux/list.h>
  77. struct plist_head {
  78. struct list_head node_list;
  79. };
  80. struct plist_node {
  81. int prio;
  82. struct list_head prio_list;
  83. struct list_head node_list;
  84. };
  85. /**
  86. * PLIST_HEAD_INIT - static struct plist_head initializer
  87. * @head: struct plist_head variable name
  88. */
  89. #define PLIST_HEAD_INIT(head) \
  90. { \
  91. .node_list = LIST_HEAD_INIT((head).node_list) \
  92. }
  93. /**
  94. * PLIST_HEAD - declare and init plist_head
  95. * @head: name for struct plist_head variable
  96. */
  97. #define PLIST_HEAD(head) \
  98. struct plist_head head = PLIST_HEAD_INIT(head)
  99. /**
  100. * PLIST_NODE_INIT - static struct plist_node initializer
  101. * @node: struct plist_node variable name
  102. * @__prio: initial node priority
  103. */
  104. #define PLIST_NODE_INIT(node, __prio) \
  105. { \
  106. .prio = (__prio), \
  107. .prio_list = LIST_HEAD_INIT((node).prio_list), \
  108. .node_list = LIST_HEAD_INIT((node).node_list), \
  109. }
  110. /**
  111. * plist_head_init - dynamic struct plist_head initializer
  112. * @head: &struct plist_head pointer
  113. */
  114. static inline void
  115. plist_head_init(struct plist_head *head)
  116. {
  117. INIT_LIST_HEAD(&head->node_list);
  118. }
  119. /**
  120. * plist_node_init - Dynamic struct plist_node initializer
  121. * @node: &struct plist_node pointer
  122. * @prio: initial node priority
  123. */
  124. static inline void plist_node_init(struct plist_node *node, int prio)
  125. {
  126. node->prio = prio;
  127. INIT_LIST_HEAD(&node->prio_list);
  128. INIT_LIST_HEAD(&node->node_list);
  129. }
  130. extern void plist_add(struct plist_node *node, struct plist_head *head);
  131. extern void plist_del(struct plist_node *node, struct plist_head *head);
  132. extern void plist_requeue(struct plist_node *node, struct plist_head *head);
  133. /**
  134. * plist_for_each - iterate over the plist
  135. * @pos: the type * to use as a loop counter
  136. * @head: the head for your list
  137. */
  138. #define plist_for_each(pos, head) \
  139. list_for_each_entry(pos, &(head)->node_list, node_list)
  140. /**
  141. * plist_for_each_continue - continue iteration over the plist
  142. * @pos: the type * to use as a loop cursor
  143. * @head: the head for your list
  144. *
  145. * Continue to iterate over plist, continuing after the current position.
  146. */
  147. #define plist_for_each_continue(pos, head) \
  148. list_for_each_entry_continue(pos, &(head)->node_list, node_list)
  149. /**
  150. * plist_for_each_safe - iterate safely over a plist of given type
  151. * @pos: the type * to use as a loop counter
  152. * @n: another type * to use as temporary storage
  153. * @head: the head for your list
  154. *
  155. * Iterate over a plist of given type, safe against removal of list entry.
  156. */
  157. #define plist_for_each_safe(pos, n, head) \
  158. list_for_each_entry_safe(pos, n, &(head)->node_list, node_list)
  159. /**
  160. * plist_for_each_entry - iterate over list of given type
  161. * @pos: the type * to use as a loop counter
  162. * @head: the head for your list
  163. * @mem: the name of the list_head within the struct
  164. */
  165. #define plist_for_each_entry(pos, head, mem) \
  166. list_for_each_entry(pos, &(head)->node_list, mem.node_list)
  167. /**
  168. * plist_for_each_entry_continue - continue iteration over list of given type
  169. * @pos: the type * to use as a loop cursor
  170. * @head: the head for your list
  171. * @m: the name of the list_head within the struct
  172. *
  173. * Continue to iterate over list of given type, continuing after
  174. * the current position.
  175. */
  176. #define plist_for_each_entry_continue(pos, head, m) \
  177. list_for_each_entry_continue(pos, &(head)->node_list, m.node_list)
  178. /**
  179. * plist_for_each_entry_safe - iterate safely over list of given type
  180. * @pos: the type * to use as a loop counter
  181. * @n: another type * to use as temporary storage
  182. * @head: the head for your list
  183. * @m: the name of the list_head within the struct
  184. *
  185. * Iterate over list of given type, safe against removal of list entry.
  186. */
  187. #define plist_for_each_entry_safe(pos, n, head, m) \
  188. list_for_each_entry_safe(pos, n, &(head)->node_list, m.node_list)
  189. /**
  190. * plist_head_empty - return !0 if a plist_head is empty
  191. * @head: &struct plist_head pointer
  192. */
  193. static inline int plist_head_empty(const struct plist_head *head)
  194. {
  195. return list_empty(&head->node_list);
  196. }
  197. /**
  198. * plist_node_empty - return !0 if plist_node is not on a list
  199. * @node: &struct plist_node pointer
  200. */
  201. static inline int plist_node_empty(const struct plist_node *node)
  202. {
  203. return list_empty(&node->node_list);
  204. }
  205. /* All functions below assume the plist_head is not empty. */
  206. /**
  207. * plist_first_entry - get the struct for the first entry
  208. * @head: the &struct plist_head pointer
  209. * @type: the type of the struct this is embedded in
  210. * @member: the name of the list_head within the struct
  211. */
  212. #ifdef CONFIG_DEBUG_PLIST
  213. # define plist_first_entry(head, type, member) \
  214. ({ \
  215. WARN_ON(plist_head_empty(head)); \
  216. container_of(plist_first(head), type, member); \
  217. })
  218. #else
  219. # define plist_first_entry(head, type, member) \
  220. container_of(plist_first(head), type, member)
  221. #endif
  222. /**
  223. * plist_last_entry - get the struct for the last entry
  224. * @head: the &struct plist_head pointer
  225. * @type: the type of the struct this is embedded in
  226. * @member: the name of the list_head within the struct
  227. */
  228. #ifdef CONFIG_DEBUG_PLIST
  229. # define plist_last_entry(head, type, member) \
  230. ({ \
  231. WARN_ON(plist_head_empty(head)); \
  232. container_of(plist_last(head), type, member); \
  233. })
  234. #else
  235. # define plist_last_entry(head, type, member) \
  236. container_of(plist_last(head), type, member)
  237. #endif
  238. /**
  239. * plist_next - get the next entry in list
  240. * @pos: the type * to cursor
  241. */
  242. #define plist_next(pos) \
  243. list_next_entry(pos, node_list)
  244. /**
  245. * plist_prev - get the prev entry in list
  246. * @pos: the type * to cursor
  247. */
  248. #define plist_prev(pos) \
  249. list_prev_entry(pos, node_list)
  250. /**
  251. * plist_first - return the first node (and thus, highest priority)
  252. * @head: the &struct plist_head pointer
  253. *
  254. * Assumes the plist is _not_ empty.
  255. */
  256. static inline struct plist_node *plist_first(const struct plist_head *head)
  257. {
  258. return list_entry(head->node_list.next,
  259. struct plist_node, node_list);
  260. }
  261. /**
  262. * plist_last - return the last node (and thus, lowest priority)
  263. * @head: the &struct plist_head pointer
  264. *
  265. * Assumes the plist is _not_ empty.
  266. */
  267. static inline struct plist_node *plist_last(const struct plist_head *head)
  268. {
  269. return list_entry(head->node_list.prev,
  270. struct plist_node, node_list);
  271. }
  272. #endif