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 #ifdef _CRTDBG_MAP_ALLOC
00006 #include <crtdbg.h>
00007 #endif
00008 #include <stdbool.h>
00009 
00010 #include "azure_c_shared_utility/gballoc.h"
00011 #include "azure_c_shared_utility/singlylinkedlist.h"
00012 
00013 typedef struct LIST_ITEM_INSTANCE_TAG
00014 {
00015     const void* item;
00016     void* next;
00017 } LIST_ITEM_INSTANCE;
00018 
00019 typedef struct SINGLYLINKEDLIST_INSTANCE_TAG
00020 {
00021     LIST_ITEM_INSTANCE* head;
00022 } LIST_INSTANCE;
00023 
00024 SINGLYLINKEDLIST_HANDLE singlylinkedlist_create(void)
00025 {
00026     LIST_INSTANCE* result;
00027 
00028     /* Codes_SRS_LIST_01_001: [singlylinkedlist_create shall create a new list and return a non-NULL handle on success.] */
00029     result = (LIST_INSTANCE*)malloc(sizeof(LIST_INSTANCE));
00030     if (result != NULL)
00031     {
00032         /* Codes_SRS_LIST_01_002: [If any error occurs during the list creation, singlylinkedlist_create shall return NULL.] */
00033         result->head = NULL;
00034     }
00035 
00036     return result;
00037 }
00038 
00039 void singlylinkedlist_destroy(SINGLYLINKEDLIST_HANDLE list)
00040 {
00041     /* Codes_SRS_LIST_01_004: [If the list argument is NULL, no freeing of resources shall occur.] */
00042     if (list != NULL)
00043     {
00044         LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
00045 
00046         while (list_instance->head != NULL)
00047         {
00048             LIST_ITEM_INSTANCE* current_item = list_instance->head;
00049             list_instance->head = (LIST_ITEM_INSTANCE*)current_item->next;
00050             free(current_item);
00051         }
00052 
00053         /* Codes_SRS_LIST_01_003: [singlylinkedlist_destroy shall free all resources associated with the list identified by the handle argument.] */
00054         free(list_instance);
00055     }
00056 }
00057 
00058 LIST_ITEM_HANDLE singlylinkedlist_add(SINGLYLINKEDLIST_HANDLE list, const void* item)
00059 {
00060     LIST_ITEM_INSTANCE* result;
00061 
00062     /* 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.] */
00063     if ((list == NULL) ||
00064         (item == NULL))
00065     {
00066         result = NULL;
00067     }
00068     else
00069     {
00070         LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
00071         result = (LIST_ITEM_INSTANCE*)malloc(sizeof(LIST_ITEM_INSTANCE));
00072 
00073         if (result == NULL)
00074         {
00075             /* Codes_SRS_LIST_01_007: [If allocating the new list node fails, singlylinkedlist_add shall return NULL.] */
00076             result = NULL;
00077         }
00078         else
00079         {
00080             /* 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.] */
00081             result->next = NULL;
00082             result->item = item;
00083 
00084             if (list_instance->head == NULL)
00085             {
00086                 list_instance->head = result;
00087             }
00088             else
00089             {
00090                 LIST_ITEM_INSTANCE* current = list_instance->head;
00091                 while (current->next != NULL)
00092                 {
00093                     current = (LIST_ITEM_INSTANCE*)current->next;
00094                 }
00095 
00096                 current->next = result;
00097             }
00098         }
00099     }
00100 
00101     return result;
00102 }
00103 
00104 int singlylinkedlist_remove(SINGLYLINKEDLIST_HANDLE list, LIST_ITEM_HANDLE item)
00105 {
00106     int result;
00107 
00108     /* 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.] */
00109     if ((list == NULL) ||
00110         (item == NULL))
00111     {
00112         result = __LINE__;
00113     }
00114     else
00115     {
00116         LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
00117         LIST_ITEM_INSTANCE* current_item = list_instance->head;
00118         LIST_ITEM_INSTANCE* previous_item = NULL;
00119 
00120         while (current_item != NULL)
00121         {
00122             if (current_item == item)
00123             {
00124                 if (previous_item != NULL)
00125                 {
00126                     previous_item->next = current_item->next;
00127                 }
00128                 else
00129                 {
00130                     list_instance->head = (LIST_ITEM_INSTANCE*)current_item->next;
00131                 }
00132 
00133                 free(current_item);
00134 
00135                 break;
00136             }
00137             previous_item = current_item;
00138             current_item = (LIST_ITEM_INSTANCE*)current_item->next;
00139         }
00140 
00141         if (current_item == NULL)
00142         {
00143             /* 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.] */
00144             result = __LINE__;
00145         }
00146         else
00147         {
00148             /* Codes_SRS_LIST_01_023: [singlylinkedlist_remove shall remove a list item from the list and on success it shall return 0.] */
00149             result = 0;
00150         }
00151     }
00152 
00153     return result;
00154 }
00155 
00156 LIST_ITEM_HANDLE singlylinkedlist_get_head_item(SINGLYLINKEDLIST_HANDLE list)
00157 {
00158     LIST_ITEM_HANDLE result;
00159     
00160     if (list == NULL)
00161     {
00162         /* Codes_SRS_LIST_01_009: [If the list argument is NULL, singlylinkedlist_get_head_item shall return 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         /* Codes_SRS_LIST_01_019: [If item_handle is NULL then singlylinkedlist_get_next_item shall return NULL.] */
00184         result = NULL;
00185     }
00186     else
00187     {
00188         /* Codes_SRS_LIST_01_018: [singlylinkedlist_get_next_item shall return the next item in the list following the item item_handle.] */
00189         result = (LIST_ITEM_HANDLE)((LIST_ITEM_INSTANCE*)item_handle)->next;
00190     }
00191 
00192     return result;
00193 }
00194 
00195 const void* singlylinkedlist_item_get_value(LIST_ITEM_HANDLE item_handle)
00196 {
00197     const void* result;
00198 
00199     if (item_handle == NULL)
00200     {
00201         /* Codes_SRS_LIST_01_021: [If item_handle is NULL, singlylinkedlist_item_get_value shall return NULL.] */
00202         result = NULL;
00203     }
00204     else
00205     {
00206         /* Codes_SRS_LIST_01_020: [singlylinkedlist_item_get_value shall return the value associated with the list item identified by the item_handle argument.] */
00207         result = ((LIST_ITEM_INSTANCE*)item_handle)->item;
00208     }
00209 
00210     return result;
00211 }
00212 
00213 LIST_ITEM_HANDLE singlylinkedlist_find(SINGLYLINKEDLIST_HANDLE list, LIST_MATCH_FUNCTION match_function, const void* match_context)
00214 {
00215     LIST_ITEM_HANDLE result;
00216 
00217     if ((list == NULL) ||
00218         (match_function == NULL))
00219     {
00220         /* Codes_SRS_LIST_01_012: [If the list or the match_function argument is NULL, singlylinkedlist_find shall return NULL.] */
00221         result = NULL;
00222     }
00223     else
00224     {
00225         LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
00226         LIST_ITEM_INSTANCE* current = list_instance->head;
00227 
00228         /* 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.] */
00229         while (current != NULL)
00230         {
00231             /* 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.] */
00232             /* 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.] */
00233             if (match_function((LIST_ITEM_HANDLE)current, match_context) == true)
00234             {
00235                 /* Codes_SRS_LIST_01_017: [If the match function returns true, singlylinkedlist_find shall consider that item as matching.] */
00236                 break;
00237             }
00238 
00239             /* Codes_SRS_LIST_01_016: [If the match function returns false, singlylinkedlist_find shall consider that item as not matching.] */
00240             current = (LIST_ITEM_INSTANCE*)current->next;
00241         }
00242 
00243         if (current == NULL)
00244         {
00245             /* Codes_SRS_LIST_01_015: [If the list is empty, singlylinkedlist_find shall return NULL.] */
00246             result = NULL;
00247         }
00248         else
00249         {
00250             result = current;
00251         }
00252     }
00253 
00254     return result;
00255 }