X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=dbus%2Fdbus-list.c;h=c4c1856f9f16403c418907eb2fd83774188b1eec;hb=bb8dd7fec5389db4df9b5e8863974149e8a650dc;hp=4c530dc79665a8b68855a856f971d88114bcd90f;hpb=ce173b29fc1e9432cb5956952afdbe775da12415;p=platform%2Fupstream%2Fdbus.git diff --git a/dbus/dbus-list.c b/dbus/dbus-list.c index 4c530dc..c4c1856 100644 --- a/dbus/dbus-list.c +++ b/dbus/dbus-list.c @@ -1,9 +1,9 @@ -/* -*- 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 @@ -17,14 +17,15 @@ * * 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 #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 @@ -34,20 +35,8 @@ * 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 @@ -67,39 +56,55 @@ alloc_link (void *data) { 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 @@ -145,6 +150,25 @@ link_after (DBusList **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) +{ + 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 + /** @} */ /** @@ -313,35 +337,6 @@ _dbus_list_prepend_link (DBusList **list, } /** - * 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 @@ -371,6 +366,42 @@ _dbus_list_insert_after (DBusList **list, } /** + * 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. @@ -417,23 +448,54 @@ _dbus_list_remove_last (DBusList **list, { 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) { @@ -450,6 +512,9 @@ _dbus_list_unlink (DBusList **list, if (*list == link) *list = link->next; } + + link->next = NULL; + link->prev = NULL; } /** @@ -723,7 +788,7 @@ _dbus_list_length_is_one (DBusList **list) /** @} */ -#ifdef DBUS_BUILD_TESTS +#ifdef DBUS_ENABLE_EMBEDDED_TESTS #include "dbus-test.h" #include @@ -964,6 +1029,58 @@ _dbus_list_test (void) _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; @@ -1189,31 +1306,6 @@ _dbus_list_test (void) _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,