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