D-Bus 1.15.2
dbus-list.c
1/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
2/* dbus-list.c Generic linked list utility (internal to D-Bus implementation)
3 *
4 * Copyright (C) 2002 Red Hat, Inc.
5 *
6 * Licensed under the Academic Free License version 2.1
7 *
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21 *
22 */
23
24#include <config.h>
25#include "dbus-internals.h"
26#include "dbus-list.h"
27#include "dbus-mempool.h"
28#include "dbus-threads-internal.h"
29#include <dbus/dbus-test-tap.h>
30
39/* Protected by _DBUS_LOCK (list) */
40static DBusMemPool *list_pool;
41
52/* the mem pool is probably a speed hit, with the thread
53 * lock, though it does still save memory - unknown.
54 */
55static DBusList*
56alloc_link (void *data)
57{
58 DBusList *link;
59
60 if (!_DBUS_LOCK (list))
61 return FALSE;
62
63 if (list_pool == NULL)
64 {
65 list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE);
66
67 if (list_pool == NULL)
68 {
69 _DBUS_UNLOCK (list);
70 return NULL;
71 }
72
73 link = _dbus_mem_pool_alloc (list_pool);
74 if (link == NULL)
75 {
76 _dbus_mem_pool_free (list_pool);
77 list_pool = NULL;
78 _DBUS_UNLOCK (list);
79 return NULL;
80 }
81 }
82 else
83 {
84 link = _dbus_mem_pool_alloc (list_pool);
85 }
86
87 if (link)
88 link->data = data;
89
90 _DBUS_UNLOCK (list);
91
92 return link;
93}
94
95static void
96free_link (DBusList *link)
97{
98 if (!_DBUS_LOCK (list))
99 _dbus_assert_not_reached ("we should have initialized global locks "
100 "before we allocated a linked-list link");
101
102 if (_dbus_mem_pool_dealloc (list_pool, link))
103 {
104 _dbus_mem_pool_free (list_pool);
105 list_pool = NULL;
106 }
107
108 _DBUS_UNLOCK (list);
109}
110
111static void
112link_before (DBusList **list,
113 DBusList *before_this_link,
114 DBusList *link)
115{
116 if (*list == NULL)
117 {
118 link->prev = link;
119 link->next = link;
120 *list = link;
121 }
122 else
123 {
124 link->next = before_this_link;
125 link->prev = before_this_link->prev;
126 before_this_link->prev = link;
127 link->prev->next = link;
128
129 if (before_this_link == *list)
130 *list = link;
131 }
132}
133
134static void
135link_after (DBusList **list,
136 DBusList *after_this_link,
137 DBusList *link)
138{
139 if (*list == NULL)
140 {
141 link->prev = link;
142 link->next = link;
143 *list = link;
144 }
145 else
146 {
147 link->prev = after_this_link;
148 link->next = after_this_link->next;
149 after_this_link->next = link;
150 link->next->prev = link;
151 }
152}
153
154#ifdef DBUS_ENABLE_STATS
155void
156_dbus_list_get_stats (dbus_uint32_t *in_use_p,
157 dbus_uint32_t *in_free_list_p,
158 dbus_uint32_t *allocated_p)
159{
160 if (!_DBUS_LOCK (list))
161 {
162 *in_use_p = 0;
163 *in_free_list_p = 0;
164 *allocated_p = 0;
165 return;
166 }
167
168 _dbus_mem_pool_get_stats (list_pool, in_use_p, in_free_list_p, allocated_p);
169 _DBUS_UNLOCK (list);
170}
171#endif
172
244{
245 return alloc_link (data);
246}
247
254void
256{
257 free_link (link);
258}
259
260
272 void *data)
273{
274 if (!_dbus_list_prepend (list, data))
275 return FALSE;
276
277 /* Now cycle the list forward one so the prepended node is the tail */
278 *list = (*list)->next;
279
280 return TRUE;
281}
282
294 void *data)
295{
296 DBusList *link;
297
298 link = alloc_link (data);
299 if (link == NULL)
300 return FALSE;
301
302 link_before (list, *list, link);
303
304 return TRUE;
305}
306
315void
317 DBusList *link)
318{
319 _dbus_list_prepend_link (list, link);
320
321 /* Now cycle the list forward one so the prepended node is the tail */
322 *list = (*list)->next;
323}
324
333void
335 DBusList *link)
336{
337 link_before (list, *list, link);
338}
339
350 DBusList *after_this_link,
351 void *data)
352{
353 DBusList *link;
354
355 if (after_this_link == NULL)
356 return _dbus_list_prepend (list, data);
357 else
358 {
359 link = alloc_link (data);
360 if (link == NULL)
361 return FALSE;
362
363 link_after (list, after_this_link, link);
364 }
365
366 return TRUE;
367}
368
376void
378 DBusList *before_this_link,
379 DBusList *link)
380{
381 if (before_this_link == NULL)
382 _dbus_list_append_link (list, link);
383 else
384 link_before (list, before_this_link, link);
385}
386
394void
396 DBusList *after_this_link,
397 DBusList *link)
398{
399 if (after_this_link == NULL)
400 _dbus_list_prepend_link (list, link);
401 else
402 link_after (list, after_this_link, link);
403}
404
417 void *data)
418{
419 DBusList *link;
420
421 link = *list;
422 while (link != NULL)
423 {
424 if (link->data == data)
425 {
426 _dbus_list_remove_link (list, link);
427 return TRUE;
428 }
429
430 link = _dbus_list_get_next_link (list, link);
431 }
432
433 return FALSE;
434}
435
448 void *data)
449{
450 DBusList *link;
451
452 link = _dbus_list_find_last (list, data);
453 if (link)
454 {
455 _dbus_list_remove_link (list, link);
456 return TRUE;
457 }
458 else
459 return FALSE;
460}
461
474 void *data)
475{
476 DBusList *link;
477
478 link = _dbus_list_get_last_link (list);
479
480 while (link != NULL)
481 {
482 if (link->data == data)
483 return link;
484
485 link = _dbus_list_get_prev_link (list, link);
486 }
487
488 return NULL;
489}
490
499void
501 DBusList *link)
502{
503 if (link->next == link)
504 {
505 /* one-element list */
506 *list = NULL;
507 }
508 else
509 {
510 link->prev->next = link->next;
511 link->next->prev = link->prev;
512
513 if (*list == link)
514 *list = link->next;
515 }
516
517 link->next = NULL;
518 link->prev = NULL;
519}
520
527void
529 DBusList *link)
530{
531 _dbus_list_unlink (list, link);
532 free_link (link);
533}
534
542void
544{
545 DBusList *link;
546
547 link = *list;
548 while (link != NULL)
549 {
550 DBusList *next = _dbus_list_get_next_link (list, link);
551
552 free_link (link);
553
554 link = next;
555 }
556
557 *list = NULL;
558}
559
567void
569 DBusFreeFunction function)
570{
571 DBusList *link;
572
573 link = *list;
574 while (link != NULL)
575 {
576 DBusList *next = _dbus_list_get_next_link (list, link);
577
578 function (link->data);
579 free_link (link);
580
581 link = next;
582 }
583
584 *list = NULL;
585}
586
596{
597 return *list;
598}
599
609{
610 if (*list == NULL)
611 return NULL;
612 else
613 return (*list)->prev;
614}
615
623void*
625{
626 if (*list == NULL)
627 return NULL;
628 else
629 return (*list)->prev->data;
630}
631
639void*
641{
642 if (*list == NULL)
643 return NULL;
644 else
645 return (*list)->data;
646}
647
657{
658 DBusList *link;
659
660 link = _dbus_list_get_first_link (list);
661 if (link == NULL)
662 return NULL;
663
664 _dbus_list_unlink (list, link);
665
666 return link;
667}
668
676void*
678{
679 DBusList *link;
680 void *data;
681
682 link = _dbus_list_get_first_link (list);
683 if (link == NULL)
684 return NULL;
685
686 data = link->data;
687 _dbus_list_remove_link (list, link);
688
689 return data;
690}
691
699void*
701{
702 DBusList *link;
703 void *data;
704
705 link = _dbus_list_get_last_link (list);
706 if (link == NULL)
707 return NULL;
708
709 data = link->data;
710 _dbus_list_remove_link (list, link);
711
712 return data;
713}
714
726 DBusList **dest)
727{
728 DBusList *link;
729
730 _dbus_assert (list != dest);
731
732 *dest = NULL;
733
734 link = *list;
735 while (link != NULL)
736 {
737 if (!_dbus_list_append (dest, link->data))
738 {
739 /* free what we have so far */
740 _dbus_list_clear (dest);
741 return FALSE;
742 }
743
744 link = _dbus_list_get_next_link (list, link);
745 }
746
747 return TRUE;
748}
749
757int
759{
760 DBusList *link;
761 int length;
762
763 length = 0;
764
765 link = *list;
766 while (link != NULL)
767 {
768 ++length;
769
770 link = _dbus_list_get_next_link (list, link);
771 }
772
773 return length;
774}
775
786void
788 DBusForeachFunction function,
789 void *data)
790{
791 DBusList *link;
792
793 link = *list;
794 while (link != NULL)
795 {
796 DBusList *next = _dbus_list_get_next_link (list, link);
797
798 (* function) (link->data, data);
799
800 link = next;
801 }
802}
803
812{
813 return (*list != NULL &&
814 (*list)->next == *list);
815}
816
#define _dbus_assert_not_reached(explanation)
Aborts with an error message if called.
#define _dbus_assert(condition)
Aborts with an error message if the condition is false.
#define _DBUS_UNLOCK(name)
Unlocks a global lock.
#define _DBUS_LOCK(name)
Locks a global lock, initializing it first if necessary.
void(* DBusForeachFunction)(void *element, void *data)
Used to iterate over each item in a collection, such as a DBusList.
DBusList * _dbus_list_get_first_link(DBusList **list)
Gets the first link in the list.
Definition: dbus-list.c:595
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:377
dbus_bool_t _dbus_list_copy(DBusList **list, DBusList **dest)
Copies a list.
Definition: dbus-list.c:725
DBusList * _dbus_list_pop_first_link(DBusList **list)
Removes the first link in the list and returns it.
Definition: dbus-list.c:656
dbus_bool_t _dbus_list_length_is_one(DBusList **list)
Check whether length is exactly one.
Definition: dbus-list.c:811
void * _dbus_list_get_last(DBusList **list)
Gets the last data in the list.
Definition: dbus-list.c:624
dbus_bool_t _dbus_list_remove(DBusList **list, void *data)
Removes a value from the list.
Definition: dbus-list.c:416
void _dbus_list_append_link(DBusList **list, DBusList *link)
Appends a link to the list.
Definition: dbus-list.c:316
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:395
void _dbus_list_clear_full(DBusList **list, DBusFreeFunction function)
Free every link and every element in the list.
Definition: dbus-list.c:568
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:349
void _dbus_list_remove_link(DBusList **list, DBusList *link)
Removes a link from the list.
Definition: dbus-list.c:528
void * _dbus_list_get_first(DBusList **list)
Gets the first data in the list.
Definition: dbus-list.c:640
DBusList * _dbus_list_get_last_link(DBusList **list)
Gets the last link in the list.
Definition: dbus-list.c:608
void _dbus_list_unlink(DBusList **list, DBusList *link)
Removes the given link from the list, but doesn't free it.
Definition: dbus-list.c:500
DBusList * _dbus_list_find_last(DBusList **list, void *data)
Finds a value in the list.
Definition: dbus-list.c:473
void * _dbus_list_pop_last(DBusList **list)
Removes the last value in the list and returns it.
Definition: dbus-list.c:700
#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:120
void _dbus_list_free_link(DBusList *link)
Frees a linked list node allocated with _dbus_list_alloc_link.
Definition: dbus-list.c:255
void * _dbus_list_pop_first(DBusList **list)
Removes the first value in the list and returns it.
Definition: dbus-list.c:677
void _dbus_list_foreach(DBusList **list, DBusForeachFunction function, void *data)
Calls the given function for each element in the list.
Definition: dbus-list.c:787
int _dbus_list_get_length(DBusList **list)
Gets the length of a list.
Definition: dbus-list.c:758
void _dbus_list_clear(DBusList **list)
Frees all links in the list and sets the list head to NULL.
Definition: dbus-list.c:543
void _dbus_list_prepend_link(DBusList **list, DBusList *link)
Prepends a link to the list.
Definition: dbus-list.c:334
dbus_bool_t _dbus_list_prepend(DBusList **list, void *data)
Prepends a value to the list.
Definition: dbus-list.c:293
DBusList * _dbus_list_alloc_link(void *data)
Allocates a linked list node.
Definition: dbus-list.c:243
dbus_bool_t _dbus_list_remove_last(DBusList **list, void *data)
Removes a value from the list.
Definition: dbus-list.c:447
dbus_bool_t _dbus_list_append(DBusList **list, void *data)
Appends a value to the list.
Definition: dbus-list.c:271
#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:119
#define NULL
A null pointer, defined appropriately for C or C++.
#define TRUE
Expands to "1".
#define FALSE
Expands to "0".
void * _dbus_mem_pool_alloc(DBusMemPool *pool)
Allocates an object from the memory pool.
Definition: dbus-mempool.c:225
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:364
void _dbus_mem_pool_free(DBusMemPool *pool)
Frees a memory pool (and all elements allocated from it).
Definition: dbus-mempool.c:198
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:146
void(* DBusFreeFunction)(void *memory)
The type of a function which frees a block of memory.
Definition: dbus-memory.h:63
dbus_uint32_t dbus_bool_t
A boolean, valid values are TRUE and FALSE.
Definition: dbus-types.h:35
unsigned int dbus_uint32_t
A 32-bit unsigned integer on all platforms.
A node in a linked list.
Definition: dbus-list.h:35
void * data
Data stored at this element.
Definition: dbus-list.h:38
DBusList * next
Next list node.
Definition: dbus-list.h:37
DBusList * prev
Previous list node.
Definition: dbus-list.h:36
Internals fields of DBusMemPool.
Definition: dbus-mempool.c:107