2002-11-23 Havoc Pennington <hp@pobox.com>

	* dbus/dbus-internals.h (_DBUS_INT_MAX): add _DBUS_INT_MIN
	_DBUS_INT_MAX

	* dbus/dbus-test.c (main): add list test, and include
	dbus-test.h as intended

	* dbus/dbus-hash.c (_dbus_hash_table_remove_string)
	(_dbus_hash_table_remove_int): return value indicates
	whether the entry existed to remove

	* dbus/dbus-list.c: add linked list utility class,
	with docs and tests

	* dbus/dbus-hash.c: add TODO item about shrinking the hash bucket
	array sometimes.

1 files changed, 1029 insertions, 0 deletions

diff --git a/dbus/dbus-list.c b/dbus/dbus-list.c
new file mode 100644
index 00000000..0b8e5a4e
--- /dev/null
+++ b/dbus/dbus-list.c
@@ -0,0 +1,1029 @@
+/* -*- mode: C; c-file-style: "gnu" -*- */
+/* 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 1.2
+ * 
+ * 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"
+
+/**
+ * @defgroup DBusList Linked list
+ * @ingroup  DBusInternals
+ * @brief DBusList data structure
+ *
+ * Types and functions related to DBusList.
+ */
+
+/**
+ * @defgroup DBusListInternals Linked list implementation details
+ * @ingroup  DBusInternals
+ * @brief DBusList implementation details
+ *
+ * The guts of DBusList.
+ *
+ * @todo should use a memory pool for the list nodes, to avoid
+ * a memory allocation for every link.
+ * @{
+ */
+
+static DBusList*
+alloc_link (void *data)
+{
+  DBusList *link;
+
+  link = dbus_new0 (DBusList, 1);
+  link->data = data;
+
+  return link;
+}
+
+static void
+free_link (DBusList *link)
+{
+  dbus_free (link);
+}
+
+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 (&list);
+ *   }
+ * @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 (&list);
+ *   }
+ * @endcode
+ *
+ * @param list address of the list head.
+ * @param link current link.
+ * @returns the previous link, or %NULL if none.
+ * 
+ */
+
+/**
+ * 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;
+}
+
+/**
+ * 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;
+}
+
+/**
+ * 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;
+}
+
+/**
+ * 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 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)
+{
+  if (link->next == link)
+    {
+      /* one-element list */
+      *list = NULL;
+      free_link (link);
+    }
+  else
+    {      
+      link->prev->next = link->next;
+      link->next->prev = link->prev;
+      
+      if (*list == link)
+        *list = link->next;
+
+      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 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;
+}
+
+/**
+ * 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;
+}
+
+/** @} */
+
+#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));
+}
+
+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 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;
+    }
+  
+  _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, &copy1);
+  verify_list (&list1);
+  verify_list (&copy1);
+  _dbus_assert (lists_equal (&list1, &copy1));
+  
+  _dbus_list_copy (&list2, &copy2);
+  verify_list (&list2);
+  verify_list (&copy2);
+  _dbus_assert (lists_equal (&list2, &copy2));
+
+  /* Now test copying empty lists */
+  _dbus_list_clear (&list1);
+  _dbus_list_clear (&list2);
+  _dbus_list_clear (&copy1);
+  _dbus_list_clear (&copy2);
+  
+  /* 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, &copy1);
+  verify_list (&list1);
+  verify_list (&copy1);
+  _dbus_assert (lists_equal (&list1, &copy1));
+  
+  _dbus_list_copy (&list2, &copy2);
+  verify_list (&list2);
+  verify_list (&copy2);
+  _dbus_assert (lists_equal (&list2, &copy2));
+
+  _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);
+
+  return TRUE;
+}
+
+#endif