Change how `HybridDirectMap` is parameterized. Specify `direct_capacity` as a runtime constructor parameter rather than a template parameter. Replace `expected_min_key` template parameter with `Traits`. This generalizes keys from an integer type to a type with a translation to an unsigned integer type. `SlowMap` is indexed by translated keys to avoid imposing a hashing requirement on the key type. Split private headers `hybrid_direct_common.h` (reexported) and `hybrid_direct_internal.h` (not reexported) out of `hybrid_direct_map.h` to keep the main public header focused. PiperOrigin-RevId: 889683578
diff --git a/riegeli/base/BUILD b/riegeli/base/BUILD index dcee9f7..a65830d 100644 --- a/riegeli/base/BUILD +++ b/riegeli/base/BUILD
@@ -655,6 +655,10 @@ cc_library( name = "hybrid_direct_map", + srcs = [ + "hybrid_direct_common.h", + "hybrid_direct_internal.h", + ], hdrs = ["hybrid_direct_map.h"], deps = [ ":arithmetic",
diff --git a/riegeli/base/hybrid_direct_common.h b/riegeli/base/hybrid_direct_common.h new file mode 100644 index 0000000..16640ff --- /dev/null +++ b/riegeli/base/hybrid_direct_common.h
@@ -0,0 +1,66 @@ +// Copyright 2026 Google LLC +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#ifndef RIEGELI_BASE_HYBRID_DIRECT_COMMON_H_ +#define RIEGELI_BASE_HYBRID_DIRECT_COMMON_H_ + +// IWYU pragma: private, include "riegeli/base/hybrid_direct_map.h" + +#include <stddef.h> + +#include <type_traits> + +#include "absl/base/nullability.h" + +ABSL_POINTERS_DEFAULT_NONNULL + +namespace riegeli { + +// The default `Traits` parameter for `HybridDirectMap`. +// +// `expected_min_key` is the expected lower bound of keys. Keys smaller than +// that are never put in the array. +template <typename Key, Key expected_min_key = Key(), typename Enable = void> +struct HybridDirectTraits; + +template <typename Key, Key expected_min_key> +struct HybridDirectTraits<Key, expected_min_key, + std::enable_if_t<std::is_integral_v<Key>>> { + using RawKey = std::make_unsigned_t<Key>; + + static RawKey ToRawKey(Key key) { + // Wrap-around is not an error. + return static_cast<RawKey>(static_cast<RawKey>(key) - + static_cast<RawKey>(expected_min_key)); + } +}; + +template <typename Key, Key expected_min_key> +struct HybridDirectTraits<Key, expected_min_key, + std::enable_if_t<std::is_enum_v<Key>>> { + using RawKey = std::make_unsigned_t<std::underlying_type_t<Key>>; + + static RawKey ToRawKey(Key key) { + // Wrap-around is not an error. + return static_cast<RawKey>(static_cast<RawKey>(key) - + static_cast<RawKey>(expected_min_key)); + } +}; + +// The default `direct_capacity` parameter for `HybridDirectMap` building. +constexpr size_t kHybridDirectDefaultDirectCapacity = 128; + +} // namespace riegeli + +#endif // RIEGELI_BASE_HYBRID_DIRECT_COMMON_H_
diff --git a/riegeli/base/hybrid_direct_internal.h b/riegeli/base/hybrid_direct_internal.h new file mode 100644 index 0000000..4e01633 --- /dev/null +++ b/riegeli/base/hybrid_direct_internal.h
@@ -0,0 +1,137 @@ +// Copyright 2026 Google LLC +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#ifndef RIEGELI_BASE_HYBRID_DIRECT_INTERNAL_H_ +#define RIEGELI_BASE_HYBRID_DIRECT_INTERNAL_H_ + +#include <stddef.h> + +#include <memory> +#include <type_traits> +#include <utility> + +#include "absl/base/attributes.h" +#include "absl/base/nullability.h" + +ABSL_POINTERS_DEFAULT_NONNULL + +namespace riegeli::hybrid_direct_internal { + +// Wraps a `T` which is constructed explicitly later, rather than when +// `DelayedConstructor<T>` is constructed. +// +// In contrast to `std::optional<T>`, this avoids the overhead of tracking +// whether the object has been constructed, at the cost of passing this +// responsibility to the caller. +template <typename T> +class DelayedConstructor { + public: + // Does not construct the wrapped object yet. + DelayedConstructor() noexcept {} + + DelayedConstructor(const DelayedConstructor&) = delete; + DelayedConstructor& operator=(const DelayedConstructor&) = delete; + + // Destroys the wrapped object. It must have been constructed. + ~DelayedConstructor() { value_.~T(); } + + // Constructs the wrapped object. It must not have been constructed yet. + template <typename... Args, + std::enable_if_t<std::is_constructible_v<T, Args&&...>, int> = 0> + T& emplace(Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND { + new (&value_) T(std::forward<Args>(args)...); + return value_; + } + + // Returns the wrapped object. It must have been constructed. + T& operator*() ABSL_ATTRIBUTE_LIFETIME_BOUND { return value_; } + const T& operator*() const ABSL_ATTRIBUTE_LIFETIME_BOUND { return value_; } + + private: + union { + T value_; + }; +}; + +// A deleter for `SizedArray<T>`. +// +// A moved-from `SizedDeleter` reports a positive size. This helps to trigger +// a null pointer dereference when a moved-from `SizedArray` is used. +template <typename T> +class SizedDeleter { + public: + static size_t max_size() { + return std::allocator_traits<std::allocator<T>>::max_size( + std::allocator<T>()); + } + + SizedDeleter() = default; + + explicit SizedDeleter(size_t size) : size_(size) {} + + SizedDeleter(SizedDeleter&& that) noexcept + : size_(std::exchange(that.size_, kPoisonedSize)) {} + + SizedDeleter& operator=(SizedDeleter&& that) noexcept { + size_ = std::exchange(that.size_, kPoisonedSize); + return *this; + } + + void operator()(T* ptr) const { + for (T* iter = ptr + size_; iter != ptr;) { + --iter; + iter->~T(); + } + std::allocator<T>().deallocate(ptr, size_); + } + + size_t size() const { return size_; } + + // If the pointer associated with this deleter is `nullptr`, returns `true` + // when this deleter is moved-from. Otherwise the result is meaningless. + bool IsMovedFromIfNull() const { return size_ == kPoisonedSize; } + + private: + // A moved-from `SizedDeleter` has `size_ == kPoisonedSize`. In debug mode + // this asserts against using a moved-from object. In non-debug mode, if the + // key is not too large, then this triggers a null pointer dereference with an + // offset up to 1MB, which is assumed to reliably crash. + static constexpr size_t kPoisonedSize = (size_t{1} << 20) / sizeof(T); + + size_t size_ = 0; +}; + +// Like `std::unique_ptr<T[]>`, but the size is stored in the deleter. +// It is available as `get_deleter().size()` and used for sized delete. +// +// A moved-from `SizedArray` is `nullptr` but reports a positive size. This +// helps to trigger a null pointer dereference when a moved-from `SizedArray` +// is used. +template <typename T> +using SizedArray = std::unique_ptr<T[], SizedDeleter<T>>; + +// Like `std::make_unique<T[]>(size)`. +template <typename T> +inline SizedArray<T> MakeSizedArray(size_t size) { + T* const ptr = std::allocator<T>().allocate(size); + T* const end = ptr + size; + for (T* iter = ptr; iter != end; ++iter) { + new (iter) T(); + } + return SizedArray<T>(ptr, SizedDeleter<T>(size)); +} + +} // namespace riegeli::hybrid_direct_internal + +#endif // RIEGELI_BASE_HYBRID_DIRECT_INTERNAL_H_
diff --git a/riegeli/base/hybrid_direct_map.h b/riegeli/base/hybrid_direct_map.h index 2bdafd5..ebc2880 100644 --- a/riegeli/base/hybrid_direct_map.h +++ b/riegeli/base/hybrid_direct_map.h
@@ -29,6 +29,8 @@ #include "absl/container/flat_hash_map.h" #include "riegeli/base/arithmetic.h" #include "riegeli/base/assert.h" +#include "riegeli/base/hybrid_direct_common.h" // IWYU pragma: export +#include "riegeli/base/hybrid_direct_internal.h" #include "riegeli/base/iterable.h" #include "riegeli/base/type_traits.h" @@ -38,17 +40,10 @@ namespace hybrid_direct_internal { -template <typename T> -class DelayedConstructor; -template <typename T> -class SizedDeleter; -template <typename T> -using SizedArray = std::unique_ptr<T[], SizedDeleter<T>>; -template <typename T> -SizedArray<T> MakeSizedArray(size_t size); - -template <typename Key, typename Value, Key expected_min_key, - size_t array_capacity> +// Part of `HybridDirectMap` excluding constructors and assignment. This is +// separated to make copy and move constructors and assignment available +// conditionally. +template <typename Key, typename Value, typename Traits> class HybridDirectMapImpl { public: static size_t max_size(); @@ -67,34 +62,27 @@ HybridDirectMapImpl& operator=(HybridDirectMapImpl&& that) = default; template <typename Src> - void Initialize(Src&& src); + void Initialize(Src&& src, size_t direct_capacity); 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 RawKey = std::decay_t<decltype(Traits::ToRawKey(std::declval<Key>()))>; + static_assert(std::is_unsigned_v<RawKey>); using DirectValues = SizedArray<DelayedConstructor<Value>>; using DirectMap = SizedArray<const Value* absl_nullable>; - using SlowMap = absl::flat_hash_map<Key, Value>; + using SlowMap = absl::flat_hash_map<RawKey, 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); + void Optimize(Iterator first, Iterator last, size_t size, + size_t direct_capacity); absl_nullable DirectValues CopyDirectValues() const; absl_nullable DirectMap CopyDirectMap( const DelayedConstructor<Value>* absl_nullable dest_values) const; absl_nullable std::unique_ptr<SlowMap> CopySlowMap() const; - const Value* absl_nullable FindSlow(Key key) const; - // Stores values for `direct_map_`, in no particular order. absl_nullable DirectValues direct_values_; // Indexed by raw key below `direct_map_.get_deleter().size()`. Elements @@ -104,6 +92,8 @@ // If not `nullptr`, stores the mapping for keys too large for `direct_map_`. // Uses `std::unique_ptr` rather than `std::optional` to reduce memory usage // in the common case when `slow_map_` is not used. + // + // Invariant: if `slow_map_ != nullptr` then `!slow_map_->empty()`. absl_nullable std::unique_ptr<SlowMap> slow_map_; }; @@ -112,19 +102,26 @@ // `HybridDirectMap` is a map optimized for keys being small integers. // It supports only lookups, but no incremental building nor iteration. // -// It stores a part of the map covering some range of keys starting from -// `expected_min_key` in an array. +// It stores a part of the map covering some range of small keys in an array. +// The remaining keys are stored in an `absl::flat_hash_map`. // -// At least `array_capacity` possible keys starting from `expected_min_key` are -// suitable for array lookup. If all present keys are suitable, the stored array -// can be smaller than `array_capacity`, covering the range to the largest key. -// If the map is large, the stored array can be larger than `array_capacity`, -// as long as it is at least 25% full. -template <typename Key, typename Value, Key expected_min_key = 0, - size_t array_capacity = 128> +// `Traits` specifies a mapping of keys to an unsigned integer type. It must +// support at least the following static member: +// +// ``` +// // Translates the key to a raw key, which is an unsigned integer type. +// // Small raw keys are put in the array. +// static RawKey ToRawKey(Key key); +// ``` +// +// `direct_capacity`, if specified during building, is the intended capacity +// of the array part. The actual capacity can be smaller if all keys fit +// in the array, or larger if the array remains at least 25% full. Default: +// `kHybridDirectDefaultDirectCapacity` (128). +template <typename Key, typename Value, + typename Traits = HybridDirectTraits<Key>> class HybridDirectMap - : public hybrid_direct_internal::HybridDirectMapImpl< - Key, Value, expected_min_key, array_capacity>, + : public hybrid_direct_internal::HybridDirectMapImpl<Key, Value, Traits>, private ConditionallyConstructible<std::is_copy_constructible_v<Value>, true>, private ConditionallyAssignable<std::is_copy_constructible_v<Value>, @@ -145,13 +142,26 @@ std::is_copy_constructible<Value>>>, int> = 0> explicit HybridDirectMap(Src&& src) { - this->Initialize(std::forward<Src>(src)); + this->Initialize(std::forward<Src>(src), + kHybridDirectDefaultDirectCapacity); + } + template <typename Src, + std::enable_if_t< + std::conjunction_v< + IsForwardIterable<Src>, IsIterableOfPairs<Src, Key, Value>, + std::conditional_t<HasMovableElements<Src>::value, + std::is_move_constructible<Value>, + std::is_copy_constructible<Value>>>, + int> = 0> + explicit HybridDirectMap(Src&& src, size_t direct_capacity) { + this->Initialize(std::forward<Src>(src), direct_capacity); } // Builds `HybridDirectMap` from an initializer list. /*implicit*/ HybridDirectMap( - std::initializer_list<std::pair<Key, Value>> src) { - this->Initialize(src); + std::initializer_list<std::pair<Key, Value>> src, + size_t direct_capacity = kHybridDirectDefaultDirectCapacity) { + this->Initialize(src, direct_capacity); } HybridDirectMap(const HybridDirectMap& that) = default; @@ -165,20 +175,21 @@ template <typename Src, std::enable_if_t< std::conjunction_v< - NotSameRef<HybridDirectMap, Src>, IsForwardIterable<Src>, - IsIterableOfPairs<Src, Key, Value>, + IsForwardIterable<Src>, IsIterableOfPairs<Src, Key, Value>, std::conditional_t<HasMovableElements<Src>::value, std::is_move_constructible<Value>, std::is_copy_constructible<Value>>>, int> = 0> - ABSL_ATTRIBUTE_REINITIALIZES void Reset(Src&& src) { + ABSL_ATTRIBUTE_REINITIALIZES void Reset( + Src&& src, size_t direct_capacity = kHybridDirectDefaultDirectCapacity) { this->Reset(); - this->Initialize(std::forward<Src>(src)); + this->Initialize(std::forward<Src>(src), direct_capacity); } ABSL_ATTRIBUTE_REINITIALIZES void Reset( - std::initializer_list<std::pair<Key, Value>> src) { + std::initializer_list<std::pair<Key, Value>> src, + size_t direct_capacity = kHybridDirectDefaultDirectCapacity) { this->Reset(); - this->Initialize(src); + this->Initialize(src, direct_capacity); } }; @@ -186,111 +197,24 @@ namespace hybrid_direct_internal { -template <typename T> -class DelayedConstructor { - public: - // Does not construct the value yet. - DelayedConstructor() noexcept {} - - DelayedConstructor(const DelayedConstructor&) = delete; - DelayedConstructor& operator=(const DelayedConstructor&) = delete; - - ~DelayedConstructor() { value_.~T(); } - - // Construct the value. Must be called exactly once. - template <typename... Args, - std::enable_if_t<std::is_constructible_v<T, Args&&...>, int> = 0> - T& emplace(Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND { - new (&value_) T(std::forward<Args>(args)...); - return value_; - } - - T& operator*() ABSL_ATTRIBUTE_LIFETIME_BOUND { return value_; } - const T& operator*() const ABSL_ATTRIBUTE_LIFETIME_BOUND { return value_; } - - private: - union { - T value_; - }; -}; - -template <typename T> -class SizedDeleter { - public: - static size_t max_size() { - return std::allocator_traits<std::allocator<T>>::max_size( - std::allocator<T>()); - } - - SizedDeleter() = default; - - explicit SizedDeleter(size_t size) : size_(size) {} - - SizedDeleter(SizedDeleter&& that) noexcept - : size_(std::exchange(that.size_, kPoisonedSize)) {} - - SizedDeleter& operator=(SizedDeleter&& that) noexcept { - size_ = std::exchange(that.size_, kPoisonedSize); - return *this; - } - - void operator()(T* ptr) const { - for (T* iter = ptr + size_; iter != ptr;) { - --iter; - iter->~T(); - } - std::allocator<T>().deallocate(ptr, size_); - } - - size_t size() const { return size_; } - - // If the pointer associated with this deleter is `nullptr`, returns `true` - // when this deleter is moved-from. Otherwise the result is meaningless. - bool IsMovedFromIfNull() const { return size_ == kPoisonedSize; } - - private: - // A moved-from `SizedDeleter` has `size_ == kPoisonedSize`. In debug mode - // this asserts against using a moved-from object. In non-debug mode, if the - // key is not too large, then this triggers a null pointer dereference with an - // offset up to 1MB, which is assumed to reliably crash. - static constexpr size_t kPoisonedSize = (size_t{1} << 20) / sizeof(T); - - size_t size_ = 0; -}; - -template <typename T> -inline SizedArray<T> MakeSizedArray(size_t size) { - T* const ptr = std::allocator<T>().allocate(size); - T* const end = ptr + size; - for (T* iter = ptr; iter != end; ++iter) { - new (iter) T(); - } - return SizedArray<T>(ptr, SizedDeleter<T>(size)); -} - -template <typename Key, typename Value, Key expected_min_key, - size_t array_capacity> -inline size_t -HybridDirectMapImpl<Key, Value, expected_min_key, array_capacity>::max_size() { - return UnsignedMin(SizedDeleter<const Value* absl_nullable>::max_size(), +template <typename Key, typename Value, typename Traits> +inline size_t HybridDirectMapImpl<Key, Value, Traits>::max_size() { + return UnsignedMin(SizedDeleter<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 HybridDirectMapImpl<Key, Value, expected_min_key, - array_capacity>::Reset() { +template <typename Key, typename Value, typename Traits> +void HybridDirectMapImpl<Key, Value, Traits>::Reset() { direct_values_ = DirectValues(); direct_map_ = DirectMap(); slow_map_.reset(); } -template <typename Key, typename Value, Key expected_min_key, - size_t array_capacity> +template <typename Key, typename Value, typename Traits> template <typename Src> -void HybridDirectMapImpl<Key, Value, expected_min_key, - array_capacity>::Initialize(Src&& src) { +void HybridDirectMapImpl<Key, Value, Traits>::Initialize( + Src&& src, size_t direct_capacity) { using std::begin; using std::end; if constexpr (IterableHasSize<Src>::value) { @@ -300,12 +224,16 @@ IntCast<size_t>(std::distance(begin(src), end(src)))) << "Failed precondition of HybridDirectMap initialization: " "size does not match the distance between iterators"; - if (src_size > 0) Optimize<Src>(begin(src), end(src), src_size); + if (src_size > 0) { + Optimize<Src>(begin(src), end(src), src_size, direct_capacity); + } } else { auto first = begin(src); auto last = end(src); const size_t src_size = IntCast<size_t>(std::distance(first, last)); - if (src_size > 0) Optimize<Src>(first, last, src_size); + if (src_size > 0) { + Optimize<Src>(first, last, src_size, direct_capacity); + } } #if RIEGELI_DEBUG // Detect building `HybridDirectMap` from a moved-from `src` if possible. @@ -316,12 +244,12 @@ #endif } -template <typename Key, typename Value, Key expected_min_key, - size_t array_capacity> +template <typename Key, typename Value, typename Traits> template <typename Src, typename Iterator> -void HybridDirectMapImpl<Key, Value, expected_min_key, - array_capacity>::Optimize(Iterator first, - Iterator last, size_t size) { +void HybridDirectMapImpl<Key, Value, Traits>::Optimize(Iterator first, + Iterator last, + size_t size, + size_t direct_capacity) { RIEGELI_ASSERT_GE(size, 0u) << "Failed precondition of HybridDirectMapImpl::Optimize(): " "an empty map must have been handled before"; @@ -330,10 +258,10 @@ "size overflow"; RawKey max_raw_key = 0; for (auto iter = first; iter != last; ++iter) { - max_raw_key = UnsignedMax(max_raw_key, ToRawKey(iter->first)); + max_raw_key = UnsignedMax(max_raw_key, Traits::ToRawKey(iter->first)); } const size_t max_num_direct_keys = - UnsignedMax(array_capacity, size * kInverseMinLoadFactor); + UnsignedMax(direct_capacity, size * kInverseMinLoadFactor); size_t direct_values_index; if (max_raw_key < max_num_direct_keys) { // All keys are suitable for `direct_map_`. `slow_map_` is not used. @@ -349,13 +277,13 @@ for (auto iter = first; iter != last; ++iter) { // `(*iter).second` rather than `iter->second` allows moving from a move // iterator. - RIEGELI_ASSERT_EQ(direct_map_[ToRawKey(iter->first)], nullptr) + const RawKey raw_key = Traits::ToRawKey(iter->first); + RIEGELI_ASSERT_EQ(direct_map_[raw_key], nullptr) << "Failed precondition of HybridDirectMap initialization: " "duplicate key: " - << iter->first; - direct_map_[ToRawKey(iter->first)] = - &direct_values_[direct_values_index++].emplace( - (*MaybeMakeMoveIterator<Src>(iter)).second); + << riegeli::Debug(iter->first); + direct_map_[raw_key] = &direct_values_[direct_values_index++].emplace( + (*MaybeMakeMoveIterator<Src>(iter)).second); } } else { // Some keys are too large for `direct_map_`. `slow_map_` is used. @@ -364,7 +292,8 @@ // only up to `max_raw_key`, to reduce lookups in `slow_map_`. size_t num_direct_values = 0; for (auto iter = first; iter != last; ++iter) { - num_direct_values += ToRawKey(iter->first) < max_num_direct_keys ? 1 : 0; + num_direct_values += + Traits::ToRawKey(iter->first) < max_num_direct_keys ? 1 : 0; } RIEGELI_ASSERT_LT(num_direct_values, size) << "Some keys should have been too large for direct_map_"; @@ -383,21 +312,21 @@ for (auto iter = first; iter != last; ++iter) { // `(*iter).second` rather than `iter->second` allows moving from a move // iterator. - if (ToRawKey(iter->first) < max_num_direct_keys) { - RIEGELI_ASSERT_EQ(direct_map_[ToRawKey(iter->first)], nullptr) + const RawKey raw_key = Traits::ToRawKey(iter->first); + if (raw_key < max_num_direct_keys) { + RIEGELI_ASSERT_EQ(direct_map_[raw_key], nullptr) << "Failed precondition of HybridDirectMap initialization: " "duplicate key: " - << iter->first; - direct_map_[ToRawKey(iter->first)] = - &direct_values_[direct_values_index++].emplace( - (*MaybeMakeMoveIterator<Src>(iter)).second); + << riegeli::Debug(iter->first); + direct_map_[raw_key] = &direct_values_[direct_values_index++].emplace( + (*MaybeMakeMoveIterator<Src>(iter)).second); } else { const auto inserted = slow_map_->try_emplace( - iter->first, (*MaybeMakeMoveIterator<Src>(iter)).second); + raw_key, (*MaybeMakeMoveIterator<Src>(iter)).second); RIEGELI_ASSERT(inserted.second) << "Failed precondition of HybridDirectMap initialization: " "duplicate key: " - << iter->first; + << riegeli::Debug(iter->first); } } } @@ -405,18 +334,16 @@ << "The whole direct_values_ array should have been filled"; } -template <typename Key, typename Value, Key expected_min_key, - size_t array_capacity> -HybridDirectMapImpl<Key, Value, expected_min_key, array_capacity>:: - HybridDirectMapImpl(const HybridDirectMapImpl& that) noexcept +template <typename Key, typename Value, typename Traits> +HybridDirectMapImpl<Key, Value, Traits>::HybridDirectMapImpl( + const HybridDirectMapImpl& that) noexcept : direct_values_(that.CopyDirectValues()), direct_map_(that.CopyDirectMap(direct_values_.get())), slow_map_(that.CopySlowMap()) {} -template <typename Key, typename Value, Key expected_min_key, - size_t array_capacity> -HybridDirectMapImpl<Key, Value, expected_min_key, array_capacity>& -HybridDirectMapImpl<Key, Value, expected_min_key, array_capacity>::operator=( +template <typename Key, typename Value, typename Traits> +HybridDirectMapImpl<Key, Value, Traits>& +HybridDirectMapImpl<Key, Value, Traits>::operator=( const HybridDirectMapImpl& that) noexcept { absl_nullable DirectValues new_direct_values = that.CopyDirectValues(); direct_map_ = that.CopyDirectMap(new_direct_values.get()); @@ -425,10 +352,8 @@ return *this; } -template <typename Key, typename Value, Key expected_min_key, - size_t array_capacity> -auto HybridDirectMapImpl<Key, Value, expected_min_key, - array_capacity>::CopyDirectValues() const -> +template <typename Key, typename Value, typename Traits> +auto HybridDirectMapImpl<Key, Value, Traits>::CopyDirectValues() const -> absl_nullable DirectValues { if (direct_values_ == nullptr) return nullptr; DirectValues dest_ptr = MakeSizedArray<DelayedConstructor<Value>>( @@ -444,11 +369,10 @@ return dest_ptr; } -template <typename Key, typename Value, Key expected_min_key, - size_t array_capacity> -auto HybridDirectMapImpl<Key, Value, expected_min_key, array_capacity>:: - CopyDirectMap(const DelayedConstructor<Value>* absl_nullable dest_values) - const -> absl_nullable DirectMap { +template <typename Key, typename Value, typename Traits> +auto HybridDirectMapImpl<Key, Value, Traits>::CopyDirectMap( + const DelayedConstructor<Value>* absl_nullable dest_values) const -> + absl_nullable DirectMap { if (direct_map_ == nullptr) return nullptr; const DelayedConstructor<Value>* const absl_nullable src_values = direct_values_.get(); @@ -470,36 +394,23 @@ return dest_ptr; } -template <typename Key, typename Value, Key expected_min_key, - size_t array_capacity> -auto HybridDirectMapImpl<Key, Value, expected_min_key, - array_capacity>::CopySlowMap() const -> +template <typename Key, typename Value, typename Traits> +auto HybridDirectMapImpl<Key, Value, Traits>::CopySlowMap() const -> absl_nullable std::unique_ptr<SlowMap> { if (slow_map_ == nullptr) return nullptr; return std::make_unique<SlowMap>(*slow_map_); } -template <typename Key, typename Value, Key expected_min_key, - size_t array_capacity> +template <typename Key, typename Value, typename Traits> ABSL_ATTRIBUTE_ALWAYS_INLINE const Value* absl_nullable -HybridDirectMapImpl<Key, Value, expected_min_key, array_capacity>::Find( - Key key) const { +HybridDirectMapImpl<Key, Value, Traits>::Find(Key key) const { RIEGELI_ASSERT(!direct_map_.get_deleter().IsMovedFromIfNull() || direct_map_ != nullptr) << "Moved-from HybridDirectMap"; - if (ToRawKey(key) < direct_map_.get_deleter().size()) { - return direct_map_[ToRawKey(key)]; - } + const RawKey raw_key = Traits::ToRawKey(key); + if (raw_key < direct_map_.get_deleter().size()) return direct_map_[raw_key]; if (ABSL_PREDICT_TRUE(slow_map_ == nullptr)) return nullptr; - return FindSlow(key); -} - -template <typename Key, typename Value, Key expected_min_key, - size_t array_capacity> -const Value* absl_nullable -HybridDirectMapImpl<Key, Value, expected_min_key, array_capacity>::FindSlow( - Key key) const { - const auto iter = slow_map_->find(key); + const auto iter = slow_map_->find(raw_key); if (iter == slow_map_->end()) return nullptr; return &iter->second; }
diff --git a/riegeli/messages/field_handler_map.h b/riegeli/messages/field_handler_map.h index 018d98b..b6026e5 100644 --- a/riegeli/messages/field_handler_map.h +++ b/riegeli/messages/field_handler_map.h
@@ -172,12 +172,15 @@ // For `FieldAction` and `LengthDelimitedActions`. friend class FieldHandlerMapBuilder<Context...>; - HybridDirectMap<int, FieldAction<uint64_t>, 1> varint_handlers_; - HybridDirectMap<int, FieldAction<uint32_t>, 1> fixed32_handlers_; - HybridDirectMap<int, FieldAction<uint64_t>, 1> fixed64_handlers_; - HybridDirectMap<int, LengthDelimitedActions, 1> length_delimited_handlers_; - HybridDirectMap<int, FieldAction<>, 1> start_group_handlers_; - HybridDirectMap<int, FieldAction<>, 1> end_group_handlers_; + template <typename Value> + using FieldMap = HybridDirectMap<int, Value, HybridDirectTraits<int, 1>>; + + FieldMap<FieldAction<uint64_t>> varint_handlers_; + FieldMap<FieldAction<uint32_t>> fixed32_handlers_; + FieldMap<FieldAction<uint64_t>> fixed64_handlers_; + FieldMap<LengthDelimitedActions> length_delimited_handlers_; + FieldMap<FieldAction<>> start_group_handlers_; + FieldMap<FieldAction<>> end_group_handlers_; }; template <typename... Context>