glib/gslist.c

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