blob: 660303b6e24c74a1e64cb4a08ecaf92dfdb78292 [file] [log] [blame]
/*
* Copyright 2015 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#include "include/core/SkRefCnt.h"
#include "include/core/SkString.h"
#include "include/private/SkChecksum.h"
#include "include/private/SkTHash.h"
#include "tests/Test.h"
#include <tuple>
// Tests use of const foreach(). map.count() is of course the better way to do this.
static int count(const SkTHashMap<int, double>& map) {
int n = 0;
map.foreach([&n](int, double) { n++; });
return n;
}
DEF_TEST(HashMap, r) {
SkTHashMap<int, double> map;
map.set(3, 4.0);
REPORTER_ASSERT(r, map.count() == 1);
REPORTER_ASSERT(r, map.approxBytesUsed() > 0);
double* found = map.find(3);
REPORTER_ASSERT(r, found);
REPORTER_ASSERT(r, *found == 4.0);
map.foreach([](int key, double* d){ *d = -key; });
REPORTER_ASSERT(r, count(map) == 1);
found = map.find(3);
REPORTER_ASSERT(r, found);
REPORTER_ASSERT(r, *found == -3.0);
REPORTER_ASSERT(r, !map.find(2));
const int N = 20;
for (int i = 0; i < N; i++) {
map.set(i, 2.0*i);
}
// Test walking the map with iterators, using preincrement (++iter).
for (SkTHashMap<int, double>::Iter iter = map.begin(); iter != map.end(); ++iter) {
REPORTER_ASSERT(r, iter->first * 2 == (*iter).second);
}
// Test walking the map with range-based for.
for (auto& entry : map) {
REPORTER_ASSERT(r, entry.first * 2 == entry.second);
}
// Ensure that iteration works equally well on a const map, using postincrement (iter++).
const auto& cmap = map;
for (SkTHashMap<int, double>::Iter iter = cmap.begin(); iter != cmap.end(); iter++) {
REPORTER_ASSERT(r, iter->first * 2 == (*iter).second);
}
// Ensure that range-based for works equally well on a const map.
for (const auto& entry : cmap) {
REPORTER_ASSERT(r, entry.first * 2 == entry.second);
}
// Ensure that structured bindings work.
for (const auto& [number, timesTwo] : cmap) {
REPORTER_ASSERT(r, number * 2 == timesTwo);
}
SkTHashMap<int, double> clone = map;
for (int i = 0; i < N; i++) {
double* found = map.find(i);
REPORTER_ASSERT(r, found);
REPORTER_ASSERT(r, *found == i*2.0);
found = clone.find(i);
REPORTER_ASSERT(r, found);
REPORTER_ASSERT(r, *found == i*2.0);
}
for (int i = N; i < 2*N; i++) {
REPORTER_ASSERT(r, !map.find(i));
REPORTER_ASSERT(r, !clone.find(i));
}
REPORTER_ASSERT(r, map.count() == N);
REPORTER_ASSERT(r, clone.count() == N);
for (int i = 0; i < N/2; i++) {
map.remove(i);
}
for (int i = 0; i < N; i++) {
double* found = map.find(i);
REPORTER_ASSERT(r, (found == nullptr) == (i < N/2));
found = clone.find(i);
REPORTER_ASSERT(r, *found == i*2.0);
}
REPORTER_ASSERT(r, map.count() == N/2);
REPORTER_ASSERT(r, clone.count() == N);
map.reset();
REPORTER_ASSERT(r, map.count() == 0);
REPORTER_ASSERT(r, clone.count() == N);
clone = map;
REPORTER_ASSERT(r, clone.count() == 0);
{
// Test that we don't leave dangling values in empty slots.
SkTHashMap<int, sk_sp<SkRefCnt>> refMap;
auto ref = sk_make_sp<SkRefCnt>();
REPORTER_ASSERT(r, ref->unique());
refMap.set(0, ref);
REPORTER_ASSERT(r, refMap.count() == 1);
REPORTER_ASSERT(r, !ref->unique());
refMap.remove(0);
REPORTER_ASSERT(r, refMap.count() == 0);
REPORTER_ASSERT(r, ref->unique());
}
}
DEF_TEST(HashSet, r) {
SkTHashSet<SkString> set;
set.add(SkString("Hello"));
set.add(SkString("World"));
REPORTER_ASSERT(r, set.count() == 2);
REPORTER_ASSERT(r, set.contains(SkString("Hello")));
REPORTER_ASSERT(r, set.contains(SkString("World")));
REPORTER_ASSERT(r, !set.contains(SkString("Goodbye")));
REPORTER_ASSERT(r, set.find(SkString("Hello")));
REPORTER_ASSERT(r, *set.find(SkString("Hello")) == SkString("Hello"));
// Test walking the set with iterators, using preincrement (++iter).
for (SkTHashSet<SkString>::Iter iter = set.begin(); iter != set.end(); ++iter) {
REPORTER_ASSERT(r, iter->equals("Hello") || (*iter).equals("World"));
}
// Test walking the set with iterators, using postincrement (iter++).
for (SkTHashSet<SkString>::Iter iter = set.begin(); iter != set.end(); iter++) {
REPORTER_ASSERT(r, iter->equals("Hello") || (*iter).equals("World"));
}
// Test walking the set with range-based for.
for (auto& entry : set) {
REPORTER_ASSERT(r, entry.equals("Hello") || entry.equals("World"));
}
// Ensure that iteration works equally well on a const set.
const auto& cset = set;
for (SkTHashSet<SkString>::Iter iter = cset.begin(); iter != cset.end(); iter++) {
REPORTER_ASSERT(r, iter->equals("Hello") || (*iter).equals("World"));
}
// Ensure that range-based for works equally well on a const set.
for (auto& entry : cset) {
REPORTER_ASSERT(r, entry.equals("Hello") || entry.equals("World"));
}
SkTHashSet<SkString> clone = set;
REPORTER_ASSERT(r, clone.count() == 2);
REPORTER_ASSERT(r, clone.contains(SkString("Hello")));
REPORTER_ASSERT(r, clone.contains(SkString("World")));
REPORTER_ASSERT(r, !clone.contains(SkString("Goodbye")));
REPORTER_ASSERT(r, clone.find(SkString("Hello")));
REPORTER_ASSERT(r, *clone.find(SkString("Hello")) == SkString("Hello"));
set.remove(SkString("Hello"));
REPORTER_ASSERT(r, !set.contains(SkString("Hello")));
REPORTER_ASSERT(r, set.count() == 1);
REPORTER_ASSERT(r, clone.contains(SkString("Hello")));
REPORTER_ASSERT(r, clone.count() == 2);
set.reset();
REPORTER_ASSERT(r, set.count() == 0);
clone = set;
REPORTER_ASSERT(r, clone.count() == 0);
}
namespace {
class CopyCounter {
public:
CopyCounter() : fID(0), fCounter(nullptr) {}
CopyCounter(uint32_t id, uint32_t* counter) : fID(id), fCounter(counter) {}
CopyCounter(const CopyCounter& other)
: fID(other.fID)
, fCounter(other.fCounter) {
SkASSERT(fCounter);
*fCounter += 1;
}
void operator=(const CopyCounter& other) {
fID = other.fID;
fCounter = other.fCounter;
*fCounter += 1;
}
CopyCounter(CopyCounter&& other) { *this = std::move(other); }
void operator=(CopyCounter&& other) {
fID = other.fID;
fCounter = other.fCounter;
}
bool operator==(const CopyCounter& other) const {
return fID == other.fID;
}
private:
uint32_t fID;
uint32_t* fCounter;
};
struct HashCopyCounter {
uint32_t operator()(const CopyCounter&) const {
return 0; // let them collide, what do we care?
}
};
} // namespace
DEF_TEST(HashSetCopyCounter, r) {
SkTHashSet<CopyCounter, HashCopyCounter> set;
uint32_t globalCounter = 0;
CopyCounter copyCounter1(1, &globalCounter);
CopyCounter copyCounter2(2, &globalCounter);
REPORTER_ASSERT(r, globalCounter == 0);
set.add(copyCounter1);
REPORTER_ASSERT(r, globalCounter == 1);
REPORTER_ASSERT(r, set.contains(copyCounter1));
REPORTER_ASSERT(r, globalCounter == 1);
set.add(copyCounter1);
// We allow copies for same-value adds for now.
REPORTER_ASSERT(r, globalCounter == 2);
set.add(copyCounter2);
REPORTER_ASSERT(r, globalCounter == 3);
REPORTER_ASSERT(r, set.contains(copyCounter1));
REPORTER_ASSERT(r, set.contains(copyCounter2));
REPORTER_ASSERT(r, globalCounter == 3);
set.add(copyCounter1);
set.add(copyCounter2);
// We allow copies for same-value adds for now.
REPORTER_ASSERT(r, globalCounter == 5);
}
DEF_TEST(HashFindOrNull, r) {
struct Entry {
int key = 0;
int val = 0;
};
struct HashTraits {
static int GetKey(const Entry* e) { return e->key; }
static uint32_t Hash(int key) { return key; }
};
SkTHashTable<Entry*, int, HashTraits> table;
REPORTER_ASSERT(r, nullptr == table.findOrNull(7));
Entry seven = { 7, 24 };
table.set(&seven);
REPORTER_ASSERT(r, &seven == table.findOrNull(7));
}
DEF_TEST(HashTableGrowsAndShrinks, r) {
SkTHashSet<int> s;
auto check_count_cap = [&](int count, int cap) {
REPORTER_ASSERT(r, s.count() == count);
REPORTER_ASSERT(r, s.approxBytesUsed() == (sizeof(int) + sizeof(uint32_t)) * cap);
};
// Add and remove some elements to test basic growth and shrink patterns.
check_count_cap(0,0);
s.add(1); check_count_cap(1,4);
s.add(2); check_count_cap(2,4);
s.add(3); check_count_cap(3,4);
s.add(4); check_count_cap(4,8);
s.remove(4); check_count_cap(3,8);
s.remove(3); check_count_cap(2,4);
s.remove(2); check_count_cap(1,4);
s.remove(1); check_count_cap(0,4);
s.add(1); check_count_cap(1,4);
s.add(2); check_count_cap(2,4);
s.add(3); check_count_cap(3,4);
s.add(4); check_count_cap(4,8);
// Add and remove single elements repeatedly to test hysteresis
// avoids reallocating these small tables all the time.
for (int i = 0; i < 10; i++) {
s. add(5); check_count_cap(5,8);
s.remove(5); check_count_cap(4,8);
}
s.remove(4); check_count_cap(3,8);
for (int i = 0; i < 10; i++) {
s. add(4); check_count_cap(4,8);
s.remove(4); check_count_cap(3,8);
}
s.remove(3); check_count_cap(2,4);
for (int i = 0; i < 10; i++) {
s. add(4); check_count_cap(3,4);
s.remove(4); check_count_cap(2,4);
}
s.remove(2); check_count_cap(1,4);
for (int i = 0; i < 10; i++) {
s. add(2); check_count_cap(2,4);
s.remove(2); check_count_cap(1,4);
}
}