1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
4 * GQueue: Double ended queue implementation, piggy backed on GList.
5 * Copyright (C) 1998 Tim Janik
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2 of the License, or (at your option) any later version.
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the
19 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
20 * Boston, MA 02111-1307, USA.
29 * @Title: Double-ended Queues
30 * @Short_description: double-ended queue data structure
32 * The #GQueue structure and its associated functions provide a standard
33 * queue data structure. Internally, GQueue uses the same data structure
34 * as #GList to store elements.
36 * The data contained in each element can be either integer values, by
37 * using one of the <link linkend="glib-Type-Conversion-Macros">Type
38 * Conversion Macros</link>, or simply pointers to any type of data.
40 * To create a new GQueue, use g_queue_new().
42 * To initialize a statically-allocated GQueue, use #G_QUEUE_INIT or
45 * To add elements, use g_queue_push_head(), g_queue_push_head_link(),
46 * g_queue_push_tail() and g_queue_push_tail_link().
48 * To remove elements, use g_queue_pop_head() and g_queue_pop_tail().
50 * To free the entire queue, use g_queue_free().
56 #include "gtestutils.h"
62 * Creates a new #GQueue.
64 * Returns: a new #GQueue.
69 return g_slice_new0 (GQueue
);
76 * Frees the memory allocated for the #GQueue. Only call this function if
77 * @queue was created with g_queue_new(). If queue elements contain
78 * dynamically-allocated memory, they should be freed first.
81 * If queue elements contain dynamically-allocated memory,
82 * you should either use g_queue_free_full() or free them manually
87 g_queue_free (GQueue
*queue
)
89 g_return_if_fail (queue
!= NULL
);
91 g_list_free (queue
->head
);
92 g_slice_free (GQueue
, queue
);
97 * @queue: a pointer to a #GQueue
98 * @free_func: the function to be called to free each element's data
100 * Convenience method, which frees all the memory used by a #GQueue, and
101 * calls the specified destroy function on every element's data.
106 g_queue_free_full (GQueue
*queue
,
107 GDestroyNotify free_func
)
109 g_queue_foreach (queue
, (GFunc
) free_func
, NULL
);
110 g_queue_free (queue
);
115 * @queue: an uninitialized #GQueue
117 * A statically-allocated #GQueue must be initialized with this function
118 * before it can be used. Alternatively you can initialize it with
119 * #G_QUEUE_INIT. It is not necessary to initialize queues created with
125 g_queue_init (GQueue
*queue
)
127 g_return_if_fail (queue
!= NULL
);
129 queue
->head
= queue
->tail
= NULL
;
137 * Removes all the elements in @queue. If queue elements contain
138 * dynamically-allocated memory, they should be freed first.
143 g_queue_clear (GQueue
*queue
)
145 g_return_if_fail (queue
!= NULL
);
147 g_list_free (queue
->head
);
148 g_queue_init (queue
);
155 * Returns %TRUE if the queue is empty.
157 * Returns: %TRUE if the queue is empty.
160 g_queue_is_empty (GQueue
*queue
)
162 g_return_val_if_fail (queue
!= NULL
, TRUE
);
164 return queue
->head
== NULL
;
168 * g_queue_get_length:
171 * Returns the number of items in @queue.
173 * Return value: The number of items in @queue.
178 g_queue_get_length (GQueue
*queue
)
180 g_return_val_if_fail (queue
!= NULL
, 0);
182 return queue
->length
;
189 * Reverses the order of the items in @queue.
194 g_queue_reverse (GQueue
*queue
)
196 g_return_if_fail (queue
!= NULL
);
198 queue
->tail
= queue
->head
;
199 queue
->head
= g_list_reverse (queue
->head
);
206 * Copies a @queue. Note that is a shallow copy. If the elements in the
207 * queue consist of pointers to data, the pointers are copied, but the
208 * actual data is not.
210 * Return value: A copy of @queue
215 g_queue_copy (GQueue
*queue
)
220 g_return_val_if_fail (queue
!= NULL
, NULL
);
222 result
= g_queue_new ();
224 for (list
= queue
->head
; list
!= NULL
; list
= list
->next
)
225 g_queue_push_tail (result
, list
->data
);
233 * @func: the function to call for each element's data
234 * @user_data: user data to pass to @func
236 * Calls @func for each element in the queue passing @user_data to the
242 g_queue_foreach (GQueue
*queue
,
248 g_return_if_fail (queue
!= NULL
);
249 g_return_if_fail (func
!= NULL
);
254 GList
*next
= list
->next
;
255 func (list
->data
, user_data
);
263 * @data: data to find
265 * Finds the first link in @queue which contains @data.
267 * Return value: The first link in @queue which contains @data.
272 g_queue_find (GQueue
*queue
,
275 g_return_val_if_fail (queue
!= NULL
, NULL
);
277 return g_list_find (queue
->head
, data
);
281 * g_queue_find_custom:
283 * @data: user data passed to @func
284 * @func: a #GCompareFunc to call for each element. It should return 0
285 * when the desired element is found
287 * Finds an element in a #GQueue, using a supplied function to find the
288 * desired element. It iterates over the queue, calling the given function
289 * which should return 0 when the desired element is found. The function
290 * takes two gconstpointer arguments, the #GQueue element's data as the
291 * first argument and the given user data as the second argument.
293 * Return value: The found link, or %NULL if it wasn't found
298 g_queue_find_custom (GQueue
*queue
,
302 g_return_val_if_fail (queue
!= NULL
, NULL
);
303 g_return_val_if_fail (func
!= NULL
, NULL
);
305 return g_list_find_custom (queue
->head
, data
, func
);
311 * @compare_func: the #GCompareDataFunc used to sort @queue. This function
312 * is passed two elements of the queue and should return 0 if they are
313 * equal, a negative value if the first comes before the second, and
314 * a positive value if the second comes before the first.
315 * @user_data: user data passed to @compare_func
317 * Sorts @queue using @compare_func.
322 g_queue_sort (GQueue
*queue
,
323 GCompareDataFunc compare_func
,
326 g_return_if_fail (queue
!= NULL
);
327 g_return_if_fail (compare_func
!= NULL
);
329 queue
->head
= g_list_sort_with_data (queue
->head
, compare_func
, user_data
);
330 queue
->tail
= g_list_last (queue
->head
);
336 * @data: the data for the new element.
338 * Adds a new element at the head of the queue.
341 g_queue_push_head (GQueue
*queue
,
344 g_return_if_fail (queue
!= NULL
);
346 queue
->head
= g_list_prepend (queue
->head
, data
);
348 queue
->tail
= queue
->head
;
355 * @data: the data for the new element
356 * @n: the position to insert the new element. If @n is negative or
357 * larger than the number of elements in the @queue, the element is
358 * added to the end of the queue.
360 * Inserts a new element into @queue at the given position
365 g_queue_push_nth (GQueue
*queue
,
369 g_return_if_fail (queue
!= NULL
);
371 if (n
< 0 || n
>= queue
->length
)
373 g_queue_push_tail (queue
, data
);
377 g_queue_insert_before (queue
, g_queue_peek_nth_link (queue
, n
), data
);
381 * g_queue_push_head_link:
383 * @link_: a single #GList element, <emphasis>not</emphasis> a list with
384 * more than one element.
386 * Adds a new element at the head of the queue.
389 g_queue_push_head_link (GQueue
*queue
,
392 g_return_if_fail (queue
!= NULL
);
393 g_return_if_fail (link
!= NULL
);
394 g_return_if_fail (link
->prev
== NULL
);
395 g_return_if_fail (link
->next
== NULL
);
397 link
->next
= queue
->head
;
399 queue
->head
->prev
= link
;
409 * @data: the data for the new element.
411 * Adds a new element at the tail of the queue.
414 g_queue_push_tail (GQueue
*queue
,
417 g_return_if_fail (queue
!= NULL
);
419 queue
->tail
= g_list_append (queue
->tail
, data
);
420 if (queue
->tail
->next
)
421 queue
->tail
= queue
->tail
->next
;
423 queue
->head
= queue
->tail
;
428 * g_queue_push_tail_link:
430 * @link_: a single #GList element, <emphasis>not</emphasis> a list with
431 * more than one element.
433 * Adds a new element at the tail of the queue.
436 g_queue_push_tail_link (GQueue
*queue
,
439 g_return_if_fail (queue
!= NULL
);
440 g_return_if_fail (link
!= NULL
);
441 g_return_if_fail (link
->prev
== NULL
);
442 g_return_if_fail (link
->next
== NULL
);
444 link
->prev
= queue
->tail
;
446 queue
->tail
->next
= link
;
454 * g_queue_push_nth_link:
456 * @n: the position to insert the link. If this is negative or larger than
457 * the number of elements in @queue, the link is added to the end of
459 * @link_: the link to add to @queue
461 * Inserts @link into @queue at the given position.
466 g_queue_push_nth_link (GQueue
*queue
,
473 g_return_if_fail (queue
!= NULL
);
474 g_return_if_fail (link_
!= NULL
);
476 if (n
< 0 || n
>= queue
->length
)
478 g_queue_push_tail_link (queue
, link_
);
482 g_assert (queue
->head
);
483 g_assert (queue
->tail
);
485 next
= g_queue_peek_nth_link (queue
, n
);
495 if (queue
->head
->prev
)
496 queue
->head
= queue
->head
->prev
;
498 if (queue
->tail
->next
)
499 queue
->tail
= queue
->tail
->next
;
508 * Removes the first element of the queue.
510 * Returns: the data of the first element in the queue, or %NULL if the queue
514 g_queue_pop_head (GQueue
*queue
)
516 g_return_val_if_fail (queue
!= NULL
, NULL
);
520 GList
*node
= queue
->head
;
521 gpointer data
= node
->data
;
523 queue
->head
= node
->next
;
525 queue
->head
->prev
= NULL
;
528 g_list_free_1 (node
);
538 * g_queue_pop_head_link:
541 * Removes the first element of the queue.
543 * Returns: the #GList element at the head of the queue, or %NULL if the queue
547 g_queue_pop_head_link (GQueue
*queue
)
549 g_return_val_if_fail (queue
!= NULL
, NULL
);
553 GList
*node
= queue
->head
;
555 queue
->head
= node
->next
;
558 queue
->head
->prev
= NULL
;
572 * g_queue_peek_head_link:
575 * Returns the first link in @queue
577 * Return value: the first link in @queue, or %NULL if @queue is empty
582 g_queue_peek_head_link (GQueue
*queue
)
584 g_return_val_if_fail (queue
!= NULL
, NULL
);
590 * g_queue_peek_tail_link:
593 * Returns the last link @queue.
595 * Return value: the last link in @queue, or %NULL if @queue is empty
600 g_queue_peek_tail_link (GQueue
*queue
)
602 g_return_val_if_fail (queue
!= NULL
, NULL
);
611 * Removes the last element of the queue.
613 * Returns: the data of the last element in the queue, or %NULL if the queue
617 g_queue_pop_tail (GQueue
*queue
)
619 g_return_val_if_fail (queue
!= NULL
, NULL
);
623 GList
*node
= queue
->tail
;
624 gpointer data
= node
->data
;
626 queue
->tail
= node
->prev
;
628 queue
->tail
->next
= NULL
;
632 g_list_free_1 (node
);
643 * @n: the position of the element.
645 * Removes the @n'th element of @queue.
647 * Return value: the element's data, or %NULL if @n is off the end of @queue.
652 g_queue_pop_nth (GQueue
*queue
,
658 g_return_val_if_fail (queue
!= NULL
, NULL
);
660 if (n
>= queue
->length
)
663 nth_link
= g_queue_peek_nth_link (queue
, n
);
664 result
= nth_link
->data
;
666 g_queue_delete_link (queue
, nth_link
);
672 * g_queue_pop_tail_link:
675 * Removes the last element of the queue.
677 * Returns: the #GList element at the tail of the queue, or %NULL if the queue
681 g_queue_pop_tail_link (GQueue
*queue
)
683 g_return_val_if_fail (queue
!= NULL
, NULL
);
687 GList
*node
= queue
->tail
;
689 queue
->tail
= node
->prev
;
692 queue
->tail
->next
= NULL
;
706 * g_queue_pop_nth_link:
708 * @n: the link's position
710 * Removes and returns the link at the given position.
712 * Return value: The @n'th link, or %NULL if @n is off the end of @queue.
717 g_queue_pop_nth_link (GQueue
*queue
,
722 g_return_val_if_fail (queue
!= NULL
, NULL
);
724 if (n
>= queue
->length
)
727 link
= g_queue_peek_nth_link (queue
, n
);
728 g_queue_unlink (queue
, link
);
734 * g_queue_peek_nth_link:
736 * @n: the position of the link
738 * Returns the link at the given position
740 * Return value: The link at the @n'th position, or %NULL if @n is off the
746 g_queue_peek_nth_link (GQueue
*queue
,
752 g_return_val_if_fail (queue
!= NULL
, NULL
);
754 if (n
>= queue
->length
)
757 if (n
> queue
->length
/ 2)
759 n
= queue
->length
- n
- 1;
762 for (i
= 0; i
< n
; ++i
)
768 for (i
= 0; i
< n
; ++i
)
776 * g_queue_link_index:
778 * @link_: A #GList link
780 * Returns the position of @link_ in @queue.
782 * Return value: The position of @link_, or -1 if the link is
788 g_queue_link_index (GQueue
*queue
,
791 g_return_val_if_fail (queue
!= NULL
, -1);
793 return g_list_position (queue
->head
, link_
);
799 * @link_: a #GList link that <emphasis>must</emphasis> be part of @queue
801 * Unlinks @link_ so that it will no longer be part of @queue. The link is
804 * @link_ must be part of @queue,
809 g_queue_unlink (GQueue
*queue
,
812 g_return_if_fail (queue
!= NULL
);
813 g_return_if_fail (link_
!= NULL
);
815 if (link_
== queue
->tail
)
816 queue
->tail
= queue
->tail
->prev
;
818 queue
->head
= g_list_remove_link (queue
->head
, link_
);
823 * g_queue_delete_link:
825 * @link_: a #GList link that <emphasis>must</emphasis> be part of @queue
827 * Removes @link_ from @queue and frees it.
829 * @link_ must be part of @queue.
834 g_queue_delete_link (GQueue
*queue
,
837 g_return_if_fail (queue
!= NULL
);
838 g_return_if_fail (link_
!= NULL
);
840 g_queue_unlink (queue
, link_
);
848 * Returns the first element of the queue.
850 * Returns: the data of the first element in the queue, or %NULL if the queue
854 g_queue_peek_head (GQueue
*queue
)
856 g_return_val_if_fail (queue
!= NULL
, NULL
);
858 return queue
->head
? queue
->head
->data
: NULL
;
865 * Returns the last element of the queue.
867 * Returns: the data of the last element in the queue, or %NULL if the queue
871 g_queue_peek_tail (GQueue
*queue
)
873 g_return_val_if_fail (queue
!= NULL
, NULL
);
875 return queue
->tail
? queue
->tail
->data
: NULL
;
881 * @n: the position of the element.
883 * Returns the @n'th element of @queue.
885 * Return value: The data for the @n'th element of @queue, or %NULL if @n is
886 * off the end of @queue.
891 g_queue_peek_nth (GQueue
*queue
,
896 g_return_val_if_fail (queue
!= NULL
, NULL
);
898 link
= g_queue_peek_nth_link (queue
, n
);
909 * @data: the data to find.
911 * Returns the position of the first element in @queue which contains @data.
913 * Return value: The position of the first element in @queue which contains @data, or -1 if no element in @queue contains @data.
918 g_queue_index (GQueue
*queue
,
921 g_return_val_if_fail (queue
!= NULL
, -1);
923 return g_list_index (queue
->head
, data
);
929 * @data: data to remove.
931 * Removes the first element in @queue that contains @data.
933 * Return value: %TRUE if @data was found and removed from @queue
938 g_queue_remove (GQueue
*queue
,
943 g_return_val_if_fail (queue
!= NULL
, FALSE
);
945 link
= g_list_find (queue
->head
, data
);
948 g_queue_delete_link (queue
, link
);
950 return (link
!= NULL
);
954 * g_queue_remove_all:
956 * @data: data to remove
958 * Remove all elements whose data equals @data from @queue.
960 * Return value: the number of elements removed from @queue
965 g_queue_remove_all (GQueue
*queue
,
971 g_return_val_if_fail (queue
!= NULL
, 0);
973 old_length
= queue
->length
;
978 GList
*next
= list
->next
;
980 if (list
->data
== data
)
981 g_queue_delete_link (queue
, list
);
986 return (old_length
- queue
->length
);
990 * g_queue_insert_before:
992 * @sibling: a #GList link that <emphasis>must</emphasis> be part of @queue
993 * @data: the data to insert
995 * Inserts @data into @queue before @sibling.
997 * @sibling must be part of @queue.
1002 g_queue_insert_before (GQueue
*queue
,
1006 g_return_if_fail (queue
!= NULL
);
1007 g_return_if_fail (sibling
!= NULL
);
1009 queue
->head
= g_list_insert_before (queue
->head
, sibling
, data
);
1014 * g_queue_insert_after:
1016 * @sibling: a #GList link that <emphasis>must</emphasis> be part of @queue
1017 * @data: the data to insert
1019 * Inserts @data into @queue after @sibling
1021 * @sibling must be part of @queue
1026 g_queue_insert_after (GQueue
*queue
,
1030 g_return_if_fail (queue
!= NULL
);
1031 g_return_if_fail (sibling
!= NULL
);
1033 if (sibling
== queue
->tail
)
1034 g_queue_push_tail (queue
, data
);
1036 g_queue_insert_before (queue
, sibling
->next
, data
);
1040 * g_queue_insert_sorted:
1042 * @data: the data to insert
1043 * @func: the #GCompareDataFunc used to compare elements in the queue. It is
1044 * called with two elements of the @queue and @user_data. It should
1045 * return 0 if the elements are equal, a negative value if the first
1046 * element comes before the second, and a positive value if the second
1047 * element comes before the first.
1048 * @user_data: user data passed to @func.
1050 * Inserts @data into @queue using @func to determine the new position.
1055 g_queue_insert_sorted (GQueue
*queue
,
1057 GCompareDataFunc func
,
1062 g_return_if_fail (queue
!= NULL
);
1065 while (list
&& func (list
->data
, data
, user_data
) < 0)
1069 g_queue_insert_before (queue
, list
, data
);
1071 g_queue_push_tail (queue
, data
);