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.

9 files changed, 1150 insertions, 15 deletions

diff --git a/dbus/Makefile.am b/dbus/Makefile.am
index 56b519e2..46d703f0 100644
--- a/dbus/Makefile.am
+++ b/dbus/Makefile.am
@@ -26,7 +26,9 @@ libdbus_convenience_la_SOURCES=			\
 	dbus-hash.c				\
 	dbus-hash.h				\
 	dbus-internals.c			\
-	dbus-internals.h
+	dbus-internals.h			\
+	dbus-list.c				\
+	dbus-list.h
 
 libdbus_1_la_LIBADD=  $(DBUS_CLIENT_LIBS) libdbus-convenience.la
 ## don't export symbols that start with "_" (we use this 
diff --git a/dbus/dbus-hash.c b/dbus/dbus-hash.c
index 77fa95dc..48e96ca6 100644
--- a/dbus/dbus-hash.c
+++ b/dbus/dbus-hash.c
@@ -92,6 +92,13 @@
  *
  * The guts of DBusHashTable.
  *
+ * @todo rebuild_table() should be modified to also shrink the hash bucket
+ * array when appropriate; otherwise if a hash table has been
+ * very large but is now small, iteration becomes inefficient.
+ * We should still only shrink when adding hash entries though, not
+ * when removing them, so that you can still iterate over the hash
+ * removing entries. So if you added 5000, removed 4000, the
+ * shrinking would happen next time an entry was added.
  * @{
  */
 
@@ -929,8 +936,9 @@ _dbus_hash_table_lookup_int (DBusHashTable *table,
  *
  * @param table the hash table.
  * @param key the hash key.
+ * @returns #TRUE if the entry existed
  */
-void
+dbus_bool_t
 _dbus_hash_table_remove_string (DBusHashTable *table,
                                 const char    *key)
 {
@@ -942,7 +950,12 @@ _dbus_hash_table_remove_string (DBusHashTable *table,
   entry = (* table->find_function) (table, (char*) key, FALSE, &bucket);
 
   if (entry)
-    remove_entry (table, bucket, entry);
+    {
+      remove_entry (table, bucket, entry);
+      return TRUE;
+    }
+  else
+    return FALSE;
 }
 
 /**
@@ -951,8 +964,9 @@ _dbus_hash_table_remove_string (DBusHashTable *table,
  *
  * @param table the hash table.
  * @param key the hash key.
+ * @returns #TRUE if the entry existed
  */
-void
+dbus_bool_t
 _dbus_hash_table_remove_int (DBusHashTable *table,
                              int            key)
 {
@@ -964,7 +978,12 @@ _dbus_hash_table_remove_int (DBusHashTable *table,
   entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket);
   
   if (entry)
-    remove_entry (table, bucket, entry);
+    {
+      remove_entry (table, bucket, entry);
+      return TRUE;
+    }
+  else
+    return FALSE;
 }
 
 /**
diff --git a/dbus/dbus-hash.h b/dbus/dbus-hash.h
index b8136524..6c753a50 100644
--- a/dbus/dbus-hash.h
+++ b/dbus/dbus-hash.h
@@ -82,9 +82,9 @@ void*       _dbus_hash_table_lookup_string (DBusHashTable *table,
                                             const char    *key);
 void*       _dbus_hash_table_lookup_int    (DBusHashTable *table,
                                             int            key);
-void        _dbus_hash_table_remove_string (DBusHashTable *table,
+dbus_bool_t _dbus_hash_table_remove_string (DBusHashTable *table,
                                             const char    *key);
-void        _dbus_hash_table_remove_int    (DBusHashTable *table,
+dbus_bool_t _dbus_hash_table_remove_int    (DBusHashTable *table,
                                             int            key);
 dbus_bool_t _dbus_hash_table_insert_string (DBusHashTable *table,
                                             char          *key,
diff --git a/dbus/dbus-internals.c b/dbus/dbus-internals.c
index ac5552b6..238baa89 100644
--- a/dbus/dbus-internals.c
+++ b/dbus/dbus-internals.c
@@ -84,6 +84,17 @@
  */
 
 /**
+ * @def _DBUS_INT_MIN
+ *
+ * Minimum value of type "int"
+ */
+/**
+ * @def _DBUS_INT_MAX
+ *
+ * Maximum value of type "int"
+ */
+
+/**
  * Prints a warning message to stderr.
  *
  * @param format printf-style format string.
diff --git a/dbus/dbus-internals.h b/dbus/dbus-internals.h
index 6d0ac928..74bae96e 100644
--- a/dbus/dbus-internals.h
+++ b/dbus/dbus-internals.h
@@ -60,6 +60,9 @@ do {
 
 char* _dbus_strdup (const char *str);
 
+#define _DBUS_INT_MIN	(-_DBUS_INT_MAX - 1)
+#define _DBUS_INT_MAX	2147483647
+
 DBUS_END_DECLS;
 
 #endif /* DBUS_INTERNALS_H */
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
diff --git a/dbus/dbus-list.h b/dbus/dbus-list.h
new file mode 100644
index 00000000..d314ad5a
--- /dev/null
+++ b/dbus/dbus-list.h
@@ -0,0 +1,73 @@
+/* -*- mode: C; c-file-style: "gnu" -*- */
+/* dbus-list.h 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
+ *
+ */
+
+#ifndef DBUS_LIST_H
+#define DBUS_LIST_H
+
+#include <dbus/dbus-memory.h>
+#include <dbus/dbus-types.h>
+
+DBUS_BEGIN_DECLS;
+
+typedef struct DBusList DBusList;
+
+struct DBusList
+{
+  DBusList *prev; /**< Previous list node. */
+  DBusList *next; /**< Next list node. */
+  void     *data; /**< Data stored at this element. */
+};
+
+dbus_bool_t _dbus_list_append         (DBusList **list,
+                                       void      *data);
+dbus_bool_t _dbus_list_prepend        (DBusList **list,
+                                       void      *data);
+dbus_bool_t _dbus_list_insert_before  (DBusList **list,
+                                       DBusList  *before_this_link,
+                                       void      *data);
+dbus_bool_t _dbus_list_insert_after   (DBusList **list,
+                                       DBusList  *after_this_link,
+                                       void      *data);
+dbus_bool_t _dbus_list_remove         (DBusList **list,
+                                       void      *data);
+void        _dbus_list_remove_link    (DBusList **list,
+                                       DBusList  *link);
+void        _dbus_list_clear          (DBusList **list);
+DBusList*   _dbus_list_get_first_link (DBusList **list);
+DBusList*   _dbus_list_get_last_link  (DBusList **list);
+void*       _dbus_list_get_last       (DBusList **list);
+void*       _dbus_list_get_first      (DBusList **list);
+void*       _dbus_list_pop_first      (DBusList **list);
+void*       _dbus_list_pop_last       (DBusList **list);
+dbus_bool_t _dbus_list_copy           (DBusList **list,
+                                       DBusList **dest);
+int         _dbus_list_get_length     (DBusList **list);
+
+
+
+#define _dbus_list_get_next_link(list, link) ((link)->next == *(list) ? NULL : (link)->next)
+#define _dbus_list_get_prev_link(list, link) ((link)->prev == *(list) ? NULL : (link)->prev)
+
+DBUS_END_DECLS;
+
+#endif /* DBUS_LIST_H */
diff --git a/dbus/dbus-test.c b/dbus/dbus-test.c
index 2eb862e2..ad01fe0c 100644
--- a/dbus/dbus-test.c
+++ b/dbus/dbus-test.c
@@ -22,23 +22,20 @@
  */
 
 #include "dbus-types.h"
+#include "dbus-test.h"
 #include <stdio.h>
 
-/* To add a test, write a function like this one,
- * declare it here, define it in the file to be tested,
- * then call it from main() below. Test functions
- * should return FALSE on failure.
- */
-dbus_bool_t _dbus_hash_test (void);
-
 int
 main (int    argc,
       char **argv)
 {
+  printf ("%s: running linked list tests\n", argv[0]);
+  if (!_dbus_list_test ())
+    return 1;
+
   printf ("%s: running hash table tests\n", argv[0]);
   if (!_dbus_hash_test ())
     return 1;
-
   
   printf ("%s: completed successfully\n", argv[0]);
   return 0;
diff --git a/dbus/dbus-test.h b/dbus/dbus-test.h
index b3b49a57..29381a5a 100644
--- a/dbus/dbus-test.h
+++ b/dbus/dbus-test.h
@@ -27,5 +27,6 @@
 #include <dbus/dbus-types.h>
 
 dbus_bool_t _dbus_hash_test (void);
+dbus_bool_t _dbus_list_test (void);
 
 #endif /* DBUS_TEST_H */