summaryrefslogtreecommitdiffstats
path: root/dbus
diff options
context:
space:
mode:
authorHavoc Pennington <hp@redhat.com>2002-11-23 19:56:30 +0000
committerHavoc Pennington <hp@redhat.com>2002-11-23 19:56:30 +0000
commit576cdb6e0b1274e9fa5276e01337aef330dd4e8c (patch)
tree6904e387bd7f70f0452abe8b4359f66070965d33 /dbus
parentf09921965c769ff6411ae2f684f6b855d4c8f38d (diff)
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.
Diffstat (limited to 'dbus')
-rw-r--r--dbus/Makefile.am4
-rw-r--r--dbus/dbus-hash.c27
-rw-r--r--dbus/dbus-hash.h4
-rw-r--r--dbus/dbus-internals.c11
-rw-r--r--dbus/dbus-internals.h3
-rw-r--r--dbus/dbus-list.c1029
-rw-r--r--dbus/dbus-list.h73
-rw-r--r--dbus/dbus-test.c13
-rw-r--r--dbus/dbus-test.h1
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 */