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