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 #define LOG_TAG "LocSvc_utils_ll"
30 
31 #include "linked_list.h"
32 #include <stdio.h>
33 #include <string.h>
34 #include <stdlib.h>
35 #include <stdint.h>
36 #include <loc_pla.h>
37 #include <log_util.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    if( list_data == NULL )
113    {
114       LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
115       return eLINKED_LIST_INVALID_HANDLE;
116    }
117 
118    if( data_obj == NULL )
119    {
120       LOC_LOGE("%s: Invalid input parameter!\n", __FUNCTION__);
121       return eLINKED_LIST_INVALID_PARAMETER;
122    }
123 
124    list_state* p_list = (list_state*)list_data;
125    list_element* elem = (list_element*)malloc(sizeof(list_element));
126    if( elem == NULL )
127    {
128       LOC_LOGE("%s: Memory allocation failed\n", __FUNCTION__);
129       return eLINKED_LIST_FAILURE_GENERAL;
130    }
131 
132    /* Copy data to newly created element */
133    elem->data_ptr = data_obj;
134    elem->next = NULL;
135    elem->prev = NULL;
136    elem->dealloc_func = dealloc;
137 
138    /* Replace head element */
139    list_element* tmp = p_list->p_head;
140    p_list->p_head = elem;
141    /* Point next to the previous head element */
142    p_list->p_head->next = tmp;
143 
144    if( tmp != NULL )
145    {
146       tmp->prev = p_list->p_head;
147    }
148    else
149    {
150       p_list->p_tail = p_list->p_head;
151    }
152 
153    return eLINKED_LIST_SUCCESS;
154 }
155 
156 /*===========================================================================
157 
158   FUNCTION:   linked_list_remove
159 
160   ===========================================================================*/
linked_list_remove(void * list_data,void ** data_obj)161 linked_list_err_type linked_list_remove(void* list_data, void **data_obj)
162 {
163    if( list_data == NULL )
164    {
165       LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
166       return eLINKED_LIST_INVALID_HANDLE;
167    }
168 
169    if( data_obj == NULL )
170    {
171       LOC_LOGE("%s: Invalid input parameter!\n", __FUNCTION__);
172       return eLINKED_LIST_INVALID_PARAMETER;
173    }
174 
175    list_state* p_list = (list_state*)list_data;
176    if( p_list->p_tail == NULL )
177    {
178       return eLINKED_LIST_UNAVAILABLE_RESOURCE;
179    }
180 
181    list_element* tmp = p_list->p_tail;
182 
183    /* Replace tail element */
184    p_list->p_tail = tmp->prev;
185 
186    if( p_list->p_tail != NULL )
187    {
188       p_list->p_tail->next = NULL;
189    }
190    else
191    {
192       p_list->p_head = p_list->p_tail;
193    }
194 
195    /* Copy data to output param */
196    *data_obj = tmp->data_ptr;
197 
198    /* Free allocated list element */
199    free(tmp);
200 
201    return eLINKED_LIST_SUCCESS;
202 }
203 
204 /*===========================================================================
205 
206   FUNCTION:   linked_list_empty
207 
208   ===========================================================================*/
linked_list_empty(void * list_data)209 int linked_list_empty(void* list_data)
210 {
211    if( list_data == NULL )
212    {
213       LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
214       return (int)eLINKED_LIST_INVALID_HANDLE;
215    }
216    else
217    {
218       list_state* p_list = (list_state*)list_data;
219       return p_list->p_head == NULL ? 1 : 0;
220    }
221 }
222 
223 /*===========================================================================
224 
225   FUNCTION:   linked_list_flush
226 
227   ===========================================================================*/
linked_list_flush(void * list_data)228 linked_list_err_type linked_list_flush(void* list_data)
229 {
230    if( list_data == NULL )
231    {
232       LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
233       return eLINKED_LIST_INVALID_HANDLE;
234    }
235 
236    list_state* p_list = (list_state*)list_data;
237 
238    /* Remove all dynamically allocated elements */
239    while( p_list->p_head != NULL )
240    {
241       list_element* tmp = p_list->p_head->next;
242 
243       /* Free data pointer if told to do so. */
244       if( p_list->p_head->dealloc_func != NULL )
245       {
246          p_list->p_head->dealloc_func(p_list->p_head->data_ptr);
247       }
248 
249       /* Free list element */
250       free(p_list->p_head);
251 
252       p_list->p_head = tmp;
253    }
254 
255    p_list->p_tail = NULL;
256 
257    return eLINKED_LIST_SUCCESS;
258 }
259 
260 /*===========================================================================
261 
262   FUNCTION:   linked_list_search
263 
264   ===========================================================================*/
linked_list_search(void * list_data,void ** data_p,bool (* equal)(void * data_0,void * data),void * data_0,bool rm_if_found)265 linked_list_err_type linked_list_search(void* list_data, void **data_p,
266                                         bool (*equal)(void* data_0, void* data),
267                                         void* data_0, bool rm_if_found)
268 {
269    if( list_data == NULL || NULL == equal )
270    {
271       LOC_LOGE("%s: Invalid list parameter! list_data %p equal %p\n",
272                __FUNCTION__, list_data, equal);
273       return eLINKED_LIST_INVALID_HANDLE;
274    }
275 
276    list_state* p_list = (list_state*)list_data;
277    if( p_list->p_tail == NULL )
278    {
279       return eLINKED_LIST_UNAVAILABLE_RESOURCE;
280    }
281 
282    list_element* tmp = p_list->p_head;
283 
284    if (NULL != data_p) {
285      *data_p = NULL;
286    }
287 
288    while (NULL != tmp) {
289      if ((*equal)(data_0, tmp->data_ptr)) {
290        if (NULL != data_p) {
291          *data_p = tmp->data_ptr;
292        }
293 
294        if (rm_if_found) {
295          if (NULL == tmp->prev) {
296            p_list->p_head = tmp->next;
297          } else {
298            tmp->prev->next = tmp->next;
299          }
300 
301          if (NULL == tmp->next) {
302            p_list->p_tail = tmp->prev;
303          } else {
304            tmp->next->prev = tmp->prev;
305          }
306 
307          tmp->prev = tmp->next = NULL;
308 
309          // dealloc data if it is not copied out && caller
310          // has given us a dealloc function pointer.
311          if (NULL == data_p && NULL != tmp->dealloc_func) {
312              tmp->dealloc_func(tmp->data_ptr);
313          }
314          free(tmp);
315        }
316 
317        tmp = NULL;
318      } else {
319        tmp = tmp->next;
320      }
321    }
322 
323    return eLINKED_LIST_SUCCESS;
324 }
325 
326