123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179 |
- /*
- * Copyright 2017-present Facebook, Inc.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
- #include <folly/container/F14Set.h>
- #include <unordered_map>
- #include <folly/Conv.h>
- #include <folly/FBString.h>
- #include <folly/container/test/F14TestUtil.h>
- #include <folly/portability/GTest.h>
- template <template <typename, typename, typename, typename> class TSet>
- void testCustomSwap() {
- using std::swap;
- TSet<
- int,
- folly::f14::DefaultHasher<int>,
- folly::f14::DefaultKeyEqual<int>,
- folly::f14::SwapTrackingAlloc<int>>
- m0, m1;
- folly::f14::resetTracking();
- swap(m0, m1);
- EXPECT_EQ(
- 0, folly::f14::Tracked<0>::counts.dist(folly::f14::Counts{0, 0, 0, 0}));
- }
- TEST(F14Set, customSwap) {
- testCustomSwap<folly::F14ValueSet>();
- testCustomSwap<folly::F14NodeSet>();
- testCustomSwap<folly::F14VectorSet>();
- testCustomSwap<folly::F14FastSet>();
- }
- namespace {
- template <
- template <typename, typename, typename, typename> class TSet,
- typename K>
- void runAllocatedMemorySizeTest() {
- using namespace folly::f14;
- using namespace folly::f14::detail;
- using A = SwapTrackingAlloc<K>;
- resetTracking();
- {
- TSet<K, DefaultHasher<K>, DefaultKeyEqual<K>, A> s;
- // if F14 intrinsics are not available then we fall back to using
- // std::unordered_set underneath, but in that case the allocation
- // info is only best effort
- bool preciseAllocInfo = getF14IntrinsicsMode() != F14IntrinsicsMode::None;
- if (preciseAllocInfo) {
- EXPECT_EQ(testAllocatedMemorySize, 0);
- EXPECT_EQ(s.getAllocatedMemorySize(), 0);
- }
- auto emptySetAllocatedMemorySize = testAllocatedMemorySize;
- auto emptySetAllocatedBlockCount = testAllocatedBlockCount;
- for (size_t i = 0; i < 1000; ++i) {
- s.insert(folly::to<K>(i));
- s.erase(folly::to<K>(i / 10 + 2));
- if (preciseAllocInfo) {
- EXPECT_EQ(testAllocatedMemorySize, s.getAllocatedMemorySize());
- }
- EXPECT_GE(s.getAllocatedMemorySize(), sizeof(K) * s.size());
- std::size_t size = 0;
- std::size_t count = 0;
- s.visitAllocationClasses([&](std::size_t, std::size_t) mutable {});
- s.visitAllocationClasses([&](std::size_t bytes, std::size_t n) {
- size += bytes * n;
- count += n;
- });
- if (preciseAllocInfo) {
- EXPECT_EQ(testAllocatedMemorySize, size);
- EXPECT_EQ(testAllocatedBlockCount, count);
- }
- }
- s = decltype(s){};
- EXPECT_EQ(testAllocatedMemorySize, emptySetAllocatedMemorySize);
- EXPECT_EQ(testAllocatedBlockCount, emptySetAllocatedBlockCount);
- s.reserve(5);
- EXPECT_GT(testAllocatedMemorySize, 0);
- s = {};
- EXPECT_GT(testAllocatedMemorySize, 0);
- }
- EXPECT_EQ(testAllocatedMemorySize, 0);
- EXPECT_EQ(testAllocatedBlockCount, 0);
- }
- template <typename K>
- void runAllocatedMemorySizeTests() {
- runAllocatedMemorySizeTest<folly::F14ValueSet, K>();
- runAllocatedMemorySizeTest<folly::F14NodeSet, K>();
- runAllocatedMemorySizeTest<folly::F14VectorSet, K>();
- runAllocatedMemorySizeTest<folly::F14FastSet, K>();
- }
- } // namespace
- TEST(F14Set, getAllocatedMemorySize) {
- runAllocatedMemorySizeTests<bool>();
- runAllocatedMemorySizeTests<int>();
- runAllocatedMemorySizeTests<long>();
- runAllocatedMemorySizeTests<double>();
- runAllocatedMemorySizeTests<std::string>();
- runAllocatedMemorySizeTests<folly::fbstring>();
- }
- template <typename S>
- void runVisitContiguousRangesTest(int n) {
- S set;
- for (int i = 0; i < n; ++i) {
- set.insert(i);
- set.erase(i / 2);
- }
- std::unordered_map<uintptr_t, bool> visited;
- for (auto& entry : set) {
- visited[reinterpret_cast<uintptr_t>(&entry)] = false;
- }
- set.visitContiguousRanges([&](auto b, auto e) {
- for (auto i = b; i != e; ++i) {
- auto iter = visited.find(reinterpret_cast<uintptr_t>(i));
- ASSERT_TRUE(iter != visited.end());
- EXPECT_FALSE(iter->second);
- iter->second = true;
- }
- });
- // ensure no entries were skipped
- for (auto& e : visited) {
- EXPECT_TRUE(e.second);
- }
- }
- template <typename S>
- void runVisitContiguousRangesTest() {
- runVisitContiguousRangesTest<S>(0); // empty
- runVisitContiguousRangesTest<S>(5); // single chunk
- runVisitContiguousRangesTest<S>(1000); // many chunks
- }
- TEST(F14ValueSet, visitContiguousRanges) {
- runVisitContiguousRangesTest<folly::F14ValueSet<int>>();
- }
- TEST(F14NodeSet, visitContiguousRanges) {
- runVisitContiguousRangesTest<folly::F14NodeSet<int>>();
- }
- TEST(F14VectorSet, visitContiguousRanges) {
- runVisitContiguousRangesTest<folly::F14VectorSet<int>>();
- }
- TEST(F14FastSet, visitContiguousRanges) {
- runVisitContiguousRangesTest<folly::F14FastSet<int>>();
- }
- ///////////////////////////////////
- #if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
- ///////////////////////////////////
- #include <chrono>
- #include <random>
- #include <string>
- #include <unordered_set>
- #include <folly/Range.h>
- using namespace folly;
- using namespace folly::f14;
- using namespace folly::string_piece_literals;
- namespace {
- std::string s(char const* p) {
- return p;
- }
- } // namespace
- template <typename T>
- void runSimple() {
- T h;
- EXPECT_EQ(h.size(), 0);
- h.insert(s("abc"));
- EXPECT_TRUE(h.find(s("def")) == h.end());
- EXPECT_FALSE(h.find(s("abc")) == h.end());
- h.insert(s("ghi"));
- EXPECT_EQ(h.size(), 2);
- h.erase(h.find(s("abc")));
- EXPECT_EQ(h.size(), 1);
- T h2(std::move(h));
- EXPECT_EQ(h.size(), 0);
- EXPECT_TRUE(h.begin() == h.end());
- EXPECT_EQ(h2.size(), 1);
- EXPECT_TRUE(h2.find(s("abc")) == h2.end());
- EXPECT_EQ(*h2.begin(), s("ghi"));
- {
- auto i = h2.begin();
- EXPECT_FALSE(i == h2.end());
- ++i;
- EXPECT_TRUE(i == h2.end());
- }
- T h3;
- h3.insert(s("xxx"));
- h3.insert(s("yyy"));
- h3 = std::move(h2);
- EXPECT_EQ(h2.size(), 0);
- EXPECT_EQ(h3.size(), 1);
- EXPECT_TRUE(h3.find(s("xxx")) == h3.end());
- for (uint64_t i = 0; i < 1000; ++i) {
- h.insert(std::move(to<std::string>(i * i * i)));
- EXPECT_EQ(h.size(), i + 1);
- }
- {
- using std::swap;
- swap(h, h2);
- }
- for (uint64_t i = 0; i < 1000; ++i) {
- EXPECT_TRUE(h2.find(to<std::string>(i * i * i)) != h2.end());
- EXPECT_EQ(*h2.find(to<std::string>(i * i * i)), to<std::string>(i * i * i));
- EXPECT_TRUE(h2.find(to<std::string>(i * i * i + 2)) == h2.end());
- }
- T h4{h2};
- EXPECT_EQ(h2.size(), 1000);
- EXPECT_EQ(h4.size(), 1000);
- T h5{std::move(h2)};
- T h6;
- h6 = h4;
- T h7 = h4;
- T h8({s("abc"), s("def")});
- T h9({s("abd"), s("def")});
- EXPECT_EQ(h8.size(), 2);
- EXPECT_EQ(h8.count(s("abc")), 1);
- EXPECT_EQ(h8.count(s("xyz")), 0);
- EXPECT_TRUE(h7 != h8);
- EXPECT_TRUE(h8 != h9);
- h8 = std::move(h7);
- // h2 and h7 are moved from, h4, h5, h6, and h8 should be identical
- EXPECT_TRUE(h4 == h8);
- EXPECT_TRUE(h2.empty());
- EXPECT_TRUE(h7.empty());
- for (uint64_t i = 0; i < 1000; ++i) {
- auto k = to<std::string>(i * i * i);
- EXPECT_EQ(h4.count(k), 1);
- EXPECT_EQ(h5.count(k), 1);
- EXPECT_EQ(h6.count(k), 1);
- EXPECT_EQ(h8.count(k), 1);
- }
- h8.clear();
- h8.emplace(s("abc"));
- EXPECT_GT(h8.bucket_count(), 1);
- h8 = {};
- EXPECT_GT(h8.bucket_count(), 1);
- h9 = {s("abc"), s("def")};
- EXPECT_TRUE(h8.empty());
- EXPECT_EQ(h9.size(), 2);
- auto expectH8 = [&](T& ref) { EXPECT_EQ(&ref, &h8); };
- expectH8((h8 = h2));
- expectH8((h8 = std::move(h2)));
- expectH8((h8 = {}));
- F14TableStats::compute(h);
- F14TableStats::compute(h2);
- F14TableStats::compute(h3);
- F14TableStats::compute(h4);
- F14TableStats::compute(h5);
- F14TableStats::compute(h6);
- F14TableStats::compute(h7);
- F14TableStats::compute(h8);
- }
- template <typename T>
- void runRehash() {
- unsigned n = 10000;
- T h;
- for (unsigned i = 0; i < n; ++i) {
- h.insert(to<std::string>(i));
- }
- EXPECT_EQ(h.size(), n);
- F14TableStats::compute(h);
- }
- // T should be a set of uint64_t
- template <typename T>
- void runRandom() {
- using R = std::unordered_set<uint64_t>;
- std::mt19937_64 gen(0);
- std::uniform_int_distribution<> pctDist(0, 100);
- std::uniform_int_distribution<uint64_t> bitsBitsDist(1, 6);
- T t0;
- T t1;
- R r0;
- R r1;
- for (std::size_t reps = 0; reps < 100000; ++reps) {
- // discardBits will be from 0 to 62
- auto discardBits = (uint64_t{1} << bitsBitsDist(gen)) - 2;
- auto k = gen() >> discardBits;
- auto pct = pctDist(gen);
- EXPECT_EQ(t0.size(), r0.size());
- if (pct < 15) {
- // insert
- auto t = t0.insert(k);
- auto r = r0.insert(k);
- EXPECT_EQ(t.second, r.second);
- EXPECT_EQ(*t.first, *r.first);
- } else if (pct < 25) {
- // emplace
- auto t = t0.emplace(k);
- auto r = r0.emplace(k);
- EXPECT_EQ(t.second, r.second);
- EXPECT_EQ(*t.first, *r.first);
- } else if (pct < 30) {
- // bulk insert
- t0.insert(t1.begin(), t1.end());
- r0.insert(r1.begin(), r1.end());
- } else if (pct < 40) {
- // erase by key
- auto t = t0.erase(k);
- auto r = r0.erase(k);
- EXPECT_EQ(t, r);
- } else if (pct < 47) {
- // erase by iterator
- if (t0.size() > 0) {
- auto r = r0.find(k);
- if (r == r0.end()) {
- r = r0.begin();
- }
- k = *r;
- auto t = t0.find(k);
- t = t0.erase(t);
- if (t != t0.end()) {
- EXPECT_NE(*t, k);
- }
- r = r0.erase(r);
- if (r != r0.end()) {
- EXPECT_NE(*r, k);
- }
- }
- } else if (pct < 50) {
- // bulk erase
- if (t0.size() > 0) {
- auto r = r0.find(k);
- if (r == r0.end()) {
- r = r0.begin();
- }
- k = *r;
- auto t = t0.find(k);
- auto firstt = t;
- auto lastt = ++t;
- t = t0.erase(firstt, lastt);
- if (t != t0.end()) {
- EXPECT_NE(*t, k);
- }
- auto firstr = r;
- auto lastr = ++r;
- r = r0.erase(firstr, lastr);
- if (r != r0.end()) {
- EXPECT_NE(*r, k);
- }
- }
- } else if (pct < 58) {
- // find
- auto t = t0.find(k);
- auto r = r0.find(k);
- EXPECT_EQ((t == t0.end()), (r == r0.end()));
- if (t != t0.end() && r != r0.end()) {
- EXPECT_EQ(*t, *r);
- }
- EXPECT_EQ(t0.count(k), r0.count(k));
- } else if (pct < 60) {
- // equal_range
- auto t = t0.equal_range(k);
- auto r = r0.equal_range(k);
- EXPECT_EQ((t.first == t.second), (r.first == r.second));
- if (t.first != t.second && r.first != r.second) {
- EXPECT_EQ(*t.first, *r.first);
- t.first++;
- r.first++;
- EXPECT_TRUE(t.first == t.second);
- EXPECT_TRUE(r.first == r.second);
- }
- } else if (pct < 65) {
- // iterate
- uint64_t t = 0;
- for (auto& e : t0) {
- t += e + 1000;
- }
- uint64_t r = 0;
- for (auto& e : r0) {
- r += e + 1000;
- }
- EXPECT_EQ(t, r);
- } else if (pct < 69) {
- // swap
- using std::swap;
- swap(t0, t1);
- swap(r0, r1);
- } else if (pct < 70) {
- // swap
- t0.swap(t1);
- r0.swap(r1);
- } else if (pct < 72) {
- // default construct
- t0.~T();
- new (&t0) T();
- r0.~R();
- new (&r0) R();
- } else if (pct < 74) {
- // default construct with capacity
- std::size_t capacity = k & 0xffff;
- t0.~T();
- new (&t0) T(capacity);
- r0.~R();
- new (&r0) R(capacity);
- } else if (pct < 80) {
- // bulk iterator construct
- t0.~T();
- new (&t0) T(r1.begin(), r1.end());
- r0.~R();
- new (&r0) R(r1.begin(), r1.end());
- } else if (pct < 82) {
- // initializer list construct
- auto k2 = gen() >> discardBits;
- t0.~T();
- new (&t0) T({k, k, k2});
- r0.~R();
- new (&r0) R({k, k, k2});
- } else if (pct < 88) {
- // copy construct
- t0.~T();
- new (&t0) T(t1);
- r0.~R();
- new (&r0) R(r1);
- } else if (pct < 90) {
- // move construct
- t0.~T();
- new (&t0) T(std::move(t1));
- r0.~R();
- new (&r0) R(std::move(r1));
- } else if (pct < 94) {
- // copy assign
- t0 = t1;
- r0 = r1;
- } else if (pct < 96) {
- // move assign
- t0 = std::move(t1);
- r0 = std::move(r1);
- } else if (pct < 98) {
- // operator==
- EXPECT_EQ((t0 == t1), (r0 == r1));
- } else if (pct < 99) {
- // clear
- t0.computeStats();
- t0.clear();
- r0.clear();
- } else if (pct < 100) {
- // reserve
- auto scale = std::uniform_int_distribution<>(0, 8)(gen);
- auto delta = std::uniform_int_distribution<>(-2, 2)(gen);
- std::ptrdiff_t target = (t0.size() * scale) / 4 + delta;
- if (target >= 0) {
- t0.reserve(static_cast<std::size_t>(target));
- r0.reserve(static_cast<std::size_t>(target));
- }
- }
- }
- }
- TEST(F14ValueSet, simple) {
- runSimple<F14ValueSet<std::string>>();
- }
- TEST(F14NodeSet, simple) {
- runSimple<F14NodeSet<std::string>>();
- }
- TEST(F14VectorSet, simple) {
- runSimple<F14VectorSet<std::string>>();
- }
- TEST(F14FastSet, simple) {
- // F14FastSet inherits from a conditional typedef. Verify it compiles.
- runRandom<F14FastSet<uint64_t>>();
- runSimple<F14FastSet<std::string>>();
- }
- TEST(F14Set, ContainerSize) {
- {
- folly::F14ValueSet<int> set;
- set.insert(10);
- EXPECT_EQ(sizeof(set), 4 * sizeof(void*));
- if (alignof(folly::max_align_t) == 16) {
- // chunks will be allocated as 2 max_align_t-s
- EXPECT_EQ(set.getAllocatedMemorySize(), 32);
- } else {
- // chunks will be allocated using aligned_malloc with the true size
- EXPECT_EQ(set.getAllocatedMemorySize(), 24);
- }
- }
- {
- folly::F14NodeSet<int> set;
- set.insert(10);
- EXPECT_EQ(sizeof(set), 4 * sizeof(void*));
- if (alignof(folly::max_align_t) == 16) {
- // chunks will be allocated as 2 max_align_t-s
- EXPECT_EQ(set.getAllocatedMemorySize(), 36);
- } else {
- // chunks will be allocated using aligned_malloc with the true size
- EXPECT_EQ(set.getAllocatedMemorySize(), 20 + 2 * sizeof(void*));
- }
- }
- {
- folly::F14VectorSet<int> set;
- set.insert(10);
- EXPECT_EQ(sizeof(set), 8 + 2 * sizeof(void*));
- EXPECT_EQ(set.getAllocatedMemorySize(), 32);
- }
- }
- TEST(F14VectorMap, reverse_iterator) {
- using TSet = F14VectorSet<uint64_t>;
- auto populate = [](TSet& h, uint64_t lo, uint64_t hi) {
- for (auto i = lo; i < hi; ++i) {
- h.insert(i);
- }
- };
- auto verify = [](TSet const& h, uint64_t lo, uint64_t hi) {
- auto loIt = h.find(lo);
- EXPECT_NE(h.end(), loIt);
- uint64_t val = lo;
- for (auto rit = h.riter(loIt); rit != h.rend(); ++rit) {
- EXPECT_EQ(val, *rit);
- TSet::const_iterator it = h.iter(rit);
- EXPECT_EQ(val, *it);
- val++;
- }
- EXPECT_EQ(hi, val);
- };
- TSet h;
- size_t prevSize = 0;
- size_t newSize = 1;
- // verify iteration order across rehashes, copies, and moves
- while (newSize < 10'000) {
- populate(h, prevSize, newSize);
- verify(h, 0, newSize);
- verify(h, newSize / 2, newSize);
- TSet h2{h};
- verify(h2, 0, newSize);
- h = std::move(h2);
- verify(h, 0, newSize);
- prevSize = newSize;
- newSize *= 10;
- }
- }
- TEST(F14ValueSet, rehash) {
- runRehash<F14ValueSet<std::string>>();
- }
- TEST(F14NodeSet, rehash) {
- runRehash<F14NodeSet<std::string>>();
- }
- TEST(F14VectorSet, rehash) {
- runRehash<F14VectorSet<std::string>>();
- }
- TEST(F14ValueSet, random) {
- runRandom<F14ValueSet<uint64_t>>();
- }
- TEST(F14NodeSet, random) {
- runRandom<F14NodeSet<uint64_t>>();
- }
- TEST(F14VectorSet, random) {
- runRandom<F14VectorSet<uint64_t>>();
- }
- TEST(F14ValueSet, grow_stats) {
- F14ValueSet<uint64_t> h;
- for (unsigned i = 1; i <= 3072; ++i) {
- h.insert(i);
- }
- // F14ValueSet just before rehash
- F14TableStats::compute(h);
- h.insert(0);
- // F14ValueSet just after rehash
- F14TableStats::compute(h);
- }
- TEST(F14ValueSet, steady_state_stats) {
- // 10k keys, 14% probability of insert, 90% chance of erase, so the
- // table should converge to 1400 size without triggering the rehash
- // that would occur at 1536.
- F14ValueSet<uint64_t> h;
- std::mt19937 gen(0);
- std::uniform_int_distribution<> dist(0, 10000);
- for (std::size_t i = 0; i < 100000; ++i) {
- auto key = dist(gen);
- if (dist(gen) < 1400) {
- h.insert(key);
- } else {
- h.erase(key);
- }
- if (((i + 1) % 10000) == 0) {
- auto stats = F14TableStats::compute(h);
- // Verify that average miss probe length is bounded despite continued
- // erase + reuse. p99 of the average across 10M random steps is 4.69,
- // average is 2.96.
- EXPECT_LT(f14::expectedProbe(stats.missProbeLengthHisto), 10.0);
- }
- }
- // F14ValueSet at steady state
- F14TableStats::compute(h);
- }
- // S should be a set of Tracked<0>. F should take a set
- // and a key_type const& or key_type&& and cause it to be inserted
- template <typename S, typename F>
- void runInsertCases(std::string const& /* name */, F const& insertFunc) {
- static_assert(std::is_same<typename S::value_type, Tracked<0>>::value, "");
- {
- typename S::value_type k{0};
- S s;
- resetTracking();
- insertFunc(s, k);
- // fresh key, value_type const& ->
- // copy is expected
- EXPECT_EQ(Tracked<0>::counts.dist(Counts{1, 0, 0, 0}), 0);
- }
- {
- typename S::value_type k{0};
- S s;
- resetTracking();
- insertFunc(s, std::move(k));
- // fresh key, value_type&& ->
- // move is expected
- EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 1, 0, 0}), 0);
- }
- }
- struct DoInsert {
- template <typename M, typename P>
- void operator()(M& m, P&& p) const {
- m.insert(std::forward<P>(p));
- }
- };
- struct DoEmplace1 {
- template <typename M, typename P>
- void operator()(M& m, P&& p) const {
- m.emplace(std::forward<P>(p));
- }
- };
- template <typename S>
- void runInsertAndEmplace() {
- {
- typename S::value_type k1{0};
- typename S::value_type k2{0};
- S s;
- resetTracking();
- EXPECT_TRUE(s.insert(k1).second);
- // copy is expected on successful insert
- EXPECT_EQ(Tracked<0>::counts.dist(Counts{1, 0, 0, 0}), 0);
- resetTracking();
- EXPECT_FALSE(s.insert(k2).second);
- // no copies or moves on failing insert
- EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 0, 0, 0}), 0);
- }
- {
- typename S::value_type k1{0};
- typename S::value_type k2{0};
- S s;
- resetTracking();
- EXPECT_TRUE(s.insert(std::move(k1)).second);
- // move is expected on successful insert
- EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 1, 0, 0}), 0);
- resetTracking();
- EXPECT_FALSE(s.insert(std::move(k2)).second);
- // no copies or moves on failing insert
- EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 0, 0, 0}), 0);
- }
- {
- typename S::value_type k1{0};
- typename S::value_type k2{0};
- uint64_t k3 = 0;
- S s;
- resetTracking();
- EXPECT_TRUE(s.emplace(k1).second);
- // copy is expected on successful emplace
- EXPECT_EQ(Tracked<0>::counts.dist(Counts{1, 0, 0, 0}), 0);
- resetTracking();
- EXPECT_FALSE(s.emplace(k2).second);
- // no copies or moves on failing emplace with value_type
- EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 0, 0, 0}), 0);
- resetTracking();
- EXPECT_FALSE(s.emplace(k3).second);
- // copy convert expected for failing emplace with wrong type
- EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 0, 1, 0}), 0);
- s.clear();
- resetTracking();
- EXPECT_TRUE(s.emplace(k3).second);
- // copy convert + move expected for successful emplace with wrong type
- EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 1, 1, 0}), 0);
- }
- {
- typename S::value_type k1{0};
- typename S::value_type k2{0};
- uint64_t k3 = 0;
- S s;
- resetTracking();
- EXPECT_TRUE(s.emplace(std::move(k1)).second);
- // move is expected on successful emplace
- EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 1, 0, 0}), 0);
- resetTracking();
- EXPECT_FALSE(s.emplace(std::move(k2)).second);
- // no copies or moves on failing emplace with value_type
- EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 0, 0, 0}), 0);
- resetTracking();
- EXPECT_FALSE(s.emplace(std::move(k3)).second);
- // move convert expected for failing emplace with wrong type
- EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 0, 0, 1}), 0);
- s.clear();
- resetTracking();
- EXPECT_TRUE(s.emplace(std::move(k3)).second);
- // move convert + move expected for successful emplace with wrong type
- EXPECT_EQ(Tracked<0>::counts.dist(Counts{0, 1, 0, 1}), 0);
- }
- // Calling the default pair constructor via emplace is valid, but not
- // very useful in real life. Verify that it works.
- S s;
- typename S::value_type k;
- EXPECT_EQ(s.count(k), 0);
- s.emplace();
- EXPECT_EQ(s.count(k), 1);
- s.emplace();
- EXPECT_EQ(s.count(k), 1);
- }
- TEST(F14ValueSet, destructuring) {
- runInsertAndEmplace<F14ValueSet<Tracked<0>>>();
- }
- TEST(F14NodeSet, destructuring) {
- runInsertAndEmplace<F14NodeSet<Tracked<0>>>();
- }
- TEST(F14VectorSet, destructuring) {
- runInsertAndEmplace<F14VectorSet<Tracked<0>>>();
- }
- TEST(F14ValueSet, maxSize) {
- F14ValueSet<int> s;
- EXPECT_EQ(
- s.max_size(), std::numeric_limits<std::size_t>::max() / sizeof(int));
- }
- TEST(F14NodeSet, maxSize) {
- F14NodeSet<int> s;
- EXPECT_EQ(
- s.max_size(), std::numeric_limits<std::size_t>::max() / sizeof(int));
- }
- TEST(F14VectorSet, maxSize) {
- F14VectorSet<int> s;
- EXPECT_EQ(
- s.max_size(),
- std::min(
- std::size_t{std::numeric_limits<uint32_t>::max()},
- std::numeric_limits<std::size_t>::max() / sizeof(int)));
- }
- template <typename S>
- void runMoveOnlyTest() {
- S t0;
- t0.emplace(10);
- t0.insert(20);
- S t1{std::move(t0)};
- EXPECT_TRUE(t0.empty());
- S t2;
- EXPECT_TRUE(t2.empty());
- t2 = std::move(t1);
- EXPECT_EQ(t2.size(), 2);
- }
- TEST(F14ValueSet, moveOnly) {
- runMoveOnlyTest<F14ValueSet<f14::MoveOnlyTestInt>>();
- }
- TEST(F14NodeSet, moveOnly) {
- runMoveOnlyTest<F14NodeSet<f14::MoveOnlyTestInt>>();
- }
- TEST(F14VectorSet, moveOnly) {
- runMoveOnlyTest<F14VectorSet<f14::MoveOnlyTestInt>>();
- }
- TEST(F14FastSet, moveOnly) {
- runMoveOnlyTest<F14FastSet<f14::MoveOnlyTestInt>>();
- }
- template <typename S>
- void runEraseIntoTest() {
- S t0;
- S t1;
- auto insertIntoT0 = [&t0](auto&& value) {
- EXPECT_FALSE(value.destroyed);
- t0.emplace(std::move(value));
- };
- auto insertIntoT0Mut = [&](typename S::value_type&& value) mutable {
- insertIntoT0(std::move(value));
- };
- t0.insert(10);
- t1.insert(20);
- t1.eraseInto(t1.begin(), insertIntoT0);
- EXPECT_TRUE(t1.empty());
- EXPECT_EQ(t0.size(), 2);
- EXPECT_TRUE(t0.find(10) != t0.end());
- EXPECT_TRUE(t0.find(20) != t0.end());
- t1.insert(20);
- t1.insert(30);
- t1.insert(40);
- t1.eraseInto(t1.begin(), t1.end(), insertIntoT0Mut);
- EXPECT_TRUE(t1.empty());
- EXPECT_EQ(t0.size(), 4);
- EXPECT_TRUE(t0.find(30) != t0.end());
- EXPECT_TRUE(t0.find(40) != t0.end());
- t1.insert(50);
- size_t erased = t1.eraseInto(*t1.find(50), insertIntoT0);
- EXPECT_EQ(erased, 1);
- EXPECT_TRUE(t1.empty());
- EXPECT_EQ(t0.size(), 5);
- EXPECT_TRUE(t0.find(50) != t0.end());
- typename S::value_type key{60};
- erased = t1.eraseInto(key, insertIntoT0Mut);
- EXPECT_EQ(erased, 0);
- EXPECT_EQ(t0.size(), 5);
- }
- TEST(F14ValueSet, eraseInto) {
- runEraseIntoTest<F14ValueSet<f14::MoveOnlyTestInt>>();
- }
- TEST(F14NodeSet, eraseInto) {
- runEraseIntoTest<F14NodeSet<f14::MoveOnlyTestInt>>();
- }
- TEST(F14VectorSet, eraseInto) {
- runEraseIntoTest<F14VectorSet<f14::MoveOnlyTestInt>>();
- }
- TEST(F14FastSet, eraseInto) {
- runEraseIntoTest<F14FastSet<f14::MoveOnlyTestInt>>();
- }
- TEST(F14ValueSet, heterogeneous) {
- // note: std::string is implicitly convertible to but not from StringPiece
- using Hasher = folly::transparent<folly::hasher<folly::StringPiece>>;
- using KeyEqual = folly::transparent<std::equal_to<folly::StringPiece>>;
- constexpr auto hello = "hello"_sp;
- constexpr auto buddy = "buddy"_sp;
- constexpr auto world = "world"_sp;
- F14ValueSet<std::string, Hasher, KeyEqual> set;
- set.emplace(hello);
- set.emplace(world);
- auto checks = [hello, buddy](auto& ref) {
- // count
- EXPECT_EQ(0, ref.count(buddy));
- EXPECT_EQ(1, ref.count(hello));
- // find
- EXPECT_TRUE(ref.end() == ref.find(buddy));
- EXPECT_EQ(hello, *ref.find(hello));
- // prehash + find
- EXPECT_TRUE(ref.end() == ref.find(ref.prehash(buddy), buddy));
- EXPECT_EQ(hello, *ref.find(ref.prehash(hello), hello));
- // equal_range
- EXPECT_TRUE(std::make_pair(ref.end(), ref.end()) == ref.equal_range(buddy));
- EXPECT_TRUE(
- std::make_pair(ref.find(hello), ++ref.find(hello)) ==
- ref.equal_range(hello));
- };
- checks(set);
- checks(folly::as_const(set));
- }
- template <typename S>
- void runStatefulFunctorTest() {
- bool ranHasher = false;
- bool ranEqual = false;
- bool ranAlloc = false;
- bool ranDealloc = false;
- auto hasher = [&](int x) {
- ranHasher = true;
- return x;
- };
- auto equal = [&](int x, int y) {
- ranEqual = true;
- return x == y;
- };
- auto alloc = [&](std::size_t n) {
- ranAlloc = true;
- return std::malloc(n);
- };
- auto dealloc = [&](void* p, std::size_t) {
- ranDealloc = true;
- std::free(p);
- };
- {
- S set(0, hasher, equal, {alloc, dealloc});
- set.insert(10);
- set.insert(10);
- EXPECT_EQ(set.size(), 1);
- S set2(set);
- S set3(std::move(set));
- set = set2;
- set2.clear();
- set2 = std::move(set3);
- }
- EXPECT_TRUE(ranHasher);
- EXPECT_TRUE(ranEqual);
- EXPECT_TRUE(ranAlloc);
- EXPECT_TRUE(ranDealloc);
- }
- TEST(F14ValueSet, statefulFunctors) {
- runStatefulFunctorTest<F14ValueSet<
- int,
- GenericHasher<int>,
- GenericEqual<int>,
- GenericAlloc<int>>>();
- }
- TEST(F14NodeSet, statefulFunctors) {
- runStatefulFunctorTest<F14NodeSet<
- int,
- GenericHasher<int>,
- GenericEqual<int>,
- GenericAlloc<int>>>();
- }
- TEST(F14VectorSet, statefulFunctors) {
- runStatefulFunctorTest<F14VectorSet<
- int,
- GenericHasher<int>,
- GenericEqual<int>,
- GenericAlloc<int>>>();
- }
- TEST(F14FastSet, statefulFunctors) {
- runStatefulFunctorTest<F14FastSet<
- int,
- GenericHasher<int>,
- GenericEqual<int>,
- GenericAlloc<int>>>();
- }
- template <typename S>
- void runHeterogeneousInsertTest() {
- S set;
- resetTracking();
- EXPECT_EQ(set.count(10), 0);
- EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
- << Tracked<1>::counts;
- resetTracking();
- set.insert(10);
- EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 1}), 0)
- << Tracked<1>::counts;
- resetTracking();
- int k = 10;
- std::vector<int> v({10});
- set.insert(10);
- set.insert(k);
- set.insert(v.begin(), v.end());
- set.insert(
- std::make_move_iterator(v.begin()), std::make_move_iterator(v.end()));
- set.emplace(10);
- set.emplace(k);
- EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
- << Tracked<1>::counts;
- resetTracking();
- set.erase(20);
- EXPECT_EQ(set.size(), 1);
- EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
- << Tracked<1>::counts;
- resetTracking();
- set.erase(10);
- EXPECT_EQ(set.size(), 0);
- EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
- << Tracked<1>::counts;
- set.insert(10);
- resetTracking();
- set.eraseInto(10, [](auto&&) {});
- EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
- << Tracked<1>::counts;
- }
- template <typename S>
- void runHeterogeneousInsertStringTest() {
- S set;
- StringPiece k{"foo"};
- std::vector<StringPiece> v{k};
- set.insert(k);
- set.insert("foo");
- set.insert(StringPiece{"foo"});
- set.insert(v.begin(), v.end());
- set.insert(
- std::make_move_iterator(v.begin()), std::make_move_iterator(v.end()));
- set.emplace();
- set.emplace(k);
- set.emplace("foo");
- set.emplace(StringPiece("foo"));
- set.erase("");
- set.erase(k);
- set.erase(StringPiece{"foo"});
- EXPECT_TRUE(set.empty());
- }
- TEST(F14ValueSet, heterogeneousInsert) {
- runHeterogeneousInsertTest<F14ValueSet<
- Tracked<1>,
- TransparentTrackedHash<1>,
- TransparentTrackedEqual<1>>>();
- runHeterogeneousInsertStringTest<F14ValueSet<
- std::string,
- transparent<hasher<StringPiece>>,
- transparent<DefaultKeyEqual<StringPiece>>>>();
- }
- TEST(F14NodeSet, heterogeneousInsert) {
- runHeterogeneousInsertTest<F14NodeSet<
- Tracked<1>,
- TransparentTrackedHash<1>,
- TransparentTrackedEqual<1>>>();
- runHeterogeneousInsertStringTest<F14NodeSet<
- std::string,
- transparent<hasher<StringPiece>>,
- transparent<DefaultKeyEqual<StringPiece>>>>();
- }
- TEST(F14VectorSet, heterogeneousInsert) {
- runHeterogeneousInsertTest<F14VectorSet<
- Tracked<1>,
- TransparentTrackedHash<1>,
- TransparentTrackedEqual<1>>>();
- runHeterogeneousInsertStringTest<F14VectorSet<
- std::string,
- transparent<hasher<StringPiece>>,
- transparent<DefaultKeyEqual<StringPiece>>>>();
- }
- TEST(F14FastSet, heterogeneousInsert) {
- runHeterogeneousInsertTest<F14FastSet<
- Tracked<1>,
- TransparentTrackedHash<1>,
- TransparentTrackedEqual<1>>>();
- runHeterogeneousInsertStringTest<F14FastSet<
- std::string,
- transparent<hasher<StringPiece>>,
- transparent<DefaultKeyEqual<StringPiece>>>>();
- }
- namespace {
- struct CharArrayHasher {
- template <std::size_t N>
- std::size_t operator()(std::array<char, N> const& value) const {
- return folly::Hash{}(
- StringPiece{value.data(), &value.data()[value.size()]});
- }
- };
- template <
- template <typename, typename, typename, typename> class S,
- std::size_t N>
- struct RunAllValueSizeTests {
- void operator()() const {
- using Key = std::array<char, N>;
- static_assert(sizeof(Key) == N, "");
- S<Key, CharArrayHasher, std::equal_to<Key>, std::allocator<Key>> set;
- for (int i = 0; i < 100; ++i) {
- Key key{{static_cast<char>(i)}};
- set.insert(key);
- }
- while (!set.empty()) {
- set.erase(set.begin());
- }
- RunAllValueSizeTests<S, N - 1>{}();
- }
- };
- template <template <typename, typename, typename, typename> class S>
- struct RunAllValueSizeTests<S, 0> {
- void operator()() const {}
- };
- } // namespace
- TEST(F14ValueSet, valueSize) {
- RunAllValueSizeTests<F14ValueSet, 32>{}();
- }
- ///////////////////////////////////
- #endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
- ///////////////////////////////////
|