Debian Codegraph @

src/misc/list.c

raw
1 /* ______ ___ ___
2 * /\ _ \ /\_ \ /\_ \
3 * \ \ \L\ \\//\ \ \//\ \ __ __ _ __ ___
4 * \ \ __ \ \ \ \ \ \ \ /'__`\ /'_ `\/\`'__\/ __`\
5 * \ \ \/\ \ \_\ \_ \_\ \_/\ __//\ \L\ \ \ \//\ \L\ \
6 * \ \_\ \_\/\____\/\____\ \____\ \____ \ \_\\ \____/
7 * \/_/\/_/\/____/\/____/\/____/\/___L\ \/_/ \/___/
8 * /\____/
9 * \_/__/
10 *
11 * Double linked list.
12 *
13 * By Michał Cichoń.
14 *
15 * See readme.txt for copyright information.
16 *
17 *
18 * This is a simple general purpose double linked list.
19 *
20 * This module is NOT thread-safe.
21 */
22
23 #include <stdlib.h>
24 #include <string.h>
25
26 #include "allegro5/allegro.h"
27 #include "allegro5/internal/aintern.h"
28 #include "allegro5/internal/aintern_list.h"
29
30
31 ALLEGRO_DEBUG_CHANNEL("list")
32
33
34 /* Definition of list, holds root and size. */
35 struct _AL_LIST {
36 /* Root of the list. It is an element, but
37 * not visible one. Using it end and the
38 * beginning can be easily identified. */
39 _AL_LIST_ITEM* root;
40 size_t size;
41 size_t capacity;
42 size_t item_size;
43 size_t item_size_with_extra;
44 _AL_LIST_ITEM* next_free;
45 void* user_data;
46 _AL_LIST_DTOR dtor;
47 };
48
49 /* List item, holds user data and destructor. */
50 struct _AL_LIST_ITEM {
51 _AL_LIST* list;
52 _AL_LIST_ITEM* next;
53 _AL_LIST_ITEM* prev;
54 void* data;
55 _AL_LIST_ITEM_DTOR dtor;
56 };
57
58
59 /* List of the internal functions. */
60 static _AL_LIST* list_do_create(size_t capacity, size_t item_extra_size);
61 static bool list_is_static(_AL_LIST* list);
62
63 static _AL_LIST_ITEM* list_get_free_item(_AL_LIST* list);
64 static _AL_LIST_ITEM* list_create_item(_AL_LIST* list);
65 static void list_destroy_item(_AL_LIST* list, _AL_LIST_ITEM* item);
66
67
68 /*
69 * Create an instance of double linked list.
70 *
71 * Parameters:
72 * capacity [in]
73 * Maximum number of elements list can hold. If it is zero, list is
74 * created as fully dynamic linked list with unlimited item count.
75 * For any other positive number static linked list is created,
76 * memory for all elements is allocated once and then used.
77 *
78 * extra_item_size [in]
79 * Number of extra bytes which should be left after each list item.
80 * It is currently not used, so default value is zero.
81 *
82 * Returns:
83 * Pointer to new instance of double linked list.
84 *
85 * Remarks:
86 * There are two kind of double linked list supported: dynamic and static.
87 * For dynamic linked list each item is allocated while adding and freed
88 * while removing. This kind of list does not have capacity limit but
89 * suffer from memory allocation delay.
90 * Static linked list use one memory allocation and are hold as solid
91 * piece of memory. This kind of list have capacity, but adding and
92 * removing elements is very cheap operation.
93 */
94 static _AL_LIST* list_do_create(size_t capacity, size_t extra_item_size)
95 {
96 size_t i;
97 size_t memory_size;
98 uint8_t* memory_ptr;
99 _AL_LIST* list = NULL;
100 _AL_LIST_ITEM* item = NULL;
101 _AL_LIST_ITEM* prev = NULL;
102
103
104 /* Calculate amount of memory needed for the list.
105 * Always at least one element is allocated together with list,
106 * which is intended to be a root.
107 */
108 memory_size = sizeof(_AL_LIST) + (capacity + 1) * (sizeof(_AL_LIST_ITEM) + extra_item_size);
109
110 memory_ptr = (uint8_t*)al_malloc(memory_size);
111 if (NULL == memory_ptr) {
112 ALLEGRO_ERROR("Out of memory.");
113 return NULL;
114 }
115
116 list = (_AL_LIST*)memory_ptr;
117 memory_ptr += sizeof(_AL_LIST);
118 list->size = 0;
119 list->capacity = capacity;
120 list->item_size = sizeof(_AL_LIST_ITEM);
121 list->item_size_with_extra = sizeof(_AL_LIST_ITEM) + extra_item_size;
122 list->next_free = (_AL_LIST_ITEM*)memory_ptr;
123 list->user_data = NULL;
124 list->dtor = NULL;
125
126 /* Initialize free item list.
127 */
128 prev = NULL;
129 item = list->next_free;
130 for (i = 0; i <= list->capacity; ++i) {
131
132 memory_ptr += list->item_size_with_extra;
133 item->list = list;
134 item->next = (_AL_LIST_ITEM*)memory_ptr;
135 prev = item;
136 item = item->next;
137 }
138
139 /* Set proper free list tail value. */
140 prev->next = NULL;
141
142 /* Initialize root. */
143 list->root = list_get_free_item(list);
144 list->root->dtor = NULL;
145 list->root->next = list->root;
146 list->root->prev = list->root;
147
148 return list;
149 }
150
151
152 /*
153 * Returns true if 'list' point to static double linked list.
154 */
155 static bool list_is_static(_AL_LIST* list)
156 {
157 return 0 != list->capacity;
158 }
159
160
161 /*
162 * Returns free item from internal list. Call to this function
163 * is valid only for static lists.
164 */
165 static _AL_LIST_ITEM* list_get_free_item(_AL_LIST* list)
166 {
167 _AL_LIST_ITEM* item;
168
169 //thedmd: disabled, root is always static-like element and this method
170 // is called even for dynamic lists
171 //ASSERT(list_is_static(list));
172
173 item = list->next_free;
174 if (NULL != item)
175 list->next_free = item->next;
176
177 return item;
178 }
179
180
181 /*
182 * Create an instance of new double linked list item.
183 */
184 static _AL_LIST_ITEM* list_create_item(_AL_LIST* list)
185 {
186 _AL_LIST_ITEM* item = NULL;
187
188 if (list_is_static(list)) {
189
190 /* Items from internal list already are partially initialized.
191 * So we do not have to setup list pointer.
192 */
193 item = list_get_free_item(list);
194 }
195 else {
196
197 item = (_AL_LIST_ITEM*)al_malloc(list->item_size_with_extra);
198
199 item->list = list;
200 }
201
202 return item;
203 }
204
205
206 /*
207 * Destroys double linked list item. Item destructor is called
208 * when necessary.
209 */
210 static void list_destroy_item(_AL_LIST* list, _AL_LIST_ITEM* item)
211 {
212 ASSERT(list == item->list);
213
214 if (NULL != item->dtor)
215 item->dtor(item->data, list->user_data);
216
217 if (list_is_static(list)) {
218 item->next = list->next_free;
219 list->next_free = item;
220 }
221 else
222 al_free(item);
223 }
224
225
226 /*
227 * Create new instance of dynamic double linked list.
228 *
229 * See:
230 * list_do_create
231 */
232 _AL_LIST* _al_list_create(void)
233 {
234 return list_do_create(0, 0);
235 }
236
237
238 /*
239 * Create new instance of list item. Maximum number of list items is
240 * limited by capacity.
241 *
242 * See:
243 * list_do_create
244 */
245 _AL_LIST* _al_list_create_static(size_t capacity)
246 {
247 if (capacity < 1) {
248
249 ALLEGRO_ERROR("Cannot create static list without any capacity.");
250 return NULL;
251 }
252
253 return list_do_create(capacity, 0);
254 }
255
256
257 /*
258 * Destroys instance of the list. All elements
259 * that list contain are also destroyed.
260 */
261 void _al_list_destroy(_AL_LIST* list)
262 {
263 if (NULL == list)
264 return;
265
266 if (list->dtor)
267 list->dtor(list->user_data);
268
269 _al_list_clear(list);
270
271 al_free(list);
272 }
273
274
275 /*
276 * Sets a destructor for the list.
277 */
278 void _al_list_set_dtor(_AL_LIST* list, _AL_LIST_DTOR dtor)
279 {
280 list->dtor = dtor;
281 }
282
283
284 /*
285 * Returns destructor of the list.
286 */
287 _AL_LIST_DTOR _al_list_get_dtor(_AL_LIST* list)
288 {
289 return list->dtor;
290 }
291
292
293 /*
294 * Create and push new item at the beginning of the list.
295 *
296 * Returns pointer to new item.
297 */
298 _AL_LIST_ITEM* _al_list_push_front(_AL_LIST* list, void* data)
299 {
300 return _al_list_insert_after(list, list->root, data);
301 }
302
303
304 /*
305 * Pretty the same as _al_list_push_front(), but also allow
306 * to provide custom destructor for the item.
307 */
308 _AL_LIST_ITEM* _al_list_push_front_ex(_AL_LIST* list, void* data, _AL_LIST_ITEM_DTOR dtor)
309 {
310 return _al_list_insert_after_ex(list, list->root, data, dtor);
311 }
312
313
314 /*
315 * Create and push new item at the end of the list.
316 *
317 * Returns pointer to new item.
318 */
319 _AL_LIST_ITEM* _al_list_push_back(_AL_LIST* list, void* data)
320 {
321 return _al_list_insert_before(list, list->root, data);
322 }
323
324
325 /*
326 * Pretty the same as _al_list_push_back(), but also allow
327 * to provide custom destructor for the item.
328 */
329 _AL_LIST_ITEM* _al_list_push_back_ex(_AL_LIST* list, void* data, _AL_LIST_ITEM_DTOR dtor)
330 {
331 return _al_list_insert_before_ex(list, list->root, data, dtor);
332 }
333
334
335 /*
336 * Remove first item in the list.
337 */
338 void _al_list_pop_front(_AL_LIST* list)
339 {
340 if (list->size > 0)
341 _al_list_erase(list, list->root->next);
342 }
343
344
345 /*
346 * Remove last item in the list.
347 */
348 void _al_list_pop_back(_AL_LIST* list)
349 {
350 if (list->size > 0)
351 _al_list_erase(list, list->root->prev);
352 }
353
354
355 /*
356 * Create and insert new item after one specified by 'where'.
357 *
358 * Returns pointer to new item.
359 */
360 _AL_LIST_ITEM* _al_list_insert_after(_AL_LIST* list, _AL_LIST_ITEM* where, void* data)
361 {
362 return _al_list_insert_after_ex(list, where, data, NULL);
363 }
364
365
366 /*
367 * Pretty the same as _al_list_insert_after(), but also allow
368 * to provide custom destructor for the item.
369 */
370 _AL_LIST_ITEM* _al_list_insert_after_ex(_AL_LIST* list, _AL_LIST_ITEM* where, void* data, _AL_LIST_ITEM_DTOR dtor)
371 {
372 _AL_LIST_ITEM* item;
373
374 ASSERT(list == where->list);
375
376 item = list_create_item(list);
377 if (NULL == item)
378 return NULL;
379
380 item->data = data;
381 item->dtor = dtor;
382
383 item->prev = where;
384 item->next = where->next;
385
386 where->next->prev = item;
387 where->next = item;
388
389 list->size++;
390
391 return item;
392 }
393
394
395 /*
396 * Create and insert new item before one specified by 'where'.
397 *
398 * Returns pointer to new item.
399 */
400 _AL_LIST_ITEM* _al_list_insert_before(_AL_LIST* list, _AL_LIST_ITEM* where, void* data)
401 {
402 return _al_list_insert_before_ex(list, where, data, NULL);
403 }
404
405
406 /*
407 * Pretty the same as _al_list_insert_before(), but also allow
408 * to provide custom destructor for the item.
409 */
410 _AL_LIST_ITEM* _al_list_insert_before_ex(_AL_LIST* list, _AL_LIST_ITEM* where, void* data, _AL_LIST_ITEM_DTOR dtor)
411 {
412 _AL_LIST_ITEM* item;
413
414 ASSERT(list == where->list);
415
416 item = list_create_item(list);
417 if (NULL == item)
418 return NULL;
419
420 item->data = data;
421 item->dtor = dtor;
422
423 item->next = where;
424 item->prev = where->prev;
425
426 where->prev->next = item;
427 where->prev = item;
428
429 list->size++;
430
431 return item;
432 }
433
434
435 /*
436 * Remove specified item from the list.
437 */
438 void _al_list_erase(_AL_LIST* list, _AL_LIST_ITEM* item)
439 {
440 if (NULL == item)
441 return;
442
443 ASSERT(list == item->list);
444
445 item->prev->next = item->next;
446 item->next->prev = item->prev;
447
448 list->size--;
449
450 list_destroy_item(list, item);
451 }
452
453
454 /*
455 * Remove all items from the list.
456 */
457 void _al_list_clear(_AL_LIST* list)
458 {
459 _AL_LIST_ITEM* item;
460 _AL_LIST_ITEM* next;
461
462 item = _al_list_front(list);
463
464 while (NULL != item) {
465
466 next = _al_list_next(list, item);
467
468 _al_list_erase(list, item);
469
470 item = next;
471 }
472 }
473
474
475 /*
476 * Remove all occurrences of specified value in the list.
477 */
478 void _al_list_remove(_AL_LIST* list, void* data)
479 {
480 _AL_LIST_ITEM* item = NULL;
481 _AL_LIST_ITEM* next = NULL;
482
483 item = _al_list_find_first(list, data);
484
485 while (NULL != item) {
486
487 next = _al_list_find_after(list, item, data);
488
489 _al_list_erase(list, item);
490
491 item = next;
492 }
493 }
494
495
496 /*
497 * Returns true if list is empty.
498 */
499 bool _al_list_is_empty(_AL_LIST* list)
500 {
501 return 0 == list->size;
502 }
503
504
505 /*
506 * Returns true if list contain specified value.
507 */
508 bool _al_list_contains(_AL_LIST* list, void* data)
509 {
510 return NULL != _al_list_find_first(list, data);
511 }
512
513
514 /*
515 * Returns first occurrence of specified value in the list.
516 */
517 _AL_LIST_ITEM* _al_list_find_first(_AL_LIST* list, void* data)
518 {
519 return _al_list_find_after(list, list->root, data);
520 }
521
522
523 /*
524 * Returns last occurrence of specified value in the list.
525 */
526 _AL_LIST_ITEM* _al_list_find_last(_AL_LIST* list, void* data)
527 {
528 return _al_list_find_before(list, list->root, data);
529 }
530
531
532 /*
533 * Return occurrence of specified value in the list after 'where' item.
534 */
535 _AL_LIST_ITEM* _al_list_find_after(_AL_LIST* list, _AL_LIST_ITEM* where, void* data)
536 {
537 _AL_LIST_ITEM* item;
538
539 ASSERT(list == where->list);
540
541 for (item = where->next; item != list->root; item = item->next)
542 if (item->data == data)
543 return item;
544
545 return NULL;
546 }
547
548
549 /*
550 * Return occurrence of specified value in the list before 'where' item.
551 */
552 _AL_LIST_ITEM* _al_list_find_before(_AL_LIST* list, _AL_LIST_ITEM* where, void* data)
553 {
554 _AL_LIST_ITEM* item;
555
556 ASSERT(list == where->list);
557
558 for (item = where->prev; item != list->root; item = item->prev)
559 if (item->data == data)
560 return item;
561
562 return NULL;
563 }
564
565
566 /*
567 * Returns current size of the list.
568 */
569 size_t _al_list_size(_AL_LIST* list)
570 {
571 return list->size;
572 }
573
574
575 /*
576 * Returns item located at specified index.
577 */
578 _AL_LIST_ITEM* _al_list_at(_AL_LIST* list, size_t index)
579 {
580 if (index >= list->size)
581 return NULL;
582
583 if (index < list->size / 2) {
584
585 _AL_LIST_ITEM* item = list->root->next;
586
587 while (index--)
588 item = item->next;
589
590 return item;
591 }
592 else {
593
594 _AL_LIST_ITEM* item = list->root->prev;
595
596 index = list->size - index - 1;
597
598 while (index--)
599 item = item->prev;
600
601 return item;
602 }
603 }
604
605
606 /*
607 * Returns first item in the list.
608 */
609 _AL_LIST_ITEM* _al_list_front(_AL_LIST* list)
610 {
611 if (list->size > 0)
612 return list->root->next;
613 else
614 return NULL;
615 }
616
617
618 /*
619 * Returns last item in the list.
620 */
621 _AL_LIST_ITEM* _al_list_back(_AL_LIST* list)
622 {
623 if (list->size > 0)
624 return list->root->prev;
625 else
626 return NULL;
627 }
628
629
630 /*
631 * Returns next element in the list.
632 */
633 _AL_LIST_ITEM* _al_list_next(_AL_LIST* list, _AL_LIST_ITEM* item)
634 {
635 ASSERT(list == item->list);
636 (void)list;
637
638 if (item->next != item->list->root)
639 return item->next;
640 else
641 return NULL;
642 }
643
644
645 /*
646 * Returns previous element in the list.
647 */
648 _AL_LIST_ITEM* _al_list_previous(_AL_LIST* list, _AL_LIST_ITEM* item)
649 {
650 ASSERT(list == item->list);
651 (void)list;
652
653 if (item->prev != item->list->root)
654 return item->prev;
655 else
656 return NULL;
657 }
658
659
660 /*
661 * Returns next element in the list. If end of the list is reached,
662 * first element is returned instead of NULL.
663 */
664 _AL_LIST_ITEM* _al_list_next_circular(_AL_LIST* list, _AL_LIST_ITEM* item)
665 {
666 ASSERT(list == item->list);
667
668 if (item->next != item->list->root)
669 return item->next;
670 else
671 return list->root->next;
672 }
673
674
675 /*
676 * Returns previous element in the list. If beginning of the list is reached,
677 * last element is returned instead of NULL.
678 */
679 _AL_LIST_ITEM* _al_list_previous_circular(_AL_LIST* list, _AL_LIST_ITEM* item)
680 {
681 ASSERT(list == item->list);
682
683 if (item->prev != item->list->root)
684 return item->prev;
685 else
686 return list->root->prev;
687 }
688
689
690 /*
691 * Returns value associated with specified item.
692 */
693 void* _al_list_item_data(_AL_LIST_ITEM* item)
694 {
695 return item->data;
696 }
697
698
699 /*
700 * Sets item destructor.
701 */
702 void _al_list_item_set_dtor(_AL_LIST_ITEM* item, _AL_LIST_ITEM_DTOR dtor)
703 {
704 item->dtor = dtor;
705 }
706
707
708 /*
709 * Returns item destructor.
710 */
711 _AL_LIST_ITEM_DTOR _al_list_item_get_dtor(_AL_LIST_ITEM* item)
712 {
713 return item->dtor;
714 }
715
716
717 /*
718 * Sets user data for list. This pointer is passed to list destructor.
719 */
720 void _al_list_set_user_data(_AL_LIST* list, void* user_data)
721 {
722 list->user_data = user_data;
723 }
724
725
726 /*
727 * Returns user data for list.
728 */
729 void* _al_list_get_user_data(_AL_LIST* list)
730 {
731 return list->user_data;
732 }