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