1 // Copyright (c) 2017, 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 <algorithm>
31 #include <string>
32
33 #include "breakpad_googletest_includes.h"
34 #include "common/long_string_dictionary.h"
35
36 namespace google_breakpad {
37
38 using std::string;
39
TEST(LongStringDictionary,LongStringDictionary)40 TEST(LongStringDictionary, LongStringDictionary) {
41 // Make a new dictionary
42 LongStringDictionary dict;
43
44 // Set three distinct values on three keys
45 dict.SetKeyValue("key1", "value1");
46 dict.SetKeyValue("key2", "value2");
47 dict.SetKeyValue("key3", "value3");
48
49 EXPECT_EQ("value1", dict.GetValueForKey("key1"));
50 EXPECT_EQ("value2", dict.GetValueForKey("key2"));
51 EXPECT_EQ("value3", dict.GetValueForKey("key3"));
52 EXPECT_EQ(3u, dict.GetCount());
53 // try an unknown key
54 EXPECT_EQ("", dict.GetValueForKey("key4"));
55
56 // Remove a key
57 dict.RemoveKey("key3");
58
59 // Now make sure it's not there anymore
60 EXPECT_EQ("", dict.GetValueForKey("key3"));
61
62 // Remove by setting value to NULL
63 dict.SetKeyValue("key2", NULL);
64
65 // Now make sure it's not there anymore
66 EXPECT_EQ("", dict.GetValueForKey("key2"));
67 }
68
69 // Add a bunch of values to the dictionary, remove some entries in the middle,
70 // and then add more.
TEST(LongStringDictionary,Iterator)71 TEST(LongStringDictionary, Iterator) {
72 LongStringDictionary* dict = new LongStringDictionary();
73 ASSERT_TRUE(dict);
74
75 char key[LongStringDictionary::key_size];
76 char value[LongStringDictionary::value_size];
77
78 const int kDictionaryCapacity = LongStringDictionary::num_entries;
79 const int kPartitionIndex = kDictionaryCapacity - 5;
80
81 // We assume at least this size in the tests below
82 ASSERT_GE(kDictionaryCapacity, 64);
83
84 // We'll keep track of the number of key/value pairs we think should
85 // be in the dictionary
86 int expectedDictionarySize = 0;
87
88 // Set a bunch of key/value pairs like key0/value0, key1/value1, ...
89 for (int i = 0; i < kPartitionIndex; ++i) {
90 sprintf(key, "key%d", i);
91 sprintf(value, "value%d", i);
92 dict->SetKeyValue(key, value);
93 }
94 expectedDictionarySize = kPartitionIndex;
95
96 // set a couple of the keys twice (with the same value) - should be nop
97 dict->SetKeyValue("key2", "value2");
98 dict->SetKeyValue("key4", "value4");
99 dict->SetKeyValue("key15", "value15");
100
101 // Remove some random elements in the middle
102 dict->RemoveKey("key7");
103 dict->RemoveKey("key18");
104 dict->RemoveKey("key23");
105 dict->RemoveKey("key31");
106 expectedDictionarySize -= 4; // we just removed four key/value pairs
107
108 // Set some more key/value pairs like key59/value59, key60/value60, ...
109 for (int i = kPartitionIndex; i < kDictionaryCapacity; ++i) {
110 sprintf(key, "key%d", i);
111 sprintf(value, "value%d", i);
112 dict->SetKeyValue(key, value);
113 }
114 expectedDictionarySize += kDictionaryCapacity - kPartitionIndex;
115
116 // Now create an iterator on the dictionary
117 SimpleStringDictionary::Iterator iter(*dict);
118
119 // We then verify that it iterates through exactly the number of
120 // key/value pairs we expect, and that they match one-for-one with what we
121 // would expect. The ordering of the iteration does not matter...
122
123 // used to keep track of number of occurrences found for key/value pairs
124 int count[kDictionaryCapacity];
125 memset(count, 0, sizeof(count));
126
127 int totalCount = 0;
128
129 const SimpleStringDictionary::Entry* entry;
130 while ((entry = iter.Next())) {
131 totalCount++;
132
133 // Extract keyNumber from a string of the form key<keyNumber>
134 int keyNumber;
135 sscanf(entry->key, "key%d", &keyNumber);
136
137 // Extract valueNumber from a string of the form value<valueNumber>
138 int valueNumber;
139 sscanf(entry->value, "value%d", &valueNumber);
140
141 // The value number should equal the key number since that's how we set them
142 EXPECT_EQ(keyNumber, valueNumber);
143
144 // Key and value numbers should be in proper range:
145 // 0 <= keyNumber < kDictionaryCapacity
146 bool isKeyInGoodRange = (keyNumber >= 0 && keyNumber < kDictionaryCapacity);
147 bool isValueInGoodRange =
148 (valueNumber >= 0 && valueNumber < kDictionaryCapacity);
149 EXPECT_TRUE(isKeyInGoodRange);
150 EXPECT_TRUE(isValueInGoodRange);
151
152 if (isKeyInGoodRange && isValueInGoodRange) {
153 ++count[keyNumber];
154 }
155 }
156
157 // Make sure each of the key/value pairs showed up exactly one time, except
158 // for the ones which we removed.
159 for (size_t i = 0; i < kDictionaryCapacity; ++i) {
160 // Skip over key7, key18, key23, and key31, since we removed them
161 if (!(i == 7 || i == 18 || i == 23 || i == 31)) {
162 EXPECT_EQ(count[i], 1);
163 }
164 }
165
166 // Make sure the number of iterations matches the expected dictionary size.
167 EXPECT_EQ(totalCount, expectedDictionarySize);
168 }
169
TEST(LongStringDictionary,AddRemove)170 TEST(LongStringDictionary, AddRemove) {
171 LongStringDictionary dict;
172 dict.SetKeyValue("rob", "ert");
173 dict.SetKeyValue("mike", "pink");
174 dict.SetKeyValue("mark", "allays");
175
176 EXPECT_EQ(3u, dict.GetCount());
177 EXPECT_EQ("ert", dict.GetValueForKey("rob"));
178 EXPECT_EQ("pink", dict.GetValueForKey("mike"));
179 EXPECT_EQ("allays", dict.GetValueForKey("mark"));
180
181 dict.RemoveKey("mike");
182
183 EXPECT_EQ(2u, dict.GetCount());
184 EXPECT_EQ("", dict.GetValueForKey("mike"));
185
186 dict.SetKeyValue("mark", "mal");
187 EXPECT_EQ(2u, dict.GetCount());
188 EXPECT_EQ("mal", dict.GetValueForKey("mark"));
189
190 dict.RemoveKey("mark");
191 EXPECT_EQ(1u, dict.GetCount());
192 EXPECT_EQ("", dict.GetValueForKey("mark"));
193 }
194
TEST(LongStringDictionary,AddRemoveLongValue)195 TEST(LongStringDictionary, AddRemoveLongValue) {
196 LongStringDictionary dict;
197
198 string long_value = string(256, 'x');
199 dict.SetKeyValue("rob", long_value.c_str());
200
201 EXPECT_EQ(2u, dict.GetCount());
202
203 string long_value_part_1 = string(255, 'x');
204
205 EXPECT_EQ(long_value_part_1, dict.GetValueForKey("rob__1"));
206 EXPECT_EQ("x", dict.GetValueForKey("rob__2"));
207
208 EXPECT_EQ(long_value, dict.GetValueForKey("rob"));
209
210 dict.RemoveKey("rob");
211 EXPECT_EQ(0u, dict.GetCount());
212 }
213
TEST(LongStringDictionary,AddRemoveSuperLongValue)214 TEST(LongStringDictionary, AddRemoveSuperLongValue) {
215 LongStringDictionary dict;
216
217 string long_value = string(255 * 10, 'x');
218 dict.SetKeyValue("rob", long_value.c_str());
219
220 EXPECT_EQ(10u, dict.GetCount());
221
222 string long_value_part = string(255, 'x');
223
224 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__1"));
225 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__2"));
226 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__3"));
227 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__4"));
228 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__5"));
229 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__6"));
230 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__7"));
231 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__8"));
232 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__9"));
233 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__10"));
234 EXPECT_EQ(10u, dict.GetCount());
235
236 EXPECT_EQ(long_value, dict.GetValueForKey("rob"));
237
238 dict.RemoveKey("rob");
239 EXPECT_EQ(0u, dict.GetCount());
240 }
241
TEST(LongStringDictionary,TruncateSuperLongValue)242 TEST(LongStringDictionary, TruncateSuperLongValue) {
243 LongStringDictionary dict;
244
245 string long_value = string(255 * 11, 'x');
246 dict.SetKeyValue("rob", long_value.c_str());
247
248 EXPECT_EQ(10u, dict.GetCount());
249
250 string long_value_part = string(255, 'x');
251
252 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__1"));
253 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__2"));
254 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__3"));
255 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__4"));
256 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__5"));
257 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__6"));
258 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__7"));
259 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__8"));
260 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__9"));
261 EXPECT_EQ(long_value_part, dict.GetValueForKey("rob__10"));
262 EXPECT_EQ(10u, dict.GetCount());
263
264 string expected_long_value = string(255 * 10, 'x');
265 EXPECT_EQ(expected_long_value, dict.GetValueForKey("rob"));
266
267 dict.RemoveKey("rob");
268 EXPECT_EQ(0u, dict.GetCount());
269 }
270
TEST(LongStringDictionary,OverrideLongValue)271 TEST(LongStringDictionary, OverrideLongValue) {
272 LongStringDictionary dict;
273
274 string long_value = string(255 * 10, 'x');
275 dict.SetKeyValue("rob", long_value.c_str());
276
277 EXPECT_EQ(10u, dict.GetCount());
278 EXPECT_EQ(long_value, dict.GetValueForKey("rob"));
279
280 dict.SetKeyValue("rob", "short_value");
281
282 EXPECT_EQ(1u, dict.GetCount());
283 EXPECT_EQ("short_value", dict.GetValueForKey("rob"));
284 }
285
TEST(LongStringDictionary,OverrideShortValue)286 TEST(LongStringDictionary, OverrideShortValue) {
287 LongStringDictionary dict;
288
289 dict.SetKeyValue("rob", "short_value");
290
291 EXPECT_EQ(1u, dict.GetCount());
292 EXPECT_EQ("short_value", dict.GetValueForKey("rob"));
293
294 string long_value = string(255 * 10, 'x');
295 dict.SetKeyValue("rob", long_value.c_str());
296
297 EXPECT_EQ(10u, dict.GetCount());
298 EXPECT_EQ(long_value, dict.GetValueForKey("rob"));
299 }
300
301 } // namespace google_breakpad
302