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"
61 * Creates a new #GQueue.
63 * Returns: a new #GQueue.
68 return g_slice_new0 (GQueue);
75 * Frees the memory allocated for the #GQueue. Only call this function if
76 * @queue was created with g_queue_new(). If queue elements contain
77 * dynamically-allocated memory, they should be freed first.
80 g_queue_free (GQueue *queue)
82 g_return_if_fail (queue != NULL);
84 g_list_free (queue->head);
85 g_slice_free (GQueue, queue);
90 * @queue: an uninitialized #GQueue
92 * A statically-allocated #GQueue must be initialized with this function
93 * before it can be used. Alternatively you can initialize it with
94 * #G_QUEUE_INIT. It is not necessary to initialize queues created with
100 g_queue_init (GQueue *queue)
102 g_return_if_fail (queue != NULL);
104 queue->head = queue->tail = NULL;
112 * Removes all the elements in @queue. If queue elements contain
113 * dynamically-allocated memory, they should be freed first.
118 g_queue_clear (GQueue *queue)
120 g_return_if_fail (queue != NULL);
122 g_list_free (queue->head);
123 g_queue_init (queue);
130 * Returns %TRUE if the queue is empty.
132 * Returns: %TRUE if the queue is empty.
135 g_queue_is_empty (GQueue *queue)
137 g_return_val_if_fail (queue != NULL, TRUE);
139 return queue->head == NULL;
143 * g_queue_get_length:
146 * Returns the number of items in @queue.
148 * Return value: The number of items in @queue.
153 g_queue_get_length (GQueue *queue)
155 g_return_val_if_fail (queue != NULL, 0);
157 return queue->length;
164 * Reverses the order of the items in @queue.
169 g_queue_reverse (GQueue *queue)
171 g_return_if_fail (queue != NULL);
173 queue->tail = queue->head;
174 queue->head = g_list_reverse (queue->head);
181 * Copies a @queue. Note that is a shallow copy. If the elements in the
182 * queue consist of pointers to data, the pointers are copied, but the
183 * actual data is not.
185 * Return value: A copy of @queue
190 g_queue_copy (GQueue *queue)
195 g_return_val_if_fail (queue != NULL, NULL);
197 result = g_queue_new ();
199 for (list = queue->head; list != NULL; list = list->next)
200 g_queue_push_tail (result, list->data);
208 * @func: the function to call for each element's data
209 * @user_data: user data to pass to @func
211 * Calls @func for each element in the queue passing @user_data to the
217 g_queue_foreach (GQueue *queue,
223 g_return_if_fail (queue != NULL);
224 g_return_if_fail (func != NULL);
229 GList *next = list->next;
230 func (list->data, user_data);
238 * @data: data to find
240 * Finds the first link in @queue which contains @data.
242 * Return value: The first link in @queue which contains @data.
247 g_queue_find (GQueue *queue,
250 g_return_val_if_fail (queue != NULL, NULL);
252 return g_list_find (queue->head, data);
256 * g_queue_find_custom:
258 * @data: user data passed to @func
259 * @func: a #GCompareFunc to call for each element. It should return 0
260 * when the desired element is found
262 * Finds an element in a #GQueue, using a supplied function to find the
263 * desired element. It iterates over the queue, calling the given function
264 * which should return 0 when the desired element is found. The function
265 * takes two gconstpointer arguments, the #GQueue element's data as the
266 * first argument and the given user data as the second argument.
268 * Return value: The found link, or %NULL if it wasn't found
273 g_queue_find_custom (GQueue *queue,
277 g_return_val_if_fail (queue != NULL, NULL);
278 g_return_val_if_fail (func != NULL, NULL);
280 return g_list_find_custom (queue->head, data, func);
286 * @compare_func: the #GCompareDataFunc used to sort @queue. This function
287 * is passed two elements of the queue and should return 0 if they are
288 * equal, a negative value if the first comes before the second, and
289 * a positive value if the second comes before the first.
290 * @user_data: user data passed to @compare_func
292 * Sorts @queue using @compare_func.
297 g_queue_sort (GQueue *queue,
298 GCompareDataFunc compare_func,
301 g_return_if_fail (queue != NULL);
302 g_return_if_fail (compare_func != NULL);
304 queue->head = g_list_sort_with_data (queue->head, compare_func, user_data);
305 queue->tail = g_list_last (queue->head);
311 * @data: the data for the new element.
313 * Adds a new element at the head of the queue.
316 g_queue_push_head (GQueue *queue,
319 g_return_if_fail (queue != NULL);
321 queue->head = g_list_prepend (queue->head, data);
323 queue->tail = queue->head;
330 * @data: the data for the new element
331 * @n: the position to insert the new element. If @n is negative or
332 * larger than the number of elements in the @queue, the element is
333 * added to the end of the queue.
335 * Inserts a new element into @queue at the given position
340 g_queue_push_nth (GQueue *queue,
344 g_return_if_fail (queue != NULL);
346 if (n < 0 || n >= queue->length)
348 g_queue_push_tail (queue, data);
352 g_queue_insert_before (queue, g_queue_peek_nth_link (queue, n), data);
356 * g_queue_push_head_link:
358 * @link_: a single #GList element, <emphasis>not</emphasis> a list with
359 * more than one element.
361 * Adds a new element at the head of the queue.
364 g_queue_push_head_link (GQueue *queue,
367 g_return_if_fail (queue != NULL);
368 g_return_if_fail (link != NULL);
369 g_return_if_fail (link->prev == NULL);
370 g_return_if_fail (link->next == NULL);
372 link->next = queue->head;
374 queue->head->prev = link;
384 * @data: the data for the new element.
386 * Adds a new element at the tail of the queue.
389 g_queue_push_tail (GQueue *queue,
392 g_return_if_fail (queue != NULL);
394 queue->tail = g_list_append (queue->tail, data);
395 if (queue->tail->next)
396 queue->tail = queue->tail->next;
398 queue->head = queue->tail;
403 * g_queue_push_tail_link:
405 * @link_: a single #GList element, <emphasis>not</emphasis> a list with
406 * more than one element.
408 * Adds a new element at the tail of the queue.
411 g_queue_push_tail_link (GQueue *queue,
414 g_return_if_fail (queue != NULL);
415 g_return_if_fail (link != NULL);
416 g_return_if_fail (link->prev == NULL);
417 g_return_if_fail (link->next == NULL);
419 link->prev = queue->tail;
421 queue->tail->next = link;
429 * g_queue_push_nth_link:
431 * @n: the position to insert the link. If this is negative or larger than
432 * the number of elements in @queue, the link is added to the end of
434 * @link_: the link to add to @queue
436 * Inserts @link into @queue at the given position.
441 g_queue_push_nth_link (GQueue *queue,
448 g_return_if_fail (queue != NULL);
449 g_return_if_fail (link_ != NULL);
451 if (n < 0 || n >= queue->length)
453 g_queue_push_tail_link (queue, link_);
457 g_assert (queue->head);
458 g_assert (queue->tail);
460 next = g_queue_peek_nth_link (queue, n);
470 if (queue->head->prev)
471 queue->head = queue->head->prev;
473 if (queue->tail->next)
474 queue->tail = queue->tail->next;
483 * Removes the first element of the queue.
485 * Returns: the data of the first element in the queue, or %NULL if the queue
489 g_queue_pop_head (GQueue *queue)
491 g_return_val_if_fail (queue != NULL, NULL);
495 GList *node = queue->head;
496 gpointer data = node->data;
498 queue->head = node->next;
500 queue->head->prev = NULL;
503 g_list_free_1 (node);
513 * g_queue_pop_head_link:
516 * Removes the first element of the queue.
518 * Returns: the #GList element at the head of the queue, or %NULL if the queue
522 g_queue_pop_head_link (GQueue *queue)
524 g_return_val_if_fail (queue != NULL, NULL);
528 GList *node = queue->head;
530 queue->head = node->next;
533 queue->head->prev = NULL;
547 * g_queue_peek_head_link:
550 * Returns the first link in @queue
552 * Return value: the first link in @queue, or %NULL if @queue is empty
557 g_queue_peek_head_link (GQueue *queue)
559 g_return_val_if_fail (queue != NULL, NULL);
565 * g_queue_peek_tail_link:
568 * Returns the last link @queue.
570 * Return value: the last link in @queue, or %NULL if @queue is empty
575 g_queue_peek_tail_link (GQueue *queue)
577 g_return_val_if_fail (queue != NULL, NULL);
586 * Removes the last element of the queue.
588 * Returns: the data of the last element in the queue, or %NULL if the queue
592 g_queue_pop_tail (GQueue *queue)
594 g_return_val_if_fail (queue != NULL, NULL);
598 GList *node = queue->tail;
599 gpointer data = node->data;
601 queue->tail = node->prev;
603 queue->tail->next = NULL;
607 g_list_free_1 (node);
618 * @n: the position of the element.
620 * Removes the @n'th element of @queue.
622 * Return value: the element's data, or %NULL if @n is off the end of @queue.
627 g_queue_pop_nth (GQueue *queue,
633 g_return_val_if_fail (queue != NULL, NULL);
635 if (n >= queue->length)
638 nth_link = g_queue_peek_nth_link (queue, n);
639 result = nth_link->data;
641 g_queue_delete_link (queue, nth_link);
647 * g_queue_pop_tail_link:
650 * Removes the last element of the queue.
652 * Returns: the #GList element at the tail of the queue, or %NULL if the queue
656 g_queue_pop_tail_link (GQueue *queue)
658 g_return_val_if_fail (queue != NULL, NULL);
662 GList *node = queue->tail;
664 queue->tail = node->prev;
667 queue->tail->next = NULL;
681 * g_queue_pop_nth_link:
683 * @n: the link's position
685 * Removes and returns the link at the given position.
687 * Return value: The @n'th link, or %NULL if @n is off the end of @queue.
692 g_queue_pop_nth_link (GQueue *queue,
697 g_return_val_if_fail (queue != NULL, NULL);
699 if (n >= queue->length)
702 link = g_queue_peek_nth_link (queue, n);
703 g_queue_unlink (queue, link);
709 * g_queue_peek_nth_link:
711 * @n: the position of the link
713 * Returns the link at the given position
715 * Return value: The link at the @n'th position, or %NULL if @n is off the
721 g_queue_peek_nth_link (GQueue *queue,
727 g_return_val_if_fail (queue != NULL, NULL);
729 if (n >= queue->length)
732 if (n > queue->length / 2)
734 n = queue->length - n - 1;
737 for (i = 0; i < n; ++i)
743 for (i = 0; i < n; ++i)
751 * g_queue_link_index:
753 * @link_: A #GList link
755 * Returns the position of @link_ in @queue.
757 * Return value: The position of @link_, or -1 if the link is
763 g_queue_link_index (GQueue *queue,
766 g_return_val_if_fail (queue != NULL, -1);
768 return g_list_position (queue->head, link_);
774 * @link_: a #GList link that <emphasis>must</emphasis> be part of @queue
776 * Unlinks @link_ so that it will no longer be part of @queue. The link is
779 * @link_ must be part of @queue,
784 g_queue_unlink (GQueue *queue,
787 g_return_if_fail (queue != NULL);
788 g_return_if_fail (link_ != NULL);
790 if (link_ == queue->tail)
791 queue->tail = queue->tail->prev;
793 queue->head = g_list_remove_link (queue->head, link_);
798 * g_queue_delete_link:
800 * @link_: a #GList link that <emphasis>must</emphasis> be part of @queue
802 * Removes @link_ from @queue and frees it.
804 * @link_ must be part of @queue.
809 g_queue_delete_link (GQueue *queue,
812 g_return_if_fail (queue != NULL);
813 g_return_if_fail (link_ != NULL);
815 g_queue_unlink (queue, link_);
823 * Returns the first element of the queue.
825 * Returns: the data of the first element in the queue, or %NULL if the queue
829 g_queue_peek_head (GQueue *queue)
831 g_return_val_if_fail (queue != NULL, NULL);
833 return queue->head ? queue->head->data : NULL;
840 * Returns the last element of the queue.
842 * Returns: the data of the last element in the queue, or %NULL if the queue
846 g_queue_peek_tail (GQueue *queue)
848 g_return_val_if_fail (queue != NULL, NULL);
850 return queue->tail ? queue->tail->data : NULL;
856 * @n: the position of the element.
858 * Returns the @n'th element of @queue.
860 * Return value: The data for the @n'th element of @queue, or %NULL if @n is
861 * off the end of @queue.
866 g_queue_peek_nth (GQueue *queue,
871 g_return_val_if_fail (queue != NULL, NULL);
873 link = g_queue_peek_nth_link (queue, n);
884 * @data: the data to find.
886 * Returns the position of the first element in @queue which contains @data.
888 * Return value: The position of the first element in @queue which contains @data, or -1 if no element in @queue contains @data.
893 g_queue_index (GQueue *queue,
896 g_return_val_if_fail (queue != NULL, -1);
898 return g_list_index (queue->head, data);
904 * @data: data to remove.
906 * Removes the first element in @queue that contains @data.
908 * Return value: %TRUE if @data was found and removed from @queue
913 g_queue_remove (GQueue *queue,
918 g_return_val_if_fail (queue != NULL, FALSE);
920 link = g_list_find (queue->head, data);
923 g_queue_delete_link (queue, link);
925 return (link != NULL);
929 * g_queue_remove_all:
931 * @data: data to remove
933 * Remove all elements whose data equals @data from @queue.
935 * Return value: the number of elements removed from @queue
940 g_queue_remove_all (GQueue *queue,
946 g_return_val_if_fail (queue != NULL, 0);
948 old_length = queue->length;
953 GList *next = list->next;
955 if (list->data == data)
956 g_queue_delete_link (queue, list);
961 return (old_length - queue->length);
965 * g_queue_insert_before:
967 * @sibling: a #GList link that <emphasis>must</emphasis> be part of @queue
968 * @data: the data to insert
970 * Inserts @data into @queue before @sibling.
972 * @sibling must be part of @queue.
977 g_queue_insert_before (GQueue *queue,
981 g_return_if_fail (queue != NULL);
982 g_return_if_fail (sibling != NULL);
984 queue->head = g_list_insert_before (queue->head, sibling, data);
989 * g_queue_insert_after:
991 * @sibling: a #GList link that <emphasis>must</emphasis> be part of @queue
992 * @data: the data to insert
994 * Inserts @data into @queue after @sibling
996 * @sibling must be part of @queue
1001 g_queue_insert_after (GQueue *queue,
1005 g_return_if_fail (queue != NULL);
1006 g_return_if_fail (sibling != NULL);
1008 if (sibling == queue->tail)
1009 g_queue_push_tail (queue, data);
1011 g_queue_insert_before (queue, sibling->next, data);
1015 * g_queue_insert_sorted:
1017 * @data: the data to insert
1018 * @func: the #GCompareDataFunc used to compare elements in the queue. It is
1019 * called with two elements of the @queue and @user_data. It should
1020 * return 0 if the elements are equal, a negative value if the first
1021 * element comes before the second, and a positive value if the second
1022 * element comes before the first.
1023 * @user_data: user data passed to @func.
1025 * Inserts @data into @queue using @func to determine the new position.
1030 g_queue_insert_sorted (GQueue *queue,
1032 GCompareDataFunc func,
1037 g_return_if_fail (queue != NULL);
1040 while (list && func (list->data, data, user_data) < 0)
1044 g_queue_insert_before (queue, list, data);
1046 g_queue_push_tail (queue, data);