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