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