linked_list.c 8.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325
  1. /* Copyright (c) 2011, 2014, 2017 The Linux Foundation. All rights reserved.
  2. *
  3. * Redistribution and use in source and binary forms, with or without
  4. * modification, are permitted provided that the following conditions are
  5. * met:
  6. * * Redistributions of source code must retain the above copyright
  7. * notice, this list of conditions and the following disclaimer.
  8. * * Redistributions in binary form must reproduce the above
  9. * copyright notice, this list of conditions and the following
  10. * disclaimer in the documentation and/or other materials provided
  11. * with the distribution.
  12. * * Neither the name of The Linux Foundation nor the names of its
  13. * contributors may be used to endorse or promote products derived
  14. * from this software without specific prior written permission.
  15. *
  16. * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
  17. * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  18. * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
  19. * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
  20. * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  21. * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  22. * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  23. * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  24. * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
  25. * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
  26. * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27. */
  28. #define LOG_TAG "LocSvc_utils_ll"
  29. #include "linked_list.h"
  30. #include <stdio.h>
  31. #include <string.h>
  32. #include <stdlib.h>
  33. #include <stdint.h>
  34. #include <loc_pla.h>
  35. #include <log_util.h>
  36. typedef struct list_element {
  37. struct list_element* next;
  38. struct list_element* prev;
  39. void* data_ptr;
  40. void (*dealloc_func)(void*);
  41. }list_element;
  42. typedef struct list_state {
  43. list_element* p_head;
  44. list_element* p_tail;
  45. } list_state;
  46. /* ----------------------- END INTERNAL FUNCTIONS ---------------------------------------- */
  47. /*===========================================================================
  48. FUNCTION: linked_list_init
  49. ===========================================================================*/
  50. linked_list_err_type linked_list_init(void** list_data)
  51. {
  52. if( list_data == NULL )
  53. {
  54. LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
  55. return eLINKED_LIST_INVALID_PARAMETER;
  56. }
  57. list_state* tmp_list;
  58. tmp_list = (list_state*)calloc(1, sizeof(list_state));
  59. if( tmp_list == NULL )
  60. {
  61. LOC_LOGE("%s: Unable to allocate space for list!\n", __FUNCTION__);
  62. return eLINKED_LIST_FAILURE_GENERAL;
  63. }
  64. tmp_list->p_head = NULL;
  65. tmp_list->p_tail = NULL;
  66. *list_data = tmp_list;
  67. return eLINKED_LIST_SUCCESS;
  68. }
  69. /*===========================================================================
  70. FUNCTION: linked_list_destroy
  71. ===========================================================================*/
  72. linked_list_err_type linked_list_destroy(void** list_data)
  73. {
  74. if( list_data == NULL )
  75. {
  76. LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
  77. return eLINKED_LIST_INVALID_HANDLE;
  78. }
  79. list_state* p_list = (list_state*)*list_data;
  80. linked_list_flush(p_list);
  81. free(*list_data);
  82. *list_data = NULL;
  83. return eLINKED_LIST_SUCCESS;
  84. }
  85. /*===========================================================================
  86. FUNCTION: linked_list_add
  87. ===========================================================================*/
  88. linked_list_err_type linked_list_add(void* list_data, void *data_obj, void (*dealloc)(void*))
  89. {
  90. if( list_data == NULL )
  91. {
  92. LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
  93. return eLINKED_LIST_INVALID_HANDLE;
  94. }
  95. if( data_obj == NULL )
  96. {
  97. LOC_LOGE("%s: Invalid input parameter!\n", __FUNCTION__);
  98. return eLINKED_LIST_INVALID_PARAMETER;
  99. }
  100. list_state* p_list = (list_state*)list_data;
  101. list_element* elem = (list_element*)malloc(sizeof(list_element));
  102. if( elem == NULL )
  103. {
  104. LOC_LOGE("%s: Memory allocation failed\n", __FUNCTION__);
  105. return eLINKED_LIST_FAILURE_GENERAL;
  106. }
  107. /* Copy data to newly created element */
  108. elem->data_ptr = data_obj;
  109. elem->next = NULL;
  110. elem->prev = NULL;
  111. elem->dealloc_func = dealloc;
  112. /* Replace head element */
  113. list_element* tmp = p_list->p_head;
  114. p_list->p_head = elem;
  115. /* Point next to the previous head element */
  116. p_list->p_head->next = tmp;
  117. if( tmp != NULL )
  118. {
  119. tmp->prev = p_list->p_head;
  120. }
  121. else
  122. {
  123. p_list->p_tail = p_list->p_head;
  124. }
  125. return eLINKED_LIST_SUCCESS;
  126. }
  127. /*===========================================================================
  128. FUNCTION: linked_list_remove
  129. ===========================================================================*/
  130. linked_list_err_type linked_list_remove(void* list_data, void **data_obj)
  131. {
  132. if( list_data == NULL )
  133. {
  134. LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
  135. return eLINKED_LIST_INVALID_HANDLE;
  136. }
  137. if( data_obj == NULL )
  138. {
  139. LOC_LOGE("%s: Invalid input parameter!\n", __FUNCTION__);
  140. return eLINKED_LIST_INVALID_PARAMETER;
  141. }
  142. list_state* p_list = (list_state*)list_data;
  143. if( p_list->p_tail == NULL )
  144. {
  145. return eLINKED_LIST_UNAVAILABLE_RESOURCE;
  146. }
  147. list_element* tmp = p_list->p_tail;
  148. /* Replace tail element */
  149. p_list->p_tail = tmp->prev;
  150. if( p_list->p_tail != NULL )
  151. {
  152. p_list->p_tail->next = NULL;
  153. }
  154. else
  155. {
  156. p_list->p_head = p_list->p_tail;
  157. }
  158. /* Copy data to output param */
  159. *data_obj = tmp->data_ptr;
  160. /* Free allocated list element */
  161. free(tmp);
  162. return eLINKED_LIST_SUCCESS;
  163. }
  164. /*===========================================================================
  165. FUNCTION: linked_list_empty
  166. ===========================================================================*/
  167. int linked_list_empty(void* list_data)
  168. {
  169. if( list_data == NULL )
  170. {
  171. LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
  172. return (int)eLINKED_LIST_INVALID_HANDLE;
  173. }
  174. else
  175. {
  176. list_state* p_list = (list_state*)list_data;
  177. return p_list->p_head == NULL ? 1 : 0;
  178. }
  179. }
  180. /*===========================================================================
  181. FUNCTION: linked_list_flush
  182. ===========================================================================*/
  183. linked_list_err_type linked_list_flush(void* list_data)
  184. {
  185. if( list_data == NULL )
  186. {
  187. LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
  188. return eLINKED_LIST_INVALID_HANDLE;
  189. }
  190. list_state* p_list = (list_state*)list_data;
  191. /* Remove all dynamically allocated elements */
  192. while( p_list->p_head != NULL )
  193. {
  194. list_element* tmp = p_list->p_head->next;
  195. /* Free data pointer if told to do so. */
  196. if( p_list->p_head->dealloc_func != NULL )
  197. {
  198. p_list->p_head->dealloc_func(p_list->p_head->data_ptr);
  199. }
  200. /* Free list element */
  201. free(p_list->p_head);
  202. p_list->p_head = tmp;
  203. }
  204. p_list->p_tail = NULL;
  205. return eLINKED_LIST_SUCCESS;
  206. }
  207. /*===========================================================================
  208. FUNCTION: linked_list_search
  209. ===========================================================================*/
  210. linked_list_err_type linked_list_search(void* list_data, void **data_p,
  211. bool (*equal)(void* data_0, void* data),
  212. void* data_0, bool rm_if_found)
  213. {
  214. if( list_data == NULL || NULL == equal )
  215. {
  216. LOC_LOGE("%s: Invalid list parameter! list_data %p equal %p\n",
  217. __FUNCTION__, list_data, equal);
  218. return eLINKED_LIST_INVALID_HANDLE;
  219. }
  220. list_state* p_list = (list_state*)list_data;
  221. if( p_list->p_tail == NULL )
  222. {
  223. return eLINKED_LIST_UNAVAILABLE_RESOURCE;
  224. }
  225. list_element* tmp = p_list->p_head;
  226. if (NULL != data_p) {
  227. *data_p = NULL;
  228. }
  229. while (NULL != tmp) {
  230. if ((*equal)(data_0, tmp->data_ptr)) {
  231. if (NULL != data_p) {
  232. *data_p = tmp->data_ptr;
  233. }
  234. if (rm_if_found) {
  235. if (NULL == tmp->prev) {
  236. p_list->p_head = tmp->next;
  237. } else {
  238. tmp->prev->next = tmp->next;
  239. }
  240. if (NULL == tmp->next) {
  241. p_list->p_tail = tmp->prev;
  242. } else {
  243. tmp->next->prev = tmp->prev;
  244. }
  245. tmp->prev = tmp->next = NULL;
  246. // dealloc data if it is not copied out && caller
  247. // has given us a dealloc function pointer.
  248. if (NULL == data_p && NULL != tmp->dealloc_func) {
  249. tmp->dealloc_func(tmp->data_ptr);
  250. }
  251. free(tmp);
  252. }
  253. tmp = NULL;
  254. } else {
  255. tmp = tmp->next;
  256. }
  257. }
  258. return eLINKED_LIST_SUCCESS;
  259. }