1 /* -*- mode: C; c-file-style: "gnu" -*- */
2 /* dbus-list.c Generic linked list utility (internal to D-BUS implementation)
4 * Copyright (C) 2002 Red Hat, Inc.
6 * Licensed under the Academic Free License version 1.2
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.
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.
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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
24 #include "dbus-internals.h"
25 #include "dbus-list.h"
26 #include "dbus-mempool.h"
27 #include "dbus-threads.h"
30 * @defgroup DBusList Linked list
31 * @ingroup DBusInternals
32 * @brief DBusList data structure
34 * Types and functions related to DBusList.
37 static DBusMemPool *list_pool;
38 static DBusMutex *list_pool_lock = NULL;
41 * Initializes the global mutex used for allocating list nodes.
46 _dbus_list_init_lock (void)
48 list_pool_lock = dbus_mutex_new ();
49 return list_pool_lock;
53 * @defgroup DBusListInternals Linked list implementation details
54 * @ingroup DBusInternals
55 * @brief DBusList implementation details
57 * The guts of DBusList.
62 /* the mem pool is probably a speed hit, with the thread
63 * lock, though it does still save memory - unknown.
66 alloc_link (void *data)
70 if (!dbus_mutex_lock (list_pool_lock))
75 list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE);
77 if (list_pool == NULL)
79 dbus_mutex_unlock (list_pool_lock);
84 link = _dbus_mem_pool_alloc (list_pool);
88 dbus_mutex_unlock (list_pool_lock);
94 free_link (DBusList *link)
96 dbus_mutex_lock (list_pool_lock);
97 _dbus_mem_pool_dealloc (list_pool, link);
98 dbus_mutex_unlock (list_pool_lock);
102 link_before (DBusList **list,
103 DBusList *before_this_link,
114 link->next = before_this_link;
115 link->prev = before_this_link->prev;
116 before_this_link->prev = link;
117 link->prev->next = link;
119 if (before_this_link == *list)
125 link_after (DBusList **list,
126 DBusList *after_this_link,
137 link->prev = after_this_link;
138 link->next = after_this_link->next;
139 after_this_link->next = link;
140 link->next->prev = link;
147 * @addtogroup DBusList
154 * A node in a linked list.
156 * DBusList is a circular list; that is, the tail of the list
157 * points back to the head of the list. The empty list is
158 * represented by a #NULL pointer.
162 * @def _dbus_list_get_next_link
164 * Gets the next link in the list, or #NULL if
165 * there are no more links. Used for iteration.
169 * link = _dbus_list_get_first_link (&list);
170 * while (link != NULL)
172 * printf ("value is %p\n", link->data);
173 * link = _dbus_list_get_next_link (&link);
177 * @param list address of the list head.
178 * @param link current link.
179 * @returns the next link, or %NULL if none.
184 * @def _dbus_list_get_prev_link
186 * Gets the previous link in the list, or #NULL if
187 * there are no more links. Used for iteration.
191 * link = _dbus_list_get_last_link (&list);
192 * while (link != NULL)
194 * printf ("value is %p\n", link->data);
195 * link = _dbus_list_get_prev_link (&link);
199 * @param list address of the list head.
200 * @param link current link.
201 * @returns the previous link, or %NULL if none.
206 * Allocates a linked list node. Useful for preallocating
207 * nodes and using _dbus_list_append_link() to avoid
210 * @param data the value to store in the link.
211 * @returns a newly allocated link.
214 _dbus_list_alloc_link (void *data)
216 return alloc_link (data);
220 * Frees a linked list node allocated with _dbus_list_alloc_link.
221 * Does not free the data in the node.
223 * @param link the list node
226 _dbus_list_free_link (DBusList *link)
233 * Appends a value to the list. May return #FALSE
234 * if insufficient memory exists to add a list link.
235 * This is a constant-time operation.
237 * @param list address of the list head.
238 * @param data the value to append.
239 * @returns #TRUE on success.
242 _dbus_list_append (DBusList **list,
245 if (!_dbus_list_prepend (list, data))
248 /* Now cycle the list forward one so the prepended node is the tail */
249 *list = (*list)->next;
255 * Prepends a value to the list. May return #FALSE
256 * if insufficient memory exists to add a list link.
257 * This is a constant-time operation.
259 * @param list address of the list head.
260 * @param data the value to prepend.
261 * @returns #TRUE on success.
264 _dbus_list_prepend (DBusList **list,
269 link = alloc_link (data);
273 link_before (list, *list, link);
279 * Appends a link to the list.
280 * Cannot fail due to out of memory.
281 * This is a constant-time operation.
283 * @param list address of the list head.
284 * @param link the link to append.
287 _dbus_list_append_link (DBusList **list,
290 _dbus_list_prepend_link (list, link);
292 /* Now cycle the list forward one so the prepended node is the tail */
293 *list = (*list)->next;
297 * Prepends a link to the list.
298 * Cannot fail due to out of memory.
299 * This is a constant-time operation.
301 * @param list address of the list head.
302 * @param link the link to prepend.
305 _dbus_list_prepend_link (DBusList **list,
308 link_before (list, *list, link);
312 * Inserts data into the list before the given existing link.
314 * @param list the list to modify
315 * @param before_this_link existing link to insert before, or #NULL to append
316 * @param data the value to insert
317 * @returns #TRUE on success, #FALSE if memory allocation fails
320 _dbus_list_insert_before (DBusList **list,
321 DBusList *before_this_link,
326 if (before_this_link == NULL)
327 return _dbus_list_append (list, data);
330 link = alloc_link (data);
334 link_before (list, before_this_link, link);
341 * Inserts data into the list after the given existing link.
343 * @param list the list to modify
344 * @param after_this_link existing link to insert after, or #NULL to prepend
345 * @param data the value to insert
346 * @returns #TRUE on success, #FALSE if memory allocation fails
349 _dbus_list_insert_after (DBusList **list,
350 DBusList *after_this_link,
355 if (after_this_link == NULL)
356 return _dbus_list_prepend (list, data);
359 link = alloc_link (data);
363 link_after (list, after_this_link, link);
370 * Removes a value from the list. Only removes the
371 * first value equal to the given data pointer,
372 * even if multiple values exist which match.
373 * This is a linear-time operation.
375 * @param list address of the list head.
376 * @param data the value to remove.
377 * @returns #TRUE if a value was found to remove.
380 _dbus_list_remove (DBusList **list,
388 if (link->data == data)
390 _dbus_list_remove_link (list, link);
394 link = _dbus_list_get_next_link (list, link);
401 * Removes a value from the list. Only removes the
402 * last value equal to the given data pointer,
403 * even if multiple values exist which match.
404 * This is a linear-time operation.
406 * @param list address of the list head.
407 * @param data the value to remove.
408 * @returns #TRUE if a value was found to remove.
411 _dbus_list_remove_last (DBusList **list,
416 link = _dbus_list_get_last_link (list);
420 if (link->data == data)
422 _dbus_list_remove_link (list, link);
426 link = _dbus_list_get_prev_link (list, link);
433 * Removes a link from the list. This is a constant-time operation.
435 * @param list address of the list head.
436 * @param link the list link to remove.
439 _dbus_list_remove_link (DBusList **list,
442 if (link->next == link)
444 /* one-element list */
450 link->prev->next = link->next;
451 link->next->prev = link->prev;
461 * Frees all links in the list and sets the list head to #NULL. Does
462 * not free the data in each link, for obvious reasons. This is a
463 * linear-time operation.
465 * @param list address of the list head.
468 _dbus_list_clear (DBusList **list)
475 DBusList *next = _dbus_list_get_next_link (list, link);
486 * Gets the first link in the list.
487 * This is a constant-time operation.
489 * @param list address of the list head.
490 * @returns the first link, or #NULL for an empty list.
493 _dbus_list_get_first_link (DBusList **list)
499 * Gets the last link in the list.
500 * This is a constant-time operation.
502 * @param list address of the list head.
503 * @returns the last link, or #NULL for an empty list.
506 _dbus_list_get_last_link (DBusList **list)
511 return (*list)->prev;
515 * Gets the last data in the list.
516 * This is a constant-time operation.
518 * @param list address of the list head.
519 * @returns the last data in the list, or #NULL for an empty list.
522 _dbus_list_get_last (DBusList **list)
527 return (*list)->prev->data;
531 * Gets the first data in the list.
532 * This is a constant-time operation.
534 * @param list address of the list head.
535 * @returns the first data in the list, or #NULL for an empty list.
538 _dbus_list_get_first (DBusList **list)
543 return (*list)->data;
547 * Removes the first value in the list and returns it. This is a
548 * constant-time operation.
550 * @param list address of the list head.
551 * @returns the first data in the list, or #NULL for an empty list.
554 _dbus_list_pop_first (DBusList **list)
559 link = _dbus_list_get_first_link (list);
564 _dbus_list_remove_link (list, link);
570 * Removes the last value in the list and returns it. This is a
571 * constant-time operation.
573 * @param list address of the list head.
574 * @returns the last data in the list, or #NULL for an empty list.
577 _dbus_list_pop_last (DBusList **list)
582 link = _dbus_list_get_last_link (list);
587 _dbus_list_remove_link (list, link);
593 * Copies a list. This is a linear-time operation. If there isn't
594 * enough memory to copy the entire list, the destination list will be
597 * @param list address of the head of the list to copy.
598 * @param dest address where the copied list should be placed.
599 * @returns #TRUE on success, #FALSE if not enough memory.
602 _dbus_list_copy (DBusList **list,
607 _dbus_assert (list != dest);
614 if (!_dbus_list_append (dest, link->data))
616 /* free what we have so far */
617 _dbus_list_clear (dest);
621 link = _dbus_list_get_next_link (list, link);
628 * Gets the length of a list. This is a linear-time
631 * @param list address of the head of the list
632 * @returns number of elements in the list.
635 _dbus_list_get_length (DBusList **list)
647 link = _dbus_list_get_next_link (list, link);
654 * Calls the given function for each element in the list. The
655 * function is passed the list element as its first argument, and the
656 * given data as its second argument.
658 * @param list address of the head of the list.
659 * @param function function to call for each element.
660 * @param data extra data for the function.
664 _dbus_list_foreach (DBusList **list,
665 DBusForeachFunction function,
673 DBusList *next = _dbus_list_get_next_link (list, link);
675 (* function) (link->data, data);
682 * Check whether length is exactly one.
684 * @param list the list
685 * @returns #TRUE if length is exactly one
688 _dbus_list_length_is_one (DBusList **list)
690 return (*list != NULL &&
691 (*list)->next == *list);
696 #ifdef DBUS_BUILD_TESTS
697 #include "dbus-test.h"
701 verify_list (DBusList **list)
711 if (link->next == link)
713 _dbus_assert (link->prev == link);
714 _dbus_assert (*list == link);
722 _dbus_assert (link->prev->next == link);
723 _dbus_assert (link->next->prev == link);
726 while (link != *list);
728 _dbus_assert (length == _dbus_list_get_length (list));
731 _dbus_assert (_dbus_list_length_is_one (list));
733 _dbus_assert (!_dbus_list_length_is_one (list));
737 is_ascending_sequence (DBusList **list)
742 prev = _DBUS_INT_MIN;
744 link = _dbus_list_get_first_link (list);
747 int v = _DBUS_POINTER_TO_INT (link->data);
754 link = _dbus_list_get_next_link (list, link);
761 is_descending_sequence (DBusList **list)
766 prev = _DBUS_INT_MAX;
768 link = _dbus_list_get_first_link (list);
771 int v = _DBUS_POINTER_TO_INT (link->data);
778 link = _dbus_list_get_next_link (list, link);
785 all_even_values (DBusList **list)
789 link = _dbus_list_get_first_link (list);
792 int v = _DBUS_POINTER_TO_INT (link->data);
797 link = _dbus_list_get_next_link (list, link);
804 all_odd_values (DBusList **list)
808 link = _dbus_list_get_first_link (list);
811 int v = _DBUS_POINTER_TO_INT (link->data);
816 link = _dbus_list_get_next_link (list, link);
823 lists_equal (DBusList **list1,
829 link1 = _dbus_list_get_first_link (list1);
830 link2 = _dbus_list_get_first_link (list2);
831 while (link1 && link2)
833 if (link1->data != link2->data)
836 link1 = _dbus_list_get_next_link (list1, link1);
837 link2 = _dbus_list_get_next_link (list2, link2);
847 * @ingroup DBusListInternals
848 * Unit test for DBusList
849 * @returns #TRUE on success.
852 _dbus_list_test (void)
865 /* Test append and prepend */
870 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
871 _dbus_assert_not_reached ("could not allocate for append");
873 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
874 _dbus_assert_not_reached ("count not allocate for prepend");
877 verify_list (&list1);
878 verify_list (&list2);
880 _dbus_assert (_dbus_list_get_length (&list1) == i);
881 _dbus_assert (_dbus_list_get_length (&list2) == i);
884 _dbus_assert (is_ascending_sequence (&list1));
885 _dbus_assert (is_descending_sequence (&list2));
887 /* Test list clear */
888 _dbus_list_clear (&list1);
889 _dbus_list_clear (&list2);
891 verify_list (&list1);
892 verify_list (&list2);
894 /* Test get_first, get_last, pop_first, pop_last */
899 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
900 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
913 got_data1 = _dbus_list_get_last (&list1);
914 got_data2 = _dbus_list_get_first (&list2);
916 data1 = _dbus_list_pop_last (&list1);
917 data2 = _dbus_list_pop_first (&list2);
919 _dbus_assert (got_data1 == data1);
920 _dbus_assert (got_data2 == data2);
922 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
923 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
925 verify_list (&list1);
926 verify_list (&list2);
928 _dbus_assert (is_ascending_sequence (&list1));
929 _dbus_assert (is_descending_sequence (&list2));
934 _dbus_assert (list1 == NULL);
935 _dbus_assert (list2 == NULL);
942 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
943 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
946 verify_list (&list1);
947 verify_list (&list2);
949 _dbus_assert (_dbus_list_get_length (&list1) == i);
950 _dbus_assert (_dbus_list_get_length (&list2) == i);
953 _dbus_assert (is_ascending_sequence (&list1));
954 _dbus_assert (is_descending_sequence (&list2));
957 link2 = _dbus_list_get_first_link (&list2);
958 while (link2 != NULL)
960 verify_list (&link2); /* pretend this link is the head */
962 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
964 link2 = _dbus_list_get_next_link (&list2, link2);
969 link1 = _dbus_list_get_first_link (&list1);
970 while (link1 != NULL)
972 verify_list (&link1); /* pretend this link is the head */
974 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
976 link1 = _dbus_list_get_next_link (&list1, link1);
981 link1 = _dbus_list_get_last_link (&list1);
982 while (link1 != NULL)
984 verify_list (&link1); /* pretend this link is the head */
986 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
988 link1 = _dbus_list_get_prev_link (&list1, link1);
992 _dbus_list_clear (&list1);
993 _dbus_list_clear (&list2);
1000 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1001 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1010 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1011 _dbus_assert_not_reached ("element should have been in list");
1012 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1013 _dbus_assert_not_reached ("element should have been in list");
1015 verify_list (&list1);
1016 verify_list (&list2);
1021 _dbus_assert (all_odd_values (&list1));
1022 _dbus_assert (all_odd_values (&list2));
1024 _dbus_list_clear (&list1);
1025 _dbus_list_clear (&list2);
1027 /* test removing the other half of the elements */
1032 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1033 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1042 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1043 _dbus_assert_not_reached ("element should have been in list");
1044 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1045 _dbus_assert_not_reached ("element should have been in list");
1047 verify_list (&list1);
1048 verify_list (&list2);
1053 _dbus_assert (all_even_values (&list1));
1054 _dbus_assert (all_even_values (&list2));
1056 /* clear list using remove_link */
1057 while (list1 != NULL)
1059 _dbus_list_remove_link (&list1, list1);
1060 verify_list (&list1);
1062 while (list2 != NULL)
1064 _dbus_list_remove_link (&list2, list2);
1065 verify_list (&list2);
1068 /* Test remove link more generally */
1072 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1073 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1078 link2 = _dbus_list_get_first_link (&list2);
1079 while (link2 != NULL)
1081 DBusList *next = _dbus_list_get_next_link (&list2, link2);
1083 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1086 _dbus_list_remove_link (&list2, link2);
1088 verify_list (&list2);
1094 _dbus_assert (all_odd_values (&list2));
1095 _dbus_list_clear (&list2);
1098 link1 = _dbus_list_get_first_link (&list1);
1099 while (link1 != NULL)
1101 DBusList *next = _dbus_list_get_next_link (&list1, link1);
1103 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1106 _dbus_list_remove_link (&list1, link1);
1108 verify_list (&list1);
1114 _dbus_assert (all_even_values (&list1));
1115 _dbus_list_clear (&list1);
1117 /* Test copying a list */
1121 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1122 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1126 /* bad pointers, because they are allowed in the copy dest */
1127 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1128 copy2 = _DBUS_INT_TO_POINTER (23);
1130 _dbus_list_copy (&list1, ©1);
1131 verify_list (&list1);
1132 verify_list (©1);
1133 _dbus_assert (lists_equal (&list1, ©1));
1135 _dbus_list_copy (&list2, ©2);
1136 verify_list (&list2);
1137 verify_list (©2);
1138 _dbus_assert (lists_equal (&list2, ©2));
1140 /* Now test copying empty lists */
1141 _dbus_list_clear (&list1);
1142 _dbus_list_clear (&list2);
1143 _dbus_list_clear (©1);
1144 _dbus_list_clear (©2);
1146 /* bad pointers, because they are allowed in the copy dest */
1147 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1148 copy2 = _DBUS_INT_TO_POINTER (23);
1150 _dbus_list_copy (&list1, ©1);
1151 verify_list (&list1);
1152 verify_list (©1);
1153 _dbus_assert (lists_equal (&list1, ©1));
1155 _dbus_list_copy (&list2, ©2);
1156 verify_list (&list2);
1157 verify_list (©2);
1158 _dbus_assert (lists_equal (&list2, ©2));
1160 _dbus_list_clear (&list1);
1161 _dbus_list_clear (&list2);
1163 /* insert_before on empty list */
1164 _dbus_list_insert_before (&list1, NULL,
1165 _DBUS_INT_TO_POINTER (0));
1166 verify_list (&list1);
1168 /* inserting before first element */
1169 _dbus_list_insert_before (&list1, list1,
1170 _DBUS_INT_TO_POINTER (2));
1171 verify_list (&list1);
1172 _dbus_assert (is_descending_sequence (&list1));
1174 /* inserting in the middle */
1175 _dbus_list_insert_before (&list1, list1->next,
1176 _DBUS_INT_TO_POINTER (1));
1177 verify_list (&list1);
1178 _dbus_assert (is_descending_sequence (&list1));
1180 /* using insert_before to append */
1181 _dbus_list_insert_before (&list1, NULL,
1182 _DBUS_INT_TO_POINTER (-1));
1183 verify_list (&list1);
1184 _dbus_assert (is_descending_sequence (&list1));
1186 _dbus_list_clear (&list1);
1188 /* insert_after on empty list */
1189 _dbus_list_insert_after (&list1, NULL,
1190 _DBUS_INT_TO_POINTER (0));
1191 verify_list (&list1);
1193 /* inserting after first element */
1194 _dbus_list_insert_after (&list1, list1,
1195 _DBUS_INT_TO_POINTER (1));
1196 verify_list (&list1);
1197 _dbus_assert (is_ascending_sequence (&list1));
1199 /* inserting at the end */
1200 _dbus_list_insert_after (&list1, list1->next,
1201 _DBUS_INT_TO_POINTER (2));
1202 verify_list (&list1);
1203 _dbus_assert (is_ascending_sequence (&list1));
1205 /* using insert_after to prepend */
1206 _dbus_list_insert_after (&list1, NULL,
1207 _DBUS_INT_TO_POINTER (-1));
1208 verify_list (&list1);
1209 _dbus_assert (is_ascending_sequence (&list1));
1211 _dbus_list_clear (&list1);
1213 /* using remove_last */
1214 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2));
1215 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1));
1216 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3));
1218 _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2));
1220 verify_list (&list1);
1221 _dbus_assert (is_ascending_sequence (&list1));
1223 _dbus_list_clear (&list1);