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 ===========================================================================*/ 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 ===========================================================================*/ 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 ===========================================================================*/ 109 linked_list_err_type linked_list_add(void* list_data, void *data_obj, void (*dealloc)(void*)) 110 { 111 if( list_data == NULL ) 112 { 113 LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__); 114 return eLINKED_LIST_INVALID_HANDLE; 115 } 116 117 if( data_obj == NULL ) 118 { 119 LOC_LOGE("%s: Invalid input parameter!\n", __FUNCTION__); 120 return eLINKED_LIST_INVALID_PARAMETER; 121 } 122 123 list_state* p_list = (list_state*)list_data; 124 list_element* elem = (list_element*)malloc(sizeof(list_element)); 125 if( elem == NULL ) 126 { 127 LOC_LOGE("%s: Memory allocation failed\n", __FUNCTION__); 128 return eLINKED_LIST_FAILURE_GENERAL; 129 } 130 131 /* Copy data to newly created element */ 132 elem->data_ptr = data_obj; 133 elem->next = NULL; 134 elem->prev = NULL; 135 elem->dealloc_func = dealloc; 136 137 /* Replace head element */ 138 list_element* tmp = p_list->p_head; 139 p_list->p_head = elem; 140 /* Point next to the previous head element */ 141 p_list->p_head->next = tmp; 142 143 if( tmp != NULL ) 144 { 145 tmp->prev = p_list->p_head; 146 } 147 else 148 { 149 p_list->p_tail = p_list->p_head; 150 } 151 152 return eLINKED_LIST_SUCCESS; 153 } 154 155 /*=========================================================================== 156 157 FUNCTION: linked_list_remove 158 159 ===========================================================================*/ 160 linked_list_err_type linked_list_remove(void* list_data, void **data_obj) 161 { 162 if( list_data == NULL ) 163 { 164 LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__); 165 return eLINKED_LIST_INVALID_HANDLE; 166 } 167 168 if( data_obj == NULL ) 169 { 170 LOC_LOGE("%s: Invalid input parameter!\n", __FUNCTION__); 171 return eLINKED_LIST_INVALID_PARAMETER; 172 } 173 174 list_state* p_list = (list_state*)list_data; 175 if( p_list->p_tail == NULL ) 176 { 177 return eLINKED_LIST_UNAVAILABLE_RESOURCE; 178 } 179 180 list_element* tmp = p_list->p_tail; 181 182 /* Replace tail element */ 183 p_list->p_tail = tmp->prev; 184 185 if( p_list->p_tail != NULL ) 186 { 187 p_list->p_tail->next = NULL; 188 } 189 else 190 { 191 p_list->p_head = p_list->p_tail; 192 } 193 194 /* Copy data to output param */ 195 *data_obj = tmp->data_ptr; 196 197 /* Free allocated list element */ 198 free(tmp); 199 200 return eLINKED_LIST_SUCCESS; 201 } 202 203 /*=========================================================================== 204 205 FUNCTION: linked_list_empty 206 207 ===========================================================================*/ 208 int linked_list_empty(void* list_data) 209 { 210 if( list_data == NULL ) 211 { 212 LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__); 213 return (int)eLINKED_LIST_INVALID_HANDLE; 214 } 215 else 216 { 217 list_state* p_list = (list_state*)list_data; 218 return p_list->p_head == NULL ? 1 : 0; 219 } 220 } 221 222 /*=========================================================================== 223 224 FUNCTION: linked_list_flush 225 226 ===========================================================================*/ 227 linked_list_err_type linked_list_flush(void* list_data) 228 { 229 if( list_data == NULL ) 230 { 231 LOC_LOGE("%s: Invalid list parameter!\n", __FUNCTION__); 232 return eLINKED_LIST_INVALID_HANDLE; 233 } 234 235 list_state* p_list = (list_state*)list_data; 236 237 /* Remove all dynamically allocated elements */ 238 while( p_list->p_head != NULL ) 239 { 240 list_element* tmp = p_list->p_head->next; 241 242 /* Free data pointer if told to do so. */ 243 if( p_list->p_head->dealloc_func != NULL ) 244 { 245 p_list->p_head->dealloc_func(p_list->p_head->data_ptr); 246 } 247 248 /* Free list element */ 249 free(p_list->p_head); 250 251 p_list->p_head = tmp; 252 } 253 254 p_list->p_tail = NULL; 255 256 return eLINKED_LIST_SUCCESS; 257 } 258 259 /*=========================================================================== 260 261 FUNCTION: linked_list_search 262 263 ===========================================================================*/ 264 linked_list_err_type linked_list_search(void* list_data, void **data_p, 265 bool (*equal)(void* data_0, void* data), 266 void* data_0, bool rm_if_found) 267 { 268 if( list_data == NULL || NULL == equal ) 269 { 270 LOC_LOGE("%s: Invalid list parameter! list_data %p equal %p\n", 271 __FUNCTION__, list_data, equal); 272 return eLINKED_LIST_INVALID_HANDLE; 273 } 274 275 list_state* p_list = (list_state*)list_data; 276 if( p_list->p_tail == NULL ) 277 { 278 return eLINKED_LIST_UNAVAILABLE_RESOURCE; 279 } 280 281 list_element* tmp = p_list->p_head; 282 283 if (NULL != data_p) { 284 *data_p = NULL; 285 } 286 287 while (NULL != tmp) { 288 if ((*equal)(data_0, tmp->data_ptr)) { 289 if (NULL != data_p) { 290 *data_p = tmp->data_ptr; 291 } 292 293 if (rm_if_found) { 294 if (NULL == tmp->prev) { 295 p_list->p_head = tmp->next; 296 } else { 297 tmp->prev->next = tmp->next; 298 } 299 300 if (NULL == tmp->next) { 301 p_list->p_tail = tmp->prev; 302 } else { 303 tmp->next->prev = tmp->prev; 304 } 305 306 tmp->prev = tmp->next = NULL; 307 308 // dealloc data if it is not copied out && caller 309 // has given us a dealloc function pointer. 310 if (NULL == data_p && NULL != tmp->dealloc_func) { 311 tmp->dealloc_func(tmp->data_ptr); 312 } 313 free(tmp); 314 } 315 316 tmp = NULL; 317 } else { 318 tmp = tmp->next; 319 } 320 } 321 322 return eLINKED_LIST_SUCCESS; 323 } 324 325