Update documentation

.drone.jsonnet

@@ -308,40 +308,51 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
     linux_pipeline(
         "Linux 22.04 Clang 13",
         "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-13', CXXSTD: '03,11,14,17,20' },
+        { TOOLSET: 'clang', COMPILER: 'clang++-13', CXXSTD: '03,11,14,17,20,2b' },
         "clang-13",
     ),
 
     linux_pipeline(
-        "Linux 22.04 Clang 14 UBSAN",
+        "Linux 22.04 Clang 14",
         "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '03,11,14,17,20,2b' } + ubsan,
+        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '03,11,14,17,20,2b' },
         "clang-14",
     ),
 
     linux_pipeline(
-        "Linux 22.04 Clang 14 ASAN",
+        "Linux 22.04 Clang 15 UBSAN",
         "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '03,11,14,17,20,2b' } + asan,
-        "clang-14",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 Clang 15",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-15', CXXSTD: '03,11,14,17,20,2b' },
+        { TOOLSET: 'clang', COMPILER: 'clang++-15', CXXSTD: '03,11,14,17,20,2b' } + ubsan,
+        "clang-15",
+    ),
+
+    linux_pipeline(
+        "Linux 22.04 Clang 15 ASAN",
+        "cppalliance/droneubuntu2204:1",
+        { TOOLSET: 'clang', COMPILER: 'clang++-15', CXXSTD: '03,11,14,17,20,2b' } + asan,
         "clang-15",
-        ["deb http://apt.llvm.org/jammy/ llvm-toolchain-jammy-15 main"],
     ),
 
     macos_pipeline(
         "MacOS 10.15 Xcode 12.2 UBSAN",
-        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '03,11,14,1z' } + ubsan,
+        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '03,11,14,17,2a' } + ubsan,
     ),
 
     macos_pipeline(
         "MacOS 10.15 Xcode 12.2 ASAN",
-        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '03,11,14,1z' } + asan,
+        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '03,11,14,17,2a' } + asan,
+    ),
+
+    macos_pipeline(
+        "MacOS 12.4 Xcode 13.4.1 UBSAN",
+        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '03,11,14,17,20,2b' } + ubsan,
+        xcode_version = "13.4.1", osx_version = "monterey", arch = "arm64",
+    ),
+
+    macos_pipeline(
+        "MacOS 12.4 Xcode 13.4.1 ASAN",
+        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '03,11,14,17,20,2b' } + asan,
+        xcode_version = "13.4.1", osx_version = "monterey", arch = "arm64",
     ),
 
     windows_pipeline(

.drone/drone.sh

@@ -5,6 +5,7 @@
 # https://www.boost.org/LICENSE_1_0.txt
 
 set -ex
+export PATH=~/.local/bin:/usr/local/bin:$PATH
 
 DRONE_BUILD_DIR=$(pwd)
 

.github/workflows/ci.yml

@@ -19,27 +19,30 @@ jobs:
         include:
           - toolset: gcc-4.8
             cxxstd: "03,11"
-            os: ubuntu-18.04
+            os: ubuntu-latest
+            container: ubuntu:18.04
             install: g++-4.8-multilib
             address-model: 32,64
           - toolset: gcc-5
             cxxstd: "03,11,14,1z"
-            os: ubuntu-18.04
+            os: ubuntu-latest
+            container: ubuntu:18.04
             install: g++-5-multilib
             address-model: 32,64
           - toolset: gcc-6
             cxxstd: "03,11,14,1z"
-            os: ubuntu-18.04
+            os: ubuntu-latest
+            container: ubuntu:18.04
             install: g++-6-multilib
             address-model: 32,64
           - toolset: gcc-7
             cxxstd: "03,11,14,17"
-            os: ubuntu-18.04
+            os: ubuntu-20.04
             install: g++-7-multilib
             address-model: 32,64
           - toolset: gcc-8
             cxxstd: "03,11,14,17,2a"
-            os: ubuntu-18.04
+            os: ubuntu-20.04
             install: g++-8-multilib
             address-model: 32,64
           - toolset: gcc-9
@@ -58,34 +61,37 @@ jobs:
             install: g++-11-multilib
             address-model: 32,64
           - toolset: gcc-12
-            cxxstd: "03,11,14,17,20"
+            cxxstd: "03,11,14,17,20,2b"
             os: ubuntu-22.04
             install: g++-12-multilib
             address-model: 32,64
           - toolset: clang
             compiler: clang++-3.9
             cxxstd: "03,11,14"
-            os: ubuntu-18.04
+            os: ubuntu-latest
+            container: ubuntu:18.04
             install: clang-3.9
           - toolset: clang
             compiler: clang++-4.0
             cxxstd: "03,11,14"
-            os: ubuntu-18.04
+            os: ubuntu-latest
+            container: ubuntu:18.04
             install: clang-4.0
           - toolset: clang
             compiler: clang++-5.0
             cxxstd: "03,11,14,1z"
-            os: ubuntu-18.04
+            os: ubuntu-latest
+            container: ubuntu:18.04
             install: clang-5.0
           - toolset: clang
             compiler: clang++-6.0
             cxxstd: "03,11,14,17"
-            os: ubuntu-18.04
+            os: ubuntu-20.04
             install: clang-6.0
           - toolset: clang
             compiler: clang++-7
             cxxstd: "03,11,14,17"
-            os: ubuntu-18.04
+            os: ubuntu-20.04
             install: clang-7
           - toolset: clang
             compiler: clang++-8
@@ -111,26 +117,45 @@ jobs:
             os: ubuntu-20.04
           - toolset: clang
             compiler: clang++-13
-            cxxstd: "03,11,14,17,20"
+            cxxstd: "03,11,14,17,20,2b"
             os: ubuntu-22.04
             install: clang-13
           - toolset: clang
             compiler: clang++-14
-            cxxstd: "03,11,14,17,20"
+            cxxstd: "03,11,14,17,20,2b"
             os: ubuntu-22.04
             install: clang-14
+          - toolset: clang
+            compiler: clang++-15
+            cxxstd: "03,11,14,17,20,2b"
+            os: ubuntu-22.04
+            install: clang-15
           - toolset: clang
             cxxstd: "03,11,14,17,2a"
             os: macos-11
+          - toolset: clang
+            cxxstd: "03,11,14,17,20,2b"
+            os: macos-12
 
     runs-on: ${{matrix.os}}
+    container: ${{matrix.container}}
+
+    defaults:
+      run:
+        shell: bash
 
     steps:
       - uses: actions/checkout@v3
 
+      - name: Setup container environment
+        if: matrix.container
+        run: |
+          apt-get update
+          apt-get -y install sudo python git g++
+
       - name: Install packages
         if: matrix.install
-        run: sudo apt install ${{matrix.install}}
+        run: sudo apt-get -y install ${{matrix.install}}
 
       - name: Setup Boost
         run: |
@@ -231,10 +256,10 @@ jobs:
       fail-fast: false
       matrix:
         include:
-          - os: ubuntu-18.04
           - os: ubuntu-20.04
           - os: ubuntu-22.04
           - os: macos-11
+          - os: macos-12
 
     runs-on: ${{matrix.os}}
 
@@ -243,7 +268,7 @@ jobs:
 
       - name: Install packages
         if: matrix.install
-        run: sudo apt install ${{matrix.install}}
+        run: sudo apt-get -y install ${{matrix.install}}
 
       - name: Setup Boost
         run: |
@@ -278,10 +303,10 @@ jobs:
       fail-fast: false
       matrix:
         include:
-          - os: ubuntu-18.04
           - os: ubuntu-20.04
           - os: ubuntu-22.04
           - os: macos-11
+          - os: macos-12
 
     runs-on: ${{matrix.os}}
 
@@ -290,7 +315,7 @@ jobs:
 
       - name: Install packages
         if: matrix.install
-        run: sudo apt install ${{matrix.install}}
+        run: sudo apt-get -y install ${{matrix.install}}
 
       - name: Setup Boost
         run: |
@@ -335,10 +360,10 @@ jobs:
       fail-fast: false
       matrix:
         include:
-          - os: ubuntu-18.04
           - os: ubuntu-20.04
           - os: ubuntu-22.04
           - os: macos-11
+          - os: macos-12
 
     runs-on: ${{matrix.os}}
 
@@ -347,7 +372,7 @@ jobs:
 
       - name: Install packages
         if: matrix.install
-        run: sudo apt install ${{matrix.install}}
+        run: sudo apt-get -y install ${{matrix.install}}
 
       - name: Setup Boost
         run: |

benchmark/.gitignore

@@ -0,0 +1,4 @@
+enwik8
+enwik9
+*.exe
+*.obj

benchmark/unordered.cpp

@@ -3,12 +3,22 @@
 // https://www.boost.org/LICENSE_1_0.txt
 
 #define _CRT_SECURE_NO_WARNINGS
+#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/container_hash/hash.hpp>
 #include <boost/unordered_set.hpp>
 #include <boost/core/detail/splitmix64.hpp>
 #include <boost/core/type_name.hpp>
 #include <boost/config.hpp>
+#ifdef HAVE_ABSEIL
+# include "absl/hash/hash.h"
+#endif
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+# include "ankerl/unordered_dense.h"
+#endif
+#ifdef HAVE_MULXP_HASH
+# include "mulxp_hash.hpp"
+#endif
 #include <cstddef>
 #include <cstdio>
 #include <cstdint>
@@ -19,10 +29,8 @@
 
 // mul31_hash
 
-class mul31_hash
+struct mul31_hash
 {
-public:
-
     std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
     {
         char const * p = st.data();
@@ -43,18 +51,20 @@ public:
     }
 };
 
-// mul31_unrolled_hash
+// mul31_x4_hash
 
-template<int Bits> struct mul31_unrolled_hash_impl;
-
-template<> struct mul31_unrolled_hash_impl<32>
+struct mul31_x4_hash
 {
     std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
     {
         char const * p = st.data();
         std::size_t n = st.size();
 
+#if SIZE_MAX > UINT32_MAX
+        std::size_t h = 0xCBF29CE484222325ull;
+#else
         std::size_t h = 0x811C9DC5u;
+#endif
 
         while( n >= 4 )
         {
@@ -80,14 +90,20 @@ template<> struct mul31_unrolled_hash_impl<32>
     }
 };
 
-template<> struct mul31_unrolled_hash_impl<64>
+// mul31_x8_hash
+
+struct mul31_x8_hash
 {
     std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
     {
         char const * p = st.data();
         std::size_t n = st.size();
 
-        std::size_t h = 0xCBF29CE484222325ull;
+#if SIZE_MAX > UINT32_MAX
+        boost::uint64_t h = 0xCBF29CE484222325ull;
+#else
+        boost::uint64_t h = 0x811C9DC5u;
+#endif
 
         while( n >= 8 )
         {
@@ -113,12 +129,10 @@ template<> struct mul31_unrolled_hash_impl<64>
             --n;
         }
 
-        return h;
+        return static_cast<std::size_t>( h );
     }
 };
 
-struct mul31_unrolled_hash: mul31_unrolled_hash_impl< std::numeric_limits<std::size_t>::digits > {};
-
 // fnv1a_hash
 
 template<int Bits> struct fnv1a_hash_impl;
@@ -163,28 +177,44 @@ template<> struct fnv1a_hash_impl<64>
 
 struct fnv1a_hash: fnv1a_hash_impl< std::numeric_limits<std::size_t>::digits > {};
 
-// old_boost_hash
+// mulxp_hash
 
-class old_boost_hash
+#ifdef HAVE_MULXP_HASH
+
+struct mulxp1_hash_
 {
-public:
-
     std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
     {
-        char const * p = st.data();
-        std::size_t n = st.size();
-
-        std::size_t h = 0;
-
-        for( std::size_t i = 0; i < n; ++i )
-        {
-            h ^= static_cast<unsigned char>( p[i] ) + 0x9e3779b9 + ( h << 6 ) + ( h >> 2 );
-        }
-
-        return h;
+        return mulxp1_hash( (unsigned char const*)st.data(), st.size(), 0 );
     }
 };
 
+struct mulxp3_hash_
+{
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp3_hash( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+struct mulxp1_hash32_
+{
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp1_hash32( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+struct mulxp3_hash32_
+{
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp3_hash32( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+#endif
+
 // test_hash_speed
 
 template<class H, class V> void test_hash_speed( int N, V const& v )
@@ -210,11 +240,11 @@ template<class H, class V> void test_hash_speed( int N, V const& v )
 
 #if defined( _MSC_VER )
 
-    std::printf( "%25s : q=%20Iu, %lld ms\n", hash.c_str(), q, ms1 );
+    std::printf( "%57s : q=%20Iu, %lld ms\n", hash.c_str(), q, ms1 );
 
 #else
 
-    std::printf( "%25s : q=%20zu, %lld ms\n", hash.c_str(), q, ms1 );
+    std::printf( "%57s : q=%20zu, %lld ms\n", hash.c_str(), q, ms1 );
 
 #endif
 }
@@ -235,11 +265,11 @@ template<class H, class V> void test_hash_collision( int N, V const& v, std::siz
 
 #if defined( _MSC_VER )
 
-    std::printf( "%25s : c=%Iu\n", hash.c_str(), n - s.size() );
+    std::printf( "%57s : c=%Iu\n", hash.c_str(), n - s.size() );
 
 #else
 
-    std::printf( "%25s : c=%zu\n", hash.c_str(), n - s.size() );
+    std::printf( "%57s : c=%zu\n", hash.c_str(), n - s.size() );
 
 #endif
 }
@@ -292,11 +322,11 @@ template<class V, class S> void test4( int N, V const& v, char const * hash, S s
 
 #if defined( _MSC_VER )
 
-    std::printf( "%25s : n=%Iu, m=%Iu, c=%Iu, q=%Iu, %lld + %lld ms\n", hash, n, m, c, q, ms1, ms2 );
+    std::printf( "%57s : n=%Iu, m=%Iu, c=%Iu, q=%Iu, %4lld + %4lld = %4lld ms\n", hash, n, m, c, q, ms1, ms2, ms1 + ms2 );
 
 #else
 
-    std::printf( "%25s : n=%zu, m=%zu, c=%zu, q=%zu, %lld + %lld ms\n", hash, n, m, c, q, ms1, ms2 );
+    std::printf( "%57s : n=%zu, m=%zu, c=%zu, q=%zu, %4lld + %4lld = %4lld ms\n", hash, n, m, c, q, ms1, ms2, ms1 + ms2 );
 
 #endif
 }
@@ -340,11 +370,23 @@ int main()
     std::puts( "Hash speed test:\n" );
 
     test_hash_speed<mul31_hash>( N * 16, v );
-    test_hash_speed<mul31_unrolled_hash>( N * 16, v );
+    test_hash_speed<mul31_x4_hash>( N * 16, v );
+    test_hash_speed<mul31_x8_hash>( N * 16, v );
     test_hash_speed<fnv1a_hash>( N * 16, v );
-    test_hash_speed<old_boost_hash>( N * 16, v );
     test_hash_speed<boost::hash<std::string> >( N * 16, v );
     test_hash_speed<std::hash<std::string> >( N * 16, v );
+#ifdef HAVE_ABSEIL
+    test_hash_speed<absl::Hash<std::string> >( N * 16, v );
+#endif
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+    test_hash_speed<ankerl::unordered_dense::hash<std::string> >( N * 16, v );
+#endif
+#ifdef HAVE_MULXP_HASH
+    test_hash_speed<mulxp1_hash_>( N * 16, v );
+    test_hash_speed<mulxp3_hash_>( N * 16, v );
+    test_hash_speed<mulxp1_hash32_>( N * 16, v );
+    test_hash_speed<mulxp3_hash32_>( N * 16, v );
+#endif
 
     std::puts( "" );
 
@@ -365,25 +407,55 @@ int main()
         }
 
         test_hash_collision<mul31_hash>( N * 16, v, n );
-        test_hash_collision<mul31_unrolled_hash>( N * 16, v, n );
+        test_hash_collision<mul31_x4_hash>( N * 16, v, n );
+        test_hash_collision<mul31_x8_hash>( N * 16, v, n );
         test_hash_collision<fnv1a_hash>( N * 16, v, n );
-        test_hash_collision<old_boost_hash>( N * 16, v, n );
         test_hash_collision<boost::hash<std::string> >( N * 16, v, n );
         test_hash_collision<std::hash<std::string> >( N * 16, v, n );
+#ifdef HAVE_ABSEIL
+        test_hash_collision<absl::Hash<std::string> >( N * 16, v, n );
+#endif
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+        test_hash_collision<ankerl::unordered_dense::hash<std::string> >( N * 16, v, n );
+#endif
+#ifdef HAVE_MULXP_HASH
+        test_hash_collision<mulxp1_hash_>( N * 16, v, n );
+        test_hash_collision<mulxp3_hash_>( N * 16, v, n );
+        test_hash_collision<mulxp1_hash32_>( N * 16, v, n );
+        test_hash_collision<mulxp3_hash32_>( N * 16, v, n );
+#endif
     }
 
     std::puts( "" );
 
     typedef std::string K;
 
-    std::puts( "Container speed test:\n" );
+    std::puts( "Container speed test:\n---\n" );
 
     test_container_speed<K, mul31_hash>( N, v );
-    test_container_speed<K, mul31_unrolled_hash>( N, v );
+    test_container_speed<K, mul31_x4_hash>( N, v );
+    test_container_speed<K, mul31_x8_hash>( N, v );
     test_container_speed<K, fnv1a_hash>( N, v );
-    test_container_speed<K, old_boost_hash>( N, v );
     test_container_speed<K, boost::hash<std::string> >( N, v );
     test_container_speed<K, std::hash<std::string> >( N, v );
+#ifdef HAVE_ABSEIL
+    test_container_speed<K, absl::Hash<std::string> >( N, v );
+#endif
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+    test_container_speed<K, ankerl::unordered_dense::hash<std::string> >( N, v );
+#endif
+#ifdef HAVE_MULXP_HASH
+    test_container_speed<K, mulxp1_hash_>( N, v );
+    test_container_speed<K, mulxp3_hash_>( N, v );
+    test_container_speed<K, mulxp1_hash32_>( N, v );
+    test_container_speed<K, mulxp3_hash32_>( N, v );
+#endif
 
     std::puts( "" );
 }
+
+#ifdef HAVE_ABSEIL
+# include "absl/hash/internal/hash.cc"
+# include "absl/hash/internal/low_level_hash.cc"
+# include "absl/hash/internal/city.cc"
+#endif

benchmark/unordered_flat.cpp

@@ -0,0 +1,386 @@
+// Copyright 2021 Peter Dimov.
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
+#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
+
+#include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/core/detail/splitmix64.hpp>
+#include <boost/config.hpp>
+#ifdef HAVE_ABSEIL
+# include "absl/hash/hash.h"
+#endif
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+# include "ankerl/unordered_dense.h"
+#endif
+#ifdef HAVE_MULXP_HASH
+# include "mulxp_hash.hpp"
+#endif
+#include <vector>
+#include <memory>
+#include <cstdint>
+#include <iostream>
+#include <iomanip>
+#include <chrono>
+
+using namespace std::chrono_literals;
+
+static void print_time( std::chrono::steady_clock::time_point & t1, char const* label, std::uint32_t s, std::size_t size )
+{
+    auto t2 = std::chrono::steady_clock::now();
+
+    std::cout << label << ": " << ( t2 - t1 ) / 1ms << " ms (s=" << s << ", size=" << size << ")\n";
+
+    t1 = t2;
+}
+
+constexpr unsigned N = 2'000'000;
+constexpr int K = 10;
+
+static std::vector<std::string> indices1, indices2;
+
+static std::string make_index( unsigned x )
+{
+    char buffer[ 64 ];
+    std::snprintf( buffer, sizeof(buffer), "pfx_%u_sfx", x );
+
+    return buffer;
+}
+
+static std::string make_random_index( unsigned x )
+{
+    char buffer[ 64 ];
+    std::snprintf( buffer, sizeof(buffer), "pfx_%0*d_%u_sfx", x % 8 + 1, 0, x );
+
+    return buffer;
+}
+
+static void init_indices()
+{
+    indices1.reserve( N*2+1 );
+    indices1.push_back( make_index( 0 ) );
+
+    for( unsigned i = 1; i <= N*2; ++i )
+    {
+        indices1.push_back( make_index( i ) );
+    }
+
+    indices2.reserve( N*2+1 );
+    indices2.push_back( make_index( 0 ) );
+
+    {
+        boost::detail::splitmix64 rng;
+
+        for( unsigned i = 1; i <= N*2; ++i )
+        {
+            indices2.push_back( make_random_index( static_cast<std::uint32_t>( rng() ) ) );
+        }
+    }
+}
+
+template<class Map> BOOST_NOINLINE void test_insert( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    for( unsigned i = 1; i <= N; ++i )
+    {
+        map.insert( { indices1[ i ], i } );
+    }
+
+    print_time( t1, "Consecutive insert",  0, map.size() );
+
+    for( unsigned i = 1; i <= N; ++i )
+    {
+        map.insert( { indices2[ i ], i } );
+    }
+
+    print_time( t1, "Random insert",  0, map.size() );
+
+    std::cout << std::endl;
+}
+
+template<class Map> BOOST_NOINLINE void test_lookup( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    std::uint32_t s;
+    
+    s = 0;
+
+    for( int j = 0; j < K; ++j )
+    {
+        for( unsigned i = 1; i <= N * 2; ++i )
+        {
+            auto it = map.find( indices1[ i ] );
+            if( it != map.end() ) s += it->second;
+        }
+    }
+
+    print_time( t1, "Consecutive lookup",  s, map.size() );
+
+    s = 0;
+
+    for( int j = 0; j < K; ++j )
+    {
+        for( unsigned i = 1; i <= N * 2; ++i )
+        {
+            auto it = map.find( indices2[ i ] );
+            if( it != map.end() ) s += it->second;
+        }
+    }
+
+    print_time( t1, "Random lookup",  s, map.size() );
+
+    std::cout << std::endl;
+}
+
+template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    auto it = map.begin();
+
+    while( it != map.end() )
+    {
+        if( it->second & 1 )
+        {
+            if constexpr( std::is_void_v< decltype( map.erase( it ) ) > )
+            {
+                map.erase( it++ );
+            }
+            else
+            {
+                it = map.erase( it );
+            }
+        }
+        else
+        {
+            ++it;
+        }
+    }
+
+    print_time( t1, "Iterate and erase odd elements",  0, map.size() );
+
+    std::cout << std::endl;
+}
+
+template<class Map> BOOST_NOINLINE void test_erase( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    for( unsigned i = 1; i <= N; ++i )
+    {
+        map.erase( indices1[ i ] );
+    }
+
+    print_time( t1, "Consecutive erase",  0, map.size() );
+
+    for( unsigned i = 1; i <= N; ++i )
+    {
+        map.erase( indices2[ i ] );
+    }
+
+    print_time( t1, "Random erase",  0, map.size() );
+
+    std::cout << std::endl;
+}
+
+//
+
+struct record
+{
+    std::string label_;
+    long long time_;
+};
+
+static std::vector<record> times;
+
+template<class Hash> BOOST_NOINLINE void test( char const* label )
+{
+    std::cout << label << ":\n\n";
+
+    boost::unordered_flat_map<std::string, std::uint32_t, Hash> map;
+
+    auto t0 = std::chrono::steady_clock::now();
+    auto t1 = t0;
+
+    test_insert( map, t1 );
+
+    record rec = { label, 0 };
+
+    test_lookup( map, t1 );
+    test_iteration( map, t1 );
+    test_lookup( map, t1 );
+    test_erase( map, t1 );
+
+    auto tN = std::chrono::steady_clock::now();
+    std::cout << "Total: " << ( tN - t0 ) / 1ms << " ms\n\n";
+
+    rec.time_ = ( tN - t0 ) / 1ms;
+    times.push_back( rec );
+}
+
+// fnv1a_hash
+
+template<int Bits> struct fnv1a_hash_impl;
+
+template<> struct fnv1a_hash_impl<32>
+{
+    std::size_t operator()( std::string const& s ) const
+    {
+        std::size_t h = 0x811C9DC5u;
+
+        char const * first = s.data();
+        char const * last = first + s.size();
+
+        for( ; first != last; ++first )
+        {
+            h ^= static_cast<unsigned char>( *first );
+            h *= 0x01000193ul;
+        }
+
+        return h;
+    }
+};
+
+template<> struct fnv1a_hash_impl<64>
+{
+    std::size_t operator()( std::string const& s ) const
+    {
+        std::size_t h = 0xCBF29CE484222325ull;
+
+        char const * first = s.data();
+        char const * last = first + s.size();
+
+        for( ; first != last; ++first )
+        {
+            h ^= static_cast<unsigned char>( *first );
+            h *= 0x00000100000001B3ull;
+        }
+
+        return h;
+    }
+};
+
+struct fnv1a_hash: fnv1a_hash_impl< std::numeric_limits<std::size_t>::digits >
+{
+    using is_avalanching = void;
+};
+
+// std_hash
+
+struct std_hash: std::hash<std::string>
+{
+    using is_avalanching = void;
+};
+
+// absl_hash
+
+#ifdef HAVE_ABSEIL
+
+struct absl_hash: absl::Hash<std::string>
+{
+    using is_avalanching = void;
+};
+
+#endif
+
+// mulxp_hash
+
+#ifdef HAVE_MULXP_HASH
+
+struct mulxp1_hash_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp1_hash( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+struct mulxp3_hash_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp3_hash( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+struct mulxp1_hash32_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        std::size_t r = mulxp1_hash32( (unsigned char const*)st.data(), st.size(), 0 );
+
+#if SIZE_MAX > UINT32_MAX
+
+        r |= r << 32;
+
+#endif
+
+        return r;
+    }
+};
+
+struct mulxp3_hash32_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        std::size_t r = mulxp3_hash32( (unsigned char const*)st.data(), st.size(), 0 );
+
+#if SIZE_MAX > UINT32_MAX
+
+        r |= r << 32;
+
+#endif
+
+        return r;
+    }
+};
+
+#endif
+
+//
+
+int main()
+{
+    init_indices();
+
+    test< boost::hash<std::string> >( "boost::hash" );
+    test< std_hash >( "std::hash" );
+    test< fnv1a_hash >( "fnv1a_hash" );
+
+#ifdef HAVE_ABSEIL
+
+    test< absl_hash >( "absl::Hash" );
+
+#endif
+
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+
+    test< ankerl::unordered_dense::hash<std::string> >( "ankerl::unordered_dense::hash" );
+
+#endif
+
+#ifdef HAVE_MULXP_HASH
+
+    test< mulxp1_hash_ >( "mulxp1_hash" );
+    test< mulxp3_hash_ >( "mulxp3_hash" );
+    test< mulxp1_hash32_ >( "mulxp1_hash32" );
+    test< mulxp3_hash32_ >( "mulxp3_hash32" );
+
+#endif
+
+    std::cout << "---\n\n";
+
+    for( auto const& x: times )
+    {
+        std::cout << std::setw( 32 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms\n";
+    }
+}
+
+#ifdef HAVE_ABSEIL
+# include "absl/hash/internal/hash.cc"
+# include "absl/hash/internal/low_level_hash.cc"
+# include "absl/hash/internal/city.cc"
+#endif

benchmark/word_count.cpp

@@ -0,0 +1,319 @@
+// Copyright 2022 Peter Dimov.
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
+#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
+
+#include <boost/unordered/unordered_flat_map.hpp>
+#ifdef HAVE_ABSEIL
+# include "absl/hash/hash.h"
+#endif
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+# include "ankerl/unordered_dense.h"
+#endif
+#ifdef HAVE_MULXP_HASH
+# include "mulxp_hash.hpp"
+#endif
+#include <boost/regex.hpp>
+#include <vector>
+#include <memory>
+#include <cstdint>
+#include <iostream>
+#include <iomanip>
+#include <chrono>
+#include <fstream>
+#include <string_view>
+#include <string>
+
+using namespace std::chrono_literals;
+
+static void print_time( std::chrono::steady_clock::time_point & t1, char const* label, std::uint32_t s, std::size_t size )
+{
+    auto t2 = std::chrono::steady_clock::now();
+
+    std::cout << label << ": " << ( t2 - t1 ) / 1ms << " ms (s=" << s << ", size=" << size << ")\n";
+
+    t1 = t2;
+}
+
+static std::vector<std::string> words;
+
+static void init_words()
+{
+#if SIZE_MAX > UINT32_MAX
+
+    char const* fn = "enwik9"; // http://mattmahoney.net/dc/textdata
+
+#else
+
+    char const* fn = "enwik8"; // ditto
+
+#endif
+
+    auto t1 = std::chrono::steady_clock::now();
+
+    std::ifstream is( fn );
+    std::string in( std::istreambuf_iterator<char>( is ), std::istreambuf_iterator<char>{} );
+
+    boost::regex re( "[a-zA-Z]+");
+    boost::sregex_token_iterator it( in.begin(), in.end(), re, 0 ), end;
+
+    words.assign( it, end );
+
+    auto t2 = std::chrono::steady_clock::now();
+
+    std::cout << fn << ": " << words.size() << " words, " << ( t2 - t1 ) / 1ms << " ms\n\n";
+}
+
+template<class Map> BOOST_NOINLINE void test_word_count( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    std::size_t s = 0;
+
+    for( auto const& word: words )
+    {
+        ++map[ word ];
+        ++s;
+    }
+
+    print_time( t1, "Word count", s, map.size() );
+
+    std::cout << std::endl;
+}
+
+template<class Map> BOOST_NOINLINE void test_contains( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    std::size_t s = 0;
+
+    for( auto const& word: words )
+    {
+        std::string_view w2( word );
+        w2.remove_prefix( 1 );
+
+        s += map.contains( w2 );
+    }
+
+    print_time( t1, "Contains", s, map.size() );
+
+    std::cout << std::endl;
+}
+
+template<class Map> BOOST_NOINLINE void test_count( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    std::size_t s = 0;
+
+    for( auto const& word: words )
+    {
+        std::string_view w2( word );
+        w2.remove_prefix( 1 );
+
+        s += map.count( w2 );
+    }
+
+    print_time( t1, "Count", s, map.size() );
+
+    std::cout << std::endl;
+}
+
+//
+
+struct record
+{
+    std::string label_;
+    long long time_;
+};
+
+static std::vector<record> times;
+
+template<class Hash> BOOST_NOINLINE void test( char const* label )
+{
+    std::cout << label << ":\n\n";
+
+    boost::unordered_flat_map<std::string_view, std::size_t, Hash> map;
+
+    auto t0 = std::chrono::steady_clock::now();
+    auto t1 = t0;
+
+    test_word_count( map, t1 );
+
+    record rec = { label, 0 };
+
+    test_contains( map, t1 );
+    test_count( map, t1 );
+
+    auto tN = std::chrono::steady_clock::now();
+    std::cout << "Total: " << ( tN - t0 ) / 1ms << " ms\n\n";
+
+    rec.time_ = ( tN - t0 ) / 1ms;
+    times.push_back( rec );
+}
+
+// fnv1a_hash
+
+template<int Bits> struct fnv1a_hash_impl;
+
+template<> struct fnv1a_hash_impl<32>
+{
+    std::size_t operator()( std::string_view const& s ) const
+    {
+        std::size_t h = 0x811C9DC5u;
+
+        char const * first = s.data();
+        char const * last = first + s.size();
+
+        for( ; first != last; ++first )
+        {
+            h ^= static_cast<unsigned char>( *first );
+            h *= 0x01000193ul;
+        }
+
+        return h;
+    }
+};
+
+template<> struct fnv1a_hash_impl<64>
+{
+    std::size_t operator()( std::string_view const& s ) const
+    {
+        std::size_t h = 0xCBF29CE484222325ull;
+
+        char const * first = s.data();
+        char const * last = first + s.size();
+
+        for( ; first != last; ++first )
+        {
+            h ^= static_cast<unsigned char>( *first );
+            h *= 0x00000100000001B3ull;
+        }
+
+        return h;
+    }
+};
+
+struct fnv1a_hash: fnv1a_hash_impl< std::numeric_limits<std::size_t>::digits >
+{
+    using is_avalanching = void;
+};
+
+// std_hash
+
+struct std_hash: std::hash<std::string_view>
+{
+    using is_avalanching = void;
+};
+
+// absl_hash
+
+#ifdef HAVE_ABSEIL
+
+struct absl_hash: absl::Hash<std::string_view>
+{
+    using is_avalanching = void;
+};
+
+#endif
+
+#ifdef HAVE_MULXP_HASH
+
+struct mulxp1_hash_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string_view const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp1_hash( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+struct mulxp3_hash_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string_view const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp3_hash( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+struct mulxp3_hash32_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string_view const& st ) const BOOST_NOEXCEPT
+    {
+        std::size_t r = mulxp3_hash32( (unsigned char const*)st.data(), st.size(), 0 );
+
+#if SIZE_MAX > UINT32_MAX
+
+        r |= r << 32;
+
+#endif
+
+        return r;
+    }
+};
+
+struct mulxp1_hash32_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string_view const& st ) const BOOST_NOEXCEPT
+    {
+        std::size_t r = mulxp1_hash32( (unsigned char const*)st.data(), st.size(), 0 );
+
+#if SIZE_MAX > UINT32_MAX
+
+        r |= r << 32;
+
+#endif
+
+        return r;
+    }
+};
+
+#endif
+
+//
+
+int main()
+{
+    init_words();
+
+    test< boost::hash<std::string_view> >( "boost::hash" );
+    test< std_hash >( "std::hash" );
+    test< fnv1a_hash >( "fnv1a_hash" );
+
+#ifdef HAVE_ABSEIL
+
+    test< absl_hash >( "absl::Hash" );
+
+#endif
+
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+
+    test< ankerl::unordered_dense::hash<std::string_view> >( "ankerl::unordered_dense::hash" );
+
+#endif
+
+#ifdef HAVE_MULXP_HASH
+
+    test< mulxp1_hash_ >( "mulxp1_hash" );
+    test< mulxp3_hash_ >( "mulxp3_hash" );
+    test< mulxp1_hash32_ >( "mulxp1_hash32" );
+    test< mulxp3_hash32_ >( "mulxp3_hash32" );
+
+#endif
+
+    std::cout << "---\n\n";
+
+    for( auto const& x: times )
+    {
+        std::cout << std::setw( 32 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms\n";
+    }
+}
+
+#ifdef HAVE_ABSEIL
+# include "absl/hash/internal/hash.cc"
+# include "absl/hash/internal/low_level_hash.cc"
+# include "absl/hash/internal/city.cc"
+#endif

doc/hash/intro.adoc

@@ -22,11 +22,13 @@ Out of the box, `boost::hash` supports
 
 * standard integral types (integers, character types, and `bool`);
 * standard floating point types (`float`, `double`, `long double`);
-* pointers (to objects and to functions, but not pointers to members);
+* pointers (to objects and to functions, but not pointers to members)
+  and `nullptr`;
 * enumeration types;
 * C arrays;
 * `std::complex`;
-* `std::pair`, `std::tuple`;
+* tuple-like types, such as `std::pair`, `std::tuple`, and user-defined
+  types that specialize `std::tuple_size` and provide `get<I>`;
 * sequence-like types, both standard and user-defined (sequence-like types
   have `begin()` and `end()` member functions returning iterators);
 * unordered sequences, standard or user-defined (sequences for which the hash

doc/hash/notes.adoc

@@ -55,6 +55,22 @@ to be templates constrained on e.g. `std::is_integral` or its moral
 equivalent. This causes types convertible to an integral to no longer
 match, avoiding the problem.
 
+== Hash Value Stability
+
+In general, the library does not promise that the hash values will stay
+the same from release to release (otherwise improvements would be
+impossible). However, historically values have been quite stable. Before
+release 1.81, the previous changes have been in 1.56 (a better
+`hash_combine`) and 1.78 (macOS-specific change to `hash_combine`.)
+
+Code should generally not depend on specific hash values, but for those
+willing to take the risk of occasional breaks due to hash value changes,
+the library now has a test that checks hash values for a number of types
+against reference values (`test/hash_reference_values.cpp`),
+whose https://github.com/boostorg/container_hash/commits/develop/test/hash_reference_values.cpp[version history]
+can be used as a rough guide to when hash values have changed, and for what
+types.
+
 == hash_combine
 
 The initial implementation of the library was based on Issue 6.18 of the
@@ -200,16 +216,9 @@ In Boost 1.81, `hash_range` was changed to process elements of type `char`,
 A `uint32_t` is composed from `first[0]` to `first[3]`, and that `uint32_t`
 is fed to `hash_combine`.
 
-In principle, when `size_t` is 64 bit, we could have used `uint64_t` instead.
-We do not, because this allows producing an arbitrary hash value by choosing
-the input bytes appropriately (because `hash_combine` is reversible.)
-
-Allowing control only over 32 bits of the full 64 bit `size_t` value makes
-these "chosen plaintext attacks" harder.
-
-This is not as harmful to performance as it first appears, because the
-input to `hash<string>` (e.g. the key in an unordered container) is often
-short (9 to 13 bytes in some typical scenarios.)
+In Boost 1.82, `hash_range` for these types was changed to use
+https://github.com/pdimov/mulxp_hash[`mulxp1_hash`]. This improves both
+quality and speed of string hashing.
 
 Note that `hash_range` has also traditionally guaranteed that the same element
 sequence yields the same hash value regardless of the iterator type. This

doc/hash/recent.adoc

@@ -8,6 +8,17 @@ https://www.boost.org/LICENSE_1_0.txt
 = Recent Changes
 :idprefix: recent_
 
+== Boost 1.82.0
+
+* Added an overload of `hash_value` for `std::nullptr_t`.
+* Added `is_tuple_like` and an overload of `hash_value` for
+  tuple-like types.
+* Changed string hashing to use
+  https://github.com/pdimov/mulxp_hash[`mulxp1_hash`],
+  improving both quality and speed. This changes the hash values
+  for string-like types (ranges of `char`, `signed char`,
+  `unsigned char`, `std::byte`, `char8_t`).
+
 == Boost 1.81.0
 
 Major update.
@@ -24,9 +35,18 @@ Major update.
 * Described structs and classes (those annotated with
   `BOOST_DESCRIBE_STRUCT` or `BOOST_DESCRIBE_CLASS`) are now
   supported out of the box.
-* `hash_combine` has been improved.
+* `hash_combine` has been improved. This changes the hash values
+  of composite (container and tuple) types and of scalar types
+  bigger than `size_t`.
 * The performance (and quality, as a result of the above change)
   of string hashing has been improved. `boost::hash` for strings
   now passes SMHasher in 64 bit mode.
 * The documentation has been substantially revised to reflect
   the changes.
+
+== Boost 1.78.0
+
+* Fixed `hash_combine` so that its behavior no longer depends
+  on whether `size_t` is the exact same type as `boost::uint64_t`
+  (which wasn't the case on macOS). This changes the hash values
+  of composite (container and tuple) types on macOS.

doc/hash/reference.adoc

@@ -30,6 +30,7 @@ template<class T> struct is_range;
 template<class T> struct is_contiguous_range;
 template<class T> struct is_unordered_range;
 template<class T> struct is_described_class;
+template<class T> struct is_tuple_like;
 
 } // namespace container_hash
 
@@ -89,8 +90,9 @@ template<class T>
 template<class A, class B>
   std::size_t hash_value( std::pair<A, B> const& v );
 
-template<class... T>
-  std::size_t hash_value( std::tuple<T...> const& v );
+// Enabled only when container_hash::is_tuple_like<T>::value is true
+template<class T>
+  std::size_t hash_value( T const& v );
 
 // Enabled only when container_hash::is_range<T>::value is true
 template<class T>
@@ -240,11 +242,16 @@ for( ; first != last; ++first )
 }
 ----
 
-Otherwise, bytes from `[first, last)` are coalesced in an unspecified manner
-and then passed to `hash_combine`, more than one at a time. This is done in
-order to improve performance when hashing strings.
+Otherwise, bytes from `[first, last)` are coalesced and hashed in an
+unspecified manner. This is done in order to improve performance when hashing
+strings.
 --
 
+Remarks: ::
+  For chars, the current implementation uses
+  https://github.com/pdimov/mulxp_hash[`mulxp1_hash`] when `std::size_t` is
+  64 bit, and `mulxp1_hash32` when it's 32 bit.
+
 [source]
 ----
 template<class It> std::size_t hash_range( It first, It last );
@@ -385,8 +392,9 @@ return seed;
 
 [source]
 ----
-template<class... T>
-  std::size_t hash_value( std::tuple<T...> const& v );
+// Enabled only when container_hash::is_tuple_like<T>::value is true
+template<class T>
+  std::size_t hash_value( T const& v );
 ----
 
 Effects: ::
@@ -395,15 +403,21 @@ Effects: ::
 ----
 std::size_t seed = 0;
 
-boost::hash_combine( seed, std::get<0>(v) );
-boost::hash_combine( seed, std::get<1>(v) );
+using std::get;
+
+boost::hash_combine( seed, get<0>(v) );
+boost::hash_combine( seed, get<1>(v) );
 // ...
-boost::hash_combine( seed, std::get<N-1>(v) );
+boost::hash_combine( seed, get<N-1>(v) );
 
 return seed;
 ----
 +
-where `N` is `sizeof...(T)`.
+where `N` is `std::tuple_size<T>::value`.
+
+Remarks: ::
+This overload is only enabled when
+`container_hash::is_range<T>::value` is `false`.
 
 [source]
 ----
@@ -703,3 +717,38 @@ template<class T> struct is_described_class
 
 Users are allowed to specialize `is_described_class` for their types
 if the default behavior does not deduce the correct value.
+
+== <boost/container_hash/{zwsp}is_tuple_like.hpp>
+
+Defines the trait `boost::container_hash::is_tuple_like`.
+
+[source]
+----
+namespace boost
+{
+
+namespace container_hash
+{
+
+template<class T> struct is_tuple_like;
+
+} // namespace container_hash
+
+} // namespace boost
+----
+
+=== is_tuple_like<T>
+
+[source]
+----
+template<class T> struct is_tuple_like
+{
+    static constexpr bool value = /* see below */;
+};
+----
+
+`is_tuple_like<T>::value` is `true` when `std::tuple_size<T>::value`
+is valid.
+
+Users are allowed to specialize `is_tuple_like` for their types
+if the default behavior does not deduce the correct value.

include/boost/container_hash/detail/hash_range.hpp

@@ -6,13 +6,16 @@
 #define BOOST_HASH_DETAIL_HASH_RANGE_HPP
 
 #include <boost/container_hash/hash_fwd.hpp>
+#include <boost/container_hash/detail/mulx.hpp>
 #include <boost/type_traits/integral_constant.hpp>
 #include <boost/type_traits/enable_if.hpp>
 #include <boost/type_traits/is_same.hpp>
 #include <boost/cstdint.hpp>
+#include <iterator>
+#include <limits>
 #include <cstddef>
 #include <climits>
-#include <iterator>
+#include <cstring>
 
 namespace boost
 {
@@ -37,6 +40,8 @@ template<> struct is_char_type<std::byte>: public boost::true_type {};
 
 #endif
 
+// generic version
+
 template<class It>
 inline typename boost::enable_if_<
     !is_char_type<typename std::iterator_traits<It>::value_type>::value,
@@ -51,120 +56,352 @@ std::size_t >::type
     return seed;
 }
 
-template<class It>
-inline typename boost::enable_if_<
-    is_char_type<typename std::iterator_traits<It>::value_type>::value &&
-    is_same<typename std::iterator_traits<It>::iterator_category, std::random_access_iterator_tag>::value,
-std::size_t>::type
-    hash_range( std::size_t seed, It first, It last )
+// specialized char[] version, 32 bit
+
+template<class It> inline boost::uint32_t read32le( It p )
 {
-    std::size_t n = static_cast<std::size_t>( last - first );
+    // clang 5+, gcc 5+ figure out this pattern and use a single mov on x86
+    // gcc on s390x and power BE even knows how to use load-reverse
 
-    for( ; n >= 4; first += 4, n -= 4 )
-    {
-        // clang 5+, gcc 5+ figure out this pattern and use a single mov on x86
-        // gcc on s390x and power BE even knows how to use load-reverse
+    boost::uint32_t w =
+        static_cast<boost::uint32_t>( static_cast<unsigned char>( p[0] ) ) |
+        static_cast<boost::uint32_t>( static_cast<unsigned char>( p[1] ) ) <<  8 |
+        static_cast<boost::uint32_t>( static_cast<unsigned char>( p[2] ) ) << 16 |
+        static_cast<boost::uint32_t>( static_cast<unsigned char>( p[3] ) ) << 24;
 
-        boost::uint32_t w =
-            static_cast<boost::uint32_t>( static_cast<unsigned char>( first[0] ) ) |
-            static_cast<boost::uint32_t>( static_cast<unsigned char>( first[1] ) ) <<  8 |
-            static_cast<boost::uint32_t>( static_cast<unsigned char>( first[2] ) ) << 16 |
-            static_cast<boost::uint32_t>( static_cast<unsigned char>( first[3] ) ) << 24;
+    return w;
+}
 
-        hash_combine( seed, w );
-    }
+#if defined(_MSC_VER) && !defined(__clang__)
 
-    {
-        // add a trailing suffix byte of 0x01 because otherwise sequences of
-        // trailing zeroes are indistinguishable from end of string
+template<class T> inline boost::uint32_t read32le( T* p )
+{
+    boost::uint32_t w;
 
-        boost::uint32_t w = 0x01u;
+    std::memcpy( &w, p, 4 );
+    return w;
+}
 
-        switch( n )
-        {
-        case 1:
+#endif
 
-            w =
-                static_cast<boost::uint32_t>( static_cast<unsigned char>( first[0] ) ) |
-                0x0100u;
-
-            break;
-
-        case 2:
-
-            w =
-                static_cast<boost::uint32_t>( static_cast<unsigned char>( first[0] ) ) |
-                static_cast<boost::uint32_t>( static_cast<unsigned char>( first[1] ) ) <<  8 |
-                0x010000u;
-
-            break;
-
-        case 3:
-
-            w =
-                static_cast<boost::uint32_t>( static_cast<unsigned char>( first[0] ) ) |
-                static_cast<boost::uint32_t>( static_cast<unsigned char>( first[1] ) ) <<  8 |
-                static_cast<boost::uint32_t>( static_cast<unsigned char>( first[2] ) ) << 16 |
-                0x01000000u;
-
-            break;
-        }
-
-        hash_combine( seed, w );
-    }
-
-    return seed;
+inline boost::uint64_t mul32( boost::uint32_t x, boost::uint32_t y )
+{
+    return static_cast<boost::uint64_t>( x ) * y;
 }
 
 template<class It>
 inline typename boost::enable_if_<
     is_char_type<typename std::iterator_traits<It>::value_type>::value &&
-    !is_same<typename std::iterator_traits<It>::iterator_category, std::random_access_iterator_tag>::value,
+    is_same<typename std::iterator_traits<It>::iterator_category, std::random_access_iterator_tag>::value &&
+    std::numeric_limits<std::size_t>::digits <= 32,
 std::size_t>::type
     hash_range( std::size_t seed, It first, It last )
 {
+    It p = first;
+    std::size_t n = static_cast<std::size_t>( last - first );
+
+    boost::uint32_t const q = 0x9e3779b9U;
+    boost::uint32_t const k = 0xe35e67b1U; // q * q
+
+    boost::uint64_t h = mul32( static_cast<boost::uint32_t>( seed ) + q, k );
+    boost::uint32_t w = static_cast<boost::uint32_t>( h & 0xFFFFFFFF );
+
+    h ^= n;
+
+    while( n >= 4 )
+    {
+        boost::uint32_t v1 = read32le( p );
+
+        w += q;
+        h ^= mul32( v1 + w, k );
+
+        p += 4;
+        n -= 4;
+    }
+
+    {
+        boost::uint32_t v1 = 0;
+
+        if( n >= 1 )
+        {
+            std::size_t const x1 = ( n - 1 ) & 2; // 1: 0, 2: 0, 3: 2
+            std::size_t const x2 = n >> 1;        // 1: 0, 2: 1, 3: 1
+
+            v1 =
+                static_cast<boost::uint32_t>( static_cast<unsigned char>( p[ static_cast<std::ptrdiff_t>( x1 ) ] ) ) << x1 * 8 |
+                static_cast<boost::uint32_t>( static_cast<unsigned char>( p[ static_cast<std::ptrdiff_t>( x2 ) ] ) ) << x2 * 8 |
+                static_cast<boost::uint32_t>( static_cast<unsigned char>( p[ 0 ] ) );
+        }
+
+        w += q;
+        h ^= mul32( v1 + w, k );
+    }
+
+    w += q;
+    h ^= mul32( static_cast<boost::uint32_t>( h & 0xFFFFFFFF ) + w, static_cast<boost::uint32_t>( h >> 32 ) + w + k );
+
+    return static_cast<boost::uint32_t>( h & 0xFFFFFFFF ) ^ static_cast<boost::uint32_t>( h >> 32 );
+}
+
+template<class It>
+inline typename boost::enable_if_<
+    is_char_type<typename std::iterator_traits<It>::value_type>::value &&
+    !is_same<typename std::iterator_traits<It>::iterator_category, std::random_access_iterator_tag>::value &&
+    std::numeric_limits<std::size_t>::digits <= 32,
+std::size_t>::type
+    hash_range( std::size_t seed, It first, It last )
+{
+    std::size_t n = 0;
+
+    boost::uint32_t const q = 0x9e3779b9U;
+    boost::uint32_t const k = 0xe35e67b1U; // q * q
+
+    boost::uint64_t h = mul32( static_cast<boost::uint32_t>( seed ) + q, k );
+    boost::uint32_t w = static_cast<boost::uint32_t>( h & 0xFFFFFFFF );
+
+    boost::uint32_t v1 = 0;
+
     for( ;; )
     {
-        boost::uint32_t w = 0;
+        v1 = 0;
 
         if( first == last )
         {
-            hash_combine( seed, w | 0x01u );
-            return seed;
+            break;
         }
 
-        w |= static_cast<boost::uint32_t>( static_cast<unsigned char>( *first ) );
+        v1 |= static_cast<boost::uint32_t>( static_cast<unsigned char>( *first ) );
         ++first;
+        ++n;
 
         if( first == last )
         {
-            hash_combine( seed, w | 0x0100u );
-            return seed;
+            break;
         }
 
-        w |= static_cast<boost::uint32_t>( static_cast<unsigned char>( *first ) ) << 8;
+        v1 |= static_cast<boost::uint32_t>( static_cast<unsigned char>( *first ) ) << 8;
         ++first;
+        ++n;
 
         if( first == last )
         {
-            hash_combine( seed, w | 0x010000u );
-            return seed;
+            break;
         }
 
-        w |= static_cast<boost::uint32_t>( static_cast<unsigned char>( *first ) ) << 16;
+        v1 |= static_cast<boost::uint32_t>( static_cast<unsigned char>( *first ) ) << 16;
         ++first;
+        ++n;
 
         if( first == last )
         {
-            hash_combine( seed, w | 0x01000000u );
-            return seed;
+            break;
         }
 
-        w |= static_cast<boost::uint32_t>( static_cast<unsigned char>( *first ) ) << 24;
+        v1 |= static_cast<boost::uint32_t>( static_cast<unsigned char>( *first ) ) << 24;
         ++first;
+        ++n;
 
-        hash_combine( seed, w );
+        w += q;
+        h ^= mul32( v1 + w, k );
     }
+
+    h ^= n;
+
+    w += q;
+    h ^= mul32( v1 + w, k );
+
+    w += q;
+    h ^= mul32( static_cast<boost::uint32_t>( h & 0xFFFFFFFF ) + w, static_cast<boost::uint32_t>( h >> 32 ) + w + k );
+
+    return static_cast<boost::uint32_t>( h & 0xFFFFFFFF ) ^ static_cast<boost::uint32_t>( h >> 32 );
+}
+
+// specialized char[] version, 64 bit
+
+template<class It> inline boost::uint64_t read64le( It p )
+{
+    boost::uint64_t w =
+        static_cast<boost::uint64_t>( static_cast<unsigned char>( p[0] ) ) |
+        static_cast<boost::uint64_t>( static_cast<unsigned char>( p[1] ) ) <<  8 |
+        static_cast<boost::uint64_t>( static_cast<unsigned char>( p[2] ) ) << 16 |
+        static_cast<boost::uint64_t>( static_cast<unsigned char>( p[3] ) ) << 24 |
+        static_cast<boost::uint64_t>( static_cast<unsigned char>( p[4] ) ) << 32 |
+        static_cast<boost::uint64_t>( static_cast<unsigned char>( p[5] ) ) << 40 |
+        static_cast<boost::uint64_t>( static_cast<unsigned char>( p[6] ) ) << 48 |
+        static_cast<boost::uint64_t>( static_cast<unsigned char>( p[7] ) ) << 56;
+
+    return w;
+}
+
+#if defined(_MSC_VER) && !defined(__clang__)
+
+template<class T> inline boost::uint64_t read64le( T* p )
+{
+    boost::uint64_t w;
+
+    std::memcpy( &w, p, 8 );
+    return w;
+}
+
+#endif
+
+template<class It>
+inline typename boost::enable_if_<
+    is_char_type<typename std::iterator_traits<It>::value_type>::value &&
+    is_same<typename std::iterator_traits<It>::iterator_category, std::random_access_iterator_tag>::value &&
+    (std::numeric_limits<std::size_t>::digits > 32),
+std::size_t>::type
+    hash_range( std::size_t seed, It first, It last )
+{
+    It p = first;
+    std::size_t n = static_cast<std::size_t>( last - first );
+
+    boost::uint64_t const q = static_cast<boost::uint64_t>( 0x9e3779b9 ) << 32 | 0x7f4a7c15;
+    boost::uint64_t const k = static_cast<boost::uint64_t>( 0xdf442d22 ) << 32 | 0xce4859b9; // q * q
+
+    boost::uint64_t w = mulx( seed + q, k );
+    boost::uint64_t h = w ^ n;
+
+    while( n >= 8 )
+    {
+        boost::uint64_t v1 = read64le( p );
+
+        w += q;
+        h ^= mulx( v1 + w, k );
+
+        p += 8;
+        n -= 8;
+    }
+
+    {
+        boost::uint64_t v1 = 0;
+
+        if( n >= 4 )
+        {
+            v1 = static_cast<boost::uint64_t>( read32le( p + static_cast<std::ptrdiff_t>( n - 4 ) ) ) << ( n - 4 ) * 8 | read32le( p );
+        }
+        else if( n >= 1 )
+        {
+            std::size_t const x1 = ( n - 1 ) & 2; // 1: 0, 2: 0, 3: 2
+            std::size_t const x2 = n >> 1;        // 1: 0, 2: 1, 3: 1
+
+            v1 =
+                static_cast<boost::uint64_t>( static_cast<unsigned char>( p[ static_cast<std::ptrdiff_t>( x1 ) ] ) ) << x1 * 8 |
+                static_cast<boost::uint64_t>( static_cast<unsigned char>( p[ static_cast<std::ptrdiff_t>( x2 ) ] ) ) << x2 * 8 |
+                static_cast<boost::uint64_t>( static_cast<unsigned char>( p[ 0 ] ) );
+        }
+
+        w += q;
+        h ^= mulx( v1 + w, k );
+    }
+
+    return mulx( h + w, k );
+}
+
+template<class It>
+inline typename boost::enable_if_<
+    is_char_type<typename std::iterator_traits<It>::value_type>::value &&
+    !is_same<typename std::iterator_traits<It>::iterator_category, std::random_access_iterator_tag>::value &&
+    (std::numeric_limits<std::size_t>::digits > 32),
+std::size_t>::type
+    hash_range( std::size_t seed, It first, It last )
+{
+    std::size_t n = 0;
+
+    boost::uint64_t const q = static_cast<boost::uint64_t>( 0x9e3779b9 ) << 32 | 0x7f4a7c15;
+    boost::uint64_t const k = static_cast<boost::uint64_t>( 0xdf442d22 ) << 32 | 0xce4859b9; // q * q
+
+    boost::uint64_t w = mulx( seed + q, k );
+    boost::uint64_t h = w;
+
+    boost::uint64_t v1 = 0;
+
+    for( ;; )
+    {
+        v1 = 0;
+
+        if( first == last )
+        {
+            break;
+        }
+
+        v1 |= static_cast<boost::uint64_t>( static_cast<unsigned char>( *first ) );
+        ++first;
+        ++n;
+
+        if( first == last )
+        {
+            break;
+        }
+
+        v1 |= static_cast<boost::uint64_t>( static_cast<unsigned char>( *first ) ) << 8;
+        ++first;
+        ++n;
+
+        if( first == last )
+        {
+            break;
+        }
+
+        v1 |= static_cast<boost::uint64_t>( static_cast<unsigned char>( *first ) ) << 16;
+        ++first;
+        ++n;
+
+        if( first == last )
+        {
+            break;
+        }
+
+        v1 |= static_cast<boost::uint64_t>( static_cast<unsigned char>( *first ) ) << 24;
+        ++first;
+        ++n;
+
+        if( first == last )
+        {
+            break;
+        }
+
+        v1 |= static_cast<boost::uint64_t>( static_cast<unsigned char>( *first ) ) << 32;
+        ++first;
+        ++n;
+
+        if( first == last )
+        {
+            break;
+        }
+
+        v1 |= static_cast<boost::uint64_t>( static_cast<unsigned char>( *first ) ) << 40;
+        ++first;
+        ++n;
+
+        if( first == last )
+        {
+            break;
+        }
+
+        v1 |= static_cast<boost::uint64_t>( static_cast<unsigned char>( *first ) ) << 48;
+        ++first;
+        ++n;
+
+        if( first == last )
+        {
+            break;
+        }
+
+        v1 |= static_cast<boost::uint64_t>( static_cast<unsigned char>( *first ) ) << 56;
+        ++first;
+        ++n;
+
+        w += q;
+        h ^= mulx( v1 + w, k );
+    }
+
+    h ^= n;
+
+    w += q;
+    h ^= mulx( v1 + w, k );
+
+    return mulx( h + w, k );
 }
 
 } // namespace hash_detail

include/boost/container_hash/detail/hash_tuple.hpp

@@ -1,133 +0,0 @@
-// Copyright 2005-2009 Daniel James.
-// Copyright 2021 Peter Dimov.
-// Distributed under the Boost Software License, Version 1.0.
-// https://www.boost.org/LICENSE_1_0.txt
-
-#ifndef BOOST_HASH_DETAIL_HASH_TUPLE_LIKE_HPP
-#define BOOST_HASH_DETAIL_HASH_TUPLE_LIKE_HPP
-
-#include <boost/container_hash/hash_fwd.hpp>
-#include <boost/type_traits/enable_if.hpp>
-#include <boost/config.hpp>
-
-#if defined(BOOST_NO_CXX11_HDR_TUPLE)
-
-// no support
-
-#else
-
-#include <tuple>
-
-namespace boost
-{
-namespace hash_detail
-{
-
-template <std::size_t I, typename T>
-inline typename boost::enable_if_<(I == std::tuple_size<T>::value),
-        void>::type
-    hash_combine_tuple(std::size_t&, T const&)
-{
-}
-
-template <std::size_t I, typename T>
-inline typename boost::enable_if_<(I < std::tuple_size<T>::value),
-        void>::type
-    hash_combine_tuple(std::size_t& seed, T const& v)
-{
-    boost::hash_combine(seed, std::get<I>(v));
-    boost::hash_detail::hash_combine_tuple<I + 1>(seed, v);
-}
-
-template <typename T>
-inline std::size_t hash_tuple(T const& v)
-{
-    std::size_t seed = 0;
-    boost::hash_detail::hash_combine_tuple<0>(seed, v);
-    return seed;
-}
-
-} // namespace hash_detail
-
-#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
-
-template <typename... T>
-inline std::size_t hash_value(std::tuple<T...> const& v)
-{
-    return boost::hash_detail::hash_tuple(v);
-}
-
-#else
-
-inline std::size_t hash_value(std::tuple<> const& v)
-{
-    return boost::hash_detail::hash_tuple(v);
-}
-
-template<typename A0>
-inline std::size_t hash_value(std::tuple<A0> const& v)
-{
-    return boost::hash_detail::hash_tuple(v);
-}
-
-template<typename A0, typename A1>
-inline std::size_t hash_value(std::tuple<A0, A1> const& v)
-{
-    return boost::hash_detail::hash_tuple(v);
-}
-
-template<typename A0, typename A1, typename A2>
-inline std::size_t hash_value(std::tuple<A0, A1, A2> const& v)
-{
-    return boost::hash_detail::hash_tuple(v);
-}
-
-template<typename A0, typename A1, typename A2, typename A3>
-inline std::size_t hash_value(std::tuple<A0, A1, A2, A3> const& v)
-{
-    return boost::hash_detail::hash_tuple(v);
-}
-
-template<typename A0, typename A1, typename A2, typename A3, typename A4>
-inline std::size_t hash_value(std::tuple<A0, A1, A2, A3, A4> const& v)
-{
-    return boost::hash_detail::hash_tuple(v);
-}
-
-template<typename A0, typename A1, typename A2, typename A3, typename A4, typename A5>
-inline std::size_t hash_value(std::tuple<A0, A1, A2, A3, A4, A5> const& v)
-{
-    return boost::hash_detail::hash_tuple(v);
-}
-
-template<typename A0, typename A1, typename A2, typename A3, typename A4, typename A5, typename A6>
-inline std::size_t hash_value(std::tuple<A0, A1, A2, A3, A4, A5, A6> const& v)
-{
-    return boost::hash_detail::hash_tuple(v);
-}
-
-template<typename A0, typename A1, typename A2, typename A3, typename A4, typename A5, typename A6, typename A7>
-inline std::size_t hash_value(std::tuple<A0, A1, A2, A3, A4, A5, A6, A7> const& v)
-{
-    return boost::hash_detail::hash_tuple(v);
-}
-
-template<typename A0, typename A1, typename A2, typename A3, typename A4, typename A5, typename A6, typename A7, typename A8>
-inline std::size_t hash_value(std::tuple<A0, A1, A2, A3, A4, A5, A6, A7, A8> const& v)
-{
-    return boost::hash_detail::hash_tuple(v);
-}
-
-template<typename A0, typename A1, typename A2, typename A3, typename A4, typename A5, typename A6, typename A7, typename A8, typename A9>
-inline std::size_t hash_value(std::tuple<A0, A1, A2, A3, A4, A5, A6, A7, A8, A9> const& v)
-{
-    return boost::hash_detail::hash_tuple(v);
-}
-
-#endif // #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
-
-} // namespace boost
-
-#endif // #if defined(BOOST_NO_CXX11_HDR_TUPLE)
-
-#endif // #ifndef BOOST_HASH_DETAIL_HASH_TUPLE_LIKE_HPP

include/boost/container_hash/detail/hash_tuple_like.hpp

@@ -0,0 +1,156 @@
+// Copyright 2005-2009 Daniel James.
+// Copyright 2021 Peter Dimov.
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#ifndef BOOST_HASH_DETAIL_HASH_TUPLE_LIKE_HPP
+#define BOOST_HASH_DETAIL_HASH_TUPLE_LIKE_HPP
+
+#include <boost/container_hash/hash_fwd.hpp>
+#include <boost/container_hash/is_tuple_like.hpp>
+#include <boost/container_hash/is_range.hpp>
+#include <boost/type_traits/enable_if.hpp>
+#include <boost/config.hpp>
+#include <boost/config/workaround.hpp>
+
+#if defined(BOOST_NO_CXX11_HDR_TUPLE)
+
+// no support for tuple-likes
+
+#else
+
+#include <tuple>
+
+namespace boost
+{
+namespace hash_detail
+{
+
+template <std::size_t I, typename T>
+inline
+typename boost::enable_if_<(I == std::tuple_size<T>::value), void>::type
+    hash_combine_tuple_like( std::size_t&, T const& )
+{
+}
+
+template <std::size_t I, typename T>
+inline
+typename boost::enable_if_<(I < std::tuple_size<T>::value), void>::type
+    hash_combine_tuple_like( std::size_t& seed, T const& v )
+{
+    using std::get;
+    boost::hash_combine( seed, get<I>( v ) );
+
+    boost::hash_detail::hash_combine_tuple_like<I + 1>( seed, v );
+}
+
+template <typename T>
+inline std::size_t hash_tuple_like( T const& v )
+{
+    std::size_t seed = 0;
+
+    boost::hash_detail::hash_combine_tuple_like<0>( seed, v );
+
+    return seed;
+}
+
+} // namespace hash_detail
+
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+#if !BOOST_WORKAROUND(BOOST_MSVC, <= 1800)
+
+template <class T>
+inline
+typename boost::enable_if_<
+    container_hash::is_tuple_like<T>::value && !container_hash::is_range<T>::value,
+std::size_t>::type
+    hash_value( T const& v )
+{
+    return boost::hash_detail::hash_tuple_like( v );
+}
+
+#else
+
+template <typename... T>
+inline std::size_t hash_value( std::tuple<T...> const& v )
+{
+    return boost::hash_detail::hash_tuple_like( v );
+}
+
+#endif
+
+#else
+
+inline std::size_t hash_value( std::tuple<> const& v )
+{
+    return boost::hash_detail::hash_tuple_like( v );
+}
+
+template<typename A0>
+inline std::size_t hash_value( std::tuple<A0> const& v )
+{
+    return boost::hash_detail::hash_tuple_like( v );
+}
+
+template<typename A0, typename A1>
+inline std::size_t hash_value( std::tuple<A0, A1> const& v )
+{
+    return boost::hash_detail::hash_tuple_like( v );
+}
+
+template<typename A0, typename A1, typename A2>
+inline std::size_t hash_value( std::tuple<A0, A1, A2> const& v )
+{
+    return boost::hash_detail::hash_tuple_like( v );
+}
+
+template<typename A0, typename A1, typename A2, typename A3>
+inline std::size_t hash_value( std::tuple<A0, A1, A2, A3> const& v )
+{
+    return boost::hash_detail::hash_tuple_like( v );
+}
+
+template<typename A0, typename A1, typename A2, typename A3, typename A4>
+inline std::size_t hash_value( std::tuple<A0, A1, A2, A3, A4> const& v )
+{
+    return boost::hash_detail::hash_tuple_like( v );
+}
+
+template<typename A0, typename A1, typename A2, typename A3, typename A4, typename A5>
+inline std::size_t hash_value( std::tuple<A0, A1, A2, A3, A4, A5> const& v )
+{
+    return boost::hash_detail::hash_tuple_like( v );
+}
+
+template<typename A0, typename A1, typename A2, typename A3, typename A4, typename A5, typename A6>
+inline std::size_t hash_value( std::tuple<A0, A1, A2, A3, A4, A5, A6> const& v )
+{
+    return boost::hash_detail::hash_tuple_like( v );
+}
+
+template<typename A0, typename A1, typename A2, typename A3, typename A4, typename A5, typename A6, typename A7>
+inline std::size_t hash_value( std::tuple<A0, A1, A2, A3, A4, A5, A6, A7> const& v )
+{
+    return boost::hash_detail::hash_tuple_like( v );
+}
+
+template<typename A0, typename A1, typename A2, typename A3, typename A4, typename A5, typename A6, typename A7, typename A8>
+inline std::size_t hash_value( std::tuple<A0, A1, A2, A3, A4, A5, A6, A7, A8> const& v )
+{
+    return boost::hash_detail::hash_tuple_like( v );
+}
+
+template<typename A0, typename A1, typename A2, typename A3, typename A4, typename A5, typename A6, typename A7, typename A8, typename A9>
+inline std::size_t hash_value( std::tuple<A0, A1, A2, A3, A4, A5, A6, A7, A8, A9> const& v )
+{
+    return boost::hash_detail::hash_tuple_like( v );
+}
+
+#endif // #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+} // namespace boost
+
+#endif // #if defined(BOOST_NO_CXX11_HDR_TUPLE)
+
+#endif // #ifndef BOOST_HASH_DETAIL_HASH_TUPLE_LIKE_HPP

include/boost/container_hash/detail/mulx.hpp

@@ -0,0 +1,79 @@
+// Copyright 2022, 2023 Peter Dimov
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#ifndef BOOST_HASH_DETAIL_MULX_HPP
+#define BOOST_HASH_DETAIL_MULX_HPP
+
+#include <boost/cstdint.hpp>
+#if defined(_MSC_VER)
+# include <intrin.h>
+#endif
+
+namespace boost
+{
+namespace hash_detail
+{
+
+#if defined(_MSC_VER) && defined(_M_X64) && !defined(__clang__)
+
+__forceinline boost::uint64_t mulx( boost::uint64_t x, boost::uint64_t y )
+{
+    boost::uint64_t r2;
+    boost::uint64_t r = _umul128( x, y, &r2 );
+    return r ^ r2;
+}
+
+#elif defined(_MSC_VER) && defined(_M_ARM64) && !defined(__clang__)
+
+__forceinline boost::uint64_t mulx( boost::uint64_t x, boost::uint64_t y )
+{
+    boost::uint64_t r = x * y;
+    boost::uint64_t r2 = __umulh( x, y );
+    return r ^ r2;
+}
+
+#elif defined(__SIZEOF_INT128__)
+
+inline boost::uint64_t mulx( boost::uint64_t x, boost::uint64_t y )
+{
+    __uint128_t r = static_cast<__uint128_t>( x ) * y;
+    return static_cast<boost::uint64_t>( r ) ^ static_cast<boost::uint64_t>( r >> 64 );
+}
+
+#else
+
+inline boost::uint64_t mulx( boost::uint64_t x, boost::uint64_t y )
+{
+    boost::uint64_t x1 = static_cast<boost::uint32_t>( x );
+    boost::uint64_t x2 = x >> 32;
+
+    boost::uint64_t y1 = static_cast<boost::uint32_t>( y );
+    boost::uint64_t y2 = y >> 32;
+
+    boost::uint64_t r3 = x2 * y2;
+
+    boost::uint64_t r2a = x1 * y2;
+
+    r3 += r2a >> 32;
+
+    boost::uint64_t r2b = x2 * y1;
+
+    r3 += r2b >> 32;
+
+    boost::uint64_t r1 = x1 * y1;
+
+    boost::uint64_t r2 = (r1 >> 32) + static_cast<boost::uint32_t>( r2a ) + static_cast<boost::uint32_t>( r2b );
+
+    r1 = (r2 << 32) + static_cast<boost::uint32_t>( r1 );
+    r3 += r2 >> 32;
+
+    return r1 ^ r3;
+}
+
+#endif
+
+} // namespace hash_detail
+} // namespace boost
+
+#endif // #ifndef BOOST_HASH_DETAIL_MULX_HPP

include/boost/container_hash/detail/requires_cxx11.hpp

@@ -0,0 +1,22 @@
+#ifndef BOOST_HASH_DETAIL_REQUIRES_CXX11_HPP_INCLUDED
+#define BOOST_HASH_DETAIL_REQUIRES_CXX11_HPP_INCLUDED
+
+// Copyright 2023 Peter Dimov
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#include <boost/config.hpp>
+#include <boost/config/pragma_message.hpp>
+
+#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || \
+    defined(BOOST_NO_CXX11_RVALUE_REFERENCES) || \
+    defined(BOOST_NO_CXX11_DECLTYPE) || \
+    defined(BOOST_NO_CXX11_CONSTEXPR) || \
+    defined(BOOST_NO_CXX11_NOEXCEPT) || \
+    defined(BOOST_NO_CXX11_HDR_TUPLE)
+
+BOOST_PRAGMA_MESSAGE("C++03 support is deprecated in Boost.ContainerHash 1.82 and will be removed in Boost.ContainerHash 1.84.")
+
+#endif
+
+#endif // #ifndef BOOST_HASH_DETAIL_REQUIRES_CXX11_HPP_INCLUDED

include/boost/container_hash/hash.hpp

@@ -11,11 +11,12 @@
 #define BOOST_FUNCTIONAL_HASH_HASH_HPP
 
 #include <boost/container_hash/hash_fwd.hpp>
+#include <boost/container_hash/detail/requires_cxx11.hpp>
 #include <boost/container_hash/is_range.hpp>
 #include <boost/container_hash/is_contiguous_range.hpp>
 #include <boost/container_hash/is_unordered_range.hpp>
 #include <boost/container_hash/is_described_class.hpp>
-#include <boost/container_hash/detail/hash_tuple.hpp>
+#include <boost/container_hash/detail/hash_tuple_like.hpp>
 #include <boost/container_hash/detail/hash_mix.hpp>
 #include <boost/container_hash/detail/hash_range.hpp>
 #include <boost/type_traits/is_enum.hpp>
@@ -27,6 +28,7 @@
 #include <boost/type_traits/enable_if.hpp>
 #include <boost/type_traits/conjunction.hpp>
 #include <boost/type_traits/is_union.hpp>
+#include <boost/type_traits/is_same.hpp>
 #include <boost/describe/bases.hpp>
 #include <boost/describe/members.hpp>
 #include <boost/cstdint.hpp>
@@ -117,7 +119,7 @@ namespace boost
                 std::size_t seed = 0;
 
                 seed = static_cast<std::size_t>( v >> 32 ) + hash_detail::hash_mix( seed );
-                seed = static_cast<std::size_t>( v ) + hash_detail::hash_mix( seed );
+                seed = static_cast<std::size_t>( v  & 0xFFFFFFFF ) + hash_detail::hash_mix( seed );
 
                 return seed;
             }
@@ -494,6 +496,19 @@ namespace boost
         return seed;
     }
 
+#endif
+
+    // std::nullptr_t
+
+#if !defined(BOOST_NO_CXX11_NULLPTR)
+
+    template <typename T>
+    typename boost::enable_if_<boost::is_same<T, std::nullptr_t>::value, std::size_t>::type
+        hash_value( T const& /*v*/ )
+    {
+        return boost::hash_value( static_cast<void*>( nullptr ) );
+    }
+
 #endif
 
     // std::optional

include/boost/container_hash/hash_fwd.hpp

@@ -18,6 +18,7 @@ template<class T> struct is_range;
 template<class T> struct is_contiguous_range;
 template<class T> struct is_unordered_range;
 template<class T> struct is_described_class;
+template<class T> struct is_tuple_like;
 
 } // namespace container_hash
 

include/boost/container_hash/is_contiguous_range.hpp

@@ -5,6 +5,7 @@
 #ifndef BOOST_HASH_IS_CONTIGUOUS_RANGE_HPP_INCLUDED
 #define BOOST_HASH_IS_CONTIGUOUS_RANGE_HPP_INCLUDED
 
+#include <boost/container_hash/detail/requires_cxx11.hpp>
 #include <boost/container_hash/is_range.hpp>
 #include <boost/type_traits/integral_constant.hpp>
 #include <boost/config.hpp>

include/boost/container_hash/is_range.hpp

@@ -5,6 +5,7 @@
 #ifndef BOOST_HASH_IS_RANGE_HPP_INCLUDED
 #define BOOST_HASH_IS_RANGE_HPP_INCLUDED
 
+#include <boost/container_hash/detail/requires_cxx11.hpp>
 #include <boost/type_traits/integral_constant.hpp>
 #include <boost/type_traits/is_integral.hpp>
 #include <boost/type_traits/declval.hpp>

include/boost/container_hash/is_tuple_like.hpp

@@ -0,0 +1,42 @@
+#ifndef BOOST_HASH_IS_TUPLE_LIKE_HPP_INCLUDED
+#define BOOST_HASH_IS_TUPLE_LIKE_HPP_INCLUDED
+
+// Copyright 2017, 2022 Peter Dimov.
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#include <boost/type_traits/integral_constant.hpp>
+#include <boost/config.hpp>
+#include <boost/config/workaround.hpp>
+#include <utility>
+
+namespace boost
+{
+namespace hash_detail
+{
+
+template<class T, class E = true_type> struct is_tuple_like_: false_type
+{
+};
+
+#if !defined(BOOST_NO_CXX11_HDR_TUPLE) && !BOOST_WORKAROUND(BOOST_MSVC, <= 1800)
+
+template<class T> struct is_tuple_like_<T, integral_constant<bool, std::tuple_size<T>::value == std::tuple_size<T>::value> >: true_type
+{
+};
+
+#endif
+
+} // namespace hash_detail
+
+namespace container_hash
+{
+
+template<class T> struct is_tuple_like: hash_detail::is_tuple_like_<T>
+{
+};
+
+} // namespace container_hash
+} // namespace boost
+
+#endif // #ifndef BOOST_HASH_IS_TUPLE_LIKE_HPP_INCLUDED

test/Jamfile.v2

@@ -77,7 +77,7 @@ run hash_string_test2.cpp ;
 # for gcc-4.8
 local fs-path-req = "-<toolset>gcc:<cxxflags>-Wshadow" "-<toolset>gcc:<cxxflags>-Wconversion" ;
 
-run hash_fs_path_test.cpp /boost//filesystem/<warnings>off : : : $(fs-path-req) <toolset>msvc-14.0,<cxxstd>latest:<build>no <toolset>msvc-8.0:<build>no ;
+run hash_fs_path_test.cpp /boost//filesystem/<warnings>off : : : $(fs-path-req) <toolset>msvc-14.0,<cxxstd>latest:<build>no <toolset>msvc-8.0:<build>no <undefined-sanitizer>norecover:<link>static ;
 run is_range_test2.cpp : : : $(fs-path-req) <toolset>msvc-8.0:<build>no ;
 
 run hash_container_test.cpp ;
@@ -115,3 +115,13 @@ run described_class_test.cpp
 
 run hash_is_avalanching_test.cpp ;
 run hash_is_avalanching_test2.cpp ;
+
+run hash_integral_test2.cpp ;
+
+run hash_nullptr_test.cpp ;
+
+run is_tuple_like_test.cpp ;
+
+run hash_tuple_like_test.cpp ;
+run hash_tuple_like_test2.cpp
+  : : : <warnings>extra ;

test/hash_complex_test.cpp

@@ -3,6 +3,8 @@
 // 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)
 
+#define _SILENCE_NONFLOATING_COMPLEX_DEPRECATION_WARNING
+
 #include "./config.hpp"
 
 #if !defined(BOOST_HASH_TEST_EXTENSIONS)

test/hash_integral_test.cpp

@@ -7,7 +7,7 @@
 #include <boost/core/lightweight_test.hpp>
 #include <boost/core/type_name.hpp>
 #include <boost/type_traits/is_signed.hpp>
-#include <set>
+#include <boost/config.hpp>
 
 #if defined(BOOST_MSVC)
 #pragma warning(disable: 4127) // conditional expression is constant

test/hash_integral_test2.cpp

@@ -0,0 +1,52 @@
+// Copyright 2005-2009 Daniel James.
+// Copyright 2021 Peter Dimov.
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#include <boost/container_hash/hash.hpp>
+#include <boost/core/lightweight_test.hpp>
+#include <boost/core/type_name.hpp>
+#include <boost/type_traits/is_signed.hpp>
+#include <boost/type_traits/make_unsigned.hpp>
+#include <boost/static_assert.hpp>
+#include <boost/config.hpp>
+
+// This test checks that values representable in a signed
+// and the corresponding unsigned type hash to the same value
+
+template<class T>
+void signed_unsigned_test()
+{
+    BOOST_STATIC_ASSERT( boost::is_signed<T>::value );
+
+    typedef typename boost::make_unsigned<T>::type U;
+
+    T x = std::numeric_limits<T>::max();
+
+    do
+    {
+        BOOST_TEST_EQ( boost::hash<T>()( x ), boost::hash<U>()( static_cast<U>( x ) ) );
+        x /= 3;
+    }
+    while( x > 0 );
+}
+
+#define TEST(type) std::cerr << "Testing: " #type " (" << boost::core::type_name<type>() << ")\n"; signed_unsigned_test<type>();
+
+int main()
+{
+    TEST(signed char)
+    TEST(short)
+    TEST(int)
+    TEST(long)
+
+#if !defined(BOOST_NO_LONG_LONG)
+    TEST(boost::long_long_type)
+#endif
+
+#if defined(BOOST_HAS_INT128)
+    TEST(boost::int128_type)
+#endif
+
+    return boost::report_errors();
+}

test/hash_is_avalanching_test.cpp

@@ -4,22 +4,8 @@
 
 #include <boost/container_hash/hash.hpp>
 #include <boost/core/lightweight_test_trait.hpp>
-#include <boost/config.hpp>
-#include <boost/config/pragma_message.hpp>
-
-#if defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS)
-
-BOOST_PRAGMA_MESSAGE( "Test skipped, BOOST_NO_CXX11_HDR_TYPE_TRAITS is defined" )
-int main() {}
-
-#elif defined(BOOST_NO_CXX11_TEMPLATE_ALIASES)
-
-BOOST_PRAGMA_MESSAGE( "Test skipped, BOOST_NO_CXX11_TEMPLATE_ALIASES is defined" )
-int main() {}
-
-#else
-
 #include <boost/unordered/hash_traits.hpp>
+#include <boost/config.hpp>
 #include <string>
 
 enum my_char { min = 0, max = 255 };
@@ -53,5 +39,3 @@ int main()
 
     return boost::report_errors();
 }
-
-#endif

test/hash_is_avalanching_test2.cpp

@@ -7,17 +7,7 @@
 #include <boost/config.hpp>
 #include <boost/config/pragma_message.hpp>
 
-#if defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS)
-
-BOOST_PRAGMA_MESSAGE( "Test skipped, BOOST_NO_CXX11_HDR_TYPE_TRAITS is defined" )
-int main() {}
-
-#elif defined(BOOST_NO_CXX11_TEMPLATE_ALIASES)
-
-BOOST_PRAGMA_MESSAGE( "Test skipped, BOOST_NO_CXX11_TEMPLATE_ALIASES is defined" )
-int main() {}
-
-#elif defined(BOOST_NO_CXX17_HDR_STRING_VIEW)
+#if defined(BOOST_NO_CXX17_HDR_STRING_VIEW)
 
 BOOST_PRAGMA_MESSAGE( "Test skipped, BOOST_NO_CXX17_HDR_STRING_VIEW is defined" )
 int main() {}

test/hash_nullptr_test.cpp

@@ -0,0 +1,41 @@
+// Copyright 2022 Peter Dimov.
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#include <boost/container_hash/hash.hpp>
+#include <boost/core/lightweight_test.hpp>
+#include <boost/config.hpp>
+#include <boost/config/pragma_message.hpp>
+#include <cstddef>
+
+#if defined(BOOST_NO_CXX11_NULLPTR)
+
+BOOST_PRAGMA_MESSAGE( "Test skipped, BOOST_NO_CXX11_NULLPTR is defined" )
+int main() {}
+
+#else
+
+template<class T> std::size_t hv( T const& x )
+{
+    return boost::hash<T>()( x );
+}
+
+int main()
+{
+    {
+        BOOST_TEST_EQ( hv((void*)0), hv(nullptr) );
+    }
+
+    {
+        int x = 0;
+
+        BOOST_TEST_EQ( hv((int*)0), hv(nullptr) );
+        BOOST_TEST_NE( hv(&x), hv(nullptr) );
+
+        (void)x;
+    }
+
+    return boost::report_errors();
+}
+
+#endif

test/hash_reference_values.cpp

@@ -284,19 +284,19 @@ int main()
     // string
 #if SIZE_MAX == 4294967295U
 
-    BOOST_TEST_EQ( hv(std::string()), 1580013426U );
-    BOOST_TEST_EQ( hv(std::string("abc")), 469308065U );
-    BOOST_TEST_EQ( hv(std::string("\0", 1)), 165258820U );
-    BOOST_TEST_EQ( hv(std::string("\0\0", 2)), 4017288109U );
-    BOOST_TEST_EQ( hv(std::string("\0\0\0", 3)), 1352445396U );
+    BOOST_TEST_EQ( hv(std::string()), 1868390524U );
+    BOOST_TEST_EQ( hv(std::string("abc")), 3674866719U );
+    BOOST_TEST_EQ( hv(std::string("\0", 1)), 1965885047U );
+    BOOST_TEST_EQ( hv(std::string("\0\0", 2)), 54340706U );
+    BOOST_TEST_EQ( hv(std::string("\0\0\0", 3)), 688730713U );
 
 #else
 
-    BOOST_TEST_EQ( hv(std::string()), 2220755840493918647ULL );
-    BOOST_TEST_EQ( hv(std::string("abc")), 7565583854499162206ULL );
-    BOOST_TEST_EQ( hv(std::string("\0", 1)), 1241131678047372712ULL );
-    BOOST_TEST_EQ( hv(std::string("\0\0", 2)), 152341731040131640ULL );
-    BOOST_TEST_EQ( hv(std::string("\0\0\0", 3)), 12957252994983528908ULL );
+    BOOST_TEST_EQ( hv(std::string()), 2060355526954642342ULL );
+    BOOST_TEST_EQ( hv(std::string("abc")), 2539195663733406973ULL );
+    BOOST_TEST_EQ( hv(std::string("\0", 1)), 18432168439372857722ULL );
+    BOOST_TEST_EQ( hv(std::string("\0\0", 2)), 6494115972580589074ULL );
+    BOOST_TEST_EQ( hv(std::string("\0\0\0", 3)), 4419026507380069870ULL );
 
 #endif
 
@@ -376,17 +376,17 @@ int main()
     // vector<char>
 #if SIZE_MAX == 4294967295U
 
-    BOOST_TEST_EQ( hv(std::vector<char>(0)), 1580013426U );
-    BOOST_TEST_EQ( hv(std::vector<char>(1)), 165258820U );
-    BOOST_TEST_EQ( hv(std::vector<char>(2)), 4017288109U );
-    BOOST_TEST_EQ( hv(std::vector<char>(3)), 1352445396U );
+    BOOST_TEST_EQ( hv(std::vector<char>(0)), 1868390524U );
+    BOOST_TEST_EQ( hv(std::vector<char>(1)), 1965885047U );
+    BOOST_TEST_EQ( hv(std::vector<char>(2)), 54340706U );
+    BOOST_TEST_EQ( hv(std::vector<char>(3)), 688730713U );
 
 #else
 
-    BOOST_TEST_EQ( hv(std::vector<char>(0)), 2220755840493918647ULL );
-    BOOST_TEST_EQ( hv(std::vector<char>(1)), 1241131678047372712ULL );
-    BOOST_TEST_EQ( hv(std::vector<char>(2)), 152341731040131640ULL );
-    BOOST_TEST_EQ( hv(std::vector<char>(3)), 12957252994983528908ULL );
+    BOOST_TEST_EQ( hv(std::vector<char>(0)), 2060355526954642342ULL );
+    BOOST_TEST_EQ( hv(std::vector<char>(1)), 18432168439372857722ULL );
+    BOOST_TEST_EQ( hv(std::vector<char>(2)), 6494115972580589074ULL );
+    BOOST_TEST_EQ( hv(std::vector<char>(3)), 4419026507380069870ULL );
 
 #endif
 
@@ -427,17 +427,17 @@ int main()
     // list<char>
 #if SIZE_MAX == 4294967295U
 
-    BOOST_TEST_EQ( hv(std::list<char>(0)), 1580013426U );
-    BOOST_TEST_EQ( hv(std::list<char>(1)), 165258820U );
-    BOOST_TEST_EQ( hv(std::list<char>(2)), 4017288109U );
-    BOOST_TEST_EQ( hv(std::list<char>(3)), 1352445396U );
+    BOOST_TEST_EQ( hv(std::list<char>(0)), 1868390524U );
+    BOOST_TEST_EQ( hv(std::list<char>(1)), 1965885047U );
+    BOOST_TEST_EQ( hv(std::list<char>(2)), 54340706U );
+    BOOST_TEST_EQ( hv(std::list<char>(3)), 688730713U );
 
 #else
 
-    BOOST_TEST_EQ( hv(std::list<char>(0)), 2220755840493918647ULL );
-    BOOST_TEST_EQ( hv(std::list<char>(1)), 1241131678047372712ULL );
-    BOOST_TEST_EQ( hv(std::list<char>(2)), 152341731040131640ULL );
-    BOOST_TEST_EQ( hv(std::list<char>(3)), 12957252994983528908ULL );
+    BOOST_TEST_EQ( hv(std::list<char>(0)), 2060355526954642342ULL );
+    BOOST_TEST_EQ( hv(std::list<char>(1)), 18432168439372857722ULL );
+    BOOST_TEST_EQ( hv(std::list<char>(2)), 6494115972580589074ULL );
+    BOOST_TEST_EQ( hv(std::list<char>(3)), 4419026507380069870ULL );
 
 #endif
 

test/hash_tuple_like_test.cpp

@@ -0,0 +1,204 @@
+// Copyright 2022 Peter Dimov.
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#if defined(__clang__)
+# pragma clang diagnostic ignored "-Wmismatched-tags"
+#endif
+
+#include <boost/container_hash/hash.hpp>
+#include <boost/core/lightweight_test.hpp>
+#include <boost/type_traits/enable_if.hpp>
+#include <boost/type_traits/is_same.hpp>
+#include <boost/type_traits/integral_constant.hpp>
+#include <boost/config.hpp>
+#include <utility>
+
+#if !defined(BOOST_NO_CXX11_HDR_TUPLE)
+
+#include <tuple>
+
+namespace user
+{
+
+struct Y1
+{
+    int a;
+    int b;
+};
+
+template<std::size_t I> int& get( Y1& v );
+template<std::size_t I> int const& get( Y1 const& v );
+
+template<> int& get<0>( Y1& v )
+{
+    return v.a;
+}
+
+template<> int const& get<0>( Y1 const& v )
+{
+    return v.a;
+}
+
+template<> int& get<1>( Y1& v )
+{
+    return v.b;
+}
+
+template<> int const& get<1>( Y1 const& v )
+{
+    return v.b;
+}
+
+struct Y2
+{
+    int a;
+    int b;
+
+    template<class T> friend
+        typename boost::enable_if_<boost::is_same<T, Y2>::value, std::size_t>::type
+        hash_value( T const& v )
+    {
+        std::size_t seed = 0;
+
+        boost::hash_combine( seed, v.a );
+        boost::hash_combine( seed, v.b );
+
+        return seed;
+    }
+};
+
+} // namespace user
+
+namespace std
+{
+
+template<> struct tuple_size<user::Y1>: std::integral_constant<std::size_t, 2>
+{
+};
+
+template<> struct tuple_size<user::Y2>: std::integral_constant<std::size_t, 2>
+{
+};
+
+} // namespace std
+
+namespace boost
+{
+namespace container_hash
+{
+
+    template<> struct is_tuple_like<user::Y2>: boost::false_type {};
+
+} // namespace container_hash
+} // namespace boost
+
+#endif
+
+template<class T> std::size_t hv( T const& t )
+{
+    return boost::hash<T>()( t );
+}
+
+int main()
+{
+    {
+        std::pair<int, int> tp( 1, 2 );
+        int const a[] = { 1, 2 };
+
+        BOOST_TEST_EQ( hv(tp), hv(a) );
+    }
+
+#if !defined(BOOST_NO_CXX11_HDR_TUPLE)
+
+    {
+        std::tuple<> tp;
+
+        BOOST_TEST_EQ( hv(tp), 0u );
+    }
+
+    {
+        std::tuple<int> tp( 1 );
+        int const a[] = { 1 };
+
+        BOOST_TEST_EQ( hv(tp), hv(a) );
+    }
+
+    {
+        std::tuple<int, int> tp( 1, 2 );
+        int const a[] = { 1, 2 };
+
+        BOOST_TEST_EQ( hv(tp), hv(a) );
+    }
+
+    {
+        std::tuple<int, int, int> tp( 1, 2, 3 );
+        int const a[] = { 1, 2, 3 };
+
+        BOOST_TEST_EQ( hv(tp), hv(a) );
+    }
+
+    {
+        std::tuple<int, int, int, int> tp( 1, 2, 3, 4 );
+        int const a[] = { 1, 2, 3, 4 };
+
+        BOOST_TEST_EQ( hv(tp), hv(a) );
+    }
+
+    {
+        std::tuple<int, int, int, int, int> tp( 1, 2, 3, 4, 5 );
+        int const a[] = { 1, 2, 3, 4, 5 };
+
+        BOOST_TEST_EQ( hv(tp), hv(a) );
+    }
+
+    {
+        std::tuple<int, int, int, int, int, int> tp( 1, 2, 3, 4, 5, 6 );
+        int const a[] = { 1, 2, 3, 4, 5, 6 };
+
+        BOOST_TEST_EQ( hv(tp), hv(a) );
+    }
+
+    {
+        std::tuple<int, int, int, int, int, int, int> tp( 1, 2, 3, 4, 5, 6, 7 );
+        int const a[] = { 1, 2, 3, 4, 5, 6, 7 };
+
+        BOOST_TEST_EQ( hv(tp), hv(a) );
+    }
+
+    {
+        std::tuple<int, int, int, int, int, int, int, int> tp( 1, 2, 3, 4, 5, 6, 7, 8 );
+        int const a[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
+
+        BOOST_TEST_EQ( hv(tp), hv(a) );
+    }
+
+    {
+        std::tuple<int, int, int, int, int, int, int, int, int> tp( 1, 2, 3, 4, 5, 6, 7, 8, 9 );
+        int const a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
+
+        BOOST_TEST_EQ( hv(tp), hv(a) );
+    }
+
+#if !BOOST_WORKAROUND(BOOST_MSVC, <= 1800)
+
+    {
+        user::Y1 tp = { 1, 2 };
+        int const a[] = { 1, 2 };
+
+        BOOST_TEST_EQ( hv(tp), hv(a) );
+    }
+
+#endif
+
+    {
+        user::Y2 tp = { 1, 2 };
+        int const a[] = { 1, 2 };
+
+        BOOST_TEST_EQ( hv(tp), hv(a) );
+    }
+
+#endif
+
+    return boost::report_errors();
+}

test/hash_tuple_like_test2.cpp

@@ -0,0 +1,78 @@
+// Copyright 2022 Peter Dimov.
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#if defined(__clang__)
+# pragma clang diagnostic ignored "-Wmismatched-tags"
+#endif
+
+#include <boost/container_hash/hash.hpp>
+#include <boost/core/lightweight_test.hpp>
+#include <boost/type_traits/integral_constant.hpp>
+#include <boost/describe/class.hpp>
+#include <boost/config.hpp>
+#include <boost/config/pragma_message.hpp>
+#include <utility>
+
+#if defined(BOOST_NO_CXX11_HDR_TUPLE)
+
+BOOST_PRAGMA_MESSAGE( "Skipping test because BOOST_NO_CXX11_HDR_TUPLE is defined" )
+int main() {}
+
+#elif !defined(BOOST_DESCRIBE_CXX14)
+
+BOOST_PRAGMA_MESSAGE( "Skipping test because BOOST_DESCRIBE_CXX14 is not defined" )
+int main() {}
+
+#else
+
+namespace user
+{
+
+struct Y3
+{
+    int a;
+    int b;
+};
+
+BOOST_DESCRIBE_STRUCT(Y3, (), (a, b))
+
+} // namespace user
+
+namespace std
+{
+
+template<> struct tuple_size<user::Y3>: std::integral_constant<std::size_t, 2>
+{
+};
+
+} // namespace std
+
+namespace boost
+{
+namespace container_hash
+{
+
+    template<> struct is_tuple_like<user::Y3>: boost::false_type {};
+
+} // namespace container_hash
+} // namespace boost
+
+template<class T> std::size_t hv( T const& t )
+{
+    return boost::hash<T>()( t );
+}
+
+int main()
+{
+    {
+        user::Y3 tp = { 1, 2 };
+        int const a[] = { 1, 2 };
+
+        BOOST_TEST_EQ( hv(tp), hv(a) );
+    }
+
+    return boost::report_errors();
+}
+
+#endif

test/is_tuple_like_test.cpp

@@ -0,0 +1,91 @@
+// Copyright 2017, 2022 Peter Dimov.
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#if defined(__clang__)
+# pragma clang diagnostic ignored "-Wmismatched-tags"
+#endif
+
+#include <boost/container_hash/is_tuple_like.hpp>
+#include <boost/core/lightweight_test_trait.hpp>
+#include <boost/config.hpp>
+#include <boost/config/workaround.hpp>
+#include <utility>
+
+struct X
+{
+};
+
+#if !defined(BOOST_NO_CXX11_HDR_TUPLE)
+
+#include <tuple>
+
+namespace user
+{
+
+struct Y
+{
+    int a;
+    int b;
+};
+
+template<std::size_t I> int& get( Y& v );
+template<std::size_t I> int const& get( Y const& v );
+
+template<> int& get<0>( Y& v )
+{
+    return v.a;
+}
+
+template<> int const& get<0>( Y const& v )
+{
+    return v.a;
+}
+
+template<> int& get<1>( Y& v )
+{
+    return v.b;
+}
+
+template<> int const& get<1>( Y const& v )
+{
+    return v.b;
+}
+
+} // namespace user
+
+namespace std
+{
+
+template<> struct tuple_size<user::Y>: std::integral_constant<std::size_t, 2>
+{
+};
+
+} // namespace std
+
+#endif // #if !defined(BOOST_NO_CXX11_HDR_TUPLE)
+
+int main()
+{
+    using boost::container_hash::is_tuple_like;
+
+    BOOST_TEST_TRAIT_FALSE((is_tuple_like<void>));
+    BOOST_TEST_TRAIT_FALSE((is_tuple_like<int>));
+    BOOST_TEST_TRAIT_FALSE((is_tuple_like<X>));
+    BOOST_TEST_TRAIT_FALSE((is_tuple_like<int[2]>));
+
+#if !defined(BOOST_NO_CXX11_HDR_TUPLE) && !BOOST_WORKAROUND(BOOST_MSVC, <= 1800)
+
+    BOOST_TEST_TRAIT_TRUE((is_tuple_like< std::pair<int, X> >));
+
+    BOOST_TEST_TRAIT_TRUE((is_tuple_like< std::tuple<> >));
+    BOOST_TEST_TRAIT_TRUE((is_tuple_like< std::tuple<X> >));
+    BOOST_TEST_TRAIT_TRUE((is_tuple_like< std::tuple<X, X> >));
+    BOOST_TEST_TRAIT_TRUE((is_tuple_like< std::tuple<X, X, X> >));
+
+    BOOST_TEST_TRAIT_TRUE((is_tuple_like<user::Y>));
+
+#endif
+
+    return boost::report_errors();
+}