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  * 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  **/
 122 GSList*
 123 g_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  */
 146 void
 147 g_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  **/
 166 void
 167 g_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  **/
 194 void
 195 g_slist_free_full (GSList         *list,
 196                    GDestroyNotify  free_func)
 197 {
 198   g_slist_foreach (list, (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  */
 232 GSList*
 233 g_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  */
 274 GSList*
 275 g_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  */
 300 GSList*
 301 g_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  */
 348 GSList*
 349 g_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  */
 399 GSList *
 400 g_slist_concat (GSList *list1, GSList *list2)
 401 {
 402   if (list2)
 403     {
 404       if (list1)
 405         g_slist_last (list1)->next = list2;
 406       else
 407         list1 = list2;
 408     }
 409
 410   return list1;
 411 }
 412
 413 static 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 (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  */
 450 GSList*
 451 g_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  */
 469 GSList*
 470 g_slist_remove_all (GSList        *list,
 471                     gconstpointer  data)
 472 {
 473   return _g_slist_remove_data (list, data, TRUE);
 474 }
 475
 476 static 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  */
 517 GSList*
 518 g_slist_remove_link (GSList *list,
 519                      GSList *link_)
 520 {
 521   return _g_slist_remove_link (list, 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  */
 541 GSList*
 542 g_slist_delete_link (GSList *list,
 543                      GSList *link_)
 544 {
 545   list = _g_slist_remove_link (list, 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  */
 564 GSList*
 565 g_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  */
 601 GSList*
 602 g_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  */
 641 GSList*
 642 g_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  */
 669 GSList*
 670 g_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  */
 689 gpointer
 690 g_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  */
 710 GSList*
 711 g_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  */
 741 GSList*
 742 g_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  */
 769 gint
 770 g_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  */
 798 gint
 799 g_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  */
 827 GSList*
 828 g_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  */
 851 guint
 852 g_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  */
 877 void
 878 g_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
 890 static GSList*
 891 g_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  */
 957 GSList*
 958 g_slist_insert_sorted (GSList       *list,
 959                        gpointer      data,
 960                        GCompareFunc  func)
 961 {
 962   return g_slist_insert_sorted_real (list, data, (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  */
 981 GSList*
 982 g_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, (GFunc) func, user_data);
 988 }
 989
 990 static GSList *
 991 g_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
1021 static GSList *
1022 g_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 (g_slist_sort_real (list, compare_func, user_data),
1046                              g_slist_sort_real (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  */
1065 GSList *
1066 g_slist_sort (GSList       *list,
1067               GCompareFunc  compare_func)
1068 {
1069   return g_slist_sort_real (list, (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  */
1082 GSList *
1083 g_slist_sort_with_data (GSList           *list,
1084                         GCompareDataFunc  compare_func,
1085                         gpointer          user_data)
1086 {
1087   return g_slist_sort_real (list, (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  */
1101 void
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 (slist, destroy);
1114       else
1115         g_slist_free (slist);
1116     }
1117 }