std::true_type /* propagate_on_container_swap */) {

using std::swap;

swap(lhs, rhs);

{

probe_seq(size_t hashval, size_t mask) {

assert(((mask + 1) & mask) == 0 && "not a mask");

mask_ = mask;

offset_ = hashval & mask_;

}

size_t offset() const { return offset_; }

size_t offset(size_t i) const { return (offset_ + i) & mask_; }

void next() {

index_ += Width;

offset_ += index_;

offset_ &= mask_;

}

// 0-based probe index. The i-th probe in the probe sequence.

size_t getindex() const { return index_; }

size_t mask_;

size_t offset_;

size_t index_ = 0;

{

template <class PassedKey, class... Args>

std::pair<

decltype(std::declval<const Hash&>()(std::declval<const PassedKey&>())),

decltype(std::declval<const Eq&>()(std::declval<const ContainerKey&>(),

std::declval<const PassedKey&>()))>*

operator()(const PassedKey&, const Args&...) const;

PHMAP_IF_CONSTEXPR(sizeof(T) == 8)

return base_internal::CountTrailingZerosNonZero64(static_cast<uint64_t>(x));

else

return base_internal::CountTrailingZerosNonZero32(static_cast<uint32_t>(x));

PHMAP_IF_CONSTEXPR(sizeof(T) == 8)

return base_internal::CountLeadingZeros64(static_cast<uint64_t>(x));

else

return base_internal::CountLeadingZeros32(static_cast<uint32_t>(x));

{

static_assert(std::is_unsigned<T>::value, "");

static_assert(Shift == 0 || Shift == 3, "");

// These are useful for unit tests (gunit).

using value_type = int;

using iterator = BitMask;

using const_iterator = BitMask;

explicit BitMask(T mask) : mask_(mask) {}

BitMask& operator++() { // ++iterator

mask_ &= (mask_ - 1); // clear the least significant bit set

return *this;

}

explicit operator bool() const { return mask_ != 0; }

uint32_t operator*() const { return LowestBitSet(); }

uint32_t LowestBitSet() const {

return priv::TrailingZeros(mask_) >> Shift;

}

uint32_t HighestBitSet() const {

return (sizeof(T) * CHAR_BIT - priv::LeadingZeros(mask_) - 1) >> Shift;

}

BitMask begin() const { return *this; }

BitMask end() const { return BitMask(0); }

uint32_t TrailingZeros() const {

return priv::TrailingZeros(mask_) >> Shift;

}

uint32_t LeadingZeros() const {

constexpr uint32_t total_significant_bits = SignificantBits << Shift;

constexpr uint32_t extra_bits = sizeof(T) * 8 - total_significant_bits;

return priv::LeadingZeros(mask_ << extra_bits) >> Shift;

}

friend bool operator==(const BitMask& a, const BitMask& b) {

return a.mask_ == b.mask_;

}

friend bool operator!=(const BitMask& a, const BitMask& b) {

return a.mask_ != b.mask_;

}

T mask_;

{

kEmpty = -128, // 0b10000000 or 0x80

kDeleted = -2, // 0b11111110 or 0xfe

kSentinel = -1, // 0b11111111 or 0xff

// The low bits of the pointer have little or no entropy because of

// alignment. We shift the pointer to try to use higher entropy bits. A

// good number seems to be 12 bits, because that aligns with page size.

return reinterpret_cast<uintptr_t>(ctrl) >> 12;

// use ctrl_ pointer to add entropy to ensure

// non-deterministic iteration order.

return (hashval >> 7) ^ HashSeed(ctrl);

#if defined(__GNUC__) && !defined(__clang__)

#pragma GCC diagnostic push

#pragma GCC diagnostic ignored "-Woverflow"

if (std::is_unsigned<char>::value) {

const __m128i mask = _mm_set1_epi8(static_cast<char>(0x80));

const __m128i diff = _mm_subs_epi8(b, a);

return _mm_cmpeq_epi8(_mm_and_si128(diff, mask), mask);

}

#pragma GCC diagnostic pop

#endif

return _mm_cmpgt_epi8(a, b);

{

enum { kWidth = 16 }; // the number of slots per group

explicit GroupSse2Impl(const ctrl_t* pos) {

ctrl = _mm_loadu_si128(reinterpret_cast<const __m128i*>(pos));

}

// Returns a bitmask representing the positions of slots that match hash.

// ----------------------------------------------------------------------

BitMask<uint32_t, kWidth> Match(h2_t hash) const {

auto match = _mm_set1_epi8((char)hash);

return BitMask<uint32_t, kWidth>(

static_cast<uint32_t>(_mm_movemask_epi8(_mm_cmpeq_epi8(match, ctrl))));

}

// Returns a bitmask representing the positions of empty slots.

// ------------------------------------------------------------

BitMask<uint32_t, kWidth> MatchEmpty() const {

#if PHMAP_HAVE_SSSE3

// This only works because kEmpty is -128.

return BitMask<uint32_t, kWidth>(

static_cast<uint32_t>(_mm_movemask_epi8(_mm_sign_epi8(ctrl, ctrl))));

#else

return Match(static_cast<h2_t>(kEmpty));

#endif

}

#ifdef __INTEL_COMPILER

#pragma warning push

#pragma warning disable 68

#endif

// Returns a bitmask representing the positions of empty or deleted slots.

// -----------------------------------------------------------------------

BitMask<uint32_t, kWidth> MatchEmptyOrDeleted() const {

auto special = _mm_set1_epi8(static_cast<uint8_t>(kSentinel));

return BitMask<uint32_t, kWidth>(

static_cast<uint32_t>(_mm_movemask_epi8(_mm_cmpgt_epi8_fixed(special, ctrl))));

}

// Returns the number of trailing empty or deleted elements in the group.

// ----------------------------------------------------------------------

uint32_t CountLeadingEmptyOrDeleted() const {

auto special = _mm_set1_epi8(static_cast<uint8_t>(kSentinel));

return TrailingZeros(

static_cast<uint32_t>(_mm_movemask_epi8(_mm_cmpgt_epi8_fixed(special, ctrl)) + 1));

}

#ifdef __INTEL_COMPILER

#pragma warning pop

#endif

// ----------------------------------------------------------------------

void ConvertSpecialToEmptyAndFullToDeleted(ctrl_t* dst) const {

auto msbs = _mm_set1_epi8(static_cast<char>(-128));

auto x126 = _mm_set1_epi8(126);

#if PHMAP_HAVE_SSSE3

auto res = _mm_or_si128(_mm_shuffle_epi8(x126, ctrl), msbs);

#else

auto zero = _mm_setzero_si128();

auto special_mask = _mm_cmpgt_epi8_fixed(zero, ctrl);

auto res = _mm_or_si128(msbs, _mm_andnot_si128(special_mask, x126));

#endif

_mm_storeu_si128(reinterpret_cast<__m128i*>(dst), res);

}

__m128i ctrl;

{

enum { kWidth = 8 };

explicit GroupPortableImpl(const ctrl_t* pos)

: ctrl(little_endian::Load64(pos)) {}

BitMask<uint64_t, kWidth, 3> Match(h2_t hash) const {

// For the technique, see:

// http://graphics.stanford.edu/~seander/bithacks.html##ValueInWord

// (Determine if a word has a byte equal to n).

//

// Caveat: there are false positives but:

// - they only occur if there is a real match

// - they never occur on kEmpty, kDeleted, kSentinel

// - they will be handled gracefully by subsequent checks in code

//

// Example:

// v = 0x1716151413121110

// hash = 0x12

// retval = (v - lsbs) & ~v & msbs = 0x0000000080800000

constexpr uint64_t msbs = 0x8080808080808080ULL;

constexpr uint64_t lsbs = 0x0101010101010101ULL;

auto x = ctrl ^ (lsbs * hash);

return BitMask<uint64_t, kWidth, 3>((x - lsbs) & ~x & msbs);

}

BitMask<uint64_t, kWidth, 3> MatchEmpty() const { // bit 1 of each byte is 0 for empty (but not for deleted)

constexpr uint64_t msbs = 0x8080808080808080ULL;

return BitMask<uint64_t, kWidth, 3>((ctrl & (~ctrl << 6)) & msbs);

}

BitMask<uint64_t, kWidth, 3> MatchEmptyOrDeleted() const { // lsb of each byte is 0 for empty or deleted

constexpr uint64_t msbs = 0x8080808080808080ULL;

return BitMask<uint64_t, kWidth, 3>((ctrl & (~ctrl << 7)) & msbs);

}

uint32_t CountLeadingEmptyOrDeleted() const {

constexpr uint64_t gaps = 0x00FEFEFEFEFEFEFEULL;

return (uint32_t)((TrailingZeros(((~ctrl & (ctrl >> 7)) | gaps) + 1) + 7) >> 3);

}

void ConvertSpecialToEmptyAndFullToDeleted(ctrl_t* dst) const {

constexpr uint64_t msbs = 0x8080808080808080ULL;

constexpr uint64_t lsbs = 0x0101010101010101ULL;

auto x = ctrl & msbs;

auto res = (~x + (x >> 7)) & ~lsbs;

little_endian::Store64(dst, res);

}

uint64_t ctrl;

ctrl_t* ctrl, size_t capacity)

{

assert(ctrl[capacity] == kSentinel);

assert(IsValidCapacity(capacity));

for (ctrl_t* pos = ctrl; pos != ctrl + capacity + 1; pos += Group::kWidth) {

Group{pos}.ConvertSpecialToEmptyAndFullToDeleted(pos);

}

// Copy the cloned ctrl bytes.

std::memcpy(ctrl + capacity + 1, ctrl, Group::kWidth);

ctrl[capacity] = kSentinel;

{

assert(IsValidCapacity(capacity));

// `capacity*7/8`

PHMAP_IF_CONSTEXPR (Group::kWidth == 8) {

if (capacity == 7)

{

// x-x/8 does not work when x==7.

return 6;

}

}

return capacity - capacity / 8;

{

// `growth*8/7`

PHMAP_IF_CONSTEXPR (Group::kWidth == 8) {

if (growth == 7)

{

// x+(x-1)/7 does not work when x==7.

return 8;

}

}

return growth + static_cast<size_t>((static_cast<int64_t>(growth) - 1) / 7);

{

// Returns the number of probes required to find `key` in `c`. The "number of

// probes" is a concept that can vary by container. Implementations should

// return 0 when `key` was found in the minimum number of operations and

// should increment the result for each non-trivial operation required to find

// `key`.

//

// The default implementation uses the bucket api from the standard and thus

// works for `std::unordered_*` containers.

// --------------------------------------------------------------------------

static size_t GetNumProbes(const Container& c,

const typename Container::key_type& key) {

if (!c.bucket_count()) return {};

size_t num_probes = 0;

size_t bucket = c.bucket(key);

for (auto it = c.begin(bucket), e = c.end(bucket);; ++it, ++num_probes) {

if (it == e) return num_probes;

if (c.key_eq()(key, GetKey<Container>(*it, 0))) return num_probes;

}

}

{

inline void RecordStorageChanged(size_t , size_t ) {}

inline void RecordRehash(size_t ) {}

inline void RecordInsert(size_t , size_t ) {}

inline void RecordErase() {}

friend inline void swap(HashtablezInfoHandle& ,

HashtablezInfoHandle& ) noexcept {}

{

// Returns a global Sampler.

static HashtablezSampler& Global() { static HashtablezSampler hzs; return hzs; }

HashtablezInfo* Register() { static HashtablezInfo info; return &info; }

void Unregister(HashtablezInfo* ) {}

using DisposeCallback = void (*)(const HashtablezInfo&);

DisposeCallback SetDisposeCallback(DisposeCallback ) { return nullptr; }

int64_t Iterate(const std::function<void(const HashtablezInfo& stack)>& ) { return 0; }

phmap::index_sequence<I...>) {

phmap::allocator_traits<Alloc>::construct(

*alloc, ptr, std::get<I>(std::forward<Tuple>(t))...);

template <class... Args>

decltype(std::declval<F>()(std::declval<T>())) operator()(

Args&&... args) const {

return std::forward<F>(f)(T(std::forward<Args>(args)...));

}

F&& f;

Tuple&& t, phmap::index_sequence<Is...>, F&& f) {

return WithConstructedImplF<T, F>{std::forward<F>(f)}(

std::get<Is>(std::forward<Tuple>(t))...);

TupleRefImpl(std::forward<T>(t),

phmap::make_index_sequence<

std::tuple_size<typename std::decay<T>::type>::value>())) {

return TupleRefImpl(

std::forward<T>(t),

phmap::make_index_sequence<

std::tuple_size<typename std::decay<T>::type>::value>());

const auto& key = std::get<0>(p.first);

return std::forward<F>(f)(key, std::piecewise_construct, std::move(p.first),

std::move(p.second));

{

using PolicyTraits = hash_policy_traits<Policy>;

using KeyArgImpl =

KeyArg<IsTransparent<Eq>::value && IsTransparent<Hash>::value>;

using init_type = typename PolicyTraits::init_type;

using key_type = typename PolicyTraits::key_type;

// TODO(sbenza): Hide slot_type as it is an implementation detail. Needs user

// code fixes!

using slot_type = typename PolicyTraits::slot_type;

using allocator_type = Alloc;

using size_type = size_t;

using difference_type = ptrdiff_t;

using hasher = Hash;

using key_equal = Eq;

using policy_type = Policy;

using value_type = typename PolicyTraits::value_type;

using reference = value_type&;

using const_reference = const value_type&;

using pointer = typename phmap::allocator_traits<

allocator_type>::template rebind_traits<value_type>::pointer;

using const_pointer = typename phmap::allocator_traits<

allocator_type>::template rebind_traits<value_type>::const_pointer;

// Alias used for heterogeneous lookup functions.

// `key_arg<K>` evaluates to `K` when the functors are transparent and to

// `key_type` otherwise. It permits template argument deduction on `K` for the

// transparent case.

template <class K>

using key_arg = typename KeyArgImpl::template type<K, key_type>;

// Give an early error when key_type is not hashable/eq.

auto KeyTypeCanBeHashed(const Hash& h, const key_type& k) -> decltype(h(k));

auto KeyTypeCanBeEq(const Eq& eq, const key_type& k) -> decltype(eq(k, k));

using Layout = phmap::priv::Layout<ctrl_t, slot_type>;

static Layout MakeLayout(size_t capacity) {

assert(IsValidCapacity(capacity));

return Layout(capacity + Group::kWidth + 1, capacity);

}

using AllocTraits = phmap::allocator_traits<allocator_type>;

using SlotAlloc = typename phmap::allocator_traits<

allocator_type>::template rebind_alloc<slot_type>;

using SlotAllocTraits = typename phmap::allocator_traits<

allocator_type>::template rebind_traits<slot_type>;

static_assert(std::is_lvalue_reference<reference>::value,

"Policy::element() must return a reference");

template <typename T>

struct SameAsElementReference

: std::is_same<typename std::remove_cv<

typename std::remove_reference<reference>::type>::type,

typename std::remove_cv<

typename std::remove_reference<T>::type>::type> {};

// An enabler for insert(T&&): T must be convertible to init_type or be the

// same as [cv] value_type [ref].

// Note: we separate SameAsElementReference into its own type to avoid using

// reference unless we need to. MSVC doesn't seem to like it in some

// cases.

template <class T>

using RequiresInsertable = typename std::enable_if<

phmap::disjunction<std::is_convertible<T, init_type>,

SameAsElementReference<T>>::value,

int>::type;

// RequiresNotInit is a workaround for gcc prior to 7.1.

// See https://godbolt.org/g/Y4xsUh.

template <class T>

using RequiresNotInit =

typename std::enable_if<!std::is_same<T, init_type>::value, int>::type;

template <class... Ts>

using IsDecomposable = IsDecomposable<void, PolicyTraits, Hash, Eq, Ts...>;

static_assert(std::is_same<pointer, value_type*>::value,

"Allocators with custom pointer types are not supported");

static_assert(std::is_same<const_pointer, const value_type*>::value,

"Allocators with custom pointer types are not supported");

class iterator

{

friend class raw_hash_set;

public:

using iterator_category = std::forward_iterator_tag;

using value_type = typename raw_hash_set::value_type;

using reference =

phmap::conditional_t<PolicyTraits::constant_iterators::value,

const value_type&, value_type&>;

using pointer = phmap::remove_reference_t<reference>*;

using difference_type = typename raw_hash_set::difference_type;

iterator() {}

// PRECONDITION: not an end() iterator.

reference operator*() const { return PolicyTraits::element(slot_); }

// PRECONDITION: not an end() iterator.

pointer operator->() const { return &operator*(); }

// PRECONDITION: not an end() iterator.

iterator& operator++() {

++ctrl_;

++slot_;

skip_empty_or_deleted();

return *this;

}

// PRECONDITION: not an end() iterator.

iterator operator++(int) {

auto tmp = *this;

++*this;

return tmp;

}

#if 0 // PHMAP_BIDIRECTIONAL

// PRECONDITION: not a begin() iterator.

iterator& operator--() {

assert(ctrl_);

do {

--ctrl_;

--slot_;

} while (IsEmptyOrDeleted(*ctrl_));

return *this;

}

// PRECONDITION: not a begin() iterator.

iterator operator--(int) {

auto tmp = *this;

--*this;

return tmp;

}

#endif

friend bool operator==(const iterator& a, const iterator& b) {

return a.ctrl_ == b.ctrl_;

}

friend bool operator!=(const iterator& a, const iterator& b) {

return !(a == b);

}

private:

iterator(ctrl_t* ctrl) : ctrl_(ctrl) {} // for end()

iterator(ctrl_t* ctrl, slot_type* slot) : ctrl_(ctrl), slot_(slot) {}

void skip_empty_or_deleted() {

while (IsEmptyOrDeleted(*ctrl_)) {

// ctrl is not necessarily aligned to Group::kWidth. It is also likely

// to read past the space for ctrl bytes and into slots. This is ok

// because ctrl has sizeof() == 1 and slot has sizeof() >= 1 so there