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_EQ("a", list.pop_front()); 107 ASSERT_EQ("bc", test_list_to_string(list)); 108 ASSERT_EQ("b", list.pop_front()); 109 ASSERT_EQ("c", test_list_to_string(list)); 110 ASSERT_EQ("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_EQ("r", list.pop_front()); 116 ASSERT_TRUE(list.pop_front() == nullptr); 117} 118