Script 'mail_helper' called by obssrc Hello community, here is the log from the commit of package robin-map for openSUSE:Factory checked in at 2021-03-02 12:32:31 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Comparing /work/SRC/openSUSE:Factory/robin-map (Old) and /work/SRC/openSUSE:Factory/.robin-map.new.2378 (New) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "robin-map" Tue Mar 2 12:32:31 2021 rev:2 rq:875631 version:0.6.3 Changes: -------- --- /work/SRC/openSUSE:Factory/robin-map/robin-map.changes 2020-04-21 13:13:22.205135725 +0200 +++ /work/SRC/openSUSE:Factory/.robin-map.new.2378/robin-map.changes 2021-03-02 12:44:46.924320526 +0100 @@ -1,0 +2,18 @@ +Sat Feb 27 14:07:52 UTC 2021 - Antoine Belvire <antoine.belv...@opensuse.org> + +- Update to version 0.6.3: + * Fix gh#Tessil/robin-map#26: Raise the maximum possible size of + the hash table when using the prime_growth_policy on a 64-bit + platform. + * Fix gh#Tessil/robin-map#31: When min_load_factor() > 0, the + clear() method will also reset the bucket_count of the hash + table to 0. + * Fix shrink when min_load_factor is set and a range erase with + end() as last is called. The m_try_skrink_on_next_insert was + not correctly set. + * Fix gh#Tessil/robin-map#33: The value function of a const + iterator can now be called and returns a mutable reference to + the underlying value_type. +- Ran spec-cleaner. + +------------------------------------------------------------------- Old: ---- robin-map-0.6.2.tar.gz New: ---- robin-map-0.6.3.tar.gz ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Other differences: ------------------ ++++++ robin-map.spec ++++++ --- /var/tmp/diff_new_pack.rXPa3G/_old 2021-03-02 12:44:47.592321104 +0100 +++ /var/tmp/diff_new_pack.rXPa3G/_new 2021-03-02 12:44:47.596321107 +0100 @@ -1,7 +1,7 @@ # # spec file for package robin-map # -# Copyright (c) 2020 SUSE LLC +# Copyright (c) 2021 SUSE LLC # # All modifications and additions to the file contributed by third parties # remain the property of their copyright owners, unless otherwise agreed @@ -17,17 +17,15 @@ Name: robin-map -Version: 0.6.2 +Version: 0.6.3 Release: 0 Summary: C++ implementation of a fast hash map and hash set using robin hood hashing License: MIT URL: https://github.com/Tessil/robin-map Source0: https://github.com/Tessil/%{name}/archive/v%{version}/%{name}-%{version}.tar.gz - -BuildArch: noarch - BuildRequires: cmake BuildRequires: gcc-c++ +BuildArch: noarch %description The robin-map library is a C++ implementation of a fast hash map and hash set @@ -37,7 +35,6 @@ *** This is a header only library. *** The package you want is %{name}-devel. - %package devel Summary: %{summary} @@ -58,21 +55,17 @@ your use case (useful if you are a bit lost with the multiple hash tables implementations in the tsl namespace). - %prep %autosetup -p1 # rpmlint complains about the downloaded file's permissions -chmod 0644 %{S:0} - +chmod 0644 %{SOURCE0} %build %cmake - %install %cmake_install - %files devel %license LICENSE %doc README.md @@ -80,5 +73,4 @@ %{_datadir}/cmake/tsl-%{name}/*.cmake %{_includedir}/tsl/ - %changelog ++++++ robin-map-0.6.2.tar.gz -> robin-map-0.6.3.tar.gz ++++++ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-0.6.2/.codecov.yml new/robin-map-0.6.3/.codecov.yml --- old/robin-map-0.6.2/.codecov.yml 2019-09-25 22:20:01.000000000 +0200 +++ new/robin-map-0.6.3/.codecov.yml 2020-06-22 07:03:29.000000000 +0200 @@ -1 +1,5 @@ comment: off +coverage: + status: + project: off + patch: off diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-0.6.2/CMakeLists.txt new/robin-map-0.6.3/CMakeLists.txt --- old/robin-map-0.6.2/CMakeLists.txt 2019-09-25 22:20:01.000000000 +0200 +++ new/robin-map-0.6.3/CMakeLists.txt 2020-06-22 07:03:29.000000000 +0200 @@ -2,7 +2,7 @@ include(GNUInstallDirs) -project(tsl-robin-map VERSION 0.6.2) +project(tsl-robin-map VERSION 0.6.3) add_library(robin_map INTERFACE) # Use tsl::robin_map as target, more consistent with other libraries conventions (Boost, Qt, ...) diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-0.6.2/LICENSE new/robin-map-0.6.3/LICENSE --- old/robin-map-0.6.2/LICENSE 2019-09-25 22:20:01.000000000 +0200 +++ new/robin-map-0.6.3/LICENSE 2020-06-22 07:03:29.000000000 +0200 @@ -1,6 +1,6 @@ MIT License -Copyright (c) 2017 Tessil +Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tes...@gmx.com> Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-0.6.2/include/tsl/robin_growth_policy.h new/robin-map-0.6.3/include/tsl/robin_growth_policy.h --- old/robin-map-0.6.2/include/tsl/robin_growth_policy.h 2019-09-25 22:20:01.000000000 +0200 +++ new/robin-map-0.6.3/include/tsl/robin_growth_policy.h 2020-06-22 07:03:29.000000000 +0200 @@ -1,7 +1,7 @@ /** * MIT License * - * Copyright (c) 2017 Tessil + * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tes...@gmx.com> * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal @@ -30,6 +30,7 @@ #include <climits> #include <cmath> #include <cstddef> +#include <cstdint> #include <iterator> #include <limits> #include <ratio> @@ -87,7 +88,7 @@ */ explicit power_of_two_growth_policy(std::size_t& min_bucket_count_in_out) { if(min_bucket_count_in_out > max_bucket_count()) { - TSL_RH_THROW_OR_TERMINATE(std::length_error, "The hash table exceeds its maxmimum size."); + TSL_RH_THROW_OR_TERMINATE(std::length_error, "The hash table exceeds its maximum size."); } if(min_bucket_count_in_out > 0) { @@ -112,7 +113,7 @@ */ std::size_t next_bucket_count() const { if((m_mask + 1) > max_bucket_count() / GrowthFactor) { - TSL_RH_THROW_OR_TERMINATE(std::length_error, "The hash table exceeds its maxmimum size."); + TSL_RH_THROW_OR_TERMINATE(std::length_error, "The hash table exceeds its maximum size."); } return (m_mask + 1) * GrowthFactor; @@ -172,7 +173,7 @@ public: explicit mod_growth_policy(std::size_t& min_bucket_count_in_out) { if(min_bucket_count_in_out > max_bucket_count()) { - TSL_RH_THROW_OR_TERMINATE(std::length_error, "The hash table exceeds its maxmimum size."); + TSL_RH_THROW_OR_TERMINATE(std::length_error, "The hash table exceeds its maximum size."); } if(min_bucket_count_in_out > 0) { @@ -189,12 +190,12 @@ std::size_t next_bucket_count() const { if(m_mod == max_bucket_count()) { - TSL_RH_THROW_OR_TERMINATE(std::length_error, "The hash table exceeds its maxmimum size."); + TSL_RH_THROW_OR_TERMINATE(std::length_error, "The hash table exceeds its maximum size."); } const double next_bucket_count = std::ceil(double(m_mod) * REHASH_SIZE_MULTIPLICATION_FACTOR); if(!std::isnormal(next_bucket_count)) { - TSL_RH_THROW_OR_TERMINATE(std::length_error, "The hash table exceeds its maxmimum size."); + TSL_RH_THROW_OR_TERMINATE(std::length_error, "The hash table exceeds its maximum size."); } if(next_bucket_count > double(max_bucket_count())) { @@ -229,11 +230,26 @@ namespace detail { -static constexpr const std::array<std::size_t, 40> PRIMES = {{ - 1ul, 5ul, 17ul, 29ul, 37ul, 53ul, 67ul, 79ul, 97ul, 131ul, 193ul, 257ul, 389ul, 521ul, 769ul, 1031ul, - 1543ul, 2053ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, - 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul, - 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul +#if SIZE_MAX >= ULLONG_MAX +#define TSL_RH_NB_PRIMES 51 +#elif SIZE_MAX >= ULONG_MAX +#define TSL_RH_NB_PRIMES 40 +#else +#define TSL_RH_NB_PRIMES 23 +#endif + +static constexpr const std::array<std::size_t, TSL_RH_NB_PRIMES> PRIMES = {{ + 1u, 5u, 17u, 29u, 37u, 53u, 67u, 79u, 97u, 131u, 193u, 257u, 389u, 521u, 769u, 1031u, + 1543u, 2053u, 3079u, 6151u, 12289u, 24593u, 49157u, +#if SIZE_MAX >= ULONG_MAX + 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, + 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 1610612741ul, + 3221225473ul, 4294967291ul, +#endif +#if SIZE_MAX >= ULLONG_MAX + 6442450939ull, 12884901893ull, 25769803751ull, 51539607551ull, 103079215111ull, 206158430209ull, + 412316860441ull, 824633720831ull, 1649267441651ull, 3298534883309ull, 6597069766657ull, +#endif }}; template<unsigned int IPrime> @@ -241,11 +257,18 @@ // MOD_PRIME[iprime](hash) returns hash % PRIMES[iprime]. This table allows for faster modulo as the // compiler can optimize the modulo code better with a constant known at the compilation. -static constexpr const std::array<std::size_t(*)(std::size_t), 40> MOD_PRIME = {{ +static constexpr const std::array<std::size_t(*)(std::size_t), TSL_RH_NB_PRIMES> MOD_PRIME = {{ &mod<0>, &mod<1>, &mod<2>, &mod<3>, &mod<4>, &mod<5>, &mod<6>, &mod<7>, &mod<8>, &mod<9>, &mod<10>, &mod<11>, &mod<12>, &mod<13>, &mod<14>, &mod<15>, &mod<16>, &mod<17>, &mod<18>, &mod<19>, &mod<20>, - &mod<21>, &mod<22>, &mod<23>, &mod<24>, &mod<25>, &mod<26>, &mod<27>, &mod<28>, &mod<29>, &mod<30>, - &mod<31>, &mod<32>, &mod<33>, &mod<34>, &mod<35>, &mod<36>, &mod<37> , &mod<38>, &mod<39> + &mod<21>, &mod<22>, +#if SIZE_MAX >= ULONG_MAX + &mod<23>, &mod<24>, &mod<25>, &mod<26>, &mod<27>, &mod<28>, &mod<29>, &mod<30>, &mod<31>, &mod<32>, + &mod<33>, &mod<34>, &mod<35>, &mod<36>, &mod<37> , &mod<38>, &mod<39>, +#endif +#if SIZE_MAX >= ULLONG_MAX + &mod<40>, &mod<41>, &mod<42>, &mod<43>, &mod<44>, &mod<45>, &mod<46>, &mod<47>, &mod<48>, &mod<49>, + &mod<50>, +#endif }}; } @@ -272,7 +295,7 @@ * Due to the constant variable in the modulo the compiler is able to optimize the operation * by a series of multiplications, substractions and shifts. * - * The 'hash % 5' could become something like 'hash - (hash * 0xCCCCCCCD) >> 34) * 5' in a 64 bits environement. + * The 'hash % 5' could become something like 'hash - (hash * 0xCCCCCCCD) >> 34) * 5' in a 64 bits environment. */ class prime_growth_policy { public: @@ -280,7 +303,7 @@ auto it_prime = std::lower_bound(detail::PRIMES.begin(), detail::PRIMES.end(), min_bucket_count_in_out); if(it_prime == detail::PRIMES.end()) { - TSL_RH_THROW_OR_TERMINATE(std::length_error, "The hash table exceeds its maxmimum size."); + TSL_RH_THROW_OR_TERMINATE(std::length_error, "The hash table exceeds its maximum size."); } m_iprime = static_cast<unsigned int>(std::distance(detail::PRIMES.begin(), it_prime)); @@ -298,7 +321,7 @@ std::size_t next_bucket_count() const { if(m_iprime + 1 >= detail::PRIMES.size()) { - TSL_RH_THROW_OR_TERMINATE(std::length_error, "The hash table exceeds its maxmimum size."); + TSL_RH_THROW_OR_TERMINATE(std::length_error, "The hash table exceeds its maximum size."); } return detail::PRIMES[m_iprime + 1]; diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-0.6.2/include/tsl/robin_hash.h new/robin-map-0.6.3/include/tsl/robin_hash.h --- old/robin-map-0.6.2/include/tsl/robin_hash.h 2019-09-25 22:20:01.000000000 +0200 +++ new/robin-map-0.6.3/include/tsl/robin_hash.h 2020-06-22 07:03:29.000000000 +0200 @@ -1,7 +1,7 @@ /** * MIT License * - * Copyright (c) 2017 Tessil + * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tes...@gmx.com> * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal @@ -144,7 +144,7 @@ * iterator of the hash table). * - If `StoreHash` is true, 32 bits of the hash of the value, if any, are also stored in the bucket. * If the size of the hash is more than 32 bits, it is truncated. We don't store the full hash - * as storing the hash is a potential opportunity to use the unused space due to the alignement + * as storing the hash is a potential opportunity to use the unused space due to the alignment * of the bucket_entry structure. We can thus potentially store the hash without any extra space * (which would not be possible with 64 bits of the hash). */ @@ -381,7 +381,7 @@ ); /** - * Only use the stored hash on lookup if we are explictly asked. We are not sure how slow + * Only use the stored hash on lookup if we are explicitly asked. We are not sure how slow * the KeyEqual operation is. An extra comparison may slow things down with a fast KeyEqual. */ static constexpr bool USE_STORED_HASH_ON_LOOKUP = StoreHash; @@ -468,7 +468,7 @@ } template<class U = ValueSelect, typename std::enable_if<has_mapped_type<U>::value && !IsConst>::type* = nullptr> - typename U::value_type& value() { + typename U::value_type& value() const { return U()(m_bucket->value()); } @@ -539,7 +539,7 @@ m_bucket_count(bucket_count), m_nb_elements(0), m_grow_on_next_insert(false), - m_try_skrink_on_next_insert(false) + m_try_shrink_on_next_insert(false) { if(m_bucket_count > 0) { tsl_rh_assert(!m_buckets_data.empty()); @@ -572,10 +572,10 @@ m_bucket_count(bucket_count), m_nb_elements(0), m_grow_on_next_insert(false), - m_try_skrink_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 maxmimum bucket count."); + TSL_RH_THROW_OR_TERMINATE(std::length_error, "The map exceeds its maximum bucket count."); } if(m_bucket_count > 0) { @@ -599,10 +599,10 @@ m_bucket_count(other.m_bucket_count), m_nb_elements(other.m_nb_elements), m_load_threshold(other.m_load_threshold), + m_min_load_factor(other.m_min_load_factor), m_max_load_factor(other.m_max_load_factor), m_grow_on_next_insert(other.m_grow_on_next_insert), - m_min_load_factor(other.m_min_load_factor), - m_try_skrink_on_next_insert(other.m_try_skrink_on_next_insert) + m_try_shrink_on_next_insert(other.m_try_shrink_on_next_insert) { } @@ -618,19 +618,12 @@ m_bucket_count(other.m_bucket_count), m_nb_elements(other.m_nb_elements), m_load_threshold(other.m_load_threshold), + m_min_load_factor(other.m_min_load_factor), m_max_load_factor(other.m_max_load_factor), m_grow_on_next_insert(other.m_grow_on_next_insert), - m_min_load_factor(other.m_min_load_factor), - m_try_skrink_on_next_insert(other.m_try_skrink_on_next_insert) + m_try_shrink_on_next_insert(other.m_try_shrink_on_next_insert) { - other.GrowthPolicy::clear(); - other.m_buckets_data.clear(); - other.m_buckets = static_empty_bucket_ptr(); - other.m_bucket_count = 0; - other.m_nb_elements = 0; - other.m_load_threshold = 0; - other.m_grow_on_next_insert = false; - other.m_try_skrink_on_next_insert = false; + other.clear_and_shrink(); } robin_hash& operator=(const robin_hash& other) { @@ -646,11 +639,11 @@ m_nb_elements = other.m_nb_elements; m_load_threshold = other.m_load_threshold; + m_min_load_factor = other.m_min_load_factor; m_max_load_factor = other.m_max_load_factor; - m_grow_on_next_insert = other.m_grow_on_next_insert; - m_min_load_factor = other.m_min_load_factor; - m_try_skrink_on_next_insert = other.m_try_skrink_on_next_insert; + m_grow_on_next_insert = other.m_grow_on_next_insert; + m_try_shrink_on_next_insert = other.m_try_shrink_on_next_insert; } return *this; @@ -725,12 +718,17 @@ * Modifiers */ void clear() noexcept { - for(auto& bucket: m_buckets_data) { - bucket.clear(); + if(m_min_load_factor > 0.0f) { + clear_and_shrink(); + } + else { + for(auto& bucket: m_buckets_data) { + bucket.clear(); + } + + m_nb_elements = 0; + m_grow_on_next_insert = false; } - - m_nb_elements = 0; - m_grow_on_next_insert = false; } @@ -836,7 +834,7 @@ ++pos; } - m_try_skrink_on_next_insert = true; + m_try_shrink_on_next_insert = true; return pos; } @@ -860,6 +858,7 @@ } if(last_mutable == end()) { + m_try_shrink_on_next_insert = true; return end(); } @@ -895,7 +894,7 @@ ++ito_move_closer_value; } - m_try_skrink_on_next_insert = true; + m_try_shrink_on_next_insert = true; return iterator(m_buckets + ireturn_bucket); } @@ -911,7 +910,7 @@ auto it = find(key, hash); if(it != end()) { erase_from_bucket(it); - m_try_skrink_on_next_insert = true; + m_try_shrink_on_next_insert = true; return 1; } @@ -935,10 +934,10 @@ swap(m_bucket_count, other.m_bucket_count); swap(m_nb_elements, other.m_nb_elements); swap(m_load_threshold, other.m_load_threshold); + swap(m_min_load_factor, other.m_min_load_factor); swap(m_max_load_factor, other.m_max_load_factor); swap(m_grow_on_next_insert, other.m_grow_on_next_insert); - swap(m_min_load_factor, other.m_min_load_factor); - swap(m_try_skrink_on_next_insert, other.m_try_skrink_on_next_insert); + swap(m_try_shrink_on_next_insert, other.m_try_shrink_on_next_insert); } @@ -1322,6 +1321,17 @@ new_table.swap(*this); } + void clear_and_shrink() noexcept { + GrowthPolicy::clear(); + m_buckets_data.clear(); + m_buckets = static_empty_bucket_ptr(); + m_bucket_count = 0; + m_nb_elements = 0; + m_load_threshold = 0; + m_grow_on_next_insert = false; + m_try_shrink_on_next_insert = false; + } + void insert_value_on_rehash(std::size_t ibucket, distance_type dist_from_ideal_bucket, truncated_hash_type hash, value_type&& value) { @@ -1345,7 +1355,7 @@ /** * Grow the table if m_grow_on_next_insert is true or we reached the max_load_factor. - * Shrink the table if m_try_skrink_on_next_insert is true (an erase occured) and + * Shrink the table if m_try_shrink_on_next_insert is true (an erase occurred) and * we're below the min_load_factor. * * Return true if the table has been rehashed. @@ -1358,8 +1368,8 @@ return true; } - if(m_try_skrink_on_next_insert) { - m_try_skrink_on_next_insert = false; + if(m_try_shrink_on_next_insert) { + m_try_shrink_on_next_insert = false; if(m_min_load_factor != 0.0f && load_factor() < m_min_load_factor) { reserve(size() + 1); @@ -1393,7 +1403,7 @@ /** * Return an always valid pointer to an static empty bucket_entry with last_bucket() == true. */ - bucket_entry* static_empty_bucket_ptr() { + bucket_entry* static_empty_bucket_ptr() noexcept { static bucket_entry empty_bucket(true); return &empty_bucket; } @@ -1419,19 +1429,19 @@ size_type m_nb_elements; size_type m_load_threshold; + + float m_min_load_factor; float m_max_load_factor; bool m_grow_on_next_insert; - float m_min_load_factor; - /** * We can't shrink down the map on erase operations as the erase methods need to return the next iterator. * Shrinking the map would invalidate all the iterators and we could not return the next iterator in a meaningful way, * On erase, we thus just indicate on erase that we should try to shrink the hash table on the next insert * if we go below the min_load_factor. */ - bool m_try_skrink_on_next_insert; + bool m_try_shrink_on_next_insert; }; } diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-0.6.2/include/tsl/robin_map.h new/robin-map-0.6.3/include/tsl/robin_map.h --- old/robin-map-0.6.2/include/tsl/robin_map.h 2019-09-25 22:20:01.000000000 +0200 +++ new/robin-map-0.6.3/include/tsl/robin_map.h 2020-06-22 07:03:29.000000000 +0200 @@ -1,7 +1,7 @@ /** * MIT License * - * Copyright (c) 2017 Tessil + * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tes...@gmx.com> * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal @@ -38,7 +38,7 @@ /** - * Implementation of a hash map using open-adressing and the robin hood hashing algorithm with backward shift deletion. + * Implementation of a hash map using open-addressing and the robin hood hashing algorithm with backward shift deletion. * * For operations modifying the hash map (insert, erase, rehash, ...), the strong exception guarantee * is only guaranteed when the expression `std::is_nothrow_swappable<std::pair<Key, T>>::value && @@ -52,7 +52,7 @@ * the performance during lookups if the `KeyEqual` function takes time (if it engenders a cache-miss for example) * as we then compare the stored hashes before comparing the keys. When `tsl::rh::power_of_two_growth_policy` is used * as `GrowthPolicy`, it may also speed-up the rehash process as we can avoid to recalculate the hash. - * When it is detected that storing the hash will not incur any memory penality due to alignement (i.e. + * When it is detected that storing the hash will not incur any memory penalty due to alignment (i.e. * `sizeof(tsl::detail_robin_hash::bucket_entry<ValueType, true>) == * sizeof(tsl::detail_robin_hash::bucket_entry<ValueType, false>)`) and `tsl::rh::power_of_two_growth_policy` is * used, the hash will be stored even if `StoreHash` is false so that we can speed-up the rehash (but it will @@ -368,7 +368,7 @@ /** * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup to the value if you already have the hash. */ size_type erase(const key_type& key, std::size_t precalculated_hash) { return m_ht.erase(key, precalculated_hash); @@ -385,7 +385,7 @@ * @copydoc erase(const K& key) * * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup to the value if you already have the hash. */ template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> size_type erase(const K& key, std::size_t precalculated_hash) { @@ -405,7 +405,7 @@ /** * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ T& at(const Key& key, std::size_t precalculated_hash) { return m_ht.at(key, precalculated_hash); } @@ -429,7 +429,7 @@ * @copydoc at(const K& key) * * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> T& at(const K& key, std::size_t precalculated_hash) { return m_ht.at(key, precalculated_hash); } @@ -460,7 +460,7 @@ /** * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ size_type count(const Key& key, std::size_t precalculated_hash) const { return m_ht.count(key, precalculated_hash); @@ -477,7 +477,7 @@ * @copydoc count(const K& key) const * * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> size_type count(const K& key, std::size_t precalculated_hash) const { return m_ht.count(key, precalculated_hash); } @@ -489,7 +489,7 @@ /** * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ iterator find(const Key& key, std::size_t precalculated_hash) { return m_ht.find(key, precalculated_hash); } @@ -513,7 +513,7 @@ * @copydoc find(const K& key) * * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> iterator find(const K& key, std::size_t precalculated_hash) { return m_ht.find(key, precalculated_hash); } @@ -528,7 +528,7 @@ * @copydoc find(const K& key) * * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> const_iterator find(const K& key, std::size_t precalculated_hash) const { @@ -542,7 +542,7 @@ /** * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ bool contains(const Key& key, std::size_t precalculated_hash) const { return m_ht.contains(key, precalculated_hash); @@ -559,7 +559,7 @@ * @copydoc contains(const K& key) const * * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> bool contains(const K& key, std::size_t precalculated_hash) const { @@ -573,7 +573,7 @@ /** * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ std::pair<iterator, iterator> equal_range(const Key& key, std::size_t precalculated_hash) { return m_ht.equal_range(key, precalculated_hash); @@ -600,7 +600,7 @@ * @copydoc equal_range(const K& key) * * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> std::pair<iterator, iterator> equal_range(const K& key, std::size_t precalculated_hash) { diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-0.6.2/include/tsl/robin_set.h new/robin-map-0.6.3/include/tsl/robin_set.h --- old/robin-map-0.6.2/include/tsl/robin_set.h 2019-09-25 22:20:01.000000000 +0200 +++ new/robin-map-0.6.3/include/tsl/robin_set.h 2020-06-22 07:03:29.000000000 +0200 @@ -1,7 +1,7 @@ /** * MIT License * - * Copyright (c) 2017 Tessil + * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tes...@gmx.com> * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal @@ -38,7 +38,7 @@ /** - * Implementation of a hash set using open-adressing and the robin hood hashing algorithm with backward shift deletion. + * Implementation of a hash set using open-addressing and the robin hood hashing algorithm with backward shift deletion. * * For operations modifying the hash set (insert, erase, rehash, ...), the strong exception guarantee * is only guaranteed when the expression `std::is_nothrow_swappable<Key>::value && @@ -52,7 +52,7 @@ * the performance during lookups if the `KeyEqual` function takes time (or engenders a cache-miss for example) * as we then compare the stored hashes before comparing the keys. When `tsl::rh::power_of_two_growth_policy` is used * as `GrowthPolicy`, it may also speed-up the rehash process as we can avoid to recalculate the hash. - * When it is detected that storing the hash will not incur any memory penality due to alignement (i.e. + * When it is detected that storing the hash will not incur any memory penalty due to alignment (i.e. * `sizeof(tsl::detail_robin_hash::bucket_entry<ValueType, true>) == * sizeof(tsl::detail_robin_hash::bucket_entry<ValueType, false>)`) and `tsl::rh::power_of_two_growth_policy` is * used, the hash will be stored even if `StoreHash` is false so that we can speed-up the rehash (but it will @@ -296,7 +296,7 @@ /** * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup to the value if you already have the hash. */ size_type erase(const key_type& key, std::size_t precalculated_hash) { return m_ht.erase(key, precalculated_hash); @@ -313,7 +313,7 @@ * @copydoc erase(const K& key) * * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup to the value if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup to the value if you already have the hash. */ template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> size_type erase(const K& key, std::size_t precalculated_hash) { @@ -333,7 +333,7 @@ /** * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ size_type count(const Key& key, std::size_t precalculated_hash) const { return m_ht.count(key, precalculated_hash); } @@ -348,7 +348,7 @@ * @copydoc count(const K& key) const * * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> size_type count(const K& key, std::size_t precalculated_hash) const { return m_ht.count(key, precalculated_hash); } @@ -360,7 +360,7 @@ /** * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ iterator find(const Key& key, std::size_t precalculated_hash) { return m_ht.find(key, precalculated_hash); } @@ -382,7 +382,7 @@ * @copydoc find(const K& key) * * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> iterator find(const K& key, std::size_t precalculated_hash) { return m_ht.find(key, precalculated_hash); } @@ -397,7 +397,7 @@ * @copydoc find(const K& key) * * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> const_iterator find(const K& key, std::size_t precalculated_hash) const { return m_ht.find(key, precalculated_hash); } @@ -409,7 +409,7 @@ /** * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ bool contains(const Key& key, std::size_t precalculated_hash) const { return m_ht.contains(key, precalculated_hash); @@ -426,7 +426,7 @@ * @copydoc contains(const K& key) const * * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> bool contains(const K& key, std::size_t precalculated_hash) const { @@ -440,7 +440,7 @@ /** * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ std::pair<iterator, iterator> equal_range(const Key& key, std::size_t precalculated_hash) { return m_ht.equal_range(key, precalculated_hash); @@ -466,7 +466,7 @@ * @copydoc equal_range(const K& key) * * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be the same - * as hash_function()(key). Usefull to speed-up the lookup if you already have the hash. + * as hash_function()(key). Useful to speed-up the lookup if you already have the hash. */ template<class K, class KE = KeyEqual, typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr> std::pair<iterator, iterator> equal_range(const K& key, std::size_t precalculated_hash) { diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-0.6.2/tests/custom_allocator_tests.cpp new/robin-map-0.6.3/tests/custom_allocator_tests.cpp --- old/robin-map-0.6.2/tests/custom_allocator_tests.cpp 2019-09-25 22:20:01.000000000 +0200 +++ new/robin-map-0.6.3/tests/custom_allocator_tests.cpp 2020-06-22 07:03:29.000000000 +0200 @@ -1,7 +1,7 @@ /** * MIT License * - * Copyright (c) 2017 Tessil + * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tes...@gmx.com> * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-0.6.2/tests/main.cpp new/robin-map-0.6.3/tests/main.cpp --- old/robin-map-0.6.2/tests/main.cpp 2019-09-25 22:20:01.000000000 +0200 +++ new/robin-map-0.6.3/tests/main.cpp 2020-06-22 07:03:29.000000000 +0200 @@ -1,7 +1,7 @@ /** * MIT License * - * Copyright (c) 2017 Tessil + * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tes...@gmx.com> * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-0.6.2/tests/policy_tests.cpp new/robin-map-0.6.3/tests/policy_tests.cpp --- old/robin-map-0.6.2/tests/policy_tests.cpp 2019-09-25 22:20:01.000000000 +0200 +++ new/robin-map-0.6.3/tests/policy_tests.cpp 2020-06-22 07:03:29.000000000 +0200 @@ -1,7 +1,7 @@ /** * MIT License * - * Copyright (c) 2017 Tessil + * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tes...@gmx.com> * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal @@ -73,7 +73,7 @@ } BOOST_AUTO_TEST_CASE_TEMPLATE(test_policy_min_bucket_count, Policy, test_types) { - // Check polcy when a bucket_count of 0 is asked. + // Check policy when a bucket_count of 0 is asked. std::size_t bucket_count = 0; Policy policy(bucket_count); diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-0.6.2/tests/robin_map_tests.cpp new/robin-map-0.6.3/tests/robin_map_tests.cpp --- old/robin-map-0.6.2/tests/robin_map_tests.cpp 2019-09-25 22:20:01.000000000 +0200 +++ new/robin-map-0.6.3/tests/robin_map_tests.cpp 2020-06-22 07:03:29.000000000 +0200 @@ -1,7 +1,7 @@ /** * MIT License * - * Copyright (c) 2017 Tessil + * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tes...@gmx.com> * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal @@ -521,6 +521,10 @@ } BOOST_AUTO_TEST_CASE(test_min_load_factor) { + // set min_load_factor to 0.15 and max_load_factor to 0.5. + // rehash to 100 buckets, insert 50 elements, erase until load_factor() < min_load_factor(), + // insert an element, check if map has shrinked. + const std::size_t nb_values = 50; tsl::robin_map<std::int64_t, std::int64_t> map; map.min_load_factor(0.15f); @@ -530,15 +534,11 @@ BOOST_CHECK_EQUAL(map.max_load_factor(), 0.5f); - map.rehash(100); - for(std::size_t i = 0; i < map.bucket_count()/2; i++) { - map.insert({utils::get_key<std::int64_t>(i), - utils::get_value<std::int64_t>(i)}); + map.rehash(nb_values*2); + for(std::size_t i = 0; i < nb_values; i++) { + map.insert({utils::get_key<std::int64_t>(i), utils::get_value<std::int64_t>(i)}); } - BOOST_CHECK_GT(map.load_factor(), map.min_load_factor()); - // Can't use BOOST_CHECK_CLOSE with -fno-exceptions - BOOST_CHECK(std::abs(map.load_factor() - 0.5f) < 0.005f); while(map.load_factor() >= map.min_load_factor()) { @@ -551,6 +551,37 @@ BOOST_CHECK_GT(map.load_factor(), map.min_load_factor()); } +BOOST_AUTO_TEST_CASE(test_min_load_factor_range_erase) { + // set min_load_factor to 0.15 and max_load_factor to 0.5. + // rehash to 100 buckets, insert 50 elements, erase 40 with range erase, insert an element, + // check if map has shrinked. + const std::size_t nb_values = 50; + const std::size_t nb_values_erase = 40; + tsl::robin_map<std::int64_t, std::int64_t> map; + + map.min_load_factor(0.15f); + BOOST_CHECK_EQUAL(map.min_load_factor(), 0.15f); + + map.max_load_factor(0.5f); + BOOST_CHECK_EQUAL(map.max_load_factor(), 0.5f); + + + map.rehash(nb_values*2); + for(std::size_t i = 0; i < nb_values; i++) { + map.insert({utils::get_key<std::int64_t>(i), utils::get_value<std::int64_t>(i)}); + } + BOOST_CHECK_GT(map.load_factor(), map.min_load_factor()); + + + map.erase(std::next(map.begin(), nb_values - nb_values_erase) , map.end()); + + // Shrink is done on insert. + map.insert({utils::get_key<std::int64_t>(map.bucket_count()), + utils::get_value<std::int64_t>(map.bucket_count())}); + BOOST_CHECK_GT(map.load_factor(), map.min_load_factor()); + BOOST_CHECK_LT(map.bucket_count(), nb_values*2); +} + /** * rehash */ @@ -646,6 +677,25 @@ BOOST_CHECK(map == (HMap({{5, -5}, {1, -1}, {2, -1}, {4, -4}, {3, -3}}))); } +BOOST_AUTO_TEST_CASE(test_clear_with_min_load_factor) { + // insert x values, clear map, test insert + using HMap = tsl::robin_map<std::int64_t, std::int64_t>; + + const std::size_t nb_values = 1000; + auto map = utils::get_filled_hash_map<HMap>(nb_values); + map.min_load_factor(0.1f); + + map.clear(); + BOOST_CHECK_EQUAL(map.bucket_count(), 0); + BOOST_CHECK_EQUAL(map.size(), 0); + BOOST_CHECK_EQUAL(std::distance(map.begin(), map.end()), 0); + + map.insert({5, -5}); + map.insert({{1, -1}, {2, -1}, {4, -4}, {3, -3}}); + + BOOST_CHECK(map == (HMap({{5, -5}, {1, -1}, {2, -1}, {4, -4}, {3, -3}}))); +} + /** * iterator.value() @@ -671,6 +721,15 @@ } } +BOOST_AUTO_TEST_CASE(test_modify_value_through_iterator_with_const_qualifier) { + tsl::robin_map<int, int> map = {{0, 1}}; + const auto it = map.begin(); + + BOOST_CHECK_EQUAL(it->second, 1); + it.value() += 10; + BOOST_CHECK_EQUAL(it->second, 11); +} + /** * constructor */ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-0.6.2/tests/robin_set_tests.cpp new/robin-map-0.6.3/tests/robin_set_tests.cpp --- old/robin-map-0.6.2/tests/robin_set_tests.cpp 2019-09-25 22:20:01.000000000 +0200 +++ new/robin-map-0.6.3/tests/robin_set_tests.cpp 2020-06-22 07:03:29.000000000 +0200 @@ -1,7 +1,7 @@ /** * MIT License * - * Copyright (c) 2017 Tessil + * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tes...@gmx.com> * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/robin-map-0.6.2/tests/utils.h new/robin-map-0.6.3/tests/utils.h --- old/robin-map-0.6.2/tests/utils.h 2019-09-25 22:20:01.000000000 +0200 +++ new/robin-map-0.6.3/tests/utils.h 2020-06-22 07:03:29.000000000 +0200 @@ -1,7 +1,7 @@ /** * MIT License * - * Copyright (c) 2017 Tessil + * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tes...@gmx.com> * * Permission is hereby granted, free of charge, to any person obtaining a copy * of this software and associated documentation files (the "Software"), to deal
