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