1 /* Copyright (c) 2011, 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
29 #include "linked_list.h"
30 #include <stdio.h>
31 #include <string.h>
32
33 #define LOG_TAG "LocSvc_utils_ll"
34 #include "log_util.h"
35 #include "platform_lib_includes.h"
36 #include <stdlib.h>
37 #include <stdint.h>
38
39 typedef struct list_element {
40 struct list_element* next;
41 struct list_element* prev;
42 void* data_ptr;
43 void (*dealloc_func)(void*);
44 }list_element;
45
46 typedef struct list_state {
47 list_element* p_head;
48 list_element* p_tail;
49 } list_state;
50
51 /* ----------------------- END INTERNAL FUNCTIONS ---------------------------------------- */
52
53 /*===========================================================================
54
55 FUNCTION: linked_list_init
56
57 ===========================================================================*/
linked_list_init(void ** list_data)58 linked_list_err_type linked_list_init(void** list_data)
59 {
60 if( list_data == NULL )
61 {
62 LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
63 return eLINKED_LIST_INVALID_PARAMETER;
64 }
65
66 list_state* tmp_list;
67 tmp_list = (list_state*)calloc(1, sizeof(list_state));
68 if( tmp_list == NULL )
69 {
70 LOC_LOGE("%s: Unable to allocate space for list!\n", __FUNCTION__);
71 return eLINKED_LIST_FAILURE_GENERAL;
72 }
73
74 tmp_list->p_head = NULL;
75 tmp_list->p_tail = NULL;
76
77 *list_data = tmp_list;
78
79 return eLINKED_LIST_SUCCESS;
80 }
81
82 /*===========================================================================
83
84 FUNCTION: linked_list_destroy
85
86 ===========================================================================*/
linked_list_destroy(void ** list_data)87 linked_list_err_type linked_list_destroy(void** list_data)
88 {
89 if( list_data == NULL )
90 {
91 LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
92 return eLINKED_LIST_INVALID_HANDLE;
93 }
94
95 list_state* p_list = (list_state*)*list_data;
96
97 linked_list_flush(p_list);
98
99 free(*list_data);
100 *list_data = NULL;
101
102 return eLINKED_LIST_SUCCESS;
103 }
104
105 /*===========================================================================
106
107 FUNCTION: linked_list_add
108
109 ===========================================================================*/
linked_list_add(void * list_data,void * data_obj,void (* dealloc)(void *))110 linked_list_err_type linked_list_add(void* list_data, void *data_obj, void (*dealloc)(void*))
111 {
112 LOC_LOGD("%s: Adding to list data_obj = 0x%08X\n", __FUNCTION__, data_obj);
113 if( list_data == NULL )
114 {
115 LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
116 return eLINKED_LIST_INVALID_HANDLE;
117 }
118
119 if( data_obj == NULL )
120 {
121 LOC_LOGE("%s: Invalid input parameter!\n", __FUNCTION__);
122 return eLINKED_LIST_INVALID_PARAMETER;
123 }
124
125 list_state* p_list = (list_state*)list_data;
126 list_element* elem = (list_element*)malloc(sizeof(list_element));
127 if( elem == NULL )
128 {
129 LOC_LOGE("%s: Memory allocation failed\n", __FUNCTION__);
130 return eLINKED_LIST_FAILURE_GENERAL;
131 }
132
133 /* Copy data to newly created element */
134 elem->data_ptr = data_obj;
135 elem->next = NULL;
136 elem->prev = NULL;
137 elem->dealloc_func = dealloc;
138
139 /* Replace head element */
140 list_element* tmp = p_list->p_head;
141 p_list->p_head = elem;
142 /* Point next to the previous head element */
143 p_list->p_head->next = tmp;
144
145 if( tmp != NULL )
146 {
147 tmp->prev = p_list->p_head;
148 }
149 else
150 {
151 p_list->p_tail = p_list->p_head;
152 }
153
154 return eLINKED_LIST_SUCCESS;
155 }
156
157 /*===========================================================================
158
159 FUNCTION: linked_list_remove
160
161 ===========================================================================*/
linked_list_remove(void * list_data,void ** data_obj)162 linked_list_err_type linked_list_remove(void* list_data, void **data_obj)
163 {
164 LOC_LOGD("%s: Removing from list\n", __FUNCTION__);
165 if( list_data == NULL )
166 {
167 LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
168 return eLINKED_LIST_INVALID_HANDLE;
169 }
170
171 if( data_obj == NULL )
172 {
173 LOC_LOGE("%s: Invalid input parameter!\n", __FUNCTION__);
174 return eLINKED_LIST_INVALID_PARAMETER;
175 }
176
177 list_state* p_list = (list_state*)list_data;
178 if( p_list->p_tail == NULL )
179 {
180 return eLINKED_LIST_UNAVAILABLE_RESOURCE;
181 }
182
183 list_element* tmp = p_list->p_tail;
184
185 /* Replace tail element */
186 p_list->p_tail = tmp->prev;
187
188 if( p_list->p_tail != NULL )
189 {
190 p_list->p_tail->next = NULL;
191 }
192 else
193 {
194 p_list->p_head = p_list->p_tail;
195 }
196
197 /* Copy data to output param */
198 *data_obj = tmp->data_ptr;
199
200 /* Free allocated list element */
201 free(tmp);
202
203 return eLINKED_LIST_SUCCESS;
204 }
205
206 /*===========================================================================
207
208 FUNCTION: linked_list_empty
209
210 ===========================================================================*/
linked_list_empty(void * list_data)211 int linked_list_empty(void* list_data)
212 {
213 if( list_data == NULL )
214 {
215 LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
216 return (int)eLINKED_LIST_INVALID_HANDLE;
217 }
218 else
219 {
220 list_state* p_list = (list_state*)list_data;
221 return p_list->p_head == NULL ? 1 : 0;
222 }
223 }
224
225 /*===========================================================================
226
227 FUNCTION: linked_list_flush
228
229 ===========================================================================*/
linked_list_flush(void * list_data)230 linked_list_err_type linked_list_flush(void* list_data)
231 {
232 if( list_data == NULL )
233 {
234 LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
235 return eLINKED_LIST_INVALID_HANDLE;
236 }
237
238 list_state* p_list = (list_state*)list_data;
239
240 /* Remove all dynamically allocated elements */
241 while( p_list->p_head != NULL )
242 {
243 list_element* tmp = p_list->p_head->next;
244
245 /* Free data pointer if told to do so. */
246 if( p_list->p_head->dealloc_func != NULL )
247 {
248 p_list->p_head->dealloc_func(p_list->p_head->data_ptr);
249 }
250
251 /* Free list element */
252 free(p_list->p_head);
253
254 p_list->p_head = tmp;
255 }
256
257 p_list->p_tail = NULL;
258
259 return eLINKED_LIST_SUCCESS;
260 }
261
262 /*===========================================================================
263
264 FUNCTION: linked_list_search
265
266 ===========================================================================*/
linked_list_search(void * list_data,void ** data_p,bool (* equal)(void * data_0,void * data),void * data_0,bool rm_if_found)267 linked_list_err_type linked_list_search(void* list_data, void **data_p,
268 bool (*equal)(void* data_0, void* data),
269 void* data_0, bool rm_if_found)
270 {
271 LOC_LOGD("%s: Search the list\n", __FUNCTION__);
272 if( list_data == NULL || NULL == equal )
273 {
274 LOC_LOGE("%s: Invalid list parameter! list_data %p equal %p\n",
275 __FUNCTION__, list_data, equal);
276 return eLINKED_LIST_INVALID_HANDLE;
277 }
278
279 list_state* p_list = (list_state*)list_data;
280 if( p_list->p_tail == NULL )
281 {
282 return eLINKED_LIST_UNAVAILABLE_RESOURCE;
283 }
284
285 list_element* tmp = p_list->p_head;
286
287 if (NULL != data_p) {
288 *data_p = NULL;
289 }
290
291 while (NULL != tmp) {
292 if ((*equal)(data_0, tmp->data_ptr)) {
293 if (NULL != data_p) {
294 *data_p = tmp->data_ptr;
295 }
296
297 if (rm_if_found) {
298 if (NULL == tmp->prev) {
299 p_list->p_head = tmp->next;
300 } else {
301 tmp->prev->next = tmp->next;
302 }
303
304 if (NULL == tmp->next) {
305 p_list->p_tail = tmp->prev;
306 } else {
307 tmp->next->prev = tmp->prev;
308 }
309
310 tmp->prev = tmp->next = NULL;
311
312 // dealloc data if it is not copied out && caller
313 // has given us a dealloc function pointer.
314 if (NULL == data_p && NULL != tmp->dealloc_func) {
315 tmp->dealloc_func(tmp->data_ptr);
316 }
317 free(tmp);
318 }
319
320 tmp = NULL;
321 } else {
322 tmp = tmp->next;
323 }
324 }
325
326 return eLINKED_LIST_SUCCESS;
327 }
328
329