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 25namespace { 26 27bool alloc_called = false; 28bool free_called = false; 29 30class 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 47typedef LinkedList<const char, LinkedListTestAllocator> test_list_t; 48 49std::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 60TEST(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 99TEST(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 119TEST(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 136TEST(linked_list, remove_if_last_then_push_back) { 137 test_list_t list; 138 139 list.push_back("a"); 140 list.push_back("b"); 141 list.push_back("c"); 142 list.push_back("d"); 143 144 list.remove_if([](const char* c) { 145 return *c == 'c' || *c == 'd'; 146 }); 147 148 ASSERT_EQ("ab", test_list_to_string(list)); 149 list.push_back("d"); 150 ASSERT_EQ("abd", test_list_to_string(list)); 151} 152 153TEST(linked_list, copy_to_array) { 154 test_list_t list; 155 const size_t max_size = 128; 156 const char* buf[max_size]; 157 memset(buf, 0, sizeof(buf)); 158 159 ASSERT_EQ(0U, list.copy_to_array(buf, max_size)); 160 ASSERT_EQ(nullptr, buf[0]); 161 162 list.push_back("a"); 163 list.push_back("b"); 164 list.push_back("c"); 165 list.push_back("d"); 166 167 memset(buf, 0, sizeof(buf)); 168 ASSERT_EQ(2U, list.copy_to_array(buf, 2)); 169 ASSERT_STREQ("a", buf[0]); 170 ASSERT_STREQ("b", buf[1]); 171 ASSERT_EQ(nullptr, buf[2]); 172 173 ASSERT_EQ(4U, list.copy_to_array(buf, max_size)); 174 ASSERT_STREQ("a", buf[0]); 175 ASSERT_STREQ("b", buf[1]); 176 ASSERT_STREQ("c", buf[2]); 177 ASSERT_STREQ("d", buf[3]); 178 ASSERT_EQ(nullptr, buf[4]); 179 180 memset(buf, 0, sizeof(buf)); 181 list.remove_if([](const char* c) { 182 return *c != 'c'; 183 }); 184 ASSERT_EQ(1U, list.copy_to_array(buf, max_size)); 185 ASSERT_STREQ("c", buf[0]); 186 ASSERT_EQ(nullptr, buf[1]); 187 188 memset(buf, 0, sizeof(buf)); 189 190 list.remove_if([](const char* c) { 191 return *c == 'c'; 192 }); 193 194 ASSERT_EQ(0U, list.copy_to_array(buf, max_size)); 195 ASSERT_EQ(nullptr, buf[0]); 196} 197 198TEST(linked_list, test_visit) { 199 test_list_t list; 200 list.push_back("a"); 201 list.push_back("b"); 202 list.push_back("c"); 203 list.push_back("d"); 204 205 int visits = 0; 206 std::stringstream ss; 207 bool result = list.visit([&](const char* c) { 208 ++visits; 209 ss << c; 210 return true; 211 }); 212 213 ASSERT_TRUE(result); 214 ASSERT_EQ(4, visits); 215 ASSERT_EQ("abcd", ss.str()); 216 217 visits = 0; 218 ss.str(std::string()); 219 220 result = list.visit([&](const char* c) { 221 if (++visits == 3) { 222 return false; 223 } 224 225 ss << c; 226 return true; 227 }); 228 229 ASSERT_TRUE(!result); 230 ASSERT_EQ(3, visits); 231 ASSERT_EQ("ab", ss.str()); 232} 233 234