regex: Remove obsolete patch
[platform/upstream/glib.git] / 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 }