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