diff options
Diffstat (limited to 'dbus')
| -rw-r--r-- | dbus/Makefile.am | 4 | ||||
| -rw-r--r-- | dbus/dbus-hash.c | 27 | ||||
| -rw-r--r-- | dbus/dbus-hash.h | 4 | ||||
| -rw-r--r-- | dbus/dbus-internals.c | 11 | ||||
| -rw-r--r-- | dbus/dbus-internals.h | 3 | ||||
| -rw-r--r-- | dbus/dbus-list.c | 1029 | ||||
| -rw-r--r-- | dbus/dbus-list.h | 73 | ||||
| -rw-r--r-- | dbus/dbus-test.c | 13 | ||||
| -rw-r--r-- | dbus/dbus-test.h | 1 |
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, ©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); + + 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 */ |