diff options
Diffstat (limited to 'dbus/dbus-list.c')
| -rw-r--r-- | dbus/dbus-list.c | 1029 |
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, ©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 |