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