| 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916 | // Copyright 2018 The Abseil Authors.//// 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////      https://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 "absl/container/internal/raw_hash_set.h"#include <cmath>#include <cstdint>#include <deque>#include <functional>#include <memory>#include <numeric>#include <random>#include <string>#include "gmock/gmock.h"#include "gtest/gtest.h"#include "absl/base/attributes.h"#include "absl/base/internal/cycleclock.h"#include "absl/base/internal/raw_logging.h"#include "absl/container/internal/container_memory.h"#include "absl/container/internal/hash_function_defaults.h"#include "absl/container/internal/hash_policy_testing.h"#include "absl/container/internal/hashtable_debug.h"#include "absl/strings/string_view.h"namespace absl {namespace container_internal {struct RawHashSetTestOnlyAccess {  template <typename C>  static auto GetSlots(const C& c) -> decltype(c.slots_) {    return c.slots_;  }};namespace {using ::testing::DoubleNear;using ::testing::ElementsAre;using ::testing::Ge;using ::testing::Lt;using ::testing::Optional;using ::testing::Pair;using ::testing::UnorderedElementsAre;TEST(Util, NormalizeCapacity) {  EXPECT_EQ(1, NormalizeCapacity(0));  EXPECT_EQ(1, NormalizeCapacity(1));  EXPECT_EQ(3, NormalizeCapacity(2));  EXPECT_EQ(3, NormalizeCapacity(3));  EXPECT_EQ(7, NormalizeCapacity(4));  EXPECT_EQ(7, NormalizeCapacity(7));  EXPECT_EQ(15, NormalizeCapacity(8));  EXPECT_EQ(15, NormalizeCapacity(15));  EXPECT_EQ(15 * 2 + 1, NormalizeCapacity(15 + 1));  EXPECT_EQ(15 * 2 + 1, NormalizeCapacity(15 + 2));}TEST(Util, GrowthAndCapacity) {  // Verify that GrowthToCapacity gives the minimum capacity that has enough  // growth.  for (size_t growth = 0; growth < 10000; ++growth) {    SCOPED_TRACE(growth);    size_t capacity = NormalizeCapacity(GrowthToLowerboundCapacity(growth));    // The capacity is large enough for `growth`    EXPECT_THAT(CapacityToGrowth(capacity), Ge(growth));    if (growth != 0 && capacity > 1) {      // There is no smaller capacity that works.      EXPECT_THAT(CapacityToGrowth(capacity / 2), Lt(growth));    }  }  for (size_t capacity = Group::kWidth - 1; capacity < 10000;       capacity = 2 * capacity + 1) {    SCOPED_TRACE(capacity);    size_t growth = CapacityToGrowth(capacity);    EXPECT_THAT(growth, Lt(capacity));    EXPECT_LE(GrowthToLowerboundCapacity(growth), capacity);    EXPECT_EQ(NormalizeCapacity(GrowthToLowerboundCapacity(growth)), capacity);  }}TEST(Util, probe_seq) {  probe_seq<16> seq(0, 127);  auto gen = [&]() {    size_t res = seq.offset();    seq.next();    return res;  };  std::vector<size_t> offsets(8);  std::generate_n(offsets.begin(), 8, gen);  EXPECT_THAT(offsets, ElementsAre(0, 16, 48, 96, 32, 112, 80, 64));  seq = probe_seq<16>(128, 127);  std::generate_n(offsets.begin(), 8, gen);  EXPECT_THAT(offsets, ElementsAre(0, 16, 48, 96, 32, 112, 80, 64));}TEST(BitMask, Smoke) {  EXPECT_FALSE((BitMask<uint8_t, 8>(0)));  EXPECT_TRUE((BitMask<uint8_t, 8>(5)));  EXPECT_THAT((BitMask<uint8_t, 8>(0)), ElementsAre());  EXPECT_THAT((BitMask<uint8_t, 8>(0x1)), ElementsAre(0));  EXPECT_THAT((BitMask<uint8_t, 8>(0x2)), ElementsAre(1));  EXPECT_THAT((BitMask<uint8_t, 8>(0x3)), ElementsAre(0, 1));  EXPECT_THAT((BitMask<uint8_t, 8>(0x4)), ElementsAre(2));  EXPECT_THAT((BitMask<uint8_t, 8>(0x5)), ElementsAre(0, 2));  EXPECT_THAT((BitMask<uint8_t, 8>(0x55)), ElementsAre(0, 2, 4, 6));  EXPECT_THAT((BitMask<uint8_t, 8>(0xAA)), ElementsAre(1, 3, 5, 7));}TEST(BitMask, WithShift) {  // See the non-SSE version of Group for details on what this math is for.  uint64_t ctrl = 0x1716151413121110;  uint64_t hash = 0x12;  constexpr uint64_t msbs = 0x8080808080808080ULL;  constexpr uint64_t lsbs = 0x0101010101010101ULL;  auto x = ctrl ^ (lsbs * hash);  uint64_t mask = (x - lsbs) & ~x & msbs;  EXPECT_EQ(0x0000000080800000, mask);  BitMask<uint64_t, 8, 3> b(mask);  EXPECT_EQ(*b, 2);}TEST(BitMask, LeadingTrailing) {  EXPECT_EQ((BitMask<uint32_t, 16>(0x00001a40).LeadingZeros()), 3);  EXPECT_EQ((BitMask<uint32_t, 16>(0x00001a40).TrailingZeros()), 6);  EXPECT_EQ((BitMask<uint32_t, 16>(0x00000001).LeadingZeros()), 15);  EXPECT_EQ((BitMask<uint32_t, 16>(0x00000001).TrailingZeros()), 0);  EXPECT_EQ((BitMask<uint32_t, 16>(0x00008000).LeadingZeros()), 0);  EXPECT_EQ((BitMask<uint32_t, 16>(0x00008000).TrailingZeros()), 15);  EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x0000008080808000).LeadingZeros()), 3);  EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x0000008080808000).TrailingZeros()), 1);  EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x0000000000000080).LeadingZeros()), 7);  EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x0000000000000080).TrailingZeros()), 0);  EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x8000000000000000).LeadingZeros()), 0);  EXPECT_EQ((BitMask<uint64_t, 8, 3>(0x8000000000000000).TrailingZeros()), 7);}TEST(Group, EmptyGroup) {  for (h2_t h = 0; h != 128; ++h) EXPECT_FALSE(Group{EmptyGroup()}.Match(h));}TEST(Group, Match) {  if (Group::kWidth == 16) {    ctrl_t group[] = {kEmpty, 1, kDeleted, 3, kEmpty, 5, kSentinel, 7,                      7,      5, 3,        1, 1,      1, 1,         1};    EXPECT_THAT(Group{group}.Match(0), ElementsAre());    EXPECT_THAT(Group{group}.Match(1), ElementsAre(1, 11, 12, 13, 14, 15));    EXPECT_THAT(Group{group}.Match(3), ElementsAre(3, 10));    EXPECT_THAT(Group{group}.Match(5), ElementsAre(5, 9));    EXPECT_THAT(Group{group}.Match(7), ElementsAre(7, 8));  } else if (Group::kWidth == 8) {    ctrl_t group[] = {kEmpty, 1, 2, kDeleted, 2, 1, kSentinel, 1};    EXPECT_THAT(Group{group}.Match(0), ElementsAre());    EXPECT_THAT(Group{group}.Match(1), ElementsAre(1, 5, 7));    EXPECT_THAT(Group{group}.Match(2), ElementsAre(2, 4));  } else {    FAIL() << "No test coverage for Group::kWidth==" << Group::kWidth;  }}TEST(Group, MatchEmpty) {  if (Group::kWidth == 16) {    ctrl_t group[] = {kEmpty, 1, kDeleted, 3, kEmpty, 5, kSentinel, 7,                      7,      5, 3,        1, 1,      1, 1,         1};    EXPECT_THAT(Group{group}.MatchEmpty(), ElementsAre(0, 4));  } else if (Group::kWidth == 8) {    ctrl_t group[] = {kEmpty, 1, 2, kDeleted, 2, 1, kSentinel, 1};    EXPECT_THAT(Group{group}.MatchEmpty(), ElementsAre(0));  } else {    FAIL() << "No test coverage for Group::kWidth==" << Group::kWidth;  }}TEST(Group, MatchEmptyOrDeleted) {  if (Group::kWidth == 16) {    ctrl_t group[] = {kEmpty, 1, kDeleted, 3, kEmpty, 5, kSentinel, 7,                      7,      5, 3,        1, 1,      1, 1,         1};    EXPECT_THAT(Group{group}.MatchEmptyOrDeleted(), ElementsAre(0, 2, 4));  } else if (Group::kWidth == 8) {    ctrl_t group[] = {kEmpty, 1, 2, kDeleted, 2, 1, kSentinel, 1};    EXPECT_THAT(Group{group}.MatchEmptyOrDeleted(), ElementsAre(0, 3));  } else {    FAIL() << "No test coverage for Group::kWidth==" << Group::kWidth;  }}TEST(Batch, DropDeletes) {  constexpr size_t kCapacity = 63;  constexpr size_t kGroupWidth = container_internal::Group::kWidth;  std::vector<ctrl_t> ctrl(kCapacity + 1 + kGroupWidth);  ctrl[kCapacity] = kSentinel;  std::vector<ctrl_t> pattern = {kEmpty, 2, kDeleted, 2, kEmpty, 1, kDeleted};  for (size_t i = 0; i != kCapacity; ++i) {    ctrl[i] = pattern[i % pattern.size()];    if (i < kGroupWidth - 1)      ctrl[i + kCapacity + 1] = pattern[i % pattern.size()];  }  ConvertDeletedToEmptyAndFullToDeleted(ctrl.data(), kCapacity);  ASSERT_EQ(ctrl[kCapacity], kSentinel);  for (size_t i = 0; i < kCapacity + 1 + kGroupWidth; ++i) {    ctrl_t expected = pattern[i % (kCapacity + 1) % pattern.size()];    if (i == kCapacity) expected = kSentinel;    if (expected == kDeleted) expected = kEmpty;    if (IsFull(expected)) expected = kDeleted;    EXPECT_EQ(ctrl[i], expected)        << i << " " << int{pattern[i % pattern.size()]};  }}TEST(Group, CountLeadingEmptyOrDeleted) {  const std::vector<ctrl_t> empty_examples = {kEmpty, kDeleted};  const std::vector<ctrl_t> full_examples = {0, 1, 2, 3, 5, 9, 127, kSentinel};  for (ctrl_t empty : empty_examples) {    std::vector<ctrl_t> e(Group::kWidth, empty);    EXPECT_EQ(Group::kWidth, Group{e.data()}.CountLeadingEmptyOrDeleted());    for (ctrl_t full : full_examples) {      for (size_t i = 0; i != Group::kWidth; ++i) {        std::vector<ctrl_t> f(Group::kWidth, empty);        f[i] = full;        EXPECT_EQ(i, Group{f.data()}.CountLeadingEmptyOrDeleted());      }      std::vector<ctrl_t> f(Group::kWidth, empty);      f[Group::kWidth * 2 / 3] = full;      f[Group::kWidth / 2] = full;      EXPECT_EQ(          Group::kWidth / 2, Group{f.data()}.CountLeadingEmptyOrDeleted());    }  }}struct IntPolicy {  using slot_type = int64_t;  using key_type = int64_t;  using init_type = int64_t;  static void construct(void*, int64_t* slot, int64_t v) { *slot = v; }  static void destroy(void*, int64_t*) {}  static void transfer(void*, int64_t* new_slot, int64_t* old_slot) {    *new_slot = *old_slot;  }  static int64_t& element(slot_type* slot) { return *slot; }  template <class F>  static auto apply(F&& f, int64_t x) -> decltype(std::forward<F>(f)(x, x)) {    return std::forward<F>(f)(x, x);  }};class StringPolicy {  template <class F, class K, class V,            class = typename std::enable_if<                std::is_convertible<const K&, absl::string_view>::value>::type>  decltype(std::declval<F>()(      std::declval<const absl::string_view&>(), std::piecewise_construct,      std::declval<std::tuple<K>>(),      std::declval<V>())) static apply_impl(F&& f,                                            std::pair<std::tuple<K>, V> p) {    const absl::string_view& key = std::get<0>(p.first);    return std::forward<F>(f)(key, std::piecewise_construct, std::move(p.first),                              std::move(p.second));  } public:  struct slot_type {    struct ctor {};    template <class... Ts>    slot_type(ctor, Ts&&... ts) : pair(std::forward<Ts>(ts)...) {}    std::pair<std::string, std::string> pair;  };  using key_type = std::string;  using init_type = std::pair<std::string, std::string>;  template <class allocator_type, class... Args>  static void construct(allocator_type* alloc, slot_type* slot, Args... args) {    std::allocator_traits<allocator_type>::construct(        *alloc, slot, typename slot_type::ctor(), std::forward<Args>(args)...);  }  template <class allocator_type>  static void destroy(allocator_type* alloc, slot_type* slot) {    std::allocator_traits<allocator_type>::destroy(*alloc, slot);  }  template <class allocator_type>  static void transfer(allocator_type* alloc, slot_type* new_slot,                       slot_type* old_slot) {    construct(alloc, new_slot, std::move(old_slot->pair));    destroy(alloc, old_slot);  }  static std::pair<std::string, std::string>& element(slot_type* slot) {    return slot->pair;  }  template <class F, class... Args>  static auto apply(F&& f, Args&&... args)      -> decltype(apply_impl(std::forward<F>(f),                             PairArgs(std::forward<Args>(args)...))) {    return apply_impl(std::forward<F>(f),                      PairArgs(std::forward<Args>(args)...));  }};struct StringHash : absl::Hash<absl::string_view> {  using is_transparent = void;};struct StringEq : std::equal_to<absl::string_view> {  using is_transparent = void;};struct StringTable    : raw_hash_set<StringPolicy, StringHash, StringEq, std::allocator<int>> {  using Base = typename StringTable::raw_hash_set;  StringTable() {}  using Base::Base;};struct IntTable    : raw_hash_set<IntPolicy, container_internal::hash_default_hash<int64_t>,                   std::equal_to<int64_t>, std::allocator<int64_t>> {  using Base = typename IntTable::raw_hash_set;  using Base::Base;};template <typename T>struct CustomAlloc : std::allocator<T> {  CustomAlloc() {}  template <typename U>  CustomAlloc(const CustomAlloc<U>& other) {}  template<class U> struct rebind {    using other = CustomAlloc<U>;  };};struct CustomAllocIntTable    : raw_hash_set<IntPolicy, container_internal::hash_default_hash<int64_t>,                   std::equal_to<int64_t>, CustomAlloc<int64_t>> {  using Base = typename CustomAllocIntTable::raw_hash_set;  using Base::Base;};struct BadFastHash {  template <class T>  size_t operator()(const T&) const {    return 0;  }};struct BadTable : raw_hash_set<IntPolicy, BadFastHash, std::equal_to<int>,                               std::allocator<int>> {  using Base = typename BadTable::raw_hash_set;  BadTable() {}  using Base::Base;};TEST(Table, EmptyFunctorOptimization) {  static_assert(std::is_empty<std::equal_to<absl::string_view>>::value, "");  static_assert(std::is_empty<std::allocator<int>>::value, "");  struct MockTable {    void* ctrl;    void* slots;    size_t size;    size_t capacity;    size_t growth_left;    void* infoz;  };  struct StatelessHash {    size_t operator()(absl::string_view) const { return 0; }  };  struct StatefulHash : StatelessHash {    size_t dummy;  };  EXPECT_EQ(      sizeof(MockTable),      sizeof(          raw_hash_set<StringPolicy, StatelessHash,                       std::equal_to<absl::string_view>, std::allocator<int>>));  EXPECT_EQ(      sizeof(MockTable) + sizeof(StatefulHash),      sizeof(          raw_hash_set<StringPolicy, StatefulHash,                       std::equal_to<absl::string_view>, std::allocator<int>>));}TEST(Table, Empty) {  IntTable t;  EXPECT_EQ(0, t.size());  EXPECT_TRUE(t.empty());}#ifdef __GNUC__template <class T>ABSL_ATTRIBUTE_ALWAYS_INLINE inline void DoNotOptimize(const T& v) {  asm volatile("" : : "r,m"(v) : "memory");}#endifTEST(Table, Prefetch) {  IntTable t;  t.emplace(1);  // Works for both present and absent keys.  t.prefetch(1);  t.prefetch(2);  // Do not run in debug mode, when prefetch is not implemented, or when  // sanitizers are enabled, or on WebAssembly.#if defined(NDEBUG) && defined(__GNUC__) && defined(__x86_64__) &&          \    !defined(ADDRESS_SANITIZER) && !defined(MEMORY_SANITIZER) &&            \    !defined(THREAD_SANITIZER) && !defined(UNDEFINED_BEHAVIOR_SANITIZER) && \    !defined(__EMSCRIPTEN__)  const auto now = [] { return absl::base_internal::CycleClock::Now(); };  // Make size enough to not fit in L2 cache (16.7 Mb)  static constexpr int size = 1 << 22;  for (int i = 0; i < size; ++i) t.insert(i);  int64_t no_prefetch = 0, prefetch = 0;  for (int iter = 0; iter < 10; ++iter) {    int64_t time = now();    for (int i = 0; i < size; ++i) {      DoNotOptimize(t.find(i));    }    no_prefetch += now() - time;    time = now();    for (int i = 0; i < size; ++i) {      t.prefetch(i + 20);      DoNotOptimize(t.find(i));    }    prefetch += now() - time;  }  // no_prefetch is at least 30% slower.  EXPECT_GE(1.0 * no_prefetch / prefetch, 1.3);#endif}TEST(Table, LookupEmpty) {  IntTable t;  auto it = t.find(0);  EXPECT_TRUE(it == t.end());}TEST(Table, Insert1) {  IntTable t;  EXPECT_TRUE(t.find(0) == t.end());  auto res = t.emplace(0);  EXPECT_TRUE(res.second);  EXPECT_THAT(*res.first, 0);  EXPECT_EQ(1, t.size());  EXPECT_THAT(*t.find(0), 0);}TEST(Table, Insert2) {  IntTable t;  EXPECT_TRUE(t.find(0) == t.end());  auto res = t.emplace(0);  EXPECT_TRUE(res.second);  EXPECT_THAT(*res.first, 0);  EXPECT_EQ(1, t.size());  EXPECT_TRUE(t.find(1) == t.end());  res = t.emplace(1);  EXPECT_TRUE(res.second);  EXPECT_THAT(*res.first, 1);  EXPECT_EQ(2, t.size());  EXPECT_THAT(*t.find(0), 0);  EXPECT_THAT(*t.find(1), 1);}TEST(Table, InsertCollision) {  BadTable t;  EXPECT_TRUE(t.find(1) == t.end());  auto res = t.emplace(1);  EXPECT_TRUE(res.second);  EXPECT_THAT(*res.first, 1);  EXPECT_EQ(1, t.size());  EXPECT_TRUE(t.find(2) == t.end());  res = t.emplace(2);  EXPECT_THAT(*res.first, 2);  EXPECT_TRUE(res.second);  EXPECT_EQ(2, t.size());  EXPECT_THAT(*t.find(1), 1);  EXPECT_THAT(*t.find(2), 2);}// Test that we do not add existent element in case we need to search through// many groups with deleted elementsTEST(Table, InsertCollisionAndFindAfterDelete) {  BadTable t;  // all elements go to the same group.  // Have at least 2 groups with Group::kWidth collisions  // plus some extra collisions in the last group.  constexpr size_t kNumInserts = Group::kWidth * 2 + 5;  for (size_t i = 0; i < kNumInserts; ++i) {    auto res = t.emplace(i);    EXPECT_TRUE(res.second);    EXPECT_THAT(*res.first, i);    EXPECT_EQ(i + 1, t.size());  }  // Remove elements one by one and check  // that we still can find all other elements.  for (size_t i = 0; i < kNumInserts; ++i) {    EXPECT_EQ(1, t.erase(i)) << i;    for (size_t j = i + 1; j < kNumInserts; ++j) {      EXPECT_THAT(*t.find(j), j);      auto res = t.emplace(j);      EXPECT_FALSE(res.second) << i << " " << j;      EXPECT_THAT(*res.first, j);      EXPECT_EQ(kNumInserts - i - 1, t.size());    }  }  EXPECT_TRUE(t.empty());}TEST(Table, LazyEmplace) {  StringTable t;  bool called = false;  auto it = t.lazy_emplace("abc", [&](const StringTable::constructor& f) {    called = true;    f("abc", "ABC");  });  EXPECT_TRUE(called);  EXPECT_THAT(*it, Pair("abc", "ABC"));  called = false;  it = t.lazy_emplace("abc", [&](const StringTable::constructor& f) {    called = true;    f("abc", "DEF");  });  EXPECT_FALSE(called);  EXPECT_THAT(*it, Pair("abc", "ABC"));}TEST(Table, ContainsEmpty) {  IntTable t;  EXPECT_FALSE(t.contains(0));}TEST(Table, Contains1) {  IntTable t;  EXPECT_TRUE(t.insert(0).second);  EXPECT_TRUE(t.contains(0));  EXPECT_FALSE(t.contains(1));  EXPECT_EQ(1, t.erase(0));  EXPECT_FALSE(t.contains(0));}TEST(Table, Contains2) {  IntTable t;  EXPECT_TRUE(t.insert(0).second);  EXPECT_TRUE(t.contains(0));  EXPECT_FALSE(t.contains(1));  t.clear();  EXPECT_FALSE(t.contains(0));}int decompose_constructed;struct DecomposeType {  DecomposeType(int i) : i(i) {  // NOLINT    ++decompose_constructed;  }  explicit DecomposeType(const char* d) : DecomposeType(*d) {}  int i;};struct DecomposeHash {  using is_transparent = void;  size_t operator()(DecomposeType a) const { return a.i; }  size_t operator()(int a) const { return a; }  size_t operator()(const char* a) const { return *a; }};struct DecomposeEq {  using is_transparent = void;  bool operator()(DecomposeType a, DecomposeType b) const { return a.i == b.i; }  bool operator()(DecomposeType a, int b) const { return a.i == b; }  bool operator()(DecomposeType a, const char* b) const { return a.i == *b; }};struct DecomposePolicy {  using slot_type = DecomposeType;  using key_type = DecomposeType;  using init_type = DecomposeType;  template <typename T>  static void construct(void*, DecomposeType* slot, T&& v) {    *slot = DecomposeType(std::forward<T>(v));  }  static void destroy(void*, DecomposeType*) {}  static DecomposeType& element(slot_type* slot) { return *slot; }  template <class F, class T>  static auto apply(F&& f, const T& x) -> decltype(std::forward<F>(f)(x, x)) {    return std::forward<F>(f)(x, x);  }};template <typename Hash, typename Eq>void TestDecompose(bool construct_three) {  DecomposeType elem{0};  const int one = 1;  const char* three_p = "3";  const auto& three = three_p;  raw_hash_set<DecomposePolicy, Hash, Eq, std::allocator<int>> set1;  decompose_constructed = 0;  int expected_constructed = 0;  EXPECT_EQ(expected_constructed, decompose_constructed);  set1.insert(elem);  EXPECT_EQ(expected_constructed, decompose_constructed);  set1.insert(1);  EXPECT_EQ(++expected_constructed, decompose_constructed);  set1.emplace("3");  EXPECT_EQ(++expected_constructed, decompose_constructed);  EXPECT_EQ(expected_constructed, decompose_constructed);  {  // insert(T&&)    set1.insert(1);    EXPECT_EQ(expected_constructed, decompose_constructed);  }  {  // insert(const T&)    set1.insert(one);    EXPECT_EQ(expected_constructed, decompose_constructed);  }  {  // insert(hint, T&&)    set1.insert(set1.begin(), 1);    EXPECT_EQ(expected_constructed, decompose_constructed);  }  {  // insert(hint, const T&)    set1.insert(set1.begin(), one);    EXPECT_EQ(expected_constructed, decompose_constructed);  }  {  // emplace(...)    set1.emplace(1);    EXPECT_EQ(expected_constructed, decompose_constructed);    set1.emplace("3");    expected_constructed += construct_three;    EXPECT_EQ(expected_constructed, decompose_constructed);    set1.emplace(one);    EXPECT_EQ(expected_constructed, decompose_constructed);    set1.emplace(three);    expected_constructed += construct_three;    EXPECT_EQ(expected_constructed, decompose_constructed);  }  {  // emplace_hint(...)    set1.emplace_hint(set1.begin(), 1);    EXPECT_EQ(expected_constructed, decompose_constructed);    set1.emplace_hint(set1.begin(), "3");    expected_constructed += construct_three;    EXPECT_EQ(expected_constructed, decompose_constructed);    set1.emplace_hint(set1.begin(), one);    EXPECT_EQ(expected_constructed, decompose_constructed);    set1.emplace_hint(set1.begin(), three);    expected_constructed += construct_three;    EXPECT_EQ(expected_constructed, decompose_constructed);  }}TEST(Table, Decompose) {  TestDecompose<DecomposeHash, DecomposeEq>(false);  struct TransparentHashIntOverload {    size_t operator()(DecomposeType a) const { return a.i; }    size_t operator()(int a) const { return a; }  };  struct TransparentEqIntOverload {    bool operator()(DecomposeType a, DecomposeType b) const {      return a.i == b.i;    }    bool operator()(DecomposeType a, int b) const { return a.i == b; }  };  TestDecompose<TransparentHashIntOverload, DecomposeEq>(true);  TestDecompose<TransparentHashIntOverload, TransparentEqIntOverload>(true);  TestDecompose<DecomposeHash, TransparentEqIntOverload>(true);}// Returns the largest m such that a table with m elements has the same number// of buckets as a table with n elements.size_t MaxDensitySize(size_t n) {  IntTable t;  t.reserve(n);  for (size_t i = 0; i != n; ++i) t.emplace(i);  const size_t c = t.bucket_count();  while (c == t.bucket_count()) t.emplace(n++);  return t.size() - 1;}struct Modulo1000Hash {  size_t operator()(int x) const { return x % 1000; }};struct Modulo1000HashTable    : public raw_hash_set<IntPolicy, Modulo1000Hash, std::equal_to<int>,                          std::allocator<int>> {};// Test that rehash with no resize happen in case of many deleted slots.TEST(Table, RehashWithNoResize) {  Modulo1000HashTable t;  // Adding the same length (and the same hash) strings  // to have at least kMinFullGroups groups  // with Group::kWidth collisions. Then fill up to MaxDensitySize;  const size_t kMinFullGroups = 7;  std::vector<int> keys;  for (size_t i = 0; i < MaxDensitySize(Group::kWidth * kMinFullGroups); ++i) {    int k = i * 1000;    t.emplace(k);    keys.push_back(k);  }  const size_t capacity = t.capacity();  // Remove elements from all groups except the first and the last one.  // All elements removed from full groups will be marked as kDeleted.  const size_t erase_begin = Group::kWidth / 2;  const size_t erase_end = (t.size() / Group::kWidth - 1) * Group::kWidth;  for (size_t i = erase_begin; i < erase_end; ++i) {    EXPECT_EQ(1, t.erase(keys[i])) << i;  }  keys.erase(keys.begin() + erase_begin, keys.begin() + erase_end);  auto last_key = keys.back();  size_t last_key_num_probes = GetHashtableDebugNumProbes(t, last_key);  // Make sure that we have to make a lot of probes for last key.  ASSERT_GT(last_key_num_probes, kMinFullGroups);  int x = 1;  // Insert and erase one element, before inplace rehash happen.  while (last_key_num_probes == GetHashtableDebugNumProbes(t, last_key)) {    t.emplace(x);    ASSERT_EQ(capacity, t.capacity());    // All elements should be there.    ASSERT_TRUE(t.find(x) != t.end()) << x;    for (const auto& k : keys) {      ASSERT_TRUE(t.find(k) != t.end()) << k;    }    t.erase(x);    ++x;  }}TEST(Table, InsertEraseStressTest) {  IntTable t;  const size_t kMinElementCount = 250;  std::deque<int> keys;  size_t i = 0;  for (; i < MaxDensitySize(kMinElementCount); ++i) {    t.emplace(i);    keys.push_back(i);  }  const size_t kNumIterations = 1000000;  for (; i < kNumIterations; ++i) {    ASSERT_EQ(1, t.erase(keys.front()));    keys.pop_front();    t.emplace(i);    keys.push_back(i);  }}TEST(Table, InsertOverloads) {  StringTable t;  // These should all trigger the insert(init_type) overload.  t.insert({{}, {}});  t.insert({"ABC", {}});  t.insert({"DEF", "!!!"});  EXPECT_THAT(t, UnorderedElementsAre(Pair("", ""), Pair("ABC", ""),                                      Pair("DEF", "!!!")));}TEST(Table, LargeTable) {  IntTable t;  for (int64_t i = 0; i != 100000; ++i) t.emplace(i << 40);  for (int64_t i = 0; i != 100000; ++i) ASSERT_EQ(i << 40, *t.find(i << 40));}// Timeout if copy is quadratic as it was in Rust.TEST(Table, EnsureNonQuadraticAsInRust) {  static const size_t kLargeSize = 1 << 15;  IntTable t;  for (size_t i = 0; i != kLargeSize; ++i) {    t.insert(i);  }  // If this is quadratic, the test will timeout.  IntTable t2;  for (const auto& entry : t) t2.insert(entry);}TEST(Table, ClearBug) {  IntTable t;  constexpr size_t capacity = container_internal::Group::kWidth - 1;  constexpr size_t max_size = capacity / 2 + 1;  for (size_t i = 0; i < max_size; ++i) {    t.insert(i);  }  ASSERT_EQ(capacity, t.capacity());  intptr_t original = reinterpret_cast<intptr_t>(&*t.find(2));  t.clear();  ASSERT_EQ(capacity, t.capacity());  for (size_t i = 0; i < max_size; ++i) {    t.insert(i);  }  ASSERT_EQ(capacity, t.capacity());  intptr_t second = reinterpret_cast<intptr_t>(&*t.find(2));  // We are checking that original and second are close enough to each other  // that they are probably still in the same group.  This is not strictly  // guaranteed.  EXPECT_LT(std::abs(original - second),            capacity * sizeof(IntTable::value_type));}TEST(Table, Erase) {  IntTable t;  EXPECT_TRUE(t.find(0) == t.end());  auto res = t.emplace(0);  EXPECT_TRUE(res.second);  EXPECT_EQ(1, t.size());  t.erase(res.first);  EXPECT_EQ(0, t.size());  EXPECT_TRUE(t.find(0) == t.end());}TEST(Table, EraseMaintainsValidIterator) {  IntTable t;  const int kNumElements = 100;  for (int i = 0; i < kNumElements; i ++) {    EXPECT_TRUE(t.emplace(i).second);  }  EXPECT_EQ(t.size(), kNumElements);  int num_erase_calls = 0;  auto it = t.begin();  while (it != t.end()) {    t.erase(it++);    num_erase_calls++;  }  EXPECT_TRUE(t.empty());  EXPECT_EQ(num_erase_calls, kNumElements);}// Collect N bad keys by following algorithm:// 1. Create an empty table and reserve it to 2 * N.// 2. Insert N random elements.// 3. Take first Group::kWidth - 1 to bad_keys array.// 4. Clear the table without resize.// 5. Go to point 2 while N keys not collectedstd::vector<int64_t> CollectBadMergeKeys(size_t N) {  static constexpr int kGroupSize = Group::kWidth - 1;  auto topk_range = [](size_t b, size_t e, IntTable* t) -> std::vector<int64_t> {    for (size_t i = b; i != e; ++i) {      t->emplace(i);    }    std::vector<int64_t> res;    res.reserve(kGroupSize);    auto it = t->begin();    for (size_t i = b; i != e && i != b + kGroupSize; ++i, ++it) {      res.push_back(*it);    }    return res;  };  std::vector<int64_t> bad_keys;  bad_keys.reserve(N);  IntTable t;  t.reserve(N * 2);  for (size_t b = 0; bad_keys.size() < N; b += N) {    auto keys = topk_range(b, b + N, &t);    bad_keys.insert(bad_keys.end(), keys.begin(), keys.end());    t.erase(t.begin(), t.end());    EXPECT_TRUE(t.empty());  }  return bad_keys;}struct ProbeStats {  // Number of elements with specific probe length over all tested tables.  std::vector<size_t> all_probes_histogram;  // Ratios total_probe_length/size for every tested table.  std::vector<double> single_table_ratios;  friend ProbeStats operator+(const ProbeStats& a, const ProbeStats& b) {    ProbeStats res = a;    res.all_probes_histogram.resize(std::max(res.all_probes_histogram.size(),                                             b.all_probes_histogram.size()));    std::transform(b.all_probes_histogram.begin(), b.all_probes_histogram.end(),                   res.all_probes_histogram.begin(),                   res.all_probes_histogram.begin(), std::plus<size_t>());    res.single_table_ratios.insert(res.single_table_ratios.end(),                                   b.single_table_ratios.begin(),                                   b.single_table_ratios.end());    return res;  }  // Average ratio total_probe_length/size over tables.  double AvgRatio() const {    return std::accumulate(single_table_ratios.begin(),                           single_table_ratios.end(), 0.0) /           single_table_ratios.size();  }  // Maximum ratio total_probe_length/size over tables.  double MaxRatio() const {    return *std::max_element(single_table_ratios.begin(),                             single_table_ratios.end());  }  // Percentile ratio total_probe_length/size over tables.  double PercentileRatio(double Percentile = 0.95) const {    auto r = single_table_ratios;    auto mid = r.begin() + static_cast<size_t>(r.size() * Percentile);    if (mid != r.end()) {      std::nth_element(r.begin(), mid, r.end());      return *mid;    } else {      return MaxRatio();    }  }  // Maximum probe length over all elements and all tables.  size_t MaxProbe() const { return all_probes_histogram.size(); }  // Fraction of elements with specified probe length.  std::vector<double> ProbeNormalizedHistogram() const {    double total_elements = std::accumulate(all_probes_histogram.begin(),                                            all_probes_histogram.end(), 0ull);    std::vector<double> res;    for (size_t p : all_probes_histogram) {      res.push_back(p / total_elements);    }    return res;  }  size_t PercentileProbe(double Percentile = 0.99) const {    size_t idx = 0;    for (double p : ProbeNormalizedHistogram()) {      if (Percentile > p) {        Percentile -= p;        ++idx;      } else {        return idx;      }    }    return idx;  }  friend std::ostream& operator<<(std::ostream& out, const ProbeStats& s) {    out << "{AvgRatio:" << s.AvgRatio() << ", MaxRatio:" << s.MaxRatio()        << ", PercentileRatio:" << s.PercentileRatio()        << ", MaxProbe:" << s.MaxProbe() << ", Probes=[";    for (double p : s.ProbeNormalizedHistogram()) {      out << p << ",";    }    out << "]}";    return out;  }};struct ExpectedStats {  double avg_ratio;  double max_ratio;  std::vector<std::pair<double, double>> pecentile_ratios;  std::vector<std::pair<double, double>> pecentile_probes;  friend std::ostream& operator<<(std::ostream& out, const ExpectedStats& s) {    out << "{AvgRatio:" << s.avg_ratio << ", MaxRatio:" << s.max_ratio        << ", PercentileRatios: [";    for (auto el : s.pecentile_ratios) {      out << el.first << ":" << el.second << ", ";    }    out << "], PercentileProbes: [";    for (auto el : s.pecentile_probes) {      out << el.first << ":" << el.second << ", ";    }    out << "]}";    return out;  }};void VerifyStats(size_t size, const ExpectedStats& exp,                 const ProbeStats& stats) {  EXPECT_LT(stats.AvgRatio(), exp.avg_ratio) << size << " " << stats;  EXPECT_LT(stats.MaxRatio(), exp.max_ratio) << size << " " << stats;  for (auto pr : exp.pecentile_ratios) {    EXPECT_LE(stats.PercentileRatio(pr.first), pr.second)        << size << " " << pr.first << " " << stats;  }  for (auto pr : exp.pecentile_probes) {    EXPECT_LE(stats.PercentileProbe(pr.first), pr.second)        << size << " " << pr.first << " " << stats;  }}using ProbeStatsPerSize = std::map<size_t, ProbeStats>;// Collect total ProbeStats on num_iters iterations of the following algorithm:// 1. Create new table and reserve it to keys.size() * 2// 2. Insert all keys xored with seed// 3. Collect ProbeStats from final table.ProbeStats CollectProbeStatsOnKeysXoredWithSeed(const std::vector<int64_t>& keys,                                                size_t num_iters) {  const size_t reserve_size = keys.size() * 2;  ProbeStats stats;  int64_t seed = 0x71b1a19b907d6e33;  while (num_iters--) {    seed = static_cast<int64_t>(static_cast<uint64_t>(seed) * 17 + 13);    IntTable t1;    t1.reserve(reserve_size);    for (const auto& key : keys) {      t1.emplace(key ^ seed);    }    auto probe_histogram = GetHashtableDebugNumProbesHistogram(t1);    stats.all_probes_histogram.resize(        std::max(stats.all_probes_histogram.size(), probe_histogram.size()));    std::transform(probe_histogram.begin(), probe_histogram.end(),                   stats.all_probes_histogram.begin(),                   stats.all_probes_histogram.begin(), std::plus<size_t>());    size_t total_probe_seq_length = 0;    for (size_t i = 0; i < probe_histogram.size(); ++i) {      total_probe_seq_length += i * probe_histogram[i];    }    stats.single_table_ratios.push_back(total_probe_seq_length * 1.0 /                                        keys.size());    t1.erase(t1.begin(), t1.end());  }  return stats;}ExpectedStats XorSeedExpectedStats() {  constexpr bool kRandomizesInserts =#ifdef NDEBUG      false;#else   // NDEBUG      true;#endif  // NDEBUG  // The effective load factor is larger in non-opt mode because we insert  // elements out of order.  switch (container_internal::Group::kWidth) {    case 8:      if (kRandomizesInserts) {  return {0.05,          1.0,          {{0.95, 0.5}},          {{0.95, 0}, {0.99, 2}, {0.999, 4}, {0.9999, 10}}};      } else {  return {0.05,          2.0,          {{0.95, 0.1}},          {{0.95, 0}, {0.99, 2}, {0.999, 4}, {0.9999, 10}}};      }    case 16:      if (kRandomizesInserts) {        return {0.1,                1.0,                {{0.95, 0.1}},                {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}};      } else {        return {0.05,                1.0,                {{0.95, 0.05}},                {{0.95, 0}, {0.99, 1}, {0.999, 4}, {0.9999, 10}}};      }  }  ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width");  return {};}TEST(Table, DISABLED_EnsureNonQuadraticTopNXorSeedByProbeSeqLength) {  ProbeStatsPerSize stats;  std::vector<size_t> sizes = {Group::kWidth << 5, Group::kWidth << 10};  for (size_t size : sizes) {    stats[size] =        CollectProbeStatsOnKeysXoredWithSeed(CollectBadMergeKeys(size), 200);  }  auto expected = XorSeedExpectedStats();  for (size_t size : sizes) {    auto& stat = stats[size];    VerifyStats(size, expected, stat);  }}// Collect total ProbeStats on num_iters iterations of the following algorithm:// 1. Create new table// 2. Select 10% of keys and insert 10 elements key * 17 + j * 13// 3. Collect ProbeStats from final tableProbeStats CollectProbeStatsOnLinearlyTransformedKeys(    const std::vector<int64_t>& keys, size_t num_iters) {  ProbeStats stats;  std::random_device rd;  std::mt19937 rng(rd());  auto linear_transform = [](size_t x, size_t y) { return x * 17 + y * 13; };  std::uniform_int_distribution<size_t> dist(0, keys.size()-1);  while (num_iters--) {    IntTable t1;    size_t num_keys = keys.size() / 10;    size_t start = dist(rng);    for (size_t i = 0; i != num_keys; ++i) {      for (size_t j = 0; j != 10; ++j) {        t1.emplace(linear_transform(keys[(i + start) % keys.size()], j));      }    }    auto probe_histogram = GetHashtableDebugNumProbesHistogram(t1);    stats.all_probes_histogram.resize(        std::max(stats.all_probes_histogram.size(), probe_histogram.size()));    std::transform(probe_histogram.begin(), probe_histogram.end(),                   stats.all_probes_histogram.begin(),                   stats.all_probes_histogram.begin(), std::plus<size_t>());    size_t total_probe_seq_length = 0;    for (size_t i = 0; i < probe_histogram.size(); ++i) {      total_probe_seq_length += i * probe_histogram[i];    }    stats.single_table_ratios.push_back(total_probe_seq_length * 1.0 /                                        t1.size());    t1.erase(t1.begin(), t1.end());  }  return stats;}ExpectedStats LinearTransformExpectedStats() {  constexpr bool kRandomizesInserts =#ifdef NDEBUG      false;#else   // NDEBUG      true;#endif  // NDEBUG  // The effective load factor is larger in non-opt mode because we insert  // elements out of order.  switch (container_internal::Group::kWidth) {    case 8:      if (kRandomizesInserts) {        return {0.1,                0.5,                {{0.95, 0.3}},                {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}};      } else {        return {0.15,                0.5,                {{0.95, 0.3}},                {{0.95, 0}, {0.99, 3}, {0.999, 15}, {0.9999, 25}}};      }    case 16:      if (kRandomizesInserts) {        return {0.1,                0.4,                {{0.95, 0.3}},                {{0.95, 0}, {0.99, 1}, {0.999, 8}, {0.9999, 15}}};      } else {        return {0.05,                0.2,                {{0.95, 0.1}},                {{0.95, 0}, {0.99, 1}, {0.999, 6}, {0.9999, 10}}};      }  }  ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width");  return {};}TEST(Table, DISABLED_EnsureNonQuadraticTopNLinearTransformByProbeSeqLength) {  ProbeStatsPerSize stats;  std::vector<size_t> sizes = {Group::kWidth << 5, Group::kWidth << 10};  for (size_t size : sizes) {    stats[size] = CollectProbeStatsOnLinearlyTransformedKeys(        CollectBadMergeKeys(size), 300);  }  auto expected = LinearTransformExpectedStats();  for (size_t size : sizes) {    auto& stat = stats[size];    VerifyStats(size, expected, stat);  }}TEST(Table, EraseCollision) {  BadTable t;  // 1 2 3  t.emplace(1);  t.emplace(2);  t.emplace(3);  EXPECT_THAT(*t.find(1), 1);  EXPECT_THAT(*t.find(2), 2);  EXPECT_THAT(*t.find(3), 3);  EXPECT_EQ(3, t.size());  // 1 DELETED 3  t.erase(t.find(2));  EXPECT_THAT(*t.find(1), 1);  EXPECT_TRUE(t.find(2) == t.end());  EXPECT_THAT(*t.find(3), 3);  EXPECT_EQ(2, t.size());  // DELETED DELETED 3  t.erase(t.find(1));  EXPECT_TRUE(t.find(1) == t.end());  EXPECT_TRUE(t.find(2) == t.end());  EXPECT_THAT(*t.find(3), 3);  EXPECT_EQ(1, t.size());  // DELETED DELETED DELETED  t.erase(t.find(3));  EXPECT_TRUE(t.find(1) == t.end());  EXPECT_TRUE(t.find(2) == t.end());  EXPECT_TRUE(t.find(3) == t.end());  EXPECT_EQ(0, t.size());}TEST(Table, EraseInsertProbing) {  BadTable t(100);  // 1 2 3 4  t.emplace(1);  t.emplace(2);  t.emplace(3);  t.emplace(4);  // 1 DELETED 3 DELETED  t.erase(t.find(2));  t.erase(t.find(4));  // 1 10 3 11 12  t.emplace(10);  t.emplace(11);  t.emplace(12);  EXPECT_EQ(5, t.size());  EXPECT_THAT(t, UnorderedElementsAre(1, 10, 3, 11, 12));}TEST(Table, Clear) {  IntTable t;  EXPECT_TRUE(t.find(0) == t.end());  t.clear();  EXPECT_TRUE(t.find(0) == t.end());  auto res = t.emplace(0);  EXPECT_TRUE(res.second);  EXPECT_EQ(1, t.size());  t.clear();  EXPECT_EQ(0, t.size());  EXPECT_TRUE(t.find(0) == t.end());}TEST(Table, Swap) {  IntTable t;  EXPECT_TRUE(t.find(0) == t.end());  auto res = t.emplace(0);  EXPECT_TRUE(res.second);  EXPECT_EQ(1, t.size());  IntTable u;  t.swap(u);  EXPECT_EQ(0, t.size());  EXPECT_EQ(1, u.size());  EXPECT_TRUE(t.find(0) == t.end());  EXPECT_THAT(*u.find(0), 0);}TEST(Table, Rehash) {  IntTable t;  EXPECT_TRUE(t.find(0) == t.end());  t.emplace(0);  t.emplace(1);  EXPECT_EQ(2, t.size());  t.rehash(128);  EXPECT_EQ(2, t.size());  EXPECT_THAT(*t.find(0), 0);  EXPECT_THAT(*t.find(1), 1);}TEST(Table, RehashDoesNotRehashWhenNotNecessary) {  IntTable t;  t.emplace(0);  t.emplace(1);  auto* p = &*t.find(0);  t.rehash(1);  EXPECT_EQ(p, &*t.find(0));}TEST(Table, RehashZeroDoesNotAllocateOnEmptyTable) {  IntTable t;  t.rehash(0);  EXPECT_EQ(0, t.bucket_count());}TEST(Table, RehashZeroDeallocatesEmptyTable) {  IntTable t;  t.emplace(0);  t.clear();  EXPECT_NE(0, t.bucket_count());  t.rehash(0);  EXPECT_EQ(0, t.bucket_count());}TEST(Table, RehashZeroForcesRehash) {  IntTable t;  t.emplace(0);  t.emplace(1);  auto* p = &*t.find(0);  t.rehash(0);  EXPECT_NE(p, &*t.find(0));}TEST(Table, ConstructFromInitList) {  using P = std::pair<std::string, std::string>;  struct Q {    operator P() const { return {}; }  };  StringTable t = {P(), Q(), {}, {{}, {}}};}TEST(Table, CopyConstruct) {  IntTable t;  t.emplace(0);  EXPECT_EQ(1, t.size());  {    IntTable u(t);    EXPECT_EQ(1, u.size());    EXPECT_THAT(*u.find(0), 0);  }  {    IntTable u{t};    EXPECT_EQ(1, u.size());    EXPECT_THAT(*u.find(0), 0);  }  {    IntTable u = t;    EXPECT_EQ(1, u.size());    EXPECT_THAT(*u.find(0), 0);  }}TEST(Table, CopyConstructWithAlloc) {  StringTable t;  t.emplace("a", "b");  EXPECT_EQ(1, t.size());  StringTable u(t, Alloc<std::pair<std::string, std::string>>());  EXPECT_EQ(1, u.size());  EXPECT_THAT(*u.find("a"), Pair("a", "b"));}struct ExplicitAllocIntTable    : raw_hash_set<IntPolicy, container_internal::hash_default_hash<int64_t>,                   std::equal_to<int64_t>, Alloc<int64_t>> {  ExplicitAllocIntTable() {}};TEST(Table, AllocWithExplicitCtor) {  ExplicitAllocIntTable t;  EXPECT_EQ(0, t.size());}TEST(Table, MoveConstruct) {  {    StringTable t;    t.emplace("a", "b");    EXPECT_EQ(1, t.size());    StringTable u(std::move(t));    EXPECT_EQ(1, u.size());    EXPECT_THAT(*u.find("a"), Pair("a", "b"));  }  {    StringTable t;    t.emplace("a", "b");    EXPECT_EQ(1, t.size());    StringTable u{std::move(t)};    EXPECT_EQ(1, u.size());    EXPECT_THAT(*u.find("a"), Pair("a", "b"));  }  {    StringTable t;    t.emplace("a", "b");    EXPECT_EQ(1, t.size());    StringTable u = std::move(t);    EXPECT_EQ(1, u.size());    EXPECT_THAT(*u.find("a"), Pair("a", "b"));  }}TEST(Table, MoveConstructWithAlloc) {  StringTable t;  t.emplace("a", "b");  EXPECT_EQ(1, t.size());  StringTable u(std::move(t), Alloc<std::pair<std::string, std::string>>());  EXPECT_EQ(1, u.size());  EXPECT_THAT(*u.find("a"), Pair("a", "b"));}TEST(Table, CopyAssign) {  StringTable t;  t.emplace("a", "b");  EXPECT_EQ(1, t.size());  StringTable u;  u = t;  EXPECT_EQ(1, u.size());  EXPECT_THAT(*u.find("a"), Pair("a", "b"));}TEST(Table, CopySelfAssign) {  StringTable t;  t.emplace("a", "b");  EXPECT_EQ(1, t.size());  t = *&t;  EXPECT_EQ(1, t.size());  EXPECT_THAT(*t.find("a"), Pair("a", "b"));}TEST(Table, MoveAssign) {  StringTable t;  t.emplace("a", "b");  EXPECT_EQ(1, t.size());  StringTable u;  u = std::move(t);  EXPECT_EQ(1, u.size());  EXPECT_THAT(*u.find("a"), Pair("a", "b"));}TEST(Table, Equality) {  StringTable t;  std::vector<std::pair<std::string, std::string>> v = {{"a", "b"},                                                        {"aa", "bb"}};  t.insert(std::begin(v), std::end(v));  StringTable u = t;  EXPECT_EQ(u, t);}TEST(Table, Equality2) {  StringTable t;  std::vector<std::pair<std::string, std::string>> v1 = {{"a", "b"},                                                         {"aa", "bb"}};  t.insert(std::begin(v1), std::end(v1));  StringTable u;  std::vector<std::pair<std::string, std::string>> v2 = {{"a", "a"},                                                         {"aa", "aa"}};  u.insert(std::begin(v2), std::end(v2));  EXPECT_NE(u, t);}TEST(Table, Equality3) {  StringTable t;  std::vector<std::pair<std::string, std::string>> v1 = {{"b", "b"},                                                         {"bb", "bb"}};  t.insert(std::begin(v1), std::end(v1));  StringTable u;  std::vector<std::pair<std::string, std::string>> v2 = {{"a", "a"},                                                         {"aa", "aa"}};  u.insert(std::begin(v2), std::end(v2));  EXPECT_NE(u, t);}TEST(Table, NumDeletedRegression) {  IntTable t;  t.emplace(0);  t.erase(t.find(0));  // construct over a deleted slot.  t.emplace(0);  t.clear();}TEST(Table, FindFullDeletedRegression) {  IntTable t;  for (int i = 0; i < 1000; ++i) {    t.emplace(i);    t.erase(t.find(i));  }  EXPECT_EQ(0, t.size());}TEST(Table, ReplacingDeletedSlotDoesNotRehash) {  size_t n;  {    // Compute n such that n is the maximum number of elements before rehash.    IntTable t;    t.emplace(0);    size_t c = t.bucket_count();    for (n = 1; c == t.bucket_count(); ++n) t.emplace(n);    --n;  }  IntTable t;  t.rehash(n);  const size_t c = t.bucket_count();  for (size_t i = 0; i != n; ++i) t.emplace(i);  EXPECT_EQ(c, t.bucket_count()) << "rehashing threshold = " << n;  t.erase(0);  t.emplace(0);  EXPECT_EQ(c, t.bucket_count()) << "rehashing threshold = " << n;}TEST(Table, NoThrowMoveConstruct) {  ASSERT_TRUE(      std::is_nothrow_copy_constructible<absl::Hash<absl::string_view>>::value);  ASSERT_TRUE(std::is_nothrow_copy_constructible<              std::equal_to<absl::string_view>>::value);  ASSERT_TRUE(std::is_nothrow_copy_constructible<std::allocator<int>>::value);  EXPECT_TRUE(std::is_nothrow_move_constructible<StringTable>::value);}TEST(Table, NoThrowMoveAssign) {  ASSERT_TRUE(      std::is_nothrow_move_assignable<absl::Hash<absl::string_view>>::value);  ASSERT_TRUE(      std::is_nothrow_move_assignable<std::equal_to<absl::string_view>>::value);  ASSERT_TRUE(std::is_nothrow_move_assignable<std::allocator<int>>::value);  ASSERT_TRUE(      absl::allocator_traits<std::allocator<int>>::is_always_equal::value);  EXPECT_TRUE(std::is_nothrow_move_assignable<StringTable>::value);}TEST(Table, NoThrowSwappable) {  ASSERT_TRUE(      container_internal::IsNoThrowSwappable<absl::Hash<absl::string_view>>());  ASSERT_TRUE(container_internal::IsNoThrowSwappable<              std::equal_to<absl::string_view>>());  ASSERT_TRUE(container_internal::IsNoThrowSwappable<std::allocator<int>>());  EXPECT_TRUE(container_internal::IsNoThrowSwappable<StringTable>());}TEST(Table, HeterogeneousLookup) {  struct Hash {    size_t operator()(int64_t i) const { return i; }    size_t operator()(double i) const {      ADD_FAILURE();      return i;    }  };  struct Eq {    bool operator()(int64_t a, int64_t b) const { return a == b; }    bool operator()(double a, int64_t b) const {      ADD_FAILURE();      return a == b;    }    bool operator()(int64_t a, double b) const {      ADD_FAILURE();      return a == b;    }    bool operator()(double a, double b) const {      ADD_FAILURE();      return a == b;    }  };  struct THash {    using is_transparent = void;    size_t operator()(int64_t i) const { return i; }    size_t operator()(double i) const { return i; }  };  struct TEq {    using is_transparent = void;    bool operator()(int64_t a, int64_t b) const { return a == b; }    bool operator()(double a, int64_t b) const { return a == b; }    bool operator()(int64_t a, double b) const { return a == b; }    bool operator()(double a, double b) const { return a == b; }  };  raw_hash_set<IntPolicy, Hash, Eq, Alloc<int64_t>> s{0, 1, 2};  // It will convert to int64_t before the query.  EXPECT_EQ(1, *s.find(double{1.1}));  raw_hash_set<IntPolicy, THash, TEq, Alloc<int64_t>> ts{0, 1, 2};  // It will try to use the double, and fail to find the object.  EXPECT_TRUE(ts.find(1.1) == ts.end());}template <class Table>using CallFind = decltype(std::declval<Table&>().find(17));template <class Table>using CallErase = decltype(std::declval<Table&>().erase(17));template <class Table>using CallExtract = decltype(std::declval<Table&>().extract(17));template <class Table>using CallPrefetch = decltype(std::declval<Table&>().prefetch(17));template <class Table>using CallCount = decltype(std::declval<Table&>().count(17));template <template <typename> class C, class Table, class = void>struct VerifyResultOf : std::false_type {};template <template <typename> class C, class Table>struct VerifyResultOf<C, Table, absl::void_t<C<Table>>> : std::true_type {};TEST(Table, HeterogeneousLookupOverloads) {  using NonTransparentTable =      raw_hash_set<StringPolicy, absl::Hash<absl::string_view>,                   std::equal_to<absl::string_view>, std::allocator<int>>;  EXPECT_FALSE((VerifyResultOf<CallFind, NonTransparentTable>()));  EXPECT_FALSE((VerifyResultOf<CallErase, NonTransparentTable>()));  EXPECT_FALSE((VerifyResultOf<CallExtract, NonTransparentTable>()));  EXPECT_FALSE((VerifyResultOf<CallPrefetch, NonTransparentTable>()));  EXPECT_FALSE((VerifyResultOf<CallCount, NonTransparentTable>()));  using TransparentTable = raw_hash_set<      StringPolicy,      absl::container_internal::hash_default_hash<absl::string_view>,      absl::container_internal::hash_default_eq<absl::string_view>,      std::allocator<int>>;  EXPECT_TRUE((VerifyResultOf<CallFind, TransparentTable>()));  EXPECT_TRUE((VerifyResultOf<CallErase, TransparentTable>()));  EXPECT_TRUE((VerifyResultOf<CallExtract, TransparentTable>()));  EXPECT_TRUE((VerifyResultOf<CallPrefetch, TransparentTable>()));  EXPECT_TRUE((VerifyResultOf<CallCount, TransparentTable>()));}// TODO(alkis): Expand iterator tests.TEST(Iterator, IsDefaultConstructible) {  StringTable::iterator i;  EXPECT_TRUE(i == StringTable::iterator());}TEST(ConstIterator, IsDefaultConstructible) {  StringTable::const_iterator i;  EXPECT_TRUE(i == StringTable::const_iterator());}TEST(Iterator, ConvertsToConstIterator) {  StringTable::iterator i;  EXPECT_TRUE(i == StringTable::const_iterator());}TEST(Iterator, Iterates) {  IntTable t;  for (size_t i = 3; i != 6; ++i) EXPECT_TRUE(t.emplace(i).second);  EXPECT_THAT(t, UnorderedElementsAre(3, 4, 5));}TEST(Table, Merge) {  StringTable t1, t2;  t1.emplace("0", "-0");  t1.emplace("1", "-1");  t2.emplace("0", "~0");  t2.emplace("2", "~2");  EXPECT_THAT(t1, UnorderedElementsAre(Pair("0", "-0"), Pair("1", "-1")));  EXPECT_THAT(t2, UnorderedElementsAre(Pair("0", "~0"), Pair("2", "~2")));  t1.merge(t2);  EXPECT_THAT(t1, UnorderedElementsAre(Pair("0", "-0"), Pair("1", "-1"),                                       Pair("2", "~2")));  EXPECT_THAT(t2, UnorderedElementsAre(Pair("0", "~0")));}TEST(Nodes, EmptyNodeType) {  using node_type = StringTable::node_type;  node_type n;  EXPECT_FALSE(n);  EXPECT_TRUE(n.empty());  EXPECT_TRUE((std::is_same<node_type::allocator_type,                            StringTable::allocator_type>::value));}TEST(Nodes, ExtractInsert) {  constexpr char k0[] = "Very long std::string zero.";  constexpr char k1[] = "Very long std::string one.";  constexpr char k2[] = "Very long std::string two.";  StringTable t = {{k0, ""}, {k1, ""}, {k2, ""}};  EXPECT_THAT(t,              UnorderedElementsAre(Pair(k0, ""), Pair(k1, ""), Pair(k2, "")));  auto node = t.extract(k0);  EXPECT_THAT(t, UnorderedElementsAre(Pair(k1, ""), Pair(k2, "")));  EXPECT_TRUE(node);  EXPECT_FALSE(node.empty());  StringTable t2;  StringTable::insert_return_type res = t2.insert(std::move(node));  EXPECT_TRUE(res.inserted);  EXPECT_THAT(*res.position, Pair(k0, ""));  EXPECT_FALSE(res.node);  EXPECT_THAT(t2, UnorderedElementsAre(Pair(k0, "")));  // Not there.  EXPECT_THAT(t, UnorderedElementsAre(Pair(k1, ""), Pair(k2, "")));  node = t.extract("Not there!");  EXPECT_THAT(t, UnorderedElementsAre(Pair(k1, ""), Pair(k2, "")));  EXPECT_FALSE(node);  // Inserting nothing.  res = t2.insert(std::move(node));  EXPECT_FALSE(res.inserted);  EXPECT_EQ(res.position, t2.end());  EXPECT_FALSE(res.node);  EXPECT_THAT(t2, UnorderedElementsAre(Pair(k0, "")));  t.emplace(k0, "1");  node = t.extract(k0);  // Insert duplicate.  res = t2.insert(std::move(node));  EXPECT_FALSE(res.inserted);  EXPECT_THAT(*res.position, Pair(k0, ""));  EXPECT_TRUE(res.node);  EXPECT_FALSE(node);}IntTable MakeSimpleTable(size_t size) {  IntTable t;  while (t.size() < size) t.insert(t.size());  return t;}std::vector<int> OrderOfIteration(const IntTable& t) {  return {t.begin(), t.end()};}// These IterationOrderChanges tests depend on non-deterministic behavior.// We are injecting non-determinism from the pointer of the table, but do so in// a way that only the page matters. We have to retry enough times to make sure// we are touching different memory pages to cause the ordering to change.// We also need to keep the old tables around to avoid getting the same memory// blocks over and over.TEST(Table, IterationOrderChangesByInstance) {  for (size_t size : {2, 6, 12, 20}) {    const auto reference_table = MakeSimpleTable(size);    const auto reference = OrderOfIteration(reference_table);    std::vector<IntTable> tables;    bool found_difference = false;    for (int i = 0; !found_difference && i < 5000; ++i) {      tables.push_back(MakeSimpleTable(size));      found_difference = OrderOfIteration(tables.back()) != reference;    }    if (!found_difference) {      FAIL()          << "Iteration order remained the same across many attempts with size "          << size;    }  }}TEST(Table, IterationOrderChangesOnRehash) {  std::vector<IntTable> garbage;  for (int i = 0; i < 5000; ++i) {    auto t = MakeSimpleTable(20);    const auto reference = OrderOfIteration(t);    // Force rehash to the same size.    t.rehash(0);    auto trial = OrderOfIteration(t);    if (trial != reference) {      // We are done.      return;    }    garbage.push_back(std::move(t));  }  FAIL() << "Iteration order remained the same across many attempts.";}// Verify that pointers are invalidated as soon as a second element is inserted.// This prevents dependency on pointer stability on small tables.TEST(Table, UnstablePointers) {  IntTable table;  const auto addr = [&](int i) {    return reinterpret_cast<uintptr_t>(&*table.find(i));  };  table.insert(0);  const uintptr_t old_ptr = addr(0);  // This causes a rehash.  table.insert(1);  EXPECT_NE(old_ptr, addr(0));}// Confirm that we assert if we try to erase() end().TEST(TableDeathTest, EraseOfEndAsserts) {  // Use an assert with side-effects to figure out if they are actually enabled.  bool assert_enabled = false;  assert([&]() {    assert_enabled = true;    return true;  }());  if (!assert_enabled) return;  IntTable t;  // Extra simple "regexp" as regexp support is highly varied across platforms.  constexpr char kDeathMsg[] = "IsFull";  EXPECT_DEATH_IF_SUPPORTED(t.erase(t.end()), kDeathMsg);}#if ABSL_PER_THREAD_TLS == 1TEST(RawHashSamplerTest, Sample) {  // Enable the feature even if the prod default is off.  SetHashtablezEnabled(true);  SetHashtablezSampleParameter(100);  auto& sampler = HashtablezSampler::Global();  size_t start_size = 0;  start_size += sampler.Iterate([&](const HashtablezInfo&) { ++start_size; });  std::vector<IntTable> tables;  for (int i = 0; i < 1000000; ++i) {    tables.emplace_back();    tables.back().insert(1);  }  size_t end_size = 0;  end_size += sampler.Iterate([&](const HashtablezInfo&) { ++end_size; });  EXPECT_NEAR((end_size - start_size) / static_cast<double>(tables.size()),              0.01, 0.005);}#endifTEST(RawHashSamplerTest, DoNotSampleCustomAllocators) {  // Enable the feature even if the prod default is off.  SetHashtablezEnabled(true);  SetHashtablezSampleParameter(100);  auto& sampler = HashtablezSampler::Global();  size_t start_size = 0;  start_size += sampler.Iterate([&](const HashtablezInfo&) { ++start_size; });  std::vector<CustomAllocIntTable> tables;  for (int i = 0; i < 1000000; ++i) {    tables.emplace_back();    tables.back().insert(1);  }  size_t end_size = 0;  end_size += sampler.Iterate([&](const HashtablezInfo&) { ++end_size; });  EXPECT_NEAR((end_size - start_size) / static_cast<double>(tables.size()),              0.00, 0.001);}#ifdef ADDRESS_SANITIZERTEST(Sanitizer, PoisoningUnused) {  IntTable t;  t.reserve(5);  // Insert something to force an allocation.  int64_t& v1 = *t.insert(0).first;  // Make sure there is something to test.  ASSERT_GT(t.capacity(), 1);  int64_t* slots = RawHashSetTestOnlyAccess::GetSlots(t);  for (size_t i = 0; i < t.capacity(); ++i) {    EXPECT_EQ(slots + i != &v1, __asan_address_is_poisoned(slots + i));  }}TEST(Sanitizer, PoisoningOnErase) {  IntTable t;  int64_t& v = *t.insert(0).first;  EXPECT_FALSE(__asan_address_is_poisoned(&v));  t.erase(0);  EXPECT_TRUE(__asan_address_is_poisoned(&v));}#endif  // ADDRESS_SANITIZER}  // namespace}  // namespace container_internal}  // namespace absl
 |