D-Bus  1.10.24
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  {
996  ++i;
997  }
998 
999  --i;
1000  while (i >= 0)
1001  {
1002  void *got_data1;
1003  void *got_data2;
1004 
1005  void *data1;
1006  void *data2;
1007 
1008  got_data1 = _dbus_list_get_last (&list1);
1009  got_data2 = _dbus_list_get_first (&list2);
1010 
1011  data1 = _dbus_list_pop_last (&list1);
1012  data2 = _dbus_list_pop_first (&list2);
1013 
1014  _dbus_assert (got_data1 == data1);
1015  _dbus_assert (got_data2 == data2);
1016 
1017  _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1018  _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1019 
1020  verify_list (&list1);
1021  verify_list (&list2);
1022 
1023  _dbus_assert (is_ascending_sequence (&list1));
1024  _dbus_assert (is_descending_sequence (&list2));
1025 
1026  --i;
1027  }
1028 
1029  _dbus_assert (list1 == NULL);
1030  _dbus_assert (list2 == NULL);
1031 
1032  /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */
1033 
1034  i = 0;
1035  while (i < 10)
1036  {
1039  ++i;
1040  }
1041 
1042  --i;
1043  while (i >= 0)
1044  {
1045  DBusList *got_link1;
1046  DBusList *got_link2;
1047 
1048  DBusList *link2;
1049 
1050  void *data1_indirect;
1051  void *data1;
1052  void *data2;
1053 
1054  got_link1 = _dbus_list_get_last_link (&list1);
1055  got_link2 = _dbus_list_get_first_link (&list2);
1056 
1057  link2 = _dbus_list_pop_first_link (&list2);
1058 
1059  _dbus_assert (got_link2 == link2);
1060 
1061  data1_indirect = got_link1->data;
1062  /* this call makes got_link1 invalid */
1063  data1 = _dbus_list_pop_last (&list1);
1064  _dbus_assert (data1 == data1_indirect);
1065  data2 = link2->data;
1066 
1067  _dbus_list_free_link (link2);
1068 
1069  _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1070  _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1071 
1072  verify_list (&list1);
1073  verify_list (&list2);
1074 
1075  _dbus_assert (is_ascending_sequence (&list1));
1076  _dbus_assert (is_descending_sequence (&list2));
1077 
1078  --i;
1079  }
1080 
1081  _dbus_assert (list1 == NULL);
1082  _dbus_assert (list2 == NULL);
1083 
1084  /* Test iteration */
1085 
1086  i = 0;
1087  while (i < 10)
1088  {
1091  ++i;
1092 
1093  verify_list (&list1);
1094  verify_list (&list2);
1095 
1096  _dbus_assert (_dbus_list_get_length (&list1) == i);
1097  _dbus_assert (_dbus_list_get_length (&list2) == i);
1098  }
1099 
1100  _dbus_assert (is_ascending_sequence (&list1));
1101  _dbus_assert (is_descending_sequence (&list2));
1102 
1103  --i;
1104  link2 = _dbus_list_get_first_link (&list2);
1105  while (link2 != NULL)
1106  {
1107  verify_list (&link2); /* pretend this link is the head */
1108 
1109  _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1110 
1111  link2 = _dbus_list_get_next_link (&list2, link2);
1112  --i;
1113  }
1114 
1115  i = 0;
1116  link1 = _dbus_list_get_first_link (&list1);
1117  while (link1 != NULL)
1118  {
1119  verify_list (&link1); /* pretend this link is the head */
1120 
1121  _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1122 
1123  link1 = _dbus_list_get_next_link (&list1, link1);
1124  ++i;
1125  }
1126 
1127  --i;
1128  link1 = _dbus_list_get_last_link (&list1);
1129  while (link1 != NULL)
1130  {
1131  verify_list (&link1); /* pretend this link is the head */
1132 
1133  _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1134 
1135  link1 = _dbus_list_get_prev_link (&list1, link1);
1136  --i;
1137  }
1138 
1139  _dbus_list_clear (&list1);
1140  _dbus_list_clear (&list2);
1141 
1142  /* Test remove */
1143 
1144  i = 0;
1145  while (i < 10)
1146  {
1149  ++i;
1150  }
1151 
1152  --i;
1153  while (i >= 0)
1154  {
1155  if ((i % 2) == 0)
1156  {
1157  if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1158  _dbus_assert_not_reached ("element should have been in list");
1159  if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1160  _dbus_assert_not_reached ("element should have been in list");
1161 
1162  verify_list (&list1);
1163  verify_list (&list2);
1164  }
1165  --i;
1166  }
1167 
1168  _dbus_assert (all_odd_values (&list1));
1169  _dbus_assert (all_odd_values (&list2));
1170 
1171  _dbus_list_clear (&list1);
1172  _dbus_list_clear (&list2);
1173 
1174  /* test removing the other half of the elements */
1175 
1176  i = 0;
1177  while (i < 10)
1178  {
1181  ++i;
1182  }
1183 
1184  --i;
1185  while (i >= 0)
1186  {
1187  if ((i % 2) != 0)
1188  {
1189  if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1190  _dbus_assert_not_reached ("element should have been in list");
1191  if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1192  _dbus_assert_not_reached ("element should have been in list");
1193 
1194  verify_list (&list1);
1195  verify_list (&list2);
1196  }
1197  --i;
1198  }
1199 
1200  _dbus_assert (all_even_values (&list1));
1201  _dbus_assert (all_even_values (&list2));
1202 
1203  /* clear list using remove_link */
1204  while (list1 != NULL)
1205  {
1206  _dbus_list_remove_link (&list1, list1);
1207  verify_list (&list1);
1208  }
1209  while (list2 != NULL)
1210  {
1211  _dbus_list_remove_link (&list2, list2);
1212  verify_list (&list2);
1213  }
1214 
1215  /* Test remove link more generally */
1216  i = 0;
1217  while (i < 10)
1218  {
1221  ++i;
1222  }
1223 
1224  --i;
1225  link2 = _dbus_list_get_first_link (&list2);
1226  while (link2 != NULL)
1227  {
1228  DBusList *next = _dbus_list_get_next_link (&list2, link2);
1229 
1230  _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1231 
1232  if ((i % 2) == 0)
1233  _dbus_list_remove_link (&list2, link2);
1234 
1235  verify_list (&list2);
1236 
1237  link2 = next;
1238  --i;
1239  }
1240 
1241  _dbus_assert (all_odd_values (&list2));
1242  _dbus_list_clear (&list2);
1243 
1244  i = 0;
1245  link1 = _dbus_list_get_first_link (&list1);
1246  while (link1 != NULL)
1247  {
1248  DBusList *next = _dbus_list_get_next_link (&list1, link1);
1249 
1250  _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1251 
1252  if ((i % 2) != 0)
1253  _dbus_list_remove_link (&list1, link1);
1254 
1255  verify_list (&list1);
1256 
1257  link1 = next;
1258  ++i;
1259  }
1260 
1261  _dbus_assert (all_even_values (&list1));
1262  _dbus_list_clear (&list1);
1263 
1264  /* Test copying a list */
1265  i = 0;
1266  while (i < 10)
1267  {
1270  ++i;
1271  }
1272 
1273  /* bad pointers, because they are allowed in the copy dest */
1274  copy1 = _DBUS_INT_TO_POINTER (0x342234);
1275  copy2 = _DBUS_INT_TO_POINTER (23);
1276 
1277  _dbus_list_copy (&list1, &copy1);
1278  verify_list (&list1);
1279  verify_list (&copy1);
1280  _dbus_assert (lists_equal (&list1, &copy1));
1281 
1282  _dbus_list_copy (&list2, &copy2);
1283  verify_list (&list2);
1284  verify_list (&copy2);
1285  _dbus_assert (lists_equal (&list2, &copy2));
1286 
1287  /* Now test copying empty lists */
1288  _dbus_list_clear (&list1);
1289  _dbus_list_clear (&list2);
1290  _dbus_list_clear (&copy1);
1291  _dbus_list_clear (&copy2);
1292 
1293  /* bad pointers, because they are allowed in the copy dest */
1294  copy1 = _DBUS_INT_TO_POINTER (0x342234);
1295  copy2 = _DBUS_INT_TO_POINTER (23);
1296 
1297  _dbus_list_copy (&list1, &copy1);
1298  verify_list (&list1);
1299  verify_list (&copy1);
1300  _dbus_assert (lists_equal (&list1, &copy1));
1301 
1302  _dbus_list_copy (&list2, &copy2);
1303  verify_list (&list2);
1304  verify_list (&copy2);
1305  _dbus_assert (lists_equal (&list2, &copy2));
1306 
1307  _dbus_list_clear (&list1);
1308  _dbus_list_clear (&list2);
1309 
1310  /* insert_after on empty list */
1311  _dbus_list_insert_after (&list1, NULL,
1312  _DBUS_INT_TO_POINTER (0));
1313  verify_list (&list1);
1314 
1315  /* inserting after first element */
1316  _dbus_list_insert_after (&list1, list1,
1317  _DBUS_INT_TO_POINTER (1));
1318  verify_list (&list1);
1319  _dbus_assert (is_ascending_sequence (&list1));
1320 
1321  /* inserting at the end */
1322  _dbus_list_insert_after (&list1, list1->next,
1323  _DBUS_INT_TO_POINTER (2));
1324  verify_list (&list1);
1325  _dbus_assert (is_ascending_sequence (&list1));
1326 
1327  /* using insert_after to prepend */
1328  _dbus_list_insert_after (&list1, NULL,
1329  _DBUS_INT_TO_POINTER (-1));
1330  verify_list (&list1);
1331  _dbus_assert (is_ascending_sequence (&list1));
1332 
1333  _dbus_list_clear (&list1);
1334 
1335  /* using remove_last */
1339 
1341 
1342  verify_list (&list1);
1343  _dbus_assert (is_ascending_sequence (&list1));
1344 
1345  _dbus_list_clear (&list1);
1346 
1347  return TRUE;
1348 }
1349 
1350 #endif
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 &quot;int&quot;.
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 &quot;int&quot;.
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 &quot;1&quot;.
#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 &quot;0&quot;.
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