dllist.h 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408
  1. /*************************************************************************/ /*!
  2. @File
  3. @Title Double linked list header
  4. @Copyright Copyright (c) Imagination Technologies Ltd. All Rights Reserved
  5. @Description Double linked list interface
  6. @License Dual MIT/GPLv2
  7. The contents of this file are subject to the MIT license as set out below.
  8. Permission is hereby granted, free of charge, to any person obtaining a copy
  9. of this software and associated documentation files (the "Software"), to deal
  10. in the Software without restriction, including without limitation the rights
  11. to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  12. copies of the Software, and to permit persons to whom the Software is
  13. furnished to do so, subject to the following conditions:
  14. The above copyright notice and this permission notice shall be included in
  15. all copies or substantial portions of the Software.
  16. Alternatively, the contents of this file may be used under the terms of
  17. the GNU General Public License Version 2 ("GPL") in which case the provisions
  18. of GPL are applicable instead of those above.
  19. If you wish to allow use of your version of this file only under the terms of
  20. GPL, and not to allow others to use your version of this file under the terms
  21. of the MIT license, indicate your decision by deleting the provisions above
  22. and replace them with the notice and other provisions required by GPL as set
  23. out in the file called "GPL-COPYING" included in this distribution. If you do
  24. not delete the provisions above, a recipient may use your version of this file
  25. under the terms of either the MIT license or GPL.
  26. This License is also included in this distribution in the file called
  27. "MIT-COPYING".
  28. EXCEPT AS OTHERWISE STATED IN A NEGOTIATED AGREEMENT: (A) THE SOFTWARE IS
  29. PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING
  30. BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  31. PURPOSE AND NONINFRINGEMENT; AND (B) IN NO EVENT SHALL THE AUTHORS OR
  32. COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
  33. IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  34. CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  35. */ /**************************************************************************/
  36. #ifndef DLLIST_H
  37. #define DLLIST_H
  38. #include "img_types.h"
  39. #include "img_defs.h"
  40. /*!
  41. Pointer to a linked list node
  42. */
  43. typedef struct DLLIST_NODE_ *PDLLIST_NODE;
  44. /*!
  45. Node in a linked list
  46. */
  47. /*
  48. * Note: the following structure's size is architecture-dependent and clients
  49. * may need to create a mirror of the structure definition if it needs to be
  50. * used in a structure shared between host and device.
  51. * Consider such clients if any changes are made to this structure.
  52. */
  53. typedef struct DLLIST_NODE_
  54. {
  55. struct DLLIST_NODE_ *psPrevNode;
  56. struct DLLIST_NODE_ *psNextNode;
  57. } DLLIST_NODE;
  58. /*!
  59. Static initialiser
  60. */
  61. #define DECLARE_DLLIST(n) \
  62. DLLIST_NODE (n) = {&(n), &(n)}
  63. /*************************************************************************/ /*!
  64. @Function dllist_foreach_node
  65. @Description Walk through all the nodes on the list.
  66. Safe against removal of (node).
  67. @Input list_head List node to start the operation
  68. @Input node Current list node
  69. @Input next Node after the current one
  70. */
  71. /*****************************************************************************/
  72. #define dllist_foreach_node(list_head, node, next) \
  73. for ((node) = (list_head)->psNextNode, (next) = (node)->psNextNode; \
  74. (node) != (list_head); \
  75. (node) = (next), (next) = (node)->psNextNode)
  76. #define dllist_foreach_node_backwards(list_head, node, prev) \
  77. for ((node) = (list_head)->psPrevNode, (prev) = (node)->psPrevNode; \
  78. (node) != (list_head); \
  79. (node) = (prev), (prev) = (node)->psPrevNode)
  80. /*************************************************************************/ /*!
  81. @Function dllist_foreach
  82. @Description Simplification of dllist_foreach_node.
  83. Walk through all the nodes on the list.
  84. Safe against removal of currently-iterated node.
  85. Adds utility-macro dllist_cur() to typecast the current node.
  86. @Input list_head List node to start the operation
  87. */
  88. /*****************************************************************************/
  89. #define dllist_foreach(list_head) \
  90. for (DLLIST_NODE *_DllNode = (list_head).psNextNode, *_DllNext = _DllNode->psNextNode; \
  91. _DllNode != &(list_head); \
  92. _DllNode = _DllNext, _DllNext = _DllNode->psNextNode)
  93. #define dllist_foreach_backwards(list_head) \
  94. for (DLLIST_NODE *_DllNode = (list_head).psPrevNode, *_DllPrev = _DllNode->psPrevNode; \
  95. _DllNode != &(list_head); \
  96. _DllNode = _DllPrev, _DllPrev = _DllNode->psPrevNode)
  97. #define dllist_cur(type, member) IMG_CONTAINER_OF(_DllNode, type, member)
  98. /*************************************************************************/ /*!
  99. @Function dllist_init
  100. @Description Initialize a new double linked list
  101. @Input psListHead List head Node
  102. */
  103. /*****************************************************************************/
  104. static INLINE
  105. void dllist_init(PDLLIST_NODE psListHead)
  106. {
  107. psListHead->psPrevNode = psListHead;
  108. psListHead->psNextNode = psListHead;
  109. }
  110. /*************************************************************************/ /*!
  111. @Function dllist_is_empty
  112. @Description Returns whether the list is empty
  113. @Input psListHead List head Node
  114. */
  115. /*****************************************************************************/
  116. static INLINE
  117. bool dllist_is_empty(PDLLIST_NODE psListHead)
  118. {
  119. return ((psListHead->psPrevNode == psListHead)
  120. && (psListHead->psNextNode == psListHead));
  121. }
  122. /*************************************************************************/ /*!
  123. @Function dllist_add_to_head
  124. @Description Add psNewNode to head of list psListHead
  125. @Input psListHead Head Node
  126. @Input psNewNode New Node
  127. */
  128. /*****************************************************************************/
  129. static INLINE
  130. void dllist_add_to_head(PDLLIST_NODE psListHead, PDLLIST_NODE psNewNode)
  131. {
  132. PDLLIST_NODE psTmp;
  133. psTmp = psListHead->psNextNode;
  134. psListHead->psNextNode = psNewNode;
  135. psNewNode->psNextNode = psTmp;
  136. psTmp->psPrevNode = psNewNode;
  137. psNewNode->psPrevNode = psListHead;
  138. }
  139. /*************************************************************************/ /*!
  140. @Function dllist_add_to_tail
  141. @Description Add psNewNode to tail of list psListHead
  142. @Input psListHead Head Node
  143. @Input psNewNode New Node
  144. */
  145. /*****************************************************************************/
  146. static INLINE
  147. void dllist_add_to_tail(PDLLIST_NODE psListHead, PDLLIST_NODE psNewNode)
  148. {
  149. PDLLIST_NODE psTmp;
  150. psTmp = psListHead->psPrevNode;
  151. psListHead->psPrevNode = psNewNode;
  152. psNewNode->psPrevNode = psTmp;
  153. psTmp->psNextNode = psNewNode;
  154. psNewNode->psNextNode = psListHead;
  155. }
  156. /*************************************************************************/ /*!
  157. @Function dllist_node_is_in_list
  158. @Description Returns true if psNode is in a list
  159. @Input psNode List node
  160. */
  161. /*****************************************************************************/
  162. static INLINE
  163. bool dllist_node_is_in_list(PDLLIST_NODE psNode)
  164. {
  165. return (psNode->psNextNode != NULL);
  166. }
  167. /*************************************************************************/ /*!
  168. @Function dllist_get_next_node
  169. @Description Returns the list node after psListHead or NULL psListHead is
  170. the only element in the list.
  171. @Input psListHead List node to start the operation
  172. */
  173. /*****************************************************************************/
  174. static INLINE
  175. PDLLIST_NODE dllist_get_next_node(PDLLIST_NODE psListHead)
  176. {
  177. if (psListHead->psNextNode == psListHead)
  178. {
  179. return NULL;
  180. }
  181. else
  182. {
  183. return psListHead->psNextNode;
  184. }
  185. }
  186. /*************************************************************************/ /*!
  187. @Function dllist_get_prev_node
  188. @Description Returns the list node preceding psListHead or NULL if
  189. psListHead is the only element in the list.
  190. @Input psListHead List node to start the operation
  191. */
  192. /*****************************************************************************/
  193. static INLINE
  194. PDLLIST_NODE dllist_get_prev_node(PDLLIST_NODE psListHead)
  195. {
  196. if (psListHead->psPrevNode == psListHead)
  197. {
  198. return NULL;
  199. }
  200. else
  201. {
  202. return psListHead->psPrevNode;
  203. }
  204. }
  205. /*************************************************************************/ /*!
  206. @Function dllist_remove_node
  207. @Description Removes psListNode from the list where it currently belongs
  208. @Input psListNode List node to be removed
  209. */
  210. /*****************************************************************************/
  211. static INLINE
  212. void dllist_remove_node(PDLLIST_NODE psListNode)
  213. {
  214. psListNode->psNextNode->psPrevNode = psListNode->psPrevNode;
  215. psListNode->psPrevNode->psNextNode = psListNode->psNextNode;
  216. /* Clear the node to show it's not in a list */
  217. psListNode->psPrevNode = NULL;
  218. psListNode->psNextNode = NULL;
  219. }
  220. /*************************************************************************/ /*!
  221. @Function dllist_replace_head
  222. @Description Moves the list from psOldHead to psNewHead
  223. @Input psOldHead List node to be replaced. Will become a
  224. head node of an empty list.
  225. @Input psNewHead List node to be inserted. Must be an
  226. empty list head.
  227. */
  228. /*****************************************************************************/
  229. static INLINE
  230. void dllist_replace_head(PDLLIST_NODE psOldHead, PDLLIST_NODE psNewHead)
  231. {
  232. if (dllist_is_empty(psOldHead))
  233. {
  234. psNewHead->psNextNode = psNewHead;
  235. psNewHead->psPrevNode = psNewHead;
  236. }
  237. else
  238. {
  239. /* Change the neighbouring nodes */
  240. psOldHead->psNextNode->psPrevNode = psNewHead;
  241. psOldHead->psPrevNode->psNextNode = psNewHead;
  242. /* Copy the old data to the new node */
  243. psNewHead->psNextNode = psOldHead->psNextNode;
  244. psNewHead->psPrevNode = psOldHead->psPrevNode;
  245. /* Remove links to the previous list */
  246. psOldHead->psNextNode = psOldHead;
  247. psOldHead->psPrevNode = psOldHead;
  248. }
  249. }
  250. /**************************************************************************/ /*!
  251. @Function dllist_insert_list_at_head
  252. @Description Inserts psInHead list into the head of the psOutHead list.
  253. After this operation psOutHead will contain psInHead at the
  254. head of the list and the remaining elements that were
  255. already in psOutHead will be places after the psInList (so
  256. at a tail of the original list).
  257. @Input psOutHead List node psInHead will be inserted to.
  258. @Input psInHead List node to be inserted to psOutHead.
  259. After this operation this becomes an empty list.
  260. */ /***************************************************************************/
  261. static INLINE
  262. void dllist_insert_list_at_head(PDLLIST_NODE psOutHead, PDLLIST_NODE psInHead)
  263. {
  264. PDLLIST_NODE psInHeadNextNode = psInHead->psNextNode;
  265. PDLLIST_NODE psOutHeadNextNode = psOutHead->psNextNode;
  266. if (!dllist_is_empty(psInHead))
  267. {
  268. psOutHead->psNextNode = psInHeadNextNode;
  269. psInHeadNextNode->psPrevNode = psOutHead;
  270. psInHead->psPrevNode->psNextNode = psOutHeadNextNode;
  271. psOutHeadNextNode->psPrevNode = psInHead->psPrevNode;
  272. dllist_init(psInHead);
  273. }
  274. }
  275. /*************************************************************************/ /*!
  276. @Description Pointer to a dllist comparison callback function.
  277. @Input psNode Pointer to a node in a dllist.
  278. @Input psNext Pointer to psNode's next neighbour.
  279. */ /**************************************************************************/
  280. typedef bool (*DLLIST_CMP_CB)(const DLLIST_NODE *psNode, const DLLIST_NODE *psNext);
  281. /*************************************************************************/ /*!
  282. @Function dllist_sort
  283. @Description Insert-sorts the List in place
  284. The cmpr function passes the current and next node,
  285. From which the user writes the function responsible
  286. for choosing to swap order or not.
  287. The function returns true if a swap is required
  288. @Input psListHead List Head to be sorted.
  289. @Input cmpr Function pointer to use for sorting
  290. */
  291. /*****************************************************************************/
  292. static INLINE void dllist_sort(PDLLIST_NODE psListHead,
  293. DLLIST_CMP_CB cmpr)
  294. {
  295. DLLIST_NODE *node, *next;
  296. DLLIST_NODE sTempHead;
  297. dllist_init(&sTempHead);
  298. dllist_foreach_node(psListHead, node, next)
  299. {
  300. dllist_remove_node(node);
  301. dllist_add_to_head(&sTempHead, node);
  302. }
  303. while (!dllist_is_empty(&sTempHead))
  304. {
  305. DLLIST_NODE *psSmallestNode = NULL;
  306. dllist_foreach_node(&sTempHead, node, next)
  307. {
  308. if (!psSmallestNode || cmpr(psSmallestNode, node))
  309. {
  310. psSmallestNode = node;
  311. }
  312. }
  313. dllist_remove_node(psSmallestNode);
  314. dllist_add_to_tail(psListHead, psSmallestNode);
  315. }
  316. }
  317. #endif /* DLLIST_H */