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))
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);
317 * Inserts data into the list before the given existing link.
319 * @param list the list to modify
320 * @param before_this_link existing link to insert before, or #NULL to append
321 * @param data the value to insert
322 * @returns #TRUE on success, #FALSE if memory allocation fails
325 _dbus_list_insert_before (DBusList **list,
326 DBusList *before_this_link,
331 if (before_this_link == NULL)
332 return _dbus_list_append (list, data);
335 link = alloc_link (data);
339 link_before (list, before_this_link, link);
346 * Inserts data into the list after the given existing link.
348 * @param list the list to modify
349 * @param after_this_link existing link to insert after, or #NULL to prepend
350 * @param data the value to insert
351 * @returns #TRUE on success, #FALSE if memory allocation fails
354 _dbus_list_insert_after (DBusList **list,
355 DBusList *after_this_link,
360 if (after_this_link == NULL)
361 return _dbus_list_prepend (list, data);
364 link = alloc_link (data);
368 link_after (list, after_this_link, link);
375 * Inserts a link into the list before the given existing link.
377 * @param list the list to modify
378 * @param before_this_link existing link to insert before, or #NULL to append
379 * @param link the link to insert
382 _dbus_list_insert_before_link (DBusList **list,
383 DBusList *before_this_link,
386 if (before_this_link == NULL)
387 _dbus_list_append_link (list, link);
389 link_before (list, before_this_link, link);
393 * Inserts a link into the list after the given existing link.
395 * @param list the list to modify
396 * @param after_this_link existing link to insert after, or #NULL to prepend
397 * @param link the link to insert
400 _dbus_list_insert_after_link (DBusList **list,
401 DBusList *after_this_link,
404 if (after_this_link == NULL)
405 _dbus_list_prepend_link (list, link);
407 link_after (list, after_this_link, link);
411 * Removes a value from the list. Only removes the
412 * first value equal to the given data pointer,
413 * even if multiple values exist which match.
414 * This is a linear-time operation.
416 * @param list address of the list head.
417 * @param data the value to remove.
418 * @returns #TRUE if a value was found to remove.
421 _dbus_list_remove (DBusList **list,
429 if (link->data == data)
431 _dbus_list_remove_link (list, link);
435 link = _dbus_list_get_next_link (list, link);
442 * Removes a value from the list. Only removes the
443 * last value equal to the given data pointer,
444 * even if multiple values exist which match.
445 * This is a linear-time operation.
447 * @param list address of the list head.
448 * @param data the value to remove.
449 * @returns #TRUE if a value was found to remove.
452 _dbus_list_remove_last (DBusList **list,
457 link = _dbus_list_find_last (list, data);
460 _dbus_list_remove_link (list, link);
468 * Finds a value in the list. Returns the last link
469 * with value equal to the given data pointer.
470 * This is a linear-time operation.
471 * Returns #NULL if no value found that matches.
473 * @param list address of the list head.
474 * @param data the value to find.
475 * @returns the link if found
478 _dbus_list_find_last (DBusList **list,
483 link = _dbus_list_get_last_link (list);
487 if (link->data == data)
490 link = _dbus_list_get_prev_link (list, link);
497 * Removes the given link from the list, but doesn't
498 * free it. _dbus_list_remove_link() both removes the
499 * link and also frees it.
501 * @param list the list
502 * @param link the link in the list
505 _dbus_list_unlink (DBusList **list,
508 if (link->next == link)
510 /* one-element list */
515 link->prev->next = link->next;
516 link->next->prev = link->prev;
527 * Removes a link from the list. This is a constant-time operation.
529 * @param list address of the list head.
530 * @param link the list link to remove.
533 _dbus_list_remove_link (DBusList **list,
536 _dbus_list_unlink (list, link);
541 * Frees all links in the list and sets the list head to #NULL. Does
542 * not free the data in each link, for obvious reasons. This is a
543 * linear-time operation.
545 * @param list address of the list head.
548 _dbus_list_clear (DBusList **list)
555 DBusList *next = _dbus_list_get_next_link (list, link);
566 * Gets the first link in the list.
567 * This is a constant-time operation.
569 * @param list address of the list head.
570 * @returns the first link, or #NULL for an empty list.
573 _dbus_list_get_first_link (DBusList **list)
579 * Gets the last link in the list.
580 * This is a constant-time operation.
582 * @param list address of the list head.
583 * @returns the last link, or #NULL for an empty list.
586 _dbus_list_get_last_link (DBusList **list)
591 return (*list)->prev;
595 * Gets the last data in the list.
596 * This is a constant-time operation.
598 * @param list address of the list head.
599 * @returns the last data in the list, or #NULL for an empty list.
602 _dbus_list_get_last (DBusList **list)
607 return (*list)->prev->data;
611 * Gets the first data in the list.
612 * This is a constant-time operation.
614 * @param list address of the list head.
615 * @returns the first data in the list, or #NULL for an empty list.
618 _dbus_list_get_first (DBusList **list)
623 return (*list)->data;
627 * Removes the first link in the list and returns it. This is a
628 * constant-time operation.
630 * @param list address of the list head.
631 * @returns the first link in the list, or #NULL for an empty list.
634 _dbus_list_pop_first_link (DBusList **list)
638 link = _dbus_list_get_first_link (list);
642 _dbus_list_unlink (list, link);
648 * Removes the first value in the list and returns it. This is a
649 * constant-time operation.
651 * @param list address of the list head.
652 * @returns the first data in the list, or #NULL for an empty list.
655 _dbus_list_pop_first (DBusList **list)
660 link = _dbus_list_get_first_link (list);
665 _dbus_list_remove_link (list, link);
671 * Removes the last value in the list and returns it. This is a
672 * constant-time operation.
674 * @param list address of the list head.
675 * @returns the last data in the list, or #NULL for an empty list.
678 _dbus_list_pop_last (DBusList **list)
683 link = _dbus_list_get_last_link (list);
688 _dbus_list_remove_link (list, link);
694 * Removes the last link in the list and returns it. This is a
695 * constant-time operation.
697 * @param list address of the list head.
698 * @returns the last link in the list, or #NULL for an empty list.
701 _dbus_list_pop_last_link (DBusList **list)
705 link = _dbus_list_get_last_link (list);
709 _dbus_list_unlink (list, link);
715 * Copies a list. This is a linear-time operation. If there isn't
716 * enough memory to copy the entire list, the destination list will be
719 * @param list address of the head of the list to copy.
720 * @param dest address where the copied list should be placed.
721 * @returns #TRUE on success, #FALSE if not enough memory.
724 _dbus_list_copy (DBusList **list,
729 _dbus_assert (list != dest);
736 if (!_dbus_list_append (dest, link->data))
738 /* free what we have so far */
739 _dbus_list_clear (dest);
743 link = _dbus_list_get_next_link (list, link);
750 * Gets the length of a list. This is a linear-time
753 * @param list address of the head of the list
754 * @returns number of elements in the list.
757 _dbus_list_get_length (DBusList **list)
769 link = _dbus_list_get_next_link (list, link);
776 * Calls the given function for each element in the list. The
777 * function is passed the list element as its first argument, and the
778 * given data as its second argument.
780 * @param list address of the head of the list.
781 * @param function function to call for each element.
782 * @param data extra data for the function.
786 _dbus_list_foreach (DBusList **list,
787 DBusForeachFunction function,
795 DBusList *next = _dbus_list_get_next_link (list, link);
797 (* function) (link->data, data);
804 * Check whether length is exactly one.
806 * @param list the list
807 * @returns #TRUE if length is exactly one
810 _dbus_list_length_is_one (DBusList **list)
812 return (*list != NULL &&
813 (*list)->next == *list);
818 #ifdef DBUS_BUILD_TESTS
819 #include "dbus-test.h"
823 verify_list (DBusList **list)
833 if (link->next == link)
835 _dbus_assert (link->prev == link);
836 _dbus_assert (*list == link);
844 _dbus_assert (link->prev->next == link);
845 _dbus_assert (link->next->prev == link);
848 while (link != *list);
850 _dbus_assert (length == _dbus_list_get_length (list));
853 _dbus_assert (_dbus_list_length_is_one (list));
855 _dbus_assert (!_dbus_list_length_is_one (list));
859 is_ascending_sequence (DBusList **list)
864 prev = _DBUS_INT_MIN;
866 link = _dbus_list_get_first_link (list);
869 int v = _DBUS_POINTER_TO_INT (link->data);
876 link = _dbus_list_get_next_link (list, link);
883 is_descending_sequence (DBusList **list)
888 prev = _DBUS_INT_MAX;
890 link = _dbus_list_get_first_link (list);
893 int v = _DBUS_POINTER_TO_INT (link->data);
900 link = _dbus_list_get_next_link (list, link);
907 all_even_values (DBusList **list)
911 link = _dbus_list_get_first_link (list);
914 int v = _DBUS_POINTER_TO_INT (link->data);
919 link = _dbus_list_get_next_link (list, link);
926 all_odd_values (DBusList **list)
930 link = _dbus_list_get_first_link (list);
933 int v = _DBUS_POINTER_TO_INT (link->data);
938 link = _dbus_list_get_next_link (list, link);
945 lists_equal (DBusList **list1,
951 link1 = _dbus_list_get_first_link (list1);
952 link2 = _dbus_list_get_first_link (list2);
953 while (link1 && link2)
955 if (link1->data != link2->data)
958 link1 = _dbus_list_get_next_link (list1, link1);
959 link2 = _dbus_list_get_next_link (list2, link2);
969 * @ingroup DBusListInternals
970 * Unit test for DBusList
971 * @returns #TRUE on success.
974 _dbus_list_test (void)
987 /* Test append and prepend */
992 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
993 _dbus_assert_not_reached ("could not allocate for append");
995 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
996 _dbus_assert_not_reached ("count not allocate for prepend");
999 verify_list (&list1);
1000 verify_list (&list2);
1002 _dbus_assert (_dbus_list_get_length (&list1) == i);
1003 _dbus_assert (_dbus_list_get_length (&list2) == i);
1006 _dbus_assert (is_ascending_sequence (&list1));
1007 _dbus_assert (is_descending_sequence (&list2));
1009 /* Test list clear */
1010 _dbus_list_clear (&list1);
1011 _dbus_list_clear (&list2);
1013 verify_list (&list1);
1014 verify_list (&list2);
1016 /* Test get_first, get_last, pop_first, pop_last */
1021 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1022 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1035 got_data1 = _dbus_list_get_last (&list1);
1036 got_data2 = _dbus_list_get_first (&list2);
1038 data1 = _dbus_list_pop_last (&list1);
1039 data2 = _dbus_list_pop_first (&list2);
1041 _dbus_assert (got_data1 == data1);
1042 _dbus_assert (got_data2 == data2);
1044 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1045 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1047 verify_list (&list1);
1048 verify_list (&list2);
1050 _dbus_assert (is_ascending_sequence (&list1));
1051 _dbus_assert (is_descending_sequence (&list2));
1056 _dbus_assert (list1 == NULL);
1057 _dbus_assert (list2 == NULL);
1059 /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */
1064 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1065 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1072 DBusList *got_link1;
1073 DBusList *got_link2;
1081 got_link1 = _dbus_list_get_last_link (&list1);
1082 got_link2 = _dbus_list_get_first_link (&list2);
1084 link1 = _dbus_list_pop_last_link (&list1);
1085 link2 = _dbus_list_pop_first_link (&list2);
1087 _dbus_assert (got_link1 == link1);
1088 _dbus_assert (got_link2 == link2);
1090 data1 = link1->data;
1091 data2 = link2->data;
1093 _dbus_list_free_link (link1);
1094 _dbus_list_free_link (link2);
1096 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1097 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1099 verify_list (&list1);
1100 verify_list (&list2);
1102 _dbus_assert (is_ascending_sequence (&list1));
1103 _dbus_assert (is_descending_sequence (&list2));
1108 _dbus_assert (list1 == NULL);
1109 _dbus_assert (list2 == NULL);
1111 /* Test iteration */
1116 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1117 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1120 verify_list (&list1);
1121 verify_list (&list2);
1123 _dbus_assert (_dbus_list_get_length (&list1) == i);
1124 _dbus_assert (_dbus_list_get_length (&list2) == i);
1127 _dbus_assert (is_ascending_sequence (&list1));
1128 _dbus_assert (is_descending_sequence (&list2));
1131 link2 = _dbus_list_get_first_link (&list2);
1132 while (link2 != NULL)
1134 verify_list (&link2); /* pretend this link is the head */
1136 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1138 link2 = _dbus_list_get_next_link (&list2, link2);
1143 link1 = _dbus_list_get_first_link (&list1);
1144 while (link1 != NULL)
1146 verify_list (&link1); /* pretend this link is the head */
1148 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1150 link1 = _dbus_list_get_next_link (&list1, link1);
1155 link1 = _dbus_list_get_last_link (&list1);
1156 while (link1 != NULL)
1158 verify_list (&link1); /* pretend this link is the head */
1160 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1162 link1 = _dbus_list_get_prev_link (&list1, link1);
1166 _dbus_list_clear (&list1);
1167 _dbus_list_clear (&list2);
1174 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1175 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1184 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1185 _dbus_assert_not_reached ("element should have been in list");
1186 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1187 _dbus_assert_not_reached ("element should have been in list");
1189 verify_list (&list1);
1190 verify_list (&list2);
1195 _dbus_assert (all_odd_values (&list1));
1196 _dbus_assert (all_odd_values (&list2));
1198 _dbus_list_clear (&list1);
1199 _dbus_list_clear (&list2);
1201 /* test removing the other half of the elements */
1206 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1207 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1216 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1217 _dbus_assert_not_reached ("element should have been in list");
1218 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1219 _dbus_assert_not_reached ("element should have been in list");
1221 verify_list (&list1);
1222 verify_list (&list2);
1227 _dbus_assert (all_even_values (&list1));
1228 _dbus_assert (all_even_values (&list2));
1230 /* clear list using remove_link */
1231 while (list1 != NULL)
1233 _dbus_list_remove_link (&list1, list1);
1234 verify_list (&list1);
1236 while (list2 != NULL)
1238 _dbus_list_remove_link (&list2, list2);
1239 verify_list (&list2);
1242 /* Test remove link more generally */
1246 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1247 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1252 link2 = _dbus_list_get_first_link (&list2);
1253 while (link2 != NULL)
1255 DBusList *next = _dbus_list_get_next_link (&list2, link2);
1257 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1260 _dbus_list_remove_link (&list2, link2);
1262 verify_list (&list2);
1268 _dbus_assert (all_odd_values (&list2));
1269 _dbus_list_clear (&list2);
1272 link1 = _dbus_list_get_first_link (&list1);
1273 while (link1 != NULL)
1275 DBusList *next = _dbus_list_get_next_link (&list1, link1);
1277 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1280 _dbus_list_remove_link (&list1, link1);
1282 verify_list (&list1);
1288 _dbus_assert (all_even_values (&list1));
1289 _dbus_list_clear (&list1);
1291 /* Test copying a list */
1295 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1296 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1300 /* bad pointers, because they are allowed in the copy dest */
1301 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1302 copy2 = _DBUS_INT_TO_POINTER (23);
1304 _dbus_list_copy (&list1, ©1);
1305 verify_list (&list1);
1306 verify_list (©1);
1307 _dbus_assert (lists_equal (&list1, ©1));
1309 _dbus_list_copy (&list2, ©2);
1310 verify_list (&list2);
1311 verify_list (©2);
1312 _dbus_assert (lists_equal (&list2, ©2));
1314 /* Now test copying empty lists */
1315 _dbus_list_clear (&list1);
1316 _dbus_list_clear (&list2);
1317 _dbus_list_clear (©1);
1318 _dbus_list_clear (©2);
1320 /* bad pointers, because they are allowed in the copy dest */
1321 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1322 copy2 = _DBUS_INT_TO_POINTER (23);
1324 _dbus_list_copy (&list1, ©1);
1325 verify_list (&list1);
1326 verify_list (©1);
1327 _dbus_assert (lists_equal (&list1, ©1));
1329 _dbus_list_copy (&list2, ©2);
1330 verify_list (&list2);
1331 verify_list (©2);
1332 _dbus_assert (lists_equal (&list2, ©2));
1334 _dbus_list_clear (&list1);
1335 _dbus_list_clear (&list2);
1337 /* insert_before on empty list */
1338 _dbus_list_insert_before (&list1, NULL,
1339 _DBUS_INT_TO_POINTER (0));
1340 verify_list (&list1);
1342 /* inserting before first element */
1343 _dbus_list_insert_before (&list1, list1,
1344 _DBUS_INT_TO_POINTER (2));
1345 verify_list (&list1);
1346 _dbus_assert (is_descending_sequence (&list1));
1348 /* inserting in the middle */
1349 _dbus_list_insert_before (&list1, list1->next,
1350 _DBUS_INT_TO_POINTER (1));
1351 verify_list (&list1);
1352 _dbus_assert (is_descending_sequence (&list1));
1354 /* using insert_before to append */
1355 _dbus_list_insert_before (&list1, NULL,
1356 _DBUS_INT_TO_POINTER (-1));
1357 verify_list (&list1);
1358 _dbus_assert (is_descending_sequence (&list1));
1360 _dbus_list_clear (&list1);
1362 /* insert_after on empty list */
1363 _dbus_list_insert_after (&list1, NULL,
1364 _DBUS_INT_TO_POINTER (0));
1365 verify_list (&list1);
1367 /* inserting after first element */
1368 _dbus_list_insert_after (&list1, list1,
1369 _DBUS_INT_TO_POINTER (1));
1370 verify_list (&list1);
1371 _dbus_assert (is_ascending_sequence (&list1));
1373 /* inserting at the end */
1374 _dbus_list_insert_after (&list1, list1->next,
1375 _DBUS_INT_TO_POINTER (2));
1376 verify_list (&list1);
1377 _dbus_assert (is_ascending_sequence (&list1));
1379 /* using insert_after to prepend */
1380 _dbus_list_insert_after (&list1, NULL,
1381 _DBUS_INT_TO_POINTER (-1));
1382 verify_list (&list1);
1383 _dbus_assert (is_ascending_sequence (&list1));
1385 _dbus_list_clear (&list1);
1387 /* using remove_last */
1388 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2));
1389 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1));
1390 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3));
1392 _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2));
1394 verify_list (&list1);
1395 _dbus_assert (is_ascending_sequence (&list1));
1397 _dbus_list_clear (&list1);