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