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