stylistic

added copy ctor for cache_aligned_size_control
fixed unqualified swap call
2026-08-06 13:44:12 +02:00 · 2023-06-09 13:58:34 +02:00 · 2023-06-09 11:39:39 +02:00 · 2023-06-09 11:04:09 +02:00 · 2023-06-09 11:03:38 +02:00 · 2023-06-09 10:03:39 +02:00
91 changed files with 588 additions and 1107 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

@@ -6,7 +6,7 @@ local library = "unordered";

 local triggers =
 {
-    branch: [ "master", "develop", "feature/*", "bugfix/*", "fix/*", "pr/*" ]
+    branch: [ "master", "develop", "bugfix/*", "fix/*", "pr/*" ]
 };

 local ubsan = { UBSAN: '1', UBSAN_OPTIONS: 'print_stacktrace=1' };
@@ -15,9 +15,9 @@ on:
      - master
      - develop
      - bugfix/**
-      - feature/**
      - fix/**
      - pr/**
+      - feature/cfoa-size-padding

 concurrency:
  group: ${{format('{0}:{1}', github.repository, github.ref)}}
@@ -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

@@ -10,10 +10,6 @@

 * 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

@@ -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.
@@ -132,7 +132,7 @@ 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
+== 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:
@@ -34,7 +34,7 @@ boost::unordered_set +
 boost::unordered_map +
 boost::unordered_multiset +
 boost::unordered_multimap
-^|
+^| N/A

 ^.^h|*Open addressing*
 ^m| boost::unordered_node_set + 
@@ -85,7 +85,7 @@ namespace boost {
 }
 ----

-Storing an object in an unordered associative container requires both a
+To store an object in an unordered associative container requires both a
 key equality function and a hash function. The default function objects in
 the standard containers support a few basic types including integer types,
 floating point types, pointer types, and the standard strings. Since
@@ -17,6 +17,7 @@ a number of aspects from that of `boost::unordered_flat_map`/`std::unordered_fla
  - `value_type` must be move-constructible. 
  - Pointer stability is not kept under rehashing.
  - `begin()` is not constant-time.
+  - `erase(iterator)` returns `void`.
  - There is no API for bucket handling (except `bucket_count`) or node extraction/insertion.
  - The maximum load factor of the container is managed internally and can't be set by the user.

@@ -154,9 +155,9 @@ namespace boost {
    template<class K, class M>
      iterator xref:#unordered_flat_map_insert_or_assign_with_hint[insert_or_assign](const_iterator hint, K&& k, M&& obj);

-    _convertible-to-iterator_     xref:#unordered_flat_map_erase_by_position[erase](iterator position);
-    _convertible-to-iterator_     xref:#unordered_flat_map_erase_by_position[erase](const_iterator position);
-    size_type                   xref:#unordered_flat_map_erase_by_key[erase](const key_type& k);
+    void      xref:#unordered_flat_map_erase_by_position[erase](iterator position);
+    void      xref:#unordered_flat_map_erase_by_position[erase](const_iterator position);
+    size_type xref:#unordered_flat_map_erase_by_key[erase](const key_type& k);
    template<class K> size_type xref:#unordered_flat_map_erase_by_key[erase](K&& k);
    iterator  xref:#unordered_flat_map_erase_range[erase](const_iterator first, const_iterator last);
    void      xref:#unordered_flat_map_swap[swap](unordered_flat_map& other)
@@ -1034,19 +1035,15 @@ The `template<class K, class M>` only participates in overload resolution if `Ha

 ==== Erase by Position

-[source,c++,subs=+quotes]
----
-_convertible-to-iterator_ erase(iterator position);
-_convertible-to-iterator_ erase(const_iterator position);
----
+```c++
+void erase(iterator position);
+void erase(const_iterator position);
+```

 Erase the element pointed to by `position`.

 [horizontal]
-Returns:;; An opaque object implicitly convertible to the `iterator` or `const_iterator`
-immediately following `position` prior to the erasure.
 Throws:;; Nothing.
-Notes:;; The opaque object returned must only be discarded or immediately converted to `iterator` or `const_iterator`.

 ---

@@ -17,6 +17,7 @@ a number of aspects from that of `boost::unordered_flat_set`/`std::unordered_fla
  - `value_type` must be move-constructible. 
  - Pointer stability is not kept under rehashing.
  - `begin()` is not constant-time.
+  - `erase(iterator)` returns `void`.
  - There is no API for bucket handling (except `bucket_count`) or node extraction/insertion.
  - The maximum load factor of the container is managed internally and can't be set by the user.

@@ -122,9 +123,9 @@ namespace boost {
    template<class InputIterator> void xref:#unordered_flat_set_insert_iterator_range[insert](InputIterator first, InputIterator last);
    void xref:#unordered_flat_set_insert_initializer_list[insert](std::initializer_list<value_type>);

-    _convertible-to-iterator_     xref:#unordered_flat_set_erase_by_position[erase](iterator position);
-    _convertible-to-iterator_     xref:#unordered_flat_set_erase_by_position[erase](const_iterator position);
-    size_type                   xref:#unordered_flat_set_erase_by_key[erase](const key_type& k);
+    void      xref:#unordered_flat_set_erase_by_position[erase](iterator position);
+    void      xref:#unordered_flat_set_erase_by_position[erase](const_iterator position);
+    size_type xref:#unordered_flat_set_erase_by_key[erase](const key_type& k);
    template<class K> size_type xref:#unordered_flat_set_erase_by_key[erase](K&& k);
    iterator  xref:#unordered_flat_set_erase_range[erase](const_iterator first, const_iterator last);
    void      xref:#unordered_flat_set_swap[swap](unordered_flat_set& other)
@@ -845,19 +846,15 @@ Notes:;; Can invalidate iterators, pointers and references, but only if the inse

 ==== Erase by Position

-[source,c++,subs=+quotes]
----
-_convertible-to-iterator_ erase(iterator position);
-_convertible-to-iterator_ erase(const_iterator position);
----
+```c++
+void erase(iterator position);
+void erase(const_iterator position);
+```

 Erase the element pointed to by `position`.

 [horizontal]
-Returns:;; An opaque object implicitly convertible to the `iterator` or `const_iterator`
-immediately following `position` prior to the erasure.
 Throws:;; Nothing.
-Notes:;; The opaque object returned must only be discarded or immediately converted to `iterator` or `const_iterator`.

 ---

@@ -13,6 +13,7 @@ As a result of its using open addressing, the interface of `boost::unordered_nod
 a number of aspects from that of `boost::unordered_map`/`std::unordered_map`: 

  - `begin()` is not constant-time.
+  - `erase(iterator)` returns `void`.
  - 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.

@@ -155,9 +156,9 @@ namespace boost {
    template<class K, class M>
      iterator xref:#unordered_node_map_insert_or_assign_with_hint[insert_or_assign](const_iterator hint, K&& k, M&& obj);

-    _convertible-to-iterator_     xref:#unordered_node_map_erase_by_position[erase](iterator position);
-    _convertible-to-iterator_     xref:#unordered_node_map_erase_by_position[erase](const_iterator position);
-    size_type                   xref:#unordered_node_map_erase_by_key[erase](const key_type& k);
+    void      xref:#unordered_node_map_erase_by_position[erase](iterator position);
+    void      xref:#unordered_node_map_erase_by_position[erase](const_iterator position);
+    size_type xref:#unordered_node_map_erase_by_key[erase](const key_type& k);
    template<class K> size_type xref:#unordered_node_map_erase_by_key[erase](K&& k);
    iterator  xref:#unordered_node_map_erase_range[erase](const_iterator first, const_iterator last);
    void      xref:#unordered_node_map_swap[swap](unordered_node_map& other)
@@ -1104,19 +1105,15 @@ The `template<class K, class M>` only participates in overload resolution if `Ha

 ==== Erase by Position

-[source,c++,subs=+quotes]
----
-_convertible-to-iterator_ erase(iterator position);
-_convertible-to-iterator_ erase(const_iterator position);
----
+```c++
+void erase(iterator position);
+void erase(const_iterator position);
+```

 Erase the element pointed to by `position`.

 [horizontal]
-Returns:;; An opaque object implicitly convertible to the `iterator` or `const_iterator`
-immediately following `position` prior to the erasure.
 Throws:;; Nothing.
-Notes:;; The opaque object returned must only be discarded or immediately converted to `iterator` or `const_iterator`.

 ---

@@ -13,6 +13,7 @@ As a result of its using open addressing, the interface of `boost::unordered_nod
 a number of aspects from that of `boost::unordered_set`/`std::unordered_set`: 

  - `begin()` is not constant-time.
+  - `erase(iterator)` returns `void`.
  - 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.

@@ -123,9 +124,9 @@ namespace boost {
    insert_return_type xref:#unordered_node_set_insert_node[insert](node_type&& nh);
    iterator xref:#unordered_node_set_insert_node_with_hint[insert](const_iterator hint, node_type&& nh);

-    _convertible-to-iterator_     xref:#unordered_node_set_erase_by_position[erase](iterator position);
-    _convertible-to-iterator_     xref:#unordered_node_set_erase_by_position[erase](const_iterator position);
-    size_type                   xref:#unordered_node_set_erase_by_key[erase](const key_type& k);
+    void      xref:#unordered_node_set_erase_by_position[erase](iterator position);
+    void      xref:#unordered_node_set_erase_by_position[erase](const_iterator position);
+    size_type xref:#unordered_node_set_erase_by_key[erase](const key_type& k);
    template<class K> size_type xref:#unordered_node_set_erase_by_key[erase](K&& k);
    iterator  xref:#unordered_node_set_erase_range[erase](const_iterator first, const_iterator last);
    void      xref:#unordered_node_set_swap[swap](unordered_node_set& other)
@@ -918,19 +919,15 @@ Notes:;; Behavior is undefined if `nh` is not empty and the allocators of `nh` a

 ==== Erase by Position

-[source,c++,subs=+quotes]
----
-_convertible-to-iterator_ erase(iterator position);
-_convertible-to-iterator_ erase(const_iterator position);
----
+```c++
+void erase(iterator position);
+void erase(const_iterator position);
+```

 Erase the element pointed to by `position`.

 [horizontal]
-Returns:;; An opaque object implicitly convertible to the `iterator` or `const_iterator`
-immediately following `position` prior to the erasure.
 Throws:;; Nothing.
-Notes:;; The opaque object returned must only be discarded or immediately converted to `iterator` or `const_iterator`.

 ---

@@ -8,12 +8,15 @@
 * See https://www.boost.org/libs/unordered for library home page.
 */

+/* Reference:
+ * https://github.com/joaquintides/concurrent_hashmap_api#proposed-synopsis
+ */
+
 #ifndef BOOST_UNORDERED_CONCURRENT_FLAT_MAP_HPP
 #define BOOST_UNORDERED_CONCURRENT_FLAT_MAP_HPP

 #include <boost/unordered/concurrent_flat_map_fwd.hpp>
 #include <boost/unordered/detail/foa/concurrent_table.hpp>
-#include <boost/unordered/detail/foa/flat_map_types.hpp>
 #include <boost/unordered/detail/type_traits.hpp>

 #include <boost/container_hash/hash.hpp>
@@ -28,12 +31,12 @@

 #define BOOST_UNORDERED_STATIC_ASSERT_INVOCABLE(F)                             \
  static_assert(boost::unordered::detail::is_invocable<F, value_type&>::value, \
-    "The provided Callable must be invocable with value_type&");
+    "The provided Callable must be invocable with `value_type&`");

 #define BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)                       \
  static_assert(                                                               \
    boost::unordered::detail::is_invocable<F, value_type const&>::value,       \
-    "The provided Callable must be invocable with value_type const&");
+    "The provided Callable must be invocable with `value_type const&`");

 #if BOOST_CXX_VERSION >= 202002L

@@ -68,6 +71,7 @@
 namespace boost {
  namespace unordered {
    namespace detail {
+
      template <class F, class... Args>
      struct is_invocable
          : std::is_constructible<std::function<void(Args...)>,
@@ -75,6 +79,60 @@ namespace boost {
      {
      };

+      template <class Key, class T> struct concurrent_map_types
+      {
+        using key_type = Key;
+        using raw_key_type = typename std::remove_const<Key>::type;
+        using raw_mapped_type = typename std::remove_const<T>::type;
+
+        using init_type = std::pair<raw_key_type, raw_mapped_type>;
+        using moved_type = std::pair<raw_key_type&&, raw_mapped_type&&>;
+        using value_type = std::pair<Key const, T>;
+
+        using element_type = value_type;
+
+        static value_type& value_from(element_type& x) { return x; }
+
+        template <class K, class V>
+        static raw_key_type const& extract(std::pair<K, V> const& kv)
+        {
+          return kv.first;
+        }
+
+        static moved_type move(init_type& x)
+        {
+          return {std::move(x.first), std::move(x.second)};
+        }
+
+        static moved_type move(element_type& x)
+        {
+          // TODO: we probably need to launder here
+          return {std::move(const_cast<raw_key_type&>(x.first)),
+            std::move(const_cast<raw_mapped_type&>(x.second))};
+        }
+
+        template <class A, class... Args>
+        static void construct(A& al, init_type* p, Args&&... args)
+        {
+          boost::allocator_construct(al, p, std::forward<Args>(args)...);
+        }
+
+        template <class A, class... Args>
+        static void construct(A& al, value_type* p, Args&&... args)
+        {
+          boost::allocator_construct(al, p, std::forward<Args>(args)...);
+        }
+
+        template <class A> static void destroy(A& al, init_type* p) noexcept
+        {
+          boost::allocator_destroy(al, p);
+        }
+
+        template <class A> static void destroy(A& al, value_type* p) noexcept
+        {
+          boost::allocator_destroy(al, p);
+        }
+      };
    } // namespace detail

    template <class Key, class T, class Hash, class Pred, class Allocator>
@@ -85,7 +143,7 @@ namespace boost {
        class Allocator2>
      friend class concurrent_flat_map;

-      using type_policy = detail::foa::flat_map_types<Key, T>;
+      using type_policy = detail::concurrent_map_types<Key, T>;

      detail::foa::concurrent_table<type_policy, Hash, Pred, Allocator> table_;

@@ -93,10 +151,6 @@ namespace boost {
      bool friend operator==(concurrent_flat_map<K, V, H, KE, A> const& lhs,
        concurrent_flat_map<K, V, H, KE, A> const& rhs);

-      template <class K, class V, class H, class KE, class A, class Predicate>
-      friend typename concurrent_flat_map<K, V, H, KE, A>::size_type erase_if(
-        concurrent_flat_map<K, V, H, KE, A>& set, Predicate pred);
-
    public:
      using key_type = Key;
      using mapped_type = T;
@@ -148,24 +202,22 @@ namespace boost {
      }

      template <class InputIterator>
-      concurrent_flat_map(
-        InputIterator f, InputIterator l, allocator_type const& a)
+      concurrent_flat_map(InputIterator f, InputIterator l, allocator_type a)
          : concurrent_flat_map(f, l, 0, hasher(), key_equal(), a)
      {
      }

-      explicit concurrent_flat_map(allocator_type const& a)
+      explicit concurrent_flat_map(allocator_type a)
          : table_(detail::foa::default_bucket_count, hasher(), key_equal(), a)
      {
      }

-      concurrent_flat_map(
-        concurrent_flat_map const& rhs, allocator_type const& a)
+      concurrent_flat_map(concurrent_flat_map const& rhs, allocator_type a)
          : table_(rhs.table_, a)
      {
      }

-      concurrent_flat_map(concurrent_flat_map&& rhs, allocator_type const& a)
+      concurrent_flat_map(concurrent_flat_map&& rhs, allocator_type a)
          : table_(std::move(rhs.table_), a)
      {
      }
@@ -250,7 +302,6 @@ namespace boost {
      ///

      size_type size() const noexcept { return table_.size(); }
-      size_type max_size() const noexcept { return table_.max_size(); }

      BOOST_ATTRIBUTE_NODISCARD bool empty() const noexcept
      {
@@ -374,7 +425,7 @@ namespace boost {
      void insert(InputIterator begin, InputIterator end)
      {
        for (auto pos = begin; pos != end; ++pos) {
-          table_.emplace(*pos);
+          table_.insert(*pos);
        }
      }

@@ -426,7 +477,7 @@ namespace boost {
      {
        BOOST_UNORDERED_STATIC_ASSERT_INVOCABLE(F)
        for (; first != last; ++first) {
-          table_.emplace_or_visit(*first, f);
+          table_.insert_or_visit(*first, f);
        }
      }

@@ -457,7 +508,7 @@ namespace boost {
      {
        BOOST_UNORDERED_STATIC_ASSERT_CONST_INVOCABLE(F)
        for (; first != last; ++first) {
-          table_.emplace_or_cvisit(*first, f);
+          table_.insert_or_cvisit(*first, f);
        }
      }

@@ -708,7 +759,7 @@ namespace boost {
    typename concurrent_flat_map<K, T, H, P, A>::size_type erase_if(
      concurrent_flat_map<K, T, H, P, A>& c, Predicate pred)
    {
-      return c.table_.erase_if(pred);
+      return c.erase_if(pred);
    }

 #if BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES
@@ -8,6 +8,10 @@
 * See https://www.boost.org/libs/unordered for library home page.
 */

+/* Reference:
+ * https://github.com/joaquintides/concurrent_hashmap_api#proposed-synopsis
+ */
+
 #ifndef BOOST_UNORDERED_CONCURRENT_FLAT_MAP_FWD_HPP
 #define BOOST_UNORDERED_CONCURRENT_FLAT_MAP_FWD_HPP

@@ -1293,7 +1293,7 @@ public:
    hash_base{empty_init,std::move(x.h())},
    pred_base{empty_init,std::move(x.pred())},
    allocator_base{empty_init,std::move(x.al())},
-    arrays(x.arrays),size_ctrl(x.size_ctrl)
+    arrays(x.arrays),size_ctrl{x.size_ctrl}
  {
    x.arrays=x.new_arrays(0);
    x.size_ctrl.ml=x.initial_max_load();
@@ -1,73 +0,0 @@
-// Copyright (C) 2023 Christian Mazakas
-// 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)
-
-#ifndef BOOST_UNORDERED_DETAIL_FOA_FLAT_MAP_TYPES_HPP
-#define BOOST_UNORDERED_DETAIL_FOA_FLAT_MAP_TYPES_HPP
-
-#include <boost/core/allocator_access.hpp>
-
-namespace boost {
-  namespace unordered {
-    namespace detail {
-      namespace foa {
-        template <class Key, class T> struct flat_map_types
-        {
-          using key_type = Key;
-          using raw_key_type = typename std::remove_const<Key>::type;
-          using raw_mapped_type = typename std::remove_const<T>::type;
-
-          using init_type = std::pair<raw_key_type, raw_mapped_type>;
-          using moved_type = std::pair<raw_key_type&&, raw_mapped_type&&>;
-          using value_type = std::pair<Key const, T>;
-
-          using element_type = value_type;
-
-          static value_type& value_from(element_type& x) { return x; }
-
-          template <class K, class V>
-          static raw_key_type const& extract(std::pair<K, V> const& kv)
-          {
-            return kv.first;
-          }
-
-          static moved_type move(init_type& x)
-          {
-            return {std::move(x.first), std::move(x.second)};
-          }
-
-          static moved_type move(element_type& x)
-          {
-            // TODO: we probably need to launder here
-            return {std::move(const_cast<raw_key_type&>(x.first)),
-              std::move(const_cast<raw_mapped_type&>(x.second))};
-          }
-
-          template <class A, class... Args>
-          static void construct(A& al, init_type* p, Args&&... args)
-          {
-            boost::allocator_construct(al, p, std::forward<Args>(args)...);
-          }
-
-          template <class A, class... Args>
-          static void construct(A& al, value_type* p, Args&&... args)
-          {
-            boost::allocator_construct(al, p, std::forward<Args>(args)...);
-          }
-
-          template <class A> static void destroy(A& al, init_type* p) noexcept
-          {
-            boost::allocator_destroy(al, p);
-          }
-
-          template <class A> static void destroy(A& al, value_type* p) noexcept
-          {
-            boost::allocator_destroy(al, p);
-          }
-        };
-      } // namespace foa
-    }   // namespace detail
-  }     // namespace unordered
-} // namespace boost
-
-#endif // BOOST_UNORDERED_DETAIL_FOA_FLAT_MAP_TYPES_HPP
@@ -1,44 +0,0 @@
-// Copyright (C) 2023 Christian Mazakas
-// 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)
-
-#ifndef BOOST_UNORDERED_DETAIL_FOA_FLAT_SET_TYPES_HPP
-#define BOOST_UNORDERED_DETAIL_FOA_FLAT_SET_TYPES_HPP
-
-#include <boost/core/allocator_access.hpp>
-
-namespace boost {
-  namespace unordered {
-    namespace detail {
-      namespace foa {
-        template <class Key> struct flat_set_types
-        {
-          using key_type = Key;
-          using init_type = Key;
-          using value_type = Key;
-
-          static Key const& extract(value_type const& key) { return key; }
-
-          using element_type = value_type;
-
-          static Key& value_from(element_type& x) { return x; }
-
-          static element_type&& move(element_type& x) { return std::move(x); }
-
-          template <class A, class... Args>
-          static void construct(A& al, value_type* p, Args&&... args)
-          {
-            boost::allocator_construct(al, p, std::forward<Args>(args)...);
-          }
-
-          template <class A> static void destroy(A& al, value_type* p) noexcept
-          {
-            boost::allocator_destroy(al, p);
-          }
-        };
-      } // namespace foa
-    }   // namespace detail
-  }     // namespace unordered
-} // namespace boost
-
-#endif // BOOST_UNORDERED_DETAIL_FOA_FLAT_SET_TYPES_HPP
@@ -1,131 +0,0 @@
-// Copyright (C) 2023 Christian Mazakas
-// 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)
-
-#ifndef BOOST_UNORDERED_DETAIL_FOA_NODE_MAP_TYPES_HPP
-#define BOOST_UNORDERED_DETAIL_FOA_NODE_MAP_TYPES_HPP
-
-#include <boost/core/allocator_access.hpp>
-#include <boost/core/pointer_traits.hpp>
-
-namespace boost {
-  namespace unordered {
-    namespace detail {
-      namespace foa {
-        template <class Key, class T> struct node_map_types
-        {
-          using key_type = Key;
-          using mapped_type = T;
-          using raw_key_type = typename std::remove_const<Key>::type;
-          using raw_mapped_type = typename std::remove_const<T>::type;
-
-          using init_type = std::pair<raw_key_type, raw_mapped_type>;
-          using value_type = std::pair<Key const, T>;
-          using moved_type = std::pair<raw_key_type&&, raw_mapped_type&&>;
-
-          using element_type = foa::element_type<value_type>;
-
-          static value_type& value_from(element_type const& x)
-          {
-            return *(x.p);
-          }
-
-          template <class K, class V>
-          static raw_key_type const& extract(std::pair<K, V> const& kv)
-          {
-            return kv.first;
-          }
-
-          static raw_key_type const& extract(element_type const& kv)
-          {
-            return kv.p->first;
-          }
-
-          static element_type&& move(element_type& x) { return std::move(x); }
-          static moved_type move(init_type& x)
-          {
-            return {std::move(x.first), std::move(x.second)};
-          }
-
-          static moved_type move(value_type& x)
-          {
-            return {std::move(const_cast<raw_key_type&>(x.first)),
-              std::move(const_cast<raw_mapped_type&>(x.second))};
-          }
-
-          template <class A>
-          static void construct(A&, element_type* p, element_type&& x) noexcept
-          {
-            p->p = x.p;
-            x.p = nullptr;
-          }
-
-          template <class A>
-          static void construct(
-            A& al, element_type* p, element_type const& copy)
-          {
-            construct(al, p, *copy.p);
-          }
-
-          template <class A, class... Args>
-          static void construct(A& al, init_type* p, Args&&... args)
-          {
-            boost::allocator_construct(al, p, std::forward<Args>(args)...);
-          }
-
-          template <class A, class... Args>
-          static void construct(A& al, value_type* p, Args&&... args)
-          {
-            boost::allocator_construct(al, p, std::forward<Args>(args)...);
-          }
-
-          template <class A, class... Args>
-          static void construct(A& al, element_type* p, Args&&... args)
-          {
-            p->p = boost::to_address(boost::allocator_allocate(al, 1));
-            BOOST_TRY
-            {
-              boost::allocator_construct(al, p->p, std::forward<Args>(args)...);
-            }
-            BOOST_CATCH(...)
-            {
-              using pointer_type = typename boost::allocator_pointer<A>::type;
-              using pointer_traits = boost::pointer_traits<pointer_type>;
-
-              boost::allocator_deallocate(
-                al, pointer_traits::pointer_to(*(p->p)), 1);
-              BOOST_RETHROW
-            }
-            BOOST_CATCH_END
-          }
-
-          template <class A> static void destroy(A& al, value_type* p) noexcept
-          {
-            boost::allocator_destroy(al, p);
-          }
-
-          template <class A> static void destroy(A& al, init_type* p) noexcept
-          {
-            boost::allocator_destroy(al, p);
-          }
-
-          template <class A>
-          static void destroy(A& al, element_type* p) noexcept
-          {
-            if (p->p) {
-              using pointer_type = typename boost::allocator_pointer<A>::type;
-              using pointer_traits = boost::pointer_traits<pointer_type>;
-
-              destroy(al, p->p);
-              boost::allocator_deallocate(
-                al, pointer_traits::pointer_to(*(p->p)), 1);
-            }
-          }
-        };
-
-      } // namespace foa
-    }   // namespace detail
-  }     // namespace unordered
-} // namespace boost
-
-#endif // BOOST_UNORDERED_DETAIL_FOA_NODE_MAP_TYPES_HPP
@@ -1,94 +0,0 @@
-// Copyright (C) 2023 Christian Mazakas
-// 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)
-
-#ifndef BOOST_UNORDERED_DETAIL_FOA_NODE_SET_TYPES_HPP
-#define BOOST_UNORDERED_DETAIL_FOA_NODE_SET_TYPES_HPP
-
-#include <boost/core/allocator_access.hpp>
-#include <boost/core/pointer_traits.hpp>
-
-namespace boost {
-  namespace unordered {
-    namespace detail {
-      namespace foa {
-
-        template <class Key> struct node_set_types
-        {
-          using key_type = Key;
-          using init_type = Key;
-          using value_type = Key;
-
-          static Key const& extract(value_type const& key) { return key; }
-
-          using element_type = foa::element_type<value_type>;
-
-          static value_type& value_from(element_type const& x) { return *x.p; }
-          static Key const& extract(element_type const& k) { return *k.p; }
-          static element_type&& move(element_type& x) { return std::move(x); }
-          static value_type&& move(value_type& x) { return std::move(x); }
-
-          template <class A>
-          static void construct(
-            A& al, element_type* p, element_type const& copy)
-          {
-            construct(al, p, *copy.p);
-          }
-
-          template <typename Allocator>
-          static void construct(
-            Allocator&, element_type* p, element_type&& x) noexcept
-          {
-            p->p = x.p;
-            x.p = nullptr;
-          }
-
-          template <class A, class... Args>
-          static void construct(A& al, value_type* p, Args&&... args)
-          {
-            boost::allocator_construct(al, p, std::forward<Args>(args)...);
-          }
-
-          template <class A, class... Args>
-          static void construct(A& al, element_type* p, Args&&... args)
-          {
-            p->p = boost::to_address(boost::allocator_allocate(al, 1));
-            BOOST_TRY
-            {
-              boost::allocator_construct(al, p->p, std::forward<Args>(args)...);
-            }
-            BOOST_CATCH(...)
-            {
-              boost::allocator_deallocate(al,
-                boost::pointer_traits<typename boost::allocator_pointer<
-                  A>::type>::pointer_to(*p->p),
-                1);
-              BOOST_RETHROW
-            }
-            BOOST_CATCH_END
-          }
-
-          template <class A> static void destroy(A& al, value_type* p) noexcept
-          {
-            boost::allocator_destroy(al, p);
-          }
-
-          template <class A>
-          static void destroy(A& al, element_type* p) noexcept
-          {
-            if (p->p) {
-              destroy(al, p->p);
-              boost::allocator_deallocate(al,
-                boost::pointer_traits<typename boost::allocator_pointer<
-                  A>::type>::pointer_to(*(p->p)),
-                1);
-            }
-          }
-        };
-
-      } // namespace foa
-    }   // namespace detail
-  }     // namespace unordered
-} // namespace boost
-
-#endif // BOOST_UNORDERED_DETAIL_FOA_NODE_SET_TYPES_HPP
@@ -30,44 +30,8 @@ private:

 private:

-    // Effects: Provides a hint to the implementation that the current thread
-    //          has been unable to make progress for k+1 iterations.
-
-    static void yield( unsigned k ) noexcept
-    {
-        unsigned const sleep_every = 1024; // see below
-
-        k %= sleep_every;
-
-        if( k < 5 )
-        {
-            // Intel recommendation from the Optimization Reference Manual
-            // Exponentially increase number of PAUSE instructions each
-            // iteration until reaching a maximum which is approximately
-            // one timeslice long (2^4 == 16 in our case)
-
-            unsigned const pause_count = 1u << k;
-
-            for( unsigned i = 0; i < pause_count; ++i )
-            {
-                boost::core::sp_thread_pause();
-            }
-        }
-        else if( k < sleep_every - 1 )
-        {
-            // Once the maximum number of PAUSE instructions is reached,
-            // we switch to yielding the timeslice immediately
-
-            boost::core::sp_thread_yield();
-        }
-        else
-        {
-            // After `sleep_every` iterations of no progress, we sleep,
-            // to avoid a deadlock if a lower priority thread has the lock
-
-            boost::core::sp_thread_sleep();
-        }
-    }
+    // number of times to spin before sleeping
+    static constexpr int spin_count = 24576;

 public:

@@ -87,17 +51,22 @@ public:

    void lock_shared() noexcept
    {
-        for( unsigned k = 0; ; ++k )
+        for( ;; )
        {
-            std::uint32_t st = state_.load( std::memory_order_relaxed );
-
-            if( st < reader_lock_count_mask )
+            for( int k = 0; k < spin_count; ++k )
            {
-                std::uint32_t newst = st + 1;
-                if( state_.compare_exchange_weak( st, newst, std::memory_order_acquire, std::memory_order_relaxed ) ) return;
+                std::uint32_t st = state_.load( std::memory_order_relaxed );
+
+                if( st < reader_lock_count_mask )
+                {
+                    std::uint32_t newst = st + 1;
+                    if( state_.compare_exchange_weak( st, newst, std::memory_order_acquire, std::memory_order_relaxed ) ) return;
+                }
+
+                boost::core::sp_thread_pause();
            }

-            yield( k );
+            boost::core::sp_thread_sleep();
        }
    }

@@ -133,34 +102,73 @@ public:

    void lock() noexcept
    {
-        for( unsigned k = 0; ; ++k )
+        for( ;; )
        {
-            std::uint32_t st = state_.load( std::memory_order_relaxed );
+            for( int k = 0; k < spin_count; ++k )
+            {
+                std::uint32_t st = state_.load( std::memory_order_relaxed );

-            if( st & locked_exclusive_mask )
-            {
-                // locked exclusive, spin
-            }
-            else if( ( st & reader_lock_count_mask ) == 0 )
-            {
-                // not locked exclusive, not locked shared, try to lock
+                if( st & locked_exclusive_mask )
+                {
+                    // locked exclusive, spin
+                }
+                else if( ( st & reader_lock_count_mask ) == 0 )
+                {
+                    // not locked exclusive, not locked shared, try to lock

-                std::uint32_t newst = locked_exclusive_mask;
-                if( state_.compare_exchange_weak( st, newst, std::memory_order_acquire, std::memory_order_relaxed ) ) return;
-            }
-            else if( st & writer_pending_mask )
-            {
-                // writer pending bit already set, nothing to do
-            }
-            else
-            {
-                // locked shared, set writer pending bit
+                    std::uint32_t newst = locked_exclusive_mask;
+                    if( state_.compare_exchange_weak( st, newst, std::memory_order_acquire, std::memory_order_relaxed ) ) return;
+                }
+                else if( st & writer_pending_mask )
+                {
+                    // writer pending bit already set, nothing to do
+                }
+                else
+                {
+                    // locked shared, set writer pending bit

-                std::uint32_t newst = st | writer_pending_mask;
-                state_.compare_exchange_weak( st, newst, std::memory_order_relaxed, std::memory_order_relaxed );
+                    std::uint32_t newst = st | writer_pending_mask;
+                    state_.compare_exchange_weak( st, newst, std::memory_order_relaxed, std::memory_order_relaxed );
+                }
+
+                boost::core::sp_thread_pause();
            }

-            yield( k );
+            // clear writer pending bit before going to sleep
+
+            {
+                std::uint32_t st = state_.load( std::memory_order_relaxed );
+
+                for( ;; )
+                {
+                    if( st & locked_exclusive_mask )
+                    {
+                        // locked exclusive, nothing to do
+                        break;
+                    }
+                    else if( ( st & reader_lock_count_mask ) == 0 )
+                    {
+                        // lock free, try to take it
+
+                        std::uint32_t newst = locked_exclusive_mask;
+                        if( state_.compare_exchange_weak( st, newst, std::memory_order_acquire, std::memory_order_relaxed ) ) return;
+                    }
+                    else if( ( st & writer_pending_mask ) == 0 )
+                    {
+                        // writer pending bit already clear, nothing to do
+                        break;
+                    }
+                    else
+                    {
+                        // clear writer pending bit
+
+                        std::uint32_t newst = st & ~writer_pending_mask;
+                        if( state_.compare_exchange_weak( st, newst, std::memory_order_relaxed, std::memory_order_relaxed ) ) break;
+                    }
+                }
+            }
+
+            boost::core::sp_thread_sleep();
        }
    }

@@ -123,7 +123,6 @@ public:

 private:
  template<typename,typename,bool> friend class table_iterator;
-  template<typename> friend class table_erase_return_type;
  template<typename,typename,typename,typename> friend class table;

  table_iterator(Group* pg,std::size_t n,const table_element_type* p_):
@@ -199,45 +198,6 @@ private:
  table_element_type *p=nullptr;
 };

-/* Returned by table::erase([const_]iterator) to avoid iterator increment
- * if discarded.
- */
-
-template<typename Iterator>
-class table_erase_return_type; 
-
-template<typename TypePolicy,typename Group,bool Const>
-class table_erase_return_type<table_iterator<TypePolicy,Group,Const>>
-{
-  using iterator=table_iterator<TypePolicy,Group,Const>;
-  using const_iterator=table_iterator<TypePolicy,Group,true>;
-
-public:
-  /* can't delete it because VS in pre-C++17 mode needs to see it for RVO */
-  table_erase_return_type(const table_erase_return_type&);
-
-  operator iterator()const noexcept
-  {
-    auto it=pos;
-    it.increment(); /* valid even if *it was erased */
-    return iterator(const_iterator_cast_tag{},it);
-  }
-
-  template<
-    bool dependent_value=false,
-    typename std::enable_if<!Const||dependent_value>::type* =nullptr
-  >
-  operator const_iterator()const noexcept{return this->operator iterator();}
-
-private:
-  template<typename,typename,typename,typename> friend class table;
-
-  table_erase_return_type(const_iterator pos_):pos{pos_}{}
-  table_erase_return_type& operator=(const table_erase_return_type&)=delete;
-
-  const_iterator pos;
-};
-
 /* foa::table interface departs in a number of ways from that of C++ unordered
 * associative containers because it's not for end-user consumption
 * (boost::unordered_(flat|node)_(map|set) wrappers complete it as
@@ -311,7 +271,6 @@ public:
    has_mutable_iterator,
    table_iterator<type_policy,group_type,false>,
    const_iterator>::type;
-  using erase_return_type=table_erase_return_type<iterator>;

  table(
    std::size_t n=default_bucket_count,const Hash& h_=Hash(),
@@ -394,14 +353,12 @@ public:
    typename std::enable_if<
      has_mutable_iterator||dependent_value>::type* =nullptr
  >
-  erase_return_type erase(iterator pos)noexcept
-  {return erase(const_iterator(pos));}
+  void erase(iterator pos)noexcept{return erase(const_iterator(pos));}

  BOOST_FORCEINLINE
-  erase_return_type erase(const_iterator pos)noexcept
+  void erase(const_iterator pos)noexcept
  {
    super::erase(pos.pc,pos.p);
-    return {pos};
  }

  template<typename Key>
@@ -10,7 +10,6 @@
 #pragma once
 #endif

-#include <boost/unordered/detail/foa/flat_map_types.hpp>
 #include <boost/unordered/detail/foa/table.hpp>
 #include <boost/unordered/detail/type_traits.hpp>
 #include <boost/unordered/unordered_flat_map_fwd.hpp>
@@ -33,10 +32,67 @@ namespace boost {
 #pragma warning(disable : 4714) /* marked as __forceinline not inlined */
 #endif

+    namespace detail {
+      template <class Key, class T> struct flat_map_types
+      {
+        using key_type = Key;
+        using raw_key_type = typename std::remove_const<Key>::type;
+        using raw_mapped_type = typename std::remove_const<T>::type;
+
+        using init_type = std::pair<raw_key_type, raw_mapped_type>;
+        using moved_type = std::pair<raw_key_type&&, raw_mapped_type&&>;
+        using value_type = std::pair<Key const, T>;
+
+        using element_type = value_type;
+
+        static value_type& value_from(element_type& x) { return x; }
+
+        template <class K, class V>
+        static raw_key_type const& extract(std::pair<K, V> const& kv)
+        {
+          return kv.first;
+        }
+
+        static moved_type move(init_type& x)
+        {
+          return {std::move(x.first), std::move(x.second)};
+        }
+
+        static moved_type move(element_type& x)
+        {
+          // TODO: we probably need to launder here
+          return {std::move(const_cast<raw_key_type&>(x.first)),
+            std::move(const_cast<raw_mapped_type&>(x.second))};
+        }
+
+        template <class A, class... Args>
+        static void construct(A& al, init_type* p, Args&&... args)
+        {
+          boost::allocator_construct(al, p, std::forward<Args>(args)...);
+        }
+
+        template <class A, class... Args>
+        static void construct(A& al, value_type* p, Args&&... args)
+        {
+          boost::allocator_construct(al, p, std::forward<Args>(args)...);
+        }
+
+        template <class A> static void destroy(A& al, init_type* p) noexcept
+        {
+          boost::allocator_destroy(al, p);
+        }
+
+        template <class A> static void destroy(A& al, value_type* p) noexcept
+        {
+          boost::allocator_destroy(al, p);
+        }
+      };
+    } // namespace detail
+
    template <class Key, class T, class Hash, class KeyEqual, class Allocator>
    class unordered_flat_map
    {
-      using map_types = detail::foa::flat_map_types<Key, T>;
+      using map_types = detail::flat_map_types<Key, T>;

      using table_type = detail::foa::table<map_types, Hash, KeyEqual,
        typename boost::allocator_rebind<Allocator,
@@ -45,7 +101,8 @@ namespace boost {
      table_type table_;

      template <class K, class V, class H, class KE, class A>
-      bool friend operator==(unordered_flat_map<K, V, H, KE, A> const& lhs,
+      bool friend operator==(
+        unordered_flat_map<K, V, H, KE, A> const& lhs,
        unordered_flat_map<K, V, H, KE, A> const& rhs);

      template <class K, class V, class H, class KE, class A, class Pred>
@@ -381,18 +438,11 @@ namespace boost {
          .first;
      }

-      BOOST_FORCEINLINE typename table_type::erase_return_type erase(
-        iterator pos)
+      BOOST_FORCEINLINE void erase(iterator pos) { table_.erase(pos); }
+      BOOST_FORCEINLINE void erase(const_iterator pos)
      {
        return table_.erase(pos);
      }
-
-      BOOST_FORCEINLINE typename table_type::erase_return_type erase(
-        const_iterator pos)
-      {
-        return table_.erase(pos);
-      }
-
      iterator erase(const_iterator first, const_iterator last)
      {
        while (first != last) {
@@ -12,6 +12,7 @@
 #endif

 #include <boost/functional/hash_fwd.hpp>
+#include <boost/unordered/detail/fwd.hpp>
 #include <functional>
 #include <memory>

@@ -10,7 +10,6 @@
 #pragma once
 #endif

-#include <boost/unordered/detail/foa/flat_set_types.hpp>
 #include <boost/unordered/detail/foa/table.hpp>
 #include <boost/unordered/detail/type_traits.hpp>
 #include <boost/unordered/unordered_flat_set_fwd.hpp>
@@ -31,10 +30,38 @@ namespace boost {
 #pragma warning(disable : 4714) /* marked as __forceinline not inlined */
 #endif

+    namespace detail {
+      template <class Key> struct flat_set_types
+      {
+        using key_type = Key;
+        using init_type = Key;
+        using value_type = Key;
+
+        static Key const& extract(value_type const& key) { return key; }
+
+        using element_type = value_type;
+
+        static Key& value_from(element_type& x) { return x; }
+
+        static element_type&& move(element_type& x) { return std::move(x); }
+
+        template <class A, class... Args>
+        static void construct(A& al, value_type* p, Args&&... args)
+        {
+          boost::allocator_construct(al, p, std::forward<Args>(args)...);
+        }
+
+        template <class A> static void destroy(A& al, value_type* p) noexcept
+        {
+          boost::allocator_destroy(al, p);
+        }
+      };
+    } // namespace detail
+
    template <class Key, class Hash, class KeyEqual, class Allocator>
    class unordered_flat_set
    {
-      using set_types = detail::foa::flat_set_types<Key>;
+      using set_types = detail::flat_set_types<Key>;

      using table_type = detail::foa::table<set_types, Hash, KeyEqual,
        typename boost::allocator_rebind<Allocator,
@@ -43,7 +70,8 @@ namespace boost {
      table_type table_;

      template <class K, class H, class KE, class A>
-      bool friend operator==(unordered_flat_set<K, H, KE, A> const& lhs,
+      bool friend operator==(
+        unordered_flat_set<K, H, KE, A> const& lhs,
        unordered_flat_set<K, H, KE, A> const& rhs);

      template <class K, class H, class KE, class A, class Pred>
@@ -282,12 +310,10 @@ namespace boost {
        return table_.emplace(std::forward<Args>(args)...).first;
      }

-      BOOST_FORCEINLINE typename table_type::erase_return_type erase(
-        const_iterator pos)
+      BOOST_FORCEINLINE void erase(const_iterator pos)
      {
        return table_.erase(pos);
      }
-
      iterator erase(const_iterator first, const_iterator last)
      {
        while (first != last) {
@@ -12,6 +12,7 @@
 #endif

 #include <boost/functional/hash_fwd.hpp>
+#include <boost/unordered/detail/fwd.hpp>
 #include <functional>
 #include <memory>

@@ -13,6 +13,7 @@
 #endif

 #include <boost/functional/hash_fwd.hpp>
+#include <boost/unordered/detail/fwd.hpp>
 #include <functional>
 #include <memory>

@@ -12,7 +12,6 @@

 #include <boost/unordered/detail/foa/element_type.hpp>
 #include <boost/unordered/detail/foa/node_handle.hpp>
-#include <boost/unordered/detail/foa/node_map_types.hpp>
 #include <boost/unordered/detail/foa/table.hpp>
 #include <boost/unordered/detail/type_traits.hpp>
 #include <boost/unordered/unordered_node_map_fwd.hpp>
@@ -36,6 +35,112 @@ namespace boost {
 #endif

    namespace detail {
+      template <class Key, class T> struct node_map_types
+      {
+        using key_type = Key;
+        using mapped_type = T;
+        using raw_key_type = typename std::remove_const<Key>::type;
+        using raw_mapped_type = typename std::remove_const<T>::type;
+
+        using init_type = std::pair<raw_key_type, raw_mapped_type>;
+        using value_type = std::pair<Key const, T>;
+        using moved_type = std::pair<raw_key_type&&, raw_mapped_type&&>;
+
+        using element_type=foa::element_type<value_type>;
+
+        static value_type& value_from(element_type const& x) { return *(x.p); }
+
+        template <class K, class V>
+        static raw_key_type const& extract(std::pair<K, V> const& kv)
+        {
+          return kv.first;
+        }
+
+        static raw_key_type const& extract(element_type const& kv)
+        {
+          return kv.p->first;
+        }
+
+        static element_type&& move(element_type& x) { return std::move(x); }
+        static moved_type move(init_type& x)
+        {
+          return {std::move(x.first), std::move(x.second)};
+        }
+
+        static moved_type move(value_type& x)
+        {
+          return {std::move(const_cast<raw_key_type&>(x.first)),
+            std::move(const_cast<raw_mapped_type&>(x.second))};
+        }
+
+        template <class A>
+        static void construct(A&, element_type* p, element_type&& x) noexcept
+        {
+          p->p = x.p;
+          x.p = nullptr;
+        }
+
+        template <class A>
+        static void construct(A& al, element_type* p, element_type const& copy)
+        {
+          construct(al, p, *copy.p);
+        }
+
+        template <class A, class... Args>
+        static void construct(A& al, init_type* p, Args&&... args)
+        {
+          boost::allocator_construct(al, p, std::forward<Args>(args)...);
+        }
+
+        template <class A, class... Args>
+        static void construct(A& al, value_type* p, Args&&... args)
+        {
+          boost::allocator_construct(al, p, std::forward<Args>(args)...);
+        }
+
+        template <class A, class... Args>
+        static void construct(A& al, element_type* p, Args&&... args)
+        {
+          p->p = boost::to_address(boost::allocator_allocate(al, 1));
+          BOOST_TRY
+          {
+            boost::allocator_construct(al, p->p, std::forward<Args>(args)...);
+          }
+          BOOST_CATCH(...)
+          {
+            using pointer_type = typename boost::allocator_pointer<A>::type;
+            using pointer_traits = boost::pointer_traits<pointer_type>;
+
+            boost::allocator_deallocate(
+              al, pointer_traits::pointer_to(*(p->p)), 1);
+            BOOST_RETHROW
+          }
+          BOOST_CATCH_END
+        }
+
+        template <class A> static void destroy(A& al, value_type* p) noexcept
+        {
+          boost::allocator_destroy(al, p);
+        }
+
+        template <class A> static void destroy(A& al, init_type* p) noexcept
+        {
+          boost::allocator_destroy(al, p);
+        }
+
+        template <class A> static void destroy(A& al, element_type* p) noexcept
+        {
+          if (p->p) {
+            using pointer_type = typename boost::allocator_pointer<A>::type;
+            using pointer_traits = boost::pointer_traits<pointer_type>;
+
+            destroy(al, p->p);
+            boost::allocator_deallocate(
+              al, pointer_traits::pointer_to(*(p->p)), 1);
+          }
+        }
+      };
+
      template <class TypePolicy, class Allocator>
      struct node_map_handle
          : public detail::foa::node_handle_base<TypePolicy, Allocator>
@@ -74,7 +179,7 @@ namespace boost {
    template <class Key, class T, class Hash, class KeyEqual, class Allocator>
    class unordered_node_map
    {
-      using map_types = detail::foa::node_map_types<Key, T>;
+      using map_types = detail::node_map_types<Key, T>;

      using table_type = detail::foa::table<map_types, Hash, KeyEqual,
        typename boost::allocator_rebind<Allocator,
@@ -83,7 +188,8 @@ namespace boost {
      table_type table_;

      template <class K, class V, class H, class KE, class A>
-      bool friend operator==(unordered_node_map<K, V, H, KE, A> const& lhs,
+      bool friend operator==(
+        unordered_node_map<K, V, H, KE, A> const& lhs,
        unordered_node_map<K, V, H, KE, A> const& rhs);

      template <class K, class V, class H, class KE, class A, class Pred>
@@ -458,18 +564,11 @@ namespace boost {
          .first;
      }

-      BOOST_FORCEINLINE typename table_type::erase_return_type erase(
-        iterator pos)
+      BOOST_FORCEINLINE void erase(iterator pos) { table_.erase(pos); }
+      BOOST_FORCEINLINE void erase(const_iterator pos)
      {
        return table_.erase(pos);
      }
-
-      BOOST_FORCEINLINE typename table_type::erase_return_type erase(
-        const_iterator pos)
-      {
-        return table_.erase(pos);
-      }
-
      iterator erase(const_iterator first, const_iterator last)
      {
        while (first != last) {
@@ -12,6 +12,7 @@
 #endif

 #include <boost/functional/hash_fwd.hpp>
+#include <boost/unordered/detail/fwd.hpp>
 #include <functional>
 #include <memory>

@@ -12,7 +12,6 @@

 #include <boost/unordered/detail/foa/element_type.hpp>
 #include <boost/unordered/detail/foa/node_handle.hpp>
-#include <boost/unordered/detail/foa/node_set_types.hpp>
 #include <boost/unordered/detail/foa/table.hpp>
 #include <boost/unordered/detail/type_traits.hpp>
 #include <boost/unordered/unordered_node_set_fwd.hpp>
@@ -35,6 +34,77 @@ namespace boost {
 #endif

    namespace detail {
+      template <class Key> struct node_set_types
+      {
+        using key_type = Key;
+        using init_type = Key;
+        using value_type = Key;
+
+        static Key const& extract(value_type const& key) { return key; }
+
+        using element_type=foa::element_type<value_type>;
+
+        static value_type& value_from(element_type const& x) { return *x.p; }
+        static Key const& extract(element_type const& k) { return *k.p; }
+        static element_type&& move(element_type& x) { return std::move(x); }
+        static value_type&& move(value_type& x) { return std::move(x); }
+
+        template <class A>
+        static void construct(A& al, element_type* p, element_type const& copy)
+        {
+          construct(al, p, *copy.p);
+        }
+
+        template <typename Allocator>
+        static void construct(
+          Allocator&, element_type* p, element_type&& x) noexcept
+        {
+          p->p = x.p;
+          x.p = nullptr;
+        }
+
+        template <class A, class... Args>
+        static void construct(A& al, value_type* p, Args&&... args)
+        {
+          boost::allocator_construct(al, p, std::forward<Args>(args)...);
+        }
+
+        template <class A, class... Args>
+        static void construct(A& al, element_type* p, Args&&... args)
+        {
+          p->p = boost::to_address(boost::allocator_allocate(al, 1));
+          BOOST_TRY
+          {
+            boost::allocator_construct(al, p->p, std::forward<Args>(args)...);
+          }
+          BOOST_CATCH(...)
+          {
+            boost::allocator_deallocate(al,
+              boost::pointer_traits<
+                typename boost::allocator_pointer<A>::type>::pointer_to(*p->p),
+              1);
+            BOOST_RETHROW
+          }
+          BOOST_CATCH_END
+        }
+
+        template <class A> static void destroy(A& al, value_type* p) noexcept
+        {
+          boost::allocator_destroy(al, p);
+        }
+
+        template <class A> static void destroy(A& al, element_type* p) noexcept
+        {
+          if (p->p) {
+            destroy(al, p->p);
+            boost::allocator_deallocate(al,
+              boost::pointer_traits<typename boost::allocator_pointer<
+                A>::type>::pointer_to(*(p->p)),
+              1);
+          }
+        }
+      };
+
      template <class TypePolicy, class Allocator>
      struct node_set_handle
          : public detail::foa::node_handle_base<TypePolicy, Allocator>
@@ -65,7 +135,7 @@ namespace boost {
    template <class Key, class Hash, class KeyEqual, class Allocator>
    class unordered_node_set
    {
-      using set_types = detail::foa::node_set_types<Key>;
+      using set_types = detail::node_set_types<Key>;

      using table_type = detail::foa::table<set_types, Hash, KeyEqual,
        typename boost::allocator_rebind<Allocator,
@@ -74,7 +144,8 @@ namespace boost {
      table_type table_;

      template <class K, class H, class KE, class A>
-      bool friend operator==(unordered_node_set<K, H, KE, A> const& lhs,
+      bool friend operator==(
+        unordered_node_set<K, H, KE, A> const& lhs,
        unordered_node_set<K, H, KE, A> const& rhs);

      template <class K, class H, class KE, class A, class Pred>
@@ -352,12 +423,10 @@ namespace boost {
        return table_.emplace(std::forward<Args>(args)...).first;
      }

-      BOOST_FORCEINLINE typename table_type::erase_return_type erase(
-        const_iterator pos)
+      BOOST_FORCEINLINE void erase(const_iterator pos)
      {
        return table_.erase(pos);
      }
-
      iterator erase(const_iterator first, const_iterator last)
      {
        while (first != last) {
@@ -12,6 +12,7 @@
 #endif

 #include <boost/functional/hash_fwd.hpp>
+#include <boost/unordered/detail/fwd.hpp>
 #include <functional>
 #include <memory>

@@ -13,6 +13,7 @@
 #endif

 #include <boost/functional/hash_fwd.hpp>
+#include <boost/unordered/detail/fwd.hpp>
 #include <functional>
 #include <memory>

@@ -140,7 +140,6 @@ foa_tests(SOURCES exception/merge_exception_tests.cpp)

 # CFOA tests

-cfoa_tests(SOURCES cfoa/rw_spinlock_tests.cpp)
 cfoa_tests(SOURCES cfoa/latch_tests.cpp)
 cfoa_tests(SOURCES cfoa/insert_tests.cpp)
 cfoa_tests(SOURCES cfoa/erase_tests.cpp)
@@ -177,7 +177,6 @@ alias foa_tests :

 local CFOA_TESTS =
  latch_tests
-  rw_spinlock_tests
  insert_tests
  erase_tests
  try_emplace_tests
@@ -157,10 +157,7 @@ namespace {
      thread_runner(values, [&x, &values](boost::span<map_value_type> s) {
        (void)s;

-        map_type y(values.size());
-        for (auto const& v : values) {
-          y.insert(v);
-        }
+        map_type y(values.begin(), values.end(), values.size());

        BOOST_TEST(x.empty());
        BOOST_TEST(!y.empty());
@@ -186,10 +183,8 @@ namespace {
    {
      raii::reset_counts();

-      map_type x(values.size(), hasher(1), key_equal(2), allocator_type(3));
-      for (auto const& v : values) {
-        x.insert(v);
-      }
+      map_type x(values.begin(), values.end(), values.size(), hasher(1),
+        key_equal(2), allocator_type(3));

      auto const old_cc = +raii::copy_constructor;

@@ -223,10 +218,8 @@ namespace {
    {
      raii::reset_counts();

-      map_type x(values.size(), hasher(1), key_equal(2), allocator_type(3));
-      for (auto const& v : values) {
-        x.insert(v);
-      }
+      map_type x(values.begin(), values.end(), values.size(), hasher(1),
+        key_equal(2), allocator_type(3));

      auto const old_size = x.size();
      auto const old_cc = +raii::copy_constructor;
@@ -234,10 +227,7 @@ namespace {
      thread_runner(values, [&x, &values](boost::span<map_value_type> s) {
        (void)s;

-        map_type y(values.size());
-        for (auto const& v : values) {
-          y.insert(v);
-        }
+        map_type y(values.begin(), values.end(), values.size());

        BOOST_TEST(!x.empty());
        BOOST_TEST(!y.empty());
@@ -261,10 +251,8 @@ namespace {
    {
      raii::reset_counts();

-      map_type x(values.size(), hasher(1), key_equal(2), allocator_type(3));
-      for (auto const& v : values) {
-        x.insert(v);
-      }
+      map_type x(values.begin(), values.end(), values.size(), hasher(1),
+        key_equal(2), allocator_type(3));

      auto const old_cc = +raii::copy_constructor;

@@ -300,11 +288,8 @@ namespace {

      raii::reset_counts();

-      pocca_map_type x(
-        values.size(), hasher(1), key_equal(2), pocca_allocator_type(3));
-      for (auto const& v : values) {
-        x.insert(v);
-      }
+      pocca_map_type x(values.begin(), values.end(), values.size(), hasher(1),
+        key_equal(2), pocca_allocator_type(3));

      auto const old_size = x.size();
      auto const old_cc = +raii::copy_constructor;
@@ -312,10 +297,7 @@ namespace {
      thread_runner(values, [&x, &values](boost::span<map_value_type> s) {
        (void)s;

-        pocca_map_type y(values.size());
-        for (auto const& v : values) {
-          y.insert(v);
-        }
+        pocca_map_type y(values.begin(), values.end(), values.size());

        BOOST_TEST(!x.empty());
        BOOST_TEST(!y.empty());
@@ -428,10 +410,8 @@ namespace {
        values, [&x, &values, &num_transfers](boost::span<map_value_type> s) {
          (void)s;

-          map_type y(values.size(), hasher(2), key_equal(1), allocator_type(3));
-          for (auto const& v : values) {
-            y.insert(v);
-          }
+          map_type y(values.begin(), values.end(), values.size(), hasher(2),
+            key_equal(1), allocator_type(3));

          BOOST_TEST(x.empty());
          BOOST_TEST(!y.empty());
@@ -467,10 +447,8 @@ namespace {
    {
      raii::reset_counts();

-      map_type x(values.size(), hasher(1), key_equal(2), allocator_type(3));
-      for (auto const& v : values) {
-        x.insert(v);
-      }
+      map_type x(values.begin(), values.end(), values.size(), hasher(1),
+        key_equal(2), allocator_type(3));

      auto const old_cc = +raii::copy_constructor;
      auto const old_mc = +raii::move_constructor;
@@ -518,10 +496,8 @@ namespace {
    {
      raii::reset_counts();

-      map_type x(values.size(), hasher(1), key_equal(2), allocator_type(3));
-      for (auto const& v : values) {
-        x.insert(v);
-      }
+      map_type x(values.begin(), values.end(), values.size(), hasher(1),
+        key_equal(2), allocator_type(3));

      auto const old_size = x.size();
      auto const old_cc = +raii::copy_constructor;
@@ -533,10 +509,8 @@ namespace {
                              boost::span<map_value_type> s) {
        (void)s;

-        map_type y(values.size(), hasher(2), key_equal(1), allocator_type(3));
-        for (auto const& v : values) {
-          y.insert(v);
-        }
+        map_type y(values.begin(), values.end(), values.size(), hasher(2),
+          key_equal(1), allocator_type(3));

        BOOST_TEST(!y.empty());
        BOOST_TEST(x.get_allocator() == y.get_allocator());
@@ -575,10 +549,8 @@ namespace {
    {
      raii::reset_counts();

-      map_type x(values.size(), hasher(1), key_equal(2), allocator_type(3));
-      for (auto const& v : values) {
-        x.insert(v);
-      }
+      map_type x(values.begin(), values.end(), values.size(), hasher(1),
+        key_equal(2), allocator_type(3));

      auto const old_size = x.size();
      auto const old_cc = +raii::copy_constructor;
@@ -590,10 +562,8 @@ namespace {
                              boost::span<map_value_type> s) {
        (void)s;

-        map_type y(values.size(), hasher(2), key_equal(1), allocator_type(13));
-        for (auto const& v : values) {
-          y.insert(v);
-        }
+        map_type y(values.begin(), values.end(), values.size(), hasher(2),
+          key_equal(1), allocator_type(13));

        BOOST_TEST(
          !boost::allocator_is_always_equal<allocator_type>::type::value);
@@ -638,11 +608,8 @@ namespace {
    {
      raii::reset_counts();

-      pocma_map_type x(
-        values.size(), hasher(1), key_equal(2), pocma_allocator_type(3));
-      for (auto const& v : values) {
-        x.insert(v);
-      }
+      pocma_map_type x(values.begin(), values.end(), values.size(), hasher(1),
+        key_equal(2), pocma_allocator_type(3));

      auto const old_size = x.size();
      auto const old_cc = +raii::copy_constructor;
@@ -654,11 +621,8 @@ namespace {
                              boost::span<map_value_type> s) {
        (void)s;

-        pocma_map_type y(
-          values.size(), hasher(2), key_equal(1), pocma_allocator_type(13));
-        for (auto const& v : values) {
-          y.insert(v);
-        }
+        pocma_map_type y(values.begin(), values.end(), values.size(), hasher(2),
+          key_equal(1), pocma_allocator_type(13));

        BOOST_TEST(!y.empty());
        BOOST_TEST(x.get_allocator() != y.get_allocator());
@@ -697,10 +661,8 @@ namespace {
    {
      raii::reset_counts();

-      map_type x(values.size(), hasher(1), key_equal(2), allocator_type(3));
-      for (auto const& v : values) {
-        x.insert(v);
-      }
+      map_type x(values.begin(), values.end(), values.size(), hasher(1),
+        key_equal(2), allocator_type(3));

      auto const old_cc = +raii::copy_constructor;
      auto const old_mc = +raii::move_constructor;
@@ -31,8 +31,8 @@ namespace {
    map_type x(values.begin(), values.end(), values.size(), hasher(1),
      key_equal(2), allocator_type(3));

-    auto const old_size = x.size();
-    auto const old_d = +raii::destructor;
+    BOOST_TEST_EQ(raii::copy_constructor, 2 * x.size());
+    BOOST_TEST_EQ(raii::destructor, 0u);

    thread_runner(values, [&x](boost::span<map_value_type> s) {
      (void)s;
@@ -40,7 +40,6 @@ namespace {
    });

    BOOST_TEST(x.empty());
-    BOOST_TEST_EQ(raii::destructor, old_d + 2 * old_size);

    check_raii_counts();
  }
@@ -605,7 +605,6 @@ namespace {
  }

  UNORDERED_AUTO_TEST (initializer_list_with_all_params) {
-    // hard-code 11 unique values
    std::initializer_list<map_value_type> ilist{
      map_value_type{raii{0}, raii{0}},
      map_value_type{raii{1}, raii{1}},
@@ -641,9 +640,7 @@ namespace {
      BOOST_TEST_EQ(x.key_eq(), key_equal(2));
      BOOST_TEST(x.get_allocator() == allocator_type(3));

-      BOOST_TEST_EQ(raii::default_constructor, 0u);
-      BOOST_TEST_EQ(raii::copy_constructor, 2 * ilist.size());
-      BOOST_TEST_EQ(raii::move_constructor, 2 * 11u);
+      BOOST_TEST_EQ(raii::move_constructor, 0u);
    }
    check_raii_counts();

@@ -657,9 +654,7 @@ namespace {
      BOOST_TEST_EQ(x.key_eq(), key_equal());
      BOOST_TEST(x.get_allocator() == allocator_type(3));

-      BOOST_TEST_EQ(raii::default_constructor, 0u);
-      BOOST_TEST_EQ(raii::copy_constructor, 2 * ilist.size());
-      BOOST_TEST_EQ(raii::move_constructor, 2 * 11u);
+      BOOST_TEST_EQ(raii::move_constructor, 0u);
    }
    check_raii_counts();

@@ -673,9 +668,7 @@ namespace {
      BOOST_TEST_EQ(x.key_eq(), key_equal());
      BOOST_TEST(x.get_allocator() == allocator_type(3));

-      BOOST_TEST_EQ(raii::default_constructor, 0u);
-      BOOST_TEST_EQ(raii::copy_constructor, 2 * ilist.size());
-      BOOST_TEST_EQ(raii::move_constructor, 2 * 11u);
+      BOOST_TEST_EQ(raii::move_constructor, 0u);
    }
    check_raii_counts();

@@ -689,9 +682,7 @@ namespace {
      BOOST_TEST_EQ(x.key_eq(), key_equal());
      BOOST_TEST(x.get_allocator() == allocator_type(3));

-      BOOST_TEST_EQ(raii::default_constructor, 0u);
-      BOOST_TEST_EQ(raii::copy_constructor, 2 * ilist.size());
-      BOOST_TEST_EQ(raii::move_constructor, 2 * 11u);
+      BOOST_TEST_EQ(raii::move_constructor, 0u);
    }
    check_raii_counts();
  }
@@ -227,9 +227,7 @@ namespace {

    {
      X x(values.size());
-      for (auto const& v : values) {
-        x.insert(v);
-      }
+      x.insert(values.begin(), values.end());

      BOOST_TEST_EQ(x.size(), reference_map.size());
      BOOST_TEST_EQ(raii::destructor, 0u);
@@ -5,7 +5,6 @@
 #include "helpers.hpp"
 #include <boost/config/workaround.hpp>
 #include <boost/unordered/concurrent_flat_map_fwd.hpp>
-#include <limits>

 test::seed_t initialize_seed{32304628};

@@ -59,12 +58,4 @@ UNORDERED_AUTO_TEST (fwd_unequal_call) {
  BOOST_TEST_NOT(unequal_call(x1, x2));
 }

-// this isn't the best place for this test but it's better than introducing a
-// new file
-UNORDERED_AUTO_TEST (max_size) {
-  map_type x1;
-  BOOST_TEST_EQ(
-    x1.max_size(), std::numeric_limits<typename map_type::size_type>::max());
-}
-
 RUN_TESTS()
@@ -8,14 +8,6 @@

 #include <boost/core/ignore_unused.hpp>

-struct raii_convertible
-{
-  int x, y;
-  raii_convertible(int x_, int y_) : x{x_}, y{y_} {}
-
-  operator std::pair<raii const, raii>() { return {x, y}; }
-};
-
 namespace {
  test::seed_t initialize_seed(78937);

@@ -103,24 +95,9 @@ namespace {
  {
    template <class T, class X> void operator()(std::vector<T>& values, X& x)
    {
-      std::vector<raii_convertible> values2;
-      values2.reserve(values.size());
-      for (auto const& p : values) {
-        values2.push_back(raii_convertible(p.first.x_, p.second.x_));
-      }
+      thread_runner(
+        values, [&x](boost::span<T> s) { x.insert(s.begin(), s.end()); });

-      thread_runner(values2, [&x](boost::span<raii_convertible> s) {
-        x.insert(s.begin(), s.end());
-      });
-
-      BOOST_TEST_EQ(raii::default_constructor, 2 * values2.size());
-#if BOOST_WORKAROUND(BOOST_GCC_VERSION, >= 50300) && \
-    BOOST_WORKAROUND(BOOST_GCC_VERSION, <  50500)
-      // some versions of old gcc have trouble eliding copies here
-      // https://godbolt.org/z/Ebo6TbvaG
-#else
-      BOOST_TEST_EQ(raii::copy_constructor, 0u);
-#endif
      BOOST_TEST_EQ(raii::copy_assignment, 0u);
      BOOST_TEST_EQ(raii::move_assignment, 0u);
    }
@@ -384,31 +361,19 @@ namespace {
  {
    template <class T, class X> void operator()(std::vector<T>& values, X& x)
    {
-      std::vector<raii_convertible> values2;
-      values2.reserve(values.size());
-      for (auto const& p : values) {
-        values2.push_back(raii_convertible(p.first.x_, p.second.x_));
-      }
-
      std::atomic<std::uint64_t> num_invokes{0};
-      thread_runner(
-        values2, [&x, &num_invokes](boost::span<raii_convertible> s) {
-          x.insert_or_cvisit(s.begin(), s.end(),
-            [&num_invokes](typename X::value_type const& v) {
-              (void)v;
-              ++num_invokes;
-            });
-        });
+      thread_runner(values, [&x, &num_invokes](boost::span<T> s) {
+        x.insert_or_cvisit(
+          s.begin(), s.end(), [&num_invokes](typename X::value_type const& v) {
+            (void)v;
+            ++num_invokes;
+          });
+      });

      BOOST_TEST_EQ(num_invokes, values.size() - x.size());

-      BOOST_TEST_EQ(raii::default_constructor, 2 * values2.size());
-#if BOOST_WORKAROUND(BOOST_GCC_VERSION, >= 50300) && \
-    BOOST_WORKAROUND(BOOST_GCC_VERSION, <  50500)
-      // skip test
-#else
-      BOOST_TEST_EQ(raii::copy_constructor, 0u);
-#endif
+      BOOST_TEST_EQ(raii::default_constructor, 0u);
+      BOOST_TEST_EQ(raii::copy_constructor, 2 * x.size());
      BOOST_TEST_GT(raii::move_constructor, 0u);
    }
  } iterator_range_insert_or_cvisit;
@@ -417,31 +382,19 @@ namespace {
  {
    template <class T, class X> void operator()(std::vector<T>& values, X& x)
    {
-      std::vector<raii_convertible> values2;
-      values2.reserve(values.size());
-      for (auto const& p : values) {
-        values2.push_back(raii_convertible(p.first.x_, p.second.x_));
-      }
-
      std::atomic<std::uint64_t> num_invokes{0};
-      thread_runner(
-        values2, [&x, &num_invokes](boost::span<raii_convertible> s) {
-          x.insert_or_visit(s.begin(), s.end(),
-            [&num_invokes](typename X::value_type const& v) {
-              (void)v;
-              ++num_invokes;
-            });
-        });
+      thread_runner(values, [&x, &num_invokes](boost::span<T> s) {
+        x.insert_or_visit(
+          s.begin(), s.end(), [&num_invokes](typename X::value_type const& v) {
+            (void)v;
+            ++num_invokes;
+          });
+      });

      BOOST_TEST_EQ(num_invokes, values.size() - x.size());

-      BOOST_TEST_EQ(raii::default_constructor, 2 * values2.size());
-#if BOOST_WORKAROUND(BOOST_GCC_VERSION, >= 50300) && \
-    BOOST_WORKAROUND(BOOST_GCC_VERSION, <  50500)
-      // skip test
-#else
-      BOOST_TEST_EQ(raii::copy_constructor, 0u);
-#endif
+      BOOST_TEST_EQ(raii::default_constructor, 0u);
+      BOOST_TEST_EQ(raii::copy_constructor, 2 * x.size());
      BOOST_TEST_GT(raii::move_constructor, 0u);
    }
  } iterator_range_insert_or_visit;
@@ -63,10 +63,7 @@ namespace {
        using map2_type = boost::unordered::concurrent_flat_map<raii, raii,
          std::hash<raii>, std::equal_to<raii>, allocator_type>;

-        map2_type y(s.size(), allocator_type(3));
-        for (auto const& v : s) {
-          y.insert(v);
-        }
+        map2_type y(s.begin(), s.end(), s.size(), allocator_type(3));
        expected_copies += 2 * y.size();

        BOOST_TEST(x.get_allocator() == y.get_allocator());
@@ -1,279 +0,0 @@
-// Copyright 2023 Peter Dimov
-// Copyright 2023 Christian Mazakas
-// Distributed under the Boost Software License, Version 1.0.
-// https://www.boost.org/LICENSE_1_0.txt
-
-#include "helpers.hpp"
-
-#include <boost/unordered/detail/foa/rw_spinlock.hpp>
-
-#ifdef BOOST_GCC
-#pragma GCC diagnostic push
-#pragma GCC diagnostic ignored "-Wconversion"
-#pragma GCC diagnostic ignored "-Wsign-conversion"
-#pragma GCC diagnostic ignored "-Wshadow"
-#endif
-
-#ifdef BOOST_CLANG
-#pragma clang diagnostic push
-#pragma clang diagnostic ignored "-Wsign-conversion"
-#pragma clang diagnostic ignored "-Wshorten-64-to-32"
-#endif
-
-#include <boost/thread/locks.hpp>
-#include <boost/thread/lock_types.hpp>
-
-#ifdef BOOST_GCC
-#pragma GCC diagnostic pop
-#endif
-
-#ifdef BOOST_CLANG
-#pragma GCC diagnostic pop
-#endif
-
-#include <mutex>
-#include <shared_mutex>
-#include <thread>
-
-using boost::unordered::detail::foa::rw_spinlock;
-
-static int lcount = 0;
-
-UNORDERED_AUTO_TEST (rw_spinlock_test) {
-  rw_spinlock sp, sp2;
-
-  sp.lock();
-  sp2.lock();
-  sp.unlock();
-  sp2.unlock();
-
-  {
-    std::lock_guard<rw_spinlock> lock(sp);
-    std::lock_guard<rw_spinlock> lock2(sp2);
-  }
-}
-
-UNORDERED_AUTO_TEST (rw_spinlock_test2) {
-  rw_spinlock sp, sp2;
-
-  BOOST_TEST(sp.try_lock());
-  BOOST_TEST(!sp.try_lock());
-  BOOST_TEST(sp2.try_lock());
-  BOOST_TEST(!sp.try_lock());
-  BOOST_TEST(!sp2.try_lock());
-  sp.unlock();
-  sp2.unlock();
-
-  sp.lock();
-  BOOST_TEST(!sp.try_lock());
-  sp2.lock();
-  BOOST_TEST(!sp.try_lock());
-  BOOST_TEST(!sp2.try_lock());
-  sp.unlock();
-  sp2.unlock();
-
-  {
-    std::lock_guard<rw_spinlock> lock(sp);
-    BOOST_TEST(!sp.try_lock());
-    std::lock_guard<rw_spinlock> lock2(sp2);
-    BOOST_TEST(!sp.try_lock());
-    BOOST_TEST(!sp2.try_lock());
-  }
-}
-
-void f(rw_spinlock& sp, int n)
-{
-  for (int i = 0; i < n; ++i) {
-    std::lock_guard<rw_spinlock> lock(sp);
-    ++lcount;
-  }
-}
-
-UNORDERED_AUTO_TEST (rw_spinlock_test3) {
-  lcount = 0;
-
-  rw_spinlock sp;
-
-  int const N = 1000000; // iterations
-  int const M = 8;       // threads
-
-  std::thread th[M];
-
-  for (int i = 0; i < M; ++i) {
-    th[i] = std::thread([=, &sp] { f(sp, N); });
-  }
-
-  for (int i = 0; i < M; ++i) {
-    th[i].join();
-  }
-
-  BOOST_TEST_EQ(lcount, N * M);
-}
-
-UNORDERED_AUTO_TEST (rw_spinlock_test4) {
-  rw_spinlock sp, sp2;
-
-  sp.lock();
-  sp2.lock_shared();
-  sp2.lock_shared();
-
-  sp.unlock();
-  sp2.unlock_shared();
-  sp2.unlock_shared();
-
-  {
-    std::lock_guard<rw_spinlock> lock(sp);
-    boost::shared_lock<rw_spinlock> lock2(sp2);
-    boost::shared_lock<rw_spinlock> lock3(sp2);
-  }
-}
-
-UNORDERED_AUTO_TEST (rw_spinlock_test5) {
-  rw_spinlock sp;
-
-  {
-    BOOST_TEST(sp.try_lock_shared());
-    BOOST_TEST(sp.try_lock_shared());
-    sp.unlock_shared();
-    sp.unlock_shared();
-  }
-
-  {
-    BOOST_TEST(sp.try_lock());
-    BOOST_TEST(!sp.try_lock_shared());
-    sp.unlock();
-  }
-
-  {
-    std::lock_guard<rw_spinlock> lock(sp);
-    BOOST_TEST(!sp.try_lock_shared());
-  }
-
-  {
-    boost::shared_lock<rw_spinlock> lock(sp);
-    BOOST_TEST(!sp.try_lock());
-    BOOST_TEST(sp.try_lock_shared());
-    sp.unlock_shared();
-  }
-}
-
-UNORDERED_AUTO_TEST (rw_spinlock_test6) {
-  lcount = 0;
-
-  rw_spinlock sp;
-
-  int const N = 1000000; // total iterations
-  int const M = 8;       // threads
-
-  std::thread th[M];
-
-  for (int i = 0; i < M; ++i) {
-    int n = N;
-    th[i] = std::thread([n, &sp] {
-      for (;;) {
-        {
-          boost::shared_lock<rw_spinlock> lock(sp);
-          if (lcount >= n)
-            break;
-        }
-
-        {
-          std::lock_guard<rw_spinlock> lock(sp);
-          if (lcount >= n)
-            break;
-          ++lcount;
-        }
-      }
-    });
-  }
-
-  for (int i = 0; i < M; ++i) {
-    th[i].join();
-  }
-
-  BOOST_TEST_EQ(lcount, N);
-}
-
-UNORDERED_AUTO_TEST (rw_spinlock_test7) {
-  rw_spinlock sp;
-
-  int const N = 1000000; // total iterations
-  int const M = 8;       // threads
-
-  std::thread th[M];
-
-  for (int i = 0; i < M; ++i) {
-    int n = N;
-    th[i] = std::thread([=, &sp] {
-      for (;;) {
-        int oldc;
-
-        {
-          boost::shared_lock<rw_spinlock> lock(sp);
-          if (lcount >= n)
-            break;
-          oldc = lcount;
-        }
-
-        {
-          std::lock_guard<rw_spinlock> lock(sp);
-          if (lcount == oldc)
-            ++lcount;
-        }
-      }
-    });
-  }
-
-  for (int i = 0; i < M; ++i) {
-    th[i].join();
-  }
-
-  BOOST_TEST_EQ(lcount, N);
-}
-
-UNORDERED_AUTO_TEST (rw_spinlock_test8) {
-  lcount = 0;
-
-  rw_spinlock sp;
-
-  int const N = 1000; // total iterations
-  int const M = 4;    // threads
-
-  std::thread th[M];
-
-  for (int i = 0; i < M; ++i) {
-    int k = i;
-    int m = M;
-    int n = N;
-
-    th[i] = std::thread([k, m, n, &sp] {
-      for (int j = 0; j < n; ++j) {
-        int oldc;
-
-        for (;;) {
-          {
-            boost::shared_lock<rw_spinlock> lock(sp);
-            oldc = lcount;
-          }
-
-          if (oldc % m == k)
-            break;
-        }
-
-        {
-          std::lock_guard<rw_spinlock> lock(sp);
-          if (lcount == oldc)
-            ++lcount;
-        }
-      }
-    });
-  }
-
-  for (int i = 0; i < M; ++i) {
-    th[i].join();
-  }
-
-  BOOST_TEST_EQ(lcount, N * M);
-}
-
-RUN_TESTS()
@@ -14,7 +14,6 @@
 #include <boost/unordered/unordered_node_map.hpp>
 #include <boost/unordered/unordered_node_set.hpp>
 #include <boost/unordered/detail/implementation.hpp>
-#include <boost/unordered/detail/fwd.hpp>
 #else
 #include <boost/unordered_set.hpp>
 #include <boost/unordered_map.hpp>
@@ -844,7 +844,7 @@ void unordered_copyable_test(X& x, Key& k, T& t, Hash& hf, Pred& eq)
  a10.insert(t);
  q = a10.cbegin();
 #ifdef BOOST_UNORDERED_FOA_TESTS
-  test::check_return_type<iterator>::convertible(a10.erase(q));
+  BOOST_STATIC_ASSERT(std::is_same<void, decltype(a10.erase(q))>::value);
 #else
  test::check_return_type<iterator>::equals(a10.erase(q));
 #endif
@@ -937,7 +937,7 @@ void unordered_movable_test(X& x, Key& k, T& /* t */, Hash& hf, Pred& eq)
  a10.insert(boost::move(v5));
  q = a10.cbegin();
 #ifdef BOOST_UNORDERED_FOA_TESTS
-  test::check_return_type<iterator>::convertible(a10.erase(q));
+  BOOST_STATIC_ASSERT(std::is_same<void, decltype(a10.erase(q))>::value);
 #else
  test::check_return_type<iterator>::equals(a10.erase(q));
 #endif
@@ -23,7 +23,9 @@ namespace erase_tests {
  template <class Container>
  void erase_tests1(Container*, test::random_generator generator)
  {
+#ifndef BOOST_UNORDERED_FOA_TESTS
    typedef typename Container::iterator iterator;
+#endif
    typedef typename Container::const_iterator c_iterator;

    BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Erase by key.\n";
@@ -57,8 +59,12 @@ namespace erase_tests {
      while (size > 0 && !x.empty()) {
        typename Container::key_type key = test::get_key<Container>(*x.begin());
        std::size_t count = x.count(key);
+#ifdef BOOST_UNORDERED_FOA_TESTS
+        x.erase(x.begin());
+#else
        iterator pos = x.erase(x.begin());
        BOOST_TEST(pos == x.begin());
+#endif
        --size;
        BOOST_TEST(x.count(key) == count - 1);
        BOOST_TEST(x.size() == size);
@@ -89,10 +95,15 @@ namespace erase_tests {
        typename Container::key_type key = test::get_key<Container>(*pos);
        std::size_t count = x.count(key);
        BOOST_TEST(count > 0);
+#ifdef BOOST_UNORDERED_FOA_TESTS
+        x.erase(pos);
+        --size;
+#else
        BOOST_TEST(next == x.erase(pos));
        --size;
        if (size > 0)
          BOOST_TEST(index == 0 ? next == x.begin() : next == test::next(prev));
+#endif
        BOOST_TEST(x.count(key) == count - 1);
        if (x.count(key) != count - 1) {
          BOOST_LIGHTWEIGHT_TEST_OSTREAM << count << " => " << x.count(key)
@@ -213,8 +213,8 @@ UNORDERED_AUTO_TEST (allocator_check) {
  typedef boost::allocator_rebind<A<int>, float>::type alloc_rebound;
  alloc_rebound b;
  A<int> a(b);
-  BOOST_TEST(alloc_rebound(a) == b);
-  BOOST_TEST(A<int>(b) == a);
+  BOOST_ASSERT(alloc_rebound(a) == b);
+  BOOST_ASSERT(A<int>(b) == a);
 }

 #ifdef BOOST_UNORDERED_FOA_TESTS
@@ -1065,7 +1065,11 @@ typedef boost::unordered_map<int, int, transparent_hasher,
 // test that in the presence of the member function template `erase()`, we still
 // invoke the correct iterator overloads when the type is implicitly convertible
 //
+#ifdef BOOST_UNORDERED_FOA_TESTS
+void
+#else
 transparent_unordered_map::iterator
+#endif
 map_erase_overload_compile_test()
 {
  convertible_to_iterator<transparent_unordered_map> c;
@@ -1075,7 +1079,11 @@ map_erase_overload_compile_test()
  return map.erase(c);
 }

+#ifdef BOOST_UNORDERED_FOA_TESTS
+void
+#else
 transparent_unordered_map::const_iterator
+#endif
 map_erase_const_overload_compile_test()
 {
  convertible_to_const_iterator<transparent_unordered_map> c;
@@ -1218,7 +1226,11 @@ typedef boost::unordered_multiset<int, transparent_hasher,
  transparent_unordered_multiset;
 #endif

+#ifdef BOOST_UNORDERED_FOA_TESTS
+void
+#else
 transparent_unordered_set::iterator
+#endif
 set_erase_overload_compile_test()
 {
  convertible_to_iterator<transparent_unordered_set> c;
@@ -1228,7 +1240,11 @@ set_erase_overload_compile_test()
  return set.erase(c);
 }

+#ifdef BOOST_UNORDERED_FOA_TESTS
+void
+#else
 transparent_unordered_set::const_iterator
+#endif
 set_erase_const_overload_compile_test()
 {
  convertible_to_const_iterator<transparent_unordered_set> c;
@@ -1641,7 +1657,7 @@ template <class UnorderedMap> void test_map_transparent_subscript(UnorderedMap*)
  int key_count = key::count_;

  map[0] = 7331;
-  BOOST_TEST_EQ(key::count_, key_count);
+  BOOST_ASSERT(BOOST_TEST_EQ(key::count_, key_count));

  map[4] = 7331;
  BOOST_TEST_EQ(key::count_, key_count + 1);
@@ -1664,7 +1680,7 @@ void test_map_non_transparent_subscript(UnorderedMap*)
  int key_count = key::count_;

  map[0] = 7331;
-  BOOST_TEST_EQ(key::count_, key_count + 1);
+  BOOST_ASSERT(BOOST_TEST_EQ(key::count_, key_count + 1));

  key_count = key::count_;
  map[4] = 7331;
Author	SHA1	Message	Date
joaquintides	834a39c6a8	stylistic	2023-06-09 13:58:34 +02:00
joaquintides	c230a87f8a	added copy ctor for cache_aligned_size_control	2023-06-09 11:39:39 +02:00
joaquintides	a0b3e0965a	fixed unqualified swap call	2023-06-09 11:04:09 +02:00
joaquintides	60a037ac33	added missing #include	2023-06-09 11:03:38 +02:00
joaquintides	7b25b7e592	refactored padding into a clean design	2023-06-09 10:03:39 +02:00
joaquintides	1a62844846	added padding between and around ml and size_	2023-06-08 09:42:35 +02:00