Re: New GQueue API
- From: Soeren Sandmann <sandmann daimi au dk>
- To: Owen Taylor <otaylor redhat com>
- Cc: gtk-devel-list gnome org
- Subject: Re: New GQueue API
- Date: 06 Oct 2003 15:38:15 +0200
Owen Taylor <otaylor redhat com> writes:
> General:
>
> - You can and should wrap lines in parameter descriptions
> in inline doc comments.
>
> - I think it might be nice if all the functions that take
> an index 'n' were O(1) for n == queue->length - 1.
>
> (In theory, you could make them walk the list backwards
> for any n > queue->length / 2. That might be overcomplex,
> though it would be easy enough to do if you wrote
> everything in terms of a g_queue_nth_link())
Here is a new patch that takes care of those and your other comments.
The test code in the new patch is also more aggressive about testing
the "nth" functions at their borders (head and tail).
Søren
? 88329.patch
? foo.patch
? gfreelist.c
? gfreelist.h
? glib-diff
? newapi
? patches
? queue.patch
? glib/gfreelist.c
? glib/gfreelist.h
? glib/memdiff
? glib/qd
? glib/strtokenize.patch
? gobject/core.469
? gobject/glib-signal.patch
? gobject/paramspec.patch
? gobject/signal.patch
? gobject/testifaceinit
? gobject/testoverride
? tests/core.10743
Index: docs/reference/glib/tmpl/unicode.sgml
===================================================================
RCS file: /cvs/gnome/glib/docs/reference/glib/tmpl/unicode.sgml,v
retrieving revision 1.23
diff -u -r1.23 unicode.sgml
--- docs/reference/glib/tmpl/unicode.sgml 12 Sep 2003 00:17:02 -0000 1.23
+++ docs/reference/glib/tmpl/unicode.sgml 6 Oct 2003 13:32:48 -0000
@@ -335,6 +335,16 @@
@Returns:
+<!-- ##### FUNCTION g_unichar_get_mirror_char ##### -->
+<para>
+
+</para>
+
+ ch:
+ mirrored_ch:
+ Returns:
+
+
<!-- ##### MACRO g_utf8_next_char ##### -->
<para>
Skips to the next character in a UTF-8 string. The string must be
Index: glib/gqueue.c
===================================================================
RCS file: /cvs/gnome/glib/glib/gqueue.c,v
retrieving revision 1.12
diff -u -r1.12 gqueue.c
--- glib/gqueue.c 4 Dec 2002 01:27:43 -0000 1.12
+++ glib/gqueue.c 6 Oct 2003 13:33:15 -0000
@@ -90,6 +90,188 @@
}
/**
+ * g_queue_is_empty:
+ * @queue: a #GQueue.
+ *
+ * Returns %TRUE if the queue is empty.
+ *
+ * Returns: %TRUE if the queue is empty.
+ **/
+gboolean
+g_queue_is_empty (GQueue *queue)
+{
+ g_return_val_if_fail (queue != NULL, TRUE);
+
+ return queue->head == NULL;
+}
+
+/**
+ * g_queue_get_length:
+ * @queue: a #GQueue
+ *
+ * Returns the number of items in @queue.
+ *
+ * Return value: The number of items in @queue.
+ *
+ * Since: 2.4
+ **/
+guint
+g_queue_get_length (GQueue *queue)
+{
+ g_return_val_if_fail (queue != NULL, 0);
+
+ return queue->length;
+}
+
+/**
+ * g_queue_reverse:
+ * @queue: a #GQueue
+ *
+ * Reverses the order of the items in @queue.
+ *
+ * Since: 2.4
+ **/
+void
+g_queue_reverse (GQueue *queue)
+{
+ g_return_if_fail (queue != NULL);
+
+ queue->tail = queue->head;
+ queue->head = g_list_reverse (queue->head);
+}
+
+/**
+ * g_queue_copy:
+ * @queue: a #GQueue
+ *
+ * Copy a @queue. Note that is a shallow copy. If the elements in the
+ * queue consist of pointers to data, the pointers are copied, but the
+ * actual data is not.
+ *
+ * Return value: A copy of @queue
+ *
+ * Since: 2.4
+ **/
+GQueue *
+g_queue_copy (GQueue *queue)
+{
+ GQueue *result;
+ GList *list;
+
+ g_return_val_if_fail (queue != NULL, NULL);
+
+ result = g_queue_new ();
+
+ for (list = queue->head; list != NULL; list = list->next)
+ g_queue_push_tail (result, list->data);
+
+ return result;
+}
+
+/**
+ * g_queue_foreach:
+ * @queue: a #GQueue
+ * @func: the function to call for each element's data
+ * @user_data: user data to pass to @func
+ *
+ * Calls @func for each element in the queue passing @user_data to the
+ * function.
+ *
+ * Since: 2.4
+ **/
+void
+g_queue_foreach (GQueue *queue,
+ GFunc func,
+ gpointer user_data)
+{
+ GList *list;
+
+ g_return_if_fail (queue != NULL);
+ g_return_if_fail (func != NULL);
+
+ list = queue->head;
+ while (list)
+ {
+ GList *next = list->next;
+ func (list->data, user_data);
+ list = next;
+ }
+}
+
+/**
+ * g_queue_find:
+ * @queue: a #GQueue
+ * @data: data to find
+ *
+ * Finds the first link in @queue which contains @data.
+ *
+ * Return value: The first link in @queue which contains @data.
+ *
+ * Since: 2.4
+ **/
+GList *
+g_queue_find (GQueue *queue,
+ gconstpointer data)
+{
+ g_return_val_if_fail (queue != NULL, NULL);
+
+ return g_list_find (queue->head, data);
+}
+
+/**
+ * g_queue_find_custom:
+ * @queue: a #GQueue
+ * @data: user data passed to @func
+ * @func: a #GCompareFunc to call for each element. It should return 0
+ * when the desired element is found
+ *
+ * Finds an element in a #GQueue, using a supplied function to find the
+ * desired element. It iterates over the queue, calling the given function
+ * which should return 0 when the desired element is found. The function
+ * takes two gconstpointer arguments, the #GQueue element's data and the
+ * given user data.
+ *
+ * Return value: The found link, or %NULL if it wasn't found
+ *
+ * Since: 2.4
+ **/
+GList *
+g_queue_find_custom (GQueue *queue,
+ gconstpointer data,
+ GCompareFunc func)
+{
+ g_return_val_if_fail (queue != NULL, NULL);
+ g_return_val_if_fail (func != NULL, NULL);
+
+ return g_list_find_custom (queue->head, data, func);
+}
+
+/**
+ * g_queue_sort:
+ * @queue: a #GQueue
+ * @compare_func: the #GCompareDataFunc used to sort @queue. This function
+ * is passed two elements of the queue and should return 0 if they are
+ * equal, a negative value if the first comes before the second, and
+ * a positive value if the second comes before the first.
+ * @user_data: user data passed to @compare_func
+ *
+ * Sorts @queue using @compare_func.
+ *
+ * Since: 2.4
+ **/
+void
+g_queue_sort (GQueue *queue,
+ GCompareDataFunc compare_func,
+ gpointer user_data)
+{
+ g_return_if_fail (queue != NULL);
+ g_return_if_fail (compare_func != NULL);
+
+ queue->head = g_list_sort_with_data (queue->head, compare_func, user_data);
+ queue->tail = g_list_last (queue->head);
+}
+
+/**
* g_queue_push_head:
* @queue: a #GQueue.
* @data: the data for the new element.
@@ -109,10 +291,38 @@
}
/**
+ * g_queue_push_nth:
+ * @queue: a #GQueue
+ * @data: the data for the new element
+ * @n: the position to insert the new element. If @n is negative or
+ * larger than the number of elements in the @queue, the element is
+ * added to the end of the queue.
+ *
+ * Insert a new element into @queue at the given position
+ *
+ * Since: 2.4
+ **/
+void
+g_queue_push_nth (GQueue *queue,
+ gpointer data,
+ gint n)
+{
+ g_return_if_fail (queue != NULL);
+
+ if (n < 0 || n >= queue->length)
+ {
+ g_queue_push_tail (queue, data);
+ return;
+ }
+
+ g_queue_insert_before (queue, g_queue_peek_nth_link (queue, n), data);
+}
+
+/**
* g_queue_push_head_link:
* @queue: a #GQueue.
* @link_: a single #GList element, <emphasis>not</emphasis> a list with
- * more than one element.
+ * more than one element.
*
* Adds a new element at the head of the queue.
**/
@@ -182,6 +392,57 @@
}
/**
+ * g_queue_push_nth_link:
+ * @queue: a #GQueue
+ * @n: the position to insert the link. If this is negative or larger than
+ * the number of elements in @queue, the link is added to the end of
+ * @queue.
+ * @link_: the link to add to @queue
+ *
+ * Insert @link into @queue at the given position.
+ *
+ * Since: 2.4
+ **/
+void
+g_queue_push_nth_link (GQueue *queue,
+ gint n,
+ GList *link_)
+{
+ GList *next;
+ GList *prev;
+
+ g_return_if_fail (queue != NULL);
+ g_return_if_fail (link_ != NULL);
+
+ if (n < 0 || n >= queue->length)
+ {
+ g_queue_push_tail_link (queue, link_);
+ return;
+ }
+
+ g_assert (queue->head);
+ g_assert (queue->tail);
+
+ next = g_queue_peek_nth_link (queue, n);
+ prev = next->prev;
+
+ if (prev)
+ prev->next = link_;
+ next->prev = link_;
+
+ link_->next = next;
+ link_->prev = prev;
+
+ if (queue->head->prev)
+ queue->head = queue->head->prev;
+
+ if (queue->tail->next)
+ queue->tail = queue->tail->next;
+
+ queue->length++;
+}
+
+/**
* g_queue_pop_head:
* @queue: a #GQueue.
*
@@ -249,6 +510,42 @@
}
/**
+ * g_queue_peek_head_link:
+ * @queue: a #GQueue
+ *
+ * Returns the first link in @queue
+ *
+ * Return value: the first link in @queue, or %NULL if @queue is empty
+ *
+ * Since: 2.4
+ **/
+GList*
+g_queue_peek_head_link (GQueue *queue)
+{
+ g_return_val_if_fail (queue != NULL, NULL);
+
+ return queue->head;
+}
+
+/**
+ * g_queue_peek_tail_link:
+ * @queue: a #GQueue
+ *
+ * Returns the last link @queue.
+ *
+ * Return value: the last link in @queue, or %NULL if @queue is empty
+ *
+ * Since: 2.4
+ **/
+GList*
+g_queue_peek_tail_link (GQueue *queue)
+{
+ g_return_val_if_fail (queue != NULL, NULL);
+
+ return queue->tail;
+}
+
+/**
* g_queue_pop_tail:
* @queue: a #GQueue.
*
@@ -282,6 +579,37 @@
}
/**
+ * g_queue_pop_nth:
+ * @queue: a #GQueue
+ * @n: the position of the element.
+ *
+ * Removes the @n'th element of @queue.
+ *
+ * Return value: the element's data, or %NULL if @n is off the end of @queue.
+ *
+ * Since: 2.4
+ **/
+gpointer
+g_queue_pop_nth (GQueue *queue,
+ guint n)
+{
+ GList *nth_link;
+ gpointer result;
+
+ g_return_val_if_fail (queue != NULL, NULL);
+
+ if (n >= queue->length)
+ return NULL;
+
+ nth_link = g_queue_peek_nth_link (queue, n);
+ result = nth_link->data;
+
+ g_queue_delete_link (queue, nth_link);
+
+ return result;
+}
+
+/**
* g_queue_pop_tail_link:
* @queue: a #GQueue.
*
@@ -316,19 +644,144 @@
}
/**
- * g_queue_is_empty:
- * @queue: a #GQueue.
- *
- * Returns %TRUE if the queue is empty.
- *
- * Returns: %TRUE if the queue is empty.
+ * g_queue_pop_nth_link:
+ * @queue: a #GQueue
+ * @n: the link's position
+ *
+ * Removes and returns the link at the given position.
+ *
+ * Return value: The @n'th link, or %NULL if @n is off the end of @queue.
+ *
+ * Since: 2.4
**/
-gboolean
-g_queue_is_empty (GQueue *queue)
+GList*
+g_queue_pop_nth_link (GQueue *queue,
+ guint n)
{
- g_return_val_if_fail (queue != NULL, TRUE);
+ GList *link;
+
+ g_return_val_if_fail (queue != NULL, NULL);
- return queue->head == NULL;
+ if (n > queue->length)
+ return NULL;
+
+ link = g_queue_peek_nth_link (queue, n);
+ g_queue_unlink (queue, link);
+
+ return link;
+}
+
+/**
+ * g_queue_peek_nth_link:
+ * @queue: a #GQueue
+ * @n: the position of the link
+ *
+ * Returns the link at the given position
+ *
+ * Return value: The link at the @n'th position, or %NULL if @n is off the
+ * end of the list
+ *
+ * Since: 2.4
+ **/
+GList *
+g_queue_peek_nth_link (GQueue *queue,
+ guint n)
+{
+ GList *link;
+ gint i;
+
+ g_return_val_if_fail (queue != NULL, NULL);
+
+ if (n >= queue->length)
+ return NULL;
+
+ if (n > queue->length / 2)
+ {
+ n = queue->length - n - 1;
+
+ link = queue->tail;
+ for (i = 0; i < n; ++i)
+ link = link->prev;
+ }
+ else
+ {
+ link = queue->head;
+ for (i = 0; i < n; ++i)
+ link = link->next;
+ }
+
+ return link;
+}
+
+/**
+ * g_queue_link_index:
+ * @queue: a #Gqueue
+ * @link_: A #GList link
+ *
+ * Returns the position of @link_ in @queue.
+ *
+ * Return value: The position of @link_, or -1 if the link is
+ * not part of @queue
+ *
+ * Since: 2.4
+ **/
+gint
+g_queue_link_index (GQueue *queue,
+ GList *link_)
+{
+ g_return_val_if_fail (queue != NULL, 0);
+
+ return g_list_position (queue->head, link_);
+}
+
+/**
+ * g_queue_unlink
+ * @queue: a #GQueue
+ * @link_: a #GList link that <emphasis>must</emphasis> be part of @queue
+ *
+ * Unlinks @link_ so that it will no longer be part of @queue. The link is
+ * not freed.
+ *
+ * @link_ must be part of @queue,
+ *
+ * Since: 2.4
+ **/
+void
+g_queue_unlink (GQueue *queue,
+ GList *link_)
+{
+ g_return_if_fail (queue != NULL);
+ g_return_if_fail (link_ != NULL);
+
+ if (link_ == queue->tail)
+ queue->tail = queue->tail->prev;
+
+ queue->head = g_list_remove_link (queue->head, link_);
+ queue->length--;
+}
+
+/**
+ * g_queue_delete_link:
+ * @queue: a #GQueue
+ * @link_: a #GList link that <emphasis>must</emphasis> be part of @queue
+ *
+ * Removes @link_ from @queue and frees it.
+ *
+ * If @link_ is not part of @queue, the result of calling this function
+ * is undefined. Unlike most other functions in GLib this will not produce
+ * any warnings or assertion failures.
+ *
+ * Since: 2.4
+ **/
+void
+g_queue_delete_link (GQueue *queue,
+ GList *link_)
+{
+ g_return_if_fail (queue != NULL);
+ g_return_if_fail (link_ != NULL);
+
+ g_queue_unlink (queue, link_);
+ g_list_free (link_);
}
/**
@@ -363,4 +816,193 @@
g_return_val_if_fail (queue != NULL, NULL);
return queue->tail ? queue->tail->data : NULL;
+}
+
+/**
+ * g_queue_peek_nth:
+ * @queue: a #GQueue
+ * @n: the position of the element.
+ *
+ * Returns the @n'th element of @queue.
+ *
+ * Return value: The data for the @n'th element of @queue, or %NULL if @n is
+ * off the end of @queue.
+ *
+ * Since: 2.4
+ **/
+gpointer
+g_queue_peek_nth (GQueue *queue,
+ guint n)
+{
+ GList *link;
+
+ g_return_val_if_fail (queue != NULL, NULL);
+
+ link = g_queue_peek_nth_link (queue, n);
+
+ if (link)
+ return link->data;
+
+ return NULL;
+}
+
+/**
+ * g_queue_index:
+ * @queue: a #GQueue
+ * @data: the data to find.
+ *
+ * Returns the position of the first element in @queue which contains @data.
+ *
+ * Return value: The position of the first element in @queue which contains @data, or -1 if no element in @queue contains @data.
+ *
+ * Since: 2.4
+ **/
+gint
+g_queue_index (GQueue *queue,
+ gconstpointer data)
+{
+ g_return_val_if_fail (queue != NULL, -1);
+
+ return g_list_index (queue->head, data);
+}
+
+/**
+ * g_queue_remove:
+ * @queue: a #GQueue
+ * @data: data to remove.
+ *
+ * Removes the first element in @queue that contains @data.
+ *
+ * Since: 2.4
+ **/
+void
+g_queue_remove (GQueue *queue,
+ gconstpointer data)
+{
+ GList *link;
+
+ g_return_if_fail (queue != NULL);
+
+ link = g_list_find (queue->head, data);
+
+ if (link)
+ g_queue_delete_link (queue, link);
+}
+
+/**
+ * g_queue_remove_all:
+ * @queue: a #GQueue
+ * @data: data to remove
+ *
+ * Remove all elemeents in @queue which contains @data.
+ *
+ * Since: 2.4
+ **/
+void
+g_queue_remove_all (GQueue *queue,
+ gconstpointer data)
+{
+ GList *list;
+
+ g_return_if_fail (queue != NULL);
+
+ list = queue->head;
+ while (list)
+ {
+ GList *next = list->next;
+
+ if (list->data == data)
+ g_queue_delete_link (queue, list);
+
+ list = next;
+ }
+}
+
+/**
+ * g_queue_insert_before:
+ * @queue: a #GQueue
+ * @sibling: a #GList link that <emphasis>must</emphasis> be part of @queue
+ * @data: the data to insert
+ *
+ * Inserts @data into @queue before @sibling.
+ *
+ * If @sibling is not part of @queue, the result of calling this function
+ * is undefined. Unlike most other functions in GLib this will not produce
+ * any warnings or assertion failures.
+ *
+ * Since: 2.4
+ **/
+void
+g_queue_insert_before (GQueue *queue,
+ GList *sibling,
+ gpointer data)
+{
+ g_return_if_fail (queue != NULL);
+ g_return_if_fail (sibling != NULL);
+
+ queue->head = g_list_insert_before (queue->head, sibling, data);
+ queue->length++;
+}
+
+/**
+ * g_queue_insert_after:
+ * @queue: a #GQueue
+ * @sibling: a #GList link that <emphasis>must</emphasis> be part of @queue
+ * @data: the data to insert
+ *
+ * Inserts @data into @queue after @sibling
+ *
+ * If @sibling is not part of @queue, the result of calling this function
+ * is undefined. Unlike most other functions in GLib this will not produce
+ * any warnings or assertion failures.
+ *
+ * Since: 2.4
+ **/
+void
+g_queue_insert_after (GQueue *queue,
+ GList *sibling,
+ gpointer data)
+{
+ g_return_if_fail (queue != NULL);
+ g_return_if_fail (sibling != NULL);
+
+ if (sibling == queue->tail)
+ g_queue_push_tail (queue, data);
+ else
+ g_queue_insert_before (queue, sibling->next, data);
+}
+
+/**
+ * g_queue_insert_sorted:
+ * @queue: a #GQueue
+ * @data: the data to insert
+ * @func: the #GCompareDataFunc used to compare elements in the queue. It is
+ * called with two elements of the @queue and @user_data. It should
+ * return 0 if the elements are equal, a negative value if the first
+ * element comes before the second, and a positive value if the second
+ * element comes after the first.
+ * @user_data: user data passed to @func.
+ *
+ * Inserts @data into @queue using @func to determine the new position.
+ *
+ * Since: 2.4
+ **/
+void
+g_queue_insert_sorted (GQueue *queue,
+ gpointer data,
+ GCompareDataFunc func,
+ gpointer user_data)
+{
+ GList *list;
+
+ g_return_if_fail (queue != NULL);
+
+ list = queue->head;
+ while (list && func (list->data, data, user_data) < 0)
+ list = list->next;
+
+ if (list)
+ g_queue_insert_before (queue, list, data);
+ else
+ g_queue_push_tail (queue, data);
}
Index: glib/gqueue.h
===================================================================
RCS file: /cvs/gnome/glib/glib/gqueue.h,v
retrieving revision 1.3
diff -u -r1.3 gqueue.h
--- glib/gqueue.h 8 Nov 2002 18:47:54 -0000 1.3
+++ glib/gqueue.h 6 Oct 2003 13:33:15 -0000
@@ -43,22 +43,76 @@
/* Queues
*/
GQueue* g_queue_new (void);
-void g_queue_free (GQueue *queue);
-void g_queue_push_head (GQueue *queue,
- gpointer data);
-void g_queue_push_tail (GQueue *queue,
- gpointer data);
-gpointer g_queue_pop_head (GQueue *queue);
-gpointer g_queue_pop_tail (GQueue *queue);
-gboolean g_queue_is_empty (GQueue *queue);
-gpointer g_queue_peek_head (GQueue *queue);
-gpointer g_queue_peek_tail (GQueue *queue);
-void g_queue_push_head_link (GQueue *queue,
- GList *link_);
-void g_queue_push_tail_link (GQueue *queue,
- GList *link_);
-GList* g_queue_pop_head_link (GQueue *queue);
-GList* g_queue_pop_tail_link (GQueue *queue);
+void g_queue_free (GQueue *queue);
+gboolean g_queue_is_empty (GQueue *queue);
+guint g_queue_get_length (GQueue *queue);
+void g_queue_reverse (GQueue *queue);
+GQueue * g_queue_copy (GQueue *queue);
+void g_queue_foreach (GQueue *queue,
+ GFunc func,
+ gpointer user_data);
+GList * g_queue_find (GQueue *queue,
+ gconstpointer data);
+GList * g_queue_find_custom (GQueue *queue,
+ gconstpointer data,
+ GCompareFunc func);
+void g_queue_sort (GQueue *queue,
+ GCompareDataFunc compare_func,
+ gpointer user_data);
+
+void g_queue_push_head (GQueue *queue,
+ gpointer data);
+void g_queue_push_tail (GQueue *queue,
+ gpointer data);
+void g_queue_push_nth (GQueue *queue,
+ gpointer data,
+ gint n);
+gpointer g_queue_pop_head (GQueue *queue);
+gpointer g_queue_pop_tail (GQueue *queue);
+gpointer g_queue_pop_nth (GQueue *queue,
+ guint n);
+gpointer g_queue_peek_head (GQueue *queue);
+gpointer g_queue_peek_tail (GQueue *queue);
+gpointer g_queue_peek_nth (GQueue *queue,
+ guint n);
+gint g_queue_index (GQueue *queue,
+ gconstpointer data);
+void g_queue_remove (GQueue *queue,
+ gconstpointer data);
+void g_queue_remove_all (GQueue *queue,
+ gconstpointer data);
+void g_queue_insert_before (GQueue *queue,
+ GList *sibling,
+ gpointer data);
+void g_queue_insert_after (GQueue *queue,
+ GList *sibling,
+ gpointer data);
+void g_queue_insert_sorted (GQueue *queue,
+ gpointer data,
+ GCompareDataFunc func,
+ gpointer user_data);
+
+void g_queue_push_head_link (GQueue *queue,
+ GList *link_);
+void g_queue_push_tail_link (GQueue *queue,
+ GList *link_);
+void g_queue_push_nth_link (GQueue *queue,
+ gint n,
+ GList *link_);
+GList* g_queue_pop_head_link (GQueue *queue);
+GList* g_queue_pop_tail_link (GQueue *queue);
+GList* g_queue_pop_nth_link (GQueue *queue,
+ guint n);
+GList* g_queue_peek_head_link (GQueue *queue);
+GList* g_queue_peek_tail_link (GQueue *queue);
+GList* g_queue_peek_nth_link (GQueue *queue,
+ guint n);
+gint g_queue_link_index (GQueue *queue,
+ GList *link_);
+void g_queue_unlink (GQueue *queue,
+ GList *link_);
+void g_queue_delete_link (GQueue *queue,
+ GList *link_);
G_END_DECLS
Index: tests/queue-test.c
===================================================================
RCS file: /cvs/gnome/glib/tests/queue-test.c,v
retrieving revision 1.5
diff -u -r1.5 queue-test.c
--- tests/queue-test.c 4 Jul 2002 15:19:30 -0000 1.5
+++ tests/queue-test.c 6 Oct 2003 13:33:22 -0000
@@ -6,27 +6,769 @@
#endif
#include <glib.h>
-int main()
+#include <time.h>
+#include <stdlib.h>
+
+static void
+check_integrity (GQueue *queue)
+{
+ GList *list;
+ GList *last;
+ GList *links;
+ GList *link;
+ gint n;
+
+ g_assert (queue->length < 4000000000u);
+
+ g_assert (g_queue_get_length (queue) == queue->length);
+
+ if (!queue->head)
+ g_assert (!queue->tail);
+ if (!queue->tail)
+ g_assert (!queue->head);
+
+ n = 0;
+ last = NULL;
+ for (list = queue->head; list != NULL; list = list->next)
+ {
+ if (!list->next)
+ last = list;
+ ++n;
+ }
+ g_assert (n == queue->length);
+ g_assert (last == queue->tail);
+
+ n = 0;
+ last = NULL;
+ for (list = queue->tail; list != NULL; list = list->prev)
+ {
+ if (!list->prev)
+ last = list;
+ ++n;
+ }
+ g_assert (n == queue->length);
+ g_assert (last == queue->head);
+
+ links = NULL;
+ for (list = queue->head; list != NULL; list = list->next)
+ links = g_list_prepend (links, list);
+
+ link = links;
+ for (list = queue->tail; list != NULL; list = list->prev)
+ {
+ g_assert (list == link->data);
+ link = link->next;
+ }
+ g_list_free (links);
+
+ links = NULL;
+ for (list = queue->tail; list != NULL; list = list->prev)
+ links = g_list_prepend (links, list);
+
+ link = links;
+ for (list = queue->head; list != NULL; list = list->next)
+ {
+ g_assert (list == link->data);
+ link = link->next;
+ }
+ g_list_free (links);
+}
+
+static gboolean
+rnd_bool (void)
+{
+ return g_random_int_range (0, 2);
+}
+
+static void
+check_max (gpointer elm, gpointer user_data)
+{
+ gint *best = user_data;
+ gint element = GPOINTER_TO_INT (elm);
+
+ if (element > *best)
+ *best = element;
+}
+
+static void
+check_min (gpointer elm, gpointer user_data)
+{
+ gint *best = user_data;
+ gint element = GPOINTER_TO_INT (elm);
+
+ if (element < *best)
+ *best = element;
+}
+
+static gint
+find_min (GQueue *queue)
+{
+ gint min = G_MAXINT;
+
+ g_queue_foreach (queue, check_min, &min);
+
+ return min;
+}
+
+static gint
+find_max (GQueue *queue)
+{
+ gint max = G_MININT;
+
+ g_queue_foreach (queue, check_max, &max);
+
+ return max;
+}
+
+static void
+delete_elm (gpointer elm, gpointer user_data)
{
- GQueue *q;
+ g_queue_remove ((GQueue *)user_data, elm);
+ check_integrity ((GQueue *)user_data);
+}
+
+static void
+delete_all (GQueue *queue)
+{
+ g_queue_foreach (queue, delete_elm, queue);
+}
+
+static int
+compare_int (gconstpointer a, gconstpointer b, gpointer data)
+{
+ int ai = GPOINTER_TO_INT (a);
+ int bi = GPOINTER_TO_INT (b);
+
+ if (ai > bi)
+ return 1;
+ else if (ai == bi)
+ return 0;
+ else
+ return -1;
+}
+
+static gint
+get_random_position (GQueue *queue, gboolean allow_offlist)
+{
+ int n;
+ enum { OFF_QUEUE, HEAD, TAIL, MIDDLE, LAST } where;
+
+ if (allow_offlist)
+ where = g_random_int_range (OFF_QUEUE, LAST);
+ else
+ where = g_random_int_range (HEAD, LAST);
+
+ switch (where)
+ {
+ case OFF_QUEUE:
+ n = g_random_int ();
+ break;
+
+ case HEAD:
+ n = 0;
+ break;
+
+ case TAIL:
+ if (allow_offlist)
+ n = queue->length;
+ else
+ n = queue->length - 1;
+ break;
+
+ case MIDDLE:
+ if (queue->length == 0)
+ n = 0;
+ else
+ n = g_random_int_range (0, queue->length);
+ break;
+
+ default:
+ g_assert_not_reached();
+ n = 100;
+ break;
+
+ }
+
+ return n;
+}
+
+static void
+random_test (int seed)
+{
+ typedef enum {
+ IS_EMPTY, GET_LENGTH, REVERSE, COPY,
+ FOREACH, FIND, FIND_CUSTOM, SORT,
+ PUSH_HEAD, PUSH_TAIL, PUSH_NTH, POP_HEAD,
+ POP_TAIL, POP_NTH, PEEK_HEAD, PEEK_TAIL,
+ PEEK_NTH, INDEX, REMOVE, REMOVE_ALL,
+ INSERT_BEFORE, INSERT_AFTER, INSERT_SORTED, PUSH_HEAD_LINK,
+ PUSH_TAIL_LINK, PUSH_NTH_LINK, POP_HEAD_LINK, POP_TAIL_LINK,
+ POP_NTH_LINK, PEEK_HEAD_LINK, PEEK_TAIL_LINK, PEEK_NTH_LINK,
+ LINK_INDEX, UNLINK, DELETE_LINK, LAST_OP
+ } QueueOp;
+
+#define N_ITERATIONS 500000
+#define N_QUEUES 3
+
+#define RANDOM_QUEUE() &(queues[g_random_int_range(0, N_QUEUES)])
+
+ typedef struct QueueInfo QueueInfo;
+ struct QueueInfo
+ {
+ GQueue *queue;
+ GList *tail;
+ GList *head;
+ guint length;
+ };
+
+ gint i;
+ QueueOp op;
+ QueueInfo queues[N_QUEUES];
+
+ g_print ("seed: %d\n", seed);
+ g_random_set_seed (seed);
+
+ for (i = 0; i < N_QUEUES; ++i)
+ {
+ queues[i].queue = g_queue_new ();
+ queues[i].head = NULL;
+ queues[i].tail = NULL;
+ queues[i].length = 0;
+ }
+
+ for (i = 0; i < N_ITERATIONS; ++i)
+ {
+ int j;
+ QueueInfo *qinf = RANDOM_QUEUE();
+ GQueue *q = qinf->queue;
+ op = g_random_int_range (IS_EMPTY, LAST_OP);
+
+ g_assert (qinf->head == q->head);
+ g_assert (qinf->tail == q->tail);
+ g_assert (qinf->length == q->length);
+
+ switch (op)
+ {
+ case IS_EMPTY:
+ {
+ if (g_queue_is_empty (qinf->queue))
+ {
+ g_assert (q->head == NULL);
+ g_assert (q->tail == NULL);
+ g_assert (q->length == 0);
+ }
+ else
+ {
+ g_assert (q->head);
+ g_assert (q->tail);
+ g_assert (q->length > 0);
+ }
+ }
+ break;
+ case GET_LENGTH:
+ {
+ int l;
+
+ l = g_queue_get_length (q);
+
+ g_assert (qinf->length == q->length);
+ g_assert (qinf->length == l);
+ }
+ break;
+ case REVERSE:
+ g_queue_reverse (q);
+ g_assert (qinf->tail == q->head);
+ g_assert (qinf->head == q->tail);
+ g_assert (qinf->length == q->length);
+ qinf->tail = q->tail;
+ qinf->head = q->head;
+ break;
+ case COPY:
+ {
+ QueueInfo *random_queue = RANDOM_QUEUE();
+ GQueue *new_queue = g_queue_copy (random_queue->queue);
+
+ g_queue_free (qinf->queue);
+ q = qinf->queue = new_queue;
+ qinf->head = new_queue->head;
+ qinf->tail = g_list_last (new_queue->head);
+ qinf->length = new_queue->length;
+ }
+ break;
+ case FOREACH:
+ delete_all (q);
+ qinf->head = NULL;
+ qinf->tail = NULL;
+ qinf->length = 0;
+ break;
+ case FIND:
+ {
+ gboolean find_existing = rnd_bool ();
+ int first = find_max (q);
+ int second = find_min (q);
+
+ if (q->length == 0)
+ find_existing = FALSE;
+
+ if (!find_existing)
+ first++;
+ if (!find_existing)
+ second--;
+
+ if (find_existing)
+ {
+ g_assert (g_queue_find (q, GINT_TO_POINTER (first)));
+ g_assert (g_queue_find (q, GINT_TO_POINTER (second)));
+ }
+ else
+ {
+ g_assert (!g_queue_find (q, GINT_TO_POINTER (first)));
+ g_assert (!g_queue_find (q, GINT_TO_POINTER (second)));
+ }
+ }
+ break;
+ case FIND_CUSTOM:
+ break;
+ case SORT:
+ {
+ if (!g_queue_is_empty (q))
+ {
+ int max = find_max (q);
+ int min = find_min (q);
+ g_queue_remove_all (q, GINT_TO_POINTER (max));
+ check_integrity (q);
+ g_queue_remove_all (q, GINT_TO_POINTER (min));
+ check_integrity (q);
+ g_queue_push_head (q, GINT_TO_POINTER (max));
+ if (max != min)
+ g_queue_push_head (q, GINT_TO_POINTER (min));
+ qinf->length = q->length;
+ }
+
+ check_integrity (q);
+
+ g_queue_sort (q, compare_int, NULL);
+
+ check_integrity (q);
+
+ qinf->head = g_queue_find (q, GINT_TO_POINTER (find_min(q)));
+ qinf->tail = g_queue_find (q, GINT_TO_POINTER (find_max(q)));
+
+ g_assert (qinf->tail == q->tail);
+ }
+ break;
+ case PUSH_HEAD:
+ {
+ int x = g_random_int_range (0, 435435);
+ g_queue_push_head (q, GINT_TO_POINTER (x));
+ if (!qinf->head)
+ qinf->tail = qinf->head = q->head;
+ else
+ qinf->head = qinf->head->prev;
+ qinf->length++;
+ }
+ break;
+ case PUSH_TAIL:
+ {
+ int x = g_random_int_range (0, 236546);
+ g_queue_push_tail (q, GINT_TO_POINTER (x));
+ if (!qinf->tail)
+ qinf->tail = qinf->head = q->head;
+ else
+ qinf->tail = qinf->tail->next;
+ qinf->length++;
+ }
+ break;
+ case PUSH_NTH:
+ {
+ int pos = get_random_position (q, TRUE);
+ int x = g_random_int_range (0, 236546);
+ g_queue_push_nth (q, GINT_TO_POINTER (x), pos);
+ if (qinf->head && qinf->head->prev)
+ qinf->head = qinf->head->prev;
+ else
+ qinf->head = q->head;
+ if (qinf->tail && qinf->tail->next)
+ qinf->tail = qinf->tail->next;
+ else
+ qinf->tail = g_list_last (qinf->head);
+ qinf->length++;
+ }
+ break;
+ case POP_HEAD:
+ if (qinf->head)
+ qinf->head = qinf->head->next;
+ if (!qinf->head)
+ qinf->tail = NULL;
+ qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
+ g_queue_pop_head (q);
+ break;
+ case POP_TAIL:
+ if (qinf->tail)
+ qinf->tail = qinf->tail->prev;
+ if (!qinf->tail)
+ qinf->head = NULL;
+ qinf->length = (qinf->length == 0)? 0 : qinf->length - 1;
+ g_queue_pop_tail (q);
+ break;
+ case POP_NTH:
+ if (!g_queue_is_empty (q))
+ {
+ int n = get_random_position (q, TRUE);
+ gpointer elm = g_queue_peek_nth (q, n);
+
+ if (n == q->length - 1)
+ qinf->tail = qinf->tail->prev;
+
+ if (n == 0)
+ qinf->head = qinf->head->next;
+
+ if (n >= 0 && n < q->length)
+ qinf->length--;
+
+ g_assert (elm == g_queue_pop_nth (q, n));
+ }
+ break;
+ case PEEK_HEAD:
+ if (qinf->head)
+ g_assert (qinf->head->data == g_queue_peek_head (q));
+ else
+ g_assert (g_queue_peek_head (q) == NULL);
+ break;
+ case PEEK_TAIL:
+ if (qinf->head)
+ g_assert (qinf->tail->data == g_queue_peek_tail (q));
+ else
+ g_assert (g_queue_peek_tail (q) == NULL);
+ break;
+ case PEEK_NTH:
+ if (g_queue_is_empty (q))
+ {
+ for (j = -10; j < 10; ++j)
+ g_assert (g_queue_peek_nth (q, j) == NULL);
+ }
+ else
+ {
+ GList *list;
+ int n = get_random_position (q, TRUE);
+ if (n < 0 || n >= q->length)
+ {
+ g_assert (g_queue_peek_nth (q, n) == NULL);
+ }
+ else
+ {
+ list = qinf->head;
+ for (j = 0; j < n; ++j)
+ list = list->next;
+
+ g_assert (list->data == g_queue_peek_nth (q, n));
+ }
+ }
+ break;
+ case INDEX:
+ case LINK_INDEX:
+ {
+ int x = g_random_int_range (0, 386538);
+ int n;
+ GList *list;
+
+ g_queue_remove_all (q, GINT_TO_POINTER (x));
+ check_integrity (q);
+ g_queue_push_tail (q, GINT_TO_POINTER (x));
+ check_integrity (q);
+ g_queue_sort (q, compare_int, NULL);
+ check_integrity (q);
+
+ n = 0;
+ for (list = q->head; list != NULL; list = list->next)
+ {
+ if (list->data == GINT_TO_POINTER (x))
+ break;
+ n++;
+ }
+ g_assert (list);
+ g_assert (g_queue_index (q, GINT_TO_POINTER (x)) ==
+ g_queue_link_index (q, list));
+ g_assert (g_queue_link_index (q, list) == n);
+
+ qinf->head = q->head;
+ qinf->tail = q->tail;
+ qinf->length = q->length;
+ }
+ break;
+ case REMOVE:
+ if (!g_queue_is_empty (q))
+ g_queue_remove (q, qinf->tail->data);
+ if (!g_queue_is_empty (q))
+ g_queue_remove (q, qinf->head->data);
+ if (!g_queue_is_empty (q))
+ g_queue_remove (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
+
+ qinf->head = q->head;
+ qinf->tail = q->tail;
+ qinf->length = q->length;
+ break;
+ case REMOVE_ALL:
+ if (!g_queue_is_empty (q))
+ g_queue_remove_all (q, qinf->tail->data);
+ if (!g_queue_is_empty (q))
+ g_queue_remove_all (q, qinf->head->data);
+ if (!g_queue_is_empty (q))
+ g_queue_remove_all (q, g_queue_peek_nth (q, get_random_position (q, TRUE)));
+
+ qinf->head = q->head;
+ qinf->tail = q->tail;
+ qinf->length = q->length;
+ break;
+ case INSERT_BEFORE:
+ if (!g_queue_is_empty (q))
+ {
+ gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
+
+ g_queue_insert_before (q, qinf->tail, x);
+ g_queue_insert_before (q, qinf->head, x);
+ g_queue_insert_before (q, g_queue_find (q, x), x);
+ }
+ qinf->head = q->head;
+ qinf->tail = q->tail;
+ qinf->length = q->length;
+ break;
+ case INSERT_AFTER:
+ if (!g_queue_is_empty (q))
+ {
+ gpointer x = GINT_TO_POINTER (g_random_int_range (0, 386538));
+
+ g_queue_insert_after (q, qinf->tail, x);
+ g_queue_insert_after (q, qinf->head, x);
+ g_queue_insert_after (q, g_queue_find (q, x), x);
+ }
+ qinf->head = q->head;
+ qinf->tail = q->tail;
+ qinf->length = q->length;
+ break;
+ case INSERT_SORTED:
+ {
+ int max = find_max (q);
+ int min = find_min (q);
+
+ if (g_queue_is_empty (q))
+ {
+ max = 345;
+ min = -12;
+ }
+
+ g_queue_sort (q, compare_int, NULL);
+ check_integrity (q);
+ g_queue_insert_sorted (q, GINT_TO_POINTER (max + 1), compare_int, NULL);
+ check_integrity (q);
+ g_assert (GPOINTER_TO_INT (q->tail->data) == max + 1);
+ g_queue_insert_sorted (q, GINT_TO_POINTER (min - 1), compare_int, NULL);
+ check_integrity (q);
+ g_assert (GPOINTER_TO_INT (q->head->data) == min - 1);
+ qinf->head = q->head;
+ qinf->tail = q->tail;
+ qinf->length = q->length;
+ }
+ break;
+ case PUSH_HEAD_LINK:
+ {
+ GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
+ g_queue_push_head_link (q, link);
+ if (!qinf->tail)
+ qinf->tail = link;
+ qinf->head = link;
+ qinf->length++;
+ }
+ break;
+ case PUSH_TAIL_LINK:
+ {
+ GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
+ g_queue_push_tail_link (q, link);
+ if (!qinf->head)
+ qinf->head = link;
+ qinf->tail = link;
+ qinf->length++;
+ }
+ break;
+ case PUSH_NTH_LINK:
+ {
+ GList *link = g_list_prepend (NULL, GINT_TO_POINTER (i));
+ gint n = get_random_position (q, TRUE);
+ g_queue_push_nth_link (q, n, link);
+
+ if (qinf->head && qinf->head->prev)
+ qinf->head = qinf->head->prev;
+ else
+ qinf->head = q->head;
+ if (qinf->tail && qinf->tail->next)
+ qinf->tail = qinf->tail->next;
+ else
+ qinf->tail = g_list_last (qinf->head);
+ qinf->length++;
+ }
+ break;
+ case POP_HEAD_LINK:
+ if (!g_queue_is_empty (q))
+ {
+ qinf->head = qinf->head->next;
+ if (!qinf->head)
+ qinf->tail = NULL;
+ qinf->length--;
+ g_list_free (g_queue_pop_head_link (q));
+ }
+ break;
+ case POP_TAIL_LINK:
+ if (!g_queue_is_empty (q))
+ {
+ qinf->tail = qinf->tail->prev;
+ if (!qinf->tail)
+ qinf->head = NULL;
+ qinf->length--;
+ g_list_free (g_queue_pop_tail_link (q));
+ }
+ break;
+ case POP_NTH_LINK:
+ if (g_queue_is_empty (q))
+ g_assert (g_queue_pop_nth_link (q, 200) == NULL);
+ else
+ {
+ int n = get_random_position (q, FALSE);
+
+ if (n == g_queue_get_length (q) - 1)
+ qinf->tail = qinf->tail->prev;
+
+ if (n == 0)
+ qinf->head = qinf->head->next;
+
+ qinf->length--;
+
+ g_list_free (g_queue_pop_nth_link (q, n));
+ }
+ break;
+ case PEEK_HEAD_LINK:
+ if (g_queue_is_empty (q))
+ g_assert (g_queue_peek_head_link (q) == NULL);
+ else
+ g_assert (g_queue_peek_head_link (q) == qinf->head);
+ break;
+ case PEEK_TAIL_LINK:
+ if (g_queue_is_empty (q))
+ g_assert (g_queue_peek_tail_link (q) == NULL);
+ else
+ g_assert (g_queue_peek_tail_link (q) == qinf->tail);
+ break;
+ case PEEK_NTH_LINK:
+ if (g_queue_is_empty(q))
+ g_assert (g_queue_peek_nth_link (q, 1000) == NULL);
+ else
+ {
+ gint n = get_random_position (q, FALSE);
+ GList *link;
+
+ link = q->head;
+ for (j = 0; j < n; ++j)
+ link = link->next;
+
+ g_assert (g_queue_peek_nth_link (q, n) == link);
+ }
+ break;
+ case UNLINK:
+ if (!g_queue_is_empty (q))
+ {
+ gint n = g_random_int_range (0, g_queue_get_length (q));
+ GList *link;
+
+ link = q->head;
+ for (j = 0; j < n; ++j)
+ link = link->next;
+
+ g_queue_unlink (q, link);
+ check_integrity (q);
+
+ g_list_free (link);
+
+ qinf->head = q->head;
+ qinf->tail = q->tail;
+ qinf->length--;
+ }
+ break;
+ case DELETE_LINK:
+ if (!g_queue_is_empty (q))
+ {
+ gint n = g_random_int_range (0, g_queue_get_length (q));
+ GList *link;
+
+ link = q->head;
+ for (j = 0; j < n; ++j)
+ link = link->next;
+
+ g_queue_delete_link (q, link);
+ check_integrity (q);
+
+ qinf->head = q->head;
+ qinf->tail = q->tail;
+ qinf->length--;
+ }
+ break;
+ case LAST_OP:
+ default:
+ g_assert_not_reached();
+ break;
+ }
+
+ if (qinf->head != q->head ||
+ qinf->tail != q->tail ||
+ qinf->length != q->length)
+ g_print ("op: %d\n", op);
+
+ g_assert (qinf->head == q->head);
+ g_assert (qinf->tail == q->tail);
+ g_assert (qinf->length == q->length);
+
+ for (j = 0; j < N_QUEUES; ++j)
+ check_integrity (queues[j].queue);
+ }
+
+ for (i = 0; i < N_QUEUES; ++i)
+ g_queue_free (queues[i].queue);
+}
+
+static void
+remove_item (gpointer data, gpointer q)
+{
+ GQueue *queue = q;
+
+ g_queue_remove (queue, data);
+}
+
+int main(int argc, gchar *args[])
+{
+ GQueue *q, *q2;
GList *node;
gpointer data;
-
+ int i;
+
q = g_queue_new ();
-
+
g_assert (g_queue_is_empty (q) == TRUE);
-
+
g_queue_push_head (q, GINT_TO_POINTER (2));
+ check_integrity (q);
g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (2));
+ check_integrity (q);
g_assert (g_queue_is_empty (q) == FALSE);
+ check_integrity (q);
g_assert (g_list_length (q->head) == 1);
g_assert (q->head == q->tail);
g_queue_push_head (q, GINT_TO_POINTER (1));
+ check_integrity (q);
g_assert (q->head->next == q->tail);
g_assert (q->tail->prev == q->head);
g_assert (g_list_length (q->head) == 2);
+ check_integrity (q);
g_assert (q->tail->data == GINT_TO_POINTER (2));
g_assert (q->head->data == GINT_TO_POINTER (1));
+ check_integrity (q);
g_queue_push_tail (q, GINT_TO_POINTER (3));
g_assert (g_list_length (q->head) == 3);
g_assert (q->head->data == GINT_TO_POINTER (1));
@@ -35,14 +777,17 @@
g_assert (q->head->next == q->tail->prev);
g_assert (q->tail->data == GINT_TO_POINTER (3));
g_queue_push_tail (q, GINT_TO_POINTER (4));
+ check_integrity (q);
g_assert (g_list_length (q->head) == 4);
g_assert (q->head->data == GINT_TO_POINTER (1));
g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (4));
g_queue_push_tail (q, GINT_TO_POINTER (5));
+ check_integrity (q);
g_assert (g_list_length (q->head) == 5);
-
+
g_assert (g_queue_is_empty (q) == FALSE);
-
+ check_integrity (q);
+
g_assert (q->length == 5);
g_assert (q->head->prev == NULL);
g_assert (q->head->data == GINT_TO_POINTER (1));
@@ -61,58 +806,135 @@
g_assert (q->tail->prev->prev->prev->prev == q->head);
g_assert (g_queue_peek_tail (q) == GINT_TO_POINTER (5));
g_assert (g_queue_peek_head (q) == GINT_TO_POINTER (1));
-
+
g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (1));
+ check_integrity (q);
g_assert (g_list_length (q->head) == 4 && q->length == 4);
g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (5));
+ check_integrity (q);
g_assert (g_list_length (q->head) == 3);
g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (2));
+ check_integrity (q);
g_assert (g_list_length (q->head) == 2);
g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (4));
+ check_integrity (q);
g_assert (g_list_length (q->head) == 1);
g_assert (g_queue_pop_head_link (q)->data == GINT_TO_POINTER (3));
+ check_integrity (q);
g_assert (g_list_length (q->head) == 0);
g_assert (g_queue_pop_tail (q) == NULL);
+ check_integrity (q);
g_assert (g_list_length (q->head) == 0);
g_assert (g_queue_pop_head (q) == NULL);
+ check_integrity (q);
g_assert (g_list_length (q->head) == 0);
-
+
g_assert (g_queue_is_empty (q) == TRUE);
-
+ check_integrity (q);
+
/************************/
-
+
g_queue_push_head (q, GINT_TO_POINTER (1));
+ check_integrity (q);
g_assert (g_list_length (q->head) == 1 && 1 == q->length);
g_queue_push_head (q, GINT_TO_POINTER (2));
+ check_integrity (q);
g_assert (g_list_length (q->head) == 2 && 2 == q->length);
g_queue_push_head (q, GINT_TO_POINTER (3));
+ check_integrity (q);
g_assert (g_list_length (q->head) == 3 && 3 == q->length);
g_queue_push_head (q, GINT_TO_POINTER (4));
+ check_integrity (q);
g_assert (g_list_length (q->head) == 4 && 4 == q->length);
g_queue_push_head (q, GINT_TO_POINTER (5));
+ check_integrity (q);
g_assert (g_list_length (q->head) == 5 && 5 == q->length);
-
+
g_assert (g_queue_pop_head (q) == GINT_TO_POINTER (5));
+ check_integrity (q);
g_assert (g_list_length (q->head) == 4);
node = q->tail;
g_assert (node == g_queue_pop_tail_link (q));
+ check_integrity (q);
g_assert (g_list_length (q->head) == 3);
data = q->head->data;
g_assert (data == g_queue_pop_head (q));
+ check_integrity (q);
g_assert (g_list_length (q->head) == 2);
g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (2));
+ check_integrity (q);
g_assert (g_list_length (q->head) == 1);
g_assert (q->head == q->tail);
g_assert (g_queue_pop_tail (q) == GINT_TO_POINTER (3));
+ check_integrity (q);
g_assert (g_list_length (q->head) == 0);
g_assert (g_queue_pop_head (q) == NULL);
+ check_integrity (q);
g_assert (g_queue_pop_head_link (q) == NULL);
+ check_integrity (q);
g_assert (g_list_length (q->head) == 0);
g_assert (g_queue_pop_tail_link (q) == NULL);
+ check_integrity (q);
g_assert (g_list_length (q->head) == 0);
-
+
+ /* */
+ g_queue_reverse (q);
+ check_integrity (q);
+ g_assert (g_list_length (q->head) == 0);
+
+ q2 = g_queue_copy (q);
+ check_integrity (q);
+ check_integrity (q2);
+ g_assert (g_list_length (q->head) == 0);
+ g_assert (g_list_length (q2->head) == 0);
+ g_queue_sort (q, compare_int, NULL);
+ check_integrity (q2);
+ check_integrity (q);
+ g_queue_sort (q2, compare_int, NULL);
+ check_integrity (q2);
+ check_integrity (q);
+
+ for (i = 0; i < 200; ++i)
+ {
+ g_queue_push_nth (q, GINT_TO_POINTER (i), i);
+ g_assert (g_queue_find (q, GINT_TO_POINTER (i)));
+ check_integrity (q);
+ check_integrity (q2);
+ }
+
+ for (i = 0; i < 200; ++i)
+ {
+ g_queue_remove (q, GINT_TO_POINTER (i));
+ check_integrity (q);
+ check_integrity (q2);
+ }
+
+ for (i = 0; i < 200; ++i)
+ {
+ GList *l = g_list_prepend (NULL, GINT_TO_POINTER (i));
+
+ g_queue_push_nth_link (q, i, l);
+ check_integrity (q);
+ check_integrity (q2);
+ g_queue_reverse (q);
+ check_integrity (q);
+ check_integrity (q2);
+ }
+
+ g_queue_free (q2);
+ q2 = g_queue_copy (q);
+
+ g_queue_foreach (q2, remove_item, q2);
+ check_integrity (q2);
+ check_integrity (q);
+
g_queue_free (q);
+ if (argc > 1)
+ random_test (strtol (args[1], NULL, 0));
+ else
+ random_test (time (0));
+
return 0;
}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
