-/* -*- mode: C; c-file-style: "gnu" -*- */
-/* dbus-list.c Generic linked list utility (internal to D-BUS implementation)
+/* -*- 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 1.2
+ * 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
*
* 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
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*
*/
+#include <config.h>
#include "dbus-internals.h"
#include "dbus-list.h"
#include "dbus-mempool.h"
-#include "dbus-threads.h"
+#include "dbus-threads-internal.h"
/**
* @defgroup DBusList Linked list
* Types and functions related to DBusList.
*/
+/* Protected by _DBUS_LOCK (list) */
static DBusMemPool *list_pool;
-static DBusMutex *list_pool_lock = NULL;
-
-/**
- * Initializes the global mutex used for allocating list nodes.
- *
- * @returns the mutex
- */
-DBusMutex *
-_dbus_list_init_lock (void)
-{
- list_pool_lock = dbus_mutex_new ();
- return list_pool_lock;
-}
/**
* @defgroup DBusListInternals Linked list implementation details
{
DBusList *link;
- if (!dbus_mutex_lock (list_pool_lock))
- return NULL;
-
- if (!list_pool)
+ if (!_DBUS_LOCK (list))
+ return FALSE;
+
+ if (list_pool == NULL)
{
list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE);
if (list_pool == NULL)
{
- dbus_mutex_unlock (list_pool_lock);
+ _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;
}
}
-
- link = _dbus_mem_pool_alloc (list_pool);
+ else
+ {
+ link = _dbus_mem_pool_alloc (list_pool);
+ }
+
if (link)
link->data = data;
- dbus_mutex_unlock (list_pool_lock);
+ _DBUS_UNLOCK (list);
return link;
}
static void
free_link (DBusList *link)
-{
- dbus_mutex_lock (list_pool_lock);
+{
+ if (!_DBUS_LOCK (list))
+ _dbus_assert_not_reached ("we should have initialized global locks "
+ "before we allocated a linked-list link");
+
if (_dbus_mem_pool_dealloc (list_pool, link))
{
_dbus_mem_pool_free (list_pool);
list_pool = NULL;
}
- dbus_mutex_unlock (list_pool_lock);
+
+ _DBUS_UNLOCK (list);
}
static void
}
}
+#ifdef DBUS_ENABLE_STATS
+void
+_dbus_list_get_stats (dbus_uint32_t *in_use_p,
+ dbus_uint32_t *in_free_list_p,
+ dbus_uint32_t *allocated_p)
+{
+ if (!_DBUS_LOCK (list))
+ {
+ *in_use_p = 0;
+ *in_free_list_p = 0;
+ *allocated_p = 0;
+ return;
+ }
+
+ _dbus_mem_pool_get_stats (list_pool, in_use_p, in_free_list_p, allocated_p);
+ _DBUS_UNLOCK (list);
+}
+#endif
+
/** @} */
/**
}
/**
- * 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
}
/**
+ * 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.
{
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)
- {
- _dbus_list_remove_link (list, link);
- return TRUE;
- }
+ return link;
link = _dbus_list_get_prev_link (list, link);
}
- return FALSE;
+ return NULL;
}
-static void
+/**
+ * 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 (*list == link)
*list = link->next;
}
+
+ link->next = NULL;
+ link->prev = NULL;
}
/**
/** @} */
-#ifdef DBUS_BUILD_TESTS
+#ifdef DBUS_ENABLE_EMBEDDED_TESTS
#include "dbus-test.h"
#include <stdio.h>
_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 *link2;
+
+ void *data1_indirect;
+ void *data1;
+ void *data2;
+
+ got_link1 = _dbus_list_get_last_link (&list1);
+ got_link2 = _dbus_list_get_first_link (&list2);
+
+ link2 = _dbus_list_pop_first_link (&list2);
+
+ _dbus_assert (got_link2 == link2);
+
+ data1_indirect = got_link1->data;
+ /* this call makes got_link1 invalid */
+ data1 = _dbus_list_pop_last (&list1);
+ _dbus_assert (data1 == data1_indirect);
+ data2 = link2->data;
+
+ _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;
_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,
projects / platform / upstream / dbus.git / blobdiff