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 if (_dbus_mem_pool_dealloc (list_pool, link))
99 _dbus_mem_pool_free (list_pool);
102 dbus_mutex_unlock (list_pool_lock);
106 link_before (DBusList **list,
107 DBusList *before_this_link,
118 link->next = before_this_link;
119 link->prev = before_this_link->prev;
120 before_this_link->prev = link;
121 link->prev->next = link;
123 if (before_this_link == *list)
129 link_after (DBusList **list,
130 DBusList *after_this_link,
141 link->prev = after_this_link;
142 link->next = after_this_link->next;
143 after_this_link->next = link;
144 link->next->prev = link;
151 * @addtogroup DBusList
158 * A node in a linked list.
160 * DBusList is a circular list; that is, the tail of the list
161 * points back to the head of the list. The empty list is
162 * represented by a #NULL pointer.
166 * @def _dbus_list_get_next_link
168 * Gets the next link in the list, or #NULL if
169 * there are no more links. Used for iteration.
173 * link = _dbus_list_get_first_link (&list);
174 * while (link != NULL)
176 * printf ("value is %p\n", link->data);
177 * link = _dbus_list_get_next_link (&link);
181 * @param list address of the list head.
182 * @param link current link.
183 * @returns the next link, or %NULL if none.
188 * @def _dbus_list_get_prev_link
190 * Gets the previous link in the list, or #NULL if
191 * there are no more links. Used for iteration.
195 * link = _dbus_list_get_last_link (&list);
196 * while (link != NULL)
198 * printf ("value is %p\n", link->data);
199 * link = _dbus_list_get_prev_link (&link);
203 * @param list address of the list head.
204 * @param link current link.
205 * @returns the previous link, or %NULL if none.
210 * Allocates a linked list node. Useful for preallocating
211 * nodes and using _dbus_list_append_link() to avoid
214 * @param data the value to store in the link.
215 * @returns a newly allocated link.
218 _dbus_list_alloc_link (void *data)
220 return alloc_link (data);
224 * Frees a linked list node allocated with _dbus_list_alloc_link.
225 * Does not free the data in the node.
227 * @param link the list node
230 _dbus_list_free_link (DBusList *link)
237 * Appends a value to the list. May return #FALSE
238 * if insufficient memory exists to add a list link.
239 * This is a constant-time operation.
241 * @param list address of the list head.
242 * @param data the value to append.
243 * @returns #TRUE on success.
246 _dbus_list_append (DBusList **list,
249 if (!_dbus_list_prepend (list, data))
252 /* Now cycle the list forward one so the prepended node is the tail */
253 *list = (*list)->next;
259 * Prepends a value to the list. May return #FALSE
260 * if insufficient memory exists to add a list link.
261 * This is a constant-time operation.
263 * @param list address of the list head.
264 * @param data the value to prepend.
265 * @returns #TRUE on success.
268 _dbus_list_prepend (DBusList **list,
273 link = alloc_link (data);
277 link_before (list, *list, link);
283 * Appends a link to the list.
284 * Cannot fail due to out of memory.
285 * This is a constant-time operation.
287 * @param list address of the list head.
288 * @param link the link to append.
291 _dbus_list_append_link (DBusList **list,
294 _dbus_list_prepend_link (list, link);
296 /* Now cycle the list forward one so the prepended node is the tail */
297 *list = (*list)->next;
301 * Prepends a link to the list.
302 * Cannot fail due to out of memory.
303 * This is a constant-time operation.
305 * @param list address of the list head.
306 * @param link the link to prepend.
309 _dbus_list_prepend_link (DBusList **list,
312 link_before (list, *list, link);
316 * Inserts data into the list before the given existing link.
318 * @param list the list to modify
319 * @param before_this_link existing link to insert before, or #NULL to append
320 * @param data the value to insert
321 * @returns #TRUE on success, #FALSE if memory allocation fails
324 _dbus_list_insert_before (DBusList **list,
325 DBusList *before_this_link,
330 if (before_this_link == NULL)
331 return _dbus_list_append (list, data);
334 link = alloc_link (data);
338 link_before (list, before_this_link, link);
345 * Inserts data into the list after the given existing link.
347 * @param list the list to modify
348 * @param after_this_link existing link to insert after, or #NULL to prepend
349 * @param data the value to insert
350 * @returns #TRUE on success, #FALSE if memory allocation fails
353 _dbus_list_insert_after (DBusList **list,
354 DBusList *after_this_link,
359 if (after_this_link == NULL)
360 return _dbus_list_prepend (list, data);
363 link = alloc_link (data);
367 link_after (list, after_this_link, link);
374 * Removes a value from the list. Only removes the
375 * first value equal to the given data pointer,
376 * even if multiple values exist which match.
377 * This is a linear-time operation.
379 * @param list address of the list head.
380 * @param data the value to remove.
381 * @returns #TRUE if a value was found to remove.
384 _dbus_list_remove (DBusList **list,
392 if (link->data == data)
394 _dbus_list_remove_link (list, link);
398 link = _dbus_list_get_next_link (list, link);
405 * Removes a value from the list. Only removes the
406 * last value equal to the given data pointer,
407 * even if multiple values exist which match.
408 * This is a linear-time operation.
410 * @param list address of the list head.
411 * @param data the value to remove.
412 * @returns #TRUE if a value was found to remove.
415 _dbus_list_remove_last (DBusList **list,
420 link = _dbus_list_get_last_link (list);
424 if (link->data == data)
426 _dbus_list_remove_link (list, link);
430 link = _dbus_list_get_prev_link (list, link);
437 _dbus_list_unlink (DBusList **list,
440 if (link->next == link)
442 /* one-element list */
447 link->prev->next = link->next;
448 link->next->prev = link->prev;
456 * Removes a link from the list. This is a constant-time operation.
458 * @param list address of the list head.
459 * @param link the list link to remove.
462 _dbus_list_remove_link (DBusList **list,
465 _dbus_list_unlink (list, link);
470 * Frees all links in the list and sets the list head to #NULL. Does
471 * not free the data in each link, for obvious reasons. This is a
472 * linear-time operation.
474 * @param list address of the list head.
477 _dbus_list_clear (DBusList **list)
484 DBusList *next = _dbus_list_get_next_link (list, link);
495 * Gets the first link in the list.
496 * This is a constant-time operation.
498 * @param list address of the list head.
499 * @returns the first link, or #NULL for an empty list.
502 _dbus_list_get_first_link (DBusList **list)
508 * Gets the last link in the list.
509 * This is a constant-time operation.
511 * @param list address of the list head.
512 * @returns the last link, or #NULL for an empty list.
515 _dbus_list_get_last_link (DBusList **list)
520 return (*list)->prev;
524 * Gets the last data in the list.
525 * This is a constant-time operation.
527 * @param list address of the list head.
528 * @returns the last data in the list, or #NULL for an empty list.
531 _dbus_list_get_last (DBusList **list)
536 return (*list)->prev->data;
540 * Gets the first data in the list.
541 * This is a constant-time operation.
543 * @param list address of the list head.
544 * @returns the first data in the list, or #NULL for an empty list.
547 _dbus_list_get_first (DBusList **list)
552 return (*list)->data;
556 * Removes the first link in the list and returns it. This is a
557 * constant-time operation.
559 * @param list address of the list head.
560 * @returns the first link in the list, or #NULL for an empty list.
563 _dbus_list_pop_first_link (DBusList **list)
567 link = _dbus_list_get_first_link (list);
571 _dbus_list_unlink (list, link);
577 * Removes the first value in the list and returns it. This is a
578 * constant-time operation.
580 * @param list address of the list head.
581 * @returns the first data in the list, or #NULL for an empty list.
584 _dbus_list_pop_first (DBusList **list)
589 link = _dbus_list_get_first_link (list);
594 _dbus_list_remove_link (list, link);
600 * Removes the last value in the list and returns it. This is a
601 * constant-time operation.
603 * @param list address of the list head.
604 * @returns the last data in the list, or #NULL for an empty list.
607 _dbus_list_pop_last (DBusList **list)
612 link = _dbus_list_get_last_link (list);
617 _dbus_list_remove_link (list, link);
623 * Copies a list. This is a linear-time operation. If there isn't
624 * enough memory to copy the entire list, the destination list will be
627 * @param list address of the head of the list to copy.
628 * @param dest address where the copied list should be placed.
629 * @returns #TRUE on success, #FALSE if not enough memory.
632 _dbus_list_copy (DBusList **list,
637 _dbus_assert (list != dest);
644 if (!_dbus_list_append (dest, link->data))
646 /* free what we have so far */
647 _dbus_list_clear (dest);
651 link = _dbus_list_get_next_link (list, link);
658 * Gets the length of a list. This is a linear-time
661 * @param list address of the head of the list
662 * @returns number of elements in the list.
665 _dbus_list_get_length (DBusList **list)
677 link = _dbus_list_get_next_link (list, link);
684 * Calls the given function for each element in the list. The
685 * function is passed the list element as its first argument, and the
686 * given data as its second argument.
688 * @param list address of the head of the list.
689 * @param function function to call for each element.
690 * @param data extra data for the function.
694 _dbus_list_foreach (DBusList **list,
695 DBusForeachFunction function,
703 DBusList *next = _dbus_list_get_next_link (list, link);
705 (* function) (link->data, data);
712 * Check whether length is exactly one.
714 * @param list the list
715 * @returns #TRUE if length is exactly one
718 _dbus_list_length_is_one (DBusList **list)
720 return (*list != NULL &&
721 (*list)->next == *list);
726 #ifdef DBUS_BUILD_TESTS
727 #include "dbus-test.h"
731 verify_list (DBusList **list)
741 if (link->next == link)
743 _dbus_assert (link->prev == link);
744 _dbus_assert (*list == link);
752 _dbus_assert (link->prev->next == link);
753 _dbus_assert (link->next->prev == link);
756 while (link != *list);
758 _dbus_assert (length == _dbus_list_get_length (list));
761 _dbus_assert (_dbus_list_length_is_one (list));
763 _dbus_assert (!_dbus_list_length_is_one (list));
767 is_ascending_sequence (DBusList **list)
772 prev = _DBUS_INT_MIN;
774 link = _dbus_list_get_first_link (list);
777 int v = _DBUS_POINTER_TO_INT (link->data);
784 link = _dbus_list_get_next_link (list, link);
791 is_descending_sequence (DBusList **list)
796 prev = _DBUS_INT_MAX;
798 link = _dbus_list_get_first_link (list);
801 int v = _DBUS_POINTER_TO_INT (link->data);
808 link = _dbus_list_get_next_link (list, link);
815 all_even_values (DBusList **list)
819 link = _dbus_list_get_first_link (list);
822 int v = _DBUS_POINTER_TO_INT (link->data);
827 link = _dbus_list_get_next_link (list, link);
834 all_odd_values (DBusList **list)
838 link = _dbus_list_get_first_link (list);
841 int v = _DBUS_POINTER_TO_INT (link->data);
846 link = _dbus_list_get_next_link (list, link);
853 lists_equal (DBusList **list1,
859 link1 = _dbus_list_get_first_link (list1);
860 link2 = _dbus_list_get_first_link (list2);
861 while (link1 && link2)
863 if (link1->data != link2->data)
866 link1 = _dbus_list_get_next_link (list1, link1);
867 link2 = _dbus_list_get_next_link (list2, link2);
877 * @ingroup DBusListInternals
878 * Unit test for DBusList
879 * @returns #TRUE on success.
882 _dbus_list_test (void)
895 /* Test append and prepend */
900 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
901 _dbus_assert_not_reached ("could not allocate for append");
903 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
904 _dbus_assert_not_reached ("count not allocate for prepend");
907 verify_list (&list1);
908 verify_list (&list2);
910 _dbus_assert (_dbus_list_get_length (&list1) == i);
911 _dbus_assert (_dbus_list_get_length (&list2) == i);
914 _dbus_assert (is_ascending_sequence (&list1));
915 _dbus_assert (is_descending_sequence (&list2));
917 /* Test list clear */
918 _dbus_list_clear (&list1);
919 _dbus_list_clear (&list2);
921 verify_list (&list1);
922 verify_list (&list2);
924 /* Test get_first, get_last, pop_first, pop_last */
929 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
930 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
943 got_data1 = _dbus_list_get_last (&list1);
944 got_data2 = _dbus_list_get_first (&list2);
946 data1 = _dbus_list_pop_last (&list1);
947 data2 = _dbus_list_pop_first (&list2);
949 _dbus_assert (got_data1 == data1);
950 _dbus_assert (got_data2 == data2);
952 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
953 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
955 verify_list (&list1);
956 verify_list (&list2);
958 _dbus_assert (is_ascending_sequence (&list1));
959 _dbus_assert (is_descending_sequence (&list2));
964 _dbus_assert (list1 == NULL);
965 _dbus_assert (list2 == NULL);
972 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
973 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
976 verify_list (&list1);
977 verify_list (&list2);
979 _dbus_assert (_dbus_list_get_length (&list1) == i);
980 _dbus_assert (_dbus_list_get_length (&list2) == i);
983 _dbus_assert (is_ascending_sequence (&list1));
984 _dbus_assert (is_descending_sequence (&list2));
987 link2 = _dbus_list_get_first_link (&list2);
988 while (link2 != NULL)
990 verify_list (&link2); /* pretend this link is the head */
992 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
994 link2 = _dbus_list_get_next_link (&list2, link2);
999 link1 = _dbus_list_get_first_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_next_link (&list1, link1);
1011 link1 = _dbus_list_get_last_link (&list1);
1012 while (link1 != NULL)
1014 verify_list (&link1); /* pretend this link is the head */
1016 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1018 link1 = _dbus_list_get_prev_link (&list1, link1);
1022 _dbus_list_clear (&list1);
1023 _dbus_list_clear (&list2);
1030 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1031 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1040 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1041 _dbus_assert_not_reached ("element should have been in list");
1042 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1043 _dbus_assert_not_reached ("element should have been in list");
1045 verify_list (&list1);
1046 verify_list (&list2);
1051 _dbus_assert (all_odd_values (&list1));
1052 _dbus_assert (all_odd_values (&list2));
1054 _dbus_list_clear (&list1);
1055 _dbus_list_clear (&list2);
1057 /* test removing the other half of the elements */
1062 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1063 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1072 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1073 _dbus_assert_not_reached ("element should have been in list");
1074 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1075 _dbus_assert_not_reached ("element should have been in list");
1077 verify_list (&list1);
1078 verify_list (&list2);
1083 _dbus_assert (all_even_values (&list1));
1084 _dbus_assert (all_even_values (&list2));
1086 /* clear list using remove_link */
1087 while (list1 != NULL)
1089 _dbus_list_remove_link (&list1, list1);
1090 verify_list (&list1);
1092 while (list2 != NULL)
1094 _dbus_list_remove_link (&list2, list2);
1095 verify_list (&list2);
1098 /* Test remove link more generally */
1102 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1103 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1108 link2 = _dbus_list_get_first_link (&list2);
1109 while (link2 != NULL)
1111 DBusList *next = _dbus_list_get_next_link (&list2, link2);
1113 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1116 _dbus_list_remove_link (&list2, link2);
1118 verify_list (&list2);
1124 _dbus_assert (all_odd_values (&list2));
1125 _dbus_list_clear (&list2);
1128 link1 = _dbus_list_get_first_link (&list1);
1129 while (link1 != NULL)
1131 DBusList *next = _dbus_list_get_next_link (&list1, link1);
1133 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1136 _dbus_list_remove_link (&list1, link1);
1138 verify_list (&list1);
1144 _dbus_assert (all_even_values (&list1));
1145 _dbus_list_clear (&list1);
1147 /* Test copying a list */
1151 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1152 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1156 /* bad pointers, because they are allowed in the copy dest */
1157 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1158 copy2 = _DBUS_INT_TO_POINTER (23);
1160 _dbus_list_copy (&list1, ©1);
1161 verify_list (&list1);
1162 verify_list (©1);
1163 _dbus_assert (lists_equal (&list1, ©1));
1165 _dbus_list_copy (&list2, ©2);
1166 verify_list (&list2);
1167 verify_list (©2);
1168 _dbus_assert (lists_equal (&list2, ©2));
1170 /* Now test copying empty lists */
1171 _dbus_list_clear (&list1);
1172 _dbus_list_clear (&list2);
1173 _dbus_list_clear (©1);
1174 _dbus_list_clear (©2);
1176 /* bad pointers, because they are allowed in the copy dest */
1177 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1178 copy2 = _DBUS_INT_TO_POINTER (23);
1180 _dbus_list_copy (&list1, ©1);
1181 verify_list (&list1);
1182 verify_list (©1);
1183 _dbus_assert (lists_equal (&list1, ©1));
1185 _dbus_list_copy (&list2, ©2);
1186 verify_list (&list2);
1187 verify_list (©2);
1188 _dbus_assert (lists_equal (&list2, ©2));
1190 _dbus_list_clear (&list1);
1191 _dbus_list_clear (&list2);
1193 /* insert_before on empty list */
1194 _dbus_list_insert_before (&list1, NULL,
1195 _DBUS_INT_TO_POINTER (0));
1196 verify_list (&list1);
1198 /* inserting before first element */
1199 _dbus_list_insert_before (&list1, list1,
1200 _DBUS_INT_TO_POINTER (2));
1201 verify_list (&list1);
1202 _dbus_assert (is_descending_sequence (&list1));
1204 /* inserting in the middle */
1205 _dbus_list_insert_before (&list1, list1->next,
1206 _DBUS_INT_TO_POINTER (1));
1207 verify_list (&list1);
1208 _dbus_assert (is_descending_sequence (&list1));
1210 /* using insert_before to append */
1211 _dbus_list_insert_before (&list1, NULL,
1212 _DBUS_INT_TO_POINTER (-1));
1213 verify_list (&list1);
1214 _dbus_assert (is_descending_sequence (&list1));
1216 _dbus_list_clear (&list1);
1218 /* insert_after on empty list */
1219 _dbus_list_insert_after (&list1, NULL,
1220 _DBUS_INT_TO_POINTER (0));
1221 verify_list (&list1);
1223 /* inserting after first element */
1224 _dbus_list_insert_after (&list1, list1,
1225 _DBUS_INT_TO_POINTER (1));
1226 verify_list (&list1);
1227 _dbus_assert (is_ascending_sequence (&list1));
1229 /* inserting at the end */
1230 _dbus_list_insert_after (&list1, list1->next,
1231 _DBUS_INT_TO_POINTER (2));
1232 verify_list (&list1);
1233 _dbus_assert (is_ascending_sequence (&list1));
1235 /* using insert_after to prepend */
1236 _dbus_list_insert_after (&list1, NULL,
1237 _DBUS_INT_TO_POINTER (-1));
1238 verify_list (&list1);
1239 _dbus_assert (is_ascending_sequence (&list1));
1241 _dbus_list_clear (&list1);
1243 /* using remove_last */
1244 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2));
1245 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1));
1246 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3));
1248 _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2));
1250 verify_list (&list1);
1251 _dbus_assert (is_ascending_sequence (&list1));
1253 _dbus_list_clear (&list1);