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