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