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