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 | }
|
---|