1 /* 2 * Copyright (C) 2013 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include <stdlib.h> 18 #include <string> 19 #include <sstream> 20 21 #include <gtest/gtest.h> 22 23 #include "../linked_list.h" 24 25 namespace { 26 27 bool alloc_called = false; 28 bool free_called = false; 29 30 class LinkedListTestAllocator { 31 public: 32 typedef LinkedListEntry<const char> entry_t; 33 34 static entry_t* alloc() { 35 alloc_called = true; 36 return reinterpret_cast<entry_t*>(::malloc(sizeof(entry_t))); 37 } 38 39 static void free(entry_t* p) { 40 free_called = true; 41 ::free(p); 42 } 43 private: 44 DISALLOW_IMPLICIT_CONSTRUCTORS(LinkedListTestAllocator); 45 }; 46 47 typedef LinkedList<const char, LinkedListTestAllocator> test_list_t; 48 49 std::string test_list_to_string(test_list_t& list) { 50 std::stringstream ss; 51 list.for_each([&] (const char* c) { 52 ss << c; 53 }); 54 55 return ss.str(); 56 } 57 58 }; 59 60 TEST(linked_list, simple) { 61 alloc_called = free_called = false; 62 test_list_t list; 63 ASSERT_EQ("", test_list_to_string(list)); 64 ASSERT_TRUE(!alloc_called); 65 ASSERT_TRUE(!free_called); 66 list.push_front("a"); 67 ASSERT_TRUE(alloc_called); 68 ASSERT_TRUE(!free_called); 69 ASSERT_EQ("a", test_list_to_string(list)); 70 list.push_front("b"); 71 ASSERT_EQ("ba", test_list_to_string(list)); 72 list.push_front("c"); 73 list.push_front("d"); 74 ASSERT_EQ("dcba", test_list_to_string(list)); 75 ASSERT_TRUE(alloc_called); 76 ASSERT_TRUE(!free_called); 77 alloc_called = free_called = false; 78 list.remove_if([] (const char* c) { 79 return *c == 'c'; 80 }); 81 82 ASSERT_TRUE(!alloc_called); 83 ASSERT_TRUE(free_called); 84 85 ASSERT_EQ("dba", test_list_to_string(list)); 86 alloc_called = free_called = false; 87 list.remove_if([] (const char* c) { 88 return *c == '2'; 89 }); 90 ASSERT_TRUE(!alloc_called); 91 ASSERT_TRUE(!free_called); 92 ASSERT_EQ("dba", test_list_to_string(list)); 93 list.clear(); 94 ASSERT_TRUE(!alloc_called); 95 ASSERT_TRUE(free_called); 96 ASSERT_EQ("", test_list_to_string(list)); 97 } 98 99 TEST(linked_list, push_pop) { 100 test_list_t list; 101 list.push_front("b"); 102 list.push_front("a"); 103 ASSERT_EQ("ab", test_list_to_string(list)); 104 list.push_back("c"); 105 ASSERT_EQ("abc", test_list_to_string(list)); 106 ASSERT_STREQ("a", list.pop_front()); 107 ASSERT_EQ("bc", test_list_to_string(list)); 108 ASSERT_STREQ("b", list.pop_front()); 109 ASSERT_EQ("c", test_list_to_string(list)); 110 ASSERT_STREQ("c", list.pop_front()); 111 ASSERT_EQ("", test_list_to_string(list)); 112 ASSERT_TRUE(list.pop_front() == nullptr); 113 list.push_back("r"); 114 ASSERT_EQ("r", test_list_to_string(list)); 115 ASSERT_STREQ("r", list.pop_front()); 116 ASSERT_TRUE(list.pop_front() == nullptr); 117 } 118 119 TEST(linked_list, remove_if_then_pop) { 120 test_list_t list; 121 list.push_back("a"); 122 list.push_back("b"); 123 list.push_back("c"); 124 list.push_back("d"); 125 list.remove_if([](const char* c) { 126 return *c == 'b' || *c == 'c'; 127 }); 128 129 ASSERT_EQ("ad", test_list_to_string(list)); 130 ASSERT_STREQ("a", list.pop_front()); 131 ASSERT_EQ("d", test_list_to_string(list)); 132 ASSERT_STREQ("d", list.pop_front()); 133 ASSERT_TRUE(list.pop_front() == nullptr); 134 } 135 136 TEST(linked_list, copy_to_array) { 137 test_list_t list; 138 const size_t max_size = 128; 139 const char* buf[max_size]; 140 memset(buf, 0, sizeof(buf)); 141 142 ASSERT_EQ(0U, list.copy_to_array(buf, max_size)); 143 ASSERT_EQ(nullptr, buf[0]); 144 145 list.push_back("a"); 146 list.push_back("b"); 147 list.push_back("c"); 148 list.push_back("d"); 149 150 memset(buf, 0, sizeof(buf)); 151 ASSERT_EQ(2U, list.copy_to_array(buf, 2)); 152 ASSERT_STREQ("a", buf[0]); 153 ASSERT_STREQ("b", buf[1]); 154 ASSERT_EQ(nullptr, buf[2]); 155 156 ASSERT_EQ(4U, list.copy_to_array(buf, max_size)); 157 ASSERT_STREQ("a", buf[0]); 158 ASSERT_STREQ("b", buf[1]); 159 ASSERT_STREQ("c", buf[2]); 160 ASSERT_STREQ("d", buf[3]); 161 ASSERT_EQ(nullptr, buf[4]); 162 163 memset(buf, 0, sizeof(buf)); 164 list.remove_if([](const char* c) { 165 return *c != 'c'; 166 }); 167 ASSERT_EQ(1U, list.copy_to_array(buf, max_size)); 168 ASSERT_STREQ("c", buf[0]); 169 ASSERT_EQ(nullptr, buf[1]); 170 171 memset(buf, 0, sizeof(buf)); 172 173 list.remove_if([](const char* c) { 174 return *c == 'c'; 175 }); 176 177 ASSERT_EQ(0U, list.copy_to_array(buf, max_size)); 178 ASSERT_EQ(nullptr, buf[0]); 179 } 180 181 TEST(linked_list, test_visit) { 182 test_list_t list; 183 list.push_back("a"); 184 list.push_back("b"); 185 list.push_back("c"); 186 list.push_back("d"); 187 188 int visits = 0; 189 std::stringstream ss; 190 bool result = list.visit([&](const char* c) { 191 ++visits; 192 ss << c; 193 return true; 194 }); 195 196 ASSERT_TRUE(result); 197 ASSERT_EQ(4, visits); 198 ASSERT_EQ("abcd", ss.str()); 199 200 visits = 0; 201 ss.str(std::string()); 202 203 result = list.visit([&](const char* c) { 204 if (++visits == 3) { 205 return false; 206 } 207 208 ss << c; 209 return true; 210 }); 211 212 ASSERT_TRUE(!result); 213 ASSERT_EQ(3, visits); 214 ASSERT_EQ("ab", ss.str()); 215 } 216 217
