1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501 |
- /*
- * 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/F14Map.h>
- #include <algorithm>
- #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, typename>
- class TMap>
- void testCustomSwap() {
- using std::swap;
- TMap<
- int,
- int,
- folly::f14::DefaultHasher<int>,
- folly::f14::DefaultKeyEqual<int>,
- folly::f14::SwapTrackingAlloc<std::pair<int const, 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(F14Map, customSwap) {
- testCustomSwap<folly::F14ValueMap>();
- testCustomSwap<folly::F14NodeMap>();
- testCustomSwap<folly::F14VectorMap>();
- testCustomSwap<folly::F14FastMap>();
- }
- namespace {
- template <
- template <typename, typename, typename, typename, typename> class TMap,
- typename K,
- typename V>
- void runAllocatedMemorySizeTest() {
- using namespace folly::f14;
- using namespace folly::f14::detail;
- using A = SwapTrackingAlloc<std::pair<const K, V>>;
- resetTracking();
- {
- TMap<K, V, DefaultHasher<K>, DefaultKeyEqual<K>, A> m;
- // if F14 intrinsics are not available then we fall back to using
- // std::unordered_map 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(m.getAllocatedMemorySize(), 0);
- }
- auto emptyMapAllocatedMemorySize = testAllocatedMemorySize;
- auto emptyMapAllocatedBlockCount = testAllocatedBlockCount;
- for (size_t i = 0; i < 1000; ++i) {
- m.insert(std::make_pair(folly::to<K>(i), V{}));
- m.erase(folly::to<K>(i / 10 + 2));
- if (preciseAllocInfo) {
- EXPECT_EQ(testAllocatedMemorySize, m.getAllocatedMemorySize());
- }
- EXPECT_GE(m.getAllocatedMemorySize(), sizeof(std::pair<K, V>) * m.size());
- std::size_t size = 0;
- std::size_t count = 0;
- m.visitAllocationClasses([&](std::size_t, std::size_t) mutable {});
- m.visitAllocationClasses([&](std::size_t bytes, std::size_t n) {
- size += bytes * n;
- count += n;
- });
- if (preciseAllocInfo) {
- EXPECT_EQ(testAllocatedMemorySize, size);
- EXPECT_EQ(testAllocatedBlockCount, count);
- }
- }
- m = decltype(m){};
- EXPECT_EQ(testAllocatedMemorySize, emptyMapAllocatedMemorySize);
- EXPECT_EQ(testAllocatedBlockCount, emptyMapAllocatedBlockCount);
- m.reserve(5);
- EXPECT_GT(testAllocatedMemorySize, 0);
- m = {};
- EXPECT_GT(testAllocatedMemorySize, 0);
- }
- EXPECT_EQ(testAllocatedMemorySize, 0);
- EXPECT_EQ(testAllocatedBlockCount, 0);
- }
- template <typename K, typename V>
- void runAllocatedMemorySizeTests() {
- runAllocatedMemorySizeTest<folly::F14ValueMap, K, V>();
- runAllocatedMemorySizeTest<folly::F14NodeMap, K, V>();
- runAllocatedMemorySizeTest<folly::F14VectorMap, K, V>();
- runAllocatedMemorySizeTest<folly::F14FastMap, K, V>();
- }
- } // namespace
- TEST(F14Map, getAllocatedMemorySize) {
- runAllocatedMemorySizeTests<bool, bool>();
- runAllocatedMemorySizeTests<int, int>();
- runAllocatedMemorySizeTests<bool, std::string>();
- runAllocatedMemorySizeTests<double, std::string>();
- runAllocatedMemorySizeTests<std::string, int>();
- runAllocatedMemorySizeTests<std::string, std::string>();
- runAllocatedMemorySizeTests<folly::fbstring, long>();
- }
- template <typename M>
- void runVisitContiguousRangesTest(int n) {
- M map;
- for (int i = 0; i < n; ++i) {
- map[i] = i;
- map.erase(i / 2);
- }
- std::unordered_map<uintptr_t, bool> visited;
- for (auto& entry : map) {
- visited[reinterpret_cast<uintptr_t>(&entry)] = false;
- }
- map.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 M>
- void runVisitContiguousRangesTest() {
- runVisitContiguousRangesTest<M>(0); // empty
- runVisitContiguousRangesTest<M>(5); // single chunk
- runVisitContiguousRangesTest<M>(1000); // many chunks
- }
- TEST(F14ValueMap, visitContiguousRanges) {
- runVisitContiguousRangesTest<folly::F14ValueMap<int, int>>();
- }
- TEST(F14NodeMap, visitContiguousRanges) {
- runVisitContiguousRangesTest<folly::F14NodeMap<int, int>>();
- }
- TEST(F14VectorMap, visitContiguousRanges) {
- runVisitContiguousRangesTest<folly::F14VectorMap<int, int>>();
- }
- TEST(F14FastMap, visitContiguousRanges) {
- runVisitContiguousRangesTest<folly::F14FastMap<int, int>>();
- }
- ///////////////////////////////////
- #if FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
- ///////////////////////////////////
- #include <chrono>
- #include <random>
- #include <string>
- #include <typeinfo>
- #include <unordered_map>
- #include <folly/Range.h>
- #include <folly/hash/Hash.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(std::make_pair(s("abc"), s("ABC")));
- EXPECT_TRUE(h.find(s("def")) == h.end());
- EXPECT_FALSE(h.find(s("abc")) == h.end());
- EXPECT_EQ(h[s("abc")], s("ABC"));
- h[s("ghi")] = 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()->first, s("ghi"));
- {
- auto i = h2.begin();
- EXPECT_FALSE(i == h2.end());
- ++i;
- EXPECT_TRUE(i == h2.end());
- }
- T h3;
- h3.try_emplace(s("xxx"));
- h3.insert_or_assign(s("yyy"), 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[to<std::string>(i * i * i)] = s("x");
- 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))->first, 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("ABC")}, {s("def"), s("DEF")}});
- T h9({{s("abc"), s("ABD")}, {s("def"), 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);
- }
- EXPECT_TRUE(h2 == h7);
- EXPECT_TRUE(h4 != h7);
- EXPECT_EQ(h3.at(s("ghi")), s("GHI"));
- EXPECT_THROW(h3.at(s("abc")), std::out_of_range);
- h8.clear();
- h8.emplace(s("abc"), s("ABC"));
- EXPECT_GE(h8.bucket_count(), 1);
- h8 = {};
- EXPECT_GE(h8.bucket_count(), 1);
- h9 = {{s("abc"), s("ABD")}, {s("def"), 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);
- F14TableStats::compute(h9);
- }
- template <typename T>
- void runRehash() {
- unsigned n = 10000;
- T h;
- auto b = h.bucket_count();
- for (unsigned i = 0; i < n; ++i) {
- h.insert(std::make_pair(to<std::string>(i), s("")));
- if (b != h.bucket_count()) {
- F14TableStats::compute(h);
- b = h.bucket_count();
- }
- }
- EXPECT_EQ(h.size(), n);
- F14TableStats::compute(h);
- }
- // T should be a map from uint64_t to Tracked<1> that uses SwapTrackingAlloc
- template <typename T>
- void runRandom() {
- using R = std::unordered_map<uint64_t, Tracked<2>>;
- resetTracking();
- 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;
- std::size_t rollbacks = 0;
- std::size_t resizingSmallRollbacks = 0;
- std::size_t resizingLargeRollbacks = 0;
- for (std::size_t reps = 0; reps < 100000 || rollbacks < 10 ||
- resizingSmallRollbacks < 1 || resizingLargeRollbacks < 1;
- ++reps) {
- if (pctDist(gen) < 20) {
- // 10% chance allocator will fail after 0 to 3 more allocations
- limitTestAllocations(gen() & 3);
- } else {
- unlimitTestAllocations();
- }
- bool leakCheckOnly = false;
- // discardBits will be from 0 to 62
- auto discardBits = (uint64_t{1} << bitsBitsDist(gen)) - 2;
- auto k = gen() >> discardBits;
- auto v = gen();
- auto pct = pctDist(gen);
- try {
- EXPECT_EQ(t0.empty(), r0.empty());
- EXPECT_EQ(t0.size(), r0.size());
- EXPECT_EQ(2, Tracked<0>::counts.liveCount());
- EXPECT_EQ(t0.size() + t1.size(), Tracked<1>::counts.liveCount());
- EXPECT_EQ(r0.size() + r1.size(), Tracked<2>::counts.liveCount());
- if (pct < 15) {
- // insert
- auto t = t0.insert(std::make_pair(k, v));
- auto r = r0.insert(std::make_pair(k, v));
- EXPECT_EQ(t.first->first, r.first->first);
- EXPECT_EQ(t.first->second.val_, r.first->second.val_);
- EXPECT_EQ(t.second, r.second);
- } else if (pct < 25) {
- // emplace
- auto t = t0.emplace(k, v);
- auto r = r0.emplace(k, v);
- EXPECT_EQ(t.first->first, r.first->first);
- EXPECT_EQ(t.first->second.val_, r.first->second.val_);
- EXPECT_EQ(t.second, r.second);
- } else if (pct < 30) {
- // bulk insert
- leakCheckOnly = true;
- 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->first;
- auto t = t0.find(k);
- t = t0.erase(t);
- if (t != t0.end()) {
- EXPECT_NE(t->first, k);
- }
- r = r0.erase(r);
- if (r != r0.end()) {
- EXPECT_NE(r->first, 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->first;
- auto t = t0.find(k);
- auto firstt = t;
- auto lastt = ++t;
- t = t0.erase(firstt, lastt);
- if (t != t0.end()) {
- EXPECT_NE(t->first, k);
- }
- auto firstr = r;
- auto lastr = ++r;
- r = r0.erase(firstr, lastr);
- if (r != r0.end()) {
- EXPECT_NE(r->first, 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->first, r->first);
- EXPECT_EQ(t->second.val_, r->second.val_);
- }
- 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->first, r.first->first);
- EXPECT_EQ(t.first->second.val_, r.first->second.val_);
- 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.first * 37 + e.second.val_ + 1000;
- }
- uint64_t r = 0;
- for (auto& e : r0) {
- r += e.first * 37 + e.second.val_ + 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;
- T t(capacity);
- t0 = std::move(t);
- R r(capacity);
- r0 = std::move(r);
- } else if (pct < 80) {
- // bulk iterator construct
- t0 = T{t1.begin(), t1.end()};
- r0 = R{r1.begin(), r1.end()};
- } else if (pct < 82) {
- // initializer list construct
- auto k2 = gen() >> discardBits;
- auto v2 = gen();
- T t({{k, v}, {k2, v}, {k2, v2}});
- t0 = std::move(t);
- R r({{k, v}, {k2, v}, {k2, v2}});
- r0 = std::move(r);
- } else if (pct < 85) {
- // copy construct
- T t(t1);
- t0 = std::move(t);
- R r(r1);
- r0 = std::move(r);
- } else if (pct < 88) {
- // copy construct
- T t(t1, t1.get_allocator());
- t0 = std::move(t);
- R r(r1, r1.get_allocator());
- r0 = std::move(r);
- } else if (pct < 89) {
- // move construct
- t0.~T();
- new (&t0) T(std::move(t1));
- r0.~R();
- new (&r0) R(std::move(r1));
- } else if (pct < 90) {
- // move construct
- t0.~T();
- auto ta = t1.get_allocator();
- new (&t0) T(std::move(t1), ta);
- r0.~R();
- auto ra = r1.get_allocator();
- new (&r0) R(std::move(r1), ra);
- } else if (pct < 94) {
- // copy assign
- leakCheckOnly = true;
- 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
- F14TableStats::compute(t0);
- 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));
- }
- }
- } catch (std::bad_alloc const&) {
- ++rollbacks;
- F14TableStats::compute(t0);
- if (leakCheckOnly) {
- unlimitTestAllocations();
- t0.clear();
- for (auto&& kv : r0) {
- t0[kv.first] = kv.second.val_;
- }
- }
- if (t0.bucket_count() == t0.size() && t0.size() > 0) {
- if (t0.size() < 10) {
- ++resizingSmallRollbacks;
- } else {
- ++resizingLargeRollbacks;
- }
- }
- assert(t0.size() == r0.size());
- for (auto&& kv : r0) {
- auto t = t0.find(kv.first);
- EXPECT_TRUE(
- t != t0.end() && t->first == kv.first &&
- t->second.val_ == kv.second.val_);
- }
- }
- }
- }
- EXPECT_EQ(testAllocatedMemorySize, 0);
- }
- template <typename T>
- void runPrehash() {
- T h;
- EXPECT_EQ(h.size(), 0);
- h.insert(std::make_pair(s("abc"), s("ABC")));
- EXPECT_TRUE(h.find(s("def")) == h.end());
- EXPECT_FALSE(h.find(s("abc")) == h.end());
- auto t1 = h.prehash(s("def"));
- F14HashToken t2;
- t2 = h.prehash(s("abc"));
- EXPECT_TRUE(h.find(t1, s("def")) == h.end());
- EXPECT_FALSE(h.find(t2, s("abc")) == h.end());
- }
- TEST(F14ValueMap, simple) {
- runSimple<F14ValueMap<std::string, std::string>>();
- }
- TEST(F14NodeMap, simple) {
- runSimple<F14NodeMap<std::string, std::string>>();
- }
- TEST(F14VectorMap, simple) {
- runSimple<F14VectorMap<std::string, std::string>>();
- }
- TEST(F14FastMap, simple) {
- runSimple<F14FastMap<std::string, std::string>>();
- }
- TEST(F14VectorMap, reverse_iterator) {
- using TMap = F14VectorMap<uint64_t, uint64_t>;
- auto populate = [](TMap& h, uint64_t lo, uint64_t hi) {
- for (auto i = lo; i < hi; ++i) {
- h.emplace(i, i);
- }
- };
- auto verify = [](TMap 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->first);
- EXPECT_EQ(val, rit->second);
- TMap::const_iterator it = h.iter(rit);
- EXPECT_EQ(val, it->first);
- EXPECT_EQ(val, it->second);
- val++;
- }
- EXPECT_EQ(hi, val);
- };
- TMap 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);
- TMap h2{h};
- verify(h2, 0, newSize);
- h = std::move(h2);
- verify(h, 0, newSize);
- prevSize = newSize;
- newSize *= 10;
- }
- }
- TEST(F14ValueMap, rehash) {
- runRehash<F14ValueMap<std::string, std::string>>();
- }
- TEST(F14NodeMap, rehash) {
- runRehash<F14NodeMap<std::string, std::string>>();
- }
- TEST(F14VectorMap, rehash) {
- runRehash<F14VectorMap<std::string, std::string>>();
- }
- TEST(F14ValueMap, prehash) {
- runPrehash<F14ValueMap<std::string, std::string>>();
- }
- TEST(F14NodeMap, prehash) {
- runPrehash<F14NodeMap<std::string, std::string>>();
- }
- TEST(F14ValueMap, random) {
- runRandom<F14ValueMap<
- uint64_t,
- Tracked<1>,
- std::hash<uint64_t>,
- std::equal_to<uint64_t>,
- SwapTrackingAlloc<std::pair<uint64_t const, Tracked<1>>>>>();
- }
- TEST(F14NodeMap, random) {
- runRandom<F14NodeMap<
- uint64_t,
- Tracked<1>,
- std::hash<uint64_t>,
- std::equal_to<uint64_t>,
- SwapTrackingAlloc<std::pair<uint64_t const, Tracked<1>>>>>();
- }
- TEST(F14VectorMap, random) {
- runRandom<F14VectorMap<
- uint64_t,
- Tracked<1>,
- std::hash<uint64_t>,
- std::equal_to<uint64_t>,
- SwapTrackingAlloc<std::pair<uint64_t const, Tracked<1>>>>>();
- }
- TEST(F14FastMap, random) {
- runRandom<F14FastMap<
- uint64_t,
- Tracked<1>,
- std::hash<uint64_t>,
- std::equal_to<uint64_t>,
- SwapTrackingAlloc<std::pair<uint64_t const, Tracked<1>>>>>();
- }
- TEST(F14ValueMap, grow_stats) {
- F14ValueMap<uint64_t, uint64_t> h;
- for (unsigned i = 1; i <= 3072; ++i) {
- h[i]++;
- }
- // F14ValueMap just before rehash
- F14TableStats::compute(h);
- h[0]++;
- // F14ValueMap just after rehash
- F14TableStats::compute(h);
- }
- TEST(F14ValueMap, 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.
- F14ValueMap<uint64_t, uint64_t> h;
- std::mt19937_64 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_or_assign(key, i);
- } 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);
- }
- }
- // F14ValueMap at steady state
- F14TableStats::compute(h);
- }
- TEST(F14VectorMap, 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.
- F14VectorMap<std::string, uint64_t> h;
- std::mt19937_64 gen(0);
- std::uniform_int_distribution<> dist(0, 10000);
- for (std::size_t i = 0; i < 100000; ++i) {
- auto key = "0123456789ABCDEFGHIJKLMNOPQ" + to<std::string>(dist(gen));
- if (dist(gen) < 1400) {
- h.insert_or_assign(key, i);
- } 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);
- }
- }
- // F14ValueMap at steady state
- F14TableStats::compute(h);
- }
- TEST(Tracked, baseline) {
- Tracked<0> a0;
- {
- resetTracking();
- Tracked<0> b0{a0};
- EXPECT_EQ(a0.val_, b0.val_);
- EXPECT_EQ(sumCounts, (Counts{1, 0, 0, 0}));
- EXPECT_EQ(Tracked<0>::counts, (Counts{1, 0, 0, 0}));
- }
- {
- resetTracking();
- Tracked<0> b0{std::move(a0)};
- EXPECT_EQ(a0.val_, b0.val_);
- EXPECT_EQ(sumCounts, (Counts{0, 1, 0, 0}));
- EXPECT_EQ(Tracked<0>::counts, (Counts{0, 1, 0, 0}));
- }
- {
- resetTracking();
- Tracked<1> b1{a0};
- EXPECT_EQ(a0.val_, b1.val_);
- EXPECT_EQ(sumCounts, (Counts{0, 0, 1, 0}));
- EXPECT_EQ(Tracked<1>::counts, (Counts{0, 0, 1, 0}));
- }
- {
- resetTracking();
- Tracked<1> b1{std::move(a0)};
- EXPECT_EQ(a0.val_, b1.val_);
- EXPECT_EQ(sumCounts, (Counts{0, 0, 0, 1}));
- EXPECT_EQ(Tracked<1>::counts, (Counts{0, 0, 0, 1}));
- }
- {
- Tracked<0> b0;
- resetTracking();
- b0 = a0;
- EXPECT_EQ(a0.val_, b0.val_);
- EXPECT_EQ(sumCounts, (Counts{0, 0, 0, 0, 1, 0}));
- EXPECT_EQ(Tracked<0>::counts, (Counts{0, 0, 0, 0, 1, 0}));
- }
- {
- Tracked<0> b0;
- resetTracking();
- b0 = std::move(a0);
- EXPECT_EQ(a0.val_, b0.val_);
- EXPECT_EQ(sumCounts, (Counts{0, 0, 0, 0, 0, 1}));
- EXPECT_EQ(Tracked<0>::counts, (Counts{0, 0, 0, 0, 0, 1}));
- }
- {
- Tracked<1> b1;
- resetTracking();
- b1 = a0;
- EXPECT_EQ(a0.val_, b1.val_);
- EXPECT_EQ(sumCounts, (Counts{0, 0, 1, 0, 0, 1, 0, 1}));
- EXPECT_EQ(Tracked<1>::counts, (Counts{0, 0, 1, 0, 0, 1, 0, 1}));
- }
- {
- Tracked<1> b1;
- resetTracking();
- b1 = std::move(a0);
- EXPECT_EQ(a0.val_, b1.val_);
- EXPECT_EQ(sumCounts, (Counts{0, 0, 0, 1, 0, 1, 0, 1}));
- EXPECT_EQ(Tracked<1>::counts, (Counts{0, 0, 0, 1, 0, 1, 0, 1}));
- }
- }
- // M should be a map from Tracked<0> to Tracked<1>. F should take a map
- // and a pair const& or pair&& and cause it to be inserted
- template <typename M, typename F>
- void runInsertCases(
- std::string const& name,
- F const& insertFunc,
- uint64_t expectedDist = 0) {
- static_assert(std::is_same<typename M::key_type, Tracked<0>>::value, "");
- static_assert(std::is_same<typename M::mapped_type, Tracked<1>>::value, "");
- {
- typename M::value_type p{0, 0};
- M m;
- resetTracking();
- insertFunc(m, p);
- // fresh key, value_type const& ->
- // copy is expected
- EXPECT_EQ(
- Tracked<0>::counts.dist(Counts{1, 0, 0, 0}) +
- Tracked<1>::counts.dist(Counts{1, 0, 0, 0}),
- expectedDist)
- << name << "\n0 -> " << Tracked<0>::counts << "\n1 -> "
- << Tracked<1>::counts;
- }
- {
- typename M::value_type p{0, 0};
- M m;
- resetTracking();
- insertFunc(m, std::move(p));
- // fresh key, value_type&& ->
- // key copy is unfortunate but required
- EXPECT_EQ(
- Tracked<0>::counts.dist(Counts{1, 0, 0, 0}) +
- Tracked<1>::counts.dist(Counts{0, 1, 0, 0}),
- expectedDist)
- << name << "\n0 -> " << Tracked<0>::counts << "\n1 -> "
- << Tracked<1>::counts;
- }
- {
- std::pair<Tracked<0>, Tracked<1>> p{0, 0};
- M m;
- resetTracking();
- insertFunc(m, p);
- // fresh key, pair<key_type,mapped_type> const& ->
- // 1 copy is required
- EXPECT_EQ(
- Tracked<0>::counts.dist(Counts{1, 0, 0, 0}) +
- Tracked<1>::counts.dist(Counts{1, 0, 0, 0}),
- expectedDist)
- << name << "\n0 -> " << Tracked<0>::counts << "\n1 -> "
- << Tracked<1>::counts;
- }
- {
- std::pair<Tracked<0>, Tracked<1>> p{0, 0};
- M m;
- resetTracking();
- insertFunc(m, std::move(p));
- // fresh key, pair<key_type,mapped_type>&& ->
- // this is the happy path for insert(make_pair(.., ..))
- EXPECT_EQ(
- Tracked<0>::counts.dist(Counts{0, 1, 0, 0}) +
- Tracked<1>::counts.dist(Counts{0, 1, 0, 0}),
- expectedDist)
- << name << "\n0 -> " << Tracked<0>::counts << "\n1 -> "
- << Tracked<1>::counts;
- }
- {
- std::pair<Tracked<2>, Tracked<3>> p{0, 0};
- M m;
- resetTracking();
- insertFunc(m, p);
- // fresh key, convertible const& ->
- // key_type ops: Tracked<0>::counts
- // mapped_type ops: Tracked<1>::counts
- // key_src ops: Tracked<2>::counts
- // mapped_src ops: Tracked<3>::counts;
- // There are three strategies that could be optimal for particular
- // ratios of cost:
- //
- // - convert key and value in place to final position, destroy if
- // insert fails. This is the strategy used by std::unordered_map
- // and FBHashMap
- //
- // - convert key and default value in place to final position,
- // convert value only if insert succeeds. Nobody uses this strategy
- //
- // - convert key to a temporary, move key and convert value if
- // insert succeeds. This is the strategy used by F14 and what is
- // EXPECT_EQ here.
- // The expectedDist * 3 is just a hack for the emplace-pieces-by-value
- // test, whose test harness copies the original pair and then uses
- // move conversion instead of copy conversion.
- EXPECT_EQ(
- Tracked<0>::counts.dist(Counts{0, 1, 1, 0}) +
- Tracked<1>::counts.dist(Counts{0, 0, 1, 0}) +
- Tracked<2>::counts.dist(Counts{0, 0, 0, 0}) +
- Tracked<3>::counts.dist(Counts{0, 0, 0, 0}),
- expectedDist * 3);
- }
- {
- std::pair<Tracked<2>, Tracked<3>> p{0, 0};
- M m;
- resetTracking();
- insertFunc(m, std::move(p));
- // fresh key, convertible&& ->
- // key_type ops: Tracked<0>::counts
- // mapped_type ops: Tracked<1>::counts
- // key_src ops: Tracked<2>::counts
- // mapped_src ops: Tracked<3>::counts;
- EXPECT_EQ(
- Tracked<0>::counts.dist(Counts{0, 1, 0, 1}) +
- Tracked<1>::counts.dist(Counts{0, 0, 0, 1}) +
- Tracked<2>::counts.dist(Counts{0, 0, 0, 0}) +
- Tracked<3>::counts.dist(Counts{0, 0, 0, 0}),
- expectedDist);
- }
- {
- typename M::value_type p{0, 0};
- M m;
- m[0] = 0;
- resetTracking();
- insertFunc(m, p);
- // duplicate key, value_type const&
- EXPECT_EQ(
- Tracked<0>::counts.dist(Counts{0, 0, 0, 0}) +
- Tracked<1>::counts.dist(Counts{0, 0, 0, 0}),
- expectedDist);
- }
- {
- typename M::value_type p{0, 0};
- M m;
- m[0] = 0;
- resetTracking();
- insertFunc(m, std::move(p));
- // duplicate key, value_type&&
- EXPECT_EQ(
- Tracked<0>::counts.dist(Counts{0, 0, 0, 0}) +
- Tracked<1>::counts.dist(Counts{0, 0, 0, 0}),
- expectedDist);
- }
- {
- std::pair<Tracked<0>, Tracked<1>> p{0, 0};
- M m;
- m[0] = 0;
- resetTracking();
- insertFunc(m, p);
- // duplicate key, pair<key_type,mapped_type> const&
- EXPECT_EQ(
- Tracked<0>::counts.dist(Counts{0, 0, 0, 0}) +
- Tracked<1>::counts.dist(Counts{0, 0, 0, 0}),
- expectedDist);
- }
- {
- std::pair<Tracked<0>, Tracked<1>> p{0, 0};
- M m;
- m[0] = 0;
- resetTracking();
- insertFunc(m, std::move(p));
- // duplicate key, pair<key_type,mapped_type>&&
- EXPECT_EQ(
- Tracked<0>::counts.dist(Counts{0, 0, 0, 0}) +
- Tracked<1>::counts.dist(Counts{0, 0, 0, 0}),
- expectedDist);
- }
- {
- std::pair<Tracked<2>, Tracked<3>> p{0, 0};
- M m;
- m[0] = 0;
- resetTracking();
- insertFunc(m, p);
- // duplicate key, convertible const& ->
- // key_type ops: Tracked<0>::counts
- // mapped_type ops: Tracked<1>::counts
- // key_src ops: Tracked<2>::counts
- // mapped_src ops: Tracked<3>::counts;
- EXPECT_EQ(
- Tracked<0>::counts.dist(Counts{0, 0, 1, 0}) +
- Tracked<1>::counts.dist(Counts{0, 0, 0, 0}) +
- Tracked<2>::counts.dist(Counts{0, 0, 0, 0}) +
- Tracked<3>::counts.dist(Counts{0, 0, 0, 0}),
- expectedDist * 2);
- }
- {
- std::pair<Tracked<2>, Tracked<3>> p{0, 0};
- M m;
- m[0] = 0;
- resetTracking();
- insertFunc(m, std::move(p));
- // duplicate key, convertible&& ->
- // key_type ops: Tracked<0>::counts
- // mapped_type ops: Tracked<1>::counts
- // key_src ops: Tracked<2>::counts
- // mapped_src ops: Tracked<3>::counts;
- EXPECT_EQ(
- Tracked<0>::counts.dist(Counts{0, 0, 0, 1}) +
- Tracked<1>::counts.dist(Counts{0, 0, 0, 0}) +
- Tracked<2>::counts.dist(Counts{0, 0, 0, 0}) +
- Tracked<3>::counts.dist(Counts{0, 0, 0, 0}),
- expectedDist);
- }
- }
- 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));
- }
- };
- struct DoEmplace2 {
- template <typename M, typename U1, typename U2>
- void operator()(M& m, std::pair<U1, U2> const& p) const {
- m.emplace(p.first, p.second);
- }
- template <typename M, typename U1, typename U2>
- void operator()(M& m, std::pair<U1, U2>&& p) const {
- m.emplace(std::move(p.first), std::move(p.second));
- }
- };
- struct DoEmplace3 {
- template <typename M, typename U1, typename U2>
- void operator()(M& m, std::pair<U1, U2> const& p) const {
- m.emplace(
- std::piecewise_construct,
- std::forward_as_tuple(p.first),
- std::forward_as_tuple(p.second));
- }
- template <typename M, typename U1, typename U2>
- void operator()(M& m, std::pair<U1, U2>&& p) const {
- m.emplace(
- std::piecewise_construct,
- std::forward_as_tuple(std::move(p.first)),
- std::forward_as_tuple(std::move(p.second)));
- }
- };
- // Simulates use of piecewise_construct without proper use of
- // forward_as_tuple. This code doesn't yield the normal pattern, but
- // it should have exactly 1 additional move or copy of the key and 1
- // additional move or copy of the mapped value.
- struct DoEmplace3Value {
- template <typename M, typename U1, typename U2>
- void operator()(M& m, std::pair<U1, U2> const& p) const {
- m.emplace(
- std::piecewise_construct,
- std::tuple<U1>{p.first},
- std::tuple<U2>{p.second});
- }
- template <typename M, typename U1, typename U2>
- void operator()(M& m, std::pair<U1, U2>&& p) const {
- m.emplace(
- std::piecewise_construct,
- std::tuple<U1>{std::move(p.first)},
- std::tuple<U2>{std::move(p.second)});
- }
- };
- template <typename M>
- void runInsertAndEmplace(std::string const& name) {
- runInsertCases<M>(name + " insert", DoInsert{});
- runInsertCases<M>(name + " emplace pair", DoEmplace1{});
- runInsertCases<M>(name + " emplace k,v", DoEmplace2{});
- runInsertCases<M>(name + " emplace pieces", DoEmplace3{});
- runInsertCases<M>(name + " emplace pieces by value", DoEmplace3Value{}, 2);
- // Calling the default pair constructor via emplace is valid, but not
- // very useful in real life. Verify that it works.
- M m;
- typename M::key_type k;
- EXPECT_EQ(m.count(k), 0);
- m.emplace();
- EXPECT_EQ(m.count(k), 1);
- m.emplace();
- EXPECT_EQ(m.count(k), 1);
- }
- TEST(F14ValueMap, destructuring) {
- runInsertAndEmplace<F14ValueMap<Tracked<0>, Tracked<1>>>("f14value");
- }
- TEST(F14NodeMap, destructuring) {
- runInsertAndEmplace<F14NodeMap<Tracked<0>, Tracked<1>>>("f14node");
- }
- TEST(F14VectorMap, destructuring) {
- runInsertAndEmplace<F14VectorMap<Tracked<0>, Tracked<1>>>("f14vector");
- }
- TEST(F14VectorMap, destructuringErase) {
- using M = F14VectorMap<Tracked<0>, Tracked<1>>;
- typename M::value_type p1{0, 0};
- typename M::value_type p2{2, 2};
- M m;
- m.insert(p1);
- m.insert(p2);
- resetTracking();
- m.erase(p1.first);
- LOG(INFO) << "erase -> "
- << "key_type ops " << Tracked<0>::counts << ", mapped_type ops "
- << Tracked<1>::counts;
- // deleting p1 will cause p2 to be moved to the front of the values array
- EXPECT_EQ(
- Tracked<0>::counts.dist(Counts{0, 1, 0, 0}) +
- Tracked<1>::counts.dist(Counts{0, 1, 0, 0}),
- 0);
- }
- TEST(F14ValueMap, maxSize) {
- F14ValueMap<int, int> m;
- EXPECT_EQ(
- m.max_size(),
- std::numeric_limits<std::size_t>::max() / sizeof(std::pair<int, int>));
- }
- TEST(F14NodeMap, maxSize) {
- F14NodeMap<int, int> m;
- EXPECT_EQ(
- m.max_size(),
- std::numeric_limits<std::size_t>::max() / sizeof(std::pair<int, int>));
- }
- TEST(F14VectorMap, vectorMaxSize) {
- F14VectorMap<int, int> m;
- EXPECT_EQ(
- m.max_size(),
- std::min(
- std::size_t{std::numeric_limits<uint32_t>::max()},
- std::numeric_limits<std::size_t>::max() /
- sizeof(std::pair<int, int>)));
- }
- template <typename M>
- void runMoveOnlyTest() {
- M t0;
- t0[10] = 20;
- t0.emplace(30, 40);
- t0.insert(std::make_pair(50, 60));
- M t1{std::move(t0)};
- EXPECT_TRUE(t0.empty());
- M t2;
- EXPECT_TRUE(t2.empty());
- t2 = std::move(t1);
- EXPECT_EQ(t2.size(), 3);
- }
- TEST(F14ValueMap, moveOnly) {
- runMoveOnlyTest<F14ValueMap<f14::MoveOnlyTestInt, int>>();
- runMoveOnlyTest<F14ValueMap<int, f14::MoveOnlyTestInt>>();
- runMoveOnlyTest<F14ValueMap<f14::MoveOnlyTestInt, f14::MoveOnlyTestInt>>();
- }
- TEST(F14NodeMap, moveOnly) {
- runMoveOnlyTest<F14NodeMap<f14::MoveOnlyTestInt, int>>();
- runMoveOnlyTest<F14NodeMap<int, f14::MoveOnlyTestInt>>();
- runMoveOnlyTest<F14NodeMap<f14::MoveOnlyTestInt, f14::MoveOnlyTestInt>>();
- }
- TEST(F14VectorMap, moveOnly) {
- runMoveOnlyTest<F14VectorMap<f14::MoveOnlyTestInt, int>>();
- runMoveOnlyTest<F14VectorMap<int, f14::MoveOnlyTestInt>>();
- runMoveOnlyTest<F14VectorMap<f14::MoveOnlyTestInt, f14::MoveOnlyTestInt>>();
- }
- TEST(F14FastMap, moveOnly) {
- runMoveOnlyTest<F14FastMap<f14::MoveOnlyTestInt, int>>();
- runMoveOnlyTest<F14FastMap<int, f14::MoveOnlyTestInt>>();
- runMoveOnlyTest<F14FastMap<f14::MoveOnlyTestInt, f14::MoveOnlyTestInt>>();
- }
- TEST(F14ValueMap, heterogeneousLookup) {
- 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;
- F14ValueMap<std::string, bool, Hasher, KeyEqual> map;
- map.emplace(hello, true);
- map.emplace(world, false);
- 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)->first);
- // prehash + find
- EXPECT_TRUE(ref.end() == ref.find(ref.prehash(buddy), buddy));
- EXPECT_EQ(hello, ref.find(ref.prehash(hello), hello)->first);
- // 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(map);
- checks(folly::as_const(map));
- }
- template <typename M>
- 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);
- };
- {
- M map(0, hasher, equal, {alloc, dealloc});
- map[10]++;
- map[10]++;
- EXPECT_EQ(map[10], 2);
- M map2(map);
- M map3(std::move(map));
- map = map2;
- map2.clear();
- map2 = std::move(map3);
- }
- EXPECT_TRUE(ranHasher);
- EXPECT_TRUE(ranEqual);
- EXPECT_TRUE(ranAlloc);
- EXPECT_TRUE(ranDealloc);
- }
- TEST(F14ValueMap, statefulFunctors) {
- runStatefulFunctorTest<F14ValueMap<
- int,
- int,
- GenericHasher<int>,
- GenericEqual<int>,
- GenericAlloc<std::pair<int const, int>>>>();
- }
- TEST(F14NodeMap, statefulFunctors) {
- runStatefulFunctorTest<F14NodeMap<
- int,
- int,
- GenericHasher<int>,
- GenericEqual<int>,
- GenericAlloc<std::pair<int const, int>>>>();
- }
- TEST(F14VectorMap, statefulFunctors) {
- runStatefulFunctorTest<F14VectorMap<
- int,
- int,
- GenericHasher<int>,
- GenericEqual<int>,
- GenericAlloc<std::pair<int const, int>>>>();
- }
- TEST(F14FastMap, statefulFunctors) {
- runStatefulFunctorTest<F14FastMap<
- int,
- int,
- GenericHasher<int>,
- GenericEqual<int>,
- GenericAlloc<std::pair<int const, int>>>>();
- }
- template <typename M>
- void runHeterogeneousInsertTest() {
- M map;
- resetTracking();
- EXPECT_EQ(map.count(10), 0);
- EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
- << Tracked<1>::counts;
- resetTracking();
- map[10] = 20;
- EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 1}), 0)
- << Tracked<1>::counts;
- resetTracking();
- std::pair<int, int> p(10, 30);
- std::vector<std::pair<int, int>> v({p});
- map[10] = 30;
- map.insert(std::pair<int, int>(10, 30));
- map.insert(std::pair<int const, int>(10, 30));
- map.insert(p);
- map.insert(v.begin(), v.end());
- map.insert(
- std::make_move_iterator(v.begin()), std::make_move_iterator(v.end()));
- map.insert_or_assign(10, 40);
- EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
- << Tracked<1>::counts;
- resetTracking();
- map.emplace(10, 30);
- map.emplace(
- std::piecewise_construct,
- std::forward_as_tuple(10),
- std::forward_as_tuple(30));
- map.emplace(p);
- map.try_emplace(10, 30);
- map.try_emplace(10);
- EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
- << Tracked<1>::counts;
- resetTracking();
- map.erase(10);
- EXPECT_EQ(map.size(), 0);
- EXPECT_EQ(Tracked<1>::counts.dist(Counts{0, 0, 0, 0}), 0)
- << Tracked<1>::counts;
- }
- template <typename M>
- void runHeterogeneousInsertStringTest() {
- using P = std::pair<StringPiece, std::string>;
- using CP = std::pair<const StringPiece, std::string>;
- M map;
- P p{"foo", "hello"};
- std::vector<P> v{p};
- StringPiece foo{"foo"};
- map.insert(P("foo", "hello"));
- // TODO(T31574848): the list-initialization below does not work on libstdc++
- // versions (e.g., GCC < 6) with no implementation of N4387 ("perfect
- // initialization" for pairs and tuples).
- // StringPiece sp{"foo"};
- // map.insert({sp, "hello"});
- map.insert({"foo", "hello"});
- map.insert(CP("foo", "hello"));
- map.insert(p);
- map.insert(v.begin(), v.end());
- map.insert(
- std::make_move_iterator(v.begin()), std::make_move_iterator(v.end()));
- map.insert_or_assign("foo", "hello");
- map.insert_or_assign(StringPiece{"foo"}, "hello");
- EXPECT_EQ(map["foo"], "hello");
- map.emplace(StringPiece{"foo"}, "hello");
- map.emplace("foo", "hello");
- map.emplace(p);
- map.emplace();
- map.emplace(
- std::piecewise_construct,
- std::forward_as_tuple(StringPiece{"foo"}),
- std::forward_as_tuple(/* count */ 20, 'x'));
- map.try_emplace(StringPiece{"foo"}, "hello");
- map.try_emplace(foo, "hello");
- map.try_emplace(foo);
- map.try_emplace("foo");
- map.try_emplace("foo", "hello");
- map.try_emplace("foo", /* count */ 20, 'x');
- map.erase(StringPiece{"foo"});
- map.erase(foo);
- map.erase("");
- EXPECT_TRUE(map.empty());
- }
- TEST(F14ValueMap, heterogeneousInsert) {
- runHeterogeneousInsertTest<F14ValueMap<
- Tracked<1>,
- int,
- TransparentTrackedHash<1>,
- TransparentTrackedEqual<1>>>();
- runHeterogeneousInsertStringTest<F14ValueMap<
- std::string,
- std::string,
- transparent<hasher<StringPiece>>,
- transparent<DefaultKeyEqual<StringPiece>>>>();
- }
- TEST(F14NodeMap, heterogeneousInsert) {
- runHeterogeneousInsertTest<F14NodeMap<
- Tracked<1>,
- int,
- TransparentTrackedHash<1>,
- TransparentTrackedEqual<1>>>();
- runHeterogeneousInsertStringTest<F14NodeMap<
- std::string,
- std::string,
- transparent<hasher<StringPiece>>,
- transparent<DefaultKeyEqual<StringPiece>>>>();
- }
- TEST(F14VectorMap, heterogeneousInsert) {
- runHeterogeneousInsertTest<F14VectorMap<
- Tracked<1>,
- int,
- TransparentTrackedHash<1>,
- TransparentTrackedEqual<1>>>();
- runHeterogeneousInsertStringTest<F14VectorMap<
- std::string,
- std::string,
- transparent<hasher<StringPiece>>,
- transparent<DefaultKeyEqual<StringPiece>>>>();
- }
- TEST(F14FastMap, heterogeneousInsert) {
- runHeterogeneousInsertTest<F14FastMap<
- Tracked<1>,
- int,
- TransparentTrackedHash<1>,
- TransparentTrackedEqual<1>>>();
- runHeterogeneousInsertStringTest<F14FastMap<
- std::string,
- std::string,
- transparent<hasher<StringPiece>>,
- transparent<DefaultKeyEqual<StringPiece>>>>();
- }
- ///////////////////////////////////
- #endif // FOLLY_F14_VECTOR_INTRINSICS_AVAILABLE
- ///////////////////////////////////
|