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