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_LOGV("%s: Adding to list data_obj = 0x%p\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_LOGV("%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_LOGV("%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