diff options
author | gritukan <gritukan@yandex-team.ru> | 2022-02-10 16:47:53 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:47:53 +0300 |
commit | 5ab2c1182d0b02a3880e1869c6351b7ba802a19b (patch) | |
tree | f1d99c4a9a7e3f3c2ed90004db7cd7dc8502c2ce /library | |
parent | 2a4a975b112fa0fa138abc7457fe67e0e1e7fd02 (diff) | |
download | ydb-5ab2c1182d0b02a3880e1869c6351b7ba802a19b.tar.gz |
Restoring authorship annotation for <gritukan@yandex-team.ru>. Commit 1 of 2.
Diffstat (limited to 'library')
22 files changed, 630 insertions, 630 deletions
diff --git a/library/cpp/logger/thread.cpp b/library/cpp/logger/thread.cpp index 0ccf9e374b..8e2e89ff88 100644 --- a/library/cpp/logger/thread.cpp +++ b/library/cpp/logger/thread.cpp @@ -106,10 +106,10 @@ public: Slave_->ReopenLogNoFlush(); } - inline size_t QueueSize() const { - return Queue_.Size(); - } - + inline size_t QueueSize() const { + return Queue_.Size(); + } + private: TLogBackend* Slave_; TThreadPool Queue_{"ThreadedLogBack"}; @@ -145,10 +145,10 @@ void TThreadedLogBackend::WriteEmergencyData(const TLogRecord& rec) { Impl_->WriteEmergencyData(rec); } -size_t TThreadedLogBackend::QueueSize() const { - return Impl_->QueueSize(); -} - +size_t TThreadedLogBackend::QueueSize() const { + return Impl_->QueueSize(); +} + TOwningThreadedLogBackend::TOwningThreadedLogBackend(TLogBackend* slave) : THolder<TLogBackend>(slave) , TThreadedLogBackend(Get()) diff --git a/library/cpp/yt/memory/blob.h b/library/cpp/yt/memory/blob.h index 99441fb8c9..2b275ed261 100644 --- a/library/cpp/yt/memory/blob.h +++ b/library/cpp/yt/memory/blob.h @@ -119,12 +119,12 @@ public: } //! Returns the size. - Y_FORCE_INLINE size_t size() const - { - return Size_; - } - - //! Returns the size. + Y_FORCE_INLINE size_t size() const + { + return Size_; + } + + //! Returns the size. Y_FORCE_INLINE size_t Size() const { return Size_; diff --git a/library/cpp/yt/memory/range.h b/library/cpp/yt/memory/range.h index 6c71aa9496..6fe43d4cf3 100644 --- a/library/cpp/yt/memory/range.h +++ b/library/cpp/yt/memory/range.h @@ -77,13 +77,13 @@ public: , Length_(end - begin) { } - //! Constructs a TRange from a TCompactVector. - template <size_t N> - TRange(const TCompactVector<T, N>& elements) - : Data_(elements.data()) - , Length_(elements.size()) - { } - + //! Constructs a TRange from a TCompactVector. + template <size_t N> + TRange(const TCompactVector<T, N>& elements) + : Data_(elements.data()) + , Length_(elements.size()) + { } + //! Constructs a TRange from an std::vector. template <class A> TRange(const std::vector<T, A>& elements) @@ -234,13 +234,13 @@ TRange<T> MakeRange(const T* begin, const T* end) return TRange<T>(begin, end); } -//! Constructs a TRange from a TCompactVector. -template <class T, size_t N> -TRange<T> MakeRange(const TCompactVector<T, N>& elements) -{ - return elements; -} - +//! Constructs a TRange from a TCompactVector. +template <class T, size_t N> +TRange<T> MakeRange(const TCompactVector<T, N>& elements) +{ + return elements; +} + //! "Copy-constructor". template <class T> TRange<T> MakeRange(TRange<T> range) @@ -327,12 +327,12 @@ public: : TRange<T>(begin, end) { } - //! Constructs a TMutableRange from a TCompactVector. - template <size_t N> - TMutableRange(TCompactVector<T, N>& elements) - : TRange<T>(elements) - { } - + //! Constructs a TMutableRange from a TCompactVector. + template <size_t N> + TMutableRange(TCompactVector<T, N>& elements) + : TRange<T>(elements) + { } + //! Constructs a TMutableRange from an std::vector. TMutableRange(std::vector<T>& elements) : TRange<T>(elements) @@ -445,13 +445,13 @@ TMutableRange<T> MakeMutableRange(T* begin, T* end) return TMutableRange<T>(begin, end); } -//! Constructs a TMutableRange from a TCompactVector. -template <class T, size_t N> -TMutableRange<T> MakeMutableRange(TCompactVector<T, N>& elements) -{ - return elements; -} - +//! Constructs a TMutableRange from a TCompactVector. +template <class T, size_t N> +TMutableRange<T> MakeMutableRange(TCompactVector<T, N>& elements) +{ + return elements; +} + //! "Copy-constructor". template <class T> TMutableRange<T> MakeMutableRange(TMutableRange<T> range) diff --git a/library/cpp/yt/memory/ref-inl.h b/library/cpp/yt/memory/ref-inl.h index 79be8356c5..70fc8ae29d 100644 --- a/library/cpp/yt/memory/ref-inl.h +++ b/library/cpp/yt/memory/ref-inl.h @@ -461,11 +461,11 @@ Y_FORCE_INLINE size_t TSharedRefArray::Size() const return Impl_ ? Impl_->Size() : 0; } -Y_FORCE_INLINE size_t TSharedRefArray::size() const -{ - return Impl_ ? Impl_->Size() : 0; -} - +Y_FORCE_INLINE size_t TSharedRefArray::size() const +{ + return Impl_ ? Impl_->Size() : 0; +} + Y_FORCE_INLINE bool TSharedRefArray::Empty() const { return Impl_ ? Impl_->Empty() : true; diff --git a/library/cpp/yt/memory/ref.h b/library/cpp/yt/memory/ref.h index 73d19d9013..7d51df3bea 100644 --- a/library/cpp/yt/memory/ref.h +++ b/library/cpp/yt/memory/ref.h @@ -278,7 +278,7 @@ public: void Reset(); size_t Size() const; - size_t size() const; + size_t size() const; i64 ByteSize() const; bool Empty() const; const TSharedRef& operator [] (size_t index) const; diff --git a/library/cpp/yt/memory/shared_range.h b/library/cpp/yt/memory/shared_range.h index 9841d7a0df..46c8936bed 100644 --- a/library/cpp/yt/memory/shared_range.h +++ b/library/cpp/yt/memory/shared_range.h @@ -10,9 +10,9 @@ namespace NYT { //////////////////////////////////////////////////////////////////////////////// -template <class T, size_t N> -class TCompactVector; - +template <class T, size_t N> +class TCompactVector; + //! TRange with ownership semantics. template <class T> class TSharedRange @@ -43,13 +43,13 @@ public: , Holder_(std::move(holder)) { } - //! Constructs a TSharedRange from a TCompactVector. - template <size_t N> - TSharedRange(const TCompactVector<T, N>& elements, THolderPtr holder) - : TRange<T>(elements) - , Holder_(std::move(holder)) - { } - + //! Constructs a TSharedRange from a TCompactVector. + template <size_t N> + TSharedRange(const TCompactVector<T, N>& elements, THolderPtr holder) + : TRange<T>(elements) + , Holder_(std::move(holder)) + { } + //! Constructs a TSharedRange from an std::vector. TSharedRange(const std::vector<T>& elements, THolderPtr holder) : TRange<T>(elements) @@ -143,13 +143,13 @@ TSharedRange<T> MakeSharedRange(std::vector<T>&& elements, THolders&&... holders return DoMakeSharedRange<T>(std::move(elements), std::forward<THolders>(holders)...); } -//! Constructs a TSharedRange by taking ownership of an TCompactVector. -template <class T, size_t N, class... THolders> -TSharedRange<T> MakeSharedRange(TCompactVector<T, N>&& elements, THolders&&... holders) -{ - return DoMakeSharedRange<T>(std::move(elements), std::forward<THolders>(holders)...); -} - +//! Constructs a TSharedRange by taking ownership of an TCompactVector. +template <class T, size_t N, class... THolders> +TSharedRange<T> MakeSharedRange(TCompactVector<T, N>&& elements, THolders&&... holders) +{ + return DoMakeSharedRange<T>(std::move(elements), std::forward<THolders>(holders)...); +} + //! Constructs a TSharedRange by copying an std::vector. template <class T, class... THolders> TSharedRange<T> MakeSharedRange(const std::vector<T>& elements, THolders&&... holders) @@ -209,13 +209,13 @@ public: , Holder_(std::move(holder)) { } - //! Constructs a TSharedMutableRange from a TCompactVector. - template <size_t N> - TSharedMutableRange(TCompactVector<T, N>& elements, THolderPtr holder) - : TMutableRange<T>(elements) - , Holder_(std::move(holder)) - { } - + //! Constructs a TSharedMutableRange from a TCompactVector. + template <size_t N> + TSharedMutableRange(TCompactVector<T, N>& elements, THolderPtr holder) + : TMutableRange<T>(elements) + , Holder_(std::move(holder)) + { } + //! Constructs a TSharedMutableRange from an std::vector. TSharedMutableRange(std::vector<T>& elements, THolderPtr holder) : TMutableRange<T>(elements) diff --git a/library/cpp/yt/misc/enum-inl.h b/library/cpp/yt/misc/enum-inl.h index 59ef704775..c574761dd7 100644 --- a/library/cpp/yt/misc/enum-inl.h +++ b/library/cpp/yt/misc/enum-inl.h @@ -177,13 +177,13 @@ static constexpr bool AreValuesDistinct(const TValues& values) #define ENUM__END_TRAITS(name) \ }; \ \ - [[maybe_unused]] inline TEnumTraitsImpl_##name GetEnumTraitsImpl(name) \ + [[maybe_unused]] inline TEnumTraitsImpl_##name GetEnumTraitsImpl(name) \ { \ return TEnumTraitsImpl_##name(); \ } \ \ using ::ToString; \ - [[maybe_unused]] inline TString ToString(name value) \ + [[maybe_unused]] inline TString ToString(name value) \ { \ return ::NYT::TEnumTraits<name>::ToString(value); \ } @@ -324,13 +324,13 @@ bool TEnumIndexedVector<E, T, Min, Max>::IsDomainValue(E value) //////////////////////////////////////////////////////////////////////////////// #define ENUM__BINARY_BITWISE_OPERATOR(T, assignOp, op) \ - [[maybe_unused]] inline constexpr T operator op (T lhs, T rhs) \ + [[maybe_unused]] inline constexpr T operator op (T lhs, T rhs) \ { \ using TUnderlying = typename TEnumTraits<T>::TUnderlying; \ return T(static_cast<TUnderlying>(lhs) op static_cast<TUnderlying>(rhs)); \ } \ \ - [[maybe_unused]] inline T& operator assignOp (T& lhs, T rhs) \ + [[maybe_unused]] inline T& operator assignOp (T& lhs, T rhs) \ { \ using TUnderlying = typename TEnumTraits<T>::TUnderlying; \ lhs = T(static_cast<TUnderlying>(lhs) op static_cast<TUnderlying>(rhs)); \ @@ -338,20 +338,20 @@ bool TEnumIndexedVector<E, T, Min, Max>::IsDomainValue(E value) } #define ENUM__UNARY_BITWISE_OPERATOR(T, op) \ - [[maybe_unused]] inline constexpr T operator op (T value) \ + [[maybe_unused]] inline constexpr T operator op (T value) \ { \ using TUnderlying = typename TEnumTraits<T>::TUnderlying; \ return T(op static_cast<TUnderlying>(value)); \ } #define ENUM__BIT_SHIFT_OPERATOR(T, assignOp, op) \ - [[maybe_unused]] inline constexpr T operator op (T lhs, size_t rhs) \ + [[maybe_unused]] inline constexpr T operator op (T lhs, size_t rhs) \ { \ using TUnderlying = typename TEnumTraits<T>::TUnderlying; \ return T(static_cast<TUnderlying>(lhs) op rhs); \ } \ \ - [[maybe_unused]] inline T& operator assignOp (T& lhs, size_t rhs) \ + [[maybe_unused]] inline T& operator assignOp (T& lhs, size_t rhs) \ { \ using TUnderlying = typename TEnumTraits<T>::TUnderlying; \ lhs = T(static_cast<TUnderlying>(lhs) op rhs); \ diff --git a/library/cpp/yt/small_containers/compact_flat_map-inl.h b/library/cpp/yt/small_containers/compact_flat_map-inl.h index 45a4dd1de3..7323815f09 100644 --- a/library/cpp/yt/small_containers/compact_flat_map-inl.h +++ b/library/cpp/yt/small_containers/compact_flat_map-inl.h @@ -1,7 +1,7 @@ -#ifndef COMPACT_FLAT_MAP_INL_H_ -#error "Direct inclusion of this file is not allowed, include compact_flat_map.h" +#ifndef COMPACT_FLAT_MAP_INL_H_ +#error "Direct inclusion of this file is not allowed, include compact_flat_map.h" // For the sake of sane code completion. -#include "compact_flat_map.h" +#include "compact_flat_map.h" #endif namespace NYT { @@ -10,93 +10,93 @@ namespace NYT { template <class K, class V, unsigned N> template <class TInputIterator> -TCompactFlatMap<K, V, N>::TCompactFlatMap(TInputIterator begin, TInputIterator end) +TCompactFlatMap<K, V, N>::TCompactFlatMap(TInputIterator begin, TInputIterator end) { insert(begin, end); } template <class K, class V, unsigned N> -bool TCompactFlatMap<K, V, N>::operator==(const TCompactFlatMap& rhs) const +bool TCompactFlatMap<K, V, N>::operator==(const TCompactFlatMap& rhs) const { return Storage_ == rhs.Storage_; } template <class K, class V, unsigned N> -bool TCompactFlatMap<K, V, N>::operator!=(const TCompactFlatMap& rhs) const +bool TCompactFlatMap<K, V, N>::operator!=(const TCompactFlatMap& rhs) const { return !(*this == rhs); } template <class K, class V, unsigned N> -typename TCompactFlatMap<K, V, N>::iterator TCompactFlatMap<K, V, N>::begin() +typename TCompactFlatMap<K, V, N>::iterator TCompactFlatMap<K, V, N>::begin() { return Storage_.begin(); } template <class K, class V, unsigned N> -typename TCompactFlatMap<K, V, N>::const_iterator TCompactFlatMap<K, V, N>::begin() const +typename TCompactFlatMap<K, V, N>::const_iterator TCompactFlatMap<K, V, N>::begin() const { return Storage_.begin(); } template <class K, class V, unsigned N> -typename TCompactFlatMap<K, V, N>::iterator TCompactFlatMap<K, V, N>::end() +typename TCompactFlatMap<K, V, N>::iterator TCompactFlatMap<K, V, N>::end() { return Storage_.end(); } template <class K, class V, unsigned N> -typename TCompactFlatMap<K, V, N>::const_iterator TCompactFlatMap<K, V, N>::end() const +typename TCompactFlatMap<K, V, N>::const_iterator TCompactFlatMap<K, V, N>::end() const { return Storage_.end(); } template <class K, class V, unsigned N> -void TCompactFlatMap<K, V, N>::reserve(size_type n) +void TCompactFlatMap<K, V, N>::reserve(size_type n) { Storage_.reserve(n); } template <class K, class V, unsigned N> -typename TCompactFlatMap<K, V, N>::size_type TCompactFlatMap<K, V, N>::size() const +typename TCompactFlatMap<K, V, N>::size_type TCompactFlatMap<K, V, N>::size() const { return Storage_.size(); } template <class K, class V, unsigned N> -int TCompactFlatMap<K, V, N>::ssize() const +int TCompactFlatMap<K, V, N>::ssize() const { return static_cast<int>(Storage_.size()); } template <class K, class V, unsigned N> -bool TCompactFlatMap<K, V, N>::empty() const +bool TCompactFlatMap<K, V, N>::empty() const { return Storage_.empty(); } template <class K, class V, unsigned N> -void TCompactFlatMap<K, V, N>::clear() +void TCompactFlatMap<K, V, N>::clear() { Storage_.clear(); } template <class K, class V, unsigned N> -typename TCompactFlatMap<K, V, N>::iterator TCompactFlatMap<K, V, N>::find(const K& k) +typename TCompactFlatMap<K, V, N>::iterator TCompactFlatMap<K, V, N>::find(const K& k) { auto [rangeBegin, rangeEnd] = EqualRange(k); return rangeBegin == rangeEnd ? end() : rangeBegin; } template <class K, class V, unsigned N> -typename TCompactFlatMap<K, V, N>::const_iterator TCompactFlatMap<K, V, N>::find(const K& k) const +typename TCompactFlatMap<K, V, N>::const_iterator TCompactFlatMap<K, V, N>::find(const K& k) const { auto [rangeBegin, rangeEnd] = EqualRange(k); return rangeBegin == rangeEnd ? end() : rangeBegin; } template <class K, class V, unsigned N> -bool TCompactFlatMap<K, V, N>::contains(const K& k) const +bool TCompactFlatMap<K, V, N>::contains(const K& k) const { return find(k) != end(); } @@ -115,7 +115,7 @@ auto TCompactFlatMap<K, V, N>::insert(const value_type& value) -> std::pair<iter template <class K, class V, unsigned N> template <class TInputIterator> -void TCompactFlatMap<K, V, N>::insert(TInputIterator begin, TInputIterator end) +void TCompactFlatMap<K, V, N>::insert(TInputIterator begin, TInputIterator end) { for (auto it = begin; it != end; ++it) { insert(*it); @@ -130,40 +130,40 @@ auto TCompactFlatMap<K, V, N>::emplace(TArgs&&... args) -> std::pair<iterator, b } template <class K, class V, unsigned N> -V& TCompactFlatMap<K, V, N>::operator[](const K& k) +V& TCompactFlatMap<K, V, N>::operator[](const K& k) { auto [it, inserted] = insert({k, V()}); return it->second; } template <class K, class V, unsigned N> -void TCompactFlatMap<K, V, N>::erase(const K& k) +void TCompactFlatMap<K, V, N>::erase(const K& k) { auto [rangeBegin, rangeEnd] = EqualRange(k); erase(rangeBegin, rangeEnd); } template <class K, class V, unsigned N> -void TCompactFlatMap<K, V, N>::erase(iterator pos) +void TCompactFlatMap<K, V, N>::erase(iterator pos) { Storage_.erase(pos); - - // Try to keep the storage inline. This is why erase doesn't return an iterator. - Storage_.shrink_to_small(); + + // Try to keep the storage inline. This is why erase doesn't return an iterator. + Storage_.shrink_to_small(); } template <class K, class V, unsigned N> -void TCompactFlatMap<K, V, N>::erase(iterator b, iterator e) +void TCompactFlatMap<K, V, N>::erase(iterator b, iterator e) { Storage_.erase(b, e); - - // Try to keep the storage inline. This is why erase doesn't return an iterator. - Storage_.shrink_to_small(); + + // Try to keep the storage inline. This is why erase doesn't return an iterator. + Storage_.shrink_to_small(); } template <class K, class V, unsigned N> -std::pair<typename TCompactFlatMap<K, V, N>::iterator, typename TCompactFlatMap<K, V, N>::iterator> -TCompactFlatMap<K, V, N>::EqualRange(const K& k) +std::pair<typename TCompactFlatMap<K, V, N>::iterator, typename TCompactFlatMap<K, V, N>::iterator> +TCompactFlatMap<K, V, N>::EqualRange(const K& k) { auto result = std::equal_range(Storage_.begin(), Storage_.end(), k, TKeyComparer()); YT_ASSERT(std::distance(result.first, result.second) <= 1); @@ -171,8 +171,8 @@ TCompactFlatMap<K, V, N>::EqualRange(const K& k) } template <class K, class V, unsigned N> -std::pair<typename TCompactFlatMap<K, V, N>::const_iterator, typename TCompactFlatMap<K, V, N>::const_iterator> -TCompactFlatMap<K, V, N>::EqualRange(const K& k) const +std::pair<typename TCompactFlatMap<K, V, N>::const_iterator, typename TCompactFlatMap<K, V, N>::const_iterator> +TCompactFlatMap<K, V, N>::EqualRange(const K& k) const { auto result = std::equal_range(Storage_.begin(), Storage_.end(), k, TKeyComparer()); YT_ASSERT(std::distance(result.first, result.second) <= 1); diff --git a/library/cpp/yt/small_containers/compact_flat_map.h b/library/cpp/yt/small_containers/compact_flat_map.h index 13bdc0e9da..13a243c366 100644 --- a/library/cpp/yt/small_containers/compact_flat_map.h +++ b/library/cpp/yt/small_containers/compact_flat_map.h @@ -1,12 +1,12 @@ #pragma once -#include "compact_vector.h" +#include "compact_vector.h" namespace NYT { /////////////////////////////////////////////////////////////////////////////// -//! A flat map implementation over TCompactVector that tries to keep data inline. +//! A flat map implementation over TCompactVector that tries to keep data inline. /*! * Similarly to SmallSet, this is implemented via binary search over a sorted * vector. Unlike SmallSet, however, this one never falls back to std::map (or @@ -22,17 +22,17 @@ namespace NYT { * any call to insert or erase may potentially invalidate all iterators. */ template <class K, class V, unsigned N> -class TCompactFlatMap +class TCompactFlatMap { public: - // NB: can't make this pair<const K, V> as TCompactVector requires its type + // NB: can't make this pair<const K, V> as TCompactVector requires its type // parameter to be copy-assignable. using value_type = std::pair<K, V>; using key_type = K; using mapped_type = V; private: - using TStorage = TCompactVector<value_type, N>; + using TStorage = TCompactVector<value_type, N>; struct TKeyComparer { @@ -52,13 +52,13 @@ public: using const_iterator = typename TStorage::const_iterator; using size_type = size_t; - TCompactFlatMap() = default; + TCompactFlatMap() = default; template <class TInputIterator> - TCompactFlatMap(TInputIterator begin, TInputIterator end); + TCompactFlatMap(TInputIterator begin, TInputIterator end); - bool operator==(const TCompactFlatMap& rhs) const; - bool operator!=(const TCompactFlatMap& rhs) const; + bool operator==(const TCompactFlatMap& rhs) const; + bool operator!=(const TCompactFlatMap& rhs) const; iterator begin(); const_iterator begin() const; @@ -104,6 +104,6 @@ private: } // namespace NYT -#define COMPACT_FLAT_MAP_INL_H_ -#include "compact_flat_map-inl.h" -#undef COMPACT_FLAT_MAP_INL_H_ +#define COMPACT_FLAT_MAP_INL_H_ +#include "compact_flat_map-inl.h" +#undef COMPACT_FLAT_MAP_INL_H_ diff --git a/library/cpp/yt/small_containers/compact_heap-inl.h b/library/cpp/yt/small_containers/compact_heap-inl.h index 2c6b3507ba..ac99ea7333 100644 --- a/library/cpp/yt/small_containers/compact_heap-inl.h +++ b/library/cpp/yt/small_containers/compact_heap-inl.h @@ -1,152 +1,152 @@ -#ifndef COMPACT_HEAP_INL_H_ -#error "Direct inclusion of this file is not allowed, include compact_heap.h" -// For the sake of sane code completion. -#include "compact_heap.h" -#endif - -#include <library/cpp/yt/assert/assert.h> - -#include <algorithm> - -namespace NYT { - -//////////////////////////////////////////////////////////////////////////////// - -template <class T, size_t N, class C> -TCompactHeap<T, N, C>::TCompactHeap(C comparator) noexcept - : Comparator_(TReverseComparator(std::move(comparator))) -{ } - -template <class T, size_t N, class C> -void TCompactHeap<T, N, C>::push(T value) -{ - bool wasInline = IsInline(); - Heap_.push_back(std::move(value)); - if (Y_UNLIKELY(!IsInline())) { - if (wasInline) { - std::make_heap(Heap_.begin(), Heap_.end(), Comparator_); - } else { - std::push_heap(Heap_.begin(), Heap_.end(), Comparator_); - } - } -} - -template <class T, size_t N, class C> -void TCompactHeap<T, N, C>::pop() -{ - YT_ASSERT(!empty()); - - if (Y_LIKELY(IsInline())) { - auto minIt = std::max_element(Heap_.begin(), Heap_.end(), Comparator_); - std::swap(*minIt, Heap_.back()); - Heap_.pop_back(); - } else { - std::pop_heap(Heap_.begin(), Heap_.end(), Comparator_); - Heap_.pop_back(); - } -} - -template <class T, size_t N, class C> -auto TCompactHeap<T, N, C>::get_min() const -> const_reference -{ - YT_ASSERT(!empty()); - - if (Y_LIKELY(IsInline())) { - return *std::max_element(Heap_.begin(), Heap_.end(), Comparator_); - } else { - return Heap_.front(); - } -} - -template <class T, size_t N, class C> -auto TCompactHeap<T, N, C>::extract_min() -> value_type -{ - YT_ASSERT(!empty()); - - if (Y_LIKELY(IsInline())) { - auto minIt = std::max_element(Heap_.begin(), Heap_.end(), Comparator_); - std::swap(*minIt, Heap_.back()); - auto value = Heap_.back(); - Heap_.pop_back(); - - return value; - } else { - std::pop_heap(Heap_.begin(), Heap_.end(), Comparator_); - auto value = std::move(Heap_.back()); - Heap_.pop_back(); - - return value; - } -} - -template <class T, size_t N, class C> -auto TCompactHeap<T, N, C>::begin() const -> const_iterator -{ - return Heap_.begin(); -} - -template <class T, size_t N, class C> -auto TCompactHeap<T, N, C>::end() const -> const_iterator -{ - return Heap_.end(); -} - -template <class T, size_t N, class C> -void TCompactHeap<T, N, C>::swap(TCompactHeap<T, N, C>& other) -{ - Heap_.swap(other.Heap_); - std::swap(Comparator_, other.Comparator_); -} - -template <class T, size_t N, class C> -size_t TCompactHeap<T, N, C>::size() const -{ - return Heap_.size(); -} - -template <class T, size_t N, class C> -size_t TCompactHeap<T, N, C>::capacity() const -{ - return Heap_.capacity(); -} - -template <class T, size_t N, class C> -size_t TCompactHeap<T, N, C>::max_size() const -{ - return Heap_.max_size(); -} - -template <class T, size_t N, class C> -bool TCompactHeap<T, N, C>::empty() const -{ - return Heap_.empty(); -} - -template <class T, size_t N, class C> -void TCompactHeap<T, N, C>::shrink_to_small() -{ - Heap_.shrink_to_small(); -} - -template <class T, size_t N, class C> -bool TCompactHeap<T, N, C>::IsInline() const -{ - return Heap_.capacity() == N; -} - -//////////////////////////////////////////////////////////////////////////////// - -template <class T, size_t N, class C> -TCompactHeap<T, N, C>::TReverseComparator::TReverseComparator(C underlying) - : Underlying_(std::move(underlying)) -{ } - -template <class T, size_t N, class C> -bool TCompactHeap<T, N, C>::TReverseComparator::operator()(const T& lhs, const T& rhs) const -{ - return Underlying_(rhs, lhs); -} - -//////////////////////////////////////////////////////////////////////////////// - -} // namespace NYT +#ifndef COMPACT_HEAP_INL_H_ +#error "Direct inclusion of this file is not allowed, include compact_heap.h" +// For the sake of sane code completion. +#include "compact_heap.h" +#endif + +#include <library/cpp/yt/assert/assert.h> + +#include <algorithm> + +namespace NYT { + +//////////////////////////////////////////////////////////////////////////////// + +template <class T, size_t N, class C> +TCompactHeap<T, N, C>::TCompactHeap(C comparator) noexcept + : Comparator_(TReverseComparator(std::move(comparator))) +{ } + +template <class T, size_t N, class C> +void TCompactHeap<T, N, C>::push(T value) +{ + bool wasInline = IsInline(); + Heap_.push_back(std::move(value)); + if (Y_UNLIKELY(!IsInline())) { + if (wasInline) { + std::make_heap(Heap_.begin(), Heap_.end(), Comparator_); + } else { + std::push_heap(Heap_.begin(), Heap_.end(), Comparator_); + } + } +} + +template <class T, size_t N, class C> +void TCompactHeap<T, N, C>::pop() +{ + YT_ASSERT(!empty()); + + if (Y_LIKELY(IsInline())) { + auto minIt = std::max_element(Heap_.begin(), Heap_.end(), Comparator_); + std::swap(*minIt, Heap_.back()); + Heap_.pop_back(); + } else { + std::pop_heap(Heap_.begin(), Heap_.end(), Comparator_); + Heap_.pop_back(); + } +} + +template <class T, size_t N, class C> +auto TCompactHeap<T, N, C>::get_min() const -> const_reference +{ + YT_ASSERT(!empty()); + + if (Y_LIKELY(IsInline())) { + return *std::max_element(Heap_.begin(), Heap_.end(), Comparator_); + } else { + return Heap_.front(); + } +} + +template <class T, size_t N, class C> +auto TCompactHeap<T, N, C>::extract_min() -> value_type +{ + YT_ASSERT(!empty()); + + if (Y_LIKELY(IsInline())) { + auto minIt = std::max_element(Heap_.begin(), Heap_.end(), Comparator_); + std::swap(*minIt, Heap_.back()); + auto value = Heap_.back(); + Heap_.pop_back(); + + return value; + } else { + std::pop_heap(Heap_.begin(), Heap_.end(), Comparator_); + auto value = std::move(Heap_.back()); + Heap_.pop_back(); + + return value; + } +} + +template <class T, size_t N, class C> +auto TCompactHeap<T, N, C>::begin() const -> const_iterator +{ + return Heap_.begin(); +} + +template <class T, size_t N, class C> +auto TCompactHeap<T, N, C>::end() const -> const_iterator +{ + return Heap_.end(); +} + +template <class T, size_t N, class C> +void TCompactHeap<T, N, C>::swap(TCompactHeap<T, N, C>& other) +{ + Heap_.swap(other.Heap_); + std::swap(Comparator_, other.Comparator_); +} + +template <class T, size_t N, class C> +size_t TCompactHeap<T, N, C>::size() const +{ + return Heap_.size(); +} + +template <class T, size_t N, class C> +size_t TCompactHeap<T, N, C>::capacity() const +{ + return Heap_.capacity(); +} + +template <class T, size_t N, class C> +size_t TCompactHeap<T, N, C>::max_size() const +{ + return Heap_.max_size(); +} + +template <class T, size_t N, class C> +bool TCompactHeap<T, N, C>::empty() const +{ + return Heap_.empty(); +} + +template <class T, size_t N, class C> +void TCompactHeap<T, N, C>::shrink_to_small() +{ + Heap_.shrink_to_small(); +} + +template <class T, size_t N, class C> +bool TCompactHeap<T, N, C>::IsInline() const +{ + return Heap_.capacity() == N; +} + +//////////////////////////////////////////////////////////////////////////////// + +template <class T, size_t N, class C> +TCompactHeap<T, N, C>::TReverseComparator::TReverseComparator(C underlying) + : Underlying_(std::move(underlying)) +{ } + +template <class T, size_t N, class C> +bool TCompactHeap<T, N, C>::TReverseComparator::operator()(const T& lhs, const T& rhs) const +{ + return Underlying_(rhs, lhs); +} + +//////////////////////////////////////////////////////////////////////////////// + +} // namespace NYT diff --git a/library/cpp/yt/small_containers/compact_heap.h b/library/cpp/yt/small_containers/compact_heap.h index 951b36962d..34daf12e50 100644 --- a/library/cpp/yt/small_containers/compact_heap.h +++ b/library/cpp/yt/small_containers/compact_heap.h @@ -1,75 +1,75 @@ -#pragma once - -#include "compact_vector.h" - -namespace NYT { - -//////////////////////////////////////////////////////////////////////////////// - -//! A heap structure optimized for storing elements inline -//! and with little memory overhead. See TCompactVector. -/*! - * When inline, uses linear search for selecting minimum - * instead of storing heap. - */ -template <class T, size_t N, class C = std::less<T>> -class TCompactHeap -{ -public: - static_assert(N <= 8, "TCompactHeap is not optimal for large N"); - - explicit TCompactHeap(C comparator = C()) noexcept; - - using value_type = T; - - using const_reference = const T&; - - using const_iterator = const T*; - - using difference_type = ptrdiff_t; - using size_type = size_t; - - void push(T value); - void pop(); - - const_reference get_min() const; - value_type extract_min(); - - const_iterator begin() const; - const_iterator end() const; - - void swap(TCompactHeap<T, N, C>& other); - - size_t size() const; - size_t capacity() const; - size_t max_size() const; - - bool empty() const; - - void shrink_to_small(); - -private: - TCompactVector<T, N> Heap_; - - class TReverseComparator - { - public: - explicit TReverseComparator(C underlying); - - bool operator()(const T& lhs, const T& rhs) const; - - private: - C Underlying_; - }; - TReverseComparator Comparator_; - - bool IsInline() const; -}; - -//////////////////////////////////////////////////////////////////////////////// - -} // namespace NYT - -#define COMPACT_HEAP_INL_H_ -#include "compact_heap-inl.h" -#undef COMPACT_HEAP_INL_H_ +#pragma once + +#include "compact_vector.h" + +namespace NYT { + +//////////////////////////////////////////////////////////////////////////////// + +//! A heap structure optimized for storing elements inline +//! and with little memory overhead. See TCompactVector. +/*! + * When inline, uses linear search for selecting minimum + * instead of storing heap. + */ +template <class T, size_t N, class C = std::less<T>> +class TCompactHeap +{ +public: + static_assert(N <= 8, "TCompactHeap is not optimal for large N"); + + explicit TCompactHeap(C comparator = C()) noexcept; + + using value_type = T; + + using const_reference = const T&; + + using const_iterator = const T*; + + using difference_type = ptrdiff_t; + using size_type = size_t; + + void push(T value); + void pop(); + + const_reference get_min() const; + value_type extract_min(); + + const_iterator begin() const; + const_iterator end() const; + + void swap(TCompactHeap<T, N, C>& other); + + size_t size() const; + size_t capacity() const; + size_t max_size() const; + + bool empty() const; + + void shrink_to_small(); + +private: + TCompactVector<T, N> Heap_; + + class TReverseComparator + { + public: + explicit TReverseComparator(C underlying); + + bool operator()(const T& lhs, const T& rhs) const; + + private: + C Underlying_; + }; + TReverseComparator Comparator_; + + bool IsInline() const; +}; + +//////////////////////////////////////////////////////////////////////////////// + +} // namespace NYT + +#define COMPACT_HEAP_INL_H_ +#include "compact_heap-inl.h" +#undef COMPACT_HEAP_INL_H_ diff --git a/library/cpp/yt/small_containers/compact_set-inl.h b/library/cpp/yt/small_containers/compact_set-inl.h index 75b8600175..92e79dd94b 100644 --- a/library/cpp/yt/small_containers/compact_set-inl.h +++ b/library/cpp/yt/small_containers/compact_set-inl.h @@ -1,7 +1,7 @@ -#ifndef COMPACT_SET_INL_H_ -#error "Direct inclusion of this file is not allowed, include compact_set.h" +#ifndef COMPACT_SET_INL_H_ +#error "Direct inclusion of this file is not allowed, include compact_set.h" // For the sake of sane code completion. -#include "compact_set.h" +#include "compact_set.h" #endif namespace NYT { @@ -9,10 +9,10 @@ namespace NYT { //////////////////////////////////////////////////////////////////////////////// template <typename T, unsigned N, typename C> -class TCompactSet<T, N, C>::const_iterator +class TCompactSet<T, N, C>::const_iterator { private: - friend class TCompactSet<T, N, C>; + friend class TCompactSet<T, N, C>; union { @@ -201,26 +201,26 @@ public: //////////////////////////////////////////////////////////////////////////////// template <typename T, unsigned N, typename C> -bool TCompactSet<T, N, C>::empty() const +bool TCompactSet<T, N, C>::empty() const { return Vector.empty() && Set.empty(); } template <typename T, unsigned N, typename C> -typename TCompactSet<T, N, C>::size_type TCompactSet<T, N, C>::size() const +typename TCompactSet<T, N, C>::size_type TCompactSet<T, N, C>::size() const { return IsSmall() ? Vector.size() : Set.size(); } template <typename T, unsigned N, typename C> -const T& TCompactSet<T, N, C>::front() const +const T& TCompactSet<T, N, C>::front() const { return IsSmall() ? Vector.front() : *Set.begin(); } template <typename T, unsigned N, typename C> -typename TCompactSet<T, N, C>::size_type TCompactSet<T, N, C>::count(const T& v) const +typename TCompactSet<T, N, C>::size_type TCompactSet<T, N, C>::count(const T& v) const { if (IsSmall()) { return std::binary_search(Vector.begin(), Vector.end(), v, C()) ? 1 : 0; @@ -230,7 +230,7 @@ typename TCompactSet<T, N, C>::size_type TCompactSet<T, N, C>::count(const T& v) } template <typename T, unsigned N, typename C> -std::pair<typename TCompactSet<T, N, C>::const_iterator, bool> TCompactSet<T, N, C>::insert(const T& v) +std::pair<typename TCompactSet<T, N, C>::const_iterator, bool> TCompactSet<T, N, C>::insert(const T& v) { if (!IsSmall()) { auto [it, inserted] = Set.insert(v); @@ -257,7 +257,7 @@ std::pair<typename TCompactSet<T, N, C>::const_iterator, bool> TCompactSet<T, N, template <typename T, unsigned N, typename C> template <typename TIter> -void TCompactSet<T, N, C>::insert(TIter i, TIter e) +void TCompactSet<T, N, C>::insert(TIter i, TIter e) { for (; i != e; ++i) { insert(*i); @@ -265,7 +265,7 @@ void TCompactSet<T, N, C>::insert(TIter i, TIter e) } template <typename T, unsigned N, typename C> -bool TCompactSet<T, N, C>::erase(const T& v) +bool TCompactSet<T, N, C>::erase(const T& v) { if (!IsSmall()) { return Set.erase(v); @@ -281,38 +281,38 @@ bool TCompactSet<T, N, C>::erase(const T& v) } template <typename T, unsigned N, typename C> -void TCompactSet<T, N, C>::clear() +void TCompactSet<T, N, C>::clear() { Vector.clear(); Set.clear(); } template <typename T, unsigned N, typename C> -typename TCompactSet<T, N, C>::const_iterator TCompactSet<T, N, C>::begin() const +typename TCompactSet<T, N, C>::const_iterator TCompactSet<T, N, C>::begin() const { return IsSmall() ? const_iterator(Vector.begin()) : const_iterator(Set.begin()); } template <typename T, unsigned N, typename C> -typename TCompactSet<T, N, C>::const_iterator TCompactSet<T, N, C>::cbegin() const +typename TCompactSet<T, N, C>::const_iterator TCompactSet<T, N, C>::cbegin() const { return begin(); } template <typename T, unsigned N, typename C> -typename TCompactSet<T, N, C>::const_iterator TCompactSet<T, N, C>::end() const +typename TCompactSet<T, N, C>::const_iterator TCompactSet<T, N, C>::end() const { return IsSmall() ? const_iterator(Vector.end()) : const_iterator(Set.end()); } template <typename T, unsigned N, typename C> -typename TCompactSet<T, N, C>::const_iterator TCompactSet<T, N, C>::cend() const +typename TCompactSet<T, N, C>::const_iterator TCompactSet<T, N, C>::cend() const { return end(); } template <typename T, unsigned N, typename C> -bool TCompactSet<T, N, C>::IsSmall() const +bool TCompactSet<T, N, C>::IsSmall() const { return Set.empty(); } diff --git a/library/cpp/yt/small_containers/compact_set.h b/library/cpp/yt/small_containers/compact_set.h index 2ca8713ea7..8a5a694ea0 100644 --- a/library/cpp/yt/small_containers/compact_set.h +++ b/library/cpp/yt/small_containers/compact_set.h @@ -7,13 +7,13 @@ // //===----------------------------------------------------------------------===// // -// This file defines the TCompactSet class. +// This file defines the TCompactSet class. // //===----------------------------------------------------------------------===// #pragma once -#include "compact_vector.h" +#include "compact_vector.h" #include <util/system/yassert.h> @@ -24,30 +24,30 @@ namespace NYT { -/// TCompactSet - This maintains a set of unique values, optimizing for the case +/// TCompactSet - This maintains a set of unique values, optimizing for the case /// when the set is small (less than N). In this case, the set can be /// maintained with no mallocs. If the set gets large, we expand to using an /// std::set to maintain reasonable lookup times. /// /// Note that any modification of the set may invalidate *all* iterators. template <typename T, unsigned N, typename C = std::less<T>> -class TCompactSet +class TCompactSet { private: - /// Use a CompactVector to hold the elements here (even though it will never + /// Use a CompactVector to hold the elements here (even though it will never /// reach its 'large' stage) to avoid calling the default ctors of elements /// we will never use. - TCompactVector<T, N> Vector; + TCompactVector<T, N> Vector; std::set<T, C> Set; using TSetConstIterator = typename std::set<T, C>::const_iterator; - using TVectorConstIterator = typename TCompactVector<T, N>::const_iterator; + using TVectorConstIterator = typename TCompactVector<T, N>::const_iterator; public: class const_iterator; using size_type = std::size_t; - TCompactSet() {} + TCompactSet() {} [[nodiscard]] bool empty() const; @@ -80,7 +80,7 @@ private: } // namespace NYT -#define COMPACT_SET_INL_H_ -#include "compact_set-inl.h" -#undef COMPACT_SET_INL_H_ +#define COMPACT_SET_INL_H_ +#include "compact_set-inl.h" +#undef COMPACT_SET_INL_H_ diff --git a/library/cpp/yt/small_containers/compact_vector-inl.h b/library/cpp/yt/small_containers/compact_vector-inl.h index 52507e4768..c24b4e6d1e 100644 --- a/library/cpp/yt/small_containers/compact_vector-inl.h +++ b/library/cpp/yt/small_containers/compact_vector-inl.h @@ -22,9 +22,9 @@ namespace NYT { static_assert(sizeof(uintptr_t) == 8); -// TODO(gritukan, babenko): Uncomment check below after DEVTOOLS-7870. -// static_assert(std::endian::native == std::endian::little); - +// TODO(gritukan, babenko): Uncomment check below after DEVTOOLS-7870. +// static_assert(std::endian::native == std::endian::little); + //////////////////////////////////////////////////////////////////////////////// template <class T> @@ -44,7 +44,7 @@ public: TCompactVectorReallocationPtrAdjuster(TVector* vector, TPtr& ptr) : Vector_(vector) , Ptr_(ptr) - , Index_(ptr >= Vector_->begin() && ptr <= Vector_->end() + , Index_(ptr >= Vector_->begin() && ptr <= Vector_->end() ? std::distance(Vector_->begin(), const_cast<typename TVector::iterator>(ptr)) : -1) { } @@ -94,7 +94,7 @@ TCompactVector<T, N>::TCompactVector(const TCompactVector<T, OtherN>& other) } template <class T, size_t N> -TCompactVector<T, N>::TCompactVector(TCompactVector&& other) noexcept(std::is_nothrow_move_constructible_v<T>) +TCompactVector<T, N>::TCompactVector(TCompactVector&& other) noexcept(std::is_nothrow_move_constructible_v<T>) : TCompactVector() { swap(other); @@ -689,26 +689,26 @@ auto TCompactVector<T, N>::insert(const_iterator pos, std::initializer_list<T> l } template <class T, size_t N> -void TCompactVector<T, N>::shrink_to_small() -{ - if (Y_LIKELY(IsInline())) { - return; - } - - auto size = this->size(); - if (size > N) { - return; - } - - auto* storage = OnHeapMeta_.Storage; - UninitializedMove(storage->Elements, storage->End, &InlineElements_[0]); - Destroy(storage->Elements, storage->End); - ::free(storage); - - InlineMeta_.SizePlusOne = size + 1; -} - -template <class T, size_t N> +void TCompactVector<T, N>::shrink_to_small() +{ + if (Y_LIKELY(IsInline())) { + return; + } + + auto size = this->size(); + if (size > N) { + return; + } + + auto* storage = OnHeapMeta_.Storage; + UninitializedMove(storage->Elements, storage->End, &InlineElements_[0]); + Destroy(storage->Elements, storage->End); + ::free(storage); + + InlineMeta_.SizePlusOne = size + 1; +} + +template <class T, size_t N> bool TCompactVector<T, N>::IsInline() const { return InlineMeta_.SizePlusOne != 0; diff --git a/library/cpp/yt/small_containers/compact_vector.h b/library/cpp/yt/small_containers/compact_vector.h index 6c4a0b0e39..a42a1f0751 100644 --- a/library/cpp/yt/small_containers/compact_vector.h +++ b/library/cpp/yt/small_containers/compact_vector.h @@ -60,7 +60,7 @@ public: TCompactVector(const TCompactVector& other); template <size_t OtherN> TCompactVector(const TCompactVector<T, OtherN>& other); - TCompactVector(TCompactVector&& other) noexcept(std::is_nothrow_move_constructible_v<T>); + TCompactVector(TCompactVector&& other) noexcept(std::is_nothrow_move_constructible_v<T>); template <size_t OtherN> TCompactVector(TCompactVector<T, OtherN>&& other); explicit TCompactVector(size_type count); @@ -144,8 +144,8 @@ public: iterator insert(const_iterator pos, TIterator first, TIterator last); iterator insert(const_iterator pos, std::initializer_list<T> list); - void shrink_to_small(); - + void shrink_to_small(); + private: template <class OtherT, size_t OtherN> friend class TCompactVector; diff --git a/library/cpp/yt/small_containers/unittests/compact_flat_map_ut.cpp b/library/cpp/yt/small_containers/unittests/compact_flat_map_ut.cpp index 0b2f290692..bbc03089bb 100644 --- a/library/cpp/yt/small_containers/unittests/compact_flat_map_ut.cpp +++ b/library/cpp/yt/small_containers/unittests/compact_flat_map_ut.cpp @@ -1,7 +1,7 @@ #include <yt/yt/core/test_framework/framework.h> -#include <yt/yt/core/misc/compact_flat_map.h> - +#include <yt/yt/core/misc/compact_flat_map.h> + #include <string> #include <vector> @@ -10,7 +10,7 @@ namespace { //////////////////////////////////////////////////////////////////////////////// -using TMap = TCompactFlatMap<std::string, std::string, 2>; +using TMap = TCompactFlatMap<std::string, std::string, 2>; TMap CreateMap() { @@ -18,15 +18,15 @@ TMap CreateMap() return {data.begin(), data.end()}; } -TEST(CompactFlatMapTest, DefaultEmpty) -{ +TEST(CompactFlatMapTest, DefaultEmpty) +{ TMap m; EXPECT_TRUE(m.empty()); EXPECT_EQ(m.begin(), m.end()); } -TEST(CompactFlatMapTest, Reserve) -{ +TEST(CompactFlatMapTest, Reserve) +{ // No real way to test reserve - just use it and wiggle about. auto m1 = CreateMap(); TMap m2; @@ -35,26 +35,26 @@ TEST(CompactFlatMapTest, Reserve) EXPECT_EQ(m1.size(), m2.size()); } -TEST(CompactFlatMapTest, Size) -{ +TEST(CompactFlatMapTest, Size) +{ auto m = CreateMap(); - EXPECT_EQ(m.size(), 4u); + EXPECT_EQ(m.size(), 4u); EXPECT_EQ(m.ssize(), 4); m.insert({"Who", "said"}); - EXPECT_EQ(m.size(), 5u); + EXPECT_EQ(m.size(), 5u); EXPECT_EQ(m.ssize(), 5); m.erase("antique"); - EXPECT_EQ(m.size(), 4u); + EXPECT_EQ(m.size(), 4u); EXPECT_EQ(m.ssize(), 4); } -TEST(CompactFlatMapTest, ClearAndEmpty) -{ +TEST(CompactFlatMapTest, ClearAndEmpty) +{ auto m = CreateMap(); EXPECT_FALSE(m.empty()); @@ -71,8 +71,8 @@ TEST(CompactFlatMapTest, ClearAndEmpty) EXPECT_NE(m.begin(), m.end()); } -TEST(CompactFlatMapTest, FindMutable) -{ +TEST(CompactFlatMapTest, FindMutable) +{ auto m = CreateMap(); { auto it = m.find("from"); @@ -91,8 +91,8 @@ TEST(CompactFlatMapTest, FindMutable) } } -TEST(CompactFlatMapTest, FindConst) -{ +TEST(CompactFlatMapTest, FindConst) +{ const auto& m = CreateMap(); { auto it = m.find("from"); @@ -105,26 +105,26 @@ TEST(CompactFlatMapTest, FindConst) } } -TEST(CompactFlatMapTest, Insert) -{ +TEST(CompactFlatMapTest, Insert) +{ auto m = CreateMap(); auto [it, inserted] = m.insert({"Who", "said"}); EXPECT_TRUE(inserted); - EXPECT_EQ(m.ssize(), 5); + EXPECT_EQ(m.ssize(), 5); EXPECT_NE(it, m.end()); EXPECT_EQ(it, m.find("Who")); EXPECT_EQ(it->second, "said"); auto [it2, inserted2] = m.insert({"Who", "told"}); EXPECT_FALSE(inserted2); - EXPECT_EQ(m.ssize(), 5); + EXPECT_EQ(m.ssize(), 5); EXPECT_EQ(it2, it); EXPECT_EQ(it->second, "said"); std::vector<std::pair<std::string, std::string>> data = {{"Two", "vast"}, {"and", "trunkless"}, {"legs", "of"}, {"stone", "Stand"}, {"in", "the"}, {"desert", "..."}}; m.insert(data.begin(), data.end()); - EXPECT_EQ(m.ssize(), 11); + EXPECT_EQ(m.ssize(), 11); EXPECT_NE(m.find("and"), m.end()); EXPECT_EQ(m.find("and")->second, "trunkless"); } @@ -147,33 +147,33 @@ TEST(CompactFlatMapTest, Emplace) EXPECT_EQ(it->second, "place"); } -TEST(CompactFlatMapTest, Subscript) -{ +TEST(CompactFlatMapTest, Subscript) +{ auto m = CreateMap(); EXPECT_EQ(m["antique"], "land"); - EXPECT_EQ(m.ssize(), 4); + EXPECT_EQ(m.ssize(), 4); EXPECT_EQ(m["Who"], ""); - EXPECT_EQ(m.ssize(), 5); + EXPECT_EQ(m.ssize(), 5); } -TEST(CompactFlatMapTest, Erase) -{ +TEST(CompactFlatMapTest, Erase) +{ auto m = CreateMap(); m.erase("antique"); - EXPECT_EQ(m.ssize(), 3); + EXPECT_EQ(m.ssize(), 3); m.erase("Who"); - EXPECT_EQ(m.ssize(), 3); + EXPECT_EQ(m.ssize(), 3); m.erase(m.begin(), m.end()); EXPECT_TRUE(m.empty()); } -TEST(CompactFlatMapTest, GrowShrink) -{ +TEST(CompactFlatMapTest, GrowShrink) +{ TMap m; m.insert({"Two", "vast"}); m.insert({"and", "trunkless"}); @@ -187,13 +187,13 @@ TEST(CompactFlatMapTest, GrowShrink) m.erase("in"); m.erase("desert"); - EXPECT_EQ(m.ssize(), 2); + EXPECT_EQ(m.ssize(), 2); // Must not crash or trigger asan. } -TEST(CompactFlatMapTest, GrowShrinkGrow) -{ +TEST(CompactFlatMapTest, GrowShrinkGrow) +{ TMap m; m.insert({"Two", "vast"}); m.insert({"and", "trunkless"}); @@ -207,14 +207,14 @@ TEST(CompactFlatMapTest, GrowShrinkGrow) m.erase("in"); m.erase("desert"); - EXPECT_EQ(m.ssize(), 2); + EXPECT_EQ(m.ssize(), 2); m.insert({"I", "met"}); m.insert({"a", "traveller"}); m.insert({"from", "an"}); m.insert({"antique", "land"}); - EXPECT_EQ(m.ssize(), 6); + EXPECT_EQ(m.ssize(), 6); // Must not crash or trigger asan. } diff --git a/library/cpp/yt/small_containers/unittests/compact_heap_ut.cpp b/library/cpp/yt/small_containers/unittests/compact_heap_ut.cpp index 259c576e87..70f9622948 100644 --- a/library/cpp/yt/small_containers/unittests/compact_heap_ut.cpp +++ b/library/cpp/yt/small_containers/unittests/compact_heap_ut.cpp @@ -1,108 +1,108 @@ -#include <library/cpp/yt/small_containers/compact_heap.h> - -#include <library/cpp/testing/gtest/gtest.h> - -#include <random> - -namespace NYT { -namespace { - -//////////////////////////////////////////////////////////////////////////////// - -TEST(CompactHeapTest, Simple) -{ - TCompactHeap<int, 2> heap; - heap.push(3); - heap.push(1); - heap.push(2); - - EXPECT_EQ(3u, heap.size()); - EXPECT_EQ(1, heap.extract_min()); - - EXPECT_EQ(2, heap.get_min()); - EXPECT_EQ(2, heap.extract_min()); - - EXPECT_EQ(3, heap.extract_min()); - - EXPECT_TRUE(heap.empty()); -} - -TEST(CompactHeapTest, SimpleComparator) -{ - TCompactHeap<int, 2, std::greater<int>> heap; - heap.push(3); - heap.push(1); - heap.push(2); - - EXPECT_EQ(3u, heap.size()); - EXPECT_EQ(3, heap.extract_min()); - EXPECT_EQ(2, heap.get_min()); - EXPECT_EQ(2, heap.extract_min()); - EXPECT_EQ(1, heap.extract_min()); - EXPECT_TRUE(heap.empty()); -} - -TEST(CompactHeapTest, Capacity) -{ - TCompactHeap<int, 2> heap; - EXPECT_EQ(2u, heap.capacity()); - EXPECT_EQ(0u, heap.size()); - - for (int i = 0; i < 100; ++i) { - heap.push(i); - } - EXPECT_LE(100u, heap.capacity()); - EXPECT_EQ(100u, heap.size()); - - for (int i = 0; i < 99; ++i) { - heap.pop(); - } - EXPECT_LE(100u, heap.capacity()); - EXPECT_EQ(1u, heap.size()); - - heap.shrink_to_small(); - - EXPECT_EQ(2u, heap.capacity()); - EXPECT_EQ(1u, heap.size()); -} - -TEST(CompactHeapTest, Stress) -{ - TCompactHeap<int, 3, std::greater<int>> heap; - std::vector<int> values; - - std::mt19937 rng(42); - for (int iteration = 0; iteration < 1000; ++iteration) { - EXPECT_EQ(values.size(), heap.size()); - EXPECT_EQ(values.empty(), heap.empty()); - - { - std::vector<int> content(heap.begin(), heap.end()); - std::sort(content.rbegin(), content.rend()); - EXPECT_EQ(values, content); - } - - if (!values.empty()) { - EXPECT_EQ(values[0], heap.get_min()); - } - - if (values.empty() || rng() % 2 == 0) { - int x = rng() % 100; - heap.push(x); - values.push_back(x); - std::sort(values.rbegin(), values.rend()); - } else { - if (rng() % 2 == 0) { - EXPECT_EQ(values[0], heap.extract_min()); - } else { - heap.pop(); - } - values.erase(values.begin()); - } - } -} - -//////////////////////////////////////////////////////////////////////////////// - -} // namespace -} // namespace NYT +#include <library/cpp/yt/small_containers/compact_heap.h> + +#include <library/cpp/testing/gtest/gtest.h> + +#include <random> + +namespace NYT { +namespace { + +//////////////////////////////////////////////////////////////////////////////// + +TEST(CompactHeapTest, Simple) +{ + TCompactHeap<int, 2> heap; + heap.push(3); + heap.push(1); + heap.push(2); + + EXPECT_EQ(3u, heap.size()); + EXPECT_EQ(1, heap.extract_min()); + + EXPECT_EQ(2, heap.get_min()); + EXPECT_EQ(2, heap.extract_min()); + + EXPECT_EQ(3, heap.extract_min()); + + EXPECT_TRUE(heap.empty()); +} + +TEST(CompactHeapTest, SimpleComparator) +{ + TCompactHeap<int, 2, std::greater<int>> heap; + heap.push(3); + heap.push(1); + heap.push(2); + + EXPECT_EQ(3u, heap.size()); + EXPECT_EQ(3, heap.extract_min()); + EXPECT_EQ(2, heap.get_min()); + EXPECT_EQ(2, heap.extract_min()); + EXPECT_EQ(1, heap.extract_min()); + EXPECT_TRUE(heap.empty()); +} + +TEST(CompactHeapTest, Capacity) +{ + TCompactHeap<int, 2> heap; + EXPECT_EQ(2u, heap.capacity()); + EXPECT_EQ(0u, heap.size()); + + for (int i = 0; i < 100; ++i) { + heap.push(i); + } + EXPECT_LE(100u, heap.capacity()); + EXPECT_EQ(100u, heap.size()); + + for (int i = 0; i < 99; ++i) { + heap.pop(); + } + EXPECT_LE(100u, heap.capacity()); + EXPECT_EQ(1u, heap.size()); + + heap.shrink_to_small(); + + EXPECT_EQ(2u, heap.capacity()); + EXPECT_EQ(1u, heap.size()); +} + +TEST(CompactHeapTest, Stress) +{ + TCompactHeap<int, 3, std::greater<int>> heap; + std::vector<int> values; + + std::mt19937 rng(42); + for (int iteration = 0; iteration < 1000; ++iteration) { + EXPECT_EQ(values.size(), heap.size()); + EXPECT_EQ(values.empty(), heap.empty()); + + { + std::vector<int> content(heap.begin(), heap.end()); + std::sort(content.rbegin(), content.rend()); + EXPECT_EQ(values, content); + } + + if (!values.empty()) { + EXPECT_EQ(values[0], heap.get_min()); + } + + if (values.empty() || rng() % 2 == 0) { + int x = rng() % 100; + heap.push(x); + values.push_back(x); + std::sort(values.rbegin(), values.rend()); + } else { + if (rng() % 2 == 0) { + EXPECT_EQ(values[0], heap.extract_min()); + } else { + heap.pop(); + } + values.erase(values.begin()); + } + } +} + +//////////////////////////////////////////////////////////////////////////////// + +} // namespace +} // namespace NYT diff --git a/library/cpp/yt/small_containers/unittests/compact_set_ut.cpp b/library/cpp/yt/small_containers/unittests/compact_set_ut.cpp index ebab5846e1..b9bc11c4d2 100644 --- a/library/cpp/yt/small_containers/unittests/compact_set_ut.cpp +++ b/library/cpp/yt/small_containers/unittests/compact_set_ut.cpp @@ -1,4 +1,4 @@ -//===- llvm/unittest/ADT/SmallSetTest.cpp ---------------------------------===// +//===- llvm/unittest/ADT/SmallSetTest.cpp ---------------------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -6,11 +6,11 @@ // //===----------------------------------------------------------------------===// // -// CompactSet unit tests. +// CompactSet unit tests. // //===----------------------------------------------------------------------===// -#include <library/cpp/yt/small_containers/compact_set.h> +#include <library/cpp/yt/small_containers/compact_set.h> #include <library/cpp/testing/gtest/gtest.h> @@ -21,9 +21,9 @@ namespace { //////////////////////////////////////////////////////////////////////////////// -TEST(CompactSetTest, Insert) { +TEST(CompactSetTest, Insert) { - TCompactSet<int, 4> s1; + TCompactSet<int, 4> s1; for (int i = 0; i < 4; i++) s1.insert(i); @@ -39,8 +39,8 @@ TEST(CompactSetTest, Insert) { EXPECT_EQ(0u, s1.count(4)); } -TEST(CompactSetTest, Grow) { - TCompactSet<int, 4> s1; +TEST(CompactSetTest, Grow) { + TCompactSet<int, 4> s1; for (int i = 0; i < 8; i++) s1.insert(i); @@ -53,8 +53,8 @@ TEST(CompactSetTest, Grow) { EXPECT_EQ(0u, s1.count(8)); } -TEST(CompactSetTest, Erase) { - TCompactSet<int, 4> s1; +TEST(CompactSetTest, Erase) { + TCompactSet<int, 4> s1; for (int i = 0; i < 8; i++) s1.insert(i); @@ -74,8 +74,8 @@ TEST(CompactSetTest, Erase) { EXPECT_EQ(0u, s1.count(8)); } -TEST(CompactSetTest, IteratorInt) { - TCompactSet<int, 4> s1; +TEST(CompactSetTest, IteratorInt) { + TCompactSet<int, 4> s1; // Test the 'small' case. for (int i = 0; i < 3; i++) @@ -99,10 +99,10 @@ TEST(CompactSetTest, IteratorInt) { EXPECT_EQ(i, V[i]); } -TEST(CompactSetTest, IteratorString) { - // Test CompactSetIterator for TCompactSet with a type with non-trivial +TEST(CompactSetTest, IteratorString) { + // Test CompactSetIterator for TCompactSet with a type with non-trivial // ctors/dtors. - TCompactSet<std::string, 2> s1; + TCompactSet<std::string, 2> s1; s1.insert("str 1"); s1.insert("str 2"); @@ -128,10 +128,10 @@ TEST(CompactSetTest, IteratorString) { EXPECT_EQ("str 4", V[3]); } -TEST(CompactSetTest, IteratorIncMoveCopy) { - // Test CompactSetIterator for TCompactSet with a type with non-trivial +TEST(CompactSetTest, IteratorIncMoveCopy) { + // Test CompactSetIterator for TCompactSet with a type with non-trivial // ctors/dtors. - TCompactSet<std::string, 2> s1; + TCompactSet<std::string, 2> s1; s1.insert("str 1"); s1.insert("str 2"); @@ -150,8 +150,8 @@ TEST(CompactSetTest, IteratorIncMoveCopy) { // These test weren't taken from llvm. -TEST(CompactSetTest, Empty) { - TCompactSet<int, 10> v; +TEST(CompactSetTest, Empty) { + TCompactSet<int, 10> v; EXPECT_TRUE(v.empty()); auto data = {1, 2, 3, 4, 5}; @@ -180,8 +180,8 @@ TEST(CompactSetTest, Empty) { EXPECT_TRUE(v.empty()); } -TEST(CompactSetTest, ForEach) { - TCompactSet<int, 10> v; +TEST(CompactSetTest, ForEach) { + TCompactSet<int, 10> v; auto data = {10, 9, 3, 4, 1, 5, 6, 8}; diff --git a/library/cpp/yt/small_containers/unittests/compact_vector_ut.cpp b/library/cpp/yt/small_containers/unittests/compact_vector_ut.cpp index 770d62b9fd..3c84933ccc 100644 --- a/library/cpp/yt/small_containers/unittests/compact_vector_ut.cpp +++ b/library/cpp/yt/small_containers/unittests/compact_vector_ut.cpp @@ -8,7 +8,7 @@ // //===----------------------------------------------------------------------===// // -// TCompactVector unit tests. +// TCompactVector unit tests. // //===----------------------------------------------------------------------===// @@ -267,43 +267,43 @@ TYPED_TEST(CompactVectorTest, PushPopTest) { } } -TYPED_TEST(CompactVectorTest, InsertEnd) -{ - SCOPED_TRACE("InsertEnd"); - - TCompactVector<TString, 5> vector; - for (int index = 0; index < 10; ++index) { - vector.insert(vector.end(), ToString(index)); - } - for (int index = 0; index < 10; ++index) { - EXPECT_EQ(vector[index], ToString(index)); - } -} - -TYPED_TEST(CompactVectorTest, ShrinkToSmall) -{ - SCOPED_TRACE("ShrinkToSmall"); - - TCompactVector<TString, 5> vector; - for (int index = 0; index < 10; ++index) { - vector.shrink_to_small(); - vector.push_back(ToString(index)); - } - - for (int index = 0; index < 6; ++index) { - vector.pop_back(); - } - - EXPECT_EQ(std::ssize(vector), 4); - EXPECT_GE(static_cast<int>(vector.capacity()), 10); - vector.shrink_to_small(); - EXPECT_EQ(std::ssize(vector), 4); - EXPECT_EQ(static_cast<int>(vector.capacity()), 5); - for (int index = 0; index < 4; ++index) { - EXPECT_EQ(vector[index], ToString(index)); - } -} - +TYPED_TEST(CompactVectorTest, InsertEnd) +{ + SCOPED_TRACE("InsertEnd"); + + TCompactVector<TString, 5> vector; + for (int index = 0; index < 10; ++index) { + vector.insert(vector.end(), ToString(index)); + } + for (int index = 0; index < 10; ++index) { + EXPECT_EQ(vector[index], ToString(index)); + } +} + +TYPED_TEST(CompactVectorTest, ShrinkToSmall) +{ + SCOPED_TRACE("ShrinkToSmall"); + + TCompactVector<TString, 5> vector; + for (int index = 0; index < 10; ++index) { + vector.shrink_to_small(); + vector.push_back(ToString(index)); + } + + for (int index = 0; index < 6; ++index) { + vector.pop_back(); + } + + EXPECT_EQ(std::ssize(vector), 4); + EXPECT_GE(static_cast<int>(vector.capacity()), 10); + vector.shrink_to_small(); + EXPECT_EQ(std::ssize(vector), 4); + EXPECT_EQ(static_cast<int>(vector.capacity()), 5); + for (int index = 0; index < 4; ++index) { + EXPECT_EQ(vector[index], ToString(index)); + } +} + // Clear test. TYPED_TEST(CompactVectorTest, ClearTest) { SCOPED_TRACE("ClearTest"); diff --git a/library/cpp/yt/small_containers/unittests/ya.make b/library/cpp/yt/small_containers/unittests/ya.make index 6bd8e1d0ec..2a95ccf594 100644 --- a/library/cpp/yt/small_containers/unittests/ya.make +++ b/library/cpp/yt/small_containers/unittests/ya.make @@ -4,8 +4,8 @@ OWNER(g:yt) SRCS( compact_flat_map_ut.cpp - compact_heap_ut.cpp - compact_set_ut.cpp + compact_heap_ut.cpp + compact_set_ut.cpp compact_vector_ut.cpp ) diff --git a/library/cpp/yt/string/format-inl.h b/library/cpp/yt/string/format-inl.h index 5484d4a216..2d9e3184e2 100644 --- a/library/cpp/yt/string/format-inl.h +++ b/library/cpp/yt/string/format-inl.h @@ -9,7 +9,7 @@ #include <library/cpp/yt/assert/assert.h> -#include <library/cpp/yt/small_containers/compact_vector.h> +#include <library/cpp/yt/small_containers/compact_vector.h> #include <library/cpp/yt/misc/enum.h> @@ -297,16 +297,16 @@ struct TValueFormatter<std::vector<T, TAllocator>> } }; -// TCompactVector -template <class T, unsigned N> -struct TValueFormatter<TCompactVector<T, N>> -{ - static void Do(TStringBuilderBase* builder, const TCompactVector<T, N>& collection, TStringBuf /*format*/) - { - FormatRange(builder, collection, TDefaultFormatter()); - } -}; - +// TCompactVector +template <class T, unsigned N> +struct TValueFormatter<TCompactVector<T, N>> +{ + static void Do(TStringBuilderBase* builder, const TCompactVector<T, N>& collection, TStringBuf /*format*/) + { + FormatRange(builder, collection, TDefaultFormatter()); + } +}; + // std::set template <class T> struct TValueFormatter<std::set<T>> diff --git a/library/cpp/yt/string/unittests/format_ut.cpp b/library/cpp/yt/string/unittests/format_ut.cpp index ee069bb2c0..499775857f 100644 --- a/library/cpp/yt/string/unittests/format_ut.cpp +++ b/library/cpp/yt/string/unittests/format_ut.cpp @@ -2,7 +2,7 @@ #include <library/cpp/yt/string/format.h> -#include <library/cpp/yt/small_containers/compact_vector.h> +#include <library/cpp/yt/small_containers/compact_vector.h> #include <limits> @@ -71,7 +71,7 @@ TEST(TFormatTest, Strings) EXPECT_EQ("abc", Format("%-2s", TString("abc"))); EXPECT_EQ("abc", Format("%0s", TString("abc"))); EXPECT_EQ("abc", Format("%-0s", TString("abc"))); - EXPECT_EQ(100, std::ssize(Format("%100v", "abc"))); + EXPECT_EQ(100, std::ssize(Format("%100v", "abc"))); } TEST(TFormatTest, Integers) @@ -79,9 +79,9 @@ TEST(TFormatTest, Integers) EXPECT_EQ("123", Format("%d", 123)); EXPECT_EQ("123", Format("%v", 123)); - EXPECT_EQ("042", Format("%03d", 42)); - EXPECT_EQ("42", Format("%01d", 42)); - + EXPECT_EQ("042", Format("%03d", 42)); + EXPECT_EQ("42", Format("%01d", 42)); + EXPECT_EQ("2147483647", Format("%d", std::numeric_limits<i32>::max())); EXPECT_EQ("-2147483648", Format("%d", std::numeric_limits<i32>::min())); |