Avoid shadowing wanrings from DateTime

Fix header includes for boost::shared_lock
Add explicit tests for rw_spinlock
2026-08-06 13:44:12 +02:00 · 2023-06-22 11:32:45 -07:00 · 2023-06-22 11:32:34 -07:00 · 2023-06-22 09:44:54 -07:00 · 2023-06-20 21:36:25 +03:00 · 2023-06-20 21:36:25 +03:00
89 changed files with 1104 additions and 585 deletions
@@ -40,87 +40,152 @@ environment:
      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2015
      B2_TOOLSET: msvc-12.0,msvc-14.0

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

-    - FLAVOR: Visual Studio 2017
+    - 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
      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
      B2_CXXSTD: latest
      B2_TOOLSET: msvc-14.1

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

-    - FLAVOR: cygwin (64-bit)
+    - 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)
      APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
      ADDPATH: C:\cygwin64\bin;
      B2_ADDRESS_MODEL: 64
-      B2_CXXSTD: 03,11,14,1z
+      B2_CXXSTD: 03,11
      B2_TOOLSET: gcc

-    - FLAVOR: cygwin (64-bit, latest)
+    - 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)
      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)
+    - FLAVOR: cygwin (64-bit, latest, C++11)
      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)
+    - FLAVOR: cygwin (64-bit, latest, C++14)
      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)
+    - FLAVOR: cygwin (64-bit, latest, C++1z)
      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
+    - FLAVOR: mingw-w64, 32 bit, C++03
      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,11,14
+      B2_CXXSTD: 03
      B2_TOOLSET: gcc
      B2_ADDRESS_MODEL: 32

-    - FLAVOR: mingw-w64, 32 bit
+    - FLAVOR: mingw-w64, 32 bit, C++11
      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,2a
+      B2_CXXSTD: 11
      B2_TOOLSET: gcc
      B2_ADDRESS_MODEL: 32

-    - FLAVOR: mingw-w64, 64 bit
+    - 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
      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,11,14
+      B2_CXXSTD: 03
      B2_TOOLSET: gcc
      B2_ADDRESS_MODEL: 64

-    - FLAVOR: mingw-w64, 64 bit
+    - FLAVOR: mingw-w64, 64 bit, C++11
      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,2a
+      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_TOOLSET: gcc
      B2_ADDRESS_MODEL: 64

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

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

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

@@ -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 11 + libstdc++-v3, x64
+=== GCC 12 + libstdc++-v3, x64

 ==== Insertion

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

 |===

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

 ==== Insertion

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

 |===

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

 ==== Insertion

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

 * 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,7 +135,9 @@ The main differences with C++ unordered associative containers are:

 * In general:
  ** `begin()` is not constant-time.
-  ** `erase(iterator)` returns `void` instead of an iterator to the following element.
+  ** `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.
  ** 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.
@@ -17,7 +17,6 @@ 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.

@@ -155,9 +154,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);

-    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);
+    _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);
    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)
@@ -1035,15 +1034,19 @@ The `template<class K, class M>` only participates in overload resolution if `Ha

 ==== Erase by Position

-```c++
-void erase(iterator position);
-void erase(const_iterator position);
-```
+[source,c++,subs=+quotes]
+----
+_convertible-to-iterator_ erase(iterator position);
+_convertible-to-iterator_ 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,7 +17,6 @@ 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.

@@ -123,9 +122,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>);

-    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);
+    _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);
    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)
@@ -846,15 +845,19 @@ Notes:;; Can invalidate iterators, pointers and references, but only if the inse

 ==== Erase by Position

-```c++
-void erase(iterator position);
-void erase(const_iterator position);
-```
+[source,c++,subs=+quotes]
+----
+_convertible-to-iterator_ erase(iterator position);
+_convertible-to-iterator_ 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,7 +13,6 @@ 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.

@@ -156,9 +155,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);

-    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);
+    _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);
    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)
@@ -1105,15 +1104,19 @@ The `template<class K, class M>` only participates in overload resolution if `Ha

 ==== Erase by Position

-```c++
-void erase(iterator position);
-void erase(const_iterator position);
-```
+[source,c++,subs=+quotes]
+----
+_convertible-to-iterator_ erase(iterator position);
+_convertible-to-iterator_ 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,7 +13,6 @@ 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.

@@ -124,9 +123,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);

-    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);
+    _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);
    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)
@@ -919,15 +918,19 @@ Notes:;; Behavior is undefined if `nh` is not empty and the allocators of `nh` a

 ==== Erase by Position

-```c++
-void erase(iterator position);
-void erase(const_iterator position);
-```
+[source,c++,subs=+quotes]
+----
+_convertible-to-iterator_ erase(iterator position);
+_convertible-to-iterator_ 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,15 +8,12 @@
 * 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>
@@ -31,12 +28,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

@@ -71,7 +68,6 @@
 namespace boost {
  namespace unordered {
    namespace detail {
-
      template <class F, class... Args>
      struct is_invocable
          : std::is_constructible<std::function<void(Args...)>,
@@ -79,60 +75,6 @@ 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>
@@ -143,7 +85,7 @@ namespace boost {
        class Allocator2>
      friend class concurrent_flat_map;

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

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

@@ -151,6 +93,10 @@ 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;
@@ -202,22 +148,24 @@ namespace boost {
      }

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

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

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

-      concurrent_flat_map(concurrent_flat_map&& rhs, allocator_type a)
+      concurrent_flat_map(concurrent_flat_map&& rhs, allocator_type const& a)
          : table_(std::move(rhs.table_), a)
      {
      }
@@ -302,6 +250,7 @@ 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
      {
@@ -425,7 +374,7 @@ namespace boost {
      void insert(InputIterator begin, InputIterator end)
      {
        for (auto pos = begin; pos != end; ++pos) {
-          table_.insert(*pos);
+          table_.emplace(*pos);
        }
      }

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

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

@@ -759,7 +708,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.erase_if(pred);
+      return c.table_.erase_if(pred);
    }

 #if BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES
@@ -8,10 +8,6 @@
 * 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

@@ -30,7 +30,6 @@
 #include <type_traits>
 #include <tuple>
 #include <utility>
-#include "oneapi/tbb/spin_rw_mutex.h"

 #if !defined(BOOST_UNORDERED_DISABLE_PARALLEL_ALGORITHMS)
 #if defined(BOOST_UNORDERED_ENABLE_PARALLEL_ALGORITHMS)|| \
@@ -212,7 +211,7 @@ struct atomic_integral

 struct group_access
 {    
-  using mutex_type=tbb::spin_rw_mutex;
+  using mutex_type=rw_spinlock;
  using shared_lock_guard=shared_lock<mutex_type>;
  using exclusive_lock_guard=lock_guard<mutex_type>;
  using insert_counter_type=std::atomic<boost::uint32_t>;
@@ -0,0 +1,73 @@
+// 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
@@ -0,0 +1,44 @@
+// 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
@@ -0,0 +1,131 @@
+// 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
@@ -0,0 +1,94 @@
+// 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,8 +30,44 @@ private:

 private:

-    // number of times to spin before sleeping
-    static constexpr int spin_count = 24576;
+    // 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();
+        }
+    }

 public:

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

    void lock_shared() noexcept
    {
-        for( ;; )
+        for( unsigned k = 0; ; ++k )
        {
-            for( int k = 0; k < spin_count; ++k )
+            std::uint32_t st = state_.load( std::memory_order_relaxed );
+
+            if( st < reader_lock_count_mask )
            {
-                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();
+                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_sleep();
+            yield( k );
        }
    }

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

    void lock() noexcept
    {
-        for( ;; )
+        for( unsigned k = 0; ; ++k )
        {
-            for( int k = 0; k < spin_count; ++k )
+            std::uint32_t st = state_.load( std::memory_order_relaxed );
+
+            if( st & locked_exclusive_mask )
            {
-                std::uint32_t st = state_.load( std::memory_order_relaxed );
+                // 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 );
-                }
-
-                boost::core::sp_thread_pause();
+                std::uint32_t newst = st | writer_pending_mask;
+                state_.compare_exchange_weak( st, newst, std::memory_order_relaxed, std::memory_order_relaxed );
            }

-            // 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();
+            yield( k );
        }
    }

@@ -123,6 +123,7 @@ 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_):
@@ -198,6 +199,45 @@ 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
@@ -271,6 +311,7 @@ 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(),
@@ -353,12 +394,14 @@ public:
    typename std::enable_if<
      has_mutable_iterator||dependent_value>::type* =nullptr
  >
-  void erase(iterator pos)noexcept{return erase(const_iterator(pos));}
+  erase_return_type erase(iterator pos)noexcept
+  {return erase(const_iterator(pos));}

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

  template<typename Key>
@@ -10,6 +10,7 @@
 #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>
@@ -32,67 +33,10 @@ 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::flat_map_types<Key, T>;
+      using map_types = detail::foa::flat_map_types<Key, T>;

      using table_type = detail::foa::table<map_types, Hash, KeyEqual,
        typename boost::allocator_rebind<Allocator,
@@ -101,8 +45,7 @@ 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>
@@ -438,11 +381,18 @@ namespace boost {
          .first;
      }

-      BOOST_FORCEINLINE void erase(iterator pos) { table_.erase(pos); }
-      BOOST_FORCEINLINE void erase(const_iterator pos)
+      BOOST_FORCEINLINE typename table_type::erase_return_type erase(
+        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,7 +12,6 @@
 #endif

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

@@ -10,6 +10,7 @@
 #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>
@@ -30,38 +31,10 @@ 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::flat_set_types<Key>;
+      using set_types = detail::foa::flat_set_types<Key>;

      using table_type = detail::foa::table<set_types, Hash, KeyEqual,
        typename boost::allocator_rebind<Allocator,
@@ -70,8 +43,7 @@ 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>
@@ -310,10 +282,12 @@ namespace boost {
        return table_.emplace(std::forward<Args>(args)...).first;
      }

-      BOOST_FORCEINLINE void erase(const_iterator 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,7 +12,6 @@
 #endif

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

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

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

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

 #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>
@@ -35,112 +36,6 @@ 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>
@@ -179,7 +74,7 @@ namespace boost {
    template <class Key, class T, class Hash, class KeyEqual, class Allocator>
    class unordered_node_map
    {
-      using map_types = detail::node_map_types<Key, T>;
+      using map_types = detail::foa::node_map_types<Key, T>;

      using table_type = detail::foa::table<map_types, Hash, KeyEqual,
        typename boost::allocator_rebind<Allocator,
@@ -188,8 +83,7 @@ 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>
@@ -564,11 +458,18 @@ namespace boost {
          .first;
      }

-      BOOST_FORCEINLINE void erase(iterator pos) { table_.erase(pos); }
-      BOOST_FORCEINLINE void erase(const_iterator pos)
+      BOOST_FORCEINLINE typename table_type::erase_return_type erase(
+        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,7 +12,6 @@
 #endif

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

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

 #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>
@@ -34,77 +35,6 @@ 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>
@@ -135,7 +65,7 @@ namespace boost {
    template <class Key, class Hash, class KeyEqual, class Allocator>
    class unordered_node_set
    {
-      using set_types = detail::node_set_types<Key>;
+      using set_types = detail::foa::node_set_types<Key>;

      using table_type = detail::foa::table<set_types, Hash, KeyEqual,
        typename boost::allocator_rebind<Allocator,
@@ -144,8 +74,7 @@ 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>
@@ -423,10 +352,12 @@ namespace boost {
        return table_.emplace(std::forward<Args>(args)...).first;
      }

-      BOOST_FORCEINLINE void erase(const_iterator 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,7 +12,6 @@
 #endif

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

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

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

@@ -140,6 +140,7 @@ 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,6 +177,7 @@ alias foa_tests :

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

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

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

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

      auto const old_cc = +raii::copy_constructor;

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

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

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

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

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

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

      auto const old_cc = +raii::copy_constructor;

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

      raii::reset_counts();

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

      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));

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

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

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

    check_raii_counts();
  }
@@ -605,6 +605,7 @@ 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}},
@@ -640,7 +641,9 @@ namespace {
      BOOST_TEST_EQ(x.key_eq(), key_equal(2));
      BOOST_TEST(x.get_allocator() == allocator_type(3));

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

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

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

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

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

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

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

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

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

 test::seed_t initialize_seed{32304628};

@@ -58,4 +59,12 @@ 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,6 +8,14 @@

 #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);

@@ -95,9 +103,24 @@ namespace {
  {
    template <class T, class X> void operator()(std::vector<T>& values, X& x)
    {
-      thread_runner(
-        values, [&x](boost::span<T> s) { x.insert(s.begin(), s.end()); });
+      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(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);
    }
@@ -361,19 +384,31 @@ 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(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;
-          });
-      });
+      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;
+            });
+        });

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

-      BOOST_TEST_EQ(raii::default_constructor, 0u);
-      BOOST_TEST_EQ(raii::copy_constructor, 2 * 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_GT(raii::move_constructor, 0u);
    }
  } iterator_range_insert_or_cvisit;
@@ -382,19 +417,31 @@ 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(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;
-          });
-      });
+      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;
+            });
+        });

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

-      BOOST_TEST_EQ(raii::default_constructor, 0u);
-      BOOST_TEST_EQ(raii::copy_constructor, 2 * 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_GT(raii::move_constructor, 0u);
    }
  } iterator_range_insert_or_visit;
@@ -63,7 +63,10 @@ namespace {
        using map2_type = boost::unordered::concurrent_flat_map<raii, raii,
          std::hash<raii>, std::equal_to<raii>, allocator_type>;

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

        BOOST_TEST(x.get_allocator() == y.get_allocator());
@@ -0,0 +1,279 @@
+// 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,6 +14,7 @@
 #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
-  BOOST_STATIC_ASSERT(std::is_same<void, decltype(a10.erase(q))>::value);
+  test::check_return_type<iterator>::convertible(a10.erase(q));
 #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
-  BOOST_STATIC_ASSERT(std::is_same<void, decltype(a10.erase(q))>::value);
+  test::check_return_type<iterator>::convertible(a10.erase(q));
 #else
  test::check_return_type<iterator>::equals(a10.erase(q));
 #endif
@@ -23,9 +23,7 @@ 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";
@@ -59,12 +57,8 @@ 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);
@@ -95,15 +89,10 @@ 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_ASSERT(alloc_rebound(a) == b);
-  BOOST_ASSERT(A<int>(b) == a);
+  BOOST_TEST(alloc_rebound(a) == b);
+  BOOST_TEST(A<int>(b) == a);
 }

 #ifdef BOOST_UNORDERED_FOA_TESTS
@@ -1065,11 +1065,7 @@ 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;
@@ -1079,11 +1075,7 @@ 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;
@@ -1226,11 +1218,7 @@ 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;
@@ -1240,11 +1228,7 @@ 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;
@@ -1657,7 +1641,7 @@ template <class UnorderedMap> void test_map_transparent_subscript(UnorderedMap*)
  int key_count = key::count_;

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

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

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

  key_count = key::count_;
  map[4] = 7331;
Author	SHA1	Message	Date
Christian Mazakas	085414479a	Avoid shadowing wanrings from DateTime	2023-06-22 11:32:45 -07:00
Christian Mazakas	515412ce0a	Fix header includes for boost::shared_lock	2023-06-22 11:32:34 -07:00
Christian Mazakas	6395ce0486	Add explicit tests for rw_spinlock	2023-06-22 09:44:54 -07:00
Peter Dimov	7d39b68e46	Fix -Wsign-conversion issue	2023-06-20 21:36:25 +03:00
Peter Dimov	79a59bce72	Change the backoff algorithm of rw_spinlock	2023-06-20 21:36:25 +03:00
Peter Dimov	717048e868	Split Appveyor jobs to avoid timeouts	2023-06-20 17:49:15 +03:00
joaquintides	de8c2a5ad9	Merge pull request #193 from boostorg/feature/proxy-erase Feature/proxy erase	2023-06-20 11:49:27 +02:00
joaquintides	678f8802f4	[skip ci] updated boost::unordered_[multi]set benchmarks	2023-06-20 09:53:25 +02:00
Christian Mazakas	704b3c7a4b	Update docs to describe the returned proxy type as "convertible to iterator"	2023-06-19 14:33:10 -07:00
Christian Mazakas	671b68f4d1	Restart drone CI	2023-06-19 10:45:37 -07:00
Christian Mazakas	b2a4b22c89	Remove erroneous asserts from the test suite These asserts were erroneously being removed in release builds of the tests which is never the intention	2023-06-19 09:21:48 -07:00
joaquintides	2eebe157fd	refactored proxy_erase to reduce template instantiations and strengthen misuse avoidance	2023-06-19 08:21:13 -07:00
joaquintides	2b6cfe4f3c	documented proxy erase(iterator)	2023-06-19 08:21:13 -07:00
Christian Mazakas	2f7bba0c21	Implement proxy erase(iterator)	2023-06-19 08:21:13 -07:00
joaquintides	d65d9a65b7	Merge pull request #188 from boostorg/feature/cfoa Feature/cfoa	2023-06-17 17:25:56 +02:00
joaquintides	67913ed99a	re-enabled CI on feature/* branches	2023-06-17 17:21:09 +02:00
joaquintides	0440cd3183	widened previous workaround	2023-06-17 09:37:17 +02:00
Christian Mazakas	3a3148cc16	Add workaround for gcc-5.4 deficiencies in copy elision and new() construction	2023-06-16 14:16:26 -07:00
Christian Mazakas	f51070ab21	Update free function erase_if() to support non-copyable predicates	2023-06-16 14:16:26 -07:00
Christian Mazakas	ac5a99da31	Add max_size() impl	2023-06-15 22:15:57 -07:00
Christian Mazakas	6fed6ea5ad	Remove extraneous fwd.hpp include from public facing headers	2023-06-15 22:15:57 -07:00
Christian Mazakas	c51c06492a	Update iterator range insert to use emplace() vs insert() to avoid copies in certain cases	2023-06-15 22:15:57 -07:00
Christian Mazakas	f604efe866	Add missing const reference qualifiers to allocator_type constructor parameters	2023-06-15 22:15:57 -07:00
Christian Mazakas	e8ec858313	Refactor type policies used by containers into their own dedicated headers	2023-06-15 22:15:57 -07:00
Christian Mazakas	bc8996559b	Remove unnecessary backticks from static_assert() messages	2023-06-15 22:15:57 -07:00
Christian Mazakas	449e1a30d3	Remove outdated reference to proposed synopsis	2023-06-15 22:15:57 -07:00