Commit | Line | Data |
---|---|---|
3719602c PC |
1 | /* Copyright (C) 2010-2020 The RetroArch team |
2 | * | |
3 | * --------------------------------------------------------------------------------------- | |
4 | * The following license statement only applies to this file (linked_list.c). | |
5 | * --------------------------------------------------------------------------------------- | |
6 | * | |
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: | |
12 | * | |
13 | * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. | |
14 | * | |
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. | |
21 | */ | |
22 | ||
23 | #include <boolean.h> | |
24 | #include <stddef.h> | |
25 | #include <stdlib.h> | |
26 | ||
27 | #include <lists/linked_list.h> | |
28 | ||
29 | struct linked_list_item_t | |
30 | { | |
31 | void *value; | |
32 | struct linked_list_item_t *previous; | |
33 | struct linked_list_item_t *next; | |
34 | }; | |
35 | ||
36 | struct linked_list | |
37 | { | |
38 | struct linked_list_item_t *first_item; | |
39 | struct linked_list_item_t *last_item; | |
40 | size_t length; | |
41 | }; | |
42 | ||
43 | struct linked_list_iterator | |
44 | { | |
45 | linked_list_t *list; | |
46 | struct linked_list_item_t *item; | |
47 | bool forward; | |
48 | }; | |
49 | ||
50 | linked_list_t *linked_list_new(void) | |
51 | { | |
52 | linked_list_t *list; | |
53 | ||
54 | list = (linked_list_t *)calloc(sizeof(linked_list_t), 1); | |
55 | return list; | |
56 | } | |
57 | ||
58 | void linked_list_free(linked_list_t *list, void (*free_value)(void *value)) | |
59 | { | |
60 | if (!list) | |
61 | { | |
62 | return; | |
63 | } | |
64 | ||
65 | while (list->first_item) | |
66 | { | |
67 | struct linked_list_item_t *next; | |
68 | ||
69 | next = list->first_item->next; | |
70 | if (free_value) | |
71 | free_value(list->first_item->value); | |
72 | free(list->first_item); | |
73 | ||
74 | list->first_item = next; | |
75 | } | |
76 | ||
77 | free (list); | |
78 | } | |
79 | ||
80 | void linked_list_add(linked_list_t *list, void *value) | |
81 | { | |
82 | struct linked_list_item_t *new_item; | |
83 | ||
84 | if (!list) | |
85 | return; | |
86 | ||
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; | |
91 | ||
92 | if (list->length == 0) | |
93 | list->first_item = new_item; | |
94 | else | |
95 | list->last_item->next = new_item; | |
96 | ||
97 | list->last_item = new_item; | |
98 | list->length++; | |
99 | } | |
100 | ||
101 | void linked_list_insert(linked_list_t *list, size_t index, void *value) | |
102 | { | |
103 | size_t i; | |
104 | struct linked_list_item_t *previous_item; | |
105 | struct linked_list_item_t *next_item; | |
106 | struct linked_list_item_t *new_item; | |
107 | ||
108 | if (!list || index > list->length) | |
109 | return; | |
110 | ||
111 | previous_item = NULL; | |
112 | next_item = list->first_item; | |
113 | for (i = 1; i <= index; i++) | |
114 | { | |
115 | previous_item = next_item; | |
116 | next_item = next_item->next; | |
117 | } | |
118 | ||
119 | new_item = (struct linked_list_item_t *)malloc(sizeof(struct linked_list_item_t)); | |
120 | new_item->value = value; | |
121 | ||
122 | if (previous_item) | |
123 | previous_item->next = new_item; | |
124 | else | |
125 | list->first_item = new_item; | |
126 | new_item->previous = previous_item; | |
127 | ||
128 | if (next_item) | |
129 | next_item->previous = new_item; | |
130 | else | |
131 | list->last_item = new_item; | |
132 | new_item->next = next_item; | |
133 | ||
134 | list->length++; | |
135 | } | |
136 | ||
137 | void *linked_list_get(linked_list_t *list, size_t index) | |
138 | { | |
139 | size_t i; | |
140 | struct linked_list_item_t *item; | |
141 | ||
142 | if (!list) | |
143 | return NULL; | |
144 | ||
145 | if (index >= list->length) | |
146 | return NULL; | |
147 | ||
148 | item = list->first_item; | |
149 | for (i = 1; i <= index; i++) | |
150 | item = item->next; | |
151 | ||
152 | return item->value; | |
153 | } | |
154 | ||
155 | void *linked_list_get_first_matching(linked_list_t *list, bool (*matches)(void *item, void *usrptr), void *usrptr) | |
156 | { | |
157 | struct linked_list_item_t *item; | |
158 | ||
159 | if (!list || !matches) | |
160 | return NULL; | |
161 | ||
162 | for (item = list->first_item; item; item = item->next) | |
163 | { | |
164 | if (matches(item->value, usrptr)) | |
165 | return item->value; | |
166 | } | |
167 | ||
168 | return NULL; | |
169 | } | |
170 | ||
171 | void *linked_list_get_last_matching(linked_list_t *list, bool (*matches)(void *item, void *usrptr), void *usrptr) | |
172 | { | |
173 | struct linked_list_item_t *item; | |
174 | ||
175 | if (!list || !matches) | |
176 | return NULL; | |
177 | ||
178 | for (item = list->last_item; item; item = item->previous) | |
179 | { | |
180 | if (matches(item->value, usrptr)) | |
181 | return item->value; | |
182 | } | |
183 | ||
184 | return NULL; | |
185 | } | |
186 | ||
187 | static void _linked_list_remove_item(linked_list_t *list, struct linked_list_item_t *item) | |
188 | { | |
189 | struct linked_list_item_t *previous_item; | |
190 | struct linked_list_item_t *next_item; | |
191 | ||
192 | previous_item = item->previous; | |
193 | next_item = item->next; | |
194 | free(item); | |
195 | list->length--; | |
196 | ||
197 | if (previous_item) | |
198 | previous_item->next = next_item; | |
199 | else | |
200 | list->first_item = next_item; | |
201 | ||
202 | if (next_item) | |
203 | next_item->previous = previous_item; | |
204 | else | |
205 | list->last_item = previous_item; | |
206 | } | |
207 | ||
208 | void *linked_list_remove_at(linked_list_t *list, size_t index) | |
209 | { | |
210 | size_t i = 0; | |
211 | struct linked_list_item_t *item; | |
212 | void *value; | |
213 | ||
214 | if (!list || list->length == 0 || index >= list->length) | |
215 | return NULL; | |
216 | ||
217 | item = list->first_item; | |
218 | for (i = 1; i <= index; i++) | |
219 | item = item->next; | |
220 | ||
221 | value = item->value; | |
222 | _linked_list_remove_item(list, item); | |
223 | return value; | |
224 | } | |
225 | ||
226 | void *linked_list_remove_first(linked_list_t *list, void *value) | |
227 | { | |
228 | struct linked_list_item_t *item; | |
229 | ||
230 | if (!list) | |
231 | return NULL; | |
232 | ||
233 | for (item = list->first_item; item; item = item->next) | |
234 | { | |
235 | if (item->value == value) | |
236 | break; | |
237 | } | |
238 | ||
239 | if (item) | |
240 | { | |
241 | _linked_list_remove_item(list, item); | |
242 | return value; | |
243 | } | |
244 | ||
245 | return NULL; | |
246 | } | |
247 | ||
248 | void *linked_list_remove_last(linked_list_t *list, void *value) | |
249 | { | |
250 | struct linked_list_item_t *item; | |
251 | ||
252 | if (!list) | |
253 | return NULL; | |
254 | ||
255 | for (item = list->last_item; item; item = item->previous) | |
256 | { | |
257 | if (item->value == value) | |
258 | break; | |
259 | } | |
260 | ||
261 | if (item) | |
262 | { | |
263 | _linked_list_remove_item(list, item); | |
264 | return value; | |
265 | } | |
266 | ||
267 | return NULL; | |
268 | } | |
269 | ||
270 | void *linked_list_remove_all(linked_list_t *list, void *value) | |
271 | { | |
272 | struct linked_list_item_t *item; | |
273 | bool found = false; | |
274 | ||
275 | if (!list) | |
276 | return NULL; | |
277 | ||
278 | for (item = list->first_item; item;) | |
279 | { | |
280 | if (item->value == value) | |
281 | { | |
282 | struct linked_list_item_t *next_item; | |
283 | ||
284 | next_item = item->next; | |
285 | _linked_list_remove_item(list, item); | |
286 | found = true; | |
287 | item = next_item; | |
288 | } else | |
289 | { | |
290 | item = item->next; | |
291 | } | |
292 | } | |
293 | ||
294 | return found ? value : NULL; | |
295 | } | |
296 | ||
297 | void *linked_list_remove_first_matching(linked_list_t *list, bool (*matches)(void *value)) | |
298 | { | |
299 | struct linked_list_item_t *item; | |
300 | ||
301 | if (!list) | |
302 | return NULL; | |
303 | ||
304 | for (item = list->first_item; item; item = item->next) | |
305 | { | |
306 | if (matches(item->value)) | |
307 | break; | |
308 | } | |
309 | ||
310 | if (item) | |
311 | { | |
312 | void *value; | |
313 | ||
314 | value = item->value; | |
315 | _linked_list_remove_item(list, item); | |
316 | return value; | |
317 | } | |
318 | ||
319 | return NULL; | |
320 | } | |
321 | ||
322 | void *linked_list_remove_last_matching(linked_list_t *list, bool (*matches)(void *value)) | |
323 | { | |
324 | struct linked_list_item_t *item; | |
325 | ||
326 | if (!list) | |
327 | return NULL; | |
328 | ||
329 | for (item = list->last_item; item; item = item->previous) | |
330 | { | |
331 | if (matches(item->value)) | |
332 | break; | |
333 | } | |
334 | ||
335 | if (item) | |
336 | { | |
337 | void *value; | |
338 | ||
339 | value = item->value; | |
340 | _linked_list_remove_item(list, item); | |
341 | return value; | |
342 | } | |
343 | ||
344 | return NULL; | |
345 | } | |
346 | ||
347 | void linked_list_remove_all_matching(linked_list_t *list, bool (*matches)(void *value)) | |
348 | { | |
349 | struct linked_list_item_t *item; | |
350 | ||
351 | if (!list) | |
352 | return; | |
353 | ||
354 | for (item = list->first_item; item;) | |
355 | { | |
356 | if (matches(item->value)) | |
357 | { | |
358 | struct linked_list_item_t *next_item; | |
359 | ||
360 | next_item = item->next; | |
361 | _linked_list_remove_item(list, item); | |
362 | item = next_item; | |
363 | } else | |
364 | { | |
365 | item = item->next; | |
366 | } | |
367 | } | |
368 | } | |
369 | ||
370 | bool linked_list_set_at(linked_list_t *list, size_t index, void *value) | |
371 | { | |
372 | struct linked_list_item_t *item; | |
373 | size_t i; | |
374 | ||
375 | if (!list || list->length == 0 || index >= list->length) | |
376 | return false; | |
377 | ||
378 | item = list->first_item; | |
379 | for (i = 1; i <= index; i++) | |
380 | item = item->next; | |
381 | ||
382 | if (item) | |
383 | { | |
384 | item->value = value; | |
385 | return true; | |
386 | } | |
387 | ||
388 | return false; | |
389 | } | |
390 | ||
391 | size_t linked_list_size(linked_list_t *list) | |
392 | { | |
393 | if (list) | |
394 | return list->length; | |
395 | ||
396 | return 0; | |
397 | } | |
398 | ||
399 | linked_list_iterator_t *linked_list_iterator(linked_list_t *list, bool forward) | |
400 | { | |
401 | linked_list_iterator_t *iterator; | |
402 | ||
403 | if (!list || !list->first_item) | |
404 | return NULL; | |
405 | ||
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; | |
410 | ||
411 | return iterator; | |
412 | } | |
413 | ||
414 | linked_list_iterator_t *linked_list_iterator_next(linked_list_iterator_t *iterator) | |
415 | { | |
416 | struct linked_list_item_t *item; | |
417 | ||
418 | if (!iterator) | |
419 | return NULL; | |
420 | ||
421 | item = iterator->forward ? iterator->item->next : iterator->item->previous; | |
422 | if (item) | |
423 | { | |
424 | iterator->item = item; | |
425 | return iterator; | |
426 | } else | |
427 | { | |
428 | free(iterator); | |
429 | return NULL; | |
430 | } | |
431 | } | |
432 | ||
433 | void *linked_list_iterator_value(linked_list_iterator_t *iterator) | |
434 | { | |
435 | if (iterator) | |
436 | return iterator->item->value; | |
437 | ||
438 | return NULL; | |
439 | } | |
440 | ||
441 | linked_list_iterator_t *linked_list_iterator_remove(linked_list_iterator_t *iterator) | |
442 | { | |
443 | struct linked_list_item_t *next_item; | |
444 | ||
445 | if (!iterator) | |
446 | return NULL; | |
447 | ||
448 | next_item = iterator->forward ? iterator->item->next : iterator->item->previous; | |
449 | _linked_list_remove_item(iterator->list, iterator->item); | |
450 | ||
451 | if (next_item) | |
452 | { | |
453 | iterator->item = next_item; | |
454 | return iterator; | |
455 | } else | |
456 | { | |
457 | free(iterator); | |
458 | return NULL; | |
459 | } | |
460 | } | |
461 | ||
462 | void linked_list_iterator_free(linked_list_iterator_t *iterator) | |
463 | { | |
464 | if (iterator) | |
465 | free(iterator); | |
466 | } | |
467 | ||
468 | void linked_list_foreach(linked_list_t *list, void (*fn)(size_t index, void *value)) | |
469 | { | |
470 | size_t i; | |
471 | struct linked_list_item_t *item; | |
472 | ||
473 | if (!list || !fn) | |
474 | return; | |
475 | ||
476 | i = 0; | |
477 | for (item = list->first_item; item; item = item->next) | |
478 | fn(i++, item->value); | |
479 | } |