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