Home | History | Annotate | Download | only in utils
      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   ===========================================================================*/
     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   ===========================================================================*/
     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   ===========================================================================*/
    110 linked_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   ===========================================================================*/
    162 linked_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   ===========================================================================*/
    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   ===========================================================================*/
    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   ===========================================================================*/
    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_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