1 // Copyright 2018 The Fuchsia Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include <zircon/listnode.h>
6 #include <unittest/unittest.h>
7 
8 namespace {
9 
10 typedef struct list_elem {
11     int value;
12     list_node_t node;
13 } list_elem_t;
14 
expect_list_sorted(list_node_t * list,int count)15 void expect_list_sorted(list_node_t* list, int count) {
16     EXPECT_EQ(list_length(list), static_cast<unsigned int>(count));
17     int index = 0;
18     list_elem_t* entry = NULL;
19     list_for_every_entry(list, entry, list_elem_t, node) {
20         EXPECT_EQ(entry->value, index);
21         EXPECT_EQ(list_next_wrap_type(list, &entry->node, list_elem_t, node)->value,
22                   (index + 1) % count);
23         EXPECT_EQ(list_prev_wrap_type(list, &entry->node, list_elem_t, node)->value,
24                   (index + count - 1) % count);
25         index++;
26     }
27 }
28 
initialize_empty_list()29 bool initialize_empty_list() {
30     BEGIN_TEST;
31 
32     list_node_t list = LIST_INITIAL_CLEARED_VALUE;
33     EXPECT_FALSE(list_in_list(&list));
34 
35     list_initialize(&list);
36     EXPECT_TRUE(list_in_list(&list));
37     EXPECT_TRUE(list_is_empty(&list));
38     EXPECT_EQ(list_length(&list), 0u);
39 
40     EXPECT_NULL(list_peek_head(&list));
41     EXPECT_NULL(list_peek_head_type(&list, list_elem_t, node));
42     EXPECT_NULL(list_peek_tail(&list));
43     EXPECT_NULL(list_peek_tail_type(&list, list_elem_t, node));
44 
45     EXPECT_NULL(list_remove_head(&list));
46     EXPECT_NULL(list_remove_head_type(&list, list_elem_t, node));
47     EXPECT_NULL(list_remove_tail(&list));
48     EXPECT_NULL(list_remove_tail_type(&list, list_elem_t, node));
49 
50     EXPECT_NULL(list_next(&list, &list));
51     EXPECT_NULL(list_next_type(&list, &list, list_elem_t, node));
52     EXPECT_NULL(list_next_wrap(&list, &list));
53     EXPECT_NULL(list_next_wrap_type(&list, &list, list_elem_t, node));
54     EXPECT_NULL(list_prev(&list, &list));
55     EXPECT_NULL(list_prev_type(&list, &list, list_elem_t, node));
56     EXPECT_NULL(list_prev_wrap(&list, &list));
57     EXPECT_NULL(list_prev_wrap_type(&list, &list, list_elem_t, node));
58 
59     END_TEST;
60 }
61 
element_add_remove()62 bool element_add_remove() {
63     BEGIN_TEST;
64 
65     list_elem_t first_set[5] = {
66         { -1, {} },
67         { 2, {} },
68         { 3, {} },
69         { 4, {} },
70         { -1, {} },
71     };
72     list_elem_t second_set[4] = {
73         { 0, {} },
74         { 6, {} },
75         { 1, {} },
76         { 5, {} },
77     };
78 
79     // Fill a list with elements from first_set.  [ -1 2 3 4 -1 ]
80     list_node_t list = LIST_INITIAL_CLEARED_VALUE;
81     list_initialize(&list);
82     for (int i = 0; i < 5; i++) {
83         list_add_tail(&list, &first_set[i].node);
84     }
85 
86     // Clear the first and last elements in the list, then add new elements in
87     // numerical order.  [ 0 1 2 3 4 5 ]
88     list_remove_head(&list);
89     list_remove_tail(&list);
90     list_add_head(&list, &second_set[0].node);
91     list_add_tail(&list, &second_set[1].node);
92     list_add_after(list_peek_head(&list), &second_set[2].node);
93     list_add_before(list_peek_tail(&list), &second_set[3].node);
94 
95     // The list should be sorted now.
96     expect_list_sorted(&list, 7);
97 
98     // Verify list deletion.
99     list_node_t* node = NULL;
100     list_node_t* to_del = NULL;
101     list_for_every_safe(&list, node, to_del) {
102         list_delete(node);
103     }
104     EXPECT_TRUE(list_is_empty(&list));
105 
106     END_TEST;
107 }
108 
list_splice_split()109 bool list_splice_split() {
110     BEGIN_TEST;
111 
112     list_elem_t first_set[3] = {
113         { 0, {} },
114         { 3, {} },
115         { 4, {} },
116     };
117     list_elem_t second_set[3] = {
118         { 5, {} },
119         { 1, {} },
120         { 2, {} },
121     };
122 
123     list_node_t first_list;
124     list_initialize(&first_list);
125     list_node_t second_list;
126     list_initialize(&second_list);
127 
128     for (int i = 0; i < 3; ++i) {
129       list_add_tail(&first_list, &first_set[i].node);
130       list_add_tail(&second_list, &second_set[i].node);
131     }
132 
133     // Splice together the initial big list.  [ 0 3 4 5 1 2 ]
134     list_splice_after(&second_list, list_peek_tail(&first_list));
135     EXPECT_EQ(list_length(&first_list), 6u);
136     EXPECT_EQ(list_length(&second_list), 0u);
137 
138     // Split off the last two elements of the list.  [ 0 3 4 5 ] [ 1 2 ]
139     list_split_after(&first_list, list_peek_tail(&first_list)->prev->prev,
140                      &second_list);
141     EXPECT_EQ(list_length(&first_list), 4u);
142     EXPECT_EQ(list_length(&second_list), 2u);
143 
144     // Splice the split portion back in, in order.  [ 0 1 2 3 4 5 ]
145     list_splice_after(&second_list, list_peek_head(&first_list));
146     EXPECT_EQ(list_length(&first_list), 6u);
147     EXPECT_EQ(list_length(&second_list), 0u);
148 
149     // The list should be sorted now.
150     expect_list_sorted(&first_list, 6);
151 
152     // Move the lists and recheck.
153     list_move(&first_list, &second_list);
154     EXPECT_EQ(list_length(&first_list), 0u);
155     EXPECT_EQ(list_length(&second_list), 6u);
156 
157     // The second list should be sorted now.
158     expect_list_sorted(&second_list, 6);
159 
160     END_TEST;
161 }
162 
163 }  // namespace
164 
165 BEGIN_TEST_CASE(listnode_tests)
166 RUN_TEST(initialize_empty_list);
167 RUN_TEST(element_add_remove);
168 RUN_TEST(list_splice_split);
END_TEST_CASE(listnode_tests)169 END_TEST_CASE(listnode_tests)
170 
171 #ifndef BUILD_COMBINED_TESTS
172 int main(int argc, char** argv) {
173     bool success = unittest_run_all_tests(argc, argv);
174     return success ? 0 : -1;
175 }
176 #endif  // BUILD_COMBINED_TESTS
177