D-Bus  1.13.16
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) */
40 static 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  */
55 static DBusList*
56 alloc_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 
95 static void
96 free_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 
111 static void
112 link_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 
134 static void
135 link_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
155 void
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 
242 DBusList*
244 {
245  return alloc_link (data);
246 }
247 
254 void
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 
315 void
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 
333 void
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 
376 void
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 
394 void
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 
472 DBusList*
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 
499 void
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 
527 void
529  DBusList *link)
530 {
531  _dbus_list_unlink (list, link);
532  free_link (link);
533 }
534 
542 void
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 
567 void
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 
594 DBusList*
596 {
597  return *list;
598 }
599 
607 DBusList*
609 {
610  if (*list == NULL)
611  return NULL;
612  else
613  return (*list)->prev;
614 }
615 
623 void*
625 {
626  if (*list == NULL)
627  return NULL;
628  else
629  return (*list)->prev->data;
630 }
631 
639 void*
641 {
642  if (*list == NULL)
643  return NULL;
644  else
645  return (*list)->data;
646 }
647 
655 DBusList*
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 
676 void*
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 
699 void*
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 
757 int
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 
786 void
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 
DBusList::next
DBusList * next
Next list node.
Definition: dbus-list.h:37
_dbus_list_get_last_link
DBusList * _dbus_list_get_last_link(DBusList **list)
Gets the last link in the list.
Definition: dbus-list.c:608
_dbus_list_find_last
DBusList * _dbus_list_find_last(DBusList **list, void *data)
Finds a value in the list.
Definition: dbus-list.c:473
_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:140
_dbus_list_prepend
dbus_bool_t _dbus_list_prepend(DBusList **list, void *data)
Prepends a value to the list.
Definition: dbus-list.c:293
_dbus_list_remove_link
void _dbus_list_remove_link(DBusList **list, DBusList *link)
Removes a link from the list.
Definition: dbus-list.c:528
_dbus_list_remove
dbus_bool_t _dbus_list_remove(DBusList **list, void *data)
Removes a value from the list.
Definition: dbus-list.c:416
_dbus_list_append_link
void _dbus_list_append_link(DBusList **list, DBusList *link)
Appends a link to the list.
Definition: dbus-list.c:316
_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:543
DBusFreeFunction
void(* DBusFreeFunction)(void *memory)
Definition: dbus-memory.h:63
_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:349
DBusMemPool
Internals fields of DBusMemPool.
Definition: dbus-mempool.c:100
_dbus_list_alloc_link
DBusList * _dbus_list_alloc_link(void *data)
Allocates a linked list node.
Definition: dbus-list.c:243
DBusList::prev
DBusList * prev
Previous list node.
Definition: dbus-list.h:36
_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:811
_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:377
_dbus_list_get_prev_link
#define _dbus_list_get_prev_link(list, link)
Definition: dbus-list.h:120
_DBUS_LOCK
#define _DBUS_LOCK(name)
Definition: dbus-internals.h:412
TRUE
#define TRUE
_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:656
_dbus_list_append
dbus_bool_t _dbus_list_append(DBusList **list, void *data)
Appends a value to the list.
Definition: dbus-list.c:271
_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:568
_dbus_list_copy
dbus_bool_t _dbus_list_copy(DBusList **list, DBusList **dest)
Copies a list.
Definition: dbus-list.c:725
_dbus_list_get_first
void * _dbus_list_get_first(DBusList **list)
Gets the first data in the list.
Definition: dbus-list.c:640
_dbus_list_get_next_link
#define _dbus_list_get_next_link(list, link)
Definition: dbus-list.h:119
_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:395
_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:677
_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:447
FALSE
#define FALSE
_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:349
DBusList::data
void * data
Data stored at this element.
Definition: dbus-list.h:38
_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:255
_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:189
_dbus_assert_not_reached
#define _dbus_assert_not_reached(explanation)
Definition: dbus-internals.h:164
_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:787
_dbus_list_prepend_link
void _dbus_list_prepend_link(DBusList **list, DBusList *link)
Prepends a link to the list.
Definition: dbus-list.c:334
_dbus_assert
#define _dbus_assert(condition)
Definition: dbus-internals.h:153
_dbus_list_get_length
int _dbus_list_get_length(DBusList **list)
Gets the length of a list.
Definition: dbus-list.c:758
DBusList
Definition: dbus-list.h:34
DBusForeachFunction
void(* DBusForeachFunction)(void *element, void *data)
Definition: dbus-internals.h:322
_dbus_mem_pool_alloc
void * _dbus_mem_pool_alloc(DBusMemPool *pool)
Allocates an object from the memory pool.
Definition: dbus-mempool.c:216
_DBUS_UNLOCK
#define _DBUS_UNLOCK(name)
Definition: dbus-internals.h:413
_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:700
_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:500
_dbus_list_get_last
void * _dbus_list_get_last(DBusList **list)
Gets the last data in the list.
Definition: dbus-list.c:624
_dbus_list_get_first_link
DBusList * _dbus_list_get_first_link(DBusList **list)
Gets the first link in the list.
Definition: dbus-list.c:595
dbus_bool_t
dbus_uint32_t dbus_bool_t
Definition: dbus-types.h:35
NULL
#define NULL