blob: d65eda0e883d53126bcc39712283e0780482753e [file] [log] [blame]
// Copyright 2017 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include <tuple>
#include "src/base/utils/random-number-generator.h"
#include "src/compiler/persistent-map.h"
#include "test/unittests/test-utils.h"
namespace v8 {
namespace internal {
namespace compiler {
// A random distribution that produces both small values and arbitrary numbers.
static int small_big_distr(base::RandomNumberGenerator* rand) {
return rand->NextInt() / std::max(1, rand->NextInt() / 100);
}
TEST(PersistentMap, RefTest) {
base::RandomNumberGenerator rand(92834738);
AccountingAllocator allocator;
Zone zone(&allocator, ZONE_NAME);
std::vector<PersistentMap<int, int>> pers_maps;
pers_maps.emplace_back(&zone);
std::vector<std::map<int, int>> ref_maps(1);
for (int i = 0; i < 100000; ++i) {
if (rand.NextInt(2) == 0) {
// Read value;
int key = small_big_distr(&rand);
if (ref_maps[0].count(key) > 0) {
ASSERT_EQ(pers_maps[0].Get(key), ref_maps[0][key]);
} else {
ASSERT_EQ(pers_maps[0].Get(key), 0);
}
}
if (rand.NextInt(2) == 0) {
// Add value;
int key = small_big_distr(&rand);
int value = small_big_distr(&rand);
pers_maps[0].Set(key, value);
ref_maps[0][key] = value;
}
if (rand.NextInt(1000) == 0) {
// Create empty map.
pers_maps.emplace_back(&zone);
ref_maps.emplace_back();
}
if (rand.NextInt(100) == 0) {
// Copy and move around maps.
int num_maps = static_cast<int>(pers_maps.size());
int source = rand.NextInt(num_maps - 1) + 1;
int target = rand.NextInt(num_maps - 1) + 1;
pers_maps[target] = std::move(pers_maps[0]);
ref_maps[target] = std::move(ref_maps[0]);
pers_maps[0] = pers_maps[source];
ref_maps[0] = ref_maps[source];
}
}
for (size_t i = 0; i < pers_maps.size(); ++i) {
std::set<int> keys;
for (auto pair : pers_maps[i]) {
ASSERT_EQ(keys.count(pair.first), 0u);
keys.insert(pair.first);
ASSERT_EQ(ref_maps[i][pair.first], pair.second);
}
for (auto pair : ref_maps[i]) {
int value = pers_maps[i].Get(pair.first);
ASSERT_EQ(pair.second, value);
if (value != 0) {
ASSERT_EQ(keys.count(pair.first), 1u);
keys.erase(pair.first);
}
}
ASSERT_TRUE(keys.empty());
}
}
TEST(PersistentMap, Zip) {
base::RandomNumberGenerator rand(92834738);
AccountingAllocator allocator;
Zone zone(&allocator, ZONE_NAME);
// Provoke hash collisions to stress the iterator.
struct bad_hash {
size_t operator()(int key) { return static_cast<size_t>(key) % 1000; }
};
PersistentMap<int, int, bad_hash> a(&zone);
PersistentMap<int, int, bad_hash> b(&zone);
int sum_a = 0;
int sum_b = 0;
for (int i = 0; i < 30000; ++i) {
int key = small_big_distr(&rand);
int value = small_big_distr(&rand);
if (rand.NextBool()) {
sum_a += value;
a.Set(key, a.Get(key) + value);
} else {
sum_b += value;
b.Set(key, b.Get(key) + value);
}
}
int sum = sum_a + sum_b;
for (auto pair : a) {
sum_a -= pair.second;
}
ASSERT_EQ(0, sum_a);
for (auto pair : b) {
sum_b -= pair.second;
}
ASSERT_EQ(0, sum_b);
for (auto triple : a.Zip(b)) {
sum -= std::get<1>(triple) + std::get<2>(triple);
}
ASSERT_EQ(0, sum);
}
} // namespace compiler
} // namespace internal
} // namespace v8