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