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
30 /**
31 * @defgroup DBusList Linked list
32 * @ingroup DBusInternals
33 * @brief DBusList data structure
34 *
35 * Types and functions related to DBusList.
36 */
37
38 static DBusMemPool *list_pool;
39 _DBUS_DEFINE_GLOBAL_LOCK (list);
40
41 /**
42 * @defgroup DBusListInternals Linked list implementation details
43 * @ingroup DBusInternals
44 * @brief DBusList implementation details
45 *
46 * The guts of DBusList.
47 *
48 * @{
49 */
50
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*
alloc_link(void * data)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
free_link(DBusList * link)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
link_before(DBusList ** list,DBusList * before_this_link,DBusList * link)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
link_after(DBusList ** list,DBusList * after_this_link,DBusList * link)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
149 /** @} */
150
151 /**
152 * @addtogroup DBusList
153 * @{
154 */
155
156 /**
157 * @struct DBusList
158 *
159 * A node in a linked list.
160 *
161 * DBusList is a circular list; that is, the tail of the list
162 * points back to the head of the list. The empty list is
163 * represented by a #NULL pointer.
164 */
165
166 /**
167 * @def _dbus_list_get_next_link
168 *
169 * Gets the next link in the list, or #NULL if
170 * there are no more links. Used for iteration.
171 *
172 * @code
173 * DBusList *link;
174 * link = _dbus_list_get_first_link (&list);
175 * while (link != NULL)
176 * {
177 * printf ("value is %p\n", link->data);
178 * link = _dbus_list_get_next_link (&link);
179 * }
180 * @endcode
181 *
182 * @param list address of the list head.
183 * @param link current link.
184 * @returns the next link, or %NULL if none.
185 *
186 */
187
188 /**
189 * @def _dbus_list_get_prev_link
190 *
191 * Gets the previous link in the list, or #NULL if
192 * there are no more links. Used for iteration.
193 *
194 * @code
195 * DBusList *link;
196 * link = _dbus_list_get_last_link (&list);
197 * while (link != NULL)
198 * {
199 * printf ("value is %p\n", link->data);
200 * link = _dbus_list_get_prev_link (&link);
201 * }
202 * @endcode
203 *
204 * @param list address of the list head.
205 * @param link current link.
206 * @returns the previous link, or %NULL if none.
207 *
208 */
209
210 /**
211 * Allocates a linked list node. Useful for preallocating
212 * nodes and using _dbus_list_append_link() to avoid
213 * allocations.
214 *
215 * @param data the value to store in the link.
216 * @returns a newly allocated link.
217 */
218 DBusList*
_dbus_list_alloc_link(void * data)219 _dbus_list_alloc_link (void *data)
220 {
221 return alloc_link (data);
222 }
223
224 /**
225 * Frees a linked list node allocated with _dbus_list_alloc_link.
226 * Does not free the data in the node.
227 *
228 * @param link the list node
229 */
230 void
_dbus_list_free_link(DBusList * link)231 _dbus_list_free_link (DBusList *link)
232 {
233 free_link (link);
234 }
235
236
237 /**
238 * Appends a value to the list. May return #FALSE
239 * if insufficient memory exists to add a list link.
240 * This is a constant-time operation.
241 *
242 * @param list address of the list head.
243 * @param data the value to append.
244 * @returns #TRUE on success.
245 */
246 dbus_bool_t
_dbus_list_append(DBusList ** list,void * data)247 _dbus_list_append (DBusList **list,
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
259 /**
260 * Prepends a value to the list. May return #FALSE
261 * if insufficient memory exists to add a list link.
262 * This is a constant-time operation.
263 *
264 * @param list address of the list head.
265 * @param data the value to prepend.
266 * @returns #TRUE on success.
267 */
268 dbus_bool_t
_dbus_list_prepend(DBusList ** list,void * data)269 _dbus_list_prepend (DBusList **list,
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
283 /**
284 * Appends a link to the list.
285 * Cannot fail due to out of memory.
286 * This is a constant-time operation.
287 *
288 * @param list address of the list head.
289 * @param link the link to append.
290 */
291 void
_dbus_list_append_link(DBusList ** list,DBusList * link)292 _dbus_list_append_link (DBusList **list,
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
301 /**
302 * Prepends a link to the list.
303 * Cannot fail due to out of memory.
304 * This is a constant-time operation.
305 *
306 * @param list address of the list head.
307 * @param link the link to prepend.
308 */
309 void
_dbus_list_prepend_link(DBusList ** list,DBusList * link)310 _dbus_list_prepend_link (DBusList **list,
311 DBusList *link)
312 {
313 link_before (list, *list, link);
314 }
315
316 #ifdef DBUS_BUILD_TESTS
317 /**
318 * Inserts data into the list before the given existing link.
319 *
320 * @param list the list to modify
321 * @param before_this_link existing link to insert before, or #NULL to append
322 * @param data the value to insert
323 * @returns #TRUE on success, #FALSE if memory allocation fails
324 */
325 dbus_bool_t
_dbus_list_insert_before(DBusList ** list,DBusList * before_this_link,void * data)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
347 /**
348 * Inserts data into the list after the given existing link.
349 *
350 * @param list the list to modify
351 * @param after_this_link existing link to insert after, or #NULL to prepend
352 * @param data the value to insert
353 * @returns #TRUE on success, #FALSE if memory allocation fails
354 */
355 dbus_bool_t
_dbus_list_insert_after(DBusList ** list,DBusList * after_this_link,void * data)356 _dbus_list_insert_after (DBusList **list,
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
376 /**
377 * Inserts a link into the list before the given existing link.
378 *
379 * @param list the list to modify
380 * @param before_this_link existing link to insert before, or #NULL to append
381 * @param link the link to insert
382 */
383 void
_dbus_list_insert_before_link(DBusList ** list,DBusList * before_this_link,DBusList * link)384 _dbus_list_insert_before_link (DBusList **list,
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
394 /**
395 * Inserts a link into the list after the given existing link.
396 *
397 * @param list the list to modify
398 * @param after_this_link existing link to insert after, or #NULL to prepend
399 * @param link the link to insert
400 */
401 void
_dbus_list_insert_after_link(DBusList ** list,DBusList * after_this_link,DBusList * link)402 _dbus_list_insert_after_link (DBusList **list,
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
412 /**
413 * Removes a value from the list. Only removes the
414 * first value equal to the given data pointer,
415 * even if multiple values exist which match.
416 * This is a linear-time operation.
417 *
418 * @param list address of the list head.
419 * @param data the value to remove.
420 * @returns #TRUE if a value was found to remove.
421 */
422 dbus_bool_t
_dbus_list_remove(DBusList ** list,void * data)423 _dbus_list_remove (DBusList **list,
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
443 /**
444 * Removes a value from the list. Only removes the
445 * last value equal to the given data pointer,
446 * even if multiple values exist which match.
447 * This is a linear-time operation.
448 *
449 * @param list address of the list head.
450 * @param data the value to remove.
451 * @returns #TRUE if a value was found to remove.
452 */
453 dbus_bool_t
_dbus_list_remove_last(DBusList ** list,void * data)454 _dbus_list_remove_last (DBusList **list,
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
469 /**
470 * Finds a value in the list. Returns the last link
471 * with value equal to the given data pointer.
472 * This is a linear-time operation.
473 * Returns #NULL if no value found that matches.
474 *
475 * @param list address of the list head.
476 * @param data the value to find.
477 * @returns the link if found
478 */
479 DBusList*
_dbus_list_find_last(DBusList ** list,void * data)480 _dbus_list_find_last (DBusList **list,
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
498 /**
499 * Removes the given link from the list, but doesn't
500 * free it. _dbus_list_remove_link() both removes the
501 * link and also frees it.
502 *
503 * @param list the list
504 * @param link the link in the list
505 */
506 void
_dbus_list_unlink(DBusList ** list,DBusList * link)507 _dbus_list_unlink (DBusList **list,
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
528 /**
529 * Removes a link from the list. This is a constant-time operation.
530 *
531 * @param list address of the list head.
532 * @param link the list link to remove.
533 */
534 void
_dbus_list_remove_link(DBusList ** list,DBusList * link)535 _dbus_list_remove_link (DBusList **list,
536 DBusList *link)
537 {
538 _dbus_list_unlink (list, link);
539 free_link (link);
540 }
541
542 /**
543 * Frees all links in the list and sets the list head to #NULL. Does
544 * not free the data in each link, for obvious reasons. This is a
545 * linear-time operation.
546 *
547 * @param list address of the list head.
548 */
549 void
_dbus_list_clear(DBusList ** list)550 _dbus_list_clear (DBusList **list)
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
567 /**
568 * Gets the first link in the list.
569 * This is a constant-time operation.
570 *
571 * @param list address of the list head.
572 * @returns the first link, or #NULL for an empty list.
573 */
574 DBusList*
_dbus_list_get_first_link(DBusList ** list)575 _dbus_list_get_first_link (DBusList **list)
576 {
577 return *list;
578 }
579
580 /**
581 * Gets the last link in the list.
582 * This is a constant-time operation.
583 *
584 * @param list address of the list head.
585 * @returns the last link, or #NULL for an empty list.
586 */
587 DBusList*
_dbus_list_get_last_link(DBusList ** list)588 _dbus_list_get_last_link (DBusList **list)
589 {
590 if (*list == NULL)
591 return NULL;
592 else
593 return (*list)->prev;
594 }
595
596 /**
597 * Gets the last data in the list.
598 * This is a constant-time operation.
599 *
600 * @param list address of the list head.
601 * @returns the last data in the list, or #NULL for an empty list.
602 */
603 void*
_dbus_list_get_last(DBusList ** list)604 _dbus_list_get_last (DBusList **list)
605 {
606 if (*list == NULL)
607 return NULL;
608 else
609 return (*list)->prev->data;
610 }
611
612 /**
613 * Gets the first data in the list.
614 * This is a constant-time operation.
615 *
616 * @param list address of the list head.
617 * @returns the first data in the list, or #NULL for an empty list.
618 */
619 void*
_dbus_list_get_first(DBusList ** list)620 _dbus_list_get_first (DBusList **list)
621 {
622 if (*list == NULL)
623 return NULL;
624 else
625 return (*list)->data;
626 }
627
628 /**
629 * Removes the first link in the list and returns it. This is a
630 * constant-time operation.
631 *
632 * @param list address of the list head.
633 * @returns the first link in the list, or #NULL for an empty list.
634 */
635 DBusList*
_dbus_list_pop_first_link(DBusList ** list)636 _dbus_list_pop_first_link (DBusList **list)
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
649 /**
650 * Removes the first value in the list and returns it. This is a
651 * constant-time operation.
652 *
653 * @param list address of the list head.
654 * @returns the first data in the list, or #NULL for an empty list.
655 */
656 void*
_dbus_list_pop_first(DBusList ** list)657 _dbus_list_pop_first (DBusList **list)
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
672 /**
673 * Removes the last value in the list and returns it. This is a
674 * constant-time operation.
675 *
676 * @param list address of the list head.
677 * @returns the last data in the list, or #NULL for an empty list.
678 */
679 void*
_dbus_list_pop_last(DBusList ** list)680 _dbus_list_pop_last (DBusList **list)
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 /**
697 * Removes the last link in the list and returns it. This is a
698 * constant-time operation.
699 *
700 * @param list address of the list head.
701 * @returns the last link in the list, or #NULL for an empty list.
702 */
703 DBusList*
_dbus_list_pop_last_link(DBusList ** list)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
718 /**
719 * Copies a list. This is a linear-time operation. If there isn't
720 * enough memory to copy the entire list, the destination list will be
721 * set to #NULL.
722 *
723 * @param list address of the head of the list to copy.
724 * @param dest address where the copied list should be placed.
725 * @returns #TRUE on success, #FALSE if not enough memory.
726 */
727 dbus_bool_t
_dbus_list_copy(DBusList ** list,DBusList ** dest)728 _dbus_list_copy (DBusList **list,
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
753 /**
754 * Gets the length of a list. This is a linear-time
755 * operation.
756 *
757 * @param list address of the head of the list
758 * @returns number of elements in the list.
759 */
760 int
_dbus_list_get_length(DBusList ** list)761 _dbus_list_get_length (DBusList **list)
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
779 /**
780 * Calls the given function for each element in the list. The
781 * function is passed the list element as its first argument, and the
782 * given data as its second argument.
783 *
784 * @param list address of the head of the list.
785 * @param function function to call for each element.
786 * @param data extra data for the function.
787 *
788 */
789 void
_dbus_list_foreach(DBusList ** list,DBusForeachFunction function,void * data)790 _dbus_list_foreach (DBusList **list,
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
807 /**
808 * Check whether length is exactly one.
809 *
810 * @param list the list
811 * @returns #TRUE if length is exactly one
812 */
813 dbus_bool_t
_dbus_list_length_is_one(DBusList ** list)814 _dbus_list_length_is_one (DBusList **list)
815 {
816 return (*list != NULL &&
817 (*list)->next == *list);
818 }
819
820 /** @} */
821
822 #ifdef DBUS_BUILD_TESTS
823 #include "dbus-test.h"
824 #include <stdio.h>
825
826 static void
verify_list(DBusList ** list)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)
857 _dbus_assert (_dbus_list_length_is_one (list));
858 else
859 _dbus_assert (!_dbus_list_length_is_one (list));
860 }
861
862 static dbus_bool_t
is_ascending_sequence(DBusList ** list)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
is_descending_sequence(DBusList ** list)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
all_even_values(DBusList ** list)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
all_odd_values(DBusList ** list)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
lists_equal(DBusList ** list1,DBusList ** list2)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
972 /**
973 * @ingroup DBusListInternals
974 * Unit test for DBusList
975 * @returns #TRUE on success.
976 */
977 dbus_bool_t
_dbus_list_test(void)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 {
1025 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1026 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
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 {
1068 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1069 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
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 {
1120 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1121 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
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 {
1178 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1179 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
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 {
1210 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1211 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
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 {
1250 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1251 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
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 {
1299 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1300 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
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, ©1);
1309 verify_list (&list1);
1310 verify_list (©1);
1311 _dbus_assert (lists_equal (&list1, ©1));
1312
1313 _dbus_list_copy (&list2, ©2);
1314 verify_list (&list2);
1315 verify_list (©2);
1316 _dbus_assert (lists_equal (&list2, ©2));
1317
1318 /* Now test copying empty lists */
1319 _dbus_list_clear (&list1);
1320 _dbus_list_clear (&list2);
1321 _dbus_list_clear (©1);
1322 _dbus_list_clear (©2);
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, ©1);
1329 verify_list (&list1);
1330 verify_list (©1);
1331 _dbus_assert (lists_equal (&list1, ©1));
1332
1333 _dbus_list_copy (&list2, ©2);
1334 verify_list (&list2);
1335 verify_list (©2);
1336 _dbus_assert (lists_equal (&list2, ©2));
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 */
1392 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2));
1393 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1));
1394 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3));
1395
1396 _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2));
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
1407