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 _DBUS_DEFINE_GLOBAL_LOCK (list);
41 * @defgroup DBusListInternals Linked list implementation details
42 * @ingroup DBusInternals
43 * @brief DBusList implementation details
45 * The guts of DBusList.
50 /* the mem pool is probably a speed hit, with the thread
51 * lock, though it does still save memory - unknown.
54 alloc_link (void *data)
58 if (!_DBUS_LOCK (list))
63 list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE);
65 if (list_pool == NULL)
72 link = _dbus_mem_pool_alloc (list_pool);
82 free_link (DBusList *link)
85 if (_dbus_mem_pool_dealloc (list_pool, link))
87 _dbus_mem_pool_free (list_pool);
94 link_before (DBusList **list,
95 DBusList *before_this_link,
106 link->next = before_this_link;
107 link->prev = before_this_link->prev;
108 before_this_link->prev = link;
109 link->prev->next = link;
111 if (before_this_link == *list)
117 link_after (DBusList **list,
118 DBusList *after_this_link,
129 link->prev = after_this_link;
130 link->next = after_this_link->next;
131 after_this_link->next = link;
132 link->next->prev = link;
139 * @addtogroup DBusList
146 * A node in a linked list.
148 * DBusList is a circular list; that is, the tail of the list
149 * points back to the head of the list. The empty list is
150 * represented by a #NULL pointer.
154 * @def _dbus_list_get_next_link
156 * Gets the next link in the list, or #NULL if
157 * there are no more links. Used for iteration.
161 * link = _dbus_list_get_first_link (&list);
162 * while (link != NULL)
164 * printf ("value is %p\n", link->data);
165 * link = _dbus_list_get_next_link (&link);
169 * @param list address of the list head.
170 * @param link current link.
171 * @returns the next link, or %NULL if none.
176 * @def _dbus_list_get_prev_link
178 * Gets the previous link in the list, or #NULL if
179 * there are no more links. Used for iteration.
183 * link = _dbus_list_get_last_link (&list);
184 * while (link != NULL)
186 * printf ("value is %p\n", link->data);
187 * link = _dbus_list_get_prev_link (&link);
191 * @param list address of the list head.
192 * @param link current link.
193 * @returns the previous link, or %NULL if none.
198 * Allocates a linked list node. Useful for preallocating
199 * nodes and using _dbus_list_append_link() to avoid
202 * @param data the value to store in the link.
203 * @returns a newly allocated link.
206 _dbus_list_alloc_link (void *data)
208 return alloc_link (data);
212 * Frees a linked list node allocated with _dbus_list_alloc_link.
213 * Does not free the data in the node.
215 * @param link the list node
218 _dbus_list_free_link (DBusList *link)
225 * Appends a value to the list. May return #FALSE
226 * if insufficient memory exists to add a list link.
227 * This is a constant-time operation.
229 * @param list address of the list head.
230 * @param data the value to append.
231 * @returns #TRUE on success.
234 _dbus_list_append (DBusList **list,
237 if (!_dbus_list_prepend (list, data))
240 /* Now cycle the list forward one so the prepended node is the tail */
241 *list = (*list)->next;
247 * Prepends a value to the list. May return #FALSE
248 * if insufficient memory exists to add a list link.
249 * This is a constant-time operation.
251 * @param list address of the list head.
252 * @param data the value to prepend.
253 * @returns #TRUE on success.
256 _dbus_list_prepend (DBusList **list,
261 link = alloc_link (data);
265 link_before (list, *list, link);
271 * Appends a link to the list.
272 * Cannot fail due to out of memory.
273 * This is a constant-time operation.
275 * @param list address of the list head.
276 * @param link the link to append.
279 _dbus_list_append_link (DBusList **list,
282 _dbus_list_prepend_link (list, link);
284 /* Now cycle the list forward one so the prepended node is the tail */
285 *list = (*list)->next;
289 * Prepends a link to the list.
290 * Cannot fail due to out of memory.
291 * This is a constant-time operation.
293 * @param list address of the list head.
294 * @param link the link to prepend.
297 _dbus_list_prepend_link (DBusList **list,
300 link_before (list, *list, link);
304 * Inserts data into the list before the given existing link.
306 * @param list the list to modify
307 * @param before_this_link existing link to insert before, or #NULL to append
308 * @param data the value to insert
309 * @returns #TRUE on success, #FALSE if memory allocation fails
312 _dbus_list_insert_before (DBusList **list,
313 DBusList *before_this_link,
318 if (before_this_link == NULL)
319 return _dbus_list_append (list, data);
322 link = alloc_link (data);
326 link_before (list, before_this_link, link);
333 * Inserts data into the list after the given existing link.
335 * @param list the list to modify
336 * @param after_this_link existing link to insert after, or #NULL to prepend
337 * @param data the value to insert
338 * @returns #TRUE on success, #FALSE if memory allocation fails
341 _dbus_list_insert_after (DBusList **list,
342 DBusList *after_this_link,
347 if (after_this_link == NULL)
348 return _dbus_list_prepend (list, data);
351 link = alloc_link (data);
355 link_after (list, after_this_link, link);
362 * Removes a value from the list. Only removes the
363 * first value equal to the given data pointer,
364 * even if multiple values exist which match.
365 * This is a linear-time operation.
367 * @param list address of the list head.
368 * @param data the value to remove.
369 * @returns #TRUE if a value was found to remove.
372 _dbus_list_remove (DBusList **list,
380 if (link->data == data)
382 _dbus_list_remove_link (list, link);
386 link = _dbus_list_get_next_link (list, link);
393 * Removes a value from the list. Only removes the
394 * last value equal to the given data pointer,
395 * even if multiple values exist which match.
396 * This is a linear-time operation.
398 * @param list address of the list head.
399 * @param data the value to remove.
400 * @returns #TRUE if a value was found to remove.
403 _dbus_list_remove_last (DBusList **list,
408 link = _dbus_list_get_last_link (list);
412 if (link->data == data)
414 _dbus_list_remove_link (list, link);
418 link = _dbus_list_get_prev_link (list, link);
425 _dbus_list_unlink (DBusList **list,
428 if (link->next == link)
430 /* one-element list */
435 link->prev->next = link->next;
436 link->next->prev = link->prev;
444 * Removes a link from the list. This is a constant-time operation.
446 * @param list address of the list head.
447 * @param link the list link to remove.
450 _dbus_list_remove_link (DBusList **list,
453 _dbus_list_unlink (list, link);
458 * Frees all links in the list and sets the list head to #NULL. Does
459 * not free the data in each link, for obvious reasons. This is a
460 * linear-time operation.
462 * @param list address of the list head.
465 _dbus_list_clear (DBusList **list)
472 DBusList *next = _dbus_list_get_next_link (list, link);
483 * Gets the first link in the list.
484 * This is a constant-time operation.
486 * @param list address of the list head.
487 * @returns the first link, or #NULL for an empty list.
490 _dbus_list_get_first_link (DBusList **list)
496 * Gets the last link in the list.
497 * This is a constant-time operation.
499 * @param list address of the list head.
500 * @returns the last link, or #NULL for an empty list.
503 _dbus_list_get_last_link (DBusList **list)
508 return (*list)->prev;
512 * Gets the last data in the list.
513 * This is a constant-time operation.
515 * @param list address of the list head.
516 * @returns the last data in the list, or #NULL for an empty list.
519 _dbus_list_get_last (DBusList **list)
524 return (*list)->prev->data;
528 * Gets the first data in the list.
529 * This is a constant-time operation.
531 * @param list address of the list head.
532 * @returns the first data in the list, or #NULL for an empty list.
535 _dbus_list_get_first (DBusList **list)
540 return (*list)->data;
544 * Removes the first link in the list and returns it. This is a
545 * constant-time operation.
547 * @param list address of the list head.
548 * @returns the first link in the list, or #NULL for an empty list.
551 _dbus_list_pop_first_link (DBusList **list)
555 link = _dbus_list_get_first_link (list);
559 _dbus_list_unlink (list, link);
565 * Removes the first value in the list and returns it. This is a
566 * constant-time operation.
568 * @param list address of the list head.
569 * @returns the first data in the list, or #NULL for an empty list.
572 _dbus_list_pop_first (DBusList **list)
577 link = _dbus_list_get_first_link (list);
582 _dbus_list_remove_link (list, link);
588 * Removes the last value in the list and returns it. This is a
589 * constant-time operation.
591 * @param list address of the list head.
592 * @returns the last data in the list, or #NULL for an empty list.
595 _dbus_list_pop_last (DBusList **list)
600 link = _dbus_list_get_last_link (list);
605 _dbus_list_remove_link (list, link);
611 * Copies a list. This is a linear-time operation. If there isn't
612 * enough memory to copy the entire list, the destination list will be
615 * @param list address of the head of the list to copy.
616 * @param dest address where the copied list should be placed.
617 * @returns #TRUE on success, #FALSE if not enough memory.
620 _dbus_list_copy (DBusList **list,
625 _dbus_assert (list != dest);
632 if (!_dbus_list_append (dest, link->data))
634 /* free what we have so far */
635 _dbus_list_clear (dest);
639 link = _dbus_list_get_next_link (list, link);
646 * Gets the length of a list. This is a linear-time
649 * @param list address of the head of the list
650 * @returns number of elements in the list.
653 _dbus_list_get_length (DBusList **list)
665 link = _dbus_list_get_next_link (list, link);
672 * Calls the given function for each element in the list. The
673 * function is passed the list element as its first argument, and the
674 * given data as its second argument.
676 * @param list address of the head of the list.
677 * @param function function to call for each element.
678 * @param data extra data for the function.
682 _dbus_list_foreach (DBusList **list,
683 DBusForeachFunction function,
691 DBusList *next = _dbus_list_get_next_link (list, link);
693 (* function) (link->data, data);
700 * Check whether length is exactly one.
702 * @param list the list
703 * @returns #TRUE if length is exactly one
706 _dbus_list_length_is_one (DBusList **list)
708 return (*list != NULL &&
709 (*list)->next == *list);
714 #ifdef DBUS_BUILD_TESTS
715 #include "dbus-test.h"
719 verify_list (DBusList **list)
729 if (link->next == link)
731 _dbus_assert (link->prev == link);
732 _dbus_assert (*list == link);
740 _dbus_assert (link->prev->next == link);
741 _dbus_assert (link->next->prev == link);
744 while (link != *list);
746 _dbus_assert (length == _dbus_list_get_length (list));
749 _dbus_assert (_dbus_list_length_is_one (list));
751 _dbus_assert (!_dbus_list_length_is_one (list));
755 is_ascending_sequence (DBusList **list)
760 prev = _DBUS_INT_MIN;
762 link = _dbus_list_get_first_link (list);
765 int v = _DBUS_POINTER_TO_INT (link->data);
772 link = _dbus_list_get_next_link (list, link);
779 is_descending_sequence (DBusList **list)
784 prev = _DBUS_INT_MAX;
786 link = _dbus_list_get_first_link (list);
789 int v = _DBUS_POINTER_TO_INT (link->data);
796 link = _dbus_list_get_next_link (list, link);
803 all_even_values (DBusList **list)
807 link = _dbus_list_get_first_link (list);
810 int v = _DBUS_POINTER_TO_INT (link->data);
815 link = _dbus_list_get_next_link (list, link);
822 all_odd_values (DBusList **list)
826 link = _dbus_list_get_first_link (list);
829 int v = _DBUS_POINTER_TO_INT (link->data);
834 link = _dbus_list_get_next_link (list, link);
841 lists_equal (DBusList **list1,
847 link1 = _dbus_list_get_first_link (list1);
848 link2 = _dbus_list_get_first_link (list2);
849 while (link1 && link2)
851 if (link1->data != link2->data)
854 link1 = _dbus_list_get_next_link (list1, link1);
855 link2 = _dbus_list_get_next_link (list2, link2);
865 * @ingroup DBusListInternals
866 * Unit test for DBusList
867 * @returns #TRUE on success.
870 _dbus_list_test (void)
883 /* Test append and prepend */
888 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
889 _dbus_assert_not_reached ("could not allocate for append");
891 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
892 _dbus_assert_not_reached ("count not allocate for prepend");
895 verify_list (&list1);
896 verify_list (&list2);
898 _dbus_assert (_dbus_list_get_length (&list1) == i);
899 _dbus_assert (_dbus_list_get_length (&list2) == i);
902 _dbus_assert (is_ascending_sequence (&list1));
903 _dbus_assert (is_descending_sequence (&list2));
905 /* Test list clear */
906 _dbus_list_clear (&list1);
907 _dbus_list_clear (&list2);
909 verify_list (&list1);
910 verify_list (&list2);
912 /* Test get_first, get_last, pop_first, pop_last */
917 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
918 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
931 got_data1 = _dbus_list_get_last (&list1);
932 got_data2 = _dbus_list_get_first (&list2);
934 data1 = _dbus_list_pop_last (&list1);
935 data2 = _dbus_list_pop_first (&list2);
937 _dbus_assert (got_data1 == data1);
938 _dbus_assert (got_data2 == data2);
940 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
941 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
943 verify_list (&list1);
944 verify_list (&list2);
946 _dbus_assert (is_ascending_sequence (&list1));
947 _dbus_assert (is_descending_sequence (&list2));
952 _dbus_assert (list1 == NULL);
953 _dbus_assert (list2 == NULL);
960 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
961 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
964 verify_list (&list1);
965 verify_list (&list2);
967 _dbus_assert (_dbus_list_get_length (&list1) == i);
968 _dbus_assert (_dbus_list_get_length (&list2) == i);
971 _dbus_assert (is_ascending_sequence (&list1));
972 _dbus_assert (is_descending_sequence (&list2));
975 link2 = _dbus_list_get_first_link (&list2);
976 while (link2 != NULL)
978 verify_list (&link2); /* pretend this link is the head */
980 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
982 link2 = _dbus_list_get_next_link (&list2, link2);
987 link1 = _dbus_list_get_first_link (&list1);
988 while (link1 != NULL)
990 verify_list (&link1); /* pretend this link is the head */
992 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
994 link1 = _dbus_list_get_next_link (&list1, link1);
999 link1 = _dbus_list_get_last_link (&list1);
1000 while (link1 != NULL)
1002 verify_list (&link1); /* pretend this link is the head */
1004 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1006 link1 = _dbus_list_get_prev_link (&list1, link1);
1010 _dbus_list_clear (&list1);
1011 _dbus_list_clear (&list2);
1018 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1019 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1028 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1029 _dbus_assert_not_reached ("element should have been in list");
1030 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1031 _dbus_assert_not_reached ("element should have been in list");
1033 verify_list (&list1);
1034 verify_list (&list2);
1039 _dbus_assert (all_odd_values (&list1));
1040 _dbus_assert (all_odd_values (&list2));
1042 _dbus_list_clear (&list1);
1043 _dbus_list_clear (&list2);
1045 /* test removing the other half of the elements */
1050 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1051 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1060 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1061 _dbus_assert_not_reached ("element should have been in list");
1062 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1063 _dbus_assert_not_reached ("element should have been in list");
1065 verify_list (&list1);
1066 verify_list (&list2);
1071 _dbus_assert (all_even_values (&list1));
1072 _dbus_assert (all_even_values (&list2));
1074 /* clear list using remove_link */
1075 while (list1 != NULL)
1077 _dbus_list_remove_link (&list1, list1);
1078 verify_list (&list1);
1080 while (list2 != NULL)
1082 _dbus_list_remove_link (&list2, list2);
1083 verify_list (&list2);
1086 /* Test remove link more generally */
1090 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1091 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1096 link2 = _dbus_list_get_first_link (&list2);
1097 while (link2 != NULL)
1099 DBusList *next = _dbus_list_get_next_link (&list2, link2);
1101 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1104 _dbus_list_remove_link (&list2, link2);
1106 verify_list (&list2);
1112 _dbus_assert (all_odd_values (&list2));
1113 _dbus_list_clear (&list2);
1116 link1 = _dbus_list_get_first_link (&list1);
1117 while (link1 != NULL)
1119 DBusList *next = _dbus_list_get_next_link (&list1, link1);
1121 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1124 _dbus_list_remove_link (&list1, link1);
1126 verify_list (&list1);
1132 _dbus_assert (all_even_values (&list1));
1133 _dbus_list_clear (&list1);
1135 /* Test copying a list */
1139 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1140 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1144 /* bad pointers, because they are allowed in the copy dest */
1145 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1146 copy2 = _DBUS_INT_TO_POINTER (23);
1148 _dbus_list_copy (&list1, ©1);
1149 verify_list (&list1);
1150 verify_list (©1);
1151 _dbus_assert (lists_equal (&list1, ©1));
1153 _dbus_list_copy (&list2, ©2);
1154 verify_list (&list2);
1155 verify_list (©2);
1156 _dbus_assert (lists_equal (&list2, ©2));
1158 /* Now test copying empty lists */
1159 _dbus_list_clear (&list1);
1160 _dbus_list_clear (&list2);
1161 _dbus_list_clear (©1);
1162 _dbus_list_clear (©2);
1164 /* bad pointers, because they are allowed in the copy dest */
1165 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1166 copy2 = _DBUS_INT_TO_POINTER (23);
1168 _dbus_list_copy (&list1, ©1);
1169 verify_list (&list1);
1170 verify_list (©1);
1171 _dbus_assert (lists_equal (&list1, ©1));
1173 _dbus_list_copy (&list2, ©2);
1174 verify_list (&list2);
1175 verify_list (©2);
1176 _dbus_assert (lists_equal (&list2, ©2));
1178 _dbus_list_clear (&list1);
1179 _dbus_list_clear (&list2);
1181 /* insert_before on empty list */
1182 _dbus_list_insert_before (&list1, NULL,
1183 _DBUS_INT_TO_POINTER (0));
1184 verify_list (&list1);
1186 /* inserting before first element */
1187 _dbus_list_insert_before (&list1, list1,
1188 _DBUS_INT_TO_POINTER (2));
1189 verify_list (&list1);
1190 _dbus_assert (is_descending_sequence (&list1));
1192 /* inserting in the middle */
1193 _dbus_list_insert_before (&list1, list1->next,
1194 _DBUS_INT_TO_POINTER (1));
1195 verify_list (&list1);
1196 _dbus_assert (is_descending_sequence (&list1));
1198 /* using insert_before to append */
1199 _dbus_list_insert_before (&list1, NULL,
1200 _DBUS_INT_TO_POINTER (-1));
1201 verify_list (&list1);
1202 _dbus_assert (is_descending_sequence (&list1));
1204 _dbus_list_clear (&list1);
1206 /* insert_after on empty list */
1207 _dbus_list_insert_after (&list1, NULL,
1208 _DBUS_INT_TO_POINTER (0));
1209 verify_list (&list1);
1211 /* inserting after first element */
1212 _dbus_list_insert_after (&list1, list1,
1213 _DBUS_INT_TO_POINTER (1));
1214 verify_list (&list1);
1215 _dbus_assert (is_ascending_sequence (&list1));
1217 /* inserting at the end */
1218 _dbus_list_insert_after (&list1, list1->next,
1219 _DBUS_INT_TO_POINTER (2));
1220 verify_list (&list1);
1221 _dbus_assert (is_ascending_sequence (&list1));
1223 /* using insert_after to prepend */
1224 _dbus_list_insert_after (&list1, NULL,
1225 _DBUS_INT_TO_POINTER (-1));
1226 verify_list (&list1);
1227 _dbus_assert (is_ascending_sequence (&list1));
1229 _dbus_list_clear (&list1);
1231 /* using remove_last */
1232 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2));
1233 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1));
1234 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3));
1236 _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2));
1238 verify_list (&list1);
1239 _dbus_assert (is_ascending_sequence (&list1));
1241 _dbus_list_clear (&list1);