1/* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
16 */
17
18/*
19 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
20 * file for a list of people on the GLib Team. See the ChangeLog
21 * files for a list of changes. These files are distributed with
22 * GLib at ftp://ftp.gtk.org/pub/gtk/.
23 */
24
25/*
26 * MT safe
27 */
28
29#include "config.h"
30
31#include "glist.h"
32#include "gslice.h"
33#include "gmessages.h"
34
35#include "gtestutils.h"
36
37/**
38 * SECTION:linked_lists_double
39 * @title: Doubly-Linked Lists
40 * @short_description: linked lists that can be iterated over in both directions
41 *
42 * The #GList structure and its associated functions provide a standard
43 * doubly-linked list data structure. The benefit of this data-structure
44 * is to provide insertion/deletion operations in O(1) complexity where
45 * access/search operations are in O(n). The benefit of #GList over
46 * #GSList (singly linked list) is that the worst case on access/search
47 * operations is divided by two which comes at a cost in space as we need
48 * to retain two pointers in place of one.
49 *
50 * Each element in the list contains a piece of data, together with
51 * pointers which link to the previous and next elements in the list.
52 * Using these pointers it is possible to move through the list in both
53 * directions (unlike the singly-linked [GSList][glib-Singly-Linked-Lists],
54 * which only allows movement through the list in the forward direction).
55 *
56 * The double linked list does not keep track of the number of items
57 * and does not keep track of both the start and end of the list. If
58 * you want fast access to both the start and the end of the list,
59 * and/or the number of items in the list, use a
60 * [GQueue][glib-Double-ended-Queues] instead.
61 *
62 * The data contained in each element can be either integer values, by
63 * using one of the [Type Conversion Macros][glib-Type-Conversion-Macros],
64 * or simply pointers to any type of data.
65 *
66 * List elements are allocated from the [slice allocator][glib-Memory-Slices],
67 * which is more efficient than allocating elements individually.
68 *
69 * Note that most of the #GList functions expect to be passed a pointer
70 * to the first element in the list. The functions which insert
71 * elements return the new start of the list, which may have changed.
72 *
73 * There is no function to create a #GList. %NULL is considered to be
74 * a valid, empty list so you simply set a #GList* to %NULL to initialize
75 * it.
76 *
77 * To add elements, use g_list_append(), g_list_prepend(),
78 * g_list_insert() and g_list_insert_sorted().
79 *
80 * To visit all elements in the list, use a loop over the list:
81 * |[<!-- language="C" -->
82 * GList *l;
83 * for (l = list; l != NULL; l = l->next)
84 * {
85 * // do something with l->data
86 * }
87 * ]|
88 *
89 * To call a function for each element in the list, use g_list_foreach().
90 *
91 * To loop over the list and modify it (e.g. remove a certain element)
92 * a while loop is more appropriate, for example:
93 * |[<!-- language="C" -->
94 * GList *l = list;
95 * while (l != NULL)
96 * {
97 * GList *next = l->next;
98 * if (should_be_removed (l))
99 * {
100 * // possibly free l->data
101 * list = g_list_delete_link (list, l);
102 * }
103 * l = next;
104 * }
105 * ]|
106 *
107 * To remove elements, use g_list_remove().
108 *
109 * To navigate in a list, use g_list_first(), g_list_last(),
110 * g_list_next(), g_list_previous().
111 *
112 * To find elements in the list use g_list_nth(), g_list_nth_data(),
113 * g_list_find() and g_list_find_custom().
114 *
115 * To find the index of an element use g_list_position() and
116 * g_list_index().
117 *
118 * To free the entire list, use g_list_free() or g_list_free_full().
119 */
120
121/**
122 * GList:
123 * @data: holds the element's data, which can be a pointer to any kind
124 * of data, or any integer value using the
125 * [Type Conversion Macros][glib-Type-Conversion-Macros]
126 * @next: contains the link to the next element in the list
127 * @prev: contains the link to the previous element in the list
128 *
129 * The #GList struct is used for each element in a doubly-linked list.
130 **/
131
132/**
133 * g_list_previous:
134 * @list: an element in a #GList
135 *
136 * A convenience macro to get the previous element in a #GList.
137 * Note that it is considered perfectly acceptable to access
138 * @list->prev directly.
139 *
140 * Returns: the previous element, or %NULL if there are no previous
141 * elements
142 **/
143
144/**
145 * g_list_next:
146 * @list: an element in a #GList
147 *
148 * A convenience macro to get the next element in a #GList.
149 * Note that it is considered perfectly acceptable to access
150 * @list->next directly.
151 *
152 * Returns: the next element, or %NULL if there are no more elements
153 **/
154
155#define _g_list_alloc() g_slice_new (GList)
156#define _g_list_alloc0() g_slice_new0 (GList)
157#define _g_list_free1(list) g_slice_free (GList, list)
158
159/**
160 * g_list_alloc:
161 *
162 * Allocates space for one #GList element. It is called by
163 * g_list_append(), g_list_prepend(), g_list_insert() and
164 * g_list_insert_sorted() and so is rarely used on its own.
165 *
166 * Returns: a pointer to the newly-allocated #GList element
167 **/
168GList *
169g_list_alloc (void)
170{
171 return _g_list_alloc0 ();
172}
173
174/**
175 * g_list_free:
176 * @list: the first link of a #GList
177 *
178 * Frees all of the memory used by a #GList.
179 * The freed elements are returned to the slice allocator.
180 *
181 * If list elements contain dynamically-allocated memory, you should
182 * either use g_list_free_full() or free them manually first.
183 *
184 * It can be combined with g_steal_pointer() to ensure the list head pointer
185 * is not left dangling:
186 * |[<!-- language="C" -->
187 * GList *list_of_borrowed_things = …; /<!-- -->* (transfer container) *<!-- -->/
188 * g_list_free (g_steal_pointer (&list_of_borrowed_things));
189 * ]|
190 */
191void
192g_list_free (GList *list)
193{
194 g_slice_free_chain (GList, list, next);
195}
196
197/**
198 * g_list_free_1:
199 * @list: a #GList element
200 *
201 * Frees one #GList element, but does not update links from the next and
202 * previous elements in the list, so you should not call this function on an
203 * element that is currently part of a list.
204 *
205 * It is usually used after g_list_remove_link().
206 */
207/**
208 * g_list_free1:
209 *
210 * Another name for g_list_free_1().
211 **/
212void
213g_list_free_1 (GList *list)
214{
215 _g_list_free1 (list);
216}
217
218/**
219 * g_list_free_full:
220 * @list: the first link of a #GList
221 * @free_func: the function to be called to free each element's data
222 *
223 * Convenience method, which frees all the memory used by a #GList,
224 * and calls @free_func on every element's data.
225 *
226 * @free_func must not modify the list (eg, by removing the freed
227 * element from it).
228 *
229 * It can be combined with g_steal_pointer() to ensure the list head pointer
230 * is not left dangling ­— this also has the nice property that the head pointer
231 * is cleared before any of the list elements are freed, to prevent double frees
232 * from @free_func:
233 * |[<!-- language="C" -->
234 * GList *list_of_owned_things = …; /<!-- -->* (transfer full) (element-type GObject) *<!-- -->/
235 * g_list_free_full (g_steal_pointer (&list_of_owned_things), g_object_unref);
236 * ]|
237 *
238 * Since: 2.28
239 */
240void
241g_list_free_full (GList *list,
242 GDestroyNotify free_func)
243{
244 g_list_foreach (list, func: (GFunc) free_func, NULL);
245 g_list_free (list);
246}
247
248/**
249 * g_list_append:
250 * @list: a pointer to a #GList
251 * @data: the data for the new element
252 *
253 * Adds a new element on to the end of the list.
254 *
255 * Note that the return value is the new start of the list,
256 * if @list was empty; make sure you store the new value.
257 *
258 * g_list_append() has to traverse the entire list to find the end,
259 * which is inefficient when adding multiple elements. A common idiom
260 * to avoid the inefficiency is to use g_list_prepend() and reverse
261 * the list with g_list_reverse() when all elements have been added.
262 *
263 * |[<!-- language="C" -->
264 * // Notice that these are initialized to the empty list.
265 * GList *string_list = NULL, *number_list = NULL;
266 *
267 * // This is a list of strings.
268 * string_list = g_list_append (string_list, "first");
269 * string_list = g_list_append (string_list, "second");
270 *
271 * // This is a list of integers.
272 * number_list = g_list_append (number_list, GINT_TO_POINTER (27));
273 * number_list = g_list_append (number_list, GINT_TO_POINTER (14));
274 * ]|
275 *
276 * Returns: either @list or the new start of the #GList if @list was %NULL
277 */
278GList *
279g_list_append (GList *list,
280 gpointer data)
281{
282 GList *new_list;
283 GList *last;
284
285 new_list = _g_list_alloc ();
286 new_list->data = data;
287 new_list->next = NULL;
288
289 if (list)
290 {
291 last = g_list_last (list);
292 /* g_assert (last != NULL); */
293 last->next = new_list;
294 new_list->prev = last;
295
296 return list;
297 }
298 else
299 {
300 new_list->prev = NULL;
301 return new_list;
302 }
303}
304
305/**
306 * g_list_prepend:
307 * @list: a pointer to a #GList, this must point to the top of the list
308 * @data: the data for the new element
309 *
310 * Prepends a new element on to the start of the list.
311 *
312 * Note that the return value is the new start of the list,
313 * which will have changed, so make sure you store the new value.
314 *
315 * |[<!-- language="C" -->
316 * // Notice that it is initialized to the empty list.
317 * GList *list = NULL;
318 *
319 * list = g_list_prepend (list, "last");
320 * list = g_list_prepend (list, "first");
321 * ]|
322 *
323 * Do not use this function to prepend a new element to a different
324 * element than the start of the list. Use g_list_insert_before() instead.
325 *
326 * Returns: a pointer to the newly prepended element, which is the new
327 * start of the #GList
328 */
329GList *
330g_list_prepend (GList *list,
331 gpointer data)
332{
333 GList *new_list;
334
335 new_list = _g_list_alloc ();
336 new_list->data = data;
337 new_list->next = list;
338
339 if (list)
340 {
341 new_list->prev = list->prev;
342 if (list->prev)
343 list->prev->next = new_list;
344 list->prev = new_list;
345 }
346 else
347 new_list->prev = NULL;
348
349 return new_list;
350}
351
352/**
353 * g_list_insert:
354 * @list: a pointer to a #GList, this must point to the top of the list
355 * @data: the data for the new element
356 * @position: the position to insert the element. If this is
357 * negative, or is larger than the number of elements in the
358 * list, the new element is added on to the end of the list.
359 *
360 * Inserts a new element into the list at the given position.
361 *
362 * Returns: the (possibly changed) start of the #GList
363 */
364GList *
365g_list_insert (GList *list,
366 gpointer data,
367 gint position)
368{
369 GList *new_list;
370 GList *tmp_list;
371
372 if (position < 0)
373 return g_list_append (list, data);
374 else if (position == 0)
375 return g_list_prepend (list, data);
376
377 tmp_list = g_list_nth (list, n: position);
378 if (!tmp_list)
379 return g_list_append (list, data);
380
381 new_list = _g_list_alloc ();
382 new_list->data = data;
383 new_list->prev = tmp_list->prev;
384 tmp_list->prev->next = new_list;
385 new_list->next = tmp_list;
386 tmp_list->prev = new_list;
387
388 return list;
389}
390
391/**
392 * g_list_insert_before_link:
393 * @list: a pointer to a #GList, this must point to the top of the list
394 * @sibling: (nullable): the list element before which the new element
395 * is inserted or %NULL to insert at the end of the list
396 * @link_: the list element to be added, which must not be part of
397 * any other list
398 *
399 * Inserts @link_ into the list before the given position.
400 *
401 * Returns: the (possibly changed) start of the #GList
402 *
403 * Since: 2.62
404 */
405GList *
406g_list_insert_before_link (GList *list,
407 GList *sibling,
408 GList *link_)
409{
410 g_return_val_if_fail (link_ != NULL, list);
411 g_return_val_if_fail (link_->prev == NULL, list);
412 g_return_val_if_fail (link_->next == NULL, list);
413
414 if (list == NULL)
415 {
416 g_return_val_if_fail (sibling == NULL, list);
417 return link_;
418 }
419 else if (sibling != NULL)
420 {
421 link_->prev = sibling->prev;
422 link_->next = sibling;
423 sibling->prev = link_;
424 if (link_->prev != NULL)
425 {
426 link_->prev->next = link_;
427 return list;
428 }
429 else
430 {
431 g_return_val_if_fail (sibling == list, link_);
432 return link_;
433 }
434 }
435 else
436 {
437 GList *last;
438
439 for (last = list; last->next != NULL; last = last->next) {}
440
441 last->next = link_;
442 last->next->prev = last;
443 last->next->next = NULL;
444
445 return list;
446 }
447}
448
449/**
450 * g_list_insert_before:
451 * @list: a pointer to a #GList, this must point to the top of the list
452 * @sibling: the list element before which the new element
453 * is inserted or %NULL to insert at the end of the list
454 * @data: the data for the new element
455 *
456 * Inserts a new element into the list before the given position.
457 *
458 * Returns: the (possibly changed) start of the #GList
459 */
460GList *
461g_list_insert_before (GList *list,
462 GList *sibling,
463 gpointer data)
464{
465 if (list == NULL)
466 {
467 list = g_list_alloc ();
468 list->data = data;
469 g_return_val_if_fail (sibling == NULL, list);
470 return list;
471 }
472 else if (sibling != NULL)
473 {
474 GList *node;
475
476 node = _g_list_alloc ();
477 node->data = data;
478 node->prev = sibling->prev;
479 node->next = sibling;
480 sibling->prev = node;
481 if (node->prev != NULL)
482 {
483 node->prev->next = node;
484 return list;
485 }
486 else
487 {
488 g_return_val_if_fail (sibling == list, node);
489 return node;
490 }
491 }
492 else
493 {
494 GList *last;
495
496 for (last = list; last->next != NULL; last = last->next) {}
497
498 last->next = _g_list_alloc ();
499 last->next->data = data;
500 last->next->prev = last;
501 last->next->next = NULL;
502
503 return list;
504 }
505}
506
507/**
508 * g_list_concat:
509 * @list1: a #GList, this must point to the top of the list
510 * @list2: the #GList to add to the end of the first #GList,
511 * this must point to the top of the list
512 *
513 * Adds the second #GList onto the end of the first #GList.
514 * Note that the elements of the second #GList are not copied.
515 * They are used directly.
516 *
517 * This function is for example used to move an element in the list.
518 * The following example moves an element to the top of the list:
519 * |[<!-- language="C" -->
520 * list = g_list_remove_link (list, llink);
521 * list = g_list_concat (llink, list);
522 * ]|
523 *
524 * Returns: the start of the new #GList, which equals @list1 if not %NULL
525 */
526GList *
527g_list_concat (GList *list1,
528 GList *list2)
529{
530 GList *tmp_list;
531
532 if (list2)
533 {
534 tmp_list = g_list_last (list: list1);
535 if (tmp_list)
536 tmp_list->next = list2;
537 else
538 list1 = list2;
539 list2->prev = tmp_list;
540 }
541
542 return list1;
543}
544
545static inline GList *
546_g_list_remove_link (GList *list,
547 GList *link)
548{
549 if (link == NULL)
550 return list;
551
552 if (link->prev)
553 {
554 if (link->prev->next == link)
555 link->prev->next = link->next;
556 else
557 g_warning ("corrupted double-linked list detected");
558 }
559 if (link->next)
560 {
561 if (link->next->prev == link)
562 link->next->prev = link->prev;
563 else
564 g_warning ("corrupted double-linked list detected");
565 }
566
567 if (link == list)
568 list = list->next;
569
570 link->next = NULL;
571 link->prev = NULL;
572
573 return list;
574}
575
576/**
577 * g_list_remove:
578 * @list: a #GList, this must point to the top of the list
579 * @data: the data of the element to remove
580 *
581 * Removes an element from a #GList.
582 * If two elements contain the same data, only the first is removed.
583 * If none of the elements contain the data, the #GList is unchanged.
584 *
585 * Returns: the (possibly changed) start of the #GList
586 */
587GList *
588g_list_remove (GList *list,
589 gconstpointer data)
590{
591 GList *tmp;
592
593 tmp = list;
594 while (tmp)
595 {
596 if (tmp->data != data)
597 tmp = tmp->next;
598 else
599 {
600 list = _g_list_remove_link (list, link: tmp);
601 _g_list_free1 (tmp);
602
603 break;
604 }
605 }
606 return list;
607}
608
609/**
610 * g_list_remove_all:
611 * @list: a #GList, this must point to the top of the list
612 * @data: data to remove
613 *
614 * Removes all list nodes with data equal to @data.
615 * Returns the new head of the list. Contrast with
616 * g_list_remove() which removes only the first node
617 * matching the given data.
618 *
619 * Returns: the (possibly changed) start of the #GList
620 */
621GList *
622g_list_remove_all (GList *list,
623 gconstpointer data)
624{
625 GList *tmp = list;
626
627 while (tmp)
628 {
629 if (tmp->data != data)
630 tmp = tmp->next;
631 else
632 {
633 GList *next = tmp->next;
634
635 if (tmp->prev)
636 tmp->prev->next = next;
637 else
638 list = next;
639 if (next)
640 next->prev = tmp->prev;
641
642 _g_list_free1 (tmp);
643 tmp = next;
644 }
645 }
646 return list;
647}
648
649/**
650 * g_list_remove_link:
651 * @list: a #GList, this must point to the top of the list
652 * @llink: an element in the #GList
653 *
654 * Removes an element from a #GList, without freeing the element.
655 * The removed element's prev and next links are set to %NULL, so
656 * that it becomes a self-contained list with one element.
657 *
658 * This function is for example used to move an element in the list
659 * (see the example for g_list_concat()) or to remove an element in
660 * the list before freeing its data:
661 * |[<!-- language="C" -->
662 * list = g_list_remove_link (list, llink);
663 * free_some_data_that_may_access_the_list_again (llink->data);
664 * g_list_free (llink);
665 * ]|
666 *
667 * Returns: the (possibly changed) start of the #GList
668 */
669GList *
670g_list_remove_link (GList *list,
671 GList *llink)
672{
673 return _g_list_remove_link (list, link: llink);
674}
675
676/**
677 * g_list_delete_link:
678 * @list: a #GList, this must point to the top of the list
679 * @link_: node to delete from @list
680 *
681 * Removes the node link_ from the list and frees it.
682 * Compare this to g_list_remove_link() which removes the node
683 * without freeing it.
684 *
685 * Returns: the (possibly changed) start of the #GList
686 */
687GList *
688g_list_delete_link (GList *list,
689 GList *link_)
690{
691 list = _g_list_remove_link (list, link: link_);
692 _g_list_free1 (link_);
693
694 return list;
695}
696
697/**
698 * g_list_copy:
699 * @list: a #GList, this must point to the top of the list
700 *
701 * Copies a #GList.
702 *
703 * Note that this is a "shallow" copy. If the list elements
704 * consist of pointers to data, the pointers are copied but
705 * the actual data is not. See g_list_copy_deep() if you need
706 * to copy the data as well.
707 *
708 * Returns: the start of the new list that holds the same data as @list
709 */
710GList *
711g_list_copy (GList *list)
712{
713 return g_list_copy_deep (list, NULL, NULL);
714}
715
716/**
717 * g_list_copy_deep:
718 * @list: a #GList, this must point to the top of the list
719 * @func: a copy function used to copy every element in the list
720 * @user_data: user data passed to the copy function @func, or %NULL
721 *
722 * Makes a full (deep) copy of a #GList.
723 *
724 * In contrast with g_list_copy(), this function uses @func to make
725 * a copy of each list element, in addition to copying the list
726 * container itself.
727 *
728 * @func, as a #GCopyFunc, takes two arguments, the data to be copied
729 * and a @user_data pointer. On common processor architectures, it's safe to
730 * pass %NULL as @user_data if the copy function takes only one argument. You
731 * may get compiler warnings from this though if compiling with GCC’s
732 * `-Wcast-function-type` warning.
733 *
734 * For instance, if @list holds a list of GObjects, you can do:
735 * |[<!-- language="C" -->
736 * another_list = g_list_copy_deep (list, (GCopyFunc) g_object_ref, NULL);
737 * ]|
738 *
739 * And, to entirely free the new list, you could do:
740 * |[<!-- language="C" -->
741 * g_list_free_full (another_list, g_object_unref);
742 * ]|
743 *
744 * Returns: the start of the new list that holds a full copy of @list,
745 * use g_list_free_full() to free it
746 *
747 * Since: 2.34
748 */
749GList *
750g_list_copy_deep (GList *list,
751 GCopyFunc func,
752 gpointer user_data)
753{
754 GList *new_list = NULL;
755
756 if (list)
757 {
758 GList *last;
759
760 new_list = _g_list_alloc ();
761 if (func)
762 new_list->data = func (list->data, user_data);
763 else
764 new_list->data = list->data;
765 new_list->prev = NULL;
766 last = new_list;
767 list = list->next;
768 while (list)
769 {
770 last->next = _g_list_alloc ();
771 last->next->prev = last;
772 last = last->next;
773 if (func)
774 last->data = func (list->data, user_data);
775 else
776 last->data = list->data;
777 list = list->next;
778 }
779 last->next = NULL;
780 }
781
782 return new_list;
783}
784
785/**
786 * g_list_reverse:
787 * @list: a #GList, this must point to the top of the list
788 *
789 * Reverses a #GList.
790 * It simply switches the next and prev pointers of each element.
791 *
792 * Returns: the start of the reversed #GList
793 */
794GList *
795g_list_reverse (GList *list)
796{
797 GList *last;
798
799 last = NULL;
800 while (list)
801 {
802 last = list;
803 list = last->next;
804 last->next = last->prev;
805 last->prev = list;
806 }
807
808 return last;
809}
810
811/**
812 * g_list_nth:
813 * @list: a #GList, this must point to the top of the list
814 * @n: the position of the element, counting from 0
815 *
816 * Gets the element at the given position in a #GList.
817 *
818 * This iterates over the list until it reaches the @n-th position. If you
819 * intend to iterate over every element, it is better to use a for-loop as
820 * described in the #GList introduction.
821 *
822 * Returns: the element, or %NULL if the position is off
823 * the end of the #GList
824 */
825GList *
826g_list_nth (GList *list,
827 guint n)
828{
829 while ((n-- > 0) && list)
830 list = list->next;
831
832 return list;
833}
834
835/**
836 * g_list_nth_prev:
837 * @list: a #GList
838 * @n: the position of the element, counting from 0
839 *
840 * Gets the element @n places before @list.
841 *
842 * Returns: the element, or %NULL if the position is
843 * off the end of the #GList
844 */
845GList *
846g_list_nth_prev (GList *list,
847 guint n)
848{
849 while ((n-- > 0) && list)
850 list = list->prev;
851
852 return list;
853}
854
855/**
856 * g_list_nth_data:
857 * @list: a #GList, this must point to the top of the list
858 * @n: the position of the element
859 *
860 * Gets the data of the element at the given position.
861 *
862 * This iterates over the list until it reaches the @n-th position. If you
863 * intend to iterate over every element, it is better to use a for-loop as
864 * described in the #GList introduction.
865 *
866 * Returns: the element's data, or %NULL if the position
867 * is off the end of the #GList
868 */
869gpointer
870g_list_nth_data (GList *list,
871 guint n)
872{
873 while ((n-- > 0) && list)
874 list = list->next;
875
876 return list ? list->data : NULL;
877}
878
879/**
880 * g_list_find:
881 * @list: a #GList, this must point to the top of the list
882 * @data: the element data to find
883 *
884 * Finds the element in a #GList which contains the given data.
885 *
886 * Returns: the found #GList element, or %NULL if it is not found
887 */
888GList *
889g_list_find (GList *list,
890 gconstpointer data)
891{
892 while (list)
893 {
894 if (list->data == data)
895 break;
896 list = list->next;
897 }
898
899 return list;
900}
901
902/**
903 * g_list_find_custom:
904 * @list: a #GList, this must point to the top of the list
905 * @data: user data passed to the function
906 * @func: the function to call for each element.
907 * It should return 0 when the desired element is found
908 *
909 * Finds an element in a #GList, using a supplied function to
910 * find the desired element. It iterates over the list, calling
911 * the given function which should return 0 when the desired
912 * element is found. The function takes two #gconstpointer arguments,
913 * the #GList element's data as the first argument and the
914 * given user data.
915 *
916 * Returns: the found #GList element, or %NULL if it is not found
917 */
918GList *
919g_list_find_custom (GList *list,
920 gconstpointer data,
921 GCompareFunc func)
922{
923 g_return_val_if_fail (func != NULL, list);
924
925 while (list)
926 {
927 if (! func (list->data, data))
928 return list;
929 list = list->next;
930 }
931
932 return NULL;
933}
934
935/**
936 * g_list_position:
937 * @list: a #GList, this must point to the top of the list
938 * @llink: an element in the #GList
939 *
940 * Gets the position of the given element
941 * in the #GList (starting from 0).
942 *
943 * Returns: the position of the element in the #GList,
944 * or -1 if the element is not found
945 */
946gint
947g_list_position (GList *list,
948 GList *llink)
949{
950 gint i;
951
952 i = 0;
953 while (list)
954 {
955 if (list == llink)
956 return i;
957 i++;
958 list = list->next;
959 }
960
961 return -1;
962}
963
964/**
965 * g_list_index:
966 * @list: a #GList, this must point to the top of the list
967 * @data: the data to find
968 *
969 * Gets the position of the element containing
970 * the given data (starting from 0).
971 *
972 * Returns: the index of the element containing the data,
973 * or -1 if the data is not found
974 */
975gint
976g_list_index (GList *list,
977 gconstpointer data)
978{
979 gint i;
980
981 i = 0;
982 while (list)
983 {
984 if (list->data == data)
985 return i;
986 i++;
987 list = list->next;
988 }
989
990 return -1;
991}
992
993/**
994 * g_list_last:
995 * @list: any #GList element
996 *
997 * Gets the last element in a #GList.
998 *
999 * Returns: the last element in the #GList,
1000 * or %NULL if the #GList has no elements
1001 */
1002GList *
1003g_list_last (GList *list)
1004{
1005 if (list)
1006 {
1007 while (list->next)
1008 list = list->next;
1009 }
1010
1011 return list;
1012}
1013
1014/**
1015 * g_list_first:
1016 * @list: any #GList element
1017 *
1018 * Gets the first element in a #GList.
1019 *
1020 * Returns: the first element in the #GList,
1021 * or %NULL if the #GList has no elements
1022 */
1023GList *
1024g_list_first (GList *list)
1025{
1026 if (list)
1027 {
1028 while (list->prev)
1029 list = list->prev;
1030 }
1031
1032 return list;
1033}
1034
1035/**
1036 * g_list_length:
1037 * @list: a #GList, this must point to the top of the list
1038 *
1039 * Gets the number of elements in a #GList.
1040 *
1041 * This function iterates over the whole list to count its elements.
1042 * Use a #GQueue instead of a GList if you regularly need the number
1043 * of items. To check whether the list is non-empty, it is faster to check
1044 * @list against %NULL.
1045 *
1046 * Returns: the number of elements in the #GList
1047 */
1048guint
1049g_list_length (GList *list)
1050{
1051 guint length;
1052
1053 length = 0;
1054 while (list)
1055 {
1056 length++;
1057 list = list->next;
1058 }
1059
1060 return length;
1061}
1062
1063/**
1064 * g_list_foreach:
1065 * @list: a #GList, this must point to the top of the list
1066 * @func: the function to call with each element's data
1067 * @user_data: user data to pass to the function
1068 *
1069 * Calls a function for each element of a #GList.
1070 *
1071 * It is safe for @func to remove the element from @list, but it must
1072 * not modify any part of the list after that element.
1073 */
1074/**
1075 * GFunc:
1076 * @data: the element's data
1077 * @user_data: user data passed to g_list_foreach() or g_slist_foreach()
1078 *
1079 * Specifies the type of functions passed to g_list_foreach() and
1080 * g_slist_foreach().
1081 */
1082void
1083g_list_foreach (GList *list,
1084 GFunc func,
1085 gpointer user_data)
1086{
1087 while (list)
1088 {
1089 GList *next = list->next;
1090 (*func) (list->data, user_data);
1091 list = next;
1092 }
1093}
1094
1095static GList*
1096g_list_insert_sorted_real (GList *list,
1097 gpointer data,
1098 GFunc func,
1099 gpointer user_data)
1100{
1101 GList *tmp_list = list;
1102 GList *new_list;
1103 gint cmp;
1104
1105 g_return_val_if_fail (func != NULL, list);
1106
1107 if (!list)
1108 {
1109 new_list = _g_list_alloc0 ();
1110 new_list->data = data;
1111 return new_list;
1112 }
1113
1114 cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);
1115
1116 while ((tmp_list->next) && (cmp > 0))
1117 {
1118 tmp_list = tmp_list->next;
1119
1120 cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);
1121 }
1122
1123 new_list = _g_list_alloc0 ();
1124 new_list->data = data;
1125
1126 if ((!tmp_list->next) && (cmp > 0))
1127 {
1128 tmp_list->next = new_list;
1129 new_list->prev = tmp_list;
1130 return list;
1131 }
1132
1133 if (tmp_list->prev)
1134 {
1135 tmp_list->prev->next = new_list;
1136 new_list->prev = tmp_list->prev;
1137 }
1138 new_list->next = tmp_list;
1139 tmp_list->prev = new_list;
1140
1141 if (tmp_list == list)
1142 return new_list;
1143 else
1144 return list;
1145}
1146
1147/**
1148 * g_list_insert_sorted:
1149 * @list: a pointer to a #GList, this must point to the top of the
1150 * already sorted list
1151 * @data: the data for the new element
1152 * @func: the function to compare elements in the list. It should
1153 * return a number > 0 if the first parameter comes after the
1154 * second parameter in the sort order.
1155 *
1156 * Inserts a new element into the list, using the given comparison
1157 * function to determine its position.
1158 *
1159 * If you are adding many new elements to a list, and the number of
1160 * new elements is much larger than the length of the list, use
1161 * g_list_prepend() to add the new items and sort the list afterwards
1162 * with g_list_sort().
1163 *
1164 * Returns: the (possibly changed) start of the #GList
1165 */
1166GList *
1167g_list_insert_sorted (GList *list,
1168 gpointer data,
1169 GCompareFunc func)
1170{
1171 return g_list_insert_sorted_real (list, data, func: (GFunc) func, NULL);
1172}
1173
1174/**
1175 * g_list_insert_sorted_with_data:
1176 * @list: a pointer to a #GList, this must point to the top of the
1177 * already sorted list
1178 * @data: the data for the new element
1179 * @func: the function to compare elements in the list. It should
1180 * return a number > 0 if the first parameter comes after the
1181 * second parameter in the sort order.
1182 * @user_data: user data to pass to comparison function
1183 *
1184 * Inserts a new element into the list, using the given comparison
1185 * function to determine its position.
1186 *
1187 * If you are adding many new elements to a list, and the number of
1188 * new elements is much larger than the length of the list, use
1189 * g_list_prepend() to add the new items and sort the list afterwards
1190 * with g_list_sort().
1191 *
1192 * Returns: the (possibly changed) start of the #GList
1193 *
1194 * Since: 2.10
1195 */
1196GList *
1197g_list_insert_sorted_with_data (GList *list,
1198 gpointer data,
1199 GCompareDataFunc func,
1200 gpointer user_data)
1201{
1202 return g_list_insert_sorted_real (list, data, func: (GFunc) func, user_data);
1203}
1204
1205static GList *
1206g_list_sort_merge (GList *l1,
1207 GList *l2,
1208 GFunc compare_func,
1209 gpointer user_data)
1210{
1211 GList list, *l, *lprev;
1212 gint cmp;
1213
1214 l = &list;
1215 lprev = NULL;
1216
1217 while (l1 && l2)
1218 {
1219 cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data);
1220
1221 if (cmp <= 0)
1222 {
1223 l->next = l1;
1224 l1 = l1->next;
1225 }
1226 else
1227 {
1228 l->next = l2;
1229 l2 = l2->next;
1230 }
1231 l = l->next;
1232 l->prev = lprev;
1233 lprev = l;
1234 }
1235 l->next = l1 ? l1 : l2;
1236 l->next->prev = l;
1237
1238 return list.next;
1239}
1240
1241static GList *
1242g_list_sort_real (GList *list,
1243 GFunc compare_func,
1244 gpointer user_data)
1245{
1246 GList *l1, *l2;
1247
1248 if (!list)
1249 return NULL;
1250 if (!list->next)
1251 return list;
1252
1253 l1 = list;
1254 l2 = list->next;
1255
1256 while ((l2 = l2->next) != NULL)
1257 {
1258 if ((l2 = l2->next) == NULL)
1259 break;
1260 l1 = l1->next;
1261 }
1262 l2 = l1->next;
1263 l1->next = NULL;
1264
1265 return g_list_sort_merge (l1: g_list_sort_real (list, compare_func, user_data),
1266 l2: g_list_sort_real (list: l2, compare_func, user_data),
1267 compare_func,
1268 user_data);
1269}
1270
1271/**
1272 * g_list_sort:
1273 * @list: a #GList, this must point to the top of the list
1274 * @compare_func: the comparison function used to sort the #GList.
1275 * This function is passed the data from 2 elements of the #GList
1276 * and should return 0 if they are equal, a negative value if the
1277 * first element comes before the second, or a positive value if
1278 * the first element comes after the second.
1279 *
1280 * Sorts a #GList using the given comparison function. The algorithm
1281 * used is a stable sort.
1282 *
1283 * Returns: the (possibly changed) start of the #GList
1284 */
1285/**
1286 * GCompareFunc:
1287 * @a: a value
1288 * @b: a value to compare with
1289 *
1290 * Specifies the type of a comparison function used to compare two
1291 * values. The function should return a negative integer if the first
1292 * value comes before the second, 0 if they are equal, or a positive
1293 * integer if the first value comes after the second.
1294 *
1295 * Returns: negative value if @a < @b; zero if @a = @b; positive
1296 * value if @a > @b
1297 */
1298GList *
1299g_list_sort (GList *list,
1300 GCompareFunc compare_func)
1301{
1302 return g_list_sort_real (list, compare_func: (GFunc) compare_func, NULL);
1303}
1304
1305/**
1306 * g_list_sort_with_data:
1307 * @list: a #GList, this must point to the top of the list
1308 * @compare_func: comparison function
1309 * @user_data: user data to pass to comparison function
1310 *
1311 * Like g_list_sort(), but the comparison function accepts
1312 * a user data argument.
1313 *
1314 * Returns: the (possibly changed) start of the #GList
1315 */
1316/**
1317 * GCompareDataFunc:
1318 * @a: a value
1319 * @b: a value to compare with
1320 * @user_data: user data
1321 *
1322 * Specifies the type of a comparison function used to compare two
1323 * values. The function should return a negative integer if the first
1324 * value comes before the second, 0 if they are equal, or a positive
1325 * integer if the first value comes after the second.
1326 *
1327 * Returns: negative value if @a < @b; zero if @a = @b; positive
1328 * value if @a > @b
1329 */
1330GList *
1331g_list_sort_with_data (GList *list,
1332 GCompareDataFunc compare_func,
1333 gpointer user_data)
1334{
1335 return g_list_sort_real (list, compare_func: (GFunc) compare_func, user_data);
1336}
1337
1338/**
1339 * g_clear_list: (skip)
1340 * @list_ptr: (not nullable): a #GList return location
1341 * @destroy: (nullable): the function to pass to g_list_free_full() or %NULL to not free elements
1342 *
1343 * Clears a pointer to a #GList, freeing it and, optionally, freeing its elements using @destroy.
1344 *
1345 * @list_ptr must be a valid pointer. If @list_ptr points to a null #GList, this does nothing.
1346 *
1347 * Since: 2.64
1348 */
1349void
1350(g_clear_list) (GList **list_ptr,
1351 GDestroyNotify destroy)
1352{
1353 GList *list;
1354
1355 list = *list_ptr;
1356 if (list)
1357 {
1358 *list_ptr = NULL;
1359
1360 if (destroy)
1361 g_list_free_full (list, free_func: destroy);
1362 else
1363 g_list_free (list);
1364 }
1365}
1366

source code of gtk/subprojects/glib/glib/glist.c