1 // Copyright 2013 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include <string> 6 #include <utility> 7 #include <vector> 8 #include "chrome/common/instant_restricted_id_cache.h" 9 #include "testing/gtest/include/gtest/gtest.h" 10 11 namespace { 12 13 struct TestData { 14 TestData() {} 15 explicit TestData(const std::string& i_value) : value(i_value) {} 16 17 bool operator==(const TestData& rhs) const { 18 return rhs.value == value; 19 } 20 21 std::string value; 22 }; 23 24 // For printing failures nicely. 25 void PrintTo(const TestData& data, std::ostream* os) { 26 *os << data.value; 27 } 28 29 } // namespace 30 31 typedef testing::Test InstantRestrictedIDCacheTest; 32 typedef InstantRestrictedIDCache<TestData>::ItemIDPair ItemIDPair; 33 34 TEST_F(InstantRestrictedIDCacheTest, AutoIDGeneration) { 35 InstantRestrictedIDCache<TestData> cache(7); 36 EXPECT_EQ(0u, cache.cache_.size()); 37 EXPECT_EQ(0, cache.last_restricted_id_); 38 39 // Check first addition. 40 std::vector<TestData> input1; 41 input1.push_back(TestData("A")); 42 input1.push_back(TestData("B")); 43 input1.push_back(TestData("C")); 44 cache.AddItems(input1); 45 EXPECT_EQ(3u, cache.cache_.size()); 46 EXPECT_EQ(3, cache.last_restricted_id_); 47 48 std::vector<ItemIDPair> output; 49 cache.GetCurrentItems(&output); 50 EXPECT_EQ(3u, output.size()); 51 for (int i = 0; i < 3; ++i) { 52 EXPECT_EQ(i + 1, output[i].first); 53 EXPECT_EQ(input1[i], output[i].second); 54 } 55 56 TestData t; 57 EXPECT_FALSE(cache.GetItemWithRestrictedID(4, &t)); 58 EXPECT_TRUE(cache.GetItemWithRestrictedID(3, &t)); 59 EXPECT_EQ(input1[2], t); 60 61 // Add more items, no overflow. 62 std::vector<TestData> input2; 63 input2.push_back(TestData("D")); 64 input2.push_back(TestData("E")); 65 cache.AddItems(input2); 66 EXPECT_EQ(5u, cache.cache_.size()); 67 EXPECT_EQ(5, cache.last_restricted_id_); 68 69 output.clear(); 70 cache.GetCurrentItems(&output); 71 EXPECT_EQ(2u, output.size()); 72 for (int i = 0; i < 2; ++i) { 73 EXPECT_EQ(i + 4, output[i].first); 74 EXPECT_EQ(input2[i], output[i].second); 75 } 76 77 EXPECT_FALSE(cache.GetItemWithRestrictedID(6, &t)); 78 EXPECT_TRUE(cache.GetItemWithRestrictedID(3, &t)); 79 EXPECT_EQ(input1[2], t); 80 EXPECT_TRUE(cache.GetItemWithRestrictedID(5, &t)); 81 EXPECT_EQ(input2[1], t); 82 83 // Add another set, overflows. 84 std::vector<TestData> input3; 85 input3.push_back(TestData("F")); 86 input3.push_back(TestData("G")); 87 input3.push_back(TestData("H")); 88 input3.push_back(TestData("I")); 89 cache.AddItems(input3); 90 EXPECT_EQ(7u, cache.cache_.size()); 91 EXPECT_EQ(9, cache.last_restricted_id_); 92 93 output.clear(); 94 cache.GetCurrentItems(&output); 95 EXPECT_EQ(4u, output.size()); 96 for (int i = 0; i < 3; ++i) { 97 EXPECT_EQ(i + 6, output[i].first); 98 EXPECT_EQ(input3[i], output[i].second); 99 } 100 101 EXPECT_FALSE(cache.GetItemWithRestrictedID(1, &t)); 102 EXPECT_FALSE(cache.GetItemWithRestrictedID(2, &t)); 103 EXPECT_TRUE(cache.GetItemWithRestrictedID(3, &t)); 104 EXPECT_EQ(input1[2], t); 105 EXPECT_TRUE(cache.GetItemWithRestrictedID(5, &t)); 106 EXPECT_EQ(input2[1], t); 107 EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t)); 108 EXPECT_EQ(input3[1], t); 109 } 110 111 TEST_F(InstantRestrictedIDCacheTest, ManualIDGeneration) { 112 InstantRestrictedIDCache<TestData> cache(5); 113 EXPECT_EQ(0u, cache.cache_.size()); 114 EXPECT_EQ(0, cache.last_restricted_id_); 115 116 // Check first addition. 117 std::vector<ItemIDPair> input1; 118 input1.push_back(std::make_pair(1, TestData("A"))); 119 input1.push_back(std::make_pair(2, TestData("B"))); 120 input1.push_back(std::make_pair(4, TestData("C"))); 121 cache.AddItemsWithRestrictedID(input1); 122 EXPECT_EQ(3u, cache.cache_.size()); 123 EXPECT_EQ(4, cache.last_restricted_id_); 124 125 std::vector<ItemIDPair> output; 126 cache.GetCurrentItems(&output); 127 EXPECT_EQ(3u, output.size()); 128 for (int i = 0; i < 3; ++i) { 129 EXPECT_EQ(input1[i].first, output[i].first); 130 EXPECT_EQ(input1[i].second, output[i].second); 131 } 132 133 TestData t; 134 EXPECT_FALSE(cache.GetItemWithRestrictedID(3, &t)); 135 EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t)); 136 EXPECT_EQ(input1[2].second, t); 137 138 139 // Add more items, one with same rid, no overflow. 140 std::vector<ItemIDPair> input2; 141 input2.push_back(std::make_pair(4, TestData("D"))); 142 input2.push_back(std::make_pair(7, TestData("E"))); 143 cache.AddItemsWithRestrictedID(input2); 144 EXPECT_EQ(4u, cache.cache_.size()); 145 EXPECT_EQ(7, cache.last_restricted_id_); 146 147 output.clear(); 148 cache.GetCurrentItems(&output); 149 EXPECT_EQ(2u, output.size()); 150 for (int i = 0; i < 2; ++i) { 151 EXPECT_EQ(input2[i].first, output[i].first); 152 EXPECT_EQ(input2[i].second, output[i].second); 153 } 154 155 EXPECT_FALSE(cache.GetItemWithRestrictedID(6, &t)); 156 EXPECT_TRUE(cache.GetItemWithRestrictedID(2, &t)); 157 EXPECT_EQ(input1[1].second, t); 158 EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t)); 159 EXPECT_EQ(input2[0].second, t); 160 EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t)); 161 EXPECT_EQ(input2[1].second, t); 162 163 // Add another set, duplicate rids, overflows. 164 std::vector<ItemIDPair> input3; 165 input3.push_back(std::make_pair(1, TestData("F"))); 166 input3.push_back(std::make_pair(6, TestData("G"))); 167 input3.push_back(std::make_pair(9, TestData("H"))); 168 cache.AddItemsWithRestrictedID(input3); 169 EXPECT_EQ(5u, cache.cache_.size()); 170 EXPECT_EQ(9, cache.last_restricted_id_); 171 172 output.clear(); 173 cache.GetCurrentItems(&output); 174 EXPECT_EQ(3u, output.size()); 175 for (int i = 0; i < 3; ++i) { 176 EXPECT_EQ(input3[i].first, output[i].first); 177 EXPECT_EQ(input3[i].second, output[i].second); 178 } 179 180 EXPECT_TRUE(cache.GetItemWithRestrictedID(1, &t)); 181 EXPECT_EQ(input3[0].second, t); 182 EXPECT_FALSE(cache.GetItemWithRestrictedID(2, &t)); 183 EXPECT_FALSE(cache.GetItemWithRestrictedID(3, &t)); 184 EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t)); 185 EXPECT_EQ(input2[0].second, t); 186 EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t)); 187 EXPECT_EQ(input2[1].second, t); 188 EXPECT_FALSE(cache.GetItemWithRestrictedID(8, &t)); 189 EXPECT_TRUE(cache.GetItemWithRestrictedID(9, &t)); 190 EXPECT_EQ(input3[2].second, t); 191 } 192 193 TEST_F(InstantRestrictedIDCacheTest, CrazyIDGeneration) { 194 InstantRestrictedIDCache<TestData> cache(4); 195 EXPECT_EQ(0u, cache.cache_.size()); 196 EXPECT_EQ(0, cache.last_restricted_id_); 197 198 // Check first addition. 199 std::vector<ItemIDPair> input1; 200 input1.push_back(std::make_pair(0, TestData("A"))); 201 input1.push_back(std::make_pair(kint32max, TestData("B"))); 202 input1.push_back(std::make_pair(-100, TestData("C"))); 203 cache.AddItemsWithRestrictedID(input1); 204 EXPECT_EQ(3u, cache.cache_.size()); 205 EXPECT_EQ(kint32max, cache.last_restricted_id_); 206 207 std::vector<ItemIDPair> output; 208 cache.GetCurrentItems(&output); 209 EXPECT_EQ(3u, output.size()); 210 for (int i = 0; i < 3; ++i) { 211 EXPECT_EQ(input1[i].first, output[i].first); 212 EXPECT_EQ(input1[i].second, output[i].second); 213 } 214 215 TestData t; 216 EXPECT_FALSE(cache.GetItemWithRestrictedID(1, &t)); 217 EXPECT_TRUE(cache.GetItemWithRestrictedID(kint32max, &t)); 218 EXPECT_EQ(input1[1].second, t); 219 EXPECT_TRUE(cache.GetItemWithRestrictedID(-100, &t)); 220 EXPECT_EQ(input1[2].second, t); 221 222 // Add more items, one with same rid, no overflow. 223 std::vector<ItemIDPair> input2; 224 input2.push_back(std::make_pair(kint32min, TestData("D"))); 225 input2.push_back(std::make_pair(7, TestData("E"))); 226 cache.AddItemsWithRestrictedID(input2); 227 EXPECT_EQ(4u, cache.cache_.size()); 228 EXPECT_EQ(kint32max, cache.last_restricted_id_); 229 230 output.clear(); 231 cache.GetCurrentItems(&output); 232 EXPECT_EQ(2u, output.size()); 233 for (int i = 0; i < 2; ++i) { 234 EXPECT_EQ(input2[i].first, output[i].first); 235 EXPECT_EQ(input2[i].second, output[i].second); 236 } 237 238 EXPECT_FALSE(cache.GetItemWithRestrictedID(0, &t)); 239 EXPECT_TRUE(cache.GetItemWithRestrictedID(kint32max, &t)); 240 EXPECT_EQ(input1[1].second, t); 241 EXPECT_TRUE(cache.GetItemWithRestrictedID(kint32min, &t)); 242 EXPECT_EQ(input2[0].second, t); 243 EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t)); 244 EXPECT_EQ(input2[1].second, t); 245 246 // Add an item without RID. last_restricted_id_ will overflow. 247 std::vector<TestData> input3; 248 input3.push_back(TestData("F")); 249 input3.push_back(TestData("G")); 250 cache.AddItems(input3); 251 EXPECT_EQ(4u, cache.cache_.size()); 252 EXPECT_EQ(kint32min + 1, cache.last_restricted_id_); 253 254 output.clear(); 255 cache.GetCurrentItems(&output); 256 EXPECT_EQ(2u, output.size()); 257 for (int i = 0; i < 2; ++i) { 258 EXPECT_EQ(kint32min + i, output[i].first); 259 EXPECT_EQ(input3[i], output[i].second); 260 } 261 262 EXPECT_TRUE(cache.GetItemWithRestrictedID(kint32min, &t)); 263 EXPECT_EQ(input3[0], t); 264 } 265 266 TEST_F(InstantRestrictedIDCacheTest, MixIDGeneration) { 267 InstantRestrictedIDCache<TestData> cache(5); 268 EXPECT_EQ(0u, cache.cache_.size()); 269 EXPECT_EQ(0, cache.last_restricted_id_); 270 271 // Add some items with manually assigned ids. 272 std::vector<ItemIDPair> input1; 273 input1.push_back(std::make_pair(1, TestData("A"))); 274 input1.push_back(std::make_pair(2, TestData("B"))); 275 input1.push_back(std::make_pair(4, TestData("C"))); 276 cache.AddItemsWithRestrictedID(input1); 277 EXPECT_EQ(3u, cache.cache_.size()); 278 EXPECT_EQ(4, cache.last_restricted_id_); 279 280 std::vector<ItemIDPair> output; 281 cache.GetCurrentItems(&output); 282 EXPECT_EQ(3u, output.size()); 283 for (int i = 0; i < 3; ++i) { 284 EXPECT_EQ(input1[i].first, output[i].first); 285 EXPECT_EQ(input1[i].second, output[i].second); 286 } 287 288 TestData t; 289 EXPECT_FALSE(cache.GetItemWithRestrictedID(3, &t)); 290 EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t)); 291 EXPECT_EQ(input1[2].second, t); 292 293 // Add items with auto id generation. 294 std::vector<TestData> input2; 295 input2.push_back(TestData("D")); 296 input2.push_back(TestData("E")); 297 cache.AddItems(input2); 298 EXPECT_EQ(5u, cache.cache_.size()); 299 EXPECT_EQ(6, cache.last_restricted_id_); 300 301 output.clear(); 302 cache.GetCurrentItems(&output); 303 EXPECT_EQ(2u, output.size()); 304 for (int i = 0; i < 2; ++i) { 305 EXPECT_EQ(i + 5, output[i].first); 306 EXPECT_EQ(input2[i], output[i].second); 307 } 308 309 EXPECT_FALSE(cache.GetItemWithRestrictedID(3, &t)); 310 EXPECT_TRUE(cache.GetItemWithRestrictedID(2, &t)); 311 EXPECT_EQ(input1[1].second, t); 312 EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t)); 313 EXPECT_EQ(input1[2].second, t); 314 EXPECT_TRUE(cache.GetItemWithRestrictedID(5, &t)); 315 EXPECT_EQ(input2[0], t); 316 EXPECT_TRUE(cache.GetItemWithRestrictedID(6, &t)); 317 EXPECT_EQ(input2[1], t); 318 EXPECT_FALSE(cache.GetItemWithRestrictedID(7, &t)); 319 320 // Add manually assigned ids again. 321 std::vector<ItemIDPair> input3; 322 input3.push_back(std::make_pair(1, TestData("F"))); 323 input3.push_back(std::make_pair(5, TestData("G"))); 324 input3.push_back(std::make_pair(7, TestData("H"))); 325 cache.AddItemsWithRestrictedID(input3); 326 EXPECT_EQ(5u, cache.cache_.size()); 327 EXPECT_EQ(7, cache.last_restricted_id_); 328 329 output.clear(); 330 cache.GetCurrentItems(&output); 331 EXPECT_EQ(3u, output.size()); 332 for (int i = 0; i < 2; ++i) { 333 EXPECT_EQ(input3[i].first, output[i].first); 334 EXPECT_EQ(input3[i].second, output[i].second); 335 } 336 337 EXPECT_TRUE(cache.GetItemWithRestrictedID(1, &t)); 338 EXPECT_EQ(input3[0].second, t); 339 EXPECT_FALSE(cache.GetItemWithRestrictedID(2, &t)); 340 EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t)); 341 EXPECT_EQ(input1[2].second, t); 342 EXPECT_TRUE(cache.GetItemWithRestrictedID(5, &t)); 343 EXPECT_EQ(input3[1].second, t); 344 EXPECT_TRUE(cache.GetItemWithRestrictedID(6, &t)); 345 EXPECT_EQ(input2[1], t); 346 EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t)); 347 EXPECT_EQ(input3[2].second, t); 348 } 349 350 TEST_F(InstantRestrictedIDCacheTest, AddEmptySet) { 351 InstantRestrictedIDCache<TestData> cache(9); 352 EXPECT_EQ(0u, cache.cache_.size()); 353 EXPECT_EQ(0, cache.last_restricted_id_); 354 355 // Add a non-empty set of items. 356 std::vector<TestData> input1; 357 input1.push_back(TestData("A")); 358 input1.push_back(TestData("B")); 359 input1.push_back(TestData("C")); 360 cache.AddItems(input1); 361 EXPECT_EQ(3u, cache.cache_.size()); 362 EXPECT_EQ(3, cache.last_restricted_id_); 363 364 std::vector<ItemIDPair> output; 365 cache.GetCurrentItems(&output); 366 EXPECT_EQ(3u, output.size()); 367 368 // Add an empty set. 369 cache.AddItems(std::vector<TestData>()); 370 EXPECT_EQ(3u, cache.cache_.size()); 371 EXPECT_EQ(3, cache.last_restricted_id_); 372 373 cache.GetCurrentItems(&output); 374 EXPECT_TRUE(output.empty()); 375 376 // Manual IDs. 377 std::vector<ItemIDPair> input2; 378 input2.push_back(std::make_pair(10, TestData("A"))); 379 input2.push_back(std::make_pair(11, TestData("B"))); 380 input2.push_back(std::make_pair(12, TestData("C"))); 381 cache.AddItemsWithRestrictedID(input2); 382 EXPECT_EQ(6u, cache.cache_.size()); 383 EXPECT_EQ(12, cache.last_restricted_id_); 384 385 cache.GetCurrentItems(&output); 386 EXPECT_EQ(3u, output.size()); 387 388 cache.AddItemsWithRestrictedID(std::vector<ItemIDPair>()); 389 EXPECT_EQ(6u, cache.cache_.size()); 390 EXPECT_EQ(12, cache.last_restricted_id_); 391 392 cache.GetCurrentItems(&output); 393 EXPECT_TRUE(output.empty()); 394 } 395 396 TEST_F(InstantRestrictedIDCacheTest, AddItemsWithRestrictedID) { 397 InstantRestrictedIDCache<TestData> cache(29); 398 EXPECT_EQ(0u, cache.cache_.size()); 399 EXPECT_EQ(0, cache.last_restricted_id_); 400 401 std::vector<ItemIDPair> input1; 402 input1.push_back(std::make_pair(10, TestData("A"))); 403 input1.push_back(std::make_pair(11, TestData("B"))); 404 input1.push_back(std::make_pair(12, TestData("C"))); 405 cache.AddItemsWithRestrictedID(input1); 406 EXPECT_EQ(3u, cache.cache_.size()); 407 EXPECT_EQ(12, cache.last_restricted_id_); 408 EXPECT_EQ(10, cache.last_add_start_->first); 409 410 std::vector<ItemIDPair> output; 411 cache.GetCurrentItems(&output); 412 EXPECT_EQ(3u, output.size()); 413 414 // Add the same items again. 415 cache.AddItemsWithRestrictedID(input1); 416 417 // Make sure |cache.last_add_start_| is still valid. 418 cache.GetCurrentItems(&output); 419 EXPECT_EQ(3u, output.size()); 420 EXPECT_EQ(3u, cache.cache_.size()); 421 EXPECT_EQ(12, cache.last_restricted_id_); 422 EXPECT_EQ(10, cache.last_add_start_->first); 423 } 424
