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   tmp_list->prev->next = new_list;
 327   new_list->next = tmp_list;
 328   tmp_list->prev = new_list;
 329
 330   return list;
 331 }
 332
 333 /**
 334  * g_list_insert_before:
 335  * @list: a pointer to a #GList
 336  * @sibling: the list element before which the new element
 337  *     is inserted or %NULL to insert at the end of the list
 338  * @data: the data for the new element
 339  *
 340  * Inserts a new element into the list before the given position.
 341  *
 342  * Returns: the new start of the #GList
 343  */
 344 GList*
 345 g_list_insert_before (GList   *list,
 346                       GList   *sibling,
 347                       gpointer data)
 348 {
 349   if (!list)
 350     {
 351       list = g_list_alloc ();
 352       list->data = data;
 353       g_return_val_if_fail (sibling == NULL, list);
 354       return list;
 355     }
 356   else if (sibling)
 357     {
 358       GList *node;
 359
 360       node = _g_list_alloc ();
 361       node->data = data;
 362       node->prev = sibling->prev;
 363       node->next = sibling;
 364       sibling->prev = node;
 365       if (node->prev)
 366         {
 367           node->prev->next = node;
 368           return list;
 369         }
 370       else
 371         {
 372           g_return_val_if_fail (sibling == list, node);
 373           return node;
 374         }
 375     }
 376   else
 377     {
 378       GList *last;
 379
 380       last = list;
 381       while (last->next)
 382         last = last->next;
 383
 384       last->next = _g_list_alloc ();
 385       last->next->data = data;
 386       last->next->prev = last;
 387       last->next->next = NULL;
 388
 389       return list;
 390     }
 391 }
 392
 393 /**
 394  * g_list_concat:
 395  * @list1: a #GList
 396  * @list2: the #GList to add to the end of the first #GList
 397  *
 398  * Adds the second #GList onto the end of the first #GList.
 399  * Note that the elements of the second #GList are not copied.
 400  * They are used directly.
 401  *
 402  * Returns: the start of the new #GList
 403  */
 404 GList *
 405 g_list_concat (GList *list1, GList *list2)
 406 {
 407   GList *tmp_list;
 408
 409   if (list2)
 410     {
 411       tmp_list = g_list_last (list1);
 412       if (tmp_list)
 413         tmp_list->next = list2;
 414       else
 415         list1 = list2;
 416       list2->prev = tmp_list;
 417     }
 418
 419   return list1;
 420 }
 421
 422 /**
 423  * g_list_remove:
 424  * @list: a #GList
 425  * @data: the data of the element to remove
 426  *
 427  * Removes an element from a #GList.
 428  * If two elements contain the same data, only the first is removed.
 429  * If none of the elements contain the data, the #GList is unchanged.
 430  *
 431  * Returns: the new start of the #GList
 432  */
 433 GList*
 434 g_list_remove (GList         *list,
 435                gconstpointer  data)
 436 {
 437   GList *tmp;
 438
 439   tmp = list;
 440   while (tmp)
 441     {
 442       if (tmp->data != data)
 443         tmp = tmp->next;
 444       else
 445         {
 446           if (tmp->prev)
 447             tmp->prev->next = tmp->next;
 448           if (tmp->next)
 449             tmp->next->prev = tmp->prev;
 450
 451           if (list == tmp)
 452             list = list->next;
 453
 454           _g_list_free1 (tmp);
 455
 456           break;
 457         }
 458     }
 459   return list;
 460 }
 461
 462 /**
 463  * g_list_remove_all:
 464  * @list: a #GList
 465  * @data: data to remove
 466  *
 467  * Removes all list nodes with data equal to @data.
 468  * Returns the new head of the list. Contrast with
 469  * g_list_remove() which removes only the first node
 470  * matching the given data.
 471  *
 472  * Returns: new head of @list
 473  */
 474 GList*
 475 g_list_remove_all (GList        *list,
 476                    gconstpointer data)
 477 {
 478   GList *tmp = list;
 479
 480   while (tmp)
 481     {
 482       if (tmp->data != data)
 483         tmp = tmp->next;
 484       else
 485         {
 486           GList *next = tmp->next;
 487
 488           if (tmp->prev)
 489             tmp->prev->next = next;
 490           else
 491             list = next;
 492           if (next)
 493             next->prev = tmp->prev;
 494
 495           _g_list_free1 (tmp);
 496           tmp = next;
 497         }
 498     }
 499   return list;
 500 }
 501
 502 static inline GList*
 503 _g_list_remove_link (GList *list,
 504                      GList *link)
 505 {
 506   if (link)
 507     {
 508       if (link->prev)
 509         link->prev->next = link->next;
 510       if (link->next)
 511         link->next->prev = link->prev;
 512
 513       if (link == list)
 514         list = list->next;
 515
 516       link->next = NULL;
 517       link->prev = NULL;
 518     }
 519
 520   return list;
 521 }
 522
 523 /**
 524  * g_list_remove_link:
 525  * @list: a #GList
 526  * @llink: an element in the #GList
 527  *
 528  * Removes an element from a #GList, without freeing the element.
 529  * The removed element's prev and next links are set to %NULL, so
 530  * that it becomes a self-contained list with one element.
 531  *
 532  * Returns: the new start of the #GList, without the element
 533  */
 534 GList*
 535 g_list_remove_link (GList *list,
 536                     GList *llink)
 537 {
 538   return _g_list_remove_link (list, llink);
 539 }
 540
 541 /**
 542  * g_list_delete_link:
 543  * @list: a #GList
 544  * @link_: node to delete from @list
 545  *
 546  * Removes the node link_ from the list and frees it.
 547  * Compare this to g_list_remove_link() which removes the node
 548  * without freeing it.
 549  *
 550  * Returns: the new head of @list
 551  */
 552 GList*
 553 g_list_delete_link (GList *list,
 554                     GList *link_)
 555 {
 556   list = _g_list_remove_link (list, link_);
 557   _g_list_free1 (link_);
 558
 559   return list;
 560 }
 561
 562 /**
 563  * g_list_copy:
 564  * @list: a #GList
 565  *
 566  * Copies a #GList.
 567  *
 568  * <note><para>
 569  * Note that this is a "shallow" copy. If the list elements
 570  * consist of pointers to data, the pointers are copied but
 571  * the actual data is not.
 572  * </para></note>
 573  *
 574  * Returns: a copy of @list
 575  */
 576 GList*
 577 g_list_copy (GList *list)
 578 {
 579   GList *new_list = NULL;
 580
 581   if (list)
 582     {
 583       GList *last;
 584
 585       new_list = _g_list_alloc ();
 586       new_list->data = list->data;
 587       new_list->prev = NULL;
 588       last = new_list;
 589       list = list->next;
 590       while (list)
 591         {
 592           last->next = _g_list_alloc ();
 593           last->next->prev = last;
 594           last = last->next;
 595           last->data = list->data;
 596           list = list->next;
 597         }
 598       last->next = NULL;
 599     }
 600
 601   return new_list;
 602 }
 603
 604 /**
 605  * g_list_reverse:
 606  * @list: a #GList
 607  *
 608  * Reverses a #GList.
 609  * It simply switches the next and prev pointers of each element.
 610  *
 611  * Returns: the start of the reversed #GList
 612  */
 613 GList*
 614 g_list_reverse (GList *list)
 615 {
 616   GList *last;
 617
 618   last = NULL;
 619   while (list)
 620     {
 621       last = list;
 622       list = last->next;
 623       last->next = last->prev;
 624       last->prev = list;
 625     }
 626
 627   return last;
 628 }
 629
 630 /**
 631  * g_list_nth:
 632  * @list: a #GList
 633  * @n: the position of the element, counting from 0
 634  *
 635  * Gets the element at the given position in a #GList.
 636  *
 637  * Returns: the element, or %NULL if the position is off
 638  *     the end of the #GList
 639  */
 640 GList*
 641 g_list_nth (GList *list,
 642             guint  n)
 643 {
 644   while ((n-- > 0) && list)
 645     list = list->next;
 646
 647   return list;
 648 }
 649
 650 /**
 651  * g_list_nth_prev:
 652  * @list: a #GList
 653  * @n: the position of the element, counting from 0
 654  *
 655  * Gets the element @n places before @list.
 656  *
 657  * Returns: the element, or %NULL if the position is
 658  *     off the end of the #GList
 659  */
 660 GList*
 661 g_list_nth_prev (GList *list,
 662                  guint  n)
 663 {
 664   while ((n-- > 0) && list)
 665     list = list->prev;
 666
 667   return list;
 668 }
 669
 670 /**
 671  * g_list_nth_data:
 672  * @list: a #GList
 673  * @n: the position of the element
 674  *
 675  * Gets the data of the element at the given position.
 676  *
 677  * Returns: the element's data, or %NULL if the position
 678  *     is off the end of the #GList
 679  */
 680 gpointer
 681 g_list_nth_data (GList     *list,
 682                  guint      n)
 683 {
 684   while ((n-- > 0) && list)
 685     list = list->next;
 686
 687   return list ? list->data : NULL;
 688 }
 689
 690 /**
 691  * g_list_find:
 692  * @list: a #GList
 693  * @data: the element data to find
 694  *
 695  * Finds the element in a #GList which
 696  * contains the given data.
 697  *
 698  * Returns: the found #GList element,
 699  *     or %NULL if it is not found
 700  */
 701 GList*
 702 g_list_find (GList         *list,
 703              gconstpointer  data)
 704 {
 705   while (list)
 706     {
 707       if (list->data == data)
 708         break;
 709       list = list->next;
 710     }
 711
 712   return list;
 713 }
 714
 715 /**
 716  * g_list_find_custom:
 717  * @list: a #GList
 718  * @data: user data passed to the function
 719  * @func: the function to call for each element.
 720  *     It should return 0 when the desired element is found
 721  *
 722  * Finds an element in a #GList, using a supplied function to
 723  * find the desired element. It iterates over the list, calling
 724  * the given function which should return 0 when the desired
 725  * element is found. The function takes two #gconstpointer arguments,
 726  * the #GList element's data as the first argument and the
 727  * given user data.
 728  *
 729  * Returns: the found #GList element, or %NULL if it is not found
 730  */
 731 GList*
 732 g_list_find_custom (GList         *list,
 733                     gconstpointer  data,
 734                     GCompareFunc   func)
 735 {
 736   g_return_val_if_fail (func != NULL, list);
 737
 738   while (list)
 739     {
 740       if (! func (list->data, data))
 741         return list;
 742       list = list->next;
 743     }
 744
 745   return NULL;
 746 }
 747
 748
 749 /**
 750  * g_list_position:
 751  * @list: a #GList
 752  * @llink: an element in the #GList
 753  *
 754  * Gets the position of the given element
 755  * in the #GList (starting from 0).
 756  *
 757  * Returns: the position of the element in the #GList,
 758  *     or -1 if the element is not found
 759  */
 760 gint
 761 g_list_position (GList *list,
 762                  GList *llink)
 763 {
 764   gint i;
 765
 766   i = 0;
 767   while (list)
 768     {
 769       if (list == llink)
 770         return i;
 771       i++;
 772       list = list->next;
 773     }
 774
 775   return -1;
 776 }
 777
 778 /**
 779  * g_list_index:
 780  * @list: a #GList
 781  * @data: the data to find
 782  *
 783  * Gets the position of the element containing
 784  * the given data (starting from 0).
 785  *
 786  * Returns: the index of the element containing the data,
 787  *     or -1 if the data is not found
 788  */
 789 gint
 790 g_list_index (GList         *list,
 791               gconstpointer  data)
 792 {
 793   gint i;
 794
 795   i = 0;
 796   while (list)
 797     {
 798       if (list->data == data)
 799         return i;
 800       i++;
 801       list = list->next;
 802     }
 803
 804   return -1;
 805 }
 806
 807 /**
 808  * g_list_last:
 809  * @list: a #GList
 810  *
 811  * Gets the last element in a #GList.
 812  *
 813  * Returns: the last element in the #GList,
 814  *     or %NULL if the #GList has no elements
 815  */
 816 GList*
 817 g_list_last (GList *list)
 818 {
 819   if (list)
 820     {
 821       while (list->next)
 822         list = list->next;
 823     }
 824
 825   return list;
 826 }
 827
 828 /**
 829  * g_list_first:
 830  * @list: a #GList
 831  *
 832  * Gets the first element in a #GList.
 833  *
 834  * Returns: the first element in the #GList,
 835  *     or %NULL if the #GList has no elements
 836  */
 837 GList*
 838 g_list_first (GList *list)
 839 {
 840   if (list)
 841     {
 842       while (list->prev)
 843         list = list->prev;
 844     }
 845
 846   return list;
 847 }
 848
 849 /**
 850  * g_list_length:
 851  * @list: a #GList
 852  *
 853  * Gets the number of elements in a #GList.
 854  *
 855  * <note><para>
 856  * This function iterates over the whole list to
 857  * count its elements.
 858  * </para></note>
 859  *
 860  * Returns: the number of elements in the #GList
 861  */
 862 guint
 863 g_list_length (GList *list)
 864 {
 865   guint length;
 866
 867   length = 0;
 868   while (list)
 869     {
 870       length++;
 871       list = list->next;
 872     }
 873
 874   return length;
 875 }
 876
 877 /**
 878  * g_list_foreach:
 879  * @list: a #GList
 880  * @func: the function to call with each element's data
 881  * @user_data: user data to pass to the function
 882  *
 883  * Calls a function for each element of a #GList.
 884  */
 885 /**
 886  * GFunc:
 887  * @data: the element's data.
 888  * @user_data: user data passed to g_list_foreach() or
 889  *             g_slist_foreach().
 890  *
 891  * Specifies the type of functions passed to g_list_foreach() and
 892  * g_slist_foreach().
 893  **/
 894 void
 895 g_list_foreach (GList    *list,
 896                 GFunc     func,
 897                 gpointer  user_data)
 898 {
 899   while (list)
 900     {
 901       GList *next = list->next;
 902       (*func) (list->data, user_data);
 903       list = next;
 904     }
 905 }
 906
 907 static GList*
 908 g_list_insert_sorted_real (GList    *list,
 909                            gpointer  data,
 910                            GFunc     func,
 911                            gpointer  user_data)
 912 {
 913   GList *tmp_list = list;
 914   GList *new_list;
 915   gint cmp;
 916
 917   g_return_val_if_fail (func != NULL, list);
 918
 919   if (!list)
 920     {
 921       new_list = _g_list_alloc0 ();
 922       new_list->data = data;
 923       return new_list;
 924     }
 925
 926   cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);
 927
 928   while ((tmp_list->next) && (cmp > 0))
 929     {
 930       tmp_list = tmp_list->next;
 931
 932       cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);
 933     }
 934
 935   new_list = _g_list_alloc0 ();
 936   new_list->data = data;
 937
 938   if ((!tmp_list->next) && (cmp > 0))
 939     {
 940       tmp_list->next = new_list;
 941       new_list->prev = tmp_list;
 942       return list;
 943     }
 944
 945   if (tmp_list->prev)
 946     {
 947       tmp_list->prev->next = new_list;
 948       new_list->prev = tmp_list->prev;
 949     }
 950   new_list->next = tmp_list;
 951   tmp_list->prev = new_list;
 952
 953   if (tmp_list == list)
 954     return new_list;
 955   else
 956     return list;
 957 }
 958
 959 /**
 960  * g_list_insert_sorted:
 961  * @list: a pointer to a #GList
 962  * @data: the data for the new element
 963  * @func: the function to compare elements in the list. It should
 964  *     return a number > 0 if the first parameter comes after the
 965  *     second parameter in the sort order.
 966  *
 967  * Inserts a new element into the list, using the given comparison
 968  * function to determine its position.
 969  *
 970  * Returns: the new start of the #GList
 971  */
 972 GList*
 973 g_list_insert_sorted (GList        *list,
 974                       gpointer      data,
 975                       GCompareFunc  func)
 976 {
 977   return g_list_insert_sorted_real (list, data, (GFunc) func, NULL);
 978 }
 979
 980 /**
 981  * g_list_insert_sorted_with_data:
 982  * @list: a pointer to a #GList
 983  * @data: the data for the new element
 984  * @func: the function to compare elements in the list.
 985  *     It should return a number > 0 if the first parameter
 986  *     comes after the second parameter in the sort order.
 987  * @user_data: user data to pass to comparison function.
 988  *
 989  * Inserts a new element into the list, using the given comparison
 990  * function to determine its position.
 991  *
 992  * Returns: the new start of the #GList
 993  *
 994  * Since: 2.10
 995  */
 996 GList*
 997 g_list_insert_sorted_with_data (GList            *list,
 998                                 gpointer          data,
 999                                 GCompareDataFunc  func,
1000                                 gpointer          user_data)
1001 {
1002   return g_list_insert_sorted_real (list, data, (GFunc) func, user_data);
1003 }
1004
1005 static GList *
1006 g_list_sort_merge (GList     *l1,
1007                    GList     *l2,
1008                    GFunc     compare_func,
1009                    gpointer  user_data)
1010 {
1011   GList list, *l, *lprev;
1012   gint cmp;
1013
1014   l = &list;
1015   lprev = NULL;
1016
1017   while (l1 && l2)
1018     {
1019       cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data);
1020
1021       if (cmp <= 0)
1022         {
1023           l->next = l1;
1024           l1 = l1->next;
1025         }
1026       else
1027         {
1028           l->next = l2;
1029           l2 = l2->next;
1030         }
1031       l = l->next;
1032       l->prev = lprev;
1033       lprev = l;
1034     }
1035   l->next = l1 ? l1 : l2;
1036   l->next->prev = l;
1037
1038   return list.next;
1039 }
1040
1041 static GList*
1042 g_list_sort_real (GList    *list,
1043                   GFunc     compare_func,
1044                   gpointer  user_data)
1045 {
1046   GList *l1, *l2;
1047
1048   if (!list)
1049     return NULL;
1050   if (!list->next)
1051     return list;
1052
1053   l1 = list;
1054   l2 = list->next;
1055
1056   while ((l2 = l2->next) != NULL)
1057     {
1058       if ((l2 = l2->next) == NULL)
1059         break;
1060       l1 = l1->next;
1061     }
1062   l2 = l1->next;
1063   l1->next = NULL;
1064
1065   return g_list_sort_merge (g_list_sort_real (list, compare_func, user_data),
1066                             g_list_sort_real (l2, compare_func, user_data),
1067                             compare_func,
1068                             user_data);
1069 }
1070
1071 /**
1072  * g_list_sort:
1073  * @list: a #GList
1074  * @compare_func: the comparison function used to sort the #GList.
1075  *     This function is passed the data from 2 elements of the #GList
1076  *     and should return 0 if they are equal, a negative value if the
1077  *     first element comes before the second, or a positive value if
1078  *     the first element comes after the second.
1079  *
1080  * Sorts a #GList using the given comparison function.
1081  *
1082  * Returns: the start of the sorted #GList
1083  */
1084 /**
1085  * GCompareFunc:
1086  * @a: a value.
1087  * @b: a value to compare with.
1088  * @Returns: negative value if @a &lt; @b; zero if @a = @b; positive
1089  *           value if @a > @b.
1090  *
1091  * Specifies the type of a comparison function used to compare two
1092  * values.  The function should return a negative integer if the first
1093  * value comes before the second, 0 if they are equal, or a positive
1094  * integer if the first value comes after the second.
1095  **/
1096 GList *
1097 g_list_sort (GList        *list,
1098              GCompareFunc  compare_func)
1099 {
1100   return g_list_sort_real (list, (GFunc) compare_func, NULL);
1101
1102 }
1103
1104 /**
1105  * g_list_sort_with_data:
1106  * @list: a #GList
1107  * @compare_func: comparison function
1108  * @user_data: user data to pass to comparison function
1109  *
1110  * Like g_list_sort(), but the comparison function accepts
1111  * a user data argument.
1112  *
1113  * Returns: the new head of @list
1114  */
1115 /**
1116  * GCompareDataFunc:
1117  * @a: a value.
1118  * @b: a value to compare with.
1119  * @user_data: user data to pass to comparison function.
1120  * @Returns: negative value if @a &lt; @b; zero if @a = @b; positive
1121  *           value if @a > @b.
1122  *
1123  * Specifies the type of a comparison function used to compare two
1124  * values.  The function should return a negative integer if the first
1125  * value comes before the second, 0 if they are equal, or a positive
1126  * integer if the first value comes after the second.
1127  **/
1128 GList *
1129 g_list_sort_with_data (GList            *list,
1130                        GCompareDataFunc  compare_func,
1131                        gpointer          user_data)
1132 {
1133   return g_list_sort_real (list, (GFunc) compare_func, user_data);
1134 }