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