glib/glist.c

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