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