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