glib/glist.c

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