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