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.
35 * Creates a new #GQueue.
37 * Returns: a new #GQueue.
42 return g_slice_new0 (GQueue
);
49 * Frees the memory allocated for the #GQueue. Only call this function if
50 * @queue was created with g_queue_new(). If queue elements contain
51 * dynamically-allocated memory, they should be freed first.
54 g_queue_free (GQueue
*queue
)
56 g_return_if_fail (queue
!= NULL
);
58 g_list_free (queue
->head
);
59 g_slice_free (GQueue
, queue
);
64 * @queue: an uninitialized #GQueue
66 * A statically-allocated #GQueue must be initialized with this function
67 * before it can be used. Alternatively you can initialize it with
68 * #G_QUEUE_INIT. It is not necessary to initialize queues created with
74 g_queue_init (GQueue
*queue
)
76 g_return_if_fail (queue
!= NULL
);
78 queue
->head
= queue
->tail
= NULL
;
86 * Removes all the elements in @queue. If queue elements contain
87 * dynamically-allocated memory, they should be freed first.
92 g_queue_clear (GQueue
*queue
)
94 g_return_if_fail (queue
!= NULL
);
96 g_list_free (queue
->head
);
104 * Returns %TRUE if the queue is empty.
106 * Returns: %TRUE if the queue is empty.
109 g_queue_is_empty (GQueue
*queue
)
111 g_return_val_if_fail (queue
!= NULL
, TRUE
);
113 return queue
->head
== NULL
;
117 * g_queue_get_length:
120 * Returns the number of items in @queue.
122 * Return value: The number of items in @queue.
127 g_queue_get_length (GQueue
*queue
)
129 g_return_val_if_fail (queue
!= NULL
, 0);
131 return queue
->length
;
138 * Reverses the order of the items in @queue.
143 g_queue_reverse (GQueue
*queue
)
145 g_return_if_fail (queue
!= NULL
);
147 queue
->tail
= queue
->head
;
148 queue
->head
= g_list_reverse (queue
->head
);
155 * Copies a @queue. Note that is a shallow copy. If the elements in the
156 * queue consist of pointers to data, the pointers are copied, but the
157 * actual data is not.
159 * Return value: A copy of @queue
164 g_queue_copy (GQueue
*queue
)
169 g_return_val_if_fail (queue
!= NULL
, NULL
);
171 result
= g_queue_new ();
173 for (list
= queue
->head
; list
!= NULL
; list
= list
->next
)
174 g_queue_push_tail (result
, list
->data
);
182 * @func: the function to call for each element's data
183 * @user_data: user data to pass to @func
185 * Calls @func for each element in the queue passing @user_data to the
191 g_queue_foreach (GQueue
*queue
,
197 g_return_if_fail (queue
!= NULL
);
198 g_return_if_fail (func
!= NULL
);
203 GList
*next
= list
->next
;
204 func (list
->data
, user_data
);
212 * @data: data to find
214 * Finds the first link in @queue which contains @data.
216 * Return value: The first link in @queue which contains @data.
221 g_queue_find (GQueue
*queue
,
224 g_return_val_if_fail (queue
!= NULL
, NULL
);
226 return g_list_find (queue
->head
, data
);
230 * g_queue_find_custom:
232 * @data: user data passed to @func
233 * @func: a #GCompareFunc to call for each element. It should return 0
234 * when the desired element is found
236 * Finds an element in a #GQueue, using a supplied function to find the
237 * desired element. It iterates over the queue, calling the given function
238 * which should return 0 when the desired element is found. The function
239 * takes two gconstpointer arguments, the #GQueue element's data as the
240 * first argument and the given user data as the second argument.
242 * Return value: The found link, or %NULL if it wasn't found
247 g_queue_find_custom (GQueue
*queue
,
251 g_return_val_if_fail (queue
!= NULL
, NULL
);
252 g_return_val_if_fail (func
!= NULL
, NULL
);
254 return g_list_find_custom (queue
->head
, data
, func
);
260 * @compare_func: the #GCompareDataFunc used to sort @queue. This function
261 * is passed two elements of the queue and should return 0 if they are
262 * equal, a negative value if the first comes before the second, and
263 * a positive value if the second comes before the first.
264 * @user_data: user data passed to @compare_func
266 * Sorts @queue using @compare_func.
271 g_queue_sort (GQueue
*queue
,
272 GCompareDataFunc compare_func
,
275 g_return_if_fail (queue
!= NULL
);
276 g_return_if_fail (compare_func
!= NULL
);
278 queue
->head
= g_list_sort_with_data (queue
->head
, compare_func
, user_data
);
279 queue
->tail
= g_list_last (queue
->head
);
285 * @data: the data for the new element.
287 * Adds a new element at the head of the queue.
290 g_queue_push_head (GQueue
*queue
,
293 g_return_if_fail (queue
!= NULL
);
295 queue
->head
= g_list_prepend (queue
->head
, data
);
297 queue
->tail
= queue
->head
;
304 * @data: the data for the new element
305 * @n: the position to insert the new element. If @n is negative or
306 * larger than the number of elements in the @queue, the element is
307 * added to the end of the queue.
309 * Inserts a new element into @queue at the given position
314 g_queue_push_nth (GQueue
*queue
,
318 g_return_if_fail (queue
!= NULL
);
320 if (n
< 0 || n
>= queue
->length
)
322 g_queue_push_tail (queue
, data
);
326 g_queue_insert_before (queue
, g_queue_peek_nth_link (queue
, n
), data
);
330 * g_queue_push_head_link:
332 * @link_: a single #GList element, <emphasis>not</emphasis> a list with
333 * more than one element.
335 * Adds a new element at the head of the queue.
338 g_queue_push_head_link (GQueue
*queue
,
341 g_return_if_fail (queue
!= NULL
);
342 g_return_if_fail (link
!= NULL
);
343 g_return_if_fail (link
->prev
== NULL
);
344 g_return_if_fail (link
->next
== NULL
);
346 link
->next
= queue
->head
;
348 queue
->head
->prev
= link
;
358 * @data: the data for the new element.
360 * Adds a new element at the tail of the queue.
363 g_queue_push_tail (GQueue
*queue
,
366 g_return_if_fail (queue
!= NULL
);
368 queue
->tail
= g_list_append (queue
->tail
, data
);
369 if (queue
->tail
->next
)
370 queue
->tail
= queue
->tail
->next
;
372 queue
->head
= queue
->tail
;
377 * g_queue_push_tail_link:
379 * @link_: a single #GList element, <emphasis>not</emphasis> a list with
380 * more than one element.
382 * Adds a new element at the tail of the queue.
385 g_queue_push_tail_link (GQueue
*queue
,
388 g_return_if_fail (queue
!= NULL
);
389 g_return_if_fail (link
!= NULL
);
390 g_return_if_fail (link
->prev
== NULL
);
391 g_return_if_fail (link
->next
== NULL
);
393 link
->prev
= queue
->tail
;
395 queue
->tail
->next
= link
;
403 * g_queue_push_nth_link:
405 * @n: the position to insert the link. If this is negative or larger than
406 * the number of elements in @queue, the link is added to the end of
408 * @link_: the link to add to @queue
410 * Inserts @link into @queue at the given position.
415 g_queue_push_nth_link (GQueue
*queue
,
422 g_return_if_fail (queue
!= NULL
);
423 g_return_if_fail (link_
!= NULL
);
425 if (n
< 0 || n
>= queue
->length
)
427 g_queue_push_tail_link (queue
, link_
);
431 g_assert (queue
->head
);
432 g_assert (queue
->tail
);
434 next
= g_queue_peek_nth_link (queue
, n
);
444 if (queue
->head
->prev
)
445 queue
->head
= queue
->head
->prev
;
447 if (queue
->tail
->next
)
448 queue
->tail
= queue
->tail
->next
;
457 * Removes the first element of the queue.
459 * Returns: the data of the first element in the queue, or %NULL if the queue
463 g_queue_pop_head (GQueue
*queue
)
465 g_return_val_if_fail (queue
!= NULL
, NULL
);
469 GList
*node
= queue
->head
;
470 gpointer data
= node
->data
;
472 queue
->head
= node
->next
;
474 queue
->head
->prev
= NULL
;
477 g_list_free_1 (node
);
487 * g_queue_pop_head_link:
490 * Removes the first element of the queue.
492 * Returns: the #GList element at the head of the queue, or %NULL if the queue
496 g_queue_pop_head_link (GQueue
*queue
)
498 g_return_val_if_fail (queue
!= NULL
, NULL
);
502 GList
*node
= queue
->head
;
504 queue
->head
= node
->next
;
507 queue
->head
->prev
= NULL
;
521 * g_queue_peek_head_link:
524 * Returns the first link in @queue
526 * Return value: the first link in @queue, or %NULL if @queue is empty
531 g_queue_peek_head_link (GQueue
*queue
)
533 g_return_val_if_fail (queue
!= NULL
, NULL
);
539 * g_queue_peek_tail_link:
542 * Returns the last link @queue.
544 * Return value: the last link in @queue, or %NULL if @queue is empty
549 g_queue_peek_tail_link (GQueue
*queue
)
551 g_return_val_if_fail (queue
!= NULL
, NULL
);
560 * Removes the last element of the queue.
562 * Returns: the data of the last element in the queue, or %NULL if the queue
566 g_queue_pop_tail (GQueue
*queue
)
568 g_return_val_if_fail (queue
!= NULL
, NULL
);
572 GList
*node
= queue
->tail
;
573 gpointer data
= node
->data
;
575 queue
->tail
= node
->prev
;
577 queue
->tail
->next
= NULL
;
581 g_list_free_1 (node
);
592 * @n: the position of the element.
594 * Removes the @n'th element of @queue.
596 * Return value: the element's data, or %NULL if @n is off the end of @queue.
601 g_queue_pop_nth (GQueue
*queue
,
607 g_return_val_if_fail (queue
!= NULL
, NULL
);
609 if (n
>= queue
->length
)
612 nth_link
= g_queue_peek_nth_link (queue
, n
);
613 result
= nth_link
->data
;
615 g_queue_delete_link (queue
, nth_link
);
621 * g_queue_pop_tail_link:
624 * Removes the last element of the queue.
626 * Returns: the #GList element at the tail of the queue, or %NULL if the queue
630 g_queue_pop_tail_link (GQueue
*queue
)
632 g_return_val_if_fail (queue
!= NULL
, NULL
);
636 GList
*node
= queue
->tail
;
638 queue
->tail
= node
->prev
;
641 queue
->tail
->next
= NULL
;
655 * g_queue_pop_nth_link:
657 * @n: the link's position
659 * Removes and returns the link at the given position.
661 * Return value: The @n'th link, or %NULL if @n is off the end of @queue.
666 g_queue_pop_nth_link (GQueue
*queue
,
671 g_return_val_if_fail (queue
!= NULL
, NULL
);
673 if (n
>= queue
->length
)
676 link
= g_queue_peek_nth_link (queue
, n
);
677 g_queue_unlink (queue
, link
);
683 * g_queue_peek_nth_link:
685 * @n: the position of the link
687 * Returns the link at the given position
689 * Return value: The link at the @n'th position, or %NULL if @n is off the
695 g_queue_peek_nth_link (GQueue
*queue
,
701 g_return_val_if_fail (queue
!= NULL
, NULL
);
703 if (n
>= queue
->length
)
706 if (n
> queue
->length
/ 2)
708 n
= queue
->length
- n
- 1;
711 for (i
= 0; i
< n
; ++i
)
717 for (i
= 0; i
< n
; ++i
)
725 * g_queue_link_index:
727 * @link_: A #GList link
729 * Returns the position of @link_ in @queue.
731 * Return value: The position of @link_, or -1 if the link is
737 g_queue_link_index (GQueue
*queue
,
740 g_return_val_if_fail (queue
!= NULL
, -1);
742 return g_list_position (queue
->head
, link_
);
748 * @link_: a #GList link that <emphasis>must</emphasis> be part of @queue
750 * Unlinks @link_ so that it will no longer be part of @queue. The link is
753 * @link_ must be part of @queue,
758 g_queue_unlink (GQueue
*queue
,
761 g_return_if_fail (queue
!= NULL
);
762 g_return_if_fail (link_
!= NULL
);
764 if (link_
== queue
->tail
)
765 queue
->tail
= queue
->tail
->prev
;
767 queue
->head
= g_list_remove_link (queue
->head
, link_
);
772 * g_queue_delete_link:
774 * @link_: a #GList link that <emphasis>must</emphasis> be part of @queue
776 * Removes @link_ from @queue and frees it.
778 * @link_ must be part of @queue.
783 g_queue_delete_link (GQueue
*queue
,
786 g_return_if_fail (queue
!= NULL
);
787 g_return_if_fail (link_
!= NULL
);
789 g_queue_unlink (queue
, link_
);
797 * Returns the first element of the queue.
799 * Returns: the data of the first element in the queue, or %NULL if the queue
803 g_queue_peek_head (GQueue
*queue
)
805 g_return_val_if_fail (queue
!= NULL
, NULL
);
807 return queue
->head
? queue
->head
->data
: NULL
;
814 * Returns the last element of the queue.
816 * Returns: the data of the last element in the queue, or %NULL if the queue
820 g_queue_peek_tail (GQueue
*queue
)
822 g_return_val_if_fail (queue
!= NULL
, NULL
);
824 return queue
->tail
? queue
->tail
->data
: NULL
;
830 * @n: the position of the element.
832 * Returns the @n'th element of @queue.
834 * Return value: The data for the @n'th element of @queue, or %NULL if @n is
835 * off the end of @queue.
840 g_queue_peek_nth (GQueue
*queue
,
845 g_return_val_if_fail (queue
!= NULL
, NULL
);
847 link
= g_queue_peek_nth_link (queue
, n
);
858 * @data: the data to find.
860 * Returns the position of the first element in @queue which contains @data.
862 * Return value: The position of the first element in @queue which contains @data, or -1 if no element in @queue contains @data.
867 g_queue_index (GQueue
*queue
,
870 g_return_val_if_fail (queue
!= NULL
, -1);
872 return g_list_index (queue
->head
, data
);
878 * @data: data to remove.
880 * Removes the first element in @queue that contains @data.
885 g_queue_remove (GQueue
*queue
,
890 g_return_if_fail (queue
!= NULL
);
892 link
= g_list_find (queue
->head
, data
);
895 g_queue_delete_link (queue
, link
);
899 * g_queue_remove_all:
901 * @data: data to remove
903 * Remove all elemeents in @queue which contains @data.
908 g_queue_remove_all (GQueue
*queue
,
913 g_return_if_fail (queue
!= NULL
);
918 GList
*next
= list
->next
;
920 if (list
->data
== data
)
921 g_queue_delete_link (queue
, list
);
928 * g_queue_insert_before:
930 * @sibling: a #GList link that <emphasis>must</emphasis> be part of @queue
931 * @data: the data to insert
933 * Inserts @data into @queue before @sibling.
935 * @sibling must be part of @queue.
940 g_queue_insert_before (GQueue
*queue
,
944 g_return_if_fail (queue
!= NULL
);
945 g_return_if_fail (sibling
!= NULL
);
947 queue
->head
= g_list_insert_before (queue
->head
, sibling
, data
);
952 * g_queue_insert_after:
954 * @sibling: a #GList link that <emphasis>must</emphasis> be part of @queue
955 * @data: the data to insert
957 * Inserts @data into @queue after @sibling
959 * @sibling must be part of @queue
964 g_queue_insert_after (GQueue
*queue
,
968 g_return_if_fail (queue
!= NULL
);
969 g_return_if_fail (sibling
!= NULL
);
971 if (sibling
== queue
->tail
)
972 g_queue_push_tail (queue
, data
);
974 g_queue_insert_before (queue
, sibling
->next
, data
);
978 * g_queue_insert_sorted:
980 * @data: the data to insert
981 * @func: the #GCompareDataFunc used to compare elements in the queue. It is
982 * called with two elements of the @queue and @user_data. It should
983 * return 0 if the elements are equal, a negative value if the first
984 * element comes before the second, and a positive value if the second
985 * element comes before the first.
986 * @user_data: user data passed to @func.
988 * Inserts @data into @queue using @func to determine the new position.
993 g_queue_insert_sorted (GQueue
*queue
,
995 GCompareDataFunc func
,
1000 g_return_if_fail (queue
!= NULL
);
1003 while (list
&& func (list
->data
, data
, user_data
) < 0)
1007 g_queue_insert_before (queue
, list
, data
);
1009 g_queue_push_tail (queue
, data
);
1012 #define __G_QUEUE_C__
1013 #include "galiasdef.c"