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