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 2.1
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-internal.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))
61 if (list_pool == NULL)
63 list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE);
65 if (list_pool == NULL)
71 link = _dbus_mem_pool_alloc (list_pool);
74 _dbus_mem_pool_free (list_pool);
82 link = _dbus_mem_pool_alloc (list_pool);
94 free_link (DBusList *link)
97 if (_dbus_mem_pool_dealloc (list_pool, link))
99 _dbus_mem_pool_free (list_pool);
107 link_before (DBusList **list,
108 DBusList *before_this_link,
119 link->next = before_this_link;
120 link->prev = before_this_link->prev;
121 before_this_link->prev = link;
122 link->prev->next = link;
124 if (before_this_link == *list)
129 #ifdef DBUS_BUILD_TESTS
131 link_after (DBusList **list,
132 DBusList *after_this_link,
143 link->prev = after_this_link;
144 link->next = after_this_link->next;
145 after_this_link->next = link;
146 link->next->prev = link;
149 #endif /* DBUS_BUILD_TESTS */
154 * @addtogroup DBusList
161 * A node in a linked list.
163 * DBusList is a circular list; that is, the tail of the list
164 * points back to the head of the list. The empty list is
165 * represented by a #NULL pointer.
169 * @def _dbus_list_get_next_link
171 * Gets the next link in the list, or #NULL if
172 * there are no more links. Used for iteration.
176 * link = _dbus_list_get_first_link (&list);
177 * while (link != NULL)
179 * printf ("value is %p\n", link->data);
180 * link = _dbus_list_get_next_link (&link);
184 * @param list address of the list head.
185 * @param link current link.
186 * @returns the next link, or %NULL if none.
191 * @def _dbus_list_get_prev_link
193 * Gets the previous link in the list, or #NULL if
194 * there are no more links. Used for iteration.
198 * link = _dbus_list_get_last_link (&list);
199 * while (link != NULL)
201 * printf ("value is %p\n", link->data);
202 * link = _dbus_list_get_prev_link (&link);
206 * @param list address of the list head.
207 * @param link current link.
208 * @returns the previous link, or %NULL if none.
213 * Allocates a linked list node. Useful for preallocating
214 * nodes and using _dbus_list_append_link() to avoid
217 * @param data the value to store in the link.
218 * @returns a newly allocated link.
221 _dbus_list_alloc_link (void *data)
223 return alloc_link (data);
227 * Frees a linked list node allocated with _dbus_list_alloc_link.
228 * Does not free the data in the node.
230 * @param link the list node
233 _dbus_list_free_link (DBusList *link)
240 * Appends a value to the list. May return #FALSE
241 * if insufficient memory exists to add a list link.
242 * This is a constant-time operation.
244 * @param list address of the list head.
245 * @param data the value to append.
246 * @returns #TRUE on success.
249 _dbus_list_append (DBusList **list,
252 if (!_dbus_list_prepend (list, data))
255 /* Now cycle the list forward one so the prepended node is the tail */
256 *list = (*list)->next;
262 * Prepends a value to the list. May return #FALSE
263 * if insufficient memory exists to add a list link.
264 * This is a constant-time operation.
266 * @param list address of the list head.
267 * @param data the value to prepend.
268 * @returns #TRUE on success.
271 _dbus_list_prepend (DBusList **list,
276 link = alloc_link (data);
280 link_before (list, *list, link);
286 * Appends a link to the list.
287 * Cannot fail due to out of memory.
288 * This is a constant-time operation.
290 * @param list address of the list head.
291 * @param link the link to append.
294 _dbus_list_append_link (DBusList **list,
297 _dbus_list_prepend_link (list, link);
299 /* Now cycle the list forward one so the prepended node is the tail */
300 *list = (*list)->next;
304 * Prepends a link to the list.
305 * Cannot fail due to out of memory.
306 * This is a constant-time operation.
308 * @param list address of the list head.
309 * @param link the link to prepend.
312 _dbus_list_prepend_link (DBusList **list,
315 link_before (list, *list, link);
318 #ifdef DBUS_BUILD_TESTS
320 * Inserts data into the list before the given existing link.
322 * @param list the list to modify
323 * @param before_this_link existing link to insert before, or #NULL to append
324 * @param data the value to insert
325 * @returns #TRUE on success, #FALSE if memory allocation fails
328 _dbus_list_insert_before (DBusList **list,
329 DBusList *before_this_link,
334 if (before_this_link == NULL)
335 return _dbus_list_append (list, data);
338 link = alloc_link (data);
342 link_before (list, before_this_link, link);
347 #endif /* DBUS_BUILD_TESTS */
349 #ifdef DBUS_BUILD_TESTS
351 * Inserts data into the list after the given existing link.
353 * @param list the list to modify
354 * @param after_this_link existing link to insert after, or #NULL to prepend
355 * @param data the value to insert
356 * @returns #TRUE on success, #FALSE if memory allocation fails
359 _dbus_list_insert_after (DBusList **list,
360 DBusList *after_this_link,
365 if (after_this_link == NULL)
366 return _dbus_list_prepend (list, data);
369 link = alloc_link (data);
373 link_after (list, after_this_link, link);
378 #endif /* DBUS_BUILD_TESTS */
381 * Inserts a link into the list before the given existing link.
383 * @param list the list to modify
384 * @param before_this_link existing link to insert before, or #NULL to append
385 * @param link the link to insert
388 _dbus_list_insert_before_link (DBusList **list,
389 DBusList *before_this_link,
392 if (before_this_link == NULL)
393 _dbus_list_append_link (list, link);
395 link_before (list, before_this_link, link);
398 #ifdef DBUS_BUILD_TESTS
400 * Inserts a link into the list after the given existing link.
402 * @param list the list to modify
403 * @param after_this_link existing link to insert after, or #NULL to prepend
404 * @param link the link to insert
407 _dbus_list_insert_after_link (DBusList **list,
408 DBusList *after_this_link,
411 if (after_this_link == NULL)
412 _dbus_list_prepend_link (list, link);
414 link_after (list, after_this_link, link);
416 #endif /* DBUS_BUILD_TESTS */
419 * Removes a value from the list. Only removes the
420 * first value equal to the given data pointer,
421 * even if multiple values exist which match.
422 * This is a linear-time operation.
424 * @param list address of the list head.
425 * @param data the value to remove.
426 * @returns #TRUE if a value was found to remove.
429 _dbus_list_remove (DBusList **list,
437 if (link->data == data)
439 _dbus_list_remove_link (list, link);
443 link = _dbus_list_get_next_link (list, link);
450 * Removes a value from the list. Only removes the
451 * last value equal to the given data pointer,
452 * even if multiple values exist which match.
453 * This is a linear-time operation.
455 * @param list address of the list head.
456 * @param data the value to remove.
457 * @returns #TRUE if a value was found to remove.
460 _dbus_list_remove_last (DBusList **list,
465 link = _dbus_list_find_last (list, data);
468 _dbus_list_remove_link (list, link);
476 * Finds a value in the list. Returns the last link
477 * with value equal to the given data pointer.
478 * This is a linear-time operation.
479 * Returns #NULL if no value found that matches.
481 * @param list address of the list head.
482 * @param data the value to find.
483 * @returns the link if found
486 _dbus_list_find_last (DBusList **list,
491 link = _dbus_list_get_last_link (list);
495 if (link->data == data)
498 link = _dbus_list_get_prev_link (list, link);
505 * Removes the given link from the list, but doesn't
506 * free it. _dbus_list_remove_link() both removes the
507 * link and also frees it.
509 * @param list the list
510 * @param link the link in the list
513 _dbus_list_unlink (DBusList **list,
516 if (link->next == link)
518 /* one-element list */
523 link->prev->next = link->next;
524 link->next->prev = link->prev;
535 * Removes a link from the list. This is a constant-time operation.
537 * @param list address of the list head.
538 * @param link the list link to remove.
541 _dbus_list_remove_link (DBusList **list,
544 _dbus_list_unlink (list, link);
549 * Frees all links in the list and sets the list head to #NULL. Does
550 * not free the data in each link, for obvious reasons. This is a
551 * linear-time operation.
553 * @param list address of the list head.
556 _dbus_list_clear (DBusList **list)
563 DBusList *next = _dbus_list_get_next_link (list, link);
574 * Gets the first link in the list.
575 * This is a constant-time operation.
577 * @param list address of the list head.
578 * @returns the first link, or #NULL for an empty list.
581 _dbus_list_get_first_link (DBusList **list)
587 * Gets the last link in the list.
588 * This is a constant-time operation.
590 * @param list address of the list head.
591 * @returns the last link, or #NULL for an empty list.
594 _dbus_list_get_last_link (DBusList **list)
599 return (*list)->prev;
603 * Gets the last data in the list.
604 * This is a constant-time operation.
606 * @param list address of the list head.
607 * @returns the last data in the list, or #NULL for an empty list.
610 _dbus_list_get_last (DBusList **list)
615 return (*list)->prev->data;
619 * Gets the first data in the list.
620 * This is a constant-time operation.
622 * @param list address of the list head.
623 * @returns the first data in the list, or #NULL for an empty list.
626 _dbus_list_get_first (DBusList **list)
631 return (*list)->data;
635 * Removes the first link in the list and returns it. This is a
636 * constant-time operation.
638 * @param list address of the list head.
639 * @returns the first link in the list, or #NULL for an empty list.
642 _dbus_list_pop_first_link (DBusList **list)
646 link = _dbus_list_get_first_link (list);
650 _dbus_list_unlink (list, link);
656 * Removes the first value in the list and returns it. This is a
657 * constant-time operation.
659 * @param list address of the list head.
660 * @returns the first data in the list, or #NULL for an empty list.
663 _dbus_list_pop_first (DBusList **list)
668 link = _dbus_list_get_first_link (list);
673 _dbus_list_remove_link (list, link);
679 * Removes the last value in the list and returns it. This is a
680 * constant-time operation.
682 * @param list address of the list head.
683 * @returns the last data in the list, or #NULL for an empty list.
686 _dbus_list_pop_last (DBusList **list)
691 link = _dbus_list_get_last_link (list);
696 _dbus_list_remove_link (list, link);
701 #ifdef DBUS_BUILD_TESTS
703 * Removes the last link in the list and returns it. This is a
704 * constant-time operation.
706 * @param list address of the list head.
707 * @returns the last link in the list, or #NULL for an empty list.
710 _dbus_list_pop_last_link (DBusList **list)
714 link = _dbus_list_get_last_link (list);
718 _dbus_list_unlink (list, link);
722 #endif /* DBUS_BUILD_TESTS */
725 * Copies a list. This is a linear-time operation. If there isn't
726 * enough memory to copy the entire list, the destination list will be
729 * @param list address of the head of the list to copy.
730 * @param dest address where the copied list should be placed.
731 * @returns #TRUE on success, #FALSE if not enough memory.
734 _dbus_list_copy (DBusList **list,
739 _dbus_assert (list != dest);
746 if (!_dbus_list_append (dest, link->data))
748 /* free what we have so far */
749 _dbus_list_clear (dest);
753 link = _dbus_list_get_next_link (list, link);
760 * Gets the length of a list. This is a linear-time
763 * @param list address of the head of the list
764 * @returns number of elements in the list.
767 _dbus_list_get_length (DBusList **list)
779 link = _dbus_list_get_next_link (list, link);
786 * Calls the given function for each element in the list. The
787 * function is passed the list element as its first argument, and the
788 * given data as its second argument.
790 * @param list address of the head of the list.
791 * @param function function to call for each element.
792 * @param data extra data for the function.
796 _dbus_list_foreach (DBusList **list,
797 DBusForeachFunction function,
805 DBusList *next = _dbus_list_get_next_link (list, link);
807 (* function) (link->data, data);
814 * Check whether length is exactly one.
816 * @param list the list
817 * @returns #TRUE if length is exactly one
820 _dbus_list_length_is_one (DBusList **list)
822 return (*list != NULL &&
823 (*list)->next == *list);
828 #ifdef DBUS_BUILD_TESTS
829 #include "dbus-test.h"
833 verify_list (DBusList **list)
843 if (link->next == link)
845 _dbus_assert (link->prev == link);
846 _dbus_assert (*list == link);
854 _dbus_assert (link->prev->next == link);
855 _dbus_assert (link->next->prev == link);
858 while (link != *list);
860 _dbus_assert (length == _dbus_list_get_length (list));
863 _dbus_assert (_dbus_list_length_is_one (list));
865 _dbus_assert (!_dbus_list_length_is_one (list));
869 is_ascending_sequence (DBusList **list)
874 prev = _DBUS_INT_MIN;
876 link = _dbus_list_get_first_link (list);
879 int v = _DBUS_POINTER_TO_INT (link->data);
886 link = _dbus_list_get_next_link (list, link);
893 is_descending_sequence (DBusList **list)
898 prev = _DBUS_INT_MAX;
900 link = _dbus_list_get_first_link (list);
903 int v = _DBUS_POINTER_TO_INT (link->data);
910 link = _dbus_list_get_next_link (list, link);
917 all_even_values (DBusList **list)
921 link = _dbus_list_get_first_link (list);
924 int v = _DBUS_POINTER_TO_INT (link->data);
929 link = _dbus_list_get_next_link (list, link);
936 all_odd_values (DBusList **list)
940 link = _dbus_list_get_first_link (list);
943 int v = _DBUS_POINTER_TO_INT (link->data);
948 link = _dbus_list_get_next_link (list, link);
955 lists_equal (DBusList **list1,
961 link1 = _dbus_list_get_first_link (list1);
962 link2 = _dbus_list_get_first_link (list2);
963 while (link1 && link2)
965 if (link1->data != link2->data)
968 link1 = _dbus_list_get_next_link (list1, link1);
969 link2 = _dbus_list_get_next_link (list2, link2);
979 * @ingroup DBusListInternals
980 * Unit test for DBusList
981 * @returns #TRUE on success.
984 _dbus_list_test (void)
997 /* Test append and prepend */
1002 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1003 _dbus_assert_not_reached ("could not allocate for append");
1005 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1006 _dbus_assert_not_reached ("count not allocate for prepend");
1009 verify_list (&list1);
1010 verify_list (&list2);
1012 _dbus_assert (_dbus_list_get_length (&list1) == i);
1013 _dbus_assert (_dbus_list_get_length (&list2) == i);
1016 _dbus_assert (is_ascending_sequence (&list1));
1017 _dbus_assert (is_descending_sequence (&list2));
1019 /* Test list clear */
1020 _dbus_list_clear (&list1);
1021 _dbus_list_clear (&list2);
1023 verify_list (&list1);
1024 verify_list (&list2);
1026 /* Test get_first, get_last, pop_first, pop_last */
1031 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1032 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1045 got_data1 = _dbus_list_get_last (&list1);
1046 got_data2 = _dbus_list_get_first (&list2);
1048 data1 = _dbus_list_pop_last (&list1);
1049 data2 = _dbus_list_pop_first (&list2);
1051 _dbus_assert (got_data1 == data1);
1052 _dbus_assert (got_data2 == data2);
1054 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1055 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1057 verify_list (&list1);
1058 verify_list (&list2);
1060 _dbus_assert (is_ascending_sequence (&list1));
1061 _dbus_assert (is_descending_sequence (&list2));
1066 _dbus_assert (list1 == NULL);
1067 _dbus_assert (list2 == NULL);
1069 /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */
1074 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1075 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1082 DBusList *got_link1;
1083 DBusList *got_link2;
1091 got_link1 = _dbus_list_get_last_link (&list1);
1092 got_link2 = _dbus_list_get_first_link (&list2);
1094 link1 = _dbus_list_pop_last_link (&list1);
1095 link2 = _dbus_list_pop_first_link (&list2);
1097 _dbus_assert (got_link1 == link1);
1098 _dbus_assert (got_link2 == link2);
1100 data1 = link1->data;
1101 data2 = link2->data;
1103 _dbus_list_free_link (link1);
1104 _dbus_list_free_link (link2);
1106 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1107 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1109 verify_list (&list1);
1110 verify_list (&list2);
1112 _dbus_assert (is_ascending_sequence (&list1));
1113 _dbus_assert (is_descending_sequence (&list2));
1118 _dbus_assert (list1 == NULL);
1119 _dbus_assert (list2 == NULL);
1121 /* Test iteration */
1126 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1127 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1130 verify_list (&list1);
1131 verify_list (&list2);
1133 _dbus_assert (_dbus_list_get_length (&list1) == i);
1134 _dbus_assert (_dbus_list_get_length (&list2) == i);
1137 _dbus_assert (is_ascending_sequence (&list1));
1138 _dbus_assert (is_descending_sequence (&list2));
1141 link2 = _dbus_list_get_first_link (&list2);
1142 while (link2 != NULL)
1144 verify_list (&link2); /* pretend this link is the head */
1146 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1148 link2 = _dbus_list_get_next_link (&list2, link2);
1153 link1 = _dbus_list_get_first_link (&list1);
1154 while (link1 != NULL)
1156 verify_list (&link1); /* pretend this link is the head */
1158 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1160 link1 = _dbus_list_get_next_link (&list1, link1);
1165 link1 = _dbus_list_get_last_link (&list1);
1166 while (link1 != NULL)
1168 verify_list (&link1); /* pretend this link is the head */
1170 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1172 link1 = _dbus_list_get_prev_link (&list1, link1);
1176 _dbus_list_clear (&list1);
1177 _dbus_list_clear (&list2);
1184 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1185 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1194 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1195 _dbus_assert_not_reached ("element should have been in list");
1196 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1197 _dbus_assert_not_reached ("element should have been in list");
1199 verify_list (&list1);
1200 verify_list (&list2);
1205 _dbus_assert (all_odd_values (&list1));
1206 _dbus_assert (all_odd_values (&list2));
1208 _dbus_list_clear (&list1);
1209 _dbus_list_clear (&list2);
1211 /* test removing the other half of the elements */
1216 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1217 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1226 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1227 _dbus_assert_not_reached ("element should have been in list");
1228 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1229 _dbus_assert_not_reached ("element should have been in list");
1231 verify_list (&list1);
1232 verify_list (&list2);
1237 _dbus_assert (all_even_values (&list1));
1238 _dbus_assert (all_even_values (&list2));
1240 /* clear list using remove_link */
1241 while (list1 != NULL)
1243 _dbus_list_remove_link (&list1, list1);
1244 verify_list (&list1);
1246 while (list2 != NULL)
1248 _dbus_list_remove_link (&list2, list2);
1249 verify_list (&list2);
1252 /* Test remove link more generally */
1256 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1257 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1262 link2 = _dbus_list_get_first_link (&list2);
1263 while (link2 != NULL)
1265 DBusList *next = _dbus_list_get_next_link (&list2, link2);
1267 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1270 _dbus_list_remove_link (&list2, link2);
1272 verify_list (&list2);
1278 _dbus_assert (all_odd_values (&list2));
1279 _dbus_list_clear (&list2);
1282 link1 = _dbus_list_get_first_link (&list1);
1283 while (link1 != NULL)
1285 DBusList *next = _dbus_list_get_next_link (&list1, link1);
1287 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1290 _dbus_list_remove_link (&list1, link1);
1292 verify_list (&list1);
1298 _dbus_assert (all_even_values (&list1));
1299 _dbus_list_clear (&list1);
1301 /* Test copying a list */
1305 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1306 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1310 /* bad pointers, because they are allowed in the copy dest */
1311 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1312 copy2 = _DBUS_INT_TO_POINTER (23);
1314 _dbus_list_copy (&list1, ©1);
1315 verify_list (&list1);
1316 verify_list (©1);
1317 _dbus_assert (lists_equal (&list1, ©1));
1319 _dbus_list_copy (&list2, ©2);
1320 verify_list (&list2);
1321 verify_list (©2);
1322 _dbus_assert (lists_equal (&list2, ©2));
1324 /* Now test copying empty lists */
1325 _dbus_list_clear (&list1);
1326 _dbus_list_clear (&list2);
1327 _dbus_list_clear (©1);
1328 _dbus_list_clear (©2);
1330 /* bad pointers, because they are allowed in the copy dest */
1331 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1332 copy2 = _DBUS_INT_TO_POINTER (23);
1334 _dbus_list_copy (&list1, ©1);
1335 verify_list (&list1);
1336 verify_list (©1);
1337 _dbus_assert (lists_equal (&list1, ©1));
1339 _dbus_list_copy (&list2, ©2);
1340 verify_list (&list2);
1341 verify_list (©2);
1342 _dbus_assert (lists_equal (&list2, ©2));
1344 _dbus_list_clear (&list1);
1345 _dbus_list_clear (&list2);
1347 /* insert_before on empty list */
1348 _dbus_list_insert_before (&list1, NULL,
1349 _DBUS_INT_TO_POINTER (0));
1350 verify_list (&list1);
1352 /* inserting before first element */
1353 _dbus_list_insert_before (&list1, list1,
1354 _DBUS_INT_TO_POINTER (2));
1355 verify_list (&list1);
1356 _dbus_assert (is_descending_sequence (&list1));
1358 /* inserting in the middle */
1359 _dbus_list_insert_before (&list1, list1->next,
1360 _DBUS_INT_TO_POINTER (1));
1361 verify_list (&list1);
1362 _dbus_assert (is_descending_sequence (&list1));
1364 /* using insert_before to append */
1365 _dbus_list_insert_before (&list1, NULL,
1366 _DBUS_INT_TO_POINTER (-1));
1367 verify_list (&list1);
1368 _dbus_assert (is_descending_sequence (&list1));
1370 _dbus_list_clear (&list1);
1372 /* insert_after on empty list */
1373 _dbus_list_insert_after (&list1, NULL,
1374 _DBUS_INT_TO_POINTER (0));
1375 verify_list (&list1);
1377 /* inserting after first element */
1378 _dbus_list_insert_after (&list1, list1,
1379 _DBUS_INT_TO_POINTER (1));
1380 verify_list (&list1);
1381 _dbus_assert (is_ascending_sequence (&list1));
1383 /* inserting at the end */
1384 _dbus_list_insert_after (&list1, list1->next,
1385 _DBUS_INT_TO_POINTER (2));
1386 verify_list (&list1);
1387 _dbus_assert (is_ascending_sequence (&list1));
1389 /* using insert_after to prepend */
1390 _dbus_list_insert_after (&list1, NULL,
1391 _DBUS_INT_TO_POINTER (-1));
1392 verify_list (&list1);
1393 _dbus_assert (is_ascending_sequence (&list1));
1395 _dbus_list_clear (&list1);
1397 /* using remove_last */
1398 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2));
1399 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1));
1400 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3));
1402 _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2));
1404 verify_list (&list1);
1405 _dbus_assert (is_ascending_sequence (&list1));
1407 _dbus_list_clear (&list1);