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