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