From a9bbf0f35d56ecf452266698e10f7e9c5b3e9e95 Mon Sep 17 00:00:00 2001 From: Soeren Sandmann Date: Sat, 21 Feb 2004 12:48:08 +0000 Subject: [PATCH] Extend GQueue API to match the GList API. (#118439). Sat Feb 21 13:45:08 2004 Soeren Sandmann * glib/gqueue.[ch]: Extend GQueue API to match the GList API. (#118439). * tests/queue-test.c: Update test suite to cover the new API. --- ChangeLog | 7 + ChangeLog.pre-2-10 | 7 + ChangeLog.pre-2-12 | 7 + ChangeLog.pre-2-4 | 7 + ChangeLog.pre-2-6 | 7 + ChangeLog.pre-2-8 | 7 + glib/gqueue.c | 660 ++++++++++++++++++++++++++++++++++++++++- glib/gqueue.h | 86 +++++- tests/queue-test.c | 848 ++++++++++++++++++++++++++++++++++++++++++++++++++++- 9 files changed, 1598 insertions(+), 38 deletions(-) diff --git a/ChangeLog b/ChangeLog index 31aa343..a33032f 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,10 @@ +Sat Feb 21 13:45:08 2004 Soeren Sandmann + + * glib/gqueue.[ch]: Extend GQueue API to match the GList + API. (#118439). + + * tests/queue-test.c: Update test suite to cover the new API. + Fri Feb 20 03:02:05 2004 Tim Janik * glib/ghash.[hc]: applied patch from #131937 with slight diff --git a/ChangeLog.pre-2-10 b/ChangeLog.pre-2-10 index 31aa343..a33032f 100644 --- a/ChangeLog.pre-2-10 +++ b/ChangeLog.pre-2-10 @@ -1,3 +1,10 @@ +Sat Feb 21 13:45:08 2004 Soeren Sandmann + + * glib/gqueue.[ch]: Extend GQueue API to match the GList + API. (#118439). + + * tests/queue-test.c: Update test suite to cover the new API. + Fri Feb 20 03:02:05 2004 Tim Janik * glib/ghash.[hc]: applied patch from #131937 with slight diff --git a/ChangeLog.pre-2-12 b/ChangeLog.pre-2-12 index 31aa343..a33032f 100644 --- a/ChangeLog.pre-2-12 +++ b/ChangeLog.pre-2-12 @@ -1,3 +1,10 @@ +Sat Feb 21 13:45:08 2004 Soeren Sandmann + + * glib/gqueue.[ch]: Extend GQueue API to match the GList + API. (#118439). + + * tests/queue-test.c: Update test suite to cover the new API. + Fri Feb 20 03:02:05 2004 Tim Janik * glib/ghash.[hc]: applied patch from #131937 with slight diff --git a/ChangeLog.pre-2-4 b/ChangeLog.pre-2-4 index 31aa343..a33032f 100644 --- a/ChangeLog.pre-2-4 +++ b/ChangeLog.pre-2-4 @@ -1,3 +1,10 @@ +Sat Feb 21 13:45:08 2004 Soeren Sandmann + + * glib/gqueue.[ch]: Extend GQueue API to match the GList + API. (#118439). + + * tests/queue-test.c: Update test suite to cover the new API. + Fri Feb 20 03:02:05 2004 Tim Janik * glib/ghash.[hc]: applied patch from #131937 with slight diff --git a/ChangeLog.pre-2-6 b/ChangeLog.pre-2-6 index 31aa343..a33032f 100644 --- a/ChangeLog.pre-2-6 +++ b/ChangeLog.pre-2-6 @@ -1,3 +1,10 @@ +Sat Feb 21 13:45:08 2004 Soeren Sandmann + + * glib/gqueue.[ch]: Extend GQueue API to match the GList + API. (#118439). + + * tests/queue-test.c: Update test suite to cover the new API. + Fri Feb 20 03:02:05 2004 Tim Janik * glib/ghash.[hc]: applied patch from #131937 with slight diff --git a/ChangeLog.pre-2-8 b/ChangeLog.pre-2-8 index 31aa343..a33032f 100644 --- a/ChangeLog.pre-2-8 +++ b/ChangeLog.pre-2-8 @@ -1,3 +1,10 @@ +Sat Feb 21 13:45:08 2004 Soeren Sandmann + + * glib/gqueue.[ch]: Extend GQueue API to match the GList + API. (#118439). + + * tests/queue-test.c: Update test suite to cover the new API. + Fri Feb 20 03:02:05 2004 Tim Janik * glib/ghash.[hc]: applied patch from #131937 with slight diff --git a/glib/gqueue.c b/glib/gqueue.c index debbfa0..437bbdc 100644 --- a/glib/gqueue.c +++ b/glib/gqueue.c @@ -90,6 +90,188 @@ g_queue_free (GQueue *queue) } /** + * 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_head (GQueue *queue, } /** + * 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, not 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_tail_link (GQueue *queue, } /** + * 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_pop_head_link (GQueue *queue) } /** + * 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_tail (GQueue *queue) } /** + * 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_pop_tail_link (GQueue *queue) } /** - * g_queue_is_empty: - * @queue: a #GQueue. + * 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 + **/ +GList* +g_queue_pop_nth_link (GQueue *queue, + guint n) +{ + GList *link; + + g_return_val_if_fail (queue != NULL, 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 must be part of @queue * - * Returns %TRUE if the queue is empty. + * Unlinks @link_ so that it will no longer be part of @queue. The link is + * not freed. * - * Returns: %TRUE if the queue is empty. + * @link_ must be part of @queue, + * + * Since: 2.4 **/ -gboolean -g_queue_is_empty (GQueue *queue) +void +g_queue_unlink (GQueue *queue, + GList *link_) { - g_return_val_if_fail (queue != NULL, TRUE); + g_return_if_fail (queue != NULL); + g_return_if_fail (link_ != NULL); - return queue->head == 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 must 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_); } /** @@ -364,3 +817,192 @@ g_queue_peek_tail (GQueue *queue) 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 must 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 must 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); +} diff --git a/glib/gqueue.h b/glib/gqueue.h index 7ce9a25..36810ff 100644 --- a/glib/gqueue.h +++ b/glib/gqueue.h @@ -43,22 +43,76 @@ struct _GQueue /* 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 diff --git a/tests/queue-test.c b/tests/queue-test.c index 101b75a..688b56e 100644 --- a/tests/queue-test.c +++ b/tests/queue-test.c @@ -6,27 +6,769 @@ #endif #include -int main() +#include +#include + +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) +{ + 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; + 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 @@ int main() 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 @@ int main() 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; } -- 2.7.4