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