1 /* 2 * Copyright (C) 2013 The Android Open Source Project 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in 12 * the documentation and/or other materials provided with the 13 * distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 16 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 17 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 18 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 19 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 21 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS 22 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 23 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 24 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 25 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 * SUCH DAMAGE. 27 */ 28 29 #include <stdlib.h> 30 #include <string> 31 #include <sstream> 32 33 #include <gtest/gtest.h> 34 35 #include "../linked_list.h" 36 37 namespace { 38 39 bool alloc_called = false; 40 bool free_called = false; 41 42 class LinkedListTestAllocator { 43 public: 44 typedef LinkedListEntry<const char> entry_t; 45 46 static entry_t* alloc() { 47 alloc_called = true; 48 return reinterpret_cast<entry_t*>(::malloc(sizeof(entry_t))); 49 } 50 51 static void free(entry_t* p) { 52 free_called = true; 53 ::free(p); 54 } 55 private: 56 DISALLOW_IMPLICIT_CONSTRUCTORS(LinkedListTestAllocator); 57 }; 58 59 typedef LinkedList<const char, LinkedListTestAllocator> test_list_t; 60 61 std::string test_list_to_string(test_list_t& list) { 62 std::stringstream ss; 63 list.for_each([&] (const char* c) { 64 ss << c; 65 }); 66 67 return ss.str(); 68 } 69 70 }; 71 72 TEST(linked_list, simple) { 73 alloc_called = free_called = false; 74 test_list_t list; 75 ASSERT_EQ("", test_list_to_string(list)); 76 ASSERT_TRUE(!alloc_called); 77 ASSERT_TRUE(!free_called); 78 list.push_front("a"); 79 ASSERT_TRUE(alloc_called); 80 ASSERT_TRUE(!free_called); 81 ASSERT_EQ("a", test_list_to_string(list)); 82 list.push_front("b"); 83 ASSERT_EQ("ba", test_list_to_string(list)); 84 list.push_front("c"); 85 list.push_front("d"); 86 ASSERT_EQ("dcba", test_list_to_string(list)); 87 ASSERT_TRUE(alloc_called); 88 ASSERT_TRUE(!free_called); 89 alloc_called = free_called = false; 90 list.remove_if([] (const char* c) { 91 return *c == 'c'; 92 }); 93 94 ASSERT_TRUE(!alloc_called); 95 ASSERT_TRUE(free_called); 96 97 ASSERT_EQ("dba", test_list_to_string(list)); 98 alloc_called = free_called = false; 99 list.remove_if([] (const char* c) { 100 return *c == '2'; 101 }); 102 ASSERT_TRUE(!alloc_called); 103 ASSERT_TRUE(!free_called); 104 ASSERT_EQ("dba", test_list_to_string(list)); 105 list.clear(); 106 ASSERT_TRUE(!alloc_called); 107 ASSERT_TRUE(free_called); 108 ASSERT_EQ("", test_list_to_string(list)); 109 } 110 111 TEST(linked_list, push_pop) { 112 test_list_t list; 113 list.push_front("b"); 114 list.push_front("a"); 115 ASSERT_EQ("ab", test_list_to_string(list)); 116 list.push_back("c"); 117 ASSERT_EQ("abc", test_list_to_string(list)); 118 ASSERT_STREQ("a", list.pop_front()); 119 ASSERT_EQ("bc", test_list_to_string(list)); 120 ASSERT_STREQ("b", list.pop_front()); 121 ASSERT_EQ("c", test_list_to_string(list)); 122 ASSERT_STREQ("c", list.pop_front()); 123 ASSERT_EQ("", test_list_to_string(list)); 124 ASSERT_TRUE(list.pop_front() == nullptr); 125 list.push_back("r"); 126 ASSERT_EQ("r", test_list_to_string(list)); 127 ASSERT_STREQ("r", list.pop_front()); 128 ASSERT_TRUE(list.pop_front() == nullptr); 129 } 130 131 TEST(linked_list, remove_if_then_pop) { 132 test_list_t list; 133 list.push_back("a"); 134 list.push_back("b"); 135 list.push_back("c"); 136 list.push_back("d"); 137 list.remove_if([](const char* c) { 138 return *c == 'b' || *c == 'c'; 139 }); 140 141 ASSERT_EQ("ad", test_list_to_string(list)); 142 ASSERT_STREQ("a", list.pop_front()); 143 ASSERT_EQ("d", test_list_to_string(list)); 144 ASSERT_STREQ("d", list.pop_front()); 145 ASSERT_TRUE(list.pop_front() == nullptr); 146 } 147 148 TEST(linked_list, remove_if_last_then_push_back) { 149 test_list_t list; 150 151 list.push_back("a"); 152 list.push_back("b"); 153 list.push_back("c"); 154 list.push_back("d"); 155 156 list.remove_if([](const char* c) { 157 return *c == 'c' || *c == 'd'; 158 }); 159 160 ASSERT_EQ("ab", test_list_to_string(list)); 161 list.push_back("d"); 162 ASSERT_EQ("abd", test_list_to_string(list)); 163 } 164 165 TEST(linked_list, copy_to_array) { 166 test_list_t list; 167 const size_t max_size = 128; 168 const char* buf[max_size]; 169 memset(buf, 0, sizeof(buf)); 170 171 ASSERT_EQ(0U, list.copy_to_array(buf, max_size)); 172 ASSERT_EQ(nullptr, buf[0]); 173 174 list.push_back("a"); 175 list.push_back("b"); 176 list.push_back("c"); 177 list.push_back("d"); 178 179 memset(buf, 0, sizeof(buf)); 180 ASSERT_EQ(2U, list.copy_to_array(buf, 2)); 181 ASSERT_STREQ("a", buf[0]); 182 ASSERT_STREQ("b", buf[1]); 183 ASSERT_EQ(nullptr, buf[2]); 184 185 ASSERT_EQ(4U, list.copy_to_array(buf, max_size)); 186 ASSERT_STREQ("a", buf[0]); 187 ASSERT_STREQ("b", buf[1]); 188 ASSERT_STREQ("c", buf[2]); 189 ASSERT_STREQ("d", buf[3]); 190 ASSERT_EQ(nullptr, buf[4]); 191 192 memset(buf, 0, sizeof(buf)); 193 list.remove_if([](const char* c) { 194 return *c != 'c'; 195 }); 196 ASSERT_EQ(1U, list.copy_to_array(buf, max_size)); 197 ASSERT_STREQ("c", buf[0]); 198 ASSERT_EQ(nullptr, buf[1]); 199 200 memset(buf, 0, sizeof(buf)); 201 202 list.remove_if([](const char* c) { 203 return *c == 'c'; 204 }); 205 206 ASSERT_EQ(0U, list.copy_to_array(buf, max_size)); 207 ASSERT_EQ(nullptr, buf[0]); 208 } 209 210 TEST(linked_list, test_visit) { 211 test_list_t list; 212 list.push_back("a"); 213 list.push_back("b"); 214 list.push_back("c"); 215 list.push_back("d"); 216 217 int visits = 0; 218 std::stringstream ss; 219 bool result = list.visit([&](const char* c) { 220 ++visits; 221 ss << c; 222 return true; 223 }); 224 225 ASSERT_TRUE(result); 226 ASSERT_EQ(4, visits); 227 ASSERT_EQ("abcd", ss.str()); 228 229 visits = 0; 230 ss.str(std::string()); 231 232 result = list.visit([&](const char* c) { 233 if (++visits == 3) { 234 return false; 235 } 236 237 ss << c; 238 return true; 239 }); 240 241 ASSERT_TRUE(!result); 242 ASSERT_EQ(3, visits); 243 ASSERT_EQ("ab", ss.str()); 244 } 245 246
