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
39typedef 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
46typedef 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  ===========================================================================*/
58linked_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  ===========================================================================*/
87linked_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  ===========================================================================*/
110linked_list_err_type linked_list_add(void* list_data, void *data_obj, void (*dealloc)(void*))
111{
112   LOC_LOGD("%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  ===========================================================================*/
162linked_list_err_type linked_list_remove(void* list_data, void **data_obj)
163{
164   LOC_LOGD("%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  ===========================================================================*/
211int 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  ===========================================================================*/
230linked_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  ===========================================================================*/
267linked_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_LOGD("%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