Simplify group14::overflow() implementation, update code to use group15 on non-SSE2 targets

Update reserve_tests for new group layout
Add group14 prototype
2026-08-05 05:04:12 +02:00 · 2023-03-09 11:18:36 -08:00 · 2023-03-08 15:34:15 -08:00 · 2023-03-08 15:34:06 -08:00
176 changed files with 2087 additions and 14953 deletions
@@ -40,152 +40,87 @@ environment:
      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2015
      B2_TOOLSET: msvc-12.0,msvc-14.0

-    - FLAVOR: Visual Studio 2017, C++14
+    - FLAVOR: Visual Studio 2017
      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
-      B2_CXXSTD: 14
+      B2_CXXSTD: 14,17
      B2_TOOLSET: msvc-14.1

-    - FLAVOR: Visual Studio 2017, C++17
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
-      B2_CXXSTD: 17
-      B2_TOOLSET: msvc-14.1
-
-    - FLAVOR: Visual Studio 2017, C++latest
+    - FLAVOR: Visual Studio 2017
      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
      B2_CXXSTD: latest
      B2_TOOLSET: msvc-14.1

-    - FLAVOR: cygwin (32-bit, C++03,11)
+    - FLAVOR: cygwin (32-bit)
      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
      ADDPATH: C:\cygwin\bin;
      B2_ADDRESS_MODEL: 32
-      B2_CXXSTD: 03,11
+      B2_CXXSTD: 03,11,14,1z
      B2_TOOLSET: gcc

-    - FLAVOR: cygwin (32-bit, C++14,1z)
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
-      ADDPATH: C:\cygwin\bin;
-      B2_ADDRESS_MODEL: 32
-      B2_CXXSTD: 14,1z
-      B2_TOOLSET: gcc
-
-    - FLAVOR: cygwin (64-bit, C++03,11)
+    - FLAVOR: cygwin (64-bit)
      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
      ADDPATH: C:\cygwin64\bin;
      B2_ADDRESS_MODEL: 64
-      B2_CXXSTD: 03,11
+      B2_CXXSTD: 03,11,14,1z
      B2_TOOLSET: gcc

-    - FLAVOR: cygwin (64-bit, C++14,1z)
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
-      ADDPATH: C:\cygwin64\bin;
-      B2_ADDRESS_MODEL: 64
-      B2_CXXSTD: 14,1z
-      B2_TOOLSET: gcc
-
-    - FLAVOR: cygwin (64-bit, latest, C++03)
+    - FLAVOR: cygwin (64-bit, latest)
      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2022
      ADDPATH: C:\cygwin64\bin;
      B2_ADDRESS_MODEL: 64
      B2_CXXSTD: 03
      B2_TOOLSET: gcc
      B2_FLAGS: "include=libs/unordered/test/unordered include=libs/unordered/test/exception"
-      B2_VARIANT: release

-    - FLAVOR: cygwin (64-bit, latest, C++11)
+    - FLAVOR: cygwin (64-bit, latest)
      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2022
      ADDPATH: C:\cygwin64\bin;
      B2_ADDRESS_MODEL: 64
      B2_CXXSTD: 11
      B2_TOOLSET: gcc
      B2_FLAGS: "include=libs/unordered/test/unordered include=libs/unordered/test/exception"
-      B2_VARIANT: release

-    - FLAVOR: cygwin (64-bit, latest, C++14)
+    - FLAVOR: cygwin (64-bit, latest)
      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2022
      ADDPATH: C:\cygwin64\bin;
      B2_ADDRESS_MODEL: 64
      B2_CXXSTD: 14
      B2_TOOLSET: gcc
      B2_FLAGS: "include=libs/unordered/test/unordered include=libs/unordered/test/exception"
-      B2_VARIANT: release

-    - FLAVOR: cygwin (64-bit, latest, C++1z)
+    - FLAVOR: cygwin (64-bit, latest)
      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2022
      ADDPATH: C:\cygwin64\bin;
      B2_ADDRESS_MODEL: 64
      B2_CXXSTD: 1z
      B2_TOOLSET: gcc
      B2_FLAGS: "include=libs/unordered/test/unordered include=libs/unordered/test/exception"
-      B2_VARIANT: release

-    - FLAVOR: mingw-w64, 32 bit, C++03
+    - FLAVOR: mingw-w64, 32 bit
      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
      ADDPATH: C:\mingw-w64\i686-8.1.0-posix-dwarf-rt_v6-rev0\mingw32\bin;
-      B2_CXXSTD: 03
+      B2_CXXSTD: 03,11,14
      B2_TOOLSET: gcc
      B2_ADDRESS_MODEL: 32

-    - FLAVOR: mingw-w64, 32 bit, C++11
+    - FLAVOR: mingw-w64, 32 bit
      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
      ADDPATH: C:\mingw-w64\i686-8.1.0-posix-dwarf-rt_v6-rev0\mingw32\bin;
-      B2_CXXSTD: 11
+      B2_CXXSTD: 17,2a
      B2_TOOLSET: gcc
      B2_ADDRESS_MODEL: 32

-    - FLAVOR: mingw-w64, 32 bit, C++14
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
-      ADDPATH: C:\mingw-w64\i686-8.1.0-posix-dwarf-rt_v6-rev0\mingw32\bin;
-      B2_CXXSTD: 14
-      B2_TOOLSET: gcc
-      B2_ADDRESS_MODEL: 32
-
-    - FLAVOR: mingw-w64, 32 bit, C++17
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
-      ADDPATH: C:\mingw-w64\i686-8.1.0-posix-dwarf-rt_v6-rev0\mingw32\bin;
-      B2_CXXSTD: 17
-      B2_TOOLSET: gcc
-      B2_ADDRESS_MODEL: 32
-
-    - FLAVOR: mingw-w64, 32 bit, C++2a
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
-      ADDPATH: C:\mingw-w64\i686-8.1.0-posix-dwarf-rt_v6-rev0\mingw32\bin;
-      B2_CXXSTD: 2a
-      B2_TOOLSET: gcc
-      B2_ADDRESS_MODEL: 32
-
-    - FLAVOR: mingw-w64, 64 bit, C++03
+    - FLAVOR: mingw-w64, 64 bit
      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
      ADDPATH: C:\mingw-w64\x86_64-8.1.0-posix-seh-rt_v6-rev0\mingw64\bin;
-      B2_CXXSTD: 03
+      B2_CXXSTD: 03,11,14
      B2_TOOLSET: gcc
      B2_ADDRESS_MODEL: 64

-    - FLAVOR: mingw-w64, 64 bit, C++11
+    - FLAVOR: mingw-w64, 64 bit
      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
      ADDPATH: C:\mingw-w64\x86_64-8.1.0-posix-seh-rt_v6-rev0\mingw64\bin;
-      B2_CXXSTD: 11
-      B2_TOOLSET: gcc
-      B2_ADDRESS_MODEL: 64
-
-    - FLAVOR: mingw-w64, 64 bit, C++14
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
-      ADDPATH: C:\mingw-w64\x86_64-8.1.0-posix-seh-rt_v6-rev0\mingw64\bin;
-      B2_CXXSTD: 14
-      B2_TOOLSET: gcc
-      B2_ADDRESS_MODEL: 64
-
-    - FLAVOR: mingw-w64, 64 bit, C++17
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
-      ADDPATH: C:\mingw-w64\x86_64-8.1.0-posix-seh-rt_v6-rev0\mingw64\bin;
-      B2_CXXSTD: 17
-      B2_TOOLSET: gcc
-      B2_ADDRESS_MODEL: 64
-
-    - FLAVOR: mingw-w64, 64 bit, C++2a
-      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
-      ADDPATH: C:\mingw-w64\x86_64-8.1.0-posix-seh-rt_v6-rev0\mingw64\bin;
-      B2_CXXSTD: 2a
+      B2_CXXSTD: 17,2a
      B2_TOOLSET: gcc
      B2_ADDRESS_MODEL: 64

@@ -11,7 +11,6 @@ local triggers =

 local ubsan = { UBSAN: '1', UBSAN_OPTIONS: 'print_stacktrace=1' };
 local asan = { ASAN: '1' };
-local tsan = { TSAN: '1' };

 local linux_pipeline(name, image, environment, packages = "", sources = [], arch = "amd64") =
 {
@@ -158,29 +157,16 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
    ),

    linux_pipeline(
-        "Linux 18.04 GCC 8 32/64 (03,11)",
+        "Linux 18.04 GCC 8 32/64",
        "cppalliance/droneubuntu1804:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-8', CXXSTD: '03,11', ADDRMD: '32,64' },
+        { TOOLSET: 'gcc', COMPILER: 'g++-8', CXXSTD: '03,11,14,17', ADDRMD: '32,64' },
        "g++-8-multilib",
    ),

    linux_pipeline(
-        "Linux 18.04 GCC 8 32/64 (14,17)",
-        "cppalliance/droneubuntu1804:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-8', CXXSTD: '14,17', ADDRMD: '32,64' },
-        "g++-8-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 20.04 GCC 9* 32/64 (03,11,14)",
+        "Linux 20.04 GCC 9* 32/64",
        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14', ADDRMD: '32,64' },
-    ),
-
-    linux_pipeline(
-        "Linux 20.04 GCC 9* 32/64 (17,2a)",
-        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '17,2a', ADDRMD: '32,64' },
+        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a', ADDRMD: '32,64' },
    ),

    linux_pipeline(
@@ -191,77 +177,36 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
    ),

    linux_pipeline(
-        "Linux 20.04 GCC 9* S390x (03,11,14)",
+        "Linux 20.04 GCC 9* S390x",
        "cppalliance/droneubuntu2004:multiarch",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14' },
+        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a' },
        arch="s390x",
    ),

    linux_pipeline(
-        "Linux 20.04 GCC 9* S390x (17,2a)",
-        "cppalliance/droneubuntu2004:multiarch",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '17,2a' },
-        arch="s390x",
-    ),
-
-    linux_pipeline(
-        "Linux 20.04 GCC 10 32/64 (03,11,14)",
+        "Linux 20.04 GCC 10 32/64",
        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-10', CXXSTD: '03,11,14', ADDRMD: '32,64' },
+        { TOOLSET: 'gcc', COMPILER: 'g++-10', CXXSTD: '03,11,14,17,20', ADDRMD: '32,64' },
        "g++-10-multilib",
    ),

    linux_pipeline(
-        "Linux 20.04 GCC 10 32/64 (17,20)",
-        "cppalliance/droneubuntu2004:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-10', CXXSTD: '17,20', ADDRMD: '32,64' },
-        "g++-10-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 11* 32/64 (03,11,14)",
+        "Linux 22.04 GCC 11* 32/64",
        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14', ADDRMD: '32,64' },
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 11* 32/64 (17,2a)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '17,2a', ADDRMD: '32,64' },
+        { TOOLSET: 'gcc', COMPILER: 'g++', CXXSTD: '03,11,14,17,2a', ADDRMD: '32,64' },
    ),

    linux_pipeline(
        "Linux 22.04 GCC 12 32 ASAN (03,11,14)",
        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '03,11', ADDRMD: '32' } + asan,
+        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '03,11,14', ADDRMD: '32' } + asan,
        "g++-12-multilib",
    ),

    linux_pipeline(
-        "Linux 22.04 GCC 12 32 ASAN (14)",
+        "Linux 22.04 GCC 12 32 ASAN (17,20,2b)",
        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '14', ADDRMD: '32' } + asan,
-        "g++-12-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 12 32 ASAN (17)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '17', ADDRMD: '32' } + asan,
-        "g++-12-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 12 32 ASAN (20)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '20', ADDRMD: '32' } + asan,
-        "g++-12-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 12 32 ASAN (2b)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '2b', ADDRMD: '32' } + asan,
+        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '17,20,2b', ADDRMD: '32' } + asan,
        "g++-12-multilib",
    ),

@@ -273,47 +218,12 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
    ),

    linux_pipeline(
-        "Linux 22.04 GCC 12 64 ASAN (17)",
+        "Linux 22.04 GCC 12 64 ASAN (17,20,2b)",
        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '17', ADDRMD: '64' } + asan,
+        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '17,20,2b', ADDRMD: '64' } + asan,
        "g++-12-multilib",
    ),

-    linux_pipeline(
-        "Linux 22.04 GCC 12 64 ASAN (20)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '20', ADDRMD: '64' } + asan,
-        "g++-12-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 12 64 ASAN (2b)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '2b', ADDRMD: '64' } + asan,
-        "g++-12-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 GCC 12 64 TSAN (11,14,17,20,2b)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-12', CXXSTD: '11,14,17,20,2b', ADDRMD: '64', TARGET: 'libs/unordered/test//cfoa_tests' } + tsan,
-        "g++-12-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 23.04 GCC 13 32/64 (03,11,14)",
-        "cppalliance/droneubuntu2304:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-13', CXXSTD: '03,11,14', ADDRMD: '32,64' },
-        "g++-13 g++-13-multilib",
-    ),
-
-    linux_pipeline(
-        "Linux 23.04 GCC 13 32/64 (17,20,2b)",
-        "cppalliance/droneubuntu2304:1",
-        { TOOLSET: 'gcc', COMPILER: 'g++-13', CXXSTD: '17,20,2b', ADDRMD: '32,64' },
-        "g++-13 g++-13-multilib",
-    ),
-
    linux_pipeline(
        "Linux 16.04 Clang 3.5",
        "cppalliance/droneubuntu1604:1",
@@ -420,40 +330,19 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
    ),

    linux_pipeline(
-        "Linux 22.04 Clang 14 UBSAN (03,11,14)",
+        "Linux 22.04 Clang 14 UBSAN",
        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '03,11,14' } + ubsan,
+        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '03,11,14,17,20' } + ubsan,
        "clang-14",
    ),

    linux_pipeline(
-        "Linux 22.04 Clang 14 UBSAN (17,20)",
+        "Linux 22.04 Clang 14 ASAN",
        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '17,20' } + ubsan,
+        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '03,11,14,17,20' } + asan,
        "clang-14",
    ),

-    linux_pipeline(
-        "Linux 22.04 Clang 14 ASAN (03,11,14)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '03,11,14' } + asan,
-        "clang-14",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 Clang 14 ASAN (17,20)",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-14', CXXSTD: '17,20' } + asan,
-        "clang-14",
-    ),
-
-    linux_pipeline(
-        "Linux 22.04 Clang 14 libc++ 64 TSAN",
-        "cppalliance/droneubuntu2204:1",
-        { TOOLSET: 'clang', COMPILER: 'clang++-14', ADDRMD: '64', TARGET: 'libs/unordered/test//cfoa_tests', CXXSTD: '11,14,17,20', STDLIB: 'libc++' } + tsan,
-        "clang-14 libc++-14-dev libc++abi-14-dev",
-    ),
-
    linux_pipeline(
        "Linux 22.04 Clang 15",
        "cppalliance/droneubuntu2204:1",
@@ -463,18 +352,8 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
    ),

    macos_pipeline(
-        "MacOS 10.15 Xcode 12.2 UBSAN (03,11)",
-        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '03,11' } + ubsan,
-    ),
-
-    macos_pipeline(
-        "MacOS 10.15 Xcode 12.2 UBSAN (14)",
-        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '14' } + ubsan,
-    ),
-
-    macos_pipeline(
-        "MacOS 10.15 Xcode 12.2 UBSAN (1z)",
-        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '1z' } + ubsan,
+        "MacOS 10.15 Xcode 12.2 UBSAN",
+        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '03,11,14,1z' } + ubsan,
    ),

    macos_pipeline(
@@ -483,12 +362,6 @@ local windows_pipeline(name, image, environment, arch = "amd64") =
        xcode_version = "13.4.1", osx_version = "monterey", arch = "arm64",
    ),

-    macos_pipeline(
-        "MacOS 12.4 Xcode 13.4.1 TSAN",
-        { TOOLSET: 'clang', COMPILER: 'clang++', CXXSTD: '11,14,1z', TARGET: 'libs/unordered/test//cfoa_tests' } + tsan,
-        xcode_version = "13.4.1", osx_version = "monterey", arch = "arm64",
-    ),
-
    windows_pipeline(
        "Windows VS2015 msvc-14.0",
        "cppalliance/dronevs2015",
@@ -7,8 +7,6 @@
 set -ex
 export PATH=~/.local/bin:/usr/local/bin:$PATH

-: ${TARGET:="libs/$LIBRARY/test"}
-
 DRONE_BUILD_DIR=$(pwd)

 BOOST_BRANCH=develop
@@ -24,4 +22,4 @@ python tools/boostdep/depinst/depinst.py $LIBRARY
 ./b2 -d0 headers

 echo "using $TOOLSET : : $COMPILER ;" > ~/user-config.jam
-./b2 -j3 $TARGET toolset=$TOOLSET cxxstd=$CXXSTD variant=debug,release ${ADDRMD:+address-model=$ADDRMD} ${STDLIB:+stdlib=$STDLIB} ${UBSAN:+undefined-sanitizer=norecover debug-symbols=on} ${ASAN:+address-sanitizer=norecover debug-symbols=on} ${TSAN:+thread-sanitizer=norecover debug-symbols=on} ${LINKFLAGS:+linkflags=$LINKFLAGS}
+./b2 -j3 libs/$LIBRARY/test toolset=$TOOLSET cxxstd=$CXXSTD variant=debug,release ${ADDRMD:+address-model=$ADDRMD} ${UBSAN:+undefined-sanitizer=norecover debug-symbols=on} ${ASAN:+address-sanitizer=norecover debug-symbols=on} ${LINKFLAGS:+linkflags=$LINKFLAGS}
@@ -52,10 +52,7 @@ jobs:
          - { name: "gcc-12 w/ sanitizers (17,20,2b)", sanitize: yes,
              compiler: gcc-12,    cxxstd: '17,20,2b',       os: ubuntu-22.04, ccache_key: "san2" }
          - { name: Collect coverage, coverage: yes,
-              compiler: gcc-12,     cxxstd: '03,20',          os: ubuntu-22.04, install: 'g++-12-multilib', address-model: '32,64', ccache_key: "cov" }
-
-          - { name: "cfoa tsan (gcc)", cxxstd: '11,14,17,20,2b', os: ubuntu-22.04, compiler: gcc-12,
-              targets: 'libs/unordered/test//cfoa_tests', thread-sanitize: yes }
+              compiler: gcc-8,     cxxstd: '03,11',          os: ubuntu-20.04, install: 'g++-8-multilib', address-model: '32,64', ccache_key: "cov" }

          # Linux, clang, libc++
          - { compiler: clang-7,   cxxstd: '03,11,14,17',       os: ubuntu-20.04, stdlib: libc++, install: 'clang-7 libc++-7-dev libc++abi-7-dev' }
@@ -68,21 +65,15 @@ jobs:
              compiler: clang-12,  cxxstd: '17,20,2b',          os: ubuntu-20.04, stdlib: libc++, install: 'clang-12 libc++-12-dev libc++abi-12-dev', ccache_key: "san2" }
          - { compiler: clang-13,  cxxstd: '03,11,14,17,20,2b', os: ubuntu-22.04, stdlib: libc++, install: 'clang-13 libc++-13-dev libc++abi-13-dev' }
          - { compiler: clang-14,  cxxstd: '03,11,14,17,20,2b', os: ubuntu-22.04, stdlib: libc++, install: 'clang-14 libc++-14-dev libc++abi-14-dev' }
-
          # not using libc++ because of https://github.com/llvm/llvm-project/issues/52771
          - { name: "clang-14 w/ sanitizers (03,11,14)", sanitize: yes,
              compiler: clang-14,  cxxstd: '03,11,14',          os: ubuntu-22.04, ccache_key: "san1" }
          - { name: "clang-14 w/ sanitizers (17,20,2b)", sanitize: yes,
              compiler: clang-14,  cxxstd: '17,20,2b',          os: ubuntu-22.04, ccache_key: "san2" }

-          - { name: "cfoa tsan (clang)", cxxstd: '11,14,17,20,2b', os: ubuntu-22.04, compiler: clang-14,
-              targets: 'libs/unordered/test//cfoa_tests', thread-sanitize: yes, 
-              stdlib: libc++, install: 'clang-14 libc++-14-dev libc++abi-14-dev' }
-
          # OSX, clang
          - { compiler: clang,     cxxstd: '03,11,14,17,2a',    os: macos-11, }
          - { compiler: clang,     cxxstd: '03,11,14,17,2a',    os: macos-12, sanitize: yes }
-          - { compiler: clang,     cxxstd: '11,14,17,2a',       os: macos-12, thread-sanitize: yes, targets: 'libs/unordered/test//cfoa_tests' }

    timeout-minutes: 180
    runs-on: ${{matrix.os}}
@@ -193,8 +184,6 @@ jobs:
          B2_COMPILER: ${{matrix.compiler}}
          B2_CXXSTD: ${{matrix.cxxstd}}
          B2_SANITIZE: ${{matrix.sanitize}}
-          B2_TSAN: ${{matrix.thread-sanitize}}
-          B2_TARGETS: ${{matrix.targets}}
          B2_STDLIB: ${{matrix.stdlib}}
          # More entries can be added in the same way, see the B2_ARGS assignment in ci/enforce.sh for the possible keys.
          # B2_DEFINES: ${{matrix.defines}}
@@ -208,7 +197,7 @@ jobs:

      - name: Run tests
        if: '!matrix.coverity'
-        run: B2_TARGETS=${{matrix.targets}} ci/build.sh
+        run: ci/build.sh

      - name: Upload coverage
        if: matrix.coverage
@@ -22,7 +22,6 @@ target_link_libraries(boost_unordered
    Boost::mp11
    Boost::predef
    Boost::preprocessor
-    Boost::static_assert
    Boost::throw_exception
    Boost::tuple
    Boost::type_traits
@@ -13,10 +13,8 @@
 include::unordered/intro.adoc[]
 include::unordered/buckets.adoc[]
 include::unordered/hash_equality.adoc[]
-include::unordered/regular.adoc[]
-include::unordered/concurrent.adoc[]
+include::unordered/comparison.adoc[]
 include::unordered/compliance.adoc[]
-include::unordered/structures.adoc[]
 include::unordered/benchmarks.adoc[]
 include::unordered/rationale.adoc[]
 include::unordered/ref.adoc[]
@@ -16,7 +16,7 @@ The successful lookup benchmarks are done by looking up all `n` values, in their

 The unsuccessful lookup benchmarks use `n` randomly generated integers but using a different seed value.

-=== GCC 12 + libstdc++-v3, x64
+=== GCC 11 + libstdc++-v3, x64

 ==== Insertion

@@ -102,7 +102,7 @@ max load factor 5

 |===

-=== Clang 15 + libc++, x64
+=== Clang 12 + libc++, x64

 ==== Insertion

@@ -190,7 +190,7 @@ max load factor 5

 |===

-=== Visual Studio 2022 + Dinkumware, x64
+=== Visual Studio 2019 + Dinkumware, x64

 ==== Insertion

@@ -431,263 +431,3 @@ h|unsuccessful lookup

 |===

-== boost::concurrent_flat_map
-
-All benchmarks were created using:
-
-* `https://spec.oneapi.io/versions/latest/elements/oneTBB/source/containers/concurrent_hash_map_cls.html[oneapi::tbb::concurrent_hash_map^]<int, int>`
-* `https://github.com/greg7mdp/gtl/blob/main/docs/phmap.md[gtl::parallel_flat_hash_map^]<int, int>` with 64 submaps
-* `boost::concurrent_flat_map<int, int>`
-
-The source code can be https://github.com/boostorg/boost_unordered_benchmarks/tree/boost_concurrent_flat_map[found here^].
-
-The benchmarks exercise a number of threads _T_ (between 1 and 16) concurrently performing operations
-randomly chosen among **update**, **successful lookup** and **unsuccessful lookup**. The keys used in the
-operations follow a https://en.wikipedia.org/wiki/Zipf%27s_law#Formal_definition[Zipf distribution^]
-with different _skew_ parameters: the higher the skew, the more concentrated are the keys in the lower values
-of the covered range.
-
-=== GCC 12, x64
-
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.500k%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.500k%2C%200.01.png]
-|image::benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.500k%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.500k%2C%200.5.png]
-|image::benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.500k%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.500k%2C%200.99.png]
-
-h|500k updates, 4.5M lookups +
-skew=0.01
-h|500k updates, 4.5M lookups +
-skew=0.5
-h|500k updates, 4.5M lookups +
-skew=0.99
-|===
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.5M%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.5M%2C%200.01.png]
-|image::benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.5M%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.5M%2C%200.5.png]
-|image::benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.5M%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x64/Parallel%20workload.xlsx.5M%2C%200.99.png]
-
-h|5M updates, 45M lookups +
-skew=0.01
-h|5M updates, 45M lookups +
-skew=0.5
-h|5M updates, 45M lookups +
-skew=0.99
-|===
-
-=== Clang 15, x64
-
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.500k%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.500k%2C%200.01.png]
-|image::benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.500k%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.500k%2C%200.5.png]
-|image::benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.500k%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.500k%2C%200.99.png]
-
-h|500k updates, 4.5M lookups +
-skew=0.01
-h|500k updates, 4.5M lookups +
-skew=0.5
-h|500k updates, 4.5M lookups +
-skew=0.99
-|===
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.5M%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.5M%2C%200.01.png]
-|image::benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.5M%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.5M%2C%200.5.png]
-|image::benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.5M%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x64/Parallel%20workload.xlsx.5M%2C%200.99.png]
-
-h|5M updates, 45M lookups +
-skew=0.01
-h|5M updates, 45M lookups +
-skew=0.5
-h|5M updates, 45M lookups +
-skew=0.99
-|===
-
-=== Visual Studio 2022, x64
-
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.500k%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.500k%2C%200.01.png]
-|image::benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.500k%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.500k%2C%200.5.png]
-|image::benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.500k%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.500k%2C%200.99.png]
-
-h|500k updates, 4.5M lookups +
-skew=0.01
-h|500k updates, 4.5M lookups +
-skew=0.5
-h|500k updates, 4.5M lookups +
-skew=0.99
-|===
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.5M%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.5M%2C%200.01.png]
-|image::benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.5M%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.5M%2C%200.5.png]
-|image::benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.5M%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x64/Parallel%20workload.xlsx.5M%2C%200.99.png]
-
-h|5M updates, 45M lookups +
-skew=0.01
-h|5M updates, 45M lookups +
-skew=0.5
-h|5M updates, 45M lookups +
-skew=0.99
-|===
-
-=== Clang 12, ARM64
-
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.500k%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.500k%2C%200.01.png]
-|image::benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.500k%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.500k%2C%200.5.png]
-|image::benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.500k%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.500k%2C%200.99.png]
-
-h|500k updates, 4.5M lookups +
-skew=0.01
-h|500k updates, 4.5M lookups +
-skew=0.5
-h|500k updates, 4.5M lookups +
-skew=0.99
-|===
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.5M%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.5M%2C%200.01.png]
-|image::benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.5M%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.5M%2C%200.5.png]
-|image::benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.5M%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-arm64/Parallel%20workload.xlsx.5M%2C%200.99.png]
-
-h|5M updates, 45M lookups +
-skew=0.01
-h|5M updates, 45M lookups +
-skew=0.5
-h|5M updates, 45M lookups +
-skew=0.99
-|===
-
-=== GCC 12, x86
-
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.500k%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.500k%2C%200.01.png]
-|image::benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.500k%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.500k%2C%200.5.png]
-|image::benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.500k%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.500k%2C%200.99.png]
-
-h|500k updates, 4.5M lookups +
-skew=0.01
-h|500k updates, 4.5M lookups +
-skew=0.5
-h|500k updates, 4.5M lookups +
-skew=0.99
-|===
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.5M%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.5M%2C%200.01.png]
-|image::benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.5M%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.5M%2C%200.5.png]
-|image::benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.5M%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/gcc-x86/Parallel%20workload.xlsx.5M%2C%200.99.png]
-
-h|5M updates, 45M lookups +
-skew=0.01
-h|5M updates, 45M lookups +
-skew=0.5
-h|5M updates, 45M lookups +
-skew=0.99
-|===
-
-=== Clang 15, x86
-
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.500k%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.500k%2C%200.01.png]
-|image::benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.500k%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.500k%2C%200.5.png]
-|image::benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.500k%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.500k%2C%200.99.png]
-
-h|500k updates, 4.5M lookups +
-skew=0.01
-h|500k updates, 4.5M lookups +
-skew=0.5
-h|500k updates, 4.5M lookups +
-skew=0.99
-|===
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.5M%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.5M%2C%200.01.png]
-|image::benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.5M%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.5M%2C%200.5.png]
-|image::benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.5M%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/clang-x86/Parallel%20workload.xlsx.5M%2C%200.99.png]
-
-h|5M updates, 45M lookups +
-skew=0.01
-h|5M updates, 45M lookups +
-skew=0.5
-h|5M updates, 45M lookups +
-skew=0.99
-|===
-
-=== Visual Studio 2022, x86
-
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.500k%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.500k%2C%200.01.png]
-|image::benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.500k%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.500k%2C%200.5.png]
-|image::benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.500k%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.500k%2C%200.99.png]
-
-h|500k updates, 4.5M lookups +
-skew=0.01
-h|500k updates, 4.5M lookups +
-skew=0.5
-h|500k updates, 4.5M lookups +
-skew=0.99
-|===
-
-[caption=]
-[cols="3*^.^a", frame=all, grid=all]
-|===
-
-|image::benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.5M%2C%200.01.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.5M%2C%200.01.png]
-|image::benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.5M%2C%200.5.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.5M%2C%200.5.png]
-|image::benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.5M%2C%200.99.png[width=250,window=_blank,link=../diagrams/benchmarks-concurrent_map/vs-x86/Parallel%20workload.xlsx.5M%2C%200.99.png]
-
-h|5M updates, 45M lookups +
-skew=0.01
-h|5M updates, 45M lookups +
-skew=0.5
-h|5M updates, 45M lookups +
-skew=0.99
-|===
@@ -2,9 +2,9 @@
 :idprefix: buckets_
 :imagesdir: ../diagrams

-= Basics of Hash Tables
+= The Data Structure

-The containers are made up of a number of _buckets_, each of which can contain
+The containers are made up of a number of 'buckets', each of which can contain
 any number of elements. For example, the following diagram shows a <<unordered_set,`boost::unordered_set`>> with 7 buckets containing 5 elements, `A`,
 `B`, `C`, `D` and `E` (this is just for illustration, containers will typically
 have more buckets).
@@ -12,7 +12,8 @@ have more buckets).
 image::buckets.png[]

 In order to decide which bucket to place an element in, the container applies
-the hash function, `Hash`, to the element's key (for sets the key is the whole element, but is referred to as the key
+the hash function, `Hash`, to the element's key (for `unordered_set` and
+`unordered_multiset` the key is the whole element, but is referred to as the key
 so that the same terminology can be used for sets and maps). This returns a
 value of type `std::size_t`. `std::size_t` has a much greater range of values
 then the number of buckets, so the container applies another transformation to
@@ -52,7 +53,8 @@ h|*Method* h|*Description*
 |`size_type bucket_count() const` 
 |The number of buckets.

-2+^h| *Closed-addressing containers only*
+2+^h| *Closed-addressing containers only* +
+`boost::unordered_[multi]set`, `boost::unordered_[multi]map` 
 h|*Method* h|*Description*

 |`size_type max_bucket_count() const` 
@@ -78,7 +80,7 @@ h|*Method* h|*Description*

 |===

-== Controlling the Number of Buckets
+== Controlling the number of buckets

 As more elements are added to an unordered associative container, the number
 of collisions will increase causing performance to degrade.
@@ -88,8 +90,8 @@ calling `rehash`.

 The standard leaves a lot of freedom to the implementer to decide how the
 number of buckets is chosen, but it does make some requirements based on the
-container's _load factor_, the number of elements divided by the number of buckets.
-Containers also have a _maximum load factor_ which they should try to keep the
+container's 'load factor', the number of elements divided by the number of buckets.
+Containers also have a 'maximum load factor' which they should try to keep the
 load factor below.

 You can't control the bucket count directly but there are two ways to
@@ -131,7 +133,9 @@ h|*Method* h|*Description*
 |`void rehash(size_type n)`
 |Changes the number of buckets so that there at least `n` buckets, and so that the load factor is less than the maximum load factor.

-2+^h| *Open-addressing and concurrent containers only*
+2+^h| *Open-addressing containers only* +
+`boost::unordered_flat_set`, `boost::unordered_flat_map` +
+`boost::unordered_node_set`, `boost::unordered_node_map` +
 h|*Method* h|*Description*

 |`size_type max_load() const`
@@ -139,7 +143,7 @@ h|*Method* h|*Description*

 |===

-A note on `max_load` for open-addressing and concurrent containers: the maximum load will be 
+A note on `max_load` for open-addressing containers: the maximum load will be 
 (`max_load_factor() * bucket_count()`) right after `rehash` or on container creation, but may
 slightly decrease when erasing elements in high-load situations. For instance, if we
 have a <<unordered_flat_map,`boost::unordered_flat_map`>> with `size()` almost
@@ -147,4 +151,165 @@ at `max_load()` level and then erase 1,000 elements, `max_load()` may decrease b
 few dozen elements. This is done internally by Boost.Unordered in order
 to keep its performance stable, and must be taken into account when planning for rehash-free insertions.

+== Iterator Invalidation

+It is not specified how member functions other than `rehash` and `reserve` affect
+the bucket count, although `insert` can only invalidate iterators
+when the insertion causes the container's load to be greater than the maximum allowed.
+For most implementations this means that `insert` will only
+change the number of buckets when this happens. Iterators can be
+invalidated by calls to `insert`, `rehash` and `reserve`.
+
+As for pointers and references,
+they are never invalidated for node-based containers 
+(`boost::unordered_[multi]set`, `boost::unordered_[multi]map`, `boost::unordered_node_set`, `boost::unordered_node_map`),
+but they will when rehashing occurs for
+`boost::unordered_flat_set` and `boost::unordered_flat_map`: this is because
+these containers store elements directly into their holding buckets, so
+when allocating a new bucket array the elements must be transferred by means of move construction.
+
+In a similar manner to using `reserve` for ``vector``s, it can be a good idea
+to call `reserve` before inserting a large number of elements. This will get
+the expensive rehashing out of the way and let you store iterators, safe in
+the knowledge that they won't be invalidated. If you are inserting `n`
+elements into container `x`, you could first call:
+
+```
+x.reserve(n);
+```
+
+Note:: `reserve(n)` reserves space for at least `n` elements, allocating enough buckets
+so as to not exceed the maximum load factor.
+
+Because the maximum load factor is defined as the number of elements divided by the total
+number of available buckets, this function is logically equivalent to:
+
+```
+x.rehash(std::ceil(n / x.max_load_factor()))
+```
+
+See the <<unordered_map_rehash,reference for more details>> on the `rehash` function.
+
+== Fast Closed Addressing Implementation
+
++++
+<style>
+  .imageblock > .title {
+    text-align: inherit;
+  }
+</style>
++++
+
+Boost.Unordered sports one of the fastest implementations of closed addressing, also commonly known as https://en.wikipedia.org/wiki/Hash_table#Separate_chaining[separate chaining]. An example figure representing the data structure is below:
+
+[#img-bucket-groups,.text-center]
+.A simple bucket group approach
+image::bucket-groups.png[align=center]
+
+An array of "buckets" is allocated and each bucket in turn points to its own individual linked list. This makes meeting the standard requirements of bucket iteration straight-forward. Unfortunately, iteration of the entire container is often times slow using this layout as each bucket must be examined for occupancy, yielding a time complexity of `O(bucket_count() + size())` when the standard requires complexity to be `O(size())`.
+
+Canonical standard implementations will wind up looking like the diagram below:
+
+[.text-center]
+.The canonical standard approach
+image::singly-linked.png[align=center,link=../diagrams/singly-linked.png,window=_blank]
+
+It's worth noting that this approach is only used by pass:[libc++] and pass:[libstdc++]; the MSVC Dinkumware implementation uses a different one. A more detailed analysis of the standard containers can be found http://bannalia.blogspot.com/2013/10/implementation-of-c-unordered.html[here].
+
+This unusually laid out data structure is chosen to make iteration of the entire container efficient by inter-connecting all of the nodes into a singly-linked list. One might also notice that buckets point to the node _before_ the start of the bucket's elements. This is done so that removing elements from the list can be done efficiently without introducing the need for a doubly-linked list. Unfortunately, this data structure introduces a guaranteed extra indirection. For example, to access the first element of a bucket, something like this must be done:
+
+```c++
+auto const idx = get_bucket_idx(hash_function(key));
+node* p = buckets[idx]; // first load
+node* n = p->next; // second load
+if (n && is_in_bucket(n, idx)) {
+  value_type const& v = *n; // third load
+  // ...
+}
+```
+
+With a simple bucket group layout, this is all that must be done:
+```c++
+auto const idx = get_bucket_idx(hash_function(key));
+node* n = buckets[idx]; // first load
+if (n) {
+  value_type const& v = *n; // second load
+  // ...
+}
+```
+
+In practice, the extra indirection can have a dramatic performance impact to common operations such as `insert`, `find` and `erase`. But to keep iteration of the container fast, Boost.Unordered introduces a novel data structure, a "bucket group". A bucket group is a fixed-width view of a subsection of the buckets array. It contains a bitmask (a `std::size_t`) which it uses to track occupancy of buckets and contains two pointers so that it can form a doubly-linked list with non-empty groups. An example diagram is below:
+
+[#img-fca-layout]
+.The new layout used by Boost
+image::fca.png[align=center]
+
+Thus container-wide iteration is turned into traversing the non-empty bucket groups (an operation with constant time complexity) which reduces the time complexity back to `O(size())`. In total, a bucket group is only 4 words in size and it views `sizeof(std::size_t) * CHAR_BIT` buckets meaning that for all common implementations, there's only 4 bits of space overhead per bucket introduced by the bucket groups.
+
+A more detailed description of Boost.Unordered's closed-addressing implementation is
+given in an
+https://bannalia.blogspot.com/2022/06/advancing-state-of-art-for.html[external article].
+For more information on implementation rationale, read the
+xref:#rationale_boostunordered_multiset_and_boostunordered_multimap[corresponding section].
+
+== Open Addressing Implementation
+
+The diagram shows the basic internal layout of `boost::unordered_flat_map`/`unordered_node_map` and
+`boost:unordered_flat_set`/`unordered_node_set`.
+
+
+[#img-foa-layout]
+.Open-addressing layout used by Boost.Unordered.
+image::foa.png[align=center]
+
+As with all open-addressing containers, elements (or pointers to the element nodes in the case of
+`boost::unordered_node_map` and `boost::unordered_node_set`) are stored directly in the bucket array.
+This array is logically divided into 2^_n_^ _groups_ of 15 elements each.
+In addition to the bucket array, there is an associated _metadata array_ with 2^_n_^
+16-byte words.
+
+[#img-foa-metadata]
+.Breakdown of a metadata word.
+image::foa-metadata.png[align=center]
+
+A metadata word is divided into 15 _h_~_i_~ bytes (one for each associated
+bucket), and an _overflow byte_ (_ofw_ in the diagram). The value of _h_~_i_~ is:
+
+  - 0 if the corresponding bucket is empty.
+  - 1 to encode a special empty bucket called a _sentinel_, which is used internally to
+  stop iteration when the container has been fully traversed.
+  - If the bucket is occupied, a _reduced hash value_ obtained from the hash value of
+  the element.
+
+When looking for an element with hash value _h_, SIMD technologies such as
+https://en.wikipedia.org/wiki/SSE2[SSE2] and
+https://en.wikipedia.org/wiki/ARM_architecture_family#Advanced_SIMD_(Neon)[Neon] allow us
+to very quickly inspect the full metadata word and look for the reduced value of _h_ among all the
+15 buckets with just a handful of CPU instructions: non-matching buckets can be
+readily discarded, and those whose reduced hash value matches need be inspected via full
+comparison with the corresponding element. If the looked-for element is not present,
+the overflow byte is inspected:
+
+- If the bit in the position _h_ mod 8 is zero, lookup terminates (and the
+element is not present).
+- If the bit is set to 1 (the group has been _overflowed_), further groups are
+checked using https://en.wikipedia.org/wiki/Quadratic_probing[_quadratic probing_], and
+the process is repeated.
+
+Insertion is algorithmically similar: empty buckets are located using SIMD,
+and when going past a full group its corresponding overflow bit is set to 1.
+
+In architectures without SIMD support, the logical layout stays the same, but the metadata
+word is codified using a technique we call _bit interleaving_: this layout allows us
+to emulate SIMD with reasonably good performance using only standard arithmetic and
+logical operations.
+
+[#img-foa-metadata-interleaving]
+.Bit-interleaved metadata word.
+image::foa-metadata-interleaving.png[align=center]
+
+A more detailed description of Boost.Unordered's open-addressing implementation is
+given in an
+https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html[external article].
+For more information on implementation rationale, read the
+xref:#rationale_boostunordered_flat_set_and_boostunordered_flat_map[corresponding section].
@@ -6,14 +6,9 @@
 :github-pr-url: https://github.com/boostorg/unordered/pull
 :cpp: C++

-== Release 1.83.0 - Major update
+== Release 1.83.0

-* Added `boost::concurrent_flat_map`, a fast, thread-safe hashmap based on open addressing.
 * Sped up iteration of open-addressing containers.
-* In open-addressing containers, `erase(iterator)`, which previously returned nothing, now
-returns a proxy object convertible to an iterator to the next element.
-This enables the typical `it = c.erase(it)` idiom without incurring any performance penalty
-when the returned proxy is not used.

 == Release 1.82.0 - Major update

@@ -1,99 +1,8 @@
-[#regular]
-= Regular Containers
-
-:idprefix: regular_
-
-Boost.Unordered closed-addressing containers (`boost::unordered_set`, `boost::unordered_map`,
-`boost::unordered_multiset` and `boost::unordered_multimap`) are fully conformant with the
-C++ specification for unordered associative containers, so for those who know how to use 
-`std::unordered_set`, `std::unordered_map`, etc., their homonyms in Boost.Unordered are
-drop-in replacements. The interface of open-addressing containers (`boost::unordered_node_set`, 
-`boost::unordered_node_map`, `boost::unordered_flat_set` and `boost::unordered_flat_map`)
-is very similar, but they present some minor differences listed in the dedicated
-xref:#compliance_open_addressing_containers[standard compliance section].
-
-
-For readers without previous experience with hash containers but familiar
-with normal associative containers (`std::set`, `std::map`,
-`std::multiset` and `std::multimap`), Boost.Unordered containers are used in a similar manner:
-
-[source,cpp]
----
-typedef boost::unordered_map<std::string, int> map;
-map x;
-x["one"] = 1;
-x["two"] = 2;
-x["three"] = 3;
-
-assert(x.at("one") == 1);
-assert(x.find("missing") == x.end());
----
-
-But since the elements aren't ordered, the output of:
-
-[source,c++]
----
-for(const map::value_type& i: x) {
-    std::cout<<i.first<<","<<i.second<<"\n";
-}
----
-
-can be in any order. For example, it might be:
-
-[source]
----
-two,2
-one,1
-three,3
----
-
-There are other differences, which are listed in the
-<<comparison,Comparison with Associative Containers>> section.
-
-== Iterator Invalidation
-
-It is not specified how member functions other than `rehash` and `reserve` affect
-the bucket count, although `insert` can only invalidate iterators
-when the insertion causes the container's load to be greater than the maximum allowed.
-For most implementations this means that `insert` will only
-change the number of buckets when this happens. Iterators can be
-invalidated by calls to `insert`, `rehash` and `reserve`.
-
-As for pointers and references,
-they are never invalidated for node-based containers 
-(`boost::unordered_[multi]set`, `boost::unordered_[multi]map`, `boost::unordered_node_set`, `boost::unordered_node_map`),
-but they will be when rehashing occurs for
-`boost::unordered_flat_set` and `boost::unordered_flat_map`: this is because
-these containers store elements directly into their holding buckets, so
-when allocating a new bucket array the elements must be transferred by means of move construction.
-
-In a similar manner to using `reserve` for ``vector``s, it can be a good idea
-to call `reserve` before inserting a large number of elements. This will get
-the expensive rehashing out of the way and let you store iterators, safe in
-the knowledge that they won't be invalidated. If you are inserting `n`
-elements into container `x`, you could first call:
-
-```
-x.reserve(n);
-```
-
-Note:: `reserve(n)` reserves space for at least `n` elements, allocating enough buckets
-so as to not exceed the maximum load factor.
-+
-Because the maximum load factor is defined as the number of elements divided by the total
-number of available buckets, this function is logically equivalent to:
-+
-```
-x.rehash(std::ceil(n / x.max_load_factor()))
-```
-+
-See the <<unordered_map_rehash,reference for more details>> on the `rehash` function.
-
 [#comparison]

 :idprefix: comparison_

-== Comparison with Associative Containers
+= Comparison with Associative Containers

 [caption=, title='Table {counter:table-counter} Interface differences']
 [cols="1,1", frame=all, grid=rows]
@@ -123,7 +32,7 @@ See the <<unordered_map_rehash,reference for more details>> on the `rehash` func
 |`iterator`, `const_iterator` are of at least the forward category.

 |Iterators, pointers and references to the container's elements are never invalidated.
-|<<regular_iterator_invalidation,Iterators can be invalidated by calls to insert or rehash>>. +
+|<<buckets_iterator_invalidation,Iterators can be invalidated by calls to insert or rehash>>. +
 **Node-based containers:** Pointers and references to the container's elements are never invalidated. +
 **Flat containers:** Pointers and references to the container's elements are invalidated when rehashing occurs.

@@ -5,7 +5,7 @@

 :cpp: C++

-== Closed-addressing Containers
+== Closed-addressing containers

 `unordered_[multi]set` and `unordered_[multi]map` are intended to provide a conformant
 implementation of the {cpp}20 standard that will work with {cpp}98 upwards.
@@ -13,7 +13,7 @@ This wide compatibility does mean some compromises have to be made.
 With a compiler and library that fully support {cpp}11, the differences should
 be minor.

-=== Move Emulation
+=== Move emulation

 Support for move semantics is implemented using Boost.Move. If rvalue
 references are available it will use them, but if not it uses a close,
@@ -25,7 +25,7 @@ but imperfect emulation. On such compilers:
 * The containers themselves are not movable.
 * Argument forwarding is not perfect.

-=== Use of Allocators
+=== Use of allocators

 {cpp}11 introduced a new allocator system. It's backwards compatible due to
 the lax requirements for allocators in the old standard, but might need
@@ -58,7 +58,7 @@ Due to imperfect move emulation, some assignments might check
 `propagate_on_container_copy_assignment` on some compilers and
 `propagate_on_container_move_assignment` on others.

-=== Construction/Destruction Using Allocators
+=== Construction/Destruction using allocators

 The following support is required for full use of {cpp}11 style
 construction/destruction:
@@ -117,7 +117,7 @@ Variadic constructor arguments for `emplace` are only used when both
 rvalue references and variadic template parameters are available.
 Otherwise `emplace` can only take up to 10 constructors arguments.

-== Open-addressing Containers
+== Open-addressing containers

 The C++ standard does not currently provide any open-addressing container
 specification to adhere to, so `boost::unordered_flat_set`/`unordered_node_set` and
@@ -135,9 +135,7 @@ The main differences with C++ unordered associative containers are:

 * In general:
  ** `begin()` is not constant-time.
-  ** `erase(iterator)` does not return an iterator to the following element, but
-     a proxy object that converts to that iterator if requested; this avoids
-     a potentially costly iterator increment operation when not needed.
+  ** `erase(iterator)` returns `void` instead of an iterator to the following element.
  ** There is no API for bucket handling (except `bucket_count`).
  ** The maximum load factor of the container is managed internally and can't be set by the user. The maximum load,
     exposed through the public function `max_load`, may decrease on erasure under high-load conditions.
@@ -146,61 +144,4 @@ The main differences with C++ unordered associative containers are:
  ** Pointer stability is not kept under rehashing.
  ** There is no API for node extraction/insertion.

-== Concurrent Containers
-
-There is currently no specification in the C++ standard for this or any other concurrent
-data structure. `boost::concurrent_flat_map` takes the same template parameters as `std::unordered_map`
-and all the maps provided by Boost.Unordered, and its API is modelled after that of
-`boost::unordered_flat_map` with the crucial difference that iterators are not provided
-due to their inherent problems in concurrent scenarios (high contention, prone to deadlocking):
-so, `boost::concurrent_flat_map` is technically not a
-https://en.cppreference.com/w/cpp/named_req/Container[Container^], although
-it meets all the requirements of https://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer[AllocatorAware^]
-containers except those implying iterators.
-
-In a non-concurrent unordered container, iterators serve two main purposes:
-
-* Access to an element previously located via lookup. 
-* Container traversal.
-
-In place of iterators, `boost::concurrent_flat_map` uses _internal visitation_
-facilities as a thread-safe substitute. Classical operations returning an iterator to an
-element already existing in the container, like for instance:
-
-[source,c++]
----
-iterator find(const key_type& k);
-std::pair<iterator, bool> insert(const value_type& obj);
----
-
-are transformed to accept a _visitation function_ that is passed such element:
-
-[source,c++]
----
-template<class F> size_t visit(const key_type& k, F f);
-template<class F> bool insert_or_visit(const value_type& obj, F f);
----
-
-(In the second case `f` is only invoked if there's an equivalent element
-to `obj` in the table, not if insertion is successful). Container traversal
-is served by:
-
-[source,c++]
----
-template<class F> size_t visit_all(F f);
----
-
-of which there are parallelized versions in C++17 compilers with parallel
-algorithm support. In general, the interface of `boost::concurrent_flat_map`
-is derived from that of `boost::unordered_flat_map` by a fairly straightforward
-process of replacing iterators with visitation where applicable. If
-`iterator` and `const_iterator` provide mutable and const access to elements,
-respectively, here visitation is granted mutable or const access depending on
-the constness of the member function used (there are also `*cvisit` overloads for
-explicit const visitation).
-
-The one notable operation not provided is `operator[]`/`at`, which can be
-replaced, if in a more convoluted manner, by
-xref:#concurrent_flat_map_try_emplace_or_cvisit[`try_emplace_or_visit`].
-
 //-
@@ -1,182 +0,0 @@
-[#concurrent]
-= Concurrent Containers
-
-:idprefix: concurrent_
-
-Boost.Unordered currently provides just one concurrent container named `boost::concurrent_flat_map`.
-`boost::concurrent_flat_map` is a hash table that allows concurrent write/read access from
-different threads without having to implement any synchronzation mechanism on the user's side.
-
-[source,c++]
----
-std::vector<int>                    input;
-boost::concurrent_flat_map<int,int> m;
-
-...
-
-// process input in parallel
-const int                 num_threads = 8;
-std::vector<std::jthread> threads;
-std::size_t               chunk = input.size() / num_threads; // how many elements per thread
-
-for (int i = 0; i < num_threads; ++i) {
-  threads.emplace_back([&,i] {
-    // calculate the portion of input this thread takes care of
-    std::size_t start = i * chunk;
-    std::size_t end = (i == num_threads - 1)? input.size(): (i + 1) * chunk;
-
-    for (std::size_t n = start; n < end; ++n) {
-      m.emplace(input[n], calculation(input[n]));
-    }
-  });
-}
----
-
-In the example above, threads access `m` without synchronization, just as we'd do in a
-single-threaded scenario. In an ideal setting, if a given workload is distributed among
-_N_ threads, execution is _N_ times faster than with one thread —this limit is
-never attained in practice due to synchronization overheads and _contention_ (one thread
-waiting for another to leave a locked portion of the map), but `boost::concurrent_flat_map`
-is designed to perform with very little overhead and typically achieves _linear scaling_
-(that is, performance is proportional to the number of threads up to the number of
-logical cores in the CPU).
-
-== Visitation-based API
-
-The first thing a new user of `boost::concurrent_flat_map` will notice is that this
-class _does not provide iterators_ (which makes it technically
-not a https://en.cppreference.com/w/cpp/named_req/Container[Container^]
-in the C++ standard sense). The reason for this is that iterators are inherently
-thread-unsafe. Consider this hypothetical code:
-
-[source,c++]
----
-auto it = m.find(k);  // A: get an iterator pointing to the element with key k
-if (it != m.end() ) {
-  some_function(*it); // B: use the value of the element
-}
----
-
-In a multithreaded scenario, the iterator `it` may be invalid at point B if some other
-thread issues an `m.erase(k)` operation between A and B. There are designs that
-can remedy this by making iterators lock the element they point to, but this
-approach lends itself to high contention and can easily produce deadlocks in a program.
-`operator[]` has similar concurrency issues, and is not provided by
-`boost::concurrent_flat_map` either. Instead, element access is done through
-so-called _visitation functions_:
-
-[source,c++]
----
-m.visit(k, [](const auto& x) { // x is the element with key k (if it exists)
-  some_function(x);            // use it
-});
----
-
-The visitation function passed by the user (in this case, a lambda function)
-is executed internally by `boost::concurrent_flat_map` in
-a thread-safe manner, so it can access the element without worrying about other
-threads interfering in the process.
-
-On the other hand, a visitation function can _not_ access the container itself:
-
-[source,c++]
----
-m.visit(k, [&](const auto& x) { 
-  some_function(x, m.size()); // forbidden: m can't be accessed inside visitation
-});
----
-
-Access to a different container is allowed, though:
-
-[source,c++]
----
-m.visit(k, [&](const auto& x) {
-  if (some_function(x)) {
-    m2.insert(x); // OK, m2 is a different boost::concurrent_flat_map
-  }
-});
----
-
-But, in general, visitation functions should be as lightweight as possible to
-reduce contention and increase parallelization. In some cases, moving heavy work
-outside of visitation may be beneficial:
-
-[source,c++]
----
-std::optional<value_type> o;
-bool found = m.visit(k, [&](const auto& x) { 
-  o = x;
-});
-if (found) {
-  some_heavy_duty_function(*o);
-}
----
-
-Visitation is prominent in the API provided by `boost::concurrent_flat_map`, and
-many classical operations have visitation-enabled variations:
-
-[source,c++]
----
-m.insert_or_visit(x, [](auto& y) { 
-  // if insertion failed because of an equivalent element y,
-  // do something with it, for instance:
-  ++y.second; // increment the mapped part of the element
-});
----
-
-Note that in this last example the visitation function could actually _modify_
-the element: as a general rule, operations on a `boost::concurrent_flat_map` `m`
-will grant visitation functions const/non-const access to  the element depending on whether
-`m` is const/non-const. Const access can be always be explicitly requested
-by using `cvisit` overloads (for instance, `insert_or_cvisit`) and may result
-in higher parallelization. Consult the xref:#concurrent_flat_map[reference]
-for a complete list of available operations.
-
-== Whole-Table Visitation
-
-In the absence of iterators, `boost::concurrent_flat_map` provides `visit_all`
-as an alternative way to process all the elements in the map:
-
-[source,c++]
----
-m.visit_all([](auto& x) {
-  x.second = 0; // reset the mapped part of the element
-});
----
-
-In C++17 compilers implementing standard parallel algorithms, whole-table
-visitation can be parallelized:
-
-[source,c++]
----
-m.visit_all(std::execution::par, [](auto& x) { // run in parallel
-  x.second = 0; // reset the mapped part of the element
-});
----
-
-There is another whole-table visitation operation, `erase_if`:
-
-[source,c++]
----
-m.erase_if([](auto& x) {
-  return x.second == 0; // erase the elements whose mapped value is zero
-});
----
-
-`erase_if` can also be parallelized. Note that, in order to increase efficiency,
-these operations do not block the table during execution: this implies that elements
-may be inserted, modified or erased by other threads during visitation. It is
-advisable not to assume too much about the exact global state of a `boost::concurrent_flat_map`
-at any point in your program.
-
-== Blocking Operations
-
-``boost::concurrent_flat_map``s can be copied, assigned, cleared and merged just like any
-Boost.Unordered container. Unlike most other operations, these are _blocking_,
-that is, all other threads are prevented from accesing the tables involved while a copy, assignment,
-clear or merge operation is in progress. Blocking is taken care of automatically by the library
-and the user need not take any special precaution, but overall performance may be affected.
-
-Another blocking operation is _rehashing_, which happens explicitly via `rehash`/`reserve`
-or during insertion when the table's load hits `max_load()`. As with non-concurrent containers,
-reserving space in advance of bulk insertions will generally speed up the process.
--- a/Show More
+++ b/Show More
Author	SHA1	Message	Date
Christian Mazakas	e8af8dcc7d	Simplify group14::overflow() implementation, update code to use group15 on non-SSE2 targets	2023-03-09 11:18:36 -08:00
Christian Mazakas	ef791cbafd	Update reserve_tests for new group layout	2023-03-08 15:34:15 -08:00
Christian Mazakas	b49fa571fb	Add group14 prototype	2023-03-08 15:34:06 -08:00