blob: b195269b7390185453498f940351623dff0da345 [file] [log] [blame]
// Copyright 2013 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include <stdint.h>
#include <limits>
#include <string>
#include <utility>
#include <vector>
#include "chrome/renderer/instant_restricted_id_cache.h"
#include "testing/gtest/include/gtest/gtest.h"
namespace {
struct TestData {
TestData() = default;
explicit TestData(const std::string& i_value) : value(i_value) {}
bool operator==(const TestData& rhs) const {
return rhs.value == value;
}
std::string value;
};
// For printing failures nicely.
void PrintTo(const TestData& data, std::ostream* os) {
*os << data.value;
}
} // namespace
typedef testing::Test InstantRestrictedIDCacheTest;
typedef InstantRestrictedIDCache<TestData>::ItemIDPair ItemIDPair;
TEST_F(InstantRestrictedIDCacheTest, AutoIDGeneration) {
InstantRestrictedIDCache<TestData> cache(7);
EXPECT_EQ(0u, cache.cache_.size());
EXPECT_EQ(0, cache.last_restricted_id_);
// Check first addition.
std::vector<TestData> input1;
input1.push_back(TestData("A"));
input1.push_back(TestData("B"));
input1.push_back(TestData("C"));
cache.AddItems(input1);
EXPECT_EQ(3u, cache.cache_.size());
EXPECT_EQ(3, cache.last_restricted_id_);
std::vector<ItemIDPair> output;
cache.GetCurrentItems(&output);
EXPECT_EQ(3u, output.size());
for (int i = 0; i < 3; ++i) {
EXPECT_EQ(i + 1, output[i].first);
EXPECT_EQ(input1[i], output[i].second);
}
TestData t;
EXPECT_FALSE(cache.GetItemWithRestrictedID(4, &t));
EXPECT_TRUE(cache.GetItemWithRestrictedID(3, &t));
EXPECT_EQ(input1[2], t);
// Add more items, no overflow.
std::vector<TestData> input2;
input2.push_back(TestData("D"));
input2.push_back(TestData("E"));
cache.AddItems(input2);
EXPECT_EQ(5u, cache.cache_.size());
EXPECT_EQ(5, cache.last_restricted_id_);
output.clear();
cache.GetCurrentItems(&output);
EXPECT_EQ(2u, output.size());
for (int i = 0; i < 2; ++i) {
EXPECT_EQ(i + 4, output[i].first);
EXPECT_EQ(input2[i], output[i].second);
}
EXPECT_FALSE(cache.GetItemWithRestrictedID(6, &t));
EXPECT_TRUE(cache.GetItemWithRestrictedID(3, &t));
EXPECT_EQ(input1[2], t);
EXPECT_TRUE(cache.GetItemWithRestrictedID(5, &t));
EXPECT_EQ(input2[1], t);
// Add another set, overflows.
std::vector<TestData> input3;
input3.push_back(TestData("F"));
input3.push_back(TestData("G"));
input3.push_back(TestData("H"));
input3.push_back(TestData("I"));
cache.AddItems(input3);
EXPECT_EQ(7u, cache.cache_.size());
EXPECT_EQ(9, cache.last_restricted_id_);
output.clear();
cache.GetCurrentItems(&output);
EXPECT_EQ(4u, output.size());
for (int i = 0; i < 3; ++i) {
EXPECT_EQ(i + 6, output[i].first);
EXPECT_EQ(input3[i], output[i].second);
}
EXPECT_FALSE(cache.GetItemWithRestrictedID(1, &t));
EXPECT_FALSE(cache.GetItemWithRestrictedID(2, &t));
EXPECT_TRUE(cache.GetItemWithRestrictedID(3, &t));
EXPECT_EQ(input1[2], t);
EXPECT_TRUE(cache.GetItemWithRestrictedID(5, &t));
EXPECT_EQ(input2[1], t);
EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t));
EXPECT_EQ(input3[1], t);
}
TEST_F(InstantRestrictedIDCacheTest, ManualIDGeneration) {
InstantRestrictedIDCache<TestData> cache(5);
EXPECT_EQ(0u, cache.cache_.size());
EXPECT_EQ(0, cache.last_restricted_id_);
// Check first addition.
std::vector<ItemIDPair> input1;
input1.push_back(std::make_pair(1, TestData("A")));
input1.push_back(std::make_pair(2, TestData("B")));
input1.push_back(std::make_pair(4, TestData("C")));
cache.AddItemsWithRestrictedID(input1);
EXPECT_EQ(3u, cache.cache_.size());
EXPECT_EQ(4, cache.last_restricted_id_);
std::vector<ItemIDPair> output;
cache.GetCurrentItems(&output);
EXPECT_EQ(3u, output.size());
for (int i = 0; i < 3; ++i) {
EXPECT_EQ(input1[i].first, output[i].first);
EXPECT_EQ(input1[i].second, output[i].second);
}
TestData t;
EXPECT_FALSE(cache.GetItemWithRestrictedID(3, &t));
EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
EXPECT_EQ(input1[2].second, t);
// Add more items, one with same rid, no overflow.
std::vector<ItemIDPair> input2;
input2.push_back(std::make_pair(4, TestData("D")));
input2.push_back(std::make_pair(7, TestData("E")));
cache.AddItemsWithRestrictedID(input2);
EXPECT_EQ(4u, cache.cache_.size());
EXPECT_EQ(7, cache.last_restricted_id_);
output.clear();
cache.GetCurrentItems(&output);
EXPECT_EQ(2u, output.size());
for (int i = 0; i < 2; ++i) {
EXPECT_EQ(input2[i].first, output[i].first);
EXPECT_EQ(input2[i].second, output[i].second);
}
EXPECT_FALSE(cache.GetItemWithRestrictedID(6, &t));
EXPECT_TRUE(cache.GetItemWithRestrictedID(2, &t));
EXPECT_EQ(input1[1].second, t);
EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
EXPECT_EQ(input2[0].second, t);
EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t));
EXPECT_EQ(input2[1].second, t);
// Add another set, duplicate rids, overflows.
std::vector<ItemIDPair> input3;
input3.push_back(std::make_pair(1, TestData("F")));
input3.push_back(std::make_pair(6, TestData("G")));
input3.push_back(std::make_pair(9, TestData("H")));
cache.AddItemsWithRestrictedID(input3);
EXPECT_EQ(5u, cache.cache_.size());
EXPECT_EQ(9, cache.last_restricted_id_);
output.clear();
cache.GetCurrentItems(&output);
EXPECT_EQ(3u, output.size());
for (int i = 0; i < 3; ++i) {
EXPECT_EQ(input3[i].first, output[i].first);
EXPECT_EQ(input3[i].second, output[i].second);
}
EXPECT_TRUE(cache.GetItemWithRestrictedID(1, &t));
EXPECT_EQ(input3[0].second, t);
EXPECT_FALSE(cache.GetItemWithRestrictedID(2, &t));
EXPECT_FALSE(cache.GetItemWithRestrictedID(3, &t));
EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
EXPECT_EQ(input2[0].second, t);
EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t));
EXPECT_EQ(input2[1].second, t);
EXPECT_FALSE(cache.GetItemWithRestrictedID(8, &t));
EXPECT_TRUE(cache.GetItemWithRestrictedID(9, &t));
EXPECT_EQ(input3[2].second, t);
}
TEST_F(InstantRestrictedIDCacheTest, CrazyIDGeneration) {
InstantRestrictedIDCache<TestData> cache(4);
EXPECT_EQ(0u, cache.cache_.size());
EXPECT_EQ(0, cache.last_restricted_id_);
// Check first addition.
std::vector<ItemIDPair> input1;
input1.push_back(std::make_pair(0, TestData("A")));
input1.push_back(
std::make_pair(std::numeric_limits<int32_t>::max(), TestData("B")));
input1.push_back(std::make_pair(-100, TestData("C")));
cache.AddItemsWithRestrictedID(input1);
EXPECT_EQ(3u, cache.cache_.size());
EXPECT_EQ(std::numeric_limits<int32_t>::max(), cache.last_restricted_id_);
std::vector<ItemIDPair> output;
cache.GetCurrentItems(&output);
EXPECT_EQ(3u, output.size());
for (int i = 0; i < 3; ++i) {
EXPECT_EQ(input1[i].first, output[i].first);
EXPECT_EQ(input1[i].second, output[i].second);
}
TestData t;
EXPECT_FALSE(cache.GetItemWithRestrictedID(1, &t));
EXPECT_TRUE(
cache.GetItemWithRestrictedID(std::numeric_limits<int32_t>::max(), &t));
EXPECT_EQ(input1[1].second, t);
EXPECT_TRUE(cache.GetItemWithRestrictedID(-100, &t));
EXPECT_EQ(input1[2].second, t);
// Add more items, one with same rid, no overflow.
std::vector<ItemIDPair> input2;
input2.push_back(
std::make_pair(std::numeric_limits<int32_t>::min(), TestData("D")));
input2.push_back(std::make_pair(7, TestData("E")));
cache.AddItemsWithRestrictedID(input2);
EXPECT_EQ(4u, cache.cache_.size());
EXPECT_EQ(std::numeric_limits<int32_t>::max(), cache.last_restricted_id_);
output.clear();
cache.GetCurrentItems(&output);
EXPECT_EQ(2u, output.size());
for (int i = 0; i < 2; ++i) {
EXPECT_EQ(input2[i].first, output[i].first);
EXPECT_EQ(input2[i].second, output[i].second);
}
EXPECT_FALSE(cache.GetItemWithRestrictedID(0, &t));
EXPECT_TRUE(
cache.GetItemWithRestrictedID(std::numeric_limits<int32_t>::max(), &t));
EXPECT_EQ(input1[1].second, t);
EXPECT_TRUE(
cache.GetItemWithRestrictedID(std::numeric_limits<int32_t>::min(), &t));
EXPECT_EQ(input2[0].second, t);
EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t));
EXPECT_EQ(input2[1].second, t);
// Add an item without RID. last_restricted_id_ will overflow.
std::vector<TestData> input3;
input3.push_back(TestData("F"));
input3.push_back(TestData("G"));
cache.AddItems(input3);
EXPECT_EQ(4u, cache.cache_.size());
EXPECT_EQ(std::numeric_limits<int32_t>::min() + 1, cache.last_restricted_id_);
output.clear();
cache.GetCurrentItems(&output);
EXPECT_EQ(2u, output.size());
for (int i = 0; i < 2; ++i) {
EXPECT_EQ(std::numeric_limits<int32_t>::min() + i, output[i].first);
EXPECT_EQ(input3[i], output[i].second);
}
EXPECT_TRUE(
cache.GetItemWithRestrictedID(std::numeric_limits<int32_t>::min(), &t));
EXPECT_EQ(input3[0], t);
}
TEST_F(InstantRestrictedIDCacheTest, MixIDGeneration) {
InstantRestrictedIDCache<TestData> cache(5);
EXPECT_EQ(0u, cache.cache_.size());
EXPECT_EQ(0, cache.last_restricted_id_);
// Add some items with manually assigned ids.
std::vector<ItemIDPair> input1;
input1.push_back(std::make_pair(1, TestData("A")));
input1.push_back(std::make_pair(2, TestData("B")));
input1.push_back(std::make_pair(4, TestData("C")));
cache.AddItemsWithRestrictedID(input1);
EXPECT_EQ(3u, cache.cache_.size());
EXPECT_EQ(4, cache.last_restricted_id_);
std::vector<ItemIDPair> output;
cache.GetCurrentItems(&output);
EXPECT_EQ(3u, output.size());
for (int i = 0; i < 3; ++i) {
EXPECT_EQ(input1[i].first, output[i].first);
EXPECT_EQ(input1[i].second, output[i].second);
}
TestData t;
EXPECT_FALSE(cache.GetItemWithRestrictedID(3, &t));
EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
EXPECT_EQ(input1[2].second, t);
// Add items with auto id generation.
std::vector<TestData> input2;
input2.push_back(TestData("D"));
input2.push_back(TestData("E"));
cache.AddItems(input2);
EXPECT_EQ(5u, cache.cache_.size());
EXPECT_EQ(6, cache.last_restricted_id_);
output.clear();
cache.GetCurrentItems(&output);
EXPECT_EQ(2u, output.size());
for (int i = 0; i < 2; ++i) {
EXPECT_EQ(i + 5, output[i].first);
EXPECT_EQ(input2[i], output[i].second);
}
EXPECT_FALSE(cache.GetItemWithRestrictedID(3, &t));
EXPECT_TRUE(cache.GetItemWithRestrictedID(2, &t));
EXPECT_EQ(input1[1].second, t);
EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
EXPECT_EQ(input1[2].second, t);
EXPECT_TRUE(cache.GetItemWithRestrictedID(5, &t));
EXPECT_EQ(input2[0], t);
EXPECT_TRUE(cache.GetItemWithRestrictedID(6, &t));
EXPECT_EQ(input2[1], t);
EXPECT_FALSE(cache.GetItemWithRestrictedID(7, &t));
// Add manually assigned ids again.
std::vector<ItemIDPair> input3;
input3.push_back(std::make_pair(1, TestData("F")));
input3.push_back(std::make_pair(5, TestData("G")));
input3.push_back(std::make_pair(7, TestData("H")));
cache.AddItemsWithRestrictedID(input3);
EXPECT_EQ(5u, cache.cache_.size());
EXPECT_EQ(7, cache.last_restricted_id_);
output.clear();
cache.GetCurrentItems(&output);
EXPECT_EQ(3u, output.size());
for (int i = 0; i < 2; ++i) {
EXPECT_EQ(input3[i].first, output[i].first);
EXPECT_EQ(input3[i].second, output[i].second);
}
EXPECT_TRUE(cache.GetItemWithRestrictedID(1, &t));
EXPECT_EQ(input3[0].second, t);
EXPECT_FALSE(cache.GetItemWithRestrictedID(2, &t));
EXPECT_TRUE(cache.GetItemWithRestrictedID(4, &t));
EXPECT_EQ(input1[2].second, t);
EXPECT_TRUE(cache.GetItemWithRestrictedID(5, &t));
EXPECT_EQ(input3[1].second, t);
EXPECT_TRUE(cache.GetItemWithRestrictedID(6, &t));
EXPECT_EQ(input2[1], t);
EXPECT_TRUE(cache.GetItemWithRestrictedID(7, &t));
EXPECT_EQ(input3[2].second, t);
}
TEST_F(InstantRestrictedIDCacheTest, AddEmptySet) {
InstantRestrictedIDCache<TestData> cache(9);
EXPECT_EQ(0u, cache.cache_.size());
EXPECT_EQ(0, cache.last_restricted_id_);
// Add a non-empty set of items.
std::vector<TestData> input1;
input1.push_back(TestData("A"));
input1.push_back(TestData("B"));
input1.push_back(TestData("C"));
cache.AddItems(input1);
EXPECT_EQ(3u, cache.cache_.size());
EXPECT_EQ(3, cache.last_restricted_id_);
std::vector<ItemIDPair> output;
cache.GetCurrentItems(&output);
EXPECT_EQ(3u, output.size());
// Add an empty set.
cache.AddItems(std::vector<TestData>());
EXPECT_EQ(3u, cache.cache_.size());
EXPECT_EQ(3, cache.last_restricted_id_);
cache.GetCurrentItems(&output);
EXPECT_TRUE(output.empty());
// Manual IDs.
std::vector<ItemIDPair> input2;
input2.push_back(std::make_pair(10, TestData("A")));
input2.push_back(std::make_pair(11, TestData("B")));
input2.push_back(std::make_pair(12, TestData("C")));
cache.AddItemsWithRestrictedID(input2);
EXPECT_EQ(6u, cache.cache_.size());
EXPECT_EQ(12, cache.last_restricted_id_);
cache.GetCurrentItems(&output);
EXPECT_EQ(3u, output.size());
cache.AddItemsWithRestrictedID(std::vector<ItemIDPair>());
EXPECT_EQ(6u, cache.cache_.size());
EXPECT_EQ(12, cache.last_restricted_id_);
cache.GetCurrentItems(&output);
EXPECT_TRUE(output.empty());
}
TEST_F(InstantRestrictedIDCacheTest, AddItemsWithRestrictedID) {
InstantRestrictedIDCache<TestData> cache(29);
EXPECT_EQ(0u, cache.cache_.size());
EXPECT_EQ(0, cache.last_restricted_id_);
std::vector<ItemIDPair> input1;
input1.push_back(std::make_pair(10, TestData("A")));
input1.push_back(std::make_pair(11, TestData("B")));
input1.push_back(std::make_pair(12, TestData("C")));
cache.AddItemsWithRestrictedID(input1);
EXPECT_EQ(3u, cache.cache_.size());
EXPECT_EQ(12, cache.last_restricted_id_);
EXPECT_EQ(10, cache.last_add_start_->first);
std::vector<ItemIDPair> output;
cache.GetCurrentItems(&output);
EXPECT_EQ(3u, output.size());
// Add the same items again.
cache.AddItemsWithRestrictedID(input1);
// Make sure |cache.last_add_start_| is still valid.
cache.GetCurrentItems(&output);
EXPECT_EQ(3u, output.size());
EXPECT_EQ(3u, cache.cache_.size());
EXPECT_EQ(12, cache.last_restricted_id_);
EXPECT_EQ(10, cache.last_add_start_->first);
}