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