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 /* Protected by _DBUS_LOCK (list) */
39 static DBusMemPool *list_pool;
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 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
free_link(DBusList * link)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
link_before(DBusList ** list,DBusList * before_this_link,DBusList * link)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
link_after(DBusList ** list,DBusList * after_this_link,DBusList * link)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
_dbus_list_get_stats(dbus_uint32_t * in_use_p,dbus_uint32_t * in_free_list_p,dbus_uint32_t * allocated_p)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
172 /** @} */
173
174 /**
175 * @addtogroup DBusList
176 * @{
177 */
178
179 /**
180 * @struct DBusList
181 *
182 * A node in a linked list.
183 *
184 * DBusList is a circular list; that is, the tail of the list
185 * points back to the head of the list. The empty list is
186 * represented by a #NULL pointer.
187 */
188
189 /**
190 * @def _dbus_list_get_next_link
191 *
192 * Gets the next link in the list, or #NULL if
193 * there are no more links. Used for iteration.
194 *
195 * @code
196 * DBusList *link;
197 * link = _dbus_list_get_first_link (&list);
198 * while (link != NULL)
199 * {
200 * printf ("value is %p\n", link->data);
201 * link = _dbus_list_get_next_link (&link);
202 * }
203 * @endcode
204 *
205 * @param list address of the list head.
206 * @param link current link.
207 * @returns the next link, or %NULL if none.
208 *
209 */
210
211 /**
212 * @def _dbus_list_get_prev_link
213 *
214 * Gets the previous link in the list, or #NULL if
215 * there are no more links. Used for iteration.
216 *
217 * @code
218 * DBusList *link;
219 * link = _dbus_list_get_last_link (&list);
220 * while (link != NULL)
221 * {
222 * printf ("value is %p\n", link->data);
223 * link = _dbus_list_get_prev_link (&link);
224 * }
225 * @endcode
226 *
227 * @param list address of the list head.
228 * @param link current link.
229 * @returns the previous link, or %NULL if none.
230 *
231 */
232
233 /**
234 * Allocates a linked list node. Useful for preallocating
235 * nodes and using _dbus_list_append_link() to avoid
236 * allocations.
237 *
238 * @param data the value to store in the link.
239 * @returns a newly allocated link.
240 */
241 DBusList*
_dbus_list_alloc_link(void * data)242 _dbus_list_alloc_link (void *data)
243 {
244 return alloc_link (data);
245 }
246
247 /**
248 * Frees a linked list node allocated with _dbus_list_alloc_link.
249 * Does not free the data in the node.
250 *
251 * @param link the list node
252 */
253 void
_dbus_list_free_link(DBusList * link)254 _dbus_list_free_link (DBusList *link)
255 {
256 free_link (link);
257 }
258
259
260 /**
261 * Appends a value to the list. May return #FALSE
262 * if insufficient memory exists to add a list link.
263 * This is a constant-time operation.
264 *
265 * @param list address of the list head.
266 * @param data the value to append.
267 * @returns #TRUE on success.
268 */
269 dbus_bool_t
_dbus_list_append(DBusList ** list,void * data)270 _dbus_list_append (DBusList **list,
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
282 /**
283 * Prepends a value to the list. May return #FALSE
284 * if insufficient memory exists to add a list link.
285 * This is a constant-time operation.
286 *
287 * @param list address of the list head.
288 * @param data the value to prepend.
289 * @returns #TRUE on success.
290 */
291 dbus_bool_t
_dbus_list_prepend(DBusList ** list,void * data)292 _dbus_list_prepend (DBusList **list,
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
306 /**
307 * Appends a link to the list.
308 * Cannot fail due to out of memory.
309 * This is a constant-time operation.
310 *
311 * @param list address of the list head.
312 * @param link the link to append.
313 */
314 void
_dbus_list_append_link(DBusList ** list,DBusList * link)315 _dbus_list_append_link (DBusList **list,
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
324 /**
325 * Prepends a link to the list.
326 * Cannot fail due to out of memory.
327 * This is a constant-time operation.
328 *
329 * @param list address of the list head.
330 * @param link the link to prepend.
331 */
332 void
_dbus_list_prepend_link(DBusList ** list,DBusList * link)333 _dbus_list_prepend_link (DBusList **list,
334 DBusList *link)
335 {
336 link_before (list, *list, link);
337 }
338
339 /**
340 * Inserts data into the list after the given existing link.
341 *
342 * @param list the list to modify
343 * @param after_this_link existing link to insert after, or #NULL to prepend
344 * @param data the value to insert
345 * @returns #TRUE on success, #FALSE if memory allocation fails
346 */
347 dbus_bool_t
_dbus_list_insert_after(DBusList ** list,DBusList * after_this_link,void * data)348 _dbus_list_insert_after (DBusList **list,
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
368 /**
369 * Inserts a link into the list before the given existing link.
370 *
371 * @param list the list to modify
372 * @param before_this_link existing link to insert before, or #NULL to append
373 * @param link the link to insert
374 */
375 void
_dbus_list_insert_before_link(DBusList ** list,DBusList * before_this_link,DBusList * link)376 _dbus_list_insert_before_link (DBusList **list,
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
386 /**
387 * Inserts a link into the list after the given existing link.
388 *
389 * @param list the list to modify
390 * @param after_this_link existing link to insert after, or #NULL to prepend
391 * @param link the link to insert
392 */
393 void
_dbus_list_insert_after_link(DBusList ** list,DBusList * after_this_link,DBusList * link)394 _dbus_list_insert_after_link (DBusList **list,
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
404 /**
405 * Removes a value from the list. Only removes the
406 * first value equal to the given data pointer,
407 * even if multiple values exist which match.
408 * This is a linear-time operation.
409 *
410 * @param list address of the list head.
411 * @param data the value to remove.
412 * @returns #TRUE if a value was found to remove.
413 */
414 dbus_bool_t
_dbus_list_remove(DBusList ** list,void * data)415 _dbus_list_remove (DBusList **list,
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
435 /**
436 * Removes a value from the list. Only removes the
437 * last value equal to the given data pointer,
438 * even if multiple values exist which match.
439 * This is a linear-time operation.
440 *
441 * @param list address of the list head.
442 * @param data the value to remove.
443 * @returns #TRUE if a value was found to remove.
444 */
445 dbus_bool_t
_dbus_list_remove_last(DBusList ** list,void * data)446 _dbus_list_remove_last (DBusList **list,
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
461 /**
462 * Finds a value in the list. Returns the last link
463 * with value equal to the given data pointer.
464 * This is a linear-time operation.
465 * Returns #NULL if no value found that matches.
466 *
467 * @param list address of the list head.
468 * @param data the value to find.
469 * @returns the link if found
470 */
471 DBusList*
_dbus_list_find_last(DBusList ** list,void * data)472 _dbus_list_find_last (DBusList **list,
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
490 /**
491 * Removes the given link from the list, but doesn't
492 * free it. _dbus_list_remove_link() both removes the
493 * link and also frees it.
494 *
495 * @param list the list
496 * @param link the link in the list
497 */
498 void
_dbus_list_unlink(DBusList ** list,DBusList * link)499 _dbus_list_unlink (DBusList **list,
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
520 /**
521 * Removes a link from the list. This is a constant-time operation.
522 *
523 * @param list address of the list head.
524 * @param link the list link to remove.
525 */
526 void
_dbus_list_remove_link(DBusList ** list,DBusList * link)527 _dbus_list_remove_link (DBusList **list,
528 DBusList *link)
529 {
530 _dbus_list_unlink (list, link);
531 free_link (link);
532 }
533
534 /**
535 * Frees all links in the list and sets the list head to #NULL. Does
536 * not free the data in each link, for obvious reasons. This is a
537 * linear-time operation.
538 *
539 * @param list address of the list head.
540 */
541 void
_dbus_list_clear(DBusList ** list)542 _dbus_list_clear (DBusList **list)
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
559 /**
560 * Gets the first link in the list.
561 * This is a constant-time operation.
562 *
563 * @param list address of the list head.
564 * @returns the first link, or #NULL for an empty list.
565 */
566 DBusList*
_dbus_list_get_first_link(DBusList ** list)567 _dbus_list_get_first_link (DBusList **list)
568 {
569 return *list;
570 }
571
572 /**
573 * Gets the last link in the list.
574 * This is a constant-time operation.
575 *
576 * @param list address of the list head.
577 * @returns the last link, or #NULL for an empty list.
578 */
579 DBusList*
_dbus_list_get_last_link(DBusList ** list)580 _dbus_list_get_last_link (DBusList **list)
581 {
582 if (*list == NULL)
583 return NULL;
584 else
585 return (*list)->prev;
586 }
587
588 /**
589 * Gets the last data in the list.
590 * This is a constant-time operation.
591 *
592 * @param list address of the list head.
593 * @returns the last data in the list, or #NULL for an empty list.
594 */
595 void*
_dbus_list_get_last(DBusList ** list)596 _dbus_list_get_last (DBusList **list)
597 {
598 if (*list == NULL)
599 return NULL;
600 else
601 return (*list)->prev->data;
602 }
603
604 /**
605 * Gets the first data in the list.
606 * This is a constant-time operation.
607 *
608 * @param list address of the list head.
609 * @returns the first data in the list, or #NULL for an empty list.
610 */
611 void*
_dbus_list_get_first(DBusList ** list)612 _dbus_list_get_first (DBusList **list)
613 {
614 if (*list == NULL)
615 return NULL;
616 else
617 return (*list)->data;
618 }
619
620 /**
621 * Removes the first link in the list and returns it. This is a
622 * constant-time operation.
623 *
624 * @param list address of the list head.
625 * @returns the first link in the list, or #NULL for an empty list.
626 */
627 DBusList*
_dbus_list_pop_first_link(DBusList ** list)628 _dbus_list_pop_first_link (DBusList **list)
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
641 /**
642 * Removes the first value in the list and returns it. This is a
643 * constant-time operation.
644 *
645 * @param list address of the list head.
646 * @returns the first data in the list, or #NULL for an empty list.
647 */
648 void*
_dbus_list_pop_first(DBusList ** list)649 _dbus_list_pop_first (DBusList **list)
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
664 /**
665 * Removes the last value in the list and returns it. This is a
666 * constant-time operation.
667 *
668 * @param list address of the list head.
669 * @returns the last data in the list, or #NULL for an empty list.
670 */
671 void*
_dbus_list_pop_last(DBusList ** list)672 _dbus_list_pop_last (DBusList **list)
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
687 /**
688 * Copies a list. This is a linear-time operation. If there isn't
689 * enough memory to copy the entire list, the destination list will be
690 * set to #NULL.
691 *
692 * @param list address of the head of the list to copy.
693 * @param dest address where the copied list should be placed.
694 * @returns #TRUE on success, #FALSE if not enough memory.
695 */
696 dbus_bool_t
_dbus_list_copy(DBusList ** list,DBusList ** dest)697 _dbus_list_copy (DBusList **list,
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
722 /**
723 * Gets the length of a list. This is a linear-time
724 * operation.
725 *
726 * @param list address of the head of the list
727 * @returns number of elements in the list.
728 */
729 int
_dbus_list_get_length(DBusList ** list)730 _dbus_list_get_length (DBusList **list)
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
748 /**
749 * Calls the given function for each element in the list. The
750 * function is passed the list element as its first argument, and the
751 * given data as its second argument.
752 *
753 * @param list address of the head of the list.
754 * @param function function to call for each element.
755 * @param data extra data for the function.
756 *
757 */
758 void
_dbus_list_foreach(DBusList ** list,DBusForeachFunction function,void * data)759 _dbus_list_foreach (DBusList **list,
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
776 /**
777 * Check whether length is exactly one.
778 *
779 * @param list the list
780 * @returns #TRUE if length is exactly one
781 */
782 dbus_bool_t
_dbus_list_length_is_one(DBusList ** list)783 _dbus_list_length_is_one (DBusList **list)
784 {
785 return (*list != NULL &&
786 (*list)->next == *list);
787 }
788
789 /** @} */
790
791 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
792 #include "dbus-test.h"
793 #include <stdio.h>
794
795 static void
verify_list(DBusList ** list)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)
826 _dbus_assert (_dbus_list_length_is_one (list));
827 else
828 _dbus_assert (!_dbus_list_length_is_one (list));
829 }
830
831 static dbus_bool_t
is_ascending_sequence(DBusList ** list)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
is_descending_sequence(DBusList ** list)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
all_even_values(DBusList ** list)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
all_odd_values(DBusList ** list)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
lists_equal(DBusList ** list1,DBusList ** list2)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
941 /**
942 * @ingroup DBusListInternals
943 * Unit test for DBusList
944 * @returns #TRUE on success.
945 */
946 dbus_bool_t
_dbus_list_test(void)947 _dbus_list_test (void)
948 {
949 DBusList *list1;
950 DBusList *list2;
951 DBusList *link1;
952 DBusList *link2;
953 DBusList *copy1;
954 DBusList *copy2;
955 int i;
956
957 list1 = NULL;
958 list2 = NULL;
959
960 /* Test append and prepend */
961
962 i = 0;
963 while (i < 10)
964 {
965 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
966 _dbus_assert_not_reached ("could not allocate for append");
967
968 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
969 _dbus_assert_not_reached ("count not allocate for prepend");
970 ++i;
971
972 verify_list (&list1);
973 verify_list (&list2);
974
975 _dbus_assert (_dbus_list_get_length (&list1) == i);
976 _dbus_assert (_dbus_list_get_length (&list2) == i);
977 }
978
979 _dbus_assert (is_ascending_sequence (&list1));
980 _dbus_assert (is_descending_sequence (&list2));
981
982 /* Test list clear */
983 _dbus_list_clear (&list1);
984 _dbus_list_clear (&list2);
985
986 verify_list (&list1);
987 verify_list (&list2);
988
989 /* Test get_first, get_last, pop_first, pop_last */
990
991 i = 0;
992 while (i < 10)
993 {
994 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
995 _dbus_assert_not_reached ("could not allocate for append");
996 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
997 _dbus_assert_not_reached ("could not allocate for prepend");
998 ++i;
999 }
1000
1001 --i;
1002 while (i >= 0)
1003 {
1004 void *got_data1;
1005 void *got_data2;
1006
1007 void *data1;
1008 void *data2;
1009
1010 got_data1 = _dbus_list_get_last (&list1);
1011 got_data2 = _dbus_list_get_first (&list2);
1012
1013 data1 = _dbus_list_pop_last (&list1);
1014 data2 = _dbus_list_pop_first (&list2);
1015
1016 _dbus_assert (got_data1 == data1);
1017 _dbus_assert (got_data2 == data2);
1018
1019 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1020 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1021
1022 verify_list (&list1);
1023 verify_list (&list2);
1024
1025 _dbus_assert (is_ascending_sequence (&list1));
1026 _dbus_assert (is_descending_sequence (&list2));
1027
1028 --i;
1029 }
1030
1031 _dbus_assert (list1 == NULL);
1032 _dbus_assert (list2 == NULL);
1033
1034 /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */
1035
1036 i = 0;
1037 while (i < 10)
1038 {
1039 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1040 _dbus_assert_not_reached ("could not allocate for append");
1041 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1042 _dbus_assert_not_reached ("could not allocate for prepend");
1043 ++i;
1044 }
1045
1046 --i;
1047 while (i >= 0)
1048 {
1049 DBusList *got_link1;
1050 DBusList *got_link2;
1051
1052 void *data1_indirect;
1053 void *data1;
1054 void *data2;
1055
1056 got_link1 = _dbus_list_get_last_link (&list1);
1057 got_link2 = _dbus_list_get_first_link (&list2);
1058
1059 link2 = _dbus_list_pop_first_link (&list2);
1060
1061 _dbus_assert (got_link2 == link2);
1062
1063 data1_indirect = got_link1->data;
1064 /* this call makes got_link1 invalid */
1065 data1 = _dbus_list_pop_last (&list1);
1066 _dbus_assert (data1 == data1_indirect);
1067 data2 = link2->data;
1068
1069 _dbus_list_free_link (link2);
1070
1071 _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
1072 _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
1073
1074 verify_list (&list1);
1075 verify_list (&list2);
1076
1077 _dbus_assert (is_ascending_sequence (&list1));
1078 _dbus_assert (is_descending_sequence (&list2));
1079
1080 --i;
1081 }
1082
1083 _dbus_assert (list1 == NULL);
1084 _dbus_assert (list2 == NULL);
1085
1086 /* Test iteration */
1087
1088 i = 0;
1089 while (i < 10)
1090 {
1091 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1092 _dbus_assert_not_reached ("could not allocate for append");
1093 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1094 _dbus_assert_not_reached ("could not allocate for prepend");
1095 ++i;
1096
1097 verify_list (&list1);
1098 verify_list (&list2);
1099
1100 _dbus_assert (_dbus_list_get_length (&list1) == i);
1101 _dbus_assert (_dbus_list_get_length (&list2) == i);
1102 }
1103
1104 _dbus_assert (is_ascending_sequence (&list1));
1105 _dbus_assert (is_descending_sequence (&list2));
1106
1107 --i;
1108 link2 = _dbus_list_get_first_link (&list2);
1109 while (link2 != NULL)
1110 {
1111 verify_list (&link2); /* pretend this link is the head */
1112
1113 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1114
1115 link2 = _dbus_list_get_next_link (&list2, link2);
1116 --i;
1117 }
1118
1119 i = 0;
1120 link1 = _dbus_list_get_first_link (&list1);
1121 while (link1 != NULL)
1122 {
1123 verify_list (&link1); /* pretend this link is the head */
1124
1125 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1126
1127 link1 = _dbus_list_get_next_link (&list1, link1);
1128 ++i;
1129 }
1130
1131 --i;
1132 link1 = _dbus_list_get_last_link (&list1);
1133 while (link1 != NULL)
1134 {
1135 verify_list (&link1); /* pretend this link is the head */
1136
1137 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1138
1139 link1 = _dbus_list_get_prev_link (&list1, link1);
1140 --i;
1141 }
1142
1143 _dbus_list_clear (&list1);
1144 _dbus_list_clear (&list2);
1145
1146 /* Test remove */
1147
1148 i = 0;
1149 while (i < 10)
1150 {
1151 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1152 _dbus_assert_not_reached ("could not allocate for append");
1153 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1154 _dbus_assert_not_reached ("could not allocate for prepend");
1155 ++i;
1156 }
1157
1158 --i;
1159 while (i >= 0)
1160 {
1161 if ((i % 2) == 0)
1162 {
1163 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1164 _dbus_assert_not_reached ("element should have been in list");
1165 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1166 _dbus_assert_not_reached ("element should have been in list");
1167
1168 verify_list (&list1);
1169 verify_list (&list2);
1170 }
1171 --i;
1172 }
1173
1174 _dbus_assert (all_odd_values (&list1));
1175 _dbus_assert (all_odd_values (&list2));
1176
1177 _dbus_list_clear (&list1);
1178 _dbus_list_clear (&list2);
1179
1180 /* test removing the other half of the elements */
1181
1182 i = 0;
1183 while (i < 10)
1184 {
1185 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1186 _dbus_assert_not_reached ("could not allocate for append");
1187 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1188 _dbus_assert_not_reached ("could not allocate for prepend");
1189 ++i;
1190 }
1191
1192 --i;
1193 while (i >= 0)
1194 {
1195 if ((i % 2) != 0)
1196 {
1197 if (!_dbus_list_remove (&list1, _DBUS_INT_TO_POINTER (i)))
1198 _dbus_assert_not_reached ("element should have been in list");
1199 if (!_dbus_list_remove (&list2, _DBUS_INT_TO_POINTER (i)))
1200 _dbus_assert_not_reached ("element should have been in list");
1201
1202 verify_list (&list1);
1203 verify_list (&list2);
1204 }
1205 --i;
1206 }
1207
1208 _dbus_assert (all_even_values (&list1));
1209 _dbus_assert (all_even_values (&list2));
1210
1211 /* clear list using remove_link */
1212 while (list1 != NULL)
1213 {
1214 _dbus_list_remove_link (&list1, list1);
1215 verify_list (&list1);
1216 }
1217 while (list2 != NULL)
1218 {
1219 _dbus_list_remove_link (&list2, list2);
1220 verify_list (&list2);
1221 }
1222
1223 /* Test remove link more generally */
1224 i = 0;
1225 while (i < 10)
1226 {
1227 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1228 _dbus_assert_not_reached ("could not allocate for append");
1229 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1230 _dbus_assert_not_reached ("could not allocate for prepend");
1231 ++i;
1232 }
1233
1234 --i;
1235 link2 = _dbus_list_get_first_link (&list2);
1236 while (link2 != NULL)
1237 {
1238 DBusList *next = _dbus_list_get_next_link (&list2, link2);
1239
1240 _dbus_assert (_DBUS_POINTER_TO_INT (link2->data) == i);
1241
1242 if ((i % 2) == 0)
1243 _dbus_list_remove_link (&list2, link2);
1244
1245 verify_list (&list2);
1246
1247 link2 = next;
1248 --i;
1249 }
1250
1251 _dbus_assert (all_odd_values (&list2));
1252 _dbus_list_clear (&list2);
1253
1254 i = 0;
1255 link1 = _dbus_list_get_first_link (&list1);
1256 while (link1 != NULL)
1257 {
1258 DBusList *next = _dbus_list_get_next_link (&list1, link1);
1259
1260 _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
1261
1262 if ((i % 2) != 0)
1263 _dbus_list_remove_link (&list1, link1);
1264
1265 verify_list (&list1);
1266
1267 link1 = next;
1268 ++i;
1269 }
1270
1271 _dbus_assert (all_even_values (&list1));
1272 _dbus_list_clear (&list1);
1273
1274 /* Test copying a list */
1275 i = 0;
1276 while (i < 10)
1277 {
1278 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i)))
1279 _dbus_assert_not_reached ("could not allocate for append");
1280 if (!_dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i)))
1281 _dbus_assert_not_reached ("could not allocate for prepend");
1282 ++i;
1283 }
1284
1285 /* bad pointers, because they are allowed in the copy dest */
1286 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1287 copy2 = _DBUS_INT_TO_POINTER (23);
1288
1289 _dbus_list_copy (&list1, ©1);
1290 verify_list (&list1);
1291 verify_list (©1);
1292 _dbus_assert (lists_equal (&list1, ©1));
1293
1294 _dbus_list_copy (&list2, ©2);
1295 verify_list (&list2);
1296 verify_list (©2);
1297 _dbus_assert (lists_equal (&list2, ©2));
1298
1299 /* Now test copying empty lists */
1300 _dbus_list_clear (&list1);
1301 _dbus_list_clear (&list2);
1302 _dbus_list_clear (©1);
1303 _dbus_list_clear (©2);
1304
1305 /* bad pointers, because they are allowed in the copy dest */
1306 copy1 = _DBUS_INT_TO_POINTER (0x342234);
1307 copy2 = _DBUS_INT_TO_POINTER (23);
1308
1309 _dbus_list_copy (&list1, ©1);
1310 verify_list (&list1);
1311 verify_list (©1);
1312 _dbus_assert (lists_equal (&list1, ©1));
1313
1314 _dbus_list_copy (&list2, ©2);
1315 verify_list (&list2);
1316 verify_list (©2);
1317 _dbus_assert (lists_equal (&list2, ©2));
1318
1319 _dbus_list_clear (&list1);
1320 _dbus_list_clear (&list2);
1321
1322 /* insert_after on empty list */
1323 _dbus_list_insert_after (&list1, NULL,
1324 _DBUS_INT_TO_POINTER (0));
1325 verify_list (&list1);
1326
1327 /* inserting after first element */
1328 _dbus_list_insert_after (&list1, list1,
1329 _DBUS_INT_TO_POINTER (1));
1330 verify_list (&list1);
1331 _dbus_assert (is_ascending_sequence (&list1));
1332
1333 /* inserting at the end */
1334 _dbus_list_insert_after (&list1, list1->next,
1335 _DBUS_INT_TO_POINTER (2));
1336 verify_list (&list1);
1337 _dbus_assert (is_ascending_sequence (&list1));
1338
1339 /* using insert_after to prepend */
1340 _dbus_list_insert_after (&list1, NULL,
1341 _DBUS_INT_TO_POINTER (-1));
1342 verify_list (&list1);
1343 _dbus_assert (is_ascending_sequence (&list1));
1344
1345 _dbus_list_clear (&list1);
1346
1347 /* using remove_last */
1348 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2)))
1349 _dbus_assert_not_reached ("could not allocate for append");
1350 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1)))
1351 _dbus_assert_not_reached ("could not allocate for append");
1352 if (!_dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3)))
1353 _dbus_assert_not_reached ("could not allocate for append");
1354
1355 _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2));
1356
1357 verify_list (&list1);
1358 _dbus_assert (is_ascending_sequence (&list1));
1359
1360 _dbus_list_clear (&list1);
1361
1362 return TRUE;
1363 }
1364
1365 #endif
1366