chrome/common/instant_restricted_id_cache_unittest.cc

   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 }