[388] | 1 | // Copyright (c) Microsoft. All rights reserved.
|
---|
| 2 | // Licensed under the MIT license. See LICENSE file in the project root for full license information.
|
---|
| 3 |
|
---|
| 4 | #include <stdlib.h>
|
---|
| 5 | #include "azure_c_shared_utility/gballoc.h"
|
---|
| 6 | #include "azure_c_shared_utility/singlylinkedlist.h"
|
---|
| 7 | #include "azure_c_shared_utility/optimize_size.h"
|
---|
| 8 | #include "azure_c_shared_utility/xlogging.h"
|
---|
| 9 |
|
---|
| 10 | typedef struct LIST_ITEM_INSTANCE_TAG
|
---|
| 11 | {
|
---|
| 12 | const void* item;
|
---|
| 13 | void* next;
|
---|
| 14 | } LIST_ITEM_INSTANCE;
|
---|
| 15 |
|
---|
| 16 | typedef struct SINGLYLINKEDLIST_INSTANCE_TAG
|
---|
| 17 | {
|
---|
| 18 | LIST_ITEM_INSTANCE* head;
|
---|
| 19 | LIST_ITEM_INSTANCE* tail;
|
---|
| 20 | } LIST_INSTANCE;
|
---|
| 21 |
|
---|
| 22 | SINGLYLINKEDLIST_HANDLE singlylinkedlist_create(void)
|
---|
| 23 | {
|
---|
| 24 | LIST_INSTANCE* result;
|
---|
| 25 |
|
---|
| 26 | /* Codes_SRS_LIST_01_001: [singlylinkedlist_create shall create a new list and return a non-NULL handle on success.] */
|
---|
| 27 | result = (LIST_INSTANCE*)malloc(sizeof(LIST_INSTANCE));
|
---|
| 28 | if (result != NULL)
|
---|
| 29 | {
|
---|
| 30 | /* Codes_SRS_LIST_01_002: [If any error occurs during the list creation, singlylinkedlist_create shall return NULL.] */
|
---|
| 31 | result->head = NULL;
|
---|
| 32 | result->tail = NULL;
|
---|
| 33 | }
|
---|
| 34 |
|
---|
| 35 | return result;
|
---|
| 36 | }
|
---|
| 37 |
|
---|
| 38 | void singlylinkedlist_destroy(SINGLYLINKEDLIST_HANDLE list)
|
---|
| 39 | {
|
---|
| 40 | /* Codes_SRS_LIST_01_004: [If the list argument is NULL, no freeing of resources shall occur.] */
|
---|
| 41 | if (list != NULL)
|
---|
| 42 | {
|
---|
| 43 | LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
|
---|
| 44 |
|
---|
| 45 | while (list_instance->head != NULL)
|
---|
| 46 | {
|
---|
| 47 | LIST_ITEM_INSTANCE* current_item = list_instance->head;
|
---|
| 48 | list_instance->head = (LIST_ITEM_INSTANCE*)current_item->next;
|
---|
| 49 | free(current_item);
|
---|
| 50 | }
|
---|
| 51 |
|
---|
| 52 | /* Codes_SRS_LIST_01_003: [singlylinkedlist_destroy shall free all resources associated with the list identified by the handle argument.] */
|
---|
| 53 | free(list_instance);
|
---|
| 54 | }
|
---|
| 55 | }
|
---|
| 56 |
|
---|
| 57 | LIST_ITEM_HANDLE singlylinkedlist_add(SINGLYLINKEDLIST_HANDLE list, const void* item)
|
---|
| 58 | {
|
---|
| 59 | LIST_ITEM_INSTANCE* result;
|
---|
| 60 |
|
---|
| 61 | /* 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.] */
|
---|
| 62 | if ((list == NULL) ||
|
---|
| 63 | (item == NULL))
|
---|
| 64 | {
|
---|
| 65 | LogError("Invalid argument (list=%p, item=%p)", list, item);
|
---|
| 66 | result = NULL;
|
---|
| 67 | }
|
---|
| 68 | else
|
---|
| 69 | {
|
---|
| 70 | LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
|
---|
| 71 | result = (LIST_ITEM_INSTANCE*)malloc(sizeof(LIST_ITEM_INSTANCE));
|
---|
| 72 |
|
---|
| 73 | if (result == NULL)
|
---|
| 74 | {
|
---|
| 75 | /* Codes_SRS_LIST_01_007: [If allocating the new list node fails, singlylinkedlist_add shall return NULL.] */
|
---|
| 76 | /*return as is*/
|
---|
| 77 | }
|
---|
| 78 | else
|
---|
| 79 | {
|
---|
| 80 | /* 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.] */
|
---|
| 81 | result->next = NULL;
|
---|
| 82 | result->item = item;
|
---|
| 83 |
|
---|
| 84 | if (list_instance->head == NULL)
|
---|
| 85 | {
|
---|
| 86 | list_instance->head = result;
|
---|
| 87 | list_instance->tail = result;
|
---|
| 88 | }
|
---|
| 89 | else
|
---|
| 90 | {
|
---|
| 91 | list_instance->tail->next = result;
|
---|
| 92 | list_instance->tail = result;
|
---|
| 93 | }
|
---|
| 94 | }
|
---|
| 95 | }
|
---|
| 96 |
|
---|
| 97 | return result;
|
---|
| 98 | }
|
---|
| 99 |
|
---|
| 100 | int singlylinkedlist_remove(SINGLYLINKEDLIST_HANDLE list, LIST_ITEM_HANDLE item)
|
---|
| 101 | {
|
---|
| 102 | int result;
|
---|
| 103 |
|
---|
| 104 | /* 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.] */
|
---|
| 105 | if ((list == NULL) ||
|
---|
| 106 | (item == NULL))
|
---|
| 107 | {
|
---|
| 108 | LogError("Invalid argument (list=%p, item=%p)", list, item);
|
---|
| 109 | result = MU_FAILURE;
|
---|
| 110 | }
|
---|
| 111 | else
|
---|
| 112 | {
|
---|
| 113 | LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
|
---|
| 114 | LIST_ITEM_INSTANCE* current_item = list_instance->head;
|
---|
| 115 | LIST_ITEM_INSTANCE* previous_item = NULL;
|
---|
| 116 |
|
---|
| 117 | while (current_item != NULL)
|
---|
| 118 | {
|
---|
| 119 | if (current_item == item)
|
---|
| 120 | {
|
---|
| 121 | if (previous_item != NULL)
|
---|
| 122 | {
|
---|
| 123 | previous_item->next = current_item->next;
|
---|
| 124 | }
|
---|
| 125 | else
|
---|
| 126 | {
|
---|
| 127 | list_instance->head = (LIST_ITEM_INSTANCE*)current_item->next;
|
---|
| 128 | }
|
---|
| 129 |
|
---|
| 130 | if (current_item == list_instance->tail)
|
---|
| 131 | {
|
---|
| 132 | list_instance->tail = previous_item;
|
---|
| 133 | }
|
---|
| 134 |
|
---|
| 135 | free(current_item);
|
---|
| 136 |
|
---|
| 137 | break;
|
---|
| 138 | }
|
---|
| 139 |
|
---|
| 140 | previous_item = current_item;
|
---|
| 141 | current_item = (LIST_ITEM_INSTANCE*)current_item->next;
|
---|
| 142 | }
|
---|
| 143 |
|
---|
| 144 | if (current_item == NULL)
|
---|
| 145 | {
|
---|
| 146 | /* 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.] */
|
---|
| 147 | result = MU_FAILURE;
|
---|
| 148 | }
|
---|
| 149 | else
|
---|
| 150 | {
|
---|
| 151 | /* Codes_SRS_LIST_01_023: [singlylinkedlist_remove shall remove a list item from the list and on success it shall return 0.] */
|
---|
| 152 | result = 0;
|
---|
| 153 | }
|
---|
| 154 | }
|
---|
| 155 |
|
---|
| 156 | return result;
|
---|
| 157 | }
|
---|
| 158 |
|
---|
| 159 | LIST_ITEM_HANDLE singlylinkedlist_get_head_item(SINGLYLINKEDLIST_HANDLE list)
|
---|
| 160 | {
|
---|
| 161 | LIST_ITEM_HANDLE result;
|
---|
| 162 |
|
---|
| 163 | if (list == NULL)
|
---|
| 164 | {
|
---|
| 165 | /* Codes_SRS_LIST_01_009: [If the list argument is NULL, singlylinkedlist_get_head_item shall return NULL.] */
|
---|
| 166 | LogError("Invalid argument (list=NULL)");
|
---|
| 167 | result = NULL;
|
---|
| 168 | }
|
---|
| 169 | else
|
---|
| 170 | {
|
---|
| 171 | LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
|
---|
| 172 |
|
---|
| 173 | /* Codes_SRS_LIST_01_008: [singlylinkedlist_get_head_item shall return the head of the list.] */
|
---|
| 174 | /* Codes_SRS_LIST_01_010: [If the list is empty, singlylinkedlist_get_head_item_shall_return NULL.] */
|
---|
| 175 | result = list_instance->head;
|
---|
| 176 | }
|
---|
| 177 |
|
---|
| 178 | return result;
|
---|
| 179 | }
|
---|
| 180 |
|
---|
| 181 | LIST_ITEM_HANDLE singlylinkedlist_get_next_item(LIST_ITEM_HANDLE item_handle)
|
---|
| 182 | {
|
---|
| 183 | LIST_ITEM_HANDLE result;
|
---|
| 184 |
|
---|
| 185 | if (item_handle == NULL)
|
---|
| 186 | {
|
---|
| 187 | LogError("Invalid argument (list is NULL)");
|
---|
| 188 | /* Codes_SRS_LIST_01_019: [If item_handle is NULL then singlylinkedlist_get_next_item shall return NULL.] */
|
---|
| 189 | result = NULL;
|
---|
| 190 | }
|
---|
| 191 | else
|
---|
| 192 | {
|
---|
| 193 | /* Codes_SRS_LIST_01_018: [singlylinkedlist_get_next_item shall return the next item in the list following the item item_handle.] */
|
---|
| 194 | result = (LIST_ITEM_HANDLE)((LIST_ITEM_INSTANCE*)item_handle)->next;
|
---|
| 195 | }
|
---|
| 196 |
|
---|
| 197 | return result;
|
---|
| 198 | }
|
---|
| 199 |
|
---|
| 200 | const void* singlylinkedlist_item_get_value(LIST_ITEM_HANDLE item_handle)
|
---|
| 201 | {
|
---|
| 202 | const void* result;
|
---|
| 203 |
|
---|
| 204 | if (item_handle == NULL)
|
---|
| 205 | {
|
---|
| 206 | LogError("Invalid argument (item_handle is NULL)");
|
---|
| 207 | /* Codes_SRS_LIST_01_021: [If item_handle is NULL, singlylinkedlist_item_get_value shall return NULL.] */
|
---|
| 208 | result = NULL;
|
---|
| 209 | }
|
---|
| 210 | else
|
---|
| 211 | {
|
---|
| 212 | /* Codes_SRS_LIST_01_020: [singlylinkedlist_item_get_value shall return the value associated with the list item identified by the item_handle argument.] */
|
---|
| 213 | result = ((LIST_ITEM_INSTANCE*)item_handle)->item;
|
---|
| 214 | }
|
---|
| 215 |
|
---|
| 216 | return result;
|
---|
| 217 | }
|
---|
| 218 |
|
---|
| 219 | LIST_ITEM_HANDLE singlylinkedlist_find(SINGLYLINKEDLIST_HANDLE list, LIST_MATCH_FUNCTION match_function, const void* match_context)
|
---|
| 220 | {
|
---|
| 221 | LIST_ITEM_HANDLE result;
|
---|
| 222 |
|
---|
| 223 | if ((list == NULL) ||
|
---|
| 224 | (match_function == NULL))
|
---|
| 225 | {
|
---|
| 226 | LogError("Invalid argument (list=%p, match_function=%p)", list, match_function);
|
---|
| 227 | /* Codes_SRS_LIST_01_012: [If the list or the match_function argument is NULL, singlylinkedlist_find shall return NULL.] */
|
---|
| 228 | result = NULL;
|
---|
| 229 | }
|
---|
| 230 | else
|
---|
| 231 | {
|
---|
| 232 | LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
|
---|
| 233 | LIST_ITEM_INSTANCE* current = list_instance->head;
|
---|
| 234 |
|
---|
| 235 | /* 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.] */
|
---|
| 236 | while (current != NULL)
|
---|
| 237 | {
|
---|
| 238 | /* 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.] */
|
---|
| 239 | /* 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.] */
|
---|
| 240 | if (match_function((LIST_ITEM_HANDLE)current, match_context) == true)
|
---|
| 241 | {
|
---|
| 242 | /* Codes_SRS_LIST_01_017: [If the match function returns true, singlylinkedlist_find shall consider that item as matching.] */
|
---|
| 243 | break;
|
---|
| 244 | }
|
---|
| 245 |
|
---|
| 246 | /* Codes_SRS_LIST_01_016: [If the match function returns false, singlylinkedlist_find shall consider that item as not matching.] */
|
---|
| 247 | current = (LIST_ITEM_INSTANCE*)current->next;
|
---|
| 248 | }
|
---|
| 249 |
|
---|
| 250 | if (current == NULL)
|
---|
| 251 | {
|
---|
| 252 | /* Codes_SRS_LIST_01_015: [If the list is empty, singlylinkedlist_find shall return NULL.] */
|
---|
| 253 | result = NULL;
|
---|
| 254 | }
|
---|
| 255 | else
|
---|
| 256 | {
|
---|
| 257 | result = current;
|
---|
| 258 | }
|
---|
| 259 | }
|
---|
| 260 |
|
---|
| 261 | return result;
|
---|
| 262 | }
|
---|
| 263 |
|
---|
| 264 | int singlylinkedlist_remove_if(SINGLYLINKEDLIST_HANDLE list, LIST_CONDITION_FUNCTION condition_function, const void* match_context)
|
---|
| 265 | {
|
---|
| 266 | int result;
|
---|
| 267 | /* Codes_SRS_LIST_09_001: [ If the list or the condition_function argument is NULL, singlylinkedlist_remove_if shall return non-zero value. ] */
|
---|
| 268 | if ((list == NULL) ||
|
---|
| 269 | (condition_function == NULL))
|
---|
| 270 | {
|
---|
| 271 | LogError("Invalid argument (list=%p, condition_function=%p)", list, condition_function);
|
---|
| 272 | result = MU_FAILURE;
|
---|
| 273 | }
|
---|
| 274 | else
|
---|
| 275 | {
|
---|
| 276 | LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
|
---|
| 277 | LIST_ITEM_INSTANCE* current_item = list_instance->head;
|
---|
| 278 | LIST_ITEM_INSTANCE* next_item = NULL;
|
---|
| 279 | LIST_ITEM_INSTANCE* previous_item = NULL;
|
---|
| 280 |
|
---|
| 281 | /* 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. ] */
|
---|
| 282 | while (current_item != NULL)
|
---|
| 283 | {
|
---|
| 284 | bool continue_processing = false;
|
---|
| 285 |
|
---|
| 286 | next_item = (LIST_ITEM_INSTANCE*)current_item->next;
|
---|
| 287 |
|
---|
| 288 | /* 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. ] */
|
---|
| 289 | /* Codes_SRS_LIST_09_004: [ If the condition function returns true, singlylinkedlist_find shall consider that item as to be removed. ] */
|
---|
| 290 | if (condition_function(current_item->item, match_context, &continue_processing) == true)
|
---|
| 291 | {
|
---|
| 292 | if (previous_item != NULL)
|
---|
| 293 | {
|
---|
| 294 | previous_item->next = next_item;
|
---|
| 295 | }
|
---|
| 296 | else
|
---|
| 297 | {
|
---|
| 298 | list_instance->head = next_item;
|
---|
| 299 | }
|
---|
| 300 |
|
---|
| 301 | if (current_item == list_instance->tail)
|
---|
| 302 | {
|
---|
| 303 | list_instance->tail = previous_item;
|
---|
| 304 | }
|
---|
| 305 |
|
---|
| 306 | free(current_item);
|
---|
| 307 | }
|
---|
| 308 | /* Codes_SRS_LIST_09_005: [ If the condition function returns false, singlylinkedlist_find shall consider that item as not to be removed. ] */
|
---|
| 309 | else
|
---|
| 310 | {
|
---|
| 311 | previous_item = current_item;
|
---|
| 312 | }
|
---|
| 313 |
|
---|
| 314 | /* 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. ] */
|
---|
| 315 | if (continue_processing == false)
|
---|
| 316 | {
|
---|
| 317 | break;
|
---|
| 318 | }
|
---|
| 319 |
|
---|
| 320 | current_item = next_item;
|
---|
| 321 | }
|
---|
| 322 |
|
---|
| 323 | /* Codes_SRS_LIST_09_007: [ If no errors occur, singlylinkedlist_remove_if shall return zero. ] */
|
---|
| 324 | result = 0;
|
---|
| 325 | }
|
---|
| 326 |
|
---|
| 327 | return result;
|
---|
| 328 | }
|
---|
| 329 |
|
---|
| 330 | int singlylinkedlist_foreach(SINGLYLINKEDLIST_HANDLE list, LIST_ACTION_FUNCTION action_function, const void* action_context)
|
---|
| 331 | {
|
---|
| 332 | int result;
|
---|
| 333 |
|
---|
| 334 | /* Codes_SRS_LIST_09_008: [ If the list or the action_function argument is NULL, singlylinkedlist_foreach shall return non-zero value. ] */
|
---|
| 335 | if ((list == NULL) ||
|
---|
| 336 | (action_function == NULL))
|
---|
| 337 | {
|
---|
| 338 | LogError("Invalid argument (list=%p, action_function=%p)", list, action_function);
|
---|
| 339 | result = MU_FAILURE;
|
---|
| 340 | }
|
---|
| 341 | else
|
---|
| 342 | {
|
---|
| 343 | LIST_INSTANCE* list_instance = (LIST_INSTANCE*)list;
|
---|
| 344 | LIST_ITEM_INSTANCE* list_item = list_instance->head;
|
---|
| 345 |
|
---|
| 346 | while (list_item != NULL)
|
---|
| 347 | {
|
---|
| 348 | bool continue_processing = false;
|
---|
| 349 |
|
---|
| 350 | /* Codes_SRS_LIST_09_009: [ singlylinkedlist_foreach shall iterate through all items in a list and invoke action_function for each one of them. ] */
|
---|
| 351 | action_function(list_item->item, action_context, &continue_processing);
|
---|
| 352 |
|
---|
| 353 | /* Codes_SRS_LIST_09_010: [ If the condition function returns continue_processing as false, singlylinkedlist_foreach shall stop iterating through the list and return. ] */
|
---|
| 354 | if (continue_processing == false)
|
---|
| 355 | {
|
---|
| 356 | break;
|
---|
| 357 | }
|
---|
| 358 |
|
---|
| 359 | list_item = (LIST_ITEM_INSTANCE*)list_item->next;
|
---|
| 360 | }
|
---|
| 361 |
|
---|
| 362 | /* Codes_SRS_LIST_09_011: [ If no errors occur, singlylinkedlist_foreach shall return zero. ] */
|
---|
| 363 | result = 0;
|
---|
| 364 | }
|
---|
| 365 |
|
---|
| 366 | return result;
|
---|
| 367 | }
|
---|
| 368 |
|
---|
| 369 | LIST_ITEM_HANDLE singlylinkedlist_add_head(SINGLYLINKEDLIST_HANDLE list, const void* item)
|
---|
| 370 | {
|
---|
| 371 | LIST_ITEM_HANDLE result;
|
---|
| 372 |
|
---|
| 373 | /* Codes_SRS_LIST_02_001: [ If list is NULL then singlylinkedlist_add_head shall fail and return NULL. ]*/
|
---|
| 374 | if (list == NULL)
|
---|
| 375 | {
|
---|
| 376 | LogError("Invalid argument SINGLYLINKEDLIST_HANDLE list=%p", list);
|
---|
| 377 | result = NULL;
|
---|
| 378 | }
|
---|
| 379 | else
|
---|
| 380 | {
|
---|
| 381 | result = malloc(sizeof(LIST_ITEM_INSTANCE));
|
---|
| 382 |
|
---|
| 383 | if (result == NULL)
|
---|
| 384 | {
|
---|
| 385 | /*Codes_SRS_LIST_02_003: [ If there are any failures then singlylinkedlist_add_head shall fail and return NULL. ]*/
|
---|
| 386 | LogError("failure in malloc");
|
---|
| 387 | /*return as is*/
|
---|
| 388 | }
|
---|
| 389 | else
|
---|
| 390 | {
|
---|
| 391 | /*Codes_SRS_LIST_02_002: [ singlylinkedlist_add_head shall insert item at head, succeed and return a non-NULL value. ]*/
|
---|
| 392 | result->item = item;
|
---|
| 393 | if (list->head == NULL)
|
---|
| 394 | {
|
---|
| 395 | result->next = NULL;
|
---|
| 396 | list->head = result;
|
---|
| 397 | list->tail = result;
|
---|
| 398 |
|
---|
| 399 | }
|
---|
| 400 | else
|
---|
| 401 | {
|
---|
| 402 | result->next = list->head;
|
---|
| 403 | list->head = result;
|
---|
| 404 | }
|
---|
| 405 | }
|
---|
| 406 | }
|
---|
| 407 |
|
---|
| 408 | return result;
|
---|
| 409 | }
|
---|