--- /dev/null
+/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
+/* dbus-list.c Generic linked list utility (internal to D-Bus implementation)
+ *
+ * Copyright (C) 2002 Red Hat, Inc.
+ *
+ * Licensed under the Academic Free License version 2.1
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ */
+
+#include "dbus-internals.h"
+#include "dbus-list.h"
+#include "dbus-mempool.h"
+#include "dbus-threads-internal.h"
+
+/**
+ * @defgroup DBusList Linked list
+ * @ingroup DBusInternals
+ * @brief DBusList data structure
+ *
+ * Types and functions related to DBusList.
+ */
+
+static DBusMemPool *list_pool;
+_DBUS_DEFINE_GLOBAL_LOCK (list);
+
+/**
+ * @defgroup DBusListInternals Linked list implementation details
+ * @ingroup DBusInternals
+ * @brief DBusList implementation details
+ *
+ * The guts of DBusList.
+ *
+ * @{
+ */
+
+/* the mem pool is probably a speed hit, with the thread
+ * lock, though it does still save memory - unknown.
+ */
+static DBusList*
+alloc_link (void *data)
+{
+ DBusList *link;
+
+ _DBUS_LOCK (list);
+
+ if (list_pool == NULL)
+ {
+ list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE);
+
+ if (list_pool == NULL)
+ {
+ _DBUS_UNLOCK (list);
+ return NULL;
+ }
+
+ link = _dbus_mem_pool_alloc (list_pool);
+ if (link == NULL)
+ {
+ _dbus_mem_pool_free (list_pool);
+ list_pool = NULL;
+ _DBUS_UNLOCK (list);
+ return NULL;
+ }
+ }
+ else
+ {
+ link = _dbus_mem_pool_alloc (list_pool);
+ }
+
+ if (link)
+ link->data = data;
+
+ _DBUS_UNLOCK (list);
+
+ return link;
+}
+
+static void
+free_link (DBusList *link)
+{
+ _DBUS_LOCK (list);
+ if (_dbus_mem_pool_dealloc (list_pool, link))
+ {
+ _dbus_mem_pool_free (list_pool);
+ list_pool = NULL;
+ }
+
+ _DBUS_UNLOCK (list);
+}
+
+static void
+link_before (DBusList **list,
+ DBusList *before_this_link,
+ DBusList *link)
+{
+ if (*list == NULL)
+ {
+ link->prev = link;
+ link->next = link;
+ *list = link;
+ }
+ else
+ {
+ link->next = before_this_link;
+ link->prev = before_this_link->prev;
+ before_this_link->prev = link;
+ link->prev->next = link;
+
+ if (before_this_link == *list)
+ *list = link;
+ }
+}
+
+static void
+link_after (DBusList **list,
+ DBusList *after_this_link,
+ DBusList *link)
+{
+ if (*list == NULL)
+ {
+ link->prev = link;
+ link->next = link;
+ *list = link;
+ }
+ else
+ {
+ link->prev = after_this_link;
+ link->next = after_this_link->next;
+ after_this_link->next = link;
+ link->next->prev = link;
+ }
+}
+
+/** @} */
+
+/**
+ * @addtogroup DBusList
+ * @{
+ */
+
+/**
+ * @struct DBusList
+ *
+ * A node in a linked list.
+ *
+ * DBusList is a circular list; that is, the tail of the list
+ * points back to the head of the list. The empty list is
+ * represented by a #NULL pointer.
+ */
+
+/**
+ * @def _dbus_list_get_next_link
+ *
+ * Gets the next link in the list, or #NULL if
+ * there are no more links. Used for iteration.
+ *
+ * @code
+ * DBusList *link;
+ * link = _dbus_list_get_first_link (&list);
+ * while (link != NULL)
+ * {
+ * printf ("value is %p\n", link->data);
+ * link = _dbus_list_get_next_link (&link);
+ * }
+ * @endcode
+ *
+ * @param list address of the list head.
+ * @param link current link.
+ * @returns the next link, or %NULL if none.
+ *
+ */
+
+/**
+ * @def _dbus_list_get_prev_link
+ *
+ * Gets the previous link in the list, or #NULL if
+ * there are no more links. Used for iteration.
+ *
+ * @code
+ * DBusList *link;
+ * link = _dbus_list_get_last_link (&list);
+ * while (link != NULL)
+ * {
+ * printf ("value is %p\n", link->data);
+ * link = _dbus_list_get_prev_link (&link);
+ * }
+ * @endcode
+ *
+ * @param list address of the list head.
+ * @param link current link.
+ * @returns the previous link, or %NULL if none.
+ *
+ */
+
+/**
+ * Allocates a linked list node. Useful for preallocating
+ * nodes and using _dbus_list_append_link() to avoid
+ * allocations.
+ *
+ * @param data the value to store in the link.
+ * @returns a newly allocated link.
+ */
+DBusList*
+_dbus_list_alloc_link (void *data)
+{
+ return alloc_link (data);
+}
+
+/**
+ * Frees a linked list node allocated with _dbus_list_alloc_link.
+ * Does not free the data in the node.
+ *
+ * @param link the list node
+ */
+void
+_dbus_list_free_link (DBusList *link)
+{
+ free_link (link);
+}
+
+
+/**
+ * Appends a value to the list. May return #FALSE
+ * if insufficient memory exists to add a list link.
+ * This is a constant-time operation.
+ *
+ * @param list address of the list head.
+ * @param data the value to append.
+ * @returns #TRUE on success.
+ */
+dbus_bool_t
+_dbus_list_append (DBusList **list,
+ void *data)
+{
+ if (!_dbus_list_prepend (list, data))
+ return FALSE;
+
+ /* Now cycle the list forward one so the prepended node is the tail */
+ *list = (*list)->next;
+
+ return TRUE;
+}
+
+/**
+ * Prepends a value to the list. May return #FALSE
+ * if insufficient memory exists to add a list link.
+ * This is a constant-time operation.
+ *
+ * @param list address of the list head.
+ * @param data the value to prepend.
+ * @returns #TRUE on success.
+ */
+dbus_bool_t
+_dbus_list_prepend (DBusList **list,
+ void *data)
+{
+ DBusList *link;
+
+ link = alloc_link (data);
+ if (link == NULL)
+ return FALSE;
+
+ link_before (list, *list, link);
+
+ return TRUE;
+}
+
+/**
+ * Appends a link to the list.
+ * Cannot fail due to out of memory.
+ * This is a constant-time operation.
+ *
+ * @param list address of the list head.
+ * @param link the link to append.
+ */
+void
+_dbus_list_append_link (DBusList **list,
+ DBusList *link)
+{
+ _dbus_list_prepend_link (list, link);
+
+ /* Now cycle the list forward one so the prepended node is the tail */
+ *list = (*list)->next;
+}
+
+/**
+ * Prepends a link to the list.
+ * Cannot fail due to out of memory.
+ * This is a constant-time operation.
+ *
+ * @param list address of the list head.
+ * @param link the link to prepend.
+ */
+void
+_dbus_list_prepend_link (DBusList **list,
+ DBusList *link)
+{
+ link_before (list, *list, link);
+}
+
+#ifdef DBUS_BUILD_TESTS
+/**
+ * Inserts data into the list before the given existing link.
+ *
+ * @param list the list to modify
+ * @param before_this_link existing link to insert before, or #NULL to append
+ * @param data the value to insert
+ * @returns #TRUE on success, #FALSE if memory allocation fails
+ */
+dbus_bool_t
+_dbus_list_insert_before (DBusList **list,
+ DBusList *before_this_link,
+ void *data)
+{
+ DBusList *link;
+
+ if (before_this_link == NULL)
+ return _dbus_list_append (list, data);
+ else
+ {
+ link = alloc_link (data);
+ if (link == NULL)
+ return FALSE;
+
+ link_before (list, before_this_link, link);
+ }
+
+ return TRUE;
+}
+#endif /* DBUS_BUILD_TESTS */
+
+/**
+ * Inserts data into the list after the given existing link.
+ *
+ * @param list the list to modify
+ * @param after_this_link existing link to insert after, or #NULL to prepend
+ * @param data the value to insert
+ * @returns #TRUE on success, #FALSE if memory allocation fails
+ */
+dbus_bool_t
+_dbus_list_insert_after (DBusList **list,
+ DBusList *after_this_link,
+ void *data)
+{
+ DBusList *link;
+
+ if (after_this_link == NULL)
+ return _dbus_list_prepend (list, data);
+ else
+ {
+ link = alloc_link (data);
+ if (link == NULL)
+ return FALSE;
+
+ link_after (list, after_this_link, link);
+ }
+
+ return TRUE;
+}
+
+/**
+ * Inserts a link into the list before the given existing link.
+ *
+ * @param list the list to modify
+ * @param before_this_link existing link to insert before, or #NULL to append
+ * @param link the link to insert
+ */
+void
+_dbus_list_insert_before_link (DBusList **list,
+ DBusList *before_this_link,
+ DBusList *link)
+{
+ if (before_this_link == NULL)
+ _dbus_list_append_link (list, link);
+ else
+ link_before (list, before_this_link, link);
+}
+
+/**
+ * Inserts a link into the list after the given existing link.
+ *
+ * @param list the list to modify
+ * @param after_this_link existing link to insert after, or #NULL to prepend
+ * @param link the link to insert
+ */
+void
+_dbus_list_insert_after_link (DBusList **list,
+ DBusList *after_this_link,
+ DBusList *link)
+{
+ if (after_this_link == NULL)
+ _dbus_list_prepend_link (list, link);
+ else
+ link_after (list, after_this_link, link);
+}
+
+/**
+ * Removes a value from the list. Only removes the
+ * first value equal to the given data pointer,
+ * even if multiple values exist which match.
+ * This is a linear-time operation.
+ *
+ * @param list address of the list head.
+ * @param data the value to remove.
+ * @returns #TRUE if a value was found to remove.
+ */
+dbus_bool_t
+_dbus_list_remove (DBusList **list,
+ void *data)
+{
+ DBusList *link;
+
+ link = *list;
+ while (link != NULL)
+ {
+ if (link->data == data)
+ {
+ _dbus_list_remove_link (list, link);
+ return TRUE;
+ }
+
+ link = _dbus_list_get_next_link (list, link);
+ }
+
+ return FALSE;
+}
+
+/**
+ * Removes a value from the list. Only removes the
+ * last value equal to the given data pointer,
+ * even if multiple values exist which match.
+ * This is a linear-time operation.
+ *
+ * @param list address of the list head.
+ * @param data the value to remove.
+ * @returns #TRUE if a value was found to remove.
+ */
+dbus_bool_t
+_dbus_list_remove_last (DBusList **list,
+ void *data)
+{
+ DBusList *link;
+
+ link = _dbus_list_find_last (list, data);
+ if (link)
+ {
+ _dbus_list_remove_link (list, link);
+ return TRUE;
+ }
+ else
+ return FALSE;
+}
+
+/**
+ * Finds a value in the list. Returns the last link
+ * with value equal to the given data pointer.
+ * This is a linear-time operation.
+ * Returns #NULL if no value found that matches.
+ *
+ * @param list address of the list head.
+ * @param data the value to find.
+ * @returns the link if found
+ */
+DBusList*
+_dbus_list_find_last (DBusList **list,
+ void *data)
+{
+ DBusList *link;
+
+ link = _dbus_list_get_last_link (list);
+
+ while (link != NULL)
+ {
+ if (link->data == data)
+ return link;
+
+ link = _dbus_list_get_prev_link (list, link);
+ }
+
+ return NULL;
+}
+
+/**
+ * Removes the given link from the list, but doesn't
+ * free it. _dbus_list_remove_link() both removes the
+ * link and also frees it.
+ *
+ * @param list the list
+ * @param link the link in the list
+ */
+void
+_dbus_list_unlink (DBusList **list,
+ DBusList *link)
+{
+ if (link->next == link)
+ {
+ /* one-element list */
+ *list = NULL;
+ }
+ else
+ {
+ link->prev->next = link->next;
+ link->next->prev = link->prev;
+
+ if (*list == link)
+ *list = link->next;
+ }
+
+ link->next = NULL;
+ link->prev = NULL;
+}
+
+/**
+ * Removes a link from the list. This is a constant-time operation.
+ *
+ * @param list address of the list head.
+ * @param link the list link to remove.
+ */
+void
+_dbus_list_remove_link (DBusList **list,
+ DBusList *link)
+{
+ _dbus_list_unlink (list, link);
+ free_link (link);
+}
+
+/**
+ * Frees all links in the list and sets the list head to #NULL. Does
+ * not free the data in each link, for obvious reasons. This is a
+ * linear-time operation.
+ *
+ * @param list address of the list head.
+ */
+void
+_dbus_list_clear (DBusList **list)
+{
+ DBusList *link;
+
+ link = *list;
+ while (link != NULL)
+ {
+ DBusList *next = _dbus_list_get_next_link (list, link);
+
+ free_link (link);
+
+ link = next;
+ }
+
+ *list = NULL;
+}
+
+/**
+ * Gets the first link in the list.
+ * This is a constant-time operation.
+ *
+ * @param list address of the list head.
+ * @returns the first link, or #NULL for an empty list.
+ */
+DBusList*
+_dbus_list_get_first_link (DBusList **list)
+{
+ return *list;
+}
+
+/**
+ * Gets the last link in the list.
+ * This is a constant-time operation.
+ *
+ * @param list address of the list head.
+ * @returns the last link, or #NULL for an empty list.
+ */
+DBusList*
+_dbus_list_get_last_link (DBusList **list)
+{
+ if (*list == NULL)
+ return NULL;
+ else
+ return (*list)->prev;
+}
+
+/**
+ * Gets the last data in the list.
+ * This is a constant-time operation.
+ *
+ * @param list address of the list head.
+ * @returns the last data in the list, or #NULL for an empty list.
+ */
+void*
+_dbus_list_get_last (DBusList **list)
+{
+ if (*list == NULL)
+ return NULL;
+ else
+ return (*list)->prev->data;
+}
+
+/**
+ * Gets the first data in the list.
+ * This is a constant-time operation.
+ *
+ * @param list address of the list head.
+ * @returns the first data in the list, or #NULL for an empty list.
+ */
+void*
+_dbus_list_get_first (DBusList **list)
+{
+ if (*list == NULL)
+ return NULL;
+ else
+ return (*list)->data;
+}
+
+/**
+ * Removes the first link in the list and returns it. This is a
+ * constant-time operation.
+ *
+ * @param list address of the list head.
+ * @returns the first link in the list, or #NULL for an empty list.
+ */
+DBusList*
+_dbus_list_pop_first_link (DBusList **list)
+{
+ DBusList *link;
+
+ link = _dbus_list_get_first_link (list);
+ if (link == NULL)
+ return NULL;
+
+ _dbus_list_unlink (list, link);
+
+ return link;
+}
+
+/**
+ * Removes the first value in the list and returns it. This is a
+ * constant-time operation.
+ *
+ * @param list address of the list head.
+ * @returns the first data in the list, or #NULL for an empty list.
+ */
+void*
+_dbus_list_pop_first (DBusList **list)
+{
+ DBusList *link;
+ void *data;
+
+ link = _dbus_list_get_first_link (list);
+ if (link == NULL)
+ return NULL;
+
+ data = link->data;
+ _dbus_list_remove_link (list, link);
+
+ return data;
+}
+
+/**
+ * Removes the last value in the list and returns it. This is a
+ * constant-time operation.
+ *
+ * @param list address of the list head.
+ * @returns the last data in the list, or #NULL for an empty list.
+ */
+void*
+_dbus_list_pop_last (DBusList **list)
+{
+ DBusList *link;
+ void *data;
+
+ link = _dbus_list_get_last_link (list);
+ if (link == NULL)
+ return NULL;
+
+ data = link->data;
+ _dbus_list_remove_link (list, link);
+
+ return data;
+}
+
+#ifdef DBUS_BUILD_TESTS
+/**
+ * Removes the last link in the list and returns it. This is a
+ * constant-time operation.
+ *
+ * @param list address of the list head.
+ * @returns the last link in the list, or #NULL for an empty list.
+ */
+DBusList*
+_dbus_list_pop_last_link (DBusList **list)
+{
+ DBusList *link;
+
+ link = _dbus_list_get_last_link (list);
+ if (link == NULL)
+ return NULL;
+
+ _dbus_list_unlink (list, link);
+
+ return link;
+}
+#endif /* DBUS_BUILD_TESTS */
+
+/**
+ * Copies a list. This is a linear-time operation. If there isn't
+ * enough memory to copy the entire list, the destination list will be
+ * set to #NULL.
+ *
+ * @param list address of the head of the list to copy.
+ * @param dest address where the copied list should be placed.
+ * @returns #TRUE on success, #FALSE if not enough memory.
+ */
+dbus_bool_t
+_dbus_list_copy (DBusList **list,
+ DBusList **dest)
+{
+ DBusList *link;
+
+ _dbus_assert (list != dest);
+
+ *dest = NULL;
+
+ link = *list;
+ while (link != NULL)
+ {
+ if (!_dbus_list_append (dest, link->data))
+ {
+ /* free what we have so far */
+ _dbus_list_clear (dest);
+ return FALSE;
+ }
+
+ link = _dbus_list_get_next_link (list, link);
+ }
+
+ return TRUE;
+}
+
+/**
+ * Gets the length of a list. This is a linear-time
+ * operation.
+ *
+ * @param list address of the head of the list
+ * @returns number of elements in the list.
+ */
+int
+_dbus_list_get_length (DBusList **list)
+{
+ DBusList *link;
+ int length;
+
+ length = 0;
+
+ link = *list;
+ while (link != NULL)
+ {
+ ++length;
+
+ link = _dbus_list_get_next_link (list, link);
+ }
+
+ return length;
+}
+
+/**
+ * Calls the given function for each element in the list. The
+ * function is passed the list element as its first argument, and the
+ * given data as its second argument.
+ *
+ * @param list address of the head of the list.
+ * @param function function to call for each element.
+ * @param data extra data for the function.
+ *
+ */
+void
+_dbus_list_foreach (DBusList **list,
+ DBusForeachFunction function,
+ void *data)
+{
+ DBusList *link;
+
+ link = *list;
+ while (link != NULL)
+ {
+ DBusList *next = _dbus_list_get_next_link (list, link);
+
+ (* function) (link->data, data);
+
+ link = next;
+ }
+}
+
+/**
+ * Check whether length is exactly one.
+ *
+ * @param list the list
+ * @returns #TRUE if length is exactly one
+ */
+dbus_bool_t
+_dbus_list_length_is_one (DBusList **list)
+{
+ return (*list != NULL &&
+ (*list)->next == *list);
+}
+
+/** @} */
+
+#ifdef DBUS_BUILD_TESTS
+#include "dbus-test.h"
+#include <stdio.h>
+
+static void
+verify_list (DBusList **list)
+{
+ DBusList *link;
+ int length;
+
+ link = *list;
+
+ if (link == NULL)
+ return;
+
+ if (link->next == link)
+ {
+ _dbus_assert (link->prev == link);
+ _dbus_assert (*list == link);
+ return;
+ }
+
+ length = 0;
+ do
+ {
+ length += 1;
+ _dbus_assert (link->prev->next == link);
+ _dbus_assert (link->next->prev == link);
+ link = link->next;
+ }
+ while (link != *list);
+
+ _dbus_assert (length == _dbus_list_get_length (list));
+
+ if (length == 1)
+ _dbus_assert (_dbus_list_length_is_one (list));
+ else
+ _dbus_assert (!_dbus_list_length_is_one (list));
+}
+
+static dbus_bool_t
+is_ascending_sequence (DBusList **list)
+{
+ DBusList *link;
+ int prev;
+
+ prev = _DBUS_INT_MIN;
+
+ link = _dbus_list_get_first_link (list);
+ while (link != NULL)
+ {
+ int v = _DBUS_POINTER_TO_INT (link->data);
+
+ if (v <= prev)
+ return FALSE;
+
+ prev = v;
+
+ link = _dbus_list_get_next_link (list, link);
+ }
+
+ return TRUE;
+}
+
+static dbus_bool_t
+is_descending_sequence (DBusList **list)
+{
+ DBusList *link;
+ int prev;
+
+ prev = _DBUS_INT_MAX;
+
+ link = _dbus_list_get_first_link (list);
+ while (link != NULL)
+ {
+ int v = _DBUS_POINTER_TO_INT (link->data);
+
+ if (v >= prev)
+ return FALSE;
+
+ prev = v;
+
+ link = _dbus_list_get_next_link (list, link);
+ }
+
+ return TRUE;
+}
+
+static dbus_bool_t
+all_even_values (DBusList **list)
+{
+ DBusList *link;
+
+ link = _dbus_list_get_first_link (list);
+ while (link != NULL)
+ {
+ int v = _DBUS_POINTER_TO_INT (link->data);
+
+ if ((v % 2) != 0)
+ return FALSE;
+
+ link = _dbus_list_get_next_link (list, link);
+ }
+
+ return TRUE;
+}
+
+static dbus_bool_t
+all_odd_values (DBusList **list)
+{
+ DBusList *link;
+
+ link = _dbus_list_get_first_link (list);
+ while (link != NULL)
+ {
+ int v = _DBUS_POINTER_TO_INT (link->data);
+
+ if ((v % 2) == 0)
+ return FALSE;
+
+ link = _dbus_list_get_next_link (list, link);
+ }
+
+ return TRUE;
+}
+
+static dbus_bool_t
+lists_equal (DBusList **list1,
+ DBusList **list2)
+{
+ DBusList *link1;
+ DBusList *link2;
+
+ link1 = _dbus_list_get_first_link (list1);
+ link2 = _dbus_list_get_first_link (list2);
+ while (link1 && link2)
+ {
+ if (link1->data != link2->data)
+ return FALSE;
+
+ link1 = _dbus_list_get_next_link (list1, link1);
+ link2 = _dbus_list_get_next_link (list2, link2);
+ }
+
+ if (link1 || link2)
+ return FALSE;
+
+ return TRUE;
+}
+
+/**
+ * @ingroup DBusListInternals
+ * Unit test for DBusList
+ * @returns #TRUE on success.
+ */
+dbus_bool_t
+_dbus_list_test (void)
+{
+ DBusList *list1;
+ DBusList *list2;
+ DBusList *link1;
+ DBusList *link2;
+ DBusList *copy1;
+ DBusList *copy2;
+ int i;
+
+ list1 = NULL;
+ list2 = NULL;
+
+ /* Test append and prepend */
+
+ i = 0;
+ while (i < 10)
+ {
+ if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
+ _dbus_assert_not_reached ("could not allocate for append");
+
+ if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
+ _dbus_assert_not_reached ("count not allocate for prepend");
+ ++i;
+
+ verify_list (&list1);
+ verify_list (&list2);
+
+ _dbus_assert (_dbus_list_get_length (&list1) == i);
+ _dbus_assert (_dbus_list_get_length (&list2) == i);
+ }
+
+ _dbus_assert (is_ascending_sequence (&list1));
+ _dbus_assert (is_descending_sequence (&list2));
+
+ /* Test list clear */
+ _dbus_list_clear (&list1);
+ _dbus_list_clear (&list2);
+
+ verify_list (&list1);
+ verify_list (&list2);
+
+ /* Test get_first, get_last, pop_first, pop_last */
+
+ i = 0;
+ while (i < 10)
+ {
+ _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
+ _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
+ ++i;
+ }
+
+ --i;
+ while (i >= 0)
+ {
+ void *got_data1;
+ void *got_data2;
+
+ void *data1;
+ void *data2;
+
+ got_data1 = _dbus_list_get_last (&list1);
+ got_data2 = _dbus_list_get_first (&list2);
+
+ data1 = _dbus_list_pop_last (&list1);
+ data2 = _dbus_list_pop_first (&list2);
+
+ _dbus_assert (got_data1 == data1);
+ _dbus_assert (got_data2 == data2);
+
+ _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
+ _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
+
+ verify_list (&list1);
+ verify_list (&list2);
+
+ _dbus_assert (is_ascending_sequence (&list1));
+ _dbus_assert (is_descending_sequence (&list2));
+
+ --i;
+ }
+
+ _dbus_assert (list1 == NULL);
+ _dbus_assert (list2 == NULL);
+
+ /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */
+
+ i = 0;
+ while (i < 10)
+ {
+ _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
+ _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
+ ++i;
+ }
+
+ --i;
+ while (i >= 0)
+ {
+ DBusList *got_link1;
+ DBusList *got_link2;
+
+ DBusList *link1;
+ DBusList *link2;
+
+ void *data1;
+ void *data2;
+
+ got_link1 = _dbus_list_get_last_link (&list1);
+ got_link2 = _dbus_list_get_first_link (&list2);
+
+ link1 = _dbus_list_pop_last_link (&list1);
+ link2 = _dbus_list_pop_first_link (&list2);
+
+ _dbus_assert (got_link1 == link1);
+ _dbus_assert (got_link2 == link2);
+
+ data1 = link1->data;
+ data2 = link2->data;
+
+ _dbus_list_free_link (link1);
+ _dbus_list_free_link (link2);
+
+ _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
+ _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
+
+ verify_list (&list1);
+ verify_list (&list2);
+
+ _dbus_assert (is_ascending_sequence (&list1));
+ _dbus_assert (is_descending_sequence (&list2));
+
+ --i;
+ }
+
+ _dbus_assert (list1 == NULL);
+ _dbus_assert (list2 == NULL);
+
+ /* Test iteration */
+
+ i = 0;
+ while (i < 10)
+ {
+ _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
+ _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
+ ++i;
+
+ verify_list (&list1);
+ verify_list (&list2);
+
+ _dbus_assert (_dbus_list_get_length (&list1) == i);
+ _dbus_assert (_dbus_list_get_length (&list2) == i);
+ }
+
+ _dbus_assert (is_ascending_sequence (&list1));
+ _dbus_assert (is_descending_sequence (&list2));
+
+ --i;
+ link2 = _dbus_list_get_first_link (&list2);
+ while (link2 != NULL)
+ {
+ verify_list (&link2); /* pretend this link is the head */
+
+ _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
+
+ link2 = _dbus_list_get_next_link (&list2, link2);
+ --i;
+ }
+
+ i = 0;
+ link1 = _dbus_list_get_first_link (&list1);
+ while (link1 != NULL)
+ {
+ verify_list (&link1); /* pretend this link is the head */
+
+ _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
+
+ link1 = _dbus_list_get_next_link (&list1, link1);
+ ++i;
+ }
+
+ --i;
+ link1 = _dbus_list_get_last_link (&list1);
+ while (link1 != NULL)
+ {
+ verify_list (&link1); /* pretend this link is the head */
+
+ _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
+
+ link1 = _dbus_list_get_prev_link (&list1, link1);
+ --i;
+ }
+
+ _dbus_list_clear (&list1);
+ _dbus_list_clear (&list2);
+
+ /* Test remove */
+
+ i = 0;
+ while (i < 10)
+ {
+ _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
+ _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
+ ++i;
+ }
+
+ --i;
+ while (i >= 0)
+ {
+ if ((i % 2) == 0)
+ {
+ if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
+ _dbus_assert_not_reached ("element should have been in list");
+ if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
+ _dbus_assert_not_reached ("element should have been in list");
+
+ verify_list (&list1);
+ verify_list (&list2);
+ }
+ --i;
+ }
+
+ _dbus_assert (all_odd_values (&list1));
+ _dbus_assert (all_odd_values (&list2));
+
+ _dbus_list_clear (&list1);
+ _dbus_list_clear (&list2);
+
+ /* test removing the other half of the elements */
+
+ i = 0;
+ while (i < 10)
+ {
+ _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
+ _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
+ ++i;
+ }
+
+ --i;
+ while (i >= 0)
+ {
+ if ((i % 2) != 0)
+ {
+ if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
+ _dbus_assert_not_reached ("element should have been in list");
+ if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
+ _dbus_assert_not_reached ("element should have been in list");
+
+ verify_list (&list1);
+ verify_list (&list2);
+ }
+ --i;
+ }
+
+ _dbus_assert (all_even_values (&list1));
+ _dbus_assert (all_even_values (&list2));
+
+ /* clear list using remove_link */
+ while (list1 != NULL)
+ {
+ _dbus_list_remove_link (&list1, list1);
+ verify_list (&list1);
+ }
+ while (list2 != NULL)
+ {
+ _dbus_list_remove_link (&list2, list2);
+ verify_list (&list2);
+ }
+
+ /* Test remove link more generally */
+ i = 0;
+ while (i < 10)
+ {
+ _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
+ _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
+ ++i;
+ }
+
+ --i;
+ link2 = _dbus_list_get_first_link (&list2);
+ while (link2 != NULL)
+ {
+ DBusList *next = _dbus_list_get_next_link (&list2, link2);
+
+ _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
+
+ if ((i % 2) == 0)
+ _dbus_list_remove_link (&list2, link2);
+
+ verify_list (&list2);
+
+ link2 = next;
+ --i;
+ }
+
+ _dbus_assert (all_odd_values (&list2));
+ _dbus_list_clear (&list2);
+
+ i = 0;
+ link1 = _dbus_list_get_first_link (&list1);
+ while (link1 != NULL)
+ {
+ DBusList *next = _dbus_list_get_next_link (&list1, link1);
+
+ _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
+
+ if ((i % 2) != 0)
+ _dbus_list_remove_link (&list1, link1);
+
+ verify_list (&list1);
+
+ link1 = next;
+ ++i;
+ }
+
+ _dbus_assert (all_even_values (&list1));
+ _dbus_list_clear (&list1);
+
+ /* Test copying a list */
+ i = 0;
+ while (i < 10)
+ {
+ _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
+ _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
+ ++i;
+ }
+
+ /* bad pointers, because they are allowed in the copy dest */
+ copy1 = _DBUS_INT_TO_POINTER (0x342234);
+ copy2 = _DBUS_INT_TO_POINTER (23);
+
+ _dbus_list_copy (&list1, ©1);
+ verify_list (&list1);
+ verify_list (©1);
+ _dbus_assert (lists_equal (&list1, ©1));
+
+ _dbus_list_copy (&list2, ©2);
+ verify_list (&list2);
+ verify_list (©2);
+ _dbus_assert (lists_equal (&list2, ©2));
+
+ /* Now test copying empty lists */
+ _dbus_list_clear (&list1);
+ _dbus_list_clear (&list2);
+ _dbus_list_clear (©1);
+ _dbus_list_clear (©2);
+
+ /* bad pointers, because they are allowed in the copy dest */
+ copy1 = _DBUS_INT_TO_POINTER (0x342234);
+ copy2 = _DBUS_INT_TO_POINTER (23);
+
+ _dbus_list_copy (&list1, ©1);
+ verify_list (&list1);
+ verify_list (©1);
+ _dbus_assert (lists_equal (&list1, ©1));
+
+ _dbus_list_copy (&list2, ©2);
+ verify_list (&list2);
+ verify_list (©2);
+ _dbus_assert (lists_equal (&list2, ©2));
+
+ _dbus_list_clear (&list1);
+ _dbus_list_clear (&list2);
+
+ /* insert_before on empty list */
+ _dbus_list_insert_before (&list1, NULL,
+ _DBUS_INT_TO_POINTER (0));
+ verify_list (&list1);
+
+ /* inserting before first element */
+ _dbus_list_insert_before (&list1, list1,
+ _DBUS_INT_TO_POINTER (2));
+ verify_list (&list1);
+ _dbus_assert (is_descending_sequence (&list1));
+
+ /* inserting in the middle */
+ _dbus_list_insert_before (&list1, list1->next,
+ _DBUS_INT_TO_POINTER (1));
+ verify_list (&list1);
+ _dbus_assert (is_descending_sequence (&list1));
+
+ /* using insert_before to append */
+ _dbus_list_insert_before (&list1, NULL,
+ _DBUS_INT_TO_POINTER (-1));
+ verify_list (&list1);
+ _dbus_assert (is_descending_sequence (&list1));
+
+ _dbus_list_clear (&list1);
+
+ /* insert_after on empty list */
+ _dbus_list_insert_after (&list1, NULL,
+ _DBUS_INT_TO_POINTER (0));
+ verify_list (&list1);
+
+ /* inserting after first element */
+ _dbus_list_insert_after (&list1, list1,
+ _DBUS_INT_TO_POINTER (1));
+ verify_list (&list1);
+ _dbus_assert (is_ascending_sequence (&list1));
+
+ /* inserting at the end */
+ _dbus_list_insert_after (&list1, list1->next,
+ _DBUS_INT_TO_POINTER (2));
+ verify_list (&list1);
+ _dbus_assert (is_ascending_sequence (&list1));
+
+ /* using insert_after to prepend */
+ _dbus_list_insert_after (&list1, NULL,
+ _DBUS_INT_TO_POINTER (-1));
+ verify_list (&list1);
+ _dbus_assert (is_ascending_sequence (&list1));
+
+ _dbus_list_clear (&list1);
+
+ /* using remove_last */
+ _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2));
+ _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1));
+ _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3));
+
+ _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2));
+
+ verify_list (&list1);
+ _dbus_assert (is_ascending_sequence (&list1));
+
+ _dbus_list_clear (&list1);
+
+ return TRUE;
+}
+
+#endif
projects / monky / blobdiff