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