-/* -*- 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
{
DBusList *link;
- if (!_DBUS_LOCK (list))
- return NULL;
-
- if (!list_pool)
+ _DBUS_LOCK (list);
+
+ if (list_pool == NULL)
{
list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE);
_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;
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);
}
}
}
+#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)
+{
+ _DBUS_LOCK (list);
+ _dbus_mem_pool_get_stats (list_pool, in_use_p, in_free_list_p, allocated_p);
+ _DBUS_UNLOCK (list);
+}
+#endif
+
/** @} */
/**
link_before (list, *list, link);
}
+#ifdef DBUS_BUILD_TESTS
/**
* Inserts data into the list before the given existing link.
*
return TRUE;
}
+#endif /* DBUS_BUILD_TESTS */
/**
* Inserts data into the list after the given existing link.
}
/**
+ * 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;
}
/**
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
_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;