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
38typedef 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
45typedef 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  ===========================================================================*/
57linked_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  ===========================================================================*/
86linked_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  ===========================================================================*/
109linked_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  ===========================================================================*/
161linked_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  ===========================================================================*/
210int 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  ===========================================================================*/
229linked_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  ===========================================================================*/
266linked_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