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 /* Protected by _DBUS_LOCK (list) */
39 static DBusMemPool *list_pool;
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)
59 if (!_DBUS_LOCK (list))
62 if (list_pool == NULL)
64 list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE);
66 if (list_pool == NULL)
72 link = _dbus_mem_pool_alloc (list_pool);
75 _dbus_mem_pool_free (list_pool);
83 link = _dbus_mem_pool_alloc (list_pool);
95 free_link (DBusList *link)
97 if (!_DBUS_LOCK (list))
98 _dbus_assert_not_reached ("we should have initialized global locks "
99 "before we allocated a linked-list link");
101 if (_dbus_mem_pool_dealloc (list_pool, link))
103 _dbus_mem_pool_free (list_pool);
111 link_before (DBusList **list,
112 DBusList *before_this_link,
123 link->next = before_this_link;
124 link->prev = before_this_link->prev;
125 before_this_link->prev = link;
126 link->prev->next = link;
128 if (before_this_link == *list)
134 link_after (DBusList **list,
135 DBusList *after_this_link,
146 link->prev = after_this_link;
147 link->next = after_this_link->next;
148 after_this_link->next = link;
149 link->next->prev = link;
153 #ifdef DBUS_ENABLE_STATS
155 _dbus_list_get_stats (dbus_uint32_t *in_use_p,
156 dbus_uint32_t *in_free_list_p,
157 dbus_uint32_t *allocated_p)
159 if (!_DBUS_LOCK (list))
167 _dbus_mem_pool_get_stats (list_pool, in_use_p, in_free_list_p, allocated_p);
175 * @addtogroup DBusList
182 * A node in a linked list.
184 * DBusList is a circular list; that is, the tail of the list
185 * points back to the head of the list. The empty list is
186 * represented by a #NULL pointer.
190 * @def _dbus_list_get_next_link
192 * Gets the next link in the list, or #NULL if
193 * there are no more links. Used for iteration.
197 * link = _dbus_list_get_first_link (&list);
198 * while (link != NULL)
200 * printf ("value is %p\n", link->data);
201 * link = _dbus_list_get_next_link (&link);
205 * @param list address of the list head.
206 * @param link current link.
207 * @returns the next link, or %NULL if none.
212 * @def _dbus_list_get_prev_link
214 * Gets the previous link in the list, or #NULL if
215 * there are no more links. Used for iteration.
219 * link = _dbus_list_get_last_link (&list);
220 * while (link != NULL)
222 * printf ("value is %p\n", link->data);
223 * link = _dbus_list_get_prev_link (&link);
227 * @param list address of the list head.
228 * @param link current link.
229 * @returns the previous link, or %NULL if none.
234 * Allocates a linked list node. Useful for preallocating
235 * nodes and using _dbus_list_append_link() to avoid
238 * @param data the value to store in the link.
239 * @returns a newly allocated link.
242 _dbus_list_alloc_link (void *data)
244 return alloc_link (data);
248 * Frees a linked list node allocated with _dbus_list_alloc_link.
249 * Does not free the data in the node.
251 * @param link the list node
254 _dbus_list_free_link (DBusList *link)
261 * Appends a value to the list. May return #FALSE
262 * if insufficient memory exists to add a list link.
263 * This is a constant-time operation.
265 * @param list address of the list head.
266 * @param data the value to append.
267 * @returns #TRUE on success.
270 _dbus_list_append (DBusList **list,
273 if (!_dbus_list_prepend (list, data))
276 /* Now cycle the list forward one so the prepended node is the tail */
277 *list = (*list)->next;
283 * Prepends a value to the list. May return #FALSE
284 * if insufficient memory exists to add a list link.
285 * This is a constant-time operation.
287 * @param list address of the list head.
288 * @param data the value to prepend.
289 * @returns #TRUE on success.
292 _dbus_list_prepend (DBusList **list,
297 link = alloc_link (data);
301 link_before (list, *list, link);
307 * Appends a link to the list.
308 * Cannot fail due to out of memory.
309 * This is a constant-time operation.
311 * @param list address of the list head.
312 * @param link the link to append.
315 _dbus_list_append_link (DBusList **list,
318 _dbus_list_prepend_link (list, link);
320 /* Now cycle the list forward one so the prepended node is the tail */
321 *list = (*list)->next;
325 * Prepends a link to the list.
326 * Cannot fail due to out of memory.
327 * This is a constant-time operation.
329 * @param list address of the list head.
330 * @param link the link to prepend.
333 _dbus_list_prepend_link (DBusList **list,
336 link_before (list, *list, link);
340 * Inserts data into the list after the given existing link.
342 * @param list the list to modify
343 * @param after_this_link existing link to insert after, or #NULL to prepend
344 * @param data the value to insert
345 * @returns #TRUE on success, #FALSE if memory allocation fails
348 _dbus_list_insert_after (DBusList **list,
349 DBusList *after_this_link,
354 if (after_this_link == NULL)
355 return _dbus_list_prepend (list, data);
358 link = alloc_link (data);
362 link_after (list, after_this_link, link);
369 * Inserts a link into the list before the given existing link.
371 * @param list the list to modify
372 * @param before_this_link existing link to insert before, or #NULL to append
373 * @param link the link to insert
376 _dbus_list_insert_before_link (DBusList **list,
377 DBusList *before_this_link,
380 if (before_this_link == NULL)
381 _dbus_list_append_link (list, link);
383 link_before (list, before_this_link, link);
387 * Inserts a link into the list after the given existing link.
389 * @param list the list to modify
390 * @param after_this_link existing link to insert after, or #NULL to prepend
391 * @param link the link to insert
394 _dbus_list_insert_after_link (DBusList **list,
395 DBusList *after_this_link,
398 if (after_this_link == NULL)
399 _dbus_list_prepend_link (list, link);
401 link_after (list, after_this_link, link);
405 * Removes a value from the list. Only removes the
406 * first 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 (DBusList **list,
423 if (link->data == data)
425 _dbus_list_remove_link (list, link);
429 link = _dbus_list_get_next_link (list, link);
436 * Removes a value from the list. Only removes the
437 * last value equal to the given data pointer,
438 * even if multiple values exist which match.
439 * This is a linear-time operation.
441 * @param list address of the list head.
442 * @param data the value to remove.
443 * @returns #TRUE if a value was found to remove.
446 _dbus_list_remove_last (DBusList **list,
451 link = _dbus_list_find_last (list, data);
454 _dbus_list_remove_link (list, link);
462 * Finds a value in the list. Returns the first link
463 * with value equal to the given data pointer.
464 * This is a linear-time operation.
465 * Returns #NULL if no value found that matches.
467 * @param list address of the list head.
468 * @param data the value to find.
469 * @returns the link if found
472 _dbus_list_find_first (DBusList **list,
477 link = _dbus_list_get_first_link (list);
481 if (link->data == data)
484 link = _dbus_list_get_next_link (list, link);
491 * Finds a value in the list. Returns the last link
492 * with value equal to the given data pointer.
493 * This is a linear-time operation.
494 * Returns #NULL if no value found that matches.
496 * @param list address of the list head.
497 * @param data the value to find.
498 * @returns the link if found
501 _dbus_list_find_last (DBusList **list,
506 link = _dbus_list_get_last_link (list);
510 if (link->data == data)
513 link = _dbus_list_get_prev_link (list, link);
520 * Removes the given link from the list, but doesn't
521 * free it. _dbus_list_remove_link() both removes the
522 * link and also frees it.
524 * @param list the list
525 * @param link the link in the list
528 _dbus_list_unlink (DBusList **list,
531 if (link->next == link)
533 /* one-element list */
538 link->prev->next = link->next;
539 link->next->prev = link->prev;
550 * Removes a link from the list. This is a constant-time operation.
552 * @param list address of the list head.
553 * @param link the list link to remove.
556 _dbus_list_remove_link (DBusList **list,
559 _dbus_list_unlink (list, link);
564 * Frees all links in the list and sets the list head to #NULL. Does
565 * not free the data in each link, for obvious reasons. This is a
566 * linear-time operation.
568 * @param list address of the list head.
571 _dbus_list_clear (DBusList **list)
578 DBusList *next = _dbus_list_get_next_link (list, link);
589 * Gets the first link in the list.
590 * This is a constant-time operation.
592 * @param list address of the list head.
593 * @returns the first link, or #NULL for an empty list.
596 _dbus_list_get_first_link (DBusList **list)
602 * Gets the last link in the list.
603 * This is a constant-time operation.
605 * @param list address of the list head.
606 * @returns the last link, or #NULL for an empty list.
609 _dbus_list_get_last_link (DBusList **list)
614 return (*list)->prev;
618 * Gets the last data in the list.
619 * This is a constant-time operation.
621 * @param list address of the list head.
622 * @returns the last data in the list, or #NULL for an empty list.
625 _dbus_list_get_last (DBusList **list)
630 return (*list)->prev->data;
634 * Gets the first data in the list.
635 * This is a constant-time operation.
637 * @param list address of the list head.
638 * @returns the first data in the list, or #NULL for an empty list.
641 _dbus_list_get_first (DBusList **list)
646 return (*list)->data;
650 * Removes the first link 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 link in the list, or #NULL for an empty list.
657 _dbus_list_pop_first_link (DBusList **list)
661 link = _dbus_list_get_first_link (list);
665 _dbus_list_unlink (list, link);
671 * Removes the first 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 first data in the list, or #NULL for an empty list.
678 _dbus_list_pop_first (DBusList **list)
683 link = _dbus_list_get_first_link (list);
688 _dbus_list_remove_link (list, link);
694 * Removes the last value 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 data in the list, or #NULL for an empty list.
701 _dbus_list_pop_last (DBusList **list)
706 link = _dbus_list_get_last_link (list);
711 _dbus_list_remove_link (list, link);
717 * Copies a list. This is a linear-time operation. If there isn't
718 * enough memory to copy the entire list, the destination list will be
721 * @param list address of the head of the list to copy.
722 * @param dest address where the copied list should be placed.
723 * @returns #TRUE on success, #FALSE if not enough memory.
726 _dbus_list_copy (DBusList **list,
731 _dbus_assert (list != dest);
738 if (!_dbus_list_append (dest, link->data))
740 /* free what we have so far */
741 _dbus_list_clear (dest);
745 link = _dbus_list_get_next_link (list, link);
752 * Gets the length of a list. This is a linear-time
755 * @param list address of the head of the list
756 * @returns number of elements in the list.
759 _dbus_list_get_length (DBusList **list)
771 link = _dbus_list_get_next_link (list, link);
778 * Calls the given function for each element in the list. The
779 * function is passed the list element as its first argument, and the
780 * given data as its second argument.
782 * @param list address of the head of the list.
783 * @param function function to call for each element.
784 * @param data extra data for the function.
788 _dbus_list_foreach (DBusList **list,
789 DBusForeachFunction function,
797 DBusList *next = _dbus_list_get_next_link (list, link);
799 (* function) (link->data, data);
806 * Check whether length is exactly one.
808 * @param list the list
809 * @returns #TRUE if length is exactly one
812 _dbus_list_length_is_one (DBusList **list)
814 return (*list != NULL &&
815 (*list)->next == *list);
820 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
821 #include "dbus-test.h"
825 verify_list (DBusList **list)
835 if (link->next == link)
837 _dbus_assert (link->prev == link);
838 _dbus_assert (*list == link);
846 _dbus_assert (link->prev->next == link);
847 _dbus_assert (link->next->prev == link);
850 while (link != *list);
852 _dbus_assert (length == _dbus_list_get_length (list));
855 _dbus_assert (_dbus_list_length_is_one (list));
857 _dbus_assert (!_dbus_list_length_is_one (list));
861 is_ascending_sequence (DBusList **list)
866 prev = _DBUS_INT_MIN;
868 link = _dbus_list_get_first_link (list);
871 int v = _DBUS_POINTER_TO_INT (link->data);
878 link = _dbus_list_get_next_link (list, link);
885 is_descending_sequence (DBusList **list)
890 prev = _DBUS_INT_MAX;
892 link = _dbus_list_get_first_link (list);
895 int v = _DBUS_POINTER_TO_INT (link->data);
902 link = _dbus_list_get_next_link (list, link);
909 all_even_values (DBusList **list)
913 link = _dbus_list_get_first_link (list);
916 int v = _DBUS_POINTER_TO_INT (link->data);
921 link = _dbus_list_get_next_link (list, link);
928 all_odd_values (DBusList **list)
932 link = _dbus_list_get_first_link (list);
935 int v = _DBUS_POINTER_TO_INT (link->data);
940 link = _dbus_list_get_next_link (list, link);
947 lists_equal (DBusList **list1,
953 link1 = _dbus_list_get_first_link (list1);
954 link2 = _dbus_list_get_first_link (list2);
955 while (link1 && link2)
957 if (link1->data != link2->data)
960 link1 = _dbus_list_get_next_link (list1, link1);
961 link2 = _dbus_list_get_next_link (list2, link2);
971 * @ingroup DBusListInternals
972 * Unit test for DBusList
973 * @returns #TRUE on success.
976 _dbus_list_test (void)
989 /* Test append and prepend */
994 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
995 _dbus_assert_not_reached ("could not allocate for append");
997 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
998 _dbus_assert_not_reached ("count not allocate for prepend");
1001 verify_list (&list1);
1002 verify_list (&list2);
1004 _dbus_assert (_dbus_list_get_length (&list1) == i);
1005 _dbus_assert (_dbus_list_get_length (&list2) == i);
1008 _dbus_assert (is_ascending_sequence (&list1));
1009 _dbus_assert (is_descending_sequence (&list2));
1011 /* Test list clear */
1012 _dbus_list_clear (&list1);
1013 _dbus_list_clear (&list2);
1015 verify_list (&list1);
1016 verify_list (&list2);
1018 /* Test get_first, get_last, pop_first, pop_last */
1023 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1024 _dbus_assert_not_reached ("could not allocate for append");
1025 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1026 _dbus_assert_not_reached ("could not allocate for prepend");
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 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1069 _dbus_assert_not_reached ("could not allocate for append");
1070 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1071 _dbus_assert_not_reached ("could not allocate for prepend");
1078 DBusList *got_link1;
1079 DBusList *got_link2;
1081 void *data1_indirect;
1085 got_link1 = _dbus_list_get_last_link (&list1);
1086 got_link2 = _dbus_list_get_first_link (&list2);
1088 link2 = _dbus_list_pop_first_link (&list2);
1090 _dbus_assert (got_link2 == link2);
1092 data1_indirect = got_link1->data;
1093 /* this call makes got_link1 invalid */
1094 data1 = _dbus_list_pop_last (&list1);
1095 _dbus_assert (data1 == data1_indirect);
1096 data2 = link2->data;
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 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1121 _dbus_assert_not_reached ("could not allocate for append");
1122 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1123 _dbus_assert_not_reached ("could not allocate for prepend");
1126 verify_list (&list1);
1127 verify_list (&list2);
1129 _dbus_assert (_dbus_list_get_length (&list1) == i);
1130 _dbus_assert (_dbus_list_get_length (&list2) == i);
1133 _dbus_assert (is_ascending_sequence (&list1));
1134 _dbus_assert (is_descending_sequence (&list2));
1137 link2 = _dbus_list_get_first_link (&list2);
1138 while (link2 != NULL)
1140 verify_list (&link2); /* pretend this link is the head */
1142 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1144 link2 = _dbus_list_get_next_link (&list2, link2);
1149 link1 = _dbus_list_get_first_link (&list1);
1150 while (link1 != NULL)
1152 verify_list (&link1); /* pretend this link is the head */
1154 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1156 link1 = _dbus_list_get_next_link (&list1, link1);
1161 link1 = _dbus_list_get_last_link (&list1);
1162 while (link1 != NULL)
1164 verify_list (&link1); /* pretend this link is the head */
1166 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1168 link1 = _dbus_list_get_prev_link (&list1, link1);
1172 _dbus_list_clear (&list1);
1173 _dbus_list_clear (&list2);
1180 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1181 _dbus_assert_not_reached ("could not allocate for append");
1182 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1183 _dbus_assert_not_reached ("could not allocate for prepend");
1192 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1193 _dbus_assert_not_reached ("element should have been in list");
1194 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1195 _dbus_assert_not_reached ("element should have been in list");
1197 verify_list (&list1);
1198 verify_list (&list2);
1203 _dbus_assert (all_odd_values (&list1));
1204 _dbus_assert (all_odd_values (&list2));
1206 _dbus_list_clear (&list1);
1207 _dbus_list_clear (&list2);
1209 /* test removing the other half of the elements */
1214 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1215 _dbus_assert_not_reached ("could not allocate for append");
1216 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1217 _dbus_assert_not_reached ("could not allocate for prepend");
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 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1257 _dbus_assert_not_reached ("could not allocate for append");
1258 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1259 _dbus_assert_not_reached ("could not allocate for prepend");
1264 link2 = _dbus_list_get_first_link (&list2);
1265 while (link2 != NULL)
1267 DBusList *next = _dbus_list_get_next_link (&list2, link2);
1269 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1272 _dbus_list_remove_link (&list2, link2);
1274 verify_list (&list2);
1280 _dbus_assert (all_odd_values (&list2));
1281 _dbus_list_clear (&list2);
1284 link1 = _dbus_list_get_first_link (&list1);
1285 while (link1 != NULL)
1287 DBusList *next = _dbus_list_get_next_link (&list1, link1);
1289 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1292 _dbus_list_remove_link (&list1, link1);
1294 verify_list (&list1);
1300 _dbus_assert (all_even_values (&list1));
1301 _dbus_list_clear (&list1);
1303 /* Test copying a list */
1307 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1308 _dbus_assert_not_reached ("could not allocate for append");
1309 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1310 _dbus_assert_not_reached ("could not allocate for prepend");
1314 /* bad pointers, because they are allowed in the copy dest */
1315 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1316 copy2 = _DBUS_INT_TO_POINTER (23);
1318 _dbus_list_copy (&list1, ©1);
1319 verify_list (&list1);
1320 verify_list (©1);
1321 _dbus_assert (lists_equal (&list1, ©1));
1323 _dbus_list_copy (&list2, ©2);
1324 verify_list (&list2);
1325 verify_list (©2);
1326 _dbus_assert (lists_equal (&list2, ©2));
1328 /* Now test copying empty lists */
1329 _dbus_list_clear (&list1);
1330 _dbus_list_clear (&list2);
1331 _dbus_list_clear (©1);
1332 _dbus_list_clear (©2);
1334 /* bad pointers, because they are allowed in the copy dest */
1335 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1336 copy2 = _DBUS_INT_TO_POINTER (23);
1338 _dbus_list_copy (&list1, ©1);
1339 verify_list (&list1);
1340 verify_list (©1);
1341 _dbus_assert (lists_equal (&list1, ©1));
1343 _dbus_list_copy (&list2, ©2);
1344 verify_list (&list2);
1345 verify_list (©2);
1346 _dbus_assert (lists_equal (&list2, ©2));
1348 _dbus_list_clear (&list1);
1349 _dbus_list_clear (&list2);
1351 /* insert_after on empty list */
1352 _dbus_list_insert_after (&list1, NULL,
1353 _DBUS_INT_TO_POINTER (0));
1354 verify_list (&list1);
1356 /* inserting after first element */
1357 _dbus_list_insert_after (&list1, list1,
1358 _DBUS_INT_TO_POINTER (1));
1359 verify_list (&list1);
1360 _dbus_assert (is_ascending_sequence (&list1));
1362 /* inserting at the end */
1363 _dbus_list_insert_after (&list1, list1->next,
1364 _DBUS_INT_TO_POINTER (2));
1365 verify_list (&list1);
1366 _dbus_assert (is_ascending_sequence (&list1));
1368 /* using insert_after to prepend */
1369 _dbus_list_insert_after (&list1, NULL,
1370 _DBUS_INT_TO_POINTER (-1));
1371 verify_list (&list1);
1372 _dbus_assert (is_ascending_sequence (&list1));
1374 _dbus_list_clear (&list1);
1376 /* using remove_last */
1377 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2)))
1378 _dbus_assert_not_reached ("could not allocate for append");
1379 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1)))
1380 _dbus_assert_not_reached ("could not allocate for append");
1381 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3)))
1382 _dbus_assert_not_reached ("could not allocate for append");
1384 _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2));
1386 verify_list (&list1);
1387 _dbus_assert (is_ascending_sequence (&list1));
1389 _dbus_list_clear (&list1);