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->prev)
 429     {
 430       if (link->prev->next == link)
 431         link->prev->next = link->next;
 432       else
 433         g_warning ("corrupted double-linked list detected");
 434     }
 435   if (link->next)
 436     {
 437       if (link->next->prev == link)
 438         link->next->prev = link->prev;
 439       else
 440         g_warning ("corrupted double-linked list detected");
 441     }
 442
 443   if (link == list)
 444     list = list->next;
 445
 446   link->next = NULL;
 447   link->prev = NULL;
 448
 449   return list;
 450 }
 451
 452 /**
 453  * g_list_remove:
 454  * @list: a #GList
 455  * @data: the data of the element to remove
 456  *
 457  * Removes an element from a #GList.
 458  * If two elements contain the same data, only the first is removed.
 459  * If none of the elements contain the data, the #GList is unchanged.
 460  *
 461  * Returns: the new start of the #GList
 462  */
 463 GList*
 464 g_list_remove (GList         *list,
 465                gconstpointer  data)
 466 {
 467   GList *tmp;
 468
 469   tmp = list;
 470   while (tmp)
 471     {
 472       if (tmp->data != data)
 473         tmp = tmp->next;
 474       else
 475         {
 476           list = _g_list_remove_link (list, tmp);
 477           _g_list_free1 (tmp);
 478
 479           break;
 480         }
 481     }
 482   return list;
 483 }
 484
 485 /**
 486  * g_list_remove_all:
 487  * @list: a #GList
 488  * @data: data to remove
 489  *
 490  * Removes all list nodes with data equal to @data.
 491  * Returns the new head of the list. Contrast with
 492  * g_list_remove() which removes only the first node
 493  * matching the given data.
 494  *
 495  * Returns: new head of @list
 496  */
 497 GList*
 498 g_list_remove_all (GList        *list,
 499                    gconstpointer data)
 500 {
 501   GList *tmp = list;
 502
 503   while (tmp)
 504     {
 505       if (tmp->data != data)
 506         tmp = tmp->next;
 507       else
 508         {
 509           GList *next = tmp->next;
 510
 511           if (tmp->prev)
 512             tmp->prev->next = next;
 513           else
 514             list = next;
 515           if (next)
 516             next->prev = tmp->prev;
 517
 518           _g_list_free1 (tmp);
 519           tmp = next;
 520         }
 521     }
 522   return list;
 523 }
 524
 525 /**
 526  * g_list_remove_link:
 527  * @list: a #GList
 528  * @llink: an element in the #GList
 529  *
 530  * Removes an element from a #GList, without freeing the element.
 531  * The removed element's prev and next links are set to %NULL, so
 532  * that it becomes a self-contained list with one element.
 533  *
 534  * Returns: the new start of the #GList, without the element
 535  */
 536 GList*
 537 g_list_remove_link (GList *list,
 538                     GList *llink)
 539 {
 540   return _g_list_remove_link (list, llink);
 541 }
 542
 543 /**
 544  * g_list_delete_link:
 545  * @list: a #GList
 546  * @link_: node to delete from @list
 547  *
 548  * Removes the node link_ from the list and frees it.
 549  * Compare this to g_list_remove_link() which removes the node
 550  * without freeing it.
 551  *
 552  * Returns: the new head of @list
 553  */
 554 GList*
 555 g_list_delete_link (GList *list,
 556                     GList *link_)
 557 {
 558   list = _g_list_remove_link (list, link_);
 559   _g_list_free1 (link_);
 560
 561   return list;
 562 }
 563
 564 /**
 565  * g_list_copy:
 566  * @list: a #GList
 567  *
 568  * Copies a #GList.
 569  *
 570  * <note><para>
 571  * Note that this is a "shallow" copy. If the list elements
 572  * consist of pointers to data, the pointers are copied but
 573  * the actual data is not. See g_list_copy_deep() if you need
 574  * to copy the data as well.
 575  * </para></note>
 576  *
 577  * Returns: a copy of @list
 578  */
 579 GList*
 580 g_list_copy (GList *list)
 581 {
 582   return g_list_copy_deep (list, NULL, NULL);
 583 }
 584
 585 /**
 586  * g_list_copy_deep:
 587  * @list: a #GList
 588  * @func: a copy function used to copy every element in the list
 589  * @user_data: user data passed to the copy function @func, or #NULL
 590  *
 591  * Makes a full (deep) copy of a #GList.
 592  *
 593  * In contrast with g_list_copy(), this function uses @func to make a copy of
 594  * each list element, in addition to copying the list container itself.
 595  *
 596  * @func, as a #GCopyFunc, takes two arguments, the data to be copied and a user
 597  * pointer. It's safe to pass #NULL as user_data, if the copy function takes only
 598  * one argument.
 599  *
 600  * For instance, if @list holds a list of GObjects, you can do:
 601  * |[
 602  * another_list = g_list_copy_deep (list, (GCopyFunc) g_object_ref, NULL);
 603  * ]|
 604  *
 605  * And, to entirely free the new list, you could do:
 606  * |[
 607  * g_list_free_full (another_list, g_object_unref);
 608  * ]|
 609  *
 610  * Returns: a full copy of @list, use #g_list_free_full to free it
 611  *
 612  * Since: 2.34
 613  */
 614 GList*
 615 g_list_copy_deep (GList *list, GCopyFunc func, gpointer user_data)
 616 {
 617   GList *new_list = NULL;
 618
 619   if (list)
 620     {
 621       GList *last;
 622
 623       new_list = _g_list_alloc ();
 624       if (func)
 625         new_list->data = func (list->data, user_data);
 626       else
 627         new_list->data = list->data;
 628       new_list->prev = NULL;
 629       last = new_list;
 630       list = list->next;
 631       while (list)
 632         {
 633           last->next = _g_list_alloc ();
 634           last->next->prev = last;
 635           last = last->next;
 636           if (func)
 637             last->data = func (list->data, user_data);
 638           else
 639             last->data = list->data;
 640           list = list->next;
 641         }
 642       last->next = NULL;
 643     }
 644
 645   return new_list;
 646 }
 647
 648 /**
 649  * g_list_reverse:
 650  * @list: a #GList
 651  *
 652  * Reverses a #GList.
 653  * It simply switches the next and prev pointers of each element.
 654  *
 655  * Returns: the start of the reversed #GList
 656  */
 657 GList*
 658 g_list_reverse (GList *list)
 659 {
 660   GList *last;
 661
 662   last = NULL;
 663   while (list)
 664     {
 665       last = list;
 666       list = last->next;
 667       last->next = last->prev;
 668       last->prev = list;
 669     }
 670
 671   return last;
 672 }
 673
 674 /**
 675  * g_list_nth:
 676  * @list: a #GList
 677  * @n: the position of the element, counting from 0
 678  *
 679  * Gets the element at the given position in a #GList.
 680  *
 681  * Returns: the element, or %NULL if the position is off
 682  *     the end of the #GList
 683  */
 684 GList*
 685 g_list_nth (GList *list,
 686             guint  n)
 687 {
 688   while ((n-- > 0) && list)
 689     list = list->next;
 690
 691   return list;
 692 }
 693
 694 /**
 695  * g_list_nth_prev:
 696  * @list: a #GList
 697  * @n: the position of the element, counting from 0
 698  *
 699  * Gets the element @n places before @list.
 700  *
 701  * Returns: the element, or %NULL if the position is
 702  *     off the end of the #GList
 703  */
 704 GList*
 705 g_list_nth_prev (GList *list,
 706                  guint  n)
 707 {
 708   while ((n-- > 0) && list)
 709     list = list->prev;
 710
 711   return list;
 712 }
 713
 714 /**
 715  * g_list_nth_data:
 716  * @list: a #GList
 717  * @n: the position of the element
 718  *
 719  * Gets the data of the element at the given position.
 720  *
 721  * Returns: the element's data, or %NULL if the position
 722  *     is off the end of the #GList
 723  */
 724 gpointer
 725 g_list_nth_data (GList     *list,
 726                  guint      n)
 727 {
 728   while ((n-- > 0) && list)
 729     list = list->next;
 730
 731   return list ? list->data : NULL;
 732 }
 733
 734 /**
 735  * g_list_find:
 736  * @list: a #GList
 737  * @data: the element data to find
 738  *
 739  * Finds the element in a #GList which
 740  * contains the given data.
 741  *
 742  * Returns: the found #GList element,
 743  *     or %NULL if it is not found
 744  */
 745 GList*
 746 g_list_find (GList         *list,
 747              gconstpointer  data)
 748 {
 749   while (list)
 750     {
 751       if (list->data == data)
 752         break;
 753       list = list->next;
 754     }
 755
 756   return list;
 757 }
 758
 759 /**
 760  * g_list_find_custom:
 761  * @list: a #GList
 762  * @data: user data passed to the function
 763  * @func: the function to call for each element.
 764  *     It should return 0 when the desired element is found
 765  *
 766  * Finds an element in a #GList, using a supplied function to
 767  * find the desired element. It iterates over the list, calling
 768  * the given function which should return 0 when the desired
 769  * element is found. The function takes two #gconstpointer arguments,
 770  * the #GList element's data as the first argument and the
 771  * given user data.
 772  *
 773  * Returns: the found #GList element, or %NULL if it is not found
 774  */
 775 GList*
 776 g_list_find_custom (GList         *list,
 777                     gconstpointer  data,
 778                     GCompareFunc   func)
 779 {
 780   g_return_val_if_fail (func != NULL, list);
 781
 782   while (list)
 783     {
 784       if (! func (list->data, data))
 785         return list;
 786       list = list->next;
 787     }
 788
 789   return NULL;
 790 }
 791
 792
 793 /**
 794  * g_list_position:
 795  * @list: a #GList
 796  * @llink: an element in the #GList
 797  *
 798  * Gets the position of the given element
 799  * in the #GList (starting from 0).
 800  *
 801  * Returns: the position of the element in the #GList,
 802  *     or -1 if the element is not found
 803  */
 804 gint
 805 g_list_position (GList *list,
 806                  GList *llink)
 807 {
 808   gint i;
 809
 810   i = 0;
 811   while (list)
 812     {
 813       if (list == llink)
 814         return i;
 815       i++;
 816       list = list->next;
 817     }
 818
 819   return -1;
 820 }
 821
 822 /**
 823  * g_list_index:
 824  * @list: a #GList
 825  * @data: the data to find
 826  *
 827  * Gets the position of the element containing
 828  * the given data (starting from 0).
 829  *
 830  * Returns: the index of the element containing the data,
 831  *     or -1 if the data is not found
 832  */
 833 gint
 834 g_list_index (GList         *list,
 835               gconstpointer  data)
 836 {
 837   gint i;
 838
 839   i = 0;
 840   while (list)
 841     {
 842       if (list->data == data)
 843         return i;
 844       i++;
 845       list = list->next;
 846     }
 847
 848   return -1;
 849 }
 850
 851 /**
 852  * g_list_last:
 853  * @list: a #GList
 854  *
 855  * Gets the last element in a #GList.
 856  *
 857  * Returns: the last element in the #GList,
 858  *     or %NULL if the #GList has no elements
 859  */
 860 GList*
 861 g_list_last (GList *list)
 862 {
 863   if (list)
 864     {
 865       while (list->next)
 866         list = list->next;
 867     }
 868
 869   return list;
 870 }
 871
 872 /**
 873  * g_list_first:
 874  * @list: a #GList
 875  *
 876  * Gets the first element in a #GList.
 877  *
 878  * Returns: the first element in the #GList,
 879  *     or %NULL if the #GList has no elements
 880  */
 881 GList*
 882 g_list_first (GList *list)
 883 {
 884   if (list)
 885     {
 886       while (list->prev)
 887         list = list->prev;
 888     }
 889
 890   return list;
 891 }
 892
 893 /**
 894  * g_list_length:
 895  * @list: a #GList
 896  *
 897  * Gets the number of elements in a #GList.
 898  *
 899  * <note><para>
 900  * This function iterates over the whole list to
 901  * count its elements.
 902  * </para></note>
 903  *
 904  * Returns: the number of elements in the #GList
 905  */
 906 guint
 907 g_list_length (GList *list)
 908 {
 909   guint length;
 910
 911   length = 0;
 912   while (list)
 913     {
 914       length++;
 915       list = list->next;
 916     }
 917
 918   return length;
 919 }
 920
 921 /**
 922  * g_list_foreach:
 923  * @list: a #GList
 924  * @func: the function to call with each element's data
 925  * @user_data: user data to pass to the function
 926  *
 927  * Calls a function for each element of a #GList.
 928  */
 929 /**
 930  * GFunc:
 931  * @data: the element's data.
 932  * @user_data: user data passed to g_list_foreach() or
 933  *             g_slist_foreach().
 934  *
 935  * Specifies the type of functions passed to g_list_foreach() and
 936  * g_slist_foreach().
 937  **/
 938 void
 939 g_list_foreach (GList    *list,
 940                 GFunc     func,
 941                 gpointer  user_data)
 942 {
 943   while (list)
 944     {
 945       GList *next = list->next;
 946       (*func) (list->data, user_data);
 947       list = next;
 948     }
 949 }
 950
 951 static GList*
 952 g_list_insert_sorted_real (GList    *list,
 953                            gpointer  data,
 954                            GFunc     func,
 955                            gpointer  user_data)
 956 {
 957   GList *tmp_list = list;
 958   GList *new_list;
 959   gint cmp;
 960
 961   g_return_val_if_fail (func != NULL, list);
 962
 963   if (!list)
 964     {
 965       new_list = _g_list_alloc0 ();
 966       new_list->data = data;
 967       return new_list;
 968     }
 969
 970   cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);
 971
 972   while ((tmp_list->next) && (cmp > 0))
 973     {
 974       tmp_list = tmp_list->next;
 975
 976       cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);
 977     }
 978
 979   new_list = _g_list_alloc0 ();
 980   new_list->data = data;
 981
 982   if ((!tmp_list->next) && (cmp > 0))
 983     {
 984       tmp_list->next = new_list;
 985       new_list->prev = tmp_list;
 986       return list;
 987     }
 988
 989   if (tmp_list->prev)
 990     {
 991       tmp_list->prev->next = new_list;
 992       new_list->prev = tmp_list->prev;
 993     }
 994   new_list->next = tmp_list;
 995   tmp_list->prev = new_list;
 996
 997   if (tmp_list == list)
 998     return new_list;
 999   else
1000     return list;
1001 }
1002
1003 /**
1004  * g_list_insert_sorted:
1005  * @list: a pointer to a #GList
1006  * @data: the data for the new element
1007  * @func: the function to compare elements in the list. It should
1008  *     return a number > 0 if the first parameter comes after the
1009  *     second parameter in the sort order.
1010  *
1011  * Inserts a new element into the list, using the given comparison
1012  * function to determine its position.
1013  *
1014  * Returns: the new start of the #GList
1015  */
1016 GList*
1017 g_list_insert_sorted (GList        *list,
1018                       gpointer      data,
1019                       GCompareFunc  func)
1020 {
1021   return g_list_insert_sorted_real (list, data, (GFunc) func, NULL);
1022 }
1023
1024 /**
1025  * g_list_insert_sorted_with_data:
1026  * @list: a pointer to a #GList
1027  * @data: the data for the new element
1028  * @func: the function to compare elements in the list.
1029  *     It should return a number > 0 if the first parameter
1030  *     comes after the second parameter in the sort order.
1031  * @user_data: user data to pass to comparison function.
1032  *
1033  * Inserts a new element into the list, using the given comparison
1034  * function to determine its position.
1035  *
1036  * Returns: the new start of the #GList
1037  *
1038  * Since: 2.10
1039  */
1040 GList*
1041 g_list_insert_sorted_with_data (GList            *list,
1042                                 gpointer          data,
1043                                 GCompareDataFunc  func,
1044                                 gpointer          user_data)
1045 {
1046   return g_list_insert_sorted_real (list, data, (GFunc) func, user_data);
1047 }
1048
1049 static GList *
1050 g_list_sort_merge (GList     *l1,
1051                    GList     *l2,
1052                    GFunc     compare_func,
1053                    gpointer  user_data)
1054 {
1055   GList list, *l, *lprev;
1056   gint cmp;
1057
1058   l = &list;
1059   lprev = NULL;
1060
1061   while (l1 && l2)
1062     {
1063       cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data);
1064
1065       if (cmp <= 0)
1066         {
1067           l->next = l1;
1068           l1 = l1->next;
1069         }
1070       else
1071         {
1072           l->next = l2;
1073           l2 = l2->next;
1074         }
1075       l = l->next;
1076       l->prev = lprev;
1077       lprev = l;
1078     }
1079   l->next = l1 ? l1 : l2;
1080   l->next->prev = l;
1081
1082   return list.next;
1083 }
1084
1085 static GList*
1086 g_list_sort_real (GList    *list,
1087                   GFunc     compare_func,
1088                   gpointer  user_data)
1089 {
1090   GList *l1, *l2;
1091
1092   if (!list)
1093     return NULL;
1094   if (!list->next)
1095     return list;
1096
1097   l1 = list;
1098   l2 = list->next;
1099
1100   while ((l2 = l2->next) != NULL)
1101     {
1102       if ((l2 = l2->next) == NULL)
1103         break;
1104       l1 = l1->next;
1105     }
1106   l2 = l1->next;
1107   l1->next = NULL;
1108
1109   return g_list_sort_merge (g_list_sort_real (list, compare_func, user_data),
1110                             g_list_sort_real (l2, compare_func, user_data),
1111                             compare_func,
1112                             user_data);
1113 }
1114
1115 /**
1116  * g_list_sort:
1117  * @list: a #GList
1118  * @compare_func: the comparison function used to sort the #GList.
1119  *     This function is passed the data from 2 elements of the #GList
1120  *     and should return 0 if they are equal, a negative value if the
1121  *     first element comes before the second, or a positive value if
1122  *     the first element comes after the second.
1123  *
1124  * Sorts a #GList using the given comparison function. The algorithm
1125  * used is a stable sort.
1126  *
1127  * Returns: the start of the sorted #GList
1128  */
1129 /**
1130  * GCompareFunc:
1131  * @a: a value.
1132  * @b: a value to compare with.
1133  *
1134  * Specifies the type of a comparison function used to compare two
1135  * values.  The function should return a negative integer if the first
1136  * value comes before the second, 0 if they are equal, or a positive
1137  * integer if the first value comes after the second.
1138  *
1139  * Returns: negative value if @a &lt; @b; zero if @a = @b; positive
1140  *          value if @a > @b.
1141  **/
1142 GList *
1143 g_list_sort (GList        *list,
1144              GCompareFunc  compare_func)
1145 {
1146   return g_list_sort_real (list, (GFunc) compare_func, NULL);
1147
1148 }
1149
1150 /**
1151  * g_list_sort_with_data:
1152  * @list: a #GList
1153  * @compare_func: comparison function
1154  * @user_data: user data to pass to comparison function
1155  *
1156  * Like g_list_sort(), but the comparison function accepts
1157  * a user data argument.
1158  *
1159  * Returns: the new head of @list
1160  */
1161 /**
1162  * GCompareDataFunc:
1163  * @a: a value.
1164  * @b: a value to compare with.
1165  * @user_data: user data to pass to comparison function.
1166  *
1167  * Specifies the type of a comparison function used to compare two
1168  * values.  The function should return a negative integer if the first
1169  * value comes before the second, 0 if they are equal, or a positive
1170  * integer if the first value comes after the second.
1171  *
1172  * Returns: negative value if @a &lt; @b; zero if @a = @b; positive
1173  *          value if @a > @b.
1174  **/
1175 GList *
1176 g_list_sort_with_data (GList            *list,
1177                        GCompareDataFunc  compare_func,
1178                        gpointer          user_data)
1179 {
1180   return g_list_sort_real (list, (GFunc) compare_func, user_data);
1181 }