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 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, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
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/.
36 #include "gtestutils.h"
39 * SECTION:linked_lists_double
40 * @title: Doubly-Linked Lists
41 * @short_description: linked lists that can be iterated over in both directions
43 * The #GList structure and its associated functions provide a standard
44 * doubly-linked list data structure.
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).
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.
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.
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.
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.
68 * To add elements, use g_list_append(), g_list_prepend(),
69 * g_list_insert() and g_list_insert_sorted().
71 * To remove elements, use g_list_remove().
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().
77 * To find the index of an element use g_list_position() and
80 * To call a function for each element in the list use g_list_foreach().
82 * To free the entire list, use g_list_free().
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
91 * @next: contains the link to the next element in the list.
92 * @prev: contains the link to the previous element in the list.
94 * The #GList struct is used for each element in a doubly-linked list.
99 * @list: an element in a #GList.
100 * @Returns: the previous element, or %NULL if there are no previous
103 * A convenience macro to get the previous element in a #GList.
108 * @list: an element in a #GList.
109 * @Returns: the next element, or %NULL if there are no more elements.
111 * A convenience macro to get the next element in a #GList.
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)
120 * @Returns: a pointer to the newly-allocated #GList element.
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.
129 return _g_list_alloc0 ();
136 * Frees all of the memory used by a #GList.
137 * The freed elements are returned to the slice allocator.
140 * If list elements contain dynamically-allocated memory,
141 * you should either use g_list_free_full() or free them manually
146 g_list_free (GList
*list
)
148 g_slice_free_chain (GList
, list
, next
);
153 * @list: a #GList element
155 * Frees one #GList element.
156 * It is usually used after g_list_remove_link().
161 * Another name for g_list_free_1().
164 g_list_free_1 (GList
*list
)
166 _g_list_free1 (list
);
171 * @list: a pointer to a #GList
172 * @free_func: the function to be called to free each element's data
174 * Convenience method, which frees all the memory used by a #GList, and
175 * calls the specified destroy function on every element's data.
180 g_list_free_full (GList
*list
,
181 GDestroyNotify free_func
)
183 g_list_foreach (list
, (GFunc
) free_func
, NULL
);
189 * @list: a pointer to a #GList
190 * @data: the data for the new element
192 * Adds a new element on to the end of the list.
195 * The return value is the new start of the list, which
196 * may have changed, so make sure you store the new value.
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.
207 * /* Notice that these are initialized to the empty list. */
208 * GList *list = NULL, *number_list = NULL;
210 * /* This is a list of strings. */
211 * list = g_list_append (list, "first");
212 * list = g_list_append (list, "second");
214 * /* This is a list of integers. */
215 * number_list = g_list_append (number_list, GINT_TO_POINTER (27));
216 * number_list = g_list_append (number_list, GINT_TO_POINTER (14));
219 * Returns: the new start of the #GList
222 g_list_append (GList
*list
,
228 new_list
= _g_list_alloc ();
229 new_list
->data
= data
;
230 new_list
->next
= NULL
;
234 last
= g_list_last (list
);
235 /* g_assert (last != NULL); */
236 last
->next
= new_list
;
237 new_list
->prev
= last
;
243 new_list
->prev
= NULL
;
250 * @list: a pointer to a #GList
251 * @data: the data for the new element
253 * Adds a new element on to the start of the list.
256 * The return value is the new start of the list, which
257 * may have changed, so make sure you store the new value.
261 * /* Notice that it is initialized to the empty list. */
262 * GList *list = NULL;
263 * list = g_list_prepend (list, "last");
264 * list = g_list_prepend (list, "first");
267 * Returns: the new start of the #GList
270 g_list_prepend (GList
*list
,
275 new_list
= _g_list_alloc ();
276 new_list
->data
= data
;
277 new_list
->next
= list
;
281 new_list
->prev
= list
->prev
;
283 list
->prev
->next
= new_list
;
284 list
->prev
= new_list
;
287 new_list
->prev
= NULL
;
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.
300 * Inserts a new element into the list at the given position.
302 * Returns: the new start of the #GList
305 g_list_insert (GList
*list
,
313 return g_list_append (list
, data
);
314 else if (position
== 0)
315 return g_list_prepend (list
, data
);
317 tmp_list
= g_list_nth (list
, position
);
319 return g_list_append (list
, data
);
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
;
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
338 * Inserts a new element into the list before the given position.
340 * Returns: the new start of the #GList
343 g_list_insert_before (GList
*list
,
349 list
= g_list_alloc ();
351 g_return_val_if_fail (sibling
== NULL
, list
);
358 node
= _g_list_alloc ();
360 node
->prev
= sibling
->prev
;
361 node
->next
= sibling
;
362 sibling
->prev
= node
;
365 node
->prev
->next
= node
;
370 g_return_val_if_fail (sibling
== list
, node
);
382 last
->next
= _g_list_alloc ();
383 last
->next
->data
= data
;
384 last
->next
->prev
= last
;
385 last
->next
->next
= NULL
;
394 * @list2: the #GList to add to the end of the first #GList
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.
400 * Returns: the start of the new #GList
403 g_list_concat (GList
*list1
, GList
*list2
)
409 tmp_list
= g_list_last (list1
);
411 tmp_list
->next
= list2
;
414 list2
->prev
= tmp_list
;
423 * @data: the data of the element to remove
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.
429 * Returns: the new start of the #GList
432 g_list_remove (GList
*list
,
440 if (tmp
->data
!= data
)
445 tmp
->prev
->next
= tmp
->next
;
447 tmp
->next
->prev
= tmp
->prev
;
463 * @data: data to remove
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.
470 * Returns: new head of @list
473 g_list_remove_all (GList
*list
,
480 if (tmp
->data
!= data
)
484 GList
*next
= tmp
->next
;
487 tmp
->prev
->next
= next
;
491 next
->prev
= tmp
->prev
;
501 _g_list_remove_link (GList
*list
,
507 link
->prev
->next
= link
->next
;
509 link
->next
->prev
= link
->prev
;
522 * g_list_remove_link:
524 * @llink: an element in the #GList
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.
530 * Returns: the new start of the #GList, without the element
533 g_list_remove_link (GList
*list
,
536 return _g_list_remove_link (list
, llink
);
540 * g_list_delete_link:
542 * @link_: node to delete from @list
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.
548 * Returns: the new head of @list
551 g_list_delete_link (GList
*list
,
554 list
= _g_list_remove_link (list
, link_
);
555 _g_list_free1 (link_
);
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. See g_list_copy_deep() if you need
570 * to copy the data as well.
573 * Returns: a copy of @list
576 g_list_copy (GList
*list
)
578 return g_list_copy_deep (list
, NULL
, NULL
);
584 * @func: a copy function used to copy every element in the list
585 * @user_data: user data passed to the copy function @func, or #NULL
587 * Makes a full (deep) copy of a #GList.
589 * In contrast with g_list_copy(), this function uses @func to make a copy of
590 * each list element, in addition to copying the list container itself.
592 * @func, as a #GCopyFunc, takes two arguments, the data to be copied and a user
593 * pointer. It's safe to pass #NULL as user_data, if the copy function takes only
596 * For instance, if @list holds a list of GObjects, you can do:
598 * another_list = g_list_copy_deep (list, (GCopyFunc) g_object_ref, NULL);
601 * And, to entirely free the new list, you could do:
603 * g_list_free_full (another_list, g_object_unref);
606 * Returns: a full copy of @list, use #g_list_free_full to free it
611 g_list_copy_deep (GList
*list
, GCopyFunc func
, gpointer user_data
)
613 GList
*new_list
= NULL
;
619 new_list
= _g_list_alloc ();
621 new_list
->data
= func (list
->data
, user_data
);
623 new_list
->data
= list
->data
;
624 new_list
->prev
= NULL
;
629 last
->next
= _g_list_alloc ();
630 last
->next
->prev
= last
;
633 last
->data
= func (list
->data
, user_data
);
635 last
->data
= list
->data
;
649 * It simply switches the next and prev pointers of each element.
651 * Returns: the start of the reversed #GList
654 g_list_reverse (GList
*list
)
663 last
->next
= last
->prev
;
673 * @n: the position of the element, counting from 0
675 * Gets the element at the given position in a #GList.
677 * Returns: the element, or %NULL if the position is off
678 * the end of the #GList
681 g_list_nth (GList
*list
,
684 while ((n
-- > 0) && list
)
693 * @n: the position of the element, counting from 0
695 * Gets the element @n places before @list.
697 * Returns: the element, or %NULL if the position is
698 * off the end of the #GList
701 g_list_nth_prev (GList
*list
,
704 while ((n
-- > 0) && list
)
713 * @n: the position of the element
715 * Gets the data of the element at the given position.
717 * Returns: the element's data, or %NULL if the position
718 * is off the end of the #GList
721 g_list_nth_data (GList
*list
,
724 while ((n
-- > 0) && list
)
727 return list
? list
->data
: NULL
;
733 * @data: the element data to find
735 * Finds the element in a #GList which
736 * contains the given data.
738 * Returns: the found #GList element,
739 * or %NULL if it is not found
742 g_list_find (GList
*list
,
747 if (list
->data
== data
)
756 * g_list_find_custom:
758 * @data: user data passed to the function
759 * @func: the function to call for each element.
760 * It should return 0 when the desired element is found
762 * Finds an element in a #GList, using a supplied function to
763 * find the desired element. It iterates over the list, calling
764 * the given function which should return 0 when the desired
765 * element is found. The function takes two #gconstpointer arguments,
766 * the #GList element's data as the first argument and the
769 * Returns: the found #GList element, or %NULL if it is not found
772 g_list_find_custom (GList
*list
,
776 g_return_val_if_fail (func
!= NULL
, list
);
780 if (! func (list
->data
, data
))
792 * @llink: an element in the #GList
794 * Gets the position of the given element
795 * in the #GList (starting from 0).
797 * Returns: the position of the element in the #GList,
798 * or -1 if the element is not found
801 g_list_position (GList
*list
,
821 * @data: the data to find
823 * Gets the position of the element containing
824 * the given data (starting from 0).
826 * Returns: the index of the element containing the data,
827 * or -1 if the data is not found
830 g_list_index (GList
*list
,
838 if (list
->data
== data
)
851 * Gets the last element in a #GList.
853 * Returns: the last element in the #GList,
854 * or %NULL if the #GList has no elements
857 g_list_last (GList
*list
)
872 * Gets the first element in a #GList.
874 * Returns: the first element in the #GList,
875 * or %NULL if the #GList has no elements
878 g_list_first (GList
*list
)
893 * Gets the number of elements in a #GList.
896 * This function iterates over the whole list to
897 * count its elements.
900 * Returns: the number of elements in the #GList
903 g_list_length (GList
*list
)
920 * @func: the function to call with each element's data
921 * @user_data: user data to pass to the function
923 * Calls a function for each element of a #GList.
927 * @data: the element's data.
928 * @user_data: user data passed to g_list_foreach() or
931 * Specifies the type of functions passed to g_list_foreach() and
935 g_list_foreach (GList
*list
,
941 GList
*next
= list
->next
;
942 (*func
) (list
->data
, user_data
);
948 g_list_insert_sorted_real (GList
*list
,
953 GList
*tmp_list
= list
;
957 g_return_val_if_fail (func
!= NULL
, list
);
961 new_list
= _g_list_alloc0 ();
962 new_list
->data
= data
;
966 cmp
= ((GCompareDataFunc
) func
) (data
, tmp_list
->data
, user_data
);
968 while ((tmp_list
->next
) && (cmp
> 0))
970 tmp_list
= tmp_list
->next
;
972 cmp
= ((GCompareDataFunc
) func
) (data
, tmp_list
->data
, user_data
);
975 new_list
= _g_list_alloc0 ();
976 new_list
->data
= data
;
978 if ((!tmp_list
->next
) && (cmp
> 0))
980 tmp_list
->next
= new_list
;
981 new_list
->prev
= tmp_list
;
987 tmp_list
->prev
->next
= new_list
;
988 new_list
->prev
= tmp_list
->prev
;
990 new_list
->next
= tmp_list
;
991 tmp_list
->prev
= new_list
;
993 if (tmp_list
== list
)
1000 * g_list_insert_sorted:
1001 * @list: a pointer to a #GList
1002 * @data: the data for the new element
1003 * @func: the function to compare elements in the list. It should
1004 * return a number > 0 if the first parameter comes after the
1005 * second parameter in the sort order.
1007 * Inserts a new element into the list, using the given comparison
1008 * function to determine its position.
1010 * Returns: the new start of the #GList
1013 g_list_insert_sorted (GList
*list
,
1017 return g_list_insert_sorted_real (list
, data
, (GFunc
) func
, NULL
);
1021 * g_list_insert_sorted_with_data:
1022 * @list: a pointer to a #GList
1023 * @data: the data for the new element
1024 * @func: the function to compare elements in the list.
1025 * It should return a number > 0 if the first parameter
1026 * comes after the second parameter in the sort order.
1027 * @user_data: user data to pass to comparison function.
1029 * Inserts a new element into the list, using the given comparison
1030 * function to determine its position.
1032 * Returns: the new start of the #GList
1037 g_list_insert_sorted_with_data (GList
*list
,
1039 GCompareDataFunc func
,
1042 return g_list_insert_sorted_real (list
, data
, (GFunc
) func
, user_data
);
1046 g_list_sort_merge (GList
*l1
,
1051 GList list
, *l
, *lprev
;
1059 cmp
= ((GCompareDataFunc
) compare_func
) (l1
->data
, l2
->data
, user_data
);
1075 l
->next
= l1
? l1
: l2
;
1082 g_list_sort_real (GList
*list
,
1096 while ((l2
= l2
->next
) != NULL
)
1098 if ((l2
= l2
->next
) == NULL
)
1105 return g_list_sort_merge (g_list_sort_real (list
, compare_func
, user_data
),
1106 g_list_sort_real (l2
, compare_func
, user_data
),
1114 * @compare_func: the comparison function used to sort the #GList.
1115 * This function is passed the data from 2 elements of the #GList
1116 * and should return 0 if they are equal, a negative value if the
1117 * first element comes before the second, or a positive value if
1118 * the first element comes after the second.
1120 * Sorts a #GList using the given comparison function. The algorithm
1121 * used is a stable sort.
1123 * Returns: the start of the sorted #GList
1128 * @b: a value to compare with.
1129 * @Returns: negative value if @a < @b; zero if @a = @b; positive
1132 * Specifies the type of a comparison function used to compare two
1133 * values. The function should return a negative integer if the first
1134 * value comes before the second, 0 if they are equal, or a positive
1135 * integer if the first value comes after the second.
1138 g_list_sort (GList
*list
,
1139 GCompareFunc compare_func
)
1141 return g_list_sort_real (list
, (GFunc
) compare_func
, NULL
);
1146 * g_list_sort_with_data:
1148 * @compare_func: comparison function
1149 * @user_data: user data to pass to comparison function
1151 * Like g_list_sort(), but the comparison function accepts
1152 * a user data argument.
1154 * Returns: the new head of @list
1159 * @b: a value to compare with.
1160 * @user_data: user data to pass to comparison function.
1161 * @Returns: negative value if @a < @b; zero if @a = @b; positive
1164 * Specifies the type of a comparison function used to compare two
1165 * values. The function should return a negative integer if the first
1166 * value comes before the second, 0 if they are equal, or a positive
1167 * integer if the first value comes after the second.
1170 g_list_sort_with_data (GList
*list
,
1171 GCompareDataFunc compare_func
,
1174 return g_list_sort_real (list
, (GFunc
) compare_func
, user_data
);