EIC code displayed by LXR master/​include/​boost/​unordered/​detail/​foa/​core.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2025-07-05 08:50:20

 /* Common base for Boost.Unordered open-addressing tables.
  *
  * Copyright 2022-2024 Joaquin M Lopez Munoz.
  * Copyright 2023 Christian Mazakas.
  * Copyright 2024 Braden Ganetsky.
  * Distributed under the Boost Software License, Version 1.0.
  * (See accompanying file LICENSE_1_0.txt or copy at
  * http://www.boost.org/LICENSE_1_0.txt)
  *
  * See https://www.boost.org/libs/unordered for library home page.
  */
 
 #ifndef BOOST_UNORDERED_DETAIL_FOA_CORE_HPP
 #define BOOST_UNORDERED_DETAIL_FOA_CORE_HPP
 
 #include <boost/assert.hpp>
 #include <boost/config.hpp>
 #include <boost/config/workaround.hpp>
 #include <boost/core/allocator_traits.hpp>
 #include <boost/core/bit.hpp>
 #include <boost/core/empty_value.hpp>
 #include <boost/core/no_exceptions_support.hpp>
 #include <boost/core/pointer_traits.hpp>
 #include <boost/cstdint.hpp>
 #include <boost/predef.h>
 #include <boost/unordered/detail/allocator_constructed.hpp>
 #include <boost/unordered/detail/narrow_cast.hpp>
 #include <boost/unordered/detail/mulx.hpp>
 #include <boost/unordered/detail/static_assert.hpp>
 #include <boost/unordered/detail/type_traits.hpp>
 #include <boost/unordered/hash_traits.hpp>
 #include <climits>
 #include <cmath>
 #include <cstddef>
 #include <cstring>
 #include <limits>
 #include <memory>
 #include <new>
 #include <tuple>
 #include <type_traits>
 #include <utility>
 
 #if defined(BOOST_UNORDERED_ENABLE_STATS)
 #include <boost/unordered/detail/foa/cumulative_stats.hpp>
 #endif
 
 #if !defined(BOOST_UNORDERED_DISABLE_SSE2)
 #if defined(BOOST_UNORDERED_ENABLE_SSE2)|| \
     defined(__SSE2__)|| \
     defined(_M_X64)||(defined(_M_IX86_FP)&&_M_IX86_FP>=2)
 #define BOOST_UNORDERED_SSE2
 #endif
 #endif
 
 #if !defined(BOOST_UNORDERED_DISABLE_NEON)
 #if defined(BOOST_UNORDERED_ENABLE_NEON)||\
     (defined(__ARM_NEON)&&!defined(__ARM_BIG_ENDIAN))
 #define BOOST_UNORDERED_LITTLE_ENDIAN_NEON
 #endif
 #endif
 
 #if defined(BOOST_UNORDERED_SSE2)
 #include <emmintrin.h>
 #elif defined(BOOST_UNORDERED_LITTLE_ENDIAN_NEON)
 #include <arm_neon.h>
 #endif
 
 #ifdef __has_builtin
 #define BOOST_UNORDERED_HAS_BUILTIN(x) __has_builtin(x)
 #else
 #define BOOST_UNORDERED_HAS_BUILTIN(x) 0
 #endif
 
 #if !defined(NDEBUG)
 #define BOOST_UNORDERED_ASSUME(cond) BOOST_ASSERT(cond)
 #elif BOOST_UNORDERED_HAS_BUILTIN(__builtin_assume)
 #define BOOST_UNORDERED_ASSUME(cond) __builtin_assume(cond)
 #elif defined(__GNUC__) || BOOST_UNORDERED_HAS_BUILTIN(__builtin_unreachable)
 #define BOOST_UNORDERED_ASSUME(cond)    \
   do{                                   \
     if(!(cond))__builtin_unreachable(); \
   }while(0)
 #elif defined(_MSC_VER)
 #define BOOST_UNORDERED_ASSUME(cond) __assume(cond)
 #else
 #define BOOST_UNORDERED_ASSUME(cond)  \
   do{                                 \
     static_cast<void>(false&&(cond)); \
   }while(0)
 #endif
 
 /* We use BOOST_UNORDERED_PREFETCH[_ELEMENTS] macros rather than proper
  * functions because of https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109985
  */
 
 #if defined(BOOST_GCC)||defined(BOOST_CLANG)
 #define BOOST_UNORDERED_PREFETCH(p) __builtin_prefetch((const char*)(p))
 #elif defined(BOOST_UNORDERED_SSE2)
 #define BOOST_UNORDERED_PREFETCH(p) _mm_prefetch((const char*)(p),_MM_HINT_T0)
 #else
 #define BOOST_UNORDERED_PREFETCH(p) ((void)(p))
 #endif
 
 /* We have experimentally confirmed that ARM architectures get a higher
  * speedup when around the first half of the element slots in a group are
  * prefetched, whereas for Intel just the first cache line is best.
  * Please report back if you find better tunings for some particular
  * architectures.
  */
 
 #if BOOST_ARCH_ARM
 /* Cache line size can't be known at compile time, so we settle on
  * the very frequent value of 64B.
  */
 
 #define BOOST_UNORDERED_PREFETCH_ELEMENTS(p,N)                          \
   do{                                                                   \
     auto           BOOST_UNORDERED_P=(p);                               \
     constexpr int  cache_line=64;                                       \
     const char    *p0=reinterpret_cast<const char*>(BOOST_UNORDERED_P), \
                   *p1=p0+sizeof(*BOOST_UNORDERED_P)*(N)/2;              \
     for(;p0<p1;p0+=cache_line)BOOST_UNORDERED_PREFETCH(p0);             \
   }while(0)
 #else
 #define BOOST_UNORDERED_PREFETCH_ELEMENTS(p,N) BOOST_UNORDERED_PREFETCH(p)
 #endif
 
 #ifdef __has_feature
 #define BOOST_UNORDERED_HAS_FEATURE(x) __has_feature(x)
 #else
 #define BOOST_UNORDERED_HAS_FEATURE(x) 0
 #endif
 
 #if BOOST_UNORDERED_HAS_FEATURE(thread_sanitizer)|| \
     defined(__SANITIZE_THREAD__)
 #define BOOST_UNORDERED_THREAD_SANITIZER
 #endif
 
 #define BOOST_UNORDERED_STATIC_ASSERT_HASH_PRED(Hash, Pred)                    \
   static_assert(boost::unordered::detail::is_nothrow_swappable<Hash>::value,   \
     "Template parameter Hash is required to be nothrow Swappable.");           \
   static_assert(boost::unordered::detail::is_nothrow_swappable<Pred>::value,   \
     "Template parameter Pred is required to be nothrow Swappable");
 
 namespace boost{
 namespace unordered{
 namespace detail{
 namespace foa{
 
 static constexpr std::size_t default_bucket_count=0;
 
 /* foa::table_core is the common base of foa::table and foa::concurrent_table,
  * which in their turn serve as the foundational core of
  * boost::unordered_(flat|node)_(map|set) and boost::concurrent_flat_(map|set),
  * respectively. Its main internal design aspects are:
  * 
  *   - Element slots are logically split into groups of size N=15. The number
  *     of groups is always a power of two, so the number of allocated slots
        is of the form (N*2^n)-1 (final slot reserved for a sentinel mark).
  *   - Positioning is done at the group level rather than the slot level, that
  *     is, for any given element its hash value is used to locate a group and
  *     insertion is performed on the first available element of that group;
  *     if the group is full (overflow), further groups are tried using
  *     quadratic probing.
  *   - Each group has an associated 16B metadata word holding reduced hash
  *     values and overflow information. Reduced hash values are used to
  *     accelerate lookup within the group by using 128-bit SIMD or 64-bit word
  *     operations.
  */
 
 /* group15 controls metadata information of a group of N=15 element slots.
  * The 16B metadata word is organized as follows (LSB depicted rightmost):
  *
  *   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  *   |ofw|h14|h13|h13|h11|h10|h09|h08|h07|h06|h05|h04|h03|h02|h01|h00|
  *   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  *
  * hi is 0 if the i-th element slot is avalaible, 1 to mark a sentinel and,
  * when the slot is occupied, a value in the range [2,255] obtained from the
  * element's original hash value.
  * ofw is the so-called overflow byte. If insertion of an element with hash
  * value h is tried on a full group, then the (h%8)-th bit of the overflow
  * byte is set to 1 and a further group is probed. Having an overflow byte
  * brings two advantages:
  * 
  *   - There's no need to reserve a special value of hi to mark tombstone
  *     slots; each reduced hash value keeps then log2(254)=7.99 bits of the
  *     original hash (alternative approaches reserve one full bit to mark
  *     if the slot is available/deleted, so their reduced hash values are 7 bit
  *     strong only).
  *   - When doing an unsuccessful lookup (i.e. the element is not present in
  *     the table), probing stops at the first non-overflowed group. Having 8
  *     bits for signalling overflow makes it very likely that we stop at the
  *     current group (this happens when no element with the same (h%8) value
  *     has overflowed in the group), saving us an additional group check even
  *     under high-load/high-erase conditions. It is critical that hash
  *     reduction is invariant under modulo 8 (see maybe_caused_overflow).
  *
  * When looking for an element with hash value h, match(h) returns a bitmask
  * signalling which slots have the same reduced hash value. If available,
  * match uses SSE2 or (little endian) Neon 128-bit SIMD operations. On non-SIMD
  * scenarios, the logical layout described above is physically mapped to two
  * 64-bit words with *bit interleaving*, i.e. the least significant 16 bits of
  * the first 64-bit word contain the least significant bits of each byte in the
  * "logical" 128-bit word, and so forth. With this layout, match can be
  * implemented with 4 ANDs, 3 shifts, 2 XORs, 1 OR and 1 NOT.
  * 
  * IntegralWrapper<Integral> is used to implement group15's underlying
  * metadata: it behaves as a plain integral for foa::table or introduces
  * atomic ops for foa::concurrent_table. If IntegralWrapper<...> is trivially
  * constructible, so is group15, in which case it can be initialized via memset
  * etc. Where needed, group15::initialize resets the metadata to the all
  * zeros (default state).
  */
 
 #if defined(BOOST_UNORDERED_SSE2)
 
 template<template<typename> class IntegralWrapper>
 struct group15
 {
   static constexpr std::size_t N=15;
   static constexpr bool        regular_layout=true;
 
   struct dummy_group_type
   {
     alignas(16) unsigned char storage[N+1]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0};
   };
 
   inline void initialize()
   {
     _mm_store_si128(
       reinterpret_cast<__m128i*>(m),_mm_setzero_si128());
   }
 
   inline void set(std::size_t pos,std::size_t hash)
   {
     BOOST_ASSERT(pos<N);
     at(pos)=reduced_hash(hash);
   }
 
   inline void set_sentinel()
   {
     at(N-1)=sentinel_;
   }
 
   inline bool is_sentinel(std::size_t pos)const
   {
     BOOST_ASSERT(pos<N);
     return at(pos)==sentinel_;
   }
 
   static inline bool is_sentinel(unsigned char* pc)noexcept
   {
     return *pc==sentinel_;
   }
 
   inline void reset(std::size_t pos)
   {
     BOOST_ASSERT(pos<N);
     at(pos)=available_;
   }
 
   static inline void reset(unsigned char* pc)
   {
     *reinterpret_cast<slot_type*>(pc)=available_;
   }
 
   inline int match(std::size_t hash)const
   {
     return _mm_movemask_epi8(
       _mm_cmpeq_epi8(load_metadata(),_mm_set1_epi32(match_word(hash))))&0x7FFF;
   }
 
   inline bool is_not_overflowed(std::size_t hash)const
   {
     static constexpr unsigned char shift[]={1,2,4,8,16,32,64,128};
 
     return !(overflow()&shift[hash%8]);
   }
 
   inline void mark_overflow(std::size_t hash)
   {
     overflow()|=static_cast<unsigned char>(1<<(hash%8));
   }
 
   static inline bool maybe_caused_overflow(unsigned char* pc)
   {
     std::size_t pos=reinterpret_cast<uintptr_t>(pc)%sizeof(group15);
     group15    *pg=reinterpret_cast<group15*>(pc-pos);
     return !pg->is_not_overflowed(*pc);
   }
 
   inline int match_available()const
   {
     return _mm_movemask_epi8(
       _mm_cmpeq_epi8(load_metadata(),_mm_setzero_si128()))&0x7FFF;
   }
 
   inline bool is_occupied(std::size_t pos)const
   {
     BOOST_ASSERT(pos<N);
     return at(pos)!=available_;
   }
 
   static inline bool is_occupied(unsigned char* pc)noexcept
   {
     return *reinterpret_cast<slot_type*>(pc)!=available_;
   }
 
   inline int match_occupied()const
   {
     return (~match_available())&0x7FFF;
   }
 
 private:
   using slot_type=IntegralWrapper<unsigned char>;
   BOOST_UNORDERED_STATIC_ASSERT(sizeof(slot_type)==1);
 
   static constexpr unsigned char available_=0,
                                  sentinel_=1;
 
   inline __m128i load_metadata()const
   {
 #if defined(BOOST_UNORDERED_THREAD_SANITIZER)
     /* ThreadSanitizer complains on 1-byte atomic writes combined with
      * 16-byte atomic reads.
      */
 
     return _mm_set_epi8(
       (char)m[15],(char)m[14],(char)m[13],(char)m[12],
       (char)m[11],(char)m[10],(char)m[ 9],(char)m[ 8],
       (char)m[ 7],(char)m[ 6],(char)m[ 5],(char)m[ 4],
       (char)m[ 3],(char)m[ 2],(char)m[ 1],(char)m[ 0]);
 #else
     return _mm_load_si128(reinterpret_cast<const __m128i*>(m));
 #endif
   }
 
   inline static int match_word(std::size_t hash)
   {
     static constexpr boost::uint32_t word[]=
     {
       0x08080808u,0x09090909u,0x02020202u,0x03030303u,0x04040404u,0x05050505u,
       0x06060606u,0x07070707u,0x08080808u,0x09090909u,0x0A0A0A0Au,0x0B0B0B0Bu,
       0x0C0C0C0Cu,0x0D0D0D0Du,0x0E0E0E0Eu,0x0F0F0F0Fu,0x10101010u,0x11111111u,
       0x12121212u,0x13131313u,0x14141414u,0x15151515u,0x16161616u,0x17171717u,
       0x18181818u,0x19191919u,0x1A1A1A1Au,0x1B1B1B1Bu,0x1C1C1C1Cu,0x1D1D1D1Du,
       0x1E1E1E1Eu,0x1F1F1F1Fu,0x20202020u,0x21212121u,0x22222222u,0x23232323u,
       0x24242424u,0x25252525u,0x26262626u,0x27272727u,0x28282828u,0x29292929u,
       0x2A2A2A2Au,0x2B2B2B2Bu,0x2C2C2C2Cu,0x2D2D2D2Du,0x2E2E2E2Eu,0x2F2F2F2Fu,
       0x30303030u,0x31313131u,0x32323232u,0x33333333u,0x34343434u,0x35353535u,
       0x36363636u,0x37373737u,0x38383838u,0x39393939u,0x3A3A3A3Au,0x3B3B3B3Bu,
       0x3C3C3C3Cu,0x3D3D3D3Du,0x3E3E3E3Eu,0x3F3F3F3Fu,0x40404040u,0x41414141u,
       0x42424242u,0x43434343u,0x44444444u,0x45454545u,0x46464646u,0x47474747u,
       0x48484848u,0x49494949u,0x4A4A4A4Au,0x4B4B4B4Bu,0x4C4C4C4Cu,0x4D4D4D4Du,
       0x4E4E4E4Eu,0x4F4F4F4Fu,0x50505050u,0x51515151u,0x52525252u,0x53535353u,
       0x54545454u,0x55555555u,0x56565656u,0x57575757u,0x58585858u,0x59595959u,
       0x5A5A5A5Au,0x5B5B5B5Bu,0x5C5C5C5Cu,0x5D5D5D5Du,0x5E5E5E5Eu,0x5F5F5F5Fu,
       0x60606060u,0x61616161u,0x62626262u,0x63636363u,0x64646464u,0x65656565u,
       0x66666666u,0x67676767u,0x68686868u,0x69696969u,0x6A6A6A6Au,0x6B6B6B6Bu,
       0x6C6C6C6Cu,0x6D6D6D6Du,0x6E6E6E6Eu,0x6F6F6F6Fu,0x70707070u,0x71717171u,
       0x72727272u,0x73737373u,0x74747474u,0x75757575u,0x76767676u,0x77777777u,
       0x78787878u,0x79797979u,0x7A7A7A7Au,0x7B7B7B7Bu,0x7C7C7C7Cu,0x7D7D7D7Du,
       0x7E7E7E7Eu,0x7F7F7F7Fu,0x80808080u,0x81818181u,0x82828282u,0x83838383u,
       0x84848484u,0x85858585u,0x86868686u,0x87878787u,0x88888888u,0x89898989u,
       0x8A8A8A8Au,0x8B8B8B8Bu,0x8C8C8C8Cu,0x8D8D8D8Du,0x8E8E8E8Eu,0x8F8F8F8Fu,
       0x90909090u,0x91919191u,0x92929292u,0x93939393u,0x94949494u,0x95959595u,
       0x96969696u,0x97979797u,0x98989898u,0x99999999u,0x9A9A9A9Au,0x9B9B9B9Bu,
       0x9C9C9C9Cu,0x9D9D9D9Du,0x9E9E9E9Eu,0x9F9F9F9Fu,0xA0A0A0A0u,0xA1A1A1A1u,
       0xA2A2A2A2u,0xA3A3A3A3u,0xA4A4A4A4u,0xA5A5A5A5u,0xA6A6A6A6u,0xA7A7A7A7u,
       0xA8A8A8A8u,0xA9A9A9A9u,0xAAAAAAAAu,0xABABABABu,0xACACACACu,0xADADADADu,
       0xAEAEAEAEu,0xAFAFAFAFu,0xB0B0B0B0u,0xB1B1B1B1u,0xB2B2B2B2u,0xB3B3B3B3u,
       0xB4B4B4B4u,0xB5B5B5B5u,0xB6B6B6B6u,0xB7B7B7B7u,0xB8B8B8B8u,0xB9B9B9B9u,
       0xBABABABAu,0xBBBBBBBBu,0xBCBCBCBCu,0xBDBDBDBDu,0xBEBEBEBEu,0xBFBFBFBFu,
       0xC0C0C0C0u,0xC1C1C1C1u,0xC2C2C2C2u,0xC3C3C3C3u,0xC4C4C4C4u,0xC5C5C5C5u,
       0xC6C6C6C6u,0xC7C7C7C7u,0xC8C8C8C8u,0xC9C9C9C9u,0xCACACACAu,0xCBCBCBCBu,
       0xCCCCCCCCu,0xCDCDCDCDu,0xCECECECEu,0xCFCFCFCFu,0xD0D0D0D0u,0xD1D1D1D1u,
       0xD2D2D2D2u,0xD3D3D3D3u,0xD4D4D4D4u,0xD5D5D5D5u,0xD6D6D6D6u,0xD7D7D7D7u,
       0xD8D8D8D8u,0xD9D9D9D9u,0xDADADADAu,0xDBDBDBDBu,0xDCDCDCDCu,0xDDDDDDDDu,
       0xDEDEDEDEu,0xDFDFDFDFu,0xE0E0E0E0u,0xE1E1E1E1u,0xE2E2E2E2u,0xE3E3E3E3u,
       0xE4E4E4E4u,0xE5E5E5E5u,0xE6E6E6E6u,0xE7E7E7E7u,0xE8E8E8E8u,0xE9E9E9E9u,
       0xEAEAEAEAu,0xEBEBEBEBu,0xECECECECu,0xEDEDEDEDu,0xEEEEEEEEu,0xEFEFEFEFu,
       0xF0F0F0F0u,0xF1F1F1F1u,0xF2F2F2F2u,0xF3F3F3F3u,0xF4F4F4F4u,0xF5F5F5F5u,
       0xF6F6F6F6u,0xF7F7F7F7u,0xF8F8F8F8u,0xF9F9F9F9u,0xFAFAFAFAu,0xFBFBFBFBu,
       0xFCFCFCFCu,0xFDFDFDFDu,0xFEFEFEFEu,0xFFFFFFFFu,
     };
 
     return (int)word[narrow_cast<unsigned char>(hash)];
   }
 
   inline static unsigned char reduced_hash(std::size_t hash)
   {
     return narrow_cast<unsigned char>(match_word(hash));
   }
 
   inline slot_type& at(std::size_t pos)
   {
     return m[pos];
   }
 
   inline const slot_type& at(std::size_t pos)const
   {
     return m[pos];
   }
 
   inline slot_type& overflow()
   {
     return at(N);
   }
 
   inline const slot_type& overflow()const
   {
     return at(N);
   }
 
   alignas(16) slot_type m[16];
 };
 
 #elif defined(BOOST_UNORDERED_LITTLE_ENDIAN_NEON)
 
 template<template<typename> class IntegralWrapper>
 struct group15
 {
   static constexpr std::size_t N=15;
   static constexpr bool        regular_layout=true;
 
   struct dummy_group_type
   {
     alignas(16) unsigned char storage[N+1]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0};
   };
 
   inline void initialize()
   {
     vst1q_u8(reinterpret_cast<uint8_t*>(m),vdupq_n_u8(0));
   }
 
   inline void set(std::size_t pos,std::size_t hash)
   {
     BOOST_ASSERT(pos<N);
     at(pos)=reduced_hash(hash);
   }
 
   inline void set_sentinel()
   {
     at(N-1)=sentinel_;
   }
 
   inline bool is_sentinel(std::size_t pos)const
   {
     BOOST_ASSERT(pos<N);
     return pos==N-1&&at(N-1)==sentinel_;
   }
 
   static inline bool is_sentinel(unsigned char* pc)noexcept
   {
     return *reinterpret_cast<slot_type*>(pc)==sentinel_;
   }
 
   inline void reset(std::size_t pos)
   {
     BOOST_ASSERT(pos<N);
     at(pos)=available_;
   }
 
   static inline void reset(unsigned char* pc)
   {
     *reinterpret_cast<slot_type*>(pc)=available_;
   }
 
   inline int match(std::size_t hash)const
   {
     return simde_mm_movemask_epi8(vceqq_u8(
       load_metadata(),vdupq_n_u8(reduced_hash(hash))))&0x7FFF;
   }
 
   inline bool is_not_overflowed(std::size_t hash)const
   {
     static constexpr unsigned char shift[]={1,2,4,8,16,32,64,128};
 
     return !(overflow()&shift[hash%8]);
   }
 
   inline void mark_overflow(std::size_t hash)
   {
     overflow()|=static_cast<unsigned char>(1<<(hash%8));
   }
 
   static inline bool maybe_caused_overflow(unsigned char* pc)
   {
     std::size_t pos=reinterpret_cast<uintptr_t>(pc)%sizeof(group15);
     group15    *pg=reinterpret_cast<group15*>(pc-pos);
     return !pg->is_not_overflowed(*pc);
   };
 
   inline int match_available()const
   {
     return simde_mm_movemask_epi8(vceqq_u8(
       load_metadata(),vdupq_n_u8(0)))&0x7FFF;
   }
 
   inline bool is_occupied(std::size_t pos)const
   {
     BOOST_ASSERT(pos<N);
     return at(pos)!=available_;
   }
 
   static inline bool is_occupied(unsigned char* pc)noexcept
   {
     return *reinterpret_cast<slot_type*>(pc)!=available_;
   }
 
   inline int match_occupied()const
   {
     return simde_mm_movemask_epi8(vcgtq_u8(
       load_metadata(),vdupq_n_u8(0)))&0x7FFF;
   }
 
 private:
   using slot_type=IntegralWrapper<unsigned char>;
   BOOST_UNORDERED_STATIC_ASSERT(sizeof(slot_type)==1);
 
   static constexpr unsigned char available_=0,
                                  sentinel_=1;
 
   inline uint8x16_t load_metadata()const
   {
 #if defined(BOOST_UNORDERED_THREAD_SANITIZER)
     /* ThreadSanitizer complains on 1-byte atomic writes combined with
      * 16-byte atomic reads.
      */
 
     alignas(16) uint8_t data[16]={
       m[ 0],m[ 1],m[ 2],m[ 3],m[ 4],m[ 5],m[ 6],m[ 7],
       m[ 8],m[ 9],m[10],m[11],m[12],m[13],m[14],m[15]};
     return vld1q_u8(data);
 #else
     return vld1q_u8(reinterpret_cast<const uint8_t*>(m));
 #endif
   }
 
   inline static unsigned char reduced_hash(std::size_t hash)
   {
     static constexpr unsigned char table[]={
       8,9,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
       16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,
       32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
       48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,
       64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,
       80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,
       96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,
       112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,
       128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,
       144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,
       160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,
       176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,
       192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,
       208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,
       224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,
       240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,
     };
     
     return table[(unsigned char)hash];
   }
 
   /* Copied from 
    * https://github.com/simd-everywhere/simde/blob/master/simde/x86/
    * sse2.h#L3763
    */
 
   static inline int simde_mm_movemask_epi8(uint8x16_t a)
   {
     static constexpr uint8_t md[16]={
       1 << 0, 1 << 1, 1 << 2, 1 << 3,
       1 << 4, 1 << 5, 1 << 6, 1 << 7,
       1 << 0, 1 << 1, 1 << 2, 1 << 3,
       1 << 4, 1 << 5, 1 << 6, 1 << 7,
     };
 
     uint8x16_t  masked=vandq_u8(vld1q_u8(md),a);
     uint8x8x2_t tmp=vzip_u8(vget_low_u8(masked),vget_high_u8(masked));
     uint16x8_t  x=vreinterpretq_u16_u8(vcombine_u8(tmp.val[0],tmp.val[1]));
 
 #if defined(__ARM_ARCH_ISA_A64)
     return vaddvq_u16(x);
 #else
     uint64x2_t t64=vpaddlq_u32(vpaddlq_u16(x));
     return int(vgetq_lane_u64(t64,0))+int(vgetq_lane_u64(t64,1));
 #endif
   }
 
   inline slot_type& at(std::size_t pos)
   {
     return m[pos];
   }
 
   inline const slot_type& at(std::size_t pos)const
   {
     return m[pos];
   }
 
   inline slot_type& overflow()
   {
     return at(N);
   }
 
   inline const slot_type& overflow()const
   {
     return at(N);
   }
 
   alignas(16) slot_type m[16];
 };
 
 #else /* non-SIMD */
 
 template<template<typename> class IntegralWrapper>
 struct group15
 {
   static constexpr std::size_t N=15;
   static constexpr bool        regular_layout=false;
 
   struct dummy_group_type
   {
     alignas(16) boost::uint64_t m[2]=
       {0x0000000000004000ull,0x0000000000000000ull};
   };
 
   inline void initialize(){m[0]=0;m[1]=0;}
 
   inline void set(std::size_t pos,std::size_t hash)
   {
     BOOST_ASSERT(pos<N);
     set_impl(pos,reduced_hash(hash));
   }
 
   inline void set_sentinel()
   {
     set_impl(N-1,sentinel_);
   }
 
   inline bool is_sentinel(std::size_t pos)const
   {
     BOOST_ASSERT(pos<N);
     return 
       pos==N-1&&
       (m[0] & boost::uint64_t(0x4000400040004000ull))==
         boost::uint64_t(0x4000ull)&&
       (m[1] & boost::uint64_t(0x4000400040004000ull))==0;
   }
 
   inline void reset(std::size_t pos)
   {
     BOOST_ASSERT(pos<N);
     set_impl(pos,available_);
   }
 
   static inline void reset(unsigned char* pc)
   {
     std::size_t pos=reinterpret_cast<uintptr_t>(pc)%sizeof(group15);
     pc-=pos;
     reinterpret_cast<group15*>(pc)->reset(pos);
   }
 
   inline int match(std::size_t hash)const
   {
     return match_impl(reduced_hash(hash));
   }
 
   inline bool is_not_overflowed(std::size_t hash)const
   {
     return !(reinterpret_cast<const boost::uint16_t*>(m)[hash%8] & 0x8000u);
   }
 
   inline void mark_overflow(std::size_t hash)
   {
     reinterpret_cast<boost::uint16_t*>(m)[hash%8]|=0x8000u;
   }
 
   static inline bool maybe_caused_overflow(unsigned char* pc)
   {
     std::size_t     pos=reinterpret_cast<uintptr_t>(pc)%sizeof(group15);
     group15        *pg=reinterpret_cast<group15*>(pc-pos);
     boost::uint64_t x=((pg->m[0])>>pos)&0x000100010001ull;
     boost::uint32_t y=narrow_cast<boost::uint32_t>(x|(x>>15)|(x>>30));
     return !pg->is_not_overflowed(y);
   };
 
   inline int match_available()const
   {
     boost::uint64_t x=~(m[0]|m[1]);
     boost::uint32_t y=static_cast<boost::uint32_t>(x&(x>>32));
     y&=y>>16;
     return y&0x7FFF;
   }
 
   inline bool is_occupied(std::size_t pos)const
   {
     BOOST_ASSERT(pos<N);
     boost::uint64_t x=m[0]|m[1];
     return (x&(0x0001000100010001ull<<pos))!=0;
   }
 
   inline int match_occupied()const
   {
     boost::uint64_t x=m[0]|m[1];
     boost::uint32_t y=narrow_cast<boost::uint32_t>(x|(x>>32));
     y|=y>>16;
     return y&0x7FFF;
   }
 
 private:
   using word_type=IntegralWrapper<uint64_t>;
   BOOST_UNORDERED_STATIC_ASSERT(sizeof(word_type)==8);
 
   static constexpr unsigned char available_=0,
                                  sentinel_=1;
 
   inline static unsigned char reduced_hash(std::size_t hash)
   {
     static constexpr unsigned char table[]={
       8,9,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
       16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,
       32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
       48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,
       64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,
       80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,
       96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,
       112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,
       128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,
       144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,
       160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,
       176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,
       192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,
       208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,
       224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,
       240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,
     };
     
     return table[narrow_cast<unsigned char>(hash)];
   }
 
   inline void set_impl(std::size_t pos,std::size_t n)
   {
     BOOST_ASSERT(n<256);
     set_impl(m[0],pos,n&0xFu);
     set_impl(m[1],pos,n>>4);
   }
 
   static inline void set_impl(word_type& x,std::size_t pos,std::size_t n)
   {
     static constexpr boost::uint64_t mask[]=
     {
       0x0000000000000000ull,0x0000000000000001ull,0x0000000000010000ull,
       0x0000000000010001ull,0x0000000100000000ull,0x0000000100000001ull,
       0x0000000100010000ull,0x0000000100010001ull,0x0001000000000000ull,
       0x0001000000000001ull,0x0001000000010000ull,0x0001000000010001ull,
       0x0001000100000000ull,0x0001000100000001ull,0x0001000100010000ull,
       0x0001000100010001ull,
     };
     static constexpr boost::uint64_t imask[]=
     {
       0x0001000100010001ull,0x0001000100010000ull,0x0001000100000001ull,
       0x0001000100000000ull,0x0001000000010001ull,0x0001000000010000ull,
       0x0001000000000001ull,0x0001000000000000ull,0x0000000100010001ull,
       0x0000000100010000ull,0x0000000100000001ull,0x0000000100000000ull,
       0x0000000000010001ull,0x0000000000010000ull,0x0000000000000001ull,
       0x0000000000000000ull,
     };
 
     BOOST_ASSERT(pos<16&&n<16);
     x|=   mask[n]<<pos;
     x&=~(imask[n]<<pos);
   }
 
   inline int match_impl(std::size_t n)const
   {
     static constexpr boost::uint64_t mask[]=
     {
       0x0000000000000000ull,0x000000000000ffffull,0x00000000ffff0000ull,
       0x00000000ffffffffull,0x0000ffff00000000ull,0x0000ffff0000ffffull,
       0x0000ffffffff0000ull,0x0000ffffffffffffull,0xffff000000000000ull,
       0xffff00000000ffffull,0xffff0000ffff0000ull,0xffff0000ffffffffull,
       0xffffffff00000000ull,0xffffffff0000ffffull,0xffffffffffff0000ull,
       0xffffffffffffffffull,
     };
 
     BOOST_ASSERT(n<256);
     boost::uint64_t x=m[0]^mask[n&0xFu];
                     x=~((m[1]^mask[n>>4])|x);
     boost::uint32_t y=static_cast<boost::uint32_t>(x&(x>>32));
                     y&=y>>16;
     return          y&0x7FFF;
   }
 
   alignas(16) word_type m[2];
 };
 
 #endif
 
 /* foa::table_core uses a size policy to obtain the permissible sizes of the
  * group array (and, by implication, the element array) and to do the
  * hash->group mapping.
  * 
  *   - size_index(n) returns an unspecified "index" number used in other policy
  *     operations.
  *   - size(size_index_) returns the number of groups for the given index. It
  *     is guaranteed that size(size_index(n)) >= n.
  *   - min_size() is the minimum number of groups permissible, i.e.
  *     size(size_index(0)).
  *   - position(hash,size_index_) maps hash to a position in the range
  *     [0,size(size_index_)).
  * 
  * The reason we're introducing the intermediate index value for calculating
  * sizes and positions is that it allows us to optimize the implementation of
  * position, which is in the hot path of lookup and insertion operations:
  * pow2_size_policy, the actual size policy used by foa::table, returns 2^n
  * (n>0) as permissible sizes and returns the n most significant bits
  * of the hash value as the position in the group array; using a size index
  * defined as i = (bits in std::size_t) - n, we have an unbeatable
  * implementation of position(hash) as hash>>i.
  * There's a twofold reason for choosing the high bits of hash for positioning:
  *   - Multiplication-based mixing tends to yield better entropy in the high
  *     part of its result.
  *   - group15 reduced-hash values take the *low* bits of hash, and we want
  *     these values and positioning to be as uncorrelated as possible.
  */
 
 struct pow2_size_policy
 {
   static inline std::size_t size_index(std::size_t n)
   {
     // TODO: min size is 2, see if we can bring it down to 1 without loss
     // of performance
 
     return sizeof(std::size_t)*CHAR_BIT-
       (n<=2?1:((std::size_t)(boost::core::bit_width(n-1))));
   }
 
   static inline std::size_t size(std::size_t size_index_)
   {
      return std::size_t(1)<<(sizeof(std::size_t)*CHAR_BIT-size_index_);  
   }
     
   static constexpr std::size_t min_size(){return 2;}
 
   static inline std::size_t position(std::size_t hash,std::size_t size_index_)
   {
     return hash>>size_index_;
   }
 };
 
 /* size index of a group array for a given *element* capacity */
 
 template<typename Group,typename SizePolicy>
 static inline std::size_t size_index_for(std::size_t n)
 {
   /* n/N+1 == ceil((n+1)/N) (extra +1 for the sentinel) */
   return SizePolicy::size_index(n/Group::N+1);
 }
 
 /* Quadratic prober over a power-of-two range using triangular numbers.
  * mask in next(mask) must be the range size minus one (and since size is 2^n,
  * mask has exactly its n first bits set to 1).
  */
 
 struct pow2_quadratic_prober
 {
   pow2_quadratic_prober(std::size_t pos_):pos{pos_}{}
 
   inline std::size_t get()const{return pos;}
   inline std::size_t length()const{return step+1;}
 
   /* next returns false when the whole array has been traversed, which ends
    * probing (in practice, full-table probing will only happen with very small
    * arrays).
    */
 
   inline bool next(std::size_t mask)
   {
     step+=1;
     pos=(pos+step)&mask;
     return step<=mask;
   }
 
 private:
   std::size_t pos,step=0;
 };
 
 /* Mixing policies: no_mix is the identity function, and mulx_mix
  * uses the mulx function from <boost/unordered/detail/mulx.hpp>.
  *
  * foa::table_core mixes hash results with mulx_mix unless the hash is marked
  * as avalanching, i.e. of good quality
  * (see <boost/unordered/hash_traits.hpp>).
  */
 
 struct no_mix
 {
   template<typename Hash,typename T>
   static inline std::size_t mix(const Hash& h,const T& x)
   {
     return h(x);
   }
 };
 
 struct mulx_mix
 {
   template<typename Hash,typename T>
   static inline std::size_t mix(const Hash& h,const T& x)
   {
     return mulx(h(x));
   }
 };
 
 /* boost::core::countr_zero has a potentially costly check for
  * the case x==0.
  */
 
 inline unsigned int unchecked_countr_zero(int x)
 {
 #if defined(BOOST_MSVC)
   unsigned long r;
   _BitScanForward(&r,(unsigned long)x);
   return (unsigned int)r;
 #else
   BOOST_UNORDERED_ASSUME(x!=0);
   return (unsigned int)boost::core::countr_zero((unsigned int)x);
 #endif
 }
 
 /* table_arrays controls allocation, initialization and deallocation of
  * paired arrays of groups and element slots. Only one chunk of memory is
  * allocated to place both arrays: this is not done for efficiency reasons,
  * but in order to be able to properly align the group array without storing
  * additional offset information --the alignment required (16B) is usually
  * greater than alignof(std::max_align_t) and thus not guaranteed by
  * allocators.
  */
 
 template<typename Group,std::size_t Size>
 Group* dummy_groups()
 {
   /* Dummy storage initialized as if in an empty container (actually, each
    * of its groups is initialized like a separate empty container).
    * We make table_arrays::groups point to this when capacity()==0, so that
    * we are not allocating any dynamic memory and yet lookup can be implemented
    * without checking for groups==nullptr. This space won't ever be used for
    * insertion as the container's capacity is precisely zero.
    */
 
   static constexpr typename Group::dummy_group_type
   storage[Size]={typename Group::dummy_group_type(),};
 
   return reinterpret_cast<Group*>(
     const_cast<typename Group::dummy_group_type*>(storage));
 }
 
 template<
   typename Ptr,typename Ptr2,
   typename std::enable_if<!std::is_same<Ptr,Ptr2>::value>::type* = nullptr
 >
 Ptr to_pointer(Ptr2 p)
 {
   if(!p){return nullptr;}
   return boost::pointer_traits<Ptr>::pointer_to(*p);
 }
 
 template<typename Ptr>
 Ptr to_pointer(Ptr p)
 {
   return p;
 }
 
 template<typename Arrays,typename Allocator>
 struct arrays_holder
 {
   arrays_holder(const Arrays& arrays,const Allocator& al):
     arrays_{arrays},al_{al}
   {}
   
   /* not defined but VS in pre-C++17 mode needs to see it for RVO */
   arrays_holder(arrays_holder const&);
   arrays_holder& operator=(arrays_holder const&)=delete;
 
   ~arrays_holder()
   {
     if(!released_){
       arrays_.delete_(typename Arrays::allocator_type(al_),arrays_);
     }
   }
 
   const Arrays& release()
   {
     released_=true;
     return arrays_;
   }
 
 private:
   Arrays    arrays_;
   Allocator al_;
   bool      released_=false;
 };
 
 template<typename Value,typename Group,typename SizePolicy,typename Allocator>
 struct table_arrays
 {
   using allocator_type=typename boost::allocator_rebind<Allocator,Value>::type;
 
   using value_type=Value;
   using group_type=Group;
   static constexpr auto N=group_type::N;
   using size_policy=SizePolicy;
   using value_type_pointer=
     typename boost::allocator_pointer<allocator_type>::type;
   using group_type_pointer=
     typename boost::pointer_traits<value_type_pointer>::template
       rebind<group_type>;
   using group_type_pointer_traits=boost::pointer_traits<group_type_pointer>;
 
   table_arrays(
     std::size_t gsi,std::size_t gsm,
     group_type_pointer pg,value_type_pointer pe):
     groups_size_index{gsi},groups_size_mask{gsm},groups_{pg},elements_{pe}{}
 
   value_type* elements()const noexcept{return boost::to_address(elements_);}
   group_type* groups()const noexcept{return boost::to_address(groups_);}
 
   static void set_arrays(table_arrays& arrays,allocator_type al,std::size_t n)
   {
     return set_arrays(
       arrays,al,n,std::is_same<group_type*,group_type_pointer>{});
   }
 
   static void set_arrays(
     table_arrays& arrays,allocator_type al,std::size_t,
     std::false_type /* always allocate */)
   {
     using storage_traits=boost::allocator_traits<allocator_type>;
     auto groups_size_index=arrays.groups_size_index;
     auto groups_size=size_policy::size(groups_size_index);
 
     auto sal=allocator_type(al);
     arrays.elements_=storage_traits::allocate(sal,buffer_size(groups_size));
     
     /* Align arrays.groups to sizeof(group_type). table_iterator critically
       * depends on such alignment for its increment operation.
       */
 
     auto p=reinterpret_cast<unsigned char*>(arrays.elements()+groups_size*N-1);
     p+=(uintptr_t(sizeof(group_type))-
         reinterpret_cast<uintptr_t>(p))%sizeof(group_type);
     arrays.groups_=
       group_type_pointer_traits::pointer_to(*reinterpret_cast<group_type*>(p));
 
     initialize_groups(
       arrays.groups(),groups_size,
       is_trivially_default_constructible<group_type>{});
     arrays.groups()[groups_size-1].set_sentinel();
   }
 
   static void set_arrays(
     table_arrays& arrays,allocator_type al,std::size_t n,
     std::true_type /* optimize for n==0*/)
   {
     if(!n){
       arrays.groups_=dummy_groups<group_type,size_policy::min_size()>();
     }
     else{
       set_arrays(arrays,al,n,std::false_type{});
     }
   }
 
   static table_arrays new_(allocator_type al,std::size_t n)
   {
     auto         groups_size_index=size_index_for<group_type,size_policy>(n);
     auto         groups_size=size_policy::size(groups_size_index);
     table_arrays arrays{groups_size_index,groups_size-1,nullptr,nullptr};
 
     set_arrays(arrays,al,n);
     return arrays;
   }
 
   static void delete_(allocator_type al,table_arrays& arrays)noexcept
   {
     using storage_traits=boost::allocator_traits<allocator_type>;
 
     auto sal=allocator_type(al);
     if(arrays.elements()){
       storage_traits::deallocate(
         sal,arrays.elements_,buffer_size(arrays.groups_size_mask+1));
     }
   }
 
   /* combined space for elements and groups measured in sizeof(value_type)s */
 
   static std::size_t buffer_size(std::size_t groups_size)
   {
     auto buffer_bytes=
       /* space for elements (we subtract 1 because of the sentinel) */
       sizeof(value_type)*(groups_size*N-1)+
       /* space for groups + padding for group alignment */
       sizeof(group_type)*(groups_size+1)-1;
 
     /* ceil(buffer_bytes/sizeof(value_type)) */
     return (buffer_bytes+sizeof(value_type)-1)/sizeof(value_type);
   }
 
   static void initialize_groups(
     group_type* pg,std::size_t size,std::true_type /* memset */)
   {
     /* memset faster/not slower than manual, assumes all zeros is group_type's
      * default layout.
      * reinterpret_cast: GCC may complain about group_type not being trivially
      * copy-assignable when we're relying on trivial copy constructibility.
      */
 
     std::memset(
       reinterpret_cast<unsigned char*>(pg),0,sizeof(group_type)*size);
   }
 
   static void initialize_groups(
     group_type* pg,std::size_t size,std::false_type /* manual */)
   {
     while(size--!=0)::new (pg++) group_type();
   }
 
   std::size_t        groups_size_index;
   std::size_t        groups_size_mask;
   group_type_pointer groups_;
   value_type_pointer elements_;
 };
 
 #if defined(BOOST_UNORDERED_ENABLE_STATS)
 /* stats support */
 
 struct table_core_cumulative_stats
 {
   concurrent_cumulative_stats<1> insertion;
   concurrent_cumulative_stats<2> successful_lookup,
                                  unsuccessful_lookup;
 };
 
 struct table_core_insertion_stats
 {
   std::size_t            count;
   sequence_stats_summary probe_length;
 };
 
 struct table_core_lookup_stats
 {
   std::size_t            count;
   sequence_stats_summary probe_length;
   sequence_stats_summary num_comparisons;
 };
 
 struct table_core_stats
 {
   table_core_insertion_stats insertion;
   table_core_lookup_stats    successful_lookup,
                              unsuccessful_lookup;
 };
 
 #define BOOST_UNORDERED_ADD_STATS(stats,args) stats.add args
 #define BOOST_UNORDERED_SWAP_STATS(stats1,stats2) std::swap(stats1,stats2)
 #define BOOST_UNORDERED_COPY_STATS(stats1,stats2) stats1=stats2
 #define BOOST_UNORDERED_RESET_STATS_OF(x) x.reset_stats()
 #define BOOST_UNORDERED_STATS_COUNTER(name) std::size_t name=0
 #define BOOST_UNORDERED_INCREMENT_STATS_COUNTER(name) ++name
 
 #else
 
 #define BOOST_UNORDERED_ADD_STATS(stats,args) ((void)0)
 #define BOOST_UNORDERED_SWAP_STATS(stats1,stats2) ((void)0)
 #define BOOST_UNORDERED_COPY_STATS(stats1,stats2) ((void)0)
 #define BOOST_UNORDERED_RESET_STATS_OF(x) ((void)0)
 #define BOOST_UNORDERED_STATS_COUNTER(name) ((void)0)
 #define BOOST_UNORDERED_INCREMENT_STATS_COUNTER(name) ((void)0)
 
 #endif
 
 struct if_constexpr_void_else{void operator()()const{}};
 
 template<bool B,typename F,typename G=if_constexpr_void_else>
 void if_constexpr(F f,G g={})
 {
   std::get<B?0:1>(std::forward_as_tuple(f,g))();
 }
 
 template<bool B,typename T,typename std::enable_if<B>::type* =nullptr>
 void copy_assign_if(T& x,const T& y){x=y;}
 
 template<bool B,typename T,typename std::enable_if<!B>::type* =nullptr>
 void copy_assign_if(T&,const T&){}
 
 template<bool B,typename T,typename std::enable_if<B>::type* =nullptr>
 void move_assign_if(T& x,T& y){x=std::move(y);}
 
 template<bool B,typename T,typename std::enable_if<!B>::type* =nullptr>
 void move_assign_if(T&,T&){}
 
 template<bool B,typename T,typename std::enable_if<B>::type* =nullptr>
 void swap_if(T& x,T& y){using std::swap; swap(x,y);}
 
 template<bool B,typename T,typename std::enable_if<!B>::type* =nullptr>
 void swap_if(T&,T&){}
 
 template<typename Allocator>
 struct is_std_allocator:std::false_type{};
 
 template<typename T>
 struct is_std_allocator<std::allocator<T>>:std::true_type{};
 
 /* std::allocator::construct marked as deprecated */
 #if defined(_LIBCPP_SUPPRESS_DEPRECATED_PUSH)
 _LIBCPP_SUPPRESS_DEPRECATED_PUSH
 #elif defined(_STL_DISABLE_DEPRECATED_WARNING)
 _STL_DISABLE_DEPRECATED_WARNING
 #elif defined(_MSC_VER)
 #pragma warning(push)
 #pragma warning(disable:4996)
 #endif
 
 template<typename Allocator,typename Ptr,typename... Args>
 struct alloc_has_construct
 {
 private:
   template<typename Allocator2>
   static decltype(
     std::declval<Allocator2&>().construct(
       std::declval<Ptr>(),std::declval<Args&&>()...),
     std::true_type{}
   ) check(int);
 
   template<typename> static std::false_type check(...);
 
 public:
   static constexpr bool value=decltype(check<Allocator>(0))::value;
 };
 
 #if defined(_LIBCPP_SUPPRESS_DEPRECATED_POP)
 _LIBCPP_SUPPRESS_DEPRECATED_POP
 #elif defined(_STL_RESTORE_DEPRECATED_WARNING)
 _STL_RESTORE_DEPRECATED_WARNING
 #elif defined(_MSC_VER)
 #pragma warning(pop)
 #endif
 
 /* We expose the hard-coded max load factor so that tests can use it without
  * needing to pull it from an instantiated class template such as the table
  * class.
  */
 static constexpr float mlf=0.875f;
 
 template<typename Group,typename Element>
 struct table_locator
 {
   table_locator()=default;
   table_locator(Group* pg_,unsigned int n_,Element* p_):pg{pg_},n{n_},p{p_}{}
 
   explicit operator bool()const noexcept{return p!=nullptr;}
 
   Group        *pg=nullptr;
   unsigned int  n=0;
   Element      *p=nullptr;
 };
 
 struct try_emplace_args_t{};
 
 template<typename TypePolicy,typename Allocator,typename... Args>
 class alloc_cted_insert_type
 {
   using emplace_type=typename std::conditional<
     std::is_constructible<typename TypePolicy::init_type,Args...>::value,
     typename TypePolicy::init_type,
     typename TypePolicy::value_type
   >::type;
 
   using insert_type=typename std::conditional<
     std::is_constructible<typename TypePolicy::value_type,emplace_type>::value,
     emplace_type,typename TypePolicy::element_type
   >::type;
 
   using alloc_cted = allocator_constructed<Allocator, insert_type, TypePolicy>;
   alloc_cted val;
 
 public:
   alloc_cted_insert_type(const Allocator& al_,Args&&... args):val{al_,std::forward<Args>(args)...}
   {
   }
 
   insert_type& value(){return val.value();}
 };
 
 template<typename TypePolicy,typename Allocator,typename... Args>
 alloc_cted_insert_type<TypePolicy,Allocator,Args...>
 alloc_make_insert_type(const Allocator& al,Args&&... args)
 {
   return {al,std::forward<Args>(args)...};
 }
 
 template <typename TypePolicy, typename Allocator, typename KFwdRef,
   typename = void>
 class alloc_cted_or_fwded_key_type
 {
   using key_type = typename TypePolicy::key_type;
   allocator_constructed<Allocator, key_type, TypePolicy> val;
 
 public:
   alloc_cted_or_fwded_key_type(const Allocator& al_, KFwdRef k)
       : val(al_, std::forward<KFwdRef>(k))
   {
   }
 
   key_type&& move_or_fwd() { return std::move(val.value()); }
 };
 
 template <typename TypePolicy, typename Allocator, typename KFwdRef>
 class alloc_cted_or_fwded_key_type<TypePolicy, Allocator, KFwdRef,
   typename std::enable_if<
     is_similar<KFwdRef, typename TypePolicy::key_type>::value>::type>
 {
   // This specialization acts as a forwarding-reference wrapper
   BOOST_UNORDERED_STATIC_ASSERT(std::is_reference<KFwdRef>::value);
   KFwdRef ref;
 
 public:
   alloc_cted_or_fwded_key_type(const Allocator&, KFwdRef k)
       : ref(std::forward<KFwdRef>(k))
   {
   }
 
   KFwdRef move_or_fwd() { return std::forward<KFwdRef>(ref); }
 };
 
 template <typename Container>
 using is_map =
   std::integral_constant<bool, !std::is_same<typename Container::key_type,
                                  typename Container::value_type>::value>;
 
 template <typename Container, typename K>
 using is_emplace_kv_able = std::integral_constant<bool,
   is_map<Container>::value &&
     (is_similar<K, typename Container::key_type>::value ||
       is_complete_and_move_constructible<typename Container::key_type>::value)>;
 
 /* table_core. The TypePolicy template parameter is used to generate
  * instantiations suitable for either maps or sets, and introduces non-standard
  * init_type and element_type:
  *
  *   - TypePolicy::key_type and TypePolicy::value_type have the obvious
  *     meaning. TypePolicy::mapped_type is expected to be provided as well
  *     when key_type and value_type are not the same.
  *
  *   - TypePolicy::init_type is the type implicitly converted to when
  *     writing x.insert({...}). For maps, this is std::pair<Key,T> rather
  *     than std::pair<const Key,T> so that, for instance, x.insert({"hello",0})
  *     produces a cheaply moveable std::string&& ("hello") rather than
  *     a copyable const std::string&&. foa::table::insert is extended to accept
  *     both init_type and value_type references.
  *
  *   - TypePolicy::construct and TypePolicy::destroy are used for the
  *     construction and destruction of the internal types: value_type,
  *     init_type, element_type, and key_type.
  * 
  *   - TypePolicy::move is used to provide move semantics for the internal
  *     types used by the container during rehashing and emplace. These types
  *     are init_type, value_type and emplace_type. During insertion, a
  *     stack-local type will be created based on the constructibility of the
  *     value_type and the supplied arguments. TypePolicy::move is used here
  *     for transfer of ownership. Similarly, TypePolicy::move is also used
  *     during rehashing when elements are moved to the new table.
  *
  *   - TypePolicy::extract returns a const reference to the key part of
  *     a value of type value_type, init_type, element_type or
  *     decltype(TypePolicy::move(...)).
  *
  *   - TypePolicy::element_type is the type that table_arrays uses when
  *     allocating buckets, which allows us to have flat and node container.
  *     For flat containers, element_type is value_type. For node
  *     containers, it is a strong typedef to value_type*.
  *
  *   - TypePolicy::value_from returns a mutable reference to value_type from
  *     a given element_type. This is used when elements of the table themselves
  *     need to be moved, such as during move construction/assignment when
  *     allocators are unequal and there is no propagation. For all other cases,
  *     the element_type itself is moved.
  */
 
 #include <boost/unordered/detail/foa/ignore_wshadow.hpp>
 
 #if defined(BOOST_MSVC)
 #pragma warning(push)
 #pragma warning(disable:4714) /* marked as __forceinline not inlined */
 #endif
 
 #if BOOST_WORKAROUND(BOOST_MSVC,<=1900)
 /* VS2015 marks as unreachable generic catch clauses around non-throwing
  * code.
  */
 #pragma warning(push)
 #pragma warning(disable:4702)
 #endif
 
 template<
   typename TypePolicy,typename Group,template<typename...> class Arrays,
   typename SizeControl,typename Hash,typename Pred,typename Allocator
 >
 class 
 
 #if defined(_MSC_VER)&&_MSC_FULL_VER>=190023918
 __declspec(empty_bases) /* activate EBO with multiple inheritance */
 #endif
 
 table_core:empty_value<Hash,0>,empty_value<Pred,1>,empty_value<Allocator,2>
 {
 public:
   using type_policy=TypePolicy;
   using group_type=Group;
   static constexpr auto N=group_type::N;
   using size_policy=pow2_size_policy;
   using prober=pow2_quadratic_prober;
   using mix_policy=typename std::conditional<
     hash_is_avalanching<Hash>::value,
     no_mix,
     mulx_mix
   >::type;
   using alloc_traits=boost::allocator_traits<Allocator>;
   using element_type=typename type_policy::element_type;
   using arrays_type=Arrays<element_type,group_type,size_policy,Allocator>;
   using size_ctrl_type=SizeControl;
   static constexpr auto uses_fancy_pointers=!std::is_same<
     typename alloc_traits::pointer,
     typename alloc_traits::value_type*
   >::value;
 
   using key_type=typename type_policy::key_type;
   using init_type=typename type_policy::init_type;
   using value_type=typename type_policy::value_type;
   using hasher=Hash;
   using key_equal=Pred;
   using allocator_type=Allocator;
   using pointer=value_type*;
   using const_pointer=const value_type*;
   using reference=value_type&;
   using const_reference=const value_type&;
   using size_type=std::size_t;
   using difference_type=std::ptrdiff_t;
   using locator=table_locator<group_type,element_type>;
   using arrays_holder_type=arrays_holder<arrays_type,Allocator>;
 
 #if defined(BOOST_UNORDERED_ENABLE_STATS)
   using cumulative_stats=table_core_cumulative_stats;
   using stats=table_core_stats;
 #endif
 
   table_core(
     std::size_t n=default_bucket_count,const Hash& h_=Hash(),
     const Pred& pred_=Pred(),const Allocator& al_=Allocator()):
     hash_base{empty_init,h_},pred_base{empty_init,pred_},
     allocator_base{empty_init,al_},arrays(new_arrays(n)),
     size_ctrl{initial_max_load(),0}
     {}
 
   /* genericize on an ArraysFn so that we can do things like delay an
    * allocation for the group_access data required by cfoa after the move
    * constructors of Hash, Pred have been invoked
    */
   template<typename ArraysFn>
   table_core(
     Hash&& h_,Pred&& pred_,Allocator&& al_,
     ArraysFn arrays_fn,const size_ctrl_type& size_ctrl_):
     hash_base{empty_init,std::move(h_)},
     pred_base{empty_init,std::move(pred_)},
     allocator_base{empty_init,std::move(al_)},
     arrays(arrays_fn()),size_ctrl(size_ctrl_)
   {}
 
   table_core(const table_core& x):
     table_core{x,alloc_traits::select_on_container_copy_construction(x.al())}{}
 
   template<typename ArraysFn>
   table_core(table_core&& x,arrays_holder_type&& ah,ArraysFn arrays_fn):
     table_core(
       std::move(x.h()),std::move(x.pred()),std::move(x.al()),
       arrays_fn,x.size_ctrl)
   {
     x.arrays=ah.release();
     x.size_ctrl.ml=x.initial_max_load();
     x.size_ctrl.size=0;
     BOOST_UNORDERED_SWAP_STATS(cstats,x.cstats);
   }
 
   table_core(table_core&& x)
     noexcept(
       std::is_nothrow_move_constructible<Hash>::value&&
       std::is_nothrow_move_constructible<Pred>::value&&
       std::is_nothrow_move_constructible<Allocator>::value&&
       !uses_fancy_pointers):
     table_core{
       std::move(x),x.make_empty_arrays(),[&x]{return x.arrays;}}
   {}
 
   table_core(const table_core& x,const Allocator& al_):
     table_core{std::size_t(std::ceil(float(x.size())/mlf)),x.h(),x.pred(),al_}
   {
     copy_elements_from(x);
   }
 
   table_core(table_core&& x,const Allocator& al_):
     table_core{std::move(x.h()),std::move(x.pred()),al_}
   {
     if(al()==x.al()){
       using std::swap;
       swap(arrays,x.arrays);
       swap(size_ctrl,x.size_ctrl);
       BOOST_UNORDERED_SWAP_STATS(cstats,x.cstats);
     }
     else{
       reserve(x.size());
       clear_on_exit c{x};
       (void)c; /* unused var warning */
       BOOST_UNORDERED_RESET_STATS_OF(x);
 
       /* This works because subsequent x.clear() does not depend on the
        * elements' values.
        */
       x.for_all_elements([this](element_type* p){
         unchecked_insert(type_policy::move(type_policy::value_from(*p)));
       });
     }
   }
 
   ~table_core()noexcept
   {
     for_all_elements([this](element_type* p){
       destroy_element(p);
     });
     delete_arrays(arrays);
   }
 
   std::size_t initial_max_load()const
   {
     static constexpr std::size_t small_capacity=2*N-1;
 
     auto capacity_=capacity();
     if(capacity_<=small_capacity){
       return capacity_; /* we allow 100% usage */
     }
     else{
       return (std::size_t)(mlf*(float)(capacity_));
     }
   }
 
   arrays_holder_type make_empty_arrays()const
   {
     return make_arrays(0);
   }
 
   table_core& operator=(const table_core& x)
   {
     BOOST_UNORDERED_STATIC_ASSERT_HASH_PRED(Hash, Pred)
 
     static constexpr auto pocca=
       alloc_traits::propagate_on_container_copy_assignment::value;
 
     if(this!=std::addressof(x)){
       /* If copy construction here winds up throwing, the container is still
        * left intact so we perform these operations first.
        */
       hasher    tmp_h=x.h();
       key_equal tmp_p=x.pred();
 
       clear();
 
       /* Because we've asserted at compile-time that Hash and Pred are nothrow
        * swappable, we can safely mutate our source container and maintain
        * consistency between the Hash, Pred compatibility.
        */
       using std::swap;
       swap(h(),tmp_h);
       swap(pred(),tmp_p);
 
       if_constexpr<pocca>([&,this]{
         if(al()!=x.al()){
           auto ah=x.make_arrays(std::size_t(std::ceil(float(x.size())/mlf)));
           delete_arrays(arrays);
           arrays=ah.release();
           size_ctrl.ml=initial_max_load();
         }
         copy_assign_if<pocca>(al(),x.al());
       });
       /* noshrink: favor memory reuse over tightness */
       noshrink_reserve(x.size());
       copy_elements_from(x);
     }
     return *this;
   }
 
 #if defined(BOOST_MSVC)
 #pragma warning(push)
 #pragma warning(disable:4127) /* conditional expression is constant */
 #endif
 
   table_core& operator=(table_core&& x)
     noexcept(
       (alloc_traits::propagate_on_container_move_assignment::value||
       alloc_traits::is_always_equal::value)&&!uses_fancy_pointers)
   {
     BOOST_UNORDERED_STATIC_ASSERT_HASH_PRED(Hash, Pred)
 
     static constexpr auto pocma=
       alloc_traits::propagate_on_container_move_assignment::value;
 
     if(this!=std::addressof(x)){
       /* Given ambiguity in implementation strategies briefly discussed here:
        * https://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#2227
        *
        * we opt into requiring nothrow swappability and eschew the move
        * operations associated with Hash, Pred.
        *
        * To this end, we ensure that the user never has to consider the
        * moved-from state of their Hash, Pred objects
        */
 
       using std::swap;
 
       clear();
 
       if(pocma||al()==x.al()){
         auto ah=x.make_empty_arrays();
         swap(h(),x.h());
         swap(pred(),x.pred());
         delete_arrays(arrays);
         move_assign_if<pocma>(al(),x.al());
         arrays=x.arrays;
         size_ctrl.ml=std::size_t(x.size_ctrl.ml);
         size_ctrl.size=std::size_t(x.size_ctrl.size);
         BOOST_UNORDERED_COPY_STATS(cstats,x.cstats);
         x.arrays=ah.release();
         x.size_ctrl.ml=x.initial_max_load();
         x.size_ctrl.size=0;
         BOOST_UNORDERED_RESET_STATS_OF(x);
       }
       else{
         swap(h(),x.h());
         swap(pred(),x.pred());
 
         /* noshrink: favor memory reuse over tightness */
         noshrink_reserve(x.size());
         clear_on_exit c{x};
         (void)c; /* unused var warning */
         BOOST_UNORDERED_RESET_STATS_OF(x);
 
         /* This works because subsequent x.clear() does not depend on the
          * elements' values.
          */
         x.for_all_elements([this](element_type* p){
           unchecked_insert(type_policy::move(type_policy::value_from(*p)));
         });
       }
     }
     return *this;
   }
 
 #if defined(BOOST_MSVC)
 #pragma warning(pop) /* C4127 */
 #endif
 
   allocator_type get_allocator()const noexcept{return al();}
 
   bool        empty()const noexcept{return size()==0;}
   std::size_t size()const noexcept{return size_ctrl.size;}
   std::size_t max_size()const noexcept{return SIZE_MAX;}
 
   BOOST_FORCEINLINE
   void erase(group_type* pg,unsigned int pos,element_type* p)noexcept
   {
     destroy_element(p);
     recover_slot(pg,pos);
   }
 
   BOOST_FORCEINLINE
   void erase(unsigned char* pc,element_type* p)noexcept
   {
     destroy_element(p);
     recover_slot(pc);
   }
 
   template<typename Key>
   BOOST_FORCEINLINE locator find(const Key& x)const
   {
     auto hash=hash_for(x);
     return find(x,position_for(hash),hash);
   }
 
 #if defined(BOOST_MSVC)
 /* warning: forcing value to bool 'true' or 'false' in bool(pred()...) */
 #pragma warning(push)
 #pragma warning(disable:4800)
 #endif
 
   template<typename Key>
   BOOST_FORCEINLINE locator find(
     const Key& x,std::size_t pos0,std::size_t hash)const
   {    
     BOOST_UNORDERED_STATS_COUNTER(num_cmps);
     prober pb(pos0);
     do{
       auto pos=pb.get();
       auto pg=arrays.groups()+pos;
       auto mask=pg->match(hash);
       if(mask){
         auto elements=arrays.elements();
         BOOST_UNORDERED_ASSUME(elements!=nullptr);
         auto p=elements+pos*N;
         BOOST_UNORDERED_PREFETCH_ELEMENTS(p,N);
         do{
           BOOST_UNORDERED_INCREMENT_STATS_COUNTER(num_cmps);
           auto n=unchecked_countr_zero(mask);
           if(BOOST_LIKELY(bool(pred()(x,key_from(p[n]))))){
             BOOST_UNORDERED_ADD_STATS(
               cstats.successful_lookup,(pb.length(),num_cmps));
             return {pg,n,p+n};
           }
           mask&=mask-1;
         }while(mask);
       }
       if(BOOST_LIKELY(pg->is_not_overflowed(hash))){
         BOOST_UNORDERED_ADD_STATS(
           cstats.unsuccessful_lookup,(pb.length(),num_cmps));
         return {};
       }
     }
     while(BOOST_LIKELY(pb.next(arrays.groups_size_mask)));
     BOOST_UNORDERED_ADD_STATS(
       cstats.unsuccessful_lookup,(pb.length(),num_cmps));
     return {};
   }
 
 #if defined(BOOST_MSVC)
 #pragma warning(pop) /* C4800 */
 #endif
 
   void swap(table_core& x)
     noexcept(
       alloc_traits::propagate_on_container_swap::value||
       alloc_traits::is_always_equal::value)
   {
     BOOST_UNORDERED_STATIC_ASSERT_HASH_PRED(Hash, Pred)
 
     static constexpr auto pocs=
       alloc_traits::propagate_on_container_swap::value;
 
     using std::swap;
     if_constexpr<pocs>([&,this]{
       swap_if<pocs>(al(),x.al());
     },
     [&,this]{ /* else */
       BOOST_ASSERT(al()==x.al());
       (void)this; /* makes sure captured this is used */
     });
 
     swap(h(),x.h());
     swap(pred(),x.pred());
     swap(arrays,x.arrays);
     swap(size_ctrl,x.size_ctrl);
   }
 
   void clear()noexcept
   {
     auto p=arrays.elements();
     if(p){
       for(auto pg=arrays.groups(),last=pg+arrays.groups_size_mask+1;
           pg!=last;++pg,p+=N){
         auto mask=match_really_occupied(pg,last);
         while(mask){
           destroy_element(p+unchecked_countr_zero(mask));
           mask&=mask-1;
         }
         /* we wipe the entire metadata to reset the overflow byte as well */
         pg->initialize();
       }
       arrays.groups()[arrays.groups_size_mask].set_sentinel();
       size_ctrl.ml=initial_max_load();
       size_ctrl.size=0;
     }
   }
 
   hasher hash_function()const{return h();}
   key_equal key_eq()const{return pred();}
 
   std::size_t capacity()const noexcept
   {
     return arrays.elements()?(arrays.groups_size_mask+1)*N-1:0;
   }
   
   float load_factor()const noexcept
   {
     if(capacity()==0)return 0;
     else             return float(size())/float(capacity());
   }
 
   float max_load_factor()const noexcept{return mlf;}
 
   std::size_t max_load()const noexcept{return size_ctrl.ml;}
 
   void rehash(std::size_t n)
   {
     auto m=size_t(std::ceil(float(size())/mlf));
     if(m>n)n=m;
     if(n)n=capacity_for(n); /* exact resulting capacity */
 
     if(n!=capacity())unchecked_rehash(n);
   }
 
   void reserve(std::size_t n)
   {
     rehash(std::size_t(std::ceil(float(n)/mlf)));
   }
 
 #if defined(BOOST_UNORDERED_ENABLE_STATS)
   stats get_stats()const
   {
     auto insertion=cstats.insertion.get_summary();
     auto successful_lookup=cstats.successful_lookup.get_summary();
     auto unsuccessful_lookup=cstats.unsuccessful_lookup.get_summary();
     return{
       {
         insertion.count,
         insertion.sequence_summary[0]
       },
       {
         successful_lookup.count,
         successful_lookup.sequence_summary[0],
         successful_lookup.sequence_summary[1]
       },
       {
         unsuccessful_lookup.count,
         unsuccessful_lookup.sequence_summary[0],
         unsuccessful_lookup.sequence_summary[1]
       },
     };
   }
 
   void reset_stats()noexcept
   {
     cstats.insertion.reset();
     cstats.successful_lookup.reset();
     cstats.unsuccessful_lookup.reset();
   }
 #endif
 
   friend bool operator==(const table_core& x,const table_core& y)
   {
     return
       x.size()==y.size()&&
       x.for_all_elements_while([&](element_type* p){
         auto loc=y.find(key_from(*p));
         return loc&&
           const_cast<const value_type&>(type_policy::value_from(*p))==
           const_cast<const value_type&>(type_policy::value_from(*loc.p));
       });
   }
 
   friend bool operator!=(const table_core& x,const table_core& y)
   {
     return !(x==y);
   }
 
   struct clear_on_exit
   {
     ~clear_on_exit(){x.clear();}
     table_core& x;
   };
 
   Hash&            h(){return hash_base::get();}
   const Hash&      h()const{return hash_base::get();}
   Pred&            pred(){return pred_base::get();}
   const Pred&      pred()const{return pred_base::get();}
   Allocator&       al(){return allocator_base::get();}
   const Allocator& al()const{return allocator_base::get();}
 
   template<typename... Args>
   void construct_element(element_type* p,Args&&... args)
   {
     type_policy::construct(al(),p,std::forward<Args>(args)...);
   }
 
   template<typename... Args>
   void construct_element(element_type* p,try_emplace_args_t,Args&&... args)
   {
     construct_element_from_try_emplace_args(
       p,
       std::integral_constant<bool,std::is_same<key_type,value_type>::value>{},
       std::forward<Args>(args)...);
   }
 
   void destroy_element(element_type* p)noexcept
   {
     type_policy::destroy(al(),p);
   }
 
   struct destroy_element_on_exit
   {
     ~destroy_element_on_exit(){this_->destroy_element(p);}
     table_core   *this_;
     element_type *p;
   };
 
   template<typename T>
   static inline auto key_from(const T& x)
     ->decltype(type_policy::extract(x))
   {
     return type_policy::extract(x);
   }
 
   template<typename Key,typename... Args>
   static inline const Key& key_from(
     try_emplace_args_t,const Key& x,const Args&...)
   {
     return x;
   }
 
   template<typename Key>
   inline std::size_t hash_for(const Key& x)const
   {
     return mix_policy::mix(h(),x);
   }
 
   inline std::size_t position_for(std::size_t hash)const
   {
     return position_for(hash,arrays);
   }
 
   static inline std::size_t position_for(
     std::size_t hash,const arrays_type& arrays_)
   {
     return size_policy::position(hash,arrays_.groups_size_index);
   }
 
   static inline int match_really_occupied(group_type* pg,group_type* last)
   {
     /* excluding the sentinel */
     return pg->match_occupied()&~(int(pg==last-1)<<(N-1));
   }
 
   template<typename... Args>
   locator unchecked_emplace_at(
     std::size_t pos0,std::size_t hash,Args&&... args)
   {
     auto res=nosize_unchecked_emplace_at(
       arrays,pos0,hash,std::forward<Args>(args)...);
     ++size_ctrl.size;
     return res;
   }
 
   BOOST_NOINLINE void unchecked_rehash_for_growth()
   {
     auto new_arrays_=new_arrays_for_growth();
     unchecked_rehash(new_arrays_);
   }
 
   template<typename... Args>
   BOOST_NOINLINE locator
   unchecked_emplace_with_rehash(std::size_t hash,Args&&... args)
   {
     auto    new_arrays_=new_arrays_for_growth();
     locator it;
     BOOST_TRY{
       /* strong exception guarantee -> try insertion before rehash */
       it=nosize_unchecked_emplace_at(
         new_arrays_,position_for(hash,new_arrays_),
         hash,std::forward<Args>(args)...);
     }
     BOOST_CATCH(...){
       delete_arrays(new_arrays_);
       BOOST_RETHROW
     }
     BOOST_CATCH_END
 
     /* new_arrays_ lifetime taken care of by unchecked_rehash */
     unchecked_rehash(new_arrays_);
     ++size_ctrl.size;
     return it;
   }
 
   void noshrink_reserve(std::size_t n)
   {
     /* used only on assignment after element clearance */
     BOOST_ASSERT(empty());
 
     if(n){
       n=std::size_t(std::ceil(float(n)/mlf)); /* elements -> slots */
       n=capacity_for(n); /* exact resulting capacity */
 
       if(n>capacity()){
         auto new_arrays_=new_arrays(n);
         delete_arrays(arrays);
         arrays=new_arrays_;
         size_ctrl.ml=initial_max_load();
       }
     }
   }
 
   template<typename F>
   void for_all_elements(F f)const
   {
     for_all_elements(arrays,f);
   }
 
   template<typename F>
   static auto for_all_elements(const arrays_type& arrays_,F f)
     ->decltype(f(nullptr),void())
   {
     for_all_elements_while(arrays_,[&](element_type* p){f(p);return true;});
   }
 
   template<typename F>
   static auto for_all_elements(const arrays_type& arrays_,F f)
     ->decltype(f(nullptr,0,nullptr),void())
   {
     for_all_elements_while(
       arrays_,[&](group_type* pg,unsigned int n,element_type* p)
         {f(pg,n,p);return true;});
   }
 
   template<typename F>
   bool for_all_elements_while(F f)const
   {
     return for_all_elements_while(arrays,f);
   }
 
   template<typename F>
   static auto for_all_elements_while(const arrays_type& arrays_,F f)
     ->decltype(f(nullptr),bool())
   {
     return for_all_elements_while(
       arrays_,[&](group_type*,unsigned int,element_type* p){return f(p);});
   }
 
   template<typename F>
   static auto for_all_elements_while(const arrays_type& arrays_,F f)
     ->decltype(f(nullptr,0,nullptr),bool())
   {
     auto p=arrays_.elements();
     if(p){
       for(auto pg=arrays_.groups(),last=pg+arrays_.groups_size_mask+1;
           pg!=last;++pg,p+=N){
         auto mask=match_really_occupied(pg,last);
         while(mask){
           auto n=unchecked_countr_zero(mask);
           if(!f(pg,n,p+n))return false;
           mask&=mask-1;
         }
       }
     }
     return true;
   }
 
   arrays_type              arrays;
   size_ctrl_type           size_ctrl;
 
 #if defined(BOOST_UNORDERED_ENABLE_STATS)
   mutable cumulative_stats cstats;
 #endif
 
 private:
   template<
     typename,typename,template<typename...> class,
     typename,typename,typename,typename
   >
   friend class table_core;
 
   using hash_base=empty_value<Hash,0>;
   using pred_base=empty_value<Pred,1>;
   using allocator_base=empty_value<Allocator,2>;
 
   /* used by allocator-extended move ctor */
 
   table_core(Hash&& h_,Pred&& pred_,const Allocator& al_):
     hash_base{empty_init,std::move(h_)},
     pred_base{empty_init,std::move(pred_)},
     allocator_base{empty_init,al_},arrays(new_arrays(0)),
     size_ctrl{initial_max_load(),0}
   {
   }
 
   arrays_type new_arrays(std::size_t n)const
   {
     return arrays_type::new_(typename arrays_type::allocator_type(al()),n);
   }
 
   arrays_type new_arrays_for_growth()const
   {
     /* Due to the anti-drift mechanism (see recover_slot), the new arrays may
      * be of the same size as the old arrays; in the limit, erasing one
      * element at full load and then inserting could bring us back to the same
      * capacity after a costly rehash. To avoid this, we jump to the next
      * capacity level when the number of erased elements is <= 10% of total
      * elements at full load, which is implemented by requesting additional
      * F*size elements, with F = P * 10% / (1 - P * 10%), where P is the
      * probability of an element having caused overflow; P has been measured as
      * ~0.162 under ideal conditions, yielding F ~ 0.0165 ~ 1/61.
      */
     return new_arrays(std::size_t(
       std::ceil(static_cast<float>(size()+size()/61+1)/mlf)));
   }
 
   void delete_arrays(arrays_type& arrays_)noexcept
   {
     arrays_type::delete_(typename arrays_type::allocator_type(al()),arrays_);
   }
 
   arrays_holder_type make_arrays(std::size_t n)const
   {
     return {new_arrays(n),al()};
   }
 
   template<typename Key,typename... Args>
   void construct_element_from_try_emplace_args(
     element_type* p,std::false_type,Key&& x,Args&&... args)
   {
     type_policy::construct(
       this->al(),p,
       std::piecewise_construct,
       std::forward_as_tuple(std::forward<Key>(x)),
       std::forward_as_tuple(std::forward<Args>(args)...));
   }
 
   /* This overload allows boost::unordered_flat_set to internally use
    * try_emplace to implement heterogeneous insert (P2363).
    */
 
   template<typename Key>
   void construct_element_from_try_emplace_args(
     element_type* p,std::true_type,Key&& x)
   {
     type_policy::construct(this->al(),p,std::forward<Key>(x));
   }
 
   void copy_elements_from(const table_core& x)
   {
     BOOST_ASSERT(empty());
     BOOST_ASSERT(this!=std::addressof(x));
     if(arrays.groups_size_mask==x.arrays.groups_size_mask){
       fast_copy_elements_from(x);
     }
     else{
       x.for_all_elements([this](const element_type* p){
         unchecked_insert(*p);
       });
     }
   }
 
   void fast_copy_elements_from(const table_core& x)
   {
     if(arrays.elements()&&x.arrays.elements()){
       copy_elements_array_from(x);
       copy_groups_array_from(x);
       size_ctrl.ml=std::size_t(x.size_ctrl.ml);
       size_ctrl.size=std::size_t(x.size_ctrl.size);
     }
   }
 
   void copy_elements_array_from(const table_core& x)
   {
     copy_elements_array_from(
       x,
       std::integral_constant<
         bool,
         is_trivially_copy_constructible<element_type>::value&&(
           is_std_allocator<Allocator>::value||
           !alloc_has_construct<Allocator,value_type*,const value_type&>::value)
       >{}
     );
   }
 
   void copy_elements_array_from(
     const table_core& x,std::true_type /* -> memcpy */)
   {
     /* reinterpret_cast: GCC may complain about value_type not being trivially
      * copy-assignable when we're relying on trivial copy constructibility.
      */
     std::memcpy(
       reinterpret_cast<unsigned char*>(arrays.elements()),
       reinterpret_cast<unsigned char*>(x.arrays.elements()),
       x.capacity()*sizeof(value_type));
   }
 
   void copy_elements_array_from(
     const table_core& x,std::false_type /* -> manual */)
   {
     std::size_t num_constructed=0;
     BOOST_TRY{
       x.for_all_elements([&,this](const element_type* p){
         construct_element(arrays.elements()+(p-x.arrays.elements()),*p);
         ++num_constructed;
       });
     }
     BOOST_CATCH(...){
       if(num_constructed){
         x.for_all_elements_while([&,this](const element_type* p){
           destroy_element(arrays.elements()+(p-x.arrays.elements()));
           return --num_constructed!=0;
         });
       }
       BOOST_RETHROW
     }
     BOOST_CATCH_END
   }
 
   void copy_groups_array_from(const table_core& x) {
     copy_groups_array_from(x,is_trivially_copy_assignable<group_type>{});
   }
 
   void copy_groups_array_from(
     const table_core& x, std::true_type /* -> memcpy */)
   {
     std::memcpy(
       arrays.groups(),x.arrays.groups(),
       (arrays.groups_size_mask+1)*sizeof(group_type));
   }
 
   void copy_groups_array_from(
     const table_core& x, std::false_type /* -> manual */) 
   {
     auto pg=arrays.groups();
     auto xpg=x.arrays.groups();
     for(std::size_t i=0;i<arrays.groups_size_mask+1;++i){
       pg[i]=xpg[i];
     }
   }
 
   void recover_slot(unsigned char* pc)
   {
     /* If this slot potentially caused overflow, we decrease the maximum load
      * so that average probe length won't increase unboundedly in repeated
      * insert/erase cycles (drift).
      */
     size_ctrl.ml-=group_type::maybe_caused_overflow(pc);
     group_type::reset(pc);
     --size_ctrl.size;
   }
 
   void recover_slot(group_type* pg,std::size_t pos)
   {
     recover_slot(reinterpret_cast<unsigned char*>(pg)+pos);
   }
 
   static std::size_t capacity_for(std::size_t n)
   {
     return size_policy::size(size_index_for<group_type,size_policy>(n))*N-1;
   }
 
   BOOST_NOINLINE void unchecked_rehash(std::size_t n)
   {
     auto new_arrays_=new_arrays(n);
     unchecked_rehash(new_arrays_);
   }
 
   BOOST_NOINLINE void unchecked_rehash(arrays_type& new_arrays_)
   {
     std::size_t num_destroyed=0;
     BOOST_TRY{
       for_all_elements([&,this](element_type* p){
         nosize_transfer_element(p,new_arrays_,num_destroyed);
       });
     }
     BOOST_CATCH(...){
       if(num_destroyed){
         for_all_elements_while(
           [&,this](group_type* pg,unsigned int n,element_type*){
             recover_slot(pg,n);
             return --num_destroyed!=0;
           }
         );
       }
       for_all_elements(new_arrays_,[this](element_type* p){
         destroy_element(p);
       });
       delete_arrays(new_arrays_);
       BOOST_RETHROW
     }
     BOOST_CATCH_END
 
     /* either all moved and destroyed or all copied */
     BOOST_ASSERT(num_destroyed==size()||num_destroyed==0);
     if(num_destroyed!=size()){
       for_all_elements([this](element_type* p){
         destroy_element(p);
       });
     }
     delete_arrays(arrays);
     arrays=new_arrays_;
     size_ctrl.ml=initial_max_load();
   }
 
   template<typename Value>
   void unchecked_insert(Value&& x)
   {
     auto hash=hash_for(key_from(x));
     unchecked_emplace_at(position_for(hash),hash,std::forward<Value>(x));
   }
 
   void nosize_transfer_element(
     element_type* p,const arrays_type& arrays_,std::size_t& num_destroyed)
   {
     nosize_transfer_element(
       p,hash_for(key_from(*p)),arrays_,num_destroyed,
       std::integral_constant< /* std::move_if_noexcept semantics */
         bool,
         std::is_nothrow_move_constructible<init_type>::value||
         !std::is_same<element_type,value_type>::value||
         !std::is_copy_constructible<element_type>::value>{});
   }
 
   void nosize_transfer_element(
     element_type* p,std::size_t hash,const arrays_type& arrays_,
     std::size_t& num_destroyed,std::true_type /* ->move */)
   {
     /* Destroy p even if an an exception is thrown in the middle of move
      * construction, which could leave the source half-moved.
      */
     ++num_destroyed;
     destroy_element_on_exit d{this,p};
     (void)d; /* unused var warning */
     nosize_unchecked_emplace_at(
       arrays_,position_for(hash,arrays_),hash,type_policy::move(*p));
   }
 
   void nosize_transfer_element(
     element_type* p,std::size_t hash,const arrays_type& arrays_,
     std::size_t& /*num_destroyed*/,std::false_type /* ->copy */)
   {
     nosize_unchecked_emplace_at(
       arrays_,position_for(hash,arrays_),hash,
       const_cast<const element_type&>(*p));
   }
 
   template<typename... Args>
   locator nosize_unchecked_emplace_at(
     const arrays_type& arrays_,std::size_t pos0,std::size_t hash,
     Args&&... args)
   {
     for(prober pb(pos0);;pb.next(arrays_.groups_size_mask)){
       auto pos=pb.get();
       auto pg=arrays_.groups()+pos;
       auto mask=pg->match_available();
       if(BOOST_LIKELY(mask!=0)){
         auto n=unchecked_countr_zero(mask);
         auto p=arrays_.elements()+pos*N+n;
         construct_element(p,std::forward<Args>(args)...);
         pg->set(n,hash);
         BOOST_UNORDERED_ADD_STATS(cstats.insertion,(pb.length()));
         return {pg,n,p};
       }
       else pg->mark_overflow(hash);
     }
   }
 };
 
 #if BOOST_WORKAROUND(BOOST_MSVC,<=1900)
 #pragma warning(pop) /* C4702 */
 #endif
 
 #if defined(BOOST_MSVC)
 #pragma warning(pop) /* C4714 */
 #endif
 
 #include <boost/unordered/detail/foa/restore_wshadow.hpp>
 
 } /* namespace foa */
 } /* namespace detail */
 } /* namespace unordered */
 } /* namespace boost */
 
 #undef BOOST_UNORDERED_STATIC_ASSERT_HASH_PRED
 #undef BOOST_UNORDERED_HAS_FEATURE
 #undef BOOST_UNORDERED_HAS_BUILTIN
 #endif

This page was automatically generated by the 2.3.7 LXR engine. The LXR team