dbus-list.c
/* -*- 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.
*
* SPDX-License-Identifier: AFL-2.1 OR GPL-2.0-or-later
*
* 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., 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-internal.h"
#include <dbus/dbus-test-tap.h>
/* Protected by _DBUS_LOCK (list) */
static DBusMemPool *list_pool;
/* 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;
if (!_DBUS_LOCK (list))
return FALSE;
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)
{
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_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;
}
}
#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
DBusList*
_dbus_list_alloc_link (void *data)
{
return alloc_link (data);
}
void
_dbus_list_free_link (DBusList *link)
{
free_link (link);
}
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;
}
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;
}
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;
}
void
_dbus_list_prepend_link (DBusList **list,
DBusList *link)
{
link_before (list, *list, link);
}
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;
}
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);
}
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);
}
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;
}
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;
}
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;
}
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;
}
void
_dbus_list_remove_link (DBusList **list,
DBusList *link)
{
_dbus_list_unlink (list, link);
free_link (link);
}
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;
}
void
_dbus_list_clear_full (DBusList **list,
DBusFreeFunction function)
{
DBusList *link;
link = *list;
while (link != NULL)
{
DBusList *next = _dbus_list_get_next_link (list, link);
function (link->data);
free_link (link);
link = next;
}
*list = NULL;
}
DBusList*
_dbus_list_get_first_link (DBusList **list)
{
return *list;
}
DBusList*
_dbus_list_get_last_link (DBusList **list)
{
if (*list == NULL)
return NULL;
else
return (*list)->prev;
}
void*
_dbus_list_get_last (DBusList **list)
{
if (*list == NULL)
return NULL;
else
return (*list)->prev->data;
}
void*
_dbus_list_get_first (DBusList **list)
{
if (*list == NULL)
return NULL;
else
return (*list)->data;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
}
dbus_bool_t
_dbus_list_length_is_one (DBusList **list)
{
return (*list != NULL &&
(*list)->next == *list);
}
_dbus_assert_not_reached
#define _dbus_assert_not_reached(explanation)
Aborts with an error message if called.
Definition dbus-internals.h:164
_dbus_assert
#define _dbus_assert(condition)
Aborts with an error message if the condition is false.
Definition dbus-internals.h:153
_DBUS_UNLOCK
#define _DBUS_UNLOCK(name)
Unlocks a global lock.
Definition dbus-internals.h:438
DBusForeachFunction
void(* DBusForeachFunction)(void *element, void *data)
Used to iterate over each item in a collection, such as a DBusList.
Definition dbus-internals.h:347
_DBUS_LOCK
#define _DBUS_LOCK(name)
Locks a global lock, initializing it first if necessary.
Definition dbus-internals.h:437
_dbus_list_get_first_link
DBusList * _dbus_list_get_first_link(DBusList **list)
Gets the first link in the list.
Definition dbus-list.c:597
_dbus_list_insert_before_link
void _dbus_list_insert_before_link(DBusList **list, DBusList *before_this_link, DBusList *link)
Inserts a link into the list before the given existing link.
Definition dbus-list.c:379
_dbus_list_copy
dbus_bool_t _dbus_list_copy(DBusList **list, DBusList **dest)
Copies a list.
Definition dbus-list.c:727
_dbus_list_pop_first_link
DBusList * _dbus_list_pop_first_link(DBusList **list)
Removes the first link in the list and returns it.
Definition dbus-list.c:658
_dbus_list_length_is_one
dbus_bool_t _dbus_list_length_is_one(DBusList **list)
Check whether length is exactly one.
Definition dbus-list.c:813
_dbus_list_get_last
void * _dbus_list_get_last(DBusList **list)
Gets the last data in the list.
Definition dbus-list.c:626
_dbus_list_remove
dbus_bool_t _dbus_list_remove(DBusList **list, void *data)
Removes a value from the list.
Definition dbus-list.c:418
_dbus_list_append_link
void _dbus_list_append_link(DBusList **list, DBusList *link)
Appends a link to the list.
Definition dbus-list.c:318
_dbus_list_insert_after_link
void _dbus_list_insert_after_link(DBusList **list, DBusList *after_this_link, DBusList *link)
Inserts a link into the list after the given existing link.
Definition dbus-list.c:397
_dbus_list_clear_full
void _dbus_list_clear_full(DBusList **list, DBusFreeFunction function)
Free every link and every element in the list.
Definition dbus-list.c:570
_dbus_list_insert_after
dbus_bool_t _dbus_list_insert_after(DBusList **list, DBusList *after_this_link, void *data)
Inserts data into the list after the given existing link.
Definition dbus-list.c:351
_dbus_list_remove_link
void _dbus_list_remove_link(DBusList **list, DBusList *link)
Removes a link from the list.
Definition dbus-list.c:530
_dbus_list_get_first
void * _dbus_list_get_first(DBusList **list)
Gets the first data in the list.
Definition dbus-list.c:642
_dbus_list_get_last_link
DBusList * _dbus_list_get_last_link(DBusList **list)
Gets the last link in the list.
Definition dbus-list.c:610
_dbus_list_unlink
void _dbus_list_unlink(DBusList **list, DBusList *link)
Removes the given link from the list, but doesn't free it.
Definition dbus-list.c:502
_dbus_list_find_last
DBusList * _dbus_list_find_last(DBusList **list, void *data)
Finds a value in the list.
Definition dbus-list.c:475
_dbus_list_pop_last
void * _dbus_list_pop_last(DBusList **list)
Removes the last value in the list and returns it.
Definition dbus-list.c:702
_dbus_list_get_prev_link
#define _dbus_list_get_prev_link(list, link)
Gets the previous link in the list, or NULL if there are no more links.
Definition dbus-list.h:122
_dbus_list_free_link
void _dbus_list_free_link(DBusList *link)
Frees a linked list node allocated with _dbus_list_alloc_link.
Definition dbus-list.c:257
_dbus_list_pop_first
void * _dbus_list_pop_first(DBusList **list)
Removes the first value in the list and returns it.
Definition dbus-list.c:679
_dbus_list_foreach
void _dbus_list_foreach(DBusList **list, DBusForeachFunction function, void *data)
Calls the given function for each element in the list.
Definition dbus-list.c:789
_dbus_list_get_length
int _dbus_list_get_length(DBusList **list)
Gets the length of a list.
Definition dbus-list.c:760
_dbus_list_clear
void _dbus_list_clear(DBusList **list)
Frees all links in the list and sets the list head to NULL.
Definition dbus-list.c:545
_dbus_list_prepend_link
void _dbus_list_prepend_link(DBusList **list, DBusList *link)
Prepends a link to the list.
Definition dbus-list.c:336
_dbus_list_prepend
dbus_bool_t _dbus_list_prepend(DBusList **list, void *data)
Prepends a value to the list.
Definition dbus-list.c:295
_dbus_list_alloc_link
DBusList * _dbus_list_alloc_link(void *data)
Allocates a linked list node.
Definition dbus-list.c:245
_dbus_list_remove_last
dbus_bool_t _dbus_list_remove_last(DBusList **list, void *data)
Removes a value from the list.
Definition dbus-list.c:449
_dbus_list_append
dbus_bool_t _dbus_list_append(DBusList **list, void *data)
Appends a value to the list.
Definition dbus-list.c:273
_dbus_list_get_next_link
#define _dbus_list_get_next_link(list, link)
Gets the next link in the list, or NULL if there are no more links.
Definition dbus-list.h:121
NULL
#define NULL
A null pointer, defined appropriately for C or C++.
Definition dbus-macros.h:51
TRUE
#define TRUE
Expands to "1".
Definition dbus-macros.h:41
FALSE
#define FALSE
Expands to "0".
Definition dbus-macros.h:44
_dbus_mem_pool_alloc
void * _dbus_mem_pool_alloc(DBusMemPool *pool)
Allocates an object from the memory pool.
Definition dbus-mempool.c:227
_dbus_mem_pool_dealloc
dbus_bool_t _dbus_mem_pool_dealloc(DBusMemPool *pool, void *element)
Deallocates an object previously created with _dbus_mem_pool_alloc().
Definition dbus-mempool.c:366
_dbus_mem_pool_free
void _dbus_mem_pool_free(DBusMemPool *pool)
Frees a memory pool (and all elements allocated from it).
Definition dbus-mempool.c:200
_dbus_mem_pool_new
DBusMemPool * _dbus_mem_pool_new(int element_size, dbus_bool_t zero_elements)
Creates a new memory pool, or returns NULL on failure.
Definition dbus-mempool.c:148
DBusFreeFunction
void(* DBusFreeFunction)(void *memory)
The type of a function which frees a block of memory.
Definition dbus-memory.h:65
dbus_uint32_t
unsigned int dbus_uint32_t
A 32-bit unsigned integer on all platforms.
Definition dbus-arch-deps.h:45
dbus_bool_t
dbus_uint32_t dbus_bool_t
A boolean, valid values are TRUE and FALSE.
Definition dbus-types.h:37
DBusList
A node in a linked list.
Definition dbus-list.h:37
DBusList::data
void * data
Data stored at this element.
Definition dbus-list.h:40
DBusList::next
DBusList * next
Next list node.
Definition dbus-list.h:39
DBusList::prev
DBusList * prev
Previous list node.
Definition dbus-list.h:38
DBusMemPool
Internals fields of DBusMemPool.
Definition dbus-mempool.c:109