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
alloc()46 static entry_t* alloc() {
47 alloc_called = true;
48 return reinterpret_cast<entry_t*>(::malloc(sizeof(entry_t)));
49 }
50
free(entry_t * p)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
test_list_to_string(test_list_t & list)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
TEST(linked_list,simple)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
TEST(linked_list,push_pop)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
TEST(linked_list,remove_if_then_pop)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
TEST(linked_list,remove_if_last_then_push_back)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
TEST(linked_list,copy_to_array)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
TEST(linked_list,test_visit)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