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