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    //LOC_LOGV("%s: Adding to list data_obj = 0x%08X\n", __FUNCTION__, data_obj);
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    //LOC_LOGV("%s: Removing from list\n", __FUNCTION__);
164    if( list_data == NULL )
165    {
166       LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
167       return eLINKED_LIST_INVALID_HANDLE;
168    }
169 
170    if( data_obj == NULL )
171    {
172       LOC_LOGE("%s: Invalid input parameter!\n", __FUNCTION__);
173       return eLINKED_LIST_INVALID_PARAMETER;
174    }
175 
176    list_state* p_list = (list_state*)list_data;
177    if( p_list->p_tail == NULL )
178    {
179       return eLINKED_LIST_UNAVAILABLE_RESOURCE;
180    }
181 
182    list_element* tmp = p_list->p_tail;
183 
184    /* Replace tail element */
185    p_list->p_tail = tmp->prev;
186 
187    if( p_list->p_tail != NULL )
188    {
189       p_list->p_tail->next = NULL;
190    }
191    else
192    {
193       p_list->p_head = p_list->p_tail;
194    }
195 
196    /* Copy data to output param */
197    *data_obj = tmp->data_ptr;
198 
199    /* Free allocated list element */
200    free(tmp);
201 
202    return eLINKED_LIST_SUCCESS;
203 }
204 
205 /*===========================================================================
206 
207   FUNCTION:   linked_list_empty
208 
209   ===========================================================================*/
linked_list_empty(void * list_data)210 int linked_list_empty(void* list_data)
211 {
212    if( list_data == NULL )
213    {
214       LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
215       return (int)eLINKED_LIST_INVALID_HANDLE;
216    }
217    else
218    {
219       list_state* p_list = (list_state*)list_data;
220       return p_list->p_head == NULL ? 1 : 0;
221    }
222 }
223 
224 /*===========================================================================
225 
226   FUNCTION:   linked_list_flush
227 
228   ===========================================================================*/
linked_list_flush(void * list_data)229 linked_list_err_type linked_list_flush(void* list_data)
230 {
231    if( list_data == NULL )
232    {
233       LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__);
234       return eLINKED_LIST_INVALID_HANDLE;
235    }
236 
237    list_state* p_list = (list_state*)list_data;
238 
239    /* Remove all dynamically allocated elements */
240    while( p_list->p_head != NULL )
241    {
242       list_element* tmp = p_list->p_head->next;
243 
244       /* Free data pointer if told to do so. */
245       if( p_list->p_head->dealloc_func != NULL )
246       {
247          p_list->p_head->dealloc_func(p_list->p_head->data_ptr);
248       }
249 
250       /* Free list element */
251       free(p_list->p_head);
252 
253       p_list->p_head = tmp;
254    }
255 
256    p_list->p_tail = NULL;
257 
258    return eLINKED_LIST_SUCCESS;
259 }
260 
261 /*===========================================================================
262 
263   FUNCTION:   linked_list_search
264 
265   ===========================================================================*/
linked_list_search(void * list_data,void ** data_p,bool (* equal)(void * data_0,void * data),void * data_0,bool rm_if_found)266 linked_list_err_type linked_list_search(void* list_data, void **data_p,
267                                         bool (*equal)(void* data_0, void* data),
268                                         void* data_0, bool rm_if_found)
269 {
270    //LOC_LOGV("%s: Search the list\n", __FUNCTION__);
271    if( list_data == NULL || NULL == equal )
272    {
273       LOC_LOGE("%s: Invalid list parameter! list_data %p equal %p\n",
274                __FUNCTION__, list_data, equal);
275       return eLINKED_LIST_INVALID_HANDLE;
276    }
277 
278    list_state* p_list = (list_state*)list_data;
279    if( p_list->p_tail == NULL )
280    {
281       return eLINKED_LIST_UNAVAILABLE_RESOURCE;
282    }
283 
284    list_element* tmp = p_list->p_head;
285 
286    if (NULL != data_p) {
287      *data_p = NULL;
288    }
289 
290    while (NULL != tmp) {
291      if ((*equal)(data_0, tmp->data_ptr)) {
292        if (NULL != data_p) {
293          *data_p = tmp->data_ptr;
294        }
295 
296        if (rm_if_found) {
297          if (NULL == tmp->prev) {
298            p_list->p_head = tmp->next;
299          } else {
300            tmp->prev->next = tmp->next;
301          }
302 
303          if (NULL == tmp->next) {
304            p_list->p_tail = tmp->prev;
305          } else {
306            tmp->next->prev = tmp->prev;
307          }
308 
309          tmp->prev = tmp->next = NULL;
310 
311          // dealloc data if it is not copied out && caller
312          // has given us a dealloc function pointer.
313          if (NULL == data_p && NULL != tmp->dealloc_func) {
314              tmp->dealloc_func(tmp->data_ptr);
315          }
316          free(tmp);
317        }
318 
319        tmp = NULL;
320      } else {
321        tmp = tmp->next;
322      }
323    }
324 
325    return eLINKED_LIST_SUCCESS;
326 }
327 
328