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