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