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