Merge branch 'source-get-id-docs' into 'master'
[glib.git] / glib / glist.c
blob6f2079a4c431e0a2a8c35c4d954368f53d066e77
1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
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.1 of the License, or (at your option) any later version.
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.
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
19 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
20 * file for a list of people on the GLib Team. See the ChangeLog
21 * files for a list of changes. These files are distributed with
22 * GLib at ftp://ftp.gtk.org/pub/gtk/.
26 * MT safe
29 #include "config.h"
31 #include "glist.h"
32 #include "gslice.h"
33 #include "gmessages.h"
35 #include "gtestutils.h"
37 /**
38 * SECTION:linked_lists_double
39 * @title: Doubly-Linked Lists
40 * @short_description: linked lists that can be iterated over in both directions
42 * The #GList structure and its associated functions provide a standard
43 * doubly-linked list data structure.
45 * Each element in the list contains a piece of data, together with
46 * pointers which link to the previous and next elements in the list.
47 * Using these pointers it is possible to move through the list in both
48 * directions (unlike the singly-linked [GSList][glib-Singly-Linked-Lists],
49 * which only allows movement through the list in the forward direction).
51 * The double linked list does not keep track of the number of items
52 * and does not keep track of both the start and end of the list. If
53 * you want fast access to both the start and the end of the list,
54 * and/or the number of items in the list, use a
55 * [GQueue][glib-Double-ended-Queues] instead.
57 * The data contained in each element can be either integer values, by
58 * using one of the [Type Conversion Macros][glib-Type-Conversion-Macros],
59 * or simply pointers to any type of data.
61 * List elements are allocated from the [slice allocator][glib-Memory-Slices],
62 * which is more efficient than allocating elements individually.
64 * Note that most of the #GList functions expect to be passed a pointer
65 * to the first element in the list. The functions which insert
66 * elements return the new start of the list, which may have changed.
68 * There is no function to create a #GList. %NULL is considered to be
69 * a valid, empty list so you simply set a #GList* to %NULL to initialize
70 * it.
72 * To add elements, use g_list_append(), g_list_prepend(),
73 * g_list_insert() and g_list_insert_sorted().
75 * To visit all elements in the list, use a loop over the list:
76 * |[<!-- language="C" -->
77 * GList *l;
78 * for (l = list; l != NULL; l = l->next)
79 * {
80 * // do something with l->data
81 * }
82 * ]|
84 * To call a function for each element in the list, use g_list_foreach().
86 * To loop over the list and modify it (e.g. remove a certain element)
87 * a while loop is more appropriate, for example:
88 * |[<!-- language="C" -->
89 * GList *l = list;
90 * while (l != NULL)
91 * {
92 * GList *next = l->next;
93 * if (should_be_removed (l))
94 * {
95 * // possibly free l->data
96 * list = g_list_delete_link (list, l);
97 * }
98 * l = next;
99 * }
100 * ]|
102 * To remove elements, use g_list_remove().
104 * To navigate in a list, use g_list_first(), g_list_last(),
105 * g_list_next(), g_list_previous().
107 * To find elements in the list use g_list_nth(), g_list_nth_data(),
108 * g_list_find() and g_list_find_custom().
110 * To find the index of an element use g_list_position() and
111 * g_list_index().
113 * To free the entire list, use g_list_free() or g_list_free_full().
117 * GList:
118 * @data: holds the element's data, which can be a pointer to any kind
119 * of data, or any integer value using the
120 * [Type Conversion Macros][glib-Type-Conversion-Macros]
121 * @next: contains the link to the next element in the list
122 * @prev: contains the link to the previous element in the list
124 * The #GList struct is used for each element in a doubly-linked list.
128 * g_list_previous:
129 * @list: an element in a #GList
131 * A convenience macro to get the previous element in a #GList.
132 * Note that it is considered perfectly acceptable to access
133 * @list->prev directly.
135 * Returns: the previous element, or %NULL if there are no previous
136 * elements
140 * g_list_next:
141 * @list: an element in a #GList
143 * A convenience macro to get the next element in a #GList.
144 * Note that it is considered perfectly acceptable to access
145 * @list->next directly.
147 * Returns: the next element, or %NULL if there are no more elements
150 #define _g_list_alloc() g_slice_new (GList)
151 #define _g_list_alloc0() g_slice_new0 (GList)
152 #define _g_list_free1(list) g_slice_free (GList, list)
155 * g_list_alloc:
157 * Allocates space for one #GList element. It is called by
158 * g_list_append(), g_list_prepend(), g_list_insert() and
159 * g_list_insert_sorted() and so is rarely used on its own.
161 * Returns: a pointer to the newly-allocated #GList element
163 GList *
164 g_list_alloc (void)
166 return _g_list_alloc0 ();
170 * g_list_free:
171 * @list: a #GList
173 * Frees all of the memory used by a #GList.
174 * The freed elements are returned to the slice allocator.
176 * If list elements contain dynamically-allocated memory, you should
177 * either use g_list_free_full() or free them manually first.
179 void
180 g_list_free (GList *list)
182 g_slice_free_chain (GList, list, next);
186 * g_list_free_1:
187 * @list: a #GList element
189 * Frees one #GList element, but does not update links from the next and
190 * previous elements in the list, so you should not call this function on an
191 * element that is currently part of a list.
193 * It is usually used after g_list_remove_link().
196 * g_list_free1:
198 * Another name for g_list_free_1().
200 void
201 g_list_free_1 (GList *list)
203 _g_list_free1 (list);
207 * g_list_free_full:
208 * @list: a pointer to a #GList
209 * @free_func: the function to be called to free each element's data
211 * Convenience method, which frees all the memory used by a #GList,
212 * and calls @free_func on every element's data.
214 * @free_func must not modify the list (eg, by removing the freed
215 * element from it).
217 * Since: 2.28
219 void
220 g_list_free_full (GList *list,
221 GDestroyNotify free_func)
223 g_list_foreach (list, (GFunc) free_func, NULL);
224 g_list_free (list);
228 * g_list_append:
229 * @list: a pointer to a #GList
230 * @data: the data for the new element
232 * Adds a new element on to the end of the list.
234 * Note that the return value is the new start of the list,
235 * if @list was empty; make sure you store the new value.
237 * g_list_append() has to traverse the entire list to find the end,
238 * which is inefficient when adding multiple elements. A common idiom
239 * to avoid the inefficiency is to use g_list_prepend() and reverse
240 * the list with g_list_reverse() when all elements have been added.
242 * |[<!-- language="C" -->
243 * // Notice that these are initialized to the empty list.
244 * GList *string_list = NULL, *number_list = NULL;
246 * // This is a list of strings.
247 * string_list = g_list_append (string_list, "first");
248 * string_list = g_list_append (string_list, "second");
250 * // This is a list of integers.
251 * number_list = g_list_append (number_list, GINT_TO_POINTER (27));
252 * number_list = g_list_append (number_list, GINT_TO_POINTER (14));
253 * ]|
255 * Returns: either @list or the new start of the #GList if @list was %NULL
257 GList *
258 g_list_append (GList *list,
259 gpointer data)
261 GList *new_list;
262 GList *last;
264 new_list = _g_list_alloc ();
265 new_list->data = data;
266 new_list->next = NULL;
268 if (list)
270 last = g_list_last (list);
271 /* g_assert (last != NULL); */
272 last->next = new_list;
273 new_list->prev = last;
275 return list;
277 else
279 new_list->prev = NULL;
280 return new_list;
285 * g_list_prepend:
286 * @list: a pointer to a #GList, this must point to the top of the list
287 * @data: the data for the new element
289 * Prepends a new element on to the start of the list.
291 * Note that the return value is the new start of the list,
292 * which will have changed, so make sure you store the new value.
294 * |[<!-- language="C" -->
295 * // Notice that it is initialized to the empty list.
296 * GList *list = NULL;
298 * list = g_list_prepend (list, "last");
299 * list = g_list_prepend (list, "first");
300 * ]|
302 * Do not use this function to prepend a new element to a different
303 * element than the start of the list. Use g_list_insert_before() instead.
305 * Returns: a pointer to the newly prepended element, which is the new
306 * start of the #GList
308 GList *
309 g_list_prepend (GList *list,
310 gpointer data)
312 GList *new_list;
314 new_list = _g_list_alloc ();
315 new_list->data = data;
316 new_list->next = list;
318 if (list)
320 new_list->prev = list->prev;
321 if (list->prev)
322 list->prev->next = new_list;
323 list->prev = new_list;
325 else
326 new_list->prev = NULL;
328 return new_list;
332 * g_list_insert:
333 * @list: a pointer to a #GList, this must point to the top of the list
334 * @data: the data for the new element
335 * @position: the position to insert the element. If this is
336 * negative, or is larger than the number of elements in the
337 * list, the new element is added on to the end of the list.
339 * Inserts a new element into the list at the given position.
341 * Returns: the (possibly changed) start of the #GList
343 GList *
344 g_list_insert (GList *list,
345 gpointer data,
346 gint position)
348 GList *new_list;
349 GList *tmp_list;
351 if (position < 0)
352 return g_list_append (list, data);
353 else if (position == 0)
354 return g_list_prepend (list, data);
356 tmp_list = g_list_nth (list, position);
357 if (!tmp_list)
358 return g_list_append (list, data);
360 new_list = _g_list_alloc ();
361 new_list->data = data;
362 new_list->prev = tmp_list->prev;
363 tmp_list->prev->next = new_list;
364 new_list->next = tmp_list;
365 tmp_list->prev = new_list;
367 return list;
371 * g_list_insert_before:
372 * @list: a pointer to a #GList, this must point to the top of the list
373 * @sibling: the list element before which the new element
374 * is inserted or %NULL to insert at the end of the list
375 * @data: the data for the new element
377 * Inserts a new element into the list before the given position.
379 * Returns: the (possibly changed) start of the #GList
381 GList *
382 g_list_insert_before (GList *list,
383 GList *sibling,
384 gpointer data)
386 if (!list)
388 list = g_list_alloc ();
389 list->data = data;
390 g_return_val_if_fail (sibling == NULL, list);
391 return list;
393 else if (sibling)
395 GList *node;
397 node = _g_list_alloc ();
398 node->data = data;
399 node->prev = sibling->prev;
400 node->next = sibling;
401 sibling->prev = node;
402 if (node->prev)
404 node->prev->next = node;
405 return list;
407 else
409 g_return_val_if_fail (sibling == list, node);
410 return node;
413 else
415 GList *last;
417 last = list;
418 while (last->next)
419 last = last->next;
421 last->next = _g_list_alloc ();
422 last->next->data = data;
423 last->next->prev = last;
424 last->next->next = NULL;
426 return list;
431 * g_list_concat:
432 * @list1: a #GList, this must point to the top of the list
433 * @list2: the #GList to add to the end of the first #GList,
434 * this must point to the top of the list
436 * Adds the second #GList onto the end of the first #GList.
437 * Note that the elements of the second #GList are not copied.
438 * They are used directly.
440 * This function is for example used to move an element in the list.
441 * The following example moves an element to the top of the list:
442 * |[<!-- language="C" -->
443 * list = g_list_remove_link (list, llink);
444 * list = g_list_concat (llink, list);
445 * ]|
447 * Returns: the start of the new #GList, which equals @list1 if not %NULL
449 GList *
450 g_list_concat (GList *list1,
451 GList *list2)
453 GList *tmp_list;
455 if (list2)
457 tmp_list = g_list_last (list1);
458 if (tmp_list)
459 tmp_list->next = list2;
460 else
461 list1 = list2;
462 list2->prev = tmp_list;
465 return list1;
468 static inline GList *
469 _g_list_remove_link (GList *list,
470 GList *link)
472 if (link == NULL)
473 return list;
475 if (link->prev)
477 if (link->prev->next == link)
478 link->prev->next = link->next;
479 else
480 g_warning ("corrupted double-linked list detected");
482 if (link->next)
484 if (link->next->prev == link)
485 link->next->prev = link->prev;
486 else
487 g_warning ("corrupted double-linked list detected");
490 if (link == list)
491 list = list->next;
493 link->next = NULL;
494 link->prev = NULL;
496 return list;
500 * g_list_remove:
501 * @list: a #GList, this must point to the top of the list
502 * @data: the data of the element to remove
504 * Removes an element from a #GList.
505 * If two elements contain the same data, only the first is removed.
506 * If none of the elements contain the data, the #GList is unchanged.
508 * Returns: the (possibly changed) start of the #GList
510 GList *
511 g_list_remove (GList *list,
512 gconstpointer data)
514 GList *tmp;
516 tmp = list;
517 while (tmp)
519 if (tmp->data != data)
520 tmp = tmp->next;
521 else
523 list = _g_list_remove_link (list, tmp);
524 _g_list_free1 (tmp);
526 break;
529 return list;
533 * g_list_remove_all:
534 * @list: a #GList, this must point to the top of the list
535 * @data: data to remove
537 * Removes all list nodes with data equal to @data.
538 * Returns the new head of the list. Contrast with
539 * g_list_remove() which removes only the first node
540 * matching the given data.
542 * Returns: the (possibly changed) start of the #GList
544 GList *
545 g_list_remove_all (GList *list,
546 gconstpointer data)
548 GList *tmp = list;
550 while (tmp)
552 if (tmp->data != data)
553 tmp = tmp->next;
554 else
556 GList *next = tmp->next;
558 if (tmp->prev)
559 tmp->prev->next = next;
560 else
561 list = next;
562 if (next)
563 next->prev = tmp->prev;
565 _g_list_free1 (tmp);
566 tmp = next;
569 return list;
573 * g_list_remove_link:
574 * @list: a #GList, this must point to the top of the list
575 * @llink: an element in the #GList
577 * Removes an element from a #GList, without freeing the element.
578 * The removed element's prev and next links are set to %NULL, so
579 * that it becomes a self-contained list with one element.
581 * This function is for example used to move an element in the list
582 * (see the example for g_list_concat()) or to remove an element in
583 * the list before freeing its data:
584 * |[<!-- language="C" -->
585 * list = g_list_remove_link (list, llink);
586 * free_some_data_that_may_access_the_list_again (llink->data);
587 * g_list_free (llink);
588 * ]|
590 * Returns: the (possibly changed) start of the #GList
592 GList *
593 g_list_remove_link (GList *list,
594 GList *llink)
596 return _g_list_remove_link (list, llink);
600 * g_list_delete_link:
601 * @list: a #GList, this must point to the top of the list
602 * @link_: node to delete from @list
604 * Removes the node link_ from the list and frees it.
605 * Compare this to g_list_remove_link() which removes the node
606 * without freeing it.
608 * Returns: the (possibly changed) start of the #GList
610 GList *
611 g_list_delete_link (GList *list,
612 GList *link_)
614 list = _g_list_remove_link (list, link_);
615 _g_list_free1 (link_);
617 return list;
621 * g_list_copy:
622 * @list: a #GList, this must point to the top of the list
624 * Copies a #GList.
626 * Note that this is a "shallow" copy. If the list elements
627 * consist of pointers to data, the pointers are copied but
628 * the actual data is not. See g_list_copy_deep() if you need
629 * to copy the data as well.
631 * Returns: the start of the new list that holds the same data as @list
633 GList *
634 g_list_copy (GList *list)
636 return g_list_copy_deep (list, NULL, NULL);
640 * g_list_copy_deep:
641 * @list: a #GList, this must point to the top of the list
642 * @func: a copy function used to copy every element in the list
643 * @user_data: user data passed to the copy function @func, or %NULL
645 * Makes a full (deep) copy of a #GList.
647 * In contrast with g_list_copy(), this function uses @func to make
648 * a copy of each list element, in addition to copying the list
649 * container itself.
651 * @func, as a #GCopyFunc, takes two arguments, the data to be copied
652 * and a @user_data pointer. It's safe to pass %NULL as user_data,
653 * if the copy function takes only one argument.
655 * For instance, if @list holds a list of GObjects, you can do:
656 * |[<!-- language="C" -->
657 * another_list = g_list_copy_deep (list, (GCopyFunc) g_object_ref, NULL);
658 * ]|
660 * And, to entirely free the new list, you could do:
661 * |[<!-- language="C" -->
662 * g_list_free_full (another_list, g_object_unref);
663 * ]|
665 * Returns: the start of the new list that holds a full copy of @list,
666 * use g_list_free_full() to free it
668 * Since: 2.34
670 GList *
671 g_list_copy_deep (GList *list,
672 GCopyFunc func,
673 gpointer user_data)
675 GList *new_list = NULL;
677 if (list)
679 GList *last;
681 new_list = _g_list_alloc ();
682 if (func)
683 new_list->data = func (list->data, user_data);
684 else
685 new_list->data = list->data;
686 new_list->prev = NULL;
687 last = new_list;
688 list = list->next;
689 while (list)
691 last->next = _g_list_alloc ();
692 last->next->prev = last;
693 last = last->next;
694 if (func)
695 last->data = func (list->data, user_data);
696 else
697 last->data = list->data;
698 list = list->next;
700 last->next = NULL;
703 return new_list;
707 * g_list_reverse:
708 * @list: a #GList, this must point to the top of the list
710 * Reverses a #GList.
711 * It simply switches the next and prev pointers of each element.
713 * Returns: the start of the reversed #GList
715 GList *
716 g_list_reverse (GList *list)
718 GList *last;
720 last = NULL;
721 while (list)
723 last = list;
724 list = last->next;
725 last->next = last->prev;
726 last->prev = list;
729 return last;
733 * g_list_nth:
734 * @list: a #GList, this must point to the top of the list
735 * @n: the position of the element, counting from 0
737 * Gets the element at the given position in a #GList.
739 * This iterates over the list until it reaches the @n-th position. If you
740 * intend to iterate over every element, it is better to use a for-loop as
741 * described in the #GList introduction.
743 * Returns: the element, or %NULL if the position is off
744 * the end of the #GList
746 GList *
747 g_list_nth (GList *list,
748 guint n)
750 while ((n-- > 0) && list)
751 list = list->next;
753 return list;
757 * g_list_nth_prev:
758 * @list: a #GList
759 * @n: the position of the element, counting from 0
761 * Gets the element @n places before @list.
763 * Returns: the element, or %NULL if the position is
764 * off the end of the #GList
766 GList *
767 g_list_nth_prev (GList *list,
768 guint n)
770 while ((n-- > 0) && list)
771 list = list->prev;
773 return list;
777 * g_list_nth_data:
778 * @list: a #GList, this must point to the top of the list
779 * @n: the position of the element
781 * Gets the data of the element at the given position.
783 * This iterates over the list until it reaches the @n-th position. If you
784 * intend to iterate over every element, it is better to use a for-loop as
785 * described in the #GList introduction.
787 * Returns: the element's data, or %NULL if the position
788 * is off the end of the #GList
790 gpointer
791 g_list_nth_data (GList *list,
792 guint n)
794 while ((n-- > 0) && list)
795 list = list->next;
797 return list ? list->data : NULL;
801 * g_list_find:
802 * @list: a #GList, this must point to the top of the list
803 * @data: the element data to find
805 * Finds the element in a #GList which contains the given data.
807 * Returns: the found #GList element, or %NULL if it is not found
809 GList *
810 g_list_find (GList *list,
811 gconstpointer data)
813 while (list)
815 if (list->data == data)
816 break;
817 list = list->next;
820 return list;
824 * g_list_find_custom:
825 * @list: a #GList, this must point to the top of the list
826 * @data: user data passed to the function
827 * @func: the function to call for each element.
828 * It should return 0 when the desired element is found
830 * Finds an element in a #GList, using a supplied function to
831 * find the desired element. It iterates over the list, calling
832 * the given function which should return 0 when the desired
833 * element is found. The function takes two #gconstpointer arguments,
834 * the #GList element's data as the first argument and the
835 * given user data.
837 * Returns: the found #GList element, or %NULL if it is not found
839 GList *
840 g_list_find_custom (GList *list,
841 gconstpointer data,
842 GCompareFunc func)
844 g_return_val_if_fail (func != NULL, list);
846 while (list)
848 if (! func (list->data, data))
849 return list;
850 list = list->next;
853 return NULL;
857 * g_list_position:
858 * @list: a #GList, this must point to the top of the list
859 * @llink: an element in the #GList
861 * Gets the position of the given element
862 * in the #GList (starting from 0).
864 * Returns: the position of the element in the #GList,
865 * or -1 if the element is not found
867 gint
868 g_list_position (GList *list,
869 GList *llink)
871 gint i;
873 i = 0;
874 while (list)
876 if (list == llink)
877 return i;
878 i++;
879 list = list->next;
882 return -1;
886 * g_list_index:
887 * @list: a #GList, this must point to the top of the list
888 * @data: the data to find
890 * Gets the position of the element containing
891 * the given data (starting from 0).
893 * Returns: the index of the element containing the data,
894 * or -1 if the data is not found
896 gint
897 g_list_index (GList *list,
898 gconstpointer data)
900 gint i;
902 i = 0;
903 while (list)
905 if (list->data == data)
906 return i;
907 i++;
908 list = list->next;
911 return -1;
915 * g_list_last:
916 * @list: any #GList element
918 * Gets the last element in a #GList.
920 * Returns: the last element in the #GList,
921 * or %NULL if the #GList has no elements
923 GList *
924 g_list_last (GList *list)
926 if (list)
928 while (list->next)
929 list = list->next;
932 return list;
936 * g_list_first:
937 * @list: any #GList element
939 * Gets the first element in a #GList.
941 * Returns: the first element in the #GList,
942 * or %NULL if the #GList has no elements
944 GList *
945 g_list_first (GList *list)
947 if (list)
949 while (list->prev)
950 list = list->prev;
953 return list;
957 * g_list_length:
958 * @list: a #GList, this must point to the top of the list
960 * Gets the number of elements in a #GList.
962 * This function iterates over the whole list to count its elements.
963 * Use a #GQueue instead of a GList if you regularly need the number
964 * of items. To check whether the list is non-empty, it is faster to check
965 * @list against %NULL.
967 * Returns: the number of elements in the #GList
969 guint
970 g_list_length (GList *list)
972 guint length;
974 length = 0;
975 while (list)
977 length++;
978 list = list->next;
981 return length;
985 * g_list_foreach:
986 * @list: a #GList, this must point to the top of the list
987 * @func: the function to call with each element's data
988 * @user_data: user data to pass to the function
990 * Calls a function for each element of a #GList.
992 * It is safe for @func to remove the element from @list, but it must
993 * not modify any part of the list after that element.
996 * GFunc:
997 * @data: the element's data
998 * @user_data: user data passed to g_list_foreach() or g_slist_foreach()
1000 * Specifies the type of functions passed to g_list_foreach() and
1001 * g_slist_foreach().
1003 void
1004 g_list_foreach (GList *list,
1005 GFunc func,
1006 gpointer user_data)
1008 while (list)
1010 GList *next = list->next;
1011 (*func) (list->data, user_data);
1012 list = next;
1016 static GList*
1017 g_list_insert_sorted_real (GList *list,
1018 gpointer data,
1019 GFunc func,
1020 gpointer user_data)
1022 GList *tmp_list = list;
1023 GList *new_list;
1024 gint cmp;
1026 g_return_val_if_fail (func != NULL, list);
1028 if (!list)
1030 new_list = _g_list_alloc0 ();
1031 new_list->data = data;
1032 return new_list;
1035 cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);
1037 while ((tmp_list->next) && (cmp > 0))
1039 tmp_list = tmp_list->next;
1041 cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);
1044 new_list = _g_list_alloc0 ();
1045 new_list->data = data;
1047 if ((!tmp_list->next) && (cmp > 0))
1049 tmp_list->next = new_list;
1050 new_list->prev = tmp_list;
1051 return list;
1054 if (tmp_list->prev)
1056 tmp_list->prev->next = new_list;
1057 new_list->prev = tmp_list->prev;
1059 new_list->next = tmp_list;
1060 tmp_list->prev = new_list;
1062 if (tmp_list == list)
1063 return new_list;
1064 else
1065 return list;
1069 * g_list_insert_sorted:
1070 * @list: a pointer to a #GList, this must point to the top of the
1071 * already sorted list
1072 * @data: the data for the new element
1073 * @func: the function to compare elements in the list. It should
1074 * return a number > 0 if the first parameter comes after the
1075 * second parameter in the sort order.
1077 * Inserts a new element into the list, using the given comparison
1078 * function to determine its position.
1080 * If you are adding many new elements to a list, and the number of
1081 * new elements is much larger than the length of the list, use
1082 * g_list_prepend() to add the new items and sort the list afterwards
1083 * with g_list_sort().
1085 * Returns: the (possibly changed) start of the #GList
1087 GList *
1088 g_list_insert_sorted (GList *list,
1089 gpointer data,
1090 GCompareFunc func)
1092 return g_list_insert_sorted_real (list, data, (GFunc) func, NULL);
1096 * g_list_insert_sorted_with_data:
1097 * @list: a pointer to a #GList, this must point to the top of the
1098 * already sorted list
1099 * @data: the data for the new element
1100 * @func: the function to compare elements in the list. It should
1101 * return a number > 0 if the first parameter comes after the
1102 * second parameter in the sort order.
1103 * @user_data: user data to pass to comparison function
1105 * Inserts a new element into the list, using the given comparison
1106 * function to determine its position.
1108 * If you are adding many new elements to a list, and the number of
1109 * new elements is much larger than the length of the list, use
1110 * g_list_prepend() to add the new items and sort the list afterwards
1111 * with g_list_sort().
1113 * Returns: the (possibly changed) start of the #GList
1115 * Since: 2.10
1117 GList *
1118 g_list_insert_sorted_with_data (GList *list,
1119 gpointer data,
1120 GCompareDataFunc func,
1121 gpointer user_data)
1123 return g_list_insert_sorted_real (list, data, (GFunc) func, user_data);
1126 static GList *
1127 g_list_sort_merge (GList *l1,
1128 GList *l2,
1129 GFunc compare_func,
1130 gpointer user_data)
1132 GList list, *l, *lprev;
1133 gint cmp;
1135 l = &list;
1136 lprev = NULL;
1138 while (l1 && l2)
1140 cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data);
1142 if (cmp <= 0)
1144 l->next = l1;
1145 l1 = l1->next;
1147 else
1149 l->next = l2;
1150 l2 = l2->next;
1152 l = l->next;
1153 l->prev = lprev;
1154 lprev = l;
1156 l->next = l1 ? l1 : l2;
1157 l->next->prev = l;
1159 return list.next;
1162 static GList *
1163 g_list_sort_real (GList *list,
1164 GFunc compare_func,
1165 gpointer user_data)
1167 GList *l1, *l2;
1169 if (!list)
1170 return NULL;
1171 if (!list->next)
1172 return list;
1174 l1 = list;
1175 l2 = list->next;
1177 while ((l2 = l2->next) != NULL)
1179 if ((l2 = l2->next) == NULL)
1180 break;
1181 l1 = l1->next;
1183 l2 = l1->next;
1184 l1->next = NULL;
1186 return g_list_sort_merge (g_list_sort_real (list, compare_func, user_data),
1187 g_list_sort_real (l2, compare_func, user_data),
1188 compare_func,
1189 user_data);
1193 * g_list_sort:
1194 * @list: a #GList, this must point to the top of the list
1195 * @compare_func: the comparison function used to sort the #GList.
1196 * This function is passed the data from 2 elements of the #GList
1197 * and should return 0 if they are equal, a negative value if the
1198 * first element comes before the second, or a positive value if
1199 * the first element comes after the second.
1201 * Sorts a #GList using the given comparison function. The algorithm
1202 * used is a stable sort.
1204 * Returns: the (possibly changed) start of the #GList
1207 * GCompareFunc:
1208 * @a: a value
1209 * @b: a value to compare with
1211 * Specifies the type of a comparison function used to compare two
1212 * values. The function should return a negative integer if the first
1213 * value comes before the second, 0 if they are equal, or a positive
1214 * integer if the first value comes after the second.
1216 * Returns: negative value if @a < @b; zero if @a = @b; positive
1217 * value if @a > @b
1219 GList *
1220 g_list_sort (GList *list,
1221 GCompareFunc compare_func)
1223 return g_list_sort_real (list, (GFunc) compare_func, NULL);
1227 * g_list_sort_with_data:
1228 * @list: a #GList, this must point to the top of the list
1229 * @compare_func: comparison function
1230 * @user_data: user data to pass to comparison function
1232 * Like g_list_sort(), but the comparison function accepts
1233 * a user data argument.
1235 * Returns: the (possibly changed) start of the #GList
1238 * GCompareDataFunc:
1239 * @a: a value
1240 * @b: a value to compare with
1241 * @user_data: user data
1243 * Specifies the type of a comparison function used to compare two
1244 * values. The function should return a negative integer if the first
1245 * value comes before the second, 0 if they are equal, or a positive
1246 * integer if the first value comes after the second.
1248 * Returns: negative value if @a < @b; zero if @a = @b; positive
1249 * value if @a > @b
1251 GList *
1252 g_list_sort_with_data (GList *list,
1253 GCompareDataFunc compare_func,
1254 gpointer user_data)
1256 return g_list_sort_real (list, (GFunc) compare_func, user_data);