D-Bus  1.4.10
dbus-list.c
1 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
2 /* dbus-list.c Generic linked list utility (internal to D-Bus implementation)
3  *
4  * Copyright (C) 2002 Red Hat, Inc.
5  *
6  * Licensed under the Academic Free License version 2.1
7  *
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.
12  *
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.
17  *
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
21  *
22  */
23 
24 #include <config.h>
25 #include "dbus-internals.h"
26 #include "dbus-list.h"
27 #include "dbus-mempool.h"
28 #include "dbus-threads-internal.h"
29 
38 static DBusMemPool *list_pool;
40 
51 /* the mem pool is probably a speed hit, with the thread
52  * lock, though it does still save memory - unknown.
53  */
54 static DBusList*
55 alloc_link (void *data)
56 {
57  DBusList *link;
58 
59  _DBUS_LOCK (list);
60 
61  if (list_pool == NULL)
62  {
63  list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE);
64 
65  if (list_pool == NULL)
66  {
67  _DBUS_UNLOCK (list);
68  return NULL;
69  }
70 
71  link = _dbus_mem_pool_alloc (list_pool);
72  if (link == NULL)
73  {
74  _dbus_mem_pool_free (list_pool);
75  list_pool = NULL;
76  _DBUS_UNLOCK (list);
77  return NULL;
78  }
79  }
80  else
81  {
82  link = _dbus_mem_pool_alloc (list_pool);
83  }
84 
85  if (link)
86  link->data = data;
87 
88  _DBUS_UNLOCK (list);
89 
90  return link;
91 }
92 
93 static void
94 free_link (DBusList *link)
95 {
96  _DBUS_LOCK (list);
97  if (_dbus_mem_pool_dealloc (list_pool, link))
98  {
99  _dbus_mem_pool_free (list_pool);
100  list_pool = NULL;
101  }
102 
103  _DBUS_UNLOCK (list);
104 }
105 
106 static void
107 link_before (DBusList **list,
108  DBusList *before_this_link,
109  DBusList *link)
110 {
111  if (*list == NULL)
112  {
113  link->prev = link;
114  link->next = link;
115  *list = link;
116  }
117  else
118  {
119  link->next = before_this_link;
120  link->prev = before_this_link->prev;
121  before_this_link->prev = link;
122  link->prev->next = link;
123 
124  if (before_this_link == *list)
125  *list = link;
126  }
127 }
128 
129 static void
130 link_after (DBusList **list,
131  DBusList *after_this_link,
132  DBusList *link)
133 {
134  if (*list == NULL)
135  {
136  link->prev = link;
137  link->next = link;
138  *list = link;
139  }
140  else
141  {
142  link->prev = after_this_link;
143  link->next = after_this_link->next;
144  after_this_link->next = link;
145  link->next->prev = link;
146  }
147 }
148 
218 DBusList*
220 {
221  return alloc_link (data);
222 }
223 
230 void
232 {
233  free_link (link);
234 }
235 
236 
248  void *data)
249 {
250  if (!_dbus_list_prepend (list, data))
251  return FALSE;
252 
253  /* Now cycle the list forward one so the prepended node is the tail */
254  *list = (*list)->next;
255 
256  return TRUE;
257 }
258 
270  void *data)
271 {
272  DBusList *link;
273 
274  link = alloc_link (data);
275  if (link == NULL)
276  return FALSE;
277 
278  link_before (list, *list, link);
279 
280  return TRUE;
281 }
282 
291 void
293  DBusList *link)
294 {
295  _dbus_list_prepend_link (list, link);
296 
297  /* Now cycle the list forward one so the prepended node is the tail */
298  *list = (*list)->next;
299 }
300 
309 void
311  DBusList *link)
312 {
313  link_before (list, *list, link);
314 }
315 
316 #ifdef DBUS_BUILD_TESTS
317 
326 _dbus_list_insert_before (DBusList **list,
327  DBusList *before_this_link,
328  void *data)
329 {
330  DBusList *link;
331 
332  if (before_this_link == NULL)
333  return _dbus_list_append (list, data);
334  else
335  {
336  link = alloc_link (data);
337  if (link == NULL)
338  return FALSE;
339 
340  link_before (list, before_this_link, link);
341  }
342 
343  return TRUE;
344 }
345 #endif /* DBUS_BUILD_TESTS */
346 
357  DBusList *after_this_link,
358  void *data)
359 {
360  DBusList *link;
361 
362  if (after_this_link == NULL)
363  return _dbus_list_prepend (list, data);
364  else
365  {
366  link = alloc_link (data);
367  if (link == NULL)
368  return FALSE;
369 
370  link_after (list, after_this_link, link);
371  }
372 
373  return TRUE;
374 }
375 
383 void
385  DBusList *before_this_link,
386  DBusList *link)
387 {
388  if (before_this_link == NULL)
389  _dbus_list_append_link (list, link);
390  else
391  link_before (list, before_this_link, link);
392 }
393 
401 void
403  DBusList *after_this_link,
404  DBusList *link)
405 {
406  if (after_this_link == NULL)
407  _dbus_list_prepend_link (list, link);
408  else
409  link_after (list, after_this_link, link);
410 }
411 
424  void *data)
425 {
426  DBusList *link;
427 
428  link = *list;
429  while (link != NULL)
430  {
431  if (link->data == data)
432  {
433  _dbus_list_remove_link (list, link);
434  return TRUE;
435  }
436 
437  link = _dbus_list_get_next_link (list, link);
438  }
439 
440  return FALSE;
441 }
442 
455  void *data)
456 {
457  DBusList *link;
458 
459  link = _dbus_list_find_last (list, data);
460  if (link)
461  {
462  _dbus_list_remove_link (list, link);
463  return TRUE;
464  }
465  else
466  return FALSE;
467 }
468 
479 DBusList*
481  void *data)
482 {
483  DBusList *link;
484 
485  link = _dbus_list_get_last_link (list);
486 
487  while (link != NULL)
488  {
489  if (link->data == data)
490  return link;
491 
492  link = _dbus_list_get_prev_link (list, link);
493  }
494 
495  return NULL;
496 }
497 
506 void
508  DBusList *link)
509 {
510  if (link->next == link)
511  {
512  /* one-element list */
513  *list = NULL;
514  }
515  else
516  {
517  link->prev->next = link->next;
518  link->next->prev = link->prev;
519 
520  if (*list == link)
521  *list = link->next;
522  }
523 
524  link->next = NULL;
525  link->prev = NULL;
526 }
527 
534 void
536  DBusList *link)
537 {
538  _dbus_list_unlink (list, link);
539  free_link (link);
540 }
541 
549 void
551 {
552  DBusList *link;
553 
554  link = *list;
555  while (link != NULL)
556  {
557  DBusList *next = _dbus_list_get_next_link (list, link);
558 
559  free_link (link);
560 
561  link = next;
562  }
563 
564  *list = NULL;
565 }
566 
574 DBusList*
576 {
577  return *list;
578 }
579 
587 DBusList*
589 {
590  if (*list == NULL)
591  return NULL;
592  else
593  return (*list)->prev;
594 }
595 
603 void*
605 {
606  if (*list == NULL)
607  return NULL;
608  else
609  return (*list)->prev->data;
610 }
611 
619 void*
621 {
622  if (*list == NULL)
623  return NULL;
624  else
625  return (*list)->data;
626 }
627 
635 DBusList*
637 {
638  DBusList *link;
639 
640  link = _dbus_list_get_first_link (list);
641  if (link == NULL)
642  return NULL;
643 
644  _dbus_list_unlink (list, link);
645 
646  return link;
647 }
648 
656 void*
658 {
659  DBusList *link;
660  void *data;
661 
662  link = _dbus_list_get_first_link (list);
663  if (link == NULL)
664  return NULL;
665 
666  data = link->data;
667  _dbus_list_remove_link (list, link);
668 
669  return data;
670 }
671 
679 void*
681 {
682  DBusList *link;
683  void *data;
684 
685  link = _dbus_list_get_last_link (list);
686  if (link == NULL)
687  return NULL;
688 
689  data = link->data;
690  _dbus_list_remove_link (list, link);
691 
692  return data;
693 }
694 
695 #ifdef DBUS_BUILD_TESTS
696 
703 DBusList*
704 _dbus_list_pop_last_link (DBusList **list)
705 {
706  DBusList *link;
707 
708  link = _dbus_list_get_last_link (list);
709  if (link == NULL)
710  return NULL;
711 
712  _dbus_list_unlink (list, link);
713 
714  return link;
715 }
716 #endif /* DBUS_BUILD_TESTS */
717 
729  DBusList **dest)
730 {
731  DBusList *link;
732 
733  _dbus_assert (list != dest);
734 
735  *dest = NULL;
736 
737  link = *list;
738  while (link != NULL)
739  {
740  if (!_dbus_list_append (dest, link->data))
741  {
742  /* free what we have so far */
743  _dbus_list_clear (dest);
744  return FALSE;
745  }
746 
747  link = _dbus_list_get_next_link (list, link);
748  }
749 
750  return TRUE;
751 }
752 
760 int
762 {
763  DBusList *link;
764  int length;
765 
766  length = 0;
767 
768  link = *list;
769  while (link != NULL)
770  {
771  ++length;
772 
773  link = _dbus_list_get_next_link (list, link);
774  }
775 
776  return length;
777 }
778 
789 void
791  DBusForeachFunction function,
792  void *data)
793 {
794  DBusList *link;
795 
796  link = *list;
797  while (link != NULL)
798  {
799  DBusList *next = _dbus_list_get_next_link (list, link);
800 
801  (* function) (link->data, data);
802 
803  link = next;
804  }
805 }
806 
815 {
816  return (*list != NULL &&
817  (*list)->next == *list);
818 }
819 
822 #ifdef DBUS_BUILD_TESTS
823 #include "dbus-test.h"
824 #include <stdio.h>
825 
826 static void
827 verify_list (DBusList **list)
828 {
829  DBusList *link;
830  int length;
831 
832  link = *list;
833 
834  if (link == NULL)
835  return;
836 
837  if (link->next == link)
838  {
839  _dbus_assert (link->prev == link);
840  _dbus_assert (*list == link);
841  return;
842  }
843 
844  length = 0;
845  do
846  {
847  length += 1;
848  _dbus_assert (link->prev->next == link);
849  _dbus_assert (link->next->prev == link);
850  link = link->next;
851  }
852  while (link != *list);
853 
854  _dbus_assert (length == _dbus_list_get_length (list));
855 
856  if (length == 1)
858  else
860 }
861 
862 static dbus_bool_t
863 is_ascending_sequence (DBusList **list)
864 {
865  DBusList *link;
866  int prev;
867 
868  prev = _DBUS_INT_MIN;
869 
870  link = _dbus_list_get_first_link (list);
871  while (link != NULL)
872  {
873  int v = _DBUS_POINTER_TO_INT (link->data);
874 
875  if (v <= prev)
876  return FALSE;
877 
878  prev = v;
879 
880  link = _dbus_list_get_next_link (list, link);
881  }
882 
883  return TRUE;
884 }
885 
886 static dbus_bool_t
887 is_descending_sequence (DBusList **list)
888 {
889  DBusList *link;
890  int prev;
891 
892  prev = _DBUS_INT_MAX;
893 
894  link = _dbus_list_get_first_link (list);
895  while (link != NULL)
896  {
897  int v = _DBUS_POINTER_TO_INT (link->data);
898 
899  if (v >= prev)
900  return FALSE;
901 
902  prev = v;
903 
904  link = _dbus_list_get_next_link (list, link);
905  }
906 
907  return TRUE;
908 }
909 
910 static dbus_bool_t
911 all_even_values (DBusList **list)
912 {
913  DBusList *link;
914 
915  link = _dbus_list_get_first_link (list);
916  while (link != NULL)
917  {
918  int v = _DBUS_POINTER_TO_INT (link->data);
919 
920  if ((v % 2) != 0)
921  return FALSE;
922 
923  link = _dbus_list_get_next_link (list, link);
924  }
925 
926  return TRUE;
927 }
928 
929 static dbus_bool_t
930 all_odd_values (DBusList **list)
931 {
932  DBusList *link;
933 
934  link = _dbus_list_get_first_link (list);
935  while (link != NULL)
936  {
937  int v = _DBUS_POINTER_TO_INT (link->data);
938 
939  if ((v % 2) == 0)
940  return FALSE;
941 
942  link = _dbus_list_get_next_link (list, link);
943  }
944 
945  return TRUE;
946 }
947 
948 static dbus_bool_t
949 lists_equal (DBusList **list1,
950  DBusList **list2)
951 {
952  DBusList *link1;
953  DBusList *link2;
954 
955  link1 = _dbus_list_get_first_link (list1);
956  link2 = _dbus_list_get_first_link (list2);
957  while (link1 && link2)
958  {
959  if (link1->data != link2->data)
960  return FALSE;
961 
962  link1 = _dbus_list_get_next_link (list1, link1);
963  link2 = _dbus_list_get_next_link (list2, link2);
964  }
965 
966  if (link1 || link2)
967  return FALSE;
968 
969  return TRUE;
970 }
971 
978 _dbus_list_test (void)
979 {
980  DBusList *list1;
981  DBusList *list2;
982  DBusList *link1;
983  DBusList *link2;
984  DBusList *copy1;
985  DBusList *copy2;
986  int i;
987 
988  list1 = NULL;
989  list2 = NULL;
990 
991  /* Test append and prepend */
992 
993  i = 0;
994  while (i < 10)
995  {
996  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
997  _dbus_assert_not_reached ("could not allocate for append");
998 
999  if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1000  _dbus_assert_not_reached ("count not allocate for prepend");
1001  ++i;
1002 
1003  verify_list (&list1);
1004  verify_list (&list2);
1005 
1006  _dbus_assert (_dbus_list_get_length (&list1) == i);
1007  _dbus_assert (_dbus_list_get_length (&list2) == i);
1008  }
1009 
1010  _dbus_assert (is_ascending_sequence (&list1));
1011  _dbus_assert (is_descending_sequence (&list2));
1012 
1013  /* Test list clear */
1014  _dbus_list_clear (&list1);
1015  _dbus_list_clear (&list2);
1016 
1017  verify_list (&list1);
1018  verify_list (&list2);
1019 
1020  /* Test get_first, get_last, pop_first, pop_last */
1021 
1022  i = 0;
1023  while (i < 10)
1024  {
1027  ++i;
1028  }
1029 
1030  --i;
1031  while (i >= 0)
1032  {
1033  void *got_data1;
1034  void *got_data2;
1035 
1036  void *data1;
1037  void *data2;
1038 
1039  got_data1 = _dbus_list_get_last (&list1);
1040  got_data2 = _dbus_list_get_first (&list2);
1041 
1042  data1 = _dbus_list_pop_last (&list1);
1043  data2 = _dbus_list_pop_first (&list2);
1044 
1045  _dbus_assert (got_data1 == data1);
1046  _dbus_assert (got_data2 == data2);
1047 
1048  _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1049  _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1050 
1051  verify_list (&list1);
1052  verify_list (&list2);
1053 
1054  _dbus_assert (is_ascending_sequence (&list1));
1055  _dbus_assert (is_descending_sequence (&list2));
1056 
1057  --i;
1058  }
1059 
1060  _dbus_assert (list1 == NULL);
1061  _dbus_assert (list2 == NULL);
1062 
1063  /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */
1064 
1065  i = 0;
1066  while (i < 10)
1067  {
1070  ++i;
1071  }
1072 
1073  --i;
1074  while (i >= 0)
1075  {
1076  DBusList *got_link1;
1077  DBusList *got_link2;
1078 
1079  DBusList *link1;
1080  DBusList *link2;
1081 
1082  void *data1;
1083  void *data2;
1084 
1085  got_link1 = _dbus_list_get_last_link (&list1);
1086  got_link2 = _dbus_list_get_first_link (&list2);
1087 
1088  link1 = _dbus_list_pop_last_link (&list1);
1089  link2 = _dbus_list_pop_first_link (&list2);
1090 
1091  _dbus_assert (got_link1 == link1);
1092  _dbus_assert (got_link2 == link2);
1093 
1094  data1 = link1->data;
1095  data2 = link2->data;
1096 
1097  _dbus_list_free_link (link1);
1098  _dbus_list_free_link (link2);
1099 
1100  _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1101  _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1102 
1103  verify_list (&list1);
1104  verify_list (&list2);
1105 
1106  _dbus_assert (is_ascending_sequence (&list1));
1107  _dbus_assert (is_descending_sequence (&list2));
1108 
1109  --i;
1110  }
1111 
1112  _dbus_assert (list1 == NULL);
1113  _dbus_assert (list2 == NULL);
1114 
1115  /* Test iteration */
1116 
1117  i = 0;
1118  while (i < 10)
1119  {
1122  ++i;
1123 
1124  verify_list (&list1);
1125  verify_list (&list2);
1126 
1127  _dbus_assert (_dbus_list_get_length (&list1) == i);
1128  _dbus_assert (_dbus_list_get_length (&list2) == i);
1129  }
1130 
1131  _dbus_assert (is_ascending_sequence (&list1));
1132  _dbus_assert (is_descending_sequence (&list2));
1133 
1134  --i;
1135  link2 = _dbus_list_get_first_link (&list2);
1136  while (link2 != NULL)
1137  {
1138  verify_list (&link2); /* pretend this link is the head */
1139 
1140  _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1141 
1142  link2 = _dbus_list_get_next_link (&list2, link2);
1143  --i;
1144  }
1145 
1146  i = 0;
1147  link1 = _dbus_list_get_first_link (&list1);
1148  while (link1 != NULL)
1149  {
1150  verify_list (&link1); /* pretend this link is the head */
1151 
1152  _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1153 
1154  link1 = _dbus_list_get_next_link (&list1, link1);
1155  ++i;
1156  }
1157 
1158  --i;
1159  link1 = _dbus_list_get_last_link (&list1);
1160  while (link1 != NULL)
1161  {
1162  verify_list (&link1); /* pretend this link is the head */
1163 
1164  _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1165 
1166  link1 = _dbus_list_get_prev_link (&list1, link1);
1167  --i;
1168  }
1169 
1170  _dbus_list_clear (&list1);
1171  _dbus_list_clear (&list2);
1172 
1173  /* Test remove */
1174 
1175  i = 0;
1176  while (i < 10)
1177  {
1180  ++i;
1181  }
1182 
1183  --i;
1184  while (i >= 0)
1185  {
1186  if ((i % 2) == 0)
1187  {
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");
1192 
1193  verify_list (&list1);
1194  verify_list (&list2);
1195  }
1196  --i;
1197  }
1198 
1199  _dbus_assert (all_odd_values (&list1));
1200  _dbus_assert (all_odd_values (&list2));
1201 
1202  _dbus_list_clear (&list1);
1203  _dbus_list_clear (&list2);
1204 
1205  /* test removing the other half of the elements */
1206 
1207  i = 0;
1208  while (i < 10)
1209  {
1212  ++i;
1213  }
1214 
1215  --i;
1216  while (i >= 0)
1217  {
1218  if ((i % 2) != 0)
1219  {
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");
1224 
1225  verify_list (&list1);
1226  verify_list (&list2);
1227  }
1228  --i;
1229  }
1230 
1231  _dbus_assert (all_even_values (&list1));
1232  _dbus_assert (all_even_values (&list2));
1233 
1234  /* clear list using remove_link */
1235  while (list1 != NULL)
1236  {
1237  _dbus_list_remove_link (&list1, list1);
1238  verify_list (&list1);
1239  }
1240  while (list2 != NULL)
1241  {
1242  _dbus_list_remove_link (&list2, list2);
1243  verify_list (&list2);
1244  }
1245 
1246  /* Test remove link more generally */
1247  i = 0;
1248  while (i < 10)
1249  {
1252  ++i;
1253  }
1254 
1255  --i;
1256  link2 = _dbus_list_get_first_link (&list2);
1257  while (link2 != NULL)
1258  {
1259  DBusList *next = _dbus_list_get_next_link (&list2, link2);
1260 
1261  _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1262 
1263  if ((i % 2) == 0)
1264  _dbus_list_remove_link (&list2, link2);
1265 
1266  verify_list (&list2);
1267 
1268  link2 = next;
1269  --i;
1270  }
1271 
1272  _dbus_assert (all_odd_values (&list2));
1273  _dbus_list_clear (&list2);
1274 
1275  i = 0;
1276  link1 = _dbus_list_get_first_link (&list1);
1277  while (link1 != NULL)
1278  {
1279  DBusList *next = _dbus_list_get_next_link (&list1, link1);
1280 
1281  _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1282 
1283  if ((i % 2) != 0)
1284  _dbus_list_remove_link (&list1, link1);
1285 
1286  verify_list (&list1);
1287 
1288  link1 = next;
1289  ++i;
1290  }
1291 
1292  _dbus_assert (all_even_values (&list1));
1293  _dbus_list_clear (&list1);
1294 
1295  /* Test copying a list */
1296  i = 0;
1297  while (i < 10)
1298  {
1301  ++i;
1302  }
1303 
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);
1307 
1308  _dbus_list_copy (&list1, &copy1);
1309  verify_list (&list1);
1310  verify_list (&copy1);
1311  _dbus_assert (lists_equal (&list1, &copy1));
1312 
1313  _dbus_list_copy (&list2, &copy2);
1314  verify_list (&list2);
1315  verify_list (&copy2);
1316  _dbus_assert (lists_equal (&list2, &copy2));
1317 
1318  /* Now test copying empty lists */
1319  _dbus_list_clear (&list1);
1320  _dbus_list_clear (&list2);
1321  _dbus_list_clear (&copy1);
1322  _dbus_list_clear (&copy2);
1323 
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);
1327 
1328  _dbus_list_copy (&list1, &copy1);
1329  verify_list (&list1);
1330  verify_list (&copy1);
1331  _dbus_assert (lists_equal (&list1, &copy1));
1332 
1333  _dbus_list_copy (&list2, &copy2);
1334  verify_list (&list2);
1335  verify_list (&copy2);
1336  _dbus_assert (lists_equal (&list2, &copy2));
1337 
1338  _dbus_list_clear (&list1);
1339  _dbus_list_clear (&list2);
1340 
1341  /* insert_before on empty list */
1342  _dbus_list_insert_before (&list1, NULL,
1343  _DBUS_INT_TO_POINTER (0));
1344  verify_list (&list1);
1345 
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));
1351 
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));
1357 
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));
1363 
1364  _dbus_list_clear (&list1);
1365 
1366  /* insert_after on empty list */
1367  _dbus_list_insert_after (&list1, NULL,
1368  _DBUS_INT_TO_POINTER (0));
1369  verify_list (&list1);
1370 
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));
1376 
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));
1382 
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));
1388 
1389  _dbus_list_clear (&list1);
1390 
1391  /* using remove_last */
1395 
1397 
1398  verify_list (&list1);
1399  _dbus_assert (is_ascending_sequence (&list1));
1400 
1401  _dbus_list_clear (&list1);
1402 
1403  return TRUE;
1404 }
1405 
1406 #endif