1 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 #include "dbus-internals.h"
26 #include "dbus-list.h"
27 #include "dbus-mempool.h"
28 #include "dbus-threads-internal.h"
31 * @defgroup DBusList Linked list
32 * @ingroup DBusInternals
33 * @brief DBusList data structure
35 * Types and functions related to DBusList.
38 static DBusMemPool *list_pool;
39 _DBUS_DEFINE_GLOBAL_LOCK (list);
42 * @defgroup DBusListInternals Linked list implementation details
43 * @ingroup DBusInternals
44 * @brief DBusList implementation details
46 * The guts of DBusList.
51 /* the mem pool is probably a speed hit, with the thread
52 * lock, though it does still save memory - unknown.
55 alloc_link (void *data)
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)
130 link_after (DBusList **list,
131 DBusList *after_this_link,
142 link->prev = after_this_link;
143 link->next = after_this_link->next;
144 after_this_link->next = link;
145 link->next->prev = link;
152 * @addtogroup DBusList
159 * A node in a linked list.
161 * DBusList is a circular list; that is, the tail of the list
162 * points back to the head of the list. The empty list is
163 * represented by a #NULL pointer.
167 * @def _dbus_list_get_next_link
169 * Gets the next link in the list, or #NULL if
170 * there are no more links. Used for iteration.
174 * link = _dbus_list_get_first_link (&list);
175 * while (link != NULL)
177 * printf ("value is %p\n", link->data);
178 * link = _dbus_list_get_next_link (&link);
182 * @param list address of the list head.
183 * @param link current link.
184 * @returns the next link, or %NULL if none.
189 * @def _dbus_list_get_prev_link
191 * Gets the previous link in the list, or #NULL if
192 * there are no more links. Used for iteration.
196 * link = _dbus_list_get_last_link (&list);
197 * while (link != NULL)
199 * printf ("value is %p\n", link->data);
200 * link = _dbus_list_get_prev_link (&link);
204 * @param list address of the list head.
205 * @param link current link.
206 * @returns the previous link, or %NULL if none.
211 * Allocates a linked list node. Useful for preallocating
212 * nodes and using _dbus_list_append_link() to avoid
215 * @param data the value to store in the link.
216 * @returns a newly allocated link.
219 _dbus_list_alloc_link (void *data)
221 return alloc_link (data);
225 * Frees a linked list node allocated with _dbus_list_alloc_link.
226 * Does not free the data in the node.
228 * @param link the list node
231 _dbus_list_free_link (DBusList *link)
238 * Appends a value to the list. May return #FALSE
239 * if insufficient memory exists to add a list link.
240 * This is a constant-time operation.
242 * @param list address of the list head.
243 * @param data the value to append.
244 * @returns #TRUE on success.
247 _dbus_list_append (DBusList **list,
250 if (!_dbus_list_prepend (list, data))
253 /* Now cycle the list forward one so the prepended node is the tail */
254 *list = (*list)->next;
260 * Prepends a value to the list. May return #FALSE
261 * if insufficient memory exists to add a list link.
262 * This is a constant-time operation.
264 * @param list address of the list head.
265 * @param data the value to prepend.
266 * @returns #TRUE on success.
269 _dbus_list_prepend (DBusList **list,
274 link = alloc_link (data);
278 link_before (list, *list, link);
284 * Appends a link to the list.
285 * Cannot fail due to out of memory.
286 * This is a constant-time operation.
288 * @param list address of the list head.
289 * @param link the link to append.
292 _dbus_list_append_link (DBusList **list,
295 _dbus_list_prepend_link (list, link);
297 /* Now cycle the list forward one so the prepended node is the tail */
298 *list = (*list)->next;
302 * Prepends a link to the list.
303 * Cannot fail due to out of memory.
304 * This is a constant-time operation.
306 * @param list address of the list head.
307 * @param link the link to prepend.
310 _dbus_list_prepend_link (DBusList **list,
313 link_before (list, *list, link);
316 #ifdef DBUS_BUILD_TESTS
318 * Inserts data into the list before the given existing link.
320 * @param list the list to modify
321 * @param before_this_link existing link to insert before, or #NULL to append
322 * @param data the value to insert
323 * @returns #TRUE on success, #FALSE if memory allocation fails
326 _dbus_list_insert_before (DBusList **list,
327 DBusList *before_this_link,
332 if (before_this_link == NULL)
333 return _dbus_list_append (list, data);
336 link = alloc_link (data);
340 link_before (list, before_this_link, link);
345 #endif /* DBUS_BUILD_TESTS */
348 * Inserts data into the list after the given existing link.
350 * @param list the list to modify
351 * @param after_this_link existing link to insert after, or #NULL to prepend
352 * @param data the value to insert
353 * @returns #TRUE on success, #FALSE if memory allocation fails
356 _dbus_list_insert_after (DBusList **list,
357 DBusList *after_this_link,
362 if (after_this_link == NULL)
363 return _dbus_list_prepend (list, data);
366 link = alloc_link (data);
370 link_after (list, after_this_link, link);
377 * Inserts a link into the list before the given existing link.
379 * @param list the list to modify
380 * @param before_this_link existing link to insert before, or #NULL to append
381 * @param link the link to insert
384 _dbus_list_insert_before_link (DBusList **list,
385 DBusList *before_this_link,
388 if (before_this_link == NULL)
389 _dbus_list_append_link (list, link);
391 link_before (list, before_this_link, link);
395 * Inserts a link into the list after the given existing link.
397 * @param list the list to modify
398 * @param after_this_link existing link to insert after, or #NULL to prepend
399 * @param link the link to insert
402 _dbus_list_insert_after_link (DBusList **list,
403 DBusList *after_this_link,
406 if (after_this_link == NULL)
407 _dbus_list_prepend_link (list, link);
409 link_after (list, after_this_link, link);
413 * Removes a value from the list. Only removes the
414 * first value equal to the given data pointer,
415 * even if multiple values exist which match.
416 * This is a linear-time operation.
418 * @param list address of the list head.
419 * @param data the value to remove.
420 * @returns #TRUE if a value was found to remove.
423 _dbus_list_remove (DBusList **list,
431 if (link->data == data)
433 _dbus_list_remove_link (list, link);
437 link = _dbus_list_get_next_link (list, link);
444 * Removes a value from the list. Only removes the
445 * last value equal to the given data pointer,
446 * even if multiple values exist which match.
447 * This is a linear-time operation.
449 * @param list address of the list head.
450 * @param data the value to remove.
451 * @returns #TRUE if a value was found to remove.
454 _dbus_list_remove_last (DBusList **list,
459 link = _dbus_list_find_last (list, data);
462 _dbus_list_remove_link (list, link);
470 * Finds a value in the list. Returns the last link
471 * with value equal to the given data pointer.
472 * This is a linear-time operation.
473 * Returns #NULL if no value found that matches.
475 * @param list address of the list head.
476 * @param data the value to find.
477 * @returns the link if found
480 _dbus_list_find_last (DBusList **list,
485 link = _dbus_list_get_last_link (list);
489 if (link->data == data)
492 link = _dbus_list_get_prev_link (list, link);
499 * Removes the given link from the list, but doesn't
500 * free it. _dbus_list_remove_link() both removes the
501 * link and also frees it.
503 * @param list the list
504 * @param link the link in the list
507 _dbus_list_unlink (DBusList **list,
510 if (link->next == link)
512 /* one-element list */
517 link->prev->next = link->next;
518 link->next->prev = link->prev;
529 * Removes a link from the list. This is a constant-time operation.
531 * @param list address of the list head.
532 * @param link the list link to remove.
535 _dbus_list_remove_link (DBusList **list,
538 _dbus_list_unlink (list, link);
543 * Frees all links in the list and sets the list head to #NULL. Does
544 * not free the data in each link, for obvious reasons. This is a
545 * linear-time operation.
547 * @param list address of the list head.
550 _dbus_list_clear (DBusList **list)
557 DBusList *next = _dbus_list_get_next_link (list, link);
568 * Gets the first link in the list.
569 * This is a constant-time operation.
571 * @param list address of the list head.
572 * @returns the first link, or #NULL for an empty list.
575 _dbus_list_get_first_link (DBusList **list)
581 * Gets the last link in the list.
582 * This is a constant-time operation.
584 * @param list address of the list head.
585 * @returns the last link, or #NULL for an empty list.
588 _dbus_list_get_last_link (DBusList **list)
593 return (*list)->prev;
597 * Gets the last data in the list.
598 * This is a constant-time operation.
600 * @param list address of the list head.
601 * @returns the last data in the list, or #NULL for an empty list.
604 _dbus_list_get_last (DBusList **list)
609 return (*list)->prev->data;
613 * Gets the first data in the list.
614 * This is a constant-time operation.
616 * @param list address of the list head.
617 * @returns the first data in the list, or #NULL for an empty list.
620 _dbus_list_get_first (DBusList **list)
625 return (*list)->data;
629 * Removes the first link in the list and returns it. This is a
630 * constant-time operation.
632 * @param list address of the list head.
633 * @returns the first link in the list, or #NULL for an empty list.
636 _dbus_list_pop_first_link (DBusList **list)
640 link = _dbus_list_get_first_link (list);
644 _dbus_list_unlink (list, link);
650 * Removes the first value in the list and returns it. This is a
651 * constant-time operation.
653 * @param list address of the list head.
654 * @returns the first data in the list, or #NULL for an empty list.
657 _dbus_list_pop_first (DBusList **list)
662 link = _dbus_list_get_first_link (list);
667 _dbus_list_remove_link (list, link);
673 * Removes the last value in the list and returns it. This is a
674 * constant-time operation.
676 * @param list address of the list head.
677 * @returns the last data in the list, or #NULL for an empty list.
680 _dbus_list_pop_last (DBusList **list)
685 link = _dbus_list_get_last_link (list);
690 _dbus_list_remove_link (list, link);
695 #ifdef DBUS_BUILD_TESTS
697 * Removes the last link in the list and returns it. This is a
698 * constant-time operation.
700 * @param list address of the list head.
701 * @returns the last link in the list, or #NULL for an empty list.
704 _dbus_list_pop_last_link (DBusList **list)
708 link = _dbus_list_get_last_link (list);
712 _dbus_list_unlink (list, link);
716 #endif /* DBUS_BUILD_TESTS */
719 * Copies a list. This is a linear-time operation. If there isn't
720 * enough memory to copy the entire list, the destination list will be
723 * @param list address of the head of the list to copy.
724 * @param dest address where the copied list should be placed.
725 * @returns #TRUE on success, #FALSE if not enough memory.
728 _dbus_list_copy (DBusList **list,
733 _dbus_assert (list != dest);
740 if (!_dbus_list_append (dest, link->data))
742 /* free what we have so far */
743 _dbus_list_clear (dest);
747 link = _dbus_list_get_next_link (list, link);
754 * Gets the length of a list. This is a linear-time
757 * @param list address of the head of the list
758 * @returns number of elements in the list.
761 _dbus_list_get_length (DBusList **list)
773 link = _dbus_list_get_next_link (list, link);
780 * Calls the given function for each element in the list. The
781 * function is passed the list element as its first argument, and the
782 * given data as its second argument.
784 * @param list address of the head of the list.
785 * @param function function to call for each element.
786 * @param data extra data for the function.
790 _dbus_list_foreach (DBusList **list,
791 DBusForeachFunction function,
799 DBusList *next = _dbus_list_get_next_link (list, link);
801 (* function) (link->data, data);
808 * Check whether length is exactly one.
810 * @param list the list
811 * @returns #TRUE if length is exactly one
814 _dbus_list_length_is_one (DBusList **list)
816 return (*list != NULL &&
817 (*list)->next == *list);
822 #ifdef DBUS_BUILD_TESTS
823 #include "dbus-test.h"
827 verify_list (DBusList **list)
837 if (link->next == link)
839 _dbus_assert (link->prev == link);
840 _dbus_assert (*list == link);
848 _dbus_assert (link->prev->next == link);
849 _dbus_assert (link->next->prev == link);
852 while (link != *list);
854 _dbus_assert (length == _dbus_list_get_length (list));
857 _dbus_assert (_dbus_list_length_is_one (list));
859 _dbus_assert (!_dbus_list_length_is_one (list));
863 is_ascending_sequence (DBusList **list)
868 prev = _DBUS_INT_MIN;
870 link = _dbus_list_get_first_link (list);
873 int v = _DBUS_POINTER_TO_INT (link->data);
880 link = _dbus_list_get_next_link (list, link);
887 is_descending_sequence (DBusList **list)
892 prev = _DBUS_INT_MAX;
894 link = _dbus_list_get_first_link (list);
897 int v = _DBUS_POINTER_TO_INT (link->data);
904 link = _dbus_list_get_next_link (list, link);
911 all_even_values (DBusList **list)
915 link = _dbus_list_get_first_link (list);
918 int v = _DBUS_POINTER_TO_INT (link->data);
923 link = _dbus_list_get_next_link (list, link);
930 all_odd_values (DBusList **list)
934 link = _dbus_list_get_first_link (list);
937 int v = _DBUS_POINTER_TO_INT (link->data);
942 link = _dbus_list_get_next_link (list, link);
949 lists_equal (DBusList **list1,
955 link1 = _dbus_list_get_first_link (list1);
956 link2 = _dbus_list_get_first_link (list2);
957 while (link1 && link2)
959 if (link1->data != link2->data)
962 link1 = _dbus_list_get_next_link (list1, link1);
963 link2 = _dbus_list_get_next_link (list2, link2);
973 * @ingroup DBusListInternals
974 * Unit test for DBusList
975 * @returns #TRUE on success.
978 _dbus_list_test (void)
991 /* Test append and prepend */
996 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
997 _dbus_assert_not_reached ("could not allocate for append");
999 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1000 _dbus_assert_not_reached ("count not allocate for prepend");
1003 verify_list (&list1);
1004 verify_list (&list2);
1006 _dbus_assert (_dbus_list_get_length (&list1) == i);
1007 _dbus_assert (_dbus_list_get_length (&list2) == i);
1010 _dbus_assert (is_ascending_sequence (&list1));
1011 _dbus_assert (is_descending_sequence (&list2));
1013 /* Test list clear */
1014 _dbus_list_clear (&list1);
1015 _dbus_list_clear (&list2);
1017 verify_list (&list1);
1018 verify_list (&list2);
1020 /* Test get_first, get_last, pop_first, pop_last */
1025 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1026 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1039 got_data1 = _dbus_list_get_last (&list1);
1040 got_data2 = _dbus_list_get_first (&list2);
1042 data1 = _dbus_list_pop_last (&list1);
1043 data2 = _dbus_list_pop_first (&list2);
1045 _dbus_assert (got_data1 == data1);
1046 _dbus_assert (got_data2 == data2);
1048 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1049 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1051 verify_list (&list1);
1052 verify_list (&list2);
1054 _dbus_assert (is_ascending_sequence (&list1));
1055 _dbus_assert (is_descending_sequence (&list2));
1060 _dbus_assert (list1 == NULL);
1061 _dbus_assert (list2 == NULL);
1063 /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */
1068 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1069 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1076 DBusList *got_link1;
1077 DBusList *got_link2;
1085 got_link1 = _dbus_list_get_last_link (&list1);
1086 got_link2 = _dbus_list_get_first_link (&list2);
1088 link1 = _dbus_list_pop_last_link (&list1);
1089 link2 = _dbus_list_pop_first_link (&list2);
1091 _dbus_assert (got_link1 == link1);
1092 _dbus_assert (got_link2 == link2);
1094 data1 = link1->data;
1095 data2 = link2->data;
1097 _dbus_list_free_link (link1);
1098 _dbus_list_free_link (link2);
1100 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1101 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1103 verify_list (&list1);
1104 verify_list (&list2);
1106 _dbus_assert (is_ascending_sequence (&list1));
1107 _dbus_assert (is_descending_sequence (&list2));
1112 _dbus_assert (list1 == NULL);
1113 _dbus_assert (list2 == NULL);
1115 /* Test iteration */
1120 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1121 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1124 verify_list (&list1);
1125 verify_list (&list2);
1127 _dbus_assert (_dbus_list_get_length (&list1) == i);
1128 _dbus_assert (_dbus_list_get_length (&list2) == i);
1131 _dbus_assert (is_ascending_sequence (&list1));
1132 _dbus_assert (is_descending_sequence (&list2));
1135 link2 = _dbus_list_get_first_link (&list2);
1136 while (link2 != NULL)
1138 verify_list (&link2); /* pretend this link is the head */
1140 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1142 link2 = _dbus_list_get_next_link (&list2, link2);
1147 link1 = _dbus_list_get_first_link (&list1);
1148 while (link1 != NULL)
1150 verify_list (&link1); /* pretend this link is the head */
1152 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1154 link1 = _dbus_list_get_next_link (&list1, link1);
1159 link1 = _dbus_list_get_last_link (&list1);
1160 while (link1 != NULL)
1162 verify_list (&link1); /* pretend this link is the head */
1164 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1166 link1 = _dbus_list_get_prev_link (&list1, link1);
1170 _dbus_list_clear (&list1);
1171 _dbus_list_clear (&list2);
1178 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1179 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1188 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1189 _dbus_assert_not_reached ("element should have been in list");
1190 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1191 _dbus_assert_not_reached ("element should have been in list");
1193 verify_list (&list1);
1194 verify_list (&list2);
1199 _dbus_assert (all_odd_values (&list1));
1200 _dbus_assert (all_odd_values (&list2));
1202 _dbus_list_clear (&list1);
1203 _dbus_list_clear (&list2);
1205 /* test removing the other half of the elements */
1210 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1211 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1220 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1221 _dbus_assert_not_reached ("element should have been in list");
1222 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1223 _dbus_assert_not_reached ("element should have been in list");
1225 verify_list (&list1);
1226 verify_list (&list2);
1231 _dbus_assert (all_even_values (&list1));
1232 _dbus_assert (all_even_values (&list2));
1234 /* clear list using remove_link */
1235 while (list1 != NULL)
1237 _dbus_list_remove_link (&list1, list1);
1238 verify_list (&list1);
1240 while (list2 != NULL)
1242 _dbus_list_remove_link (&list2, list2);
1243 verify_list (&list2);
1246 /* Test remove link more generally */
1250 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1251 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1256 link2 = _dbus_list_get_first_link (&list2);
1257 while (link2 != NULL)
1259 DBusList *next = _dbus_list_get_next_link (&list2, link2);
1261 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1264 _dbus_list_remove_link (&list2, link2);
1266 verify_list (&list2);
1272 _dbus_assert (all_odd_values (&list2));
1273 _dbus_list_clear (&list2);
1276 link1 = _dbus_list_get_first_link (&list1);
1277 while (link1 != NULL)
1279 DBusList *next = _dbus_list_get_next_link (&list1, link1);
1281 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1284 _dbus_list_remove_link (&list1, link1);
1286 verify_list (&list1);
1292 _dbus_assert (all_even_values (&list1));
1293 _dbus_list_clear (&list1);
1295 /* Test copying a list */
1299 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1300 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1304 /* bad pointers, because they are allowed in the copy dest */
1305 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1306 copy2 = _DBUS_INT_TO_POINTER (23);
1308 _dbus_list_copy (&list1, ©1);
1309 verify_list (&list1);
1310 verify_list (©1);
1311 _dbus_assert (lists_equal (&list1, ©1));
1313 _dbus_list_copy (&list2, ©2);
1314 verify_list (&list2);
1315 verify_list (©2);
1316 _dbus_assert (lists_equal (&list2, ©2));
1318 /* Now test copying empty lists */
1319 _dbus_list_clear (&list1);
1320 _dbus_list_clear (&list2);
1321 _dbus_list_clear (©1);
1322 _dbus_list_clear (©2);
1324 /* bad pointers, because they are allowed in the copy dest */
1325 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1326 copy2 = _DBUS_INT_TO_POINTER (23);
1328 _dbus_list_copy (&list1, ©1);
1329 verify_list (&list1);
1330 verify_list (©1);
1331 _dbus_assert (lists_equal (&list1, ©1));
1333 _dbus_list_copy (&list2, ©2);
1334 verify_list (&list2);
1335 verify_list (©2);
1336 _dbus_assert (lists_equal (&list2, ©2));
1338 _dbus_list_clear (&list1);
1339 _dbus_list_clear (&list2);
1341 /* insert_before on empty list */
1342 _dbus_list_insert_before (&list1, NULL,
1343 _DBUS_INT_TO_POINTER (0));
1344 verify_list (&list1);
1346 /* inserting before first element */
1347 _dbus_list_insert_before (&list1, list1,
1348 _DBUS_INT_TO_POINTER (2));
1349 verify_list (&list1);
1350 _dbus_assert (is_descending_sequence (&list1));
1352 /* inserting in the middle */
1353 _dbus_list_insert_before (&list1, list1->next,
1354 _DBUS_INT_TO_POINTER (1));
1355 verify_list (&list1);
1356 _dbus_assert (is_descending_sequence (&list1));
1358 /* using insert_before to append */
1359 _dbus_list_insert_before (&list1, NULL,
1360 _DBUS_INT_TO_POINTER (-1));
1361 verify_list (&list1);
1362 _dbus_assert (is_descending_sequence (&list1));
1364 _dbus_list_clear (&list1);
1366 /* insert_after on empty list */
1367 _dbus_list_insert_after (&list1, NULL,
1368 _DBUS_INT_TO_POINTER (0));
1369 verify_list (&list1);
1371 /* inserting after first element */
1372 _dbus_list_insert_after (&list1, list1,
1373 _DBUS_INT_TO_POINTER (1));
1374 verify_list (&list1);
1375 _dbus_assert (is_ascending_sequence (&list1));
1377 /* inserting at the end */
1378 _dbus_list_insert_after (&list1, list1->next,
1379 _DBUS_INT_TO_POINTER (2));
1380 verify_list (&list1);
1381 _dbus_assert (is_ascending_sequence (&list1));
1383 /* using insert_after to prepend */
1384 _dbus_list_insert_after (&list1, NULL,
1385 _DBUS_INT_TO_POINTER (-1));
1386 verify_list (&list1);
1387 _dbus_assert (is_ascending_sequence (&list1));
1389 _dbus_list_clear (&list1);
1391 /* using remove_last */
1392 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2));
1393 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1));
1394 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3));
1396 _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2));
1398 verify_list (&list1);
1399 _dbus_assert (is_ascending_sequence (&list1));
1401 _dbus_list_clear (&list1);