glib/glist.c

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