1 /* Copyright (C) 2010-2020 The RetroArch team
3 * ---------------------------------------------------------------------------------------
4 * The following license statement only applies to this file (linked_list.c).
5 * ---------------------------------------------------------------------------------------
7 * Permission is hereby granted, free of charge,
8 * to any person obtaining a copy of this software and associated documentation files (the "Software"),
9 * to deal in the Software without restriction, including without limitation the rights to
10 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software,
11 * and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
13 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
16 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
18 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
19 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
27 #include <lists/linked_list.h>
29 struct linked_list_item_t
32 struct linked_list_item_t *previous;
33 struct linked_list_item_t *next;
38 struct linked_list_item_t *first_item;
39 struct linked_list_item_t *last_item;
43 struct linked_list_iterator
46 struct linked_list_item_t *item;
50 linked_list_t *linked_list_new(void)
54 list = (linked_list_t *)calloc(sizeof(linked_list_t), 1);
58 void linked_list_free(linked_list_t *list, void (*free_value)(void *value))
65 while (list->first_item)
67 struct linked_list_item_t *next;
69 next = list->first_item->next;
71 free_value(list->first_item->value);
72 free(list->first_item);
74 list->first_item = next;
80 void linked_list_add(linked_list_t *list, void *value)
82 struct linked_list_item_t *new_item;
87 new_item = (struct linked_list_item_t *)malloc(sizeof(struct linked_list_item_t));
88 new_item->value = value;
89 new_item->previous = list->last_item;
90 new_item->next = NULL;
92 if (list->length == 0)
93 list->first_item = new_item;
95 list->last_item->next = new_item;
97 list->last_item = new_item;
101 void linked_list_insert(linked_list_t *list, size_t index, void *value)
104 struct linked_list_item_t *previous_item;
105 struct linked_list_item_t *next_item;
106 struct linked_list_item_t *new_item;
108 if (!list || index > list->length)
111 previous_item = NULL;
112 next_item = list->first_item;
113 for (i = 1; i <= index; i++)
115 previous_item = next_item;
116 next_item = next_item->next;
119 new_item = (struct linked_list_item_t *)malloc(sizeof(struct linked_list_item_t));
120 new_item->value = value;
123 previous_item->next = new_item;
125 list->first_item = new_item;
126 new_item->previous = previous_item;
129 next_item->previous = new_item;
131 list->last_item = new_item;
132 new_item->next = next_item;
137 void *linked_list_get(linked_list_t *list, size_t index)
140 struct linked_list_item_t *item;
145 if (index >= list->length)
148 item = list->first_item;
149 for (i = 1; i <= index; i++)
155 void *linked_list_get_first_matching(linked_list_t *list, bool (*matches)(void *item, void *usrptr), void *usrptr)
157 struct linked_list_item_t *item;
159 if (!list || !matches)
162 for (item = list->first_item; item; item = item->next)
164 if (matches(item->value, usrptr))
171 void *linked_list_get_last_matching(linked_list_t *list, bool (*matches)(void *item, void *usrptr), void *usrptr)
173 struct linked_list_item_t *item;
175 if (!list || !matches)
178 for (item = list->last_item; item; item = item->previous)
180 if (matches(item->value, usrptr))
187 static void _linked_list_remove_item(linked_list_t *list, struct linked_list_item_t *item)
189 struct linked_list_item_t *previous_item;
190 struct linked_list_item_t *next_item;
192 previous_item = item->previous;
193 next_item = item->next;
198 previous_item->next = next_item;
200 list->first_item = next_item;
203 next_item->previous = previous_item;
205 list->last_item = previous_item;
208 void *linked_list_remove_at(linked_list_t *list, size_t index)
211 struct linked_list_item_t *item;
214 if (!list || list->length == 0 || index >= list->length)
217 item = list->first_item;
218 for (i = 1; i <= index; i++)
222 _linked_list_remove_item(list, item);
226 void *linked_list_remove_first(linked_list_t *list, void *value)
228 struct linked_list_item_t *item;
233 for (item = list->first_item; item; item = item->next)
235 if (item->value == value)
241 _linked_list_remove_item(list, item);
248 void *linked_list_remove_last(linked_list_t *list, void *value)
250 struct linked_list_item_t *item;
255 for (item = list->last_item; item; item = item->previous)
257 if (item->value == value)
263 _linked_list_remove_item(list, item);
270 void *linked_list_remove_all(linked_list_t *list, void *value)
272 struct linked_list_item_t *item;
278 for (item = list->first_item; item;)
280 if (item->value == value)
282 struct linked_list_item_t *next_item;
284 next_item = item->next;
285 _linked_list_remove_item(list, item);
294 return found ? value : NULL;
297 void *linked_list_remove_first_matching(linked_list_t *list, bool (*matches)(void *value))
299 struct linked_list_item_t *item;
304 for (item = list->first_item; item; item = item->next)
306 if (matches(item->value))
315 _linked_list_remove_item(list, item);
322 void *linked_list_remove_last_matching(linked_list_t *list, bool (*matches)(void *value))
324 struct linked_list_item_t *item;
329 for (item = list->last_item; item; item = item->previous)
331 if (matches(item->value))
340 _linked_list_remove_item(list, item);
347 void linked_list_remove_all_matching(linked_list_t *list, bool (*matches)(void *value))
349 struct linked_list_item_t *item;
354 for (item = list->first_item; item;)
356 if (matches(item->value))
358 struct linked_list_item_t *next_item;
360 next_item = item->next;
361 _linked_list_remove_item(list, item);
370 bool linked_list_set_at(linked_list_t *list, size_t index, void *value)
372 struct linked_list_item_t *item;
375 if (!list || list->length == 0 || index >= list->length)
378 item = list->first_item;
379 for (i = 1; i <= index; i++)
391 size_t linked_list_size(linked_list_t *list)
399 linked_list_iterator_t *linked_list_iterator(linked_list_t *list, bool forward)
401 linked_list_iterator_t *iterator;
403 if (!list || !list->first_item)
406 iterator = (linked_list_iterator_t *)malloc(sizeof(linked_list_iterator_t));
407 iterator->list = list;
408 iterator->item = forward ? list->first_item : list->last_item;
409 iterator->forward = forward;
414 linked_list_iterator_t *linked_list_iterator_next(linked_list_iterator_t *iterator)
416 struct linked_list_item_t *item;
421 item = iterator->forward ? iterator->item->next : iterator->item->previous;
424 iterator->item = item;
433 void *linked_list_iterator_value(linked_list_iterator_t *iterator)
436 return iterator->item->value;
441 linked_list_iterator_t *linked_list_iterator_remove(linked_list_iterator_t *iterator)
443 struct linked_list_item_t *next_item;
448 next_item = iterator->forward ? iterator->item->next : iterator->item->previous;
449 _linked_list_remove_item(iterator->list, iterator->item);
453 iterator->item = next_item;
462 void linked_list_iterator_free(linked_list_iterator_t *iterator)
468 void linked_list_foreach(linked_list_t *list, void (*fn)(size_t index, void *value))
471 struct linked_list_item_t *item;
477 for (item = list->first_item; item; item = item->next)
478 fn(i++, item->value);