D-Bus  1.13.7
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 #include <dbus/dbus-test-tap.h>
30 
39 /* Protected by _DBUS_LOCK (list) */
40 static DBusMemPool *list_pool;
41 
52 /* the mem pool is probably a speed hit, with the thread
53  * lock, though it does still save memory - unknown.
54  */
55 static DBusList*
56 alloc_link (void *data)
57 {
58  DBusList *link;
59 
60  if (!_DBUS_LOCK (list))
61  return FALSE;
62 
63  if (list_pool == NULL)
64  {
65  list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE);
66 
67  if (list_pool == NULL)
68  {
69  _DBUS_UNLOCK (list);
70  return NULL;
71  }
72 
73  link = _dbus_mem_pool_alloc (list_pool);
74  if (link == NULL)
75  {
76  _dbus_mem_pool_free (list_pool);
77  list_pool = NULL;
78  _DBUS_UNLOCK (list);
79  return NULL;
80  }
81  }
82  else
83  {
84  link = _dbus_mem_pool_alloc (list_pool);
85  }
86 
87  if (link)
88  link->data = data;
89 
90  _DBUS_UNLOCK (list);
91 
92  return link;
93 }
94 
95 static void
96 free_link (DBusList *link)
97 {
98  if (!_DBUS_LOCK (list))
99  _dbus_assert_not_reached ("we should have initialized global locks "
100  "before we allocated a linked-list link");
101 
102  if (_dbus_mem_pool_dealloc (list_pool, link))
103  {
104  _dbus_mem_pool_free (list_pool);
105  list_pool = NULL;
106  }
107 
108  _DBUS_UNLOCK (list);
109 }
110 
111 static void
112 link_before (DBusList **list,
113  DBusList *before_this_link,
114  DBusList *link)
115 {
116  if (*list == NULL)
117  {
118  link->prev = link;
119  link->next = link;
120  *list = link;
121  }
122  else
123  {
124  link->next = before_this_link;
125  link->prev = before_this_link->prev;
126  before_this_link->prev = link;
127  link->prev->next = link;
128 
129  if (before_this_link == *list)
130  *list = link;
131  }
132 }
133 
134 static void
135 link_after (DBusList **list,
136  DBusList *after_this_link,
137  DBusList *link)
138 {
139  if (*list == NULL)
140  {
141  link->prev = link;
142  link->next = link;
143  *list = link;
144  }
145  else
146  {
147  link->prev = after_this_link;
148  link->next = after_this_link->next;
149  after_this_link->next = link;
150  link->next->prev = link;
151  }
152 }
153 
154 #ifdef DBUS_ENABLE_STATS
155 void
156 _dbus_list_get_stats (dbus_uint32_t *in_use_p,
157  dbus_uint32_t *in_free_list_p,
158  dbus_uint32_t *allocated_p)
159 {
160  if (!_DBUS_LOCK (list))
161  {
162  *in_use_p = 0;
163  *in_free_list_p = 0;
164  *allocated_p = 0;
165  return;
166  }
167 
168  _dbus_mem_pool_get_stats (list_pool, in_use_p, in_free_list_p, allocated_p);
169  _DBUS_UNLOCK (list);
170 }
171 #endif
172 
242 DBusList*
244 {
245  return alloc_link (data);
246 }
247 
254 void
256 {
257  free_link (link);
258 }
259 
260 
272  void *data)
273 {
274  if (!_dbus_list_prepend (list, data))
275  return FALSE;
276 
277  /* Now cycle the list forward one so the prepended node is the tail */
278  *list = (*list)->next;
279 
280  return TRUE;
281 }
282 
294  void *data)
295 {
296  DBusList *link;
297 
298  link = alloc_link (data);
299  if (link == NULL)
300  return FALSE;
301 
302  link_before (list, *list, link);
303 
304  return TRUE;
305 }
306 
315 void
317  DBusList *link)
318 {
319  _dbus_list_prepend_link (list, link);
320 
321  /* Now cycle the list forward one so the prepended node is the tail */
322  *list = (*list)->next;
323 }
324 
333 void
335  DBusList *link)
336 {
337  link_before (list, *list, link);
338 }
339 
350  DBusList *after_this_link,
351  void *data)
352 {
353  DBusList *link;
354 
355  if (after_this_link == NULL)
356  return _dbus_list_prepend (list, data);
357  else
358  {
359  link = alloc_link (data);
360  if (link == NULL)
361  return FALSE;
362 
363  link_after (list, after_this_link, link);
364  }
365 
366  return TRUE;
367 }
368 
376 void
378  DBusList *before_this_link,
379  DBusList *link)
380 {
381  if (before_this_link == NULL)
382  _dbus_list_append_link (list, link);
383  else
384  link_before (list, before_this_link, link);
385 }
386 
394 void
396  DBusList *after_this_link,
397  DBusList *link)
398 {
399  if (after_this_link == NULL)
400  _dbus_list_prepend_link (list, link);
401  else
402  link_after (list, after_this_link, link);
403 }
404 
417  void *data)
418 {
419  DBusList *link;
420 
421  link = *list;
422  while (link != NULL)
423  {
424  if (link->data == data)
425  {
426  _dbus_list_remove_link (list, link);
427  return TRUE;
428  }
429 
430  link = _dbus_list_get_next_link (list, link);
431  }
432 
433  return FALSE;
434 }
435 
448  void *data)
449 {
450  DBusList *link;
451 
452  link = _dbus_list_find_last (list, data);
453  if (link)
454  {
455  _dbus_list_remove_link (list, link);
456  return TRUE;
457  }
458  else
459  return FALSE;
460 }
461 
472 DBusList*
474  void *data)
475 {
476  DBusList *link;
477 
478  link = _dbus_list_get_last_link (list);
479 
480  while (link != NULL)
481  {
482  if (link->data == data)
483  return link;
484 
485  link = _dbus_list_get_prev_link (list, link);
486  }
487 
488  return NULL;
489 }
490 
499 void
501  DBusList *link)
502 {
503  if (link->next == link)
504  {
505  /* one-element list */
506  *list = NULL;
507  }
508  else
509  {
510  link->prev->next = link->next;
511  link->next->prev = link->prev;
512 
513  if (*list == link)
514  *list = link->next;
515  }
516 
517  link->next = NULL;
518  link->prev = NULL;
519 }
520 
527 void
529  DBusList *link)
530 {
531  _dbus_list_unlink (list, link);
532  free_link (link);
533 }
534 
542 void
544 {
545  DBusList *link;
546 
547  link = *list;
548  while (link != NULL)
549  {
550  DBusList *next = _dbus_list_get_next_link (list, link);
551 
552  free_link (link);
553 
554  link = next;
555  }
556 
557  *list = NULL;
558 }
559 
567 void
569  DBusFreeFunction function)
570 {
571  DBusList *link;
572 
573  link = *list;
574  while (link != NULL)
575  {
576  DBusList *next = _dbus_list_get_next_link (list, link);
577 
578  function (link->data);
579  free_link (link);
580 
581  link = next;
582  }
583 
584  *list = NULL;
585 }
586 
594 DBusList*
596 {
597  return *list;
598 }
599 
607 DBusList*
609 {
610  if (*list == NULL)
611  return NULL;
612  else
613  return (*list)->prev;
614 }
615 
623 void*
625 {
626  if (*list == NULL)
627  return NULL;
628  else
629  return (*list)->prev->data;
630 }
631 
639 void*
641 {
642  if (*list == NULL)
643  return NULL;
644  else
645  return (*list)->data;
646 }
647 
655 DBusList*
657 {
658  DBusList *link;
659 
660  link = _dbus_list_get_first_link (list);
661  if (link == NULL)
662  return NULL;
663 
664  _dbus_list_unlink (list, link);
665 
666  return link;
667 }
668 
676 void*
678 {
679  DBusList *link;
680  void *data;
681 
682  link = _dbus_list_get_first_link (list);
683  if (link == NULL)
684  return NULL;
685 
686  data = link->data;
687  _dbus_list_remove_link (list, link);
688 
689  return data;
690 }
691 
699 void*
701 {
702  DBusList *link;
703  void *data;
704 
705  link = _dbus_list_get_last_link (list);
706  if (link == NULL)
707  return NULL;
708 
709  data = link->data;
710  _dbus_list_remove_link (list, link);
711 
712  return data;
713 }
714 
726  DBusList **dest)
727 {
728  DBusList *link;
729 
730  _dbus_assert (list != dest);
731 
732  *dest = NULL;
733 
734  link = *list;
735  while (link != NULL)
736  {
737  if (!_dbus_list_append (dest, link->data))
738  {
739  /* free what we have so far */
740  _dbus_list_clear (dest);
741  return FALSE;
742  }
743 
744  link = _dbus_list_get_next_link (list, link);
745  }
746 
747  return TRUE;
748 }
749 
757 int
759 {
760  DBusList *link;
761  int length;
762 
763  length = 0;
764 
765  link = *list;
766  while (link != NULL)
767  {
768  ++length;
769 
770  link = _dbus_list_get_next_link (list, link);
771  }
772 
773  return length;
774 }
775 
786 void
788  DBusForeachFunction function,
789  void *data)
790 {
791  DBusList *link;
792 
793  link = *list;
794  while (link != NULL)
795  {
796  DBusList *next = _dbus_list_get_next_link (list, link);
797 
798  (* function) (link->data, data);
799 
800  link = next;
801  }
802 }
803 
812 {
813  return (*list != NULL &&
814  (*list)->next == *list);
815 }
816 
819 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
820 #include "dbus-test.h"
821 #include <stdio.h>
822 
823 static void
824 verify_list (DBusList **list)
825 {
826  DBusList *link;
827  int length;
828 
829  link = *list;
830 
831  if (link == NULL)
832  return;
833 
834  if (link->next == link)
835  {
836  _dbus_assert (link->prev == link);
837  _dbus_assert (*list == link);
838  return;
839  }
840 
841  length = 0;
842  do
843  {
844  length += 1;
845  _dbus_assert (link->prev->next == link);
846  _dbus_assert (link->next->prev == link);
847  link = link->next;
848  }
849  while (link != *list);
850 
851  _dbus_assert (length == _dbus_list_get_length (list));
852 
853  if (length == 1)
855  else
857 }
858 
859 static dbus_bool_t
860 is_ascending_sequence (DBusList **list)
861 {
862  DBusList *link;
863  int prev;
864 
865  prev = _DBUS_INT_MIN;
866 
867  link = _dbus_list_get_first_link (list);
868  while (link != NULL)
869  {
870  int v = _DBUS_POINTER_TO_INT (link->data);
871 
872  if (v <= prev)
873  return FALSE;
874 
875  prev = v;
876 
877  link = _dbus_list_get_next_link (list, link);
878  }
879 
880  return TRUE;
881 }
882 
883 static dbus_bool_t
884 is_descending_sequence (DBusList **list)
885 {
886  DBusList *link;
887  int prev;
888 
889  prev = _DBUS_INT_MAX;
890 
891  link = _dbus_list_get_first_link (list);
892  while (link != NULL)
893  {
894  int v = _DBUS_POINTER_TO_INT (link->data);
895 
896  if (v >= prev)
897  return FALSE;
898 
899  prev = v;
900 
901  link = _dbus_list_get_next_link (list, link);
902  }
903 
904  return TRUE;
905 }
906 
907 static dbus_bool_t
908 all_even_values (DBusList **list)
909 {
910  DBusList *link;
911 
912  link = _dbus_list_get_first_link (list);
913  while (link != NULL)
914  {
915  int v = _DBUS_POINTER_TO_INT (link->data);
916 
917  if ((v % 2) != 0)
918  return FALSE;
919 
920  link = _dbus_list_get_next_link (list, link);
921  }
922 
923  return TRUE;
924 }
925 
926 static dbus_bool_t
927 all_odd_values (DBusList **list)
928 {
929  DBusList *link;
930 
931  link = _dbus_list_get_first_link (list);
932  while (link != NULL)
933  {
934  int v = _DBUS_POINTER_TO_INT (link->data);
935 
936  if ((v % 2) == 0)
937  return FALSE;
938 
939  link = _dbus_list_get_next_link (list, link);
940  }
941 
942  return TRUE;
943 }
944 
945 static dbus_bool_t
946 lists_equal (DBusList **list1,
947  DBusList **list2)
948 {
949  DBusList *link1;
950  DBusList *link2;
951 
952  link1 = _dbus_list_get_first_link (list1);
953  link2 = _dbus_list_get_first_link (list2);
954  while (link1 && link2)
955  {
956  if (link1->data != link2->data)
957  return FALSE;
958 
959  link1 = _dbus_list_get_next_link (list1, link1);
960  link2 = _dbus_list_get_next_link (list2, link2);
961  }
962 
963  if (link1 || link2)
964  return FALSE;
965 
966  return TRUE;
967 }
968 
975 _dbus_list_test (void)
976 {
977  DBusList *list1;
978  DBusList *list2;
979  DBusList *link1;
980  DBusList *link2;
981  DBusList *copy1;
982  DBusList *copy2;
983  int i;
984 
985  list1 = NULL;
986  list2 = NULL;
987 
988  /* Test append and prepend */
989 
990  i = 0;
991  while (i < 10)
992  {
993  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
994  _dbus_test_fatal ("could not allocate for append");
995 
996  if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
997  _dbus_test_fatal ("count not allocate for prepend");
998  ++i;
999 
1000  verify_list (&list1);
1001  verify_list (&list2);
1002 
1003  _dbus_assert (_dbus_list_get_length (&list1) == i);
1004  _dbus_assert (_dbus_list_get_length (&list2) == i);
1005  }
1006 
1007  _dbus_assert (is_ascending_sequence (&list1));
1008  _dbus_assert (is_descending_sequence (&list2));
1009 
1010  /* Test list clear */
1011  _dbus_list_clear (&list1);
1012  _dbus_list_clear (&list2);
1013 
1014  verify_list (&list1);
1015  verify_list (&list2);
1016 
1017  /* Test get_first, get_last, pop_first, pop_last */
1018 
1019  i = 0;
1020  while (i < 10)
1021  {
1022  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1023  _dbus_test_fatal ("could not allocate for append");
1024  if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1025  _dbus_test_fatal ("could not allocate for prepend");
1026  ++i;
1027  }
1028 
1029  --i;
1030  while (i >= 0)
1031  {
1032  void *got_data1;
1033  void *got_data2;
1034 
1035  void *data1;
1036  void *data2;
1037 
1038  got_data1 = _dbus_list_get_last (&list1);
1039  got_data2 = _dbus_list_get_first (&list2);
1040 
1041  data1 = _dbus_list_pop_last (&list1);
1042  data2 = _dbus_list_pop_first (&list2);
1043 
1044  _dbus_assert (got_data1 == data1);
1045  _dbus_assert (got_data2 == data2);
1046 
1047  _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1048  _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1049 
1050  verify_list (&list1);
1051  verify_list (&list2);
1052 
1053  _dbus_assert (is_ascending_sequence (&list1));
1054  _dbus_assert (is_descending_sequence (&list2));
1055 
1056  --i;
1057  }
1058 
1059  _dbus_assert (list1 == NULL);
1060  _dbus_assert (list2 == NULL);
1061 
1062  /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */
1063 
1064  i = 0;
1065  while (i < 10)
1066  {
1067  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1068  _dbus_test_fatal ("could not allocate for append");
1069  if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1070  _dbus_test_fatal ("could not allocate for prepend");
1071  ++i;
1072  }
1073 
1074  --i;
1075  while (i >= 0)
1076  {
1077  DBusList *got_link1;
1078  DBusList *got_link2;
1079 
1080  void *data1_indirect;
1081  void *data1;
1082  void *data2;
1083 
1084  got_link1 = _dbus_list_get_last_link (&list1);
1085  got_link2 = _dbus_list_get_first_link (&list2);
1086 
1087  link2 = _dbus_list_pop_first_link (&list2);
1088 
1089  _dbus_assert (got_link2 == link2);
1090 
1091  data1_indirect = got_link1->data;
1092  /* this call makes got_link1 invalid */
1093  data1 = _dbus_list_pop_last (&list1);
1094  _dbus_assert (data1 == data1_indirect);
1095  data2 = link2->data;
1096 
1097  _dbus_list_free_link (link2);
1098 
1099  _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1100  _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1101 
1102  verify_list (&list1);
1103  verify_list (&list2);
1104 
1105  _dbus_assert (is_ascending_sequence (&list1));
1106  _dbus_assert (is_descending_sequence (&list2));
1107 
1108  --i;
1109  }
1110 
1111  _dbus_assert (list1 == NULL);
1112  _dbus_assert (list2 == NULL);
1113 
1114  /* Test iteration */
1115 
1116  i = 0;
1117  while (i < 10)
1118  {
1119  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1120  _dbus_test_fatal ("could not allocate for append");
1121  if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1122  _dbus_test_fatal ("could not allocate for prepend");
1123  ++i;
1124 
1125  verify_list (&list1);
1126  verify_list (&list2);
1127 
1128  _dbus_assert (_dbus_list_get_length (&list1) == i);
1129  _dbus_assert (_dbus_list_get_length (&list2) == i);
1130  }
1131 
1132  _dbus_assert (is_ascending_sequence (&list1));
1133  _dbus_assert (is_descending_sequence (&list2));
1134 
1135  --i;
1136  link2 = _dbus_list_get_first_link (&list2);
1137  while (link2 != NULL)
1138  {
1139  verify_list (&link2); /* pretend this link is the head */
1140 
1141  _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1142 
1143  link2 = _dbus_list_get_next_link (&list2, link2);
1144  --i;
1145  }
1146 
1147  i = 0;
1148  link1 = _dbus_list_get_first_link (&list1);
1149  while (link1 != NULL)
1150  {
1151  verify_list (&link1); /* pretend this link is the head */
1152 
1153  _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1154 
1155  link1 = _dbus_list_get_next_link (&list1, link1);
1156  ++i;
1157  }
1158 
1159  --i;
1160  link1 = _dbus_list_get_last_link (&list1);
1161  while (link1 != NULL)
1162  {
1163  verify_list (&link1); /* pretend this link is the head */
1164 
1165  _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1166 
1167  link1 = _dbus_list_get_prev_link (&list1, link1);
1168  --i;
1169  }
1170 
1171  _dbus_list_clear (&list1);
1172  _dbus_list_clear (&list2);
1173 
1174  /* Test remove */
1175 
1176  i = 0;
1177  while (i < 10)
1178  {
1179  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1180  _dbus_test_fatal ("could not allocate for append");
1181  if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1182  _dbus_test_fatal ("could not allocate for prepend");
1183  ++i;
1184  }
1185 
1186  --i;
1187  while (i >= 0)
1188  {
1189  if ((i % 2) == 0)
1190  {
1191  if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1192  _dbus_test_fatal ("element should have been in list");
1193  if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1194  _dbus_test_fatal ("element should have been in list");
1195 
1196  verify_list (&list1);
1197  verify_list (&list2);
1198  }
1199  --i;
1200  }
1201 
1202  _dbus_assert (all_odd_values (&list1));
1203  _dbus_assert (all_odd_values (&list2));
1204 
1205  _dbus_list_clear (&list1);
1206  _dbus_list_clear (&list2);
1207 
1208  /* test removing the other half of the elements */
1209 
1210  i = 0;
1211  while (i < 10)
1212  {
1213  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1214  _dbus_test_fatal ("could not allocate for append");
1215  if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1216  _dbus_test_fatal ("could not allocate for prepend");
1217  ++i;
1218  }
1219 
1220  --i;
1221  while (i >= 0)
1222  {
1223  if ((i % 2) != 0)
1224  {
1225  if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1226  _dbus_test_fatal ("element should have been in list");
1227  if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1228  _dbus_test_fatal ("element should have been in list");
1229 
1230  verify_list (&list1);
1231  verify_list (&list2);
1232  }
1233  --i;
1234  }
1235 
1236  _dbus_assert (all_even_values (&list1));
1237  _dbus_assert (all_even_values (&list2));
1238 
1239  /* clear list using remove_link */
1240  while (list1 != NULL)
1241  {
1242  _dbus_list_remove_link (&list1, list1);
1243  verify_list (&list1);
1244  }
1245  while (list2 != NULL)
1246  {
1247  _dbus_list_remove_link (&list2, list2);
1248  verify_list (&list2);
1249  }
1250 
1251  /* Test remove link more generally */
1252  i = 0;
1253  while (i < 10)
1254  {
1255  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1256  _dbus_test_fatal ("could not allocate for append");
1257  if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1258  _dbus_test_fatal ("could not allocate for prepend");
1259  ++i;
1260  }
1261 
1262  --i;
1263  link2 = _dbus_list_get_first_link (&list2);
1264  while (link2 != NULL)
1265  {
1266  DBusList *next = _dbus_list_get_next_link (&list2, link2);
1267 
1268  _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1269 
1270  if ((i % 2) == 0)
1271  _dbus_list_remove_link (&list2, link2);
1272 
1273  verify_list (&list2);
1274 
1275  link2 = next;
1276  --i;
1277  }
1278 
1279  _dbus_assert (all_odd_values (&list2));
1280  _dbus_list_clear (&list2);
1281 
1282  i = 0;
1283  link1 = _dbus_list_get_first_link (&list1);
1284  while (link1 != NULL)
1285  {
1286  DBusList *next = _dbus_list_get_next_link (&list1, link1);
1287 
1288  _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1289 
1290  if ((i % 2) != 0)
1291  _dbus_list_remove_link (&list1, link1);
1292 
1293  verify_list (&list1);
1294 
1295  link1 = next;
1296  ++i;
1297  }
1298 
1299  _dbus_assert (all_even_values (&list1));
1300  _dbus_list_clear (&list1);
1301 
1302  /* Test copying a list */
1303  i = 0;
1304  while (i < 10)
1305  {
1306  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1307  _dbus_test_fatal ("could not allocate for append");
1308  if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1309  _dbus_test_fatal ("could not allocate for prepend");
1310  ++i;
1311  }
1312 
1313  /* bad pointers, because they are allowed in the copy dest */
1314  copy1 = _DBUS_INT_TO_POINTER (0x342234);
1315  copy2 = _DBUS_INT_TO_POINTER (23);
1316 
1317  _dbus_list_copy (&list1, &copy1);
1318  verify_list (&list1);
1319  verify_list (&copy1);
1320  _dbus_assert (lists_equal (&list1, &copy1));
1321 
1322  _dbus_list_copy (&list2, &copy2);
1323  verify_list (&list2);
1324  verify_list (&copy2);
1325  _dbus_assert (lists_equal (&list2, &copy2));
1326 
1327  /* Now test copying empty lists */
1328  _dbus_list_clear (&list1);
1329  _dbus_list_clear (&list2);
1330  _dbus_list_clear (&copy1);
1331  _dbus_list_clear (&copy2);
1332 
1333  /* bad pointers, because they are allowed in the copy dest */
1334  copy1 = _DBUS_INT_TO_POINTER (0x342234);
1335  copy2 = _DBUS_INT_TO_POINTER (23);
1336 
1337  _dbus_list_copy (&list1, &copy1);
1338  verify_list (&list1);
1339  verify_list (&copy1);
1340  _dbus_assert (lists_equal (&list1, &copy1));
1341 
1342  _dbus_list_copy (&list2, &copy2);
1343  verify_list (&list2);
1344  verify_list (&copy2);
1345  _dbus_assert (lists_equal (&list2, &copy2));
1346 
1347  _dbus_list_clear (&list1);
1348  _dbus_list_clear (&list2);
1349 
1350  /* insert_after on empty list */
1351  _dbus_list_insert_after (&list1, NULL,
1352  _DBUS_INT_TO_POINTER (0));
1353  verify_list (&list1);
1354 
1355  /* inserting after first element */
1356  _dbus_list_insert_after (&list1, list1,
1357  _DBUS_INT_TO_POINTER (1));
1358  verify_list (&list1);
1359  _dbus_assert (is_ascending_sequence (&list1));
1360 
1361  /* inserting at the end */
1362  _dbus_list_insert_after (&list1, list1->next,
1363  _DBUS_INT_TO_POINTER (2));
1364  verify_list (&list1);
1365  _dbus_assert (is_ascending_sequence (&list1));
1366 
1367  /* using insert_after to prepend */
1368  _dbus_list_insert_after (&list1, NULL,
1369  _DBUS_INT_TO_POINTER (-1));
1370  verify_list (&list1);
1371  _dbus_assert (is_ascending_sequence (&list1));
1372 
1373  _dbus_list_clear (&list1);
1374 
1375  /* using remove_last */
1376  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2)))
1377  _dbus_test_fatal ("could not allocate for append");
1378  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1)))
1379  _dbus_test_fatal ("could not allocate for append");
1380  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3)))
1381  _dbus_test_fatal ("could not allocate for append");
1382 
1384 
1385  verify_list (&list1);
1386  _dbus_assert (is_ascending_sequence (&list1));
1387 
1388  _dbus_list_clear (&list1);
1389 
1390  return TRUE;
1391 }
1392 
1393 #endif
void * _dbus_list_get_last(DBusList **list)
Gets the last data in the list.
Definition: dbus-list.c:624
dbus_bool_t _dbus_list_prepend(DBusList **list, void *data)
Prepends a value to the list.
Definition: dbus-list.c:293
#define NULL
A null pointer, defined appropriately for C or C++.
void * _dbus_mem_pool_alloc(DBusMemPool *pool)
Allocates an object from the memory pool.
Definition: dbus-mempool.c:214
void(* DBusFreeFunction)(void *memory)
The type of a function which frees a block of memory.
Definition: dbus-memory.h:63
void * _dbus_list_pop_last(DBusList **list)
Removes the last value in the list and returns it.
Definition: dbus-list.c:700
DBusList * next
Next list node.
Definition: dbus-list.h:37
#define _DBUS_INT_MIN
Minimum value of type "int".
dbus_bool_t _dbus_list_length_is_one(DBusList **list)
Check whether length is exactly one.
Definition: dbus-list.c:811
DBusList * _dbus_list_get_last_link(DBusList **list)
Gets the last link in the list.
Definition: dbus-list.c:608
DBusList * _dbus_list_find_last(DBusList **list, void *data)
Finds a value in the list.
Definition: dbus-list.c:473
dbus_bool_t _dbus_list_insert_after(DBusList **list, DBusList *after_this_link, void *data)
Inserts data into the list after the given existing link.
Definition: dbus-list.c:349
void _dbus_list_remove_link(DBusList **list, DBusList *link)
Removes a link from the list.
Definition: dbus-list.c:528
#define _dbus_assert(condition)
Aborts with an error message if the condition is false.
#define _DBUS_INT_TO_POINTER(integer)
Safely stuffs an integer into a pointer, to be extracted later with _DBUS_POINTER_TO_INT.
void _dbus_list_append_link(DBusList **list, DBusList *link)
Appends a link to the list.
Definition: dbus-list.c:316
void * data
Data stored at this element.
Definition: dbus-list.h:38
void _dbus_list_insert_before_link(DBusList **list, DBusList *before_this_link, DBusList *link)
Inserts a link into the list before the given existing link.
Definition: dbus-list.c:377
void _dbus_list_clear_full(DBusList **list, DBusFreeFunction function)
Free every link and every element in the list.
Definition: dbus-list.c:568
#define _dbus_list_get_prev_link(list, link)
Gets the previous link in the list, or NULL if there are no more links.
Definition: dbus-list.h:120
DBusList * _dbus_list_alloc_link(void *data)
Allocates a linked list node.
Definition: dbus-list.c:243
dbus_bool_t _dbus_list_remove(DBusList **list, void *data)
Removes a value from the list.
Definition: dbus-list.c:416
DBusList * _dbus_list_pop_first_link(DBusList **list)
Removes the first link in the list and returns it.
Definition: dbus-list.c:656
dbus_bool_t _dbus_mem_pool_dealloc(DBusMemPool *pool, void *element)
Deallocates an object previously created with _dbus_mem_pool_alloc().
Definition: dbus-mempool.c:347
DBusList * prev
Previous list node.
Definition: dbus-list.h:36
void * _dbus_list_get_first(DBusList **list)
Gets the first data in the list.
Definition: dbus-list.c:640
#define _dbus_list_get_next_link(list, link)
Gets the next link in the list, or NULL if there are no more links.
Definition: dbus-list.h:119
#define _DBUS_INT_MAX
Maximum value of type "int".
dbus_bool_t _dbus_list_copy(DBusList **list, DBusList **dest)
Copies a list.
Definition: dbus-list.c:725
void _dbus_list_insert_after_link(DBusList **list, DBusList *after_this_link, DBusList *link)
Inserts a link into the list after the given existing link.
Definition: dbus-list.c:395
dbus_bool_t _dbus_list_remove_last(DBusList **list, void *data)
Removes a value from the list.
Definition: dbus-list.c:447
dbus_uint32_t dbus_bool_t
A boolean, valid values are TRUE and FALSE.
Definition: dbus-types.h:35
dbus_bool_t _dbus_list_append(DBusList **list, void *data)
Appends a value to the list.
Definition: dbus-list.c:271
void _dbus_list_foreach(DBusList **list, DBusForeachFunction function, void *data)
Calls the given function for each element in the list.
Definition: dbus-list.c:787
void _dbus_mem_pool_free(DBusMemPool *pool)
Frees a memory pool (and all elements allocated from it).
Definition: dbus-mempool.c:187
#define _DBUS_POINTER_TO_INT(pointer)
Safely casts a void* to an integer; should only be used on void* that actually contain integers...
void * _dbus_list_pop_first(DBusList **list)
Removes the first value in the list and returns it.
Definition: dbus-list.c:677
Internals fields of DBusMemPool.
Definition: dbus-mempool.c:98
#define _DBUS_UNLOCK(name)
Unlocks a global lock.
#define TRUE
Expands to "1".
#define _dbus_assert_not_reached(explanation)
Aborts with an error message if called.
void _dbus_list_free_link(DBusList *link)
Frees a linked list node allocated with _dbus_list_alloc_link.
Definition: dbus-list.c:255
A node in a linked list.
Definition: dbus-list.h:34
void _dbus_list_unlink(DBusList **list, DBusList *link)
Removes the given link from the list, but doesn&#39;t free it.
Definition: dbus-list.c:500
int _dbus_list_get_length(DBusList **list)
Gets the length of a list.
Definition: dbus-list.c:758
void(* DBusForeachFunction)(void *element, void *data)
Used to iterate over each item in a collection, such as a DBusList.
DBusList * _dbus_list_get_first_link(DBusList **list)
Gets the first link in the list.
Definition: dbus-list.c:595
#define FALSE
Expands to "0".
void _dbus_list_prepend_link(DBusList **list, DBusList *link)
Prepends a link to the list.
Definition: dbus-list.c:334
#define _DBUS_LOCK(name)
Locks a global lock, initializing it first if necessary.
DBusMemPool * _dbus_mem_pool_new(int element_size, dbus_bool_t zero_elements)
Creates a new memory pool, or returns NULL on failure.
Definition: dbus-mempool.c:138
void _dbus_list_clear(DBusList **list)
Frees all links in the list and sets the list head to NULL.
Definition: dbus-list.c:543