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