D-Bus  1.12.2
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 /* Protected by _DBUS_LOCK (list) */
39 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  if (!_DBUS_LOCK (list))
60  return FALSE;
61 
62  if (list_pool == NULL)
63  {
64  list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE);
65 
66  if (list_pool == NULL)
67  {
68  _DBUS_UNLOCK (list);
69  return NULL;
70  }
71 
72  link = _dbus_mem_pool_alloc (list_pool);
73  if (link == NULL)
74  {
75  _dbus_mem_pool_free (list_pool);
76  list_pool = NULL;
77  _DBUS_UNLOCK (list);
78  return NULL;
79  }
80  }
81  else
82  {
83  link = _dbus_mem_pool_alloc (list_pool);
84  }
85 
86  if (link)
87  link->data = data;
88 
89  _DBUS_UNLOCK (list);
90 
91  return link;
92 }
93 
94 static void
95 free_link (DBusList *link)
96 {
97  if (!_DBUS_LOCK (list))
98  _dbus_assert_not_reached ("we should have initialized global locks "
99  "before we allocated a linked-list link");
100 
101  if (_dbus_mem_pool_dealloc (list_pool, link))
102  {
103  _dbus_mem_pool_free (list_pool);
104  list_pool = NULL;
105  }
106 
107  _DBUS_UNLOCK (list);
108 }
109 
110 static void
111 link_before (DBusList **list,
112  DBusList *before_this_link,
113  DBusList *link)
114 {
115  if (*list == NULL)
116  {
117  link->prev = link;
118  link->next = link;
119  *list = link;
120  }
121  else
122  {
123  link->next = before_this_link;
124  link->prev = before_this_link->prev;
125  before_this_link->prev = link;
126  link->prev->next = link;
127 
128  if (before_this_link == *list)
129  *list = link;
130  }
131 }
132 
133 static void
134 link_after (DBusList **list,
135  DBusList *after_this_link,
136  DBusList *link)
137 {
138  if (*list == NULL)
139  {
140  link->prev = link;
141  link->next = link;
142  *list = link;
143  }
144  else
145  {
146  link->prev = after_this_link;
147  link->next = after_this_link->next;
148  after_this_link->next = link;
149  link->next->prev = link;
150  }
151 }
152 
153 #ifdef DBUS_ENABLE_STATS
154 void
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)
158 {
159  if (!_DBUS_LOCK (list))
160  {
161  *in_use_p = 0;
162  *in_free_list_p = 0;
163  *allocated_p = 0;
164  return;
165  }
166 
167  _dbus_mem_pool_get_stats (list_pool, in_use_p, in_free_list_p, allocated_p);
168  _DBUS_UNLOCK (list);
169 }
170 #endif
171 
241 DBusList*
243 {
244  return alloc_link (data);
245 }
246 
253 void
255 {
256  free_link (link);
257 }
258 
259 
271  void *data)
272 {
273  if (!_dbus_list_prepend (list, data))
274  return FALSE;
275 
276  /* Now cycle the list forward one so the prepended node is the tail */
277  *list = (*list)->next;
278 
279  return TRUE;
280 }
281 
293  void *data)
294 {
295  DBusList *link;
296 
297  link = alloc_link (data);
298  if (link == NULL)
299  return FALSE;
300 
301  link_before (list, *list, link);
302 
303  return TRUE;
304 }
305 
314 void
316  DBusList *link)
317 {
318  _dbus_list_prepend_link (list, link);
319 
320  /* Now cycle the list forward one so the prepended node is the tail */
321  *list = (*list)->next;
322 }
323 
332 void
334  DBusList *link)
335 {
336  link_before (list, *list, link);
337 }
338 
349  DBusList *after_this_link,
350  void *data)
351 {
352  DBusList *link;
353 
354  if (after_this_link == NULL)
355  return _dbus_list_prepend (list, data);
356  else
357  {
358  link = alloc_link (data);
359  if (link == NULL)
360  return FALSE;
361 
362  link_after (list, after_this_link, link);
363  }
364 
365  return TRUE;
366 }
367 
375 void
377  DBusList *before_this_link,
378  DBusList *link)
379 {
380  if (before_this_link == NULL)
381  _dbus_list_append_link (list, link);
382  else
383  link_before (list, before_this_link, link);
384 }
385 
393 void
395  DBusList *after_this_link,
396  DBusList *link)
397 {
398  if (after_this_link == NULL)
399  _dbus_list_prepend_link (list, link);
400  else
401  link_after (list, after_this_link, link);
402 }
403 
416  void *data)
417 {
418  DBusList *link;
419 
420  link = *list;
421  while (link != NULL)
422  {
423  if (link->data == data)
424  {
425  _dbus_list_remove_link (list, link);
426  return TRUE;
427  }
428 
429  link = _dbus_list_get_next_link (list, link);
430  }
431 
432  return FALSE;
433 }
434 
447  void *data)
448 {
449  DBusList *link;
450 
451  link = _dbus_list_find_last (list, data);
452  if (link)
453  {
454  _dbus_list_remove_link (list, link);
455  return TRUE;
456  }
457  else
458  return FALSE;
459 }
460 
471 DBusList*
473  void *data)
474 {
475  DBusList *link;
476 
477  link = _dbus_list_get_last_link (list);
478 
479  while (link != NULL)
480  {
481  if (link->data == data)
482  return link;
483 
484  link = _dbus_list_get_prev_link (list, link);
485  }
486 
487  return NULL;
488 }
489 
498 void
500  DBusList *link)
501 {
502  if (link->next == link)
503  {
504  /* one-element list */
505  *list = NULL;
506  }
507  else
508  {
509  link->prev->next = link->next;
510  link->next->prev = link->prev;
511 
512  if (*list == link)
513  *list = link->next;
514  }
515 
516  link->next = NULL;
517  link->prev = NULL;
518 }
519 
526 void
528  DBusList *link)
529 {
530  _dbus_list_unlink (list, link);
531  free_link (link);
532 }
533 
541 void
543 {
544  DBusList *link;
545 
546  link = *list;
547  while (link != NULL)
548  {
549  DBusList *next = _dbus_list_get_next_link (list, link);
550 
551  free_link (link);
552 
553  link = next;
554  }
555 
556  *list = NULL;
557 }
558 
566 DBusList*
568 {
569  return *list;
570 }
571 
579 DBusList*
581 {
582  if (*list == NULL)
583  return NULL;
584  else
585  return (*list)->prev;
586 }
587 
595 void*
597 {
598  if (*list == NULL)
599  return NULL;
600  else
601  return (*list)->prev->data;
602 }
603 
611 void*
613 {
614  if (*list == NULL)
615  return NULL;
616  else
617  return (*list)->data;
618 }
619 
627 DBusList*
629 {
630  DBusList *link;
631 
632  link = _dbus_list_get_first_link (list);
633  if (link == NULL)
634  return NULL;
635 
636  _dbus_list_unlink (list, link);
637 
638  return link;
639 }
640 
648 void*
650 {
651  DBusList *link;
652  void *data;
653 
654  link = _dbus_list_get_first_link (list);
655  if (link == NULL)
656  return NULL;
657 
658  data = link->data;
659  _dbus_list_remove_link (list, link);
660 
661  return data;
662 }
663 
671 void*
673 {
674  DBusList *link;
675  void *data;
676 
677  link = _dbus_list_get_last_link (list);
678  if (link == NULL)
679  return NULL;
680 
681  data = link->data;
682  _dbus_list_remove_link (list, link);
683 
684  return data;
685 }
686 
698  DBusList **dest)
699 {
700  DBusList *link;
701 
702  _dbus_assert (list != dest);
703 
704  *dest = NULL;
705 
706  link = *list;
707  while (link != NULL)
708  {
709  if (!_dbus_list_append (dest, link->data))
710  {
711  /* free what we have so far */
712  _dbus_list_clear (dest);
713  return FALSE;
714  }
715 
716  link = _dbus_list_get_next_link (list, link);
717  }
718 
719  return TRUE;
720 }
721 
729 int
731 {
732  DBusList *link;
733  int length;
734 
735  length = 0;
736 
737  link = *list;
738  while (link != NULL)
739  {
740  ++length;
741 
742  link = _dbus_list_get_next_link (list, link);
743  }
744 
745  return length;
746 }
747 
758 void
760  DBusForeachFunction function,
761  void *data)
762 {
763  DBusList *link;
764 
765  link = *list;
766  while (link != NULL)
767  {
768  DBusList *next = _dbus_list_get_next_link (list, link);
769 
770  (* function) (link->data, data);
771 
772  link = next;
773  }
774 }
775 
784 {
785  return (*list != NULL &&
786  (*list)->next == *list);
787 }
788 
791 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
792 #include "dbus-test.h"
793 #include <stdio.h>
794 
795 static void
796 verify_list (DBusList **list)
797 {
798  DBusList *link;
799  int length;
800 
801  link = *list;
802 
803  if (link == NULL)
804  return;
805 
806  if (link->next == link)
807  {
808  _dbus_assert (link->prev == link);
809  _dbus_assert (*list == link);
810  return;
811  }
812 
813  length = 0;
814  do
815  {
816  length += 1;
817  _dbus_assert (link->prev->next == link);
818  _dbus_assert (link->next->prev == link);
819  link = link->next;
820  }
821  while (link != *list);
822 
823  _dbus_assert (length == _dbus_list_get_length (list));
824 
825  if (length == 1)
827  else
829 }
830 
831 static dbus_bool_t
832 is_ascending_sequence (DBusList **list)
833 {
834  DBusList *link;
835  int prev;
836 
837  prev = _DBUS_INT_MIN;
838 
839  link = _dbus_list_get_first_link (list);
840  while (link != NULL)
841  {
842  int v = _DBUS_POINTER_TO_INT (link->data);
843 
844  if (v <= prev)
845  return FALSE;
846 
847  prev = v;
848 
849  link = _dbus_list_get_next_link (list, link);
850  }
851 
852  return TRUE;
853 }
854 
855 static dbus_bool_t
856 is_descending_sequence (DBusList **list)
857 {
858  DBusList *link;
859  int prev;
860 
861  prev = _DBUS_INT_MAX;
862 
863  link = _dbus_list_get_first_link (list);
864  while (link != NULL)
865  {
866  int v = _DBUS_POINTER_TO_INT (link->data);
867 
868  if (v >= prev)
869  return FALSE;
870 
871  prev = v;
872 
873  link = _dbus_list_get_next_link (list, link);
874  }
875 
876  return TRUE;
877 }
878 
879 static dbus_bool_t
880 all_even_values (DBusList **list)
881 {
882  DBusList *link;
883 
884  link = _dbus_list_get_first_link (list);
885  while (link != NULL)
886  {
887  int v = _DBUS_POINTER_TO_INT (link->data);
888 
889  if ((v % 2) != 0)
890  return FALSE;
891 
892  link = _dbus_list_get_next_link (list, link);
893  }
894 
895  return TRUE;
896 }
897 
898 static dbus_bool_t
899 all_odd_values (DBusList **list)
900 {
901  DBusList *link;
902 
903  link = _dbus_list_get_first_link (list);
904  while (link != NULL)
905  {
906  int v = _DBUS_POINTER_TO_INT (link->data);
907 
908  if ((v % 2) == 0)
909  return FALSE;
910 
911  link = _dbus_list_get_next_link (list, link);
912  }
913 
914  return TRUE;
915 }
916 
917 static dbus_bool_t
918 lists_equal (DBusList **list1,
919  DBusList **list2)
920 {
921  DBusList *link1;
922  DBusList *link2;
923 
924  link1 = _dbus_list_get_first_link (list1);
925  link2 = _dbus_list_get_first_link (list2);
926  while (link1 && link2)
927  {
928  if (link1->data != link2->data)
929  return FALSE;
930 
931  link1 = _dbus_list_get_next_link (list1, link1);
932  link2 = _dbus_list_get_next_link (list2, link2);
933  }
934 
935  if (link1 || link2)
936  return FALSE;
937 
938  return TRUE;
939 }
940 
947 _dbus_list_test (void)
948 {
949  DBusList *list1;
950  DBusList *list2;
951  DBusList *link1;
952  DBusList *link2;
953  DBusList *copy1;
954  DBusList *copy2;
955  int i;
956 
957  list1 = NULL;
958  list2 = NULL;
959 
960  /* Test append and prepend */
961 
962  i = 0;
963  while (i < 10)
964  {
965  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
966  _dbus_assert_not_reached ("could not allocate for append");
967 
968  if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
969  _dbus_assert_not_reached ("count not allocate for prepend");
970  ++i;
971 
972  verify_list (&list1);
973  verify_list (&list2);
974 
975  _dbus_assert (_dbus_list_get_length (&list1) == i);
976  _dbus_assert (_dbus_list_get_length (&list2) == i);
977  }
978 
979  _dbus_assert (is_ascending_sequence (&list1));
980  _dbus_assert (is_descending_sequence (&list2));
981 
982  /* Test list clear */
983  _dbus_list_clear (&list1);
984  _dbus_list_clear (&list2);
985 
986  verify_list (&list1);
987  verify_list (&list2);
988 
989  /* Test get_first, get_last, pop_first, pop_last */
990 
991  i = 0;
992  while (i < 10)
993  {
994  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
995  _dbus_assert_not_reached ("could not allocate for append");
996  if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
997  _dbus_assert_not_reached ("could not allocate for prepend");
998  ++i;
999  }
1000 
1001  --i;
1002  while (i >= 0)
1003  {
1004  void *got_data1;
1005  void *got_data2;
1006 
1007  void *data1;
1008  void *data2;
1009 
1010  got_data1 = _dbus_list_get_last (&list1);
1011  got_data2 = _dbus_list_get_first (&list2);
1012 
1013  data1 = _dbus_list_pop_last (&list1);
1014  data2 = _dbus_list_pop_first (&list2);
1015 
1016  _dbus_assert (got_data1 == data1);
1017  _dbus_assert (got_data2 == data2);
1018 
1019  _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1020  _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1021 
1022  verify_list (&list1);
1023  verify_list (&list2);
1024 
1025  _dbus_assert (is_ascending_sequence (&list1));
1026  _dbus_assert (is_descending_sequence (&list2));
1027 
1028  --i;
1029  }
1030 
1031  _dbus_assert (list1 == NULL);
1032  _dbus_assert (list2 == NULL);
1033 
1034  /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */
1035 
1036  i = 0;
1037  while (i < 10)
1038  {
1039  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1040  _dbus_assert_not_reached ("could not allocate for append");
1041  if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1042  _dbus_assert_not_reached ("could not allocate for prepend");
1043  ++i;
1044  }
1045 
1046  --i;
1047  while (i >= 0)
1048  {
1049  DBusList *got_link1;
1050  DBusList *got_link2;
1051 
1052  void *data1_indirect;
1053  void *data1;
1054  void *data2;
1055 
1056  got_link1 = _dbus_list_get_last_link (&list1);
1057  got_link2 = _dbus_list_get_first_link (&list2);
1058 
1059  link2 = _dbus_list_pop_first_link (&list2);
1060 
1061  _dbus_assert (got_link2 == link2);
1062 
1063  data1_indirect = got_link1->data;
1064  /* this call makes got_link1 invalid */
1065  data1 = _dbus_list_pop_last (&list1);
1066  _dbus_assert (data1 == data1_indirect);
1067  data2 = link2->data;
1068 
1069  _dbus_list_free_link (link2);
1070 
1071  _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1072  _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1073 
1074  verify_list (&list1);
1075  verify_list (&list2);
1076 
1077  _dbus_assert (is_ascending_sequence (&list1));
1078  _dbus_assert (is_descending_sequence (&list2));
1079 
1080  --i;
1081  }
1082 
1083  _dbus_assert (list1 == NULL);
1084  _dbus_assert (list2 == NULL);
1085 
1086  /* Test iteration */
1087 
1088  i = 0;
1089  while (i < 10)
1090  {
1091  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1092  _dbus_assert_not_reached ("could not allocate for append");
1093  if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1094  _dbus_assert_not_reached ("could not allocate for prepend");
1095  ++i;
1096 
1097  verify_list (&list1);
1098  verify_list (&list2);
1099 
1100  _dbus_assert (_dbus_list_get_length (&list1) == i);
1101  _dbus_assert (_dbus_list_get_length (&list2) == i);
1102  }
1103 
1104  _dbus_assert (is_ascending_sequence (&list1));
1105  _dbus_assert (is_descending_sequence (&list2));
1106 
1107  --i;
1108  link2 = _dbus_list_get_first_link (&list2);
1109  while (link2 != NULL)
1110  {
1111  verify_list (&link2); /* pretend this link is the head */
1112 
1113  _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1114 
1115  link2 = _dbus_list_get_next_link (&list2, link2);
1116  --i;
1117  }
1118 
1119  i = 0;
1120  link1 = _dbus_list_get_first_link (&list1);
1121  while (link1 != NULL)
1122  {
1123  verify_list (&link1); /* pretend this link is the head */
1124 
1125  _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1126 
1127  link1 = _dbus_list_get_next_link (&list1, link1);
1128  ++i;
1129  }
1130 
1131  --i;
1132  link1 = _dbus_list_get_last_link (&list1);
1133  while (link1 != NULL)
1134  {
1135  verify_list (&link1); /* pretend this link is the head */
1136 
1137  _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1138 
1139  link1 = _dbus_list_get_prev_link (&list1, link1);
1140  --i;
1141  }
1142 
1143  _dbus_list_clear (&list1);
1144  _dbus_list_clear (&list2);
1145 
1146  /* Test remove */
1147 
1148  i = 0;
1149  while (i < 10)
1150  {
1151  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1152  _dbus_assert_not_reached ("could not allocate for append");
1153  if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1154  _dbus_assert_not_reached ("could not allocate for prepend");
1155  ++i;
1156  }
1157 
1158  --i;
1159  while (i >= 0)
1160  {
1161  if ((i % 2) == 0)
1162  {
1163  if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1164  _dbus_assert_not_reached ("element should have been in list");
1165  if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1166  _dbus_assert_not_reached ("element should have been in list");
1167 
1168  verify_list (&list1);
1169  verify_list (&list2);
1170  }
1171  --i;
1172  }
1173 
1174  _dbus_assert (all_odd_values (&list1));
1175  _dbus_assert (all_odd_values (&list2));
1176 
1177  _dbus_list_clear (&list1);
1178  _dbus_list_clear (&list2);
1179 
1180  /* test removing the other half of the elements */
1181 
1182  i = 0;
1183  while (i < 10)
1184  {
1185  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1186  _dbus_assert_not_reached ("could not allocate for append");
1187  if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1188  _dbus_assert_not_reached ("could not allocate for prepend");
1189  ++i;
1190  }
1191 
1192  --i;
1193  while (i >= 0)
1194  {
1195  if ((i % 2) != 0)
1196  {
1197  if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1198  _dbus_assert_not_reached ("element should have been in list");
1199  if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1200  _dbus_assert_not_reached ("element should have been in list");
1201 
1202  verify_list (&list1);
1203  verify_list (&list2);
1204  }
1205  --i;
1206  }
1207 
1208  _dbus_assert (all_even_values (&list1));
1209  _dbus_assert (all_even_values (&list2));
1210 
1211  /* clear list using remove_link */
1212  while (list1 != NULL)
1213  {
1214  _dbus_list_remove_link (&list1, list1);
1215  verify_list (&list1);
1216  }
1217  while (list2 != NULL)
1218  {
1219  _dbus_list_remove_link (&list2, list2);
1220  verify_list (&list2);
1221  }
1222 
1223  /* Test remove link more generally */
1224  i = 0;
1225  while (i < 10)
1226  {
1227  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1228  _dbus_assert_not_reached ("could not allocate for append");
1229  if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1230  _dbus_assert_not_reached ("could not allocate for prepend");
1231  ++i;
1232  }
1233 
1234  --i;
1235  link2 = _dbus_list_get_first_link (&list2);
1236  while (link2 != NULL)
1237  {
1238  DBusList *next = _dbus_list_get_next_link (&list2, link2);
1239 
1240  _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1241 
1242  if ((i % 2) == 0)
1243  _dbus_list_remove_link (&list2, link2);
1244 
1245  verify_list (&list2);
1246 
1247  link2 = next;
1248  --i;
1249  }
1250 
1251  _dbus_assert (all_odd_values (&list2));
1252  _dbus_list_clear (&list2);
1253 
1254  i = 0;
1255  link1 = _dbus_list_get_first_link (&list1);
1256  while (link1 != NULL)
1257  {
1258  DBusList *next = _dbus_list_get_next_link (&list1, link1);
1259 
1260  _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1261 
1262  if ((i % 2) != 0)
1263  _dbus_list_remove_link (&list1, link1);
1264 
1265  verify_list (&list1);
1266 
1267  link1 = next;
1268  ++i;
1269  }
1270 
1271  _dbus_assert (all_even_values (&list1));
1272  _dbus_list_clear (&list1);
1273 
1274  /* Test copying a list */
1275  i = 0;
1276  while (i < 10)
1277  {
1278  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1279  _dbus_assert_not_reached ("could not allocate for append");
1280  if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1281  _dbus_assert_not_reached ("could not allocate for prepend");
1282  ++i;
1283  }
1284 
1285  /* bad pointers, because they are allowed in the copy dest */
1286  copy1 = _DBUS_INT_TO_POINTER (0x342234);
1287  copy2 = _DBUS_INT_TO_POINTER (23);
1288 
1289  _dbus_list_copy (&list1, &copy1);
1290  verify_list (&list1);
1291  verify_list (&copy1);
1292  _dbus_assert (lists_equal (&list1, &copy1));
1293 
1294  _dbus_list_copy (&list2, &copy2);
1295  verify_list (&list2);
1296  verify_list (&copy2);
1297  _dbus_assert (lists_equal (&list2, &copy2));
1298 
1299  /* Now test copying empty lists */
1300  _dbus_list_clear (&list1);
1301  _dbus_list_clear (&list2);
1302  _dbus_list_clear (&copy1);
1303  _dbus_list_clear (&copy2);
1304 
1305  /* bad pointers, because they are allowed in the copy dest */
1306  copy1 = _DBUS_INT_TO_POINTER (0x342234);
1307  copy2 = _DBUS_INT_TO_POINTER (23);
1308 
1309  _dbus_list_copy (&list1, &copy1);
1310  verify_list (&list1);
1311  verify_list (&copy1);
1312  _dbus_assert (lists_equal (&list1, &copy1));
1313 
1314  _dbus_list_copy (&list2, &copy2);
1315  verify_list (&list2);
1316  verify_list (&copy2);
1317  _dbus_assert (lists_equal (&list2, &copy2));
1318 
1319  _dbus_list_clear (&list1);
1320  _dbus_list_clear (&list2);
1321 
1322  /* insert_after on empty list */
1323  _dbus_list_insert_after (&list1, NULL,
1324  _DBUS_INT_TO_POINTER (0));
1325  verify_list (&list1);
1326 
1327  /* inserting after first element */
1328  _dbus_list_insert_after (&list1, list1,
1329  _DBUS_INT_TO_POINTER (1));
1330  verify_list (&list1);
1331  _dbus_assert (is_ascending_sequence (&list1));
1332 
1333  /* inserting at the end */
1334  _dbus_list_insert_after (&list1, list1->next,
1335  _DBUS_INT_TO_POINTER (2));
1336  verify_list (&list1);
1337  _dbus_assert (is_ascending_sequence (&list1));
1338 
1339  /* using insert_after to prepend */
1340  _dbus_list_insert_after (&list1, NULL,
1341  _DBUS_INT_TO_POINTER (-1));
1342  verify_list (&list1);
1343  _dbus_assert (is_ascending_sequence (&list1));
1344 
1345  _dbus_list_clear (&list1);
1346 
1347  /* using remove_last */
1348  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2)))
1349  _dbus_assert_not_reached ("could not allocate for append");
1350  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1)))
1351  _dbus_assert_not_reached ("could not allocate for append");
1352  if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3)))
1353  _dbus_assert_not_reached ("could not allocate for append");
1354 
1356 
1357  verify_list (&list1);
1358  _dbus_assert (is_ascending_sequence (&list1));
1359 
1360  _dbus_list_clear (&list1);
1361 
1362  return TRUE;
1363 }
1364 
1365 #endif
unsigned int dbus_uint32_t
A 32-bit unsigned integer on all platforms.
void * _dbus_list_get_last(DBusList **list)
Gets the last data in the list.
Definition: dbus-list.c:596
dbus_bool_t _dbus_list_prepend(DBusList **list, void *data)
Prepends a value to the list.
Definition: dbus-list.c:292
#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 * _dbus_list_pop_last(DBusList **list)
Removes the last value in the list and returns it.
Definition: dbus-list.c:672
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:783
DBusList * _dbus_list_get_last_link(DBusList **list)
Gets the last link in the list.
Definition: dbus-list.c:580
DBusList * _dbus_list_find_last(DBusList **list, void *data)
Finds a value in the list.
Definition: dbus-list.c:472
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:348
void _dbus_list_remove_link(DBusList **list, DBusList *link)
Removes a link from the list.
Definition: dbus-list.c:527
#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:315
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:376
#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:117
DBusList * _dbus_list_alloc_link(void *data)
Allocates a linked list node.
Definition: dbus-list.c:242
dbus_bool_t _dbus_list_remove(DBusList **list, void *data)
Removes a value from the list.
Definition: dbus-list.c:415
DBusList * _dbus_list_pop_first_link(DBusList **list)
Removes the first link in the list and returns it.
Definition: dbus-list.c:628
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:612
#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:116
#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:697
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:394
dbus_bool_t _dbus_list_remove_last(DBusList **list, void *data)
Removes a value from the list.
Definition: dbus-list.c:446
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:270
void _dbus_list_foreach(DBusList **list, DBusForeachFunction function, void *data)
Calls the given function for each element in the list.
Definition: dbus-list.c:759
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:649
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:254
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:499
int _dbus_list_get_length(DBusList **list)
Gets the length of a list.
Definition: dbus-list.c:730
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:567
#define FALSE
Expands to "0".
void _dbus_list_prepend_link(DBusList **list, DBusList *link)
Prepends a link to the list.
Definition: dbus-list.c:333
#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:542