+++ /dev/null
-/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
-/* 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 2.1
- *
- * 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"
-#include "dbus-mempool.h"
-#include "dbus-threads-internal.h"
-
-/**
- * @defgroup DBusList Linked list
- * @ingroup DBusInternals
- * @brief DBusList data structure
- *
- * Types and functions related to DBusList.
- */
-
-static DBusMemPool *list_pool;
-_DBUS_DEFINE_GLOBAL_LOCK (list);
-
-/**
- * @defgroup DBusListInternals Linked list implementation details
- * @ingroup DBusInternals
- * @brief DBusList implementation details
- *
- * The guts of DBusList.
- *
- * @{
- */
-
-/* the mem pool is probably a speed hit, with the thread
- * lock, though it does still save memory - unknown.
- */
-static DBusList*
-alloc_link (void *data)
-{
- DBusList *link;
-
- _DBUS_LOCK (list);
-
- if (list_pool == NULL)
- {
- list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE);
-
- if (list_pool == NULL)
- {
- _DBUS_UNLOCK (list);
- return NULL;
- }
-
- link = _dbus_mem_pool_alloc (list_pool);
- if (link == NULL)
- {
- _dbus_mem_pool_free (list_pool);
- list_pool = NULL;
- _DBUS_UNLOCK (list);
- return NULL;
- }
- }
- else
- {
- link = _dbus_mem_pool_alloc (list_pool);
- }
-
- if (link)
- link->data = data;
-
- _DBUS_UNLOCK (list);
-
- return link;
-}
-
-static void
-free_link (DBusList *link)
-{
- _DBUS_LOCK (list);
- if (_dbus_mem_pool_dealloc (list_pool, link))
- {
- _dbus_mem_pool_free (list_pool);
- list_pool = NULL;
- }
-
- _DBUS_UNLOCK (list);
-}
-
-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 (&link);
- * }
- * @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 (&link);
- * }
- * @endcode
- *
- * @param list address of the list head.
- * @param link current link.
- * @returns the previous link, or %NULL if none.
- *
- */
-
-/**
- * Allocates a linked list node. Useful for preallocating
- * nodes and using _dbus_list_append_link() to avoid
- * allocations.
- *
- * @param data the value to store in the link.
- * @returns a newly allocated link.
- */
-DBusList*
-_dbus_list_alloc_link (void *data)
-{
- return alloc_link (data);
-}
-
-/**
- * Frees a linked list node allocated with _dbus_list_alloc_link.
- * Does not free the data in the node.
- *
- * @param link the list node
- */
-void
-_dbus_list_free_link (DBusList *link)
-{
- free_link (link);
-}
-
-
-/**
- * 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;
-}
-
-/**
- * Appends a link to the list.
- * Cannot fail due to out of memory.
- * This is a constant-time operation.
- *
- * @param list address of the list head.
- * @param link the link to append.
- */
-void
-_dbus_list_append_link (DBusList **list,
- DBusList *link)
-{
- _dbus_list_prepend_link (list, link);
-
- /* Now cycle the list forward one so the prepended node is the tail */
- *list = (*list)->next;
-}
-
-/**
- * Prepends a link to the list.
- * Cannot fail due to out of memory.
- * This is a constant-time operation.
- *
- * @param list address of the list head.
- * @param link the link to prepend.
- */
-void
-_dbus_list_prepend_link (DBusList **list,
- DBusList *link)
-{
- link_before (list, *list, link);
-}
-
-#ifdef DBUS_BUILD_TESTS
-/**
- * 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;
-}
-#endif /* DBUS_BUILD_TESTS */
-
-/**
- * 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;
-}
-
-/**
- * Inserts a link 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 link the link to insert
- */
-void
-_dbus_list_insert_before_link (DBusList **list,
- DBusList *before_this_link,
- DBusList *link)
-{
- if (before_this_link == NULL)
- _dbus_list_append_link (list, link);
- else
- link_before (list, before_this_link, link);
-}
-
-/**
- * Inserts a link 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 link the link to insert
- */
-void
-_dbus_list_insert_after_link (DBusList **list,
- DBusList *after_this_link,
- DBusList *link)
-{
- if (after_this_link == NULL)
- _dbus_list_prepend_link (list, link);
- else
- link_after (list, after_this_link, link);
-}
-
-/**
- * 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 value from the list. Only removes the
- * last 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_last (DBusList **list,
- void *data)
-{
- DBusList *link;
-
- link = _dbus_list_find_last (list, data);
- if (link)
- {
- _dbus_list_remove_link (list, link);
- return TRUE;
- }
- else
- return FALSE;
-}
-
-/**
- * Finds a value in the list. Returns the last link
- * with value equal to the given data pointer.
- * This is a linear-time operation.
- * Returns #NULL if no value found that matches.
- *
- * @param list address of the list head.
- * @param data the value to find.
- * @returns the link if found
- */
-DBusList*
-_dbus_list_find_last (DBusList **list,
- void *data)
-{
- DBusList *link;
-
- link = _dbus_list_get_last_link (list);
-
- while (link != NULL)
- {
- if (link->data == data)
- return link;
-
- link = _dbus_list_get_prev_link (list, link);
- }
-
- return NULL;
-}
-
-/**
- * Removes the given link from the list, but doesn't
- * free it. _dbus_list_remove_link() both removes the
- * link and also frees it.
- *
- * @param list the list
- * @param link the link in the list
- */
-void
-_dbus_list_unlink (DBusList **list,
- DBusList *link)
-{
- if (link->next == link)
- {
- /* one-element list */
- *list = NULL;
- }
- else
- {
- link->prev->next = link->next;
- link->next->prev = link->prev;
-
- if (*list == link)
- *list = link->next;
- }
-
- link->next = NULL;
- link->prev = NULL;
-}
-
-/**
- * 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)
-{
- _dbus_list_unlink (list, link);
- 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 link in the list and returns it. This is a
- * constant-time operation.
- *
- * @param list address of the list head.
- * @returns the first link in the list, or #NULL for an empty list.
- */
-DBusList*
-_dbus_list_pop_first_link (DBusList **list)
-{
- DBusList *link;
-
- link = _dbus_list_get_first_link (list);
- if (link == NULL)
- return NULL;
-
- _dbus_list_unlink (list, link);
-
- return link;
-}
-
-/**
- * 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;
-}
-
-#ifdef DBUS_BUILD_TESTS
-/**
- * Removes the last link in the list and returns it. This is a
- * constant-time operation.
- *
- * @param list address of the list head.
- * @returns the last link in the list, or #NULL for an empty list.
- */
-DBusList*
-_dbus_list_pop_last_link (DBusList **list)
-{
- DBusList *link;
-
- link = _dbus_list_get_last_link (list);
- if (link == NULL)
- return NULL;
-
- _dbus_list_unlink (list, link);
-
- return link;
-}
-#endif /* DBUS_BUILD_TESTS */
-
-/**
- * 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;
-}
-
-/**
- * Calls the given function for each element in the list. The
- * function is passed the list element as its first argument, and the
- * given data as its second argument.
- *
- * @param list address of the head of the list.
- * @param function function to call for each element.
- * @param data extra data for the function.
- *
- */
-void
-_dbus_list_foreach (DBusList **list,
- DBusForeachFunction function,
- void *data)
-{
- DBusList *link;
-
- link = *list;
- while (link != NULL)
- {
- DBusList *next = _dbus_list_get_next_link (list, link);
-
- (* function) (link->data, data);
-
- link = next;
- }
-}
-
-/**
- * Check whether length is exactly one.
- *
- * @param list the list
- * @returns #TRUE if length is exactly one
- */
-dbus_bool_t
-_dbus_list_length_is_one (DBusList **list)
-{
- return (*list != NULL &&
- (*list)->next == *list);
-}
-
-/** @} */
-
-#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));
-
- if (length == 1)
- _dbus_assert (_dbus_list_length_is_one (list));
- else
- _dbus_assert (!_dbus_list_length_is_one (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 get_first_link, get_last_link, pop_first_link, pop_last_link */
-
- 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)
- {
- DBusList *got_link1;
- DBusList *got_link2;
-
- DBusList *link1;
- DBusList *link2;
-
- void *data1;
- void *data2;
-
- got_link1 = _dbus_list_get_last_link (&list1);
- got_link2 = _dbus_list_get_first_link (&list2);
-
- link1 = _dbus_list_pop_last_link (&list1);
- link2 = _dbus_list_pop_first_link (&list2);
-
- _dbus_assert (got_link1 == link1);
- _dbus_assert (got_link2 == link2);
-
- data1 = link1->data;
- data2 = link2->data;
-
- _dbus_list_free_link (link1);
- _dbus_list_free_link (link2);
-
- _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;
- }
-
- --i;
- link1 = _dbus_list_get_last_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_prev_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);
-
- /* using remove_last */
- _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2));
- _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1));
- _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3));
-
- _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2));
-
- verify_list (&list1);
- _dbus_assert (is_ascending_sequence (&list1));
-
- _dbus_list_clear (&list1);
-
- return TRUE;
-}
-
-#endif
projects / monky / blobdiff