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 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 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 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. 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 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 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. 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 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
