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 "gslist.h"
32
33#include "gtestutils.h"
34#include "gslice.h"
35
36/**
37 * SECTION:linked_lists_single
38 * @title: Singly-Linked Lists
39 * @short_description: linked lists that can be iterated in one direction
40 *
41 * The #GSList structure and its associated functions provide a
42 * standard singly-linked list data structure. The benefit of this
43 * data-structure is to provide insertion/deletion operations in O(1)
44 * complexity where access/search operations are in O(n). The benefit
45 * of #GSList over #GList (doubly linked list) is that they are lighter
46 * in space as they only need to retain one pointer but it double the
47 * cost of the worst case access/search operations.
48 *
49 * Each element in the list contains a piece of data, together with a
50 * pointer which links to the next element in the list. Using this
51 * pointer it is possible to move through the list in one direction
52 * only (unlike the [double-linked lists][glib-Doubly-Linked-Lists],
53 * which allow movement in both directions).
54 *
55 * The data contained in each element can be either integer values, by
56 * using one of the [Type Conversion Macros][glib-Type-Conversion-Macros],
57 * or simply pointers to any type of data.
58 *
59 * List elements are allocated from the [slice allocator][glib-Memory-Slices],
60 * which is more efficient than allocating elements individually.
61 *
62 * Note that most of the #GSList functions expect to be passed a
63 * pointer to the first element in the list. The functions which insert
64 * elements return the new start of the list, which may have changed.
65 *
66 * There is no function to create a #GSList. %NULL is considered to be
67 * the empty list so you simply set a #GSList* to %NULL.
68 *
69 * To add elements, use g_slist_append(), g_slist_prepend(),
70 * g_slist_insert() and g_slist_insert_sorted().
71 *
72 * To remove elements, use g_slist_remove().
73 *
74 * To find elements in the list use g_slist_last(), g_slist_next(),
75 * g_slist_nth(), g_slist_nth_data(), g_slist_find() and
76 * g_slist_find_custom().
77 *
78 * To find the index of an element use g_slist_position() and
79 * g_slist_index().
80 *
81 * To call a function for each element in the list use
82 * g_slist_foreach().
83 *
84 * To free the entire list, use g_slist_free().
85 **/
86
87/**
88 * GSList:
89 * @data: holds the element's data, which can be a pointer to any kind
90 * of data, or any integer value using the
91 * [Type Conversion Macros][glib-Type-Conversion-Macros]
92 * @next: contains the link to the next element in the list.
93 *
94 * The #GSList struct is used for each element in the singly-linked
95 * list.
96 **/
97
98/**
99 * g_slist_next:
100 * @slist: an element in a #GSList.
101 *
102 * A convenience macro to get the next element in a #GSList.
103 * Note that it is considered perfectly acceptable to access
104 * @slist->next directly.
105 *
106 * Returns: the next element, or %NULL if there are no more elements.
107 **/
108
109#define _g_slist_alloc0() g_slice_new0 (GSList)
110#define _g_slist_alloc() g_slice_new (GSList)
111#define _g_slist_free1(slist) g_slice_free (GSList, slist)
112
113/**
114 * g_slist_alloc:
115 *
116 * Allocates space for one #GSList element. It is called by the
117 * g_slist_append(), g_slist_prepend(), g_slist_insert() and
118 * g_slist_insert_sorted() functions and so is rarely used on its own.
119 *
120 * Returns: a pointer to the newly-allocated #GSList element.
121 **/
122GSList*
123g_slist_alloc (void)
124{
125 return _g_slist_alloc0 ();
126}
127
128/**
129 * g_slist_free:
130 * @list: the first link of a #GSList
131 *
132 * Frees all of the memory used by a #GSList.
133 * The freed elements are returned to the slice allocator.
134 *
135 * If list elements contain dynamically-allocated memory,
136 * you should either use g_slist_free_full() or free them manually
137 * first.
138 *
139 * It can be combined with g_steal_pointer() to ensure the list head pointer
140 * is not left dangling:
141 * |[<!-- language="C" -->
142 * GSList *list_of_borrowed_things = …; /<!-- -->* (transfer container) *<!-- -->/
143 * g_slist_free (g_steal_pointer (&list_of_borrowed_things));
144 * ]|
145 */
146void
147g_slist_free (GSList *list)
148{
149 g_slice_free_chain (GSList, list, next);
150}
151
152/**
153 * g_slist_free_1:
154 * @list: a #GSList element
155 *
156 * Frees one #GSList element.
157 * It is usually used after g_slist_remove_link().
158 */
159/**
160 * g_slist_free1:
161 *
162 * A macro which does the same as g_slist_free_1().
163 *
164 * Since: 2.10
165 **/
166void
167g_slist_free_1 (GSList *list)
168{
169 _g_slist_free1 (list);
170}
171
172/**
173 * g_slist_free_full:
174 * @list: the first link of a #GSList
175 * @free_func: the function to be called to free each element's data
176 *
177 * Convenience method, which frees all the memory used by a #GSList, and
178 * calls the specified destroy function on every element's data.
179 *
180 * @free_func must not modify the list (eg, by removing the freed
181 * element from it).
182 *
183 * It can be combined with g_steal_pointer() to ensure the list head pointer
184 * is not left dangling ­— this also has the nice property that the head pointer
185 * is cleared before any of the list elements are freed, to prevent double frees
186 * from @free_func:
187 * |[<!-- language="C" -->
188 * GSList *list_of_owned_things = …; /<!-- -->* (transfer full) (element-type GObject) *<!-- -->/
189 * g_slist_free_full (g_steal_pointer (&list_of_owned_things), g_object_unref);
190 * ]|
191 *
192 * Since: 2.28
193 **/
194void
195g_slist_free_full (GSList *list,
196 GDestroyNotify free_func)
197{
198 g_slist_foreach (list, func: (GFunc) free_func, NULL);
199 g_slist_free (list);
200}
201
202/**
203 * g_slist_append:
204 * @list: a #GSList
205 * @data: the data for the new element
206 *
207 * Adds a new element on to the end of the list.
208 *
209 * The return value is the new start of the list, which may
210 * have changed, so make sure you store the new value.
211 *
212 * Note that g_slist_append() has to traverse the entire list
213 * to find the end, which is inefficient when adding multiple
214 * elements. A common idiom to avoid the inefficiency is to prepend
215 * the elements and reverse the list when all elements have been added.
216 *
217 * |[<!-- language="C" -->
218 * // Notice that these are initialized to the empty list.
219 * GSList *list = NULL, *number_list = NULL;
220 *
221 * // This is a list of strings.
222 * list = g_slist_append (list, "first");
223 * list = g_slist_append (list, "second");
224 *
225 * // This is a list of integers.
226 * number_list = g_slist_append (number_list, GINT_TO_POINTER (27));
227 * number_list = g_slist_append (number_list, GINT_TO_POINTER (14));
228 * ]|
229 *
230 * Returns: the new start of the #GSList
231 */
232GSList*
233g_slist_append (GSList *list,
234 gpointer data)
235{
236 GSList *new_list;
237 GSList *last;
238
239 new_list = _g_slist_alloc ();
240 new_list->data = data;
241 new_list->next = NULL;
242
243 if (list)
244 {
245 last = g_slist_last (list);
246 /* g_assert (last != NULL); */
247 last->next = new_list;
248
249 return list;
250 }
251 else
252 return new_list;
253}
254
255/**
256 * g_slist_prepend:
257 * @list: a #GSList
258 * @data: the data for the new element
259 *
260 * Adds a new element on to the start of the list.
261 *
262 * The return value is the new start of the list, which
263 * may have changed, so make sure you store the new value.
264 *
265 * |[<!-- language="C" -->
266 * // Notice that it is initialized to the empty list.
267 * GSList *list = NULL;
268 * list = g_slist_prepend (list, "last");
269 * list = g_slist_prepend (list, "first");
270 * ]|
271 *
272 * Returns: the new start of the #GSList
273 */
274GSList*
275g_slist_prepend (GSList *list,
276 gpointer data)
277{
278 GSList *new_list;
279
280 new_list = _g_slist_alloc ();
281 new_list->data = data;
282 new_list->next = list;
283
284 return new_list;
285}
286
287/**
288 * g_slist_insert:
289 * @list: a #GSList
290 * @data: the data for the new element
291 * @position: the position to insert the element.
292 * If this is negative, or is larger than the number
293 * of elements in the list, the new element is added on
294 * to the end of the list.
295 *
296 * Inserts a new element into the list at the given position.
297 *
298 * Returns: the new start of the #GSList
299 */
300GSList*
301g_slist_insert (GSList *list,
302 gpointer data,
303 gint position)
304{
305 GSList *prev_list;
306 GSList *tmp_list;
307 GSList *new_list;
308
309 if (position < 0)
310 return g_slist_append (list, data);
311 else if (position == 0)
312 return g_slist_prepend (list, data);
313
314 new_list = _g_slist_alloc ();
315 new_list->data = data;
316
317 if (!list)
318 {
319 new_list->next = NULL;
320 return new_list;
321 }
322
323 prev_list = NULL;
324 tmp_list = list;
325
326 while ((position-- > 0) && tmp_list)
327 {
328 prev_list = tmp_list;
329 tmp_list = tmp_list->next;
330 }
331
332 new_list->next = prev_list->next;
333 prev_list->next = new_list;
334
335 return list;
336}
337
338/**
339 * g_slist_insert_before:
340 * @slist: a #GSList
341 * @sibling: node to insert @data before
342 * @data: data to put in the newly-inserted node
343 *
344 * Inserts a node before @sibling containing @data.
345 *
346 * Returns: the new head of the list.
347 */
348GSList*
349g_slist_insert_before (GSList *slist,
350 GSList *sibling,
351 gpointer data)
352{
353 if (!slist)
354 {
355 slist = _g_slist_alloc ();
356 slist->data = data;
357 slist->next = NULL;
358 g_return_val_if_fail (sibling == NULL, slist);
359 return slist;
360 }
361 else
362 {
363 GSList *node, *last = NULL;
364
365 for (node = slist; node; last = node, node = last->next)
366 if (node == sibling)
367 break;
368 if (!last)
369 {
370 node = _g_slist_alloc ();
371 node->data = data;
372 node->next = slist;
373
374 return node;
375 }
376 else
377 {
378 node = _g_slist_alloc ();
379 node->data = data;
380 node->next = last->next;
381 last->next = node;
382
383 return slist;
384 }
385 }
386}
387
388/**
389 * g_slist_concat:
390 * @list1: a #GSList
391 * @list2: the #GSList to add to the end of the first #GSList
392 *
393 * Adds the second #GSList onto the end of the first #GSList.
394 * Note that the elements of the second #GSList are not copied.
395 * They are used directly.
396 *
397 * Returns: the start of the new #GSList
398 */
399GSList *
400g_slist_concat (GSList *list1, GSList *list2)
401{
402 if (list2)
403 {
404 if (list1)
405 g_slist_last (list: list1)->next = list2;
406 else
407 list1 = list2;
408 }
409
410 return list1;
411}
412
413static GSList*
414_g_slist_remove_data (GSList *list,
415 gconstpointer data,
416 gboolean all)
417{
418 GSList *tmp = NULL;
419 GSList **previous_ptr = &list;
420
421 while (*previous_ptr)
422 {
423 tmp = *previous_ptr;
424 if (tmp->data == data)
425 {
426 *previous_ptr = tmp->next;
427 g_slist_free_1 (list: tmp);
428 if (!all)
429 break;
430 }
431 else
432 {
433 previous_ptr = &tmp->next;
434 }
435 }
436
437 return list;
438}
439/**
440 * g_slist_remove:
441 * @list: a #GSList
442 * @data: the data of the element to remove
443 *
444 * Removes an element from a #GSList.
445 * If two elements contain the same data, only the first is removed.
446 * If none of the elements contain the data, the #GSList is unchanged.
447 *
448 * Returns: the new start of the #GSList
449 */
450GSList*
451g_slist_remove (GSList *list,
452 gconstpointer data)
453{
454 return _g_slist_remove_data (list, data, FALSE);
455}
456
457/**
458 * g_slist_remove_all:
459 * @list: a #GSList
460 * @data: data to remove
461 *
462 * Removes all list nodes with data equal to @data.
463 * Returns the new head of the list. Contrast with
464 * g_slist_remove() which removes only the first node
465 * matching the given data.
466 *
467 * Returns: new head of @list
468 */
469GSList*
470g_slist_remove_all (GSList *list,
471 gconstpointer data)
472{
473 return _g_slist_remove_data (list, data, TRUE);
474}
475
476static inline GSList*
477_g_slist_remove_link (GSList *list,
478 GSList *link)
479{
480 GSList *tmp = NULL;
481 GSList **previous_ptr = &list;
482
483 while (*previous_ptr)
484 {
485 tmp = *previous_ptr;
486 if (tmp == link)
487 {
488 *previous_ptr = tmp->next;
489 tmp->next = NULL;
490 break;
491 }
492
493 previous_ptr = &tmp->next;
494 }
495
496 return list;
497}
498
499/**
500 * g_slist_remove_link:
501 * @list: a #GSList
502 * @link_: an element in the #GSList
503 *
504 * Removes an element from a #GSList, without
505 * freeing the element. The removed element's next
506 * link is set to %NULL, so that it becomes a
507 * self-contained list with one element.
508 *
509 * Removing arbitrary nodes from a singly-linked list
510 * requires time that is proportional to the length of the list
511 * (ie. O(n)). If you find yourself using g_slist_remove_link()
512 * frequently, you should consider a different data structure,
513 * such as the doubly-linked #GList.
514 *
515 * Returns: the new start of the #GSList, without the element
516 */
517GSList*
518g_slist_remove_link (GSList *list,
519 GSList *link_)
520{
521 return _g_slist_remove_link (list, link: link_);
522}
523
524/**
525 * g_slist_delete_link:
526 * @list: a #GSList
527 * @link_: node to delete
528 *
529 * Removes the node link_ from the list and frees it.
530 * Compare this to g_slist_remove_link() which removes the node
531 * without freeing it.
532 *
533 * Removing arbitrary nodes from a singly-linked list requires time
534 * that is proportional to the length of the list (ie. O(n)). If you
535 * find yourself using g_slist_delete_link() frequently, you should
536 * consider a different data structure, such as the doubly-linked
537 * #GList.
538 *
539 * Returns: the new head of @list
540 */
541GSList*
542g_slist_delete_link (GSList *list,
543 GSList *link_)
544{
545 list = _g_slist_remove_link (list, link: link_);
546 _g_slist_free1 (link_);
547
548 return list;
549}
550
551/**
552 * g_slist_copy:
553 * @list: a #GSList
554 *
555 * Copies a #GSList.
556 *
557 * Note that this is a "shallow" copy. If the list elements
558 * consist of pointers to data, the pointers are copied but
559 * the actual data isn't. See g_slist_copy_deep() if you need
560 * to copy the data as well.
561 *
562 * Returns: a copy of @list
563 */
564GSList*
565g_slist_copy (GSList *list)
566{
567 return g_slist_copy_deep (list, NULL, NULL);
568}
569
570/**
571 * g_slist_copy_deep:
572 * @list: a #GSList
573 * @func: a copy function used to copy every element in the list
574 * @user_data: user data passed to the copy function @func, or #NULL
575 *
576 * Makes a full (deep) copy of a #GSList.
577 *
578 * In contrast with g_slist_copy(), this function uses @func to make a copy of
579 * each list element, in addition to copying the list container itself.
580 *
581 * @func, as a #GCopyFunc, takes two arguments, the data to be copied
582 * and a @user_data pointer. On common processor architectures, it's safe to
583 * pass %NULL as @user_data if the copy function takes only one argument. You
584 * may get compiler warnings from this though if compiling with GCC’s
585 * `-Wcast-function-type` warning.
586 *
587 * For instance, if @list holds a list of GObjects, you can do:
588 * |[<!-- language="C" -->
589 * another_list = g_slist_copy_deep (list, (GCopyFunc) g_object_ref, NULL);
590 * ]|
591 *
592 * And, to entirely free the new list, you could do:
593 * |[<!-- language="C" -->
594 * g_slist_free_full (another_list, g_object_unref);
595 * ]|
596 *
597 * Returns: a full copy of @list, use g_slist_free_full() to free it
598 *
599 * Since: 2.34
600 */
601GSList*
602g_slist_copy_deep (GSList *list, GCopyFunc func, gpointer user_data)
603{
604 GSList *new_list = NULL;
605
606 if (list)
607 {
608 GSList *last;
609
610 new_list = _g_slist_alloc ();
611 if (func)
612 new_list->data = func (list->data, user_data);
613 else
614 new_list->data = list->data;
615 last = new_list;
616 list = list->next;
617 while (list)
618 {
619 last->next = _g_slist_alloc ();
620 last = last->next;
621 if (func)
622 last->data = func (list->data, user_data);
623 else
624 last->data = list->data;
625 list = list->next;
626 }
627 last->next = NULL;
628 }
629
630 return new_list;
631}
632
633/**
634 * g_slist_reverse:
635 * @list: a #GSList
636 *
637 * Reverses a #GSList.
638 *
639 * Returns: the start of the reversed #GSList
640 */
641GSList*
642g_slist_reverse (GSList *list)
643{
644 GSList *prev = NULL;
645
646 while (list)
647 {
648 GSList *next = list->next;
649
650 list->next = prev;
651
652 prev = list;
653 list = next;
654 }
655
656 return prev;
657}
658
659/**
660 * g_slist_nth:
661 * @list: a #GSList
662 * @n: the position of the element, counting from 0
663 *
664 * Gets the element at the given position in a #GSList.
665 *
666 * Returns: the element, or %NULL if the position is off
667 * the end of the #GSList
668 */
669GSList*
670g_slist_nth (GSList *list,
671 guint n)
672{
673 while (n-- > 0 && list)
674 list = list->next;
675
676 return list;
677}
678
679/**
680 * g_slist_nth_data:
681 * @list: a #GSList
682 * @n: the position of the element
683 *
684 * Gets the data of the element at the given position.
685 *
686 * Returns: the element's data, or %NULL if the position
687 * is off the end of the #GSList
688 */
689gpointer
690g_slist_nth_data (GSList *list,
691 guint n)
692{
693 while (n-- > 0 && list)
694 list = list->next;
695
696 return list ? list->data : NULL;
697}
698
699/**
700 * g_slist_find:
701 * @list: a #GSList
702 * @data: the element data to find
703 *
704 * Finds the element in a #GSList which
705 * contains the given data.
706 *
707 * Returns: the found #GSList element,
708 * or %NULL if it is not found
709 */
710GSList*
711g_slist_find (GSList *list,
712 gconstpointer data)
713{
714 while (list)
715 {
716 if (list->data == data)
717 break;
718 list = list->next;
719 }
720
721 return list;
722}
723
724
725/**
726 * g_slist_find_custom:
727 * @list: a #GSList
728 * @data: user data passed to the function
729 * @func: the function to call for each element.
730 * It should return 0 when the desired element is found
731 *
732 * Finds an element in a #GSList, using a supplied function to
733 * find the desired element. It iterates over the list, calling
734 * the given function which should return 0 when the desired
735 * element is found. The function takes two #gconstpointer arguments,
736 * the #GSList element's data as the first argument and the
737 * given user data.
738 *
739 * Returns: the found #GSList element, or %NULL if it is not found
740 */
741GSList*
742g_slist_find_custom (GSList *list,
743 gconstpointer data,
744 GCompareFunc func)
745{
746 g_return_val_if_fail (func != NULL, list);
747
748 while (list)
749 {
750 if (! func (list->data, data))
751 return list;
752 list = list->next;
753 }
754
755 return NULL;
756}
757
758/**
759 * g_slist_position:
760 * @list: a #GSList
761 * @llink: an element in the #GSList
762 *
763 * Gets the position of the given element
764 * in the #GSList (starting from 0).
765 *
766 * Returns: the position of the element in the #GSList,
767 * or -1 if the element is not found
768 */
769gint
770g_slist_position (GSList *list,
771 GSList *llink)
772{
773 gint i;
774
775 i = 0;
776 while (list)
777 {
778 if (list == llink)
779 return i;
780 i++;
781 list = list->next;
782 }
783
784 return -1;
785}
786
787/**
788 * g_slist_index:
789 * @list: a #GSList
790 * @data: the data to find
791 *
792 * Gets the position of the element containing
793 * the given data (starting from 0).
794 *
795 * Returns: the index of the element containing the data,
796 * or -1 if the data is not found
797 */
798gint
799g_slist_index (GSList *list,
800 gconstpointer data)
801{
802 gint i;
803
804 i = 0;
805 while (list)
806 {
807 if (list->data == data)
808 return i;
809 i++;
810 list = list->next;
811 }
812
813 return -1;
814}
815
816/**
817 * g_slist_last:
818 * @list: a #GSList
819 *
820 * Gets the last element in a #GSList.
821 *
822 * This function iterates over the whole list.
823 *
824 * Returns: the last element in the #GSList,
825 * or %NULL if the #GSList has no elements
826 */
827GSList*
828g_slist_last (GSList *list)
829{
830 if (list)
831 {
832 while (list->next)
833 list = list->next;
834 }
835
836 return list;
837}
838
839/**
840 * g_slist_length:
841 * @list: a #GSList
842 *
843 * Gets the number of elements in a #GSList.
844 *
845 * This function iterates over the whole list to
846 * count its elements. To check whether the list is non-empty, it is faster to
847 * check @list against %NULL.
848 *
849 * Returns: the number of elements in the #GSList
850 */
851guint
852g_slist_length (GSList *list)
853{
854 guint length;
855
856 length = 0;
857 while (list)
858 {
859 length++;
860 list = list->next;
861 }
862
863 return length;
864}
865
866/**
867 * g_slist_foreach:
868 * @list: a #GSList
869 * @func: the function to call with each element's data
870 * @user_data: user data to pass to the function
871 *
872 * Calls a function for each element of a #GSList.
873 *
874 * It is safe for @func to remove the element from @list, but it must
875 * not modify any part of the list after that element.
876 */
877void
878g_slist_foreach (GSList *list,
879 GFunc func,
880 gpointer user_data)
881{
882 while (list)
883 {
884 GSList *next = list->next;
885 (*func) (list->data, user_data);
886 list = next;
887 }
888}
889
890static GSList*
891g_slist_insert_sorted_real (GSList *list,
892 gpointer data,
893 GFunc func,
894 gpointer user_data)
895{
896 GSList *tmp_list = list;
897 GSList *prev_list = NULL;
898 GSList *new_list;
899 gint cmp;
900
901 g_return_val_if_fail (func != NULL, list);
902
903 if (!list)
904 {
905 new_list = _g_slist_alloc ();
906 new_list->data = data;
907 new_list->next = NULL;
908 return new_list;
909 }
910
911 cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);
912
913 while ((tmp_list->next) && (cmp > 0))
914 {
915 prev_list = tmp_list;
916 tmp_list = tmp_list->next;
917
918 cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);
919 }
920
921 new_list = _g_slist_alloc ();
922 new_list->data = data;
923
924 if ((!tmp_list->next) && (cmp > 0))
925 {
926 tmp_list->next = new_list;
927 new_list->next = NULL;
928 return list;
929 }
930
931 if (prev_list)
932 {
933 prev_list->next = new_list;
934 new_list->next = tmp_list;
935 return list;
936 }
937 else
938 {
939 new_list->next = list;
940 return new_list;
941 }
942}
943
944/**
945 * g_slist_insert_sorted:
946 * @list: a #GSList
947 * @data: the data for the new element
948 * @func: the function to compare elements in the list.
949 * It should return a number > 0 if the first parameter
950 * comes after the second parameter in the sort order.
951 *
952 * Inserts a new element into the list, using the given
953 * comparison function to determine its position.
954 *
955 * Returns: the new start of the #GSList
956 */
957GSList*
958g_slist_insert_sorted (GSList *list,
959 gpointer data,
960 GCompareFunc func)
961{
962 return g_slist_insert_sorted_real (list, data, func: (GFunc) func, NULL);
963}
964
965/**
966 * g_slist_insert_sorted_with_data:
967 * @list: a #GSList
968 * @data: the data for the new element
969 * @func: the function to compare elements in the list.
970 * It should return a number > 0 if the first parameter
971 * comes after the second parameter in the sort order.
972 * @user_data: data to pass to comparison function
973 *
974 * Inserts a new element into the list, using the given
975 * comparison function to determine its position.
976 *
977 * Returns: the new start of the #GSList
978 *
979 * Since: 2.10
980 */
981GSList*
982g_slist_insert_sorted_with_data (GSList *list,
983 gpointer data,
984 GCompareDataFunc func,
985 gpointer user_data)
986{
987 return g_slist_insert_sorted_real (list, data, func: (GFunc) func, user_data);
988}
989
990static GSList *
991g_slist_sort_merge (GSList *l1,
992 GSList *l2,
993 GFunc compare_func,
994 gpointer user_data)
995{
996 GSList list, *l;
997 gint cmp;
998
999 l=&list;
1000
1001 while (l1 && l2)
1002 {
1003 cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data);
1004
1005 if (cmp <= 0)
1006 {
1007 l=l->next=l1;
1008 l1=l1->next;
1009 }
1010 else
1011 {
1012 l=l->next=l2;
1013 l2=l2->next;
1014 }
1015 }
1016 l->next= l1 ? l1 : l2;
1017
1018 return list.next;
1019}
1020
1021static GSList *
1022g_slist_sort_real (GSList *list,
1023 GFunc compare_func,
1024 gpointer user_data)
1025{
1026 GSList *l1, *l2;
1027
1028 if (!list)
1029 return NULL;
1030 if (!list->next)
1031 return list;
1032
1033 l1 = list;
1034 l2 = list->next;
1035
1036 while ((l2 = l2->next) != NULL)
1037 {
1038 if ((l2 = l2->next) == NULL)
1039 break;
1040 l1=l1->next;
1041 }
1042 l2 = l1->next;
1043 l1->next = NULL;
1044
1045 return g_slist_sort_merge (l1: g_slist_sort_real (list, compare_func, user_data),
1046 l2: g_slist_sort_real (list: l2, compare_func, user_data),
1047 compare_func,
1048 user_data);
1049}
1050
1051/**
1052 * g_slist_sort:
1053 * @list: a #GSList
1054 * @compare_func: the comparison function used to sort the #GSList.
1055 * This function is passed the data from 2 elements of the #GSList
1056 * and should return 0 if they are equal, a negative value if the
1057 * first element comes before the second, or a positive value if
1058 * the first element comes after the second.
1059 *
1060 * Sorts a #GSList using the given comparison function. The algorithm
1061 * used is a stable sort.
1062 *
1063 * Returns: the start of the sorted #GSList
1064 */
1065GSList *
1066g_slist_sort (GSList *list,
1067 GCompareFunc compare_func)
1068{
1069 return g_slist_sort_real (list, compare_func: (GFunc) compare_func, NULL);
1070}
1071
1072/**
1073 * g_slist_sort_with_data:
1074 * @list: a #GSList
1075 * @compare_func: comparison function
1076 * @user_data: data to pass to comparison function
1077 *
1078 * Like g_slist_sort(), but the sort function accepts a user data argument.
1079 *
1080 * Returns: new head of the list
1081 */
1082GSList *
1083g_slist_sort_with_data (GSList *list,
1084 GCompareDataFunc compare_func,
1085 gpointer user_data)
1086{
1087 return g_slist_sort_real (list, compare_func: (GFunc) compare_func, user_data);
1088}
1089
1090/**
1091 * g_clear_slist: (skip)
1092 * @slist_ptr: (not nullable): a #GSList return location
1093 * @destroy: (nullable): the function to pass to g_slist_free_full() or %NULL to not free elements
1094 *
1095 * Clears a pointer to a #GSList, freeing it and, optionally, freeing its elements using @destroy.
1096 *
1097 * @slist_ptr must be a valid pointer. If @slist_ptr points to a null #GSList, this does nothing.
1098 *
1099 * Since: 2.64
1100 */
1101void
1102(g_clear_slist) (GSList **slist_ptr,
1103 GDestroyNotify destroy)
1104{
1105 GSList *slist;
1106
1107 slist = *slist_ptr;
1108 if (slist)
1109 {
1110 *slist_ptr = NULL;
1111
1112 if (destroy)
1113 g_slist_free_full (list: slist, free_func: destroy);
1114 else
1115 g_slist_free (list: slist);
1116 }
1117}
1118

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