Coverage Report

Created: 2025-11-16 07:45

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