1 /* -*- mode: C; c-file-style: "gnu" -*- */
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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21 *
22 */
23
24 #include "dbus-internals.h"
25 #include "dbus-list.h"
26 #include "dbus-mempool.h"
27 #include "dbus-threads-internal.h"
28
29 /**
30 * @defgroup DBusList Linked list
31 * @ingroup DBusInternals
32 * @brief DBusList data structure
33 *
34 * Types and functions related to DBusList.
35 */
36
37 static DBusMemPool *list_pool;
38 _DBUS_DEFINE_GLOBAL_LOCK (list);
39
40 /**
41 * @defgroup DBusListInternals Linked list implementation details
42 * @ingroup DBusInternals
43 * @brief DBusList implementation details
44 *
45 * The guts of DBusList.
46 *
47 * @{
48 */
49
50 /* the mem pool is probably a speed hit, with the thread
51 * lock, though it does still save memory - unknown.
52 */
53 static DBusList*
alloc_link(void * data)54 alloc_link (void *data)
55 {
56 DBusList *link;
57
58 _DBUS_LOCK (list);
59
60 if (list_pool == NULL)
61 {
62 list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE);
63
64 if (list_pool == NULL)
65 {
66 _DBUS_UNLOCK (list);
67 return NULL;
68 }
69
70 link = _dbus_mem_pool_alloc (list_pool);
71 if (link == NULL)
72 {
73 _dbus_mem_pool_free (list_pool);
74 list_pool = NULL;
75 _DBUS_UNLOCK (list);
76 return NULL;
77 }
78 }
79 else
80 {
81 link = _dbus_mem_pool_alloc (list_pool);
82 }
83
84 if (link)
85 link->data = data;
86
87 _DBUS_UNLOCK (list);
88
89 return link;
90 }
91
92 static void
free_link(DBusList * link)93 free_link (DBusList *link)
94 {
95 _DBUS_LOCK (list);
96 if (_dbus_mem_pool_dealloc (list_pool, link))
97 {
98 _dbus_mem_pool_free (list_pool);
99 list_pool = NULL;
100 }
101
102 _DBUS_UNLOCK (list);
103 }
104
105 static void
link_before(DBusList ** list,DBusList * before_this_link,DBusList * link)106 link_before (DBusList **list,
107 DBusList *before_this_link,
108 DBusList *link)
109 {
110 if (*list == NULL)
111 {
112 link->prev = link;
113 link->next = link;
114 *list = link;
115 }
116 else
117 {
118 link->next = before_this_link;
119 link->prev = before_this_link->prev;
120 before_this_link->prev = link;
121 link->prev->next = link;
122
123 if (before_this_link == *list)
124 *list = link;
125 }
126 }
127
128 static void
link_after(DBusList ** list,DBusList * after_this_link,DBusList * link)129 link_after (DBusList **list,
130 DBusList *after_this_link,
131 DBusList *link)
132 {
133 if (*list == NULL)
134 {
135 link->prev = link;
136 link->next = link;
137 *list = link;
138 }
139 else
140 {
141 link->prev = after_this_link;
142 link->next = after_this_link->next;
143 after_this_link->next = link;
144 link->next->prev = link;
145 }
146 }
147
148 /** @} */
149
150 /**
151 * @addtogroup DBusList
152 * @{
153 */
154
155 /**
156 * @struct DBusList
157 *
158 * A node in a linked list.
159 *
160 * DBusList is a circular list; that is, the tail of the list
161 * points back to the head of the list. The empty list is
162 * represented by a #NULL pointer.
163 */
164
165 /**
166 * @def _dbus_list_get_next_link
167 *
168 * Gets the next link in the list, or #NULL if
169 * there are no more links. Used for iteration.
170 *
171 * @code
172 * DBusList *link;
173 * link = _dbus_list_get_first_link (&list);
174 * while (link != NULL)
175 * {
176 * printf ("value is %p\n", link->data);
177 * link = _dbus_list_get_next_link (&link);
178 * }
179 * @endcode
180 *
181 * @param list address of the list head.
182 * @param link current link.
183 * @returns the next link, or %NULL if none.
184 *
185 */
186
187 /**
188 * @def _dbus_list_get_prev_link
189 *
190 * Gets the previous link in the list, or #NULL if
191 * there are no more links. Used for iteration.
192 *
193 * @code
194 * DBusList *link;
195 * link = _dbus_list_get_last_link (&list);
196 * while (link != NULL)
197 * {
198 * printf ("value is %p\n", link->data);
199 * link = _dbus_list_get_prev_link (&link);
200 * }
201 * @endcode
202 *
203 * @param list address of the list head.
204 * @param link current link.
205 * @returns the previous link, or %NULL if none.
206 *
207 */
208
209 /**
210 * Allocates a linked list node. Useful for preallocating
211 * nodes and using _dbus_list_append_link() to avoid
212 * allocations.
213 *
214 * @param data the value to store in the link.
215 * @returns a newly allocated link.
216 */
217 DBusList*
_dbus_list_alloc_link(void * data)218 _dbus_list_alloc_link (void *data)
219 {
220 return alloc_link (data);
221 }
222
223 /**
224 * Frees a linked list node allocated with _dbus_list_alloc_link.
225 * Does not free the data in the node.
226 *
227 * @param link the list node
228 */
229 void
_dbus_list_free_link(DBusList * link)230 _dbus_list_free_link (DBusList *link)
231 {
232 free_link (link);
233 }
234
235
236 /**
237 * Appends a value to the list. May return #FALSE
238 * if insufficient memory exists to add a list link.
239 * This is a constant-time operation.
240 *
241 * @param list address of the list head.
242 * @param data the value to append.
243 * @returns #TRUE on success.
244 */
245 dbus_bool_t
_dbus_list_append(DBusList ** list,void * data)246 _dbus_list_append (DBusList **list,
247 void *data)
248 {
249 if (!_dbus_list_prepend (list, data))
250 return FALSE;
251
252 /* Now cycle the list forward one so the prepended node is the tail */
253 *list = (*list)->next;
254
255 return TRUE;
256 }
257
258 /**
259 * Prepends a value to the list. May return #FALSE
260 * if insufficient memory exists to add a list link.
261 * This is a constant-time operation.
262 *
263 * @param list address of the list head.
264 * @param data the value to prepend.
265 * @returns #TRUE on success.
266 */
267 dbus_bool_t
_dbus_list_prepend(DBusList ** list,void * data)268 _dbus_list_prepend (DBusList **list,
269 void *data)
270 {
271 DBusList *link;
272
273 link = alloc_link (data);
274 if (link == NULL)
275 return FALSE;
276
277 link_before (list, *list, link);
278
279 return TRUE;
280 }
281
282 /**
283 * Appends a link to the list.
284 * Cannot fail due to out of memory.
285 * This is a constant-time operation.
286 *
287 * @param list address of the list head.
288 * @param link the link to append.
289 */
290 void
_dbus_list_append_link(DBusList ** list,DBusList * link)291 _dbus_list_append_link (DBusList **list,
292 DBusList *link)
293 {
294 _dbus_list_prepend_link (list, link);
295
296 /* Now cycle the list forward one so the prepended node is the tail */
297 *list = (*list)->next;
298 }
299
300 /**
301 * Prepends a link to the list.
302 * Cannot fail due to out of memory.
303 * This is a constant-time operation.
304 *
305 * @param list address of the list head.
306 * @param link the link to prepend.
307 */
308 void
_dbus_list_prepend_link(DBusList ** list,DBusList * link)309 _dbus_list_prepend_link (DBusList **list,
310 DBusList *link)
311 {
312 link_before (list, *list, link);
313 }
314
315 #ifdef DBUS_BUILD_TESTS
316 /**
317 * Inserts data into the list before the given existing link.
318 *
319 * @param list the list to modify
320 * @param before_this_link existing link to insert before, or #NULL to append
321 * @param data the value to insert
322 * @returns #TRUE on success, #FALSE if memory allocation fails
323 */
324 dbus_bool_t
_dbus_list_insert_before(DBusList ** list,DBusList * before_this_link,void * data)325 _dbus_list_insert_before (DBusList **list,
326 DBusList *before_this_link,
327 void *data)
328 {
329 DBusList *link;
330
331 if (before_this_link == NULL)
332 return _dbus_list_append (list, data);
333 else
334 {
335 link = alloc_link (data);
336 if (link == NULL)
337 return FALSE;
338
339 link_before (list, before_this_link, link);
340 }
341
342 return TRUE;
343 }
344 #endif /* DBUS_BUILD_TESTS */
345
346 /**
347 * Inserts data into the list after the given existing link.
348 *
349 * @param list the list to modify
350 * @param after_this_link existing link to insert after, or #NULL to prepend
351 * @param data the value to insert
352 * @returns #TRUE on success, #FALSE if memory allocation fails
353 */
354 dbus_bool_t
_dbus_list_insert_after(DBusList ** list,DBusList * after_this_link,void * data)355 _dbus_list_insert_after (DBusList **list,
356 DBusList *after_this_link,
357 void *data)
358 {
359 DBusList *link;
360
361 if (after_this_link == NULL)
362 return _dbus_list_prepend (list, data);
363 else
364 {
365 link = alloc_link (data);
366 if (link == NULL)
367 return FALSE;
368
369 link_after (list, after_this_link, link);
370 }
371
372 return TRUE;
373 }
374
375 /**
376 * Inserts a link into the list before the given existing link.
377 *
378 * @param list the list to modify
379 * @param before_this_link existing link to insert before, or #NULL to append
380 * @param link the link to insert
381 */
382 void
_dbus_list_insert_before_link(DBusList ** list,DBusList * before_this_link,DBusList * link)383 _dbus_list_insert_before_link (DBusList **list,
384 DBusList *before_this_link,
385 DBusList *link)
386 {
387 if (before_this_link == NULL)
388 _dbus_list_append_link (list, link);
389 else
390 link_before (list, before_this_link, link);
391 }
392
393 /**
394 * Inserts a link into the list after the given existing link.
395 *
396 * @param list the list to modify
397 * @param after_this_link existing link to insert after, or #NULL to prepend
398 * @param link the link to insert
399 */
400 void
_dbus_list_insert_after_link(DBusList ** list,DBusList * after_this_link,DBusList * link)401 _dbus_list_insert_after_link (DBusList **list,
402 DBusList *after_this_link,
403 DBusList *link)
404 {
405 if (after_this_link == NULL)
406 _dbus_list_prepend_link (list, link);
407 else
408 link_after (list, after_this_link, link);
409 }
410
411 /**
412 * Removes a value from the list. Only removes the
413 * first value equal to the given data pointer,
414 * even if multiple values exist which match.
415 * This is a linear-time operation.
416 *
417 * @param list address of the list head.
418 * @param data the value to remove.
419 * @returns #TRUE if a value was found to remove.
420 */
421 dbus_bool_t
_dbus_list_remove(DBusList ** list,void * data)422 _dbus_list_remove (DBusList **list,
423 void *data)
424 {
425 DBusList *link;
426
427 link = *list;
428 while (link != NULL)
429 {
430 if (link->data == data)
431 {
432 _dbus_list_remove_link (list, link);
433 return TRUE;
434 }
435
436 link = _dbus_list_get_next_link (list, link);
437 }
438
439 return FALSE;
440 }
441
442 /**
443 * Removes a value from the list. Only removes the
444 * last value equal to the given data pointer,
445 * even if multiple values exist which match.
446 * This is a linear-time operation.
447 *
448 * @param list address of the list head.
449 * @param data the value to remove.
450 * @returns #TRUE if a value was found to remove.
451 */
452 dbus_bool_t
_dbus_list_remove_last(DBusList ** list,void * data)453 _dbus_list_remove_last (DBusList **list,
454 void *data)
455 {
456 DBusList *link;
457
458 link = _dbus_list_find_last (list, data);
459 if (link)
460 {
461 _dbus_list_remove_link (list, link);
462 return TRUE;
463 }
464 else
465 return FALSE;
466 }
467
468 /**
469 * Finds a value in the list. Returns the last link
470 * with value equal to the given data pointer.
471 * This is a linear-time operation.
472 * Returns #NULL if no value found that matches.
473 *
474 * @param list address of the list head.
475 * @param data the value to find.
476 * @returns the link if found
477 */
478 DBusList*
_dbus_list_find_last(DBusList ** list,void * data)479 _dbus_list_find_last (DBusList **list,
480 void *data)
481 {
482 DBusList *link;
483
484 link = _dbus_list_get_last_link (list);
485
486 while (link != NULL)
487 {
488 if (link->data == data)
489 return link;
490
491 link = _dbus_list_get_prev_link (list, link);
492 }
493
494 return NULL;
495 }
496
497 /**
498 * Removes the given link from the list, but doesn't
499 * free it. _dbus_list_remove_link() both removes the
500 * link and also frees it.
501 *
502 * @param list the list
503 * @param link the link in the list
504 */
505 void
_dbus_list_unlink(DBusList ** list,DBusList * link)506 _dbus_list_unlink (DBusList **list,
507 DBusList *link)
508 {
509 if (link->next == link)
510 {
511 /* one-element list */
512 *list = NULL;
513 }
514 else
515 {
516 link->prev->next = link->next;
517 link->next->prev = link->prev;
518
519 if (*list == link)
520 *list = link->next;
521 }
522
523 link->next = NULL;
524 link->prev = NULL;
525 }
526
527 /**
528 * Removes a link from the list. This is a constant-time operation.
529 *
530 * @param list address of the list head.
531 * @param link the list link to remove.
532 */
533 void
_dbus_list_remove_link(DBusList ** list,DBusList * link)534 _dbus_list_remove_link (DBusList **list,
535 DBusList *link)
536 {
537 _dbus_list_unlink (list, link);
538 free_link (link);
539 }
540
541 /**
542 * Frees all links in the list and sets the list head to #NULL. Does
543 * not free the data in each link, for obvious reasons. This is a
544 * linear-time operation.
545 *
546 * @param list address of the list head.
547 */
548 void
_dbus_list_clear(DBusList ** list)549 _dbus_list_clear (DBusList **list)
550 {
551 DBusList *link;
552
553 link = *list;
554 while (link != NULL)
555 {
556 DBusList *next = _dbus_list_get_next_link (list, link);
557
558 free_link (link);
559
560 link = next;
561 }
562
563 *list = NULL;
564 }
565
566 /**
567 * Gets the first link in the list.
568 * This is a constant-time operation.
569 *
570 * @param list address of the list head.
571 * @returns the first link, or #NULL for an empty list.
572 */
573 DBusList*
_dbus_list_get_first_link(DBusList ** list)574 _dbus_list_get_first_link (DBusList **list)
575 {
576 return *list;
577 }
578
579 /**
580 * Gets the last link in the list.
581 * This is a constant-time operation.
582 *
583 * @param list address of the list head.
584 * @returns the last link, or #NULL for an empty list.
585 */
586 DBusList*
_dbus_list_get_last_link(DBusList ** list)587 _dbus_list_get_last_link (DBusList **list)
588 {
589 if (*list == NULL)
590 return NULL;
591 else
592 return (*list)->prev;
593 }
594
595 /**
596 * Gets the last data in the list.
597 * This is a constant-time operation.
598 *
599 * @param list address of the list head.
600 * @returns the last data in the list, or #NULL for an empty list.
601 */
602 void*
_dbus_list_get_last(DBusList ** list)603 _dbus_list_get_last (DBusList **list)
604 {
605 if (*list == NULL)
606 return NULL;
607 else
608 return (*list)->prev->data;
609 }
610
611 /**
612 * Gets the first data in the list.
613 * This is a constant-time operation.
614 *
615 * @param list address of the list head.
616 * @returns the first data in the list, or #NULL for an empty list.
617 */
618 void*
_dbus_list_get_first(DBusList ** list)619 _dbus_list_get_first (DBusList **list)
620 {
621 if (*list == NULL)
622 return NULL;
623 else
624 return (*list)->data;
625 }
626
627 /**
628 * Removes the first link in the list and returns it. This is a
629 * constant-time operation.
630 *
631 * @param list address of the list head.
632 * @returns the first link in the list, or #NULL for an empty list.
633 */
634 DBusList*
_dbus_list_pop_first_link(DBusList ** list)635 _dbus_list_pop_first_link (DBusList **list)
636 {
637 DBusList *link;
638
639 link = _dbus_list_get_first_link (list);
640 if (link == NULL)
641 return NULL;
642
643 _dbus_list_unlink (list, link);
644
645 return link;
646 }
647
648 /**
649 * Removes the first value in the list and returns it. This is a
650 * constant-time operation.
651 *
652 * @param list address of the list head.
653 * @returns the first data in the list, or #NULL for an empty list.
654 */
655 void*
_dbus_list_pop_first(DBusList ** list)656 _dbus_list_pop_first (DBusList **list)
657 {
658 DBusList *link;
659 void *data;
660
661 link = _dbus_list_get_first_link (list);
662 if (link == NULL)
663 return NULL;
664
665 data = link->data;
666 _dbus_list_remove_link (list, link);
667
668 return data;
669 }
670
671 /**
672 * Removes the last value in the list and returns it. This is a
673 * constant-time operation.
674 *
675 * @param list address of the list head.
676 * @returns the last data in the list, or #NULL for an empty list.
677 */
678 void*
_dbus_list_pop_last(DBusList ** list)679 _dbus_list_pop_last (DBusList **list)
680 {
681 DBusList *link;
682 void *data;
683
684 link = _dbus_list_get_last_link (list);
685 if (link == NULL)
686 return NULL;
687
688 data = link->data;
689 _dbus_list_remove_link (list, link);
690
691 return data;
692 }
693
694 #ifdef DBUS_BUILD_TESTS
695 /**
696 * Removes the last link in the list and returns it. This is a
697 * constant-time operation.
698 *
699 * @param list address of the list head.
700 * @returns the last link in the list, or #NULL for an empty list.
701 */
702 DBusList*
_dbus_list_pop_last_link(DBusList ** list)703 _dbus_list_pop_last_link (DBusList **list)
704 {
705 DBusList *link;
706
707 link = _dbus_list_get_last_link (list);
708 if (link == NULL)
709 return NULL;
710
711 _dbus_list_unlink (list, link);
712
713 return link;
714 }
715 #endif /* DBUS_BUILD_TESTS */
716
717 /**
718 * Copies a list. This is a linear-time operation. If there isn't
719 * enough memory to copy the entire list, the destination list will be
720 * set to #NULL.
721 *
722 * @param list address of the head of the list to copy.
723 * @param dest address where the copied list should be placed.
724 * @returns #TRUE on success, #FALSE if not enough memory.
725 */
726 dbus_bool_t
_dbus_list_copy(DBusList ** list,DBusList ** dest)727 _dbus_list_copy (DBusList **list,
728 DBusList **dest)
729 {
730 DBusList *link;
731
732 _dbus_assert (list != dest);
733
734 *dest = NULL;
735
736 link = *list;
737 while (link != NULL)
738 {
739 if (!_dbus_list_append (dest, link->data))
740 {
741 /* free what we have so far */
742 _dbus_list_clear (dest);
743 return FALSE;
744 }
745
746 link = _dbus_list_get_next_link (list, link);
747 }
748
749 return TRUE;
750 }
751
752 /**
753 * Gets the length of a list. This is a linear-time
754 * operation.
755 *
756 * @param list address of the head of the list
757 * @returns number of elements in the list.
758 */
759 int
_dbus_list_get_length(DBusList ** list)760 _dbus_list_get_length (DBusList **list)
761 {
762 DBusList *link;
763 int length;
764
765 length = 0;
766
767 link = *list;
768 while (link != NULL)
769 {
770 ++length;
771
772 link = _dbus_list_get_next_link (list, link);
773 }
774
775 return length;
776 }
777
778 /**
779 * Calls the given function for each element in the list. The
780 * function is passed the list element as its first argument, and the
781 * given data as its second argument.
782 *
783 * @param list address of the head of the list.
784 * @param function function to call for each element.
785 * @param data extra data for the function.
786 *
787 */
788 void
_dbus_list_foreach(DBusList ** list,DBusForeachFunction function,void * data)789 _dbus_list_foreach (DBusList **list,
790 DBusForeachFunction function,
791 void *data)
792 {
793 DBusList *link;
794
795 link = *list;
796 while (link != NULL)
797 {
798 DBusList *next = _dbus_list_get_next_link (list, link);
799
800 (* function) (link->data, data);
801
802 link = next;
803 }
804 }
805
806 /**
807 * Check whether length is exactly one.
808 *
809 * @param list the list
810 * @returns #TRUE if length is exactly one
811 */
812 dbus_bool_t
_dbus_list_length_is_one(DBusList ** list)813 _dbus_list_length_is_one (DBusList **list)
814 {
815 return (*list != NULL &&
816 (*list)->next == *list);
817 }
818
819 /** @} */
820
821 #ifdef DBUS_BUILD_TESTS
822 #include "dbus-test.h"
823 #include <stdio.h>
824
825 static void
verify_list(DBusList ** list)826 verify_list (DBusList **list)
827 {
828 DBusList *link;
829 int length;
830
831 link = *list;
832
833 if (link == NULL)
834 return;
835
836 if (link->next == link)
837 {
838 _dbus_assert (link->prev == link);
839 _dbus_assert (*list == link);
840 return;
841 }
842
843 length = 0;
844 do
845 {
846 length += 1;
847 _dbus_assert (link->prev->next == link);
848 _dbus_assert (link->next->prev == link);
849 link = link->next;
850 }
851 while (link != *list);
852
853 _dbus_assert (length == _dbus_list_get_length (list));
854
855 if (length == 1)
856 _dbus_assert (_dbus_list_length_is_one (list));
857 else
858 _dbus_assert (!_dbus_list_length_is_one (list));
859 }
860
861 static dbus_bool_t
is_ascending_sequence(DBusList ** list)862 is_ascending_sequence (DBusList **list)
863 {
864 DBusList *link;
865 int prev;
866
867 prev = _DBUS_INT_MIN;
868
869 link = _dbus_list_get_first_link (list);
870 while (link != NULL)
871 {
872 int v = _DBUS_POINTER_TO_INT (link->data);
873
874 if (v <= prev)
875 return FALSE;
876
877 prev = v;
878
879 link = _dbus_list_get_next_link (list, link);
880 }
881
882 return TRUE;
883 }
884
885 static dbus_bool_t
is_descending_sequence(DBusList ** list)886 is_descending_sequence (DBusList **list)
887 {
888 DBusList *link;
889 int prev;
890
891 prev = _DBUS_INT_MAX;
892
893 link = _dbus_list_get_first_link (list);
894 while (link != NULL)
895 {
896 int v = _DBUS_POINTER_TO_INT (link->data);
897
898 if (v >= prev)
899 return FALSE;
900
901 prev = v;
902
903 link = _dbus_list_get_next_link (list, link);
904 }
905
906 return TRUE;
907 }
908
909 static dbus_bool_t
all_even_values(DBusList ** list)910 all_even_values (DBusList **list)
911 {
912 DBusList *link;
913
914 link = _dbus_list_get_first_link (list);
915 while (link != NULL)
916 {
917 int v = _DBUS_POINTER_TO_INT (link->data);
918
919 if ((v % 2) != 0)
920 return FALSE;
921
922 link = _dbus_list_get_next_link (list, link);
923 }
924
925 return TRUE;
926 }
927
928 static dbus_bool_t
all_odd_values(DBusList ** list)929 all_odd_values (DBusList **list)
930 {
931 DBusList *link;
932
933 link = _dbus_list_get_first_link (list);
934 while (link != NULL)
935 {
936 int v = _DBUS_POINTER_TO_INT (link->data);
937
938 if ((v % 2) == 0)
939 return FALSE;
940
941 link = _dbus_list_get_next_link (list, link);
942 }
943
944 return TRUE;
945 }
946
947 static dbus_bool_t
lists_equal(DBusList ** list1,DBusList ** list2)948 lists_equal (DBusList **list1,
949 DBusList **list2)
950 {
951 DBusList *link1;
952 DBusList *link2;
953
954 link1 = _dbus_list_get_first_link (list1);
955 link2 = _dbus_list_get_first_link (list2);
956 while (link1 && link2)
957 {
958 if (link1->data != link2->data)
959 return FALSE;
960
961 link1 = _dbus_list_get_next_link (list1, link1);
962 link2 = _dbus_list_get_next_link (list2, link2);
963 }
964
965 if (link1 || link2)
966 return FALSE;
967
968 return TRUE;
969 }
970
971 /**
972 * @ingroup DBusListInternals
973 * Unit test for DBusList
974 * @returns #TRUE on success.
975 */
976 dbus_bool_t
_dbus_list_test(void)977 _dbus_list_test (void)
978 {
979 DBusList *list1;
980 DBusList *list2;
981 DBusList *link1;
982 DBusList *link2;
983 DBusList *copy1;
984 DBusList *copy2;
985 int i;
986
987 list1 = NULL;
988 list2 = NULL;
989
990 /* Test append and prepend */
991
992 i = 0;
993 while (i < 10)
994 {
995 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
996 _dbus_assert_not_reached ("could not allocate for append");
997
998 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
999 _dbus_assert_not_reached ("count not allocate for prepend");
1000 ++i;
1001
1002 verify_list (&list1);
1003 verify_list (&list2);
1004
1005 _dbus_assert (_dbus_list_get_length (&list1) == i);
1006 _dbus_assert (_dbus_list_get_length (&list2) == i);
1007 }
1008
1009 _dbus_assert (is_ascending_sequence (&list1));
1010 _dbus_assert (is_descending_sequence (&list2));
1011
1012 /* Test list clear */
1013 _dbus_list_clear (&list1);
1014 _dbus_list_clear (&list2);
1015
1016 verify_list (&list1);
1017 verify_list (&list2);
1018
1019 /* Test get_first, get_last, pop_first, pop_last */
1020
1021 i = 0;
1022 while (i < 10)
1023 {
1024 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1025 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
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 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1068 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1069 ++i;
1070 }
1071
1072 --i;
1073 while (i >= 0)
1074 {
1075 DBusList *got_link1;
1076 DBusList *got_link2;
1077
1078 DBusList *link1;
1079 DBusList *link2;
1080
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 link1 = _dbus_list_pop_last_link (&list1);
1088 link2 = _dbus_list_pop_first_link (&list2);
1089
1090 _dbus_assert (got_link1 == link1);
1091 _dbus_assert (got_link2 == link2);
1092
1093 data1 = link1->data;
1094 data2 = link2->data;
1095
1096 _dbus_list_free_link (link1);
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 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1120 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1121 ++i;
1122
1123 verify_list (&list1);
1124 verify_list (&list2);
1125
1126 _dbus_assert (_dbus_list_get_length (&list1) == i);
1127 _dbus_assert (_dbus_list_get_length (&list2) == i);
1128 }
1129
1130 _dbus_assert (is_ascending_sequence (&list1));
1131 _dbus_assert (is_descending_sequence (&list2));
1132
1133 --i;
1134 link2 = _dbus_list_get_first_link (&list2);
1135 while (link2 != NULL)
1136 {
1137 verify_list (&link2); /* pretend this link is the head */
1138
1139 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1140
1141 link2 = _dbus_list_get_next_link (&list2, link2);
1142 --i;
1143 }
1144
1145 i = 0;
1146 link1 = _dbus_list_get_first_link (&list1);
1147 while (link1 != NULL)
1148 {
1149 verify_list (&link1); /* pretend this link is the head */
1150
1151 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1152
1153 link1 = _dbus_list_get_next_link (&list1, link1);
1154 ++i;
1155 }
1156
1157 --i;
1158 link1 = _dbus_list_get_last_link (&list1);
1159 while (link1 != NULL)
1160 {
1161 verify_list (&link1); /* pretend this link is the head */
1162
1163 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1164
1165 link1 = _dbus_list_get_prev_link (&list1, link1);
1166 --i;
1167 }
1168
1169 _dbus_list_clear (&list1);
1170 _dbus_list_clear (&list2);
1171
1172 /* Test remove */
1173
1174 i = 0;
1175 while (i < 10)
1176 {
1177 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1178 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1179 ++i;
1180 }
1181
1182 --i;
1183 while (i >= 0)
1184 {
1185 if ((i % 2) == 0)
1186 {
1187 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1188 _dbus_assert_not_reached ("element should have been in list");
1189 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1190 _dbus_assert_not_reached ("element should have been in list");
1191
1192 verify_list (&list1);
1193 verify_list (&list2);
1194 }
1195 --i;
1196 }
1197
1198 _dbus_assert (all_odd_values (&list1));
1199 _dbus_assert (all_odd_values (&list2));
1200
1201 _dbus_list_clear (&list1);
1202 _dbus_list_clear (&list2);
1203
1204 /* test removing the other half of the elements */
1205
1206 i = 0;
1207 while (i < 10)
1208 {
1209 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1210 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1211 ++i;
1212 }
1213
1214 --i;
1215 while (i >= 0)
1216 {
1217 if ((i % 2) != 0)
1218 {
1219 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1220 _dbus_assert_not_reached ("element should have been in list");
1221 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1222 _dbus_assert_not_reached ("element should have been in list");
1223
1224 verify_list (&list1);
1225 verify_list (&list2);
1226 }
1227 --i;
1228 }
1229
1230 _dbus_assert (all_even_values (&list1));
1231 _dbus_assert (all_even_values (&list2));
1232
1233 /* clear list using remove_link */
1234 while (list1 != NULL)
1235 {
1236 _dbus_list_remove_link (&list1, list1);
1237 verify_list (&list1);
1238 }
1239 while (list2 != NULL)
1240 {
1241 _dbus_list_remove_link (&list2, list2);
1242 verify_list (&list2);
1243 }
1244
1245 /* Test remove link more generally */
1246 i = 0;
1247 while (i < 10)
1248 {
1249 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1250 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1251 ++i;
1252 }
1253
1254 --i;
1255 link2 = _dbus_list_get_first_link (&list2);
1256 while (link2 != NULL)
1257 {
1258 DBusList *next = _dbus_list_get_next_link (&list2, link2);
1259
1260 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1261
1262 if ((i % 2) == 0)
1263 _dbus_list_remove_link (&list2, link2);
1264
1265 verify_list (&list2);
1266
1267 link2 = next;
1268 --i;
1269 }
1270
1271 _dbus_assert (all_odd_values (&list2));
1272 _dbus_list_clear (&list2);
1273
1274 i = 0;
1275 link1 = _dbus_list_get_first_link (&list1);
1276 while (link1 != NULL)
1277 {
1278 DBusList *next = _dbus_list_get_next_link (&list1, link1);
1279
1280 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1281
1282 if ((i % 2) != 0)
1283 _dbus_list_remove_link (&list1, link1);
1284
1285 verify_list (&list1);
1286
1287 link1 = next;
1288 ++i;
1289 }
1290
1291 _dbus_assert (all_even_values (&list1));
1292 _dbus_list_clear (&list1);
1293
1294 /* Test copying a list */
1295 i = 0;
1296 while (i < 10)
1297 {
1298 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
1299 _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
1300 ++i;
1301 }
1302
1303 /* bad pointers, because they are allowed in the copy dest */
1304 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1305 copy2 = _DBUS_INT_TO_POINTER (23);
1306
1307 _dbus_list_copy (&list1, ©1);
1308 verify_list (&list1);
1309 verify_list (©1);
1310 _dbus_assert (lists_equal (&list1, ©1));
1311
1312 _dbus_list_copy (&list2, ©2);
1313 verify_list (&list2);
1314 verify_list (©2);
1315 _dbus_assert (lists_equal (&list2, ©2));
1316
1317 /* Now test copying empty lists */
1318 _dbus_list_clear (&list1);
1319 _dbus_list_clear (&list2);
1320 _dbus_list_clear (©1);
1321 _dbus_list_clear (©2);
1322
1323 /* bad pointers, because they are allowed in the copy dest */
1324 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1325 copy2 = _DBUS_INT_TO_POINTER (23);
1326
1327 _dbus_list_copy (&list1, ©1);
1328 verify_list (&list1);
1329 verify_list (©1);
1330 _dbus_assert (lists_equal (&list1, ©1));
1331
1332 _dbus_list_copy (&list2, ©2);
1333 verify_list (&list2);
1334 verify_list (©2);
1335 _dbus_assert (lists_equal (&list2, ©2));
1336
1337 _dbus_list_clear (&list1);
1338 _dbus_list_clear (&list2);
1339
1340 /* insert_before on empty list */
1341 _dbus_list_insert_before (&list1, NULL,
1342 _DBUS_INT_TO_POINTER (0));
1343 verify_list (&list1);
1344
1345 /* inserting before first element */
1346 _dbus_list_insert_before (&list1, list1,
1347 _DBUS_INT_TO_POINTER (2));
1348 verify_list (&list1);
1349 _dbus_assert (is_descending_sequence (&list1));
1350
1351 /* inserting in the middle */
1352 _dbus_list_insert_before (&list1, list1->next,
1353 _DBUS_INT_TO_POINTER (1));
1354 verify_list (&list1);
1355 _dbus_assert (is_descending_sequence (&list1));
1356
1357 /* using insert_before to append */
1358 _dbus_list_insert_before (&list1, NULL,
1359 _DBUS_INT_TO_POINTER (-1));
1360 verify_list (&list1);
1361 _dbus_assert (is_descending_sequence (&list1));
1362
1363 _dbus_list_clear (&list1);
1364
1365 /* insert_after on empty list */
1366 _dbus_list_insert_after (&list1, NULL,
1367 _DBUS_INT_TO_POINTER (0));
1368 verify_list (&list1);
1369
1370 /* inserting after first element */
1371 _dbus_list_insert_after (&list1, list1,
1372 _DBUS_INT_TO_POINTER (1));
1373 verify_list (&list1);
1374 _dbus_assert (is_ascending_sequence (&list1));
1375
1376 /* inserting at the end */
1377 _dbus_list_insert_after (&list1, list1->next,
1378 _DBUS_INT_TO_POINTER (2));
1379 verify_list (&list1);
1380 _dbus_assert (is_ascending_sequence (&list1));
1381
1382 /* using insert_after to prepend */
1383 _dbus_list_insert_after (&list1, NULL,
1384 _DBUS_INT_TO_POINTER (-1));
1385 verify_list (&list1);
1386 _dbus_assert (is_ascending_sequence (&list1));
1387
1388 _dbus_list_clear (&list1);
1389
1390 /* using remove_last */
1391 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2));
1392 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1));
1393 _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3));
1394
1395 _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2));
1396
1397 verify_list (&list1);
1398 _dbus_assert (is_ascending_sequence (&list1));
1399
1400 _dbus_list_clear (&list1);
1401
1402 return TRUE;
1403 }
1404
1405 #endif
1406