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
8namespace {
9
10typedef struct list_elem {
11    int value;
12    list_node_t node;
13} list_elem_t;
14
15void 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
29bool 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
62bool 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
109bool 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
165BEGIN_TEST_CASE(listnode_tests)
166RUN_TEST(initialize_empty_list);
167RUN_TEST(element_add_remove);
168RUN_TEST(list_splice_split);
169END_TEST_CASE(listnode_tests)
170
171#ifndef BUILD_COMBINED_TESTS
172int 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