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, and
 201  * 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   g_slist_foreach (list, (GFunc) free_func, NULL);
 210   g_slist_free (list);
 211 }
 212
 213 /**
 214  * g_slist_append:
 215  * @list: a #GSList
 216  * @data: the data for the new element
 217  *
 218  * Adds a new element on to the end of the list.
 219  *
 220  * <note><para>
 221  * The return value is the new start of the list, which may
 222  * have changed, so make sure you store the new value.
 223  * </para></note>
 224  *
 225  * <note><para>
 226  * Note that g_slist_append() has to traverse the entire list
 227  * to find the end, which is inefficient when adding multiple
 228  * elements. A common idiom to avoid the inefficiency is to prepend
 229  * the elements and reverse the list when all elements have been added.
 230  * </para></note>
 231  *
 232  * |[
 233  * /&ast; Notice that these are initialized to the empty list. &ast;/
 234  * GSList *list = NULL, *number_list = NULL;
 235  *
 236  * /&ast; This is a list of strings. &ast;/
 237  * list = g_slist_append (list, "first");
 238  * list = g_slist_append (list, "second");
 239  *
 240  * /&ast; This is a list of integers. &ast;/
 241  * number_list = g_slist_append (number_list, GINT_TO_POINTER (27));
 242  * number_list = g_slist_append (number_list, GINT_TO_POINTER (14));
 243  * ]|
 244  *
 245  * Returns: the new start of the #GSList
 246  */
 247 GSList*
 248 g_slist_append (GSList   *list,
 249                 gpointer  data)
 250 {
 251   GSList *new_list;
 252   GSList *last;
 253
 254   new_list = _g_slist_alloc ();
 255   new_list->data = data;
 256   new_list->next = NULL;
 257
 258   if (list)
 259     {
 260       last = g_slist_last (list);
 261       /* g_assert (last != NULL); */
 262       last->next = new_list;
 263
 264       return list;
 265     }
 266   else
 267     return new_list;
 268 }
 269
 270 /**
 271  * g_slist_prepend:
 272  * @list: a #GSList
 273  * @data: the data for the new element
 274  *
 275  * Adds a new element on to the start of the list.
 276  *
 277  * <note><para>
 278  * The return value is the new start of the list, which
 279  * may have changed, so make sure you store the new value.
 280  * </para></note>
 281  *
 282  * |[
 283  * /&ast; Notice that it is initialized to the empty list. &ast;/
 284  * GSList *list = NULL;
 285  * list = g_slist_prepend (list, "last");
 286  * list = g_slist_prepend (list, "first");
 287  * ]|
 288  *
 289  * Returns: the new start of the #GSList
 290  */
 291 GSList*
 292 g_slist_prepend (GSList   *list,
 293                  gpointer  data)
 294 {
 295   GSList *new_list;
 296
 297   new_list = _g_slist_alloc ();
 298   new_list->data = data;
 299   new_list->next = list;
 300
 301   return new_list;
 302 }
 303
 304 /**
 305  * g_slist_insert:
 306  * @list: a #GSList
 307  * @data: the data for the new element
 308  * @position: the position to insert the element.
 309  *     If this is negative, or is larger than the number
 310  *     of elements in the list, the new element is added on
 311  *     to the end of the list.
 312  *
 313  * Inserts a new element into the list at the given position.
 314  *
 315  * Returns: the new start of the #GSList
 316  */
 317 GSList*
 318 g_slist_insert (GSList   *list,
 319                 gpointer  data,
 320                 gint      position)
 321 {
 322   GSList *prev_list;
 323   GSList *tmp_list;
 324   GSList *new_list;
 325
 326   if (position < 0)
 327     return g_slist_append (list, data);
 328   else if (position == 0)
 329     return g_slist_prepend (list, data);
 330
 331   new_list = _g_slist_alloc ();
 332   new_list->data = data;
 333
 334   if (!list)
 335     {
 336       new_list->next = NULL;
 337       return new_list;
 338     }
 339
 340   prev_list = NULL;
 341   tmp_list = list;
 342
 343   while ((position-- > 0) && tmp_list)
 344     {
 345       prev_list = tmp_list;
 346       tmp_list = tmp_list->next;
 347     }
 348
 349   if (prev_list)
 350     {
 351       new_list->next = prev_list->next;
 352       prev_list->next = new_list;
 353     }
 354   else
 355     {
 356       new_list->next = list;
 357       list = new_list;
 358     }
 359
 360   return list;
 361 }
 362
 363 /**
 364  * g_slist_insert_before:
 365  * @slist: a #GSList
 366  * @sibling: node to insert @data before
 367  * @data: data to put in the newly-inserted node
 368  *
 369  * Inserts a node before @sibling containing @data.
 370  *
 371  * Returns: the new head of the list.
 372  */
 373 GSList*
 374 g_slist_insert_before (GSList  *slist,
 375                        GSList  *sibling,
 376                        gpointer data)
 377 {
 378   if (!slist)
 379     {
 380       slist = _g_slist_alloc ();
 381       slist->data = data;
 382       slist->next = NULL;
 383       g_return_val_if_fail (sibling == NULL, slist);
 384       return slist;
 385     }
 386   else
 387     {
 388       GSList *node, *last = NULL;
 389
 390       for (node = slist; node; last = node, node = last->next)
 391         if (node == sibling)
 392           break;
 393       if (!last)
 394         {
 395           node = _g_slist_alloc ();
 396           node->data = data;
 397           node->next = slist;
 398
 399           return node;
 400         }
 401       else
 402         {
 403           node = _g_slist_alloc ();
 404           node->data = data;
 405           node->next = last->next;
 406           last->next = node;
 407
 408           return slist;
 409         }
 410     }
 411 }
 412
 413 /**
 414  * g_slist_concat:
 415  * @list1: a #GSList
 416  * @list2: the #GSList to add to the end of the first #GSList
 417  *
 418  * Adds the second #GSList onto the end of the first #GSList.
 419  * Note that the elements of the second #GSList are not copied.
 420  * They are used directly.
 421  *
 422  * Returns: the start of the new #GSList
 423  */
 424 GSList *
 425 g_slist_concat (GSList *list1, GSList *list2)
 426 {
 427   if (list2)
 428     {
 429       if (list1)
 430         g_slist_last (list1)->next = list2;
 431       else
 432         list1 = list2;
 433     }
 434
 435   return list1;
 436 }
 437
 438 /**
 439  * g_slist_remove:
 440  * @list: a #GSList
 441  * @data: the data of the element to remove
 442  *
 443  * Removes an element from a #GSList.
 444  * If two elements contain the same data, only the first is removed.
 445  * If none of the elements contain the data, the #GSList is unchanged.
 446  *
 447  * Returns: the new start of the #GSList
 448  */
 449 GSList*
 450 g_slist_remove (GSList        *list,
 451                 gconstpointer  data)
 452 {
 453   GSList *tmp, *prev = NULL;
 454
 455   tmp = list;
 456   while (tmp)
 457     {
 458       if (tmp->data == data)
 459         {
 460           if (prev)
 461             prev->next = tmp->next;
 462           else
 463             list = tmp->next;
 464
 465           g_slist_free_1 (tmp);
 466           break;
 467         }
 468       prev = tmp;
 469       tmp = prev->next;
 470     }
 471
 472   return list;
 473 }
 474
 475 /**
 476  * g_slist_remove_all:
 477  * @list: a #GSList
 478  * @data: data to remove
 479  *
 480  * Removes all list nodes with data equal to @data.
 481  * Returns the new head of the list. Contrast with
 482  * g_slist_remove() which removes only the first node
 483  * matching the given data.
 484  *
 485  * Returns: new head of @list
 486  */
 487 GSList*
 488 g_slist_remove_all (GSList        *list,
 489                     gconstpointer  data)
 490 {
 491   GSList *tmp, *prev = NULL;
 492
 493   tmp = list;
 494   while (tmp)
 495     {
 496       if (tmp->data == data)
 497         {
 498           GSList *next = tmp->next;
 499
 500           if (prev)
 501             prev->next = next;
 502           else
 503             list = next;
 504
 505           g_slist_free_1 (tmp);
 506           tmp = next;
 507         }
 508       else
 509         {
 510           prev = tmp;
 511           tmp = prev->next;
 512         }
 513     }
 514
 515   return list;
 516 }
 517
 518 static inline GSList*
 519 _g_slist_remove_link (GSList *list,
 520                       GSList *link)
 521 {
 522   GSList *tmp;
 523   GSList *prev;
 524
 525   prev = NULL;
 526   tmp = list;
 527
 528   while (tmp)
 529     {
 530       if (tmp == link)
 531         {
 532           if (prev)
 533             prev->next = tmp->next;
 534           if (list == tmp)
 535             list = list->next;
 536
 537           tmp->next = NULL;
 538           break;
 539         }
 540
 541       prev = tmp;
 542       tmp = tmp->next;
 543     }
 544
 545   return list;
 546 }
 547
 548 /**
 549  * g_slist_remove_link:
 550  * @list: a #GSList
 551  * @link_: an element in the #GSList
 552  *
 553  * Removes an element from a #GSList, without
 554  * freeing the element. The removed element's next
 555  * link is set to %NULL, so that it becomes a
 556  * self-contained list with one element.
 557  *
 558  * Returns: the new start of the #GSList, without the element
 559  */
 560 GSList*
 561 g_slist_remove_link (GSList *list,
 562                      GSList *link_)
 563 {
 564   return _g_slist_remove_link (list, link_);
 565 }
 566
 567 /**
 568  * g_slist_delete_link:
 569  * @list: a #GSList
 570  * @link_: node to delete
 571  *
 572  * Removes the node link_ from the list and frees it.
 573  * Compare this to g_slist_remove_link() which removes the node
 574  * without freeing it.
 575  *
 576  * Returns: the new head of @list
 577  */
 578 GSList*
 579 g_slist_delete_link (GSList *list,
 580                      GSList *link_)
 581 {
 582   list = _g_slist_remove_link (list, link_);
 583   _g_slist_free1 (link_);
 584
 585   return list;
 586 }
 587
 588 /**
 589  * g_slist_copy:
 590  * @list: a #GSList
 591  *
 592  * Copies a #GSList.
 593  *
 594  * <note><para>
 595  * Note that this is a "shallow" copy. If the list elements
 596  * consist of pointers to data, the pointers are copied but
 597  * the actual data isn't.
 598  * </para></note>
 599  *
 600  * Returns: a copy of @list
 601  */
 602 GSList*
 603 g_slist_copy (GSList *list)
 604 {
 605   GSList *new_list = NULL;
 606
 607   if (list)
 608     {
 609       GSList *last;
 610
 611       new_list = _g_slist_alloc ();
 612       new_list->data = list->data;
 613       last = new_list;
 614       list = list->next;
 615       while (list)
 616         {
 617           last->next = _g_slist_alloc ();
 618           last = last->next;
 619           last->data = list->data;
 620           list = list->next;
 621         }
 622       last->next = NULL;
 623     }
 624
 625   return new_list;
 626 }
 627
 628 /**
 629  * g_slist_reverse:
 630  * @list: a #GSList
 631  *
 632  * Reverses a #GSList.
 633  *
 634  * Returns: the start of the reversed #GSList
 635  */
 636 GSList*
 637 g_slist_reverse (GSList *list)
 638 {
 639   GSList *prev = NULL;
 640
 641   while (list)
 642     {
 643       GSList *next = list->next;
 644
 645       list->next = prev;
 646
 647       prev = list;
 648       list = next;
 649     }
 650
 651   return prev;
 652 }
 653
 654 /**
 655  * g_slist_nth:
 656  * @list: a #GSList
 657  * @n: the position of the element, counting from 0
 658  *
 659  * Gets the element at the given position in a #GSList.
 660  *
 661  * Returns: the element, or %NULL if the position is off
 662  *     the end of the #GSList
 663  */
 664 GSList*
 665 g_slist_nth (GSList *list,
 666              guint   n)
 667 {
 668   while (n-- > 0 && list)
 669     list = list->next;
 670
 671   return list;
 672 }
 673
 674 /**
 675  * g_slist_nth_data:
 676  * @list: a #GSList
 677  * @n: the position of the element
 678  *
 679  * Gets the data of the element at the given position.
 680  *
 681  * Returns: the element's data, or %NULL if the position
 682  *     is off the end of the #GSList
 683  */
 684 gpointer
 685 g_slist_nth_data (GSList   *list,
 686                   guint     n)
 687 {
 688   while (n-- > 0 && list)
 689     list = list->next;
 690
 691   return list ? list->data : NULL;
 692 }
 693
 694 /**
 695  * g_slist_find:
 696  * @list: a #GSList
 697  * @data: the element data to find
 698  *
 699  * Finds the element in a #GSList which
 700  * contains the given data.
 701  *
 702  * Returns: the found #GSList element,
 703  *     or %NULL if it is not found
 704  */
 705 GSList*
 706 g_slist_find (GSList        *list,
 707               gconstpointer  data)
 708 {
 709   while (list)
 710     {
 711       if (list->data == data)
 712         break;
 713       list = list->next;
 714     }
 715
 716   return list;
 717 }
 718
 719
 720 /**
 721  * g_slist_find_custom:
 722  * @list: a #GSList
 723  * @data: user data passed to the function
 724  * @func: the function to call for each element.
 725  *     It should return 0 when the desired element is found
 726  *
 727  * Finds an element in a #GSList, using a supplied function to
 728  * find the desired element. It iterates over the list, calling
 729  * the given function which should return 0 when the desired
 730  * element is found. The function takes two #gconstpointer arguments,
 731  * the #GSList element's data as the first argument and the
 732  * given user data.
 733  *
 734  * Returns: the found #GSList element, or %NULL if it is not found
 735  */
 736 GSList*
 737 g_slist_find_custom (GSList        *list,
 738                      gconstpointer  data,
 739                      GCompareFunc   func)
 740 {
 741   g_return_val_if_fail (func != NULL, list);
 742
 743   while (list)
 744     {
 745       if (! func (list->data, data))
 746         return list;
 747       list = list->next;
 748     }
 749
 750   return NULL;
 751 }
 752
 753 /**
 754  * g_slist_position:
 755  * @list: a #GSList
 756  * @llink: an element in the #GSList
 757  *
 758  * Gets the position of the given element
 759  * in the #GSList (starting from 0).
 760  *
 761  * Returns: the position of the element in the #GSList,
 762  *     or -1 if the element is not found
 763  */
 764 gint
 765 g_slist_position (GSList *list,
 766                   GSList *llink)
 767 {
 768   gint i;
 769
 770   i = 0;
 771   while (list)
 772     {
 773       if (list == llink)
 774         return i;
 775       i++;
 776       list = list->next;
 777     }
 778
 779   return -1;
 780 }
 781
 782 /**
 783  * g_slist_index:
 784  * @list: a #GSList
 785  * @data: the data to find
 786  *
 787  * Gets the position of the element containing
 788  * the given data (starting from 0).
 789  *
 790  * Returns: the index of the element containing the data,
 791  *     or -1 if the data is not found
 792  */
 793 gint
 794 g_slist_index (GSList        *list,
 795                gconstpointer  data)
 796 {
 797   gint i;
 798
 799   i = 0;
 800   while (list)
 801     {
 802       if (list->data == data)
 803         return i;
 804       i++;
 805       list = list->next;
 806     }
 807
 808   return -1;
 809 }
 810
 811 /**
 812  * g_slist_last:
 813  * @list: a #GSList
 814  *
 815  * Gets the last element in a #GSList.
 816  *
 817  * <note><para>
 818  * This function iterates over the whole list.
 819  * </para></note>
 820  *
 821  * Returns: the last element in the #GSList,
 822  *     or %NULL if the #GSList has no elements
 823  */
 824 GSList*
 825 g_slist_last (GSList *list)
 826 {
 827   if (list)
 828     {
 829       while (list->next)
 830         list = list->next;
 831     }
 832
 833   return list;
 834 }
 835
 836 /**
 837  * g_slist_length:
 838  * @list: a #GSList
 839  *
 840  * Gets the number of elements in a #GSList.
 841  *
 842  * <note><para>
 843  * This function iterates over the whole list to
 844  * count its elements.
 845  * </para></note>
 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 }