1 // Copyright (c) 2008, Google Inc.
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are
6 // met:
7 //
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
11 // copyright notice, this list of conditions and the following disclaimer
12 // in the documentation and/or other materials provided with the
13 // distribution.
14 // * Neither the name of Google Inc. nor the names of its
15 // contributors may be used to endorse or promote products derived from
16 // this software without specific prior written permission.
17 //
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30 #include "breakpad_googletest_includes.h"
31 #include "common/simple_string_dictionary.h"
32
33 namespace google_breakpad {
34
TEST(NonAllocatingMapTest,Entry)35 TEST(NonAllocatingMapTest, Entry) {
36 typedef NonAllocatingMap<5, 9, 15> TestMap;
37 TestMap map;
38
39 const TestMap::Entry* entry = TestMap::Iterator(map).Next();
40 EXPECT_FALSE(entry);
41
42 // Try setting a key/value and then verify.
43 map.SetKeyValue("key1", "value1");
44 entry = TestMap::Iterator(map).Next();
45 ASSERT_TRUE(entry);
46 EXPECT_STREQ(entry->key, "key1");
47 EXPECT_STREQ(entry->value, "value1");
48
49 // Try setting a new value.
50 map.SetKeyValue("key1", "value3");
51 EXPECT_STREQ(entry->value, "value3");
52
53 // Make sure the key didn't change.
54 EXPECT_STREQ(entry->key, "key1");
55
56 // Clear the entry and verify the key and value are empty strings.
57 map.RemoveKey("key1");
58 EXPECT_FALSE(entry->is_active());
59 EXPECT_EQ(strlen(entry->key), 0u);
60 EXPECT_EQ(strlen(entry->value), 0u);
61 }
62
TEST(NonAllocatingMapTest,SimpleStringDictionary)63 TEST(NonAllocatingMapTest, SimpleStringDictionary) {
64 // Make a new dictionary
65 SimpleStringDictionary dict;
66
67 // Set three distinct values on three keys
68 dict.SetKeyValue("key1", "value1");
69 dict.SetKeyValue("key2", "value2");
70 dict.SetKeyValue("key3", "value3");
71
72 EXPECT_NE(dict.GetValueForKey("key1"), "value1");
73 EXPECT_NE(dict.GetValueForKey("key2"), "value2");
74 EXPECT_NE(dict.GetValueForKey("key3"), "value3");
75 EXPECT_EQ(dict.GetCount(), 3u);
76 // try an unknown key
77 EXPECT_FALSE(dict.GetValueForKey("key4"));
78
79 // Remove a key
80 dict.RemoveKey("key3");
81
82 // Now make sure it's not there anymore
83 EXPECT_FALSE(dict.GetValueForKey("key3"));
84
85 // Remove by setting value to NULL
86 dict.SetKeyValue("key2", NULL);
87
88 // Now make sure it's not there anymore
89 EXPECT_FALSE(dict.GetValueForKey("key2"));
90 }
91
TEST(NonAllocatingMapTest,CopyAndAssign)92 TEST(NonAllocatingMapTest, CopyAndAssign) {
93 NonAllocatingMap<10, 10, 10> map;
94 map.SetKeyValue("one", "a");
95 map.SetKeyValue("two", "b");
96 map.SetKeyValue("three", "c");
97 map.RemoveKey("two");
98 EXPECT_EQ(2u, map.GetCount());
99
100 // Test copy.
101 NonAllocatingMap<10, 10, 10> map_copy(map);
102 EXPECT_EQ(2u, map_copy.GetCount());
103 EXPECT_STREQ("a", map_copy.GetValueForKey("one"));
104 EXPECT_STREQ("c", map_copy.GetValueForKey("three"));
105 map_copy.SetKeyValue("four", "d");
106 EXPECT_STREQ("d", map_copy.GetValueForKey("four"));
107 EXPECT_FALSE(map.GetValueForKey("four"));
108
109 // Test assign.
110 NonAllocatingMap<10, 10, 10> map_assign;
111 map_assign = map;
112 EXPECT_EQ(2u, map_assign.GetCount());
113 EXPECT_STREQ("a", map_assign.GetValueForKey("one"));
114 EXPECT_STREQ("c", map_assign.GetValueForKey("three"));
115 map_assign.SetKeyValue("four", "d");
116 EXPECT_STREQ("d", map_assign.GetValueForKey("four"));
117 EXPECT_FALSE(map.GetValueForKey("four"));
118
119 map.RemoveKey("one");
120 EXPECT_FALSE(map.GetValueForKey("one"));
121 EXPECT_STREQ("a", map_copy.GetValueForKey("one"));
122 EXPECT_STREQ("a", map_assign.GetValueForKey("one"));
123 }
124
125 // Add a bunch of values to the dictionary, remove some entries in the middle,
126 // and then add more.
TEST(NonAllocatingMapTest,Iterator)127 TEST(NonAllocatingMapTest, Iterator) {
128 SimpleStringDictionary* dict = new SimpleStringDictionary();
129 ASSERT_TRUE(dict);
130
131 char key[SimpleStringDictionary::key_size];
132 char value[SimpleStringDictionary::value_size];
133
134 const int kDictionaryCapacity = SimpleStringDictionary::num_entries;
135 const int kPartitionIndex = kDictionaryCapacity - 5;
136
137 // We assume at least this size in the tests below
138 ASSERT_GE(kDictionaryCapacity, 64);
139
140 // We'll keep track of the number of key/value pairs we think should
141 // be in the dictionary
142 int expectedDictionarySize = 0;
143
144 // Set a bunch of key/value pairs like key0/value0, key1/value1, ...
145 for (int i = 0; i < kPartitionIndex; ++i) {
146 sprintf(key, "key%d", i);
147 sprintf(value, "value%d", i);
148 dict->SetKeyValue(key, value);
149 }
150 expectedDictionarySize = kPartitionIndex;
151
152 // set a couple of the keys twice (with the same value) - should be nop
153 dict->SetKeyValue("key2", "value2");
154 dict->SetKeyValue("key4", "value4");
155 dict->SetKeyValue("key15", "value15");
156
157 // Remove some random elements in the middle
158 dict->RemoveKey("key7");
159 dict->RemoveKey("key18");
160 dict->RemoveKey("key23");
161 dict->RemoveKey("key31");
162 expectedDictionarySize -= 4; // we just removed four key/value pairs
163
164 // Set some more key/value pairs like key59/value59, key60/value60, ...
165 for (int i = kPartitionIndex; i < kDictionaryCapacity; ++i) {
166 sprintf(key, "key%d", i);
167 sprintf(value, "value%d", i);
168 dict->SetKeyValue(key, value);
169 }
170 expectedDictionarySize += kDictionaryCapacity - kPartitionIndex;
171
172 // Now create an iterator on the dictionary
173 SimpleStringDictionary::Iterator iter(*dict);
174
175 // We then verify that it iterates through exactly the number of
176 // key/value pairs we expect, and that they match one-for-one with what we
177 // would expect. The ordering of the iteration does not matter...
178
179 // used to keep track of number of occurrences found for key/value pairs
180 int count[kDictionaryCapacity];
181 memset(count, 0, sizeof(count));
182
183 int totalCount = 0;
184
185 const SimpleStringDictionary::Entry* entry;
186 while ((entry = iter.Next())) {
187 totalCount++;
188
189 // Extract keyNumber from a string of the form key<keyNumber>
190 int keyNumber;
191 sscanf(entry->key, "key%d", &keyNumber);
192
193 // Extract valueNumber from a string of the form value<valueNumber>
194 int valueNumber;
195 sscanf(entry->value, "value%d", &valueNumber);
196
197 // The value number should equal the key number since that's how we set them
198 EXPECT_EQ(keyNumber, valueNumber);
199
200 // Key and value numbers should be in proper range:
201 // 0 <= keyNumber < kDictionaryCapacity
202 bool isKeyInGoodRange =
203 (keyNumber >= 0 && keyNumber < kDictionaryCapacity);
204 bool isValueInGoodRange =
205 (valueNumber >= 0 && valueNumber < kDictionaryCapacity);
206 EXPECT_TRUE(isKeyInGoodRange);
207 EXPECT_TRUE(isValueInGoodRange);
208
209 if (isKeyInGoodRange && isValueInGoodRange) {
210 ++count[keyNumber];
211 }
212 }
213
214 // Make sure each of the key/value pairs showed up exactly one time, except
215 // for the ones which we removed.
216 for (size_t i = 0; i < kDictionaryCapacity; ++i) {
217 // Skip over key7, key18, key23, and key31, since we removed them
218 if (!(i == 7 || i == 18 || i == 23 || i == 31)) {
219 EXPECT_EQ(count[i], 1);
220 }
221 }
222
223 // Make sure the number of iterations matches the expected dictionary size.
224 EXPECT_EQ(totalCount, expectedDictionarySize);
225 }
226
227
TEST(NonAllocatingMapTest,AddRemove)228 TEST(NonAllocatingMapTest, AddRemove) {
229 NonAllocatingMap<5, 7, 6> map;
230 map.SetKeyValue("rob", "ert");
231 map.SetKeyValue("mike", "pink");
232 map.SetKeyValue("mark", "allays");
233
234 EXPECT_EQ(3u, map.GetCount());
235 EXPECT_STREQ("ert", map.GetValueForKey("rob"));
236 EXPECT_STREQ("pink", map.GetValueForKey("mike"));
237 EXPECT_STREQ("allays", map.GetValueForKey("mark"));
238
239 map.RemoveKey("mike");
240
241 EXPECT_EQ(2u, map.GetCount());
242 EXPECT_FALSE(map.GetValueForKey("mike"));
243
244 map.SetKeyValue("mark", "mal");
245 EXPECT_EQ(2u, map.GetCount());
246 EXPECT_STREQ("mal", map.GetValueForKey("mark"));
247
248 map.RemoveKey("mark");
249 EXPECT_EQ(1u, map.GetCount());
250 EXPECT_FALSE(map.GetValueForKey("mark"));
251 }
252
TEST(NonAllocatingMapTest,Serialize)253 TEST(NonAllocatingMapTest, Serialize) {
254 typedef NonAllocatingMap<4, 5, 7> TestMap;
255 TestMap map;
256 map.SetKeyValue("one", "abc");
257 map.SetKeyValue("two", "def");
258 map.SetKeyValue("tre", "hig");
259
260 EXPECT_STREQ("abc", map.GetValueForKey("one"));
261 EXPECT_STREQ("def", map.GetValueForKey("two"));
262 EXPECT_STREQ("hig", map.GetValueForKey("tre"));
263
264 const SerializedNonAllocatingMap* serialized;
265 size_t size = map.Serialize(&serialized);
266
267 SerializedNonAllocatingMap* serialized_copy =
268 reinterpret_cast<SerializedNonAllocatingMap*>(malloc(size));
269 ASSERT_TRUE(serialized_copy);
270 memcpy(serialized_copy, serialized, size);
271
272 TestMap deserialized(serialized_copy, size);
273 free(serialized_copy);
274
275 EXPECT_EQ(3u, deserialized.GetCount());
276 EXPECT_STREQ("abc", deserialized.GetValueForKey("one"));
277 EXPECT_STREQ("def", deserialized.GetValueForKey("two"));
278 EXPECT_STREQ("hig", deserialized.GetValueForKey("tre"));
279 }
280
281 // Running out of space shouldn't crash.
TEST(NonAllocatingMapTest,OutOfSpace)282 TEST(NonAllocatingMapTest, OutOfSpace) {
283 NonAllocatingMap<3, 2, 2> map;
284 map.SetKeyValue("a", "1");
285 map.SetKeyValue("b", "2");
286 map.SetKeyValue("c", "3");
287 EXPECT_EQ(2u, map.GetCount());
288 EXPECT_FALSE(map.GetValueForKey("c"));
289 }
290
291 #ifndef NDEBUG
292
TEST(NonAllocatingMapTest,NullKey)293 TEST(NonAllocatingMapTest, NullKey) {
294 NonAllocatingMap<4, 6, 6> map;
295 ASSERT_DEATH(map.SetKeyValue(NULL, "hello"), "");
296
297 map.SetKeyValue("hi", "there");
298 ASSERT_DEATH(map.GetValueForKey(NULL), "");
299 EXPECT_STREQ("there", map.GetValueForKey("hi"));
300
301 ASSERT_DEATH(map.GetValueForKey(NULL), "");
302 map.RemoveKey("hi");
303 EXPECT_EQ(0u, map.GetCount());
304 }
305
306 #endif // !NDEBUG
307
308 } // namespace google_breakpad
309