Coverage Report

Created: 2024-07-27 06:04

/src/parallel-hashmap/parallel_hashmap/phmap.h
Line
Count
Source (jump to first uncovered line)
1
#if !defined(phmap_h_guard_)
2
#define phmap_h_guard_
3
4
// ---------------------------------------------------------------------------
5
// Copyright (c) 2019, Gregory Popovitch - greg7mdp@gmail.com
6
//
7
// Licensed under the Apache License, Version 2.0 (the "License");
8
// you may not use this file except in compliance with the License.
9
// You may obtain a copy of the License at
10
//
11
//      https://www.apache.org/licenses/LICENSE-2.0
12
//
13
// Unless required by applicable law or agreed to in writing, software
14
// distributed under the License is distributed on an "AS IS" BASIS,
15
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16
// See the License for the specific language governing permissions and
17
// limitations under the License.
18
//
19
// Includes work from abseil-cpp (https://github.com/abseil/abseil-cpp)
20
// with modifications.
21
// 
22
// Copyright 2018 The Abseil Authors.
23
//
24
// Licensed under the Apache License, Version 2.0 (the "License");
25
// you may not use this file except in compliance with the License.
26
// You may obtain a copy of the License at
27
//
28
//      https://www.apache.org/licenses/LICENSE-2.0
29
//
30
// Unless required by applicable law or agreed to in writing, software
31
// distributed under the License is distributed on an "AS IS" BASIS,
32
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
33
// See the License for the specific language governing permissions and
34
// limitations under the License.
35
// ---------------------------------------------------------------------------
36
37
// ---------------------------------------------------------------------------
38
// IMPLEMENTATION DETAILS
39
//
40
// The table stores elements inline in a slot array. In addition to the slot
41
// array the table maintains some control state per slot. The extra state is one
42
// byte per slot and stores empty or deleted marks, or alternatively 7 bits from
43
// the hash of an occupied slot. The table is split into logical groups of
44
// slots, like so:
45
//
46
//      Group 1         Group 2        Group 3
47
// +---------------+---------------+---------------+
48
// | | | | | | | | | | | | | | | | | | | | | | | | |
49
// +---------------+---------------+---------------+
50
//
51
// On lookup the hash is split into two parts:
52
// - H2: 7 bits (those stored in the control bytes)
53
// - H1: the rest of the bits
54
// The groups are probed using H1. For each group the slots are matched to H2 in
55
// parallel. Because H2 is 7 bits (128 states) and the number of slots per group
56
// is low (8 or 16) in almost all cases a match in H2 is also a lookup hit.
57
//
58
// On insert, once the right group is found (as in lookup), its slots are
59
// filled in order.
60
//
61
// On erase a slot is cleared. In case the group did not have any empty slots
62
// before the erase, the erased slot is marked as deleted.
63
//
64
// Groups without empty slots (but maybe with deleted slots) extend the probe
65
// sequence. The probing algorithm is quadratic. Given N the number of groups,
66
// the probing function for the i'th probe is:
67
//
68
//   P(0) = H1 % N
69
//
70
//   P(i) = (P(i - 1) + i) % N
71
//
72
// This probing function guarantees that after N probes, all the groups of the
73
// table will be probed exactly once.
74
//
75
// The control state and slot array are stored contiguously in a shared heap
76
// allocation. The layout of this allocation is: `capacity()` control bytes,
77
// one sentinel control byte, `Group::kWidth - 1` cloned control bytes,
78
// <possible padding>, `capacity()` slots. The sentinel control byte is used in
79
// iteration so we know when we reach the end of the table. The cloned control
80
// bytes at the end of the table are cloned from the beginning of the table so
81
// groups that begin near the end of the table can see a full group. In cases in
82
// which there are more than `capacity()` cloned control bytes, the extra bytes
83
// are `kEmpty`, and these ensure that we always see at least one empty slot and
84
// can stop an unsuccessful search.
85
// ---------------------------------------------------------------------------
86
87
88
89
#ifdef _MSC_VER
90
    #pragma warning(push)  
91
92
    #pragma warning(disable : 4127) // conditional expression is constant
93
    #pragma warning(disable : 4324) // structure was padded due to alignment specifier
94
    #pragma warning(disable : 4514) // unreferenced inline function has been removed
95
    #pragma warning(disable : 4623) // default constructor was implicitly defined as deleted
96
    #pragma warning(disable : 4625) // copy constructor was implicitly defined as deleted
97
    #pragma warning(disable : 4626) // assignment operator was implicitly defined as deleted
98
    #pragma warning(disable : 4710) // function not inlined
99
    #pragma warning(disable : 4711) // selected for automatic inline expansion
100
    #pragma warning(disable : 4820) // '6' bytes padding added after data member
101
    #pragma warning(disable : 4868) // compiler may not enforce left-to-right evaluation order in braced initializer list
102
    #pragma warning(disable : 5027) // move assignment operator was implicitly defined as deleted
103
    #pragma warning(disable : 5045) // Compiler will insert Spectre mitigation for memory load if /Qspectre switch specified
104
#endif
105
106
#include <algorithm>
107
#include <cmath>
108
#include <cstring>
109
#include <iterator>
110
#include <limits>
111
#include <memory>
112
#include <tuple>
113
#include <type_traits>
114
#include <utility>
115
#include <array>
116
#include <cassert>
117
#include <atomic>
118
119
#include "phmap_fwd_decl.h"
120
#include "phmap_utils.h"
121
#include "phmap_base.h"
122
123
#if PHMAP_HAVE_STD_STRING_VIEW
124
    #include <string_view>
125
#endif
126
127
namespace phmap {
128
129
namespace priv {
130
131
// --------------------------------------------------------------------------
132
template <typename AllocType>
133
void SwapAlloc(AllocType& lhs, AllocType& rhs,
134
               std::true_type /* propagate_on_container_swap */) {
135
  using std::swap;
136
  swap(lhs, rhs);
137
}
138
139
template <typename AllocType>
140
void SwapAlloc(AllocType& /*lhs*/, AllocType& /*rhs*/,
141
506
               std::false_type /* propagate_on_container_swap */) {}
142
143
// --------------------------------------------------------------------------
144
template <size_t Width>
145
class probe_seq 
146
{
147
public:
148
10.0M
    probe_seq(size_t hashval, size_t mask) {
149
10.0M
        assert(((mask + 1) & mask) == 0 && "not a mask");
150
10.0M
        mask_ = mask;
151
10.0M
        offset_ = hashval & mask_;
152
10.0M
    }
153
11.1M
    size_t offset() const { return offset_; }
154
19.9M
    size_t offset(size_t i) const { return (offset_ + i) & mask_; }
155
156
1.11M
    void next() {
157
1.11M
        index_ += Width;
158
1.11M
        offset_ += index_;
159
1.11M
        offset_ &= mask_;
160
1.11M
    }
161
    // 0-based probe index. The i-th probe in the probe sequence.
162
1.57M
    size_t getindex() const { return index_; }
163
164
private:
165
    size_t mask_;
166
    size_t offset_;
167
    size_t index_ = 0;
168
};
169
170
// --------------------------------------------------------------------------
171
template <class ContainerKey, class Hash, class Eq>
172
struct RequireUsableKey 
173
{
174
    template <class PassedKey, class... Args>
175
    std::pair<
176
        decltype(std::declval<const Hash&>()(std::declval<const PassedKey&>())),
177
        decltype(std::declval<const Eq&>()(std::declval<const ContainerKey&>(),
178
                                           std::declval<const PassedKey&>()))>*
179
    operator()(const PassedKey&, const Args&...) const;
180
};
181
182
// --------------------------------------------------------------------------
183
template <class E, class Policy, class Hash, class Eq, class... Ts>
184
struct IsDecomposable : std::false_type {};
185
186
template <class Policy, class Hash, class Eq, class... Ts>
187
struct IsDecomposable<
188
    phmap::void_t<decltype(
189
        Policy::apply(RequireUsableKey<typename Policy::key_type, Hash, Eq>(),
190
                      std::declval<Ts>()...))>,
191
    Policy, Hash, Eq, Ts...> : std::true_type {};
192
193
// TODO(alkis): Switch to std::is_nothrow_swappable when gcc/clang supports it.
194
// --------------------------------------------------------------------------
195
template <class T>
196
0
constexpr bool IsNoThrowSwappable(std::true_type = {} /* is_swappable */) {
197
0
    using std::swap;
198
0
    return noexcept(swap(std::declval<T&>(), std::declval<T&>()));
199
0
}
Unexecuted instantiation: bool phmap::priv::IsNoThrowSwappable<phmap::Hash<unsigned int> >(std::__1::integral_constant<bool, true>)
Unexecuted instantiation: bool phmap::priv::IsNoThrowSwappable<phmap::EqualTo<unsigned int> >(std::__1::integral_constant<bool, true>)
200
201
template <class T>
202
0
constexpr bool IsNoThrowSwappable(std::false_type /* is_swappable */) {
203
0
  return false;
204
0
}
205
206
// --------------------------------------------------------------------------
207
template <typename T>
208
12.6M
uint32_t TrailingZeros(T x) {
209
12.6M
    uint32_t res;
210
12.6M
    PHMAP_IF_CONSTEXPR(sizeof(T) == 8)
211
0
        res = base_internal::CountTrailingZerosNonZero64(static_cast<uint64_t>(x));
212
12.6M
    else
213
12.6M
        res = base_internal::CountTrailingZerosNonZero32(static_cast<uint32_t>(x));
214
12.6M
    return res;
215
12.6M
}
unsigned int phmap::priv::TrailingZeros<unsigned int>(unsigned int)
Line
Count
Source
208
12.6M
uint32_t TrailingZeros(T x) {
209
12.6M
    uint32_t res;
210
12.6M
    PHMAP_IF_CONSTEXPR(sizeof(T) == 8)
211
0
        res = base_internal::CountTrailingZerosNonZero64(static_cast<uint64_t>(x));
212
12.6M
    else
213
12.6M
        res = base_internal::CountTrailingZerosNonZero32(static_cast<uint32_t>(x));
214
12.6M
    return res;
215
12.6M
}
Unexecuted instantiation: unsigned int phmap::priv::TrailingZeros<unsigned long>(unsigned long)
216
217
// --------------------------------------------------------------------------
218
template <typename T>
219
0
uint32_t LeadingZeros(T x) {
220
0
    uint32_t res;
221
0
    PHMAP_IF_CONSTEXPR(sizeof(T) == 8)
222
0
        res = base_internal::CountLeadingZeros64(static_cast<uint64_t>(x));
223
0
    else
224
0
        res = base_internal::CountLeadingZeros32(static_cast<uint32_t>(x));
225
0
    return res;
226
0
}
227
228
// --------------------------------------------------------------------------
229
// An abstraction over a bitmask. It provides an easy way to iterate through the
230
// indexes of the set bits of a bitmask.  When Shift=0 (platforms with SSE),
231
// this is a true bitmask.  On non-SSE, platforms the arithematic used to
232
// emulate the SSE behavior works in bytes (Shift=3) and leaves each bytes as
233
// either 0x00 or 0x80.
234
//
235
// For example:
236
//   for (int i : BitMask<uint32_t, 16>(0x5)) -> yields 0, 2
237
//   for (int i : BitMask<uint64_t, 8, 3>(0x0000000080800000)) -> yields 2, 3
238
// --------------------------------------------------------------------------
239
template <class T, int SignificantBits, int Shift = 0>
240
class BitMask 
241
{
242
    static_assert(std::is_unsigned<T>::value, "");
243
    static_assert(Shift == 0 || Shift == 3, "");
244
245
public:
246
    // These are useful for unit tests (gunit).
247
    using value_type = int;
248
    using iterator = BitMask;
249
    using const_iterator = BitMask;
250
251
22.3M
    explicit BitMask(T mask) : mask_(mask) {}
252
253
2.96M
    BitMask& operator++() {    // ++iterator
254
2.96M
        mask_ &= (mask_ - 1);  // clear the least significant bit set
255
2.96M
        return *this;
256
2.96M
    }
257
258
3.15M
    explicit operator bool() const { return mask_ != 0; }
259
10.9M
    uint32_t operator*() const { return LowestBitSet(); }
260
261
12.4M
    uint32_t LowestBitSet() const {
262
12.4M
        return priv::TrailingZeros(mask_) >> Shift;
263
12.4M
    }
264
265
    uint32_t HighestBitSet() const {
266
        return (sizeof(T) * CHAR_BIT - priv::LeadingZeros(mask_) - 1) >> Shift;
267
    }
268
269
9.57M
    BitMask begin() const { return *this; }
270
9.57M
    BitMask end() const { return BitMask(0); }
271
272
    uint32_t TrailingZeros() const {
273
        return priv::TrailingZeros(mask_) >> Shift;
274
    }
275
276
    uint32_t LeadingZeros() const {
277
        constexpr uint32_t total_significant_bits = SignificantBits << Shift;
278
        constexpr uint32_t extra_bits = sizeof(T) * 8 - total_significant_bits;
279
        return priv::LeadingZeros(mask_ << extra_bits) >> Shift;
280
    }
281
282
private:
283
    friend bool operator==(const BitMask& a, const BitMask& b) {
284
        return a.mask_ == b.mask_;
285
    }
286
12.5M
    friend bool operator!=(const BitMask& a, const BitMask& b) {
287
12.5M
        return a.mask_ != b.mask_;
288
12.5M
    }
289
290
    T mask_;
291
};
292
293
// --------------------------------------------------------------------------
294
using ctrl_t = signed char;
295
using h2_t = uint8_t;
296
297
// --------------------------------------------------------------------------
298
// The values here are selected for maximum performance. See the static asserts
299
// below for details.
300
// --------------------------------------------------------------------------
301
enum Ctrl : ctrl_t 
302
{
303
    kEmpty = -128,   // 0b10000000 or 0x80
304
    kDeleted = -2,   // 0b11111110 or 0xfe
305
    kSentinel = -1,  // 0b11111111 or 0xff
306
};
307
308
static_assert(
309
    kEmpty & kDeleted & kSentinel & 0x80,
310
    "Special markers need to have the MSB to make checking for them efficient");
311
static_assert(kEmpty < kSentinel && kDeleted < kSentinel,
312
              "kEmpty and kDeleted must be smaller than kSentinel to make the "
313
              "SIMD test of IsEmptyOrDeleted() efficient");
314
static_assert(kSentinel == -1,
315
              "kSentinel must be -1 to elide loading it from memory into SIMD "
316
              "registers (pcmpeqd xmm, xmm)");
317
static_assert(kEmpty == -128,
318
              "kEmpty must be -128 to make the SIMD check for its "
319
              "existence efficient (psignb xmm, xmm)");
320
static_assert(~kEmpty & ~kDeleted & kSentinel & 0x7F,
321
              "kEmpty and kDeleted must share an unset bit that is not shared "
322
              "by kSentinel to make the scalar test for MatchEmptyOrDeleted() "
323
              "efficient");
324
static_assert(kDeleted == -2,
325
              "kDeleted must be -2 to make the implementation of "
326
              "ConvertSpecialToEmptyAndFullToDeleted efficient");
327
328
// --------------------------------------------------------------------------
329
// A single block of empty control bytes for tables without any slots allocated.
330
// This enables removing a branch in the hot path of find().
331
// --------------------------------------------------------------------------
332
2.63k
inline ctrl_t* EmptyGroup() {
333
2.63k
  alignas(16) static constexpr ctrl_t empty_group[] = {
334
2.63k
      kSentinel, kEmpty, kEmpty, kEmpty, kEmpty, kEmpty, kEmpty, kEmpty,
335
2.63k
      kEmpty,    kEmpty, kEmpty, kEmpty, kEmpty, kEmpty, kEmpty, kEmpty};
336
2.63k
  return const_cast<ctrl_t*>(empty_group);
337
2.63k
}
338
339
// --------------------------------------------------------------------------
340
0
inline size_t HashSeed(const ctrl_t* ctrl) {
341
0
  // The low bits of the pointer have little or no entropy because of
342
0
  // alignment. We shift the pointer to try to use higher entropy bits. A
343
0
  // good number seems to be 12 bits, because that aligns with page size.
344
0
  return reinterpret_cast<uintptr_t>(ctrl) >> 12;
345
0
}
346
347
#ifdef PHMAP_NON_DETERMINISTIC
348
349
inline size_t H1(size_t hashval, const ctrl_t* ctrl) {
350
    // use ctrl_ pointer to add entropy to ensure
351
    // non-deterministic iteration order.
352
    return (hashval >> 7) ^ HashSeed(ctrl);
353
}
354
355
#else
356
357
10.0M
inline size_t H1(size_t hashval, const ctrl_t* ) {
358
10.0M
    return (hashval >> 7);
359
10.0M
}
360
361
#endif
362
363
364
11.0M
inline ctrl_t H2(size_t hashval)       { return (ctrl_t)(hashval & 0x7F); }
365
366
536k
inline bool IsEmpty(ctrl_t c)          { return c == kEmpty; }
367
2.58M
inline bool IsFull(ctrl_t c)           { return c >= static_cast<ctrl_t>(0); }
368
2.81k
inline bool IsDeleted(ctrl_t c)        { return c == kDeleted; }
369
728k
inline bool IsEmptyOrDeleted(ctrl_t c) { return c < kSentinel; }
370
371
#if PHMAP_HAVE_SSE2
372
373
#ifdef _MSC_VER
374
    #pragma warning(push)  
375
    #pragma warning(disable : 4365) // conversion from 'int' to 'T', signed/unsigned mismatch
376
#endif
377
378
// --------------------------------------------------------------------------
379
// https://github.com/abseil/abseil-cpp/issues/209
380
// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87853
381
// _mm_cmpgt_epi8 is broken under GCC with -funsigned-char
382
// Work around this by using the portable implementation of Group
383
// when using -funsigned-char under GCC.
384
// --------------------------------------------------------------------------
385
1.78M
inline __m128i _mm_cmpgt_epi8_fixed(__m128i a, __m128i b) {
386
#if defined(__GNUC__) && !defined(__clang__)
387
  #pragma GCC diagnostic push
388
  #pragma GCC diagnostic ignored "-Woverflow"
389
390
  if (std::is_unsigned<char>::value) {
391
    const __m128i mask = _mm_set1_epi8(static_cast<char>(0x80));
392
    const __m128i diff = _mm_subs_epi8(b, a);
393
    return _mm_cmpeq_epi8(_mm_and_si128(diff, mask), mask);
394
  }
395
396
  #pragma GCC diagnostic pop
397
#endif
398
1.78M
  return _mm_cmpgt_epi8(a, b);
399
1.78M
}
400
401
// --------------------------------------------------------------------------
402
// --------------------------------------------------------------------------
403
struct GroupSse2Impl 
404
{
405
    enum { kWidth = 16 };  // the number of slots per group
406
407
11.3M
    explicit GroupSse2Impl(const ctrl_t* pos) {
408
11.3M
        ctrl = _mm_loadu_si128(reinterpret_cast<const __m128i*>(pos));
409
11.3M
    }
410
411
    // Returns a bitmask representing the positions of slots that match hash.
412
    // ----------------------------------------------------------------------
413
11.1M
    BitMask<uint32_t, kWidth> Match(h2_t hash) const {
414
11.1M
        auto match = _mm_set1_epi8((char)hash);
415
11.1M
        return BitMask<uint32_t, kWidth>(
416
11.1M
            static_cast<uint32_t>(_mm_movemask_epi8(_mm_cmpeq_epi8(match, ctrl))));
417
11.1M
    }
418
419
    // Returns a bitmask representing the positions of empty slots.
420
    // ------------------------------------------------------------
421
1.57M
    BitMask<uint32_t, kWidth> MatchEmpty() const {
422
#if PHMAP_HAVE_SSSE3
423
        // This only works because kEmpty is -128.
424
        return BitMask<uint32_t, kWidth>(
425
            static_cast<uint32_t>(_mm_movemask_epi8(_mm_sign_epi8(ctrl, ctrl))));
426
#else
427
1.57M
        return Match(static_cast<h2_t>(kEmpty));
428
1.57M
#endif
429
1.57M
    }
430
431
    // Returns a bitmask representing the positions of empty or deleted slots.
432
    // -----------------------------------------------------------------------
433
1.57M
    BitMask<uint32_t, kWidth> MatchEmptyOrDeleted() const {
434
1.57M
        auto special = _mm_set1_epi8(static_cast<char>(kSentinel));
435
1.57M
        return BitMask<uint32_t, kWidth>(
436
1.57M
            static_cast<uint32_t>(_mm_movemask_epi8(_mm_cmpgt_epi8_fixed(special, ctrl))));
437
1.57M
    }
438
439
    // Returns the number of trailing empty or deleted elements in the group.
440
    // ----------------------------------------------------------------------
441
206k
    uint32_t CountLeadingEmptyOrDeleted() const {
442
206k
        auto special = _mm_set1_epi8(static_cast<char>(kSentinel));
443
206k
        return TrailingZeros(
444
206k
            static_cast<uint32_t>(_mm_movemask_epi8(_mm_cmpgt_epi8_fixed(special, ctrl)) + 1));
445
206k
    }
446
447
    // ----------------------------------------------------------------------
448
0
    void ConvertSpecialToEmptyAndFullToDeleted(ctrl_t* dst) const {
449
0
        auto msbs = _mm_set1_epi8(static_cast<char>(-128));
450
0
        auto x126 = _mm_set1_epi8(126);
451
#if PHMAP_HAVE_SSSE3
452
        auto res = _mm_or_si128(_mm_shuffle_epi8(x126, ctrl), msbs);
453
#else
454
0
        auto zero = _mm_setzero_si128();
455
0
        auto special_mask = _mm_cmpgt_epi8_fixed(zero, ctrl);
456
0
        auto res = _mm_or_si128(msbs, _mm_andnot_si128(special_mask, x126));
457
0
#endif
458
0
        _mm_storeu_si128(reinterpret_cast<__m128i*>(dst), res);
459
0
    }
460
461
    __m128i ctrl;
462
};
463
464
#ifdef _MSC_VER
465
     #pragma warning(pop)  
466
#endif
467
468
#endif  // PHMAP_HAVE_SSE2
469
470
// --------------------------------------------------------------------------
471
// --------------------------------------------------------------------------
472
struct GroupPortableImpl 
473
{
474
    enum { kWidth = 8 };
475
476
    explicit GroupPortableImpl(const ctrl_t* pos)
477
0
        : ctrl(little_endian::Load64(pos)) {}
478
479
0
    BitMask<uint64_t, kWidth, 3> Match(h2_t hash) const {
480
0
        // For the technique, see:
481
0
        // http://graphics.stanford.edu/~seander/bithacks.html##ValueInWord
482
0
        // (Determine if a word has a byte equal to n).
483
0
        //
484
0
        // Caveat: there are false positives but:
485
0
        // - they only occur if there is a real match
486
0
        // - they never occur on kEmpty, kDeleted, kSentinel
487
0
        // - they will be handled gracefully by subsequent checks in code
488
0
        //
489
0
        // Example:
490
0
        //   v = 0x1716151413121110
491
0
        //   hash = 0x12
492
0
        //   retval = (v - lsbs) & ~v & msbs = 0x0000000080800000
493
0
        constexpr uint64_t msbs = 0x8080808080808080ULL;
494
0
        constexpr uint64_t lsbs = 0x0101010101010101ULL;
495
0
        auto x = ctrl ^ (lsbs * hash);
496
0
        return BitMask<uint64_t, kWidth, 3>((x - lsbs) & ~x & msbs);
497
0
    }
498
499
0
    BitMask<uint64_t, kWidth, 3> MatchEmpty() const {          // bit 1 of each byte is 0 for empty (but not for deleted)
500
0
        constexpr uint64_t msbs = 0x8080808080808080ULL;
501
0
        return BitMask<uint64_t, kWidth, 3>((ctrl & (~ctrl << 6)) & msbs);
502
0
    }
503
504
0
    BitMask<uint64_t, kWidth, 3> MatchEmptyOrDeleted() const { // lsb of each byte is 0 for empty or deleted
505
0
        constexpr uint64_t msbs = 0x8080808080808080ULL;
506
0
        return BitMask<uint64_t, kWidth, 3>((ctrl & (~ctrl << 7)) & msbs);
507
0
    }
508
509
0
    uint32_t CountLeadingEmptyOrDeleted() const {
510
0
        constexpr uint64_t gaps = 0x00FEFEFEFEFEFEFEULL;
511
0
        return (uint32_t)((TrailingZeros(((~ctrl & (ctrl >> 7)) | gaps) + 1) + 7) >> 3);
512
0
    }
513
514
0
    void ConvertSpecialToEmptyAndFullToDeleted(ctrl_t* dst) const {
515
0
        constexpr uint64_t msbs = 0x8080808080808080ULL;
516
0
        constexpr uint64_t lsbs = 0x0101010101010101ULL;
517
0
        auto x = ctrl & msbs;
518
0
        auto res = (~x + (x >> 7)) & ~lsbs;
519
0
        little_endian::Store64(dst, res);
520
0
    }
521
522
    uint64_t ctrl;
523
};
524
525
#if PHMAP_HAVE_SSE2  
526
    using Group = GroupSse2Impl;
527
#else
528
    using Group = GroupPortableImpl;
529
#endif
530
531
// The number of cloned control bytes that we copy from the beginning to the
532
// end of the control bytes array.
533
// -------------------------------------------------------------------------
534
0
constexpr size_t NumClonedBytes() { return Group::kWidth - 1; }
535
536
template <class Policy, class Hash, class Eq, class Alloc>
537
class raw_hash_set;
538
539
14.0k
inline bool IsValidCapacity(size_t n) { return ((n + 1) & n) == 0 && n > 0; }
540
541
// --------------------------------------------------------------------------
542
// PRECONDITION:
543
//   IsValidCapacity(capacity)
544
//   ctrl[capacity] == kSentinel
545
//   ctrl[i] != kSentinel for all i < capacity
546
// Applies mapping for every byte in ctrl:
547
//   DELETED -> EMPTY
548
//   EMPTY -> EMPTY
549
//   FULL -> DELETED
550
// --------------------------------------------------------------------------
551
inline void ConvertDeletedToEmptyAndFullToDeleted(
552
    ctrl_t* ctrl, size_t capacity) 
553
0
{
554
0
    assert(ctrl[capacity] == kSentinel);
555
0
    assert(IsValidCapacity(capacity));
556
0
    for (ctrl_t* pos = ctrl; pos != ctrl + capacity + 1; pos += Group::kWidth) {
557
0
        Group{pos}.ConvertSpecialToEmptyAndFullToDeleted(pos);
558
0
    }
559
    // Copy the cloned ctrl bytes.
560
0
    std::memcpy(ctrl + capacity + 1, ctrl, Group::kWidth);
561
0
    ctrl[capacity] = kSentinel;
562
0
}
563
564
// --------------------------------------------------------------------------
565
// Rounds up the capacity to the next power of 2 minus 1, with a minimum of 1.
566
// --------------------------------------------------------------------------
567
inline size_t NormalizeCapacity(size_t n) 
568
0
{
569
0
    return n ? ~size_t{} >> LeadingZeros(n) : 1;
570
0
}
571
572
// --------------------------------------------------------------------------
573
// We use 7/8th as maximum load factor.
574
// For 16-wide groups, that gives an average of two empty slots per group.
575
// --------------------------------------------------------------------------
576
inline size_t CapacityToGrowth(size_t capacity) 
577
5.29k
{
578
5.29k
    assert(IsValidCapacity(capacity));
579
    // `capacity*7/8`
580
5.29k
    PHMAP_IF_CONSTEXPR (Group::kWidth == 8) {
581
0
        if (capacity == 7) {
582
            // x-x/8 does not work when x==7.
583
0
            return 6;
584
0
        }
585
0
    }
586
5.29k
    return capacity - capacity / 8;
587
5.29k
}
588
589
// --------------------------------------------------------------------------
590
// From desired "growth" to a lowerbound of the necessary capacity.
591
// Might not be a valid one and required NormalizeCapacity().
592
// --------------------------------------------------------------------------
593
inline size_t GrowthToLowerboundCapacity(size_t growth) 
594
0
{
595
0
    // `growth*8/7`
596
0
    PHMAP_IF_CONSTEXPR (Group::kWidth == 8) {
597
0
        if (growth == 7) {
598
0
            // x+(x-1)/7 does not work when x==7.
599
0
            return 8;
600
0
        }
601
0
    }
602
0
    return growth + static_cast<size_t>((static_cast<int64_t>(growth) - 1) / 7);
603
0
}
604
605
namespace hashtable_debug_internal {
606
607
// If it is a map, call get<0>().
608
using std::get;
609
template <typename T, typename = typename T::mapped_type>
610
auto GetKey(const typename T::value_type& pair, int) -> decltype(get<0>(pair)) {
611
    return get<0>(pair);
612
}
613
614
// If it is not a map, return the value directly.
615
template <typename T>
616
const typename T::key_type& GetKey(const typename T::key_type& key, char) {
617
    return key;
618
}
619
620
// --------------------------------------------------------------------------
621
// Containers should specialize this to provide debug information for that
622
// container.
623
// --------------------------------------------------------------------------
624
template <class Container, typename Enabler = void>
625
struct HashtableDebugAccess
626
{
627
    // Returns the number of probes required to find `key` in `c`.  The "number of
628
    // probes" is a concept that can vary by container.  Implementations should
629
    // return 0 when `key` was found in the minimum number of operations and
630
    // should increment the result for each non-trivial operation required to find
631
    // `key`.
632
    //
633
    // The default implementation uses the bucket api from the standard and thus
634
    // works for `std::unordered_*` containers.
635
    // --------------------------------------------------------------------------
636
    static size_t GetNumProbes(const Container& c,
637
                               const typename Container::key_type& key) {
638
        if (!c.bucket_count()) return {};
639
        size_t num_probes = 0;
640
        size_t bucket = c.bucket(key);
641
        for (auto it = c.begin(bucket), e = c.end(bucket);; ++it, ++num_probes) {
642
            if (it == e) return num_probes;
643
            if (c.key_eq()(key, GetKey<Container>(*it, 0))) return num_probes;
644
        }
645
    }
646
};
647
648
}  // namespace hashtable_debug_internal
649
650
// ----------------------------------------------------------------------------
651
//                    I N F O Z   S T U B S
652
// ----------------------------------------------------------------------------
653
struct HashtablezInfo 
654
{
655
0
    void PrepareForSampling() {}
656
};
657
658
0
inline void RecordRehashSlow(HashtablezInfo*, size_t ) {}
659
660
0
static inline void RecordInsertSlow(HashtablezInfo* , size_t, size_t ) {}
661
662
0
static inline void RecordEraseSlow(HashtablezInfo*) {}
663
664
0
static inline HashtablezInfo* SampleSlow(int64_t*) { return nullptr; }
665
0
static inline void UnsampleSlow(HashtablezInfo* ) {}
666
667
class HashtablezInfoHandle 
668
{
669
public:
670
2.95k
    inline void RecordStorageChanged(size_t , size_t ) {}
671
0
    inline void RecordRehash(size_t ) {}
672
536k
    inline void RecordInsert(size_t , size_t ) {}
673
0
    inline void RecordErase() {}
674
    friend inline void swap(HashtablezInfoHandle& ,
675
506
                            HashtablezInfoHandle& ) noexcept {}
676
};
677
678
607
static inline HashtablezInfoHandle Sample() { return HashtablezInfoHandle(); }
679
680
class HashtablezSampler 
681
{
682
public:
683
    // Returns a global Sampler.
684
0
    static HashtablezSampler& Global() {  static HashtablezSampler hzs; return hzs; }
685
0
    HashtablezInfo* Register() {  static HashtablezInfo info; return &info; }
686
0
    void Unregister(HashtablezInfo* ) {}
687
688
    using DisposeCallback = void (*)(const HashtablezInfo&);
689
0
    DisposeCallback SetDisposeCallback(DisposeCallback ) { return nullptr; }
690
0
    int64_t Iterate(const std::function<void(const HashtablezInfo& stack)>& ) { return 0; }
691
};
692
693
0
static inline void SetHashtablezEnabled(bool ) {}
694
0
static inline void SetHashtablezSampleParameter(int32_t ) {}
695
0
static inline void SetHashtablezMaxSamples(int32_t ) {}
696
697
698
namespace memory_internal {
699
700
// Constructs T into uninitialized storage pointed by `ptr` using the args
701
// specified in the tuple.
702
// ----------------------------------------------------------------------------
703
template <class Alloc, class T, class Tuple, size_t... I>
704
void ConstructFromTupleImpl(Alloc* alloc, T* ptr, Tuple&& t,
705
                            phmap::index_sequence<I...>) {
706
    phmap::allocator_traits<Alloc>::construct(
707
        *alloc, ptr, std::get<I>(std::forward<Tuple>(t))...);
708
}
709
710
template <class T, class F>
711
struct WithConstructedImplF {
712
    template <class... Args>
713
    decltype(std::declval<F>()(std::declval<T>())) operator()(
714
        Args&&... args) const {
715
        return std::forward<F>(f)(T(std::forward<Args>(args)...));
716
    }
717
    F&& f;
718
};
719
720
template <class T, class Tuple, size_t... Is, class F>
721
decltype(std::declval<F>()(std::declval<T>())) WithConstructedImpl(
722
    Tuple&& t, phmap::index_sequence<Is...>, F&& f) {
723
    return WithConstructedImplF<T, F>{std::forward<F>(f)}(
724
        std::get<Is>(std::forward<Tuple>(t))...);
725
}
726
727
template <class T, size_t... Is>
728
auto TupleRefImpl(T&& t, phmap::index_sequence<Is...>)
729
    -> decltype(std::forward_as_tuple(std::get<Is>(std::forward<T>(t))...)) {
730
  return std::forward_as_tuple(std::get<Is>(std::forward<T>(t))...);
731
}
732
733
// Returns a tuple of references to the elements of the input tuple. T must be a
734
// tuple.
735
// ----------------------------------------------------------------------------
736
template <class T>
737
auto TupleRef(T&& t) -> decltype(
738
    TupleRefImpl(std::forward<T>(t),
739
                 phmap::make_index_sequence<
740
                     std::tuple_size<typename std::decay<T>::type>::value>())) {
741
  return TupleRefImpl(
742
      std::forward<T>(t),
743
      phmap::make_index_sequence<
744
          std::tuple_size<typename std::decay<T>::type>::value>());
745
}
746
747
template <class F, class K, class V>
748
decltype(std::declval<F>()(std::declval<const K&>(), std::piecewise_construct,
749
                           std::declval<std::tuple<K>>(), std::declval<V>()))
750
19.9M
DecomposePairImpl(F&& f, std::pair<std::tuple<K>, V> p) {
751
19.9M
    const auto& key = std::get<0>(p.first);
752
19.9M
    return std::forward<F>(f)(key, std::piecewise_construct, std::move(p.first),
753
19.9M
                              std::move(p.second));
754
19.9M
}
_ZN5phmap4priv15memory_internal17DecomposePairImplINS0_12raw_hash_setINS0_17FlatHashMapPolicyIjiEENS_4HashIjEENS_7EqualToIjEENSt3__19allocatorINSA_4pairIKjiEEEEE19EmplaceDecomposableEOSD_NSA_5tupleIJOiEEEEEDTclclsr3stdE7declvalIT_EEclsr3stdE7declvalIRKT0_EEL_ZNSA_19piecewise_constructEEclsr3stdE7declvalINSJ_IJSN_EEEEEclsr3stdE7declvalIT1_EEEEOSM_NSC_ISQ_SR_EE
Line
Count
Source
750
8.01M
DecomposePairImpl(F&& f, std::pair<std::tuple<K>, V> p) {
751
8.01M
    const auto& key = std::get<0>(p.first);
752
8.01M
    return std::forward<F>(f)(key, std::piecewise_construct, std::move(p.first),
753
8.01M
                              std::move(p.second));
754
8.01M
}
_ZN5phmap4priv15memory_internal17DecomposePairImplINS0_12raw_hash_setINS0_17FlatHashMapPolicyIjiEENS_4HashIjEENS_7EqualToIjEENSt3__19allocatorINSA_4pairIKjiEEEEE12EqualElementIjEERSD_NSA_5tupleIJRKiEEEEEDTclclsr3stdE7declvalIT_EEclsr3stdE7declvalIRKT0_EEL_ZNSA_19piecewise_constructEEclsr3stdE7declvalINSK_IJSP_EEEEEclsr3stdE7declvalIT1_EEEEOSO_NSC_ISS_ST_EE
Line
Count
Source
750
10.4M
DecomposePairImpl(F&& f, std::pair<std::tuple<K>, V> p) {
751
10.4M
    const auto& key = std::get<0>(p.first);
752
10.4M
    return std::forward<F>(f)(key, std::piecewise_construct, std::move(p.first),
753
10.4M
                              std::move(p.second));
754
10.4M
}
_ZN5phmap4priv15memory_internal17DecomposePairImplINS0_12raw_hash_setINS0_17FlatHashMapPolicyIjiEENS_4HashIjEENS_7EqualToIjEENSt3__19allocatorINSA_4pairIKjiEEEEE11HashElementERSD_NSA_5tupleIJRKiEEEEEDTclclsr3stdE7declvalIT_EEclsr3stdE7declvalIRKT0_EEL_ZNSA_19piecewise_constructEEclsr3stdE7declvalINSJ_IJSO_EEEEEclsr3stdE7declvalIT1_EEEEOSN_NSC_ISR_SS_EE
Line
Count
Source
750
1.47M
DecomposePairImpl(F&& f, std::pair<std::tuple<K>, V> p) {
751
1.47M
    const auto& key = std::get<0>(p.first);
752
1.47M
    return std::forward<F>(f)(key, std::piecewise_construct, std::move(p.first),
753
1.47M
                              std::move(p.second));
754
1.47M
}
755
756
}  // namespace memory_internal
757
758
759
// ----------------------------------------------------------------------------
760
//                     R A W _ H A S H _ S E T
761
// ----------------------------------------------------------------------------
762
// An open-addressing
763
// hashtable with quadratic probing.
764
//
765
// This is a low level hashtable on top of which different interfaces can be
766
// implemented, like flat_hash_set, node_hash_set, string_hash_set, etc.
767
//
768
// The table interface is similar to that of std::unordered_set. Notable
769
// differences are that most member functions support heterogeneous keys when
770
// BOTH the hash and eq functions are marked as transparent. They do so by
771
// providing a typedef called `is_transparent`.
772
//
773
// When heterogeneous lookup is enabled, functions that take key_type act as if
774
// they have an overload set like:
775
//
776
//   iterator find(const key_type& key);
777
//   template <class K>
778
//   iterator find(const K& key);
779
//
780
//   size_type erase(const key_type& key);
781
//   template <class K>
782
//   size_type erase(const K& key);
783
//
784
//   std::pair<iterator, iterator> equal_range(const key_type& key);
785
//   template <class K>
786
//   std::pair<iterator, iterator> equal_range(const K& key);
787
//
788
// When heterogeneous lookup is disabled, only the explicit `key_type` overloads
789
// exist.
790
//
791
// find() also supports passing the hash explicitly:
792
//
793
//   iterator find(const key_type& key, size_t hash);
794
//   template <class U>
795
//   iterator find(const U& key, size_t hash);
796
//
797
// In addition the pointer to element and iterator stability guarantees are
798
// weaker: all iterators and pointers are invalidated after a new element is
799
// inserted.
800
//
801
// IMPLEMENTATION DETAILS
802
//
803
// The table stores elements inline in a slot array. In addition to the slot
804
// array the table maintains some control state per slot. The extra state is one
805
// byte per slot and stores empty or deleted marks, or alternatively 7 bits from
806
// the hash of an occupied slot. The table is split into logical groups of
807
// slots, like so:
808
//
809
//      Group 1         Group 2        Group 3
810
// +---------------+---------------+---------------+
811
// | | | | | | | | | | | | | | | | | | | | | | | | |
812
// +---------------+---------------+---------------+
813
//
814
// On lookup the hash is split into two parts:
815
// - H2: 7 bits (those stored in the control bytes)
816
// - H1: the rest of the bits
817
// The groups are probed using H1. For each group the slots are matched to H2 in
818
// parallel. Because H2 is 7 bits (128 states) and the number of slots per group
819
// is low (8 or 16) in almost all cases a match in H2 is also a lookup hit.
820
//
821
// On insert, once the right group is found (as in lookup), its slots are
822
// filled in order.
823
//
824
// On erase a slot is cleared. In case the group did not have any empty slots
825
// before the erase, the erased slot is marked as deleted.
826
//
827
// Groups without empty slots (but maybe with deleted slots) extend the probe
828
// sequence. The probing algorithm is quadratic. Given N the number of groups,
829
// the probing function for the i'th probe is:
830
//
831
//   P(0) = H1 % N
832
//
833
//   P(i) = (P(i - 1) + i) % N
834
//
835
// This probing function guarantees that after N probes, all the groups of the
836
// table will be probed exactly once.
837
// ----------------------------------------------------------------------------
838
template <class Policy, class Hash, class Eq, class Alloc>
839
class raw_hash_set 
840
{
841
    using PolicyTraits = hash_policy_traits<Policy>;
842
    using KeyArgImpl =
843
        KeyArg<IsTransparent<Eq>::value && IsTransparent<Hash>::value>;
844
845
public:
846
    using init_type = typename PolicyTraits::init_type;
847
    using key_type = typename PolicyTraits::key_type;
848
    // TODO(sbenza): Hide slot_type as it is an implementation detail. Needs user
849
    // code fixes!
850
    using slot_type = typename PolicyTraits::slot_type;
851
    using allocator_type = Alloc;
852
    using size_type = size_t;
853
    using difference_type = ptrdiff_t;
854
    using hasher = Hash;
855
    using key_equal = Eq;
856
    using policy_type = Policy;
857
    using value_type = typename PolicyTraits::value_type;
858
    using reference = value_type&;
859
    using const_reference = const value_type&;
860
    using pointer = typename phmap::allocator_traits<
861
        allocator_type>::template rebind_traits<value_type>::pointer;
862
    using const_pointer = typename phmap::allocator_traits<
863
        allocator_type>::template rebind_traits<value_type>::const_pointer;
864
865
    // Alias used for heterogeneous lookup functions.
866
    // `key_arg<K>` evaluates to `K` when the functors are transparent and to
867
    // `key_type` otherwise. It permits template argument deduction on `K` for the
868
    // transparent case.
869
    template <class K>
870
    using key_arg = typename KeyArgImpl::template type<K, key_type>;
871
872
private:
873
    // Give an early error when key_type is not hashable/eq.
874
    auto KeyTypeCanBeHashed(const Hash& h, const key_type& k) -> decltype(h(k));
875
    auto KeyTypeCanBeEq(const Eq& eq, const key_type& k) -> decltype(eq(k, k));
876
877
    using Layout = phmap::priv::Layout<ctrl_t, slot_type>;
878
879
5.90k
    static Layout MakeLayout(size_t capacity) {
880
5.90k
        assert(IsValidCapacity(capacity));
881
5.90k
        return Layout(capacity + Group::kWidth + 1, capacity);
882
5.90k
    }
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::MakeLayout(unsigned long)
Line
Count
Source
879
5.90k
    static Layout MakeLayout(size_t capacity) {
880
5.90k
        assert(IsValidCapacity(capacity));
881
5.90k
        return Layout(capacity + Group::kWidth + 1, capacity);
882
5.90k
    }
Unexecuted instantiation: phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::MakeLayout(unsigned long)
883
884
    using AllocTraits = phmap::allocator_traits<allocator_type>;
885
    using SlotAlloc = typename phmap::allocator_traits<
886
        allocator_type>::template rebind_alloc<slot_type>;
887
    using SlotAllocTraits = typename phmap::allocator_traits<
888
        allocator_type>::template rebind_traits<slot_type>;
889
890
    static_assert(std::is_lvalue_reference<reference>::value,
891
                  "Policy::element() must return a reference");
892
893
    template <typename T>
894
    struct SameAsElementReference
895
        : std::is_same<typename std::remove_cv<
896
                           typename std::remove_reference<reference>::type>::type,
897
                       typename std::remove_cv<
898
                           typename std::remove_reference<T>::type>::type> {};
899
900
    // An enabler for insert(T&&): T must be convertible to init_type or be the
901
    // same as [cv] value_type [ref].
902
    // Note: we separate SameAsElementReference into its own type to avoid using
903
    // reference unless we need to. MSVC doesn't seem to like it in some
904
    // cases.
905
    template <class T>
906
    using RequiresInsertable = typename std::enable_if<
907
        phmap::disjunction<std::is_convertible<T, init_type>,
908
                           SameAsElementReference<T>>::value,
909
        int>::type;
910
911
    // RequiresNotInit is a workaround for gcc prior to 7.1.
912
    // See https://godbolt.org/g/Y4xsUh.
913
    template <class T>
914
    using RequiresNotInit =
915
        typename std::enable_if<!std::is_same<T, init_type>::value, int>::type;
916
917
    template <class... Ts>
918
    using IsDecomposable = IsDecomposable<void, PolicyTraits, Hash, Eq, Ts...>;
919
920
public:
921
    static_assert(std::is_same<pointer, value_type*>::value,
922
                  "Allocators with custom pointer types are not supported");
923
    static_assert(std::is_same<const_pointer, const value_type*>::value,
924
                  "Allocators with custom pointer types are not supported");
925
926
    class iterator 
927
    {
928
        friend class raw_hash_set;
929
930
    public:
931
        using iterator_category = std::forward_iterator_tag;
932
        using value_type = typename raw_hash_set::value_type;
933
        using reference =
934
            phmap::conditional_t<PolicyTraits::constant_iterators::value,
935
                                 const value_type&, value_type&>;
936
        using pointer = phmap::remove_reference_t<reference>*;
937
        using difference_type = typename raw_hash_set::difference_type;
938
939
        iterator() {}
940
941
        // PRECONDITION: not an end() iterator.
942
521k
        reference operator*() const { return PolicyTraits::element(slot_); }
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::iterator::operator*() const
Line
Count
Source
942
521k
        reference operator*() const { return PolicyTraits::element(slot_); }
Unexecuted instantiation: phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::iterator::operator*() const
943
944
        // PRECONDITION: not an end() iterator.
945
        pointer operator->() const { return &operator*(); }
946
947
        // PRECONDITION: not an end() iterator.
948
521k
        iterator& operator++() {
949
521k
            ++ctrl_;
950
521k
            ++slot_;
951
521k
            skip_empty_or_deleted();
952
521k
            return *this;
953
521k
        }
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::iterator::operator++()
Line
Count
Source
948
521k
        iterator& operator++() {
949
521k
            ++ctrl_;
950
521k
            ++slot_;
951
521k
            skip_empty_or_deleted();
952
521k
            return *this;
953
521k
        }
Unexecuted instantiation: phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::iterator::operator++()
954
        // PRECONDITION: not an end() iterator.
955
        iterator operator++(int) {
956
            auto tmp = *this;
957
            ++*this;
958
            return tmp;
959
        }
960
961
#if 0 // PHMAP_BIDIRECTIONAL
962
        // PRECONDITION: not a begin() iterator.
963
        iterator& operator--() {
964
            assert(ctrl_);
965
            do {
966
                --ctrl_;
967
                --slot_;
968
            } while (IsEmptyOrDeleted(*ctrl_));
969
            return *this;
970
        }
971
972
        // PRECONDITION: not a begin() iterator.
973
        iterator operator--(int) {
974
            auto tmp = *this;
975
            --*this;
976
            return tmp;
977
        }
978
#endif
979
980
521k
        friend bool operator==(const iterator& a, const iterator& b) {
981
521k
            return a.ctrl_ == b.ctrl_;
982
521k
        }
phmap::priv::operator==(phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::iterator const&, phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::iterator const&)
Line
Count
Source
980
521k
        friend bool operator==(const iterator& a, const iterator& b) {
981
521k
            return a.ctrl_ == b.ctrl_;
982
521k
        }
phmap::priv::operator==(phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::iterator const&, phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::iterator const&)
Line
Count
Source
980
506
        friend bool operator==(const iterator& a, const iterator& b) {
981
506
            return a.ctrl_ == b.ctrl_;
982
506
        }
983
506
        friend bool operator!=(const iterator& a, const iterator& b) {
984
506
            return !(a == b);
985
506
        }
986
987
    private:
988
679
        iterator(ctrl_t* ctrl) : ctrl_(ctrl) {}  // for end()
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::iterator::iterator(signed char*)
Line
Count
Source
988
173
        iterator(ctrl_t* ctrl) : ctrl_(ctrl) {}  // for end()
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::iterator::iterator(signed char*)
Line
Count
Source
988
506
        iterator(ctrl_t* ctrl) : ctrl_(ctrl) {}  // for end()
989
8.01M
        iterator(ctrl_t* ctrl, slot_type* slot) : ctrl_(ctrl), slot_(slot) {}
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::iterator::iterator(signed char*, phmap::priv::map_slot_type<unsigned int, int>*)
Line
Count
Source
989
8.01M
        iterator(ctrl_t* ctrl, slot_type* slot) : ctrl_(ctrl), slot_(slot) {}
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::iterator::iterator(signed char*, phmap::priv::map_slot_type<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >*)
Line
Count
Source
989
506
        iterator(ctrl_t* ctrl, slot_type* slot) : ctrl_(ctrl), slot_(slot) {}
990
991
521k
        void skip_empty_or_deleted() {
992
728k
            while (IsEmptyOrDeleted(*ctrl_)) {
993
                // ctrl is not necessarily aligned to Group::kWidth. It is also likely
994
                // to read past the space for ctrl bytes and into slots. This is ok
995
                // because ctrl has sizeof() == 1 and slot has sizeof() >= 1 so there
996
                // is no way to read outside the combined slot array.
997
206k
                uint32_t shift = Group{ctrl_}.CountLeadingEmptyOrDeleted();
998
206k
                ctrl_ += shift;
999
206k
                slot_ += shift;
1000
206k
            }
1001
521k
        }
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::iterator::skip_empty_or_deleted()
Line
Count
Source
991
521k
        void skip_empty_or_deleted() {
992
727k
            while (IsEmptyOrDeleted(*ctrl_)) {
993
                // ctrl is not necessarily aligned to Group::kWidth. It is also likely
994
                // to read past the space for ctrl bytes and into slots. This is ok
995
                // because ctrl has sizeof() == 1 and slot has sizeof() >= 1 so there
996
                // is no way to read outside the combined slot array.
997
206k
                uint32_t shift = Group{ctrl_}.CountLeadingEmptyOrDeleted();
998
206k
                ctrl_ += shift;
999
206k
                slot_ += shift;
1000
206k
            }
1001
521k
        }
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::iterator::skip_empty_or_deleted()
Line
Count
Source
991
506
        void skip_empty_or_deleted() {
992
506
            while (IsEmptyOrDeleted(*ctrl_)) {
993
                // ctrl is not necessarily aligned to Group::kWidth. It is also likely
994
                // to read past the space for ctrl bytes and into slots. This is ok
995
                // because ctrl has sizeof() == 1 and slot has sizeof() >= 1 so there
996
                // is no way to read outside the combined slot array.
997
0
                uint32_t shift = Group{ctrl_}.CountLeadingEmptyOrDeleted();
998
0
                ctrl_ += shift;
999
0
                slot_ += shift;
1000
0
            }
1001
506
        }
1002
1003
        ctrl_t* ctrl_ = nullptr;
1004
        // To avoid uninitialized member warnings, put slot_ in an anonymous union.
1005
        // The member is not initialized on singleton and end iterators.
1006
        union {
1007
            slot_type* slot_;
1008
        };
1009
    };
1010
1011
    class const_iterator 
1012
    {
1013
        friend class raw_hash_set;
1014
1015
    public:
1016
        using iterator_category = typename iterator::iterator_category;
1017
        using value_type = typename raw_hash_set::value_type;
1018
        using reference = typename raw_hash_set::const_reference;
1019
        using pointer = typename raw_hash_set::const_pointer;
1020
        using difference_type = typename raw_hash_set::difference_type;
1021
1022
        const_iterator() {}
1023
        // Implicit construction from iterator.
1024
346
        const_iterator(iterator i) : inner_(std::move(i)) {}
1025
1026
521k
        reference operator*() const { return *inner_; }
1027
        pointer operator->() const { return inner_.operator->(); }
1028
1029
521k
        const_iterator& operator++() {
1030
521k
            ++inner_;
1031
521k
            return *this;
1032
521k
        }
1033
        const_iterator operator++(int) { return inner_++; }
1034
1035
521k
        friend bool operator==(const const_iterator& a, const const_iterator& b) {
1036
521k
            return a.inner_ == b.inner_;
1037
521k
        }
1038
521k
        friend bool operator!=(const const_iterator& a, const const_iterator& b) {
1039
521k
            return !(a == b);
1040
521k
        }
1041
1042
    private:
1043
        const_iterator(const ctrl_t* ctrl, const slot_type* slot)
1044
            : inner_(const_cast<ctrl_t*>(ctrl), const_cast<slot_type*>(slot)) {}
1045
1046
        iterator inner_;
1047
    };
1048
1049
    using node_type = node_handle<Policy, hash_policy_traits<Policy>, Alloc>;
1050
    using insert_return_type = InsertReturnType<iterator, node_type>;
1051
1052
    raw_hash_set() noexcept(
1053
        std::is_nothrow_default_constructible<hasher>::value&&
1054
        std::is_nothrow_default_constructible<key_equal>::value&&
1055
2.02k
        std::is_nothrow_default_constructible<allocator_type>::value) {}
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::raw_hash_set()
Line
Count
Source
1055
1.51k
        std::is_nothrow_default_constructible<allocator_type>::value) {}
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::raw_hash_set()
Line
Count
Source
1055
506
        std::is_nothrow_default_constructible<allocator_type>::value) {}
1056
1057
    explicit raw_hash_set(size_t bucket_cnt, const hasher& hashfn = hasher(),
1058
                          const key_equal& eq = key_equal(),
1059
                          const allocator_type& alloc = allocator_type())
1060
        : ctrl_(EmptyGroup()), settings_(0, hashfn, eq, alloc) {
1061
        if (bucket_cnt) {
1062
            size_t new_capacity = NormalizeCapacity(bucket_cnt);
1063
            reset_growth_left(new_capacity);
1064
            initialize_slots(new_capacity);
1065
            capacity_ = new_capacity;
1066
        }
1067
    }
1068
1069
    raw_hash_set(size_t bucket_cnt, const hasher& hashfn,
1070
                 const allocator_type& alloc)
1071
        : raw_hash_set(bucket_cnt, hashfn, key_equal(), alloc) {}
1072
1073
    raw_hash_set(size_t bucket_cnt, const allocator_type& alloc)
1074
        : raw_hash_set(bucket_cnt, hasher(), key_equal(), alloc) {}
1075
1076
    explicit raw_hash_set(const allocator_type& alloc)
1077
        : raw_hash_set(0, hasher(), key_equal(), alloc) {}
1078
1079
    template <class InputIter>
1080
    raw_hash_set(InputIter first, InputIter last, size_t bucket_cnt = 0,
1081
                 const hasher& hashfn = hasher(), const key_equal& eq = key_equal(),
1082
                 const allocator_type& alloc = allocator_type())
1083
        : raw_hash_set(bucket_cnt, hashfn, eq, alloc) {
1084
        insert(first, last);
1085
    }
1086
1087
    template <class InputIter>
1088
    raw_hash_set(InputIter first, InputIter last, size_t bucket_cnt,
1089
                 const hasher& hashfn, const allocator_type& alloc)
1090
        : raw_hash_set(first, last, bucket_cnt, hashfn, key_equal(), alloc) {}
1091
1092
    template <class InputIter>
1093
    raw_hash_set(InputIter first, InputIter last, size_t bucket_cnt,
1094
                 const allocator_type& alloc)
1095
        : raw_hash_set(first, last, bucket_cnt, hasher(), key_equal(), alloc) {}
1096
1097
    template <class InputIter>
1098
    raw_hash_set(InputIter first, InputIter last, const allocator_type& alloc)
1099
        : raw_hash_set(first, last, 0, hasher(), key_equal(), alloc) {}
1100
1101
    // Instead of accepting std::initializer_list<value_type> as the first
1102
    // argument like std::unordered_set<value_type> does, we have two overloads
1103
    // that accept std::initializer_list<T> and std::initializer_list<init_type>.
1104
    // This is advantageous for performance.
1105
    //
1106
    //   // Turns {"abc", "def"} into std::initializer_list<std::string>, then
1107
    //   // copies the strings into the set.
1108
    //   std::unordered_set<std::string> s = {"abc", "def"};
1109
    //
1110
    //   // Turns {"abc", "def"} into std::initializer_list<const char*>, then
1111
    //   // copies the strings into the set.
1112
    //   phmap::flat_hash_set<std::string> s = {"abc", "def"};
1113
    //
1114
    // The same trick is used in insert().
1115
    //
1116
    // The enabler is necessary to prevent this constructor from triggering where
1117
    // the copy constructor is meant to be called.
1118
    //
1119
    //   phmap::flat_hash_set<int> a, b{a};
1120
    //
1121
    // RequiresNotInit<T> is a workaround for gcc prior to 7.1.
1122
    template <class T, RequiresNotInit<T> = 0, RequiresInsertable<T> = 0>
1123
    raw_hash_set(std::initializer_list<T> init, size_t bucket_cnt = 0,
1124
                 const hasher& hashfn = hasher(), const key_equal& eq = key_equal(),
1125
                 const allocator_type& alloc = allocator_type())
1126
        : raw_hash_set(init.begin(), init.end(), bucket_cnt, hashfn, eq, alloc) {}
1127
1128
    raw_hash_set(std::initializer_list<init_type> init, size_t bucket_cnt = 0,
1129
                 const hasher& hashfn = hasher(), const key_equal& eq = key_equal(),
1130
                 const allocator_type& alloc = allocator_type())
1131
        : raw_hash_set(init.begin(), init.end(), bucket_cnt, hashfn, eq, alloc) {}
1132
1133
    template <class T, RequiresNotInit<T> = 0, RequiresInsertable<T> = 0>
1134
    raw_hash_set(std::initializer_list<T> init, size_t bucket_cnt,
1135
                 const hasher& hashfn, const allocator_type& alloc)
1136
        : raw_hash_set(init, bucket_cnt, hashfn, key_equal(), alloc) {}
1137
1138
    raw_hash_set(std::initializer_list<init_type> init, size_t bucket_cnt,
1139
                 const hasher& hashfn, const allocator_type& alloc)
1140
        : raw_hash_set(init, bucket_cnt, hashfn, key_equal(), alloc) {}
1141
1142
    template <class T, RequiresNotInit<T> = 0, RequiresInsertable<T> = 0>
1143
    raw_hash_set(std::initializer_list<T> init, size_t bucket_cnt,
1144
                 const allocator_type& alloc)
1145
        : raw_hash_set(init, bucket_cnt, hasher(), key_equal(), alloc) {}
1146
1147
    raw_hash_set(std::initializer_list<init_type> init, size_t bucket_cnt,
1148
                 const allocator_type& alloc)
1149
        : raw_hash_set(init, bucket_cnt, hasher(), key_equal(), alloc) {}
1150
1151
    template <class T, RequiresNotInit<T> = 0, RequiresInsertable<T> = 0>
1152
    raw_hash_set(std::initializer_list<T> init, const allocator_type& alloc)
1153
        : raw_hash_set(init, 0, hasher(), key_equal(), alloc) {}
1154
1155
    raw_hash_set(std::initializer_list<init_type> init,
1156
                 const allocator_type& alloc)
1157
        : raw_hash_set(init, 0, hasher(), key_equal(), alloc) {}
1158
1159
    raw_hash_set(const raw_hash_set& that)
1160
        : raw_hash_set(that, AllocTraits::select_on_container_copy_construction(
1161
                           that.alloc_ref())) {}
1162
1163
    raw_hash_set(const raw_hash_set& that, const allocator_type& a)
1164
        : raw_hash_set(0, that.hash_ref(), that.eq_ref(), a) {
1165
        rehash(that.capacity());   // operator=() should preserve load_factor
1166
        // Because the table is guaranteed to be empty, we can do something faster
1167
        // than a full `insert`.
1168
        for (const auto& v : that) {
1169
            const size_t hashval = PolicyTraits::apply(HashElement{hash_ref()}, v);
1170
            auto target = find_first_non_full(hashval);
1171
            set_ctrl(target.offset, H2(hashval));
1172
            emplace_at(target.offset, v);
1173
            infoz_.RecordInsert(hashval, target.probe_length);
1174
        }
1175
        size_ = that.size();
1176
        growth_left() -= that.size();
1177
    }
1178
1179
    raw_hash_set(raw_hash_set&& that) noexcept(
1180
        std::is_nothrow_copy_constructible<hasher>::value&&
1181
        std::is_nothrow_copy_constructible<key_equal>::value&&
1182
        std::is_nothrow_copy_constructible<allocator_type>::value)
1183
        : ctrl_(phmap::exchange(that.ctrl_, EmptyGroup())),
1184
        slots_(phmap::exchange(that.slots_, nullptr)),
1185
        size_(phmap::exchange(that.size_, 0)),
1186
        capacity_(phmap::exchange(that.capacity_, 0)),
1187
        infoz_(phmap::exchange(that.infoz_, HashtablezInfoHandle())),
1188
        // Hash, equality and allocator are copied instead of moved because
1189
        // `that` must be left valid. If Hash is std::function<Key>, moving it
1190
        // would create a nullptr functor that cannot be called.
1191
        settings_(std::move(that.settings_)) {
1192
        // growth_left was copied above, reset the one from `that`.
1193
        that.growth_left() = 0;
1194
    }
1195
1196
    raw_hash_set(raw_hash_set&& that, const allocator_type& a)
1197
        : ctrl_(EmptyGroup()),
1198
          slots_(nullptr),
1199
          size_(0),
1200
          capacity_(0),
1201
          settings_(0, that.hash_ref(), that.eq_ref(), a) {
1202
        if (a == that.alloc_ref()) {
1203
            std::swap(ctrl_, that.ctrl_);
1204
            std::swap(slots_, that.slots_);
1205
            std::swap(size_, that.size_);
1206
            std::swap(capacity_, that.capacity_);
1207
            std::swap(growth_left(), that.growth_left());
1208
            std::swap(infoz_, that.infoz_);
1209
        } else {
1210
            reserve(that.size());
1211
            // Note: this will copy elements of dense_set and unordered_set instead of
1212
            // moving them. This can be fixed if it ever becomes an issue.
1213
            for (auto& elem : that) insert(std::move(elem));
1214
        }
1215
    }
1216
1217
    raw_hash_set& operator=(const raw_hash_set& that) {
1218
        raw_hash_set tmp(that,
1219
                         AllocTraits::propagate_on_container_copy_assignment::value
1220
                         ? that.alloc_ref()
1221
                         : alloc_ref());
1222
        swap(tmp);
1223
        return *this;
1224
    }
1225
1226
    raw_hash_set& operator=(raw_hash_set&& that) noexcept(
1227
        phmap::allocator_traits<allocator_type>::is_always_equal::value&&
1228
        std::is_nothrow_move_assignable<hasher>::value&&
1229
        std::is_nothrow_move_assignable<key_equal>::value) {
1230
        // TODO(sbenza): We should only use the operations from the noexcept clause
1231
        // to make sure we actually adhere to that contract.
1232
        return move_assign(
1233
            std::move(that),
1234
            typename AllocTraits::propagate_on_container_move_assignment());
1235
    }
1236
1237
2.02k
    ~raw_hash_set() { destroy_slots(); }
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::~raw_hash_set()
Line
Count
Source
1237
1.51k
    ~raw_hash_set() { destroy_slots(); }
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::~raw_hash_set()
Line
Count
Source
1237
506
    ~raw_hash_set() { destroy_slots(); }
1238
1239
679
    iterator begin() {
1240
679
        auto it = iterator_at(0);
1241
679
        it.skip_empty_or_deleted();
1242
679
        return it;
1243
679
    }
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::begin()
Line
Count
Source
1239
173
    iterator begin() {
1240
173
        auto it = iterator_at(0);
1241
173
        it.skip_empty_or_deleted();
1242
173
        return it;
1243
173
    }
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::begin()
Line
Count
Source
1239
506
    iterator begin() {
1240
506
        auto it = iterator_at(0);
1241
506
        it.skip_empty_or_deleted();
1242
506
        return it;
1243
506
    }
1244
    iterator end() 
1245
679
    {
1246
#if 0 // PHMAP_BIDIRECTIONAL
1247
        return iterator_at(capacity_); 
1248
#else
1249
679
        return {ctrl_ + capacity_};
1250
679
#endif
1251
679
    }
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::end()
Line
Count
Source
1245
173
    {
1246
#if 0 // PHMAP_BIDIRECTIONAL
1247
        return iterator_at(capacity_); 
1248
#else
1249
173
        return {ctrl_ + capacity_};
1250
173
#endif
1251
173
    }
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::end()
Line
Count
Source
1245
506
    {
1246
#if 0 // PHMAP_BIDIRECTIONAL
1247
        return iterator_at(capacity_); 
1248
#else
1249
506
        return {ctrl_ + capacity_};
1250
506
#endif
1251
506
    }
1252
1253
173
    const_iterator begin() const {
1254
173
        return const_cast<raw_hash_set*>(this)->begin();
1255
173
    }
1256
173
    const_iterator end() const { return const_cast<raw_hash_set*>(this)->end(); }
1257
    const_iterator cbegin() const { return begin(); }
1258
    const_iterator cend() const { return end(); }
1259
1260
    bool empty() const { return !size(); }
1261
3.35k
    size_t size() const { return size_; }
1262
2.69k
    size_t capacity() const { return capacity_; }
1263
    size_t max_size() const { return (std::numeric_limits<size_t>::max)(); }
1264
1265
    PHMAP_ATTRIBUTE_REINITIALIZES void clear() {
1266
        if (empty())
1267
            return;
1268
        if (capacity_) {
1269
           PHMAP_IF_CONSTEXPR((!std::is_trivially_destructible<typename PolicyTraits::value_type>::value ||
1270
                               std::is_same<typename Policy::is_flat, std::false_type>::value)) {
1271
                // node map or not trivially destructible... we  need to iterate and destroy values one by one
1272
                for (size_t i = 0; i != capacity_; ++i) {
1273
                    if (IsFull(ctrl_[i])) {
1274
                        PolicyTraits::destroy(&alloc_ref(), slots_ + i);
1275
                    }
1276
                }
1277
            }
1278
            size_ = 0;
1279
            reset_ctrl(capacity_);
1280
            reset_growth_left(capacity_);
1281
        }
1282
        assert(empty());
1283
        infoz_.RecordStorageChanged(0, capacity_);
1284
    }
1285
1286
    // This overload kicks in when the argument is an rvalue of insertable and
1287
    // decomposable type other than init_type.
1288
    //
1289
    //   flat_hash_map<std::string, int> m;
1290
    //   m.insert(std::make_pair("abc", 42));
1291
    template <class T, RequiresInsertable<T> = 0,
1292
              typename std::enable_if<IsDecomposable<T>::value, int>::type = 0,
1293
              T* = nullptr>
1294
8.01M
    std::pair<iterator, bool> insert(T&& value) {
1295
8.01M
        return emplace(std::forward<T>(value));
1296
8.01M
    }
1297
1298
    // This overload kicks in when the argument is a bitfield or an lvalue of
1299
    // insertable and decomposable type.
1300
    //
1301
    //   union { int n : 1; };
1302
    //   flat_hash_set<int> s;
1303
    //   s.insert(n);
1304
    //
1305
    //   flat_hash_set<std::string> s;
1306
    //   const char* p = "hello";
1307
    //   s.insert(p);
1308
    //
1309
    // TODO(romanp): Once we stop supporting gcc 5.1 and below, replace
1310
    // RequiresInsertable<T> with RequiresInsertable<const T&>.
1311
    // We are hitting this bug: https://godbolt.org/g/1Vht4f.
1312
    template <class T, RequiresInsertable<T> = 0,
1313
              typename std::enable_if<IsDecomposable<const T&>::value, int>::type = 0>
1314
    std::pair<iterator, bool> insert(const T& value) {
1315
        return emplace(value);
1316
    }
1317
1318
    // This overload kicks in when the argument is an rvalue of init_type. Its
1319
    // purpose is to handle brace-init-list arguments.
1320
    //
1321
    //   flat_hash_set<std::string, int> s;
1322
    //   s.insert({"abc", 42});
1323
    std::pair<iterator, bool> insert(init_type&& value) {
1324
        return emplace(std::move(value));
1325
    }
1326
1327
    template <class T, RequiresInsertable<T> = 0,
1328
              typename std::enable_if<IsDecomposable<T>::value, int>::type = 0,
1329
              T* = nullptr>
1330
    iterator insert(const_iterator, T&& value) {
1331
        return insert(std::forward<T>(value)).first;
1332
    }
1333
1334
    // TODO(romanp): Once we stop supporting gcc 5.1 and below, replace
1335
    // RequiresInsertable<T> with RequiresInsertable<const T&>.
1336
    // We are hitting this bug: https://godbolt.org/g/1Vht4f.
1337
    template <class T, RequiresInsertable<T> = 0,
1338
              typename std::enable_if<IsDecomposable<const T&>::value, int>::type = 0>
1339
    iterator insert(const_iterator, const T& value) {
1340
        return insert(value).first;
1341
    }
1342
1343
    iterator insert(const_iterator, init_type&& value) {
1344
        return insert(std::move(value)).first;
1345
    }
1346
1347
    template <typename It>
1348
    using IsRandomAccess = std::is_same<typename std::iterator_traits<It>::iterator_category,
1349
                                        std::random_access_iterator_tag>;
1350
1351
1352
    template<typename T>
1353
    struct has_difference_operator
1354
    {
1355
    private:
1356
        using yes = std::true_type;
1357
        using no  = std::false_type;
1358
 
1359
        template<typename U> static auto test(int) -> decltype(std::declval<U>() - std::declval<U>() == 1, yes());
1360
        template<typename>   static no   test(...);
1361
 
1362
    public:
1363
        static constexpr bool value = std::is_same<decltype(test<T>(0)), yes>::value;
1364
    };
1365
1366
    template <class InputIt, typename phmap::enable_if_t<has_difference_operator<InputIt>::value, int> = 0>
1367
    void insert(InputIt first, InputIt last) {
1368
        this->reserve(this->size() + (last - first));
1369
        for (; first != last; ++first) 
1370
            emplace(*first);
1371
    }
1372
1373
    template <class InputIt, typename phmap::enable_if_t<!has_difference_operator<InputIt>::value, int> = 0>
1374
    void insert(InputIt first, InputIt last) {
1375
        for (; first != last; ++first) 
1376
            emplace(*first);
1377
    }
1378
1379
    template <class T, RequiresNotInit<T> = 0, RequiresInsertable<const T&> = 0>
1380
    void insert(std::initializer_list<T> ilist) {
1381
        insert(ilist.begin(), ilist.end());
1382
    }
1383
1384
    void insert(std::initializer_list<init_type> ilist) {
1385
        insert(ilist.begin(), ilist.end());
1386
    }
1387
1388
    insert_return_type insert(node_type&& node) {
1389
        if (!node) return {end(), false, node_type()};
1390
        const auto& elem = PolicyTraits::element(CommonAccess::GetSlot(node));
1391
        auto res = PolicyTraits::apply(
1392
            InsertSlot<false>{*this, std::move(*CommonAccess::GetSlot(node))},
1393
            elem);
1394
        if (res.second) {
1395
            CommonAccess::Reset(&node);
1396
            return {res.first, true, node_type()};
1397
        } else {
1398
            return {res.first, false, std::move(node)};
1399
        }
1400
    }
1401
1402
    insert_return_type insert(node_type&& node, size_t hashval) {
1403
        if (!node) return {end(), false, node_type()};
1404
        const auto& elem = PolicyTraits::element(CommonAccess::GetSlot(node));
1405
        auto res = PolicyTraits::apply(
1406
            InsertSlotWithHash<false>{*this, std::move(*CommonAccess::GetSlot(node)), hashval},
1407
            elem);
1408
        if (res.second) {
1409
            CommonAccess::Reset(&node);
1410
            return {res.first, true, node_type()};
1411
        } else {
1412
            return {res.first, false, std::move(node)};
1413
        }
1414
    }
1415
1416
    iterator insert(const_iterator, node_type&& node) {
1417
        auto res = insert(std::move(node));
1418
        node = std::move(res.node);
1419
        return res.position;
1420
    }
1421
1422
    // This overload kicks in if we can deduce the key from args. This enables us
1423
    // to avoid constructing value_type if an entry with the same key already
1424
    // exists.
1425
    //
1426
    // For example:
1427
    //
1428
    //   flat_hash_map<std::string, std::string> m = {{"abc", "def"}};
1429
    //   // Creates no std::string copies and makes no heap allocations.
1430
    //   m.emplace("abc", "xyz");
1431
    template <class... Args, typename std::enable_if<
1432
                                 IsDecomposable<Args...>::value, int>::type = 0>
1433
8.01M
    std::pair<iterator, bool> emplace(Args&&... args) {
1434
8.01M
        return PolicyTraits::apply(EmplaceDecomposable{*this},
1435
8.01M
                                   std::forward<Args>(args)...);
1436
8.01M
    }
1437
1438
    template <class... Args, typename std::enable_if<IsDecomposable<Args...>::value, int>::type = 0>
1439
    std::pair<iterator, bool> emplace_with_hash(size_t hashval, Args&&... args) {
1440
        return PolicyTraits::apply(EmplaceDecomposableHashval{*this, hashval}, std::forward<Args>(args)...);
1441
    }
1442
1443
    // This overload kicks in if we cannot deduce the key from args. It constructs
1444
    // value_type unconditionally and then either moves it into the table or
1445
    // destroys.
1446
    template <class... Args, typename std::enable_if<!IsDecomposable<Args...>::value, int>::type = 0>
1447
    std::pair<iterator, bool> emplace(Args&&... args) {
1448
        typename phmap::aligned_storage<sizeof(slot_type), alignof(slot_type)>::type
1449
            raw;
1450
        slot_type* slot = reinterpret_cast<slot_type*>(&raw);
1451
1452
        PolicyTraits::construct(&alloc_ref(), slot, std::forward<Args>(args)...);
1453
        const auto& elem = PolicyTraits::element(slot);
1454
        return PolicyTraits::apply(InsertSlot<true>{*this, std::move(*slot)}, elem);
1455
    }
1456
1457
    template <class... Args, typename std::enable_if<!IsDecomposable<Args...>::value, int>::type = 0>
1458
    std::pair<iterator, bool> emplace_with_hash(size_t hashval, Args&&... args) {
1459
        typename phmap::aligned_storage<sizeof(slot_type), alignof(slot_type)>::type raw;
1460
        slot_type* slot = reinterpret_cast<slot_type*>(&raw);
1461
1462
        PolicyTraits::construct(&alloc_ref(), slot, std::forward<Args>(args)...);
1463
        const auto& elem = PolicyTraits::element(slot);
1464
        return PolicyTraits::apply(InsertSlotWithHash<true>{*this, std::move(*slot), hashval}, elem);
1465
    }
1466
1467
    template <class... Args>
1468
    iterator emplace_hint(const_iterator, Args&&... args) {
1469
        return emplace(std::forward<Args>(args)...).first;
1470
    }
1471
1472
    template <class... Args>
1473
    iterator emplace_hint_with_hash(size_t hashval, const_iterator, Args&&... args) {
1474
        return emplace_with_hash(hashval, std::forward<Args>(args)...).first;
1475
    }
1476
1477
    // Extension API: support for lazy emplace.
1478
    //
1479
    // Looks up key in the table. If found, returns the iterator to the element.
1480
    // Otherwise calls f with one argument of type raw_hash_set::constructor. f
1481
    // MUST call raw_hash_set::constructor with arguments as if a
1482
    // raw_hash_set::value_type is constructed, otherwise the behavior is
1483
    // undefined.
1484
    //
1485
    // For example:
1486
    //
1487
    //   std::unordered_set<ArenaString> s;
1488
    //   // Makes ArenaStr even if "abc" is in the map.
1489
    //   s.insert(ArenaString(&arena, "abc"));
1490
    //
1491
    //   flat_hash_set<ArenaStr> s;
1492
    //   // Makes ArenaStr only if "abc" is not in the map.
1493
    //   s.lazy_emplace("abc", [&](const constructor& ctor) {
1494
    //     ctor(&arena, "abc");
1495
    //   });
1496
    //
1497
    // WARNING: This API is currently experimental. If there is a way to implement
1498
    // the same thing with the rest of the API, prefer that.
1499
    class constructor 
1500
    {
1501
        friend class raw_hash_set;
1502
1503
    public:
1504
        slot_type* slot() const {
1505
            return *slot_;
1506
        }
1507
1508
        template <class... Args>
1509
        void operator()(Args&&... args) const {
1510
            assert(*slot_);
1511
            PolicyTraits::construct(alloc_, *slot_, std::forward<Args>(args)...);
1512
            *slot_ = nullptr;
1513
        }
1514
1515
    private:
1516
        constructor(allocator_type* a, slot_type** slot) : alloc_(a), slot_(slot) {}
1517
1518
        allocator_type* alloc_;
1519
        slot_type** slot_;
1520
    };
1521
1522
    // Extension API: support for lazy emplace.
1523
    // Looks up key in the table. If found, returns the iterator to the element.
1524
    // Otherwise calls f with one argument of type raw_hash_set::constructor. f
1525
    // MUST call raw_hash_set::constructor with arguments as if a
1526
    // raw_hash_set::value_type is constructed, otherwise the behavior is
1527
    // undefined.
1528
    //
1529
    // For example:
1530
    //
1531
    //   std::unordered_set<ArenaString> s;
1532
    //   // Makes ArenaStr even if "abc" is in the map.
1533
    //   s.insert(ArenaString(&arena, "abc"));
1534
    //
1535
    //   flat_hash_set<ArenaStr> s;
1536
    //   // Makes ArenaStr only if "abc" is not in the map.
1537
    //   s.lazy_emplace("abc", [&](const constructor& ctor) {
1538
    //                         ctor(&arena, "abc");
1539
    //   });
1540
    // -----------------------------------------------------
1541
    template <class K = key_type, class F>
1542
    iterator lazy_emplace(const key_arg<K>& key, F&& f) {
1543
        return lazy_emplace_with_hash(key, this->hash(key), std::forward<F>(f));
1544
    }
1545
1546
    template <class K = key_type, class F>
1547
    iterator lazy_emplace_with_hash(const key_arg<K>& key, size_t hashval, F&& f) {
1548
        size_t offset = _find_key(key, hashval);
1549
        if (offset == (size_t)-1) {
1550
            offset = prepare_insert(hashval);
1551
            lazy_emplace_at(offset, std::forward<F>(f));
1552
            this->set_ctrl(offset, H2(hashval));
1553
        }
1554
        return iterator_at(offset);
1555
    }
1556
1557
    template <class K = key_type, class F>
1558
    void lazy_emplace_at(size_t& idx, F&& f) {
1559
        slot_type* slot = slots_ + idx;
1560
        std::forward<F>(f)(constructor(&alloc_ref(), &slot));
1561
        assert(!slot);
1562
    }
1563
1564
    template <class K = key_type, class F>
1565
    void emplace_single_with_hash(const key_arg<K>& key, size_t hashval, F&& f) {
1566
        size_t offset = _find_key(key, hashval);
1567
        if (offset == (size_t)-1) {
1568
            offset = prepare_insert(hashval);
1569
            lazy_emplace_at(offset, std::forward<F>(f));
1570
            this->set_ctrl(offset, H2(hashval));
1571
        } else
1572
            _erase(iterator_at(offset));
1573
    }
1574
1575
1576
    // Extension API: support for heterogeneous keys.
1577
    //
1578
    //   std::unordered_set<std::string> s;
1579
    //   // Turns "abc" into std::string.
1580
    //   s.erase("abc");
1581
    //
1582
    //   flat_hash_set<std::string> s;
1583
    //   // Uses "abc" directly without copying it into std::string.
1584
    //   s.erase("abc");
1585
    template <class K = key_type>
1586
    size_type erase(const key_arg<K>& key) {
1587
        auto it = find(key);
1588
        if (it == end()) return 0;
1589
        _erase(it);
1590
        return 1;
1591
    }
1592
1593
1594
    iterator erase(const_iterator cit) { return erase(cit.inner_); }
1595
    
1596
    // Erases the element pointed to by `it`.  Unlike `std::unordered_set::erase`,
1597
    // this method returns void to reduce algorithmic complexity to O(1).  In
1598
    // order to erase while iterating across a map, use the following idiom (which
1599
    // also works for standard containers):
1600
    //
1601
    // for (auto it = m.begin(), end = m.end(); it != end;) {
1602
    //   if (<pred>) {
1603
    //     m._erase(it++);
1604
    //   } else {
1605
    //     ++it;
1606
    //   }
1607
    // }
1608
    void _erase(iterator it) {
1609
        assert(it != end());
1610
        PolicyTraits::destroy(&alloc_ref(), it.slot_);
1611
        erase_meta_only(it);
1612
    }
1613
    void _erase(const_iterator cit) { _erase(cit.inner_); }
1614
1615
    // This overload is necessary because otherwise erase<K>(const K&) would be
1616
    // a better match if non-const iterator is passed as an argument.
1617
    iterator erase(iterator it) {
1618
        auto res = it;
1619
        ++res;
1620
        _erase(it);
1621
        return res;
1622
    }
1623
1624
    iterator erase(const_iterator first, const_iterator last) {
1625
        while (first != last) {
1626
            _erase(first++);
1627
        }
1628
        return last.inner_;
1629
    }
1630
1631
    // Moves elements from `src` into `this`.
1632
    // If the element already exists in `this`, it is left unmodified in `src`.
1633
    template <typename H, typename E>
1634
    void merge(raw_hash_set<Policy, H, E, Alloc>& src) {  // NOLINT
1635
        assert(this != &src);
1636
        for (auto it = src.begin(), e = src.end(); it != e; ++it) {
1637
            if (PolicyTraits::apply(InsertSlot<false>{*this, std::move(*it.slot_)},
1638
                                    PolicyTraits::element(it.slot_))
1639
                .second) {
1640
                src.erase_meta_only(it);
1641
            }
1642
        }
1643
    }
1644
1645
    template <typename H, typename E>
1646
    void merge(raw_hash_set<Policy, H, E, Alloc>&& src) {
1647
        merge(src);
1648
    }
1649
1650
    node_type extract(const_iterator position) {
1651
        auto node =
1652
            CommonAccess::Make<node_type>(alloc_ref(), position.inner_.slot_);
1653
        erase_meta_only(position);
1654
        return node;
1655
    }
1656
1657
    template <
1658
        class K = key_type,
1659
        typename std::enable_if<!std::is_same<K, iterator>::value, int>::type = 0>
1660
    node_type extract(const key_arg<K>& key) {
1661
        auto it = find(key);
1662
        return it == end() ? node_type() : extract(const_iterator{it});
1663
    }
1664
1665
    void swap(raw_hash_set& that) noexcept(
1666
        IsNoThrowSwappable<hasher>() && IsNoThrowSwappable<key_equal>() &&
1667
        (!AllocTraits::propagate_on_container_swap::value ||
1668
506
         IsNoThrowSwappable<allocator_type>(typename AllocTraits::propagate_on_container_swap{}))) {
1669
506
        using std::swap;
1670
506
        swap(ctrl_, that.ctrl_);
1671
506
        swap(slots_, that.slots_);
1672
506
        swap(size_, that.size_);
1673
506
        swap(capacity_, that.capacity_);
1674
506
        swap(growth_left(), that.growth_left());
1675
506
        swap(hash_ref(), that.hash_ref());
1676
506
        swap(eq_ref(), that.eq_ref());
1677
506
        swap(infoz_, that.infoz_);
1678
506
        SwapAlloc(alloc_ref(), that.alloc_ref(), typename AllocTraits::propagate_on_container_swap{});
1679
506
    }
1680
1681
#if !defined(PHMAP_NON_DETERMINISTIC)
1682
    template<typename OutputArchive>
1683
    bool phmap_dump(OutputArchive&) const;
1684
1685
    template<typename InputArchive>
1686
    bool  phmap_load(InputArchive&);
1687
#endif
1688
1689
    void rehash(size_t n) {
1690
        if (n == 0 && capacity_ == 0) return;
1691
        if (n == 0 && size_ == 0) {
1692
            destroy_slots();
1693
            infoz_.RecordStorageChanged(0, 0);
1694
            return;
1695
        }
1696
        // bitor is a faster way of doing `max` here. We will round up to the next
1697
        // power-of-2-minus-1, so bitor is good enough.
1698
        auto m = NormalizeCapacity((std::max)(n, size()));
1699
        // n == 0 unconditionally rehashes as per the standard.
1700
        if (n == 0 || m > capacity_) {
1701
            resize(m);
1702
        }
1703
    }
1704
1705
    void reserve(size_t n) { rehash(GrowthToLowerboundCapacity(n)); }
1706
1707
    // Extension API: support for heterogeneous keys.
1708
    //
1709
    //   std::unordered_set<std::string> s;
1710
    //   // Turns "abc" into std::string.
1711
    //   s.count("abc");
1712
    //
1713
    //   ch_set<std::string> s;
1714
    //   // Uses "abc" directly without copying it into std::string.
1715
    //   s.count("abc");
1716
    template <class K = key_type>
1717
    size_t count(const key_arg<K>& key) const {
1718
        return find(key) == end() ? size_t(0) : size_t(1);
1719
    }
1720
1721
    // Issues CPU prefetch instructions for the memory needed to find or insert
1722
    // a key.  Like all lookup functions, this support heterogeneous keys.
1723
    //
1724
    // NOTE: This is a very low level operation and should not be used without
1725
    // specific benchmarks indicating its importance.
1726
    void prefetch_hash(size_t hashval) const {
1727
        (void)hashval;
1728
#if defined(_MSC_VER) && (defined(_M_X64) || defined(_M_IX86))
1729
        auto seq = probe(hashval);
1730
        _mm_prefetch((const char *)(ctrl_ + seq.offset()), _MM_HINT_NTA);
1731
        _mm_prefetch((const char *)(slots_ + seq.offset()), _MM_HINT_NTA);
1732
#elif defined(__GNUC__)
1733
        auto seq = probe(hashval);
1734
        __builtin_prefetch(static_cast<const void*>(ctrl_ + seq.offset()));
1735
        __builtin_prefetch(static_cast<const void*>(slots_ + seq.offset()));
1736
#endif  // __GNUC__
1737
    }
1738
1739
    template <class K = key_type>
1740
    void prefetch(const key_arg<K>& key) const {
1741
        prefetch_hash(this->hash(key));
1742
    }
1743
1744
    // The API of find() has two extensions.
1745
    //
1746
    // 1. The hash can be passed by the user. It must be equal to the hash of the
1747
    // key.
1748
    //
1749
    // 2. The type of the key argument doesn't have to be key_type. This is so
1750
    // called heterogeneous key support.
1751
    template <class K = key_type>
1752
    iterator find(const key_arg<K>& key, size_t hashval) {
1753
        size_t offset;
1754
        if (find_impl(key, hashval, offset))
1755
            return iterator_at(offset);
1756
        else
1757
            return end();
1758
    }
1759
1760
    template <class K = key_type>
1761
    pointer find_ptr(const key_arg<K>& key, size_t hashval) {
1762
        size_t offset;
1763
        if (find_impl(key, hashval, offset))
1764
            return &PolicyTraits::element(slots_ + offset);
1765
        else
1766
            return nullptr;
1767
    }
1768
1769
    template <class K = key_type>
1770
    iterator find(const key_arg<K>& key) {
1771
        return find(key, this->hash(key));
1772
    }
1773
1774
    template <class K = key_type>
1775
    const_iterator find(const key_arg<K>& key, size_t hashval) const {
1776
        return const_cast<raw_hash_set*>(this)->find(key, hashval);
1777
    }
1778
    template <class K = key_type>
1779
    const_iterator find(const key_arg<K>& key) const {
1780
        return find(key, this->hash(key));
1781
    }
1782
1783
    template <class K = key_type>
1784
    bool contains(const key_arg<K>& key) const {
1785
        return find(key) != end();
1786
    }
1787
1788
    template <class K = key_type>
1789
    bool contains(const key_arg<K>& key, size_t hashval) const {
1790
        return find(key, hashval) != end();
1791
    }
1792
1793
    template <class K = key_type>
1794
    std::pair<iterator, iterator> equal_range(const key_arg<K>& key) {
1795
        auto it = find(key);
1796
        if (it != end()) return {it, std::next(it)};
1797
        return {it, it};
1798
    }
1799
    template <class K = key_type>
1800
    std::pair<const_iterator, const_iterator> equal_range(
1801
        const key_arg<K>& key) const {
1802
        auto it = find(key);
1803
        if (it != end()) return {it, std::next(it)};
1804
        return {it, it};
1805
    }
1806
1807
    size_t bucket_count() const { return capacity_; }
1808
    float load_factor() const {
1809
        return capacity_ ? static_cast<float>(static_cast<double>(size()) / capacity_) : 0.0f;
1810
    }
1811
    float max_load_factor() const { return 1.0f; }
1812
    void max_load_factor(float) {
1813
        // Does nothing.
1814
    }
1815
1816
    hasher hash_function() const { return hash_ref(); } // warning: doesn't match internal hash - use hash() member function
1817
    key_equal key_eq() const { return eq_ref(); }
1818
    allocator_type get_allocator() const { return alloc_ref(); }
1819
1820
506
    friend bool operator==(const raw_hash_set& a, const raw_hash_set& b) {
1821
506
        if (a.size() != b.size()) return false;
1822
173
        const raw_hash_set* outer = &a;
1823
173
        const raw_hash_set* inner = &b;
1824
173
        if (outer->capacity() > inner->capacity()) 
1825
0
            std::swap(outer, inner);
1826
173
        for (const value_type& elem : *outer)
1827
521k
            if (!inner->has_element(elem)) return false;
1828
42
        return true;
1829
173
    }
1830
1831
    friend bool operator!=(const raw_hash_set& a, const raw_hash_set& b) {
1832
        return !(a == b);
1833
    }
1834
1835
    friend void swap(raw_hash_set& a,
1836
                     raw_hash_set& b) noexcept(noexcept(a.swap(b))) {
1837
        a.swap(b);
1838
    }
1839
1840
    template <class K>
1841
8.01M
    size_t hash(const K& key) const {
1842
8.01M
        return HashElement{hash_ref()}(key);
1843
8.01M
    }
1844
1845
private:
1846
    template <class Container, typename Enabler>
1847
    friend struct phmap::priv::hashtable_debug_internal::HashtableDebugAccess;
1848
1849
    template <class K = key_type>
1850
    bool find_impl(const key_arg<K>& key, size_t hashval, size_t& offset) {
1851
        auto seq = probe(hashval);
1852
        while (true) {
1853
            Group g{ ctrl_ + seq.offset() };
1854
            for (uint32_t i : g.Match((h2_t)H2(hashval))) {
1855
                offset = seq.offset((size_t)i);
1856
                if (PHMAP_PREDICT_TRUE(PolicyTraits::apply(
1857
                    EqualElement<K>{key, eq_ref()},
1858
                    PolicyTraits::element(slots_ + offset))))
1859
                    return true;
1860
            }
1861
            if (PHMAP_PREDICT_TRUE(g.MatchEmpty()))
1862
                return false;
1863
            seq.next();
1864
        }
1865
    }
1866
1867
    struct FindElement 
1868
    {
1869
        template <class K, class... Args>
1870
        const_iterator operator()(const K& key, Args&&...) const {
1871
            return s.find(key);
1872
        }
1873
        const raw_hash_set& s;
1874
    };
1875
1876
    struct HashElement 
1877
    {
1878
        template <class K, class... Args>
1879
9.49M
        size_t operator()(const K& key, Args&&...) const {
1880
9.49M
            return phmap_mix<sizeof(size_t)>()(h(key));
1881
9.49M
        }
unsigned long phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::HashElement::operator()<unsigned int, std::__1::piecewise_construct_t const&, std::__1::tuple<unsigned int const&>, std::__1::tuple<int const&> >(unsigned int const&, std::__1::piecewise_construct_t const&, std::__1::tuple<unsigned int const&>&&, std::__1::tuple<int const&>&&) const
Line
Count
Source
1879
1.47M
        size_t operator()(const K& key, Args&&...) const {
1880
1.47M
            return phmap_mix<sizeof(size_t)>()(h(key));
1881
1.47M
        }
unsigned long phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::HashElement::operator()<unsigned int>(unsigned int const&) const
Line
Count
Source
1879
8.01M
        size_t operator()(const K& key, Args&&...) const {
1880
8.01M
            return phmap_mix<sizeof(size_t)>()(h(key));
1881
8.01M
        }
1882
        const hasher& h;
1883
    };
1884
1885
    template <class K1>
1886
    struct EqualElement 
1887
    {
1888
        template <class K2, class... Args>
1889
10.4M
        bool operator()(const K2& lhs, Args&&...) const {
1890
10.4M
            return eq(lhs, rhs);
1891
10.4M
        }
1892
        const K1& rhs;
1893
        const key_equal& eq;
1894
    };
1895
1896
    template <class K, class... Args>
1897
    std::pair<iterator, bool> emplace_decomposable(const K& key, size_t hashval, 
1898
                                                   Args&&... args)
1899
8.01M
    {
1900
8.01M
        size_t offset = _find_key(key, hashval);
1901
8.01M
        if (offset == (size_t)-1) {
1902
536k
            offset = prepare_insert(hashval);
1903
536k
            emplace_at(offset, std::forward<Args>(args)...);
1904
536k
            this->set_ctrl(offset, H2(hashval));
1905
536k
            return {iterator_at(offset), true};
1906
536k
        }
1907
7.48M
        return {iterator_at(offset), false};
1908
8.01M
    }
1909
1910
    struct EmplaceDecomposable 
1911
    {
1912
        template <class K, class... Args>
1913
8.01M
        std::pair<iterator, bool> operator()(const K& key, Args&&... args) const {
1914
8.01M
            return s.emplace_decomposable(key, s.hash(key), std::forward<Args>(args)...);
1915
8.01M
        }
1916
        raw_hash_set& s;
1917
    };
1918
1919
    struct EmplaceDecomposableHashval {
1920
        template <class K, class... Args>
1921
        std::pair<iterator, bool> operator()(const K& key, Args&&... args) const {
1922
            return s.emplace_decomposable(key, hashval, std::forward<Args>(args)...);
1923
        }
1924
        raw_hash_set& s;
1925
        size_t hashval;
1926
    };
1927
1928
    template <bool do_destroy>
1929
    struct InsertSlot 
1930
    {
1931
        template <class K, class... Args>
1932
        std::pair<iterator, bool> operator()(const K& key, Args&&...) && {
1933
            size_t hashval = s.hash(key);
1934
            auto res = s.find_or_prepare_insert(key, hashval);
1935
            if (res.second) {
1936
                PolicyTraits::transfer(&s.alloc_ref(), s.slots_ + res.first, &slot);
1937
                s.set_ctrl(res.first, H2(hashval));
1938
            } else if (do_destroy) {
1939
                PolicyTraits::destroy(&s.alloc_ref(), &slot);
1940
            }
1941
            return {s.iterator_at(res.first), res.second};
1942
        }
1943
        raw_hash_set& s;
1944
        // Constructed slot. Either moved into place or destroyed.
1945
        slot_type&& slot;
1946
    };
1947
1948
    template <bool do_destroy>
1949
    struct InsertSlotWithHash 
1950
    {
1951
        template <class K, class... Args>
1952
        std::pair<iterator, bool> operator()(const K& key, Args&&...) && {
1953
            auto res = s.find_or_prepare_insert(key, hashval);
1954
            if (res.second) {
1955
                PolicyTraits::transfer(&s.alloc_ref(), s.slots_ + res.first, &slot);
1956
                s.set_ctrl(res.first, H2(hashval));
1957
            } else if (do_destroy) {
1958
                PolicyTraits::destroy(&s.alloc_ref(), &slot);
1959
            }
1960
            return {s.iterator_at(res.first), res.second};
1961
        }
1962
        raw_hash_set& s;
1963
        // Constructed slot. Either moved into place or destroyed.
1964
        slot_type&& slot;
1965
        size_t &hashval;
1966
    };
1967
1968
    // "erases" the object from the container, except that it doesn't actually
1969
    // destroy the object. It only updates all the metadata of the class.
1970
    // This can be used in conjunction with Policy::transfer to move the object to
1971
    // another place.
1972
    void erase_meta_only(const_iterator it) {
1973
        assert(IsFull(*it.inner_.ctrl_) && "erasing a dangling iterator");
1974
        --size_;
1975
        const size_t index = (size_t)(it.inner_.ctrl_ - ctrl_);
1976
        const size_t index_before = (index - Group::kWidth) & capacity_;
1977
        const auto empty_after = Group(it.inner_.ctrl_).MatchEmpty();
1978
        const auto empty_before = Group(ctrl_ + index_before).MatchEmpty();
1979
1980
        // We count how many consecutive non empties we have to the right and to the
1981
        // left of `it`. If the sum is >= kWidth then there is at least one probe
1982
        // window that might have seen a full group.
1983
        bool was_never_full =
1984
            empty_before && empty_after &&
1985
            static_cast<size_t>(empty_after.TrailingZeros() +
1986
                                empty_before.LeadingZeros()) < Group::kWidth;
1987
1988
        set_ctrl(index, was_never_full ? kEmpty : kDeleted);
1989
        growth_left() += was_never_full;
1990
        infoz_.RecordErase();
1991
    }
1992
1993
2.95k
    void initialize_slots(size_t new_capacity) {
1994
2.95k
        assert(new_capacity);
1995
2.95k
        if (std::is_same<SlotAlloc, std::allocator<slot_type>>::value && 
1996
2.95k
            slots_ == nullptr) {
1997
607
            infoz_ = Sample();
1998
607
        }
1999
2000
2.95k
        auto layout = MakeLayout(new_capacity);
2001
2.95k
        char* mem = static_cast<char*>(
2002
2.95k
            Allocate<Layout::Alignment()>(&alloc_ref(), layout.AllocSize()));
2003
2.95k
        ctrl_ = reinterpret_cast<ctrl_t*>(layout.template Pointer<0>(mem));
2004
2.95k
        slots_ = layout.template Pointer<1>(mem);
2005
2.95k
        reset_ctrl(new_capacity);
2006
2.95k
        reset_growth_left(new_capacity);
2007
2.95k
        infoz_.RecordStorageChanged(size_, new_capacity);
2008
2.95k
    }
2009
2010
2.02k
    void destroy_slots() {
2011
2.02k
        if (!capacity_)
2012
1.41k
            return;
2013
        
2014
607
        PHMAP_IF_CONSTEXPR((!std::is_trivially_destructible<typename PolicyTraits::value_type>::value ||
2015
607
                            std::is_same<typename Policy::is_flat, std::false_type>::value)) {
2016
            // node map, or not trivially destructible... we  need to iterate and destroy values one by one
2017
            // std::cout << "either this is a node map or " << type_name<typename PolicyTraits::value_type>()  << " is not trivially_destructible\n";
2018
0
            for (size_t i = 0; i != capacity_; ++i) {
2019
0
                if (IsFull(ctrl_[i])) {
2020
0
                    PolicyTraits::destroy(&alloc_ref(), slots_ + i);
2021
0
                }
2022
0
            }
2023
0
        } 
2024
607
        auto layout = MakeLayout(capacity_);
2025
        // Unpoison before returning the memory to the allocator.
2026
607
        SanitizerUnpoisonMemoryRegion(slots_, sizeof(slot_type) * capacity_);
2027
607
        Deallocate<Layout::Alignment()>(&alloc_ref(), ctrl_, layout.AllocSize());
2028
607
        ctrl_ = EmptyGroup();
2029
607
        slots_ = nullptr;
2030
607
        size_ = 0;
2031
607
        capacity_ = 0;
2032
607
        growth_left() = 0;
2033
607
    }
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::destroy_slots()
Line
Count
Source
2010
1.51k
    void destroy_slots() {
2011
1.51k
        if (!capacity_)
2012
911
            return;
2013
        
2014
607
        PHMAP_IF_CONSTEXPR((!std::is_trivially_destructible<typename PolicyTraits::value_type>::value ||
2015
607
                            std::is_same<typename Policy::is_flat, std::false_type>::value)) {
2016
            // node map, or not trivially destructible... we  need to iterate and destroy values one by one
2017
            // std::cout << "either this is a node map or " << type_name<typename PolicyTraits::value_type>()  << " is not trivially_destructible\n";
2018
607
            for (size_t i = 0; i != capacity_; ++i) {
2019
607
                if (IsFull(ctrl_[i])) {
2020
607
                    PolicyTraits::destroy(&alloc_ref(), slots_ + i);
2021
607
                }
2022
607
            }
2023
607
        } 
2024
607
        auto layout = MakeLayout(capacity_);
2025
        // Unpoison before returning the memory to the allocator.
2026
607
        SanitizerUnpoisonMemoryRegion(slots_, sizeof(slot_type) * capacity_);
2027
607
        Deallocate<Layout::Alignment()>(&alloc_ref(), ctrl_, layout.AllocSize());
2028
607
        ctrl_ = EmptyGroup();
2029
607
        slots_ = nullptr;
2030
607
        size_ = 0;
2031
607
        capacity_ = 0;
2032
607
        growth_left() = 0;
2033
607
    }
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::destroy_slots()
Line
Count
Source
2010
506
    void destroy_slots() {
2011
506
        if (!capacity_)
2012
506
            return;
2013
        
2014
0
        PHMAP_IF_CONSTEXPR((!std::is_trivially_destructible<typename PolicyTraits::value_type>::value ||
2015
0
                            std::is_same<typename Policy::is_flat, std::false_type>::value)) {
2016
            // node map, or not trivially destructible... we  need to iterate and destroy values one by one
2017
            // std::cout << "either this is a node map or " << type_name<typename PolicyTraits::value_type>()  << " is not trivially_destructible\n";
2018
0
            for (size_t i = 0; i != capacity_; ++i) {
2019
0
                if (IsFull(ctrl_[i])) {
2020
0
                    PolicyTraits::destroy(&alloc_ref(), slots_ + i);
2021
0
                }
2022
0
            }
2023
0
        } 
2024
0
        auto layout = MakeLayout(capacity_);
2025
        // Unpoison before returning the memory to the allocator.
2026
0
        SanitizerUnpoisonMemoryRegion(slots_, sizeof(slot_type) * capacity_);
2027
0
        Deallocate<Layout::Alignment()>(&alloc_ref(), ctrl_, layout.AllocSize());
2028
0
        ctrl_ = EmptyGroup();
2029
0
        slots_ = nullptr;
2030
0
        size_ = 0;
2031
0
        capacity_ = 0;
2032
0
        growth_left() = 0;
2033
0
    }
2034
2035
2.81k
    void resize(size_t new_capacity) {
2036
2.81k
        assert(IsValidCapacity(new_capacity));
2037
2.81k
        auto* old_ctrl = ctrl_;
2038
2.81k
        auto* old_slots = slots_;
2039
2.81k
        const size_t old_capacity = capacity_;
2040
2.81k
        initialize_slots(new_capacity);
2041
2.81k
        capacity_ = new_capacity;
2042
2043
1.09M
        for (size_t i = 0; i != old_capacity; ++i) {
2044
1.09M
            if (IsFull(old_ctrl[i])) {
2045
958k
                size_t hashval = PolicyTraits::apply(HashElement{hash_ref()},
2046
958k
                                                     PolicyTraits::element(old_slots + i));
2047
958k
                auto target = find_first_non_full(hashval);
2048
958k
                size_t new_i = target.offset;
2049
958k
                set_ctrl(new_i, H2(hashval));
2050
958k
                PolicyTraits::transfer(&alloc_ref(), slots_ + new_i, old_slots + i);
2051
958k
            }
2052
1.09M
        }
2053
2.81k
        if (old_capacity) {
2054
2.34k
            SanitizerUnpoisonMemoryRegion(old_slots,
2055
2.34k
                                          sizeof(slot_type) * old_capacity);
2056
2.34k
            auto layout = MakeLayout(old_capacity);
2057
2.34k
            Deallocate<Layout::Alignment()>(&alloc_ref(), old_ctrl,
2058
2.34k
                                            layout.AllocSize());
2059
2.34k
        }
2060
2.81k
    }
2061
2062
0
    void drop_deletes_without_resize() PHMAP_ATTRIBUTE_NOINLINE {
2063
0
        assert(IsValidCapacity(capacity_));
2064
0
        assert(!is_small());
2065
        // Algorithm:
2066
        // - mark all DELETED slots as EMPTY
2067
        // - mark all FULL slots as DELETED
2068
        // - for each slot marked as DELETED
2069
        //     hash = Hash(element)
2070
        //     target = find_first_non_full(hash)
2071
        //     if target is in the same group
2072
        //       mark slot as FULL
2073
        //     else if target is EMPTY
2074
        //       transfer element to target
2075
        //       mark slot as EMPTY
2076
        //       mark target as FULL
2077
        //     else if target is DELETED
2078
        //       swap current element with target element
2079
        //       mark target as FULL
2080
        //       repeat procedure for current slot with moved from element (target)
2081
0
        ConvertDeletedToEmptyAndFullToDeleted(ctrl_, capacity_);
2082
0
        typename phmap::aligned_storage<sizeof(slot_type), alignof(slot_type)>::type
2083
0
            raw;
2084
0
        slot_type* slot = reinterpret_cast<slot_type*>(&raw);
2085
0
        for (size_t i = 0; i != capacity_; ++i) {
2086
0
            if (!IsDeleted(ctrl_[i])) continue;
2087
0
            size_t hashval = PolicyTraits::apply(HashElement{hash_ref()},
2088
0
                                                 PolicyTraits::element(slots_ + i));
2089
0
            auto target = find_first_non_full(hashval);
2090
0
            size_t new_i = target.offset;
2091
2092
            // Verify if the old and new i fall within the same group wrt the hashval.
2093
            // If they do, we don't need to move the object as it falls already in the
2094
            // best probe we can.
2095
0
            const auto probe_index = [&](size_t pos) {
2096
0
                return ((pos - probe(hashval).offset()) & capacity_) / Group::kWidth;
2097
0
            };
2098
2099
            // Element doesn't move.
2100
0
            if (PHMAP_PREDICT_TRUE(probe_index(new_i) == probe_index(i))) {
2101
0
                set_ctrl(i, H2(hashval));
2102
0
                continue;
2103
0
            }
2104
0
            if (IsEmpty(ctrl_[new_i])) {
2105
                // Transfer element to the empty spot.
2106
                // set_ctrl poisons/unpoisons the slots so we have to call it at the
2107
                // right time.
2108
0
                set_ctrl(new_i, H2(hashval));
2109
0
                PolicyTraits::transfer(&alloc_ref(), slots_ + new_i, slots_ + i);
2110
0
                set_ctrl(i, kEmpty);
2111
0
            } else {
2112
0
                assert(IsDeleted(ctrl_[new_i]));
2113
0
                set_ctrl(new_i, H2(hashval));
2114
                // Until we are done rehashing, DELETED marks previously FULL slots.
2115
                // Swap i and new_i elements.
2116
0
                PolicyTraits::transfer(&alloc_ref(), slot, slots_ + i);
2117
0
                PolicyTraits::transfer(&alloc_ref(), slots_ + i, slots_ + new_i);
2118
0
                PolicyTraits::transfer(&alloc_ref(), slots_ + new_i, slot);
2119
0
                --i;  // repeat
2120
0
            }
2121
0
        }
2122
0
        reset_growth_left(capacity_);
2123
0
    }
2124
2125
2.81k
    void rehash_and_grow_if_necessary() {
2126
2.81k
        if (capacity_ == 0) {
2127
470
            resize(1);
2128
2.34k
        } else if (size() <= CapacityToGrowth(capacity()) / 2) {
2129
            // Squash DELETED without growing if there is enough capacity.
2130
0
            drop_deletes_without_resize();
2131
2.34k
        } else {
2132
            // Otherwise grow the container.
2133
2.34k
            resize(capacity_ * 2 + 1);
2134
2.34k
        }
2135
2.81k
    }
2136
2137
521k
    bool has_element(const value_type& elem, size_t hashval) const {
2138
521k
        auto seq = probe(hashval);
2139
522k
        while (true) {
2140
522k
            Group g{ctrl_ + seq.offset()};
2141
523k
            for (uint32_t i : g.Match((h2_t)H2(hashval))) {
2142
523k
                if (PHMAP_PREDICT_TRUE(PolicyTraits::element(slots_ + seq.offset((size_t)i)) ==
2143
523k
                                      elem))
2144
521k
                    return true;
2145
523k
            }
2146
1.60k
            if (PHMAP_PREDICT_TRUE(g.MatchEmpty())) return false;
2147
1.46k
            seq.next();
2148
1.46k
            assert(seq.getindex() < capacity_ && "full table!");
2149
1.46k
        }
2150
0
        return false;
2151
521k
    }
2152
2153
521k
    bool has_element(const value_type& elem) const {
2154
521k
        size_t hashval = PolicyTraits::apply(HashElement{hash_ref()}, elem);
2155
521k
        return has_element(elem, hashval);
2156
521k
    }
2157
2158
    // Probes the raw_hash_set with the probe sequence for hash and returns the
2159
    // pointer to the first empty or deleted slot.
2160
    // NOTE: this function must work with tables having both kEmpty and kDelete
2161
    // in one group. Such tables appears during drop_deletes_without_resize.
2162
    //
2163
    // This function is very useful when insertions happen and:
2164
    // - the input is already a set
2165
    // - there are enough slots
2166
    // - the element with the hash is not in the table
2167
    struct FindInfo 
2168
    {
2169
        size_t offset;
2170
        size_t probe_length;
2171
    };
2172
1.49M
    FindInfo find_first_non_full(size_t hashval) {
2173
1.49M
        auto seq = probe(hashval);
2174
1.57M
        while (true) {
2175
1.57M
            Group g{ctrl_ + seq.offset()};
2176
1.57M
            auto mask = g.MatchEmptyOrDeleted();
2177
1.57M
            if (mask) {
2178
1.49M
                return {seq.offset((size_t)mask.LowestBitSet()), seq.getindex()};
2179
1.49M
            }
2180
80.3k
            assert(seq.getindex() < capacity_ && "full table!");
2181
80.3k
            seq.next();
2182
80.3k
        }
2183
1.49M
    }
2184
2185
    // TODO(alkis): Optimize this assuming *this and that don't overlap.
2186
    raw_hash_set& move_assign(raw_hash_set&& that, std::true_type) {
2187
        raw_hash_set tmp(std::move(that));
2188
        swap(tmp);
2189
        return *this;
2190
    }
2191
    raw_hash_set& move_assign(raw_hash_set&& that, std::false_type) {
2192
        raw_hash_set tmp(std::move(that), alloc_ref());
2193
        swap(tmp);
2194
        return *this;
2195
    }
2196
2197
protected:
2198
    template <class K>
2199
8.01M
    size_t _find_key(const K& key, size_t hashval) {
2200
8.01M
        auto seq = probe(hashval);
2201
9.05M
        while (true) {
2202
9.05M
            Group g{ctrl_ + seq.offset()};
2203
10.4M
            for (uint32_t i : g.Match((h2_t)H2(hashval))) {
2204
10.4M
                if (PHMAP_PREDICT_TRUE(PolicyTraits::apply(
2205
10.4M
                                          EqualElement<K>{key, eq_ref()},
2206
10.4M
                                          PolicyTraits::element(slots_ + seq.offset((size_t)i)))))
2207
7.48M
                    return seq.offset((size_t)i);
2208
10.4M
            }
2209
1.57M
            if (PHMAP_PREDICT_TRUE(g.MatchEmpty())) break;
2210
1.03M
            seq.next();
2211
1.03M
        }
2212
536k
        return (size_t)-1;
2213
8.01M
    }
2214
2215
    template <class K>
2216
    std::pair<size_t, bool> find_or_prepare_insert(const K& key, size_t hashval) {
2217
        size_t offset = _find_key(key, hashval);
2218
        if (offset == (size_t)-1)
2219
            return {prepare_insert(hashval), true};
2220
        return {offset, false};
2221
    }
2222
2223
536k
    size_t prepare_insert(size_t hashval) PHMAP_ATTRIBUTE_NOINLINE {
2224
536k
        auto target = find_first_non_full(hashval);
2225
536k
        if (PHMAP_PREDICT_FALSE(growth_left() == 0 &&
2226
536k
                               !IsDeleted(ctrl_[target.offset]))) {
2227
2.81k
            rehash_and_grow_if_necessary();
2228
2.81k
            target = find_first_non_full(hashval);
2229
2.81k
        }
2230
536k
        ++size_;
2231
536k
        growth_left() -= IsEmpty(ctrl_[target.offset]);
2232
        // set_ctrl(target.offset, H2(hashval));
2233
536k
        infoz_.RecordInsert(hashval, target.probe_length);
2234
536k
        return target.offset;
2235
536k
    }
2236
2237
    // Constructs the value in the space pointed by the iterator. This only works
2238
    // after an unsuccessful find_or_prepare_insert() and before any other
2239
    // modifications happen in the raw_hash_set.
2240
    //
2241
    // PRECONDITION: i is an index returned from find_or_prepare_insert(k), where
2242
    // k is the key decomposed from `forward<Args>(args)...`, and the bool
2243
    // returned by find_or_prepare_insert(k) was true.
2244
    // POSTCONDITION: *m.iterator_at(i) == value_type(forward<Args>(args)...).
2245
    template <class... Args>
2246
536k
    void emplace_at(size_t i, Args&&... args) {
2247
536k
        PolicyTraits::construct(&alloc_ref(), slots_ + i,
2248
536k
                                std::forward<Args>(args)...);
2249
        
2250
#ifdef PHMAP_CHECK_CONSTRUCTED_VALUE
2251
        // this check can be costly, so do it only when requested
2252
        assert(PolicyTraits::apply(FindElement{*this}, *iterator_at(i)) ==
2253
               iterator_at(i) &&
2254
               "constructed value does not match the lookup key");
2255
#endif
2256
536k
    }
2257
2258
8.01M
    iterator iterator_at(size_t i) { return {ctrl_ + i, slots_ + i}; }
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::iterator_at(unsigned long)
Line
Count
Source
2258
8.01M
    iterator iterator_at(size_t i) { return {ctrl_ + i, slots_ + i}; }
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::iterator_at(unsigned long)
Line
Count
Source
2258
506
    iterator iterator_at(size_t i) { return {ctrl_ + i, slots_ + i}; }
2259
    const_iterator iterator_at(size_t i) const { return {ctrl_ + i, slots_ + i}; }
2260
2261
protected:
2262
    // Sets the control byte, and if `i < Group::kWidth`, set the cloned byte at
2263
    // the end too.
2264
1.49M
    void set_ctrl(size_t i, ctrl_t h) {
2265
1.49M
        assert(i < capacity_);
2266
2267
1.49M
        if (IsFull(h)) {
2268
1.49M
            SanitizerUnpoisonObject(slots_ + i);
2269
1.49M
        } else {
2270
0
            SanitizerPoisonObject(slots_ + i);
2271
0
        }
2272
2273
1.49M
        ctrl_[i] = h;
2274
1.49M
        ctrl_[((i - Group::kWidth) & capacity_) + 1 +
2275
1.49M
              ((Group::kWidth - 1) & capacity_)] = h;
2276
1.49M
    }
2277
2278
private:
2279
    friend struct RawHashSetTestOnlyAccess;
2280
2281
10.0M
    probe_seq<Group::kWidth> probe(size_t hashval) const {
2282
10.0M
        return probe_seq<Group::kWidth>(H1(hashval, ctrl_), capacity_);
2283
10.0M
    }
2284
2285
    // Reset all ctrl bytes back to kEmpty, except the sentinel.
2286
2.95k
    void reset_ctrl(size_t new_capacity) {
2287
2.95k
        std::memset(ctrl_, kEmpty, new_capacity + Group::kWidth);
2288
2.95k
        ctrl_[new_capacity] = kSentinel;
2289
2.95k
        SanitizerPoisonMemoryRegion(slots_, sizeof(slot_type) * new_capacity);
2290
2.95k
    }
2291
2292
2.95k
    void reset_growth_left(size_t new_capacity) {
2293
2.95k
        growth_left() = CapacityToGrowth(new_capacity) - size_;
2294
2.95k
    }
2295
2296
1.07M
    size_t& growth_left() { return std::get<0>(settings_); }
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::growth_left()
Line
Count
Source
2296
1.07M
    size_t& growth_left() { return std::get<0>(settings_); }
Unexecuted instantiation: phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::growth_left()
2297
2298
470
    const size_t& growth_left() const { return std::get<0>(settings_); }
2299
2300
    template <size_t N,
2301
              template <class, class, class, class> class RefSet,
2302
              class M, class P, class H, class E, class A>
2303
    friend class parallel_hash_set;
2304
2305
    template <size_t N,
2306
              template <class, class, class, class> class RefSet,
2307
              class M, class P, class H, class E, class A>
2308
    friend class parallel_hash_map;
2309
2310
    // The representation of the object has two modes:
2311
    //  - small: For capacities < kWidth-1
2312
    //  - large: For the rest.
2313
    //
2314
    // Differences:
2315
    //  - In small mode we are able to use the whole capacity. The extra control
2316
    //  bytes give us at least one "empty" control byte to stop the iteration.
2317
    //  This is important to make 1 a valid capacity.
2318
    //
2319
    //  - In small mode only the first `capacity()` control bytes after the
2320
    //  sentinel are valid. The rest contain dummy kEmpty values that do not
2321
    //  represent a real slot. This is important to take into account on
2322
    //  find_first_non_full(), where we never try ShouldInsertBackwards() for
2323
    //  small tables.
2324
0
    bool is_small() const { return capacity_ < Group::kWidth - 1; }
2325
2326
959k
    hasher& hash_ref() { return std::get<1>(settings_); }
2327
8.54M
    const hasher& hash_ref() const { return std::get<1>(settings_); }
2328
10.4M
    key_equal& eq_ref() { return std::get<2>(settings_); }
2329
    const key_equal& eq_ref() const { return std::get<2>(settings_); }
2330
1.50M
    allocator_type& alloc_ref() { return std::get<3>(settings_); }
phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::alloc_ref()
Line
Count
Source
2330
1.50M
    allocator_type& alloc_ref() { return std::get<3>(settings_); }
Unexecuted instantiation: phmap::priv::raw_hash_set<phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::alloc_ref()
2331
    const allocator_type& alloc_ref() const {
2332
        return std::get<3>(settings_);
2333
    }
2334
2335
    // TODO(alkis): Investigate removing some of these fields:
2336
    // - ctrl/slots can be derived from each other
2337
    // - size can be moved into the slot array
2338
    ctrl_t* ctrl_ = EmptyGroup();    // [(capacity + 1) * ctrl_t]
2339
    slot_type* slots_ = nullptr;     // [capacity * slot_type]
2340
    size_t size_ = 0;                // number of full slots
2341
    size_t capacity_ = 0;            // total number of slots
2342
    HashtablezInfoHandle infoz_;
2343
    std::tuple<size_t /* growth_left */, hasher, key_equal, allocator_type>
2344
        settings_{0, hasher{}, key_equal{}, allocator_type{}};
2345
};
2346
2347
2348
// --------------------------------------------------------------------------
2349
// --------------------------------------------------------------------------
2350
template <class Policy, class Hash, class Eq, class Alloc>
2351
class raw_hash_map : public raw_hash_set<Policy, Hash, Eq, Alloc> 
2352
{
2353
    // P is Policy. It's passed as a template argument to support maps that have
2354
    // incomplete types as values, as in unordered_map<K, IncompleteType>.
2355
    // MappedReference<> may be a non-reference type.
2356
    template <class P>
2357
    using MappedReference = decltype(P::value(
2358
               std::addressof(std::declval<typename raw_hash_map::reference>())));
2359
2360
    // MappedConstReference<> may be a non-reference type.
2361
    template <class P>
2362
    using MappedConstReference = decltype(P::value(
2363
               std::addressof(std::declval<typename raw_hash_map::const_reference>())));
2364
2365
    using KeyArgImpl =
2366
        KeyArg<IsTransparent<Eq>::value && IsTransparent<Hash>::value>;
2367
2368
    using Base = raw_hash_set<Policy, Hash, Eq, Alloc>;
2369
2370
public:
2371
    using key_type = typename Policy::key_type;
2372
    using mapped_type = typename Policy::mapped_type;
2373
    template <class K>
2374
    using key_arg = typename KeyArgImpl::template type<K, key_type>;
2375
2376
    static_assert(!std::is_reference<key_type>::value, "");
2377
2378
    // TODO(b/187807849): Evaluate whether to support reference mapped_type and
2379
    // remove this assertion if/when it is supported.
2380
     static_assert(!std::is_reference<mapped_type>::value, "");
2381
2382
    using iterator = typename raw_hash_map::raw_hash_set::iterator;
2383
    using const_iterator = typename raw_hash_map::raw_hash_set::const_iterator;
2384
2385
1.51k
    raw_hash_map() {}
phmap::priv::raw_hash_map<phmap::priv::FlatHashMapPolicy<unsigned int, int>, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::raw_hash_map()
Line
Count
Source
2385
1.01k
    raw_hash_map() {}
phmap::priv::raw_hash_map<phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::raw_hash_map()
Line
Count
Source
2385
506
    raw_hash_map() {}
2386
    using Base::raw_hash_set; // use raw_hash_set constructor  
2387
2388
    // The last two template parameters ensure that both arguments are rvalues
2389
    // (lvalue arguments are handled by the overloads below). This is necessary
2390
    // for supporting bitfield arguments.
2391
    //
2392
    //   union { int n : 1; };
2393
    //   flat_hash_map<int, int> m;
2394
    //   m.insert_or_assign(n, n);
2395
    template <class K = key_type, class V = mapped_type, K* = nullptr,
2396
              V* = nullptr>
2397
    std::pair<iterator, bool> insert_or_assign(key_arg<K>&& k, V&& v) {
2398
        return insert_or_assign_impl(std::forward<K>(k), std::forward<V>(v));
2399
    }
2400
2401
    template <class K = key_type, class V = mapped_type, K* = nullptr>
2402
    std::pair<iterator, bool> insert_or_assign(key_arg<K>&& k, const V& v) {
2403
        return insert_or_assign_impl(std::forward<K>(k), v);
2404
    }
2405
2406
    template <class K = key_type, class V = mapped_type, V* = nullptr>
2407
    std::pair<iterator, bool> insert_or_assign(const key_arg<K>& k, V&& v) {
2408
        return insert_or_assign_impl(k, std::forward<V>(v));
2409
    }
2410
2411
    template <class K = key_type, class V = mapped_type>
2412
    std::pair<iterator, bool> insert_or_assign(const key_arg<K>& k, const V& v) {
2413
        return insert_or_assign_impl(k, v);
2414
    }
2415
2416
    template <class K = key_type, class V = mapped_type, K* = nullptr,
2417
              V* = nullptr>
2418
    iterator insert_or_assign(const_iterator, key_arg<K>&& k, V&& v) {
2419
        return insert_or_assign(std::forward<K>(k), std::forward<V>(v)).first;
2420
    }
2421
2422
    template <class K = key_type, class V = mapped_type, K* = nullptr>
2423
    iterator insert_or_assign(const_iterator, key_arg<K>&& k, const V& v) {
2424
        return insert_or_assign(std::forward<K>(k), v).first;
2425
    }
2426
2427
    template <class K = key_type, class V = mapped_type, V* = nullptr>
2428
    iterator insert_or_assign(const_iterator, const key_arg<K>& k, V&& v) {
2429
        return insert_or_assign(k, std::forward<V>(v)).first;
2430
    }
2431
2432
    template <class K = key_type, class V = mapped_type>
2433
    iterator insert_or_assign(const_iterator, const key_arg<K>& k, const V& v) {
2434
        return insert_or_assign(k, v).first;
2435
    }
2436
2437
    template <class K = key_type, class... Args,
2438
              typename std::enable_if<
2439
                  !std::is_convertible<K, const_iterator>::value, int>::type = 0,
2440
              K* = nullptr>
2441
    std::pair<iterator, bool> try_emplace(key_arg<K>&& k, Args&&... args) {
2442
        return try_emplace_impl(std::forward<K>(k), std::forward<Args>(args)...);
2443
    }
2444
2445
    template <class K = key_type, class... Args,
2446
              typename std::enable_if<
2447
                  !std::is_convertible<K, const_iterator>::value, int>::type = 0>
2448
    std::pair<iterator, bool> try_emplace(const key_arg<K>& k, Args&&... args) {
2449
        return try_emplace_impl(k, std::forward<Args>(args)...);
2450
    }
2451
2452
    template <class K = key_type, class... Args, K* = nullptr>
2453
    iterator try_emplace(const_iterator, key_arg<K>&& k, Args&&... args) {
2454
        return try_emplace(std::forward<K>(k), std::forward<Args>(args)...).first;
2455
    }
2456
2457
    template <class K = key_type, class... Args>
2458
    iterator try_emplace(const_iterator, const key_arg<K>& k, Args&&... args) {
2459
        return try_emplace(k, std::forward<Args>(args)...).first;
2460
    }
2461
2462
    template <class K = key_type, class P = Policy>
2463
    MappedReference<P> at(const key_arg<K>& key) {
2464
        auto it = this->find(key);
2465
        if (it == this->end()) 
2466
            phmap::base_internal::ThrowStdOutOfRange("phmap at(): lookup non-existent key");
2467
        return Policy::value(&*it);
2468
    }
2469
2470
    template <class K = key_type, class P = Policy>
2471
    MappedConstReference<P> at(const key_arg<K>& key) const {
2472
        auto it = this->find(key);
2473
        if (it == this->end())
2474
            phmap::base_internal::ThrowStdOutOfRange("phmap at(): lookup non-existent key");
2475
        return Policy::value(&*it);
2476
    }
2477
2478
    template <class K = key_type, class P = Policy, K* = nullptr>
2479
    MappedReference<P> operator[](key_arg<K>&& key) {
2480
        return Policy::value(&*try_emplace(std::forward<K>(key)).first);
2481
    }
2482
2483
    template <class K = key_type, class P = Policy>
2484
    MappedReference<P> operator[](const key_arg<K>& key) {
2485
        return Policy::value(&*try_emplace(key).first);
2486
    }
2487
2488
private:
2489
    template <class K, class V>
2490
    std::pair<iterator, bool> insert_or_assign_impl(K&& k, V&& v) {
2491
        size_t hashval = this->hash(k);
2492
        size_t offset = this->_find_key(k, hashval);
2493
        if (offset == (size_t)-1) {
2494
            offset = this->prepare_insert(hashval);
2495
            this->emplace_at(offset, std::forward<K>(k), std::forward<V>(v));
2496
            this->set_ctrl(offset, H2(hashval));
2497
            return {this->iterator_at(offset), true};
2498
        } 
2499
        Policy::value(&*this->iterator_at(offset)) = std::forward<V>(v);
2500
        return {this->iterator_at(offset), false};
2501
    }
2502
2503
    template <class K = key_type, class... Args>
2504
    std::pair<iterator, bool> try_emplace_impl(K&& k, Args&&... args) {
2505
        size_t hashval = this->hash(k);
2506
        size_t offset = this->_find_key(k, hashval);
2507
        if (offset == (size_t)-1) {
2508
            offset = this->prepare_insert(hashval);
2509
            this->emplace_at(offset, std::piecewise_construct,
2510
                             std::forward_as_tuple(std::forward<K>(k)),
2511
                             std::forward_as_tuple(std::forward<Args>(args)...));
2512
            this->set_ctrl(offset, H2(hashval));
2513
            return {this->iterator_at(offset), true};
2514
        }
2515
        return {this->iterator_at(offset), false};
2516
    }
2517
};
2518
2519
// ----------------------------------------------------------------------------
2520
// ----------------------------------------------------------------------------
2521
// Returns "random" seed.
2522
inline size_t RandomSeed() 
2523
0
{
2524
0
#if PHMAP_HAVE_THREAD_LOCAL
2525
0
    static thread_local size_t counter = 0;
2526
0
    size_t value = ++counter;
2527
0
#else   // PHMAP_HAVE_THREAD_LOCAL
2528
0
    static std::atomic<size_t> counter(0);
2529
0
    size_t value = counter.fetch_add(1, std::memory_order_relaxed);
2530
0
#endif  // PHMAP_HAVE_THREAD_LOCAL
2531
0
    return value ^ static_cast<size_t>(reinterpret_cast<uintptr_t>(&counter));
2532
0
}
2533
2534
// ----------------------------------------------------------------------------
2535
// ----------------------------------------------------------------------------
2536
template <size_t N,
2537
          template <class, class, class, class> class RefSet,
2538
          class Mtx_,
2539
          class Policy, class Hash, class Eq, class Alloc>
2540
class parallel_hash_set 
2541
{
2542
    using PolicyTraits = hash_policy_traits<Policy>;
2543
    using KeyArgImpl =
2544
        KeyArg<IsTransparent<Eq>::value && IsTransparent<Hash>::value>;
2545
2546
    static_assert(N <= 12, "N = 12 means 4096 hash tables!");
2547
    constexpr static size_t num_tables = 1 << N;
2548
    constexpr static size_t mask = num_tables - 1;
2549
2550
public:
2551
    using EmbeddedSet     = RefSet<Policy, Hash, Eq, Alloc>;
2552
    using EmbeddedIterator= typename EmbeddedSet::iterator;
2553
    using EmbeddedConstIterator= typename EmbeddedSet::const_iterator;
2554
    using constructor     = typename EmbeddedSet::constructor;
2555
    using init_type       = typename PolicyTraits::init_type;
2556
    using key_type        = typename PolicyTraits::key_type;
2557
    using slot_type       = typename PolicyTraits::slot_type;
2558
    using allocator_type  = Alloc;
2559
    using size_type       = size_t;
2560
    using difference_type = ptrdiff_t;
2561
    using hasher          = Hash;
2562
    using key_equal       = Eq;
2563
    using policy_type     = Policy;
2564
    using value_type      = typename PolicyTraits::value_type;
2565
    using reference       = value_type&;
2566
    using const_reference = const value_type&;
2567
    using pointer         = typename phmap::allocator_traits<
2568
        allocator_type>::template rebind_traits<value_type>::pointer;
2569
    using const_pointer   = typename phmap::allocator_traits<
2570
        allocator_type>::template rebind_traits<value_type>::const_pointer;
2571
2572
    // Alias used for heterogeneous lookup functions.
2573
    // `key_arg<K>` evaluates to `K` when the functors are transparent and to
2574
    // `key_type` otherwise. It permits template argument deduction on `K` for the
2575
    // transparent case.
2576
    // --------------------------------------------------------------------
2577
    template <class K>
2578
    using key_arg         = typename KeyArgImpl::template type<K, key_type>;
2579
2580
protected:
2581
    using Lockable      = phmap::LockableImpl<Mtx_>;
2582
    using UniqueLock    = typename Lockable::UniqueLock;
2583
    using SharedLock    = typename Lockable::SharedLock;
2584
    using ReadWriteLock = typename Lockable::ReadWriteLock;
2585
    
2586
2587
    // --------------------------------------------------------------------
2588
    struct Inner : public Lockable
2589
    {
2590
        struct Params
2591
        {
2592
            size_t bucket_cnt;
2593
            const hasher& hashfn;
2594
            const key_equal& eq;
2595
            const allocator_type& alloc;
2596
        };
2597
2598
        Inner() {}
2599
2600
        Inner(Params const &p) : set_(p.bucket_cnt, p.hashfn, p.eq, p.alloc)
2601
        {}
2602
2603
        bool operator==(const Inner& o) const
2604
        {
2605
            typename Lockable::SharedLocks l(const_cast<Inner &>(*this), const_cast<Inner &>(o));
2606
            return set_ == o.set_;
2607
        }
2608
2609
        EmbeddedSet set_;
2610
    };
2611
2612
private:
2613
    // Give an early error when key_type is not hashable/eq.
2614
    // --------------------------------------------------------------------
2615
    auto KeyTypeCanBeHashed(const Hash& h, const key_type& k) -> decltype(h(k));
2616
    auto KeyTypeCanBeEq(const Eq& eq, const key_type& k)      -> decltype(eq(k, k));
2617
2618
    using AllocTraits     = phmap::allocator_traits<allocator_type>;
2619
2620
    static_assert(std::is_lvalue_reference<reference>::value,
2621
                  "Policy::element() must return a reference");
2622
2623
    template <typename T>
2624
    struct SameAsElementReference : std::is_same<
2625
        typename std::remove_cv<typename std::remove_reference<reference>::type>::type,
2626
        typename std::remove_cv<typename std::remove_reference<T>::type>::type> {};
2627
2628
    // An enabler for insert(T&&): T must be convertible to init_type or be the
2629
    // same as [cv] value_type [ref].
2630
    // Note: we separate SameAsElementReference into its own type to avoid using
2631
    // reference unless we need to. MSVC doesn't seem to like it in some
2632
    // cases.
2633
    // --------------------------------------------------------------------
2634
    template <class T>
2635
    using RequiresInsertable = typename std::enable_if<
2636
        phmap::disjunction<std::is_convertible<T, init_type>, SameAsElementReference<T>>::value, int>::type;
2637
2638
    // RequiresNotInit is a workaround for gcc prior to 7.1.
2639
    // See https://godbolt.org/g/Y4xsUh.
2640
    template <class T>
2641
    using RequiresNotInit =
2642
        typename std::enable_if<!std::is_same<T, init_type>::value, int>::type;
2643
2644
    template <class... Ts>
2645
    using IsDecomposable = IsDecomposable<void, PolicyTraits, Hash, Eq, Ts...>;
2646
2647
public:
2648
    static_assert(std::is_same<pointer, value_type*>::value,
2649
                  "Allocators with custom pointer types are not supported");
2650
    static_assert(std::is_same<const_pointer, const value_type*>::value,
2651
                  "Allocators with custom pointer types are not supported");
2652
2653
    // --------------------- i t e r a t o r ------------------------------
2654
    class iterator 
2655
    {
2656
        friend class parallel_hash_set;
2657
2658
    public:
2659
        using iterator_category = std::forward_iterator_tag;
2660
        using value_type        = typename parallel_hash_set::value_type;
2661
        using reference         =
2662
            phmap::conditional_t<PolicyTraits::constant_iterators::value,
2663
                                const value_type&, value_type&>;
2664
        using pointer           = phmap::remove_reference_t<reference>*;
2665
        using difference_type   = typename parallel_hash_set::difference_type;
2666
        using Inner             = typename parallel_hash_set::Inner;
2667
        using EmbeddedSet       = typename parallel_hash_set::EmbeddedSet;
2668
        using EmbeddedIterator  = typename EmbeddedSet::iterator;
2669
2670
        iterator() {}
2671
2672
        reference operator*()  const { return *it_; }
2673
        pointer   operator->() const { return &operator*(); }
2674
2675
        iterator& operator++() {
2676
            assert(inner_); // null inner means we are already at the end
2677
            ++it_;
2678
            skip_empty();
2679
            return *this;
2680
        }
2681
    
2682
        iterator operator++(int) {
2683
            assert(inner_);  // null inner means we are already at the end
2684
            auto tmp = *this;
2685
            ++*this;
2686
            return tmp;
2687
        }
2688
2689
        friend bool operator==(const iterator& a, const iterator& b) {
2690
            return a.inner_ == b.inner_ && (!a.inner_ || a.it_ == b.it_);
2691
        }
2692
2693
        friend bool operator!=(const iterator& a, const iterator& b) {
2694
            return !(a == b);
2695
        }
2696
2697
    private:
2698
        iterator(Inner *inner, Inner *inner_end, const EmbeddedIterator& it) : 
2699
            inner_(inner), inner_end_(inner_end), it_(it)  {  // for begin() and end()
2700
            if (inner)
2701
                it_end_ = inner->set_.end();
2702
        }
2703
2704
        void skip_empty() {
2705
            while (it_ == it_end_) {
2706
                ++inner_;
2707
                if (inner_ == inner_end_) {
2708
                    inner_ = nullptr; // marks end()
2709
                    break;
2710
                }
2711
                else {
2712
                    it_ = inner_->set_.begin();
2713
                    it_end_ = inner_->set_.end();
2714
                }
2715
            }
2716
        }
2717
2718
        Inner *inner_      = nullptr;
2719
        Inner *inner_end_  = nullptr;
2720
        EmbeddedIterator it_, it_end_;
2721
    };
2722
2723
    // --------------------- c o n s t   i t e r a t o r -----------------
2724
    class const_iterator 
2725
    {
2726
        friend class parallel_hash_set;
2727
2728
    public:
2729
        using iterator_category = typename iterator::iterator_category;
2730
        using value_type        = typename parallel_hash_set::value_type;
2731
        using reference         = typename parallel_hash_set::const_reference;
2732
        using pointer           = typename parallel_hash_set::const_pointer;
2733
        using difference_type   = typename parallel_hash_set::difference_type;
2734
        using Inner             = typename parallel_hash_set::Inner;
2735
2736
        const_iterator() {}
2737
        // Implicit construction from iterator.
2738
        const_iterator(iterator i) : iter_(std::move(i)) {}
2739
2740
        reference operator*()  const { return *(iter_); }
2741
        pointer   operator->() const { return iter_.operator->(); }
2742
2743
        const_iterator& operator++() {
2744
            ++iter_;
2745
            return *this;
2746
        }
2747
        const_iterator operator++(int) { return iter_++; }
2748
2749
        friend bool operator==(const const_iterator& a, const const_iterator& b) {
2750
            return a.iter_ == b.iter_;
2751
        }
2752
        friend bool operator!=(const const_iterator& a, const const_iterator& b) {
2753
            return !(a == b);
2754
        }
2755
2756
    private:
2757
        const_iterator(const Inner *inner, const Inner *inner_end, const EmbeddedIterator& it)
2758
            : iter_(const_cast<Inner**>(inner), 
2759
                    const_cast<Inner**>(inner_end),
2760
                    const_cast<EmbeddedIterator*>(it)) {}
2761
2762
        iterator iter_;
2763
    };
2764
2765
    using node_type = node_handle<Policy, hash_policy_traits<Policy>, Alloc>;
2766
    using insert_return_type = InsertReturnType<iterator, node_type>;
2767
2768
    // ------------------------- c o n s t r u c t o r s ------------------
2769
2770
    parallel_hash_set() noexcept(
2771
        std::is_nothrow_default_constructible<hasher>::value&&
2772
        std::is_nothrow_default_constructible<key_equal>::value&&
2773
        std::is_nothrow_default_constructible<allocator_type>::value) {}
2774
2775
#if  (__cplusplus >= 201703L || _MSVC_LANG >= 201402) && (defined(_MSC_VER) || defined(__clang__) || (defined(__GNUC__) && __GNUC__ > 6))
2776
    explicit parallel_hash_set(size_t bucket_cnt, 
2777
                               const hasher& hash_param    = hasher(),
2778
                               const key_equal& eq         = key_equal(),
2779
                               const allocator_type& alloc = allocator_type()) :
2780
        parallel_hash_set(typename Inner::Params{bucket_cnt, hash_param, eq, alloc}, 
2781
                          phmap::make_index_sequence<num_tables>{})
2782
    {}
2783
2784
    template <std::size_t... i>
2785
    parallel_hash_set(typename Inner::Params const &p,
2786
                      phmap::index_sequence<i...>) : sets_{((void)i, p)...}
2787
    {}
2788
#else
2789
    explicit parallel_hash_set(size_t bucket_cnt, 
2790
                               const hasher& hash_param    = hasher(),
2791
                               const key_equal& eq         = key_equal(),
2792
                               const allocator_type& alloc = allocator_type()) {
2793
        for (auto& inner : sets_)
2794
            inner.set_ = EmbeddedSet(bucket_cnt / N, hash_param, eq, alloc);
2795
    }
2796
#endif
2797
2798
    parallel_hash_set(size_t bucket_cnt, 
2799
                      const hasher& hash_param,
2800
                      const allocator_type& alloc)
2801
        : parallel_hash_set(bucket_cnt, hash_param, key_equal(), alloc) {}
2802
2803
    parallel_hash_set(size_t bucket_cnt, const allocator_type& alloc)
2804
        : parallel_hash_set(bucket_cnt, hasher(), key_equal(), alloc) {}
2805
2806
    explicit parallel_hash_set(const allocator_type& alloc)
2807
        : parallel_hash_set(0, hasher(), key_equal(), alloc) {}
2808
2809
    template <class InputIter>
2810
    parallel_hash_set(InputIter first, InputIter last, size_t bucket_cnt = 0,
2811
                      const hasher& hash_param = hasher(), const key_equal& eq = key_equal(),
2812
                      const allocator_type& alloc = allocator_type())
2813
        : parallel_hash_set(bucket_cnt, hash_param, eq, alloc) {
2814
        insert(first, last);
2815
    }
2816
2817
    template <class InputIter>
2818
    parallel_hash_set(InputIter first, InputIter last, size_t bucket_cnt,
2819
                      const hasher& hash_param, const allocator_type& alloc)
2820
        : parallel_hash_set(first, last, bucket_cnt, hash_param, key_equal(), alloc) {}
2821
2822
    template <class InputIter>
2823
    parallel_hash_set(InputIter first, InputIter last, size_t bucket_cnt,
2824
                      const allocator_type& alloc)
2825
        : parallel_hash_set(first, last, bucket_cnt, hasher(), key_equal(), alloc) {}
2826
2827
    template <class InputIter>
2828
    parallel_hash_set(InputIter first, InputIter last, const allocator_type& alloc)
2829
        : parallel_hash_set(first, last, 0, hasher(), key_equal(), alloc) {}
2830
2831
    // Instead of accepting std::initializer_list<value_type> as the first
2832
    // argument like std::unordered_set<value_type> does, we have two overloads
2833
    // that accept std::initializer_list<T> and std::initializer_list<init_type>.
2834
    // This is advantageous for performance.
2835
    //
2836
    //   // Turns {"abc", "def"} into std::initializer_list<std::string>, then copies
2837
    //   // the strings into the set.
2838
    //   std::unordered_set<std::string> s = {"abc", "def"};
2839
    //
2840
    //   // Turns {"abc", "def"} into std::initializer_list<const char*>, then
2841
    //   // copies the strings into the set.
2842
    //   phmap::flat_hash_set<std::string> s = {"abc", "def"};
2843
    //
2844
    // The same trick is used in insert().
2845
    //
2846
    // The enabler is necessary to prevent this constructor from triggering where
2847
    // the copy constructor is meant to be called.
2848
    //
2849
    //   phmap::flat_hash_set<int> a, b{a};
2850
    //
2851
    // RequiresNotInit<T> is a workaround for gcc prior to 7.1.
2852
    // --------------------------------------------------------------------
2853
    template <class T, RequiresNotInit<T> = 0, RequiresInsertable<T> = 0>
2854
    parallel_hash_set(std::initializer_list<T> init, size_t bucket_cnt = 0,
2855
                      const hasher& hash_param = hasher(), const key_equal& eq = key_equal(),
2856
                      const allocator_type& alloc = allocator_type())
2857
        : parallel_hash_set(init.begin(), init.end(), bucket_cnt, hash_param, eq, alloc) {}
2858
2859
    parallel_hash_set(std::initializer_list<init_type> init, size_t bucket_cnt = 0,
2860
                      const hasher& hash_param = hasher(), const key_equal& eq = key_equal(),
2861
                      const allocator_type& alloc = allocator_type())
2862
        : parallel_hash_set(init.begin(), init.end(), bucket_cnt, hash_param, eq, alloc) {}
2863
2864
    template <class T, RequiresNotInit<T> = 0, RequiresInsertable<T> = 0>
2865
    parallel_hash_set(std::initializer_list<T> init, size_t bucket_cnt,
2866
                      const hasher& hash_param, const allocator_type& alloc)
2867
        : parallel_hash_set(init, bucket_cnt, hash_param, key_equal(), alloc) {}
2868
2869
    parallel_hash_set(std::initializer_list<init_type> init, size_t bucket_cnt,
2870
                      const hasher& hash_param, const allocator_type& alloc)
2871
        : parallel_hash_set(init, bucket_cnt, hash_param, key_equal(), alloc) {}
2872
2873
    template <class T, RequiresNotInit<T> = 0, RequiresInsertable<T> = 0>
2874
    parallel_hash_set(std::initializer_list<T> init, size_t bucket_cnt,
2875
                      const allocator_type& alloc)
2876
        : parallel_hash_set(init, bucket_cnt, hasher(), key_equal(), alloc) {}
2877
2878
    parallel_hash_set(std::initializer_list<init_type> init, size_t bucket_cnt,
2879
                      const allocator_type& alloc)
2880
        : parallel_hash_set(init, bucket_cnt, hasher(), key_equal(), alloc) {}
2881
2882
    template <class T, RequiresNotInit<T> = 0, RequiresInsertable<T> = 0>
2883
    parallel_hash_set(std::initializer_list<T> init, const allocator_type& alloc)
2884
        : parallel_hash_set(init, 0, hasher(), key_equal(), alloc) {}
2885
  
2886
    parallel_hash_set(std::initializer_list<init_type> init,
2887
                      const allocator_type& alloc)
2888
        : parallel_hash_set(init, 0, hasher(), key_equal(), alloc) {}
2889
2890
    parallel_hash_set(const parallel_hash_set& that)
2891
        : parallel_hash_set(that, AllocTraits::select_on_container_copy_construction(
2892
                                that.alloc_ref())) {}
2893
2894
    parallel_hash_set(const parallel_hash_set& that, const allocator_type& a)
2895
        : parallel_hash_set(0, that.hash_ref(), that.eq_ref(), a) {
2896
        for (size_t i=0; i<num_tables; ++i)
2897
            sets_[i].set_ = { that.sets_[i].set_, a };
2898
    }
2899
  
2900
    parallel_hash_set(parallel_hash_set&& that) noexcept(
2901
        std::is_nothrow_copy_constructible<hasher>::value&&
2902
        std::is_nothrow_copy_constructible<key_equal>::value&&
2903
        std::is_nothrow_copy_constructible<allocator_type>::value)
2904
        : parallel_hash_set(std::move(that), that.alloc_ref()) {
2905
    }
2906
2907
    parallel_hash_set(parallel_hash_set&& that, const allocator_type& a)
2908
    {
2909
        for (size_t i=0; i<num_tables; ++i)
2910
            sets_[i].set_ = { std::move(that.sets_[i]).set_, a };
2911
    }
2912
2913
    parallel_hash_set& operator=(const parallel_hash_set& that) {
2914
        for (size_t i=0; i<num_tables; ++i)
2915
            sets_[i].set_ = that.sets_[i].set_;
2916
        return *this;
2917
    }
2918
2919
    parallel_hash_set& operator=(parallel_hash_set&& that) noexcept(
2920
        phmap::allocator_traits<allocator_type>::is_always_equal::value &&
2921
        std::is_nothrow_move_assignable<hasher>::value &&
2922
        std::is_nothrow_move_assignable<key_equal>::value) {
2923
        for (size_t i=0; i<num_tables; ++i)
2924
            sets_[i].set_ = std::move(that.sets_[i].set_);
2925
        return *this;
2926
    }
2927
2928
    ~parallel_hash_set() {}
2929
2930
    iterator begin() {
2931
        auto it = iterator(&sets_[0], &sets_[0] + num_tables, sets_[0].set_.begin());
2932
        it.skip_empty();
2933
        return it;
2934
    }
2935
2936
    iterator       end()          { return iterator(); }
2937
    const_iterator begin()  const { return const_cast<parallel_hash_set *>(this)->begin(); }
2938
    const_iterator end()    const { return const_cast<parallel_hash_set *>(this)->end(); }
2939
    const_iterator cbegin() const { return begin(); }
2940
    const_iterator cend()   const { return end(); }
2941
2942
    bool empty() const { return !size(); }
2943
2944
    size_t size() const { 
2945
        size_t sz = 0;
2946
        for (const auto& inner : sets_)
2947
            sz += inner.set_.size();
2948
        return sz; 
2949
    }
2950
  
2951
    size_t capacity() const { 
2952
        size_t c = 0;
2953
        for (const auto& inner : sets_)
2954
            c += inner.set_.capacity();
2955
        return c; 
2956
    }
2957
2958
    size_t max_size() const { return (std::numeric_limits<size_t>::max)(); }
2959
2960
    PHMAP_ATTRIBUTE_REINITIALIZES void clear() {
2961
        for (auto& inner : sets_)
2962
        {
2963
            UniqueLock m(inner);
2964
            inner.set_.clear();
2965
        }
2966
    }
2967
2968
    // extension - clears only soecified submap
2969
    // ----------------------------------------
2970
    void clear(std::size_t submap_index) {
2971
        Inner& inner = sets_[submap_index];
2972
        UniqueLock m(inner);
2973
        inner.set_.clear();
2974
    }
2975
2976
    // This overload kicks in when the argument is an rvalue of insertable and
2977
    // decomposable type other than init_type.
2978
    //
2979
    //   flat_hash_map<std::string, int> m;
2980
    //   m.insert(std::make_pair("abc", 42));
2981
    // --------------------------------------------------------------------
2982
    template <class T, RequiresInsertable<T> = 0,
2983
              typename std::enable_if<IsDecomposable<T>::value, int>::type = 0,
2984
              T* = nullptr>
2985
    std::pair<iterator, bool> insert(T&& value) {
2986
        return emplace(std::forward<T>(value));
2987
    }
2988
2989
    // This overload kicks in when the argument is a bitfield or an lvalue of
2990
    // insertable and decomposable type.
2991
    //
2992
    //   union { int n : 1; };
2993
    //   flat_hash_set<int> s;
2994
    //   s.insert(n);
2995
    //
2996
    //   flat_hash_set<std::string> s;
2997
    //   const char* p = "hello";
2998
    //   s.insert(p);
2999
    //
3000
    // TODO(romanp): Once we stop supporting gcc 5.1 and below, replace
3001
    // RequiresInsertable<T> with RequiresInsertable<const T&>.
3002
    // We are hitting this bug: https://godbolt.org/g/1Vht4f.
3003
    // --------------------------------------------------------------------
3004
    template <
3005
        class T, RequiresInsertable<T> = 0,
3006
        typename std::enable_if<IsDecomposable<const T&>::value, int>::type = 0>
3007
    std::pair<iterator, bool> insert(const T& value) {
3008
        return emplace(value);
3009
    }
3010
3011
    // This overload kicks in when the argument is an rvalue of init_type. Its
3012
    // purpose is to handle brace-init-list arguments.
3013
    //
3014
    //   flat_hash_set<std::pair<std::string, int>> s;
3015
    //   s.insert({"abc", 42});
3016
    // --------------------------------------------------------------------
3017
    std::pair<iterator, bool> insert(init_type&& value) {
3018
        return emplace(std::move(value));
3019
    }
3020
3021
    template <class T, RequiresInsertable<T> = 0,
3022
              typename std::enable_if<IsDecomposable<T>::value, int>::type = 0,
3023
              T* = nullptr>
3024
    iterator insert(const_iterator, T&& value) {
3025
        return insert(std::forward<T>(value)).first;
3026
    }
3027
3028
    // TODO(romanp): Once we stop supporting gcc 5.1 and below, replace
3029
    // RequiresInsertable<T> with RequiresInsertable<const T&>.
3030
    // We are hitting this bug: https://godbolt.org/g/1Vht4f.
3031
    // --------------------------------------------------------------------
3032
    template <
3033
        class T, RequiresInsertable<T> = 0,
3034
        typename std::enable_if<IsDecomposable<const T&>::value, int>::type = 0>
3035
    iterator insert(const_iterator, const T& value) {
3036
        return insert(value).first;
3037
    }
3038
3039
    iterator insert(const_iterator, init_type&& value) {
3040
        return insert(std::move(value)).first;
3041
    }
3042
3043
    template <class InputIt>
3044
    void insert(InputIt first, InputIt last) {
3045
        for (; first != last; ++first) insert(*first);
3046
    }
3047
3048
    template <class T, RequiresNotInit<T> = 0, RequiresInsertable<const T&> = 0>
3049
    void insert(std::initializer_list<T> ilist) {
3050
        insert(ilist.begin(), ilist.end());
3051
    }
3052
3053
    void insert(std::initializer_list<init_type> ilist) {
3054
        insert(ilist.begin(), ilist.end());
3055
    }
3056
3057
    insert_return_type insert(node_type&& node) {
3058
        if (!node) 
3059
            return {end(), false, node_type()};
3060
        auto& key      = node.key();
3061
        size_t hashval = this->hash(key);
3062
        Inner& inner   = sets_[subidx(hashval)];
3063
        auto&  set     = inner.set_;
3064
3065
        UniqueLock m(inner);
3066
        auto   res  = set.insert(std::move(node), hashval);
3067
        return { make_iterator(&inner, res.position),
3068
                 res.inserted,
3069
                 res.inserted ? node_type() : std::move(res.node) };
3070
    }
3071
3072
    iterator insert(const_iterator, node_type&& node) {
3073
        return insert(std::move(node)).first;
3074
    }
3075
3076
    struct ReturnKey_ 
3077
    {
3078
        template <class Key, class... Args>
3079
        Key operator()(Key&& k, const Args&...) const {
3080
            return std::forward<Key>(k);
3081
        }
3082
    };
3083
3084
    // --------------------------------------------------------------------
3085
    // phmap extension: emplace_with_hash
3086
    // ----------------------------------
3087
    // same as emplace, but hashval is provided
3088
    // --------------------------------------------------------------------
3089
    struct EmplaceDecomposableHashval 
3090
    {
3091
        template <class K, class... Args>
3092
        std::pair<iterator, bool> operator()(const K& key, Args&&... args) const {
3093
            return s.emplace_decomposable_with_hash(key, hashval, std::forward<Args>(args)...);
3094
        }
3095
        parallel_hash_set& s;
3096
        size_t hashval;
3097
    };
3098
3099
    // This overload kicks in if we can deduce the key from args. This enables us
3100
    // to avoid constructing value_type if an entry with the same key already
3101
    // exists.
3102
    //
3103
    // For example:
3104
    //
3105
    //   flat_hash_map<std::string, std::string> m = {{"abc", "def"}};
3106
    //   // Creates no std::string copies and makes no heap allocations.
3107
    //   m.emplace("abc", "xyz");
3108
    // --------------------------------------------------------------------
3109
    template <class... Args, typename std::enable_if<IsDecomposable<Args...>::value, int>::type = 0>
3110
    std::pair<iterator, bool> emplace_with_hash(size_t hashval, Args&&... args) {
3111
        return PolicyTraits::apply(EmplaceDecomposableHashval{*this, hashval},
3112
                                   std::forward<Args>(args)...);
3113
    }
3114
3115
    // This overload kicks in if we cannot deduce the key from args. It constructs
3116
    // value_type unconditionally and then either moves it into the table or
3117
    // destroys.
3118
    // --------------------------------------------------------------------
3119
    template <class... Args, typename std::enable_if<!IsDecomposable<Args...>::value, int>::type = 0>
3120
    std::pair<iterator, bool> emplace_with_hash(size_t hashval, Args&&... args) {
3121
        typename phmap::aligned_storage<sizeof(slot_type), alignof(slot_type)>::type raw;
3122
        slot_type* slot = reinterpret_cast<slot_type*>(&raw);
3123
3124
        PolicyTraits::construct(&alloc_ref(), slot, std::forward<Args>(args)...);
3125
        const auto& elem = PolicyTraits::element(slot);
3126
        Inner& inner    = sets_[subidx(hashval)];
3127
        auto&  set      = inner.set_;
3128
        UniqueLock m(inner);
3129
        typename EmbeddedSet::template InsertSlotWithHash<true> f { inner, std::move(*slot), hashval };
3130
        return make_rv(PolicyTraits::apply(f, elem));
3131
    }
3132
3133
    template <class... Args>
3134
    iterator emplace_hint_with_hash(size_t hashval, const_iterator, Args&&... args) {
3135
        return emplace_with_hash(hashval, std::forward<Args>(args)...).first;
3136
    }
3137
3138
    // --------------------------------------------------------------------
3139
    // end of phmap expension
3140
    // --------------------------------------------------------------------
3141
3142
    template <class K, class... Args>
3143
    std::pair<iterator, bool> emplace_decomposable_with_hash(const K& key, size_t hashval, Args&&... args)
3144
    {
3145
        Inner& inner   = sets_[subidx(hashval)];
3146
        auto&  set     = inner.set_;
3147
        ReadWriteLock m(inner);
3148
        
3149
        size_t offset = set._find_key(key, hashval);
3150
        if (offset == (size_t)-1 && m.switch_to_unique()) {
3151
            // we did an unlock/lock, and another thread could have inserted the same key, so we need to
3152
            // do a find() again.
3153
            offset = set._find_key(key, hashval);
3154
        }
3155
        if (offset == (size_t)-1) {
3156
            offset = set.prepare_insert(hashval);
3157
            set.emplace_at(offset, std::forward<Args>(args)...);
3158
            set.set_ctrl(offset, H2(hashval));
3159
            return make_rv(&inner, {set.iterator_at(offset), true});
3160
        }
3161
        return make_rv(&inner, {set.iterator_at(offset), false});
3162
    }
3163
3164
    template <class K, class... Args>
3165
    std::pair<iterator, bool> emplace_decomposable(const K& key, Args&&... args)
3166
    {
3167
        return emplace_decomposable_with_hash(key, this->hash(key), std::forward<Args>(args)...);
3168
    }
3169
3170
    struct EmplaceDecomposable 
3171
    {
3172
        template <class K, class... Args>
3173
        std::pair<iterator, bool> operator()(const K& key, Args&&... args) const {
3174
            return s.emplace_decomposable(key, std::forward<Args>(args)...);
3175
        }
3176
        parallel_hash_set& s;
3177
    };
3178
3179
    // This overload kicks in if we can deduce the key from args. This enables us
3180
    // to avoid constructing value_type if an entry with the same key already
3181
    // exists.
3182
    //
3183
    // For example:
3184
    //
3185
    //   flat_hash_map<std::string, std::string> m = {{"abc", "def"}};
3186
    //   // Creates no std::string copies and makes no heap allocations.
3187
    //   m.emplace("abc", "xyz");
3188
    // --------------------------------------------------------------------
3189
    template <class... Args, typename std::enable_if<IsDecomposable<Args...>::value, int>::type = 0>
3190
    std::pair<iterator, bool> emplace(Args&&... args) {
3191
        return PolicyTraits::apply(EmplaceDecomposable{*this}, std::forward<Args>(args)...);
3192
    }
3193
3194
    // This overload kicks in if we cannot deduce the key from args. It constructs
3195
    // value_type unconditionally and then either moves it into the table or
3196
    // destroys.
3197
    // --------------------------------------------------------------------
3198
    template <class... Args, typename std::enable_if<!IsDecomposable<Args...>::value, int>::type = 0>
3199
    std::pair<iterator, bool> emplace(Args&&... args) {
3200
        typename phmap::aligned_storage<sizeof(slot_type), alignof(slot_type)>::type raw;
3201
        slot_type* slot = reinterpret_cast<slot_type*>(&raw);
3202
        size_t hashval  = this->hash(PolicyTraits::key(slot));
3203
3204
        PolicyTraits::construct(&alloc_ref(), slot, std::forward<Args>(args)...);
3205
        const auto& elem = PolicyTraits::element(slot);
3206
        Inner& inner     = sets_[subidx(hashval)];
3207
        auto&  set       = inner.set_;
3208
        UniqueLock m(inner);
3209
        typename EmbeddedSet::template InsertSlotWithHash<true> f { inner, std::move(*slot), hashval };
3210
        return make_rv(PolicyTraits::apply(f, elem));
3211
    }
3212
3213
    template <class... Args>
3214
    iterator emplace_hint(const_iterator, Args&&... args) {
3215
        return emplace(std::forward<Args>(args)...).first;
3216
    }
3217
3218
    iterator make_iterator(Inner* inner, const EmbeddedIterator it)
3219
    {
3220
        if (it == inner->set_.end())
3221
            return iterator();
3222
        return iterator(inner, &sets_[0] + num_tables, it);
3223
    }
3224
3225
    std::pair<iterator, bool> make_rv(Inner* inner, 
3226
                                      const std::pair<EmbeddedIterator, bool>& res)
3227
    {
3228
        return {iterator(inner, &sets_[0] + num_tables, res.first), res.second};
3229
    }
3230
3231
    // lazy_emplace
3232
    // ------------
3233
    template <class K = key_type, class F>
3234
    iterator lazy_emplace_with_hash(const key_arg<K>& key, size_t hashval, F&& f) {
3235
        Inner& inner = sets_[subidx(hashval)];
3236
        auto&  set   = inner.set_;
3237
        ReadWriteLock m(inner);
3238
        size_t offset = set._find_key(key, hashval);
3239
        if (offset == (size_t)-1 && m.switch_to_unique()) {
3240
            // we did an unlock/lock, and another thread could have inserted the same key, so we need to
3241
            // do a find() again.
3242
            offset = set._find_key(key, hashval);
3243
        }
3244
        if (offset == (size_t)-1) {
3245
            offset = set.prepare_insert(hashval);
3246
            set.lazy_emplace_at(offset, std::forward<F>(f));
3247
            set.set_ctrl(offset, H2(hashval));
3248
        }
3249
        return make_iterator(&inner, set.iterator_at(offset));
3250
    }
3251
3252
    template <class K = key_type, class F>
3253
    iterator lazy_emplace(const key_arg<K>& key, F&& f) {
3254
        return lazy_emplace_with_hash(key, this->hash(key), std::forward<F>(f));
3255
    }
3256
    
3257
    // emplace_single
3258
    // --------------
3259
    template <class K = key_type, class F>
3260
    void emplace_single_with_hash(const key_arg<K>& key, size_t hashval, F&& f) {
3261
        Inner& inner = sets_[subidx(hashval)];
3262
        auto&  set   = inner.set_;
3263
        UniqueLock m(inner);
3264
        set.emplace_single_with_hash(key, hashval, std::forward<F>(f));
3265
    }
3266
3267
    template <class K = key_type, class F>
3268
    void emplace_single(const key_arg<K>& key, F&& f) {
3269
        emplace_single_with_hash<K, F>(key, this->hash(key), std::forward<F>(f));
3270
    }
3271
3272
    // if set contains key, lambda is called with the value_type (under read lock protection),
3273
    // and if_contains returns true. This is a const API and lambda should not modify the value
3274
    // -----------------------------------------------------------------------------------------
3275
    template <class K = key_type, class F>
3276
    bool if_contains(const key_arg<K>& key, F&& f) const {
3277
        return const_cast<parallel_hash_set*>(this)->template 
3278
            modify_if_impl<K, F, SharedLock>(key, std::forward<F>(f));
3279
    }
3280
3281
    // if set contains key, lambda is called with the value_type  without read lock protection,
3282
    // and if_contains_unsafe returns true. This is a const API and lambda should not modify the value
3283
    // This should be used only if we know that no other thread may be mutating the set at the time.
3284
    // -----------------------------------------------------------------------------------------
3285
    template <class K = key_type, class F>
3286
    bool if_contains_unsafe(const key_arg<K>& key, F&& f) const {
3287
        return const_cast<parallel_hash_set*>(this)->template 
3288
            modify_if_impl<K, F, LockableBaseImpl<phmap::NullMutex>::DoNothing>(key, std::forward<F>(f));
3289
    }
3290
3291
    // if map contains key, lambda is called with the value_type  (under write lock protection),
3292
    // and modify_if returns true. This is a non-const API and lambda is allowed to modify the mapped value
3293
    // ----------------------------------------------------------------------------------------------------
3294
    template <class K = key_type, class F>
3295
    bool modify_if(const key_arg<K>& key, F&& f) {
3296
        return modify_if_impl<K, F, UniqueLock>(key, std::forward<F>(f));
3297
    }
3298
3299
    // -----------------------------------------------------------------------------------------
3300
    template <class K = key_type, class F, class L>
3301
    bool modify_if_impl(const key_arg<K>& key, F&& f) {
3302
#if __cplusplus >= 201703L
3303
        static_assert(std::is_invocable<F, value_type&>::value);
3304
#endif
3305
        L m;
3306
        auto ptr = this->template find_ptr<K, L>(key, this->hash(key), m);
3307
        if (ptr == nullptr)
3308
            return false;
3309
        std::forward<F>(f)(*ptr);
3310
        return true;
3311
    }
3312
3313
    // if map contains key, lambda is called with the mapped value  (under write lock protection).
3314
    // If the lambda returns true, the key is subsequently erased from the map (the write lock
3315
    // is only released after erase).
3316
    // returns true if key was erased, false otherwise.
3317
    // ----------------------------------------------------------------------------------------------------
3318
    template <class K = key_type, class F>
3319
    bool erase_if(const key_arg<K>& key, F&& f) {
3320
        return !!erase_if_impl<K, F, ReadWriteLock>(key, std::forward<F>(f));
3321
    }
3322
3323
    template <class K = key_type, class F, class L>
3324
    size_type erase_if_impl(const key_arg<K>& key, F&& f) {
3325
#if __cplusplus >= 201703L
3326
        static_assert(std::is_invocable<F, value_type&>::value);
3327
#endif
3328
        auto hashval = this->hash(key);
3329
        Inner& inner = sets_[subidx(hashval)];
3330
        auto& set = inner.set_;
3331
        L m(inner);
3332
        auto it = set.find(key, hashval);
3333
        if (it == set.end())
3334
            return 0;
3335
        if (m.switch_to_unique()) {
3336
            // we did an unlock/lock, need to call `find()` again
3337
            it = set.find(key, hashval);
3338
            if (it == set.end())
3339
                return 0;
3340
        }
3341
        if (std::forward<F>(f)(const_cast<value_type &>(*it)))
3342
        {
3343
            set._erase(it);
3344
            return 1;
3345
        }
3346
        return 0;
3347
    }
3348
3349
    // if map already  contains key, the first lambda is called with the mapped value (under 
3350
    // write lock protection) and can update the mapped value.
3351
    // if map does not contains key, the second lambda is called and it should invoke the 
3352
    // passed constructor to construct the value
3353
    // returns true if key was not already present, false otherwise.
3354
    // ---------------------------------------------------------------------------------------
3355
    template <class K = key_type, class FExists, class FEmplace>
3356
    bool lazy_emplace_l(const key_arg<K>& key, FExists&& fExists, FEmplace&& fEmplace) {
3357
        size_t hashval = this->hash(key);
3358
        ReadWriteLock m;
3359
        auto res = this->find_or_prepare_insert_with_hash(hashval, key, m);
3360
        Inner* inner = std::get<0>(res);
3361
        if (std::get<2>(res)) {
3362
            // key not found. call fEmplace lambda which should invoke passed constructor
3363
            inner->set_.lazy_emplace_at(std::get<1>(res), std::forward<FEmplace>(fEmplace));
3364
            inner->set_.set_ctrl(std::get<1>(res), H2(hashval));
3365
        } else {
3366
            // key found. Call fExists lambda. In case of the set, non "key" part of value_type can be changed
3367
            auto it = this->iterator_at(inner, inner->set_.iterator_at(std::get<1>(res)));
3368
            std::forward<FExists>(fExists)(const_cast<value_type &>(*it)); 
3369
        }
3370
        return std::get<2>(res);
3371
    }
3372
3373
    // Extension API: support iterating over all values
3374
    //
3375
    // flat_hash_set<std::string> s;
3376
    // s.insert(...);
3377
    // s.for_each([](auto const & key) {
3378
    //    // Safely iterates over all the keys
3379
    // });
3380
    template <class F>
3381
    void for_each(F&& fCallback) const {
3382
        for (auto const& inner : sets_) {
3383
            SharedLock m(const_cast<Inner&>(inner));
3384
            std::for_each(inner.set_.begin(), inner.set_.end(), fCallback);
3385
        }
3386
    }
3387
3388
    // this version allows to modify the values
3389
    template <class F>
3390
    void for_each_m(F&& fCallback) {
3391
        for (auto& inner : sets_) {
3392
            UniqueLock m(inner);
3393
            std::for_each(inner.set_.begin(), inner.set_.end(), fCallback);
3394
        }
3395
    }
3396
3397
#if __cplusplus >= 201703L
3398
    template <class ExecutionPolicy, class F>
3399
    void for_each(ExecutionPolicy&& policy, F&& fCallback) const {
3400
        std::for_each(
3401
            std::forward<ExecutionPolicy>(policy), sets_.begin(), sets_.end(),
3402
            [&](auto const& inner) {
3403
                SharedLock m(const_cast<Inner&>(inner));
3404
                std::for_each(inner.set_.begin(), inner.set_.end(), fCallback);
3405
            }
3406
        );
3407
    }
3408
3409
    template <class ExecutionPolicy, class F>
3410
    void for_each_m(ExecutionPolicy&& policy, F&& fCallback) {
3411
        std::for_each(
3412
            std::forward<ExecutionPolicy>(policy), sets_.begin(), sets_.end(),
3413
            [&](auto& inner) {
3414
                UniqueLock m(inner);
3415
                std::for_each(inner.set_.begin(), inner.set_.end(), fCallback);
3416
            }
3417
        );
3418
    }
3419
#endif
3420
3421
    // Extension API: access internal submaps by index
3422
    // under lock protection
3423
    // ex: m.with_submap(i, [&](const Map::EmbeddedSet& set) {
3424
    //        for (auto& p : set) { ...; }});
3425
    // -------------------------------------------------
3426
    template <class F>
3427
    void with_submap(size_t idx, F&& fCallback) const {
3428
        const Inner& inner     = sets_[idx];
3429
        const auto&  set = inner.set_;
3430
        SharedLock m(const_cast<Inner&>(inner));
3431
        fCallback(set);
3432
    }
3433
3434
    template <class F>
3435
    void with_submap_m(size_t idx, F&& fCallback) {
3436
        Inner& inner   = sets_[idx];
3437
        auto&  set     = inner.set_;
3438
        UniqueLock m(inner);
3439
        fCallback(set);
3440
    }
3441
3442
    // unsafe, for internal use only
3443
    Inner& get_inner(size_t idx) {
3444
        return  sets_[idx];
3445
    }
3446
3447
    const Inner& get_inner(size_t idx) const {
3448
        return  sets_[idx];
3449
    }
3450
3451
    // Extension API: support for heterogeneous keys.
3452
    //
3453
    //   std::unordered_set<std::string> s;
3454
    //   // Turns "abc" into std::string.
3455
    //   s.erase("abc");
3456
    //
3457
    //   flat_hash_set<std::string> s;
3458
    //   // Uses "abc" directly without copying it into std::string.
3459
    //   s.erase("abc");
3460
    //
3461
    // --------------------------------------------------------------------
3462
    template <class K = key_type>
3463
    size_type erase(const key_arg<K>& key) {
3464
        auto always_erase =  [](const value_type&){ return true; };
3465
        return erase_if_impl<K, decltype(always_erase), ReadWriteLock>(key, std::move(always_erase));
3466
    }
3467
3468
    // --------------------------------------------------------------------
3469
    iterator erase(const_iterator cit) { return erase(cit.iter_); }
3470
3471
    // Erases the element pointed to by `it`.  Unlike `std::unordered_set::erase`,
3472
    // this method returns void to reduce algorithmic complexity to O(1).  In
3473
    // order to erase while iterating across a map, use the following idiom (which
3474
    // also works for standard containers):
3475
    //
3476
    // for (auto it = m.begin(), end = m.end(); it != end;) {
3477
    //   if (<pred>) {
3478
    //     m._erase(it++);
3479
    //   } else {
3480
    //     ++it;
3481
    //   }
3482
    // }
3483
    //
3484
    // Do not use erase APIs taking iterators when accessing the map concurrently
3485
    // --------------------------------------------------------------------
3486
    void _erase(iterator it) {
3487
        Inner* inner = it.inner_;
3488
        assert(inner != nullptr);
3489
        auto&  set   = inner->set_;
3490
        // UniqueLock m(*inner); // don't lock here 
3491
        
3492
        set._erase(it.it_);
3493
    }
3494
    void _erase(const_iterator cit) { _erase(cit.iter_); }
3495
3496
    // This overload is necessary because otherwise erase<K>(const K&) would be
3497
    // a better match if non-const iterator is passed as an argument.
3498
    // Do not use erase APIs taking iterators when accessing the map concurrently
3499
    // --------------------------------------------------------------------
3500
    iterator erase(iterator it) { _erase(it++); return it; }
3501
3502
    iterator erase(const_iterator first, const_iterator last) {
3503
        while (first != last) {
3504
            _erase(first++);
3505
        }
3506
        return last.iter_;
3507
    }
3508
3509
    // Moves elements from `src` into `this`.
3510
    // If the element already exists in `this`, it is left unmodified in `src`.
3511
    // Do not use erase APIs taking iterators when accessing the map concurrently
3512
    // --------------------------------------------------------------------
3513
    template <typename E = Eq>
3514
    void merge(parallel_hash_set<N, RefSet, Mtx_, Policy, Hash, E, Alloc>& src) {  // NOLINT
3515
        assert(this != &src);
3516
        if (this != &src)
3517
        {
3518
            for (size_t i=0; i<num_tables; ++i)
3519
            {
3520
                typename Lockable::UniqueLocks l(sets_[i], src.sets_[i]);
3521
                sets_[i].set_.merge(src.sets_[i].set_);
3522
            }
3523
        }
3524
    }
3525
3526
    template <typename E = Eq>
3527
    void merge(parallel_hash_set<N, RefSet, Mtx_, Policy, Hash, E, Alloc>&& src) {
3528
        merge(src);
3529
    }
3530
3531
    node_type extract(const_iterator position) {
3532
        return position.iter_.inner_->set_.extract(EmbeddedConstIterator(position.iter_.it_));
3533
    }
3534
3535
    template <
3536
        class K = key_type,
3537
        typename std::enable_if<!std::is_same<K, iterator>::value, int>::type = 0>
3538
    node_type extract(const key_arg<K>& key) {
3539
        auto it = find(key);
3540
        return it == end() ? node_type() : extract(const_iterator{it});
3541
    }
3542
3543
    template<class Mtx2_>
3544
    void swap(parallel_hash_set<N, RefSet, Mtx2_, Policy, Hash, Eq, Alloc>& that)
3545
        noexcept(IsNoThrowSwappable<EmbeddedSet>() &&
3546
                 (!AllocTraits::propagate_on_container_swap::value ||
3547
                  IsNoThrowSwappable<allocator_type>(typename AllocTraits::propagate_on_container_swap{})))
3548
    {
3549
        using std::swap;
3550
        using Lockable2 = phmap::LockableImpl<Mtx2_>;
3551
         
3552
        for (size_t i=0; i<num_tables; ++i)
3553
        {
3554
            typename Lockable::UniqueLock l(sets_[i]);
3555
            typename Lockable2::UniqueLock l2(that.get_inner(i));
3556
            swap(sets_[i].set_, that.get_inner(i).set_);
3557
        }
3558
    }
3559
3560
    void rehash(size_t n) {
3561
        size_t nn = n / num_tables;
3562
        for (auto& inner : sets_)
3563
        {
3564
            UniqueLock m(inner);
3565
            inner.set_.rehash(nn);
3566
        }
3567
    }
3568
3569
    void reserve(size_t n) 
3570
    {
3571
        size_t target = GrowthToLowerboundCapacity(n);
3572
        size_t normalized = num_tables * NormalizeCapacity(n / num_tables);
3573
        rehash(normalized > target ? normalized : target); 
3574
    }
3575
3576
    // Extension API: support for heterogeneous keys.
3577
    //
3578
    //   std::unordered_set<std::string> s;
3579
    //   // Turns "abc" into std::string.
3580
    //   s.count("abc");
3581
    //
3582
    //   ch_set<std::string> s;
3583
    //   // Uses "abc" directly without copying it into std::string.
3584
    //   s.count("abc");
3585
    // --------------------------------------------------------------------
3586
    template <class K = key_type>
3587
    size_t count(const key_arg<K>& key) const {
3588
        return find(key) == end() ? 0 : 1;
3589
    }
3590
3591
    // Issues CPU prefetch instructions for the memory needed to find or insert
3592
    // a key.  Like all lookup functions, this support heterogeneous keys.
3593
    //
3594
    // NOTE: This is a very low level operation and should not be used without
3595
    // specific benchmarks indicating its importance.
3596
    // --------------------------------------------------------------------
3597
    void prefetch_hash(size_t hashval) const {
3598
        const Inner& inner = sets_[subidx(hashval)];
3599
        const auto&  set   = inner.set_;
3600
        SharedLock m(const_cast<Inner&>(inner));
3601
        set.prefetch_hash(hashval);
3602
    }
3603
3604
    template <class K = key_type>
3605
    void prefetch(const key_arg<K>& key) const {
3606
        prefetch_hash(this->hash(key));
3607
    }
3608
3609
    // The API of find() has two extensions.
3610
    //
3611
    // 1. The hash can be passed by the user. It must be equal to the hash of the
3612
    // key.
3613
    //
3614
    // 2. The type of the key argument doesn't have to be key_type. This is so
3615
    // called heterogeneous key support.
3616
    // --------------------------------------------------------------------
3617
    template <class K = key_type>
3618
    iterator find(const key_arg<K>& key, size_t hashval) {
3619
        SharedLock m;
3620
        return find(key, hashval, m);
3621
    }
3622
3623
    template <class K = key_type>
3624
    iterator find(const key_arg<K>& key) {
3625
        return find(key, this->hash(key));
3626
    }
3627
3628
    template <class K = key_type>
3629
    const_iterator find(const key_arg<K>& key, size_t hashval) const {
3630
        return const_cast<parallel_hash_set*>(this)->find(key, hashval);
3631
    }
3632
3633
    template <class K = key_type>
3634
    const_iterator find(const key_arg<K>& key) const {
3635
        return find(key, this->hash(key));
3636
    }
3637
3638
    template <class K = key_type>
3639
    bool contains(const key_arg<K>& key) const {
3640
        return find(key) != end();
3641
    }
3642
3643
    template <class K = key_type>
3644
    bool contains(const key_arg<K>& key, size_t hashval) const {
3645
        return find(key, hashval) != end();
3646
    }
3647
3648
    template <class K = key_type>
3649
    std::pair<iterator, iterator> equal_range(const key_arg<K>& key) {
3650
        auto it = find(key);
3651
        if (it != end()) return {it, std::next(it)};
3652
        return {it, it};
3653
    }
3654
3655
    template <class K = key_type>
3656
    std::pair<const_iterator, const_iterator> equal_range(
3657
        const key_arg<K>& key) const {
3658
        auto it = find(key);
3659
        if (it != end()) return {it, std::next(it)};
3660
        return {it, it};
3661
    }
3662
3663
    size_t bucket_count() const {
3664
        size_t sz = 0;
3665
        for (const auto& inner : sets_)
3666
        {
3667
            SharedLock m(const_cast<Inner&>(inner));
3668
            sz += inner.set_.bucket_count();
3669
        }
3670
        return sz; 
3671
    }
3672
3673
    float load_factor() const {
3674
        size_t _capacity = bucket_count();
3675
        return _capacity ? static_cast<float>(static_cast<double>(size()) / _capacity) : 0;
3676
    }
3677
3678
    float max_load_factor() const { return 1.0f; }
3679
    void max_load_factor(float) {
3680
        // Does nothing.
3681
    }
3682
3683
    hasher hash_function() const { return hash_ref(); }  // warning: doesn't match internal hash - use hash() member function
3684
    key_equal key_eq() const { return eq_ref(); }
3685
    allocator_type get_allocator() const { return alloc_ref(); }
3686
3687
    friend bool operator==(const parallel_hash_set& a, const parallel_hash_set& b) {
3688
        return std::equal(a.sets_.begin(), a.sets_.end(), b.sets_.begin());
3689
    }
3690
3691
    friend bool operator!=(const parallel_hash_set& a, const parallel_hash_set& b) {
3692
        return !(a == b);
3693
    }
3694
3695
    template<class Mtx2_>
3696
    friend void swap(parallel_hash_set& a,
3697
                     parallel_hash_set<N, RefSet, Mtx2_, Policy, Hash, Eq, Alloc>& b)
3698
        noexcept(noexcept(a.swap(b)))
3699
    {
3700
        a.swap(b);
3701
    }
3702
3703
    template <class K>
3704
    size_t hash(const K& key) const {
3705
        return HashElement{hash_ref()}(key);
3706
    }
3707
3708
#if !defined(PHMAP_NON_DETERMINISTIC)
3709
    template<typename OutputArchive>
3710
    bool phmap_dump(OutputArchive& ar) const;
3711
3712
    template<typename InputArchive>
3713
    bool phmap_load(InputArchive& ar);
3714
#endif
3715
3716
private:
3717
    template <class Container, typename Enabler>
3718
    friend struct phmap::priv::hashtable_debug_internal::HashtableDebugAccess;
3719
3720
    struct FindElement 
3721
    {
3722
        template <class K, class... Args>
3723
        const_iterator operator()(const K& key, Args&&...) const {
3724
            return s.find(key);
3725
        }
3726
        const parallel_hash_set& s;
3727
    };
3728
3729
    struct HashElement 
3730
    {
3731
        template <class K, class... Args>
3732
        size_t operator()(const K& key, Args&&...) const {
3733
            return phmap_mix<sizeof(size_t)>()(h(key));
3734
        }
3735
        const hasher& h;
3736
    };
3737
3738
    template <class K1>
3739
    struct EqualElement 
3740
    {
3741
        template <class K2, class... Args>
3742
        bool operator()(const K2& lhs, Args&&...) const {
3743
            return eq(lhs, rhs);
3744
        }
3745
        const K1& rhs;
3746
        const key_equal& eq;
3747
    };
3748
3749
    // "erases" the object from the container, except that it doesn't actually
3750
    // destroy the object. It only updates all the metadata of the class.
3751
    // This can be used in conjunction with Policy::transfer to move the object to
3752
    // another place.
3753
    // --------------------------------------------------------------------
3754
    void erase_meta_only(const_iterator cit) {
3755
        auto &it = cit.iter_;
3756
        assert(it.set_ != nullptr);
3757
        it.set_.erase_meta_only(const_iterator(it.it_));
3758
    }
3759
3760
    void drop_deletes_without_resize() PHMAP_ATTRIBUTE_NOINLINE {
3761
        for (auto& inner : sets_)
3762
        {
3763
            UniqueLock m(inner);
3764
            inner.set_.drop_deletes_without_resize();
3765
        }
3766
    }
3767
3768
    bool has_element(const value_type& elem) const {
3769
        size_t hashval = PolicyTraits::apply(HashElement{hash_ref()}, elem);
3770
        Inner& inner   = sets_[subidx(hashval)];
3771
        auto&  set     = inner.set_;
3772
        SharedLock m(const_cast<Inner&>(inner));
3773
        return set.has_element(elem, hashval);
3774
    }
3775
3776
    // TODO(alkis): Optimize this assuming *this and that don't overlap.
3777
    // --------------------------------------------------------------------
3778
    template<class Mtx2_>
3779
    parallel_hash_set& move_assign(parallel_hash_set<N, RefSet, Mtx2_, Policy, Hash, Eq, Alloc>&& that, std::true_type) {
3780
        parallel_hash_set<N, RefSet, Mtx2_, Policy, Hash, Eq, Alloc> tmp(std::move(that));
3781
        swap(tmp);
3782
        return *this;
3783
    }
3784
3785
    template<class Mtx2_>
3786
    parallel_hash_set& move_assign(parallel_hash_set<N, RefSet, Mtx2_, Policy, Hash, Eq, Alloc>&& that, std::false_type) {
3787
        parallel_hash_set<N, RefSet, Mtx2_, Policy, Hash, Eq, Alloc> tmp(std::move(that), alloc_ref());
3788
        swap(tmp);
3789
        return *this;
3790
    }
3791
3792
protected:
3793
    template <class K = key_type, class L = SharedLock>
3794
    pointer find_ptr(const key_arg<K>& key, size_t hashval, L& mutexlock)
3795
    {
3796
        Inner& inner = sets_[subidx(hashval)];
3797
        auto& set = inner.set_;
3798
        mutexlock = std::move(L(inner));
3799
        return set.find_ptr(key, hashval);
3800
    }
3801
3802
    template <class K = key_type, class L = SharedLock>
3803
    iterator find(const key_arg<K>& key, size_t hashval, L& mutexlock) {
3804
        Inner& inner = sets_[subidx(hashval)];
3805
        auto& set = inner.set_;
3806
        mutexlock = std::move(L(inner));
3807
        return make_iterator(&inner, set.find(key, hashval));
3808
    }
3809
3810
    template <class K>
3811
    std::tuple<Inner*, size_t, bool> 
3812
    find_or_prepare_insert_with_hash(size_t hashval, const K& key, ReadWriteLock &mutexlock) {
3813
        Inner& inner = sets_[subidx(hashval)];
3814
        auto&  set   = inner.set_;
3815
        mutexlock    = std::move(ReadWriteLock(inner));
3816
        size_t offset = set._find_key(key, hashval);
3817
        if (offset == (size_t)-1 && mutexlock.switch_to_unique()) {
3818
            // we did an unlock/lock, and another thread could have inserted the same key, so we need to
3819
            // do a find() again.
3820
            offset = set._find_key(key, hashval);
3821
        }
3822
        if (offset == (size_t)-1) {
3823
            offset = set.prepare_insert(hashval);
3824
            return std::make_tuple(&inner, offset, true);
3825
        }
3826
        return std::make_tuple(&inner, offset, false);
3827
    }
3828
3829
    template <class K>
3830
    std::tuple<Inner*, size_t, bool> 
3831
    find_or_prepare_insert(const K& key, ReadWriteLock &mutexlock) {
3832
        return find_or_prepare_insert_with_hash<K>(this->hash(key), key, mutexlock);
3833
    }
3834
3835
    iterator iterator_at(Inner *inner, 
3836
                         const EmbeddedIterator& it) { 
3837
        return {inner, &sets_[0] + num_tables, it}; 
3838
    }
3839
    const_iterator iterator_at(Inner *inner, 
3840
                               const EmbeddedIterator& it) const { 
3841
        return {inner, &sets_[0] + num_tables, it}; 
3842
    }
3843
3844
    static size_t subidx(size_t hashval) {
3845
        return ((hashval >> 8) ^ (hashval >> 16) ^ (hashval >> 24)) & mask;
3846
    }
3847
3848
    static size_t subcnt() {
3849
        return num_tables;
3850
    }
3851
3852
private:
3853
    friend struct RawHashSetTestOnlyAccess;
3854
3855
    size_t growth_left() { 
3856
        size_t sz = 0;
3857
        for (const auto& set : sets_)
3858
            sz += set.growth_left();
3859
        return sz; 
3860
    }
3861
3862
    hasher&       hash_ref()        { return sets_[0].set_.hash_ref(); }
3863
    const hasher& hash_ref() const  { return sets_[0].set_.hash_ref(); }
3864
    key_equal&       eq_ref()       { return sets_[0].set_.eq_ref(); }
3865
    const key_equal& eq_ref() const { return sets_[0].set_.eq_ref(); }
3866
    allocator_type&  alloc_ref()    { return sets_[0].set_.alloc_ref(); }
3867
    const allocator_type& alloc_ref() const { 
3868
        return sets_[0].set_.alloc_ref();
3869
    }
3870
3871
protected:       // protected in case users want to derive fromm this
3872
    std::array<Inner, num_tables> sets_;
3873
};
3874
3875
// --------------------------------------------------------------------------
3876
// --------------------------------------------------------------------------
3877
template <size_t N,
3878
          template <class, class, class, class> class RefSet,
3879
          class Mtx_,
3880
          class Policy, class Hash, class Eq, class Alloc>
3881
class parallel_hash_map : public parallel_hash_set<N, RefSet, Mtx_, Policy, Hash, Eq, Alloc> 
3882
{
3883
    // P is Policy. It's passed as a template argument to support maps that have
3884
    // incomplete types as values, as in unordered_map<K, IncompleteType>.
3885
    // MappedReference<> may be a non-reference type.
3886
    template <class P>
3887
    using MappedReference = decltype(P::value(
3888
            std::addressof(std::declval<typename parallel_hash_map::reference>())));
3889
3890
    // MappedConstReference<> may be a non-reference type.
3891
    template <class P>
3892
    using MappedConstReference = decltype(P::value(
3893
            std::addressof(std::declval<typename parallel_hash_map::const_reference>())));
3894
3895
    using KeyArgImpl =
3896
        KeyArg<IsTransparent<Eq>::value && IsTransparent<Hash>::value>;
3897
3898
    using Base = typename parallel_hash_map::parallel_hash_set;
3899
    using Lockable      = phmap::LockableImpl<Mtx_>;
3900
    using UniqueLock    = typename Lockable::UniqueLock;
3901
    using SharedLock    = typename Lockable::SharedLock;
3902
    using ReadWriteLock = typename Lockable::ReadWriteLock;
3903
3904
public:
3905
    using key_type    = typename Policy::key_type;
3906
    using mapped_type = typename Policy::mapped_type;
3907
    using value_type  = typename Base::value_type;
3908
    template <class K>
3909
    using key_arg = typename KeyArgImpl::template type<K, key_type>;
3910
3911
    static_assert(!std::is_reference<key_type>::value, "");
3912
    // TODO(alkis): remove this assertion and verify that reference mapped_type is
3913
    // supported.
3914
    static_assert(!std::is_reference<mapped_type>::value, "");
3915
3916
    using iterator = typename parallel_hash_map::parallel_hash_set::iterator;
3917
    using const_iterator = typename parallel_hash_map::parallel_hash_set::const_iterator;
3918
3919
    parallel_hash_map() {}
3920
3921
#ifdef __INTEL_COMPILER
3922
    using Base::parallel_hash_set;
3923
#else
3924
    using parallel_hash_map::parallel_hash_set::parallel_hash_set;
3925
#endif
3926
3927
    // The last two template parameters ensure that both arguments are rvalues
3928
    // (lvalue arguments are handled by the overloads below). This is necessary
3929
    // for supporting bitfield arguments.
3930
    //
3931
    //   union { int n : 1; };
3932
    //   flat_hash_map<int, int> m;
3933
    //   m.insert_or_assign(n, n);
3934
    template <class K = key_type, class V = mapped_type, K* = nullptr,
3935
              V* = nullptr>
3936
    std::pair<iterator, bool> insert_or_assign(key_arg<K>&& k, V&& v) {
3937
        return insert_or_assign_impl(std::forward<K>(k), std::forward<V>(v));
3938
    }
3939
3940
    template <class K = key_type, class V = mapped_type, K* = nullptr>
3941
    std::pair<iterator, bool> insert_or_assign(key_arg<K>&& k, const V& v) {
3942
        return insert_or_assign_impl(std::forward<K>(k), v);
3943
    }
3944
3945
    template <class K = key_type, class V = mapped_type, V* = nullptr>
3946
    std::pair<iterator, bool> insert_or_assign(const key_arg<K>& k, V&& v) {
3947
        return insert_or_assign_impl(k, std::forward<V>(v));
3948
    }
3949
3950
    template <class K = key_type, class V = mapped_type>
3951
    std::pair<iterator, bool> insert_or_assign(const key_arg<K>& k, const V& v) {
3952
        return insert_or_assign_impl(k, v);
3953
    }
3954
3955
    template <class K = key_type, class V = mapped_type, K* = nullptr,
3956
              V* = nullptr>
3957
    iterator insert_or_assign(const_iterator, key_arg<K>&& k, V&& v) {
3958
        return insert_or_assign(std::forward<K>(k), std::forward<V>(v)).first;
3959
    }
3960
3961
    template <class K = key_type, class V = mapped_type, K* = nullptr>
3962
    iterator insert_or_assign(const_iterator, key_arg<K>&& k, const V& v) {
3963
        return insert_or_assign(std::forward<K>(k), v).first;
3964
    }
3965
3966
    template <class K = key_type, class V = mapped_type, V* = nullptr>
3967
    iterator insert_or_assign(const_iterator, const key_arg<K>& k, V&& v) {
3968
        return insert_or_assign(k, std::forward<V>(v)).first;
3969
    }
3970
3971
    template <class K = key_type, class V = mapped_type>
3972
    iterator insert_or_assign(const_iterator, const key_arg<K>& k, const V& v) {
3973
        return insert_or_assign(k, v).first;
3974
    }
3975
3976
    template <class K = key_type, class... Args,
3977
              typename std::enable_if<
3978
                  !std::is_convertible<K, const_iterator>::value, int>::type = 0,
3979
              K* = nullptr>
3980
    std::pair<iterator, bool> try_emplace(key_arg<K>&& k, Args&&... args) {
3981
        return try_emplace_impl(std::forward<K>(k), std::forward<Args>(args)...);
3982
    }
3983
3984
    template <class K = key_type, class... Args,
3985
              typename std::enable_if<
3986
                  !std::is_convertible<K, const_iterator>::value, int>::type = 0>
3987
    std::pair<iterator, bool> try_emplace(const key_arg<K>& k, Args&&... args) {
3988
        return try_emplace_impl(k, std::forward<Args>(args)...);
3989
    }
3990
3991
    template <class K = key_type, class... Args, K* = nullptr>
3992
    iterator try_emplace(const_iterator, key_arg<K>&& k, Args&&... args) {
3993
        return try_emplace(std::forward<K>(k), std::forward<Args>(args)...).first;
3994
    }
3995
3996
    template <class K = key_type, class... Args>
3997
    iterator try_emplace(const_iterator, const key_arg<K>& k, Args&&... args) {
3998
        return try_emplace(k, std::forward<Args>(args)...).first;
3999
    }
4000
4001
    template <class K = key_type, class P = Policy>
4002
    MappedReference<P> at(const key_arg<K>& key) {
4003
        auto it = this->find(key);
4004
        if (it == this->end()) 
4005
            phmap::base_internal::ThrowStdOutOfRange("phmap at(): lookup non-existent key");
4006
        return Policy::value(&*it);
4007
    }
4008
4009
    template <class K = key_type, class P = Policy>
4010
    MappedConstReference<P> at(const key_arg<K>& key) const {
4011
        auto it = this->find(key);
4012
        if (it == this->end()) 
4013
            phmap::base_internal::ThrowStdOutOfRange("phmap at(): lookup non-existent key");
4014
        return Policy::value(&*it);
4015
    }
4016
4017
    // ----------- phmap extensions --------------------------
4018
4019
    template <class K = key_type, class... Args,
4020
              typename std::enable_if<
4021
                  !std::is_convertible<K, const_iterator>::value, int>::type = 0,
4022
              K* = nullptr>
4023
    std::pair<iterator, bool> try_emplace_with_hash(size_t hashval, key_arg<K>&& k, Args&&... args) {
4024
        return try_emplace_impl_with_hash(hashval, std::forward<K>(k), std::forward<Args>(args)...);
4025
    }
4026
4027
    template <class K = key_type, class... Args,
4028
              typename std::enable_if<
4029
                  !std::is_convertible<K, const_iterator>::value, int>::type = 0>
4030
    std::pair<iterator, bool> try_emplace_with_hash(size_t hashval, const key_arg<K>& k, Args&&... args) {
4031
        return try_emplace_impl_with_hash(hashval, k, std::forward<Args>(args)...);
4032
    }
4033
4034
    template <class K = key_type, class... Args, K* = nullptr>
4035
    iterator try_emplace_with_hash(size_t hashval, const_iterator, key_arg<K>&& k, Args&&... args) {
4036
        return try_emplace_with_hash(hashval, std::forward<K>(k), std::forward<Args>(args)...).first;
4037
    }
4038
4039
    template <class K = key_type, class... Args>
4040
    iterator try_emplace_with_hash(size_t hashval, const_iterator, const key_arg<K>& k, Args&&... args) {
4041
        return try_emplace_with_hash(hashval, k, std::forward<Args>(args)...).first;
4042
    }
4043
4044
    // if map does not contains key, it is inserted and the mapped value is value-constructed 
4045
    // with the provided arguments (if any), as with try_emplace. 
4046
    // if map already  contains key, then the lambda is called with the mapped value (under 
4047
    // write lock protection) and can update the mapped value.
4048
    // returns true if key was not already present, false otherwise.
4049
    // ---------------------------------------------------------------------------------------
4050
    template <class K = key_type, class F, class... Args>
4051
    bool try_emplace_l(K&& k, F&& f, Args&&... args) {
4052
        size_t hashval = this->hash(k);
4053
        ReadWriteLock m;
4054
        auto res = this->find_or_prepare_insert_with_hash(hashval, k, m);
4055
        typename Base::Inner *inner = std::get<0>(res);
4056
        if (std::get<2>(res)) {
4057
            inner->set_.emplace_at(std::get<1>(res), std::piecewise_construct,
4058
                                   std::forward_as_tuple(std::forward<K>(k)),
4059
                                   std::forward_as_tuple(std::forward<Args>(args)...));
4060
            inner->set_.set_ctrl(std::get<1>(res), H2(hashval));
4061
        } else {
4062
            auto it = this->iterator_at(inner, inner->set_.iterator_at(std::get<1>(res)));
4063
            // call lambda. in case of the set, non "key" part of value_type can be changed
4064
            std::forward<F>(f)(const_cast<value_type &>(*it));
4065
        }
4066
        return std::get<2>(res);
4067
    }
4068
4069
    // returns {pointer, bool} instead of {iterator, bool} per try_emplace.
4070
    // useful for node-based containers, since the pointer is not invalidated by concurrent insert etc.
4071
    template <class K = key_type, class... Args>
4072
    std::pair<typename parallel_hash_map::parallel_hash_set::pointer, bool> try_emplace_p(K&& k, Args&&... args) {
4073
        size_t hashval = this->hash(k);
4074
        ReadWriteLock m;
4075
        auto res = this->find_or_prepare_insert_with_hash(hashval, k, m);
4076
        typename Base::Inner *inner = std::get<0>(res);
4077
        if (std::get<2>(res)) {
4078
            inner->set_.emplace_at(std::get<1>(res), std::piecewise_construct,
4079
                                   std::forward_as_tuple(std::forward<K>(k)),
4080
                                   std::forward_as_tuple(std::forward<Args>(args)...));
4081
            inner->set_.set_ctrl(std::get<1>(res), H2(hashval));
4082
        }
4083
        auto it = this->iterator_at(inner, inner->set_.iterator_at(std::get<1>(res)));
4084
        return {&*it, std::get<2>(res)};
4085
    }
4086
4087
    // ----------- end of phmap extensions --------------------------
4088
4089
    template <class K = key_type, class P = Policy, K* = nullptr>
4090
    MappedReference<P> operator[](key_arg<K>&& key) {
4091
        return Policy::value(&*try_emplace(std::forward<K>(key)).first);
4092
    }
4093
4094
    template <class K = key_type, class P = Policy>
4095
    MappedReference<P> operator[](const key_arg<K>& key) {
4096
        return Policy::value(&*try_emplace(key).first);
4097
    }
4098
4099
private:
4100
4101
    template <class K, class V>
4102
    std::pair<iterator, bool> insert_or_assign_impl(K&& k, V&& v) {
4103
        size_t hashval = this->hash(k);
4104
        ReadWriteLock m;
4105
        auto res = this->find_or_prepare_insert_with_hash(hashval, k, m);
4106
        typename Base::Inner *inner = std::get<0>(res);
4107
        if (std::get<2>(res)) {
4108
            inner->set_.emplace_at(std::get<1>(res), std::forward<K>(k), std::forward<V>(v));
4109
            inner->set_.set_ctrl(std::get<1>(res), H2(hashval));
4110
        } else
4111
            Policy::value(&*inner->set_.iterator_at(std::get<1>(res))) = std::forward<V>(v);
4112
        return {this->iterator_at(inner, inner->set_.iterator_at(std::get<1>(res))), 
4113
                std::get<2>(res)};
4114
    }
4115
4116
    template <class K = key_type, class... Args>
4117
    std::pair<iterator, bool> try_emplace_impl(K&& k, Args&&... args) {
4118
        return try_emplace_impl_with_hash(this->hash(k), std::forward<K>(k),
4119
                                          std::forward<Args>(args)...);
4120
    }
4121
4122
    template <class K = key_type, class... Args>
4123
    std::pair<iterator, bool> try_emplace_impl_with_hash(size_t hashval, K&& k, Args&&... args) {
4124
        ReadWriteLock m;
4125
        auto res = this->find_or_prepare_insert_with_hash(hashval, k, m);
4126
        typename Base::Inner *inner = std::get<0>(res);
4127
        if (std::get<2>(res)) {
4128
            inner->set_.emplace_at(std::get<1>(res), std::piecewise_construct,
4129
                                   std::forward_as_tuple(std::forward<K>(k)),
4130
                                   std::forward_as_tuple(std::forward<Args>(args)...));
4131
            inner->set_.set_ctrl(std::get<1>(res), H2(hashval));
4132
        }
4133
        return {this->iterator_at(inner, inner->set_.iterator_at(std::get<1>(res))), 
4134
                std::get<2>(res)};
4135
    }
4136
4137
    
4138
};
4139
4140
4141
// Constructs T into uninitialized storage pointed by `ptr` using the args
4142
// specified in the tuple.
4143
// ----------------------------------------------------------------------------
4144
template <class Alloc, class T, class Tuple>
4145
void ConstructFromTuple(Alloc* alloc, T* ptr, Tuple&& t) {
4146
    memory_internal::ConstructFromTupleImpl(
4147
        alloc, ptr, std::forward<Tuple>(t),
4148
        phmap::make_index_sequence<
4149
        std::tuple_size<typename std::decay<Tuple>::type>::value>());
4150
}
4151
4152
// Constructs T using the args specified in the tuple and calls F with the
4153
// constructed value.
4154
// ----------------------------------------------------------------------------
4155
template <class T, class Tuple, class F>
4156
decltype(std::declval<F>()(std::declval<T>())) WithConstructed(
4157
    Tuple&& t, F&& f) {
4158
    return memory_internal::WithConstructedImpl<T>(
4159
        std::forward<Tuple>(t),
4160
        phmap::make_index_sequence<
4161
        std::tuple_size<typename std::decay<Tuple>::type>::value>(),
4162
        std::forward<F>(f));
4163
}
4164
4165
// ----------------------------------------------------------------------------
4166
// Given arguments of an std::pair's consructor, PairArgs() returns a pair of
4167
// tuples with references to the passed arguments. The tuples contain
4168
// constructor arguments for the first and the second elements of the pair.
4169
//
4170
// The following two snippets are equivalent.
4171
//
4172
// 1. std::pair<F, S> p(args...);
4173
//
4174
// 2. auto a = PairArgs(args...);
4175
//    std::pair<F, S> p(std::piecewise_construct,
4176
//                      std::move(p.first), std::move(p.second));
4177
// ----------------------------------------------------------------------------
4178
0
inline std::pair<std::tuple<>, std::tuple<>> PairArgs() { return {}; }
4179
4180
template <class F, class S>
4181
19.9M
std::pair<std::tuple<F&&>, std::tuple<S&&>> PairArgs(F&& f, S&& s) {
4182
19.9M
  return {std::piecewise_construct, std::forward_as_tuple(std::forward<F>(f)),
4183
19.9M
          std::forward_as_tuple(std::forward<S>(s))};
4184
19.9M
}
std::__1::pair<std::__1::tuple<unsigned int const&>, std::__1::tuple<int const&> > phmap::priv::PairArgs<unsigned int const&, int const&>(unsigned int const&, int const&)
Line
Count
Source
4181
11.9M
std::pair<std::tuple<F&&>, std::tuple<S&&>> PairArgs(F&& f, S&& s) {
4182
11.9M
  return {std::piecewise_construct, std::forward_as_tuple(std::forward<F>(f)),
4183
11.9M
          std::forward_as_tuple(std::forward<S>(s))};
4184
11.9M
}
std::__1::pair<std::__1::tuple<unsigned int const&&>, std::__1::tuple<int&&> > phmap::priv::PairArgs<unsigned int const, int>(unsigned int const&&, int&&)
Line
Count
Source
4181
8.01M
std::pair<std::tuple<F&&>, std::tuple<S&&>> PairArgs(F&& f, S&& s) {
4182
8.01M
  return {std::piecewise_construct, std::forward_as_tuple(std::forward<F>(f)),
4183
8.01M
          std::forward_as_tuple(std::forward<S>(s))};
4184
8.01M
}
4185
4186
template <class F, class S>
4187
std::pair<std::tuple<const F&>, std::tuple<const S&>> PairArgs(
4188
11.9M
    const std::pair<F, S>& p) {
4189
11.9M
    return PairArgs(p.first, p.second);
4190
11.9M
}
4191
4192
template <class F, class S>
4193
8.01M
std::pair<std::tuple<F&&>, std::tuple<S&&>> PairArgs(std::pair<F, S>&& p) {
4194
8.01M
    return PairArgs(std::forward<F>(p.first), std::forward<S>(p.second));
4195
8.01M
}
4196
4197
template <class F, class S>
4198
auto PairArgs(std::piecewise_construct_t, F&& f, S&& s)
4199
    -> decltype(std::make_pair(memory_internal::TupleRef(std::forward<F>(f)),
4200
                               memory_internal::TupleRef(std::forward<S>(s)))) {
4201
    return std::make_pair(memory_internal::TupleRef(std::forward<F>(f)),
4202
                          memory_internal::TupleRef(std::forward<S>(s)));
4203
}
4204
4205
// A helper function for implementing apply() in map policies.
4206
// ----------------------------------------------------------------------------
4207
template <class F, class... Args>
4208
auto DecomposePair(F&& f, Args&&... args)
4209
    -> decltype(memory_internal::DecomposePairImpl(
4210
19.9M
        std::forward<F>(f), PairArgs(std::forward<Args>(args)...))) {
4211
19.9M
    return memory_internal::DecomposePairImpl(
4212
19.9M
        std::forward<F>(f), PairArgs(std::forward<Args>(args)...));
4213
19.9M
}
_ZN5phmap4priv13DecomposePairINS0_12raw_hash_setINS0_17FlatHashMapPolicyIjiEENS_4HashIjEENS_7EqualToIjEENSt3__19allocatorINS9_4pairIKjiEEEEE19EmplaceDecomposableEJSD_EEEDTclsr15memory_internalE17DecomposePairImplclsr3stdE7forwardIT_Efp_Ecl8PairArgsspclsr3stdE7forwardIT0_Efp0_EEEEOSH_DpOSI_
Line
Count
Source
4210
8.01M
        std::forward<F>(f), PairArgs(std::forward<Args>(args)...))) {
4211
8.01M
    return memory_internal::DecomposePairImpl(
4212
8.01M
        std::forward<F>(f), PairArgs(std::forward<Args>(args)...));
4213
8.01M
}
_ZN5phmap4priv13DecomposePairINS0_12raw_hash_setINS0_17FlatHashMapPolicyIjiEENS_4HashIjEENS_7EqualToIjEENSt3__19allocatorINS9_4pairIKjiEEEEE12EqualElementIjEEJRSD_EEEDTclsr15memory_internalE17DecomposePairImplclsr3stdE7forwardIT_Efp_Ecl8PairArgsspclsr3stdE7forwardIT0_Efp0_EEEEOSJ_DpOSK_
Line
Count
Source
4210
10.4M
        std::forward<F>(f), PairArgs(std::forward<Args>(args)...))) {
4211
10.4M
    return memory_internal::DecomposePairImpl(
4212
10.4M
        std::forward<F>(f), PairArgs(std::forward<Args>(args)...));
4213
10.4M
}
_ZN5phmap4priv13DecomposePairINS0_12raw_hash_setINS0_17FlatHashMapPolicyIjiEENS_4HashIjEENS_7EqualToIjEENSt3__19allocatorINS9_4pairIKjiEEEEE11HashElementEJRSD_EEEDTclsr15memory_internalE17DecomposePairImplclsr3stdE7forwardIT_Efp_Ecl8PairArgsspclsr3stdE7forwardIT0_Efp0_EEEEOSI_DpOSJ_
Line
Count
Source
4210
958k
        std::forward<F>(f), PairArgs(std::forward<Args>(args)...))) {
4211
958k
    return memory_internal::DecomposePairImpl(
4212
958k
        std::forward<F>(f), PairArgs(std::forward<Args>(args)...));
4213
958k
}
_ZN5phmap4priv13DecomposePairINS0_12raw_hash_setINS0_17FlatHashMapPolicyIjiEENS_4HashIjEENS_7EqualToIjEENSt3__19allocatorINS9_4pairIKjiEEEEE11HashElementEJRKSD_EEEDTclsr15memory_internalE17DecomposePairImplclsr3stdE7forwardIT_Efp_Ecl8PairArgsspclsr3stdE7forwardIT0_Efp0_EEEEOSJ_DpOSK_
Line
Count
Source
4210
521k
        std::forward<F>(f), PairArgs(std::forward<Args>(args)...))) {
4211
521k
    return memory_internal::DecomposePairImpl(
4212
521k
        std::forward<F>(f), PairArgs(std::forward<Args>(args)...));
4213
521k
}
4214
4215
// A helper function for implementing apply() in set policies.
4216
// ----------------------------------------------------------------------------
4217
template <class F, class Arg>
4218
decltype(std::declval<F>()(std::declval<const Arg&>(), std::declval<Arg>()))
4219
DecomposeValue(F&& f, Arg&& arg) {
4220
    const auto& key = arg;
4221
    return std::forward<F>(f)(key, std::forward<Arg>(arg));
4222
}
4223
4224
4225
// --------------------------------------------------------------------------
4226
// Policy: a policy defines how to perform different operations on
4227
// the slots of the hashtable (see hash_policy_traits.h for the full interface
4228
// of policy).
4229
//
4230
// Hash: a (possibly polymorphic) functor that hashes keys of the hashtable. The
4231
// functor should accept a key and return size_t as hash. For best performance
4232
// it is important that the hash function provides high entropy across all bits
4233
// of the hash.
4234
//
4235
// Eq: a (possibly polymorphic) functor that compares two keys for equality. It
4236
// should accept two (of possibly different type) keys and return a bool: true
4237
// if they are equal, false if they are not. If two keys compare equal, then
4238
// their hash values as defined by Hash MUST be equal.
4239
//
4240
// Allocator: an Allocator [https://devdocs.io/cpp/concept/allocator] with which
4241
// the storage of the hashtable will be allocated and the elements will be
4242
// constructed and destroyed.
4243
// --------------------------------------------------------------------------
4244
template <class T>
4245
struct FlatHashSetPolicy 
4246
{
4247
    using slot_type = T;
4248
    using key_type = T;
4249
    using init_type = T;
4250
    using constant_iterators = std::true_type;
4251
    using is_flat = std::true_type;
4252
4253
    template <class Allocator, class... Args>
4254
    static void construct(Allocator* alloc, slot_type* slot, Args&&... args) {
4255
        phmap::allocator_traits<Allocator>::construct(*alloc, slot,
4256
                                                      std::forward<Args>(args)...);
4257
    }
4258
4259
    template <class Allocator>
4260
    static void destroy(Allocator* alloc, slot_type* slot) {
4261
        phmap::allocator_traits<Allocator>::destroy(*alloc, slot);
4262
    }
4263
4264
    template <class Allocator>
4265
    static void transfer(Allocator* alloc, slot_type* new_slot,
4266
                         slot_type* old_slot) {
4267
        construct(alloc, new_slot, std::move(*old_slot));
4268
        destroy(alloc, old_slot);
4269
    }
4270
4271
    static T& element(slot_type* slot) { return *slot; }
4272
4273
    template <class F, class... Args>
4274
    static decltype(phmap::priv::DecomposeValue(
4275
                        std::declval<F>(), std::declval<Args>()...))
4276
    apply(F&& f, Args&&... args) {
4277
        return phmap::priv::DecomposeValue(
4278
            std::forward<F>(f), std::forward<Args>(args)...);
4279
    }
4280
4281
    static size_t space_used(const T*) { return 0; }
4282
};
4283
4284
// --------------------------------------------------------------------------
4285
// --------------------------------------------------------------------------
4286
template <class K, class V>
4287
struct FlatHashMapPolicy 
4288
{
4289
    using slot_policy = priv::map_slot_policy<K, V>;
4290
    using slot_type = typename slot_policy::slot_type;
4291
    using key_type = K;
4292
    using mapped_type = V;
4293
    using init_type = std::pair</*non const*/ key_type, mapped_type>;
4294
    using is_flat = std::true_type;
4295
4296
    template <class Allocator, class... Args>
4297
536k
    static void construct(Allocator* alloc, slot_type* slot, Args&&... args) {
4298
536k
        slot_policy::construct(alloc, slot, std::forward<Args>(args)...);
4299
536k
    }
4300
4301
    template <class Allocator>
4302
0
    static void destroy(Allocator* alloc, slot_type* slot) {
4303
0
        slot_policy::destroy(alloc, slot);
4304
0
    }
4305
4306
    template <class Allocator>
4307
    static void transfer(Allocator* alloc, slot_type* new_slot,
4308
958k
                         slot_type* old_slot) {
4309
958k
        slot_policy::transfer(alloc, new_slot, old_slot);
4310
958k
    }
4311
4312
    template <class F, class... Args>
4313
    static decltype(phmap::priv::DecomposePair(
4314
                        std::declval<F>(), std::declval<Args>()...))
4315
19.9M
    apply(F&& f, Args&&... args) {
4316
19.9M
        return phmap::priv::DecomposePair(std::forward<F>(f),
4317
19.9M
                                                        std::forward<Args>(args)...);
4318
19.9M
    }
_ZN5phmap4priv17FlatHashMapPolicyIjiE5applyINS0_12raw_hash_setIS2_NS_4HashIjEENS_7EqualToIjEENSt3__19allocatorINS9_4pairIKjiEEEEE19EmplaceDecomposableEJSD_EEEDTclsr5phmap4privE13DecomposePairclsr3stdE7declvalIT_EEspclsr3stdE7declvalIT0_EEEEOSH_DpOSI_
Line
Count
Source
4315
8.01M
    apply(F&& f, Args&&... args) {
4316
8.01M
        return phmap::priv::DecomposePair(std::forward<F>(f),
4317
8.01M
                                                        std::forward<Args>(args)...);
4318
8.01M
    }
_ZN5phmap4priv17FlatHashMapPolicyIjiE5applyINS0_12raw_hash_setIS2_NS_4HashIjEENS_7EqualToIjEENSt3__19allocatorINS9_4pairIKjiEEEEE12EqualElementIjEEJRSD_EEEDTclsr5phmap4privE13DecomposePairclsr3stdE7declvalIT_EEspclsr3stdE7declvalIT0_EEEEOSJ_DpOSK_
Line
Count
Source
4315
10.4M
    apply(F&& f, Args&&... args) {
4316
10.4M
        return phmap::priv::DecomposePair(std::forward<F>(f),
4317
10.4M
                                                        std::forward<Args>(args)...);
4318
10.4M
    }
_ZN5phmap4priv17FlatHashMapPolicyIjiE5applyINS0_12raw_hash_setIS2_NS_4HashIjEENS_7EqualToIjEENSt3__19allocatorINS9_4pairIKjiEEEEE11HashElementEJRSD_EEEDTclsr5phmap4privE13DecomposePairclsr3stdE7declvalIT_EEspclsr3stdE7declvalIT0_EEEEOSI_DpOSJ_
Line
Count
Source
4315
958k
    apply(F&& f, Args&&... args) {
4316
958k
        return phmap::priv::DecomposePair(std::forward<F>(f),
4317
958k
                                                        std::forward<Args>(args)...);
4318
958k
    }
_ZN5phmap4priv17FlatHashMapPolicyIjiE5applyINS0_12raw_hash_setIS2_NS_4HashIjEENS_7EqualToIjEENSt3__19allocatorINS9_4pairIKjiEEEEE11HashElementEJRKSD_EEEDTclsr5phmap4privE13DecomposePairclsr3stdE7declvalIT_EEspclsr3stdE7declvalIT0_EEEEOSJ_DpOSK_
Line
Count
Source
4315
521k
    apply(F&& f, Args&&... args) {
4316
521k
        return phmap::priv::DecomposePair(std::forward<F>(f),
4317
521k
                                                        std::forward<Args>(args)...);
4318
521k
    }
4319
4320
    static size_t space_used(const slot_type*) { return 0; }
4321
4322
12.4M
    static std::pair<const K, V>& element(slot_type* slot) { return slot->value; }
phmap::priv::FlatHashMapPolicy<unsigned int, int>::element(phmap::priv::map_slot_type<unsigned int, int>*)
Line
Count
Source
4322
12.4M
    static std::pair<const K, V>& element(slot_type* slot) { return slot->value; }
Unexecuted instantiation: phmap::priv::FlatHashMapPolicy<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >::element(phmap::priv::map_slot_type<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >*)
4323
4324
    static V& value(std::pair<const K, V>* kv) { return kv->second; }
4325
    static const V& value(const std::pair<const K, V>* kv) { return kv->second; }
4326
};
4327
4328
template <class Reference, class Policy>
4329
struct node_hash_policy {
4330
    static_assert(std::is_lvalue_reference<Reference>::value, "");
4331
4332
    using slot_type = typename std::remove_cv<
4333
        typename std::remove_reference<Reference>::type>::type*;
4334
4335
    template <class Alloc, class... Args>
4336
    static void construct(Alloc* alloc, slot_type* slot, Args&&... args) {
4337
        *slot = Policy::new_element(alloc, std::forward<Args>(args)...);
4338
    }
4339
4340
    template <class Alloc>
4341
    static void destroy(Alloc* alloc, slot_type* slot) {
4342
        Policy::delete_element(alloc, *slot);
4343
    }
4344
4345
    template <class Alloc>
4346
    static void transfer(Alloc*, slot_type* new_slot, slot_type* old_slot) {
4347
        *new_slot = *old_slot;
4348
    }
4349
4350
    static size_t space_used(const slot_type* slot) {
4351
        if (slot == nullptr) return Policy::element_space_used(nullptr);
4352
        return Policy::element_space_used(*slot);
4353
    }
4354
4355
    static Reference element(slot_type* slot) { return **slot; }
4356
4357
    template <class T, class P = Policy>
4358
    static auto value(T* elem) -> decltype(P::value(elem)) {
4359
        return P::value(elem);
4360
    }
4361
4362
    template <class... Ts, class P = Policy>
4363
    static auto apply(Ts&&... ts) -> decltype(P::apply(std::forward<Ts>(ts)...)) {
4364
        return P::apply(std::forward<Ts>(ts)...);
4365
    }
4366
};
4367
4368
// --------------------------------------------------------------------------
4369
// --------------------------------------------------------------------------
4370
template <class T>
4371
struct NodeHashSetPolicy
4372
    : phmap::priv::node_hash_policy<T&, NodeHashSetPolicy<T>> 
4373
{
4374
    using key_type = T;
4375
    using init_type = T;
4376
    using constant_iterators = std::true_type;
4377
    using is_flat = std::false_type;
4378
4379
    template <class Allocator, class... Args>
4380
        static T* new_element(Allocator* alloc, Args&&... args) {
4381
        using ValueAlloc =
4382
            typename phmap::allocator_traits<Allocator>::template rebind_alloc<T>;
4383
        ValueAlloc value_alloc(*alloc);
4384
        T* res = phmap::allocator_traits<ValueAlloc>::allocate(value_alloc, 1);
4385
        phmap::allocator_traits<ValueAlloc>::construct(value_alloc, res,
4386
                                                       std::forward<Args>(args)...);
4387
        return res;
4388
    }
4389
4390
    template <class Allocator>
4391
        static void delete_element(Allocator* alloc, T* elem) {
4392
        using ValueAlloc =
4393
            typename phmap::allocator_traits<Allocator>::template rebind_alloc<T>;
4394
        ValueAlloc value_alloc(*alloc);
4395
        phmap::allocator_traits<ValueAlloc>::destroy(value_alloc, elem);
4396
        phmap::allocator_traits<ValueAlloc>::deallocate(value_alloc, elem, 1);
4397
    }
4398
4399
    template <class F, class... Args>
4400
        static decltype(phmap::priv::DecomposeValue(
4401
                            std::declval<F>(), std::declval<Args>()...))
4402
        apply(F&& f, Args&&... args) {
4403
        return phmap::priv::DecomposeValue(
4404
            std::forward<F>(f), std::forward<Args>(args)...);
4405
    }
4406
4407
    static size_t element_space_used(const T*) { return sizeof(T); }
4408
};
4409
4410
// --------------------------------------------------------------------------
4411
// --------------------------------------------------------------------------
4412
template <class Key, class Value>
4413
class NodeHashMapPolicy
4414
    : public phmap::priv::node_hash_policy<
4415
          std::pair<const Key, Value>&, NodeHashMapPolicy<Key, Value>> 
4416
{
4417
    using value_type = std::pair<const Key, Value>;
4418
4419
public:
4420
    using key_type = Key;
4421
    using mapped_type = Value;
4422
    using init_type = std::pair</*non const*/ key_type, mapped_type>;
4423
    using is_flat = std::false_type;
4424
4425
    template <class Allocator, class... Args>
4426
        static value_type* new_element(Allocator* alloc, Args&&... args) {
4427
        using PairAlloc = typename phmap::allocator_traits<
4428
            Allocator>::template rebind_alloc<value_type>;
4429
        PairAlloc pair_alloc(*alloc);
4430
        value_type* res =
4431
            phmap::allocator_traits<PairAlloc>::allocate(pair_alloc, 1);
4432
        phmap::allocator_traits<PairAlloc>::construct(pair_alloc, res,
4433
                                                      std::forward<Args>(args)...);
4434
        return res;
4435
    }
4436
4437
    template <class Allocator>
4438
        static void delete_element(Allocator* alloc, value_type* pair) {
4439
        using PairAlloc = typename phmap::allocator_traits<
4440
            Allocator>::template rebind_alloc<value_type>;
4441
        PairAlloc pair_alloc(*alloc);
4442
        phmap::allocator_traits<PairAlloc>::destroy(pair_alloc, pair);
4443
        phmap::allocator_traits<PairAlloc>::deallocate(pair_alloc, pair, 1);
4444
    }
4445
4446
    template <class F, class... Args>
4447
        static decltype(phmap::priv::DecomposePair(
4448
                            std::declval<F>(), std::declval<Args>()...))
4449
        apply(F&& f, Args&&... args) {
4450
        return phmap::priv::DecomposePair(std::forward<F>(f),
4451
                                                        std::forward<Args>(args)...);
4452
    }
4453
4454
    static size_t element_space_used(const value_type*) {
4455
        return sizeof(value_type);
4456
    }
4457
4458
    static Value& value(value_type* elem) { return elem->second; }
4459
    static const Value& value(const value_type* elem) { return elem->second; }
4460
};
4461
4462
4463
// --------------------------------------------------------------------------
4464
//  hash_default
4465
// --------------------------------------------------------------------------
4466
4467
#if PHMAP_HAVE_STD_STRING_VIEW
4468
4469
// Supports heterogeneous lookup for basic_string<T>-like elements.
4470
template<class CharT> 
4471
struct StringHashEqT
4472
{
4473
    struct Hash 
4474
    {
4475
        using is_transparent = void;
4476
        
4477
        size_t operator()(std::basic_string_view<CharT> v) const {
4478
            std::string_view bv{
4479
                reinterpret_cast<const char*>(v.data()), v.size() * sizeof(CharT)};
4480
            return std::hash<std::string_view>()(bv);
4481
        }
4482
    };
4483
4484
    struct Eq {
4485
        using is_transparent = void;
4486
4487
        bool operator()(std::basic_string_view<CharT> lhs,
4488
                        std::basic_string_view<CharT> rhs) const {
4489
            return lhs == rhs;
4490
        }
4491
    };
4492
};
4493
4494
template <>
4495
struct HashEq<std::string> : StringHashEqT<char> {};
4496
4497
template <>
4498
struct HashEq<std::string_view> : StringHashEqT<char> {};
4499
4500
// char16_t
4501
template <>
4502
struct HashEq<std::u16string> : StringHashEqT<char16_t> {};
4503
4504
template <>
4505
struct HashEq<std::u16string_view> : StringHashEqT<char16_t> {};
4506
4507
// wchar_t
4508
template <>
4509
struct HashEq<std::wstring> : StringHashEqT<wchar_t> {};
4510
4511
template <>
4512
struct HashEq<std::wstring_view> : StringHashEqT<wchar_t> {};
4513
4514
#endif
4515
4516
// Supports heterogeneous lookup for pointers and smart pointers.
4517
// -------------------------------------------------------------
4518
template <class T>
4519
struct HashEq<T*> 
4520
{
4521
    struct Hash {
4522
        using is_transparent = void;
4523
        template <class U>
4524
        size_t operator()(const U& ptr) const {
4525
            // we want phmap::Hash<T*> and not phmap::Hash<const T*>
4526
            // so "struct std::hash<T*> " override works
4527
            return phmap::Hash<T*>{}((T*)(uintptr_t)HashEq::ToPtr(ptr));
4528
        }
4529
    };
4530
4531
    struct Eq {
4532
        using is_transparent = void;
4533
        template <class A, class B>
4534
        bool operator()(const A& a, const B& b) const {
4535
            return HashEq::ToPtr(a) == HashEq::ToPtr(b);
4536
        }
4537
    };
4538
4539
private:
4540
    static const T* ToPtr(const T* ptr) { return ptr; }
4541
4542
    template <class U, class D>
4543
    static const T* ToPtr(const std::unique_ptr<U, D>& ptr) {
4544
        return ptr.get();
4545
    }
4546
4547
    template <class U>
4548
    static const T* ToPtr(const std::shared_ptr<U>& ptr) {
4549
        return ptr.get();
4550
    }
4551
};
4552
4553
template <class T, class D>
4554
struct HashEq<std::unique_ptr<T, D>> : HashEq<T*> {};
4555
4556
template <class T>
4557
struct HashEq<std::shared_ptr<T>> : HashEq<T*> {};
4558
4559
namespace hashtable_debug_internal {
4560
4561
// --------------------------------------------------------------------------
4562
// --------------------------------------------------------------------------
4563
4564
template<typename, typename = void >
4565
struct has_member_type_raw_hash_set : std::false_type
4566
{};
4567
template<typename T>
4568
struct has_member_type_raw_hash_set<T, phmap::void_t<typename T::raw_hash_set>> : std::true_type
4569
{};
4570
4571
template <typename Set>
4572
struct HashtableDebugAccess<Set, typename std::enable_if<has_member_type_raw_hash_set<Set>::value>::type>
4573
{
4574
    using Traits = typename Set::PolicyTraits;
4575
    using Slot = typename Traits::slot_type;
4576
4577
    static size_t GetNumProbes(const Set& set,
4578
                               const typename Set::key_type& key) {
4579
        size_t num_probes = 0;
4580
        size_t hashval = set.hash(key); 
4581
        auto seq = set.probe(hashval);
4582
        while (true) {
4583
            priv::Group g{set.ctrl_ + seq.offset()};
4584
            for (uint32_t i : g.Match((h2_t)priv::H2(hashval))) {
4585
                if (Traits::apply(
4586
                        typename Set::template EqualElement<typename Set::key_type>{
4587
                            key, set.eq_ref()},
4588
                        Traits::element(set.slots_ + seq.offset((size_t)i))))
4589
                    return num_probes;
4590
                ++num_probes;
4591
            }
4592
            if (g.MatchEmpty()) return num_probes;
4593
            seq.next();
4594
            ++num_probes;
4595
        }
4596
    }
4597
4598
    static size_t AllocatedByteSize(const Set& c) {
4599
        size_t capacity = c.capacity_;
4600
        if (capacity == 0) return 0;
4601
        auto layout = Set::MakeLayout(capacity);
4602
        size_t m = layout.AllocSize();
4603
4604
        size_t per_slot = Traits::space_used(static_cast<const Slot*>(nullptr));
4605
        if (per_slot != ~size_t{}) {
4606
            m += per_slot * c.size();
4607
        } else {
4608
            for (size_t i = 0; i != capacity; ++i) {
4609
                if (priv::IsFull(c.ctrl_[i])) {
4610
                    m += Traits::space_used(c.slots_ + i);
4611
                }
4612
            }
4613
        }
4614
        return m;
4615
    }
4616
4617
    static size_t LowerBoundAllocatedByteSize(size_t size) {
4618
        size_t capacity = GrowthToLowerboundCapacity(size);
4619
        if (capacity == 0) return 0;
4620
        auto layout = Set::MakeLayout(NormalizeCapacity(capacity));
4621
        size_t m = layout.AllocSize();
4622
        size_t per_slot = Traits::space_used(static_cast<const Slot*>(nullptr));
4623
        if (per_slot != ~size_t{}) {
4624
            m += per_slot * size;
4625
        }
4626
        return m;
4627
    }
4628
};
4629
4630
4631
template<typename, typename = void >
4632
struct has_member_type_EmbeddedSet : std::false_type
4633
{};
4634
template<typename T>
4635
struct has_member_type_EmbeddedSet<T, phmap::void_t<typename T::EmbeddedSet>> : std::true_type
4636
{};
4637
4638
template <typename Set>
4639
struct HashtableDebugAccess<Set, typename std::enable_if<has_member_type_EmbeddedSet<Set>::value>::type> {
4640
    using Traits = typename Set::PolicyTraits;
4641
    using Slot = typename Traits::slot_type;
4642
    using EmbeddedSet = typename Set::EmbeddedSet;
4643
4644
    static size_t GetNumProbes(const Set& set, const typename Set::key_type& key) {
4645
        size_t hashval = set.hash(key);
4646
        auto& inner = set.sets_[set.subidx(hashval)];
4647
        auto& inner_set = inner.set_;
4648
        return HashtableDebugAccess<EmbeddedSet>::GetNumProbes(inner_set, key);
4649
    }
4650
};
4651
4652
}  // namespace hashtable_debug_internal
4653
}  // namespace priv
4654
4655
// -----------------------------------------------------------------------------
4656
// phmap::flat_hash_set
4657
// -----------------------------------------------------------------------------
4658
// An `phmap::flat_hash_set<T>` is an unordered associative container which has
4659
// been optimized for both speed and memory footprint in most common use cases.
4660
// Its interface is similar to that of `std::unordered_set<T>` with the
4661
// following notable differences:
4662
//
4663
// * Supports heterogeneous lookup, through `find()`, `operator[]()` and
4664
//   `insert()`, provided that the set is provided a compatible heterogeneous
4665
//   hashing function and equality operator.
4666
// * Invalidates any references and pointers to elements within the table after
4667
//   `rehash()`.
4668
// * Contains a `capacity()` member function indicating the number of element
4669
//   slots (open, deleted, and empty) within the hash set.
4670
// * Returns `void` from the `_erase(iterator)` overload.
4671
// -----------------------------------------------------------------------------
4672
template <class T, class Hash, class Eq, class Alloc> // default values in phmap_fwd_decl.h
4673
class flat_hash_set
4674
    : public phmap::priv::raw_hash_set<
4675
          phmap::priv::FlatHashSetPolicy<T>, Hash, Eq, Alloc> 
4676
{
4677
    using Base = typename flat_hash_set::raw_hash_set;
4678
4679
public:
4680
    flat_hash_set() {}
4681
#ifdef __INTEL_COMPILER
4682
    using Base::raw_hash_set;
4683
#else
4684
    using Base::Base;
4685
#endif
4686
    using Base::begin;
4687
    using Base::cbegin;
4688
    using Base::cend;
4689
    using Base::end;
4690
    using Base::capacity;
4691
    using Base::empty;
4692
    using Base::max_size;
4693
    using Base::size;
4694
    using Base::clear; // may shrink - To avoid shrinking `erase(begin(), end())`
4695
    using Base::erase;
4696
    using Base::insert;
4697
    using Base::emplace;
4698
    using Base::emplace_hint; 
4699
    using Base::extract;
4700
    using Base::merge;
4701
    using Base::swap;
4702
    using Base::rehash;
4703
    using Base::reserve;
4704
    using Base::contains;
4705
    using Base::count;
4706
    using Base::equal_range;
4707
    using Base::find;
4708
    using Base::bucket_count;
4709
    using Base::load_factor;
4710
    using Base::max_load_factor;
4711
    using Base::get_allocator;
4712
    using Base::hash_function;
4713
    using Base::hash;
4714
    using Base::key_eq;
4715
};
4716
4717
// -----------------------------------------------------------------------------
4718
// phmap::flat_hash_map
4719
// -----------------------------------------------------------------------------
4720
//
4721
// An `phmap::flat_hash_map<K, V>` is an unordered associative container which
4722
// has been optimized for both speed and memory footprint in most common use
4723
// cases. Its interface is similar to that of `std::unordered_map<K, V>` with
4724
// the following notable differences:
4725
//
4726
// * Supports heterogeneous lookup, through `find()`, `operator[]()` and
4727
//   `insert()`, provided that the map is provided a compatible heterogeneous
4728
//   hashing function and equality operator.
4729
// * Invalidates any references and pointers to elements within the table after
4730
//   `rehash()`.
4731
// * Contains a `capacity()` member function indicating the number of element
4732
//   slots (open, deleted, and empty) within the hash map.
4733
// * Returns `void` from the `_erase(iterator)` overload.
4734
// -----------------------------------------------------------------------------
4735
template <class K, class V, class Hash, class Eq, class Alloc> // default values in phmap_fwd_decl.h
4736
class flat_hash_map : public phmap::priv::raw_hash_map<
4737
                          phmap::priv::FlatHashMapPolicy<K, V>,
4738
                          Hash, Eq, Alloc> {
4739
    using Base = typename flat_hash_map::raw_hash_map;
4740
4741
public:
4742
1.51k
    flat_hash_map() {}
phmap::flat_hash_map<unsigned int, int, phmap::Hash<unsigned int>, phmap::EqualTo<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, int> > >::flat_hash_map()
Line
Count
Source
4742
1.01k
    flat_hash_map() {}
phmap::flat_hash_map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, phmap::priv::StringHashEqT<char>::Hash, phmap::priv::StringHashEqT<char>::Eq, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > > > >::flat_hash_map()
Line
Count
Source
4742
506
    flat_hash_map() {}
4743
#ifdef __INTEL_COMPILER
4744
    using Base::raw_hash_map;
4745
#else
4746
    using Base::Base;
4747
#endif
4748
    using Base::begin;
4749
    using Base::cbegin;
4750
    using Base::cend;
4751
    using Base::end;
4752
    using Base::capacity;
4753
    using Base::empty;
4754
    using Base::max_size;
4755
    using Base::size;
4756
    using Base::clear;
4757
    using Base::erase;
4758
    using Base::insert;
4759
    using Base::insert_or_assign;
4760
    using Base::emplace;
4761
    using Base::emplace_hint;
4762
    using Base::try_emplace;
4763
    using Base::extract;
4764
    using Base::merge;
4765
    using Base::swap;
4766
    using Base::rehash;
4767
    using Base::reserve;
4768
    using Base::at;
4769
    using Base::contains;
4770
    using Base::count;
4771
    using Base::equal_range;
4772
    using Base::find;
4773
    using Base::operator[];
4774
    using Base::bucket_count;
4775
    using Base::load_factor;
4776
    using Base::max_load_factor;
4777
    using Base::get_allocator;
4778
    using Base::hash_function;
4779
    using Base::hash;
4780
    using Base::key_eq;
4781
};
4782
4783
// -----------------------------------------------------------------------------
4784
// phmap::node_hash_set
4785
// -----------------------------------------------------------------------------
4786
// An `phmap::node_hash_set<T>` is an unordered associative container which
4787
// has been optimized for both speed and memory footprint in most common use
4788
// cases. Its interface is similar to that of `std::unordered_set<T>` with the
4789
// following notable differences:
4790
//
4791
// * Supports heterogeneous lookup, through `find()`, `operator[]()` and
4792
//   `insert()`, provided that the map is provided a compatible heterogeneous
4793
//   hashing function and equality operator.
4794
// * Contains a `capacity()` member function indicating the number of element
4795
//   slots (open, deleted, and empty) within the hash set.
4796
// * Returns `void` from the `_erase(iterator)` overload.
4797
// -----------------------------------------------------------------------------
4798
template <class T, class Hash, class Eq, class Alloc> // default values in phmap_fwd_decl.h
4799
class node_hash_set
4800
    : public phmap::priv::raw_hash_set<
4801
          phmap::priv::NodeHashSetPolicy<T>, Hash, Eq, Alloc> 
4802
{
4803
    using Base = typename node_hash_set::raw_hash_set;
4804
4805
public:
4806
    node_hash_set() {}
4807
#ifdef __INTEL_COMPILER
4808
    using Base::raw_hash_set;
4809
#else
4810
    using Base::Base;
4811
#endif
4812
    using Base::begin;
4813
    using Base::cbegin;
4814
    using Base::cend;
4815
    using Base::end;
4816
    using Base::capacity;
4817
    using Base::empty;
4818
    using Base::max_size;
4819
    using Base::size;
4820
    using Base::clear;
4821
    using Base::erase;
4822
    using Base::insert;
4823
    using Base::emplace;
4824
    using Base::emplace_hint;
4825
    using Base::emplace_with_hash;
4826
    using Base::emplace_hint_with_hash;
4827
    using Base::extract;
4828
    using Base::merge;
4829
    using Base::swap;
4830
    using Base::rehash;
4831
    using Base::reserve;
4832
    using Base::contains;
4833
    using Base::count;
4834
    using Base::equal_range;
4835
    using Base::find;
4836
    using Base::bucket_count;
4837
    using Base::load_factor;
4838
    using Base::max_load_factor;
4839
    using Base::get_allocator;
4840
    using Base::hash_function;
4841
    using Base::hash;
4842
    using Base::key_eq;
4843
    typename Base::hasher hash_funct() { return this->hash_function(); }
4844
    void resize(typename Base::size_type hint) { this->rehash(hint); }
4845
};
4846
4847
// -----------------------------------------------------------------------------
4848
// phmap::node_hash_map
4849
// -----------------------------------------------------------------------------
4850
//
4851
// An `phmap::node_hash_map<K, V>` is an unordered associative container which
4852
// has been optimized for both speed and memory footprint in most common use
4853
// cases. Its interface is similar to that of `std::unordered_map<K, V>` with
4854
// the following notable differences:
4855
//
4856
// * Supports heterogeneous lookup, through `find()`, `operator[]()` and
4857
//   `insert()`, provided that the map is provided a compatible heterogeneous
4858
//   hashing function and equality operator.
4859
// * Contains a `capacity()` member function indicating the number of element
4860
//   slots (open, deleted, and empty) within the hash map.
4861
// * Returns `void` from the `_erase(iterator)` overload.
4862
// -----------------------------------------------------------------------------
4863
template <class Key, class Value, class Hash, class Eq, class Alloc>  // default values in phmap_fwd_decl.h
4864
class node_hash_map
4865
    : public phmap::priv::raw_hash_map<
4866
          phmap::priv::NodeHashMapPolicy<Key, Value>, Hash, Eq,
4867
          Alloc> 
4868
{
4869
    using Base = typename node_hash_map::raw_hash_map;
4870
4871
public:
4872
    node_hash_map() {}
4873
#ifdef __INTEL_COMPILER
4874
    using Base::raw_hash_map;
4875
#else
4876
    using Base::Base;
4877
#endif
4878
    using Base::begin;
4879
    using Base::cbegin;
4880
    using Base::cend;
4881
    using Base::end;
4882
    using Base::capacity;
4883
    using Base::empty;
4884
    using Base::max_size;
4885
    using Base::size;
4886
    using Base::clear;
4887
    using Base::erase;
4888
    using Base::insert;
4889
    using Base::insert_or_assign;
4890
    using Base::emplace;
4891
    using Base::emplace_hint;
4892
    using Base::try_emplace;
4893
    using Base::extract;
4894
    using Base::merge;
4895
    using Base::swap;
4896
    using Base::rehash;
4897
    using Base::reserve;
4898
    using Base::at;
4899
    using Base::contains;
4900
    using Base::count;
4901
    using Base::equal_range;
4902
    using Base::find;
4903
    using Base::operator[];
4904
    using Base::bucket_count;
4905
    using Base::load_factor;
4906
    using Base::max_load_factor;
4907
    using Base::get_allocator;
4908
    using Base::hash_function;
4909
    using Base::hash;
4910
    using Base::key_eq;
4911
    typename Base::hasher hash_funct() { return this->hash_function(); }
4912
    void resize(typename Base::size_type hint) { this->rehash(hint); }
4913
};
4914
4915
// -----------------------------------------------------------------------------
4916
// phmap::parallel_flat_hash_set
4917
// -----------------------------------------------------------------------------
4918
template <class T, class Hash, class Eq, class Alloc, size_t N, class Mtx_> // default values in phmap_fwd_decl.h
4919
class parallel_flat_hash_set
4920
    : public phmap::priv::parallel_hash_set<
4921
         N, phmap::priv::raw_hash_set, Mtx_,
4922
         phmap::priv::FlatHashSetPolicy<T>, 
4923
         Hash, Eq, Alloc> 
4924
{
4925
    using Base = typename parallel_flat_hash_set::parallel_hash_set;
4926
4927
public:
4928
    parallel_flat_hash_set() {}
4929
#ifdef __INTEL_COMPILER
4930
    using Base::parallel_hash_set;
4931
#else
4932
    using Base::Base;
4933
#endif
4934
    using Base::hash;
4935
    using Base::subidx;
4936
    using Base::subcnt;
4937
    using Base::begin;
4938
    using Base::cbegin;
4939
    using Base::cend;
4940
    using Base::end;
4941
    using Base::capacity;
4942
    using Base::empty;
4943
    using Base::max_size;
4944
    using Base::size;
4945
    using Base::clear;
4946
    using Base::erase;
4947
    using Base::insert;
4948
    using Base::emplace;
4949
    using Base::emplace_hint;
4950
    using Base::emplace_with_hash;
4951
    using Base::emplace_hint_with_hash;
4952
    using Base::extract;
4953
    using Base::merge;
4954
    using Base::swap;
4955
    using Base::rehash;
4956
    using Base::reserve;
4957
    using Base::contains;
4958
    using Base::count;
4959
    using Base::equal_range;
4960
    using Base::find;
4961
    using Base::bucket_count;
4962
    using Base::load_factor;
4963
    using Base::max_load_factor;
4964
    using Base::get_allocator;
4965
    using Base::hash_function;
4966
    using Base::key_eq;
4967
};
4968
4969
// -----------------------------------------------------------------------------
4970
// phmap::parallel_flat_hash_map - default values in phmap_fwd_decl.h
4971
// -----------------------------------------------------------------------------
4972
template <class K, class V, class Hash, class Eq, class Alloc, size_t N, class Mtx_>
4973
class parallel_flat_hash_map : public phmap::priv::parallel_hash_map<
4974
                N, phmap::priv::raw_hash_set, Mtx_,
4975
                phmap::priv::FlatHashMapPolicy<K, V>,
4976
                Hash, Eq, Alloc> 
4977
{
4978
    using Base = typename parallel_flat_hash_map::parallel_hash_map;
4979
4980
public:
4981
    parallel_flat_hash_map() {}
4982
#ifdef __INTEL_COMPILER
4983
    using Base::parallel_hash_map;
4984
#else
4985
    using Base::Base;
4986
#endif
4987
    using Base::hash;
4988
    using Base::subidx;
4989
    using Base::subcnt;
4990
    using Base::begin;
4991
    using Base::cbegin;
4992
    using Base::cend;
4993
    using Base::end;
4994
    using Base::capacity;
4995
    using Base::empty;
4996
    using Base::max_size;
4997
    using Base::size;
4998
    using Base::clear;
4999
    using Base::erase;
5000
    using Base::insert;
5001
    using Base::insert_or_assign;
5002
    using Base::emplace;
5003
    using Base::emplace_hint;
5004
    using Base::try_emplace;
5005
    using Base::emplace_with_hash;
5006
    using Base::emplace_hint_with_hash;
5007
    using Base::try_emplace_with_hash;
5008
    using Base::extract;
5009
    using Base::merge;
5010
    using Base::swap;
5011
    using Base::rehash;
5012
    using Base::reserve;
5013
    using Base::at;
5014
    using Base::contains;
5015
    using Base::count;
5016
    using Base::equal_range;
5017
    using Base::find;
5018
    using Base::operator[];
5019
    using Base::bucket_count;
5020
    using Base::load_factor;
5021
    using Base::max_load_factor;
5022
    using Base::get_allocator;
5023
    using Base::hash_function;
5024
    using Base::key_eq;
5025
};
5026
5027
// -----------------------------------------------------------------------------
5028
// phmap::parallel_node_hash_set
5029
// -----------------------------------------------------------------------------
5030
template <class T, class Hash, class Eq, class Alloc, size_t N, class Mtx_>
5031
class parallel_node_hash_set
5032
    : public phmap::priv::parallel_hash_set<
5033
             N, phmap::priv::raw_hash_set, Mtx_,
5034
             phmap::priv::NodeHashSetPolicy<T>, Hash, Eq, Alloc> 
5035
{
5036
    using Base = typename parallel_node_hash_set::parallel_hash_set;
5037
5038
public:
5039
    parallel_node_hash_set() {}
5040
#ifdef __INTEL_COMPILER
5041
    using Base::parallel_hash_set;
5042
#else
5043
    using Base::Base;
5044
#endif
5045
    using Base::hash;
5046
    using Base::subidx;
5047
    using Base::subcnt;
5048
    using Base::begin;
5049
    using Base::cbegin;
5050
    using Base::cend;
5051
    using Base::end;
5052
    using Base::capacity;
5053
    using Base::empty;
5054
    using Base::max_size;
5055
    using Base::size;
5056
    using Base::clear;
5057
    using Base::erase;
5058
    using Base::insert;
5059
    using Base::emplace;
5060
    using Base::emplace_hint;
5061
    using Base::emplace_with_hash;
5062
    using Base::emplace_hint_with_hash;
5063
    using Base::extract;
5064
    using Base::merge;
5065
    using Base::swap;
5066
    using Base::rehash;
5067
    using Base::reserve;
5068
    using Base::contains;
5069
    using Base::count;
5070
    using Base::equal_range;
5071
    using Base::find;
5072
    using Base::bucket_count;
5073
    using Base::load_factor;
5074
    using Base::max_load_factor;
5075
    using Base::get_allocator;
5076
    using Base::hash_function;
5077
    using Base::key_eq;
5078
    typename Base::hasher hash_funct() { return this->hash_function(); }
5079
    void resize(typename Base::size_type hint) { this->rehash(hint); }
5080
};
5081
5082
// -----------------------------------------------------------------------------
5083
// phmap::parallel_node_hash_map
5084
// -----------------------------------------------------------------------------
5085
template <class Key, class Value, class Hash, class Eq, class Alloc, size_t N, class Mtx_>
5086
class parallel_node_hash_map
5087
    : public phmap::priv::parallel_hash_map<
5088
          N, phmap::priv::raw_hash_set, Mtx_,
5089
          phmap::priv::NodeHashMapPolicy<Key, Value>, Hash, Eq,
5090
          Alloc> 
5091
{
5092
    using Base = typename parallel_node_hash_map::parallel_hash_map;
5093
5094
public:
5095
    parallel_node_hash_map() {}
5096
#ifdef __INTEL_COMPILER
5097
    using Base::parallel_hash_map;
5098
#else
5099
    using Base::Base;
5100
#endif
5101
    using Base::hash;
5102
    using Base::subidx;
5103
    using Base::subcnt;
5104
    using Base::begin;
5105
    using Base::cbegin;
5106
    using Base::cend;
5107
    using Base::end;
5108
    using Base::capacity;
5109
    using Base::empty;
5110
    using Base::max_size;
5111
    using Base::size;
5112
    using Base::clear;
5113
    using Base::erase;
5114
    using Base::insert;
5115
    using Base::insert_or_assign;
5116
    using Base::emplace;
5117
    using Base::emplace_hint;
5118
    using Base::try_emplace;
5119
    using Base::emplace_with_hash;
5120
    using Base::emplace_hint_with_hash;
5121
    using Base::try_emplace_with_hash;
5122
    using Base::extract;
5123
    using Base::merge;
5124
    using Base::swap;
5125
    using Base::rehash;
5126
    using Base::reserve;
5127
    using Base::at;
5128
    using Base::contains;
5129
    using Base::count;
5130
    using Base::equal_range;
5131
    using Base::find;
5132
    using Base::operator[];
5133
    using Base::bucket_count;
5134
    using Base::load_factor;
5135
    using Base::max_load_factor;
5136
    using Base::get_allocator;
5137
    using Base::hash_function;
5138
    using Base::key_eq;
5139
    typename Base::hasher hash_funct() { return this->hash_function(); }
5140
    void resize(typename Base::size_type hint) { this->rehash(hint); }
5141
};
5142
5143
}  // namespace phmap
5144
5145
5146
namespace phmap {
5147
    namespace priv {
5148
        template <class C, class Pred> 
5149
        std::size_t erase_if(C &c, Pred pred) {
5150
            auto old_size = c.size();
5151
            for (auto i = c.begin(), last = c.end(); i != last; ) {
5152
                if (pred(*i)) {
5153
                    i = c.erase(i);
5154
                } else {
5155
                    ++i;
5156
                }
5157
            }
5158
            return old_size - c.size();
5159
        }
5160
    } // priv
5161
5162
    // ======== erase_if for phmap set containers ==================================
5163
    template <class T, class Hash, class Eq, class Alloc, class Pred> 
5164
    std::size_t erase_if(phmap::flat_hash_set<T, Hash, Eq, Alloc>& c, Pred pred) {
5165
        return phmap::priv::erase_if(c, std::move(pred));
5166
    }
5167
5168
    template <class T, class Hash, class Eq, class Alloc, class Pred> 
5169
    std::size_t erase_if(phmap::node_hash_set<T, Hash, Eq, Alloc>& c, Pred pred) {
5170
        return phmap::priv::erase_if(c, std::move(pred));
5171
    }
5172
5173
    template <class T, class Hash, class Eq, class Alloc, size_t N, class Mtx_, class Pred> 
5174
    std::size_t erase_if(phmap::parallel_flat_hash_set<T, Hash, Eq, Alloc, N, Mtx_>& c, Pred pred) {
5175
        return phmap::priv::erase_if(c, std::move(pred));
5176
    }
5177
5178
    template <class T, class Hash, class Eq, class Alloc, size_t N, class Mtx_, class Pred> 
5179
    std::size_t erase_if(phmap::parallel_node_hash_set<T, Hash, Eq, Alloc, N, Mtx_>& c, Pred pred) {
5180
        return phmap::priv::erase_if(c, std::move(pred));
5181
    }
5182
5183
    // ======== erase_if for phmap map containers ==================================
5184
    template <class K, class V, class Hash, class Eq, class Alloc, class Pred> 
5185
    std::size_t erase_if(phmap::flat_hash_map<K, V, Hash, Eq, Alloc>& c, Pred pred) {
5186
        return phmap::priv::erase_if(c, std::move(pred));
5187
    }
5188
5189
    template <class K, class V, class Hash, class Eq, class Alloc, class Pred> 
5190
    std::size_t erase_if(phmap::node_hash_map<K, V, Hash, Eq, Alloc>& c, Pred pred) {
5191
        return phmap::priv::erase_if(c, std::move(pred));
5192
    }
5193
5194
    template <class K, class V, class Hash, class Eq, class Alloc, size_t N, class Mtx_, class Pred> 
5195
    std::size_t erase_if(phmap::parallel_flat_hash_map<K, V, Hash, Eq, Alloc, N, Mtx_>& c, Pred pred) {
5196
        return phmap::priv::erase_if(c, std::move(pred));
5197
    }
5198
5199
    template <class K, class V, class Hash, class Eq, class Alloc, size_t N, class Mtx_, class Pred> 
5200
    std::size_t erase_if(phmap::parallel_node_hash_map<K, V, Hash, Eq, Alloc, N, Mtx_>& c, Pred pred) {
5201
        return phmap::priv::erase_if(c, std::move(pred));
5202
    }
5203
5204
} // phmap
5205
5206
#ifdef _MSC_VER
5207
     #pragma warning(pop)  
5208
#endif
5209
5210
5211
#endif // phmap_h_guard_