singlylinkedlist.c

00001 // Copyright (c) Microsoft. All rights reserved.
00002 // Licensed under the MIT license. See LICENSE file in the project root for full license information.
00003 
00004 #include <stdlib.h>
00005 #include "azure_c_shared_utility/gballoc.h"
00006 #include "azure_c_shared_utility/singlylinkedlist.h"
00007 #include "azure_c_shared_utility/optimize_size.h"
00008 #include "azure_c_shared_utility/xlogging.h"
00009 
00010 typedef struct LIST_ITEM_INSTANCE_TAG
00011 {
00012     const void* item;
00013     void* next;
00014 } LIST_ITEM_INSTANCE;
00015 
00016 typedef struct SINGLYLINKEDLIST_INSTANCE_TAG
00017 {
00018     LIST_ITEM_INSTANCE* head;
00019 } LIST_INSTANCE;
00020 
00021 SINGLYLINKEDLIST_HANDLE singlylinkedlist_create(void)
00022 {
00023     LIST_INSTANCE* result;
00024 
00025     /* Codes_SRS_LIST_01_001: [singlylinkedlist_create shall create a new list and return a non-NULL handle on success.] */
00026     result = (LIST_INSTANCE*)malloc(sizeof(LIST_INSTANCE));
00027     if (result != NULL)
00028     {
00029         /* Codes_SRS_LIST_01_002: [If any error occurs during the list creation, singlylinkedlist_create shall return NULL.] */
00030         result->head = NULL;
00031     }
00032 
00033     return result;
00034 }
00035 
00036 void singlylinkedlist_destroy(SINGLYLINKEDLIST_HANDLE list)
00037 {
00038     /* Codes_SRS_LIST_01_004: [If the list argument is NULL, no freeing of resources shall occur.] */
00039     if (list != NULL)
00040     {
00041         LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
00042 
00043         while (list_instance->head != NULL)
00044         {
00045             LIST_ITEM_INSTANCE* current_item = list_instance->head;
00046             list_instance->head = (LIST_ITEM_INSTANCE*)current_item->next;
00047             free(current_item);
00048         }
00049 
00050         /* Codes_SRS_LIST_01_003: [singlylinkedlist_destroy shall free all resources associated with the list identified by the handle argument.] */
00051         free(list_instance);
00052     }
00053 }
00054 
00055 LIST_ITEM_HANDLE singlylinkedlist_add(SINGLYLINKEDLIST_HANDLE list, const void* item)
00056 {
00057     LIST_ITEM_INSTANCE* result;
00058 
00059     /* Codes_SRS_LIST_01_006: [If any of the arguments is NULL, singlylinkedlist_add shall not add the item to the list and return NULL.] */
00060     if ((list == NULL) ||
00061         (item == NULL))
00062     {
00063         LogError("Invalid argument (list=%p, item=%p)", list, item);
00064         result = NULL;
00065     }
00066     else
00067     {
00068         LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
00069         result = (LIST_ITEM_INSTANCE*)malloc(sizeof(LIST_ITEM_INSTANCE));
00070 
00071         if (result == NULL)
00072         {
00073             /* Codes_SRS_LIST_01_007: [If allocating the new list node fails, singlylinkedlist_add shall return NULL.] */
00074             result = NULL;
00075         }
00076         else
00077         {
00078             /* Codes_SRS_LIST_01_005: [singlylinkedlist_add shall add one item to the tail of the list and on success it shall return a handle to the added item.] */
00079             result->next = NULL;
00080             result->item = item;
00081 
00082             if (list_instance->head == NULL)
00083             {
00084                 list_instance->head = result;
00085             }
00086             else
00087             {
00088                 LIST_ITEM_INSTANCE* current = list_instance->head;
00089                 while (current->next != NULL)
00090                 {
00091                     current = (LIST_ITEM_INSTANCE*)current->next;
00092                 }
00093 
00094                 current->next = result;
00095             }
00096         }
00097     }
00098 
00099     return result;
00100 }
00101 
00102 int singlylinkedlist_remove(SINGLYLINKEDLIST_HANDLE list, LIST_ITEM_HANDLE item)
00103 {
00104     int result;
00105 
00106     /* Codes_SRS_LIST_01_024: [If any of the arguments list or item_handle is NULL, singlylinkedlist_remove shall fail and return a non-zero value.] */
00107     if ((list == NULL) ||
00108         (item == NULL))
00109     {
00110         LogError("Invalid argument (list=%p, item=%p)", list, item);
00111         result = __FAILURE__;
00112     }
00113     else
00114     {
00115         LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
00116         LIST_ITEM_INSTANCE* current_item = list_instance->head;
00117         LIST_ITEM_INSTANCE* previous_item = NULL;
00118 
00119         while (current_item != NULL)
00120         {
00121             if (current_item == item)
00122             {
00123                 if (previous_item != NULL)
00124                 {
00125                     previous_item->next = current_item->next;
00126                 }
00127                 else
00128                 {
00129                     list_instance->head = (LIST_ITEM_INSTANCE*)current_item->next;
00130                 }
00131 
00132                 free(current_item);
00133 
00134                 break;
00135             }
00136             previous_item = current_item;
00137             current_item = (LIST_ITEM_INSTANCE*)current_item->next;
00138         }
00139 
00140         if (current_item == NULL)
00141         {
00142             /* Codes_SRS_LIST_01_025: [If the item item_handle is not found in the list, then singlylinkedlist_remove shall fail and return a non-zero value.] */
00143             result = __FAILURE__;
00144         }
00145         else
00146         {
00147             /* Codes_SRS_LIST_01_023: [singlylinkedlist_remove shall remove a list item from the list and on success it shall return 0.] */
00148             result = 0;
00149         }
00150     }
00151 
00152     return result;
00153 }
00154 
00155 LIST_ITEM_HANDLE singlylinkedlist_get_head_item(SINGLYLINKEDLIST_HANDLE list)
00156 {
00157     LIST_ITEM_HANDLE result;
00158     
00159     if (list == NULL)
00160     {
00161         /* Codes_SRS_LIST_01_009: [If the list argument is NULL, singlylinkedlist_get_head_item shall return NULL.] */
00162         LogError("Invalid argument (list=NULL)");
00163         result = NULL;
00164     }
00165     else
00166     {
00167         LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
00168 
00169         /* Codes_SRS_LIST_01_008: [singlylinkedlist_get_head_item shall return the head of the list.] */
00170         /* Codes_SRS_LIST_01_010: [If the list is empty, singlylinkedlist_get_head_item_shall_return NULL.] */
00171         result = list_instance->head;
00172     }
00173 
00174     return result;
00175 }
00176 
00177 LIST_ITEM_HANDLE singlylinkedlist_get_next_item(LIST_ITEM_HANDLE item_handle)
00178 {
00179     LIST_ITEM_HANDLE result;
00180 
00181     if (item_handle == NULL)
00182     {
00183         LogError("Invalid argument (list is NULL)");
00184         /* Codes_SRS_LIST_01_019: [If item_handle is NULL then singlylinkedlist_get_next_item shall return NULL.] */
00185         result = NULL;
00186     }
00187     else
00188     {
00189         /* Codes_SRS_LIST_01_018: [singlylinkedlist_get_next_item shall return the next item in the list following the item item_handle.] */
00190         result = (LIST_ITEM_HANDLE)((LIST_ITEM_INSTANCE*)item_handle)->next;
00191     }
00192 
00193     return result;
00194 }
00195 
00196 const void* singlylinkedlist_item_get_value(LIST_ITEM_HANDLE item_handle)
00197 {
00198     const void* result;
00199 
00200     if (item_handle == NULL)
00201     {
00202         LogError("Invalid argument (item_handle is NULL)");
00203         /* Codes_SRS_LIST_01_021: [If item_handle is NULL, singlylinkedlist_item_get_value shall return NULL.] */
00204         result = NULL;
00205     }
00206     else
00207     {
00208         /* Codes_SRS_LIST_01_020: [singlylinkedlist_item_get_value shall return the value associated with the list item identified by the item_handle argument.] */
00209         result = ((LIST_ITEM_INSTANCE*)item_handle)->item;
00210     }
00211 
00212     return result;
00213 }
00214 
00215 LIST_ITEM_HANDLE singlylinkedlist_find(SINGLYLINKEDLIST_HANDLE list, LIST_MATCH_FUNCTION match_function, const void* match_context)
00216 {
00217     LIST_ITEM_HANDLE result;
00218 
00219     if ((list == NULL) ||
00220         (match_function == NULL))
00221     {
00222         LogError("Invalid argument (list=%p, match_function=%p)", list, match_function);
00223         /* Codes_SRS_LIST_01_012: [If the list or the match_function argument is NULL, singlylinkedlist_find shall return NULL.] */
00224         result = NULL;
00225     }
00226     else
00227     {
00228         LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
00229         LIST_ITEM_INSTANCE* current = list_instance->head;
00230 
00231         /* Codes_SRS_LIST_01_011: [singlylinkedlist_find shall iterate through all items in a list and return the first one that satisfies a certain match function.] */
00232         while (current != NULL)
00233         {
00234             /* Codes_SRS_LIST_01_014: [list find shall determine whether an item satisfies the match criteria by invoking the match function for each item in the list until a matching item is found.] */
00235             /* Codes_SRS_LIST_01_013: [The match_function shall get as arguments the list item being attempted to be matched and the match_context as is.] */
00236             if (match_function((LIST_ITEM_HANDLE)current, match_context) == true)
00237             {
00238                 /* Codes_SRS_LIST_01_017: [If the match function returns true, singlylinkedlist_find shall consider that item as matching.] */
00239                 break;
00240             }
00241 
00242             /* Codes_SRS_LIST_01_016: [If the match function returns false, singlylinkedlist_find shall consider that item as not matching.] */
00243             current = (LIST_ITEM_INSTANCE*)current->next;
00244         }
00245 
00246         if (current == NULL)
00247         {
00248             /* Codes_SRS_LIST_01_015: [If the list is empty, singlylinkedlist_find shall return NULL.] */
00249             result = NULL;
00250         }
00251         else
00252         {
00253             result = current;
00254         }
00255     }
00256 
00257     return result;
00258 }
00259 
00260 int singlylinkedlist_remove_if(SINGLYLINKEDLIST_HANDLE list, LIST_CONDITION_FUNCTION condition_function, const void* match_context)
00261 {
00262     int result;
00263     /* Codes_SRS_LIST_09_001: [ If the list or the condition_function argument is NULL, singlylinkedlist_remove_if shall return non-zero value. ] */
00264     if ((list == NULL) ||
00265         (condition_function == NULL))
00266     {
00267         LogError("Invalid argument (list=%p, condition_function=%p)", list, condition_function);
00268         result = __FAILURE__;
00269     }
00270     else
00271     {
00272         LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
00273         LIST_ITEM_INSTANCE* current_item = list_instance->head;
00274         LIST_ITEM_INSTANCE* next_item = NULL;
00275         LIST_ITEM_INSTANCE* previous_item = NULL;
00276 
00277         /* Codes_SRS_LIST_09_002: [ singlylinkedlist_remove_if shall iterate through all items in a list and remove all that satisfies a certain condition function. ] */
00278         while (current_item != NULL)
00279         {
00280             bool continue_processing = false;
00281 
00282             next_item = (LIST_ITEM_INSTANCE*)current_item->next;
00283 
00284             /* Codes_SRS_LIST_09_003: [ singlylinkedlist_remove_if shall determine whether an item satisfies the condition criteria by invoking the condition function for that item. ] */
00285             /* Codes_SRS_LIST_09_004: [ If the condition function returns true, singlylinkedlist_find shall consider that item as to be removed. ] */
00286             if (condition_function(current_item->item, match_context, &continue_processing) == true)
00287             {
00288                 if (previous_item != NULL)
00289                 {
00290                     previous_item->next = next_item;
00291                 }
00292                 else
00293                 {
00294                     list_instance->head = next_item;
00295                 }
00296 
00297                 free(current_item);
00298             }
00299             /* Codes_SRS_LIST_09_005: [ If the condition function returns false, singlylinkedlist_find shall consider that item as not to be removed. ] */
00300             else
00301             {
00302                 previous_item = current_item;
00303             }
00304 
00305             /* Codes_SRS_LIST_09_006: [ If the condition function returns continue_processing as false, singlylinkedlist_remove_if shall stop iterating through the list and return. ] */
00306             if (continue_processing == false)
00307             {
00308                 break;
00309             }
00310 
00311             current_item = next_item;
00312         }
00313 
00314         /* Codes_SRS_LIST_09_007: [ If no errors occur, singlylinkedlist_remove_if shall return zero. ] */
00315         result = 0;
00316     }
00317 
00318     return result;
00319 }
00320 
00321 int singlylinkedlist_foreach(SINGLYLINKEDLIST_HANDLE list, LIST_ACTION_FUNCTION action_function, const void* action_context)
00322 {
00323     int result;
00324 
00325     /* Codes_SRS_LIST_09_008: [ If the list or the action_function argument is NULL, singlylinkedlist_foreach shall return non-zero value. ] */
00326     if ((list == NULL) ||
00327         (action_function == NULL))
00328     {
00329         LogError("Invalid argument (list=%p, action_function=%p)", list, action_function);
00330         result = __FAILURE__;
00331     }
00332     else
00333     {
00334         LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
00335         LIST_ITEM_INSTANCE* list_item = list_instance->head;
00336 
00337         while (list_item != NULL)
00338         {
00339             bool continue_processing = false;
00340 
00341             /* Codes_SRS_LIST_09_009: [ singlylinkedlist_foreach shall iterate through all items in a list and invoke action_function for each one of them. ] */
00342             action_function(list_item->item, action_context, &continue_processing);
00343 
00344             /* Codes_SRS_LIST_09_010: [ If the condition function returns continue_processing as false, singlylinkedlist_foreach shall stop iterating through the list and return. ] */
00345             if (continue_processing == false)
00346             {
00347                 break;
00348             }
00349 
00350             list_item = (LIST_ITEM_INSTANCE*)list_item->next;
00351         }
00352 
00353         /* Codes_SRS_LIST_09_011: [ If no errors occur, singlylinkedlist_foreach shall return zero. ] */
00354         result = 0;
00355     }
00356 
00357     return result;
00358 }