Coverage Report

Created: 2024-07-27 06:04

/src/parallel-hashmap/parallel_hashmap/phmap_base.h
Line
Count
Source (jump to first uncovered line)
1
#if !defined(phmap_base_h_guard_)
2
#define phmap_base_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
#include <algorithm>
38
#include <cassert>
39
#include <cstddef>
40
#include <initializer_list>
41
#include <iterator>
42
#include <string>
43
#include <type_traits>
44
#include <utility>
45
#include <functional>
46
#include <tuple>
47
#include <utility>
48
#include <memory>
49
#include <mutex> // for std::lock
50
51
#include "phmap_config.h"
52
53
#ifdef PHMAP_HAVE_SHARED_MUTEX
54
    #include <shared_mutex>  // after "phmap_config.h"
55
#endif
56
57
#ifdef _MSC_VER
58
    #pragma warning(push)
59
    #pragma warning(disable : 4514) // unreferenced inline function has been removed
60
    #pragma warning(disable : 4582) // constructor is not implicitly called
61
    #pragma warning(disable : 4625) // copy constructor was implicitly defined as deleted
62
    #pragma warning(disable : 4626) // assignment operator was implicitly defined as deleted
63
    #pragma warning(disable : 4710) // function not inlined
64
    #pragma warning(disable : 4711) //  selected for automatic inline expansion
65
    #pragma warning(disable : 4820) // '6' bytes padding added after data member
66
#endif  // _MSC_VER
67
68
namespace phmap {
69
70
template <class T> using Allocator = typename std::allocator<T>;
71
72
template<class T1, class T2> using Pair = typename std::pair<T1, T2>;
73
74
template <class T>
75
struct EqualTo
76
{
77
    inline bool operator()(const T& a, const T& b) const
78
10.4M
    {
79
10.4M
        return std::equal_to<T>()(a, b);
80
10.4M
    }
81
};
82
83
template <class T>
84
struct Less
85
{
86
    inline bool operator()(const T& a, const T& b) const
87
    {
88
        return std::less<T>()(a, b);
89
    }
90
};
91
92
namespace type_traits_internal {
93
94
template <typename... Ts>
95
struct VoidTImpl {
96
  using type = void;
97
};
98
99
// NOTE: The `is_detected` family of templates here differ from the library
100
// fundamentals specification in that for library fundamentals, `Op<Args...>` is
101
// evaluated as soon as the type `is_detected<Op, Args...>` undergoes
102
// substitution, regardless of whether or not the `::value` is accessed. That
103
// is inconsistent with all other standard traits and prevents lazy evaluation
104
// in larger contexts (such as if the `is_detected` check is a trailing argument
105
// of a `conjunction`. This implementation opts to instead be lazy in the same
106
// way that the standard traits are (this "defect" of the detection idiom
107
// specifications has been reported).
108
// ---------------------------------------------------------------------------
109
110
template <class Enabler, template <class...> class Op, class... Args>
111
struct is_detected_impl {
112
  using type = std::false_type;
113
};
114
115
template <template <class...> class Op, class... Args>
116
struct is_detected_impl<typename VoidTImpl<Op<Args...>>::type, Op, Args...> {
117
  using type = std::true_type;
118
};
119
120
template <template <class...> class Op, class... Args>
121
struct is_detected : is_detected_impl<void, Op, Args...>::type {};
122
123
template <class Enabler, class To, template <class...> class Op, class... Args>
124
struct is_detected_convertible_impl {
125
  using type = std::false_type;
126
};
127
128
template <class To, template <class...> class Op, class... Args>
129
struct is_detected_convertible_impl<
130
    typename std::enable_if<std::is_convertible<Op<Args...>, To>::value>::type,
131
    To, Op, Args...> {
132
  using type = std::true_type;
133
};
134
135
template <class To, template <class...> class Op, class... Args>
136
struct is_detected_convertible
137
    : is_detected_convertible_impl<void, To, Op, Args...>::type {};
138
139
template <typename T>
140
using IsCopyAssignableImpl =
141
    decltype(std::declval<T&>() = std::declval<const T&>());
142
143
template <typename T>
144
using IsMoveAssignableImpl = decltype(std::declval<T&>() = std::declval<T&&>());
145
146
}  // namespace type_traits_internal
147
148
template <typename T>
149
struct is_copy_assignable : type_traits_internal::is_detected<
150
                                type_traits_internal::IsCopyAssignableImpl, T> {
151
};
152
153
template <typename T>
154
struct is_move_assignable : type_traits_internal::is_detected<
155
                                type_traits_internal::IsMoveAssignableImpl, T> {
156
};
157
158
// ---------------------------------------------------------------------------
159
// void_t()
160
//
161
// Ignores the type of any its arguments and returns `void`. In general, this
162
// metafunction allows you to create a general case that maps to `void` while
163
// allowing specializations that map to specific types.
164
//
165
// This metafunction is designed to be a drop-in replacement for the C++17
166
// `std::void_t` metafunction.
167
//
168
// NOTE: `phmap::void_t` does not use the standard-specified implementation so
169
// that it can remain compatible with gcc < 5.1. This can introduce slightly
170
// different behavior, such as when ordering partial specializations.
171
// ---------------------------------------------------------------------------
172
template <typename... Ts>
173
using void_t = typename type_traits_internal::VoidTImpl<Ts...>::type;
174
175
// ---------------------------------------------------------------------------
176
// conjunction
177
//
178
// Performs a compile-time logical AND operation on the passed types (which
179
// must have  `::value` members convertible to `bool`. Short-circuits if it
180
// encounters any `false` members (and does not compare the `::value` members
181
// of any remaining arguments).
182
//
183
// This metafunction is designed to be a drop-in replacement for the C++17
184
// `std::conjunction` metafunction.
185
// ---------------------------------------------------------------------------
186
template <typename... Ts>
187
struct conjunction;
188
189
template <typename T, typename... Ts>
190
struct conjunction<T, Ts...>
191
    : std::conditional<T::value, conjunction<Ts...>, T>::type {};
192
193
template <typename T>
194
struct conjunction<T> : T {};
195
196
template <>
197
struct conjunction<> : std::true_type {};
198
199
// ---------------------------------------------------------------------------
200
// disjunction
201
//
202
// Performs a compile-time logical OR operation on the passed types (which
203
// must have  `::value` members convertible to `bool`. Short-circuits if it
204
// encounters any `true` members (and does not compare the `::value` members
205
// of any remaining arguments).
206
//
207
// This metafunction is designed to be a drop-in replacement for the C++17
208
// `std::disjunction` metafunction.
209
// ---------------------------------------------------------------------------
210
template <typename... Ts>
211
struct disjunction;
212
213
template <typename T, typename... Ts>
214
struct disjunction<T, Ts...> :
215
      std::conditional<T::value, T, disjunction<Ts...>>::type {};
216
217
template <typename T>
218
struct disjunction<T> : T {};
219
220
template <>
221
struct disjunction<> : std::false_type {};
222
223
template <typename T>
224
struct negation : std::integral_constant<bool, !T::value> {};
225
226
#if defined(__GNUC__) && __GNUC__ < 5 && !defined(__clang__) && !defined(_MSC_VER) && !defined(__INTEL_COMPILER)
227
    #define PHMAP_OLD_GCC 1
228
#else
229
    #define PHMAP_OLD_GCC 0
230
#endif
231
232
#if PHMAP_OLD_GCC
233
  template <typename T>
234
  struct is_trivially_copy_constructible
235
     : std::integral_constant<bool,
236
                              __has_trivial_copy(typename std::remove_reference<T>::type) &&
237
                              std::is_copy_constructible<T>::value &&
238
                              std::is_trivially_destructible<T>::value> {};
239
 
240
  template <typename T>
241
  struct is_trivially_copy_assignable :
242
     std::integral_constant<bool,
243
                            __has_trivial_assign(typename std::remove_reference<T>::type) &&
244
                            phmap::is_copy_assignable<T>::value> {};
245
246
  template <typename T>
247
  struct is_trivially_copyable :
248
     std::integral_constant<bool, __has_trivial_copy(typename std::remove_reference<T>::type)> {};
249
250
#else
251
  template <typename T> using is_trivially_copy_constructible = std::is_trivially_copy_constructible<T>;
252
  template <typename T> using is_trivially_copy_assignable = std::is_trivially_copy_assignable<T>;
253
  template <typename T> using is_trivially_copyable = std::is_trivially_copyable<T>;
254
#endif
255
256
// -----------------------------------------------------------------------------
257
// C++14 "_t" trait aliases
258
// -----------------------------------------------------------------------------
259
260
template <typename T>
261
using remove_cv_t = typename std::remove_cv<T>::type;
262
263
template <typename T>
264
using remove_const_t = typename std::remove_const<T>::type;
265
266
template <typename T>
267
using remove_volatile_t = typename std::remove_volatile<T>::type;
268
269
template <typename T>
270
using add_cv_t = typename std::add_cv<T>::type;
271
272
template <typename T>
273
using add_const_t = typename std::add_const<T>::type;
274
275
template <typename T>
276
using add_volatile_t = typename std::add_volatile<T>::type;
277
278
template <typename T>
279
using remove_reference_t = typename std::remove_reference<T>::type;
280
281
template <typename T>
282
using add_lvalue_reference_t = typename std::add_lvalue_reference<T>::type;
283
284
template <typename T>
285
using add_rvalue_reference_t = typename std::add_rvalue_reference<T>::type;
286
287
template <typename T>
288
using remove_pointer_t = typename std::remove_pointer<T>::type;
289
290
template <typename T>
291
using add_pointer_t = typename std::add_pointer<T>::type;
292
293
template <typename T>
294
using make_signed_t = typename std::make_signed<T>::type;
295
296
template <typename T>
297
using make_unsigned_t = typename std::make_unsigned<T>::type;
298
299
template <typename T>
300
using remove_extent_t = typename std::remove_extent<T>::type;
301
302
template <typename T>
303
using remove_all_extents_t = typename std::remove_all_extents<T>::type;
304
305
template<std::size_t Len, std::size_t Align>
306
struct aligned_storage {
307
    struct type {
308
        alignas(Align) unsigned char data[Len];
309
    };
310
};
311
312
template< std::size_t Len, std::size_t Align>
313
using aligned_storage_t = typename aligned_storage<Len, Align>::type;
314
315
template <typename T>
316
using decay_t = typename std::decay<T>::type;
317
318
template <bool B, typename T = void>
319
using enable_if_t = typename std::enable_if<B, T>::type;
320
321
template <bool B, typename T, typename F>
322
using conditional_t = typename std::conditional<B, T, F>::type;
323
324
325
template <typename... T>
326
using common_type_t = typename std::common_type<T...>::type;
327
328
template <typename T>
329
using underlying_type_t = typename std::underlying_type<T>::type;
330
331
template< class F, class... ArgTypes>
332
#if PHMAP_HAVE_CC17 && defined(__cpp_lib_result_of_sfinae)
333
    using invoke_result_t = typename std::invoke_result_t<F, ArgTypes...>;
334
#else
335
    using invoke_result_t = typename std::result_of<F(ArgTypes...)>::type;
336
#endif
337
338
namespace type_traits_internal {
339
340
// ----------------------------------------------------------------------
341
// In MSVC we can't probe std::hash or stdext::hash because it triggers a
342
// static_assert instead of failing substitution. Libc++ prior to 4.0
343
// also used a static_assert.
344
// ----------------------------------------------------------------------
345
#if defined(_MSC_VER) || (defined(_LIBCPP_VERSION) && \
346
                          _LIBCPP_VERSION < 4000 && _LIBCPP_STD_VER > 11)
347
    #define PHMAP_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ 0
348
#else
349
    #define PHMAP_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ 1
350
#endif
351
352
#if !PHMAP_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_
353
    template <typename Key, typename = size_t>
354
    struct IsHashable : std::true_type {};
355
#else   // PHMAP_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_
356
    template <typename Key, typename = void>
357
    struct IsHashable : std::false_type {};
358
359
    template <typename Key>
360
    struct IsHashable<Key,
361
        phmap::enable_if_t<std::is_convertible<
362
            decltype(std::declval<std::hash<Key>&>()(std::declval<Key const&>())),
363
            std::size_t>::value>> : std::true_type {};
364
#endif
365
366
struct AssertHashEnabledHelper 
367
{
368
private:
369
0
    static void Sink(...) {}
370
    struct NAT {};
371
372
    template <class Key>
373
    static auto GetReturnType(int)
374
        -> decltype(std::declval<std::hash<Key>>()(std::declval<Key const&>()));
375
    template <class Key>
376
    static NAT GetReturnType(...);
377
378
    template <class Key>
379
    static std::nullptr_t DoIt() {
380
        static_assert(IsHashable<Key>::value,
381
                      "std::hash<Key> does not provide a call operator");
382
        static_assert(
383
            std::is_default_constructible<std::hash<Key>>::value,
384
            "std::hash<Key> must be default constructible when it is enabled");
385
        static_assert(
386
            std::is_copy_constructible<std::hash<Key>>::value,
387
            "std::hash<Key> must be copy constructible when it is enabled");
388
        static_assert(phmap::is_copy_assignable<std::hash<Key>>::value,
389
                      "std::hash<Key> must be copy assignable when it is enabled");
390
        // is_destructible is unchecked as it's implied by each of the
391
        // is_constructible checks.
392
        using ReturnType = decltype(GetReturnType<Key>(0));
393
        static_assert(std::is_same<ReturnType, NAT>::value ||
394
                      std::is_same<ReturnType, size_t>::value,
395
                      "std::hash<Key> must return size_t");
396
        return nullptr;
397
    }
398
399
    template <class... Ts>
400
    friend void AssertHashEnabled();
401
};
402
403
template <class... Ts>
404
inline void AssertHashEnabled
405
() 
406
{
407
    using Helper = AssertHashEnabledHelper;
408
    Helper::Sink(Helper::DoIt<Ts>()...);
409
}
410
411
}  // namespace type_traits_internal
412
413
}  // namespace phmap
414
415
416
// -----------------------------------------------------------------------------
417
//          hash_policy_traits
418
// -----------------------------------------------------------------------------
419
namespace phmap {
420
namespace priv {
421
422
// Defines how slots are initialized/destroyed/moved.
423
template <class Policy, class = void>
424
struct hash_policy_traits 
425
{
426
private:
427
    struct ReturnKey 
428
    {
429
        // We return `Key` here.
430
        // When Key=T&, we forward the lvalue reference.
431
        // When Key=T, we return by value to avoid a dangling reference.
432
        // eg, for string_hash_map.
433
        template <class Key, class... Args>
434
        Key operator()(Key&& k, const Args&...) const {
435
            return std::forward<Key>(k);
436
        }
437
    };
438
439
    template <class P = Policy, class = void>
440
    struct ConstantIteratorsImpl : std::false_type {};
441
442
    template <class P>
443
    struct ConstantIteratorsImpl<P, phmap::void_t<typename P::constant_iterators>>
444
        : P::constant_iterators {};
445
446
public:
447
    // The actual object stored in the hash table.
448
    using slot_type  = typename Policy::slot_type;
449
450
    // The type of the keys stored in the hashtable.
451
    using key_type   = typename Policy::key_type;
452
453
    // The argument type for insertions into the hashtable. This is different
454
    // from value_type for increased performance. See initializer_list constructor
455
    // and insert() member functions for more details.
456
    using init_type  = typename Policy::init_type;
457
458
    using reference  = decltype(Policy::element(std::declval<slot_type*>()));
459
    using pointer    = typename std::remove_reference<reference>::type*;
460
    using value_type = typename std::remove_reference<reference>::type;
461
462
    // Policies can set this variable to tell raw_hash_set that all iterators
463
    // should be constant, even `iterator`. This is useful for set-like
464
    // containers.
465
    // Defaults to false if not provided by the policy.
466
    using constant_iterators = ConstantIteratorsImpl<>;
467
468
    // PRECONDITION: `slot` is UNINITIALIZED
469
    // POSTCONDITION: `slot` is INITIALIZED
470
    template <class Alloc, class... Args>
471
536k
    static void construct(Alloc* alloc, slot_type* slot, Args&&... args) {
472
536k
        Policy::construct(alloc, slot, std::forward<Args>(args)...);
473
536k
    }
474
475
    // PRECONDITION: `slot` is INITIALIZED
476
    // POSTCONDITION: `slot` is UNINITIALIZED
477
    template <class Alloc>
478
0
    static void destroy(Alloc* alloc, slot_type* slot) {
479
0
        Policy::destroy(alloc, slot);
480
0
    }
481
482
    // Transfers the `old_slot` to `new_slot`. Any memory allocated by the
483
    // allocator inside `old_slot` to `new_slot` can be transferred.
484
    //
485
    // OPTIONAL: defaults to:
486
    //
487
    //     clone(new_slot, std::move(*old_slot));
488
    //     destroy(old_slot);
489
    //
490
    // PRECONDITION: `new_slot` is UNINITIALIZED and `old_slot` is INITIALIZED
491
    // POSTCONDITION: `new_slot` is INITIALIZED and `old_slot` is
492
    //                UNINITIALIZED
493
    template <class Alloc>
494
958k
    static void transfer(Alloc* alloc, slot_type* new_slot, slot_type* old_slot) {
495
958k
        transfer_impl(alloc, new_slot, old_slot, 0);
496
958k
    }
497
498
    // PRECONDITION: `slot` is INITIALIZED
499
    // POSTCONDITION: `slot` is INITIALIZED
500
    template <class P = Policy>
501
12.4M
    static auto element(slot_type* slot) -> decltype(P::element(slot)) {
502
12.4M
        return P::element(slot);
503
12.4M
    }
decltype (phmap::priv::FlatHashMapPolicy<unsigned int, int>::element({parm#1})) phmap::priv::hash_policy_traits<phmap::priv::FlatHashMapPolicy<unsigned int, int>, void>::element<phmap::priv::FlatHashMapPolicy<unsigned int, int> >(phmap::priv::map_slot_type<unsigned int, int>*)
Line
Count
Source
501
12.4M
    static auto element(slot_type* slot) -> decltype(P::element(slot)) {
502
12.4M
        return P::element(slot);
503
12.4M
    }
Unexecuted instantiation: decltype (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({parm#1})) phmap::priv::hash_policy_traits<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> > >, void>::element<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::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> > >*)
504
505
    // Returns the amount of memory owned by `slot`, exclusive of `sizeof(*slot)`.
506
    //
507
    // If `slot` is nullptr, returns the constant amount of memory owned by any
508
    // full slot or -1 if slots own variable amounts of memory.
509
    //
510
    // PRECONDITION: `slot` is INITIALIZED or nullptr
511
    template <class P = Policy>
512
    static size_t space_used(const slot_type* slot) {
513
        return P::space_used(slot);
514
    }
515
516
    // Provides generalized access to the key for elements, both for elements in
517
    // the table and for elements that have not yet been inserted (or even
518
    // constructed).  We would like an API that allows us to say: `key(args...)`
519
    // but we cannot do that for all cases, so we use this more general API that
520
    // can be used for many things, including the following:
521
    //
522
    //   - Given an element in a table, get its key.
523
    //   - Given an element initializer, get its key.
524
    //   - Given `emplace()` arguments, get the element key.
525
    //
526
    // Implementations of this must adhere to a very strict technical
527
    // specification around aliasing and consuming arguments:
528
    //
529
    // Let `value_type` be the result type of `element()` without ref- and
530
    // cv-qualifiers. The first argument is a functor, the rest are constructor
531
    // arguments for `value_type`. Returns `std::forward<F>(f)(k, xs...)`, where
532
    // `k` is the element key, and `xs...` are the new constructor arguments for
533
    // `value_type`. It's allowed for `k` to alias `xs...`, and for both to alias
534
    // `ts...`. The key won't be touched once `xs...` are used to construct an
535
    // element; `ts...` won't be touched at all, which allows `apply()` to consume
536
    // any rvalues among them.
537
    //
538
    // If `value_type` is constructible from `Ts&&...`, `Policy::apply()` must not
539
    // trigger a hard compile error unless it originates from `f`. In other words,
540
    // `Policy::apply()` must be SFINAE-friendly. If `value_type` is not
541
    // constructible from `Ts&&...`, either SFINAE or a hard compile error is OK.
542
    //
543
    // If `Ts...` is `[cv] value_type[&]` or `[cv] init_type[&]`,
544
    // `Policy::apply()` must work. A compile error is not allowed, SFINAE or not.
545
    template <class F, class... Ts, class P = Policy>
546
    static auto apply(F&& f, Ts&&... ts)
547
19.9M
        -> decltype(P::apply(std::forward<F>(f), std::forward<Ts>(ts)...)) {
548
19.9M
        return P::apply(std::forward<F>(f), std::forward<Ts>(ts)...);
549
19.9M
    }
_ZN5phmap4priv18hash_policy_traitsINS0_17FlatHashMapPolicyIjiEEvE5applyINS0_12raw_hash_setIS3_NS_4HashIjEENS_7EqualToIjEENSt3__19allocatorINSB_4pairIKjiEEEEE19EmplaceDecomposableEJSF_ES3_EEDTclsrT1_5applyclsr3stdE7forwardIT_Efp_Espclsr3stdE7forwardIT0_Efp0_EEEOSK_DpOSL_
Line
Count
Source
547
8.01M
        -> decltype(P::apply(std::forward<F>(f), std::forward<Ts>(ts)...)) {
548
8.01M
        return P::apply(std::forward<F>(f), std::forward<Ts>(ts)...);
549
8.01M
    }
_ZN5phmap4priv18hash_policy_traitsINS0_17FlatHashMapPolicyIjiEEvE5applyINS0_12raw_hash_setIS3_NS_4HashIjEENS_7EqualToIjEENSt3__19allocatorINSB_4pairIKjiEEEEE12EqualElementIjEEJRSF_ES3_EEDTclsrT1_5applyclsr3stdE7forwardIT_Efp_Espclsr3stdE7forwardIT0_Efp0_EEEOSM_DpOSN_
Line
Count
Source
547
10.4M
        -> decltype(P::apply(std::forward<F>(f), std::forward<Ts>(ts)...)) {
548
10.4M
        return P::apply(std::forward<F>(f), std::forward<Ts>(ts)...);
549
10.4M
    }
_ZN5phmap4priv18hash_policy_traitsINS0_17FlatHashMapPolicyIjiEEvE5applyINS0_12raw_hash_setIS3_NS_4HashIjEENS_7EqualToIjEENSt3__19allocatorINSB_4pairIKjiEEEEE11HashElementEJRSF_ES3_EEDTclsrT1_5applyclsr3stdE7forwardIT_Efp_Espclsr3stdE7forwardIT0_Efp0_EEEOSL_DpOSM_
Line
Count
Source
547
958k
        -> decltype(P::apply(std::forward<F>(f), std::forward<Ts>(ts)...)) {
548
958k
        return P::apply(std::forward<F>(f), std::forward<Ts>(ts)...);
549
958k
    }
_ZN5phmap4priv18hash_policy_traitsINS0_17FlatHashMapPolicyIjiEEvE5applyINS0_12raw_hash_setIS3_NS_4HashIjEENS_7EqualToIjEENSt3__19allocatorINSB_4pairIKjiEEEEE11HashElementEJRKSF_ES3_EEDTclsrT1_5applyclsr3stdE7forwardIT_Efp_Espclsr3stdE7forwardIT0_Efp0_EEEOSM_DpOSN_
Line
Count
Source
547
521k
        -> decltype(P::apply(std::forward<F>(f), std::forward<Ts>(ts)...)) {
548
521k
        return P::apply(std::forward<F>(f), std::forward<Ts>(ts)...);
549
521k
    }
550
551
    // Returns the "key" portion of the slot.
552
    // Used for node handle manipulation.
553
    template <class P = Policy>
554
    static auto key(slot_type* slot)
555
        -> decltype(P::apply(ReturnKey(), element(slot))) {
556
        return P::apply(ReturnKey(), element(slot));
557
    }
558
559
    // Returns the "value" (as opposed to the "key") portion of the element. Used
560
    // by maps to implement `operator[]`, `at()` and `insert_or_assign()`.
561
    template <class T, class P = Policy>
562
    static auto value(T* elem) -> decltype(P::value(elem)) {
563
        return P::value(elem);
564
    }
565
566
private:
567
568
    // Use auto -> decltype as an enabler.
569
    template <class Alloc, class P = Policy>
570
    static auto transfer_impl(Alloc* alloc, slot_type* new_slot,
571
                              slot_type* old_slot, int)
572
958k
        -> decltype((void)P::transfer(alloc, new_slot, old_slot)) {
573
958k
        P::transfer(alloc, new_slot, old_slot);
574
958k
    }
575
576
    template <class Alloc>
577
    static void transfer_impl(Alloc* alloc, slot_type* new_slot,
578
                              slot_type* old_slot, char) {
579
        construct(alloc, new_slot, std::move(element(old_slot)));
580
        destroy(alloc, old_slot);
581
    }
582
};
583
584
}  // namespace priv
585
}  // namespace phmap
586
587
// -----------------------------------------------------------------------------
588
// file utility.h
589
// -----------------------------------------------------------------------------
590
591
// --------- identity.h
592
namespace phmap {
593
namespace internal {
594
595
template <typename T>
596
struct identity {
597
    typedef T type;
598
};
599
600
template <typename T>
601
using identity_t = typename identity<T>::type;
602
603
}  // namespace internal
604
}  // namespace phmap
605
606
607
// --------- inline_variable.h
608
609
#ifdef __cpp_inline_variables
610
611
#if defined(__clang__)
612
    #define PHMAP_INTERNAL_EXTERN_DECL(type, name) \
613
      extern const ::phmap::internal::identity_t<type> name;
614
#else  // Otherwise, just define the macro to do nothing.
615
    #define PHMAP_INTERNAL_EXTERN_DECL(type, name)
616
#endif  // defined(__clang__)
617
618
// See above comment at top of file for details.
619
#define PHMAP_INTERNAL_INLINE_CONSTEXPR(type, name, init) \
620
  PHMAP_INTERNAL_EXTERN_DECL(type, name)                  \
621
  inline constexpr ::phmap::internal::identity_t<type> name = init
622
623
#else
624
625
// See above comment at top of file for details.
626
//
627
// Note:
628
//   identity_t is used here so that the const and name are in the
629
//   appropriate place for pointer types, reference types, function pointer
630
//   types, etc..
631
#define PHMAP_INTERNAL_INLINE_CONSTEXPR(var_type, name, init)                  \
632
  template <class /*PhmapInternalDummy*/ = void>                               \
633
  struct PhmapInternalInlineVariableHolder##name {                             \
634
    static constexpr ::phmap::internal::identity_t<var_type> kInstance = init; \
635
  };                                                                          \
636
                                                                              \
637
  template <class PhmapInternalDummy>                                          \
638
  constexpr ::phmap::internal::identity_t<var_type>                            \
639
      PhmapInternalInlineVariableHolder##name<PhmapInternalDummy>::kInstance;   \
640
                                                                              \
641
  static constexpr const ::phmap::internal::identity_t<var_type>&              \
642
      name = /* NOLINT */                                                     \
643
      PhmapInternalInlineVariableHolder##name<>::kInstance;                    \
644
  static_assert(sizeof(void (*)(decltype(name))) != 0,                        \
645
                "Silence unused variable warnings.")
646
647
#endif  // __cpp_inline_variables
648
649
// ----------- throw_delegate
650
651
namespace phmap {
652
namespace base_internal {
653
654
namespace {
655
656
#ifdef PHMAP_HAVE_EXCEPTIONS
657
  #define PHMAP_THROW_IMPL_MSG(e, message) throw e(message)
658
  #define PHMAP_THROW_IMPL(e) throw e()
659
#else
660
  #define PHMAP_THROW_IMPL_MSG(e, message) do { (void)(message); std::abort(); } while(0)
661
  #define PHMAP_THROW_IMPL(e) std::abort()
662
#endif
663
}  // namespace
664
665
0
static inline void ThrowStdLogicError(const std::string& what_arg) {
666
0
  PHMAP_THROW_IMPL_MSG(std::logic_error, what_arg);
667
0
}
668
0
static inline void ThrowStdLogicError(const char* what_arg) {
669
0
  PHMAP_THROW_IMPL_MSG(std::logic_error, what_arg);
670
0
}
671
0
static inline void ThrowStdInvalidArgument(const std::string& what_arg) {
672
0
  PHMAP_THROW_IMPL_MSG(std::invalid_argument, what_arg);
673
0
}
674
0
static inline void ThrowStdInvalidArgument(const char* what_arg) {
675
0
  PHMAP_THROW_IMPL_MSG(std::invalid_argument, what_arg);
676
0
}
677
678
0
static inline void ThrowStdDomainError(const std::string& what_arg) {
679
0
  PHMAP_THROW_IMPL_MSG(std::domain_error, what_arg);
680
0
}
681
0
static inline void ThrowStdDomainError(const char* what_arg) {
682
0
  PHMAP_THROW_IMPL_MSG(std::domain_error, what_arg);
683
0
}
684
685
0
static inline void ThrowStdLengthError(const std::string& what_arg) {
686
0
  PHMAP_THROW_IMPL_MSG(std::length_error, what_arg);
687
0
}
688
0
static inline void ThrowStdLengthError(const char* what_arg) {
689
0
  PHMAP_THROW_IMPL_MSG(std::length_error, what_arg);
690
0
}
691
692
0
static inline void ThrowStdOutOfRange(const std::string& what_arg) {
693
0
  PHMAP_THROW_IMPL_MSG(std::out_of_range, what_arg);
694
0
}
695
0
static inline void ThrowStdOutOfRange(const char* what_arg) {
696
0
  PHMAP_THROW_IMPL_MSG(std::out_of_range, what_arg);
697
0
}
698
699
0
static inline void ThrowStdRuntimeError(const std::string& what_arg) {
700
0
  PHMAP_THROW_IMPL_MSG(std::runtime_error, what_arg);
701
0
}
702
0
static inline void ThrowStdRuntimeError(const char* what_arg) {
703
0
  PHMAP_THROW_IMPL_MSG(std::runtime_error, what_arg);
704
0
}
705
706
0
static inline void ThrowStdRangeError(const std::string& what_arg) {
707
0
  PHMAP_THROW_IMPL_MSG(std::range_error, what_arg);
708
0
}
709
0
static inline void ThrowStdRangeError(const char* what_arg) {
710
0
  PHMAP_THROW_IMPL_MSG(std::range_error, what_arg);
711
0
}
712
713
0
static inline void ThrowStdOverflowError(const std::string& what_arg) {
714
0
  PHMAP_THROW_IMPL_MSG(std::overflow_error, what_arg);
715
0
}
716
    
717
0
static inline void ThrowStdOverflowError(const char* what_arg) {
718
0
  PHMAP_THROW_IMPL_MSG(std::overflow_error, what_arg);
719
0
}
720
721
0
static inline void ThrowStdUnderflowError(const std::string& what_arg) {
722
0
  PHMAP_THROW_IMPL_MSG(std::underflow_error, what_arg);
723
0
}
724
    
725
0
static inline void ThrowStdUnderflowError(const char* what_arg) {
726
0
  PHMAP_THROW_IMPL_MSG(std::underflow_error, what_arg);
727
0
}
728
    
729
0
static inline void ThrowStdBadFunctionCall() {
730
0
  PHMAP_THROW_IMPL(std::bad_function_call);
731
0
}
732
    
733
0
static inline void ThrowStdBadAlloc() {
734
0
  PHMAP_THROW_IMPL(std::bad_alloc);
735
0
}
736
737
}  // namespace base_internal
738
}  // namespace phmap
739
740
// ----------- invoke.h
741
742
namespace phmap {
743
namespace base_internal {
744
745
template <typename Derived>
746
struct StrippedAccept 
747
{
748
    template <typename... Args>
749
    struct Accept : Derived::template AcceptImpl<typename std::remove_cv<
750
                                                     typename std::remove_reference<Args>::type>::type...> {};
751
};
752
753
// (t1.*f)(t2, ..., tN) when f is a pointer to a member function of a class T
754
// and t1 is an object of type T or a reference to an object of type T or a
755
// reference to an object of a type derived from T.
756
struct MemFunAndRef : StrippedAccept<MemFunAndRef> 
757
{
758
    template <typename... Args>
759
    struct AcceptImpl : std::false_type {};
760
761
    template <typename R, typename C, typename... Params, typename Obj,
762
              typename... Args>
763
    struct AcceptImpl<R (C::*)(Params...), Obj, Args...>
764
        : std::is_base_of<C, Obj> {};
765
766
    template <typename R, typename C, typename... Params, typename Obj,
767
              typename... Args>
768
    struct AcceptImpl<R (C::*)(Params...) const, Obj, Args...>
769
        : std::is_base_of<C, Obj> {};
770
771
    template <typename MemFun, typename Obj, typename... Args>
772
    static decltype((std::declval<Obj>().*
773
                     std::declval<MemFun>())(std::declval<Args>()...))
774
    Invoke(MemFun&& mem_fun, Obj&& obj, Args&&... args) {
775
        return (std::forward<Obj>(obj).*
776
                std::forward<MemFun>(mem_fun))(std::forward<Args>(args)...);
777
    }
778
};
779
780
// ((*t1).*f)(t2, ..., tN) when f is a pointer to a member function of a
781
// class T and t1 is not one of the types described in the previous item.
782
struct MemFunAndPtr : StrippedAccept<MemFunAndPtr> 
783
{
784
    template <typename... Args>
785
    struct AcceptImpl : std::false_type {};
786
787
    template <typename R, typename C, typename... Params, typename Ptr,
788
              typename... Args>
789
    struct AcceptImpl<R (C::*)(Params...), Ptr, Args...>
790
        : std::integral_constant<bool, !std::is_base_of<C, Ptr>::value> {};
791
792
    template <typename R, typename C, typename... Params, typename Ptr,
793
              typename... Args>
794
    struct AcceptImpl<R (C::*)(Params...) const, Ptr, Args...>
795
        : std::integral_constant<bool, !std::is_base_of<C, Ptr>::value> {};
796
797
    template <typename MemFun, typename Ptr, typename... Args>
798
    static decltype(((*std::declval<Ptr>()).*
799
                     std::declval<MemFun>())(std::declval<Args>()...))
800
    Invoke(MemFun&& mem_fun, Ptr&& ptr, Args&&... args) {
801
        return ((*std::forward<Ptr>(ptr)).*
802
                std::forward<MemFun>(mem_fun))(std::forward<Args>(args)...);
803
    }
804
};
805
806
// t1.*f when N == 1 and f is a pointer to member data of a class T and t1 is
807
// an object of type T or a reference to an object of type T or a reference
808
// to an object of a type derived from T.
809
struct DataMemAndRef : StrippedAccept<DataMemAndRef> 
810
{
811
    template <typename... Args>
812
    struct AcceptImpl : std::false_type {};
813
814
    template <typename R, typename C, typename Obj>
815
    struct AcceptImpl<R C::*, Obj> : std::is_base_of<C, Obj> {};
816
817
    template <typename DataMem, typename Ref>
818
    static decltype(std::declval<Ref>().*std::declval<DataMem>()) Invoke(
819
        DataMem&& data_mem, Ref&& ref) {
820
        return std::forward<Ref>(ref).*std::forward<DataMem>(data_mem);
821
    }
822
};
823
824
// (*t1).*f when N == 1 and f is a pointer to member data of a class T and t1
825
// is not one of the types described in the previous item.
826
struct DataMemAndPtr : StrippedAccept<DataMemAndPtr> 
827
{
828
    template <typename... Args>
829
    struct AcceptImpl : std::false_type {};
830
831
    template <typename R, typename C, typename Ptr>
832
    struct AcceptImpl<R C::*, Ptr>
833
        : std::integral_constant<bool, !std::is_base_of<C, Ptr>::value> {};
834
835
    template <typename DataMem, typename Ptr>
836
    static decltype((*std::declval<Ptr>()).*std::declval<DataMem>()) Invoke(
837
        DataMem&& data_mem, Ptr&& ptr) {
838
        return (*std::forward<Ptr>(ptr)).*std::forward<DataMem>(data_mem);
839
    }
840
};
841
842
// f(t1, t2, ..., tN) in all other cases.
843
struct Callable
844
{
845
    // Callable doesn't have Accept because it's the last clause that gets picked
846
    // when none of the previous clauses are applicable.
847
    template <typename F, typename... Args>
848
    static decltype(std::declval<F>()(std::declval<Args>()...)) Invoke(
849
        F&& f, Args&&... args) {
850
        return std::forward<F>(f)(std::forward<Args>(args)...);
851
    }
852
};
853
854
// Resolves to the first matching clause.
855
template <typename... Args>
856
struct Invoker 
857
{
858
    typedef typename std::conditional<
859
        MemFunAndRef::Accept<Args...>::value, MemFunAndRef,
860
        typename std::conditional<
861
            MemFunAndPtr::Accept<Args...>::value, MemFunAndPtr,
862
            typename std::conditional<
863
                DataMemAndRef::Accept<Args...>::value, DataMemAndRef,
864
                typename std::conditional<DataMemAndPtr::Accept<Args...>::value,
865
                                          DataMemAndPtr, Callable>::type>::type>::
866
        type>::type type;
867
};
868
869
// The result type of Invoke<F, Args...>.
870
template <typename F, typename... Args>
871
using InvokeT = decltype(Invoker<F, Args...>::type::Invoke(
872
    std::declval<F>(), std::declval<Args>()...));
873
874
// Invoke(f, args...) is an implementation of INVOKE(f, args...) from section
875
// [func.require] of the C++ standard.
876
template <typename F, typename... Args>
877
InvokeT<F, Args...> Invoke(F&& f, Args&&... args) {
878
  return Invoker<F, Args...>::type::Invoke(std::forward<F>(f),
879
                                           std::forward<Args>(args)...);
880
}
881
}  // namespace base_internal
882
}  // namespace phmap
883
884
885
// ----------- utility.h
886
887
namespace phmap {
888
889
// integer_sequence
890
//
891
// Class template representing a compile-time integer sequence. An instantiation
892
// of `integer_sequence<T, Ints...>` has a sequence of integers encoded in its
893
// type through its template arguments (which is a common need when
894
// working with C++11 variadic templates). `phmap::integer_sequence` is designed
895
// to be a drop-in replacement for C++14's `std::integer_sequence`.
896
//
897
// Example:
898
//
899
//   template< class T, T... Ints >
900
//   void user_function(integer_sequence<T, Ints...>);
901
//
902
//   int main()
903
//   {
904
//     // user_function's `T` will be deduced to `int` and `Ints...`
905
//     // will be deduced to `0, 1, 2, 3, 4`.
906
//     user_function(make_integer_sequence<int, 5>());
907
//   }
908
template <typename T, T... Ints>
909
struct integer_sequence 
910
{
911
    using value_type = T;
912
    static constexpr size_t size() noexcept { return sizeof...(Ints); }
913
};
914
915
// index_sequence
916
//
917
// A helper template for an `integer_sequence` of `size_t`,
918
// `phmap::index_sequence` is designed to be a drop-in replacement for C++14's
919
// `std::index_sequence`.
920
template <size_t... Ints>
921
using index_sequence = integer_sequence<size_t, Ints...>;
922
923
namespace utility_internal {
924
925
template <typename Seq, size_t SeqSize, size_t Rem>
926
struct Extend;
927
928
// Note that SeqSize == sizeof...(Ints). It's passed explicitly for efficiency.
929
template <typename T, T... Ints, size_t SeqSize>
930
struct Extend<integer_sequence<T, Ints...>, SeqSize, 0> {
931
  using type = integer_sequence<T, Ints..., (Ints + SeqSize)...>;
932
};
933
934
template <typename T, T... Ints, size_t SeqSize>
935
struct Extend<integer_sequence<T, Ints...>, SeqSize, 1> {
936
  using type = integer_sequence<T, Ints..., (Ints + SeqSize)..., 2 * SeqSize>;
937
};
938
939
// Recursion helper for 'make_integer_sequence<T, N>'.
940
// 'Gen<T, N>::type' is an alias for 'integer_sequence<T, 0, 1, ... N-1>'.
941
template <typename T, size_t N>
942
struct Gen {
943
  using type =
944
      typename Extend<typename Gen<T, N / 2>::type, N / 2, N % 2>::type;
945
};
946
947
template <typename T>
948
struct Gen<T, 0> {
949
  using type = integer_sequence<T>;
950
};
951
952
}  // namespace utility_internal
953
954
// Compile-time sequences of integers
955
956
// make_integer_sequence
957
//
958
// This template alias is equivalent to
959
// `integer_sequence<int, 0, 1, ..., N-1>`, and is designed to be a drop-in
960
// replacement for C++14's `std::make_integer_sequence`.
961
template <typename T, T N>
962
using make_integer_sequence = typename utility_internal::Gen<T, N>::type;
963
964
// make_index_sequence
965
//
966
// This template alias is equivalent to `index_sequence<0, 1, ..., N-1>`,
967
// and is designed to be a drop-in replacement for C++14's
968
// `std::make_index_sequence`.
969
template <size_t N>
970
using make_index_sequence = make_integer_sequence<size_t, N>;
971
972
// index_sequence_for
973
//
974
// Converts a typename pack into an index sequence of the same length, and
975
// is designed to be a drop-in replacement for C++14's
976
// `std::index_sequence_for()`
977
template <typename... Ts>
978
using index_sequence_for = make_index_sequence<sizeof...(Ts)>;
979
980
// Tag types
981
982
#ifdef PHMAP_HAVE_STD_OPTIONAL
983
984
using std::in_place_t;
985
using std::in_place;
986
987
#else  // PHMAP_HAVE_STD_OPTIONAL
988
989
// in_place_t
990
//
991
// Tag type used to specify in-place construction, such as with
992
// `phmap::optional`, designed to be a drop-in replacement for C++17's
993
// `std::in_place_t`.
994
struct in_place_t {};
995
996
PHMAP_INTERNAL_INLINE_CONSTEXPR(in_place_t, in_place, {});
997
998
#endif  // PHMAP_HAVE_STD_OPTIONAL
999
1000
#if defined(PHMAP_HAVE_STD_ANY) || defined(PHMAP_HAVE_STD_VARIANT)
1001
using std::in_place_type_t;
1002
#else
1003
1004
// in_place_type_t
1005
//
1006
// Tag type used for in-place construction when the type to construct needs to
1007
// be specified, such as with `phmap::any`, designed to be a drop-in replacement
1008
// for C++17's `std::in_place_type_t`.
1009
template <typename T>
1010
struct in_place_type_t {};
1011
#endif  // PHMAP_HAVE_STD_ANY || PHMAP_HAVE_STD_VARIANT
1012
1013
#ifdef PHMAP_HAVE_STD_VARIANT
1014
using std::in_place_index_t;
1015
#else
1016
1017
// in_place_index_t
1018
//
1019
// Tag type used for in-place construction when the type to construct needs to
1020
// be specified, such as with `phmap::any`, designed to be a drop-in replacement
1021
// for C++17's `std::in_place_index_t`.
1022
template <size_t I>
1023
struct in_place_index_t {};
1024
#endif  // PHMAP_HAVE_STD_VARIANT
1025
1026
// Constexpr move and forward
1027
1028
// move()
1029
//
1030
// A constexpr version of `std::move()`, designed to be a drop-in replacement
1031
// for C++14's `std::move()`.
1032
template <typename T>
1033
constexpr phmap::remove_reference_t<T>&& move(T&& t) noexcept {
1034
  return static_cast<phmap::remove_reference_t<T>&&>(t);
1035
}
1036
1037
// forward()
1038
//
1039
// A constexpr version of `std::forward()`, designed to be a drop-in replacement
1040
// for C++14's `std::forward()`.
1041
template <typename T>
1042
constexpr T&& forward(
1043
    phmap::remove_reference_t<T>& t) noexcept {  // NOLINT(runtime/references)
1044
  return static_cast<T&&>(t);
1045
}
1046
1047
namespace utility_internal {
1048
// Helper method for expanding tuple into a called method.
1049
template <typename Functor, typename Tuple, std::size_t... Indexes>
1050
auto apply_helper(Functor&& functor, Tuple&& t, index_sequence<Indexes...>)
1051
    -> decltype(phmap::base_internal::Invoke(
1052
        phmap::forward<Functor>(functor),
1053
        std::get<Indexes>(phmap::forward<Tuple>(t))...)) {
1054
  return phmap::base_internal::Invoke(
1055
      phmap::forward<Functor>(functor),
1056
      std::get<Indexes>(phmap::forward<Tuple>(t))...);
1057
}
1058
1059
}  // namespace utility_internal
1060
1061
// apply
1062
//
1063
// Invokes a Callable using elements of a tuple as its arguments.
1064
// Each element of the tuple corresponds to an argument of the call (in order).
1065
// Both the Callable argument and the tuple argument are perfect-forwarded.
1066
// For member-function Callables, the first tuple element acts as the `this`
1067
// pointer. `phmap::apply` is designed to be a drop-in replacement for C++17's
1068
// `std::apply`. Unlike C++17's `std::apply`, this is not currently `constexpr`.
1069
//
1070
// Example:
1071
//
1072
//   class Foo {
1073
//    public:
1074
//     void Bar(int);
1075
//   };
1076
//   void user_function1(int, std::string);
1077
//   void user_function2(std::unique_ptr<Foo>);
1078
//   auto user_lambda = [](int, int) {};
1079
//
1080
//   int main()
1081
//   {
1082
//       std::tuple<int, std::string> tuple1(42, "bar");
1083
//       // Invokes the first user function on int, std::string.
1084
//       phmap::apply(&user_function1, tuple1);
1085
//
1086
//       std::tuple<std::unique_ptr<Foo>> tuple2(phmap::make_unique<Foo>());
1087
//       // Invokes the user function that takes ownership of the unique
1088
//       // pointer.
1089
//       phmap::apply(&user_function2, std::move(tuple2));
1090
//
1091
//       auto foo = phmap::make_unique<Foo>();
1092
//       std::tuple<Foo*, int> tuple3(foo.get(), 42);
1093
//       // Invokes the method Bar on foo with one argument, 42.
1094
//       phmap::apply(&Foo::Bar, tuple3);
1095
//
1096
//       std::tuple<int, int> tuple4(8, 9);
1097
//       // Invokes a lambda.
1098
//       phmap::apply(user_lambda, tuple4);
1099
//   }
1100
template <typename Functor, typename Tuple>
1101
auto apply(Functor&& functor, Tuple&& t)
1102
    -> decltype(utility_internal::apply_helper(
1103
        phmap::forward<Functor>(functor), phmap::forward<Tuple>(t),
1104
        phmap::make_index_sequence<std::tuple_size<
1105
            typename std::remove_reference<Tuple>::type>::value>{})) {
1106
  return utility_internal::apply_helper(
1107
      phmap::forward<Functor>(functor), phmap::forward<Tuple>(t),
1108
      phmap::make_index_sequence<std::tuple_size<
1109
          typename std::remove_reference<Tuple>::type>::value>{});
1110
}
1111
1112
#ifdef _MSC_VER
1113
    #pragma warning(push)
1114
    #pragma warning(disable : 4365) // '=': conversion from 'T' to 'T', signed/unsigned mismatch
1115
#endif  // _MSC_VER
1116
1117
// exchange
1118
//
1119
// Replaces the value of `obj` with `new_value` and returns the old value of
1120
// `obj`.  `phmap::exchange` is designed to be a drop-in replacement for C++14's
1121
// `std::exchange`.
1122
//
1123
// Example:
1124
//
1125
//   Foo& operator=(Foo&& other) {
1126
//     ptr1_ = phmap::exchange(other.ptr1_, nullptr);
1127
//     int1_ = phmap::exchange(other.int1_, -1);
1128
//     return *this;
1129
//   }
1130
template <typename T, typename U = T>
1131
T exchange(T& obj, U&& new_value)
1132
{
1133
    T old_value = phmap::move(obj);
1134
    obj = phmap::forward<U>(new_value);
1135
    return old_value;
1136
}
1137
1138
#ifdef _MSC_VER
1139
    #pragma warning(pop)
1140
#endif  // _MSC_VER
1141
1142
1143
}  // namespace phmap
1144
1145
// -----------------------------------------------------------------------------
1146
//          memory.h
1147
// -----------------------------------------------------------------------------
1148
1149
namespace phmap {
1150
1151
template <typename T>
1152
std::unique_ptr<T> WrapUnique(T* ptr) 
1153
{
1154
    static_assert(!std::is_array<T>::value, "array types are unsupported");
1155
    static_assert(std::is_object<T>::value, "non-object types are unsupported");
1156
    return std::unique_ptr<T>(ptr);
1157
}
1158
1159
namespace memory_internal {
1160
1161
// Traits to select proper overload and return type for `phmap::make_unique<>`.
1162
template <typename T>
1163
struct MakeUniqueResult {
1164
    using scalar = std::unique_ptr<T>;
1165
};
1166
template <typename T>
1167
struct MakeUniqueResult<T[]> {
1168
    using array = std::unique_ptr<T[]>;
1169
};
1170
template <typename T, size_t N>
1171
struct MakeUniqueResult<T[N]> {
1172
    using invalid = void;
1173
};
1174
1175
}  // namespace memory_internal
1176
1177
#if (__cplusplus > 201103L || defined(_MSC_VER)) && \
1178
    !(defined(__GNUC__) && __GNUC__ == 4 && __GNUC_MINOR__ == 8) 
1179
    using std::make_unique;
1180
#else
1181
1182
    template <typename T, typename... Args>
1183
    typename memory_internal::MakeUniqueResult<T>::scalar make_unique(
1184
        Args&&... args) {
1185
        return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
1186
    }
1187
    
1188
    template <typename T>
1189
    typename memory_internal::MakeUniqueResult<T>::array make_unique(size_t n) {
1190
        return std::unique_ptr<T>(new typename phmap::remove_extent_t<T>[n]());
1191
    }
1192
    
1193
    template <typename T, typename... Args>
1194
    typename memory_internal::MakeUniqueResult<T>::invalid make_unique(
1195
        Args&&... /* args */) = delete;
1196
#endif
1197
1198
template <typename T>
1199
auto RawPtr(T&& ptr) -> decltype(std::addressof(*ptr))
1200
{
1201
    // ptr is a forwarding reference to support Ts with non-const operators.
1202
    return (ptr != nullptr) ? std::addressof(*ptr) : nullptr;
1203
}
1204
1205
0
inline std::nullptr_t RawPtr(std::nullptr_t) { return nullptr; }
1206
1207
template <typename T, typename D>
1208
std::shared_ptr<T> ShareUniquePtr(std::unique_ptr<T, D>&& ptr) {
1209
    return ptr ? std::shared_ptr<T>(std::move(ptr)) : std::shared_ptr<T>();
1210
}
1211
1212
template <typename T>
1213
std::weak_ptr<T> WeakenPtr(const std::shared_ptr<T>& ptr) {
1214
    return std::weak_ptr<T>(ptr);
1215
}
1216
1217
namespace memory_internal {
1218
1219
// ExtractOr<E, O, D>::type evaluates to E<O> if possible. Otherwise, D.
1220
template <template <typename> class Extract, typename Obj, typename Default,
1221
          typename>
1222
struct ExtractOr {
1223
    using type = Default;
1224
};
1225
1226
template <template <typename> class Extract, typename Obj, typename Default>
1227
struct ExtractOr<Extract, Obj, Default, void_t<Extract<Obj>>> {
1228
    using type = Extract<Obj>;
1229
};
1230
1231
template <template <typename> class Extract, typename Obj, typename Default>
1232
using ExtractOrT = typename ExtractOr<Extract, Obj, Default, void>::type;
1233
1234
// Extractors for the features of allocators.
1235
template <typename T>
1236
using GetPointer = typename T::pointer;
1237
1238
template <typename T>
1239
using GetConstPointer = typename T::const_pointer;
1240
1241
template <typename T>
1242
using GetVoidPointer = typename T::void_pointer;
1243
1244
template <typename T>
1245
using GetConstVoidPointer = typename T::const_void_pointer;
1246
1247
template <typename T>
1248
using GetDifferenceType = typename T::difference_type;
1249
1250
template <typename T>
1251
using GetSizeType = typename T::size_type;
1252
1253
template <typename T>
1254
using GetPropagateOnContainerCopyAssignment =
1255
    typename T::propagate_on_container_copy_assignment;
1256
1257
template <typename T>
1258
using GetPropagateOnContainerMoveAssignment =
1259
    typename T::propagate_on_container_move_assignment;
1260
1261
template <typename T>
1262
using GetPropagateOnContainerSwap = typename T::propagate_on_container_swap;
1263
1264
template <typename T>
1265
using GetIsAlwaysEqual = typename T::is_always_equal;
1266
1267
template <typename T>
1268
struct GetFirstArg;
1269
1270
template <template <typename...> class Class, typename T, typename... Args>
1271
struct GetFirstArg<Class<T, Args...>> {
1272
  using type = T;
1273
};
1274
1275
template <typename Ptr, typename = void>
1276
struct ElementType {
1277
  using type = typename GetFirstArg<Ptr>::type;
1278
};
1279
1280
template <typename T>
1281
struct ElementType<T, void_t<typename T::element_type>> {
1282
  using type = typename T::element_type;
1283
};
1284
1285
template <typename T, typename U>
1286
struct RebindFirstArg;
1287
1288
template <template <typename...> class Class, typename T, typename... Args,
1289
          typename U>
1290
struct RebindFirstArg<Class<T, Args...>, U> {
1291
  using type = Class<U, Args...>;
1292
};
1293
1294
template <typename T, typename U, typename = void>
1295
struct RebindPtr {
1296
  using type = typename RebindFirstArg<T, U>::type;
1297
};
1298
1299
template <typename T, typename U>
1300
struct RebindPtr<T, U, void_t<typename T::template rebind<U>>> {
1301
  using type = typename T::template rebind<U>;
1302
};
1303
1304
template <typename T, typename U>
1305
constexpr bool HasRebindAlloc(...) {
1306
  return false;
1307
}
1308
1309
template <typename T, typename U>
1310
0
constexpr bool HasRebindAlloc(typename std::allocator_traits<T>::template rebind_alloc<U>*) {
1311
0
  return true;
1312
0
}
Unexecuted instantiation: bool phmap::memory_internal::HasRebindAlloc<std::__1::allocator<std::__1::pair<unsigned int const, int> >, std::__1::pair<unsigned int const, int> >(std::__1::allocator_traits<std::__1::allocator<std::__1::pair<unsigned int const, int> > >::rebind_alloc<std::__1::pair<unsigned int const, int> >*)
Unexecuted instantiation: bool phmap::memory_internal::HasRebindAlloc<std::__1::allocator<std::__1::pair<unsigned int const, int> >, phmap::priv::map_slot_type<unsigned int, int> >(std::__1::allocator_traits<std::__1::allocator<std::__1::pair<unsigned int const, int> > >::rebind_alloc<phmap::priv::map_slot_type<unsigned int, int> >*)
Unexecuted instantiation: bool phmap::memory_internal::HasRebindAlloc<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> > > >, 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> > > >(std::__1::allocator_traits<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> > > > >::rebind_alloc<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> > > >*)
Unexecuted instantiation: bool phmap::memory_internal::HasRebindAlloc<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> > > >, 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> > > >(std::__1::allocator_traits<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> > > > >::rebind_alloc<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> > > >*)
Unexecuted instantiation: bool phmap::memory_internal::HasRebindAlloc<std::__1::allocator<std::__1::pair<unsigned int const, int> >, phmap::priv::Deallocate<4ul, std::__1::allocator<std::__1::pair<unsigned int const, int> > >(std::__1::allocator<std::__1::pair<unsigned int const, int> >*, void*, unsigned long)::M>(std::__1::allocator_traits<std::__1::allocator<std::__1::pair<unsigned int const, int> > >::rebind_alloc<phmap::priv::Deallocate<4ul, std::__1::allocator<std::__1::pair<unsigned int const, int> > >(std::__1::allocator<std::__1::pair<unsigned int const, int> >*, void*, unsigned long)::M>*)
Unexecuted instantiation: bool phmap::memory_internal::HasRebindAlloc<std::__1::allocator<std::__1::pair<unsigned int const, int> >, phmap::priv::Allocate<4ul, std::__1::allocator<std::__1::pair<unsigned int const, int> > >(std::__1::allocator<std::__1::pair<unsigned int const, int> >*, unsigned long)::M>(std::__1::allocator_traits<std::__1::allocator<std::__1::pair<unsigned int const, int> > >::rebind_alloc<phmap::priv::Allocate<4ul, std::__1::allocator<std::__1::pair<unsigned int const, int> > >(std::__1::allocator<std::__1::pair<unsigned int const, int> >*, unsigned long)::M>*)
Unexecuted instantiation: bool phmap::memory_internal::HasRebindAlloc<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> > > >, phmap::priv::Deallocate<8ul, 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> > > > >(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> > > >*, void*, unsigned long)::M>(std::__1::allocator_traits<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> > > > >::rebind_alloc<phmap::priv::Deallocate<8ul, 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> > > > >(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> > > >*, void*, unsigned long)::M>*)
1313
1314
template <typename T, typename U, bool = HasRebindAlloc<T, U>(nullptr)>
1315
struct RebindAlloc {
1316
  using type = typename RebindFirstArg<T, U>::type;
1317
};
1318
1319
template <typename A, typename U>
1320
struct RebindAlloc<A, U, true> {
1321
    using type = typename std::allocator_traits<A>::template rebind_alloc<U>;
1322
};
1323
1324
1325
}  // namespace memory_internal
1326
1327
template <typename Ptr>
1328
struct pointer_traits 
1329
{
1330
    using pointer = Ptr;
1331
1332
    // element_type:
1333
    // Ptr::element_type if present. Otherwise T if Ptr is a template
1334
    // instantiation Template<T, Args...>
1335
    using element_type = typename memory_internal::ElementType<Ptr>::type;
1336
1337
    // difference_type:
1338
    // Ptr::difference_type if present, otherwise std::ptrdiff_t
1339
    using difference_type =
1340
        memory_internal::ExtractOrT<memory_internal::GetDifferenceType, Ptr,
1341
                                    std::ptrdiff_t>;
1342
1343
    // rebind:
1344
    // Ptr::rebind<U> if exists, otherwise Template<U, Args...> if Ptr is a
1345
    // template instantiation Template<T, Args...>
1346
    template <typename U>
1347
    using rebind = typename memory_internal::RebindPtr<Ptr, U>::type;
1348
1349
    // pointer_to:
1350
    // Calls Ptr::pointer_to(r)
1351
    static pointer pointer_to(element_type& r) {  // NOLINT(runtime/references)
1352
        return Ptr::pointer_to(r);
1353
    }
1354
};
1355
1356
// Specialization for T*.
1357
template <typename T>
1358
struct pointer_traits<T*> 
1359
{
1360
    using pointer = T*;
1361
    using element_type = T;
1362
    using difference_type = std::ptrdiff_t;
1363
1364
    template <typename U>
1365
    using rebind = U*;
1366
1367
    // pointer_to:
1368
    // Calls std::addressof(r)
1369
    static pointer pointer_to(
1370
        element_type& r) noexcept {  // NOLINT(runtime/references)
1371
        return std::addressof(r);
1372
    }
1373
};
1374
1375
// -----------------------------------------------------------------------------
1376
// Class Template: allocator_traits
1377
// -----------------------------------------------------------------------------
1378
//
1379
// A C++11 compatible implementation of C++17's std::allocator_traits.
1380
//
1381
template <typename Alloc>
1382
struct allocator_traits 
1383
{
1384
    using allocator_type = Alloc;
1385
1386
    // value_type:
1387
    // Alloc::value_type
1388
    using value_type = typename Alloc::value_type;
1389
1390
    // pointer:
1391
    // Alloc::pointer if present, otherwise value_type*
1392
    using pointer = memory_internal::ExtractOrT<memory_internal::GetPointer,
1393
                                                Alloc, value_type*>;
1394
1395
    // const_pointer:
1396
    // Alloc::const_pointer if present, otherwise
1397
    // phmap::pointer_traits<pointer>::rebind<const value_type>
1398
    using const_pointer =
1399
        memory_internal::ExtractOrT<memory_internal::GetConstPointer, Alloc,
1400
                                    typename phmap::pointer_traits<pointer>::
1401
                                    template rebind<const value_type>>;
1402
1403
    // void_pointer:
1404
    // Alloc::void_pointer if present, otherwise
1405
    // phmap::pointer_traits<pointer>::rebind<void>
1406
    using void_pointer = memory_internal::ExtractOrT<
1407
        memory_internal::GetVoidPointer, Alloc,
1408
        typename phmap::pointer_traits<pointer>::template rebind<void>>;
1409
1410
    // const_void_pointer:
1411
    // Alloc::const_void_pointer if present, otherwise
1412
    // phmap::pointer_traits<pointer>::rebind<const void>
1413
    using const_void_pointer = memory_internal::ExtractOrT<
1414
        memory_internal::GetConstVoidPointer, Alloc,
1415
        typename phmap::pointer_traits<pointer>::template rebind<const void>>;
1416
1417
    // difference_type:
1418
    // Alloc::difference_type if present, otherwise
1419
    // phmap::pointer_traits<pointer>::difference_type
1420
    using difference_type = memory_internal::ExtractOrT<
1421
        memory_internal::GetDifferenceType, Alloc,
1422
        typename phmap::pointer_traits<pointer>::difference_type>;
1423
1424
    // size_type:
1425
    // Alloc::size_type if present, otherwise
1426
    // std::make_unsigned<difference_type>::type
1427
    using size_type = memory_internal::ExtractOrT<
1428
        memory_internal::GetSizeType, Alloc,
1429
        typename std::make_unsigned<difference_type>::type>;
1430
1431
    // propagate_on_container_copy_assignment:
1432
    // Alloc::propagate_on_container_copy_assignment if present, otherwise
1433
    // std::false_type
1434
    using propagate_on_container_copy_assignment = memory_internal::ExtractOrT<
1435
        memory_internal::GetPropagateOnContainerCopyAssignment, Alloc,
1436
        std::false_type>;
1437
1438
    // propagate_on_container_move_assignment:
1439
    // Alloc::propagate_on_container_move_assignment if present, otherwise
1440
    // std::false_type
1441
    using propagate_on_container_move_assignment = memory_internal::ExtractOrT<
1442
        memory_internal::GetPropagateOnContainerMoveAssignment, Alloc,
1443
        std::false_type>;
1444
1445
    // propagate_on_container_swap:
1446
    // Alloc::propagate_on_container_swap if present, otherwise std::false_type
1447
    using propagate_on_container_swap =
1448
        memory_internal::ExtractOrT<memory_internal::GetPropagateOnContainerSwap,
1449
                                    Alloc, std::false_type>;
1450
1451
    // is_always_equal:
1452
    // Alloc::is_always_equal if present, otherwise std::is_empty<Alloc>::type
1453
    using is_always_equal =
1454
        memory_internal::ExtractOrT<memory_internal::GetIsAlwaysEqual, Alloc,
1455
                                    typename std::is_empty<Alloc>::type>;
1456
1457
    // rebind_alloc:
1458
    // Alloc::rebind<T>::other if present, otherwise Alloc<T, Args> if this Alloc
1459
    // is Alloc<U, Args>
1460
    template <typename T>
1461
    using rebind_alloc = typename memory_internal::RebindAlloc<Alloc, T>::type;
1462
1463
    // rebind_traits:
1464
    // phmap::allocator_traits<rebind_alloc<T>>
1465
    template <typename T>
1466
    using rebind_traits = phmap::allocator_traits<rebind_alloc<T>>;
1467
1468
    // allocate(Alloc& a, size_type n):
1469
    // Calls a.allocate(n)
1470
    static pointer allocate(Alloc& a,  // NOLINT(runtime/references)
1471
2.95k
                            size_type n) {
1472
2.95k
        return a.allocate(n);
1473
2.95k
    }
1474
1475
    // allocate(Alloc& a, size_type n, const_void_pointer hint):
1476
    // Calls a.allocate(n, hint) if possible.
1477
    // If not possible, calls a.allocate(n)
1478
    static pointer allocate(Alloc& a, size_type n,  // NOLINT(runtime/references)
1479
                            const_void_pointer hint) {
1480
        return allocate_impl(0, a, n, hint);
1481
    }
1482
1483
    // deallocate(Alloc& a, pointer p, size_type n):
1484
    // Calls a.deallocate(p, n)
1485
    static void deallocate(Alloc& a, pointer p,  // NOLINT(runtime/references)
1486
2.95k
                           size_type n) {
1487
2.95k
        a.deallocate(p, n);
1488
2.95k
    }
phmap::allocator_traits<std::__1::allocator<phmap::priv::Deallocate<4ul, std::__1::allocator<std::__1::pair<unsigned int const, int> > >(std::__1::allocator<std::__1::pair<unsigned int const, int> >*, void*, unsigned long)::M> >::deallocate(std::__1::allocator<phmap::priv::Deallocate<4ul, std::__1::allocator<std::__1::pair<unsigned int const, int> > >(std::__1::allocator<std::__1::pair<unsigned int const, int> >*, void*, unsigned long)::M>&, phmap::priv::Deallocate<4ul, std::__1::allocator<std::__1::pair<unsigned int const, int> > >(std::__1::allocator<std::__1::pair<unsigned int const, int> >*, void*, unsigned long)::M*, unsigned long)
Line
Count
Source
1486
2.95k
                           size_type n) {
1487
2.95k
        a.deallocate(p, n);
1488
2.95k
    }
Unexecuted instantiation: phmap::allocator_traits<std::__1::allocator<phmap::priv::Deallocate<8ul, 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> > > > >(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> > > >*, void*, unsigned long)::M> >::deallocate(std::__1::allocator<phmap::priv::Deallocate<8ul, 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> > > > >(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> > > >*, void*, unsigned long)::M>&, phmap::priv::Deallocate<8ul, 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> > > > >(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> > > >*, void*, unsigned long)::M*, unsigned long)
1489
1490
    // construct(Alloc& a, T* p, Args&&... args):
1491
    // Calls a.construct(p, std::forward<Args>(args)...) if possible.
1492
    // If not possible, calls
1493
    //   ::new (static_cast<void*>(p)) T(std::forward<Args>(args)...)
1494
    template <typename T, typename... Args>
1495
    static void construct(Alloc& a, T* p,  // NOLINT(runtime/references)
1496
1.49M
                          Args&&... args) {
1497
1.49M
        construct_impl(0, a, p, std::forward<Args>(args)...);
1498
1.49M
    }
void phmap::allocator_traits<std::__1::allocator<std::__1::pair<unsigned int const, int> > >::construct<std::__1::pair<unsigned int, int>, std::__1::pair<unsigned int, int> >(std::__1::allocator<std::__1::pair<unsigned int const, int> >&, std::__1::pair<unsigned int, int>*, std::__1::pair<unsigned int, int>&&)
Line
Count
Source
1496
958k
                          Args&&... args) {
1497
958k
        construct_impl(0, a, p, std::forward<Args>(args)...);
1498
958k
    }
void phmap::allocator_traits<std::__1::allocator<std::__1::pair<unsigned int const, int> > >::construct<std::__1::pair<unsigned int, int>, std::__1::piecewise_construct_t const&, std::__1::tuple<unsigned int const&&>, std::__1::tuple<int&&> >(std::__1::allocator<std::__1::pair<unsigned int const, int> >&, std::__1::pair<unsigned int, int>*, std::__1::piecewise_construct_t const&, std::__1::tuple<unsigned int const&&>&&, std::__1::tuple<int&&>&&)
Line
Count
Source
1496
536k
                          Args&&... args) {
1497
536k
        construct_impl(0, a, p, std::forward<Args>(args)...);
1498
536k
    }
Unexecuted instantiation: void phmap::allocator_traits<std::__1::allocator<std::__1::pair<unsigned int const, int> > >::construct<std::__1::pair<unsigned int const, int>, std::__1::pair<unsigned int const, int> >(std::__1::allocator<std::__1::pair<unsigned int const, int> >&, std::__1::pair<unsigned int const, int>*, std::__1::pair<unsigned int const, int>&&)
Unexecuted instantiation: void phmap::allocator_traits<std::__1::allocator<std::__1::pair<unsigned int const, int> > >::construct<std::__1::pair<unsigned int const, int>, std::__1::piecewise_construct_t const&, std::__1::tuple<unsigned int const&&>, std::__1::tuple<int&&> >(std::__1::allocator<std::__1::pair<unsigned int const, int> >&, std::__1::pair<unsigned int const, int>*, std::__1::piecewise_construct_t const&, std::__1::tuple<unsigned int const&&>&&, std::__1::tuple<int&&>&&)
1499
1500
    // destroy(Alloc& a, T* p):
1501
    // Calls a.destroy(p) if possible. If not possible, calls p->~T().
1502
    template <typename T>
1503
958k
    static void destroy(Alloc& a, T* p) {  // NOLINT(runtime/references)
1504
958k
        destroy_impl(0, a, p);
1505
958k
    }
Unexecuted instantiation: void phmap::allocator_traits<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<std::__1::pair<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> > > >(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> > > >&, std::__1::pair<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> > >*)
void phmap::allocator_traits<std::__1::allocator<std::__1::pair<unsigned int const, int> > >::destroy<std::__1::pair<unsigned int, int> >(std::__1::allocator<std::__1::pair<unsigned int const, int> >&, std::__1::pair<unsigned int, int>*)
Line
Count
Source
1503
958k
    static void destroy(Alloc& a, T* p) {  // NOLINT(runtime/references)
1504
958k
        destroy_impl(0, a, p);
1505
958k
    }
Unexecuted instantiation: void phmap::allocator_traits<std::__1::allocator<std::__1::pair<unsigned int const, int> > >::destroy<std::__1::pair<unsigned int const, int> >(std::__1::allocator<std::__1::pair<unsigned int const, int> >&, std::__1::pair<unsigned int const, int>*)
Unexecuted instantiation: void phmap::allocator_traits<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<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> > > >(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> > > >&, 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> > >*)
1506
1507
    // max_size(const Alloc& a):
1508
    // Returns a.max_size() if possible. If not possible, returns
1509
    //   std::numeric_limits<size_type>::max() / sizeof(value_type)
1510
    static size_type max_size(const Alloc& a) { return max_size_impl(0, a); }
1511
1512
    // select_on_container_copy_construction(const Alloc& a):
1513
    // Returns a.select_on_container_copy_construction() if possible.
1514
    // If not possible, returns a.
1515
    static Alloc select_on_container_copy_construction(const Alloc& a) {
1516
        return select_on_container_copy_construction_impl(0, a);
1517
    }
1518
1519
private:
1520
    template <typename A>
1521
    static auto allocate_impl(int, A& a,  // NOLINT(runtime/references)
1522
                              size_type n, const_void_pointer hint)
1523
        -> decltype(a.allocate(n, hint)) {
1524
        return a.allocate(n, hint);
1525
    }
1526
    static pointer allocate_impl(char, Alloc& a,  // NOLINT(runtime/references)
1527
                                 size_type n, const_void_pointer) {
1528
        return a.allocate(n);
1529
    }
1530
1531
    template <typename A, typename... Args>
1532
    static auto construct_impl(int, A& a,  // NOLINT(runtime/references)
1533
                               Args&&... args)
1534
1.49M
        -> decltype(std::allocator_traits<A>::construct(a, std::forward<Args>(args)...)) {
1535
1.49M
        std::allocator_traits<A>::construct(a, std::forward<Args>(args)...);
1536
1.49M
    }
_ZN5phmap16allocator_traitsINSt3__19allocatorINS1_4pairIKjiEEEEE14construct_implIS6_JRPNS3_IjiEES9_EEEDTclsr3std16allocator_traitsIT_EE9constructfp0_spclsr3stdE7forwardIT0_Efp1_EEEiRSC_DpOSD_
Line
Count
Source
1534
958k
        -> decltype(std::allocator_traits<A>::construct(a, std::forward<Args>(args)...)) {
1535
958k
        std::allocator_traits<A>::construct(a, std::forward<Args>(args)...);
1536
958k
    }
_ZN5phmap16allocator_traitsINSt3__19allocatorINS1_4pairIKjiEEEEE14construct_implIS6_JRPNS3_IjiEERKNS1_21piecewise_construct_tENS1_5tupleIJOS4_EEENSF_IJOiEEEEEEDTclsr3std16allocator_traitsIT_EE9constructfp0_spclsr3stdE7forwardIT0_Efp1_EEEiRSK_DpOSL_
Line
Count
Source
1534
536k
        -> decltype(std::allocator_traits<A>::construct(a, std::forward<Args>(args)...)) {
1535
536k
        std::allocator_traits<A>::construct(a, std::forward<Args>(args)...);
1536
536k
    }
Unexecuted instantiation: _ZN5phmap16allocator_traitsINSt3__19allocatorINS1_4pairIKjiEEEEE14construct_implIS6_JRPS5_S5_EEEDTclsr3std16allocator_traitsIT_EE9constructfp0_spclsr3stdE7forwardIT0_Efp1_EEEiRSB_DpOSC_
Unexecuted instantiation: _ZN5phmap16allocator_traitsINSt3__19allocatorINS1_4pairIKjiEEEEE14construct_implIS6_JRPS5_RKNS1_21piecewise_construct_tENS1_5tupleIJOS4_EEENSE_IJOiEEEEEEDTclsr3std16allocator_traitsIT_EE9constructfp0_spclsr3stdE7forwardIT0_Efp1_EEEiRSJ_DpOSK_
1537
1538
    template <typename T, typename... Args>
1539
    static void construct_impl(char, Alloc&, T* p, Args&&... args) {
1540
        ::new (static_cast<void*>(p)) T(std::forward<Args>(args)...);
1541
    }
1542
1543
    template <typename A, typename T>
1544
    static auto destroy_impl(int, A& a,  // NOLINT(runtime/references)
1545
958k
                             T* p) -> decltype(std::allocator_traits<A>::destroy(a, p)) {
1546
958k
        std::allocator_traits<A>::destroy(a, p);
1547
958k
    }
Unexecuted instantiation: _ZN5phmap16allocator_traitsINSt3__19allocatorINS1_4pairIKNS1_12basic_stringIcNS1_11char_traitsIcEENS2_IcEEEES8_EEEEE12destroy_implISB_NS3_IS8_S8_EEEEDTclsr3std16allocator_traitsIT_EE7destroyfp0_fp1_EEiRSF_PT0_
_ZN5phmap16allocator_traitsINSt3__19allocatorINS1_4pairIKjiEEEEE12destroy_implIS6_NS3_IjiEEEEDTclsr3std16allocator_traitsIT_EE7destroyfp0_fp1_EEiRSA_PT0_
Line
Count
Source
1545
958k
                             T* p) -> decltype(std::allocator_traits<A>::destroy(a, p)) {
1546
958k
        std::allocator_traits<A>::destroy(a, p);
1547
958k
    }
Unexecuted instantiation: _ZN5phmap16allocator_traitsINSt3__19allocatorINS1_4pairIKjiEEEEE12destroy_implIS6_S5_EEDTclsr3std16allocator_traitsIT_EE7destroyfp0_fp1_EEiRS9_PT0_
Unexecuted instantiation: _ZN5phmap16allocator_traitsINSt3__19allocatorINS1_4pairIKNS1_12basic_stringIcNS1_11char_traitsIcEENS2_IcEEEES8_EEEEE12destroy_implISB_SA_EEDTclsr3std16allocator_traitsIT_EE7destroyfp0_fp1_EEiRSE_PT0_
1548
    template <typename T>
1549
    static void destroy_impl(char, Alloc&, T* p) {
1550
        p->~T();
1551
    }
1552
1553
    template <typename A>
1554
    static auto max_size_impl(int, const A& a) -> decltype(a.max_size()) {
1555
        return a.max_size();
1556
    }
1557
    static size_type max_size_impl(char, const Alloc&) {
1558
        return (std::numeric_limits<size_type>::max)() / sizeof(value_type);
1559
    }
1560
1561
    template <typename A>
1562
    static auto select_on_container_copy_construction_impl(int, const A& a)
1563
        -> decltype(a.select_on_container_copy_construction()) {
1564
        return a.select_on_container_copy_construction();
1565
    }
1566
    static Alloc select_on_container_copy_construction_impl(char,
1567
                                                            const Alloc& a) {
1568
        return a;
1569
    }
1570
};
1571
1572
namespace memory_internal {
1573
1574
// This template alias transforms Alloc::is_nothrow into a metafunction with
1575
// Alloc as a parameter so it can be used with ExtractOrT<>.
1576
template <typename Alloc>
1577
using GetIsNothrow = typename Alloc::is_nothrow;
1578
1579
}  // namespace memory_internal
1580
1581
// PHMAP_ALLOCATOR_NOTHROW is a build time configuration macro for user to
1582
// specify whether the default allocation function can throw or never throws.
1583
// If the allocation function never throws, user should define it to a non-zero
1584
// value (e.g. via `-DPHMAP_ALLOCATOR_NOTHROW`).
1585
// If the allocation function can throw, user should leave it undefined or
1586
// define it to zero.
1587
//
1588
// allocator_is_nothrow<Alloc> is a traits class that derives from
1589
// Alloc::is_nothrow if present, otherwise std::false_type. It's specialized
1590
// for Alloc = std::allocator<T> for any type T according to the state of
1591
// PHMAP_ALLOCATOR_NOTHROW.
1592
//
1593
// default_allocator_is_nothrow is a class that derives from std::true_type
1594
// when the default allocator (global operator new) never throws, and
1595
// std::false_type when it can throw. It is a convenience shorthand for writing
1596
// allocator_is_nothrow<std::allocator<T>> (T can be any type).
1597
// NOTE: allocator_is_nothrow<std::allocator<T>> is guaranteed to derive from
1598
// the same type for all T, because users should specialize neither
1599
// allocator_is_nothrow nor std::allocator.
1600
template <typename Alloc>
1601
struct allocator_is_nothrow
1602
    : memory_internal::ExtractOrT<memory_internal::GetIsNothrow, Alloc,
1603
                                  std::false_type> {};
1604
1605
#if defined(PHMAP_ALLOCATOR_NOTHROW) && PHMAP_ALLOCATOR_NOTHROW
1606
    template <typename T>
1607
    struct allocator_is_nothrow<std::allocator<T>> : std::true_type {};
1608
    struct default_allocator_is_nothrow : std::true_type {};
1609
#else
1610
    struct default_allocator_is_nothrow : std::false_type {};
1611
#endif
1612
1613
namespace memory_internal {
1614
template <typename Allocator, typename Iterator, typename... Args>
1615
void ConstructRange(Allocator& alloc, Iterator first, Iterator last,
1616
                    const Args&... args) 
1617
{
1618
    for (Iterator cur = first; cur != last; ++cur) {
1619
        PHMAP_INTERNAL_TRY {
1620
            std::allocator_traits<Allocator>::construct(alloc, std::addressof(*cur),
1621
                                                        args...);
1622
        }
1623
        PHMAP_INTERNAL_CATCH_ANY {
1624
            while (cur != first) {
1625
                --cur;
1626
                std::allocator_traits<Allocator>::destroy(alloc, std::addressof(*cur));
1627
            }
1628
            PHMAP_INTERNAL_RETHROW;
1629
        }
1630
    }
1631
}
1632
1633
template <typename Allocator, typename Iterator, typename InputIterator>
1634
void CopyRange(Allocator& alloc, Iterator destination, InputIterator first,
1635
               InputIterator last) 
1636
{
1637
    for (Iterator cur = destination; first != last;
1638
         static_cast<void>(++cur), static_cast<void>(++first)) {
1639
        PHMAP_INTERNAL_TRY {
1640
            std::allocator_traits<Allocator>::construct(alloc, std::addressof(*cur),
1641
                                                        *first);
1642
        }
1643
        PHMAP_INTERNAL_CATCH_ANY {
1644
            while (cur != destination) {
1645
                --cur;
1646
                std::allocator_traits<Allocator>::destroy(alloc, std::addressof(*cur));
1647
            }
1648
            PHMAP_INTERNAL_RETHROW;
1649
        }
1650
    }
1651
}
1652
}  // namespace memory_internal
1653
}  // namespace phmap
1654
1655
1656
// -----------------------------------------------------------------------------
1657
//          optional.h
1658
// -----------------------------------------------------------------------------
1659
#ifdef PHMAP_HAVE_STD_OPTIONAL
1660
1661
#include <optional>  // IWYU pragma: export
1662
1663
namespace phmap {
1664
using std::bad_optional_access;
1665
using std::optional;
1666
using std::make_optional;
1667
using std::nullopt_t;
1668
using std::nullopt;
1669
}  // namespace phmap
1670
1671
#else
1672
1673
#if defined(__clang__)
1674
    #if __has_feature(cxx_inheriting_constructors)
1675
        #define PHMAP_OPTIONAL_USE_INHERITING_CONSTRUCTORS 1
1676
    #endif
1677
#elif (defined(__GNUC__) &&                                       \
1678
       (__GNUC__ > 4 || __GNUC__ == 4 && __GNUC_MINOR__ >= 8)) || \
1679
    (__cpp_inheriting_constructors >= 200802) ||                  \
1680
    (defined(_MSC_VER) && _MSC_VER >= 1910)
1681
1682
    #define PHMAP_OPTIONAL_USE_INHERITING_CONSTRUCTORS 1
1683
#endif
1684
1685
namespace phmap {
1686
1687
class bad_optional_access : public std::exception 
1688
{
1689
public:
1690
    bad_optional_access() = default;
1691
    ~bad_optional_access() override;
1692
    const char* what() const noexcept override;
1693
};
1694
1695
template <typename T>
1696
class optional;
1697
1698
// --------------------------------
1699
struct nullopt_t 
1700
{
1701
    struct init_t {};
1702
    static init_t init;
1703
1704
    explicit constexpr nullopt_t(init_t& /*unused*/) {}
1705
};
1706
1707
constexpr nullopt_t nullopt(nullopt_t::init);
1708
1709
namespace optional_internal {
1710
1711
// throw delegator
1712
[[noreturn]] void throw_bad_optional_access();
1713
1714
1715
struct empty_struct {};
1716
1717
// This class stores the data in optional<T>.
1718
// It is specialized based on whether T is trivially destructible.
1719
// This is the specialization for non trivially destructible type.
1720
template <typename T, bool unused = std::is_trivially_destructible<T>::value>
1721
class optional_data_dtor_base 
1722
{
1723
    struct dummy_type {
1724
        static_assert(sizeof(T) % sizeof(empty_struct) == 0, "");
1725
        // Use an array to avoid GCC 6 placement-new warning.
1726
        empty_struct data[sizeof(T) / sizeof(empty_struct)];
1727
    };
1728
1729
protected:
1730
    // Whether there is data or not.
1731
    bool engaged_;
1732
    // Data storage
1733
    union {
1734
        dummy_type dummy_;
1735
        T data_;
1736
    };
1737
1738
    void destruct() noexcept {
1739
        if (engaged_) {
1740
            data_.~T();
1741
            engaged_ = false;
1742
        }
1743
    }
1744
1745
    // dummy_ must be initialized for constexpr constructor.
1746
    constexpr optional_data_dtor_base() noexcept : engaged_(false), dummy_{{}} {}
1747
1748
    template <typename... Args>
1749
    constexpr explicit optional_data_dtor_base(in_place_t, Args&&... args)
1750
        : engaged_(true), data_(phmap::forward<Args>(args)...) {}
1751
1752
    ~optional_data_dtor_base() { destruct(); }
1753
};
1754
1755
// Specialization for trivially destructible type.
1756
template <typename T>
1757
class optional_data_dtor_base<T, true> 
1758
{
1759
    struct dummy_type {
1760
        static_assert(sizeof(T) % sizeof(empty_struct) == 0, "");
1761
        // Use array to avoid GCC 6 placement-new warning.
1762
        empty_struct data[sizeof(T) / sizeof(empty_struct)];
1763
    };
1764
1765
protected:
1766
    // Whether there is data or not.
1767
    bool engaged_;
1768
    // Data storage
1769
    union {
1770
        dummy_type dummy_;
1771
        T data_;
1772
    };
1773
    void destruct() noexcept { engaged_ = false; }
1774
1775
    // dummy_ must be initialized for constexpr constructor.
1776
    constexpr optional_data_dtor_base() noexcept : engaged_(false), dummy_{{}} {}
1777
1778
    template <typename... Args>
1779
    constexpr explicit optional_data_dtor_base(in_place_t, Args&&... args)
1780
        : engaged_(true), data_(phmap::forward<Args>(args)...) {}
1781
};
1782
1783
template <typename T>
1784
class optional_data_base : public optional_data_dtor_base<T> 
1785
{
1786
protected:
1787
    using base = optional_data_dtor_base<T>;
1788
#if PHMAP_OPTIONAL_USE_INHERITING_CONSTRUCTORS
1789
    using base::base;
1790
#else
1791
    optional_data_base() = default;
1792
1793
    template <typename... Args>
1794
    constexpr explicit optional_data_base(in_place_t t, Args&&... args)
1795
        : base(t, phmap::forward<Args>(args)...) {}
1796
#endif
1797
1798
    template <typename... Args>
1799
    void construct(Args&&... args) {
1800
        // Use dummy_'s address to work around casting cv-qualified T* to void*.
1801
        ::new (static_cast<void*>(&this->dummy_)) T(std::forward<Args>(args)...);
1802
        this->engaged_ = true;
1803
    }
1804
1805
    template <typename U>
1806
    void assign(U&& u) {
1807
        if (this->engaged_) {
1808
            this->data_ = std::forward<U>(u);
1809
        } else {
1810
            construct(std::forward<U>(u));
1811
        }
1812
    }
1813
};
1814
1815
// TODO: Add another class using
1816
// std::is_trivially_move_constructible trait when available to match
1817
// http://cplusplus.github.io/LWG/lwg-defects.html#2900, for types that
1818
// have trivial move but nontrivial copy.
1819
// Also, we should be checking is_trivially_copyable here, which is not
1820
// supported now, so we use is_trivially_* traits instead.
1821
template <typename T,
1822
          bool unused =
1823
          phmap::is_trivially_copy_constructible<T>::value &&
1824
          phmap::is_trivially_copy_assignable<typename std::remove_cv<T>::type>::value &&
1825
          std::is_trivially_destructible<T>::value>
1826
class optional_data;
1827
1828
// Trivially copyable types
1829
template <typename T>
1830
class optional_data<T, true> : public optional_data_base<T> 
1831
{
1832
protected:
1833
#if PHMAP_OPTIONAL_USE_INHERITING_CONSTRUCTORS
1834
    using optional_data_base<T>::optional_data_base;
1835
#else
1836
    optional_data() = default;
1837
1838
    template <typename... Args>
1839
    constexpr explicit optional_data(in_place_t t, Args&&... args)
1840
        : optional_data_base<T>(t, phmap::forward<Args>(args)...) {}
1841
#endif
1842
};
1843
1844
template <typename T>
1845
class optional_data<T, false> : public optional_data_base<T> 
1846
{
1847
protected:
1848
#if PHMAP_OPTIONAL_USE_INHERITING_CONSTRUCTORS
1849
    using optional_data_base<T>::optional_data_base;
1850
#else
1851
    template <typename... Args>
1852
    constexpr explicit optional_data(in_place_t t, Args&&... args)
1853
        : optional_data_base<T>(t, phmap::forward<Args>(args)...) {}
1854
#endif
1855
1856
    optional_data() = default;
1857
1858
    optional_data(const optional_data& rhs) : optional_data_base<T>() {
1859
        if (rhs.engaged_) {
1860
            this->construct(rhs.data_);
1861
        }
1862
    }
1863
1864
    optional_data(optional_data&& rhs) noexcept(
1865
        phmap::default_allocator_is_nothrow::value ||
1866
        std::is_nothrow_move_constructible<T>::value)
1867
    : optional_data_base<T>() {
1868
        if (rhs.engaged_) {
1869
            this->construct(std::move(rhs.data_));
1870
        }
1871
    }
1872
1873
    optional_data& operator=(const optional_data& rhs) {
1874
        if (rhs.engaged_) {
1875
            this->assign(rhs.data_);
1876
        } else {
1877
            this->destruct();
1878
        }
1879
        return *this;
1880
    }
1881
1882
    optional_data& operator=(optional_data&& rhs) noexcept(
1883
        std::is_nothrow_move_assignable<T>::value&&
1884
        std::is_nothrow_move_constructible<T>::value) {
1885
        if (rhs.engaged_) {
1886
            this->assign(std::move(rhs.data_));
1887
        } else {
1888
            this->destruct();
1889
        }
1890
        return *this;
1891
    }
1892
};
1893
1894
// Ordered by level of restriction, from low to high.
1895
// Copyable implies movable.
1896
enum class copy_traits { copyable = 0, movable = 1, non_movable = 2 };
1897
1898
// Base class for enabling/disabling copy/move constructor.
1899
template <copy_traits>
1900
class optional_ctor_base;
1901
1902
template <>
1903
class optional_ctor_base<copy_traits::copyable> 
1904
{
1905
public:
1906
    constexpr optional_ctor_base() = default;
1907
    optional_ctor_base(const optional_ctor_base&) = default;
1908
    optional_ctor_base(optional_ctor_base&&) = default;
1909
    optional_ctor_base& operator=(const optional_ctor_base&) = default;
1910
    optional_ctor_base& operator=(optional_ctor_base&&) = default;
1911
};
1912
1913
template <>
1914
class optional_ctor_base<copy_traits::movable> 
1915
{
1916
public:
1917
    constexpr optional_ctor_base() = default;
1918
    optional_ctor_base(const optional_ctor_base&) = delete;
1919
    optional_ctor_base(optional_ctor_base&&) = default;
1920
    optional_ctor_base& operator=(const optional_ctor_base&) = default;
1921
    optional_ctor_base& operator=(optional_ctor_base&&) = default;
1922
};
1923
1924
template <>
1925
class optional_ctor_base<copy_traits::non_movable> 
1926
{
1927
public:
1928
    constexpr optional_ctor_base() = default;
1929
    optional_ctor_base(const optional_ctor_base&) = delete;
1930
    optional_ctor_base(optional_ctor_base&&) = delete;
1931
    optional_ctor_base& operator=(const optional_ctor_base&) = default;
1932
    optional_ctor_base& operator=(optional_ctor_base&&) = default;
1933
};
1934
1935
// Base class for enabling/disabling copy/move assignment.
1936
template <copy_traits>
1937
class optional_assign_base;
1938
1939
template <>
1940
class optional_assign_base<copy_traits::copyable> 
1941
{
1942
public:
1943
    constexpr optional_assign_base() = default;
1944
    optional_assign_base(const optional_assign_base&) = default;
1945
    optional_assign_base(optional_assign_base&&) = default;
1946
    optional_assign_base& operator=(const optional_assign_base&) = default;
1947
    optional_assign_base& operator=(optional_assign_base&&) = default;
1948
};
1949
1950
template <>
1951
class optional_assign_base<copy_traits::movable> 
1952
{
1953
public:
1954
    constexpr optional_assign_base() = default;
1955
    optional_assign_base(const optional_assign_base&) = default;
1956
    optional_assign_base(optional_assign_base&&) = default;
1957
    optional_assign_base& operator=(const optional_assign_base&) = delete;
1958
    optional_assign_base& operator=(optional_assign_base&&) = default;
1959
};
1960
1961
template <>
1962
class optional_assign_base<copy_traits::non_movable> 
1963
{
1964
public:
1965
    constexpr optional_assign_base() = default;
1966
    optional_assign_base(const optional_assign_base&) = default;
1967
    optional_assign_base(optional_assign_base&&) = default;
1968
    optional_assign_base& operator=(const optional_assign_base&) = delete;
1969
    optional_assign_base& operator=(optional_assign_base&&) = delete;
1970
};
1971
1972
template <typename T>
1973
constexpr copy_traits get_ctor_copy_traits() 
1974
{
1975
    return std::is_copy_constructible<T>::value
1976
        ? copy_traits::copyable
1977
        : std::is_move_constructible<T>::value ? copy_traits::movable
1978
        : copy_traits::non_movable;
1979
}
1980
1981
template <typename T>
1982
constexpr copy_traits get_assign_copy_traits() 
1983
{
1984
    return phmap::is_copy_assignable<T>::value &&
1985
                 std::is_copy_constructible<T>::value
1986
             ? copy_traits::copyable
1987
             : phmap::is_move_assignable<T>::value &&
1988
                       std::is_move_constructible<T>::value
1989
                   ? copy_traits::movable
1990
                   : copy_traits::non_movable;
1991
}
1992
1993
// Whether T is constructible or convertible from optional<U>.
1994
template <typename T, typename U>
1995
struct is_constructible_convertible_from_optional
1996
    : std::integral_constant<
1997
          bool, std::is_constructible<T, optional<U>&>::value ||
1998
                    std::is_constructible<T, optional<U>&&>::value ||
1999
                    std::is_constructible<T, const optional<U>&>::value ||
2000
                    std::is_constructible<T, const optional<U>&&>::value ||
2001
                    std::is_convertible<optional<U>&, T>::value ||
2002
                    std::is_convertible<optional<U>&&, T>::value ||
2003
                    std::is_convertible<const optional<U>&, T>::value ||
2004
                    std::is_convertible<const optional<U>&&, T>::value> {};
2005
2006
// Whether T is constructible or convertible or assignable from optional<U>.
2007
template <typename T, typename U>
2008
struct is_constructible_convertible_assignable_from_optional
2009
    : std::integral_constant<
2010
          bool, is_constructible_convertible_from_optional<T, U>::value ||
2011
                    std::is_assignable<T&, optional<U>&>::value ||
2012
                    std::is_assignable<T&, optional<U>&&>::value ||
2013
                    std::is_assignable<T&, const optional<U>&>::value ||
2014
                    std::is_assignable<T&, const optional<U>&&>::value> {};
2015
2016
// Helper function used by [optional.relops], [optional.comp_with_t],
2017
// for checking whether an expression is convertible to bool.
2018
bool convertible_to_bool(bool);
2019
2020
// Base class for std::hash<phmap::optional<T>>:
2021
// If std::hash<std::remove_const_t<T>> is enabled, it provides operator() to
2022
// compute the hash; Otherwise, it is disabled.
2023
// Reference N4659 23.14.15 [unord.hash].
2024
template <typename T, typename = size_t>
2025
struct optional_hash_base 
2026
{
2027
    optional_hash_base() = delete;
2028
    optional_hash_base(const optional_hash_base&) = delete;
2029
    optional_hash_base(optional_hash_base&&) = delete;
2030
    optional_hash_base& operator=(const optional_hash_base&) = delete;
2031
    optional_hash_base& operator=(optional_hash_base&&) = delete;
2032
};
2033
2034
template <typename T>
2035
struct optional_hash_base<T, decltype(std::hash<phmap::remove_const_t<T> >()(
2036
                                 std::declval<phmap::remove_const_t<T> >()))> 
2037
{
2038
    using argument_type = phmap::optional<T>;
2039
    using result_type = size_t;
2040
    size_t operator()(const phmap::optional<T>& opt) const {
2041
        phmap::type_traits_internal::AssertHashEnabled<phmap::remove_const_t<T>>();
2042
        if (opt) {
2043
            return std::hash<phmap::remove_const_t<T> >()(*opt);
2044
        } else {
2045
            return static_cast<size_t>(0x297814aaad196e6dULL);
2046
        }
2047
    }
2048
};
2049
2050
}  // namespace optional_internal
2051
2052
2053
// -----------------------------------------------------------------------------
2054
// phmap::optional class definition
2055
// -----------------------------------------------------------------------------
2056
#if PHMAP_OLD_GCC
2057
    #define PHMAP_OPTIONAL_NOEXCEPT
2058
#else
2059
    #define PHMAP_OPTIONAL_NOEXCEPT noexcept
2060
#endif
2061
2062
template <typename T>
2063
class optional : private optional_internal::optional_data<T>,
2064
                 private optional_internal::optional_ctor_base<
2065
                     optional_internal::get_ctor_copy_traits<T>()>,
2066
                 private optional_internal::optional_assign_base<
2067
                     optional_internal::get_assign_copy_traits<T>()> 
2068
{
2069
    using data_base = optional_internal::optional_data<T>;
2070
2071
public:
2072
    typedef T value_type;
2073
2074
    // Constructors
2075
2076
    // Constructs an `optional` holding an empty value, NOT a default constructed
2077
    // `T`.
2078
    constexpr optional() noexcept {}
2079
2080
    // Constructs an `optional` initialized with `nullopt` to hold an empty value.
2081
    constexpr optional(nullopt_t) noexcept {}  // NOLINT(runtime/explicit)
2082
2083
    // Copy constructor, standard semantics
2084
    optional(const optional& src) = default;
2085
2086
    // Move constructor, standard semantics
2087
    optional(optional&& src) PHMAP_OPTIONAL_NOEXCEPT = default;
2088
2089
    // Constructs a non-empty `optional` direct-initialized value of type `T` from
2090
    // the arguments `std::forward<Args>(args)...`  within the `optional`.
2091
    // (The `in_place_t` is a tag used to indicate that the contained object
2092
    // should be constructed in-place.)
2093
    template <typename InPlaceT, typename... Args,
2094
              phmap::enable_if_t<phmap::conjunction<
2095
                                    std::is_same<InPlaceT, in_place_t>,
2096
                                    std::is_constructible<T, Args&&...> >::value>* = nullptr>
2097
        constexpr explicit optional(InPlaceT, Args&&... args)
2098
        : data_base(in_place_t(), phmap::forward<Args>(args)...) {}
2099
2100
    // Constructs a non-empty `optional` direct-initialized value of type `T` from
2101
    // the arguments of an initializer_list and `std::forward<Args>(args)...`.
2102
    // (The `in_place_t` is a tag used to indicate that the contained object
2103
    // should be constructed in-place.)
2104
    template <typename U, typename... Args,
2105
              typename = typename std::enable_if<std::is_constructible<
2106
                                                     T, std::initializer_list<U>&, Args&&...>::value>::type>
2107
        constexpr explicit optional(in_place_t, std::initializer_list<U> il,
2108
                                    Args&&... args)
2109
        : data_base(in_place_t(), il, phmap::forward<Args>(args)...) {
2110
    }
2111
2112
    // Value constructor (implicit)
2113
    template <
2114
        typename U = T,
2115
        typename std::enable_if<
2116
            phmap::conjunction<phmap::negation<std::is_same<
2117
                                                 in_place_t, typename std::decay<U>::type> >,
2118
                              phmap::negation<std::is_same<
2119
                                                 optional<T>, typename std::decay<U>::type> >,
2120
                              std::is_convertible<U&&, T>,
2121
                              std::is_constructible<T, U&&> >::value,
2122
            bool>::type = false>
2123
        constexpr optional(U&& v) : data_base(in_place_t(), phmap::forward<U>(v)) {}
2124
2125
    // Value constructor (explicit)
2126
    template <
2127
        typename U = T,
2128
        typename std::enable_if<
2129
            phmap::conjunction<phmap::negation<std::is_same<
2130
                                                 in_place_t, typename std::decay<U>::type>>,
2131
                              phmap::negation<std::is_same<
2132
                                                 optional<T>, typename std::decay<U>::type>>,
2133
                              phmap::negation<std::is_convertible<U&&, T>>,
2134
                              std::is_constructible<T, U&&>>::value,
2135
            bool>::type = false>
2136
        explicit constexpr optional(U&& v)
2137
        : data_base(in_place_t(), phmap::forward<U>(v)) {}
2138
2139
    // Converting copy constructor (implicit)
2140
    template <typename U,
2141
              typename std::enable_if<
2142
                  phmap::conjunction<
2143
                      phmap::negation<std::is_same<T, U> >,
2144
                      std::is_constructible<T, const U&>,
2145
                      phmap::negation<
2146
                          optional_internal::
2147
                          is_constructible_convertible_from_optional<T, U> >,
2148
                      std::is_convertible<const U&, T> >::value,
2149
                  bool>::type = false>
2150
    optional(const optional<U>& rhs) {
2151
        if (rhs) {
2152
            this->construct(*rhs);
2153
        }
2154
    }
2155
2156
    // Converting copy constructor (explicit)
2157
    template <typename U,
2158
              typename std::enable_if<
2159
                  phmap::conjunction<
2160
                      phmap::negation<std::is_same<T, U>>,
2161
                      std::is_constructible<T, const U&>,
2162
                      phmap::negation<
2163
                          optional_internal::
2164
                          is_constructible_convertible_from_optional<T, U>>,
2165
                      phmap::negation<std::is_convertible<const U&, T>>>::value,
2166
                  bool>::type = false>
2167
        explicit optional(const optional<U>& rhs) {
2168
        if (rhs) {
2169
            this->construct(*rhs);
2170
        }
2171
    }
2172
2173
    // Converting move constructor (implicit)
2174
    template <typename U,
2175
              typename std::enable_if<
2176
                  phmap::conjunction<
2177
                      phmap::negation<std::is_same<T, U> >,
2178
                      std::is_constructible<T, U&&>,
2179
                      phmap::negation<
2180
                          optional_internal::
2181
                          is_constructible_convertible_from_optional<T, U> >,
2182
                      std::is_convertible<U&&, T> >::value,
2183
                  bool>::type = false>
2184
        optional(optional<U>&& rhs) {
2185
        if (rhs) {
2186
            this->construct(std::move(*rhs));
2187
        }
2188
    }
2189
2190
    // Converting move constructor (explicit)
2191
    template <
2192
        typename U,
2193
        typename std::enable_if<
2194
            phmap::conjunction<
2195
                phmap::negation<std::is_same<T, U>>, std::is_constructible<T, U&&>,
2196
                phmap::negation<
2197
                    optional_internal::is_constructible_convertible_from_optional<
2198
                        T, U>>,
2199
                phmap::negation<std::is_convertible<U&&, T>>>::value,
2200
            bool>::type = false>
2201
        explicit optional(optional<U>&& rhs) {
2202
        if (rhs) {
2203
            this->construct(std::move(*rhs));
2204
        }
2205
    }
2206
2207
    // Destructor. Trivial if `T` is trivially destructible.
2208
    ~optional() = default;
2209
2210
    // Assignment Operators
2211
2212
    // Assignment from `nullopt`
2213
    //
2214
    // Example:
2215
    //
2216
    //   struct S { int value; };
2217
    //   optional<S> opt = phmap::nullopt;  // Could also use opt = { };
2218
    optional& operator=(nullopt_t) noexcept {
2219
        this->destruct();
2220
        return *this;
2221
    }
2222
2223
    // Copy assignment operator, standard semantics
2224
    optional& operator=(const optional& src) = default;
2225
2226
    // Move assignment operator, standard semantics
2227
    optional& operator=(optional&& src) PHMAP_OPTIONAL_NOEXCEPT = default;
2228
2229
    // Value assignment operators
2230
    template <
2231
        typename U = T,
2232
        typename = typename std::enable_if<phmap::conjunction<
2233
                                               phmap::negation<
2234
                                                   std::is_same<optional<T>, typename std::decay<U>::type>>,
2235
                                               phmap::negation<
2236
                                                   phmap::conjunction<std::is_scalar<T>,
2237
                                                                     std::is_same<T, typename std::decay<U>::type>>>,
2238
                                               std::is_constructible<T, U>, std::is_assignable<T&, U>>::value>::type>
2239
        optional& operator=(U&& v) {
2240
        this->assign(std::forward<U>(v));
2241
        return *this;
2242
    }
2243
2244
    template <
2245
        typename U,
2246
        typename = typename std::enable_if<phmap::conjunction<
2247
                                               phmap::negation<std::is_same<T, U>>,
2248
                                               std::is_constructible<T, const U&>, std::is_assignable<T&, const U&>,
2249
                                               phmap::negation<
2250
                                                   optional_internal::
2251
                                                   is_constructible_convertible_assignable_from_optional<
2252
                                                       T, U>>>::value>::type>
2253
        optional& operator=(const optional<U>& rhs) {
2254
        if (rhs) {
2255
            this->assign(*rhs);
2256
        } else {
2257
            this->destruct();
2258
        }
2259
        return *this;
2260
    }
2261
2262
    template <typename U,
2263
              typename = typename std::enable_if<phmap::conjunction<
2264
                                                     phmap::negation<std::is_same<T, U>>, std::is_constructible<T, U>,
2265
                                                     std::is_assignable<T&, U>,
2266
                                                     phmap::negation<
2267
                                                         optional_internal::
2268
                                                         is_constructible_convertible_assignable_from_optional<
2269
                                                             T, U>>>::value>::type>
2270
        optional& operator=(optional<U>&& rhs) {
2271
        if (rhs) {
2272
            this->assign(std::move(*rhs));
2273
        } else {
2274
            this->destruct();
2275
        }
2276
        return *this;
2277
    }
2278
2279
    // Modifiers
2280
2281
    // optional::reset()
2282
    //
2283
    // Destroys the inner `T` value of an `phmap::optional` if one is present.
2284
    PHMAP_ATTRIBUTE_REINITIALIZES void reset() noexcept { this->destruct(); }
2285
2286
    // optional::emplace()
2287
    //
2288
    // (Re)constructs the underlying `T` in-place with the given forwarded
2289
    // arguments.
2290
    //
2291
    // Example:
2292
    //
2293
    //   optional<Foo> opt;
2294
    //   opt.emplace(arg1,arg2,arg3);  // Constructs Foo(arg1,arg2,arg3)
2295
    //
2296
    // If the optional is non-empty, and the `args` refer to subobjects of the
2297
    // current object, then behaviour is undefined, because the current object
2298
    // will be destructed before the new object is constructed with `args`.
2299
    template <typename... Args,
2300
              typename = typename std::enable_if<
2301
                  std::is_constructible<T, Args&&...>::value>::type>
2302
        T& emplace(Args&&... args) {
2303
        this->destruct();
2304
        this->construct(std::forward<Args>(args)...);
2305
        return reference();
2306
    }
2307
2308
    // Emplace reconstruction overload for an initializer list and the given
2309
    // forwarded arguments.
2310
    //
2311
    // Example:
2312
    //
2313
    //   struct Foo {
2314
    //     Foo(std::initializer_list<int>);
2315
    //   };
2316
    //
2317
    //   optional<Foo> opt;
2318
    //   opt.emplace({1,2,3});  // Constructs Foo({1,2,3})
2319
    template <typename U, typename... Args,
2320
              typename = typename std::enable_if<std::is_constructible<
2321
                                                     T, std::initializer_list<U>&, Args&&...>::value>::type>
2322
        T& emplace(std::initializer_list<U> il, Args&&... args) {
2323
        this->destruct();
2324
        this->construct(il, std::forward<Args>(args)...);
2325
        return reference();
2326
    }
2327
2328
    // Swaps
2329
2330
    // Swap, standard semantics
2331
    void swap(optional& rhs) noexcept(
2332
        std::is_nothrow_move_constructible<T>::value&&
2333
        std::is_trivial<T>::value) {
2334
        if (*this) {
2335
            if (rhs) {
2336
                using std::swap;
2337
                swap(**this, *rhs);
2338
            } else {
2339
                rhs.construct(std::move(**this));
2340
                this->destruct();
2341
            }
2342
        } else {
2343
            if (rhs) {
2344
                this->construct(std::move(*rhs));
2345
                rhs.destruct();
2346
            } else {
2347
                // No effect (swap(disengaged, disengaged)).
2348
            }
2349
        }
2350
    }
2351
2352
    // Observers
2353
2354
    // optional::operator->()
2355
    //
2356
    // Accesses the underlying `T` value's member `m` of an `optional`. If the
2357
    // `optional` is empty, behavior is undefined.
2358
    //
2359
    // If you need myOpt->foo in constexpr, use (*myOpt).foo instead.
2360
    const T* operator->() const {
2361
        assert(this->engaged_);
2362
        return std::addressof(this->data_);
2363
    }
2364
    T* operator->() {
2365
        assert(this->engaged_);
2366
        return std::addressof(this->data_);
2367
    }
2368
2369
    // optional::operator*()
2370
    //
2371
    // Accesses the underlying `T` value of an `optional`. If the `optional` is
2372
    // empty, behavior is undefined.
2373
    constexpr const T& operator*() const & { return reference(); }
2374
    T& operator*() & {
2375
        assert(this->engaged_);
2376
        return reference();
2377
    }
2378
    constexpr const T&& operator*() const && {
2379
        return phmap::move(reference());
2380
    }
2381
    T&& operator*() && {
2382
        assert(this->engaged_);
2383
        return std::move(reference());
2384
    }
2385
2386
    // optional::operator bool()
2387
    //
2388
    // Returns false if and only if the `optional` is empty.
2389
    //
2390
    //   if (opt) {
2391
    //     // do something with opt.value();
2392
    //   } else {
2393
    //     // opt is empty.
2394
    //   }
2395
    //
2396
    constexpr explicit operator bool() const noexcept { return this->engaged_; }
2397
2398
    // optional::has_value()
2399
    //
2400
    // Determines whether the `optional` contains a value. Returns `false` if and
2401
    // only if `*this` is empty.
2402
    constexpr bool has_value() const noexcept { return this->engaged_; }
2403
2404
// Suppress bogus warning on MSVC: MSVC complains call to reference() after
2405
// throw_bad_optional_access() is unreachable.
2406
#ifdef _MSC_VER
2407
    #pragma warning(push)
2408
    #pragma warning(disable : 4702)
2409
#endif  // _MSC_VER
2410
    // optional::value()
2411
    //
2412
    // Returns a reference to an `optional`s underlying value. The constness
2413
    // and lvalue/rvalue-ness of the `optional` is preserved to the view of
2414
    // the `T` sub-object. Throws `phmap::bad_optional_access` when the `optional`
2415
    // is empty.
2416
    constexpr const T& value() const & {
2417
        return static_cast<bool>(*this)
2418
            ? reference()
2419
            : (optional_internal::throw_bad_optional_access(), reference());
2420
    }
2421
    T& value() & {
2422
        return static_cast<bool>(*this)
2423
            ? reference()
2424
            : (optional_internal::throw_bad_optional_access(), reference());
2425
    }
2426
    T&& value() && {  // NOLINT(build/c++11)
2427
        return std::move(
2428
            static_cast<bool>(*this)
2429
            ? reference()
2430
            : (optional_internal::throw_bad_optional_access(), reference()));
2431
    }
2432
    constexpr const T&& value() const && {  // NOLINT(build/c++11)
2433
        return phmap::move(
2434
            static_cast<bool>(*this)
2435
            ? reference()
2436
            : (optional_internal::throw_bad_optional_access(), reference()));
2437
    }
2438
#ifdef _MSC_VER
2439
    #pragma warning(pop)
2440
#endif  // _MSC_VER
2441
2442
    // optional::value_or()
2443
    //
2444
    // Returns either the value of `T` or a passed default `v` if the `optional`
2445
    // is empty.
2446
    template <typename U>
2447
    constexpr T value_or(U&& v) const& {
2448
        static_assert(std::is_copy_constructible<value_type>::value,
2449
                      "optional<T>::value_or: T must by copy constructible");
2450
        static_assert(std::is_convertible<U&&, value_type>::value,
2451
                      "optional<T>::value_or: U must be convertible to T");
2452
        return static_cast<bool>(*this)
2453
            ? **this
2454
            : static_cast<T>(phmap::forward<U>(v));
2455
    }
2456
    template <typename U>
2457
    T value_or(U&& v) && {  // NOLINT(build/c++11)
2458
        static_assert(std::is_move_constructible<value_type>::value,
2459
                      "optional<T>::value_or: T must by move constructible");
2460
        static_assert(std::is_convertible<U&&, value_type>::value,
2461
                      "optional<T>::value_or: U must be convertible to T");
2462
        return static_cast<bool>(*this) ? std::move(**this)
2463
            : static_cast<T>(std::forward<U>(v));
2464
    }
2465
2466
private:
2467
    // Private accessors for internal storage viewed as reference to T.
2468
    constexpr const T& reference() const { return this->data_; }
2469
    T& reference() { return this->data_; }
2470
2471
    // T constraint checks.  You can't have an optional of nullopt_t, in_place_t
2472
    // or a reference.
2473
    static_assert(
2474
        !std::is_same<nullopt_t, typename std::remove_cv<T>::type>::value,
2475
        "optional<nullopt_t> is not allowed.");
2476
    static_assert(
2477
        !std::is_same<in_place_t, typename std::remove_cv<T>::type>::value,
2478
        "optional<in_place_t> is not allowed.");
2479
    static_assert(!std::is_reference<T>::value,
2480
                  "optional<reference> is not allowed.");
2481
};
2482
2483
// Non-member functions
2484
2485
// swap()
2486
//
2487
// Performs a swap between two `phmap::optional` objects, using standard
2488
// semantics.
2489
//
2490
// NOTE: we assume `is_swappable()` is always `true`. A compile error will
2491
// result if this is not the case.
2492
template <typename T,
2493
          typename std::enable_if<std::is_move_constructible<T>::value,
2494
                                  bool>::type = false>
2495
void swap(optional<T>& a, optional<T>& b) noexcept(noexcept(a.swap(b))) {
2496
    a.swap(b);
2497
}
2498
2499
// make_optional()
2500
//
2501
// Creates a non-empty `optional<T>` where the type of `T` is deduced. An
2502
// `phmap::optional` can also be explicitly instantiated with
2503
// `make_optional<T>(v)`.
2504
//
2505
// Note: `make_optional()` constructions may be declared `constexpr` for
2506
// trivially copyable types `T`. Non-trivial types require copy elision
2507
// support in C++17 for `make_optional` to support `constexpr` on such
2508
// non-trivial types.
2509
//
2510
// Example:
2511
//
2512
//   constexpr phmap::optional<int> opt = phmap::make_optional(1);
2513
//   static_assert(opt.value() == 1, "");
2514
template <typename T>
2515
constexpr optional<typename std::decay<T>::type> make_optional(T&& v) {
2516
    return optional<typename std::decay<T>::type>(phmap::forward<T>(v));
2517
}
2518
2519
template <typename T, typename... Args>
2520
constexpr optional<T> make_optional(Args&&... args) {
2521
    return optional<T>(in_place_t(), phmap::forward<Args>(args)...);
2522
}
2523
2524
template <typename T, typename U, typename... Args>
2525
constexpr optional<T> make_optional(std::initializer_list<U> il,
2526
                                    Args&&... args) {
2527
    return optional<T>(in_place_t(), il,
2528
                       phmap::forward<Args>(args)...);
2529
}
2530
2531
// Relational operators [optional.relops]
2532
2533
// Empty optionals are considered equal to each other and less than non-empty
2534
// optionals. Supports relations between optional<T> and optional<U>, between
2535
// optional<T> and U, and between optional<T> and nullopt.
2536
//
2537
// Note: We're careful to support T having non-bool relationals.
2538
2539
// Requires: The expression, e.g. "*x == *y" shall be well-formed and its result
2540
// shall be convertible to bool.
2541
// The C++17 (N4606) "Returns:" statements are translated into
2542
// code in an obvious way here, and the original text retained as function docs.
2543
// Returns: If bool(x) != bool(y), false; otherwise if bool(x) == false, true;
2544
// otherwise *x == *y.
2545
template <typename T, typename U>
2546
constexpr auto operator==(const optional<T>& x, const optional<U>& y)
2547
    -> decltype(optional_internal::convertible_to_bool(*x == *y)) {
2548
    return static_cast<bool>(x) != static_cast<bool>(y)
2549
             ? false
2550
             : static_cast<bool>(x) == false ? true
2551
                                             : static_cast<bool>(*x == *y);
2552
}
2553
2554
// Returns: If bool(x) != bool(y), true; otherwise, if bool(x) == false, false;
2555
// otherwise *x != *y.
2556
template <typename T, typename U>
2557
constexpr auto operator!=(const optional<T>& x, const optional<U>& y)
2558
    -> decltype(optional_internal::convertible_to_bool(*x != *y)) {
2559
    return static_cast<bool>(x) != static_cast<bool>(y)
2560
             ? true
2561
             : static_cast<bool>(x) == false ? false
2562
                                             : static_cast<bool>(*x != *y);
2563
}
2564
// Returns: If !y, false; otherwise, if !x, true; otherwise *x < *y.
2565
template <typename T, typename U>
2566
constexpr auto operator<(const optional<T>& x, const optional<U>& y)
2567
    -> decltype(optional_internal::convertible_to_bool(*x < *y)) {
2568
    return !y ? false : !x ? true : static_cast<bool>(*x < *y);
2569
}
2570
// Returns: If !x, false; otherwise, if !y, true; otherwise *x > *y.
2571
template <typename T, typename U>
2572
constexpr auto operator>(const optional<T>& x, const optional<U>& y)
2573
    -> decltype(optional_internal::convertible_to_bool(*x > *y)) {
2574
    return !x ? false : !y ? true : static_cast<bool>(*x > *y);
2575
}
2576
// Returns: If !x, true; otherwise, if !y, false; otherwise *x <= *y.
2577
template <typename T, typename U>
2578
constexpr auto operator<=(const optional<T>& x, const optional<U>& y)
2579
    -> decltype(optional_internal::convertible_to_bool(*x <= *y)) {
2580
    return !x ? true : !y ? false : static_cast<bool>(*x <= *y);
2581
}
2582
// Returns: If !y, true; otherwise, if !x, false; otherwise *x >= *y.
2583
template <typename T, typename U>
2584
constexpr auto operator>=(const optional<T>& x, const optional<U>& y)
2585
    -> decltype(optional_internal::convertible_to_bool(*x >= *y)) {
2586
    return !y ? true : !x ? false : static_cast<bool>(*x >= *y);
2587
}
2588
2589
// Comparison with nullopt [optional.nullops]
2590
// The C++17 (N4606) "Returns:" statements are used directly here.
2591
template <typename T>
2592
constexpr bool operator==(const optional<T>& x, nullopt_t) noexcept {
2593
    return !x;
2594
}
2595
template <typename T>
2596
constexpr bool operator==(nullopt_t, const optional<T>& x) noexcept {
2597
    return !x;
2598
}
2599
template <typename T>
2600
constexpr bool operator!=(const optional<T>& x, nullopt_t) noexcept {
2601
    return static_cast<bool>(x);
2602
}
2603
template <typename T>
2604
constexpr bool operator!=(nullopt_t, const optional<T>& x) noexcept {
2605
    return static_cast<bool>(x);
2606
}
2607
template <typename T>
2608
constexpr bool operator<(const optional<T>&, nullopt_t) noexcept {
2609
    return false;
2610
}
2611
template <typename T>
2612
constexpr bool operator<(nullopt_t, const optional<T>& x) noexcept {
2613
    return static_cast<bool>(x);
2614
}
2615
template <typename T>
2616
constexpr bool operator<=(const optional<T>& x, nullopt_t) noexcept {
2617
    return !x;
2618
}
2619
template <typename T>
2620
constexpr bool operator<=(nullopt_t, const optional<T>&) noexcept {
2621
    return true;
2622
}
2623
template <typename T>
2624
constexpr bool operator>(const optional<T>& x, nullopt_t) noexcept {
2625
    return static_cast<bool>(x);
2626
}
2627
template <typename T>
2628
constexpr bool operator>(nullopt_t, const optional<T>&) noexcept {
2629
    return false;
2630
}
2631
template <typename T>
2632
constexpr bool operator>=(const optional<T>&, nullopt_t) noexcept {
2633
    return true;
2634
}
2635
template <typename T>
2636
constexpr bool operator>=(nullopt_t, const optional<T>& x) noexcept {
2637
    return !x;
2638
}
2639
2640
// Comparison with T [optional.comp_with_t]
2641
2642
// Requires: The expression, e.g. "*x == v" shall be well-formed and its result
2643
// shall be convertible to bool.
2644
// The C++17 (N4606) "Equivalent to:" statements are used directly here.
2645
template <typename T, typename U>
2646
constexpr auto operator==(const optional<T>& x, const U& v)
2647
    -> decltype(optional_internal::convertible_to_bool(*x == v)) {
2648
    return static_cast<bool>(x) ? static_cast<bool>(*x == v) : false;
2649
}
2650
template <typename T, typename U>
2651
constexpr auto operator==(const U& v, const optional<T>& x)
2652
    -> decltype(optional_internal::convertible_to_bool(v == *x)) {
2653
    return static_cast<bool>(x) ? static_cast<bool>(v == *x) : false;
2654
}
2655
template <typename T, typename U>
2656
constexpr auto operator!=(const optional<T>& x, const U& v)
2657
    -> decltype(optional_internal::convertible_to_bool(*x != v)) {
2658
    return static_cast<bool>(x) ? static_cast<bool>(*x != v) : true;
2659
}
2660
template <typename T, typename U>
2661
constexpr auto operator!=(const U& v, const optional<T>& x)
2662
    -> decltype(optional_internal::convertible_to_bool(v != *x)) {
2663
    return static_cast<bool>(x) ? static_cast<bool>(v != *x) : true;
2664
}
2665
template <typename T, typename U>
2666
constexpr auto operator<(const optional<T>& x, const U& v)
2667
    -> decltype(optional_internal::convertible_to_bool(*x < v)) {
2668
    return static_cast<bool>(x) ? static_cast<bool>(*x < v) : true;
2669
}
2670
template <typename T, typename U>
2671
constexpr auto operator<(const U& v, const optional<T>& x)
2672
    -> decltype(optional_internal::convertible_to_bool(v < *x)) {
2673
    return static_cast<bool>(x) ? static_cast<bool>(v < *x) : false;
2674
}
2675
template <typename T, typename U>
2676
constexpr auto operator<=(const optional<T>& x, const U& v)
2677
    -> decltype(optional_internal::convertible_to_bool(*x <= v)) {
2678
    return static_cast<bool>(x) ? static_cast<bool>(*x <= v) : true;
2679
}
2680
template <typename T, typename U>
2681
constexpr auto operator<=(const U& v, const optional<T>& x)
2682
    -> decltype(optional_internal::convertible_to_bool(v <= *x)) {
2683
    return static_cast<bool>(x) ? static_cast<bool>(v <= *x) : false;
2684
}
2685
template <typename T, typename U>
2686
constexpr auto operator>(const optional<T>& x, const U& v)
2687
    -> decltype(optional_internal::convertible_to_bool(*x > v)) {
2688
    return static_cast<bool>(x) ? static_cast<bool>(*x > v) : false;
2689
}
2690
template <typename T, typename U>
2691
constexpr auto operator>(const U& v, const optional<T>& x)
2692
    -> decltype(optional_internal::convertible_to_bool(v > *x)) {
2693
    return static_cast<bool>(x) ? static_cast<bool>(v > *x) : true;
2694
}
2695
template <typename T, typename U>
2696
constexpr auto operator>=(const optional<T>& x, const U& v)
2697
    -> decltype(optional_internal::convertible_to_bool(*x >= v)) {
2698
    return static_cast<bool>(x) ? static_cast<bool>(*x >= v) : false;
2699
}
2700
template <typename T, typename U>
2701
constexpr auto operator>=(const U& v, const optional<T>& x)
2702
    -> decltype(optional_internal::convertible_to_bool(v >= *x)) {
2703
    return static_cast<bool>(x) ? static_cast<bool>(v >= *x) : true;
2704
}
2705
2706
}  // namespace phmap
2707
2708
namespace std {
2709
2710
// std::hash specialization for phmap::optional.
2711
template <typename T>
2712
struct hash<phmap::optional<T> >
2713
    : phmap::optional_internal::optional_hash_base<T> {};
2714
2715
}  // namespace std
2716
2717
#endif
2718
2719
// -----------------------------------------------------------------------------
2720
//          common.h
2721
// -----------------------------------------------------------------------------
2722
namespace phmap {
2723
namespace priv {
2724
2725
template <class, class = void>
2726
struct IsTransparent : std::false_type {};
2727
template <class T>
2728
struct IsTransparent<T, phmap::void_t<typename T::is_transparent>>
2729
    : std::true_type {};
2730
2731
template <bool is_transparent>
2732
struct KeyArg 
2733
{
2734
    // Transparent. Forward `K`.
2735
    template <typename K, typename key_type>
2736
    using type = K;
2737
};
2738
2739
template <>
2740
struct KeyArg<false> 
2741
{
2742
    // Not transparent. Always use `key_type`.
2743
    template <typename K, typename key_type>
2744
    using type = key_type;
2745
};
2746
2747
#ifdef _MSC_VER
2748
    #pragma warning(push)  
2749
    //  warning C4820: '6' bytes padding added after data member
2750
    #pragma warning(disable : 4820)
2751
#endif
2752
2753
// The node_handle concept from C++17.
2754
// We specialize node_handle for sets and maps. node_handle_base holds the
2755
// common API of both.
2756
// -----------------------------------------------------------------------
2757
template <typename PolicyTraits, typename Alloc>
2758
class node_handle_base 
2759
{
2760
protected:
2761
    using slot_type = typename PolicyTraits::slot_type;
2762
2763
public:
2764
    using allocator_type = Alloc;
2765
2766
    constexpr node_handle_base() {}
2767
2768
    node_handle_base(node_handle_base&& other) noexcept {
2769
        *this = std::move(other);
2770
    }
2771
2772
    ~node_handle_base() { destroy(); }
2773
2774
    node_handle_base& operator=(node_handle_base&& other) noexcept {
2775
        destroy();
2776
        if (!other.empty()) {
2777
            alloc_ = other.alloc_;
2778
            PolicyTraits::transfer(alloc(), slot(), other.slot());
2779
            other.reset();
2780
        }
2781
        return *this;
2782
    }
2783
2784
    bool empty() const noexcept { return !alloc_; }
2785
    explicit operator bool() const noexcept { return !empty(); }
2786
    allocator_type get_allocator() const { return *alloc_; }
2787
2788
protected:
2789
    friend struct CommonAccess;
2790
2791
    struct transfer_tag_t {};
2792
    node_handle_base(transfer_tag_t, const allocator_type& a, slot_type* s)
2793
        : alloc_(a) {
2794
        PolicyTraits::transfer(alloc(), slot(), s);
2795
    }
2796
    
2797
    struct move_tag_t {};
2798
    node_handle_base(move_tag_t, const allocator_type& a, slot_type* s)
2799
        : alloc_(a) {
2800
        PolicyTraits::construct(alloc(), slot(), s);
2801
    }
2802
2803
    node_handle_base(const allocator_type& a, slot_type* s) : alloc_(a) {
2804
        PolicyTraits::transfer(alloc(), slot(), s);
2805
    }
2806
2807
    //node_handle_base(const node_handle_base&) = delete;
2808
    //node_handle_base& operator=(const node_handle_base&) = delete;
2809
2810
    void destroy() {
2811
        if (!empty()) {
2812
            PolicyTraits::destroy(alloc(), slot());
2813
            reset();
2814
        }
2815
    }
2816
2817
    void reset() {
2818
        assert(alloc_.has_value());
2819
        alloc_ = phmap::nullopt;
2820
    }
2821
2822
    slot_type* slot() const {
2823
        assert(!empty());
2824
        return reinterpret_cast<slot_type*>(std::addressof(slot_space_));
2825
    }
2826
2827
    allocator_type* alloc() { return std::addressof(*alloc_); }
2828
2829
private:
2830
    phmap::optional<allocator_type> alloc_;
2831
    mutable phmap::aligned_storage_t<sizeof(slot_type), alignof(slot_type)> slot_space_;
2832
};
2833
2834
#ifdef _MSC_VER
2835
     #pragma warning(pop)  
2836
#endif
2837
2838
// For sets.
2839
// ---------
2840
template <typename Policy, typename PolicyTraits, typename Alloc,
2841
          typename = void>
2842
class node_handle : public node_handle_base<PolicyTraits, Alloc> 
2843
{
2844
    using Base = node_handle_base<PolicyTraits, Alloc>;
2845
2846
public:
2847
    using value_type = typename PolicyTraits::value_type;
2848
2849
    constexpr node_handle() {}
2850
2851
    value_type& value() const { return PolicyTraits::element(this->slot()); }
2852
2853
    value_type& key() const { return PolicyTraits::element(this->slot()); }
2854
2855
private:
2856
    friend struct CommonAccess;
2857
2858
    using Base::Base;
2859
};
2860
2861
// For maps.
2862
// ---------
2863
template <typename Policy, typename PolicyTraits, typename Alloc>
2864
class node_handle<Policy, PolicyTraits, Alloc,
2865
                  phmap::void_t<typename Policy::mapped_type>>
2866
    : public node_handle_base<PolicyTraits, Alloc> 
2867
{
2868
    using Base = node_handle_base<PolicyTraits, Alloc>;
2869
    using slot_type = typename PolicyTraits::slot_type;
2870
2871
public:
2872
    using key_type = typename Policy::key_type;
2873
    using mapped_type = typename Policy::mapped_type;
2874
2875
    constexpr node_handle() {}
2876
2877
    auto key() const -> decltype(PolicyTraits::key(this->slot())) {
2878
        return PolicyTraits::key(this->slot());
2879
    }
2880
2881
    mapped_type& mapped() const {
2882
        return PolicyTraits::value(&PolicyTraits::element(this->slot()));
2883
    }
2884
2885
private:
2886
    friend struct CommonAccess;
2887
2888
    using Base::Base;
2889
};
2890
2891
// Provide access to non-public node-handle functions.
2892
struct CommonAccess 
2893
{
2894
    template <typename Node>
2895
    static auto GetSlot(const Node& node) -> decltype(node.slot()) {
2896
        return node.slot();
2897
    }
2898
2899
    template <typename Node>
2900
    static void Destroy(Node* node) {
2901
        node->destroy();
2902
    }
2903
2904
    template <typename Node>
2905
    static void Reset(Node* node) {
2906
        node->reset();
2907
    }
2908
2909
    template <typename T, typename... Args>
2910
    static T Make(Args&&... args) {
2911
        return T(std::forward<Args>(args)...);
2912
    }
2913
2914
    template <typename T, typename... Args>
2915
    static T Transfer(Args&&... args) {
2916
        return T(typename T::transfer_tag_t{}, std::forward<Args>(args)...);
2917
    }
2918
2919
    template <typename T, typename... Args>
2920
    static T Move(Args&&... args) {
2921
        return T(typename T::move_tag_t{}, std::forward<Args>(args)...);
2922
    }
2923
};
2924
2925
// Implement the insert_return_type<> concept of C++17.
2926
template <class Iterator, class NodeType>
2927
struct InsertReturnType 
2928
{
2929
    Iterator position;
2930
    bool inserted;
2931
    NodeType node;
2932
};
2933
2934
}  // namespace priv
2935
}  // namespace phmap
2936
2937
2938
#ifdef ADDRESS_SANITIZER
2939
    #include <sanitizer/asan_interface.h>
2940
#endif
2941
2942
// ---------------------------------------------------------------------------
2943
//  span.h
2944
// ---------------------------------------------------------------------------
2945
2946
namespace phmap {
2947
2948
template <typename T>
2949
class Span;
2950
2951
namespace span_internal {
2952
// A constexpr min function
2953
0
constexpr size_t Min(size_t a, size_t b) noexcept { return a < b ? a : b; }
2954
2955
// Wrappers for access to container data pointers.
2956
template <typename C>
2957
constexpr auto GetDataImpl(C& c, char) noexcept  // NOLINT(runtime/references)
2958
    -> decltype(c.data()) {
2959
  return c.data();
2960
}
2961
2962
// Before C++17, std::string::data returns a const char* in all cases.
2963
inline char* GetDataImpl(std::string& s,  // NOLINT(runtime/references)
2964
0
                         int) noexcept {
2965
0
  return &s[0];
2966
0
}
2967
2968
template <typename C>
2969
constexpr auto GetData(C& c) noexcept  // NOLINT(runtime/references)
2970
    -> decltype(GetDataImpl(c, 0)) {
2971
  return GetDataImpl(c, 0);
2972
}
2973
2974
// Detection idioms for size() and data().
2975
template <typename C>
2976
using HasSize =
2977
    std::is_integral<phmap::decay_t<decltype(std::declval<C&>().size())>>;
2978
2979
// We want to enable conversion from vector<T*> to Span<const T* const> but
2980
// disable conversion from vector<Derived> to Span<Base>. Here we use
2981
// the fact that U** is convertible to Q* const* if and only if Q is the same
2982
// type or a more cv-qualified version of U.  We also decay the result type of
2983
// data() to avoid problems with classes which have a member function data()
2984
// which returns a reference.
2985
template <typename T, typename C>
2986
using HasData =
2987
    std::is_convertible<phmap::decay_t<decltype(GetData(std::declval<C&>()))>*,
2988
                        T* const*>;
2989
2990
// Extracts value type from a Container
2991
template <typename C>
2992
struct ElementType {
2993
  using type = typename phmap::remove_reference_t<C>::value_type;
2994
};
2995
2996
template <typename T, size_t N>
2997
struct ElementType<T (&)[N]> {
2998
  using type = T;
2999
};
3000
3001
template <typename C>
3002
using ElementT = typename ElementType<C>::type;
3003
3004
template <typename T>
3005
using EnableIfMutable =
3006
    typename std::enable_if<!std::is_const<T>::value, int>::type;
3007
3008
template <typename T>
3009
bool EqualImpl(Span<T> a, Span<T> b) {
3010
  static_assert(std::is_const<T>::value, "");
3011
  return std::equal(a.begin(), a.end(), b.begin(), b.end());
3012
}
3013
3014
template <typename T>
3015
bool LessThanImpl(Span<T> a, Span<T> b) {
3016
  static_assert(std::is_const<T>::value, "");
3017
  return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
3018
}
3019
3020
// The `IsConvertible` classes here are needed because of the
3021
// `std::is_convertible` bug in libcxx when compiled with GCC. This build
3022
// configuration is used by Android NDK toolchain. Reference link:
3023
// https://bugs.llvm.org/show_bug.cgi?id=27538.
3024
template <typename From, typename To>
3025
struct IsConvertibleHelper {
3026
  static std::true_type testval(To);
3027
  static std::false_type testval(...);
3028
3029
  using type = decltype(testval(std::declval<From>()));
3030
};
3031
3032
template <typename From, typename To>
3033
struct IsConvertible : IsConvertibleHelper<From, To>::type {};
3034
3035
// TODO(zhangxy): replace `IsConvertible` with `std::is_convertible` once the
3036
// older version of libcxx is not supported.
3037
template <typename From, typename To>
3038
using EnableIfConvertibleToSpanConst =
3039
    typename std::enable_if<IsConvertible<From, Span<const To>>::value>::type;
3040
}  // namespace span_internal
3041
3042
//------------------------------------------------------------------------------
3043
// Span
3044
//------------------------------------------------------------------------------
3045
//
3046
// A `Span` is an "array view" type for holding a view of a contiguous data
3047
// array; the `Span` object does not and cannot own such data itself. A span
3048
// provides an easy way to provide overloads for anything operating on
3049
// contiguous sequences without needing to manage pointers and array lengths
3050
// manually.
3051
3052
// A span is conceptually a pointer (ptr) and a length (size) into an already
3053
// existing array of contiguous memory; the array it represents references the
3054
// elements "ptr[0] .. ptr[size-1]". Passing a properly-constructed `Span`
3055
// instead of raw pointers avoids many issues related to index out of bounds
3056
// errors.
3057
//
3058
// Spans may also be constructed from containers holding contiguous sequences.
3059
// Such containers must supply `data()` and `size() const` methods (e.g
3060
// `std::vector<T>`, `phmap::InlinedVector<T, N>`). All implicit conversions to
3061
// `phmap::Span` from such containers will create spans of type `const T`;
3062
// spans which can mutate their values (of type `T`) must use explicit
3063
// constructors.
3064
//
3065
// A `Span<T>` is somewhat analogous to an `phmap::string_view`, but for an array
3066
// of elements of type `T`. A user of `Span` must ensure that the data being
3067
// pointed to outlives the `Span` itself.
3068
//
3069
// You can construct a `Span<T>` in several ways:
3070
//
3071
//   * Explicitly from a reference to a container type
3072
//   * Explicitly from a pointer and size
3073
//   * Implicitly from a container type (but only for spans of type `const T`)
3074
//   * Using the `MakeSpan()` or `MakeConstSpan()` factory functions.
3075
//
3076
// Examples:
3077
//
3078
//   // Construct a Span explicitly from a container:
3079
//   std::vector<int> v = {1, 2, 3, 4, 5};
3080
//   auto span = phmap::Span<const int>(v);
3081
//
3082
//   // Construct a Span explicitly from a C-style array:
3083
//   int a[5] =  {1, 2, 3, 4, 5};
3084
//   auto span = phmap::Span<const int>(a);
3085
//
3086
//   // Construct a Span implicitly from a container
3087
//   void MyRoutine(phmap::Span<const int> a) {
3088
//     ...
3089
//   }
3090
//   std::vector v = {1,2,3,4,5};
3091
//   MyRoutine(v)                     // convert to Span<const T>
3092
//
3093
// Note that `Span` objects, in addition to requiring that the memory they
3094
// point to remains alive, must also ensure that such memory does not get
3095
// reallocated. Therefore, to avoid undefined behavior, containers with
3096
// associated span views should not invoke operations that may reallocate memory
3097
// (such as resizing) or invalidate iterators into the container.
3098
//
3099
// One common use for a `Span` is when passing arguments to a routine that can
3100
// accept a variety of array types (e.g. a `std::vector`, `phmap::InlinedVector`,
3101
// a C-style array, etc.). Instead of creating overloads for each case, you
3102
// can simply specify a `Span` as the argument to such a routine.
3103
//
3104
// Example:
3105
//
3106
//   void MyRoutine(phmap::Span<const int> a) {
3107
//     ...
3108
//   }
3109
//
3110
//   std::vector v = {1,2,3,4,5};
3111
//   MyRoutine(v);
3112
//
3113
//   phmap::InlinedVector<int, 4> my_inline_vector;
3114
//   MyRoutine(my_inline_vector);
3115
//
3116
//   // Explicit constructor from pointer,size
3117
//   int* my_array = new int[10];
3118
//   MyRoutine(phmap::Span<const int>(my_array, 10));
3119
template <typename T>
3120
class Span 
3121
{
3122
private:
3123
    // Used to determine whether a Span can be constructed from a container of
3124
    // type C.
3125
    template <typename C>
3126
    using EnableIfConvertibleFrom =
3127
        typename std::enable_if<span_internal::HasData<T, C>::value &&
3128
                                span_internal::HasSize<C>::value>::type;
3129
3130
    // Used to SFINAE-enable a function when the slice elements are const.
3131
    template <typename U>
3132
    using EnableIfConstView =
3133
        typename std::enable_if<std::is_const<T>::value, U>::type;
3134
3135
    // Used to SFINAE-enable a function when the slice elements are mutable.
3136
    template <typename U>
3137
    using EnableIfMutableView =
3138
        typename std::enable_if<!std::is_const<T>::value, U>::type;
3139
3140
public:
3141
    using value_type = phmap::remove_cv_t<T>;
3142
    using pointer = T*;
3143
    using const_pointer = const T*;
3144
    using reference = T&;
3145
    using const_reference = const T&;
3146
    using iterator = pointer;
3147
    using const_iterator = const_pointer;
3148
    using reverse_iterator = std::reverse_iterator<iterator>;
3149
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
3150
    using size_type = size_t;
3151
    using difference_type = ptrdiff_t;
3152
3153
    static const size_type npos = ~(size_type(0));
3154
3155
    constexpr Span() noexcept : Span(nullptr, 0) {}
3156
    constexpr Span(pointer array, size_type lgth) noexcept
3157
        : ptr_(array), len_(lgth) {}
3158
3159
    // Implicit conversion constructors
3160
    template <size_t N>
3161
    constexpr Span(T (&a)[N]) noexcept  // NOLINT(runtime/explicit)
3162
        : Span(a, N) {}
3163
3164
    // Explicit reference constructor for a mutable `Span<T>` type. Can be
3165
    // replaced with MakeSpan() to infer the type parameter.
3166
    template <typename V, typename = EnableIfConvertibleFrom<V>,
3167
              typename = EnableIfMutableView<V>>
3168
        explicit Span(V& v) noexcept  // NOLINT(runtime/references)
3169
        : Span(span_internal::GetData(v), v.size()) {}
3170
3171
    // Implicit reference constructor for a read-only `Span<const T>` type
3172
    template <typename V, typename = EnableIfConvertibleFrom<V>,
3173
              typename = EnableIfConstView<V>>
3174
        constexpr Span(const V& v) noexcept  // NOLINT(runtime/explicit)
3175
        : Span(span_internal::GetData(v), v.size()) {}
3176
3177
    // Implicit constructor from an initializer list, making it possible to pass a
3178
    // brace-enclosed initializer list to a function expecting a `Span`. Such
3179
    // spans constructed from an initializer list must be of type `Span<const T>`.
3180
    //
3181
    //   void Process(phmap::Span<const int> x);
3182
    //   Process({1, 2, 3});
3183
    //
3184
    // Note that as always the array referenced by the span must outlive the span.
3185
    // Since an initializer list constructor acts as if it is fed a temporary
3186
    // array (cf. C++ standard [dcl.init.list]/5), it's safe to use this
3187
    // constructor only when the `std::initializer_list` itself outlives the span.
3188
    // In order to meet this requirement it's sufficient to ensure that neither
3189
    // the span nor a copy of it is used outside of the expression in which it's
3190
    // created:
3191
    //
3192
    //   // Assume that this function uses the array directly, not retaining any
3193
    //   // copy of the span or pointer to any of its elements.
3194
    //   void Process(phmap::Span<const int> ints);
3195
    //
3196
    //   // Okay: the std::initializer_list<int> will reference a temporary array
3197
    //   // that isn't destroyed until after the call to Process returns.
3198
    //   Process({ 17, 19 });
3199
    //
3200
    //   // Not okay: the storage used by the std::initializer_list<int> is not
3201
    //   // allowed to be referenced after the first line.
3202
    //   phmap::Span<const int> ints = { 17, 19 };
3203
    //   Process(ints);
3204
    //
3205
    //   // Not okay for the same reason as above: even when the elements of the
3206
    //   // initializer list expression are not temporaries the underlying array
3207
    //   // is, so the initializer list must still outlive the span.
3208
    //   const int foo = 17;
3209
    //   phmap::Span<const int> ints = { foo };
3210
    //   Process(ints);
3211
    //
3212
    template <typename LazyT = T,
3213
              typename = EnableIfConstView<LazyT>>
3214
        Span(
3215
            std::initializer_list<value_type> v) noexcept  // NOLINT(runtime/explicit)
3216
        : Span(v.begin(), v.size()) {}
3217
3218
    // Accessors
3219
3220
    // Span::data()
3221
    //
3222
    // Returns a pointer to the span's underlying array of data (which is held
3223
    // outside the span).
3224
    constexpr pointer data() const noexcept { return ptr_; }
3225
3226
    // Span::size()
3227
    //
3228
    // Returns the size of this span.
3229
    constexpr size_type size() const noexcept { return len_; }
3230
3231
    // Span::length()
3232
    //
3233
    // Returns the length (size) of this span.
3234
    constexpr size_type length() const noexcept { return size(); }
3235
3236
    // Span::empty()
3237
    //
3238
    // Returns a boolean indicating whether or not this span is considered empty.
3239
    constexpr bool empty() const noexcept { return size() == 0; }
3240
3241
    // Span::operator[]
3242
    //
3243
    // Returns a reference to the i'th element of this span.
3244
    constexpr reference operator[](size_type i) const noexcept {
3245
        // MSVC 2015 accepts this as constexpr, but not ptr_[i]
3246
        return *(data() + i);
3247
    }
3248
3249
    // Span::at()
3250
    //
3251
    // Returns a reference to the i'th element of this span.
3252
    constexpr reference at(size_type i) const {
3253
        return PHMAP_PREDICT_TRUE(i < size())  //
3254
            ? *(data() + i)
3255
            : (base_internal::ThrowStdOutOfRange(
3256
                   "Span::at failed bounds check"),
3257
               *(data() + i));
3258
    }
3259
3260
    // Span::front()
3261
    //
3262
    // Returns a reference to the first element of this span.
3263
    constexpr reference front() const noexcept {
3264
        return PHMAP_ASSERT(size() > 0), *data();
3265
    }
3266
3267
    // Span::back()
3268
    //
3269
    // Returns a reference to the last element of this span.
3270
    constexpr reference back() const noexcept {
3271
        return PHMAP_ASSERT(size() > 0), *(data() + size() - 1);
3272
    }
3273
3274
    // Span::begin()
3275
    //
3276
    // Returns an iterator to the first element of this span.
3277
    constexpr iterator begin() const noexcept { return data(); }
3278
3279
    // Span::cbegin()
3280
    //
3281
    // Returns a const iterator to the first element of this span.
3282
    constexpr const_iterator cbegin() const noexcept { return begin(); }
3283
3284
    // Span::end()
3285
    //
3286
    // Returns an iterator to the last element of this span.
3287
    constexpr iterator end() const noexcept { return data() + size(); }
3288
3289
    // Span::cend()
3290
    //
3291
    // Returns a const iterator to the last element of this span.
3292
    constexpr const_iterator cend() const noexcept { return end(); }
3293
3294
    // Span::rbegin()
3295
    //
3296
    // Returns a reverse iterator starting at the last element of this span.
3297
    constexpr reverse_iterator rbegin() const noexcept {
3298
        return reverse_iterator(end());
3299
    }
3300
3301
    // Span::crbegin()
3302
    //
3303
    // Returns a reverse const iterator starting at the last element of this span.
3304
    constexpr const_reverse_iterator crbegin() const noexcept { return rbegin(); }
3305
3306
    // Span::rend()
3307
    //
3308
    // Returns a reverse iterator starting at the first element of this span.
3309
    constexpr reverse_iterator rend() const noexcept {
3310
        return reverse_iterator(begin());
3311
    }
3312
3313
    // Span::crend()
3314
    //
3315
    // Returns a reverse iterator starting at the first element of this span.
3316
    constexpr const_reverse_iterator crend() const noexcept { return rend(); }
3317
3318
    // Span mutations
3319
3320
    // Span::remove_prefix()
3321
    //
3322
    // Removes the first `n` elements from the span.
3323
    void remove_prefix(size_type n) noexcept {
3324
        assert(size() >= n);
3325
        ptr_ += n;
3326
        len_ -= n;
3327
    }
3328
3329
    // Span::remove_suffix()
3330
    //
3331
    // Removes the last `n` elements from the span.
3332
    void remove_suffix(size_type n) noexcept {
3333
        assert(size() >= n);
3334
        len_ -= n;
3335
    }
3336
3337
    // Span::subspan()
3338
    //
3339
    // Returns a `Span` starting at element `pos` and of length `len`. Both `pos`
3340
    // and `len` are of type `size_type` and thus non-negative. Parameter `pos`
3341
    // must be <= size(). Any `len` value that points past the end of the span
3342
    // will be trimmed to at most size() - `pos`. A default `len` value of `npos`
3343
    // ensures the returned subspan continues until the end of the span.
3344
    //
3345
    // Examples:
3346
    //
3347
    //   std::vector<int> vec = {10, 11, 12, 13};
3348
    //   phmap::MakeSpan(vec).subspan(1, 2);  // {11, 12}
3349
    //   phmap::MakeSpan(vec).subspan(2, 8);  // {12, 13}
3350
    //   phmap::MakeSpan(vec).subspan(1);     // {11, 12, 13}
3351
    //   phmap::MakeSpan(vec).subspan(4);     // {}
3352
    //   phmap::MakeSpan(vec).subspan(5);     // throws std::out_of_range
3353
    constexpr Span subspan(size_type pos = 0, size_type len = npos) const {
3354
        return (pos <= size())
3355
            ? Span(data() + pos, span_internal::Min(size() - pos, len))
3356
            : (base_internal::ThrowStdOutOfRange("pos > size()"), Span());
3357
    }
3358
3359
    // Span::first()
3360
    //
3361
    // Returns a `Span` containing first `len` elements. Parameter `len` is of
3362
    // type `size_type` and thus non-negative. `len` value must be <= size().
3363
    //
3364
    // Examples:
3365
    //
3366
    //   std::vector<int> vec = {10, 11, 12, 13};
3367
    //   phmap::MakeSpan(vec).first(1);  // {10}
3368
    //   phmap::MakeSpan(vec).first(3);  // {10, 11, 12}
3369
    //   phmap::MakeSpan(vec).first(5);  // throws std::out_of_range
3370
    constexpr Span first(size_type len) const {
3371
        return (len <= size())
3372
            ? Span(data(), len)
3373
            : (base_internal::ThrowStdOutOfRange("len > size()"), Span());
3374
    }
3375
3376
    // Span::last()
3377
    //
3378
    // Returns a `Span` containing last `len` elements. Parameter `len` is of
3379
    // type `size_type` and thus non-negative. `len` value must be <= size().
3380
    //
3381
    // Examples:
3382
    //
3383
    //   std::vector<int> vec = {10, 11, 12, 13};
3384
    //   phmap::MakeSpan(vec).last(1);  // {13}
3385
    //   phmap::MakeSpan(vec).last(3);  // {11, 12, 13}
3386
    //   phmap::MakeSpan(vec).last(5);  // throws std::out_of_range
3387
    constexpr Span last(size_type len) const {
3388
        return (len <= size())
3389
            ? Span(size() - len + data(), len)
3390
            : (base_internal::ThrowStdOutOfRange("len > size()"), Span());
3391
    }
3392
3393
    // Support for phmap::Hash.
3394
    template <typename H>
3395
    friend H AbslHashValue(H h, Span v) {
3396
        return H::combine(H::combine_contiguous(std::move(h), v.data(), v.size()),
3397
                          v.size());
3398
    }
3399
3400
private:
3401
    pointer ptr_;
3402
    size_type len_;
3403
};
3404
3405
template <typename T>
3406
const typename Span<T>::size_type Span<T>::npos;
3407
3408
// Span relationals
3409
3410
// Equality is compared element-by-element, while ordering is lexicographical.
3411
// We provide three overloads for each operator to cover any combination on the
3412
// left or right hand side of mutable Span<T>, read-only Span<const T>, and
3413
// convertible-to-read-only Span<T>.
3414
// TODO(zhangxy): Due to MSVC overload resolution bug with partial ordering
3415
// template functions, 5 overloads per operator is needed as a workaround. We
3416
// should update them to 3 overloads per operator using non-deduced context like
3417
// string_view, i.e.
3418
// - (Span<T>, Span<T>)
3419
// - (Span<T>, non_deduced<Span<const T>>)
3420
// - (non_deduced<Span<const T>>, Span<T>)
3421
3422
// operator==
3423
template <typename T>
3424
bool operator==(Span<T> a, Span<T> b) {
3425
  return span_internal::EqualImpl<const T>(a, b);
3426
}
3427
3428
template <typename T>
3429
bool operator==(Span<const T> a, Span<T> b) {
3430
  return span_internal::EqualImpl<const T>(a, b);
3431
}
3432
3433
template <typename T>
3434
bool operator==(Span<T> a, Span<const T> b) {
3435
  return span_internal::EqualImpl<const T>(a, b);
3436
}
3437
3438
template <typename T, typename U,
3439
          typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
3440
bool operator==(const U& a, Span<T> b) {
3441
  return span_internal::EqualImpl<const T>(a, b);
3442
}
3443
3444
template <typename T, typename U,
3445
          typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
3446
bool operator==(Span<T> a, const U& b) {
3447
  return span_internal::EqualImpl<const T>(a, b);
3448
}
3449
3450
// operator!=
3451
template <typename T>
3452
bool operator!=(Span<T> a, Span<T> b) {
3453
  return !(a == b);
3454
}
3455
3456
template <typename T>
3457
bool operator!=(Span<const T> a, Span<T> b) {
3458
  return !(a == b);
3459
}
3460
3461
template <typename T>
3462
bool operator!=(Span<T> a, Span<const T> b) {
3463
  return !(a == b);
3464
}
3465
3466
template <typename T, typename U,
3467
          typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
3468
bool operator!=(const U& a, Span<T> b) {
3469
  return !(a == b);
3470
}
3471
3472
template <typename T, typename U,
3473
          typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
3474
bool operator!=(Span<T> a, const U& b) {
3475
  return !(a == b);
3476
}
3477
3478
// operator<
3479
template <typename T>
3480
bool operator<(Span<T> a, Span<T> b) {
3481
  return span_internal::LessThanImpl<const T>(a, b);
3482
}
3483
3484
template <typename T>
3485
bool operator<(Span<const T> a, Span<T> b) {
3486
  return span_internal::LessThanImpl<const T>(a, b);
3487
}
3488
3489
template <typename T>
3490
bool operator<(Span<T> a, Span<const T> b) {
3491
  return span_internal::LessThanImpl<const T>(a, b);
3492
}
3493
3494
template <typename T, typename U,
3495
          typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
3496
bool operator<(const U& a, Span<T> b) {
3497
  return span_internal::LessThanImpl<const T>(a, b);
3498
}
3499
3500
template <typename T, typename U,
3501
          typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
3502
bool operator<(Span<T> a, const U& b) {
3503
  return span_internal::LessThanImpl<const T>(a, b);
3504
}
3505
3506
// operator>
3507
template <typename T>
3508
bool operator>(Span<T> a, Span<T> b) {
3509
  return b < a;
3510
}
3511
3512
template <typename T>
3513
bool operator>(Span<const T> a, Span<T> b) {
3514
  return b < a;
3515
}
3516
3517
template <typename T>
3518
bool operator>(Span<T> a, Span<const T> b) {
3519
  return b < a;
3520
}
3521
3522
template <typename T, typename U,
3523
          typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
3524
bool operator>(const U& a, Span<T> b) {
3525
  return b < a;
3526
}
3527
3528
template <typename T, typename U,
3529
          typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
3530
bool operator>(Span<T> a, const U& b) {
3531
  return b < a;
3532
}
3533
3534
// operator<=
3535
template <typename T>
3536
bool operator<=(Span<T> a, Span<T> b) {
3537
  return !(b < a);
3538
}
3539
3540
template <typename T>
3541
bool operator<=(Span<const T> a, Span<T> b) {
3542
  return !(b < a);
3543
}
3544
3545
template <typename T>
3546
bool operator<=(Span<T> a, Span<const T> b) {
3547
  return !(b < a);
3548
}
3549
3550
template <typename T, typename U,
3551
          typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
3552
bool operator<=(const U& a, Span<T> b) {
3553
  return !(b < a);
3554
}
3555
3556
template <typename T, typename U,
3557
          typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
3558
bool operator<=(Span<T> a, const U& b) {
3559
  return !(b < a);
3560
}
3561
3562
// operator>=
3563
template <typename T>
3564
bool operator>=(Span<T> a, Span<T> b) {
3565
  return !(a < b);
3566
}
3567
3568
template <typename T>
3569
bool operator>=(Span<const T> a, Span<T> b) {
3570
  return !(a < b);
3571
}
3572
3573
template <typename T>
3574
bool operator>=(Span<T> a, Span<const T> b) {
3575
  return !(a < b);
3576
}
3577
3578
template <typename T, typename U,
3579
          typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
3580
bool operator>=(const U& a, Span<T> b) {
3581
  return !(a < b);
3582
}
3583
3584
template <typename T, typename U,
3585
          typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
3586
bool operator>=(Span<T> a, const U& b) {
3587
  return !(a < b);
3588
}
3589
3590
// MakeSpan()
3591
//
3592
// Constructs a mutable `Span<T>`, deducing `T` automatically from either a
3593
// container or pointer+size.
3594
//
3595
// Because a read-only `Span<const T>` is implicitly constructed from container
3596
// types regardless of whether the container itself is a const container,
3597
// constructing mutable spans of type `Span<T>` from containers requires
3598
// explicit constructors. The container-accepting version of `MakeSpan()`
3599
// deduces the type of `T` by the constness of the pointer received from the
3600
// container's `data()` member. Similarly, the pointer-accepting version returns
3601
// a `Span<const T>` if `T` is `const`, and a `Span<T>` otherwise.
3602
//
3603
// Examples:
3604
//
3605
//   void MyRoutine(phmap::Span<MyComplicatedType> a) {
3606
//     ...
3607
//   };
3608
//   // my_vector is a container of non-const types
3609
//   std::vector<MyComplicatedType> my_vector;
3610
//
3611
//   // Constructing a Span implicitly attempts to create a Span of type
3612
//   // `Span<const T>`
3613
//   MyRoutine(my_vector);                // error, type mismatch
3614
//
3615
//   // Explicitly constructing the Span is verbose
3616
//   MyRoutine(phmap::Span<MyComplicatedType>(my_vector));
3617
//
3618
//   // Use MakeSpan() to make an phmap::Span<T>
3619
//   MyRoutine(phmap::MakeSpan(my_vector));
3620
//
3621
//   // Construct a span from an array ptr+size
3622
//   phmap::Span<T> my_span() {
3623
//     return phmap::MakeSpan(&array[0], num_elements_);
3624
//   }
3625
//
3626
template <int&... ExplicitArgumentBarrier, typename T>
3627
constexpr Span<T> MakeSpan(T* ptr, size_t size) noexcept {
3628
  return Span<T>(ptr, size);
3629
}
3630
3631
template <int&... ExplicitArgumentBarrier, typename T>
3632
Span<T> MakeSpan(T* begin, T* end) noexcept {
3633
  return PHMAP_ASSERT(begin <= end), Span<T>(begin, end - begin);
3634
}
3635
3636
template <int&... ExplicitArgumentBarrier, typename C>
3637
constexpr auto MakeSpan(C& c) noexcept  // NOLINT(runtime/references)
3638
    -> decltype(phmap::MakeSpan(span_internal::GetData(c), c.size())) {
3639
  return MakeSpan(span_internal::GetData(c), c.size());
3640
}
3641
3642
template <int&... ExplicitArgumentBarrier, typename T, size_t N>
3643
constexpr Span<T> MakeSpan(T (&array)[N]) noexcept {
3644
  return Span<T>(array, N);
3645
}
3646
3647
// MakeConstSpan()
3648
//
3649
// Constructs a `Span<const T>` as with `MakeSpan`, deducing `T` automatically,
3650
// but always returning a `Span<const T>`.
3651
//
3652
// Examples:
3653
//
3654
//   void ProcessInts(phmap::Span<const int> some_ints);
3655
//
3656
//   // Call with a pointer and size.
3657
//   int array[3] = { 0, 0, 0 };
3658
//   ProcessInts(phmap::MakeConstSpan(&array[0], 3));
3659
//
3660
//   // Call with a [begin, end) pair.
3661
//   ProcessInts(phmap::MakeConstSpan(&array[0], &array[3]));
3662
//
3663
//   // Call directly with an array.
3664
//   ProcessInts(phmap::MakeConstSpan(array));
3665
//
3666
//   // Call with a contiguous container.
3667
//   std::vector<int> some_ints = ...;
3668
//   ProcessInts(phmap::MakeConstSpan(some_ints));
3669
//   ProcessInts(phmap::MakeConstSpan(std::vector<int>{ 0, 0, 0 }));
3670
//
3671
template <int&... ExplicitArgumentBarrier, typename T>
3672
constexpr Span<const T> MakeConstSpan(T* ptr, size_t size) noexcept {
3673
  return Span<const T>(ptr, size);
3674
}
3675
3676
template <int&... ExplicitArgumentBarrier, typename T>
3677
Span<const T> MakeConstSpan(T* begin, T* end) noexcept {
3678
  return PHMAP_ASSERT(begin <= end), Span<const T>(begin, end - begin);
3679
}
3680
3681
template <int&... ExplicitArgumentBarrier, typename C>
3682
constexpr auto MakeConstSpan(const C& c) noexcept -> decltype(MakeSpan(c)) {
3683
  return MakeSpan(c);
3684
}
3685
3686
template <int&... ExplicitArgumentBarrier, typename T, size_t N>
3687
constexpr Span<const T> MakeConstSpan(const T (&array)[N]) noexcept {
3688
  return Span<const T>(array, N);
3689
}
3690
}  // namespace phmap
3691
3692
// ---------------------------------------------------------------------------
3693
//  layout.h
3694
// ---------------------------------------------------------------------------
3695
namespace phmap {
3696
namespace priv {
3697
3698
// A type wrapper that instructs `Layout` to use the specific alignment for the
3699
// array. `Layout<..., Aligned<T, N>, ...>` has exactly the same API
3700
// and behavior as `Layout<..., T, ...>` except that the first element of the
3701
// array of `T` is aligned to `N` (the rest of the elements follow without
3702
// padding).
3703
//
3704
// Requires: `N >= alignof(T)` and `N` is a power of 2.
3705
template <class T, size_t N>
3706
struct Aligned;
3707
3708
namespace internal_layout {
3709
3710
template <class T>
3711
struct NotAligned {};
3712
3713
template <class T, size_t N>
3714
struct NotAligned<const Aligned<T, N>> {
3715
  static_assert(sizeof(T) == 0, "Aligned<T, N> cannot be const-qualified");
3716
};
3717
3718
template <size_t>
3719
using IntToSize = size_t;
3720
3721
template <class>
3722
using TypeToSize = size_t;
3723
3724
template <class T>
3725
struct Type : NotAligned<T> {
3726
    using type = T;
3727
};
3728
3729
template <class T, size_t N>
3730
struct Type<Aligned<T, N>> {
3731
    using type = T;
3732
};
3733
3734
template <class T>
3735
struct SizeOf : NotAligned<T>, std::integral_constant<size_t, sizeof(T)> {};
3736
3737
template <class T, size_t N>
3738
struct SizeOf<Aligned<T, N>> : std::integral_constant<size_t, sizeof(T)> {};
3739
3740
// Note: workaround for https://gcc.gnu.org/PR88115
3741
template <class T>
3742
struct AlignOf : NotAligned<T> {
3743
    static constexpr size_t value = alignof(T);
3744
};
3745
3746
template <class T, size_t N>
3747
struct AlignOf<Aligned<T, N>> {
3748
    static_assert(N % alignof(T) == 0,
3749
                  "Custom alignment can't be lower than the type's alignment");
3750
    static constexpr size_t value = N;
3751
};
3752
3753
// Does `Ts...` contain `T`?
3754
template <class T, class... Ts>
3755
using Contains = phmap::disjunction<std::is_same<T, Ts>...>;
3756
3757
template <class From, class To>
3758
using CopyConst =
3759
    typename std::conditional<std::is_const<From>::value, const To, To>::type;
3760
3761
// Note: We're not qualifying this with phmap:: because it doesn't compile under
3762
// MSVC.
3763
template <class T>
3764
using SliceType = Span<T>;
3765
3766
// This namespace contains no types. It prevents functions defined in it from
3767
// being found by ADL.
3768
namespace adl_barrier {
3769
3770
template <class Needle, class... Ts>
3771
constexpr size_t Find(Needle, Needle, Ts...) {
3772
    static_assert(!Contains<Needle, Ts...>(), "Duplicate element type");
3773
    return 0;
3774
}
3775
3776
template <class Needle, class T, class... Ts>
3777
constexpr size_t Find(Needle, T, Ts...) {
3778
  return adl_barrier::Find(Needle(), Ts()...) + 1;
3779
}
3780
3781
0
constexpr bool IsPow2(size_t n) { return !(n & (n - 1)); }
3782
3783
// Returns `q * m` for the smallest `q` such that `q * m >= n`.
3784
// Requires: `m` is a power of two. It's enforced by IsLegalElementType below.
3785
8.85k
constexpr size_t Align(size_t n, size_t m) { return (n + m - 1) & ~(m - 1); }
3786
3787
0
constexpr size_t Min(size_t a, size_t b) { return b < a ? b : a; }
3788
3789
0
constexpr size_t Max(size_t a) { return a; }
3790
3791
template <class... Ts>
3792
0
constexpr size_t Max(size_t a, size_t b, Ts... rest) {
3793
0
    return adl_barrier::Max(b < a ? a : b, rest...);
3794
0
}
3795
3796
}  // namespace adl_barrier
3797
3798
template <bool C>
3799
using EnableIf = typename std::enable_if<C, int>::type;
3800
3801
// Can `T` be a template argument of `Layout`?
3802
// ---------------------------------------------------------------------------
3803
template <class T>
3804
using IsLegalElementType = std::integral_constant<
3805
    bool, !std::is_reference<T>::value && !std::is_volatile<T>::value &&
3806
              !std::is_reference<typename Type<T>::type>::value &&
3807
              !std::is_volatile<typename Type<T>::type>::value &&
3808
              adl_barrier::IsPow2(AlignOf<T>::value)>;
3809
3810
template <class Elements, class SizeSeq, class OffsetSeq>
3811
class LayoutImpl;
3812
3813
// ---------------------------------------------------------------------------
3814
// Public base class of `Layout` and the result type of `Layout::Partial()`.
3815
//
3816
// `Elements...` contains all template arguments of `Layout` that created this
3817
// instance.
3818
//
3819
// `SizeSeq...` is `[0, NumSizes)` where `NumSizes` is the number of arguments
3820
// passed to `Layout::Partial()` or `Layout::Layout()`.
3821
//
3822
// `OffsetSeq...` is `[0, NumOffsets)` where `NumOffsets` is
3823
// `Min(sizeof...(Elements), NumSizes + 1)` (the number of arrays for which we
3824
// can compute offsets).
3825
// ---------------------------------------------------------------------------
3826
template <class... Elements, size_t... SizeSeq, size_t... OffsetSeq>
3827
class LayoutImpl<std::tuple<Elements...>, phmap::index_sequence<SizeSeq...>,
3828
                 phmap::index_sequence<OffsetSeq...>> 
3829
{
3830
private:
3831
    static_assert(sizeof...(Elements) > 0, "At least one field is required");
3832
    static_assert(phmap::conjunction<IsLegalElementType<Elements>...>::value,
3833
                  "Invalid element type (see IsLegalElementType)");
3834
3835
    enum {
3836
        NumTypes = sizeof...(Elements),
3837
        NumSizes = sizeof...(SizeSeq),
3838
        NumOffsets = sizeof...(OffsetSeq),
3839
    };
3840
3841
    // These are guaranteed by `Layout`.
3842
    static_assert(NumOffsets == adl_barrier::Min(NumTypes, NumSizes + 1),
3843
                  "Internal error");
3844
    static_assert(NumTypes > 0, "Internal error");
3845
3846
    // Returns the index of `T` in `Elements...`. Results in a compilation error
3847
    // if `Elements...` doesn't contain exactly one instance of `T`.
3848
    template <class T>
3849
        static constexpr size_t ElementIndex() {
3850
        static_assert(Contains<Type<T>, Type<typename Type<Elements>::type>...>(),
3851
                      "Type not found");
3852
        return adl_barrier::Find(Type<T>(),
3853
                                 Type<typename Type<Elements>::type>()...);
3854
    }
3855
3856
    template <size_t N>
3857
        using ElementAlignment =
3858
        AlignOf<typename std::tuple_element<N, std::tuple<Elements...>>::type>;
3859
3860
public:
3861
    // Element types of all arrays packed in a tuple.
3862
    using ElementTypes = std::tuple<typename Type<Elements>::type...>;
3863
3864
    // Element type of the Nth array.
3865
    template <size_t N>
3866
        using ElementType = typename std::tuple_element<N, ElementTypes>::type;
3867
3868
    constexpr explicit LayoutImpl(IntToSize<SizeSeq>... sizes)
3869
5.90k
        : size_{sizes...} {}
phmap::priv::internal_layout::LayoutImpl<std::__1::tuple<signed char, phmap::priv::map_slot_type<unsigned int, int> >, phmap::integer_sequence<unsigned long, 0ul, 1ul>, phmap::integer_sequence<unsigned long, 0ul, 1ul> >::LayoutImpl(unsigned long, unsigned long)
Line
Count
Source
3869
5.90k
        : size_{sizes...} {}
Unexecuted instantiation: phmap::priv::internal_layout::LayoutImpl<std::__1::tuple<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> > > >, phmap::integer_sequence<unsigned long, 0ul, 1ul>, phmap::integer_sequence<unsigned long, 0ul, 1ul> >::LayoutImpl(unsigned long, unsigned long)
3870
3871
    // Alignment of the layout, equal to the strictest alignment of all elements.
3872
    // All pointers passed to the methods of layout must be aligned to this value.
3873
0
    static constexpr size_t Alignment() {
3874
0
        return adl_barrier::Max(AlignOf<Elements>::value...);
3875
0
    }
Unexecuted instantiation: phmap::priv::internal_layout::LayoutImpl<std::__1::tuple<signed char, phmap::priv::map_slot_type<unsigned int, int> >, phmap::integer_sequence<unsigned long, 0ul, 1ul>, phmap::integer_sequence<unsigned long, 0ul, 1ul> >::Alignment()
Unexecuted instantiation: phmap::priv::internal_layout::LayoutImpl<std::__1::tuple<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> > > >, phmap::integer_sequence<unsigned long, 0ul, 1ul>, phmap::integer_sequence<unsigned long, 0ul, 1ul> >::Alignment()
3876
3877
    // Offset in bytes of the Nth array.
3878
    //
3879
    //   // int[3], 4 bytes of padding, double[4].
3880
    //   Layout<int, double> x(3, 4);
3881
    //   assert(x.Offset<0>() == 0);   // The ints starts from 0.
3882
    //   assert(x.Offset<1>() == 16);  // The doubles starts from 16.
3883
    //
3884
    // Requires: `N <= NumSizes && N < sizeof...(Ts)`.
3885
    template <size_t N, EnableIf<N == 0> = 0>
3886
11.8k
        constexpr size_t Offset() const {
3887
11.8k
        return 0;
3888
11.8k
    }
unsigned long phmap::priv::internal_layout::LayoutImpl<std::__1::tuple<signed char, phmap::priv::map_slot_type<unsigned int, int> >, phmap::integer_sequence<unsigned long, 0ul, 1ul>, phmap::integer_sequence<unsigned long, 0ul, 1ul> >::Offset<0ul, 0>() const
Line
Count
Source
3886
11.8k
        constexpr size_t Offset() const {
3887
11.8k
        return 0;
3888
11.8k
    }
Unexecuted instantiation: unsigned long phmap::priv::internal_layout::LayoutImpl<std::__1::tuple<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> > > >, phmap::integer_sequence<unsigned long, 0ul, 1ul>, phmap::integer_sequence<unsigned long, 0ul, 1ul> >::Offset<0ul, 0>() const
3889
3890
    template <size_t N, EnableIf<N != 0> = 0>
3891
8.85k
        constexpr size_t Offset() const {
3892
8.85k
        static_assert(N < NumOffsets, "Index out of bounds");
3893
8.85k
        return adl_barrier::Align(
3894
8.85k
            Offset<N - 1>() + SizeOf<ElementType<N - 1>>::value * size_[N - 1],
3895
8.85k
            ElementAlignment<N>::value);
3896
8.85k
    }
unsigned long phmap::priv::internal_layout::LayoutImpl<std::__1::tuple<signed char, phmap::priv::map_slot_type<unsigned int, int> >, phmap::integer_sequence<unsigned long, 0ul, 1ul>, phmap::integer_sequence<unsigned long, 0ul, 1ul> >::Offset<1ul, 0>() const
Line
Count
Source
3891
8.85k
        constexpr size_t Offset() const {
3892
8.85k
        static_assert(N < NumOffsets, "Index out of bounds");
3893
8.85k
        return adl_barrier::Align(
3894
8.85k
            Offset<N - 1>() + SizeOf<ElementType<N - 1>>::value * size_[N - 1],
3895
8.85k
            ElementAlignment<N>::value);
3896
8.85k
    }
Unexecuted instantiation: unsigned long phmap::priv::internal_layout::LayoutImpl<std::__1::tuple<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> > > >, phmap::integer_sequence<unsigned long, 0ul, 1ul>, phmap::integer_sequence<unsigned long, 0ul, 1ul> >::Offset<1ul, 0>() const
3897
3898
    // Offset in bytes of the array with the specified element type. There must
3899
    // be exactly one such array and its zero-based index must be at most
3900
    // `NumSizes`.
3901
    //
3902
    //   // int[3], 4 bytes of padding, double[4].
3903
    //   Layout<int, double> x(3, 4);
3904
    //   assert(x.Offset<int>() == 0);      // The ints starts from 0.
3905
    //   assert(x.Offset<double>() == 16);  // The doubles starts from 16.
3906
    template <class T>
3907
        constexpr size_t Offset() const {
3908
        return Offset<ElementIndex<T>()>();
3909
    }
3910
3911
    // Offsets in bytes of all arrays for which the offsets are known.
3912
    constexpr std::array<size_t, NumOffsets> Offsets() const {
3913
        return {{Offset<OffsetSeq>()...}};
3914
    }
3915
3916
    // The number of elements in the Nth array. This is the Nth argument of
3917
    // `Layout::Partial()` or `Layout::Layout()` (zero-based).
3918
    //
3919
    //   // int[3], 4 bytes of padding, double[4].
3920
    //   Layout<int, double> x(3, 4);
3921
    //   assert(x.Size<0>() == 3);
3922
    //   assert(x.Size<1>() == 4);
3923
    //
3924
    // Requires: `N < NumSizes`.
3925
    template <size_t N>
3926
        constexpr size_t Size() const {
3927
        static_assert(N < NumSizes, "Index out of bounds");
3928
        return size_[N];
3929
    }
3930
3931
    // The number of elements in the array with the specified element type.
3932
    // There must be exactly one such array and its zero-based index must be
3933
    // at most `NumSizes`.
3934
    //
3935
    //   // int[3], 4 bytes of padding, double[4].
3936
    //   Layout<int, double> x(3, 4);
3937
    //   assert(x.Size<int>() == 3);
3938
    //   assert(x.Size<double>() == 4);
3939
    template <class T>
3940
        constexpr size_t Size() const {
3941
        return Size<ElementIndex<T>()>();
3942
    }
3943
3944
    // The number of elements of all arrays for which they are known.
3945
    constexpr std::array<size_t, NumSizes> Sizes() const {
3946
        return {{Size<SizeSeq>()...}};
3947
    }
3948
3949
    // Pointer to the beginning of the Nth array.
3950
    //
3951
    // `Char` must be `[const] [signed|unsigned] char`.
3952
    //
3953
    //   // int[3], 4 bytes of padding, double[4].
3954
    //   Layout<int, double> x(3, 4);
3955
    //   unsigned char* p = new unsigned char[x.AllocSize()];
3956
    //   int* ints = x.Pointer<0>(p);
3957
    //   double* doubles = x.Pointer<1>(p);
3958
    //
3959
    // Requires: `N <= NumSizes && N < sizeof...(Ts)`.
3960
    // Requires: `p` is aligned to `Alignment()`.
3961
    template <size_t N, class Char>
3962
5.90k
        CopyConst<Char, ElementType<N>>* Pointer(Char* p) const {
3963
5.90k
        using C = typename std::remove_const<Char>::type;
3964
5.90k
        static_assert(
3965
5.90k
            std::is_same<C, char>() || std::is_same<C, unsigned char>() ||
3966
5.90k
            std::is_same<C, signed char>(),
3967
5.90k
            "The argument must be a pointer to [const] [signed|unsigned] char");
3968
5.90k
        constexpr size_t alignment = Alignment();
3969
5.90k
        (void)alignment;
3970
5.90k
        assert(reinterpret_cast<uintptr_t>(p) % alignment == 0);
3971
5.90k
        return reinterpret_cast<CopyConst<Char, ElementType<N>>*>(p + Offset<N>());
3972
5.90k
    }
_ZNK5phmap4priv15internal_layout10LayoutImplINSt3__15tupleIJaNS0_13map_slot_typeIjiEEEEENS_16integer_sequenceImJLm0ELm1EEEES9_E7PointerILm0EcEEPNS3_11conditionalIXsr3std8is_constIT0_EE5valueEKNS3_13tuple_elementIXT_ES7_E4typeESG_E4typeEPSD_
Line
Count
Source
3962
2.95k
        CopyConst<Char, ElementType<N>>* Pointer(Char* p) const {
3963
2.95k
        using C = typename std::remove_const<Char>::type;
3964
2.95k
        static_assert(
3965
2.95k
            std::is_same<C, char>() || std::is_same<C, unsigned char>() ||
3966
2.95k
            std::is_same<C, signed char>(),
3967
2.95k
            "The argument must be a pointer to [const] [signed|unsigned] char");
3968
2.95k
        constexpr size_t alignment = Alignment();
3969
2.95k
        (void)alignment;
3970
2.95k
        assert(reinterpret_cast<uintptr_t>(p) % alignment == 0);
3971
2.95k
        return reinterpret_cast<CopyConst<Char, ElementType<N>>*>(p + Offset<N>());
3972
2.95k
    }
_ZNK5phmap4priv15internal_layout10LayoutImplINSt3__15tupleIJaNS0_13map_slot_typeIjiEEEEENS_16integer_sequenceImJLm0ELm1EEEES9_E7PointerILm1EcEEPNS3_11conditionalIXsr3std8is_constIT0_EE5valueEKNS3_13tuple_elementIXT_ES7_E4typeESG_E4typeEPSD_
Line
Count
Source
3962
2.95k
        CopyConst<Char, ElementType<N>>* Pointer(Char* p) const {
3963
2.95k
        using C = typename std::remove_const<Char>::type;
3964
2.95k
        static_assert(
3965
2.95k
            std::is_same<C, char>() || std::is_same<C, unsigned char>() ||
3966
2.95k
            std::is_same<C, signed char>(),
3967
2.95k
            "The argument must be a pointer to [const] [signed|unsigned] char");
3968
2.95k
        constexpr size_t alignment = Alignment();
3969
2.95k
        (void)alignment;
3970
2.95k
        assert(reinterpret_cast<uintptr_t>(p) % alignment == 0);
3971
2.95k
        return reinterpret_cast<CopyConst<Char, ElementType<N>>*>(p + Offset<N>());
3972
2.95k
    }
3973
3974
    // Pointer to the beginning of the array with the specified element type.
3975
    // There must be exactly one such array and its zero-based index must be at
3976
    // most `NumSizes`.
3977
    //
3978
    // `Char` must be `[const] [signed|unsigned] char`.
3979
    //
3980
    //   // int[3], 4 bytes of padding, double[4].
3981
    //   Layout<int, double> x(3, 4);
3982
    //   unsigned char* p = new unsigned char[x.AllocSize()];
3983
    //   int* ints = x.Pointer<int>(p);
3984
    //   double* doubles = x.Pointer<double>(p);
3985
    //
3986
    // Requires: `p` is aligned to `Alignment()`.
3987
    template <class T, class Char>
3988
        CopyConst<Char, T>* Pointer(Char* p) const {
3989
        return Pointer<ElementIndex<T>()>(p);
3990
    }
3991
3992
    // Pointers to all arrays for which pointers are known.
3993
    //
3994
    // `Char` must be `[const] [signed|unsigned] char`.
3995
    //
3996
    //   // int[3], 4 bytes of padding, double[4].
3997
    //   Layout<int, double> x(3, 4);
3998
    //   unsigned char* p = new unsigned char[x.AllocSize()];
3999
    //
4000
    //   int* ints;
4001
    //   double* doubles;
4002
    //   std::tie(ints, doubles) = x.Pointers(p);
4003
    //
4004
    // Requires: `p` is aligned to `Alignment()`.
4005
    //
4006
    // Note: We're not using ElementType alias here because it does not compile
4007
    // under MSVC.
4008
    template <class Char>
4009
        std::tuple<CopyConst<
4010
                       Char, typename std::tuple_element<OffsetSeq, ElementTypes>::type>*...>
4011
        Pointers(Char* p) const {
4012
        return std::tuple<CopyConst<Char, ElementType<OffsetSeq>>*...>(
4013
            Pointer<OffsetSeq>(p)...);
4014
    }
4015
4016
    // The Nth array.
4017
    //
4018
    // `Char` must be `[const] [signed|unsigned] char`.
4019
    //
4020
    //   // int[3], 4 bytes of padding, double[4].
4021
    //   Layout<int, double> x(3, 4);
4022
    //   unsigned char* p = new unsigned char[x.AllocSize()];
4023
    //   Span<int> ints = x.Slice<0>(p);
4024
    //   Span<double> doubles = x.Slice<1>(p);
4025
    //
4026
    // Requires: `N < NumSizes`.
4027
    // Requires: `p` is aligned to `Alignment()`.
4028
    template <size_t N, class Char>
4029
        SliceType<CopyConst<Char, ElementType<N>>> Slice(Char* p) const {
4030
        return SliceType<CopyConst<Char, ElementType<N>>>(Pointer<N>(p), Size<N>());
4031
    }
4032
4033
    // The array with the specified element type. There must be exactly one
4034
    // such array and its zero-based index must be less than `NumSizes`.
4035
    //
4036
    // `Char` must be `[const] [signed|unsigned] char`.
4037
    //
4038
    //   // int[3], 4 bytes of padding, double[4].
4039
    //   Layout<int, double> x(3, 4);
4040
    //   unsigned char* p = new unsigned char[x.AllocSize()];
4041
    //   Span<int> ints = x.Slice<int>(p);
4042
    //   Span<double> doubles = x.Slice<double>(p);
4043
    //
4044
    // Requires: `p` is aligned to `Alignment()`.
4045
    template <class T, class Char>
4046
        SliceType<CopyConst<Char, T>> Slice(Char* p) const {
4047
        return Slice<ElementIndex<T>()>(p);
4048
    }
4049
4050
    // All arrays with known sizes.
4051
    //
4052
    // `Char` must be `[const] [signed|unsigned] char`.
4053
    //
4054
    //   // int[3], 4 bytes of padding, double[4].
4055
    //   Layout<int, double> x(3, 4);
4056
    //   unsigned char* p = new unsigned char[x.AllocSize()];
4057
    //
4058
    //   Span<int> ints;
4059
    //   Span<double> doubles;
4060
    //   std::tie(ints, doubles) = x.Slices(p);
4061
    //
4062
    // Requires: `p` is aligned to `Alignment()`.
4063
    //
4064
    // Note: We're not using ElementType alias here because it does not compile
4065
    // under MSVC.
4066
    template <class Char>
4067
        std::tuple<SliceType<CopyConst<
4068
                                 Char, typename std::tuple_element<SizeSeq, ElementTypes>::type>>...>
4069
        Slices(Char* p) const {
4070
        // Workaround for https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63875 (fixed
4071
        // in 6.1).
4072
        (void)p;
4073
        return std::tuple<SliceType<CopyConst<Char, ElementType<SizeSeq>>>...>(
4074
            Slice<SizeSeq>(p)...);
4075
    }
4076
4077
    // The size of the allocation that fits all arrays.
4078
    //
4079
    //   // int[3], 4 bytes of padding, double[4].
4080
    //   Layout<int, double> x(3, 4);
4081
    //   unsigned char* p = new unsigned char[x.AllocSize()];  // 48 bytes
4082
    //
4083
    // Requires: `NumSizes == sizeof...(Ts)`.
4084
5.90k
    constexpr size_t AllocSize() const {
4085
5.90k
        static_assert(NumTypes == NumSizes, "You must specify sizes of all fields");
4086
5.90k
        return Offset<NumTypes - 1>() +
4087
5.90k
            SizeOf<ElementType<NumTypes - 1>>::value * size_[NumTypes - 1];
4088
5.90k
    }
phmap::priv::internal_layout::LayoutImpl<std::__1::tuple<signed char, phmap::priv::map_slot_type<unsigned int, int> >, phmap::integer_sequence<unsigned long, 0ul, 1ul>, phmap::integer_sequence<unsigned long, 0ul, 1ul> >::AllocSize() const
Line
Count
Source
4084
5.90k
    constexpr size_t AllocSize() const {
4085
5.90k
        static_assert(NumTypes == NumSizes, "You must specify sizes of all fields");
4086
5.90k
        return Offset<NumTypes - 1>() +
4087
5.90k
            SizeOf<ElementType<NumTypes - 1>>::value * size_[NumTypes - 1];
4088
5.90k
    }
Unexecuted instantiation: phmap::priv::internal_layout::LayoutImpl<std::__1::tuple<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> > > >, phmap::integer_sequence<unsigned long, 0ul, 1ul>, phmap::integer_sequence<unsigned long, 0ul, 1ul> >::AllocSize() const
4089
4090
    // If built with --config=asan, poisons padding bytes (if any) in the
4091
    // allocation. The pointer must point to a memory block at least
4092
    // `AllocSize()` bytes in length.
4093
    //
4094
    // `Char` must be `[const] [signed|unsigned] char`.
4095
    //
4096
    // Requires: `p` is aligned to `Alignment()`.
4097
    template <class Char, size_t N = NumOffsets - 1, EnableIf<N == 0> = 0>
4098
        void PoisonPadding(const Char* p) const {
4099
        Pointer<0>(p);  // verify the requirements on `Char` and `p`
4100
    }
4101
4102
    template <class Char, size_t N = NumOffsets - 1, EnableIf<N != 0> = 0>
4103
        void PoisonPadding(const Char* p) const {
4104
        static_assert(N < NumOffsets, "Index out of bounds");
4105
        (void)p;
4106
#ifdef ADDRESS_SANITIZER
4107
        PoisonPadding<Char, N - 1>(p);
4108
        // The `if` is an optimization. It doesn't affect the observable behaviour.
4109
        if (ElementAlignment<N - 1>::value % ElementAlignment<N>::value) {
4110
            size_t start =
4111
                Offset<N - 1>() + SizeOf<ElementType<N - 1>>::value * size_[N - 1];
4112
            ASAN_POISON_MEMORY_REGION(p + start, Offset<N>() - start);
4113
        }
4114
#endif
4115
    }
4116
4117
private:
4118
    // Arguments of `Layout::Partial()` or `Layout::Layout()`.
4119
    size_t size_[NumSizes > 0 ? NumSizes : 1];
4120
};
4121
4122
template <size_t NumSizes, class... Ts>
4123
using LayoutType = LayoutImpl<
4124
    std::tuple<Ts...>, phmap::make_index_sequence<NumSizes>,
4125
    phmap::make_index_sequence<adl_barrier::Min(sizeof...(Ts), NumSizes + 1)>>;
4126
4127
}  // namespace internal_layout
4128
4129
// ---------------------------------------------------------------------------
4130
// Descriptor of arrays of various types and sizes laid out in memory one after
4131
// another. See the top of the file for documentation.
4132
//
4133
// Check out the public API of internal_layout::LayoutImpl above. The type is
4134
// internal to the library but its methods are public, and they are inherited
4135
// by `Layout`.
4136
// ---------------------------------------------------------------------------
4137
template <class... Ts>
4138
class Layout : public internal_layout::LayoutType<sizeof...(Ts), Ts...> 
4139
{
4140
public:
4141
    static_assert(sizeof...(Ts) > 0, "At least one field is required");
4142
    static_assert(
4143
        phmap::conjunction<internal_layout::IsLegalElementType<Ts>...>::value,
4144
        "Invalid element type (see IsLegalElementType)");
4145
4146
    template <size_t NumSizes>
4147
    using PartialType = internal_layout::LayoutType<NumSizes, Ts...>;
4148
4149
    template <class... Sizes>
4150
    static constexpr PartialType<sizeof...(Sizes)> Partial(Sizes&&... sizes) {
4151
        static_assert(sizeof...(Sizes) <= sizeof...(Ts), "");
4152
        return PartialType<sizeof...(Sizes)>(phmap::forward<Sizes>(sizes)...);
4153
    }
4154
4155
    // Creates a layout with the sizes of all arrays specified. If you know
4156
    // only the sizes of the first N arrays (where N can be zero), you can use
4157
    // `Partial()` defined above. The constructor is essentially equivalent to
4158
    // calling `Partial()` and passing in all array sizes; the constructor is
4159
    // provided as a convenient abbreviation.
4160
    //
4161
    // Note: The sizes of the arrays must be specified in number of elements,
4162
    // not in bytes.
4163
    constexpr explicit Layout(internal_layout::TypeToSize<Ts>... sizes)
4164
5.90k
        : internal_layout::LayoutType<sizeof...(Ts), Ts...>(sizes...) {}
phmap::priv::Layout<signed char, phmap::priv::map_slot_type<unsigned int, int> >::Layout(unsigned long, unsigned long)
Line
Count
Source
4164
5.90k
        : internal_layout::LayoutType<sizeof...(Ts), Ts...>(sizes...) {}
Unexecuted instantiation: phmap::priv::Layout<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> > > >::Layout(unsigned long, unsigned long)
4165
};
4166
4167
4168
#ifdef _MSC_VER
4169
    #pragma warning(push)  
4170
    // warning warning C4324: structure was padded due to alignment specifier
4171
    #pragma warning(disable : 4324)
4172
#endif
4173
4174
4175
// ----------------------------------------------------------------------------
4176
// Allocates at least n bytes aligned to the specified alignment.
4177
// Alignment must be a power of 2. It must be positive.
4178
//
4179
// Note that many allocators don't honor alignment requirements above certain
4180
// threshold (usually either alignof(std::max_align_t) or alignof(void*)).
4181
// Allocate() doesn't apply alignment corrections. If the underlying allocator
4182
// returns insufficiently alignment pointer, that's what you are going to get.
4183
// ----------------------------------------------------------------------------
4184
template <size_t Alignment, class Alloc>
4185
2.95k
void* Allocate(Alloc* alloc, size_t n) {
4186
2.95k
  static_assert(Alignment > 0, "");
4187
2.95k
  assert(n && "n must be positive");
4188
2.95k
  struct alignas(Alignment) M {};
4189
2.95k
  using A = typename phmap::allocator_traits<Alloc>::template rebind_alloc<M>;
4190
2.95k
  using AT = typename phmap::allocator_traits<Alloc>::template rebind_traits<M>;
4191
2.95k
  A mem_alloc(*alloc);
4192
2.95k
  void* p = AT::allocate(mem_alloc, (n + sizeof(M) - 1) / sizeof(M));
4193
2.95k
  assert(reinterpret_cast<uintptr_t>(p) % Alignment == 0 &&
4194
2.95k
         "allocator does not respect alignment");
4195
2.95k
  return p;
4196
2.95k
}
4197
4198
// ----------------------------------------------------------------------------
4199
// The pointer must have been previously obtained by calling
4200
// Allocate<Alignment>(alloc, n).
4201
// ----------------------------------------------------------------------------
4202
template <size_t Alignment, class Alloc>
4203
2.95k
void Deallocate(Alloc* alloc, void* p, size_t n) {
4204
2.95k
  static_assert(Alignment > 0, "");
4205
2.95k
  assert(n && "n must be positive");
4206
2.95k
  struct alignas(Alignment) M {};
4207
2.95k
  using A = typename phmap::allocator_traits<Alloc>::template rebind_alloc<M>;
4208
2.95k
  using AT = typename phmap::allocator_traits<Alloc>::template rebind_traits<M>;
4209
2.95k
  A mem_alloc(*alloc);
4210
2.95k
  AT::deallocate(mem_alloc, static_cast<M*>(p),
4211
2.95k
                 (n + sizeof(M) - 1) / sizeof(M));
4212
2.95k
}
void phmap::priv::Deallocate<4ul, std::__1::allocator<std::__1::pair<unsigned int const, int> > >(std::__1::allocator<std::__1::pair<unsigned int const, int> >*, void*, unsigned long)
Line
Count
Source
4203
2.95k
void Deallocate(Alloc* alloc, void* p, size_t n) {
4204
2.95k
  static_assert(Alignment > 0, "");
4205
2.95k
  assert(n && "n must be positive");
4206
2.95k
  struct alignas(Alignment) M {};
4207
2.95k
  using A = typename phmap::allocator_traits<Alloc>::template rebind_alloc<M>;
4208
2.95k
  using AT = typename phmap::allocator_traits<Alloc>::template rebind_traits<M>;
4209
2.95k
  A mem_alloc(*alloc);
4210
2.95k
  AT::deallocate(mem_alloc, static_cast<M*>(p),
4211
2.95k
                 (n + sizeof(M) - 1) / sizeof(M));
4212
2.95k
}
Unexecuted instantiation: void phmap::priv::Deallocate<8ul, 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> > > > >(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> > > >*, void*, unsigned long)
4213
4214
#ifdef _MSC_VER
4215
     #pragma warning(pop)  
4216
#endif
4217
4218
// Helper functions for asan and msan.
4219
// ----------------------------------------------------------------------------
4220
2.95k
inline void SanitizerPoisonMemoryRegion(const void* m, size_t s) {
4221
#ifdef ADDRESS_SANITIZER
4222
    ASAN_POISON_MEMORY_REGION(m, s);
4223
#endif
4224
#ifdef MEMORY_SANITIZER
4225
    __msan_poison(m, s);
4226
#endif
4227
2.95k
    (void)m;
4228
2.95k
    (void)s;
4229
2.95k
}
4230
4231
1.49M
inline void SanitizerUnpoisonMemoryRegion(const void* m, size_t s) {
4232
#ifdef ADDRESS_SANITIZER
4233
    ASAN_UNPOISON_MEMORY_REGION(m, s);
4234
#endif
4235
#ifdef MEMORY_SANITIZER
4236
    __msan_unpoison(m, s);
4237
#endif
4238
1.49M
    (void)m;
4239
1.49M
    (void)s;
4240
1.49M
}
4241
4242
template <typename T>
4243
0
inline void SanitizerPoisonObject(const T* object) {
4244
0
    SanitizerPoisonMemoryRegion(object, sizeof(T));
4245
0
}
4246
4247
template <typename T>
4248
1.49M
inline void SanitizerUnpoisonObject(const T* object) {
4249
1.49M
    SanitizerUnpoisonMemoryRegion(object, sizeof(T));
4250
1.49M
}
4251
4252
}  // namespace priv
4253
}  // namespace phmap
4254
4255
4256
// ---------------------------------------------------------------------------
4257
//  thread_annotations.h
4258
// ---------------------------------------------------------------------------
4259
4260
#if defined(__clang__)
4261
    #define PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(x)   __attribute__((x))
4262
#else
4263
    #define PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(x)   // no-op
4264
#endif
4265
4266
#define PHMAP_GUARDED_BY(x) PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(guarded_by(x))
4267
#define PHMAP_PT_GUARDED_BY(x) PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(pt_guarded_by(x))
4268
4269
#define PHMAP_ACQUIRED_AFTER(...) \
4270
  PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(acquired_after(__VA_ARGS__))
4271
4272
#define PHMAP_ACQUIRED_BEFORE(...) \
4273
  PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(acquired_before(__VA_ARGS__))
4274
4275
#define PHMAP_EXCLUSIVE_LOCKS_REQUIRED(...) \
4276
  PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(exclusive_locks_required(__VA_ARGS__))
4277
4278
#define PHMAP_SHARED_LOCKS_REQUIRED(...) \
4279
  PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(shared_locks_required(__VA_ARGS__))
4280
4281
#define PHMAP_LOCKS_EXCLUDED(...) \
4282
  PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(locks_excluded(__VA_ARGS__))
4283
4284
#define PHMAP_LOCK_RETURNED(x) \
4285
  PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(lock_returned(x))
4286
4287
#define PHMAP_LOCKABLE \
4288
  PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(lockable)
4289
4290
#define PHMAP_SCOPED_LOCKABLE \
4291
  PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(scoped_lockable)
4292
4293
#define PHMAP_EXCLUSIVE_LOCK_FUNCTION(...) \
4294
  PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(exclusive_lock_function(__VA_ARGS__))
4295
4296
#define PHMAP_SHARED_LOCK_FUNCTION(...) \
4297
  PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(shared_lock_function(__VA_ARGS__))
4298
4299
#define PHMAP_UNLOCK_FUNCTION(...) \
4300
  PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(unlock_function(__VA_ARGS__))
4301
4302
#define PHMAP_EXCLUSIVE_TRYLOCK_FUNCTION(...) \
4303
  PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(exclusive_trylock_function(__VA_ARGS__))
4304
4305
#define PHMAP_SHARED_TRYLOCK_FUNCTION(...) \
4306
  PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(shared_trylock_function(__VA_ARGS__))
4307
4308
#define PHMAP_ASSERT_EXCLUSIVE_LOCK(...) \
4309
  PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(assert_exclusive_lock(__VA_ARGS__))
4310
4311
#define PHMAP_ASSERT_SHARED_LOCK(...) \
4312
  PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(assert_shared_lock(__VA_ARGS__))
4313
4314
#define PHMAP_NO_THREAD_SAFETY_ANALYSIS \
4315
  PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(no_thread_safety_analysis)
4316
4317
//------------------------------------------------------------------------------
4318
// Tool-Supplied Annotations
4319
//------------------------------------------------------------------------------
4320
4321
// TS_UNCHECKED should be placed around lock expressions that are not valid
4322
// C++ syntax, but which are present for documentation purposes.  These
4323
// annotations will be ignored by the analysis.
4324
#define PHMAP_TS_UNCHECKED(x) ""
4325
4326
// TS_FIXME is used to mark lock expressions that are not valid C++ syntax.
4327
// It is used by automated tools to mark and disable invalid expressions.
4328
// The annotation should either be fixed, or changed to TS_UNCHECKED.
4329
#define PHMAP_TS_FIXME(x) ""
4330
4331
// Like NO_THREAD_SAFETY_ANALYSIS, this turns off checking within the body of
4332
// a particular function.  However, this attribute is used to mark functions
4333
// that are incorrect and need to be fixed.  It is used by automated tools to
4334
// avoid breaking the build when the analysis is updated.
4335
// Code owners are expected to eventually fix the routine.
4336
#define PHMAP_NO_THREAD_SAFETY_ANALYSIS_FIXME  PHMAP_NO_THREAD_SAFETY_ANALYSIS
4337
4338
// Similar to NO_THREAD_SAFETY_ANALYSIS_FIXME, this macro marks a GUARDED_BY
4339
// annotation that needs to be fixed, because it is producing thread safety
4340
// warning.  It disables the GUARDED_BY.
4341
#define PHMAP_GUARDED_BY_FIXME(x)
4342
4343
// Disables warnings for a single read operation.  This can be used to avoid
4344
// warnings when it is known that the read is not actually involved in a race,
4345
// but the compiler cannot confirm that.
4346
#define PHMAP_TS_UNCHECKED_READ(x) thread_safety_analysis::ts_unchecked_read(x)
4347
4348
4349
namespace phmap {
4350
namespace thread_safety_analysis {
4351
4352
// Takes a reference to a guarded data member, and returns an unguarded
4353
// reference.
4354
template <typename T>
4355
inline const T& ts_unchecked_read(const T& v) PHMAP_NO_THREAD_SAFETY_ANALYSIS {
4356
    return v;
4357
}
4358
4359
template <typename T>
4360
inline T& ts_unchecked_read(T& v) PHMAP_NO_THREAD_SAFETY_ANALYSIS {
4361
    return v;
4362
}
4363
4364
}  // namespace thread_safety_analysis
4365
4366
namespace priv {
4367
4368
namespace memory_internal {
4369
4370
// ----------------------------------------------------------------------------
4371
// If Pair is a standard-layout type, OffsetOf<Pair>::kFirst and
4372
// OffsetOf<Pair>::kSecond are equivalent to offsetof(Pair, first) and
4373
// offsetof(Pair, second) respectively. Otherwise they are -1.
4374
//
4375
// The purpose of OffsetOf is to avoid calling offsetof() on non-standard-layout
4376
// type, which is non-portable.
4377
// ----------------------------------------------------------------------------
4378
template <class Pair, class = std::true_type>
4379
struct OffsetOf {
4380
   static constexpr size_t kFirst  = static_cast<size_t>(-1);
4381
   static constexpr size_t kSecond = static_cast<size_t>(-1);
4382
};
4383
4384
template <class Pair>
4385
struct OffsetOf<Pair, typename std::is_standard_layout<Pair>::type> 
4386
{
4387
    static constexpr size_t kFirst  = offsetof(Pair, first);
4388
    static constexpr size_t kSecond = offsetof(Pair, second);
4389
};
4390
4391
// ----------------------------------------------------------------------------
4392
template <class K, class V>
4393
struct IsLayoutCompatible 
4394
{
4395
private:
4396
    struct Pair {
4397
        K first;
4398
        V second;
4399
    };
4400
4401
    // Is P layout-compatible with Pair?
4402
    template <class P>
4403
0
    static constexpr bool LayoutCompatible() {
4404
0
        return std::is_standard_layout<P>() && sizeof(P) == sizeof(Pair) &&
4405
0
            alignof(P) == alignof(Pair) &&
4406
0
            memory_internal::OffsetOf<P>::kFirst ==
4407
0
            memory_internal::OffsetOf<Pair>::kFirst &&
4408
0
            memory_internal::OffsetOf<P>::kSecond ==
4409
0
            memory_internal::OffsetOf<Pair>::kSecond;
4410
0
    }
Unexecuted instantiation: bool phmap::priv::memory_internal::IsLayoutCompatible<unsigned int, int>::LayoutCompatible<std::__1::pair<unsigned int, int> >()
Unexecuted instantiation: bool phmap::priv::memory_internal::IsLayoutCompatible<unsigned int, int>::LayoutCompatible<std::__1::pair<unsigned int const, int> >()
Unexecuted instantiation: bool phmap::priv::memory_internal::IsLayoutCompatible<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> > >::LayoutCompatible<std::__1::pair<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> > > >()
Unexecuted instantiation: bool phmap::priv::memory_internal::IsLayoutCompatible<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> > >::LayoutCompatible<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> > > >()
4411
4412
public:
4413
    // Whether pair<const K, V> and pair<K, V> are layout-compatible. If they are,
4414
    // then it is safe to store them in a union and read from either.
4415
    static constexpr bool value = std::is_standard_layout<K>() &&
4416
        std::is_standard_layout<Pair>() &&
4417
        memory_internal::OffsetOf<Pair>::kFirst == 0 &&
4418
        LayoutCompatible<std::pair<K, V>>() &&
4419
        LayoutCompatible<std::pair<const K, V>>();
4420
};
4421
4422
}  // namespace memory_internal
4423
4424
// ----------------------------------------------------------------------------
4425
// The internal storage type for key-value containers like flat_hash_map.
4426
//
4427
// It is convenient for the value_type of a flat_hash_map<K, V> to be
4428
// pair<const K, V>; the "const K" prevents accidental modification of the key
4429
// when dealing with the reference returned from find() and similar methods.
4430
// However, this creates other problems; we want to be able to emplace(K, V)
4431
// efficiently with move operations, and similarly be able to move a
4432
// pair<K, V> in insert().
4433
//
4434
// The solution is this union, which aliases the const and non-const versions
4435
// of the pair. This also allows flat_hash_map<const K, V> to work, even though
4436
// that has the same efficiency issues with move in emplace() and insert() -
4437
// but people do it anyway.
4438
//
4439
// If kMutableKeys is false, only the value member can be accessed.
4440
//
4441
// If kMutableKeys is true, key can be accessed through all slots while value
4442
// and mutable_value must be accessed only via INITIALIZED slots. Slots are
4443
// created and destroyed via mutable_value so that the key can be moved later.
4444
//
4445
// Accessing one of the union fields while the other is active is safe as
4446
// long as they are layout-compatible, which is guaranteed by the definition of
4447
// kMutableKeys. For C++11, the relevant section of the standard is
4448
// https://timsong-cpp.github.io/cppwp/n3337/class.mem#19 (9.2.19)
4449
// ----------------------------------------------------------------------------
4450
template <class K, class V>
4451
union map_slot_type 
4452
{
4453
1.49M
    map_slot_type() {}
4454
    ~map_slot_type() = delete;
4455
    map_slot_type(const map_slot_type&) = delete;
4456
    map_slot_type& operator=(const map_slot_type&) = delete;
4457
4458
    using value_type = std::pair<const K, V>;
4459
    using mutable_value_type = std::pair<K, V>;
4460
4461
    value_type value;
4462
    mutable_value_type mutable_value;
4463
    K key;
4464
};
4465
4466
// ----------------------------------------------------------------------------
4467
// ----------------------------------------------------------------------------
4468
template <class K, class V>
4469
struct map_slot_policy 
4470
{
4471
    using slot_type = map_slot_type<K, V>;
4472
    using value_type = std::pair<const K, V>;
4473
    using mutable_value_type = std::pair<K, V>;
4474
4475
private:
4476
1.49M
    static void emplace(slot_type* slot) {
4477
        // The construction of union doesn't do anything at runtime but it allows us
4478
        // to access its members without violating aliasing rules.
4479
1.49M
        new (slot) slot_type;
4480
1.49M
    }
4481
    // If pair<const K, V> and pair<K, V> are layout-compatible, we can accept one
4482
    // or the other via slot_type. We are also free to access the key via
4483
    // slot_type::key in this case.
4484
    using kMutableKeys = memory_internal::IsLayoutCompatible<K, V>;
4485
4486
public:
4487
    static value_type& element(slot_type* slot) { return slot->value; }
4488
    static const value_type& element(const slot_type* slot) {
4489
        return slot->value;
4490
    }
4491
4492
    static const K& key(const slot_type* slot) {
4493
        return kMutableKeys::value ? slot->key : slot->value.first;
4494
    }
4495
4496
    template <class Allocator, class... Args>
4497
536k
    static void construct(Allocator* alloc, slot_type* slot, Args&&... args) {
4498
536k
        emplace(slot);
4499
536k
        if (kMutableKeys::value) {
4500
536k
            phmap::allocator_traits<Allocator>::construct(*alloc, &slot->mutable_value,
4501
536k
                                                         std::forward<Args>(args)...);
4502
536k
        } else {
4503
0
            phmap::allocator_traits<Allocator>::construct(*alloc, &slot->value,
4504
0
                                                         std::forward<Args>(args)...);
4505
0
        }
4506
536k
    }
4507
4508
    // Construct this slot by moving from another slot.
4509
    template <class Allocator>
4510
    static void construct(Allocator* alloc, slot_type* slot, slot_type* other) {
4511
        emplace(slot);
4512
        if (kMutableKeys::value) {
4513
            phmap::allocator_traits<Allocator>::construct(
4514
                *alloc, &slot->mutable_value, std::move(other->mutable_value));
4515
        } else {
4516
            phmap::allocator_traits<Allocator>::construct(*alloc, &slot->value,
4517
                                                         std::move(other->value));
4518
        }
4519
    }
4520
4521
    template <class Allocator>
4522
958k
    static void destroy(Allocator* alloc, slot_type* slot) {
4523
958k
        if (kMutableKeys::value) {
4524
958k
            phmap::allocator_traits<Allocator>::destroy(*alloc, &slot->mutable_value);
4525
958k
        } else {
4526
0
            phmap::allocator_traits<Allocator>::destroy(*alloc, &slot->value);
4527
0
        }
4528
958k
    }
Unexecuted instantiation: void phmap::priv::map_slot_policy<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> > >::destroy<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> > > > >(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> > > >*, 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> > >*)
void phmap::priv::map_slot_policy<unsigned int, int>::destroy<std::__1::allocator<std::__1::pair<unsigned int const, int> > >(std::__1::allocator<std::__1::pair<unsigned int const, int> >*, phmap::priv::map_slot_type<unsigned int, int>*)
Line
Count
Source
4522
958k
    static void destroy(Allocator* alloc, slot_type* slot) {
4523
958k
        if (kMutableKeys::value) {
4524
958k
            phmap::allocator_traits<Allocator>::destroy(*alloc, &slot->mutable_value);
4525
958k
        } else {
4526
0
            phmap::allocator_traits<Allocator>::destroy(*alloc, &slot->value);
4527
0
        }
4528
958k
    }
4529
4530
    template <class Allocator>
4531
    static void transfer(Allocator* alloc, slot_type* new_slot,
4532
958k
                         slot_type* old_slot) {
4533
958k
        emplace(new_slot);
4534
958k
        if (kMutableKeys::value) {
4535
958k
            phmap::allocator_traits<Allocator>::construct(
4536
958k
                *alloc, &new_slot->mutable_value, std::move(old_slot->mutable_value));
4537
958k
        } else {
4538
0
            phmap::allocator_traits<Allocator>::construct(*alloc, &new_slot->value,
4539
0
                                                         std::move(old_slot->value));
4540
0
        }
4541
958k
        destroy(alloc, old_slot);
4542
958k
    }
4543
4544
    template <class Allocator>
4545
    static void swap(Allocator* alloc, slot_type* a, slot_type* b) {
4546
        if (kMutableKeys::value) {
4547
            using std::swap;
4548
            swap(a->mutable_value, b->mutable_value);
4549
        } else {
4550
            value_type tmp = std::move(a->value);
4551
            phmap::allocator_traits<Allocator>::destroy(*alloc, &a->value);
4552
            phmap::allocator_traits<Allocator>::construct(*alloc, &a->value,
4553
                                                         std::move(b->value));
4554
            phmap::allocator_traits<Allocator>::destroy(*alloc, &b->value);
4555
            phmap::allocator_traits<Allocator>::construct(*alloc, &b->value,
4556
                                                         std::move(tmp));
4557
        }
4558
    }
4559
4560
    template <class Allocator>
4561
    static void move(Allocator* alloc, slot_type* src, slot_type* dest) {
4562
        if (kMutableKeys::value) {
4563
            dest->mutable_value = std::move(src->mutable_value);
4564
        } else {
4565
            phmap::allocator_traits<Allocator>::destroy(*alloc, &dest->value);
4566
            phmap::allocator_traits<Allocator>::construct(*alloc, &dest->value,
4567
                                                          std::move(src->value));
4568
        }
4569
    }
4570
4571
    template <class Allocator>
4572
    static void move(Allocator* alloc, slot_type* first, slot_type* last,
4573
                     slot_type* result) {
4574
        for (slot_type *src = first, *dest = result; src != last; ++src, ++dest)
4575
            move(alloc, src, dest);
4576
    }
4577
};
4578
4579
}  // namespace priv
4580
}  // phmap
4581
4582
4583
namespace phmap {
4584
4585
#ifdef BOOST_THREAD_LOCK_OPTIONS_HPP
4586
    using defer_lock_t  = boost::defer_lock_t;
4587
    using try_to_lock_t = boost::try_to_lock_t;
4588
    using adopt_lock_t  = boost::adopt_lock_t;
4589
#else
4590
    struct adopt_lock_t  { explicit adopt_lock_t() = default; };
4591
    struct defer_lock_t  { explicit defer_lock_t() = default; };
4592
    struct try_to_lock_t { explicit try_to_lock_t() = default; };
4593
#endif
4594
4595
// -----------------------------------------------------------------------------
4596
// NullMutex
4597
// -----------------------------------------------------------------------------
4598
// A class that implements the Mutex interface, but does nothing. This is to be 
4599
// used as a default template parameters for classes who provide optional 
4600
// internal locking (like phmap::parallel_flat_hash_map).
4601
// -----------------------------------------------------------------------------
4602
class NullMutex {
4603
public:
4604
0
    NullMutex() {}
4605
0
    ~NullMutex() {}
4606
0
    void lock() {}
4607
0
    void unlock() {}
4608
0
    bool try_lock() { return true; }
4609
0
    void lock_shared() {}
4610
0
    void unlock_shared() {}
4611
0
    bool try_lock_shared() { return true; }
4612
};
4613
4614
// ------------------------ lockable object used internally -------------------------
4615
template <class MutexType>
4616
class LockableBaseImpl 
4617
{
4618
public:
4619
    // ----------------------------------------------------
4620
    struct DoNothing
4621
    {
4622
        using mutex_type = MutexType;  
4623
        DoNothing() noexcept {}
4624
        explicit DoNothing(mutex_type& ) noexcept {}
4625
        explicit DoNothing(mutex_type& , mutex_type&) noexcept {}
4626
        DoNothing(mutex_type&, phmap::adopt_lock_t) noexcept {}
4627
        DoNothing(mutex_type&, phmap::defer_lock_t) noexcept {}
4628
        DoNothing(mutex_type&, phmap::try_to_lock_t) {}
4629
        template<class T> explicit DoNothing(T&&) {}
4630
        DoNothing& operator=(const DoNothing&) { return *this; }
4631
        DoNothing& operator=(DoNothing&&) noexcept { return *this; }
4632
        void swap(DoNothing &)  noexcept {}
4633
        bool owns_lock() const noexcept { return true; }
4634
        void lock() {}
4635
        void unlock() {}
4636
        void lock_shared() {}
4637
        void unlock_shared() {}
4638
        bool switch_to_unique() { return false; }
4639
    };
4640
4641
    // ----------------------------------------------------
4642
    class WriteLock
4643
    {
4644
    public:
4645
        using mutex_type = MutexType;
4646
4647
        WriteLock() :  m_(nullptr), locked_(false)  {}
4648
4649
        explicit WriteLock(mutex_type &m) : m_(&m) { 
4650
            m_->lock(); 
4651
            locked_ = true; 
4652
        }
4653
4654
        WriteLock(mutex_type& m, adopt_lock_t) noexcept :
4655
            m_(&m), locked_(true) 
4656
        {}
4657
4658
        WriteLock(mutex_type& m, defer_lock_t) noexcept :
4659
            m_(&m), locked_(false) 
4660
        {}
4661
4662
        WriteLock(mutex_type& m, try_to_lock_t)  :
4663
            m_(&m), locked_(false) { 
4664
            m_->try_lock(); 
4665
        }
4666
4667
        WriteLock(WriteLock &&o) noexcept :
4668
            m_(std::move(o.m_)), locked_(std::move(o.locked_)) {
4669
            o.locked_ = false;
4670
            o.m_      = nullptr;
4671
        }
4672
4673
        WriteLock& operator=(WriteLock&& other) noexcept {
4674
            WriteLock temp(std::move(other));
4675
            swap(temp);
4676
            return *this;
4677
        }
4678
4679
        ~WriteLock() {
4680
            if (locked_) 
4681
                m_->unlock(); 
4682
        }
4683
4684
        void lock() { 
4685
            if (!locked_) { 
4686
                m_->lock(); 
4687
                locked_ = true; 
4688
            }
4689
        }
4690
4691
        void unlock() { 
4692
            if (locked_) {
4693
                m_->unlock(); 
4694
                locked_ = false;
4695
            }
4696
        } 
4697
4698
        bool try_lock() { 
4699
            if (locked_)
4700
                return true;
4701
            locked_ = m_->try_lock(); 
4702
            return locked_;
4703
        }
4704
        
4705
        bool owns_lock() const noexcept { return locked_; }
4706
4707
        void swap(WriteLock &o) noexcept { 
4708
            std::swap(m_, o.m_);
4709
            std::swap(locked_, o.locked_);
4710
        }
4711
4712
        mutex_type *mutex() const noexcept { return m_; }
4713
        
4714
        bool switch_to_unique() { return false; }
4715
4716
    private:
4717
        mutex_type *m_;
4718
        bool        locked_;
4719
    };
4720
4721
    // ----------------------------------------------------
4722
    class ReadLock
4723
    {
4724
    public:
4725
        using mutex_type = MutexType;
4726
4727
        ReadLock() :  m_(nullptr), locked_(false)  {}
4728
4729
        explicit ReadLock(mutex_type &m) : m_(&m) { 
4730
            m_->lock_shared(); 
4731
            locked_ = true; 
4732
        }
4733
4734
        ReadLock(mutex_type& m, adopt_lock_t) noexcept :
4735
            m_(&m), locked_(true) 
4736
        {}
4737
4738
        ReadLock(mutex_type& m, defer_lock_t) noexcept :
4739
            m_(&m), locked_(false) 
4740
        {}
4741
4742
        ReadLock(mutex_type& m, try_to_lock_t)  :
4743
            m_(&m), locked_(false) { 
4744
            m_->try_lock_shared(); 
4745
        }
4746
4747
        ReadLock(ReadLock &&o) noexcept :
4748
            m_(std::move(o.m_)), locked_(std::move(o.locked_)) {
4749
            o.locked_ = false;
4750
            o.m_      = nullptr;
4751
        }
4752
4753
        ReadLock& operator=(ReadLock&& other) noexcept {
4754
            ReadLock temp(std::move(other));
4755
            swap(temp);
4756
            return *this;
4757
        }
4758
4759
        ~ReadLock() {
4760
            if (locked_) 
4761
                m_->unlock_shared(); 
4762
        }
4763
4764
        void lock() { 
4765
            if (!locked_) { 
4766
                m_->lock_shared(); 
4767
                locked_ = true; 
4768
            }
4769
        }
4770
4771
        void unlock() { 
4772
            if (locked_) {
4773
                m_->unlock_shared(); 
4774
                locked_ = false;
4775
            }
4776
        } 
4777
4778
        bool try_lock() { 
4779
            if (locked_)
4780
                return true;
4781
            locked_ = m_->try_lock_shared(); 
4782
            return locked_;
4783
        }
4784
        
4785
        bool owns_lock() const noexcept { return locked_; }
4786
4787
        void swap(ReadLock &o) noexcept { 
4788
            std::swap(m_, o.m_);
4789
            std::swap(locked_, o.locked_);
4790
        }
4791
4792
        mutex_type *mutex() const noexcept { return m_; }
4793
4794
        bool switch_to_unique() { return false; }
4795
4796
    private:
4797
        mutex_type *m_;
4798
        bool        locked_;
4799
    };
4800
4801
    // ----------------------------------------------------
4802
    class ReadWriteLock
4803
    {
4804
    public:
4805
        using mutex_type = MutexType;
4806
4807
        ReadWriteLock() :  m_(nullptr), locked_(false), locked_shared_(false)  {}
4808
4809
        explicit ReadWriteLock(mutex_type &m) : m_(&m), locked_(false), locked_shared_(true)  {
4810
            m_->lock_shared(); 
4811
        }
4812
4813
        ReadWriteLock(mutex_type& m, defer_lock_t) noexcept :
4814
            m_(&m), locked_(false), locked_shared_(false)
4815
        {}
4816
4817
        ReadWriteLock(ReadWriteLock &&o) noexcept :
4818
            m_(std::move(o.m_)), locked_(o.locked_), locked_shared_(o.locked_shared_) {
4819
            o.locked_        = false;
4820
            o.locked_shared_ = false;
4821
            o.m_             = nullptr;
4822
        }
4823
4824
        ReadWriteLock& operator=(ReadWriteLock&& other) noexcept {
4825
            ReadWriteLock temp(std::move(other));
4826
            swap(temp);
4827
            return *this;
4828
        }
4829
4830
        ~ReadWriteLock() {
4831
            if (locked_shared_) 
4832
                m_->unlock_shared();
4833
            else if (locked_) 
4834
                m_->unlock();
4835
        }
4836
4837
        void lock_shared() {
4838
            assert(!locked_);
4839
            if (!locked_shared_) { 
4840
                m_->lock_shared(); 
4841
                locked_shared_ = true; 
4842
            }
4843
        }
4844
4845
        void unlock_shared() { 
4846
            if (locked_shared_) {
4847
                m_->unlock_shared(); 
4848
                locked_shared_ = false;
4849
            }
4850
        } 
4851
4852
        void lock() {
4853
            assert(!locked_shared_);
4854
            if (!locked_) { 
4855
                m_->lock(); 
4856
                locked_ = true; 
4857
            }
4858
        }
4859
4860
        void unlock() { 
4861
            if (locked_) {
4862
                m_->unlock(); 
4863
                locked_ = false;
4864
            }
4865
        } 
4866
4867
        bool owns_lock() const noexcept { return locked_; }
4868
        bool owns_shared_lock() const noexcept { return locked_shared_; }
4869
4870
        void swap(ReadWriteLock &o) noexcept { 
4871
            std::swap(m_, o.m_);
4872
            std::swap(locked_, o.locked_);
4873
            std::swap(locked_shared_, o.locked_shared_);
4874
        }
4875
4876
        mutex_type *mutex() const noexcept { return m_; }
4877
4878
        bool switch_to_unique() {
4879
            assert(locked_shared_);
4880
            unlock_shared();
4881
            lock();
4882
            return true;
4883
        }
4884
4885
    private:
4886
        mutex_type *m_;
4887
        bool        locked_;
4888
        bool        locked_shared_;
4889
    };
4890
4891
    // ----------------------------------------------------
4892
    class WriteLocks
4893
    {
4894
    public:
4895
        using mutex_type = MutexType;  
4896
4897
        explicit WriteLocks(mutex_type& m1, mutex_type& m2) : 
4898
            _m1(m1), _m2(m2)
4899
        { 
4900
            std::lock(m1, m2); 
4901
        }
4902
4903
        WriteLocks(adopt_lock_t, mutex_type& m1, mutex_type& m2) :
4904
            _m1(m1), _m2(m2)
4905
        { // adopt means we already own the mutexes
4906
        }
4907
4908
        ~WriteLocks()
4909
        {
4910
            _m1.unlock();
4911
            _m2.unlock();
4912
        }
4913
4914
        WriteLocks(WriteLocks const&) = delete;
4915
        WriteLocks& operator=(WriteLocks const&) = delete;
4916
    private:
4917
        mutex_type& _m1;
4918
        mutex_type& _m2;
4919
    };
4920
4921
    // ----------------------------------------------------
4922
    class ReadLocks
4923
    {
4924
    public:
4925
        using mutex_type = MutexType;  
4926
4927
        explicit ReadLocks(mutex_type& m1, mutex_type& m2) : 
4928
            _m1(m1), _m2(m2)
4929
        { 
4930
            _m1.lock_shared(); 
4931
            _m2.lock_shared(); 
4932
        }
4933
4934
        ReadLocks(adopt_lock_t, mutex_type& m1, mutex_type& m2) :
4935
            _m1(m1), _m2(m2)
4936
        { // adopt means we already own the mutexes
4937
        }
4938
4939
        ~ReadLocks()
4940
        {
4941
            _m1.unlock_shared();
4942
            _m2.unlock_shared();
4943
        }
4944
4945
        ReadLocks(ReadLocks const&) = delete;
4946
        ReadLocks& operator=(ReadLocks const&) = delete;
4947
    private:
4948
        mutex_type& _m1;
4949
        mutex_type& _m2;
4950
    };
4951
};
4952
4953
// ------------------------ holds a mutex ------------------------------------
4954
// Default implementation for Lockable, should work fine for std::mutex 
4955
// -----------------------------------
4956
// use as:
4957
//    using Lockable = phmap::LockableImpl<mutex_type>;
4958
//    Lockable m;
4959
//  
4960
//    Lockable::ReadWriteLock read_lock(m); // take a lock (read if supported, otherwise write)
4961
//    ... do something
4962
// 
4963
//    m.switch_to_unique(); // returns true if we had a read lock and switched to write
4964
//    // now locked for write
4965
//
4966
// ---------------------------------------------------------------------------
4967
//         Generic mutex support (always write locks)
4968
// --------------------------------------------------------------------------
4969
template <class Mtx_>
4970
class LockableImpl : public Mtx_
4971
{
4972
public:
4973
    using mutex_type      = Mtx_;
4974
    using Base            = LockableBaseImpl<Mtx_>;
4975
    using SharedLock      = typename Base::WriteLock;
4976
    using UniqueLock      = typename Base::WriteLock;
4977
    using ReadWriteLock   = typename Base::WriteLock;
4978
    using SharedLocks     = typename Base::WriteLocks;
4979
    using UniqueLocks     = typename Base::WriteLocks;
4980
};
4981
4982
// ---------------------------------------------------------------------------
4983
//          Null mutex (no-op) - when we don't want internal synchronization
4984
// ---------------------------------------------------------------------------
4985
template <>
4986
class  LockableImpl<phmap::NullMutex>: public phmap::NullMutex
4987
{
4988
public:
4989
    using mutex_type      = phmap::NullMutex;
4990
    using Base            = LockableBaseImpl<phmap::NullMutex>;
4991
    using SharedLock      = typename Base::DoNothing; 
4992
    using ReadWriteLock   = typename Base::DoNothing;
4993
    using UniqueLock      = typename Base::DoNothing; 
4994
    using SharedLocks     = typename Base::DoNothing;
4995
    using UniqueLocks     = typename Base::DoNothing;
4996
};
4997
4998
// --------------------------------------------------------------------------
4999
//         Abseil Mutex support (read and write lock support)
5000
//         use: `phmap::AbslMutex` instead of `std::mutex`
5001
// --------------------------------------------------------------------------
5002
#ifdef ABSL_SYNCHRONIZATION_MUTEX_H_
5003
    
5004
    struct AbslMutex : protected absl::Mutex
5005
    {
5006
        void lock()            ABSL_EXCLUSIVE_LOCK_FUNCTION()        { this->Lock(); }
5007
        void unlock()          ABSL_UNLOCK_FUNCTION()                { this->Unlock(); }
5008
        void try_lock()        ABSL_EXCLUSIVE_TRYLOCK_FUNCTION(true) { this->TryLock(); }
5009
        void lock_shared()     ABSL_SHARED_LOCK_FUNCTION()           { this->ReaderLock(); }
5010
        void unlock_shared()   ABSL_UNLOCK_FUNCTION()                { this->ReaderUnlock(); }
5011
        void try_lock_shared() ABSL_SHARED_TRYLOCK_FUNCTION(true)    { this->ReaderTryLock(); }
5012
    };
5013
    
5014
    template <>
5015
    class  LockableImpl<absl::Mutex> : public AbslMutex
5016
    {
5017
    public:
5018
        using mutex_type      = phmap::AbslMutex;
5019
        using Base            = LockableBaseImpl<phmap::AbslMutex>;
5020
        using SharedLock      = typename Base::ReadLock;
5021
        using ReadWriteLock   = typename Base::ReadWriteLock;
5022
        using UniqueLock      = typename Base::WriteLock;
5023
        using SharedLocks     = typename Base::ReadLocks;
5024
        using UniqueLocks     = typename Base::WriteLocks;
5025
    };
5026
5027
#endif
5028
5029
// --------------------------------------------------------------------------
5030
//         Microsoft SRWLOCK support (read and write lock support)
5031
//         use: `phmap::srwlock` instead of `std::mutex`
5032
// --------------------------------------------------------------------------
5033
#if defined(_MSC_VER) && defined(SRWLOCK_INIT)
5034
5035
    class srwlock {
5036
        SRWLOCK _lock;
5037
    public:
5038
        srwlock()              { InitializeSRWLock(&_lock); }
5039
        void lock()            { AcquireSRWLockExclusive(&_lock); }
5040
        void unlock()          { ReleaseSRWLockExclusive(&_lock); }
5041
        bool try_lock()        { return !!TryAcquireSRWLockExclusive(&_lock); }
5042
        void lock_shared()     { AcquireSRWLockShared(&_lock); }
5043
        void unlock_shared()   { ReleaseSRWLockShared(&_lock); }
5044
        bool try_lock_shared() { return !!TryAcquireSRWLockShared(&_lock); }
5045
    };
5046
5047
5048
    template<>
5049
    class LockableImpl<srwlock> : public srwlock
5050
    {
5051
    public:
5052
        using mutex_type    = srwlock;
5053
        using Base          = LockableBaseImpl<srwlock>;
5054
        using SharedLock    = typename Base::ReadLock;
5055
        using ReadWriteLock = typename Base::ReadWriteLock;
5056
        using UniqueLock    = typename Base::WriteLock;
5057
        using SharedLocks   = typename Base::ReadLocks;
5058
        using UniqueLocks   = typename Base::WriteLocks;
5059
    };
5060
5061
#endif
5062
5063
// --------------------------------------------------------------------------
5064
//         Boost shared_mutex support (read and write lock support)
5065
// --------------------------------------------------------------------------
5066
#ifdef BOOST_THREAD_SHARED_MUTEX_HPP
5067
5068
    // ---------------------------------------------------------------------------
5069
    template <>
5070
    class  LockableImpl<boost::shared_mutex> : public boost::shared_mutex
5071
    {
5072
    public:
5073
        using mutex_type      = boost::shared_mutex;
5074
        using Base            = LockableBaseImpl<boost::shared_mutex>;
5075
        using SharedLock      = boost::shared_lock<mutex_type>;
5076
        using ReadWriteLock   = typename Base::ReadWriteLock;
5077
        using UniqueLock      = boost::unique_lock<mutex_type>;
5078
        using SharedLocks     = typename Base::ReadLocks;
5079
        using UniqueLocks     = typename Base::WriteLocks;
5080
    };
5081
5082
#endif // BOOST_THREAD_SHARED_MUTEX_HPP
5083
5084
// --------------------------------------------------------------------------
5085
//         std::shared_mutex support (read and write lock support)
5086
// --------------------------------------------------------------------------
5087
#ifdef PHMAP_HAVE_SHARED_MUTEX
5088
5089
    // ---------------------------------------------------------------------------
5090
    template <>
5091
    class  LockableImpl<std::shared_mutex> : public std::shared_mutex
5092
    {
5093
    public:
5094
        using mutex_type      = std::shared_mutex;
5095
        using Base            = LockableBaseImpl<std::shared_mutex>;
5096
        using SharedLock      = std::shared_lock<mutex_type>;
5097
        using ReadWriteLock   = typename Base::ReadWriteLock;
5098
        using UniqueLock      = std::unique_lock<mutex_type>;
5099
        using SharedLocks     = typename Base::ReadLocks;
5100
        using UniqueLocks     = typename Base::WriteLocks;
5101
    };
5102
#endif // PHMAP_HAVE_SHARED_MUTEX
5103
5104
5105
}  // phmap
5106
5107
#ifdef _MSC_VER
5108
     #pragma warning(pop)  
5109
#endif
5110
5111
5112
#endif // phmap_base_h_guard_