added some new graphics for BD engine game elements
[rocksndiamonds.git] / src / libgame / list.c
1 // ============================================================================
2 // list.c
3 // ============================================================================
4
5 /* GLIB - Library of useful routines for C programming
6  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
7  *
8  * SPDX-License-Identifier: LGPL-2.1-or-later
9  *
10  * This library is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU Lesser General Public
12  * License as published by the Free Software Foundation; either
13  * version 2.1 of the License, or (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18  * Lesser General Public License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public
21  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
22  */
23
24 /*
25  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
26  * file for a list of people on the GLib Team.  See the ChangeLog
27  * files for a list of changes.  These files are distributed with
28  * GLib at ftp://ftp.gtk.org/pub/gtk/.
29  */
30
31 #include <stdlib.h>
32 #include <stddef.h>
33
34 #include "list.h"
35
36
37 /**
38  * List:
39  * @data: holds the element's data, which can be a pointer to any kind
40  *        of data, or any integer value using the
41  *        [Type Conversion Macros][glib-Type-Conversion-Macros]
42  * @next: contains the link to the next element in the list
43  * @prev: contains the link to the previous element in the list
44  *
45  * The #List struct is used for each element in a doubly-linked list.
46  **/
47
48 /**
49  * list_previous:
50  * @list: an element in a #List
51  *
52  * A convenience macro to get the previous element in a #List.
53  * Note that it is considered perfectly acceptable to access
54  * @list->prev directly.
55  *
56  * Returns: the previous element, or %NULL if there are no previous
57  *          elements
58  **/
59
60 /**
61  * list_next:
62  * @list: an element in a #List
63  *
64  * A convenience macro to get the next element in a #List.
65  * Note that it is considered perfectly acceptable to access
66  * @list->next directly.
67  *
68  * Returns: the next element, or %NULL if there are no more elements
69  **/
70
71 /**
72  * list_alloc:
73  *
74  * Allocates space for one #List element. It is called by
75  * list_append(), list_prepend(), list_insert() and
76  * list_insert_sorted() and so is rarely used on its own.
77  *
78  * Returns: a pointer to the newly-allocated #List element
79  **/
80 List *
81 list_alloc (void)
82 {
83   return checked_calloc(sizeof(List));
84 }
85
86 /**
87  * list_free:
88  * @list: the first link of a #List
89  *
90  * Frees all of the memory used by a #List.
91  * The freed elements are returned to the slice allocator.
92  *
93  * If list elements contain dynamically-allocated memory, you should
94  * either use list_free_full() or free them manually first.
95  *
96  * It can be combined with steal_pointer() to ensure the list head pointer
97  * is not left dangling:
98  * |[<!-- language="C" -->
99  * List *list_of_borrowed_things = …;  /<!-- -->* (transfer container) *<!-- -->/
100  * list_free (steal_pointer (&list_of_borrowed_things));
101  * ]|
102  */
103 void
104 list_free (List *list)
105 {
106   void *slice = list;
107   size_t next_offset = offsetof(List, next);
108
109   while (slice)
110   {
111     void *current = slice;
112     slice = *(void**) (current + next_offset);
113     checked_free(current);
114   }
115 }
116
117 /**
118  * list_free_1:
119  * @list: a #List element
120  *
121  * Frees one #List element, but does not update links from the next and
122  * previous elements in the list, so you should not call this function on an
123  * element that is currently part of a list.
124  *
125  * It is usually used after list_remove_link().
126  */
127 /**
128  * list_free1:
129  *
130  * Another name for list_free_1().
131  **/
132 void
133 list_free_1 (List *list)
134 {
135   checked_free(list);
136 }
137
138 /**
139  * list_append:
140  * @list: a pointer to a #List
141  * @data: the data for the new element
142  *
143  * Adds a new element on to the end of the list.
144  *
145  * Note that the return value is the new start of the list,
146  * if @list was empty; make sure you store the new value.
147  *
148  * list_append() has to traverse the entire list to find the end,
149  * which is inefficient when adding multiple elements. A common idiom
150  * to avoid the inefficiency is to use list_prepend() and reverse
151  * the list with list_reverse() when all elements have been added.
152  *
153  * |[<!-- language="C" -->
154  * // Notice that these are initialized to the empty list.
155  * List *strinlist = NULL, *number_list = NULL;
156  *
157  * // This is a list of strings.
158  * strinlist = list_append (strinlist, "first");
159  * strinlist = list_append (strinlist, "second");
160  *
161  * // This is a list of integers.
162  * number_list = list_append (number_list, INT_TO_PTR (27));
163  * number_list = list_append (number_list, INT_TO_PTR (14));
164  * ]|
165  *
166  * Returns: either @list or the new start of the #List if @list was %NULL
167  */
168 List *
169 list_append (List *list, void *data)
170 {
171   List *new_list;
172   List *last;
173
174   new_list = checked_malloc(sizeof(List));
175   new_list->data = data;
176   new_list->next = NULL;
177
178   if (list)
179   {
180     last = list_last(list);
181     last->next = new_list;
182     new_list->prev = last;
183
184     return list;
185   }
186   else
187   {
188     new_list->prev = NULL;
189
190     return new_list;
191   }
192 }
193
194 /**
195  * list_prepend:
196  * @list: a pointer to a #List, this must point to the top of the list
197  * @data: the data for the new element
198  *
199  * Prepends a new element on to the start of the list.
200  *
201  * Note that the return value is the new start of the list,
202  * which will have changed, so make sure you store the new value.
203  *
204  * |[<!-- language="C" -->
205  * // Notice that it is initialized to the empty list.
206  * List *list = NULL;
207  *
208  * list = list_prepend (list, "last");
209  * list = list_prepend (list, "first");
210  * ]|
211  *
212  * Do not use this function to prepend a new element to a different
213  * element than the start of the list. Use list_insert_before() instead.
214  *
215  * Returns: a pointer to the newly prepended element, which is the new
216  *     start of the #List
217  */
218 List *
219 list_prepend (List *list, void *data)
220 {
221   List *new_list;
222
223   new_list = checked_malloc(sizeof(List));
224   new_list->data = data;
225   new_list->next = list;
226
227   if (list)
228   {
229     new_list->prev = list->prev;
230     if (list->prev)
231       list->prev->next = new_list;
232     list->prev = new_list;
233   }
234   else
235   {
236     new_list->prev = NULL;
237   }
238
239   return new_list;
240 }
241
242 /**
243  * list_insert:
244  * @list: a pointer to a #List, this must point to the top of the list
245  * @data: the data for the new element
246  * @position: the position to insert the element. If this is
247  *     negative, or is larger than the number of elements in the
248  *     list, the new element is added on to the end of the list.
249  *
250  * Inserts a new element into the list at the given position.
251  *
252  * Returns: the (possibly changed) start of the #List
253  */
254 List *
255 list_insert (List *list, void *data, int position)
256 {
257   List *new_list;
258   List *tmp_list;
259
260   if (position < 0)
261     return list_append(list, data);
262   else if (position == 0)
263     return list_prepend(list, data);
264
265   tmp_list = list_nth(list, position);
266   if (!tmp_list)
267     return list_append(list, data);
268
269   new_list = checked_malloc(sizeof(List));
270   new_list->data = data;
271   new_list->prev = tmp_list->prev;
272   tmp_list->prev->next = new_list;
273   new_list->next = tmp_list;
274   tmp_list->prev = new_list;
275
276   return list;
277 }
278
279 static inline List *
280 _list_remove_link (List *list, List *link)
281 {
282   if (link == NULL)
283     return list;
284
285   if (link->prev)
286   {
287     if (link->prev->next == link)
288       link->prev->next = link->next;
289     else
290       Warn("corrupted double-linked list detected");
291   }
292
293   if (link->next)
294   {
295     if (link->next->prev == link)
296       link->next->prev = link->prev;
297     else
298       Warn("corrupted double-linked list detected");
299   }
300
301   if (link == list)
302     list = list->next;
303
304   link->next = NULL;
305   link->prev = NULL;
306
307   return list;
308 }
309
310 /**
311  * list_remove:
312  * @list: a #List, this must point to the top of the list
313  * @data: the data of the element to remove
314  *
315  * Removes an element from a #List.
316  * If two elements contain the same data, only the first is removed.
317  * If none of the elements contain the data, the #List is unchanged.
318  *
319  * Returns: the (possibly changed) start of the #List
320  */
321 List *
322 list_remove (List *list, const void *data)
323 {
324   List *tmp;
325
326   tmp = list;
327   while (tmp)
328   {
329     if (tmp->data != data)
330     {
331       tmp = tmp->next;
332     }
333     else
334     {
335       list = _list_remove_link (list, tmp);
336       free (tmp);
337
338       break;
339     }
340   }
341
342   return list;
343 }
344
345 /**
346  * list_remove_all:
347  * @list: a #List, this must point to the top of the list
348  * @data: data to remove
349  *
350  * Removes all list nodes with data equal to @data.
351  * Returns the new head of the list. Contrast with
352  * list_remove() which removes only the first node
353  * matching the given data.
354  *
355  * Returns: the (possibly changed) start of the #List
356  */
357 List *
358 list_remove_all (List *list, const void *data)
359 {
360   List *tmp = list;
361
362   while (tmp)
363   {
364     if (tmp->data != data)
365     {
366       tmp = tmp->next;
367     }
368     else
369     {
370       List *next = tmp->next;
371
372       if (tmp->prev)
373         tmp->prev->next = next;
374       else
375         list = next;
376
377       if (next)
378         next->prev = tmp->prev;
379
380       free (tmp);
381       tmp = next;
382     }
383   }
384
385   return list;
386 }
387
388 /**
389  * list_remove_link:
390  * @list: a #List, this must point to the top of the list
391  * @llink: an element in the #List
392  *
393  * Removes an element from a #List, without freeing the element.
394  * The removed element's prev and next links are set to %NULL, so
395  * that it becomes a self-contained list with one element.
396  *
397  * This function is for example used to move an element in the list
398  * (see the example for list_concat()) or to remove an element in
399  * the list before freeing its data:
400  * |[<!-- language="C" -->
401  * list = list_remove_link (list, llink);
402  * free_some_data_that_may_access_the_list_again (llink->data);
403  * list_free (llink);
404  * ]|
405  *
406  * Returns: the (possibly changed) start of the #List
407  */
408 List *
409 list_remove_link (List *list, List *llink)
410 {
411   return _list_remove_link(list, llink);
412 }
413
414 /**
415  * list_delete_link:
416  * @list: a #List, this must point to the top of the list
417  * @link_: node to delete from @list
418  *
419  * Removes the node link_ from the list and frees it.
420  * Compare this to list_remove_link() which removes the node
421  * without freeing it.
422  *
423  * Returns: the (possibly changed) start of the #List
424  */
425 List *
426 list_delete_link (List *list, List *link_)
427 {
428   list = _list_remove_link(list, link_);
429   checked_free(link_);
430
431   return list;
432 }
433
434 /**
435  * list_copy:
436  * @list: a #List, this must point to the top of the list
437  *
438  * Copies a #List.
439  *
440  * Note that this is a "shallow" copy. If the list elements
441  * consist of pointers to data, the pointers are copied but
442  * the actual data is not. See list_copy_deep() if you need
443  * to copy the data as well.
444  *
445  * Returns: the start of the new list that holds the same data as @list
446  */
447 List *
448 list_copy (List *list)
449 {
450   return list_copy_deep(list, NULL, NULL);
451 }
452
453 /**
454  * g_list_copy_deep:
455  * @list: a #List, this must point to the top of the list
456  * @func: (scope call): a copy function used to copy every element in the list
457  * @user_data: user data passed to the copy function @func, or %NULL
458  *
459  * Makes a full (deep) copy of a #List.
460  *
461  * In contrast with g_list_copy(), this function uses @func to make
462  * a copy of each list element, in addition to copying the list
463  * container itself.
464  *
465  * @func, as a #GCopyFunc, takes two arguments, the data to be copied
466  * and a @user_data pointer. On common processor architectures, it's safe to
467  * pass %NULL as @user_data if the copy function takes only one argument. You
468  * may get compiler warnings from this though if compiling with GCC’s
469  * `-Wcast-function-type` warning.
470  *
471  * For instance, if @list holds a list of GObjects, you can do:
472  * |[<!-- language="C" -->
473  * another_list = g_list_copy_deep (list, (GCopyFunc) g_object_ref, NULL);
474  * ]|
475  *
476  * And, to entirely free the new list, you could do:
477  * |[<!-- language="C" -->
478  * g_list_free_full (another_list, g_object_unref);
479  * ]|
480  *
481  * Returns: the start of the new list that holds a full copy of @list,
482  *     use g_list_free_full() to free it
483  *
484  * Since: 2.34
485  */
486 List *
487 list_copy_deep (List *list, list_copy_fn func, void *user_data)
488 {
489   List *new_list = NULL;
490
491   if (list)
492   {
493     List *last;
494
495     new_list = checked_malloc(sizeof(List));
496
497     if (func)
498       new_list->data = func (list->data, user_data);
499     else
500       new_list->data = list->data;
501
502     new_list->prev = NULL;
503     last = new_list;
504     list = list->next;
505
506     while (list)
507     {
508       last->next = checked_malloc(sizeof(List));
509       last->next->prev = last;
510       last = last->next;
511
512       if (func)
513         last->data = func (list->data, user_data);
514       else
515         last->data = list->data;
516
517       list = list->next;
518     }
519
520     last->next = NULL;
521   }
522
523   return new_list;
524 }
525
526 /**
527  * list_reverse:
528  * @list: a #List, this must point to the top of the list
529  *
530  * Reverses a #List.
531  * It simply switches the next and prev pointers of each element.
532  *
533  * Returns: the start of the reversed #List
534  */
535 List *
536 list_reverse (List *list)
537 {
538   List *last;
539
540   last = NULL;
541
542   while (list)
543   {
544     last = list;
545     list = last->next;
546     last->next = last->prev;
547     last->prev = list;
548   }
549
550   return last;
551 }
552
553 /**
554  * list_nth:
555  * @list: a #List, this must point to the top of the list
556  * @n: the position of the element, counting from 0
557  *
558  * Gets the element at the given position in a #List.
559  *
560  * This iterates over the list until it reaches the @n-th position. If you
561  * intend to iterate over every element, it is better to use a for-loop as
562  * described in the #List introduction.
563  *
564  * Returns: the element, or %NULL if the position is off
565  *     the end of the #List
566  */
567 List *
568 list_nth (List *list, unsigned int  n)
569 {
570   while ((n-- > 0) && list)
571     list = list->next;
572
573   return list;
574 }
575
576 /**
577  * list_nth_prev:
578  * @list: a #List
579  * @n: the position of the element, counting from 0
580  *
581  * Gets the element @n places before @list.
582  *
583  * Returns: the element, or %NULL if the position is
584  *     off the end of the #List
585  */
586 List *
587 list_nth_prev (List *list, unsigned int n)
588 {
589   while ((n-- > 0) && list)
590     list = list->prev;
591
592   return list;
593 }
594
595 /**
596  * list_nth_data:
597  * @list: a #List, this must point to the top of the list
598  * @n: the position of the element
599  *
600  * Gets the data of the element at the given position.
601  *
602  * This iterates over the list until it reaches the @n-th position. If you
603  * intend to iterate over every element, it is better to use a for-loop as
604  * described in the #List introduction.
605  *
606  * Returns: the element's data, or %NULL if the position
607  *     is off the end of the #List
608  */
609 void *
610 list_nth_data (List *list, unsigned int n)
611 {
612   while ((n-- > 0) && list)
613     list = list->next;
614
615   return list ? list->data : NULL;
616 }
617
618 /**
619  * list_position:
620  * @list: a #List, this must point to the top of the list
621  * @llink: an element in the #List
622  *
623  * Gets the position of the given element
624  * in the #List (starting from 0).
625  *
626  * Returns: the position of the element in the #List,
627  *     or -1 if the element is not found
628  */
629 int
630 list_position (List *list, List *llink)
631 {
632   int i;
633
634   i = 0;
635   while (list)
636   {
637     if (list == llink)
638       return i;
639
640     i++;
641     list = list->next;
642   }
643
644   return -1;
645 }
646
647 /**
648  * list_index:
649  * @list: a #List, this must point to the top of the list
650  * @data: the data to find
651  *
652  * Gets the position of the element containing
653  * the given data (starting from 0).
654  *
655  * Returns: the index of the element containing the data,
656  *     or -1 if the data is not found
657  */
658 int
659 list_index (List *list, const void *data)
660 {
661   int i;
662
663   i = 0;
664   while (list)
665   {
666     if (list->data == data)
667       return i;
668
669     i++;
670     list = list->next;
671   }
672
673   return -1;
674 }
675
676 /**
677  * list_last:
678  * @list: any #List element
679  *
680  * Gets the last element in a #List.
681  *
682  * Returns: the last element in the #List,
683  *     or %NULL if the #List has no elements
684  */
685 List *
686 list_last (List *list)
687 {
688   if (list)
689   {
690     while (list->next)
691       list = list->next;
692   }
693
694   return list;
695 }
696
697 /**
698  * list_first:
699  * @list: any #List element
700  *
701  * Gets the first element in a #List.
702  *
703  * Returns: the first element in the #List,
704  *     or %NULL if the #List has no elements
705  */
706 List *
707 list_first (List *list)
708 {
709   if (list)
710   {
711     while (list->prev)
712       list = list->prev;
713   }
714
715   return list;
716 }
717
718 /**
719  * list_length:
720  * @list: a #List, this must point to the top of the list
721  *
722  * Gets the number of elements in a #List.
723  *
724  * This function iterates over the whole list to count its elements.
725  * Use a #GQueue instead of a List if you regularly need the number
726  * of items. To check whether the list is non-empty, it is faster to check
727  * @list against %NULL.
728  *
729  * Returns: the number of elements in the #List
730  */
731 unsigned int
732 list_length (List *list)
733 {
734   unsigned int length;
735
736   length = 0;
737   while (list)
738   {
739     length++;
740     list = list->next;
741   }
742
743   return length;
744 }
745
746 /**
747  * list_foreach:
748  * @list: a #List, this must point to the top of the list
749  * @func: (scope call): the function to call with each element's data
750  * @user_data: user data to pass to the function
751  *
752  * Calls a function for each element of a #List.
753  *
754  * It is safe for @func to remove the element from @list, but it must
755  * not modify any part of the list after that element.
756  */
757 /**
758  * list_fn:
759  * @data: the element's data
760  * @user_data: user data passed to list_foreach() or slist_foreach()
761  *
762  * Specifies the type of functions passed to list_foreach() and
763  * slist_foreach().
764  */
765 void
766 list_foreach (List *list, list_fn func, void *user_data)
767 {
768   while (list)
769   {
770     List *next = list->next;
771
772     (*func) (list->data, user_data);
773     list = next;
774   }
775 }