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