protected visitation against spurious insertion sentinels

fixed is_reserved
protected for_all_elements(_while) against transient slot reserves
2026-08-08 14:42:05 +02:00 · 2023-12-27 12:32:31 +01:00 · 2023-12-26 18:11:22 +01:00 · 2023-12-26 09:53:29 +01:00 · 2023-12-25 20:25:34 +01:00 · 2023-12-19 17:08:08 +01:00
109 changed files with 370 additions and 135 deletions
@@ -95,12 +95,12 @@ jobs:
          - { name: "clang-14 w/ sanitizers (17)", sanitize: yes,
              compiler: clang-14,  cxxstd: '17',    os: 'ubuntu-22.04', ccache_key: "san2" }
          - { name: "clang-14 w/ sanitizers (20)", sanitize: yes,
-              compiler: clang-14,  cxxstd: '20',    os: 'ubuntu-22.04', ccache_key: "san2" }
+              compiler: clang-14,  cxxstd: '20',   container: 'ubuntu:22.04',  os: 'ubuntu-latest', ccache_key: "san2" }
          - { name: "clang-14 w/ sanitizers (2b)", sanitize: yes,
-              compiler: clang-14,  cxxstd: '2b',    os: 'ubuntu-22.04', ccache_key: "san2" }
+              compiler: clang-14,  cxxstd: '2b',   container: 'ubuntu:22.04',  os: 'ubuntu-latest', ccache_key: "san2" }

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

          - { compiler: 'clang-15', cxxstd: '11,14',    os: 'ubuntu-22.04', stdlib: libc++, install: 'clang-15 libc++-15-dev libc++abi-15-dev' }
@@ -134,7 +134,7 @@ jobs:
                apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv-keys E1DD270288B4E6030699E45FA1715D88E1DF1F24
                for i in {1..${NET_RETRY_COUNT:-3}}; do sudo -E add-apt-repository -y ppa:git-core/ppa && break || sleep 10; done
                apt-get -o Acquire::Retries=$NET_RETRY_COUNT update
-                apt-get -o Acquire::Retries=$NET_RETRY_COUNT install -y g++ python libpython-dev git
+                apt-get -o Acquire::Retries=$NET_RETRY_COUNT install -y g++ python-is-python3 git
            fi
            # For jobs not compatible with ccache, use "ccache: no" in the matrix
            if [[ "${{ matrix.ccache }}" == "no" ]]; then
@@ -3,7 +3,7 @@
 # Distributed under the Boost Software License, Version 1.0.
 # https://www.boost.org/LICENSE_1_0.txt

-cmake_minimum_required(VERSION 3.5...3.20)
+cmake_minimum_required(VERSION 3.8...3.20)

 project(boost_unordered VERSION "${BOOST_SUPERPROJECT_VERSION}" LANGUAGES CXX)

@@ -18,16 +18,13 @@ target_link_libraries(boost_unordered
    Boost::config
    Boost::container_hash
    Boost::core
-    Boost::move
    Boost::mp11
    Boost::predef
-    Boost::preprocessor
-    Boost::static_assert
    Boost::throw_exception
-    Boost::tuple
-    Boost::type_traits
 )

+target_compile_features(boost_unordered INTERFACE cxx_std_11)
+
 if(BUILD_TESTING AND EXISTS "${CMAKE_CURRENT_SOURCE_DIR}/test/CMakeLists.txt")

  add_subdirectory(test)
@@ -1,49 +1,73 @@
 # Boost.Unordered

-Part of collection of the [Boost C++ Libraries](http://github.com/boostorg).
+[![Branch](https://img.shields.io/badge/branch-master-brightgreen.svg)](https://github.com/boostorg/unordered/tree/master) [![CI](https://github.com/boostorg/unordered/actions/workflows/ci.yml/badge.svg?branch=master)](https://github.com/boostorg/unordered/actions/workflows/ci.yml) [![Drone status](https://img.shields.io/drone/build/boostorg/unordered/master?server=https%3A%2F%2Fdrone.cpp.al&logo=drone&logoColor=%23CCCCCC&label=CI)](https://drone.cpp.al/boostorg/unordered) [![Build status](https://img.shields.io/appveyor/build/cppalliance/unordered/master?logo=appveyor&label=CI)](https://ci.appveyor.com/project/cppalliance/unordered/branch/master)  [![codecov](https://codecov.io/gh/boostorg/unordered/branch/master/graph/badge.svg)](https://codecov.io/gh/boostorg/unordered/branch/master)  [![Deps](https://img.shields.io/badge/deps-master-brightgreen.svg)](https://pdimov.github.io/boostdep-report/master/unordered.html)  [![Documentation](https://img.shields.io/badge/docs-master-brightgreen.svg)](https://www.boost.org/doc/libs/master/libs/unordered/doc/html/unordered.html)  [![Enter the Matrix](https://img.shields.io/badge/matrix-master-brightgreen.svg)](http://www.boost.org/development/tests/master/developer/unordered.html)<br/>
+[![Branch](https://img.shields.io/badge/branch-develop-brightgreen.svg)](https://github.com/boostorg/unordered/tree/develop) [![CI](https://github.com/boostorg/unordered/actions/workflows/ci.yml/badge.svg?branch=develop)](https://github.com/boostorg/unordered/actions/workflows/ci.yml) [![Drone status](https://img.shields.io/drone/build/boostorg/unordered/develop?server=https%3A%2F%2Fdrone.cpp.al&logo=drone&logoColor=%23CCCCCC&label=CI)](https://drone.cpp.al/boostorg/unordered) [![Build status](https://img.shields.io/appveyor/build/cppalliance/unordered/master?logo=appveyor&label=CI)](https://ci.appveyor.com/project/cppalliance/unordered/branch/develop) [![codecov](https://codecov.io/gh/boostorg/unordered/branch/develop/graph/badge.svg)](https://codecov.io/gh/boostorg/unordered/branch/develop) [![Deps](https://img.shields.io/badge/deps-develop-brightgreen.svg)](https://pdimov.github.io/boostdep-report/develop/unordered.html) [![Documentation](https://img.shields.io/badge/docs-develop-brightgreen.svg)](https://www.boost.org/doc/libs/develop/libs/unordered/doc/html/unordered.html) [![Enter the Matrix](https://img.shields.io/badge/matrix-develop-brightgreen.svg)](http://www.boost.org/development/tests/develop/developer/unordered.html)<br/>
+[![BSL 1.0](https://img.shields.io/badge/license-BSL_1.0-blue.svg)](https://www.boost.org/users/license.html) <img alt="C++11 required" src="https://img.shields.io/badge/standard-C%2b%2b11-blue.svg"> <img alt="Header-only library" src="https://img.shields.io/badge/build-header--only-blue.svg">

-For accessing data based on key lookup, the C++ standard library offers `std::set`, `std::map`, `std::multiset` and `std::multimap`.
-These are generally implemented using balanced binary trees so that lookup time has logarithmic complexity.
-That is generally okay, but in many cases a hash table can perform better, as accessing data has constant complexity, on average.
-The worst case complexity is linear, but that occurs rarely and with some care, can be avoided.
+Boost.Unordered offers a catalog of hash containers with different standards compliance levels, performances and intented usage scenarios:

-Also, the existing containers require a 'less than' comparison object to order their elements.
-For some data types this is impossible to implement or isn’t practical.
-In contrast, a hash table only needs an equality function and a hash function for the key.
+**`boost::unordered_set` `boost::unordered_map` `boost::unordered_multiset` `boost::unordered_multimap`**

-With this in mind, unordered associative containers were added to the C++ standard.
-This is an implementation of the containers described in C++11, with some deviations from the standard in order to work with non-C++11 compilers and libraries.
+<ul>Fully conformant implementations of <code>std::unordered_[multi](set|map)</code>,
+but faster and up to the latest revisions of the standard even if you're working in an older version of C++ (heterogeneous lookup,
+<code>try_emplace</code>, <code>contains</code>, etc.)</ul>

+**`boost::unordered_flat_set` `boost::unordered_flat_map`**

-### License
+<ul>The fastest of the lot. Based on open addressing, these containers slightly
+deviate from the standard in exchange for top performance.</ul>

-Distributed under the [Boost Software License, Version 1.0](http://www.boost.org/LICENSE_1_0.txt).
+**`boost::unordered_node_set` `boost::unordered_node_map`**

-### Properties
+<ul>Variations of <code>boost::unordered_flat_(set|map)</code> providing pointer stability.</ul>

-* C++03
-* Header-Only
+**`boost::concurrent_flat_set` `boost::concurrent_flat_map`**

-### Build Status
+<ul>High performance for multithreaded scenarios. Introducing a new non-standard, iterator-free API.</ul>

-Branch          | GH Actions | Appveyor | codecov.io | Deps | Docs | Tests |
-:-------------: | ---------- | -------- | ---------- | ---- | ---- | ----- |
-[`master`](https://github.com/boostorg/unordered/tree/master)   | [![CI](https://github.com/boostorg/unordered/actions/workflows/ci.yml/badge.svg?branch=master)](https://github.com/boostorg/unordered/actions/workflows/ci.yml)  | [![Build status](https://ci.appveyor.com/api/projects/status/github/boostorg/unordered?branch=master&svg=true)](https://ci.appveyor.com/project/danieljames/unordered-qtwe6/branch/master)   | [![codecov](https://codecov.io/gh/boostorg/unordered/branch/master/graph/badge.svg)](https://codecov.io/gh/boostorg/unordered/branch/master)   | [![Deps](https://img.shields.io/badge/deps-master-brightgreen.svg)](https://pdimov.github.io/boostdep-report/master/unordered.html)   | [![Documentation](https://img.shields.io/badge/docs-master-brightgreen.svg)](https://www.boost.org/doc/libs/master/libs/unordered/doc/html/unordered.html)   | [![Enter the Matrix](https://img.shields.io/badge/matrix-master-brightgreen.svg)](http://www.boost.org/development/tests/master/developer/unordered.html)
-[`develop`](https://github.com/boostorg/unordered/tree/develop) | [![CI](https://github.com/boostorg/unordered/actions/workflows/ci.yml/badge.svg?branch=develop)](https://github.com/boostorg/unordered/actions/workflows/ci.yml) | [![Build status](https://ci.appveyor.com/api/projects/status/github/boostorg/unordered?branch=develop&svg=true)](https://ci.appveyor.com/project/danieljames/unordered-qtwe6/branch/develop) | [![codecov](https://codecov.io/gh/boostorg/unordered/branch/develop/graph/badge.svg)](https://codecov.io/gh/boostorg/unordered/branch/develop) | [![Deps](https://img.shields.io/badge/deps-develop-brightgreen.svg)](https://pdimov.github.io/boostdep-report/develop/unordered.html) | [![Documentation](https://img.shields.io/badge/docs-develop-brightgreen.svg)](https://www.boost.org/doc/libs/develop/libs/unordered/doc/html/unordered.html) | [![Enter the Matrix](https://img.shields.io/badge/matrix-develop-brightgreen.svg)](http://www.boost.org/development/tests/develop/developer/unordered.html)
+## Learn about Boost.Unordered

-### Directories
+* [Online documentation](https://boost.org/libs/unordered)
+* [Some benchmarks](https://github.com/boostorg/boost_unordered_benchmarks)
+* Technical articles on Boost.Unordered internal design:
+  * [Advancing the state of the art for `std::unordered_map` implementations](https://bannalia.blogspot.com/2022/06/advancing-state-of-art-for.html)
+  * [Inside `boost::unordered_flat_map`](https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html)
+  * [Inside `boost::concurrent_flat_map`](https://bannalia.blogspot.com/2023/07/inside-boostconcurrentflatmap.html)
+  * [Bulk visitation in `boost::concurrent_flat_map`](https://bannalia.blogspot.com/2023/10/bulk-visitation-in-boostconcurrentflatm.html)

-| Name        | Purpose                        |
-| ----------- | ------------------------------ |
-| `doc`       | documentation                  |
-| `example`   | examples                       |
-| `include`   | headers                        |
-| `test`      | unit tests                     |
+## Get the library

-### More information
+Boost.Unordered can be installed in a number of ways:

-* [Ask questions](http://stackoverflow.com/questions/ask?tags=c%2B%2B,boost,boost-unordered)
-* [Report bugs](https://github.com/boostorg/unordered/issues): Be sure to mention Boost version, platform and compiler you're using. A small compilable code sample to reproduce the problem is always good as well.
-* Submit your patches as pull requests against **develop** branch. Note that by submitting patches you agree to license your modifications under the [Boost Software License, Version 1.0](http://www.boost.org/LICENSE_1_0.txt).
-* Discussions about the library are held on the [Boost developers mailing list](http://www.boost.org/community/groups.html#main). Be sure to read the [discussion policy](http://www.boost.org/community/policy.html) before posting and add the `[unordered]` tag at the beginning of the subject line.
+* [Download Boost](https://www.boost.org/users/download/) and you're ready to go (this is a header-only library requiring no building).
+* Using Conan 2: In case you don't have it yet, add an entry for Boost in your `conanfile.txt` (the example requires at least Boost 1.83):
+```
+[requires]
+boost/[>=1.83.0]
+```
+<ul>If you're not using any compiled Boost library, the following will skip building altogether:</ul>

+```
+[options]
+boost:header_only=True
+```
+* Using vcpkg: Execute the command
+```
+vcpkg install boost-unordered
+```
+* Using CMake: [Boost CMake support infrastructure](https://github.com/boostorg/cmake)
+allows you to use CMake directly to download, build and consume all of Boost or
+some specific libraries.
+
+## Support
+
+* Join the **#boost-unordered** discussion group at [cpplang.slack.com](https://cpplang.slack.com/)
+([ask for an invite](https://cppalliance.org/slack/) if you’re not a member of this workspace yet)
+* Ask in the [Boost Users mailing list](https://lists.boost.org/mailman/listinfo.cgi/boost-users)
+(add the `[unordered]` tag at the beginning of the subject line)
+* [File an issue](https://github.com/boostorg/unordered/issues)
+
+## Contribute
+
+* [Pull requests](https://github.com/boostorg/unordered/pulls) against **develop** branch are most welcome.
+Note that by submitting patches you agree to license your modifications under the [Boost Software License, Version 1.0](http://www.boost.org/LICENSE_1_0.txt).
@@ -10,7 +10,7 @@ All benchmarks were created using `unordered_set<unsigned int>` (non-duplicate)

 The insertion benchmarks insert `n` random values, where `n` is between 10,000 and 3 million. For the duplicated benchmarks, the same random values are repeated an average of 5 times.

-The erasure benchmarks erase all `n` elements randomly until the container is empty.
+The erasure benchmarks erase all `n` elements randomly until the container is empty. Erasure by key uses `erase(const key_type&)` to remove entire groups of equivalent elements in each operation.

 The successful lookup benchmarks are done by looking up all `n` values, in their original insertion order.

@@ -30,7 +30,7 @@ The unsuccessful lookup benchmarks use `n` randomly generated integers but using

 h|non-duplicate elements 
 h|duplicate elements 
-h|duplicate elements +
+h|duplicate elements, +
 max load factor 5
 |===

@@ -64,8 +64,18 @@ prior `reserve`

 h|non-duplicate elements 
 h|duplicate elements 
-h|duplicate elements +
+h|duplicate elements, +
 max load factor 5
+
+|
+|image::benchmarks-set/gcc/scattered%20erasure%20by%20key.xlsx.practice non-unique.png[width=250,link=../diagrams/benchmarks-set/gcc/scattered%20erasure%20by%20key.xlsx.practice non-unique.png,window=_blank]
+|image::benchmarks-set/gcc/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png[width=250,link=../diagrams/benchmarks-set/gcc/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png,window=_blank]
+
+|
+h|by key, duplicate elements 
+h|by key, duplicate elements, +
+max load factor 5
+
 |===

 ==== Successful Lookup
@@ -154,6 +164,15 @@ h|duplicate elements
 h|duplicate elements, +
 max load factor 5

+|
+|image::benchmarks-set/clang_libcpp/scattered%20erasure%20by%20key.xlsx.practice non-unique.png[width=250,link=../diagrams/benchmarks-set/clang_libcpp/scattered%20erasure%20by%20key.xlsx.practice non-unique.png,window=_blank]
+|image::benchmarks-set/clang_libcpp/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png[width=250,link=../diagrams/benchmarks-set/clang_libcpp/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png,window=_blank]
+
+|
+h|by key, duplicate elements 
+h|by key, duplicate elements, +
+max load factor 5
+
 |===

 ==== Successful lookup
@@ -242,6 +261,15 @@ h|duplicate elements
 h|duplicate elements, +
 max load factor 5

+|
+|image::benchmarks-set/vs/scattered%20erasure%20by%20key.xlsx.practice non-unique.png[width=250,link=../diagrams/benchmarks-set/vs/scattered%20erasure%20by%20key.xlsx.practice non-unique.png,window=_blank]
+|image::benchmarks-set/vs/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png[width=250,link=../diagrams/benchmarks-set/vs/scattered%20erasure%20by%20key.xlsx.practice non-unique 5.png,window=_blank]
+
+|
+h|by key, duplicate elements 
+h|by key, duplicate elements, +
+max load factor 5
+
 |===

 ==== Successful lookup
@@ -19,6 +19,9 @@ a concurrent container from user code.
 * Added Boost.Serialization support to all containers and their (non-local) iterator types.
 * Added support for fancy pointers to open-addressing and concurrent containers.
  This enables scenarios like the use of Boost.Interprocess allocators to construct containers in shared memory.
+* Fixed bug in member of pointer operator for local iterators of closed-addressing
+  containers ({github-pr-url}/221[PR#221^], credit goes to GitHub user vslashg for finding
+  and fixing this issue).
 * Starting with this release, `boost::unordered_[multi]set` and `boost::unordered_[multi]map`
  only work with C++11 onwards.

@@ -39,7 +42,7 @@ when the returned proxy is not used.
  `boost::unordered_node_map` and `boost::unordered_node_set`.
 * Extended heterogeneous lookup to more member functions as specified in
  https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p2363r5.html[P2363].
-* Replaced the previous post-mixing process for open-addressing containers with 
+* Replaced the previous post-mixing process for open-addressing containers with
  a new algorithm based on extended multiplication by a constant.
 * Fixed bug in internal emplace() impl where stack-local types were not properly
  constructed using the Allocator of the container which breaks uses-allocator
@@ -56,20 +59,20 @@ when the returned proxy is not used.

 * Refactor internal implementation to be dramatically faster
 * Allow `final` Hasher and KeyEqual objects
-* Update documentation, adding benchmark graphs and notes on the new internal 
+* Update documentation, adding benchmark graphs and notes on the new internal
  data structures

 == Release 1.79.0

 * Improved {cpp}20 support:
-  ** All containers have been updated to support 
+  ** All containers have been updated to support
    heterogeneous `count`, `equal_range` and `find`.
  ** All containers now implement the member function `contains`.
  ** `erase_if` has been implemented for all containers.
 * Improved {cpp}23 support:
  ** All containers have been updated to support
    heterogeneous `erase` and `extract`.
-* Changed behavior of `reserve` to eagerly 
+* Changed behavior of `reserve` to eagerly
  allocate ({github-pr-url}/59[PR#59^]).
 * Various warning fixes in the test suite.
 * Update code to internally use `boost::allocator_traits`.
@@ -38,7 +38,7 @@ Users can then declare a hash function `Hash` as avalanching either by embedding
 into the definition of `Hash`, or directly by specializing `hash_is_avalanching<Hash>` to a class with
 an embedded compile-time constant `value` set to `true`.

-xref:unordered_flat_set[`boost::unordered_flat_set`] and xref:unordered_flat_map[`boost::unordered_flat_map`]
+Open-addressing and concurrent containers
 use the provided hash function `Hash` as-is if `hash_is_avalanching<Hash>::value` is `true`; otherwise, they
 implement a bit-mixing post-processing stage to increase the quality of hashing at the expense of
 extra computational cost.
@@ -152,7 +152,7 @@ performing container-wide operations such as swapping or assignment.

 By using atomic operations to access the group metadata, lookup is (group-level)
 lock-free up to the point where an actual comparison needs to be done with an element
-that has been previously SIMD-matched: only then it's the group's spinlock used.
+that has been previously SIMD-matched: only then is the group's spinlock used.

 Insertion uses the following _optimistic algorithm_:

@@ -1216,6 +1216,12 @@ template<class H2, class P2>

 Transfers all the element nodes from `source` whose key is not already present in `*this`.

+[horizontal]
+Requires:;; `this\->get_allocator() == source.get_allocator()`.
+Notes:;; Invalidates iterators to the elements transferred.
+If the resulting size of `*this` is greater than its original maximum load,
+invalidates all iterators associated to `*this`.
+
 ---

 === Observers
@@ -1030,6 +1030,12 @@ template<class H2, class P2>

 Transfers all the element nodes from `source` whose key is not already present in `*this`.

+[horizontal]
+Requires:;; `this\->get_allocator() == source.get_allocator()`.
+Notes:;; Invalidates iterators to the elements transferred.
+If the resulting size of `*this` is greater than its original maximum load,
+invalidates all iterators associated to `*this`.
+
 ---

 === Observers
@@ -855,8 +855,6 @@ namespace boost {
 #endif

  } // namespace unordered
-
-  using unordered::concurrent_flat_map;
 } // namespace boost

 #endif // BOOST_UNORDERED_CONCURRENT_FLAT_MAP_HPP
@@ -46,9 +46,6 @@ namespace boost {
  } // namespace unordered

  using boost::unordered::concurrent_flat_map;
-  using boost::unordered::swap;
-  using boost::unordered::operator==;
-  using boost::unordered::operator!=;
 } // namespace boost

 #endif // BOOST_UNORDERED_CONCURRENT_FLAT_MAP_HPP
@@ -711,8 +711,6 @@ namespace boost {
 #endif

  } // namespace unordered
-
-  using unordered::concurrent_flat_set;
 } // namespace boost

 #endif // BOOST_UNORDERED_CONCURRENT_FLAT_SET_HPP
@@ -47,9 +47,6 @@ namespace boost {
  } // namespace unordered

  using boost::unordered::concurrent_flat_set;
-  using boost::unordered::swap;
-  using boost::unordered::operator==;
-  using boost::unordered::operator!=;
 } // namespace boost

 #endif // BOOST_UNORDERED_CONCURRENT_FLAT_SET_FWD_HPP
@@ -318,7 +318,10 @@ namespace boost {

        reference operator*() const noexcept { return dereference(); }

-        pointer operator->() const noexcept { return boost::to_address(p); }
+        pointer operator->() const noexcept
+        {
+          return std::addressof(dereference());
+        }

        grouped_local_bucket_iterator& operator++() noexcept
        {
@@ -386,7 +389,10 @@ namespace boost {

        reference operator*() const noexcept { return dereference(); }

-        pointer operator->() const noexcept { return boost::to_address(p); }
+        pointer operator->() const noexcept
+        {
+          return std::addressof(dereference());
+        }

        const_grouped_local_bucket_iterator& operator++() noexcept
        {
@@ -198,13 +198,13 @@ private:
 template<typename Integral>
 struct atomic_integral
 {
-  operator Integral()const{return n.load(std::memory_order_relaxed);}
-  void operator=(Integral m){n.store(m,std::memory_order_relaxed);}
-  void operator|=(Integral m){n.fetch_or(m,std::memory_order_relaxed);}
-  void operator&=(Integral m){n.fetch_and(m,std::memory_order_relaxed);}
+  operator Integral()const{return n.load(std::memory_order_acquire);}
+  void operator=(Integral m){n.store(m,std::memory_order_release);}
+  void operator|=(Integral m){n.fetch_or(m);}
+  void operator&=(Integral m){n.fetch_and(m);}

  atomic_integral& operator=(atomic_integral const& rhs) {
-    n.store(rhs.n.load(std::memory_order_relaxed),std::memory_order_relaxed);
+    n.store(rhs.n.load());
    return *this;
  }

@@ -1177,7 +1177,7 @@ private:
        do{
          auto n=unchecked_countr_zero(mask);
          if(BOOST_LIKELY(
-            pg->is_occupied(n)&&bool(this->pred()(x,this->key_from(p[n]))))){
+            is_occupied(pg,n)&&bool(this->pred()(x,this->key_from(p[n]))))){
            f(pg,n,p+n);
            return 1;
          }
@@ -1216,7 +1216,8 @@ private:
      auto mask=masks[i]=(this->arrays.groups()+pos)->match(hash);
      if(mask){
        BOOST_UNORDERED_PREFETCH(this->arrays.group_accesses()+pos);
-        BOOST_UNORDERED_PREFETCH_ELEMENTS(this->arrays.elements()+pos*N,N);
+        BOOST_UNORDERED_PREFETCH(
+          this->arrays.elements()+pos*N+unchecked_countr_zero(mask));
      }
    }

@@ -1235,7 +1236,7 @@ private:
          do{
            auto n=unchecked_countr_zero(mask);
            if(BOOST_LIKELY(
-              pg->is_occupied(n)&&
+              is_occupied(pg,n)&&
              bool(this->pred()(*it,this->key_from(p[n]))))){
              f(cast_for(access_mode,type_policy::value_from(p[n])));
              ++res;
@@ -1435,10 +1436,103 @@ private:
    bool        commit_=false;
  };

+  struct latch_free_reserve_slot
+  {
+    latch_free_reserve_slot(group_type* pg_,std::size_t pos_):pg{pg_},pos{pos_}
+    {
+      unsigned char expected=0;
+      succeeded_=reinterpret_cast<std::atomic<unsigned char>*>(pg)[pos].
+        compare_exchange_weak(expected,1);
+    }
+
+    ~latch_free_reserve_slot()
+    {
+      if(succeeded_&&!commit_)pg->reset(pos);
+    }
+
+    bool succeeded()const{return succeeded_;}
+
+    void commit(){commit_=true;}
+
+    group_type  *pg;
+    std::size_t pos;
+    bool        succeeded_;
+    bool        commit_=false;
+  };
+
+  struct assign_insert_counter_on_exit
+  {
+    ~assign_insert_counter_on_exit(){counter=x;}
+
+    group_insert_counter_type &counter;
+    boost::uint32_t            x;
+  };
+
  template<typename GroupAccessMode,typename F,typename... Args>
  BOOST_FORCEINLINE int
  unprotected_norehash_emplace_or_visit(
    GroupAccessMode access_mode,F&& f,Args&&... args)
+  {
+    return unprotected_norehash_emplace_or_visit_with_layout(
+      std::integral_constant<bool,group_type::regular_layout>{},
+      access_mode,std::forward<F>(f),std::forward<Args>(args)...);
+  }
+
+  template<typename GroupAccessMode,typename F,typename... Args>
+  BOOST_FORCEINLINE int
+  unprotected_norehash_emplace_or_visit_with_layout(
+    std::true_type, /* regular layout, almost-latch-free */
+    GroupAccessMode access_mode,F&& f,Args&&... args)
+  {
+    const auto &k=this->key_from(std::forward<Args>(args)...);
+    auto        hash=this->hash_for(k);
+    auto        pos0=this->position_for(hash);
+
+    for(;;){
+    startover:
+      boost::uint32_t counter=0;
+      while(BOOST_UNLIKELY((counter=insert_counter(pos0))%2==1)){}
+      if(unprotected_visit(
+        access_mode,k,pos0,hash,std::forward<F>(f)))return 0;
+
+      reserve_size rsize(*this);
+      if(BOOST_LIKELY(rsize.succeeded())){
+        for(prober pb(pos0);;pb.next(this->arrays.groups_size_mask)){
+          auto pos=pb.get();
+          auto pg=this->arrays.groups()+pos;
+          auto mask=pg->match_available();
+          if(BOOST_LIKELY(mask!=0)){
+            auto n=unchecked_countr_zero(mask);
+            latch_free_reserve_slot rslot{pg,n};
+            if(BOOST_UNLIKELY(!rslot.succeeded())){
+              /* slot wasn't empty */
+              goto startover;
+            }
+            if(BOOST_UNLIKELY(
+              !insert_counter(pos0).compare_exchange_weak(counter,counter+1))){
+              /* other thread inserted from pos0, need to start over */
+              goto startover;
+            }
+            assign_insert_counter_on_exit a{insert_counter(pos0),counter+2};
+            auto p=this->arrays.elements()+pos*N+n;
+            this->construct_element(p,std::forward<Args>(args)...);
+            pg->set(n,hash);
+            rslot.commit();
+            rsize.commit();
+            return 1;
+          }
+          pg->mark_overflow(hash);
+        }
+      }
+      else return -1;
+    }
+  }
+
+  template<typename GroupAccessMode,typename F,typename... Args>
+  BOOST_FORCEINLINE int
+  unprotected_norehash_emplace_or_visit_with_layout(
+    std::false_type, /* non-regular layout, latched */
+    GroupAccessMode access_mode,F&& f,Args&&... args)
  {
    const auto &k=this->key_from(std::forward<Args>(args)...);
    auto        hash=this->hash_for(k);
@@ -1485,6 +1579,46 @@ private:
    }
  }

+  /* check occupation with previous unsynced match */
+
+  static bool is_occupied(group_type* pg,std::size_t pos)
+  {
+    return is_occupied(
+      std::integral_constant<bool,group_type::regular_layout>{},pg,pos);
+  }
+
+  static bool is_occupied(std::true_type,group_type* pg,std::size_t pos)
+  {
+    /* regular layout, almost-latch-free insertion -> possible reserved slot */
+    return reinterpret_cast<std::atomic<unsigned char>*>(pg)[pos]>1;
+  }
+
+  static bool is_occupied(std::false_type,group_type* pg,std::size_t pos)
+  {
+    /* non-regular layout, latched insertion -> no reserved slots */
+    return pg->is_occupied(pos);
+  }
+
+  /* check occupation with previous synced match */
+
+  static bool is_really_occupied(group_type* pg,std::size_t pos)
+  {
+    return is_really_occupied(
+      std::integral_constant<bool,group_type::regular_layout>{},pg,pos);
+  }
+
+  static bool is_really_occupied(std::true_type,group_type* pg,std::size_t pos)
+  {
+    /* regular layout, almost-latch-free insertion -> possible reserved slot */
+    return reinterpret_cast<std::atomic<unsigned char>*>(pg)[pos]>1;
+  }
+
+  static bool is_really_occupied(std::false_type,group_type*,std::size_t)
+  {
+    /* non-regular layout, latched insertion -> no false positives */
+    return true;
+  }
+
  template<typename GroupAccessMode,typename F>
  auto for_all_elements(GroupAccessMode access_mode,F f)const
    ->decltype(f(nullptr),void())
@@ -1522,7 +1656,7 @@ private:
        auto mask=this->match_really_occupied(pg,last);
        while(mask){
          auto n=unchecked_countr_zero(mask);
-          if(!f(pg,n,p+n))return false;
+          if(BOOST_LIKELY(is_really_occupied(pg,n))&&!f(pg,n,p+n))return false;
          mask&=mask-1;
        }
      }
@@ -1557,7 +1691,7 @@ private:
        auto mask=this->match_really_occupied(&g,last);
        while(mask){
          auto n=unchecked_countr_zero(mask);
-          f(&g,n,p+n);
+          if(BOOST_LIKELY(is_really_occupied(&g,n)))f(&g,n,p+n);
          mask&=mask-1;
        }
      }
@@ -1579,7 +1713,7 @@ private:
        auto mask=this->match_really_occupied(&g,last);
        while(mask){
          auto n=unchecked_countr_zero(mask);
-          if(!f(p+n))return false;
+          if(BOOST_LIKELY(is_really_occupied(&g,n))&&!f(p+n))return false;
          mask&=mask-1;
        }
        return true;
@@ -0,0 +1,30 @@
+// Copyright (C) 2023 Braden Ganetsky
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_UNORDERED_DETAIL_THROW_EXCEPTION_HPP
+#define BOOST_UNORDERED_DETAIL_THROW_EXCEPTION_HPP
+
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#pragma once
+#endif
+
+#include <boost/throw_exception.hpp>
+#include <stdexcept>
+
+namespace boost {
+  namespace unordered {
+    namespace detail {
+
+      BOOST_NOINLINE BOOST_NORETURN inline void throw_out_of_range(
+        char const* message)
+      {
+        boost::throw_exception(std::out_of_range(message));
+      }
+
+    } // namespace detail
+  } // namespace unordered
+} // namespace boost
+
+#endif // BOOST_UNORDERED_DETAIL_THROW_EXCEPTION_HPP
@@ -14,12 +14,12 @@
 #include <boost/unordered/detail/foa/flat_map_types.hpp>
 #include <boost/unordered/detail/foa/table.hpp>
 #include <boost/unordered/detail/serialize_container.hpp>
+#include <boost/unordered/detail/throw_exception.hpp>
 #include <boost/unordered/detail/type_traits.hpp>
 #include <boost/unordered/unordered_flat_map_fwd.hpp>

 #include <boost/core/allocator_access.hpp>
 #include <boost/container_hash/hash.hpp>
-#include <boost/throw_exception.hpp>

 #include <initializer_list>
 #include <iterator>
@@ -459,8 +459,8 @@ namespace boost {
        // TODO: someday refactor this to conditionally serialize the key and
        // include it in the error message
        //
-        boost::throw_exception(
-          std::out_of_range("key was not found in unordered_flat_map"));
+        boost::unordered::detail::throw_out_of_range(
+          "key was not found in unordered_flat_map");
      }

      mapped_type const& at(key_type const& key) const
@@ -469,8 +469,8 @@ namespace boost {
        if (pos != table_.end()) {
          return pos->second;
        }
-        boost::throw_exception(
-          std::out_of_range("key was not found in unordered_flat_map"));
+        boost::unordered::detail::throw_out_of_range(
+          "key was not found in unordered_flat_map");
      }

      template <class K>
@@ -483,8 +483,8 @@ namespace boost {
        if (pos != table_.end()) {
          return pos->second;
        }
-        boost::throw_exception(
-          std::out_of_range("key was not found in unordered_flat_map"));
+        boost::unordered::detail::throw_out_of_range(
+          "key was not found in unordered_flat_map");
      }

      template <class K>
@@ -497,8 +497,8 @@ namespace boost {
        if (pos != table_.end()) {
          return pos->second;
        }
-        boost::throw_exception(
-          std::out_of_range("key was not found in unordered_flat_map"));
+        boost::unordered::detail::throw_out_of_range(
+          "key was not found in unordered_flat_map");
      }

      BOOST_FORCEINLINE mapped_type& operator[](key_type const& key)
@@ -39,10 +39,6 @@ namespace boost {
  } // namespace unordered

  using boost::unordered::unordered_flat_map;
-
-  using boost::unordered::swap;
-  using boost::unordered::operator==;
-  using boost::unordered::operator!=;
 } // namespace boost

 #endif
@@ -39,10 +39,6 @@ namespace boost {
  } // namespace unordered

  using boost::unordered::unordered_flat_set;
-
-  using boost::unordered::swap;
-  using boost::unordered::operator==;
-  using boost::unordered::operator!=;
 } // namespace boost

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

 #include <boost/unordered/detail/map.hpp>
 #include <boost/unordered/detail/serialize_fca_container.hpp>
+#include <boost/unordered/detail/throw_exception.hpp>
 #include <boost/unordered/detail/type_traits.hpp>

 #include <boost/container_hash/hash.hpp>
@@ -1586,8 +1587,8 @@ namespace boost {
          return p->value().second;
      }

-      boost::throw_exception(
-        std::out_of_range("Unable to find key in unordered_map."));
+      boost::unordered::detail::throw_out_of_range(
+        "Unable to find key in unordered_map.");
    }

    template <class K, class T, class H, class P, class A>
@@ -1602,8 +1603,8 @@ namespace boost {
          return p->value().second;
      }

-      boost::throw_exception(
-        std::out_of_range("Unable to find key in unordered_map."));
+      boost::unordered::detail::throw_out_of_range(
+        "Unable to find key in unordered_map.");
    }

    template <class K, class T, class H, class P, class A>
@@ -1620,8 +1621,8 @@ namespace boost {
          return p->value().second;
      }

-      boost::throw_exception(
-        std::out_of_range("Unable to find key in unordered_map."));
+      boost::unordered::detail::throw_out_of_range(
+        "Unable to find key in unordered_map.");
    }

    template <class K, class T, class H, class P, class A>
@@ -1638,8 +1639,8 @@ namespace boost {
          return p->value().second;
      }

-      boost::throw_exception(
-        std::out_of_range("Unable to find key in unordered_map."));
+      boost::unordered::detail::throw_out_of_range(
+        "Unable to find key in unordered_map.");
    }

    template <class K, class T, class H, class P, class A>
@@ -60,11 +60,8 @@ namespace boost {
    template <class Iter, class NodeType> struct insert_return_type_map;
  } // namespace unordered

-  using boost::unordered::swap;
  using boost::unordered::unordered_map;
  using boost::unordered::unordered_multimap;
-  using boost::unordered::operator==;
-  using boost::unordered::operator!=;
 } // namespace boost

 #endif
--- a/Show More
+++ b/Show More
Author	SHA1	Message	Date
joaquintides	d689613172	protected visitation against spurious insertion sentinels	2023-12-27 12:32:31 +01:00
joaquintides	8365ccb78a	fixed is_reserved	2023-12-26 18:11:22 +01:00
joaquintides	0a6da6979f	protected for_all_elements(_while) against transient slot reserves	2023-12-26 09:53:29 +01:00
joaquintides	31c33faf57	added almost-latch-free insertion for regular-layout group_type	2023-12-25 20:25:34 +01:00
Braden Ganetsky	0d2751c5e1	Extract `at()`'s throw_exception calls into noinline function (#223 ) * Create function `detail::throw_out_of_range()` to make `at()` more inlineable * Replace `boost::throw_exception()` with `detail::throw_out_of_range()`	2023-12-19 17:08:08 +01:00
joaquintides	f493603f5c	[skip ci] editorial	2023-12-01 12:22:48 +01:00
Peter Dimov	74ca1b0e74	Update test/CMakeLists.txt	2023-11-30 17:54:53 +02:00
Peter Dimov	7b16324869	Regenerate CMakeLists.txt	2023-11-30 17:40:41 +02:00
joaquintides	6680e86b38	[skip ci] typo	2023-11-25 09:49:24 +01:00
joaquintides	3e76b1cf68	[skip ci] beautified some badges	2023-11-19 18:45:21 +01:00
joaquintides	22f29718e4	changed drone badges	2023-11-19 09:48:38 +01:00
joaquintides	f7c7f8fdd2	[skip ci] added Drone badges	2023-11-18 11:30:47 +01:00
joaquintides	7fd94b9df7	Fix/bucket iterator indirection operator (#220 rewrite) (#221 ) * Add tests for member of pointer operator for bucket iterators * Fix erroneous conversion from node* to value_type* in bucket iterators Originally caughy by vslashg from PR https://github.com/boostorg/unordered/pull/220 * Update change log * Update GHA config to use containers in C++20 builds for clang-14 as it's incompatible with libstdc++-13 * fixed Python installation problem * tried variation of former fix * tried another variation of former fix * tried yet another variation * editorial --------- Co-authored-by: Christian Mazakas <christian.mazakas@gmail.com>	2023-11-17 08:51:40 +01:00
joaquintides	1c0e54ee3e	updated boost::unordered_[multi]set and boost::unordered_(flat\|node)_map benchmarks	2023-11-06 18:20:36 +01:00
joaquintides	329022b23c	removed unnecesary picture tags README.md	2023-10-31 09:38:53 +01:00
joaquintides	47f5be3a3f	typo	2023-10-31 08:59:21 +01:00
joaquintides	de2ac0ce33	revamped README.md	2023-10-29 18:46:51 +01:00
joaquintides	42df4f2749	removed lifting of swap and ==/!= operations	2023-10-22 20:16:05 +02:00
joaquintides	dbe93c765c	asserted allocator equality on unordered_node_(map\|set)::merge and updated docs	2023-10-21 12:35:59 +02:00
joaquintides	ea4fc5e66d	fine-tuned element prefetching in unprotected_bulk_visit	2023-10-18 18:20:22 +02:00