diff -Nru robin-map-1.0.1/CMakeLists.txt robin-map-1.2.1/CMakeLists.txt --- robin-map-1.0.1/CMakeLists.txt 2022-04-05 17:54:26.000000000 +0000 +++ robin-map-1.2.1/CMakeLists.txt 2023-01-05 23:07:42.000000000 +0000 @@ -1,6 +1,6 @@ cmake_minimum_required(VERSION 3.1) -project(tsl-robin-map VERSION 1.0.1 LANGUAGES CXX) +project(tsl-robin-map VERSION 1.2.1 LANGUAGES CXX) include(GNUInstallDirs) @@ -28,8 +28,13 @@ +set(IS_SUBPROJECT TRUE) +if(CMAKE_SOURCE_DIR STREQUAL PROJECT_SOURCE_DIR) + set(IS_SUBPROJECT FALSE) +endif() + # Installation (only compatible with CMake version >= 3.3) -if(${CMAKE_VERSION} VERSION_GREATER "3.2") +if(NOT IS_SUBPROJECT AND ${CMAKE_VERSION} VERSION_GREATER "3.2") include(CMakePackageConfigHelpers) ## Install include directory and potential natvis file diff -Nru robin-map-1.0.1/debian/changelog robin-map-1.2.1/debian/changelog --- robin-map-1.0.1/debian/changelog 2022-04-15 21:15:46.000000000 +0000 +++ robin-map-1.2.1/debian/changelog 2023-01-21 17:58:19.000000000 +0000 @@ -1,3 +1,10 @@ +robin-map (1.2.1-1) unstable; urgency=medium + + * New upstream release + * debian/control: S-V bump 4.6.0 -> 4.6.2 (no changes needed) + + -- Matteo F. Vescovi Sat, 21 Jan 2023 18:58:19 +0100 + robin-map (1.0.1-1) unstable; urgency=medium * New upstream release @@ -6,6 +13,13 @@ -- Matteo F. Vescovi Fri, 15 Apr 2022 23:15:46 +0200 +robin-map (0.6.3-2) UNRELEASED; urgency=low + + * Set upstream metadata fields: Bug-Database, Bug-Submit, Repository, + Repository-Browse. + + -- Debian Janitor Sat, 25 Jul 2020 03:57:47 -0000 + robin-map (0.6.3-1) unstable; urgency=medium * New upstream release diff -Nru robin-map-1.0.1/debian/control robin-map-1.2.1/debian/control --- robin-map-1.0.1/debian/control 2022-04-15 21:14:07.000000000 +0000 +++ robin-map-1.2.1/debian/control 2023-01-21 17:57:31.000000000 +0000 @@ -5,7 +5,7 @@ Build-Depends: cmake, debhelper-compat (= 13) -Standards-Version: 4.6.0 +Standards-Version: 4.6.2 Rules-Requires-Root: no Homepage: https://github.com/Tessil/robin-map Vcs-Git: https://salsa.debian.org/debian/robin-map.git diff -Nru robin-map-1.0.1/debian/upstream/metadata robin-map-1.2.1/debian/upstream/metadata --- robin-map-1.0.1/debian/upstream/metadata 1970-01-01 00:00:00.000000000 +0000 +++ robin-map-1.2.1/debian/upstream/metadata 2023-01-21 17:52:47.000000000 +0000 @@ -0,0 +1,5 @@ +--- +Bug-Database: https://github.com/Tessil/robin-map/issues +Bug-Submit: https://github.com/Tessil/robin-map/issues/new +Repository: https://github.com/Tessil/robin-map.git +Repository-Browse: https://github.com/Tessil/robin-map diff -Nru robin-map-1.0.1/include/tsl/robin_growth_policy.h robin-map-1.2.1/include/tsl/robin_growth_policy.h --- robin-map-1.0.1/include/tsl/robin_growth_policy.h 2022-04-05 17:54:26.000000000 +0000 +++ robin-map-1.2.1/include/tsl/robin_growth_policy.h 2023-01-05 23:07:42.000000000 +0000 @@ -51,15 +51,15 @@ #define TSL_RH_THROW_OR_TERMINATE(ex, msg) throw ex(msg) #else #define TSL_RH_NO_EXCEPTIONS -#ifdef NDEBUG -#define TSL_RH_THROW_OR_TERMINATE(ex, msg) std::terminate() -#else +#ifdef TSL_DEBUG #include #define TSL_RH_THROW_OR_TERMINATE(ex, msg) \ do { \ std::cerr << msg << std::endl; \ std::terminate(); \ } while (0) +#else +#define TSL_RH_THROW_OR_TERMINATE(ex, msg) std::terminate() #endif #endif diff -Nru robin-map-1.0.1/include/tsl/robin_hash.h robin-map-1.2.1/include/tsl/robin_hash.h --- robin-map-1.0.1/include/tsl/robin_hash.h 2022-04-05 17:54:26.000000000 +0000 +++ robin-map-1.2.1/include/tsl/robin_hash.h 2023-01-05 23:07:42.000000000 +0000 @@ -33,6 +33,7 @@ #include #include #include +#include #include #include #include @@ -195,6 +196,7 @@ value_type(other.value()); m_dist_from_ideal_bucket = other.m_dist_from_ideal_bucket; } + tsl_rh_assert(empty() == other.empty()); } /** @@ -212,6 +214,7 @@ value_type(std::move(other.value())); m_dist_from_ideal_bucket = other.m_dist_from_ideal_bucket; } + tsl_rh_assert(empty() == other.empty()); } bucket_entry& operator=(const bucket_entry& other) noexcept( @@ -249,12 +252,22 @@ value_type& value() noexcept { tsl_rh_assert(!empty()); +#if defined(__cplusplus) && __cplusplus >= 201703L + return *std::launder( + reinterpret_cast(std::addressof(m_value))); +#else return *reinterpret_cast(std::addressof(m_value)); +#endif } const value_type& value() const noexcept { tsl_rh_assert(!empty()); +#if defined(__cplusplus) && __cplusplus >= 201703L + return *std::launder( + reinterpret_cast(std::addressof(m_value))); +#else return *reinterpret_cast(std::addressof(m_value)); +#endif } distance_type dist_from_ideal_bucket() const noexcept { @@ -283,6 +296,7 @@ void swap_with_value_in_bucket(distance_type& dist_from_ideal_bucket, truncated_hash_type& hash, value_type& value) { tsl_rh_assert(!empty()); + tsl_rh_assert(dist_from_ideal_bucket > m_dist_from_ideal_bucket); using std::swap; swap(value, this->value()); @@ -310,19 +324,16 @@ public: static const distance_type EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1; - static const distance_type DIST_FROM_IDEAL_BUCKET_LIMIT = 4096; + static const distance_type DIST_FROM_IDEAL_BUCKET_LIMIT = 8192; static_assert(DIST_FROM_IDEAL_BUCKET_LIMIT <= std::numeric_limits::max() - 1, "DIST_FROM_IDEAL_BUCKET_LIMIT must be <= " "std::numeric_limits::max() - 1."); private: - using storage = typename std::aligned_storage::type; - distance_type m_dist_from_ideal_bucket; bool m_last_bucket; - storage m_value; + alignas(value_type) unsigned char m_value[sizeof(value_type)]; }; /** @@ -536,23 +547,18 @@ : Hash(hash), KeyEqual(equal), GrowthPolicy(bucket_count), - m_buckets_data( - [&]() { - if (bucket_count > max_bucket_count()) { - TSL_RH_THROW_OR_TERMINATE( - std::length_error, - "The map exceeds its maximum bucket count."); - } - - return bucket_count; - }(), - alloc), + m_buckets_data(bucket_count, alloc), m_buckets(m_buckets_data.empty() ? static_empty_bucket_ptr() : m_buckets_data.data()), m_bucket_count(bucket_count), m_nb_elements(0), m_grow_on_next_insert(false), m_try_shrink_on_next_insert(false) { + if (bucket_count > max_bucket_count()) { + TSL_RH_THROW_OR_TERMINATE(std::length_error, + "The map exceeds its maximum bucket count."); + } + if (m_bucket_count > 0) { tsl_rh_assert(!m_buckets_data.empty()); m_buckets_data.back().set_as_last_bucket(); @@ -664,7 +670,7 @@ robin_hash& operator=(robin_hash&& other) { other.swap(*this); - other.clear(); + other.clear_and_shrink(); return *this; } @@ -1073,11 +1079,12 @@ m_max_load_factor = clamp(ml, float(MINIMUM_MAX_LOAD_FACTOR), float(MAXIMUM_MAX_LOAD_FACTOR)); m_load_threshold = size_type(float(bucket_count()) * m_max_load_factor); + tsl_rh_assert(bucket_count() == 0 || m_load_threshold < bucket_count()); } void rehash(size_type count_) { count_ = std::max(count_, - size_type(std::ceil(float(size()) / max_load_factor()))); + size_type(std::ceil(float(size()) / max_load_factor()))); rehash_impl(count_); } @@ -1224,7 +1231,7 @@ dist_from_ideal_bucket++; } - if (rehash_on_extreme_load()) { + while (rehash_on_extreme_load(dist_from_ideal_bucket)) { ibucket = bucket_for_hash(hash); dist_from_ideal_bucket = 0; @@ -1276,6 +1283,8 @@ void insert_value_impl(std::size_t ibucket, distance_type dist_from_ideal_bucket, truncated_hash_type hash, value_type& value) { + tsl_rh_assert(dist_from_ideal_bucket > + m_buckets[ibucket].dist_from_ideal_bucket()); m_buckets[ibucket].swap_with_value_in_bucket(dist_from_ideal_bucket, hash, value); ibucket = next_bucket(ibucket); @@ -1284,7 +1293,7 @@ while (!m_buckets[ibucket].empty()) { if (dist_from_ideal_bucket > m_buckets[ibucket].dist_from_ideal_bucket()) { - if (dist_from_ideal_bucket >= + if (dist_from_ideal_bucket > bucket_entry::DIST_FROM_IDEAL_BUCKET_LIMIT) { /** * The number of probes is really high, rehash the map on the next @@ -1309,6 +1318,7 @@ robin_hash new_table(count_, static_cast(*this), static_cast(*this), get_allocator(), m_min_load_factor, m_max_load_factor); + tsl_rh_assert(size() <= new_table.m_load_threshold); const bool use_stored_hash = USE_STORED_HASH_ON_REHASH(new_table.bucket_count()); @@ -1369,8 +1379,11 @@ * * Return true if the table has been rehashed. */ - bool rehash_on_extreme_load() { - if (m_grow_on_next_insert || size() >= m_load_threshold) { + bool rehash_on_extreme_load(distance_type curr_dist_from_ideal_bucket) { + if (m_grow_on_next_insert || + curr_dist_from_ideal_bucket > + bucket_entry::DIST_FROM_IDEAL_BUCKET_LIMIT || + size() >= m_load_threshold) { rehash_impl(GrowthPolicy::next_bucket_count()); m_grow_on_next_insert = false; @@ -1576,6 +1589,7 @@ */ bucket_entry* static_empty_bucket_ptr() noexcept { static bucket_entry empty_bucket(true); + tsl_rh_assert(empty_bucket.empty()); return &empty_bucket; } diff -Nru robin-map-1.0.1/include/tsl/robin_map.h robin-map-1.2.1/include/tsl/robin_map.h --- robin-map-1.0.1/include/tsl/robin_map.h 2022-04-05 17:54:26.000000000 +0000 +++ robin-map-1.2.1/include/tsl/robin_map.h 2023-01-05 23:07:42.000000000 +0000 @@ -97,8 +97,8 @@ public: using key_type = Key; - const key_type& operator()(const std::pair& key_value) const - noexcept { + const key_type& operator()( + const std::pair& key_value) const noexcept { return key_value.first; } @@ -111,8 +111,8 @@ public: using value_type = T; - const value_type& operator()(const std::pair& key_value) const - noexcept { + const value_type& operator()( + const std::pair& key_value) const noexcept { return key_value.second; } diff -Nru robin-map-1.0.1/README.md robin-map-1.2.1/README.md --- robin-map-1.0.1/README.md 2022-04-05 17:54:26.000000000 +0000 +++ robin-map-1.2.1/README.md 2023-01-05 23:07:42.000000000 +0000 @@ -90,7 +90,7 @@ If the project has been installed through `make install`, you can also use `find_package(tsl-robin-map REQUIRED)` instead of `add_subdirectory`. -The library is available in [vcpkg](https://github.com/Microsoft/vcpkg/tree/master/ports/robin-map) and [conan](https://bintray.com/tessil/tsl/tsl-robin-map%3Atessil). It's also present in [Debian](https://packages.debian.org/buster/robin-map-dev), [Ubuntu](https://packages.ubuntu.com/disco/robin-map-dev) and [Fedora](https://apps.fedoraproject.org/packages/robin-map-devel) package repositories. +The library is available in [vcpkg](https://github.com/Microsoft/vcpkg/tree/master/ports/robin-map) and [conan](https://conan.io/center/tsl-robin-map). It's also present in [Debian](https://packages.debian.org/buster/robin-map-dev), [Ubuntu](https://packages.ubuntu.com/disco/robin-map-dev) and [Fedora](https://apps.fedoraproject.org/packages/robin-map-devel) package repositories. The code should work with any C++11 standard-compliant compiler and has been tested with GCC 4.8.4, Clang 3.5.0 and Visual Studio 2015. diff -Nru robin-map-1.0.1/tests/robin_map_tests.cpp robin-map-1.2.1/tests/robin_map_tests.cpp --- robin-map-1.0.1/tests/robin_map_tests.cpp 2022-04-05 17:54:26.000000000 +0000 +++ robin-map-1.2.1/tests/robin_map_tests.cpp 2023-01-05 23:07:42.000000000 +0000 @@ -139,10 +139,9 @@ } BOOST_AUTO_TEST_CASE(test_rehash_0) { - tsl::robin_map, - std::equal_to, - std::allocator>, - true> map; + tsl::robin_map, std::equal_to, + std::allocator>, true> + map; map.rehash(0); } @@ -745,41 +744,44 @@ /** * constructor */ + BOOST_AUTO_TEST_CASE(test_extreme_bucket_count_value_construction) { - TSL_RH_CHECK_THROW( + // std::bad_alloc or std::length_error will be thrown depending on the + // platform overcommit + TSL_RH_CHECK_THROW_EITHER( (tsl::robin_map, std::equal_to, std::allocator>, false, tsl::rh::power_of_two_growth_policy<2>>( std::numeric_limits::max())), - std::length_error); + std::bad_alloc, std::length_error); - TSL_RH_CHECK_THROW( + TSL_RH_CHECK_THROW_EITHER( (tsl::robin_map, std::equal_to, std::allocator>, false, tsl::rh::power_of_two_growth_policy<2>>( std::numeric_limits::max() / 2 + 1)), - std::length_error); + std::bad_alloc, std::length_error); - TSL_RH_CHECK_THROW( + TSL_RH_CHECK_THROW_EITHER( (tsl::robin_map, std::equal_to, std::allocator>, false, tsl::rh::prime_growth_policy>( std::numeric_limits::max())), - std::length_error); + std::bad_alloc, std::length_error); - TSL_RH_CHECK_THROW( + TSL_RH_CHECK_THROW_EITHER( (tsl::robin_map, std::equal_to, std::allocator>, false, tsl::rh::prime_growth_policy>( std::numeric_limits::max() / 2)), - std::length_error); + std::bad_alloc, std::length_error); - TSL_RH_CHECK_THROW( + TSL_RH_CHECK_THROW_EITHER( (tsl::robin_map, std::equal_to, std::allocator>, false, tsl::rh::mod_growth_policy<>>( std::numeric_limits::max())), - std::length_error); + std::bad_alloc, std::length_error); } BOOST_AUTO_TEST_CASE(test_range_construct) { diff -Nru robin-map-1.0.1/tests/utils.h robin-map-1.2.1/tests/utils.h --- robin-map-1.0.1/tests/utils.h 2022-04-05 17:54:26.000000000 +0000 +++ robin-map-1.2.1/tests/utils.h 2023-01-05 23:07:42.000000000 +0000 @@ -36,8 +36,18 @@ #ifdef TSL_RH_NO_EXCEPTIONS #define TSL_RH_CHECK_THROW(S, E) +#define TSL_RH_CHECK_THROW_EITHER(S, E1, E2) #else #define TSL_RH_CHECK_THROW(S, E) BOOST_CHECK_THROW(S, E) +#define TSL_RH_CHECK_THROW_EITHER(S, E1, E2) \ + do { \ + try { \ + S; \ + BOOST_CHECK(false); \ + } catch (const E1&) { \ + } catch (const E2&) { \ + } \ + } while (0) #endif template