dllist.h 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373
  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 Strictly Confidential.
  7. */ /**************************************************************************/
  8. #ifndef DLLIST_H
  9. #define DLLIST_H
  10. #include "img_types.h"
  11. #include "img_defs.h"
  12. /*!
  13. Pointer to a linked list node
  14. */
  15. typedef struct DLLIST_NODE_ *PDLLIST_NODE;
  16. /*!
  17. Node in a linked list
  18. */
  19. /*
  20. * Note: the following structure's size is architecture-dependent and clients
  21. * may need to create a mirror of the structure definition if it needs to be
  22. * used in a structure shared between host and device.
  23. * Consider such clients if any changes are made to this structure.
  24. */
  25. typedef struct DLLIST_NODE_
  26. {
  27. struct DLLIST_NODE_ *psPrevNode;
  28. struct DLLIST_NODE_ *psNextNode;
  29. } DLLIST_NODE;
  30. /*!
  31. Static initialiser
  32. */
  33. #define DECLARE_DLLIST(n) \
  34. DLLIST_NODE (n) = {&(n), &(n)}
  35. /*************************************************************************/ /*!
  36. @Function dllist_foreach_node
  37. @Description Walk through all the nodes on the list.
  38. Safe against removal of (node).
  39. @Input list_head List node to start the operation
  40. @Input node Current list node
  41. @Input next Node after the current one
  42. */
  43. /*****************************************************************************/
  44. #define dllist_foreach_node(list_head, node, next) \
  45. for ((node) = (list_head)->psNextNode, (next) = (node)->psNextNode; \
  46. (node) != (list_head); \
  47. (node) = (next), (next) = (node)->psNextNode)
  48. #define dllist_foreach_node_backwards(list_head, node, prev) \
  49. for ((node) = (list_head)->psPrevNode, (prev) = (node)->psPrevNode; \
  50. (node) != (list_head); \
  51. (node) = (prev), (prev) = (node)->psPrevNode)
  52. /*************************************************************************/ /*!
  53. @Function dllist_foreach
  54. @Description Simplification of dllist_foreach_node.
  55. Walk through all the nodes on the list.
  56. Safe against removal of currently-iterated node.
  57. Adds utility-macro dllist_cur() to typecast the current node.
  58. @Input list_head List node to start the operation
  59. */
  60. /*****************************************************************************/
  61. #define dllist_foreach(list_head) \
  62. for (DLLIST_NODE *_DllNode = (list_head).psNextNode, *_DllNext = _DllNode->psNextNode; \
  63. _DllNode != &(list_head); \
  64. _DllNode = _DllNext, _DllNext = _DllNode->psNextNode)
  65. #define dllist_foreach_backwards(list_head) \
  66. for (DLLIST_NODE *_DllNode = (list_head).psPrevNode, *_DllPrev = _DllNode->psPrevNode; \
  67. _DllNode != &(list_head); \
  68. _DllNode = _DllPrev, _DllPrev = _DllNode->psPrevNode)
  69. #define dllist_cur(type, member) IMG_CONTAINER_OF(_DllNode, type, member)
  70. /*************************************************************************/ /*!
  71. @Function dllist_init
  72. @Description Initialize a new double linked list
  73. @Input psListHead List head Node
  74. */
  75. /*****************************************************************************/
  76. static INLINE
  77. void dllist_init(PDLLIST_NODE psListHead)
  78. {
  79. psListHead->psPrevNode = psListHead;
  80. psListHead->psNextNode = psListHead;
  81. }
  82. /*************************************************************************/ /*!
  83. @Function dllist_is_empty
  84. @Description Returns whether the list is empty
  85. @Input psListHead List head Node
  86. */
  87. /*****************************************************************************/
  88. static INLINE
  89. bool dllist_is_empty(PDLLIST_NODE psListHead)
  90. {
  91. return ((psListHead->psPrevNode == psListHead)
  92. && (psListHead->psNextNode == psListHead));
  93. }
  94. /*************************************************************************/ /*!
  95. @Function dllist_add_to_head
  96. @Description Add psNewNode to head of list psListHead
  97. @Input psListHead Head Node
  98. @Input psNewNode New Node
  99. */
  100. /*****************************************************************************/
  101. static INLINE
  102. void dllist_add_to_head(PDLLIST_NODE psListHead, PDLLIST_NODE psNewNode)
  103. {
  104. PDLLIST_NODE psTmp;
  105. psTmp = psListHead->psNextNode;
  106. psListHead->psNextNode = psNewNode;
  107. psNewNode->psNextNode = psTmp;
  108. psTmp->psPrevNode = psNewNode;
  109. psNewNode->psPrevNode = psListHead;
  110. }
  111. /*************************************************************************/ /*!
  112. @Function dllist_add_to_tail
  113. @Description Add psNewNode to tail of list psListHead
  114. @Input psListHead Head Node
  115. @Input psNewNode New Node
  116. */
  117. /*****************************************************************************/
  118. static INLINE
  119. void dllist_add_to_tail(PDLLIST_NODE psListHead, PDLLIST_NODE psNewNode)
  120. {
  121. PDLLIST_NODE psTmp;
  122. psTmp = psListHead->psPrevNode;
  123. psListHead->psPrevNode = psNewNode;
  124. psNewNode->psPrevNode = psTmp;
  125. psTmp->psNextNode = psNewNode;
  126. psNewNode->psNextNode = psListHead;
  127. }
  128. /*************************************************************************/ /*!
  129. @Function dllist_node_is_in_list
  130. @Description Returns true if psNode is in a list
  131. @Input psNode List node
  132. */
  133. /*****************************************************************************/
  134. static INLINE
  135. bool dllist_node_is_in_list(PDLLIST_NODE psNode)
  136. {
  137. return (psNode->psNextNode != NULL);
  138. }
  139. /*************************************************************************/ /*!
  140. @Function dllist_get_next_node
  141. @Description Returns the list node after psListHead or NULL psListHead is
  142. the only element in the list.
  143. @Input psListHead List node to start the operation
  144. */
  145. /*****************************************************************************/
  146. static INLINE
  147. PDLLIST_NODE dllist_get_next_node(PDLLIST_NODE psListHead)
  148. {
  149. if (psListHead->psNextNode == psListHead)
  150. {
  151. return NULL;
  152. }
  153. else
  154. {
  155. return psListHead->psNextNode;
  156. }
  157. }
  158. /*************************************************************************/ /*!
  159. @Function dllist_get_prev_node
  160. @Description Returns the list node preceding psListHead or NULL if
  161. psListHead is the only element in the list.
  162. @Input psListHead List node to start the operation
  163. */
  164. /*****************************************************************************/
  165. static INLINE
  166. PDLLIST_NODE dllist_get_prev_node(PDLLIST_NODE psListHead)
  167. {
  168. if (psListHead->psPrevNode == psListHead)
  169. {
  170. return NULL;
  171. }
  172. else
  173. {
  174. return psListHead->psPrevNode;
  175. }
  176. }
  177. /*************************************************************************/ /*!
  178. @Function dllist_remove_node
  179. @Description Removes psListNode from the list where it currently belongs
  180. @Input psListNode List node to be removed
  181. */
  182. /*****************************************************************************/
  183. static INLINE
  184. void dllist_remove_node(PDLLIST_NODE psListNode)
  185. {
  186. psListNode->psNextNode->psPrevNode = psListNode->psPrevNode;
  187. psListNode->psPrevNode->psNextNode = psListNode->psNextNode;
  188. /* Clear the node to show it's not in a list */
  189. psListNode->psPrevNode = NULL;
  190. psListNode->psNextNode = NULL;
  191. }
  192. /*************************************************************************/ /*!
  193. @Function dllist_replace_head
  194. @Description Moves the list from psOldHead to psNewHead
  195. @Input psOldHead List node to be replaced. Will become a
  196. head node of an empty list.
  197. @Input psNewHead List node to be inserted. Must be an
  198. empty list head.
  199. */
  200. /*****************************************************************************/
  201. static INLINE
  202. void dllist_replace_head(PDLLIST_NODE psOldHead, PDLLIST_NODE psNewHead)
  203. {
  204. if (dllist_is_empty(psOldHead))
  205. {
  206. psNewHead->psNextNode = psNewHead;
  207. psNewHead->psPrevNode = psNewHead;
  208. }
  209. else
  210. {
  211. /* Change the neighbouring nodes */
  212. psOldHead->psNextNode->psPrevNode = psNewHead;
  213. psOldHead->psPrevNode->psNextNode = psNewHead;
  214. /* Copy the old data to the new node */
  215. psNewHead->psNextNode = psOldHead->psNextNode;
  216. psNewHead->psPrevNode = psOldHead->psPrevNode;
  217. /* Remove links to the previous list */
  218. psOldHead->psNextNode = psOldHead;
  219. psOldHead->psPrevNode = psOldHead;
  220. }
  221. }
  222. /**************************************************************************/ /*!
  223. @Function dllist_insert_list_at_head
  224. @Description Inserts psInHead list into the head of the psOutHead list.
  225. After this operation psOutHead will contain psInHead at the
  226. head of the list and the remaining elements that were
  227. already in psOutHead will be places after the psInList (so
  228. at a tail of the original list).
  229. @Input psOutHead List node psInHead will be inserted to.
  230. @Input psInHead List node to be inserted to psOutHead.
  231. After this operation this becomes an empty list.
  232. */ /***************************************************************************/
  233. static INLINE
  234. void dllist_insert_list_at_head(PDLLIST_NODE psOutHead, PDLLIST_NODE psInHead)
  235. {
  236. PDLLIST_NODE psInHeadNextNode = psInHead->psNextNode;
  237. PDLLIST_NODE psOutHeadNextNode = psOutHead->psNextNode;
  238. if (!dllist_is_empty(psInHead))
  239. {
  240. psOutHead->psNextNode = psInHeadNextNode;
  241. psInHeadNextNode->psPrevNode = psOutHead;
  242. psInHead->psPrevNode->psNextNode = psOutHeadNextNode;
  243. psOutHeadNextNode->psPrevNode = psInHead->psPrevNode;
  244. dllist_init(psInHead);
  245. }
  246. }
  247. /*************************************************************************/ /*!
  248. @Description Pointer to a dllist comparison callback function.
  249. @Input psNode Pointer to a node in a dllist.
  250. @Input psNext Pointer to psNode's next neighbour.
  251. */ /**************************************************************************/
  252. typedef bool (*DLLIST_CMP_CB)(const DLLIST_NODE *psNode, const DLLIST_NODE *psNext);
  253. /*************************************************************************/ /*!
  254. @Function dllist_sort
  255. @Description Insert-sorts the List in place
  256. The cmpr function passes the current and next node,
  257. From which the user writes the function responsible
  258. for choosing to swap order or not.
  259. The function returns true if a swap is required
  260. @Input psListHead List Head to be sorted.
  261. @Input cmpr Function pointer to use for sorting
  262. */
  263. /*****************************************************************************/
  264. static INLINE void dllist_sort(PDLLIST_NODE psListHead,
  265. DLLIST_CMP_CB cmpr)
  266. {
  267. DLLIST_NODE *node, *next;
  268. DLLIST_NODE sTempHead;
  269. dllist_init(&sTempHead);
  270. dllist_foreach_node(psListHead, node, next)
  271. {
  272. dllist_remove_node(node);
  273. dllist_add_to_head(&sTempHead, node);
  274. }
  275. while (!dllist_is_empty(&sTempHead))
  276. {
  277. DLLIST_NODE *psSmallestNode = NULL;
  278. dllist_foreach_node(&sTempHead, node, next)
  279. {
  280. if (!psSmallestNode || cmpr(psSmallestNode, node))
  281. {
  282. psSmallestNode = node;
  283. }
  284. }
  285. dllist_remove_node(psSmallestNode);
  286. dllist_add_to_tail(psListHead, psSmallestNode);
  287. }
  288. }
  289. #endif /* DLLIST_H */