Add copy constructor and assignment to `SmallIntMap`. It was weird that it was copy-constructible from all maps with the same type except for the same type. PiperOrigin-RevId: 884551507
diff --git a/riegeli/base/small_int_map.h b/riegeli/base/small_int_map.h index b540821..0c71cdf 100644 --- a/riegeli/base/small_int_map.h +++ b/riegeli/base/small_int_map.h
@@ -47,6 +47,66 @@ template <typename T> SizedArray<T> MakeSizedArray(size_t size); +template <typename Key, typename Value, Key expected_min_key, + size_t array_capacity> +class SmallIntMapImpl { + public: + static size_t max_size(); + + ABSL_ATTRIBUTE_REINITIALIZES void Reset(); + + const Value* absl_nullable Find(Key key) const; + + protected: + SmallIntMapImpl() = default; + + SmallIntMapImpl(const SmallIntMapImpl& that) noexcept; + SmallIntMapImpl& operator=(const SmallIntMapImpl& that) noexcept; + + SmallIntMapImpl(SmallIntMapImpl&& that) = default; + SmallIntMapImpl& operator=(SmallIntMapImpl&& that) = default; + + template <typename Src> + void Initialize(Src&& src); + + private: + // The raw key corresponding to a key is the key minus `expected_min_key`, + // represented in an unsigned type with wrap-around. + using RawKey = std::common_type_t<std::make_unsigned_t<Key>, size_t>; + + using SmallValues = SizedArray<DelayedConstructor<Value>>; + using SmallMap = SizedArray<const Value* absl_nullable>; + using LargeMap = absl::flat_hash_map<Key, Value>; + + static constexpr int kInverseMinLoadFactor = 4; // 25%. + + static RawKey ToRawKey(Key key) { + // Wrap-around is not an error. + return static_cast<RawKey>(key) - static_cast<RawKey>(expected_min_key); + } + + template <typename Src, typename Iterator> + void Optimize(Iterator first, Iterator last, size_t size); + + absl_nullable SmallValues CopySmallValues() const; + absl_nullable SmallMap CopySmallMap( + const DelayedConstructor<Value>* absl_nullable dest_values) const; + absl_nullable std::unique_ptr<LargeMap> CopyLargeMap() const; + + const Value* absl_nullable FindSlow(Key key) const; + + // Stores values for `small_map_`, in no particular order. + absl_nullable SmallValues small_values_; + // Indexed by raw key below `small_map_.get_deleter().size()`. Elements + // corresponding to present values point to elements of `small_values_`. + // The remaining elements are `nullptr`. + absl_nullable SmallMap small_map_; + // If not `nullptr`, stores the mapping for keys too large for `small_map_`. + // Uses `std::unique_ptr` rather than `std::optional` to reduce memory usage + // in the common case when `large_map_` is not used. + absl_nullable std::unique_ptr<LargeMap> large_map_; +}; + } // namespace small_int_map_internal // `SmallIntMap` is a map optimized for keys being small integers. It supports @@ -62,10 +122,14 @@ // as long as it is at least 25% full. template <typename Key, typename Value, Key expected_min_key = 0, size_t array_capacity = 128> -class SmallIntMap { +class SmallIntMap + : public small_int_map_internal::SmallIntMapImpl< + Key, Value, expected_min_key, array_capacity>, + private ConditionallyConstructible<std::is_copy_constructible_v<Value>, + true>, + private ConditionallyAssignable<std::is_copy_constructible_v<Value>, + true> { public: - static size_t max_size(); - // Constructs an empty `SmallIntMap`. SmallIntMap() = default; @@ -81,19 +145,22 @@ std::is_copy_constructible<Value>>>, int> = 0> explicit SmallIntMap(Src&& src) { - Initialize(std::forward<Src>(src)); + this->Initialize(std::forward<Src>(src)); } // Builds `SmallIntMap` from an initializer list. /*implicit*/ SmallIntMap(std::initializer_list<std::pair<Key, Value>> src) { - Initialize(src); + this->Initialize(src); } + SmallIntMap(const SmallIntMap& that) = default; + SmallIntMap& operator=(const SmallIntMap& that) = default; + SmallIntMap(SmallIntMap&& that) = default; SmallIntMap& operator=(SmallIntMap&& that) = default; // Makes `*this` equivalent to a newly constructed `SmallIntMap`. - ABSL_ATTRIBUTE_REINITIALIZES void Reset(); + using SmallIntMap::SmallIntMapImpl::Reset; template <typename Src, std::enable_if_t< std::conjunction_v< @@ -104,53 +171,14 @@ std::is_copy_constructible<Value>>>, int> = 0> ABSL_ATTRIBUTE_REINITIALIZES void Reset(Src&& src) { - Reset(); - Initialize(std::forward<Src>(src)); + this->Reset(); + this->Initialize(std::forward<Src>(src)); } ABSL_ATTRIBUTE_REINITIALIZES void Reset( std::initializer_list<std::pair<Key, Value>> src) { - Reset(); - Initialize(src); + this->Reset(); + this->Initialize(src); } - - const Value* absl_nullable Find(Key key) const; - - private: - // The raw key corresponding to a key is the key minus `expected_min_key`, - // represented in an unsigned type with wrap-around. - using RawKey = std::common_type_t<std::make_unsigned_t<Key>, size_t>; - - using SmallValues = small_int_map_internal::SizedArray< - small_int_map_internal::DelayedConstructor<Value>>; - using SmallMap = - small_int_map_internal::SizedArray<const Value* absl_nullable>; - using LargeMap = absl::flat_hash_map<Key, Value>; - - static constexpr int kInverseMinLoadFactor = 4; // 25%. - - static RawKey ToRawKey(Key key) { - // Wrap-around is not an error. - return static_cast<RawKey>(key) - static_cast<RawKey>(expected_min_key); - } - - template <typename Src> - void Initialize(Src&& src); - - template <typename Src, typename Iterator> - void Optimize(Iterator first, Iterator last, size_t size); - - const Value* absl_nullable FindSlow(Key key) const; - - // Stores values for `small_map_`, in no particular order. - absl_nullable SmallValues small_values_; - // Indexed by raw key below `small_map_.get_deleter().size()`. Elements - // corresponding to present values point to elements of `small_values_`. - // The remaining elements are `nullptr`. - absl_nullable SmallMap small_map_; - // If not `nullptr`, stores the mapping for keys too large for `small_map_`. - // Uses `std::unique_ptr` rather than `std::optional` to reduce memory usage - // in the common case when `large_map_` is not used. - absl_nullable std::unique_ptr<LargeMap> large_map_; }; // Implementation details follow. @@ -176,6 +204,9 @@ return value_; } + T& operator*() ABSL_ATTRIBUTE_LIFETIME_BOUND { return value_; } + const T& operator*() const ABSL_ATTRIBUTE_LIFETIME_BOUND { return value_; } + private: union { T value_; @@ -236,23 +267,18 @@ return SizedArray<T>(ptr, SizedDeleter<T>(size)); } -} // namespace small_int_map_internal - template <typename Key, typename Value, Key expected_min_key, size_t array_capacity> inline size_t -SmallIntMap<Key, Value, expected_min_key, array_capacity>::max_size() { - return UnsignedMin(small_int_map_internal::SizedDeleter< - const Value* absl_nullable>::max_size(), - small_int_map_internal::SizedDeleter< - small_int_map_internal::DelayedConstructor<Value>>:: - max_size()) / +SmallIntMapImpl<Key, Value, expected_min_key, array_capacity>::max_size() { + return UnsignedMin(SizedDeleter<const Value* absl_nullable>::max_size(), + SizedDeleter<DelayedConstructor<Value>>::max_size()) / kInverseMinLoadFactor; } template <typename Key, typename Value, Key expected_min_key, size_t array_capacity> -void SmallIntMap<Key, Value, expected_min_key, array_capacity>::Reset() { +void SmallIntMapImpl<Key, Value, expected_min_key, array_capacity>::Reset() { small_values_ = SmallValues(); small_map_ = SmallMap(); large_map_.reset(); @@ -261,7 +287,7 @@ template <typename Key, typename Value, Key expected_min_key, size_t array_capacity> template <typename Src> -void SmallIntMap<Key, Value, expected_min_key, array_capacity>::Initialize( +void SmallIntMapImpl<Key, Value, expected_min_key, array_capacity>::Initialize( Src&& src) { using std::begin; using std::end; @@ -291,10 +317,10 @@ template <typename Key, typename Value, Key expected_min_key, size_t array_capacity> template <typename Src, typename Iterator> -void SmallIntMap<Key, Value, expected_min_key, array_capacity>::Optimize( +void SmallIntMapImpl<Key, Value, expected_min_key, array_capacity>::Optimize( Iterator first, Iterator last, size_t size) { RIEGELI_ASSERT_GE(size, 0u) - << "Failed precondition of SmallIntMap::Optimize(): " + << "Failed precondition of SmallIntMapImpl::Optimize(): " "an empty map must have been handled before"; RIEGELI_CHECK_LE(size, max_size()) << "Failed precondition of SmallIntMap initialization: " @@ -312,12 +338,10 @@ // There is no need for `small_map_` to cover raw keys larger than // `max_raw_key` because their lookup is fast if `large_map_` is `nullptr`. RIEGELI_ASSUME_EQ(small_values_, nullptr) << "Initialization"; - small_values_ = small_int_map_internal::MakeSizedArray< - small_int_map_internal::DelayedConstructor<Value>>(size); + small_values_ = MakeSizedArray<DelayedConstructor<Value>>(size); RIEGELI_ASSUME_EQ(small_map_, nullptr) << "Initialization"; - small_map_ = - small_int_map_internal::MakeSizedArray<const Value* absl_nullable>( - IntCast<size_t>(max_raw_key) + 1); + small_map_ = MakeSizedArray<const Value* absl_nullable>( + IntCast<size_t>(max_raw_key) + 1); small_values_index = 0; for (auto iter = first; iter != last; ++iter) { // `(*iter).second` rather than `iter->second` allows moving from a move @@ -343,13 +367,11 @@ << "Some keys should have been too large for small_map_"; RIEGELI_ASSUME_EQ(small_values_, nullptr) << "Initialization"; if (num_small_values > 0) { - small_values_ = small_int_map_internal::MakeSizedArray< - small_int_map_internal::DelayedConstructor<Value>>(num_small_values); + small_values_ = + MakeSizedArray<DelayedConstructor<Value>>(num_small_values); } RIEGELI_ASSUME_EQ(small_map_, nullptr) << "Initialization"; - small_map_ = - small_int_map_internal::MakeSizedArray<const Value* absl_nullable>( - max_num_small_keys); + small_map_ = MakeSizedArray<const Value* absl_nullable>(max_num_small_keys); RIEGELI_ASSUME_EQ(large_map_, nullptr) << "Initialization"; large_map_ = std::make_unique<LargeMap>(); large_map_->reserve(size - num_small_values); @@ -381,8 +403,83 @@ template <typename Key, typename Value, Key expected_min_key, size_t array_capacity> +SmallIntMapImpl<Key, Value, expected_min_key, array_capacity>::SmallIntMapImpl( + const SmallIntMapImpl& that) noexcept + : small_values_(that.CopySmallValues()), + small_map_(that.CopySmallMap(small_values_.get())), + large_map_(that.CopyLargeMap()) {} + +template <typename Key, typename Value, Key expected_min_key, + size_t array_capacity> +SmallIntMapImpl<Key, Value, expected_min_key, array_capacity>& +SmallIntMapImpl<Key, Value, expected_min_key, array_capacity>::operator=( + const SmallIntMapImpl& that) noexcept { + absl_nullable SmallValues new_small_values = that.CopySmallValues(); + small_map_ = that.CopySmallMap(new_small_values.get()); + small_values_ = std::move(new_small_values); + large_map_ = that.CopyLargeMap(); + return *this; +} + +template <typename Key, typename Value, Key expected_min_key, + size_t array_capacity> +auto SmallIntMapImpl<Key, Value, expected_min_key, + array_capacity>::CopySmallValues() const -> + absl_nullable SmallValues { + if (small_values_ == nullptr) return nullptr; + SmallValues dest_ptr = MakeSizedArray<DelayedConstructor<Value>>( + small_values_.get_deleter().size()); + DelayedConstructor<Value>* src_iter = small_values_.get(); + DelayedConstructor<Value>* const end = + dest_ptr.get() + dest_ptr.get_deleter().size(); + for (DelayedConstructor<Value>* dest_iter = dest_ptr.get(); dest_iter != end; + ++dest_iter) { + dest_iter->emplace(**src_iter); + ++src_iter; + } + return dest_ptr; +} + +template <typename Key, typename Value, Key expected_min_key, + size_t array_capacity> +auto SmallIntMapImpl<Key, Value, expected_min_key, array_capacity>:: + CopySmallMap(const DelayedConstructor<Value>* absl_nullable dest_values) + const -> absl_nullable SmallMap { + if (small_map_ == nullptr) return nullptr; + const DelayedConstructor<Value>* const absl_nullable src_values = + small_values_.get(); + SmallMap dest_ptr = MakeSizedArray<const Value* absl_nullable>( + small_map_.get_deleter().size()); + const Value* absl_nullable* src_iter = small_map_.get(); + const Value* absl_nullable* const end = + dest_ptr.get() + dest_ptr.get_deleter().size(); + for (const Value* absl_nullable* dest_iter = dest_ptr.get(); dest_iter != end; + ++dest_iter) { + if (*src_iter != nullptr) { + *dest_iter = reinterpret_cast<const Value*>( + reinterpret_cast<const char*>(dest_values) + + ((reinterpret_cast<const char*>(*src_iter) - + reinterpret_cast<const char*>(src_values)))); + } + ++src_iter; + } + return dest_ptr; +} + +template <typename Key, typename Value, Key expected_min_key, + size_t array_capacity> +auto SmallIntMapImpl<Key, Value, expected_min_key, + array_capacity>::CopyLargeMap() const -> + absl_nullable std::unique_ptr<LargeMap> { + if (large_map_ == nullptr) return nullptr; + return std::make_unique<LargeMap>(*large_map_); +} + +template <typename Key, typename Value, Key expected_min_key, + size_t array_capacity> ABSL_ATTRIBUTE_ALWAYS_INLINE const Value* absl_nullable -SmallIntMap<Key, Value, expected_min_key, array_capacity>::Find(Key key) const { +SmallIntMapImpl<Key, Value, expected_min_key, array_capacity>::Find( + Key key) const { RIEGELI_ASSERT(!small_map_.get_deleter().IsMovedFromIfNull() || small_map_ != nullptr) << "Moved-from SmallIntMap"; @@ -396,13 +493,15 @@ template <typename Key, typename Value, Key expected_min_key, size_t array_capacity> const Value* absl_nullable -SmallIntMap<Key, Value, expected_min_key, array_capacity>::FindSlow( +SmallIntMapImpl<Key, Value, expected_min_key, array_capacity>::FindSlow( Key key) const { const auto iter = large_map_->find(key); if (iter == large_map_->end()) return nullptr; return &iter->second; } +} // namespace small_int_map_internal + } // namespace riegeli #endif // RIEGELI_BASE_SMALL_INT_MAP_H_