diff options
author | Alexander Fokin <apfokin@gmail.com> | 2022-02-10 16:45:38 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:45:38 +0300 |
commit | 863a59a65247c24db7cb06789bc5cf79d04da32f (patch) | |
tree | 139dc000c8cd4a40f5659e421b7c75135d080307 /util/generic | |
parent | f64e95a9eb9ab03240599eb9581c5a9102426a96 (diff) | |
download | ydb-863a59a65247c24db7cb06789bc5cf79d04da32f.tar.gz |
Restoring authorship annotation for Alexander Fokin <apfokin@gmail.com>. Commit 1 of 2.
Diffstat (limited to 'util/generic')
55 files changed, 1552 insertions, 1552 deletions
diff --git a/util/generic/adaptor.h b/util/generic/adaptor.h index b88a65fc81..0c5aa16c87 100644 --- a/util/generic/adaptor.h +++ b/util/generic/adaptor.h @@ -5,136 +5,136 @@ namespace NPrivate { template <class Range> - class TReverseRangeStorage { - public: + class TReverseRangeStorage { + public: TReverseRangeStorage(Range&& range) : Base_(std::forward<Range>(range)) { } - decltype(auto) Base() const { - return *Base_.Ptr(); - } - - decltype(auto) Base() { - return *Base_.Ptr(); - } - - private: - TAutoEmbedOrPtrPolicy<Range> Base_; - }; - - template <class Range> - constexpr bool HasReverseIterators(i32, decltype(std::declval<Range>().rbegin())*) { - return true; - } - - template <class Range> - constexpr bool HasReverseIterators(char, std::nullptr_t*) { - return false; - } - - template <class Range, bool hasReverseIterators = HasReverseIterators<Range>((i32)0, nullptr)> - class TReverseRangeBase: public TReverseRangeStorage<Range> { - using TBase = TReverseRangeStorage<Range>; - - public: + decltype(auto) Base() const { + return *Base_.Ptr(); + } + + decltype(auto) Base() { + return *Base_.Ptr(); + } + + private: + TAutoEmbedOrPtrPolicy<Range> Base_; + }; + + template <class Range> + constexpr bool HasReverseIterators(i32, decltype(std::declval<Range>().rbegin())*) { + return true; + } + + template <class Range> + constexpr bool HasReverseIterators(char, std::nullptr_t*) { + return false; + } + + template <class Range, bool hasReverseIterators = HasReverseIterators<Range>((i32)0, nullptr)> + class TReverseRangeBase: public TReverseRangeStorage<Range> { + using TBase = TReverseRangeStorage<Range>; + + public: using TBase::Base; - using TBase::TBase; - + using TBase::TBase; + auto begin() const { - return Base().rbegin(); + return Base().rbegin(); } auto end() const { - return Base().rend(); + return Base().rend(); } auto begin() { - return Base().rbegin(); + return Base().rbegin(); } auto end() { - return Base().rend(); + return Base().rend(); } }; - template <class Range> - class TReverseRangeBase<Range, false>: public TReverseRangeStorage<Range> { - using TBase = TReverseRangeStorage<Range>; + template <class Range> + class TReverseRangeBase<Range, false>: public TReverseRangeStorage<Range> { + using TBase = TReverseRangeStorage<Range>; - public: + public: using TBase::Base; - using TBase::TBase; - - auto begin() const { + using TBase::TBase; + + auto begin() const { using std::end; - return std::make_reverse_iterator(end(Base())); + return std::make_reverse_iterator(end(Base())); } - auto end() const { + auto end() const { using std::begin; - return std::make_reverse_iterator(begin(Base())); + return std::make_reverse_iterator(begin(Base())); } - auto begin() { + auto begin() { using std::end; - return std::make_reverse_iterator(end(Base())); + return std::make_reverse_iterator(end(Base())); } - auto end() { + auto end() { using std::begin; - return std::make_reverse_iterator(begin(Base())); + return std::make_reverse_iterator(begin(Base())); } }; - template <class Range> + template <class Range> class TReverseRange: public TReverseRangeBase<Range> { - using TBase = TReverseRangeBase<Range>; + using TBase = TReverseRangeBase<Range>; - public: + public: using TBase::Base; - using TBase::TBase; + using TBase::TBase; - TReverseRange(TReverseRange&&) = default; - TReverseRange(const TReverseRange&) = default; + TReverseRange(TReverseRange&&) = default; + TReverseRange(const TReverseRange&) = default; auto rbegin() const { using std::begin; - return begin(Base()); + return begin(Base()); } auto rend() const { using std::end; - return end(Base()); + return end(Base()); } auto rbegin() { using std::begin; - return begin(Base()); + return begin(Base()); } auto rend() { using std::end; - return end(Base()); + return end(Base()); } }; } -/** - * Provides a reverse view into the provided container. - * - * Example usage: - * @code - * for(auto&& value: Reversed(container)) { - * // use value here. - * } - * @endcode - * - * @param cont Container to provide a view into. Must be an lvalue. - * @returns A reverse view into the provided container. - */ -template <class Range> -constexpr ::NPrivate::TReverseRange<Range> Reversed(Range&& range) { - return ::NPrivate::TReverseRange<Range>(std::forward<Range>(range)); +/** + * Provides a reverse view into the provided container. + * + * Example usage: + * @code + * for(auto&& value: Reversed(container)) { + * // use value here. + * } + * @endcode + * + * @param cont Container to provide a view into. Must be an lvalue. + * @returns A reverse view into the provided container. + */ +template <class Range> +constexpr ::NPrivate::TReverseRange<Range> Reversed(Range&& range) { + return ::NPrivate::TReverseRange<Range>(std::forward<Range>(range)); } diff --git a/util/generic/adaptor_ut.cpp b/util/generic/adaptor_ut.cpp index 721f849f93..adff58615b 100644 --- a/util/generic/adaptor_ut.cpp +++ b/util/generic/adaptor_ut.cpp @@ -65,8 +65,8 @@ Y_UNIT_TEST_SUITE(TReverseAdaptor) { const TStub cstub; using namespace NPrivate; - UNIT_ASSERT_TYPES_EQUAL(decltype(Reversed(stub)), TReverseRange<TStub&>); - UNIT_ASSERT_TYPES_EQUAL(decltype(Reversed(cstub)), TReverseRange<const TStub&>); + UNIT_ASSERT_TYPES_EQUAL(decltype(Reversed(stub)), TReverseRange<TStub&>); + UNIT_ASSERT_TYPES_EQUAL(decltype(Reversed(cstub)), TReverseRange<const TStub&>); } Y_UNIT_TEST(CopyMoveTest) { diff --git a/util/generic/algorithm.h b/util/generic/algorithm.h index badfb88993..028aa29218 100644 --- a/util/generic/algorithm.h +++ b/util/generic/algorithm.h @@ -55,7 +55,7 @@ static inline void Sort(TContainer& container, TCompare compare) { template <class TIterator, typename TGetKey> static inline void SortBy(TIterator begin, TIterator end, const TGetKey& getKey) { - Sort(begin, end, [&](auto&& left, auto&& right) { return getKey(left) < getKey(right); }); + Sort(begin, end, [&](auto&& left, auto&& right) { return getKey(left) < getKey(right); }); } template <class TContainer, typename TGetKey> @@ -64,12 +64,12 @@ static inline void SortBy(TContainer& container, const TGetKey& getKey) { } template <class T> -static inline void StableSort(T f, T l) { +static inline void StableSort(T f, T l) { std::stable_sort(f, l); } template <class T, class C> -static inline void StableSort(T f, T l, C c) { +static inline void StableSort(T f, T l, C c) { std::stable_sort(f, l, c); } @@ -85,7 +85,7 @@ static inline void StableSort(TContainer& container, TCompare compare) { template <class TIterator, typename TGetKey> static inline void StableSortBy(TIterator begin, TIterator end, const TGetKey& getKey) { - StableSort(begin, end, [&](auto&& left, auto&& right) { return getKey(left) < getKey(right); }); + StableSort(begin, end, [&](auto&& left, auto&& right) { return getKey(left) < getKey(right); }); } template <class TContainer, typename TGetKey> @@ -118,14 +118,14 @@ static inline I Find(I f, I l, const T& v) { return std::find(f, l, v); } -template <class C, class T> -static inline auto Find(C&& c, const T& v) { - using std::begin; - using std::end; - - return std::find(begin(c), end(c), v); -} - +template <class C, class T> +static inline auto Find(C&& c, const T& v) { + using std::begin; + using std::end; + + return std::find(begin(c), end(c), v); +} + // FindPtr - return NULL if not found. Works for arrays, containers, iterators template <class I, class T> static inline auto FindPtr(I f, I l, const T& v) -> decltype(&*f) { @@ -155,7 +155,7 @@ static inline auto FindIf(C&& c, P p) { template <class I, class P> static inline bool AllOf(I f, I l, P pred) { - return std::all_of(f, l, pred); + return std::all_of(f, l, pred); } template <class C, class P> @@ -167,7 +167,7 @@ static inline bool AllOf(const C& c, P pred) { template <class I, class P> static inline bool AnyOf(I f, I l, P pred) { - return std::any_of(f, l, pred); + return std::any_of(f, l, pred); } template <class C, class P> @@ -185,7 +185,7 @@ static inline auto FindIfPtr(I f, I l, P pred) -> decltype(&*f) { } template <class C, class P> -static inline auto FindIfPtr(C&& c, P pred) { +static inline auto FindIfPtr(C&& c, P pred) { using std::begin; using std::end; return FindIfPtr(begin(c), end(c), pred); @@ -529,7 +529,7 @@ auto MaxElementBy(C& c, F&& func) { } template <class C, class F> -auto MaxElementBy(const C& c, F&& func) { +auto MaxElementBy(const C& c, F&& func) { return MaxElementBy(std::begin(c), std::end(c), std::forward<F>(func)); } @@ -545,7 +545,7 @@ auto MinElementBy(C& c, F&& func) { } template <class C, class F> -auto MinElementBy(const C& c, F&& func) { +auto MinElementBy(const C& c, F&& func) { return MinElementBy(std::begin(c), std::end(c), std::forward<F>(func)); } @@ -644,12 +644,12 @@ static inline auto Count(const TContainer& container, const TValue& value) { } template <class It, class P> -static inline auto CountIf(It first, It last, P p) { +static inline auto CountIf(It first, It last, P p) { return std::count_if(first, last, p); } template <class C, class P> -static inline auto CountIf(const C& c, P pred) { +static inline auto CountIf(const C& c, P pred) { using std::begin; using std::end; return CountIf(begin(c), end(c), pred); @@ -713,16 +713,16 @@ template <class It, class Val, class Comp> static inline std::pair<It, It> EqualRange(It begin, It end, const Val& val, Comp comp) { return std::equal_range(begin, end, val, comp); } - -template <class ForwardIt> -bool IsSorted(ForwardIt begin, ForwardIt end) { + +template <class ForwardIt> +bool IsSorted(ForwardIt begin, ForwardIt end) { return std::is_sorted(begin, end); -} - -template <class ForwardIt, class Compare> -bool IsSorted(ForwardIt begin, ForwardIt end, Compare comp) { +} + +template <class ForwardIt, class Compare> +bool IsSorted(ForwardIt begin, ForwardIt end, Compare comp) { return std::is_sorted(begin, end, comp); -} +} template <class TIterator, typename TGetKey> bool IsSortedBy(TIterator begin, TIterator end, const TGetKey& getKey) { diff --git a/util/generic/algorithm_ut.cpp b/util/generic/algorithm_ut.cpp index 8d732fcc0c..b281753f1a 100644 --- a/util/generic/algorithm_ut.cpp +++ b/util/generic/algorithm_ut.cpp @@ -415,21 +415,21 @@ Y_UNIT_TEST_SUITE(TAlgorithm) { UNIT_ASSERT_EQUAL(tmpR.second - tmpR.first, 2); } } - + Y_UNIT_TEST(IsSortedTest) { TVector<int> v0; - UNIT_ASSERT_VALUES_EQUAL(IsSorted(v0.begin(), v0.end()), true); - + UNIT_ASSERT_VALUES_EQUAL(IsSorted(v0.begin(), v0.end()), true); + TVector<int> v1 = {1, 2, 3, 4, 5, 5, 5, 6, 6, 7, 8}; - UNIT_ASSERT_VALUES_EQUAL(IsSorted(v1.begin(), v1.end()), true); - UNIT_ASSERT_VALUES_EQUAL(IsSorted(v1.begin(), v1.end(), TLess<int>()), true); - UNIT_ASSERT_VALUES_EQUAL(IsSorted(v1.begin(), v1.end(), TGreater<int>()), false); - + UNIT_ASSERT_VALUES_EQUAL(IsSorted(v1.begin(), v1.end()), true); + UNIT_ASSERT_VALUES_EQUAL(IsSorted(v1.begin(), v1.end(), TLess<int>()), true); + UNIT_ASSERT_VALUES_EQUAL(IsSorted(v1.begin(), v1.end(), TGreater<int>()), false); + TVector<int> v2 = {1, 2, 1}; - UNIT_ASSERT_VALUES_EQUAL(IsSorted(v2.begin(), v2.end()), false); - UNIT_ASSERT_VALUES_EQUAL(IsSorted(v2.begin(), v2.end(), TLess<int>()), false); - UNIT_ASSERT_VALUES_EQUAL(IsSorted(v2.begin(), v2.end(), TGreater<int>()), false); - } + UNIT_ASSERT_VALUES_EQUAL(IsSorted(v2.begin(), v2.end()), false); + UNIT_ASSERT_VALUES_EQUAL(IsSorted(v2.begin(), v2.end(), TLess<int>()), false); + UNIT_ASSERT_VALUES_EQUAL(IsSorted(v2.begin(), v2.end(), TGreater<int>()), false); + } Y_UNIT_TEST(IsSortedByTest) { TVector<int> v0; @@ -835,13 +835,13 @@ Y_UNIT_TEST_SUITE(TAlgorithm) { UNIT_ASSERT((it + 1) == data.end()); } - + Y_UNIT_TEST(TestFindInContainer) { - std::vector<int> v = {1, 2, 1000, 15, 100}; - UNIT_ASSERT(Find(v, 5) == v.end()); - UNIT_ASSERT(Find(v, 1) == v.begin()); - UNIT_ASSERT(Find(v, 100) == v.end() - 1); - } + std::vector<int> v = {1, 2, 1000, 15, 100}; + UNIT_ASSERT(Find(v, 5) == v.end()); + UNIT_ASSERT(Find(v, 1) == v.begin()); + UNIT_ASSERT(Find(v, 100) == v.end() - 1); + } Y_UNIT_TEST(AccumulateWithBinOp) { std::vector<int> v = {1, 2, 777}; diff --git a/util/generic/array_ref.h b/util/generic/array_ref.h index 1ac60ac7d3..a67cf93bf3 100644 --- a/util/generic/array_ref.h +++ b/util/generic/array_ref.h @@ -3,30 +3,30 @@ #include <util/generic/yexception.h> #include <algorithm> -#include <initializer_list> +#include <initializer_list> #include <iterator> -/** - * `TArrayRef` works pretty much like `std::span` with dynamic extent, presenting - * an array-like interface into a contiguous sequence of objects. - * - * It can be used at interface boundaries instead of `TVector` or - * pointer-size pairs, and is actually a preferred way to pass contiguous data - * into functions. - * - * Note that `TArrayRef` can be auto-constructed from any contiguous container - * (with `size` and `data` members), and thus you don't have to change client code +/** + * `TArrayRef` works pretty much like `std::span` with dynamic extent, presenting + * an array-like interface into a contiguous sequence of objects. + * + * It can be used at interface boundaries instead of `TVector` or + * pointer-size pairs, and is actually a preferred way to pass contiguous data + * into functions. + * + * Note that `TArrayRef` can be auto-constructed from any contiguous container + * (with `size` and `data` members), and thus you don't have to change client code * when switching over from passing `TVector` to `TArrayRef`. - * - * Note that `TArrayRef` has the same const-semantics as raw pointers: - * - `TArrayRef<T>` is a non-const reference to non-const data (like `T*`); - * - `TArrayRef<const T>` is a non-const reference to const data (like `const T*`); - * - `const TArrayRef<T>` is a const reference to non-const data (like `T* const`); - * - `const TArrayRef<const T>` is a const reference to const data (like `const T* const`). - */ -template <class T> + * + * Note that `TArrayRef` has the same const-semantics as raw pointers: + * - `TArrayRef<T>` is a non-const reference to non-const data (like `T*`); + * - `TArrayRef<const T>` is a non-const reference to const data (like `const T*`); + * - `const TArrayRef<T>` is a const reference to non-const data (like `T* const`); + * - `const TArrayRef<const T>` is a const reference to const data (like `const T* const`). + */ +template <class T> class TArrayRef { -public: +public: using iterator = T*; using const_iterator = const T*; using reference = T&; @@ -36,55 +36,55 @@ public: using const_reverse_iterator = std::reverse_iterator<const_iterator>; constexpr inline TArrayRef() noexcept - : T_(nullptr) - , S_(0) - { - } + : T_(nullptr) + , S_(0) + { + } constexpr inline TArrayRef(T* data, size_t len) noexcept - : T_(data) - , S_(len) - { - } + : T_(data) + , S_(len) + { + } constexpr inline TArrayRef(T* begin, T* end) noexcept - : T_(begin) - , S_(end - begin) - { - } + : T_(begin) + , S_(end - begin) + { + } constexpr inline TArrayRef(std::initializer_list<T> list) noexcept - : T_(list.begin()) - , S_(list.size()) - { - } - - template <class Container> + : T_(list.begin()) + , S_(list.size()) + { + } + + template <class Container> constexpr inline TArrayRef(Container&& container, decltype(std::declval<T*&>() = container.data(), nullptr) = nullptr) noexcept - : T_(container.data()) - , S_(container.size()) - { - } + : T_(container.data()) + , S_(container.size()) + { + } - template <size_t N> + template <size_t N> constexpr inline TArrayRef(T (&array)[N]) noexcept - : T_(array) - , S_(N) - { - } + : T_(array) + , S_(N) + { + } template <class TT, typename = std::enable_if_t<std::is_same<std::remove_const_t<T>, std::remove_const_t<TT>>::value>> - bool operator==(const TArrayRef<TT>& other) const noexcept { + bool operator==(const TArrayRef<TT>& other) const noexcept { return (S_ == other.size()) && std::equal(begin(), end(), other.begin()); - } + } constexpr inline T* data() const noexcept { - return T_; - } + return T_; + } constexpr inline size_t size() const noexcept { - return S_; - } + return S_; + } constexpr size_t size_bytes() const noexcept { return (size() * sizeof(T)); @@ -153,7 +153,7 @@ public: constexpr inline explicit operator bool() const noexcept { return (S_ > 0); } - + /** * Obtains a ref that is a view over the first `count` elements of this TArrayRef. * @@ -220,11 +220,11 @@ public: return static_cast<yssize_t>(this->size()); } -private: - T* T_; - size_t S_; -}; - +private: + T* T_; + size_t S_; +}; + /** * Obtains a view to the object representation of the elements of the TArrayRef arrayRef. * @@ -251,14 +251,14 @@ TArrayRef<char> as_writable_bytes(TArrayRef<T> arrayRef) noexcept { template <class Range> constexpr TArrayRef<const typename Range::value_type> MakeArrayRef(const Range& range) { - return TArrayRef<const typename Range::value_type>(range); + return TArrayRef<const typename Range::value_type>(range); } template <class Range> constexpr TArrayRef<typename Range::value_type> MakeArrayRef(Range& range) { - return TArrayRef<typename Range::value_type>(range); + return TArrayRef<typename Range::value_type>(range); } - + template <class Range> constexpr TArrayRef<const typename Range::value_type> MakeConstArrayRef(const Range& range) { return TArrayRef<const typename Range::value_type>(range); @@ -269,10 +269,10 @@ constexpr TArrayRef<const typename Range::value_type> MakeConstArrayRef(Range& r return TArrayRef<const typename Range::value_type>(range); } -template <class T> +template <class T> constexpr TArrayRef<T> MakeArrayRef(T* data, size_t size) { - return TArrayRef<T>(data, size); -} + return TArrayRef<T>(data, size); +} template <class T> constexpr TArrayRef<T> MakeArrayRef(T* begin, T* end) { diff --git a/util/generic/array_ref_ut.cpp b/util/generic/array_ref_ut.cpp index 4c8eaf7135..c926b55704 100644 --- a/util/generic/array_ref_ut.cpp +++ b/util/generic/array_ref_ut.cpp @@ -168,23 +168,23 @@ Y_UNIT_TEST_SUITE(TestArrayRef) { //Testing if operator== compares values, not pointers UNIT_ASSERT_EQUAL(cRef, bSubRef); } - + Y_UNIT_TEST(TestImplicitConstructionFromContainer) { - /* Just test compilation. */ - auto fc = [](TArrayRef<const int>) {}; - auto fm = [](TArrayRef<int>) {}; - + /* Just test compilation. */ + auto fc = [](TArrayRef<const int>) {}; + auto fm = [](TArrayRef<int>) {}; + fc(TVector<int>({1})); - + const TVector<int> ac = {1}; TVector<int> am = {1}; - - fc(ac); - fc(am); - fm(am); - // fm(ac); // This one shouldn't compile. - } - + + fc(ac); + fc(am); + fm(am); + // fm(ac); // This one shouldn't compile. + } + Y_UNIT_TEST(TestFirstLastSubspan) { const int arr[] = {1, 2, 3, 4, 5}; TArrayRef<const int> aRef(arr); @@ -198,20 +198,20 @@ Y_UNIT_TEST_SUITE(TestArrayRef) { Y_UNIT_TEST(TestSlice) { const int a0[] = {1, 2, 3}; TArrayRef<const int> r0(a0); - TArrayRef<const int> s0 = r0.Slice(2); - - UNIT_ASSERT_VALUES_EQUAL(s0.size(), 1); - UNIT_ASSERT_VALUES_EQUAL(s0[0], 3); - + TArrayRef<const int> s0 = r0.Slice(2); + + UNIT_ASSERT_VALUES_EQUAL(s0.size(), 1); + UNIT_ASSERT_VALUES_EQUAL(s0[0], 3); + const int a1[] = {1, 2, 3, 4}; TArrayRef<const int> r1(a1); - TArrayRef<const int> s1 = r1.Slice(2, 1); - - UNIT_ASSERT_VALUES_EQUAL(s1.size(), 1); - UNIT_ASSERT_VALUES_EQUAL(s1[0], 3); + TArrayRef<const int> s1 = r1.Slice(2, 1); + + UNIT_ASSERT_VALUES_EQUAL(s1.size(), 1); + UNIT_ASSERT_VALUES_EQUAL(s1[0], 3); //FIXME: size checks are implemented via Y_ASSERT, hence there is no way to test them - } + } Y_UNIT_TEST(SubRegion) { TVector<char> x; diff --git a/util/generic/bitmap.h b/util/generic/bitmap.h index f77d182460..8d7e427009 100644 --- a/util/generic/bitmap.h +++ b/util/generic/bitmap.h @@ -1,6 +1,6 @@ #pragma once -#include "fwd.h" +#include "fwd.h" #include "ptr.h" #include "bitops.h" #include "typetraits.h" @@ -1077,7 +1077,7 @@ inline TBitMapOps<X> operator~(const TBitMapOps<X>& x) { /////////////////// Specialization /////////////////////////// -template <size_t BitCount, typename TChunkType /*= ui64*/> +template <size_t BitCount, typename TChunkType /*= ui64*/> class TBitMap: public TBitMapOps<TFixedBitMapTraits<BitCount, TChunkType>> { private: using TBase = TBitMapOps<TFixedBitMapTraits<BitCount, TChunkType>>; diff --git a/util/generic/bitops.h b/util/generic/bitops.h index 2db15fc59b..704540da9d 100644 --- a/util/generic/bitops.h +++ b/util/generic/bitops.h @@ -269,7 +269,7 @@ Y_FORCE_INLINE ui64 InverseMaskLowerBits(ui64 bits, ui64 skipbits) { } /* - * Returns 0-based position of the most significant bit that is set. 0 for 0. + * Returns 0-based position of the most significant bit that is set. 0 for 0. */ Y_FORCE_INLINE ui64 MostSignificantBit(ui64 v) { #ifdef __GNUC__ @@ -287,28 +287,28 @@ Y_FORCE_INLINE ui64 MostSignificantBit(ui64 v) { return res; } -/** - * Returns 0-based position of the least significant bit that is set. 0 for 0. - */ -Y_FORCE_INLINE ui64 LeastSignificantBit(ui64 v) { -#ifdef __GNUC__ - ui64 res = v ? __builtin_ffsll(v) - 1 : 0; -#elif defined(_MSC_VER) && defined(_64_) - unsigned long res = 0; - if (v) - _BitScanForward64(&res, v); -#else - ui64 res = 0; - if (v) { - while (!(v & 1)) { +/** + * Returns 0-based position of the least significant bit that is set. 0 for 0. + */ +Y_FORCE_INLINE ui64 LeastSignificantBit(ui64 v) { +#ifdef __GNUC__ + ui64 res = v ? __builtin_ffsll(v) - 1 : 0; +#elif defined(_MSC_VER) && defined(_64_) + unsigned long res = 0; + if (v) + _BitScanForward64(&res, v); +#else + ui64 res = 0; + if (v) { + while (!(v & 1)) { ++res; - v >>= 1; - } - } -#endif - return res; -} - + v >>= 1; + } + } +#endif + return res; +} + /* * Returns 0 - based position of the most significant bit (compile time) * 0 for 0. diff --git a/util/generic/bitops_ut.cpp b/util/generic/bitops_ut.cpp index d23c2b5c27..3d1f7e9575 100644 --- a/util/generic/bitops_ut.cpp +++ b/util/generic/bitops_ut.cpp @@ -65,7 +65,7 @@ Y_UNIT_TEST_SUITE(TBitOpsTest) { UNIT_ASSERT(IsPowerOf2(0x1000000000000000ull)); UNIT_ASSERT(!IsPowerOf2(0x1000000000000001ull)); } - + Y_UNIT_TEST(TestFastClp2) { TestFastClp2ForEachPowerOf2<unsigned>(); TestFastClp2ForEachPowerOf2<unsigned long>(); @@ -89,7 +89,7 @@ Y_UNIT_TEST_SUITE(TBitOpsTest) { for (ui32 i = 0; i < 64; ++i) { UNIT_ASSERT_VALUES_EQUAL(i, MostSignificantBit(ui64{1} << i)); } - + for (ui32 i = 0; i < 63; ++i) { UNIT_ASSERT_VALUES_EQUAL(i + 1, MostSignificantBit(ui64{3} << i)); } @@ -99,17 +99,17 @@ Y_UNIT_TEST_SUITE(TBitOpsTest) { for (ui32 i = 0; i < 64; ++i) { UNIT_ASSERT_VALUES_EQUAL(i, LeastSignificantBit(ui64{1} << i)); } - + for (ui32 i = 0; i < 63; ++i) { UNIT_ASSERT_VALUES_EQUAL(i, LeastSignificantBit(ui64{3} << i)); } - + for (ui32 i = 0; i < 64; ++i) { ui64 value = (ui64(-1)) << i; UNIT_ASSERT_VALUES_EQUAL(i, LeastSignificantBit(value)); } - } - + } + Y_UNIT_TEST(TestCeilLog2) { UNIT_ASSERT_VALUES_EQUAL(CeilLog2(ui64{1}), 1); diff --git a/util/generic/cast_ut.cpp b/util/generic/cast_ut.cpp index 718a8de79d..677afacdf9 100644 --- a/util/generic/cast_ut.cpp +++ b/util/generic/cast_ut.cpp @@ -85,7 +85,7 @@ private: void TestBitCast() { // Change sign of float { - const float floatValue = 17.33f; + const float floatValue = 17.33f; ui32 ui32Value = BitCast<ui32>(floatValue); ui32Value ^= (ui32)1 << 31; UNIT_ASSERT_VALUES_EQUAL(-floatValue, BitCast<float>(ui32Value)); diff --git a/util/generic/deque.h b/util/generic/deque.h index 2dabaf3177..501256d55c 100644 --- a/util/generic/deque.h +++ b/util/generic/deque.h @@ -1,11 +1,11 @@ #pragma once #include "fwd.h" - + #include <util/memory/alloc.h> #include <deque> -#include <memory> +#include <memory> #include <initializer_list> template <class T, class A> diff --git a/util/generic/explicit_type.cpp b/util/generic/explicit_type.cpp index 65bc80093a..207a62a474 100644 --- a/util/generic/explicit_type.cpp +++ b/util/generic/explicit_type.cpp @@ -1 +1 @@ -#include "explicit_type.h" +#include "explicit_type.h" diff --git a/util/generic/explicit_type.h b/util/generic/explicit_type.h index 34e269f155..636b5499cb 100644 --- a/util/generic/explicit_type.h +++ b/util/generic/explicit_type.h @@ -1,42 +1,42 @@ -#pragma once - -#include "typetraits.h" - -/** - * Helper type that can be used as one of the parameters in function declaration - * to limit the number of types this function can be called with. - * - * Example usage: - * @code - * void CharOnlyFunction(TExplicitType<char> value); - * void AnythingFunction(char value); - * - * CharOnlyFunction('c'); // Works. - * CharOnlyFunction(1); // Compilation error. - * CharOnlyFunction(1ull); // Compilation error. - * - * AnythingFunction('c'); // Works. - * AnythingFunction(1); // Works. - * AnythingFunction(1ull); // Works. - * @endcode - */ +#pragma once + +#include "typetraits.h" + +/** + * Helper type that can be used as one of the parameters in function declaration + * to limit the number of types this function can be called with. + * + * Example usage: + * @code + * void CharOnlyFunction(TExplicitType<char> value); + * void AnythingFunction(char value); + * + * CharOnlyFunction('c'); // Works. + * CharOnlyFunction(1); // Compilation error. + * CharOnlyFunction(1ull); // Compilation error. + * + * AnythingFunction('c'); // Works. + * AnythingFunction(1); // Works. + * AnythingFunction(1ull); // Works. + * @endcode + */ template <class T> -class TExplicitType { -public: +class TExplicitType { +public: template <class OtherT> TExplicitType(const OtherT& value, std::enable_if_t<std::is_same<OtherT, T>::value>* = nullptr) noexcept - : Value_(value) - { - } - - const T& Value() const noexcept { - return Value_; - } - - operator const T&() const noexcept { - return Value_; - } - -private: - const T& Value_; -}; + : Value_(value) + { + } + + const T& Value() const noexcept { + return Value_; + } + + operator const T&() const noexcept { + return Value_; + } + +private: + const T& Value_; +}; diff --git a/util/generic/explicit_type_ut.cpp b/util/generic/explicit_type_ut.cpp index 50a745f090..ef40fbbce6 100644 --- a/util/generic/explicit_type_ut.cpp +++ b/util/generic/explicit_type_ut.cpp @@ -1,43 +1,43 @@ -#include "explicit_type.h" - +#include "explicit_type.h" + #include <library/cpp/testing/unittest/registar.h> - -struct TCallableBase { -public: - using TYes = char; - using TNo = struct { TYes dummy[32]; }; - + +struct TCallableBase { +public: + using TYes = char; + using TNo = struct { TYes dummy[32]; }; + template <class T, class Arg> - static TNo Test(const T&, const Arg&, ...); - + static TNo Test(const T&, const Arg&, ...); + template <class T, class Arg> static TYes Test(const T&, const Arg&, int, decltype(std::declval<T>()(std::declval<Arg>()))* = nullptr); -}; - +}; + template <class T, class Arg> -struct TCallable: public TCallableBase { - enum { +struct TCallable: public TCallableBase { + enum { Result = sizeof(Test(std::declval<T>(), std::declval<Arg>(), 1)) == sizeof(TYes) - }; -}; - + }; +}; + template <class T> -struct TExplicitlyCallable { +struct TExplicitlyCallable { void operator()(TExplicitType<T>) { } -}; - -struct IntConvertible { +}; + +struct IntConvertible { operator int() { return 1; } -}; - -struct IntConstructible { +}; + +struct IntConstructible { IntConstructible(const int&) { } -}; - +}; + Y_UNIT_TEST_SUITE(TestExplicitType) { Y_UNIT_TEST(Test1) { UNIT_ASSERT_VALUES_EQUAL(static_cast<bool>(TCallable<TExplicitlyCallable<char>, char>::Result), true); @@ -48,5 +48,5 @@ Y_UNIT_TEST_SUITE(TestExplicitType) { UNIT_ASSERT_VALUES_EQUAL(static_cast<bool>(TCallable<TExplicitlyCallable<IntConstructible>, IntConstructible>::Result), true); UNIT_ASSERT_VALUES_EQUAL(static_cast<bool>(TCallable<TExplicitlyCallable<IntConstructible>, IntConvertible>::Result), false); UNIT_ASSERT_VALUES_EQUAL(static_cast<bool>(TCallable<TExplicitlyCallable<IntConstructible>, int>::Result), false); - } -} + } +} diff --git a/util/generic/flags.cpp b/util/generic/flags.cpp index 2ee52188a0..3fd1f2b272 100644 --- a/util/generic/flags.cpp +++ b/util/generic/flags.cpp @@ -1,14 +1,14 @@ -#include "flags.h" - -#include <util/stream/format.h> -#include <util/system/yassert.h> - +#include "flags.h" + +#include <util/stream/format.h> +#include <util/system/yassert.h> + void ::NPrivate::PrintFlags(IOutputStream& stream, ui64 value, size_t size) { - /* Note that this function is in cpp because we need to break circular - * dependency between TFlags and ENumberFormat. */ - stream << "TFlags("; - - switch (size) { + /* Note that this function is in cpp because we need to break circular + * dependency between TFlags and ENumberFormat. */ + stream << "TFlags("; + + switch (size) { case 1: stream << Bin(static_cast<ui8>(value), HF_FULL); break; @@ -23,7 +23,7 @@ void ::NPrivate::PrintFlags(IOutputStream& stream, ui64 value, size_t size) { break; default: Y_VERIFY(false); - } - - stream << ")"; -} + } + + stream << ")"; +} diff --git a/util/generic/flags.h b/util/generic/flags.h index a1f5921d42..1d9bda5855 100644 --- a/util/generic/flags.h +++ b/util/generic/flags.h @@ -1,173 +1,173 @@ -#pragma once - -#include <type_traits> - -#include <util/system/types.h> +#pragma once + +#include <type_traits> + +#include <util/system/types.h> #include <util/generic/typetraits.h> -#include <util/generic/fwd.h> - +#include <util/generic/fwd.h> + class IOutputStream; -namespace NPrivate { +namespace NPrivate { void PrintFlags(IOutputStream& stream, ui64 value, size_t size); -} - -/** - * `TFlags` wrapper provides a type-safe mechanism for storing OR combinations - * of enumeration values. - * - * This class is intended to be used mainly via helper macros. For example: - * @code - * class TAligner { - * public: - * enum EOrientation { - * Vertical = 1, - * Horizontal = 2 - * }; - * Y_DECLARE_FLAGS(EOrientations, EOrientation) - * - * // ... - * }; - * - * Y_DECLARE_OPERATORS_FOR_FLAGS(TAligner::EOrientations) - * @endcode - */ -template <class Enum> -class TFlags { - static_assert(std::is_enum<Enum>::value, "Expecting an enumeration here."); - -public: - using TEnum = Enum; +} + +/** + * `TFlags` wrapper provides a type-safe mechanism for storing OR combinations + * of enumeration values. + * + * This class is intended to be used mainly via helper macros. For example: + * @code + * class TAligner { + * public: + * enum EOrientation { + * Vertical = 1, + * Horizontal = 2 + * }; + * Y_DECLARE_FLAGS(EOrientations, EOrientation) + * + * // ... + * }; + * + * Y_DECLARE_OPERATORS_FOR_FLAGS(TAligner::EOrientations) + * @endcode + */ +template <class Enum> +class TFlags { + static_assert(std::is_enum<Enum>::value, "Expecting an enumeration here."); + +public: + using TEnum = Enum; using TInt = std::underlying_type_t<Enum>; - + constexpr TFlags(std::nullptr_t = 0) - : Value_(0) - { - } - - constexpr TFlags(Enum value) - : Value_(static_cast<TInt>(value)) - { - } - - /* Generated copy/move ctor/assignment are OK. */ - - constexpr operator TInt() const { - return Value_; - } - + : Value_(0) + { + } + + constexpr TFlags(Enum value) + : Value_(static_cast<TInt>(value)) + { + } + + /* Generated copy/move ctor/assignment are OK. */ + + constexpr operator TInt() const { + return Value_; + } + constexpr TInt ToBaseType() const { return Value_; } constexpr static TFlags FromBaseType(TInt value) { - return TFlags(TFlag(value)); - } - - constexpr friend TFlags operator|(TFlags l, TFlags r) { - return TFlags(TFlag(l.Value_ | r.Value_)); - } - - constexpr friend TFlags operator|(TEnum l, TFlags r) { - return TFlags(TFlag(static_cast<TInt>(l) | r.Value_)); - } - - constexpr friend TFlags operator|(TFlags l, TEnum r) { - return TFlags(TFlag(l.Value_ | static_cast<TInt>(r))); - } - - constexpr friend TFlags operator^(TFlags l, TFlags r) { - return TFlags(TFlag(l.Value_ ^ r.Value_)); - } - + return TFlags(TFlag(value)); + } + + constexpr friend TFlags operator|(TFlags l, TFlags r) { + return TFlags(TFlag(l.Value_ | r.Value_)); + } + + constexpr friend TFlags operator|(TEnum l, TFlags r) { + return TFlags(TFlag(static_cast<TInt>(l) | r.Value_)); + } + + constexpr friend TFlags operator|(TFlags l, TEnum r) { + return TFlags(TFlag(l.Value_ | static_cast<TInt>(r))); + } + + constexpr friend TFlags operator^(TFlags l, TFlags r) { + return TFlags(TFlag(l.Value_ ^ r.Value_)); + } + constexpr friend TFlags operator^(TEnum l, TFlags r) { - return TFlags(TFlag(static_cast<TInt>(l) ^ r.Value_)); - } - + return TFlags(TFlag(static_cast<TInt>(l) ^ r.Value_)); + } + constexpr friend TFlags operator^(TFlags l, TEnum r) { - return TFlags(TFlag(l.Value_ ^ static_cast<TInt>(r))); - } - + return TFlags(TFlag(l.Value_ ^ static_cast<TInt>(r))); + } + constexpr friend TFlags operator&(TFlags l, TFlags r) { - return TFlags(TFlag(l.Value_ & r.Value_)); - } - - constexpr friend TFlags operator&(TEnum l, TFlags r) { - return TFlags(TFlag(static_cast<TInt>(l) & r.Value_)); - } - - constexpr friend TFlags operator&(TFlags l, TEnum r) { - return TFlags(TFlag(l.Value_ & static_cast<TInt>(r))); - } - - constexpr friend bool operator==(TFlags l, TFlags r) { - return l.Value_ == r.Value_; - } - - constexpr friend bool operator==(TEnum l, TFlags r) { + return TFlags(TFlag(l.Value_ & r.Value_)); + } + + constexpr friend TFlags operator&(TEnum l, TFlags r) { + return TFlags(TFlag(static_cast<TInt>(l) & r.Value_)); + } + + constexpr friend TFlags operator&(TFlags l, TEnum r) { + return TFlags(TFlag(l.Value_ & static_cast<TInt>(r))); + } + + constexpr friend bool operator==(TFlags l, TFlags r) { + return l.Value_ == r.Value_; + } + + constexpr friend bool operator==(TEnum l, TFlags r) { return static_cast<TInt>(l) == r.Value_; - } - - constexpr friend bool operator==(TFlags l, TEnum r) { + } + + constexpr friend bool operator==(TFlags l, TEnum r) { return l.Value_ == static_cast<TInt>(r); - } - - constexpr friend bool operator!=(TFlags l, TFlags r) { - return l.Value_ != r.Value_; - } - - constexpr friend bool operator!=(TEnum l, TFlags r) { + } + + constexpr friend bool operator!=(TFlags l, TFlags r) { + return l.Value_ != r.Value_; + } + + constexpr friend bool operator!=(TEnum l, TFlags r) { return static_cast<TInt>(l) != r.Value_; - } - - constexpr friend bool operator!=(TFlags l, TEnum r) { + } + + constexpr friend bool operator!=(TFlags l, TEnum r) { return l.Value_ != static_cast<TInt>(r); - } - - TFlags& operator&=(TFlags mask) { + } + + TFlags& operator&=(TFlags mask) { *this = *this & mask; - return *this; - } - - TFlags& operator&=(Enum mask) { + return *this; + } + + TFlags& operator&=(Enum mask) { *this = *this & mask; - return *this; - } - - TFlags& operator|=(TFlags flags) { - *this = *this | flags; - return *this; - } - - TFlags& operator|=(Enum flags) { - *this = *this | flags; - return *this; - } - - TFlags& operator^=(TFlags flags) { - *this = *this ^ flags; - return *this; - } - - TFlags& operator^=(Enum flags) { - *this = *this ^ flags; - return *this; - } - - constexpr TFlags operator~() const { - return TFlags(TFlag(~Value_)); - } - - constexpr bool operator!() const { - return !Value_; - } - - constexpr explicit operator bool() const { - return Value_; - } - + return *this; + } + + TFlags& operator|=(TFlags flags) { + *this = *this | flags; + return *this; + } + + TFlags& operator|=(Enum flags) { + *this = *this | flags; + return *this; + } + + TFlags& operator^=(TFlags flags) { + *this = *this ^ flags; + return *this; + } + + TFlags& operator^=(Enum flags) { + *this = *this ^ flags; + return *this; + } + + constexpr TFlags operator~() const { + return TFlags(TFlag(~Value_)); + } + + constexpr bool operator!() const { + return !Value_; + } + + constexpr explicit operator bool() const { + return Value_; + } + constexpr bool HasFlags(TFlags flags) const { return (Value_ & flags.Value_) == flags.Value_; } @@ -178,31 +178,31 @@ public: } friend IOutputStream& operator<<(IOutputStream& stream, const TFlags& flags) { - ::NPrivate::PrintFlags(stream, static_cast<ui64>(flags.Value_), sizeof(TInt)); - return stream; - } - -private: - struct TFlag { + ::NPrivate::PrintFlags(stream, static_cast<ui64>(flags.Value_), sizeof(TInt)); + return stream; + } + +private: + struct TFlag { constexpr TFlag() { } constexpr explicit TFlag(TInt value) : Value(value) { } - - TInt Value = 0; - }; - - constexpr explicit TFlags(TFlag value) - : Value_(value.Value) - { - } - -private: - TInt Value_; -}; - + + TInt Value = 0; + }; + + constexpr explicit TFlags(TFlag value) + : Value_(value.Value) + { + } + +private: + TInt Value_; +}; + template <class T> struct TPodTraits<TFlags<T>> { enum { @@ -210,35 +210,35 @@ struct TPodTraits<TFlags<T>> { }; }; -template <class Enum> -struct THash<TFlags<Enum>> { - size_t operator()(const TFlags<Enum>& flags) const noexcept { - return THash<typename TFlags<Enum>::TInt>()(flags); - } -}; - -/** - * This macro defines a flags type for the provided enum. - * - * @param FLAGS Name of the flags type to declare. - * @param ENUM Name of the base enum type to use. - */ -#define Y_DECLARE_FLAGS(FLAGS, ENUM) \ - using FLAGS = TFlags<ENUM>; - -/** - * This macro declares global operator functions for enum base of `FLAGS` type. - * This way operations on individual enum values will provide a type-safe - * `TFlags` object. - * - * @param FLAGS Flags type to declare operator for. - */ -#define Y_DECLARE_OPERATORS_FOR_FLAGS(FLAGS) \ +template <class Enum> +struct THash<TFlags<Enum>> { + size_t operator()(const TFlags<Enum>& flags) const noexcept { + return THash<typename TFlags<Enum>::TInt>()(flags); + } +}; + +/** + * This macro defines a flags type for the provided enum. + * + * @param FLAGS Name of the flags type to declare. + * @param ENUM Name of the base enum type to use. + */ +#define Y_DECLARE_FLAGS(FLAGS, ENUM) \ + using FLAGS = TFlags<ENUM>; + +/** + * This macro declares global operator functions for enum base of `FLAGS` type. + * This way operations on individual enum values will provide a type-safe + * `TFlags` object. + * + * @param FLAGS Flags type to declare operator for. + */ +#define Y_DECLARE_OPERATORS_FOR_FLAGS(FLAGS) \ Y_DECLARE_UNUSED \ - constexpr inline FLAGS operator|(FLAGS::TEnum l, FLAGS::TEnum r) { \ - return FLAGS(l) | r; \ - } \ + constexpr inline FLAGS operator|(FLAGS::TEnum l, FLAGS::TEnum r) { \ + return FLAGS(l) | r; \ + } \ Y_DECLARE_UNUSED \ - constexpr inline FLAGS operator~(FLAGS::TEnum value) { \ - return ~FLAGS(value); \ - } + constexpr inline FLAGS operator~(FLAGS::TEnum value) { \ + return ~FLAGS(value); \ + } diff --git a/util/generic/flags_ut.cpp b/util/generic/flags_ut.cpp index 5377c6a058..109ead7090 100644 --- a/util/generic/flags_ut.cpp +++ b/util/generic/flags_ut.cpp @@ -1,27 +1,27 @@ #include <library/cpp/testing/unittest/registar.h> - -#include "flags.h" - + +#include "flags.h" + enum ETestFlag1: ui16 { - Test1 = 1, - Test2 = 2, - Test4 = 4, - Test8 = 8 -}; -Y_DECLARE_FLAGS(ETest1, ETestFlag1) -Y_DECLARE_OPERATORS_FOR_FLAGS(ETest1) - + Test1 = 1, + Test2 = 2, + Test4 = 4, + Test8 = 8 +}; +Y_DECLARE_FLAGS(ETest1, ETestFlag1) +Y_DECLARE_OPERATORS_FOR_FLAGS(ETest1) + static_assert(TTypeTraits<ETest1>::IsPod, "flags should be POD type"); -enum class ETestFlag2 { - Test1 = 1, - Test2 = 2, - Test4 = 4, - Test8 = 8 -}; -Y_DECLARE_FLAGS(ETest2, ETestFlag2) -Y_DECLARE_OPERATORS_FOR_FLAGS(ETest2) - +enum class ETestFlag2 { + Test1 = 1, + Test2 = 2, + Test4 = 4, + Test8 = 8 +}; +Y_DECLARE_FLAGS(ETest2, ETestFlag2) +Y_DECLARE_OPERATORS_FOR_FLAGS(ETest2) + namespace { // won't compile without Y_DECLARE_UNUSED enum class ETestFlag3 { One = 1, @@ -32,16 +32,16 @@ namespace { } Y_UNIT_TEST_SUITE(TFlagsTest) { - template <class Enum> - void TestEnum() { + template <class Enum> + void TestEnum() { { auto i = Enum::Test1 | Enum::Test2; - + UNIT_ASSERT((std::is_same<decltype(i), TFlags<Enum>>::value)); UNIT_ASSERT((std::is_same<decltype(~i), TFlags<Enum>>::value)); UNIT_ASSERT(!(std::is_same<decltype(i), int>::value)); UNIT_ASSERT_VALUES_EQUAL(sizeof(Enum), sizeof(TFlags<Enum>)); - + UNIT_ASSERT(i.HasFlags(Enum::Test1)); UNIT_ASSERT(i.HasFlags(Enum::Test4) == false); UNIT_ASSERT(i.HasFlags(Enum::Test1 | Enum::Test4) == false); @@ -64,42 +64,42 @@ Y_UNIT_TEST_SUITE(TFlagsTest) { i.RemoveFlags(Enum::Test1 | Enum::Test2); UNIT_ASSERT_EQUAL(i, TFlags<Enum>()); } - } - + } + Y_UNIT_TEST(TestFlags) { - TestEnum<ETestFlag1>(); - TestEnum<ETestFlag2>(); - } - + TestEnum<ETestFlag1>(); + TestEnum<ETestFlag2>(); + } + Y_UNIT_TEST(TestZero) { - /* This code should simply compile. */ - - ETest1 f = 0; - f = 0; - f = ETest1(0); - - ETest1 ff(0); + /* This code should simply compile. */ + + ETest1 f = 0; + f = 0; + f = ETest1(0); + + ETest1 ff(0); ff = 0; - } - + } + Y_UNIT_TEST(TestOutput) { ETest1 value0 = nullptr, value1 = Test1, value7 = Test1 | Test2 | Test4; - - UNIT_ASSERT_VALUES_EQUAL(ToString(value0), "TFlags(0000000000000000)"); - UNIT_ASSERT_VALUES_EQUAL(ToString(value1), "TFlags(0000000000000001)"); - UNIT_ASSERT_VALUES_EQUAL(ToString(value7), "TFlags(0000000000000111)"); - } - + + UNIT_ASSERT_VALUES_EQUAL(ToString(value0), "TFlags(0000000000000000)"); + UNIT_ASSERT_VALUES_EQUAL(ToString(value1), "TFlags(0000000000000001)"); + UNIT_ASSERT_VALUES_EQUAL(ToString(value7), "TFlags(0000000000000111)"); + } + Y_UNIT_TEST(TestHash) { ETest1 value0 = nullptr, value1 = Test1; - + THashMap<ETest1, int> hash; - hash[value0] = 0; - hash[value1] = 1; - - UNIT_ASSERT_VALUES_EQUAL(hash[value0], 0); - UNIT_ASSERT_VALUES_EQUAL(hash[value1], 1); - } + hash[value0] = 0; + hash[value1] = 1; + + UNIT_ASSERT_VALUES_EQUAL(hash[value0], 0); + UNIT_ASSERT_VALUES_EQUAL(hash[value1], 1); + } Y_UNIT_TEST(TestBaseType) { ui16 goodValue = 7; @@ -114,4 +114,4 @@ Y_UNIT_TEST_SUITE(TFlagsTest) { auto badFlags = ETest1::FromBaseType(badValue); UNIT_ASSERT_VALUES_EQUAL(badValue, badFlags.ToBaseType()); } -} +} diff --git a/util/generic/fwd.h b/util/generic/fwd.h index 5cc2da40e5..3e3b8d8122 100644 --- a/util/generic/fwd.h +++ b/util/generic/fwd.h @@ -21,19 +21,19 @@ using TUtf32StringBuf = TBasicStringBuf<wchar32>; //misc class TBuffer; -//functors -template <class T = void> -struct TLess; - -template <class T = void> +//functors +template <class T = void> +struct TLess; + +template <class T = void> struct TGreater; -template <class T = void> -struct TEqualTo; - -template <class T> -struct THash; - +template <class T = void> +struct TEqualTo; + +template <class T> +struct THash; + //intrusive containers struct TIntrusiveListDefaultTag; template <class T, class Tag = TIntrusiveListDefaultTag> @@ -54,7 +54,7 @@ class TRbTree; //containers template <class T, class A = std::allocator<T>> class TVector; - + template <class T, class A = std::allocator<T>> class TDeque; @@ -94,22 +94,22 @@ class TMultiSet; template <class T, class S = TDeque<T>> class TStack; -template <size_t BitCount, typename TChunkType = ui64> +template <size_t BitCount, typename TChunkType = ui64> class TBitMap; //autopointers -class TDelete; +class TDelete; class TDeleteArray; class TFree; -class TCopyNew; - -template <class T, class D = TDelete> +class TCopyNew; + +template <class T, class D = TDelete> class TAutoPtr; -template <class T, class D = TDelete> +template <class T, class D = TDelete> class THolder; -template <class T, class C, class D = TDelete> +template <class T, class C, class D = TDelete> class TRefCounted; template <class T> @@ -127,10 +127,10 @@ class TIntrusiveConstPtr; template <class T, class Ops = TDefaultIntrusivePtrOps<T>> using TSimpleIntrusivePtr = TIntrusivePtr<T, TSimpleIntrusiveOps<T, Ops>>; -template <class T, class C, class D = TDelete> +template <class T, class C, class D = TDelete> class TSharedPtr; -template <class T, class C = TCopyNew, class D = TDelete> +template <class T, class C = TCopyNew, class D = TDelete> class TCopyPtr; template <class TPtr, class TCopy = TCopyNew> diff --git a/util/generic/guid.h b/util/generic/guid.h index 2bf6c8ad99..247819f88e 100644 --- a/util/generic/guid.h +++ b/util/generic/guid.h @@ -13,7 +13,7 @@ * * See https://clubs.at.yandex-team.ru/stackoverflow/10238/10240 * and https://st.yandex-team.ru/IGNIETFERRO-768 for details. - */ + */ struct TGUID { ui32 dw[4] = {}; diff --git a/util/generic/hash.cpp b/util/generic/hash.cpp index a674ee4538..07c8daf1c0 100644 --- a/util/generic/hash.cpp +++ b/util/generic/hash.cpp @@ -1,8 +1,8 @@ -#include "hash.h" - +#include "hash.h" + #include <util/string/escape.h> -#include <util/string/cast.h> - +#include <util/string/cast.h> + const void* const _yhashtable_empty_data[] = {(void*)3, nullptr, (void*)1}; TString NPrivate::MapKeyToString(TStringBuf key) { @@ -10,41 +10,41 @@ TString NPrivate::MapKeyToString(TStringBuf key) { try { return EscapeC(key.substr(0, HASH_KEY_MAX_LENGTH)); } catch (...) { - return "TStringBuf"; + return "TStringBuf"; } } - + TString NPrivate::MapKeyToString(unsigned short key) { - return ToString(key); -} - + return ToString(key); +} + TString NPrivate::MapKeyToString(short key) { - return ToString(key); -} - + return ToString(key); +} + TString NPrivate::MapKeyToString(unsigned int key) { - return ToString(key); -} - + return ToString(key); +} + TString NPrivate::MapKeyToString(int key) { - return ToString(key); -} - + return ToString(key); +} + TString NPrivate::MapKeyToString(unsigned long key) { - return ToString(key); -} - + return ToString(key); +} + TString NPrivate::MapKeyToString(long key) { - return ToString(key); -} - + return ToString(key); +} + TString NPrivate::MapKeyToString(unsigned long long key) { - return ToString(key); -} - + return ToString(key); +} + TString NPrivate::MapKeyToString(long long key) { - return ToString(key); -} + return ToString(key); +} void NPrivate::ThrowKeyNotFoundInHashTableException(const TStringBuf keyRepresentation) { ythrow yexception() << "Key not found in hashtable: " << keyRepresentation; diff --git a/util/generic/hash.h b/util/generic/hash.h index e46db21fa9..78572070a9 100644 --- a/util/generic/hash.h +++ b/util/generic/hash.h @@ -1,6 +1,6 @@ #pragma once -#include "fwd.h" +#include "fwd.h" #include "mapfindptr.h" #include <util/memory/alloc.h> @@ -19,8 +19,8 @@ #include <cstdlib> -#include "hash_primes.h" - +#include "hash_primes.h" + struct TSelect1st { template <class TPair> inline const typename TPair::first_type& operator()(const TPair& x) const { @@ -37,10 +37,10 @@ struct __yhashtable_node { * This trick makes it possible to use only one node pointer in a hash table * iterator. */ __yhashtable_node* next; - + /** Value stored in a node. */ Value val; - + __yhashtable_node& operator=(const __yhashtable_node&) = delete; }; @@ -148,19 +148,19 @@ struct __yhashtable_const_iterator { } }; -/** - * This class saves some space in allocator-based containers for the most common - * use case of empty allocators. This is achieved thanks to the application of - * empty base class optimization (aka EBCO). - */ +/** + * This class saves some space in allocator-based containers for the most common + * use case of empty allocators. This is achieved thanks to the application of + * empty base class optimization (aka EBCO). + */ template <class Alloc> -class _allocator_base: private Alloc { -public: +class _allocator_base: private Alloc { +public: _allocator_base(const Alloc& other) : Alloc(other) { } - + Alloc& _get_alloc() { return static_cast<Alloc&>(*this); } @@ -170,45 +170,45 @@ public: void _set_alloc(const Alloc& allocator) { _get_alloc() = allocator; } - + void swap(_allocator_base& other) { DoSwap(_get_alloc(), other._get_alloc()); } -}; - -/** +}; + +/** * Wrapper for an array of THashTable buckets. - * - * Is better than vector for this particular use case. Main differences: - * - Occupies one less word on stack. + * + * Is better than vector for this particular use case. Main differences: + * - Occupies one less word on stack. * - Doesn't even try to initialize its elements. It is THashTable's responsibility. * - Presents a better interface in relation to THashTable's marker element trick. - * - * Internally this class is just a pointer-size pair, and the data on the heap - * has the following structure: - * - * +----------+----------------------+----------+-------------------------+ - * | raw_size | elements ... | marker | unused space [optional] | - * +----------+----------------------+----------+-------------------------+ - * ^ ^ - * | | - * Data points here end() points here - * - * `raw_size` stores the size of the allocated memory block. It is used to - * support resizing without reallocation. - * + * + * Internally this class is just a pointer-size pair, and the data on the heap + * has the following structure: + * + * +----------+----------------------+----------+-------------------------+ + * | raw_size | elements ... | marker | unused space [optional] | + * +----------+----------------------+----------+-------------------------+ + * ^ ^ + * | | + * Data points here end() points here + * + * `raw_size` stores the size of the allocated memory block. It is used to + * support resizing without reallocation. + * * `marker` is a special marker element that is set by the THashTable that is - * then used in iterator implementation to know when the end is reached. - * - * Unused space at the end of the memory block may not be present. - */ + * then used in iterator implementation to know when the end is reached. + * + * Unused space at the end of the memory block may not be present. + */ template <class T, class Alloc> class _yhashtable_buckets: private _allocator_base<Alloc> { using base_type = _allocator_base<Alloc>; - + static_assert(sizeof(T) == sizeof(size_t), "T is expected to be the same size as size_t."); - -public: + +public: using allocator_type = Alloc; using value_type = T; using pointer = T*; @@ -220,55 +220,55 @@ public: using size_type = size_t; using difference_type = ptrdiff_t; using TBucketDivisor = ::NPrivate::THashDivisor; - + _yhashtable_buckets(const Alloc& other) : base_type(other) , Data(nullptr) , Size() { } - + ~_yhashtable_buckets() { Y_ASSERT(!Data); } - + void initialize_dynamic(TBucketDivisor size) { Y_ASSERT(!Data); - + Data = this->_get_alloc().allocate(size() + 2) + 1; Size = size; - + *reinterpret_cast<size_type*>(Data - 1) = size() + 2; } - + void deinitialize_dynamic() { Y_ASSERT(Data); - + this->_get_alloc().deallocate(Data - 1, *reinterpret_cast<size_type*>(Data - 1)); Data = pointer(); Size = TBucketDivisor(); } - + void initialize_static(pointer data, TBucketDivisor size) { Y_ASSERT(!Data && data && size() >= 1); - + Data = data; Size = size; } - + void deinitialize_static() { Y_ASSERT(Data); - + Data = pointer(); Size = TBucketDivisor(); } - + void resize_noallocate(TBucketDivisor size) { Y_ASSERT(size() <= capacity()); - + Size = size; } - + iterator begin() { return Data; } @@ -281,14 +281,14 @@ public: const_iterator end() const { return Data + Size(); } - + pointer data() { return Data; } const_pointer data() const { return Data; } - + size_type size() const { return Size(); } @@ -301,57 +301,57 @@ public: int BucketDivisorHint() const { return +Size.Hint; } - + allocator_type get_allocator() const { return this->_get_alloc(); } - + const_reference operator[](size_type index) const { Y_ASSERT(index <= Size()); - + return *(Data + index); } - + reference operator[](size_type index) { Y_ASSERT(index <= Size()); - + return *(Data + index); } - + void swap(_yhashtable_buckets& other) { base_type::swap(other); DoSwap(Data, other.Data); DoSwap(Size, other.Size); } - -private: + +private: /** Pointer to the first element of the buckets array. */ pointer Data; - + /** Size of the buckets array. Doesn't take the marker element at the end into account. */ TBucketDivisor Size; -}; - -/** +}; + +/** * This class saves one word in THashTable for the most common use case of empty - * functors. The exact implementation picks a specialization with storage allocated - * for the functors if those are non-empty, and another specialization that creates - * functors on the fly if they are empty. It is expected that empty functors have - * trivial constructors. - * - * Note that this is basically the only way to do it portably. Another option is - * multiple inheritance from empty functors, but MSVC's empty base class - * optimization chokes up on multiple empty bases, and we're already using - * EBCO in _allocator_base. - * - * Note that there are no specializations for the case when only one or two - * of the functors are empty as this is a case that's just way too rare. - */ + * functors. The exact implementation picks a specialization with storage allocated + * for the functors if those are non-empty, and another specialization that creates + * functors on the fly if they are empty. It is expected that empty functors have + * trivial constructors. + * + * Note that this is basically the only way to do it portably. Another option is + * multiple inheritance from empty functors, but MSVC's empty base class + * optimization chokes up on multiple empty bases, and we're already using + * EBCO in _allocator_base. + * + * Note that there are no specializations for the case when only one or two + * of the functors are empty as this is a case that's just way too rare. + */ template <class HashFcn, class ExtractKey, class EqualKey, class Alloc, bool IsEmpty = std::is_empty<HashFcn>::value&& std::is_empty<ExtractKey>::value&& std::is_empty<EqualKey>::value> class _yhashtable_base: public _allocator_base<Alloc> { using base_type = _allocator_base<Alloc>; -public: +public: _yhashtable_base(const HashFcn& hash, const ExtractKey& extract, const EqualKey& equals, const Alloc& alloc) : base_type(alloc) , hash_(hash) @@ -359,7 +359,7 @@ public: , equals_(equals) { } - + const EqualKey& _get_key_eq() const { return equals_; } @@ -369,7 +369,7 @@ public: void _set_key_eq(const EqualKey& equals) { this->equals_ = equals; } - + const ExtractKey& _get_key_extract() const { return extract_; } @@ -379,7 +379,7 @@ public: void _set_key_extract(const ExtractKey& extract) { this->extract_ = extract; } - + const HashFcn& _get_hash_fun() const { return hash_; } @@ -389,63 +389,63 @@ public: void _set_hash_fun(const HashFcn& hash) { this->hash_ = hash; } - + void swap(_yhashtable_base& other) { base_type::swap(other); DoSwap(equals_, other.equals_); DoSwap(extract_, other.extract_); DoSwap(hash_, other.hash_); } - -private: + +private: HashFcn hash_; ExtractKey extract_; EqualKey equals_; -}; - +}; + template <class HashFcn, class ExtractKey, class EqualKey, class Alloc> class _yhashtable_base<HashFcn, ExtractKey, EqualKey, Alloc, true>: public _allocator_base<Alloc> { using base_type = _allocator_base<Alloc>; - -public: + +public: _yhashtable_base(const HashFcn&, const ExtractKey&, const EqualKey&, const Alloc& alloc) : base_type(alloc) { } - + EqualKey _get_key_eq() const { return EqualKey(); } void _set_key_eq(const EqualKey&) { } - + ExtractKey _get_key_extract() const { return ExtractKey(); } void _set_key_extract(const ExtractKey&) { } - + HashFcn _get_hash_fun() const { return HashFcn(); } void _set_hash_fun(const HashFcn&) { } - + void swap(_yhashtable_base& other) { base_type::swap(other); } -}; - -template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc> +}; + +template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc> struct _yhashtable_traits { using node = __yhashtable_node<Value>; - + using node_allocator_type = TReboundAllocator<Alloc, node>; using nodep_allocator_type = TReboundAllocator<Alloc, node*>; - + using base_type = _yhashtable_base<HashFcn, ExtractKey, EqualKey, node_allocator_type>; -}; - +}; + extern const void* const _yhashtable_empty_data[]; template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc> @@ -456,7 +456,7 @@ class THashTable: private _yhashtable_traits<Value, Key, HashFcn, ExtractKey, Eq using nodep_allocator_type = typename traits_type::nodep_allocator_type; using buckets_type = _yhashtable_buckets<node*, nodep_allocator_type>; using TBucketDivisor = ::NPrivate::THashDivisor; - + public: using key_type = Key; using value_type = Value; @@ -497,16 +497,16 @@ private: auto get_key(const ValueL& value) const -> decltype(ExtractKey()(value)) { return this->_get_key_extract()(value); } - + node* get_node() { - node* result = this->_get_alloc().allocate(1); + node* result = this->_get_alloc().allocate(1); Y_ASSERT((reinterpret_cast<uintptr_t>(result) & 1) == 0); /* We're using the last bit of the node pointer. */ - return result; + return result; } void put_node(node* p) { this->_get_alloc().deallocate(p, 1); } - + buckets_type buckets; size_type num_elements; @@ -526,7 +526,7 @@ public: { initialize_buckets(buckets, 0); } - + THashTable(size_type n, const HashFcn& hf, const EqualKey& eql, const ExtractKey& ext) : base_type(hf, ext, eql, node_allocator_type()) , buckets(nodep_allocator_type()) @@ -550,7 +550,7 @@ public: , num_elements(0) { initialize_buckets(buckets, n); - } + } THashTable(const THashTable& ht) : base_type(ht._get_hash_fun(), ht._get_key_extract(), ht._get_key_eq(), ht._get_alloc()) @@ -559,12 +559,12 @@ public: { if (ht.empty()) { initialize_buckets(buckets, 0); - } else { + } else { initialize_buckets_dynamic(buckets, ht.buckets.ExtSize()); copy_from_dynamic(ht); - } + } } - + THashTable(THashTable&& ht) noexcept : base_type(ht._get_hash_fun(), ht._get_key_extract(), ht._get_key_eq(), ht._get_alloc()) , buckets(ht.buckets.get_allocator()) @@ -580,16 +580,16 @@ public: this->_set_hash_fun(ht._get_hash_fun()); this->_set_key_eq(ht._get_key_eq()); this->_set_key_extract(ht._get_key_extract()); - /* We don't copy allocator for a reason. */ - - if (ht.empty()) { - /* Some of the old code in Arcadia works around the behavior in - * clear() by invoking operator= with empty hash as an argument. - * It's expected that this will deallocate the buckets array, so - * this is what we have to do here. */ - deinitialize_buckets(buckets); - initialize_buckets(buckets, 0); - } else { + /* We don't copy allocator for a reason. */ + + if (ht.empty()) { + /* Some of the old code in Arcadia works around the behavior in + * clear() by invoking operator= with empty hash as an argument. + * It's expected that this will deallocate the buckets array, so + * this is what we have to do here. */ + deinitialize_buckets(buckets); + initialize_buckets(buckets, 0); + } else { if (buckets.capacity() > ht.buckets.size()) { buckets.resize_noallocate(ht.buckets.ExtSize()); } else { @@ -604,8 +604,8 @@ public: } THashTable& operator=(THashTable&& ht) noexcept { - basic_clear(); - swap(ht); + basic_clear(); + swap(ht); return *this; } @@ -668,13 +668,13 @@ public: } template <class OtherValue> - std::pair<iterator, bool> insert_unique(const OtherValue& obj) { + std::pair<iterator, bool> insert_unique(const OtherValue& obj) { reserve(num_elements + 1); return insert_unique_noresize(obj); } template <class OtherValue> - iterator insert_equal(const OtherValue& obj) { + iterator insert_equal(const OtherValue& obj) { reserve(num_elements + 1); return emplace_equal_noresize(obj); } @@ -686,7 +686,7 @@ public: } template <class OtherValue> - iterator insert_direct(const OtherValue& obj, insert_ctx ins) { + iterator insert_direct(const OtherValue& obj, insert_ctx ins) { return emplace_direct(ins, obj); } @@ -712,9 +712,9 @@ public: template <typename... Args> std::pair<iterator, bool> emplace_unique_noresize(Args&&... args); - template <class OtherValue> - std::pair<iterator, bool> insert_unique_noresize(const OtherValue& obj); - + template <class OtherValue> + std::pair<iterator, bool> insert_unique_noresize(const OtherValue& obj); + template <typename... Args> iterator emplace_equal_noresize(Args&&... args); @@ -759,10 +759,10 @@ public: } template <class OtherValue> - reference find_or_insert(const OtherValue& v); + reference find_or_insert(const OtherValue& v); template <class OtherKey> - iterator find(const OtherKey& key) { + iterator find(const OtherKey& key) { size_type n = bkt_num_key(key); node* first; for (first = buckets[n]; @@ -774,7 +774,7 @@ public: } template <class OtherKey> - const_iterator find(const OtherKey& key) const { + const_iterator find(const OtherKey& key) const { size_type n = bkt_num_key(key); const node* first; for (first = buckets[n]; @@ -786,10 +786,10 @@ public: } template <class OtherKey> - iterator find_i(const OtherKey& key, insert_ctx& ins); + iterator find_i(const OtherKey& key, insert_ctx& ins); template <class OtherKey> - size_type count(const OtherKey& key) const { + size_type count(const OtherKey& key) const { const size_type n = bkt_num_key(key); size_type result = 0; @@ -801,17 +801,17 @@ public: } template <class OtherKey> - std::pair<iterator, iterator> equal_range(const OtherKey& key); + std::pair<iterator, iterator> equal_range(const OtherKey& key); template <class OtherKey> - std::pair<const_iterator, const_iterator> equal_range(const OtherKey& key) const; - + std::pair<const_iterator, const_iterator> equal_range(const OtherKey& key) const; + template <class OtherKey> - size_type erase(const OtherKey& key); - + size_type erase(const OtherKey& key); + template <class OtherKey> - size_type erase_one(const OtherKey& key); - + size_type erase_one(const OtherKey& key); + // void (instead of iterator) is intended, see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2023.pdf void erase(const iterator& it); void erase(iterator first, iterator last); @@ -822,21 +822,21 @@ public: bool reserve(size_type num_elements_hint); void basic_clear(); - /** - * Clears the hashtable without deallocating the nodes. - * - * This might come in handy with non-standard allocators, e.g. a pool - * allocator with a pool that is then cleared manually, thus releasing all - * the nodes at once. - */ - void release_nodes() { - if (empty()) - return; /* Need this check because empty buckets may reside in read-only memory. */ - - clear_buckets(buckets); - num_elements = 0; - } - + /** + * Clears the hashtable without deallocating the nodes. + * + * This might come in handy with non-standard allocators, e.g. a pool + * allocator with a pool that is then cleared manually, thus releasing all + * the nodes at once. + */ + void release_nodes() { + if (empty()) + return; /* Need this check because empty buckets may reside in read-only memory. */ + + clear_buckets(buckets); + num_elements = 0; + } + // implemented in save_stl.h template <class KeySaver> int save_for_st(IOutputStream* stream, KeySaver& ks, sthash<int, int, THash<int>, TEqualTo<int>, typename KeySaver::TSizeType>* stHash = nullptr) const; @@ -852,7 +852,7 @@ public: } } } - + /** * Clears the hashtable and tries to reasonably downsize it. Note that * downsizing is mainly for the following use case: @@ -884,36 +884,36 @@ private: } else { TBucketDivisor size = HashBucketCountExt(sizeHint); Y_ASSERT(size() >= 7); - + initialize_buckets_dynamic(buckets, size); } - } + } static void initialize_buckets_dynamic(buckets_type& buckets, TBucketDivisor size) { buckets.initialize_dynamic(size); memset(buckets.data(), 0, size() * sizeof(*buckets.data())); buckets[size()] = (node*)1; } - + static void deinitialize_buckets(buckets_type& buckets) { if (buckets.size() == 1) { buckets.deinitialize_static(); } else { buckets.deinitialize_dynamic(); } - } - + } + static void clear_buckets(buckets_type& buckets) { memset(buckets.data(), 0, buckets.size() * sizeof(*buckets.data())); } - + template <class OtherKey> - size_type bkt_num_key(const OtherKey& key) const { + size_type bkt_num_key(const OtherKey& key) const { return bkt_num_key(key, buckets.ExtSize()); } template <class OtherValue> - size_type bkt_num(const OtherValue& obj) const { + size_type bkt_num(const OtherValue& obj) const { return bkt_num_key(get_key(obj)); } @@ -1019,7 +1019,7 @@ std::pair<typename THashTable<V, K, HF, Ex, Eq, A>::iterator, bool> THashTable<V } template <class V, class K, class HF, class Ex, class Eq, class A> -template <class OtherValue> +template <class OtherValue> std::pair<typename THashTable<V, K, HF, Ex, Eq, A>::iterator, bool> THashTable<V, K, HF, Ex, Eq, A>::insert_unique_noresize(const OtherValue& obj) { const size_type n = bkt_num(obj); node* first = buckets[n]; @@ -1063,7 +1063,7 @@ __yhashtable_iterator<V> THashTable<V, K, HF, Ex, Eq, A>::emplace_equal_noresize } template <class V, class K, class HF, class Ex, class Eq, class A> -template <class OtherValue> +template <class OtherValue> typename THashTable<V, K, HF, Ex, Eq, A>::reference THashTable<V, K, HF, Ex, Eq, A>::find_or_insert(const OtherValue& v) { reserve(num_elements + 1); @@ -1083,7 +1083,7 @@ typename THashTable<V, K, HF, Ex, Eq, A>::reference THashTable<V, K, HF, Ex, Eq, } template <class V, class K, class HF, class Ex, class Eq, class A> -template <class OtherKey> +template <class OtherKey> __yhashtable_iterator<V> THashTable<V, K, HF, Ex, Eq, A>::find_i(const OtherKey& key, insert_ctx& ins) { size_type n = bkt_num_key(key); ins = &buckets[n]; @@ -1097,7 +1097,7 @@ __yhashtable_iterator<V> THashTable<V, K, HF, Ex, Eq, A>::find_i(const OtherKey& } template <class V, class K, class HF, class Ex, class Eq, class A> -template <class OtherKey> +template <class OtherKey> std::pair<__yhashtable_iterator<V>, __yhashtable_iterator<V>> THashTable<V, K, HF, Ex, Eq, A>::equal_range(const OtherKey& key) { using pii = std::pair<iterator, iterator>; const size_type n = bkt_num_key(key); @@ -1120,7 +1120,7 @@ std::pair<__yhashtable_iterator<V>, __yhashtable_iterator<V>> THashTable<V, K, H } template <class V, class K, class HF, class Ex, class Eq, class A> -template <class OtherKey> +template <class OtherKey> std::pair<__yhashtable_const_iterator<V>, __yhashtable_const_iterator<V>> THashTable<V, K, HF, Ex, Eq, A>::equal_range(const OtherKey& key) const { using pii = std::pair<const_iterator, const_iterator>; const size_type n = bkt_num_key(key); @@ -1144,7 +1144,7 @@ std::pair<__yhashtable_const_iterator<V>, __yhashtable_const_iterator<V>> THashT } template <class V, class K, class HF, class Ex, class Eq, class A> -template <class OtherKey> +template <class OtherKey> typename THashTable<V, K, HF, Ex, Eq, A>::size_type THashTable<V, K, HF, Ex, Eq, A>::erase(const OtherKey& key) { const size_type n = bkt_num_key(key); node* first = buckets[n]; @@ -1176,7 +1176,7 @@ typename THashTable<V, K, HF, Ex, Eq, A>::size_type THashTable<V, K, HF, Ex, Eq, } template <class V, class K, class HF, class Ex, class Eq, class A> -template <class OtherKey> +template <class OtherKey> typename THashTable<V, K, HF, Ex, Eq, A>::size_type THashTable<V, K, HF, Ex, Eq, A>::erase_one(const OtherKey& key) { const size_type n = bkt_num_key(key); node* first = buckets[n]; @@ -1287,7 +1287,7 @@ bool THashTable<V, K, HF, Ex, Eq, A>::reserve(size_type num_elements_hint) { first = buckets[bucket]; } } - + buckets.swap(tmp); deinitialize_buckets(tmp); @@ -1365,7 +1365,7 @@ void THashTable<V, K, HF, Ex, Eq, A>::basic_clear() { template <class V, class K, class HF, class Ex, class Eq, class A> void THashTable<V, K, HF, Ex, Eq, A>::copy_from_dynamic(const THashTable& ht) { Y_ASSERT(buckets.size() == ht.buckets.size() && !ht.empty()); - + #ifdef __STL_USE_EXCEPTIONS try { #endif /* __STL_USE_EXCEPTIONS */ @@ -1391,9 +1391,9 @@ void THashTable<V, K, HF, Ex, Eq, A>::copy_from_dynamic(const THashTable& ht) { } namespace NPrivate { - template <class Key> + template <class Key> inline TString MapKeyToString(const Key&) { - return TypeName<Key>(); + return TypeName<Key>(); } TString MapKeyToString(TStringBuf key); @@ -1649,7 +1649,7 @@ public: template <class TheKey> const T& at(const TheKey& key) const { - using namespace ::NPrivate; + using namespace ::NPrivate; const_iterator it = find(key); if (Y_UNLIKELY(it == end())) { @@ -1661,7 +1661,7 @@ public: template <class TheKey> T& at(const TheKey& key) { - using namespace ::NPrivate; + using namespace ::NPrivate; iterator it = find(key); if (Y_UNLIKELY(it == end())) { @@ -1706,14 +1706,14 @@ public: void basic_clear() { rep.basic_clear(); } - void release_nodes() { - rep.release_nodes(); - } + void release_nodes() { + rep.release_nodes(); + } // if (stHash != NULL) bucket_count() must be equal to stHash->bucket_count() template <class KeySaver> int save_for_st(IOutputStream* stream, KeySaver& ks, sthash<int, int, THash<int>, TEqualTo<int>, typename KeySaver::TSizeType>* stHash = nullptr) const { - return rep.template save_for_st<KeySaver>(stream, ks, stHash); + return rep.template save_for_st<KeySaver>(stream, ks, stHash); } public: @@ -1748,12 +1748,12 @@ inline bool operator==(const THashMap<Key, T, HashFcn, EqualKey, Alloc>& hm1, co return true; } -template <class Key, class T, class HashFcn, class EqualKey, class Alloc> +template <class Key, class T, class HashFcn, class EqualKey, class Alloc> inline bool operator!=(const THashMap<Key, T, HashFcn, EqualKey, Alloc>& hm1, const THashMap<Key, T, HashFcn, EqualKey, Alloc>& hm2) { - return !(hm1 == hm2); -} - -template <class Key, class T, class HashFcn, class EqualKey, class Alloc> + return !(hm1 == hm2); +} + +template <class Key, class T, class HashFcn, class EqualKey, class Alloc> class THashMultiMap { private: using ht = THashTable<std::pair<const Key, T>, Key, HashFcn, TSelect1st, EqualKey, Alloc>; @@ -1972,9 +1972,9 @@ public: void basic_clear() { rep.basic_clear(); } - void release_nodes() { - rep.release_nodes(); - } + void release_nodes() { + rep.release_nodes(); + } // if (stHash != NULL) bucket_count() must be equal to stHash->bucket_count() template <class KeySaver> @@ -2017,10 +2017,10 @@ inline bool operator==(const THashMultiMap<Key, T, HF, EqKey, Alloc>& hm1, const return true; } -template <class Key, class T, class HF, class EqKey, class Alloc> +template <class Key, class T, class HF, class EqKey, class Alloc> inline bool operator!=(const THashMultiMap<Key, T, HF, EqKey, Alloc>& hm1, const THashMultiMap<Key, T, HF, EqKey, Alloc>& hm2) { - return !(hm1 == hm2); -} + return !(hm1 == hm2); +} // Cannot name it just 'Hash' because it clashes with too many class members in the code. template <class T> diff --git a/util/generic/hash_primes.cpp b/util/generic/hash_primes.cpp index 656d31e046..1c3594eb46 100644 --- a/util/generic/hash_primes.cpp +++ b/util/generic/hash_primes.cpp @@ -1,7 +1,7 @@ -#include "hash_primes.h" -#include "array_size.h" +#include "hash_primes.h" +#include "array_size.h" #include "algorithm.h" - + /// Order of fields: reciprocal, reciprocal shift, adjacent hint, divisor #if defined(_32_) static constexpr ::NPrivate::THashDivisor PRIME_DIVISORS_HOLDER[]{ diff --git a/util/generic/hash_primes.h b/util/generic/hash_primes.h index 4dc2da0b8f..a7750716b7 100644 --- a/util/generic/hash_primes.h +++ b/util/generic/hash_primes.h @@ -1,5 +1,5 @@ -#pragma once - +#pragma once + #include <util/system/compiler.h> #include <util/system/types.h> @@ -7,14 +7,14 @@ #include <intrin.h> #endif -/** - * Calculates the number of buckets for the hash table that will hold the given - * number of elements. - * - * @param elementCount Number of elements that the hash table will hold. - * @returns Number of buckets, a prime number that is - * greater or equal to `elementCount`. - */ +/** + * Calculates the number of buckets for the hash table that will hold the given + * number of elements. + * + * @param elementCount Number of elements that the hash table will hold. + * @returns Number of buckets, a prime number that is + * greater or equal to `elementCount`. + */ Y_CONST_FUNCTION unsigned long HashBucketCount(unsigned long elementCount); diff --git a/util/generic/hash_set.h b/util/generic/hash_set.h index e8088cf23b..24333e16c4 100644 --- a/util/generic/hash_set.h +++ b/util/generic/hash_set.h @@ -1,11 +1,11 @@ #pragma once -#include "fwd.h" +#include "fwd.h" #include "hash.h" -#include <initializer_list> +#include <initializer_list> #include <utility> - + #undef value_type template <class Value, class HashFcn, class EqualKey, class Alloc> @@ -65,25 +65,25 @@ public: THashSet(std::initializer_list<value_type> list) : rep(list.size(), hasher(), key_equal()) - { - rep.insert_unique(list.begin(), list.end()); - } + { + rep.insert_unique(list.begin(), list.end()); + } THashSet(std::initializer_list<value_type> list, size_type n) - : rep(n, hasher(), key_equal()) - { - rep.insert_unique(list.begin(), list.end()); - } + : rep(n, hasher(), key_equal()) + { + rep.insert_unique(list.begin(), list.end()); + } THashSet(std::initializer_list<value_type> list, size_type n, const hasher& hf) - : rep(n, hf, key_equal()) - { - rep.insert_unique(list.begin(), list.end()); - } + : rep(n, hf, key_equal()) + { + rep.insert_unique(list.begin(), list.end()); + } THashSet(std::initializer_list<value_type> list, size_type n, const hasher& hf, const key_equal& eql) - : rep(n, hf, eql) - { - rep.insert_unique(list.begin(), list.end()); - } - + : rep(n, hf, eql) + { + rep.insert_unique(list.begin(), list.end()); + } + template <class InputIterator> THashSet(InputIterator f, InputIterator l) : rep(0, hasher(), key_equal()) @@ -168,9 +168,9 @@ public: iterator insert(const_iterator, const value_type& obj) { // insert_hint std::pair<mutable_iterator, bool> p = rep.insert_unique(obj); - return p.first; - } - + return p.first; + } + std::pair<iterator, bool> insert_noresize(const value_type& obj) { std::pair<mutable_iterator, bool> p = rep.insert_unique_noresize(obj); return std::pair<iterator, bool>(p.first, p.second); @@ -236,13 +236,13 @@ public: void basic_clear() { rep.basic_clear(); } - void release_nodes() { - rep.release_nodes(); - } + void release_nodes() { + rep.release_nodes(); + } template <class KeySaver> int save_for_st(IOutputStream* stream, KeySaver& ks) const { - return rep.template save_for_st<KeySaver>(stream, ks); + return rep.template save_for_st<KeySaver>(stream, ks); } public: @@ -273,12 +273,12 @@ inline bool operator==(const THashSet<Value, HashFcn, EqualKey, Alloc>& hs1, con return true; } -template <class Value, class HashFcn, class EqualKey, class Alloc> +template <class Value, class HashFcn, class EqualKey, class Alloc> inline bool operator!=(const THashSet<Value, HashFcn, EqualKey, Alloc>& hs1, const THashSet<Value, HashFcn, EqualKey, Alloc>& hs2) { - return !(hs1 == hs2); -} - -template <class Value, class HashFcn, class EqualKey, class Alloc> + return !(hs1 == hs2); +} + +template <class Value, class HashFcn, class EqualKey, class Alloc> class THashMultiSet { private: using ht = THashTable<Value, Value, HashFcn, ::TIdentity, EqualKey, Alloc>; @@ -444,9 +444,9 @@ public: void basic_clear() { rep.basic_clear(); } - void release_nodes() { - rep.release_nodes(); - } + void release_nodes() { + rep.release_nodes(); + } public: void reserve(size_type hint) { @@ -481,8 +481,8 @@ inline bool operator==(const THashMultiSet<Val, HashFcn, EqualKey, Alloc>& hs1, } return true; } - -template <class Val, class HashFcn, class EqualKey, class Alloc> + +template <class Val, class HashFcn, class EqualKey, class Alloc> inline bool operator!=(const THashMultiSet<Val, HashFcn, EqualKey, Alloc>& hs1, const THashMultiSet<Val, HashFcn, EqualKey, Alloc>& hs2) { - return !(hs1 == hs2); -} + return !(hs1 == hs2); +} diff --git a/util/generic/hash_ut.cpp b/util/generic/hash_ut.cpp index 0551d58770..7153d7a742 100644 --- a/util/generic/hash_ut.cpp +++ b/util/generic/hash_ut.cpp @@ -36,7 +36,7 @@ class THashTest: public TTestBase { UNIT_TEST(TestSizeOf); UNIT_TEST(TestInvariants); UNIT_TEST(TestAllocation); - UNIT_TEST(TestInsertCopy); + UNIT_TEST(TestInsertCopy); UNIT_TEST(TestEmplace); UNIT_TEST(TestEmplaceNoresize); UNIT_TEST(TestEmplaceDirect); @@ -49,9 +49,9 @@ class THashTest: public TTestBase { UNIT_TEST(TestHSetEmplaceNoresize); UNIT_TEST(TestHSetEmplaceDirect); UNIT_TEST(TestNonCopyable); - UNIT_TEST(TestValueInitialization); - UNIT_TEST(TestAssignmentClear); - UNIT_TEST(TestReleaseNodes); + UNIT_TEST(TestValueInitialization); + UNIT_TEST(TestAssignmentClear); + UNIT_TEST(TestReleaseNodes); UNIT_TEST(TestAt); UNIT_TEST(TestHMapInitializerList); UNIT_TEST(TestHMMapInitializerList); @@ -87,7 +87,7 @@ protected: void TestSizeOf(); void TestInvariants(); void TestAllocation(); - void TestInsertCopy(); + void TestInsertCopy(); void TestEmplace(); void TestEmplaceNoresize(); void TestEmplaceDirect(); @@ -100,9 +100,9 @@ protected: void TestHMMapEmplaceNoresize(); void TestHMMapEmplaceDirect(); void TestNonCopyable(); - void TestValueInitialization(); - void TestAssignmentClear(); - void TestReleaseNodes(); + void TestValueInitialization(); + void TestAssignmentClear(); + void TestReleaseNodes(); void TestAt(); void TestHMapInitializerList(); void TestHMMapInitializerList(); @@ -218,11 +218,11 @@ void THashTest::TestHMapEqualityOperator() { UNIT_ASSERT(c2 == base); c2["three"] = 3; - UNIT_ASSERT(c2 != base); + UNIT_ASSERT(c2 != base); container c3(base); c3["one"] = 0; - UNIT_ASSERT(c3 != base); + UNIT_ASSERT(c3 != base); } void THashTest::TestHMMapEqualityOperator() { @@ -399,9 +399,9 @@ void THashTest::TestHSetConstructorsAndAssignments() { UNIT_ASSERT_VALUES_EQUAL(0, c2.size()); UNIT_ASSERT_VALUES_EQUAL(4, c3.size()); UNIT_ASSERT(c3.contains(400)); - - container c4 = {1, 2, 3}; - UNIT_ASSERT_VALUES_EQUAL(c4.size(), 3); + + container c4 = {1, 2, 3}; + UNIT_ASSERT_VALUES_EQUAL(c4.size(), 3); UNIT_ASSERT(c4.contains(1)); UNIT_ASSERT(c4.contains(2)); UNIT_ASSERT(c4.contains(3)); @@ -423,7 +423,7 @@ void THashTest::TestHSetSize() { void THashTest::TestHSet2() { THashSet<int, THash<int>, TEqualTo<int>> s; - auto p = s.insert(42); + auto p = s.insert(42); UNIT_ASSERT(p.second); UNIT_ASSERT(*(p.first) == 42); @@ -445,7 +445,7 @@ void THashTest::TestHSetEqualityOperator() { UNIT_ASSERT(c1 == base); c1.insert(3); - UNIT_ASSERT(c1 != base); + UNIT_ASSERT(c1 != base); container c2; c2.insert(2); @@ -454,7 +454,7 @@ void THashTest::TestHSetEqualityOperator() { container c3; c3.insert(1); - UNIT_ASSERT(c3 != base); + UNIT_ASSERT(c3 != base); } void THashTest::TestHMSetConstructorsAndAssignments() { @@ -513,7 +513,7 @@ void THashTest::TestHMSet1() { UNIT_ASSERT(s.count(star) == 1); s.insert(star); UNIT_ASSERT(s.count(star) == 2); - auto i = s.find(char(40)); + auto i = s.find(char(40)); UNIT_ASSERT(i == s.end()); i = s.find(star); @@ -659,7 +659,7 @@ namespace { THash<TString>, TSelectKey, TEqualTo<TString>, - std::allocator<TItemPtr>>; + std::allocator<TItemPtr>>; struct TItemMap: public TItemMapBase { TItemMap() @@ -705,188 +705,188 @@ void THashTest::TestEmpty() { EmptyAndInsertTest<THashMap<int, int>>(std::pair<int, int>(1, 2)); EmptyAndInsertTest<THashMultiMap<int, int>>(std::pair<int, int>(1, 2)); } - -void THashTest::TestDefaultConstructor() { + +void THashTest::TestDefaultConstructor() { THashSet<int> set; - - UNIT_ASSERT(set.begin() == set.end()); - - UNIT_ASSERT(set.find(0) == set.end()); - - auto range = set.equal_range(0); - UNIT_ASSERT(range.first == range.second); -} - -void THashTest::TestSizeOf() { - /* This test checks that we don't waste memory when all functors passed to + + UNIT_ASSERT(set.begin() == set.end()); + + UNIT_ASSERT(set.find(0) == set.end()); + + auto range = set.equal_range(0); + UNIT_ASSERT(range.first == range.second); +} + +void THashTest::TestSizeOf() { + /* This test checks that we don't waste memory when all functors passed to * THashTable are empty. It does rely on knowledge of THashTable internals, - * so if those change, the test will have to be adjusted accordingly. */ - + * so if those change, the test will have to be adjusted accordingly. */ + size_t expectedSize = sizeof(uintptr_t) + 3 * sizeof(size_t); - + UNIT_ASSERT_VALUES_EQUAL(sizeof(THashMap<int, int>), expectedSize); UNIT_ASSERT_VALUES_EQUAL(sizeof(THashMap<std::pair<int, int>, std::pair<int, int>>), expectedSize); -} - -void THashTest::TestInvariants() { +} + +void THashTest::TestInvariants() { std::set<int> reference_set; THashSet<int> set; - - for (int i = 0; i < 1000; i++) { - set.insert(i); - reference_set.insert(i); - } - UNIT_ASSERT_VALUES_EQUAL(set.size(), 1000); - - int count0 = 0; + + for (int i = 0; i < 1000; i++) { + set.insert(i); + reference_set.insert(i); + } + UNIT_ASSERT_VALUES_EQUAL(set.size(), 1000); + + int count0 = 0; for (int i = 0; i < 1000; i++) { - count0 += (set.find(i) != set.end()) ? 1 : 0; + count0 += (set.find(i) != set.end()) ? 1 : 0; } - UNIT_ASSERT_VALUES_EQUAL(count0, 1000); - - int count1 = 0; + UNIT_ASSERT_VALUES_EQUAL(count0, 1000); + + int count1 = 0; for (auto pos = set.begin(); pos != set.end(); pos++) { ++count1; } - UNIT_ASSERT_VALUES_EQUAL(count1, 1000); - - int count2 = 0; + UNIT_ASSERT_VALUES_EQUAL(count1, 1000); + + int count2 = 0; for (const int& value : set) { - count2 += (reference_set.find(value) != reference_set.end()) ? 1 : 0; + count2 += (reference_set.find(value) != reference_set.end()) ? 1 : 0; } - UNIT_ASSERT_VALUES_EQUAL(count2, 1000); -} - -struct TAllocatorCounters { - TAllocatorCounters() - : Allocations(0) - , Deallocations(0) + UNIT_ASSERT_VALUES_EQUAL(count2, 1000); +} + +struct TAllocatorCounters { + TAllocatorCounters() + : Allocations(0) + , Deallocations(0) { } - - ~TAllocatorCounters() { + + ~TAllocatorCounters() { std::allocator<char> allocator; - - /* Release whatever was (intentionally) leaked. */ + + /* Release whatever was (intentionally) leaked. */ for (const auto& chunk : Chunks) { - allocator.deallocate(static_cast<char*>(chunk.first), chunk.second); + allocator.deallocate(static_cast<char*>(chunk.first), chunk.second); } - } - - size_t Allocations; - size_t Deallocations; + } + + size_t Allocations; + size_t Deallocations; TSet<std::pair<void*, size_t>> Chunks; -}; - +}; + template <class T> class TCountingAllocator: public std::allocator<T> { using base_type = std::allocator<T>; -public: +public: using size_type = typename base_type::size_type; - + template <class Other> - struct rebind { - using other = TCountingAllocator<Other>; - }; - - TCountingAllocator() + struct rebind { + using other = TCountingAllocator<Other>; + }; + + TCountingAllocator() : Counters_(nullptr) { } - - TCountingAllocator(TAllocatorCounters* counters) + + TCountingAllocator(TAllocatorCounters* counters) : Counters_(counters) { Y_ASSERT(counters); - } - + } + template <class Other> - TCountingAllocator(const TCountingAllocator<Other>& other) + TCountingAllocator(const TCountingAllocator<Other>& other) : Counters_(other.Counters) { } - + T* allocate(size_type n) { auto result = base_type::allocate(n); - + if (Counters_) { ++Counters_->Allocations; Counters_->Chunks.emplace(result, n * sizeof(T)); - } - - return result; - } - + } + + return result; + } + void deallocate(T* p, size_type n) { if (Counters_) { ++Counters_->Deallocations; Counters_->Chunks.erase(std::make_pair(p, n * sizeof(T))); - } - - base_type::deallocate(p, n); - } - -private: + } + + base_type::deallocate(p, n); + } + +private: TAllocatorCounters* Counters_; -}; - -void THashTest::TestAllocation() { - TAllocatorCounters counters; - +}; + +void THashTest::TestAllocation() { + TAllocatorCounters counters; + using int_set = THashSet<int, THash<int>, TEqualTo<int>, TCountingAllocator<int>>; - - { - int_set set0(&counters); - int_set set1(set0); - set0.clear(); - int_set set2(&counters); - set2 = set1; - UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 0); /* Copying around null sets should not trigger allocations. */ - - set0.insert(0); - UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 2); /* One for buckets array, one for a new node. */ - - set0.clear(); - set1 = set0; - int_set set3(set0); - UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 2); /* Copying from an empty set with allocated buckets should not trigger allocations. */ - + + { + int_set set0(&counters); + int_set set1(set0); + set0.clear(); + int_set set2(&counters); + set2 = set1; + UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 0); /* Copying around null sets should not trigger allocations. */ + + set0.insert(0); + UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 2); /* One for buckets array, one for a new node. */ + + set0.clear(); + set1 = set0; + int_set set3(set0); + UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 2); /* Copying from an empty set with allocated buckets should not trigger allocations. */ + for (int i = 0; i < 1000; i++) { - set0.insert(i); + set0.insert(i); } - size_t allocations = counters.Allocations; - set0.clear(); - UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, allocations); /* clear() should not trigger allocations. */ - } - - UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, counters.Deallocations); -} - + size_t allocations = counters.Allocations; + set0.clear(); + UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, allocations); /* clear() should not trigger allocations. */ + } + + UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, counters.Deallocations); +} + template <int Value> -class TNonCopyableInt { -public: +class TNonCopyableInt { +public: explicit TNonCopyableInt(int) { } - - TNonCopyableInt() = delete; - TNonCopyableInt(const TNonCopyableInt&) = delete; - TNonCopyableInt(TNonCopyable&&) = delete; + + TNonCopyableInt() = delete; + TNonCopyableInt(const TNonCopyableInt&) = delete; + TNonCopyableInt(TNonCopyable&&) = delete; TNonCopyableInt& operator=(const TNonCopyable&) = delete; TNonCopyableInt& operator=(TNonCopyable&&) = delete; - - operator int() const { - return Value; - } -}; - -void THashTest::TestInsertCopy() { + + operator int() const { + return Value; + } +}; + +void THashTest::TestInsertCopy() { THashMap<int, int> hash; - - /* Insertion should not make copies of the provided key. */ - hash[TNonCopyableInt<0>(0)] = 0; -} - + + /* Insertion should not make copies of the provided key. */ + hash[TNonCopyableInt<0>(0)] = 0; +} + void THashTest::TestEmplace() { using hash_t = THashMap<int, TNonCopyableInt<0>>; hash_t hash; @@ -1057,60 +1057,60 @@ void THashTest::TestNonCopyable() { UNIT_ASSERT_VALUES_EQUAL(static_cast<int>(not_inserted), 0); } -void THashTest::TestValueInitialization() { +void THashTest::TestValueInitialization() { THashMap<int, int> hash; - + int& value = hash[0]; - - /* Implicitly inserted values should be value-initialized. */ - UNIT_ASSERT_VALUES_EQUAL(value, 0); -} - -void THashTest::TestAssignmentClear() { - /* This one tests that assigning an empty hash resets the buckets array. - * See operator= for details. */ - + + /* Implicitly inserted values should be value-initialized. */ + UNIT_ASSERT_VALUES_EQUAL(value, 0); +} + +void THashTest::TestAssignmentClear() { + /* This one tests that assigning an empty hash resets the buckets array. + * See operator= for details. */ + THashMap<int, int> hash; - size_t emptyBucketCount = hash.bucket_count(); - - for (int i = 0; i < 100; i++) { - hash[i] = i; - } - + size_t emptyBucketCount = hash.bucket_count(); + + for (int i = 0; i < 100; i++) { + hash[i] = i; + } + hash = THashMap<int, int>(); - - UNIT_ASSERT_VALUES_EQUAL(hash.bucket_count(), emptyBucketCount); -} - -void THashTest::TestReleaseNodes() { - TAllocatorCounters counters; + + UNIT_ASSERT_VALUES_EQUAL(hash.bucket_count(), emptyBucketCount); +} + +void THashTest::TestReleaseNodes() { + TAllocatorCounters counters; using TIntSet = THashSet<int, THash<int>, TEqualTo<int>, TCountingAllocator<int>>; - - TIntSet set(&counters); + + TIntSet set(&counters); for (int i = 0; i < 3; i++) { - set.insert(i); + set.insert(i); } - UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 4); - - set.release_nodes(); - UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 4); - UNIT_ASSERT_VALUES_EQUAL(set.size(), 0); - + UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 4); + + set.release_nodes(); + UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 4); + UNIT_ASSERT_VALUES_EQUAL(set.size(), 0); + for (int i = 10; i < 13; i++) { - set.insert(i); + set.insert(i); } - UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 7); + UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 7); UNIT_ASSERT(set.contains(10)); UNIT_ASSERT(!set.contains(0)); - - set.basic_clear(); - UNIT_ASSERT_VALUES_EQUAL(counters.Deallocations, 3); - - TIntSet set2; - set2.release_nodes(); - set2.insert(1); - UNIT_ASSERT_VALUES_EQUAL(set2.size(), 1); -} + + set.basic_clear(); + UNIT_ASSERT_VALUES_EQUAL(counters.Deallocations, 3); + + TIntSet set2; + set2.release_nodes(); + set2.insert(1); + UNIT_ASSERT_VALUES_EQUAL(set2.size(), 1); +} void THashTest::TestAt() { #define TEST_AT_THROWN_EXCEPTION(SRC_TYPE, DST_TYPE, KEY_TYPE, KEY, MESSAGE) \ @@ -1121,7 +1121,7 @@ void THashTest::TestAt() { testMap.at(testKey); \ UNIT_ASSERT_C(false, "THashMap::at(\"" << KEY << "\") should throw"); \ } catch (const yexception& e) { \ - UNIT_ASSERT_C(e.AsStrBuf().Contains(MESSAGE), "Incorrect exception description: got \"" << e.what() << "\", expected: \"" << MESSAGE << "\""); \ + UNIT_ASSERT_C(e.AsStrBuf().Contains(MESSAGE), "Incorrect exception description: got \"" << e.what() << "\", expected: \"" << MESSAGE << "\""); \ } catch (...) { \ UNIT_ASSERT_C(false, "THashMap::at(\"" << KEY << "\") should throw yexception"); \ } \ @@ -1132,14 +1132,14 @@ void THashTest::TestAt() { TEST_AT_THROWN_EXCEPTION(TString, TString, TStringBuf, "111", "111"); TEST_AT_THROWN_EXCEPTION(TString, TString, const TStringBuf, "111", "111"); TEST_AT_THROWN_EXCEPTION(TStringBuf, TStringBuf, const char*, "111", "111"); - TEST_AT_THROWN_EXCEPTION(int, int, short, 11, "11"); - TEST_AT_THROWN_EXCEPTION(int, int, int, -1, "-1"); - TEST_AT_THROWN_EXCEPTION(int, int, long, 111, "111"); - TEST_AT_THROWN_EXCEPTION(int, int, long long, -1000000000000ll, "-1000000000000"); - TEST_AT_THROWN_EXCEPTION(int, int, unsigned short, 11, "11"); - TEST_AT_THROWN_EXCEPTION(int, int, unsigned int, 2, "2"); - TEST_AT_THROWN_EXCEPTION(int, int, unsigned long, 131, "131"); - TEST_AT_THROWN_EXCEPTION(int, int, unsigned long long, 1000000000000ll, "1000000000000"); + TEST_AT_THROWN_EXCEPTION(int, int, short, 11, "11"); + TEST_AT_THROWN_EXCEPTION(int, int, int, -1, "-1"); + TEST_AT_THROWN_EXCEPTION(int, int, long, 111, "111"); + TEST_AT_THROWN_EXCEPTION(int, int, long long, -1000000000000ll, "-1000000000000"); + TEST_AT_THROWN_EXCEPTION(int, int, unsigned short, 11, "11"); + TEST_AT_THROWN_EXCEPTION(int, int, unsigned int, 2, "2"); + TEST_AT_THROWN_EXCEPTION(int, int, unsigned long, 131, "131"); + TEST_AT_THROWN_EXCEPTION(int, int, unsigned long long, 1000000000000ll, "1000000000000"); char key[] = {11, 12, 0, 1, 2, 11, 0}; TEST_AT_THROWN_EXCEPTION(TString, TString, char*, key, "\\x0B\\x0C"); diff --git a/util/generic/is_in_ut.cpp b/util/generic/is_in_ut.cpp index c668bce807..2cb9d7c6c4 100644 --- a/util/generic/is_in_ut.cpp +++ b/util/generic/is_in_ut.cpp @@ -72,19 +72,19 @@ Y_UNIT_TEST_SUITE(TIsIn) { } Y_UNIT_TEST(IsInInitListTest) { - const char* abc = "abc"; - const char* def = "def"; - + const char* abc = "abc"; + const char* def = "def"; + UNIT_ASSERT(IsIn({6, 2, 12}, 6)); UNIT_ASSERT(IsIn({6, 2, 12}, 2)); UNIT_ASSERT(!IsIn({6, 2, 12}, 7)); UNIT_ASSERT(IsIn({6}, 6)); UNIT_ASSERT(!IsIn({6}, 7)); - UNIT_ASSERT(!IsIn(std::initializer_list<int>(), 6)); + UNIT_ASSERT(!IsIn(std::initializer_list<int>(), 6)); UNIT_ASSERT(IsIn({TStringBuf("abc"), TStringBuf("def")}, TStringBuf("abc"))); UNIT_ASSERT(IsIn({TStringBuf("abc"), TStringBuf("def")}, TStringBuf("def"))); UNIT_ASSERT(IsIn({"abc", "def"}, TStringBuf("def"))); - UNIT_ASSERT(IsIn({abc, def}, def)); // direct pointer comparison + UNIT_ASSERT(IsIn({abc, def}, def)); // direct pointer comparison UNIT_ASSERT(!IsIn({TStringBuf("abc"), TStringBuf("def")}, TStringBuf("ghi"))); UNIT_ASSERT(!IsIn({"abc", "def"}, TStringBuf("ghi"))); UNIT_ASSERT(!IsIn({"abc", "def"}, TString("ghi"))); diff --git a/util/generic/iterator.h b/util/generic/iterator.h index 19e9d20976..0d5587691c 100644 --- a/util/generic/iterator.h +++ b/util/generic/iterator.h @@ -30,42 +30,42 @@ namespace NStlIterator { }; } // namespace NStlIterator -/** - * Range adaptor that turns a derived class with a Java-style iteration - * interface into an STL range. - * - * Derived class is expected to define: - * \code - * TSomething* Next(); - * \endcode - * - * `Next()` returning `nullptr` signals end of range. Note that you can also use - * pointer-like types instead of actual pointers (e.g. `TAtomicSharedPtr`). - * - * Since iteration state is stored inside the derived class, the resulting range - * is an input range (works for single pass algorithms only). Technically speaking, - * if you're returning a non-const pointer from `Next`, it can also work as an output range. - * - * Example usage: - * \code - * class TSquaresGenerator: public TInputRangeAdaptor<TSquaresGenerator> { - * public: - * const double* Next() { - * Current_ = State_ * State_; - * State_ += 1.0; - * // Never return nullptr => we have infinite range! - * return &Current_; - * } - * - * private: - * double State_ = 0.0; - * double Current_ = 0.0; - * } - * \endcode - */ +/** + * Range adaptor that turns a derived class with a Java-style iteration + * interface into an STL range. + * + * Derived class is expected to define: + * \code + * TSomething* Next(); + * \endcode + * + * `Next()` returning `nullptr` signals end of range. Note that you can also use + * pointer-like types instead of actual pointers (e.g. `TAtomicSharedPtr`). + * + * Since iteration state is stored inside the derived class, the resulting range + * is an input range (works for single pass algorithms only). Technically speaking, + * if you're returning a non-const pointer from `Next`, it can also work as an output range. + * + * Example usage: + * \code + * class TSquaresGenerator: public TInputRangeAdaptor<TSquaresGenerator> { + * public: + * const double* Next() { + * Current_ = State_ * State_; + * State_ += 1.0; + * // Never return nullptr => we have infinite range! + * return &Current_; + * } + * + * private: + * double State_ = 0.0; + * double Current_ = 0.0; + * } + * \endcode + */ template <class TSlave> -class TInputRangeAdaptor { -public: // TODO: private +class TInputRangeAdaptor { +public: // TODO: private class TIterator { public: static constexpr bool IsNoexceptNext = noexcept(std::declval<TSlave>().Next()); @@ -74,7 +74,7 @@ public: // TODO: private using pointer = decltype(std::declval<TSlave>().Next()); using reference = decltype(*std::declval<TSlave>().Next()); using value_type = std::remove_cv_t<std::remove_reference_t<reference>>; - using iterator_category = std::input_iterator_tag; + using iterator_category = std::input_iterator_tag; inline TIterator() noexcept : Slave_(nullptr) @@ -96,11 +96,11 @@ public: // TODO: private return !(*this == it); } - inline pointer operator->() const noexcept { + inline pointer operator->() const noexcept { return Cur_; } - inline reference operator*() const noexcept { + inline reference operator*() const noexcept { return *Cur_; } @@ -128,12 +128,12 @@ public: } }; -/** - * Transform given reverse iterator into forward iterator pointing to the same element. +/** + * Transform given reverse iterator into forward iterator pointing to the same element. * - * @see http://stackoverflow.com/a/1830240 + * @see http://stackoverflow.com/a/1830240 */ template <class TIterator> -auto ToForwardIterator(TIterator iter) { +auto ToForwardIterator(TIterator iter) { return std::next(iter).base(); } diff --git a/util/generic/iterator_range.h b/util/generic/iterator_range.h index 9f4d02da29..1011553e37 100644 --- a/util/generic/iterator_range.h +++ b/util/generic/iterator_range.h @@ -1,10 +1,10 @@ -#pragma once - +#pragma once + #include <util/system/yassert.h> -#include <iterator> -#include <utility> - +#include <iterator> +#include <utility> + template <typename TBegin, typename TEnd = TBegin> struct TIteratorRange { using TElement = std::remove_reference_t<decltype(*std::declval<TBegin>())>; @@ -40,35 +40,35 @@ private: template <class TIterator> class TIteratorRange<TIterator, TIterator> { -public: +public: using iterator = TIterator; using const_iterator = TIterator; using value_type = typename std::iterator_traits<iterator>::value_type; using reference = typename std::iterator_traits<iterator>::reference; using const_reference = typename std::iterator_traits<const_iterator>::reference; using difference_type = typename std::iterator_traits<iterator>::difference_type; - using size_type = std::size_t; - + using size_type = std::size_t; + TIteratorRange() : Begin_() , End_() { } - + TIteratorRange(TIterator begin, TIterator end) - : Begin_(begin) - , End_(end) + : Begin_(begin) + , End_(end) { } - + TIterator begin() const { - return Begin_; - } - + return Begin_; + } + TIterator end() const { - return End_; - } - + return End_; + } + Y_PURE_FUNCTION bool empty() const { return Begin_ == End_; } @@ -83,20 +83,20 @@ public: return *(Begin_ + at); } -private: +private: TIterator Begin_; TIterator End_; -}; - +}; + template <class TIterator> TIteratorRange<TIterator> MakeIteratorRange(TIterator begin, TIterator end) { return TIteratorRange<TIterator>(begin, end); -} - +} + template <class TIterator> TIteratorRange<TIterator> MakeIteratorRange(const std::pair<TIterator, TIterator>& range) { return TIteratorRange<TIterator>(range.first, range.second); -} +} template <class TBegin, class TEnd> TIteratorRange<TBegin, TEnd> MakeIteratorRange(TBegin begin, TEnd end) { diff --git a/util/generic/list.h b/util/generic/list.h index 7b0b8ffc72..56d097af80 100644 --- a/util/generic/list.h +++ b/util/generic/list.h @@ -1,17 +1,17 @@ #pragma once -#include "fwd.h" - +#include "fwd.h" + #include <util/memory/alloc.h> #include <initializer_list> #include <list> -#include <memory> +#include <memory> #include <utility> template <class T, class A> class TList: public std::list<T, TReboundAllocator<A, T>> { - using TBase = std::list<T, TReboundAllocator<A, T>>; + using TBase = std::list<T, TReboundAllocator<A, T>>; public: using TBase::TBase; diff --git a/util/generic/map.h b/util/generic/map.h index b5001b56c0..0a4321383b 100644 --- a/util/generic/map.h +++ b/util/generic/map.h @@ -1,15 +1,15 @@ #pragma once -#include "fwd.h" +#include "fwd.h" #include "mapfindptr.h" -#include <util/str_stl.h> +#include <util/str_stl.h> #include <util/memory/alloc.h> - + #include <utility> #include <initializer_list> #include <map> -#include <memory> +#include <memory> template <class K, class V, class Less, class A> class TMap: public std::map<K, V, Less, TReboundAllocator<A, std::pair<const K, V>>>, public TMapOps<TMap<K, V, Less, A>> { diff --git a/util/generic/mapfindptr.h b/util/generic/mapfindptr.h index bc10cac60f..b44585af48 100644 --- a/util/generic/mapfindptr.h +++ b/util/generic/mapfindptr.h @@ -1,7 +1,7 @@ #pragma once -#include <type_traits> - +#include <type_traits> + /** MapFindPtr usage: if (T* value = MapFindPtr(myMap, someKey) { @@ -11,50 +11,50 @@ if (T* value = MapFindPtr(myMap, someKey) { */ template <class Map, class K> -inline auto MapFindPtr(Map& map, const K& key) { +inline auto MapFindPtr(Map& map, const K& key) { auto i = map.find(key); return (i == map.end() ? nullptr : &i->second); } template <class Map, class K> -inline auto MapFindPtr(const Map& map, const K& key) { +inline auto MapFindPtr(const Map& map, const K& key) { auto i = map.find(key); return (i == map.end() ? nullptr : &i->second); } /** helper for THashMap/TMap */ -template <class Derived> +template <class Derived> struct TMapOps { template <class K> - inline auto FindPtr(const K& key) { + inline auto FindPtr(const K& key) { return MapFindPtr(static_cast<Derived&>(*this), key); } template <class K> - inline auto FindPtr(const K& key) const { + inline auto FindPtr(const K& key) const { return MapFindPtr(static_cast<const Derived&>(*this), key); } - template <class K, class DefaultValue> - inline auto Value(const K& key, const DefaultValue& defaultValue) const -> std::remove_reference_t<decltype(*this->FindPtr(key))> { - if (auto found = FindPtr(key)) { + template <class K, class DefaultValue> + inline auto Value(const K& key, const DefaultValue& defaultValue) const -> std::remove_reference_t<decltype(*this->FindPtr(key))> { + if (auto found = FindPtr(key)) { return *found; } - return defaultValue; + return defaultValue; } - - template <class K, class V> - inline const V& ValueRef(const K& key, V& defaultValue) const { - static_assert(std::is_same<std::remove_const_t<V>, typename Derived::mapped_type>::value, "Passed default value must have the same type as the underlying map's mapped_type."); - - if (auto found = FindPtr(key)) { - return *found; - } - return defaultValue; - } - - template <class K, class V> - inline const V& ValueRef(const K& key, V&& defaultValue) const = delete; + + template <class K, class V> + inline const V& ValueRef(const K& key, V& defaultValue) const { + static_assert(std::is_same<std::remove_const_t<V>, typename Derived::mapped_type>::value, "Passed default value must have the same type as the underlying map's mapped_type."); + + if (auto found = FindPtr(key)) { + return *found; + } + return defaultValue; + } + + template <class K, class V> + inline const V& ValueRef(const K& key, V&& defaultValue) const = delete; }; diff --git a/util/generic/mapfindptr_ut.cpp b/util/generic/mapfindptr_ut.cpp index 613da7a96b..75443e8b62 100644 --- a/util/generic/mapfindptr_ut.cpp +++ b/util/generic/mapfindptr_ut.cpp @@ -14,7 +14,7 @@ Y_UNIT_TEST_SUITE(TMapFindPtrTest) { TTestMap a; a[42] = "cat"; - UNIT_ASSERT(a.FindPtr(42)); + UNIT_ASSERT(a.FindPtr(42)); UNIT_ASSERT_EQUAL(*a.FindPtr(42), "cat"); UNIT_ASSERT_EQUAL(a.FindPtr(0), nullptr); @@ -22,7 +22,7 @@ Y_UNIT_TEST_SUITE(TMapFindPtrTest) { if (TString* p = a.FindPtr(42)) { *p = "dog"; } - UNIT_ASSERT(a.FindPtr(42)); + UNIT_ASSERT(a.FindPtr(42)); UNIT_ASSERT_EQUAL(*a.FindPtr(42), "dog"); //test const-overloaded functions too @@ -42,26 +42,26 @@ Y_UNIT_TEST_SUITE(TMapFindPtrTest) { UNIT_ASSERT(m.FindPtr(TStringBuf("x"))); UNIT_ASSERT_EQUAL(*m.FindPtr(TStringBuf("x")), 2); } - + Y_UNIT_TEST(TestValue) { - TTestMap a; - - a[1] = "lol"; - - UNIT_ASSERT_VALUES_EQUAL(a.Value(1, "123"), "lol"); - UNIT_ASSERT_VALUES_EQUAL(a.Value(2, "123"), "123"); - } - + TTestMap a; + + a[1] = "lol"; + + UNIT_ASSERT_VALUES_EQUAL(a.Value(1, "123"), "lol"); + UNIT_ASSERT_VALUES_EQUAL(a.Value(2, "123"), "123"); + } + Y_UNIT_TEST(TestValueRef) { - TTestMap a; - - a[1] = "lol"; - + TTestMap a; + + a[1] = "lol"; + const TString str123 = "123"; TString str1234 = "1234"; - - UNIT_ASSERT_VALUES_EQUAL(a.ValueRef(1, str123), "lol"); - UNIT_ASSERT_VALUES_EQUAL(a.ValueRef(2, str123), "123"); - UNIT_ASSERT_VALUES_EQUAL(a.ValueRef(3, str1234), "1234"); - } -} + + UNIT_ASSERT_VALUES_EQUAL(a.ValueRef(1, str123), "lol"); + UNIT_ASSERT_VALUES_EQUAL(a.ValueRef(2, str123), "123"); + UNIT_ASSERT_VALUES_EQUAL(a.ValueRef(3, str1234), "1234"); + } +} diff --git a/util/generic/mem_copy_ut.cpp b/util/generic/mem_copy_ut.cpp index 8b55a11cf6..9d69ec108f 100644 --- a/util/generic/mem_copy_ut.cpp +++ b/util/generic/mem_copy_ut.cpp @@ -74,10 +74,10 @@ Y_UNIT_TEST_SUITE(TestMemCopy) { template <class T> inline void FillX(T* b, T* e) { - int tmp = 0; + int tmp = 0; while (b != e) { - (b++)->X = ++tmp; + (b++)->X = ++tmp; } } @@ -105,9 +105,9 @@ Y_UNIT_TEST_SUITE(TestMemCopy) { } Y_UNIT_TEST(TestEmpty) { - char* tmp = nullptr; + char* tmp = nullptr; - UNIT_ASSERT(MemCopy(tmp, tmp, 0) == nullptr); - UNIT_ASSERT(MemMove(tmp, tmp, 0) == nullptr); + UNIT_ASSERT(MemCopy(tmp, tmp, 0) == nullptr); + UNIT_ASSERT(MemMove(tmp, tmp, 0) == nullptr); } } diff --git a/util/generic/noncopyable.h b/util/generic/noncopyable.h index c007934133..655436a70d 100644 --- a/util/generic/noncopyable.h +++ b/util/generic/noncopyable.h @@ -1,20 +1,20 @@ #pragma once -/** - * @class TNonCopyable +/** + * @class TNonCopyable * - * Inherit your class from `TNonCopyable` if you want to make it noncopyable. + * Inherit your class from `TNonCopyable` if you want to make it noncopyable. * - * Example usage: - * @code - * class Foo: private TNonCopyable { - * // ... - * }; - * @endcode + * Example usage: + * @code + * class Foo: private TNonCopyable { + * // ... + * }; + * @endcode */ namespace NNonCopyable { // protection from unintended ADL - struct TNonCopyable { + struct TNonCopyable { TNonCopyable(const TNonCopyable&) = delete; TNonCopyable& operator=(const TNonCopyable&) = delete; @@ -22,7 +22,7 @@ namespace NNonCopyable { // protection from unintended ADL ~TNonCopyable() = default; }; - struct TMoveOnly { + struct TMoveOnly { TMoveOnly(TMoveOnly&&) noexcept = default; TMoveOnly& operator=(TMoveOnly&&) noexcept = default; diff --git a/util/generic/object_counter.h b/util/generic/object_counter.h index 5257afa2e6..9b0710e971 100644 --- a/util/generic/object_counter.h +++ b/util/generic/object_counter.h @@ -2,20 +2,20 @@ #include <util/system/atomic.h> -/** - * Simple thread-safe per-class counter that can be used to make sure you don't - * have any leaks in your code, or for statistical purposes. - * - * Example usage: - * \code - * class TMyClass: public TObjectCounter<TMyClass> { - * // ... - * }; - * - * // In your code: - * Cerr << "TMyClass instances in use: " << TMyClass::ObjectCount() << Endl; - * \endcode - */ +/** + * Simple thread-safe per-class counter that can be used to make sure you don't + * have any leaks in your code, or for statistical purposes. + * + * Example usage: + * \code + * class TMyClass: public TObjectCounter<TMyClass> { + * // ... + * }; + * + * // In your code: + * Cerr << "TMyClass instances in use: " << TMyClass::ObjectCount() << Endl; + * \endcode + */ template <class T> class TObjectCounter { public: @@ -35,12 +35,12 @@ public: return AtomicGet(Count_); } - /** - * Resets object count. Mainly for tests, as you don't want to do this in - * your code and then end up with negative counts. - * - * \returns Current object count. - */ + /** + * Resets object count. Mainly for tests, as you don't want to do this in + * your code and then end up with negative counts. + * + * \returns Current object count. + */ static inline long ResetObjectCount() noexcept { return AtomicSwap(&Count_, 0); } diff --git a/util/generic/ptr.h b/util/generic/ptr.h index 19db0e3ec5..8483d382b6 100644 --- a/util/generic/ptr.h +++ b/util/generic/ptr.h @@ -1,6 +1,6 @@ #pragma once -#include "fwd.h" +#include "fwd.h" #include "utility.h" #include "intrlist.h" #include "refcount.h" @@ -160,7 +160,7 @@ template <class Base> class TPointerBase<Base, void>: public TPointerCommon<Base, void> { }; -template <class T, class D> +template <class T, class D> class TAutoPtr: public TPointerBase<TAutoPtr<T, D>, T> { public: inline TAutoPtr(T* t = nullptr) noexcept @@ -197,9 +197,9 @@ public: } inline void Reset() noexcept { - Destroy(); - } - + Destroy(); + } + inline void Destroy() noexcept { Reset(nullptr); } @@ -229,7 +229,7 @@ private: mutable T* T_; }; -template <class T, class D> +template <class T, class D> class THolder: public TPointerBase<THolder<T, D>, T> { public: constexpr THolder() noexcept @@ -296,9 +296,9 @@ public: } inline void Reset() noexcept { - Destroy(); - } - + Destroy(); + } + inline void Swap(THolder& r) noexcept { DoSwap(T_, r.T_); } @@ -355,7 +355,7 @@ template <typename T, typename... Args> * and we get methods Ref() && UnRef() with * proper destruction of last UnRef() */ -template <class T, class C, class D> +template <class T, class C, class D> class TRefCounted { public: inline TRefCounted(long initval = 0) noexcept @@ -551,9 +551,9 @@ public: } inline void Reset() noexcept { - Drop(); - } - + Drop(); + } + inline T* Get() const noexcept { return T_; } @@ -671,9 +671,9 @@ public: } inline void Reset() noexcept { - Drop(); - } - + Drop(); + } + inline const T* Get() const noexcept { return T_; } @@ -788,7 +788,7 @@ template <typename T, class Ops = TDefaultIntrusivePtrOps<T>, typename... Args> return new T{std::forward<Args>(args)...}; } -template <class T, class C, class D> +template <class T, class C, class D> class TSharedPtr: public TPointerBase<TSharedPtr<T, C, D>, T> { template <class TT, class CC, class DD> friend class TSharedPtr; @@ -870,9 +870,9 @@ public: } inline void Reset() noexcept { - Drop(); - } - + Drop(); + } + inline void Drop() noexcept { TSharedPtr().Swap(*this); } @@ -982,7 +982,7 @@ public: } }; -template <class T, class C, class D> +template <class T, class C, class D> class TCopyPtr: public TPointerBase<TCopyPtr<T, C, D>, T> { public: inline TCopyPtr(T* t = nullptr) noexcept @@ -1023,9 +1023,9 @@ public: } inline void Reset() noexcept { - Destroy(); - } - + Destroy(); + } + inline void Destroy() noexcept { Reset(nullptr); } @@ -1098,10 +1098,10 @@ public: p.Swap(*this); } - inline void Reset() { - T_.Reset(); - } - + inline void Reset() { + T_.Reset(); + } + #ifdef __cpp_impl_three_way_comparison template <class Other> inline bool operator==(const Other& p) const noexcept { diff --git a/util/generic/queue.h b/util/generic/queue.h index f5959f68f2..992645e004 100644 --- a/util/generic/queue.h +++ b/util/generic/queue.h @@ -1,6 +1,6 @@ #pragma once -#include "fwd.h" +#include "fwd.h" #include "deque.h" #include "vector.h" #include "utility.h" @@ -9,7 +9,7 @@ #include <queue> -template <class T, class S> +template <class T, class S> class TQueue: public std::queue<T, S> { using TBase = std::queue<T, S>; @@ -33,7 +33,7 @@ public: } }; -template <class T, class S, class C> +template <class T, class S, class C> class TPriorityQueue: public std::priority_queue<T, S, C> { using TBase = std::priority_queue<T, S, C>; diff --git a/util/generic/set.h b/util/generic/set.h index 4c437ca26f..43325e7bd5 100644 --- a/util/generic/set.h +++ b/util/generic/set.h @@ -1,18 +1,18 @@ #pragma once -#include "fwd.h" - -#include <util/str_stl.h> +#include "fwd.h" + +#include <util/str_stl.h> #include <util/memory/alloc.h> #include <initializer_list> -#include <memory> +#include <memory> #include <set> template <class K, class L, class A> class TSet: public std::set<K, L, TReboundAllocator<A, K>> { public: - using TBase = std::set<K, L, TReboundAllocator<A, K>>; + using TBase = std::set<K, L, TReboundAllocator<A, K>>; using TBase::TBase; inline explicit operator bool() const noexcept { @@ -25,10 +25,10 @@ public: } }; -template <class K, class L, class A> +template <class K, class L, class A> class TMultiSet: public std::multiset<K, L, TReboundAllocator<A, K>> { public: - using TBase = std::multiset<K, L, TReboundAllocator<A, K>>; + using TBase = std::multiset<K, L, TReboundAllocator<A, K>>; using TBase::TBase; inline explicit operator bool() const noexcept { diff --git a/util/generic/stack.h b/util/generic/stack.h index dbcbf2b5c9..6bfa5f90a4 100644 --- a/util/generic/stack.h +++ b/util/generic/stack.h @@ -1,11 +1,11 @@ #pragma once -#include "fwd.h" +#include "fwd.h" #include "deque.h" #include <stack> -template <class T, class S> +template <class T, class S> class TStack: public std::stack<T, S> { using TBase = std::stack<T, S>; diff --git a/util/generic/store_policy.h b/util/generic/store_policy.h index 148821c70c..d8a4b530ae 100644 --- a/util/generic/store_policy.h +++ b/util/generic/store_policy.h @@ -71,10 +71,10 @@ struct TRefPolicy { }; /** - * Storage class that can be handy for implementing proxies / adaptors that can - * accept both lvalues and rvalues. In the latter case it's often required to - * extend the lifetime of the passed rvalue, and the only option is to store it - * in your proxy / adaptor. + * Storage class that can be handy for implementing proxies / adaptors that can + * accept both lvalues and rvalues. In the latter case it's often required to + * extend the lifetime of the passed rvalue, and the only option is to store it + * in your proxy / adaptor. * * Example usage: * \code @@ -87,28 +87,28 @@ struct TRefPolicy { * template<class T> * TProxy<T> MakeProxy(T&& value) { * // Rvalues are automagically moved-from, and stored inside the proxy. - * return {std::forward<T>(value)}; + * return {std::forward<T>(value)}; * } * \endcode * * Look at `Reversed` in `adaptor.h` for real example. */ -template <class T, bool IsReference = std::is_reference<T>::value> +template <class T, bool IsReference = std::is_reference<T>::value> struct TAutoEmbedOrPtrPolicy: TPtrPolicy<std::remove_reference_t<T>> { - using TBase = TPtrPolicy<std::remove_reference_t<T>>; + using TBase = TPtrPolicy<std::remove_reference_t<T>>; - TAutoEmbedOrPtrPolicy(T& reference) - : TBase(&reference) + TAutoEmbedOrPtrPolicy(T& reference) + : TBase(&reference) { } }; -template <class T> +template <class T> struct TAutoEmbedOrPtrPolicy<T, false>: TEmbedPolicy<T> { - using TBase = TEmbedPolicy<T>; + using TBase = TEmbedPolicy<T>; - TAutoEmbedOrPtrPolicy(T&& object) - : TBase(std::move(object)) + TAutoEmbedOrPtrPolicy(T&& object) + : TBase(std::move(object)) { } }; diff --git a/util/generic/store_policy_ut.cpp b/util/generic/store_policy_ut.cpp index c9722203aa..5d78823bac 100644 --- a/util/generic/store_policy_ut.cpp +++ b/util/generic/store_policy_ut.cpp @@ -46,7 +46,7 @@ Y_UNIT_TEST_SUITE(StorePolicy) { static_assert(std::is_const<decltype(a)>::value); FunctionTakingRefDefaultIsObject(a, [](auto& holder) { - static_assert(std::is_const<std::remove_reference_t<decltype(*holder.Ptr())>>::value); + static_assert(std::is_const<std::remove_reference_t<decltype(*holder.Ptr())>>::value); UNIT_ASSERT_VALUES_EQUAL(holder.Ptr()->size(), 3); }); } @@ -54,7 +54,7 @@ Y_UNIT_TEST_SUITE(StorePolicy) { template <typename T, typename TFunc> void FunctionTakingObjectDefaultObject(T&& a, TFunc func) { - TAutoEmbedOrPtrPolicy<T> objectHolder(std::forward<T>(a)); + TAutoEmbedOrPtrPolicy<T> objectHolder(std::forward<T>(a)); func(objectHolder); } diff --git a/util/generic/strbase.h b/util/generic/strbase.h index ab39fc7537..263ac52bb2 100644 --- a/util/generic/strbase.h +++ b/util/generic/strbase.h @@ -124,9 +124,9 @@ public: } /** - * @param Pointer to character inside the string, or nullptr. - * @return Offset from string beginning (in chars), or npos on nullptr. - */ + * @param Pointer to character inside the string, or nullptr. + * @return Offset from string beginning (in chars), or npos on nullptr. + */ inline size_t off(const TCharType* ret) const noexcept { return ret ? (size_t)(ret - Ptr()) : npos; } @@ -168,7 +168,7 @@ public: } inline TCharType back() const noexcept { - Y_ASSERT(!this->empty()); + Y_ASSERT(!this->empty()); return Ptr()[Len() - 1]; } @@ -177,10 +177,10 @@ public: return Ptr()[0]; } - constexpr const TCharType* data() const noexcept { - return Ptr(); - } - + constexpr const TCharType* data() const noexcept { + return Ptr(); + } + constexpr inline size_t size() const noexcept { return Len(); } @@ -253,10 +253,10 @@ public: return compare(LegacySubString(*this, p, n), LegacySubString(t, 0, n1)); } - inline int compare(const TCharType* p, size_t len) const noexcept { + inline int compare(const TCharType* p, size_t len) const noexcept { return compare(*this, TStringView(p, len)); - } - + } + static bool equal(const TSelf& s1, const TSelf& s2) noexcept { return s1.AsStringView() == s2.AsStringView(); } @@ -441,13 +441,13 @@ public: inline TCharType operator[](size_t pos) const noexcept { Y_ASSERT(pos < this->size()); - return Ptr()[pos]; + return Ptr()[pos]; } //~~~~Search~~~~ - /** - * @return Position of the substring inside this string, or `npos` if not found. - */ + /** + * @return Position of the substring inside this string, or `npos` if not found. + */ inline size_t find(const TStringView s, size_t pos = 0) const noexcept { return find(s.data(), pos, s.size()); } @@ -476,9 +476,9 @@ public: } //~~~~Contains~~~~ - /** - * @returns Whether this string contains the provided substring. - */ + /** + * @returns Whether this string contains the provided substring. + */ inline bool Contains(const TStringView s, size_t pos = 0) const noexcept { return !s.length() || find(s, pos) != npos; } @@ -493,33 +493,33 @@ public: //~~~~Character Set Search~~~ inline size_t find_first_of(TCharType c) const noexcept { - return find_first_of(c, 0); + return find_first_of(c, 0); } inline size_t find_first_of(TCharType c, size_t pos) const noexcept { - return find(c, pos); - } - + return find(c, pos); + } + inline size_t find_first_of(const TStringView set) const noexcept { - return find_first_of(set, 0); - } - + return find_first_of(set, 0); + } + inline size_t find_first_of(const TStringView set, size_t pos) const noexcept { return AsStringView().find_first_of(set.data(), pos, set.size()); } inline size_t find_first_not_of(TCharType c) const noexcept { - return find_first_not_of(c, 0); - } - + return find_first_not_of(c, 0); + } + inline size_t find_first_not_of(TCharType c, size_t pos) const noexcept { return find_first_not_of(TStringView(&c, 1), pos); - } - + } + inline size_t find_first_not_of(const TStringView set) const noexcept { - return find_first_not_of(set, 0); - } - + return find_first_not_of(set, 0); + } + inline size_t find_first_not_of(const TStringView set, size_t pos) const noexcept { return AsStringView().find_first_not_of(set.data(), pos, set.size()); } diff --git a/util/generic/strbuf.h b/util/generic/strbuf.h index 70b9360d58..7cbc94cc38 100644 --- a/util/generic/strbuf.h +++ b/util/generic/strbuf.h @@ -1,6 +1,6 @@ #pragma once -#include "fwd.h" +#include "fwd.h" #include "strbase.h" #include "utility.h" #include "typetraits.h" @@ -13,7 +13,7 @@ template <typename TCharType, typename TTraits> class TBasicStringBuf: public std::basic_string_view<TCharType>, public TStringBase<TBasicStringBuf<TCharType, TTraits>, TCharType, TTraits> { private: - using TdSelf = TBasicStringBuf; + using TdSelf = TBasicStringBuf; using TBase = TStringBase<TdSelf, TCharType, TTraits>; using TStringView = std::basic_string_view<TCharType>; @@ -152,7 +152,7 @@ public: } inline TBasicStringBuf(const TBasicStringBuf& src, size_t pos) noexcept - : TBasicStringBuf(src, pos, TBase::npos) + : TBasicStringBuf(src, pos, TBase::npos) { } diff --git a/util/generic/string.h b/util/generic/string.h index 8cd8aa6917..210d1b6d43 100644 --- a/util/generic/string.h +++ b/util/generic/string.h @@ -13,7 +13,7 @@ #include "ptr.h" #include "utility.h" #include "bitops.h" -#include "explicit_type.h" +#include "explicit_type.h" #include "reserve.h" #include "singleton.h" #include "strbase.h" @@ -158,7 +158,7 @@ private: template <typename TCharType, typename TTraits> class TBasicString: public TStringBase<TBasicString<TCharType, TTraits>, TCharType, TTraits> { public: - // TODO: Move to private section + // TODO: Move to private section using TBase = TStringBase<TBasicString, TCharType, TTraits>; using TStringType = std::basic_string<TCharType, TTraits>; #ifdef TSTRING_IS_STD_STRING @@ -169,7 +169,7 @@ public: using TStorage = TIntrusivePtr<TStdStr, TStringPtrOps<TStdStr>>; using reference = TBasicCharRef<TBasicString>; #endif - using char_type = TCharType; // TODO: DROP + using char_type = TCharType; // TODO: DROP using value_type = TCharType; using traits_type = TTraits; @@ -179,15 +179,15 @@ public: using typename TBase::const_reference; using typename TBase::const_reverse_iterator; - struct TUninitialized { + struct TUninitialized { explicit TUninitialized(size_t size) : Size(size) { } - - size_t Size; - }; - + + size_t Size; + }; + static size_t max_size() noexcept { static size_t res = TStringType().max_size(); @@ -217,11 +217,11 @@ protected: return *S_; } - /** - * Makes a distinct copy of this string. `IsDetached()` is always true after this call. - * - * @throw std::length_error - */ + /** + * Makes a distinct copy of this string. `IsDetached()` is always true after this call. + * + * @throw std::length_error + */ void Clone() { Construct(StdStr()).Swap(S_); } @@ -253,7 +253,7 @@ public: inline const_reference operator[](size_t pos) const noexcept { Y_ASSERT(pos <= length()); - return this->data()[pos]; + return this->data()[pos]; } inline reference operator[](size_t pos) noexcept { @@ -269,8 +269,8 @@ public: using TBase::back; inline reference back() noexcept { - Y_ASSERT(!this->empty()); - + Y_ASSERT(!this->empty()); + #ifdef TSTRING_IS_STD_STRING return Storage_.back(); #else @@ -302,10 +302,10 @@ public: return ConstRef().data(); } - inline const TCharType* c_str() const noexcept { + inline const TCharType* c_str() const noexcept { return ConstRef().c_str(); - } - + } + // ~~~ STL compatible method to obtain data pointer ~~~ iterator begin() { return &*MutRef().begin(); @@ -344,19 +344,19 @@ public: #endif } - TCharType* Detach() { + TCharType* Detach() { #ifdef TSTRING_IS_STD_STRING return Storage_.data(); #else if (Y_UNLIKELY(!IsDetached())) { Clone(); - } - + } + return (TCharType*)S_->data(); #endif - } - - bool IsDetached() const { + } + + bool IsDetached() const { #ifdef TSTRING_IS_STD_STRING return true; #else @@ -371,7 +371,7 @@ public: return *this; } - // ~~~ Constructor ~~~ : FAMILY0(,TBasicString) + // ~~~ Constructor ~~~ : FAMILY0(,TBasicString) TBasicString() noexcept #ifndef TSTRING_IS_STD_STRING : S_(Construct()) @@ -410,7 +410,7 @@ public: } template <typename T, typename A> - explicit inline TBasicString(const std::basic_string<TCharType, T, A>& s) + explicit inline TBasicString(const std::basic_string<TCharType, T, A>& s) : TBasicString(s.data(), s.size()) { } @@ -457,7 +457,7 @@ public: } #ifdef TSTRING_IS_STD_STRING - explicit TBasicString(TExplicitType<TCharType> c) { + explicit TBasicString(TExplicitType<TCharType> c) { Storage_.push_back(c); } #else @@ -480,13 +480,13 @@ public: { } - /** - * Constructs an uninitialized string of size `uninitialized.Size`. The proper - * way to use this ctor is via `TBasicString::Uninitialized` factory function. - * - * @throw std::length_error - */ - TBasicString(TUninitialized uninitialized) { + /** + * Constructs an uninitialized string of size `uninitialized.Size`. The proper + * way to use this ctor is via `TBasicString::Uninitialized` factory function. + * + * @throw std::length_error + */ + TBasicString(TUninitialized uninitialized) { #if !defined(TSTRING_IS_STD_STRING) S_ = Construct(); #endif @@ -503,12 +503,12 @@ public: { } - template <typename Traits> + template <typename Traits> explicit inline TBasicString(const std::basic_string_view<TCharType, Traits>& s) : TBasicString(s.data(), s.size()) { - } - + } + /** * WARN: * Certain invocations of this method will result in link-time error. @@ -528,8 +528,8 @@ public: static TBasicString Uninitialized(size_t n) { return TBasicString(TUninitialized(n)); - } - + } + private: template <typename... R> static size_t SumLength(const TBasicStringBuf<TCharType, TTraits> s1, const R&... r) noexcept { @@ -565,7 +565,7 @@ public: #ifdef TSTRING_IS_STD_STRING Storage_.clear(); #else - if (IsDetached()) { + if (IsDetached()) { S_->clear(); return; @@ -584,7 +584,7 @@ public: return s; } - // ~~~ Assignment ~~~ : FAMILY0(TBasicString&, assign); + // ~~~ Assignment ~~~ : FAMILY0(TBasicString&, assign); TBasicString& assign(size_t size, TCharType ch) { ReserveAndResize(size); std::fill(begin(), vend(), ch); @@ -711,7 +711,7 @@ public: MutRef().reserve(len); } - // ~~~ Appending ~~~ : FAMILY0(TBasicString&, append); + // ~~~ Appending ~~~ : FAMILY0(TBasicString&, append); inline TBasicString& append(size_t count, TCharType ch) { MutRef().append(count, ch); @@ -1011,7 +1011,7 @@ public: return *this; #else - return insert(this->off(pos), b, e - b); + return insert(this->off(pos), b, e - b); #endif } @@ -1022,11 +1022,11 @@ public: } TBasicString& insert(const_iterator pos, size_t len, TCharType ch) { - return this->insert(this->off(pos), len, ch); + return this->insert(this->off(pos), len, ch); } TBasicString& insert(const_iterator pos, TCharType ch) { - return this->insert(pos, 1, ch); + return this->insert(pos, 1, ch); } TBasicString& insert(size_t pos, const TBasicStringBuf<TCharType, TTraits> s, size_t spos = 0, size_t sn = TBase::npos) { @@ -1125,10 +1125,10 @@ public: #endif } - /** - * @returns String suitable for debug printing (like Python's `repr()`). - * Format of the string is unspecified and may be changed over time. - */ + /** + * @returns String suitable for debug printing (like Python's `repr()`). + * Format of the string is unspecified and may be changed over time. + */ TBasicString Quote() const { extern TBasicString EscapeC(const TBasicString&); diff --git a/util/generic/string_ut.cpp b/util/generic/string_ut.cpp index ac82e9091d..2ec5963903 100644 --- a/util/generic/string_ut.cpp +++ b/util/generic/string_ut.cpp @@ -136,7 +136,7 @@ protected: s.reserve(128); UNIT_ASSERT(s.capacity() >= 128 && s.capacity() < 256 && s.data() != data); - UNIT_ASSERT(s.IsDetached()); + UNIT_ASSERT(s.IsDetached()); s.resize(64, 'x'); data = s.data(); @@ -145,7 +145,7 @@ protected: s.reserve(10); UNIT_ASSERT(s.capacity() >= 64 && s.capacity() < 128 && s.data() != data); - UNIT_ASSERT(s.IsDetached()); + UNIT_ASSERT(s.IsDetached()); #endif #endif } @@ -746,8 +746,8 @@ public: #endif UNIT_TEST(TestBack) UNIT_TEST(TestFront) - UNIT_TEST(TestIterators); - UNIT_TEST(TestReverseIterators); + UNIT_TEST(TestIterators); + UNIT_TEST(TestReverseIterators); UNIT_TEST(TestAppendUtf16) UNIT_TEST(TestFillingAssign) UNIT_TEST(TestStdStreamApi) @@ -809,8 +809,8 @@ public: UNIT_TEST(TestBack); UNIT_TEST(TestFront) UNIT_TEST(TestDecodingMethods); - UNIT_TEST(TestIterators); - UNIT_TEST(TestReverseIterators); + UNIT_TEST(TestIterators); + UNIT_TEST(TestReverseIterators); UNIT_TEST(TestStringLiterals); UNIT_TEST_SUITE_END(); @@ -934,8 +934,8 @@ public: UNIT_TEST(TestFront) UNIT_TEST(TestDecodingMethods); UNIT_TEST(TestDecodingMethodsMixedStr); - UNIT_TEST(TestIterators); - UNIT_TEST(TestReverseIterators); + UNIT_TEST(TestIterators); + UNIT_TEST(TestReverseIterators); UNIT_TEST(TestStringLiterals); UNIT_TEST_SUITE_END(); diff --git a/util/generic/string_ut.h b/util/generic/string_ut.h index 44bb10bdeb..0ed2c4e979 100644 --- a/util/generic/string_ut.h +++ b/util/generic/string_ut.h @@ -543,7 +543,7 @@ public: #ifndef TSTRING_IS_STD_STRING TStringType s3 = TStringType::Uninitialized(10); - UNIT_ASSERT(s3.size() == 10); + UNIT_ASSERT(s3.size() == 10); #endif TStringType s4(Data._0123456(), 1, 3); @@ -562,9 +562,9 @@ public: TStringType s8(s7, 1, 3); UNIT_ASSERT(s8 == Data._123()); - + TStringType s9(*Data._1()); - UNIT_ASSERT(s9 == Data._1()); + UNIT_ASSERT(s9 == Data._1()); TStringType s10(Reserve(100)); UNIT_ASSERT(s10.empty()); @@ -692,10 +692,10 @@ public: UNIT_ASSERT(s.find_first_of(Data._389()) == 3); UNIT_ASSERT(s.find_first_of(Data._389(), s.size()) == TStringType::npos); UNIT_ASSERT(s.find_first_not_of(Data._123()) == 0); - UNIT_ASSERT(s.find_first_of('6') == 6); - UNIT_ASSERT(s.find_first_of('1', 2) == 8); - UNIT_ASSERT(s.find_first_not_of('0') == 1); - UNIT_ASSERT(s.find_first_not_of('1', 1) == 2); + UNIT_ASSERT(s.find_first_of('6') == 6); + UNIT_ASSERT(s.find_first_of('1', 2) == 8); + UNIT_ASSERT(s.find_first_not_of('0') == 1); + UNIT_ASSERT(s.find_first_not_of('1', 1) == 2); const TStringType rs = Data._0123401234(); UNIT_ASSERT(rs.rfind(*Data._3()) == 8); @@ -1075,7 +1075,7 @@ public: UNIT_ASSERT_VALUES_EQUAL(str.front(), (ui8)'r'); } - void TestIterators() { + void TestIterators() { const char_type chars[] = {'f', 'o', 0}; TStringType str = chars; @@ -1113,7 +1113,7 @@ public: UNIT_ASSERT_VALUES_EQUAL(*citBegin, (ui8)'f'); } - void TestReverseIterators() { + void TestReverseIterators() { const char_type chars[] = {'f', 'o', 0}; TStringType str = chars; diff --git a/util/generic/typetraits.h b/util/generic/typetraits.h index d165bd1a06..ca0a56b276 100644 --- a/util/generic/typetraits.h +++ b/util/generic/typetraits.h @@ -7,7 +7,7 @@ #include <iterator> #include <type_traits> #include <stlfwd> - + #if _LIBCPP_STD_VER >= 17 template <bool B> using TBoolConstant = std::bool_constant<B>; diff --git a/util/generic/typetraits_ut.cpp b/util/generic/typetraits_ut.cpp index e7571c75ec..e373acc322 100644 --- a/util/generic/typetraits_ut.cpp +++ b/util/generic/typetraits_ut.cpp @@ -16,29 +16,29 @@ namespace { TNonPodClass() { } }; - - class TEmptyClass { + + class TEmptyClass { void operator()() const { } - }; - - class TAnotherEmptyClass { - }; - + }; + + class TAnotherEmptyClass { + }; + class TEmptyDerivedClass: public TEmptyClass { - }; - + }; + class TEmptyMultiDerivedClass: public TEmptyDerivedClass, public TAnotherEmptyClass { - /* Not empty under MSVC. - * MSVC's EBCO implementation can handle only one empty base class. */ - }; - + /* Not empty under MSVC. + * MSVC's EBCO implementation can handle only one empty base class. */ + }; + struct TNonEmptyClass { - TEmptyClass member; - }; - + TEmptyClass member; + }; + class TNonEmptyDerivedClass: public TNonEmptyClass { - }; + }; class TStdLayoutClass1: public TEmptyClass { public: @@ -80,10 +80,10 @@ namespace { Y_UNIT_TEST_SUITE(TTypeTraitsTest) { Y_UNIT_TEST(TestIsSame) { - UNIT_ASSERT((std::is_same<int, int>::value)); - UNIT_ASSERT(!(std::is_same<signed int, unsigned int>::value)); - } - + UNIT_ASSERT((std::is_same<int, int>::value)); + UNIT_ASSERT(!(std::is_same<signed int, unsigned int>::value)); + } + Y_UNIT_TEST(TestRemoveReference) { ASSERT_SAME_TYPE(std::remove_reference_t<int>, int); ASSERT_SAME_TYPE(std::remove_reference_t<const int>, const int); @@ -137,7 +137,7 @@ Y_UNIT_TEST_SUITE(TTypeTraitsTest) { a = std::is_same<typename TTypeTraits<const volatile T>::TFuncParam, const volatile T>::value; UNIT_ASSERT(a); } - + template <class T> inline void TestUnsignedIntType() { UNIT_ASSERT(std::is_unsigned<T>::value); @@ -174,28 +174,28 @@ Y_UNIT_TEST_SUITE(TTypeTraitsTest) { } Y_UNIT_TEST(TestUnsignedChar) { - TestArithmeticType<unsigned char>(); + TestArithmeticType<unsigned char>(); TestUnsignedIntType<unsigned char>(); - } - + } + Y_UNIT_TEST(TestSizeT) { - TestArithmeticType<size_t>(); + TestArithmeticType<size_t>(); TestUnsignedIntType<size_t>(); - } - + } + Y_UNIT_TEST(TestInt) { TestArithmeticType<int>(); TestSignedIntType<int>(); } Y_UNIT_TEST(TestDouble) { - TestArithmeticType<double>(); - } - + TestArithmeticType<double>(); + } + Y_UNIT_TEST(TestLongDouble) { - TestArithmeticType<long double>(); - } - + TestArithmeticType<long double>(); + } + Y_UNIT_TEST(TestAddRValueReference) { ASSERT_SAME_TYPE(std::add_rvalue_reference_t<int>, int&&); ASSERT_SAME_TYPE(std::add_rvalue_reference_t<int const&>, int const&); @@ -209,11 +209,11 @@ Y_UNIT_TEST_SUITE(TTypeTraitsTest) { UNIT_ASSERT(std::is_empty<TEmptyClass>::value); UNIT_ASSERT(std::is_empty<TEmptyDerivedClass>::value); UNIT_ASSERT(std::is_empty<TAnotherEmptyClass>::value); -#ifdef _MSC_VER - UNIT_ASSERT(!std::is_empty<TEmptyMultiDerivedClass>::value); -#else +#ifdef _MSC_VER + UNIT_ASSERT(!std::is_empty<TEmptyMultiDerivedClass>::value); +#else UNIT_ASSERT(std::is_empty<TEmptyMultiDerivedClass>::value); -#endif +#endif UNIT_ASSERT(!std::is_empty<TNonEmptyClass>::value); UNIT_ASSERT(!std::is_empty<TNonEmptyDerivedClass>::value); } @@ -234,29 +234,29 @@ Y_UNIT_TEST_SUITE(TTypeTraitsTest) { struct TPod { int value; }; - - struct TNontriviallyCopyAssignable { - TNontriviallyCopyAssignable(const TNontriviallyCopyAssignable&) = default; - TNontriviallyCopyAssignable& operator=(const TNontriviallyCopyAssignable&); - }; - - struct TNonTriviallyCopyConstructible { - TNonTriviallyCopyConstructible(const TNonTriviallyCopyConstructible&); - TNonTriviallyCopyConstructible& operator=(const TNonTriviallyCopyConstructible&) = default; - }; - - struct TNonTriviallyDestructible { - TNonTriviallyDestructible(const TNonTriviallyDestructible&) = default; - TNonTriviallyDestructible& operator=(const TNonTriviallyDestructible&) = default; - ~TNonTriviallyDestructible(); - }; - - UNIT_ASSERT(std::is_trivially_copyable<int>::value); - UNIT_ASSERT(std::is_trivially_copyable<TPod>::value); - UNIT_ASSERT(!std::is_trivially_copyable<TNontriviallyCopyAssignable>::value); - UNIT_ASSERT(!std::is_trivially_copyable<TNonTriviallyCopyConstructible>::value); - UNIT_ASSERT(!std::is_trivially_copyable<TNonTriviallyDestructible>::value); - } + + struct TNontriviallyCopyAssignable { + TNontriviallyCopyAssignable(const TNontriviallyCopyAssignable&) = default; + TNontriviallyCopyAssignable& operator=(const TNontriviallyCopyAssignable&); + }; + + struct TNonTriviallyCopyConstructible { + TNonTriviallyCopyConstructible(const TNonTriviallyCopyConstructible&); + TNonTriviallyCopyConstructible& operator=(const TNonTriviallyCopyConstructible&) = default; + }; + + struct TNonTriviallyDestructible { + TNonTriviallyDestructible(const TNonTriviallyDestructible&) = default; + TNonTriviallyDestructible& operator=(const TNonTriviallyDestructible&) = default; + ~TNonTriviallyDestructible(); + }; + + UNIT_ASSERT(std::is_trivially_copyable<int>::value); + UNIT_ASSERT(std::is_trivially_copyable<TPod>::value); + UNIT_ASSERT(!std::is_trivially_copyable<TNontriviallyCopyAssignable>::value); + UNIT_ASSERT(!std::is_trivially_copyable<TNonTriviallyCopyConstructible>::value); + UNIT_ASSERT(!std::is_trivially_copyable<TNonTriviallyDestructible>::value); + } }; namespace { diff --git a/util/generic/ut/ya.make b/util/generic/ut/ya.make index 6eaf24cc5f..49cd3fd345 100644 --- a/util/generic/ut/ya.make +++ b/util/generic/ut/ya.make @@ -16,7 +16,7 @@ SRCS( generic/cast_ut.cpp generic/deque_ut.cpp generic/explicit_type_ut.cpp - generic/flags_ut.cpp + generic/flags_ut.cpp generic/function_ut.cpp generic/guid_ut.cpp generic/hash_primes_ut.cpp diff --git a/util/generic/vector.h b/util/generic/vector.h index a5b258955a..b794ad038d 100644 --- a/util/generic/vector.h +++ b/util/generic/vector.h @@ -1,8 +1,8 @@ #pragma once -#include "fwd.h" +#include "fwd.h" #include "reserve.h" - + #include <util/memory/alloc.h> #include <vector> @@ -11,7 +11,7 @@ template <class T, class A> class TVector: public std::vector<T, TReboundAllocator<A, T>> { public: - using TBase = std::vector<T, TReboundAllocator<A, T>>; + using TBase = std::vector<T, TReboundAllocator<A, T>>; using TSelf = TVector<T, A>; using size_type = typename TBase::size_type; diff --git a/util/generic/vector_ut.cpp b/util/generic/vector_ut.cpp index 0f6b4037a0..e210f2f7f1 100644 --- a/util/generic/vector_ut.cpp +++ b/util/generic/vector_ut.cpp @@ -565,7 +565,7 @@ private: } void CheckInitializeList(const TVector<int>& v) { - for (size_t i = 0; i < v.size(); ++i) { + for (size_t i = 0; i < v.size(); ++i) { UNIT_ASSERT_EQUAL(v[i], static_cast<int>(i)); } } diff --git a/util/generic/yexception.h b/util/generic/yexception.h index b0c604e8c4..416adcab2d 100644 --- a/util/generic/yexception.h +++ b/util/generic/yexception.h @@ -119,8 +119,8 @@ class TIoSystemError: public TIoException { class TFileError: public TIoSystemError { }; -/** - * TBadArgumentException should be thrown when an argument supplied to some function (or constructor) +/** + * TBadArgumentException should be thrown when an argument supplied to some function (or constructor) * is invalid or incorrect. * * \note @@ -131,8 +131,8 @@ class TFileError: public TIoSystemError { struct TBadArgumentException: public virtual yexception { }; -/** - * TBadCastException should be thrown to indicate the failure of some type casting procedure +/** + * TBadCastException should be thrown to indicate the failure of some type casting procedure * (e.g. reading an integer parameter from string). */ struct TBadCastException: public virtual TBadArgumentException { diff --git a/util/generic/ymath.cpp b/util/generic/ymath.cpp index 31270728f4..d6a0038b5d 100644 --- a/util/generic/ymath.cpp +++ b/util/generic/ymath.cpp @@ -26,9 +26,9 @@ double Erf(double x) { return f; } -#endif // _MSC_VER +#endif // _MSC_VER -double LogGammaImpl(double x) { +double LogGammaImpl(double x) { static constexpr double lnSqrt2Pi = 0.91893853320467274178; // log(sqrt(2.0 * PI)) static constexpr double coeff9 = 1.0 / 1188.0; static constexpr double coeff7 = -1.0 / 1680.0; @@ -37,20 +37,20 @@ double LogGammaImpl(double x) { static constexpr double coeff1 = 1.0 / 12.0; if ((x == 1.0) || (x == 2.0)) { - return 0.0; // 0! = 1 + return 0.0; // 0! = 1 } - double bonus = 0.0; - while (x < 3.0) { - bonus -= log(x); - x += 1.0; - } - double lnX = log(x); - double sqrXInv = 1.0 / (x * x); - double res = coeff9 * sqrXInv + coeff7; - res = res * sqrXInv + coeff5; - res = res * sqrXInv + coeff3; - res = res * sqrXInv + coeff1; - res /= x; - res += x * lnX - x + lnSqrt2Pi - 0.5 * lnX; - return res + bonus; + double bonus = 0.0; + while (x < 3.0) { + bonus -= log(x); + x += 1.0; + } + double lnX = log(x); + double sqrXInv = 1.0 / (x * x); + double res = coeff9 * sqrXInv + coeff7; + res = res * sqrXInv + coeff5; + res = res * sqrXInv + coeff3; + res = res * sqrXInv + coeff1; + res /= x; + res += x * lnX - x + lnSqrt2Pi - 0.5 * lnX; + return res + bonus; } diff --git a/util/generic/ymath.h b/util/generic/ymath.h index 9ff9ae2abe..aabb1b0295 100644 --- a/util/generic/ymath.h +++ b/util/generic/ymath.h @@ -7,46 +7,46 @@ #include <cfloat> #include <cstdlib> -#include "typetraits.h" -#include "utility.h" - +#include "typetraits.h" +#include "utility.h" + constexpr double PI = M_PI; constexpr double M_LOG2_10 = 3.32192809488736234787; // log2(10) constexpr double M_LN2_INV = M_LOG2E; // 1 / ln(2) == log2(e) -/** - * \returns Absolute value of the provided argument. - */ -template <class T> +/** + * \returns Absolute value of the provided argument. + */ +template <class T> constexpr T Abs(T value) { return std::abs(value); -} - -/** - * @returns Base 2 logarithm of the provided double - * precision floating point value. - */ -inline double Log2(double value) { - return log(value) * M_LN2_INV; -} - -/** - * @returns Base 2 logarithm of the provided - * floating point value. - */ -inline float Log2(float value) { - return logf(value) * static_cast<float>(M_LN2_INV); -} - -/** - * @returns Base 2 logarithm of the provided integral value. - */ +} + +/** + * @returns Base 2 logarithm of the provided double + * precision floating point value. + */ +inline double Log2(double value) { + return log(value) * M_LN2_INV; +} + +/** + * @returns Base 2 logarithm of the provided + * floating point value. + */ +inline float Log2(float value) { + return logf(value) * static_cast<float>(M_LN2_INV); +} + +/** + * @returns Base 2 logarithm of the provided integral value. + */ template <class T> inline std::enable_if_t<std::is_integral<T>::value, double> -Log2(T value) { - return Log2(static_cast<double>(value)); -} - +Log2(T value) { + return Log2(static_cast<double>(value)); +} + /** Returns 2^x */ double Exp2(double); float Exp2f(float); @@ -100,10 +100,10 @@ inline double Erf(double x) { } #endif -/** - * @returns Natural logarithm of the absolute value - * of the gamma function of provided argument. - */ +/** + * @returns Natural logarithm of the absolute value + * of the gamma function of provided argument. + */ inline double LogGamma(double x) noexcept { #if defined(_glibc_) int sign; @@ -118,7 +118,7 @@ inline double LogGamma(double x) noexcept { #else extern double LogGammaImpl(double); return LogGammaImpl(x); -#endif +#endif } /** @@ -146,32 +146,32 @@ T Power(T x, Int n) { } return result; }; - -/** - * Compares two floating point values and returns true if they are considered equal. - * The two numbers are compared in a relative way, where the exactness is stronger - * the smaller the numbers are. - * - * Note that comparing values where either one is 0.0 will not work. - * The solution to this is to compare against values greater than or equal to 1.0. - * - * @code - * // Instead of comparing with 0.0 - * FuzzyEquals(0.0, 1.0e-200); // This will return false - * // Compare adding 1 to both values will fix the problem - * FuzzyEquals(1 + 0.0, 1 + 1.0e-200); // This will return true - * @endcode - */ -inline bool FuzzyEquals(double p1, double p2, double eps = 1.0e-13) { - return (Abs(p1 - p2) <= eps * Min(Abs(p1), Abs(p2))); -} - -/** - * @see FuzzyEquals(double, double, double) - */ -inline bool FuzzyEquals(float p1, float p2, float eps = 1.0e-6) { - return (Abs(p1 - p2) <= eps * Min(Abs(p1), Abs(p2))); -} + +/** + * Compares two floating point values and returns true if they are considered equal. + * The two numbers are compared in a relative way, where the exactness is stronger + * the smaller the numbers are. + * + * Note that comparing values where either one is 0.0 will not work. + * The solution to this is to compare against values greater than or equal to 1.0. + * + * @code + * // Instead of comparing with 0.0 + * FuzzyEquals(0.0, 1.0e-200); // This will return false + * // Compare adding 1 to both values will fix the problem + * FuzzyEquals(1 + 0.0, 1 + 1.0e-200); // This will return true + * @endcode + */ +inline bool FuzzyEquals(double p1, double p2, double eps = 1.0e-13) { + return (Abs(p1 - p2) <= eps * Min(Abs(p1), Abs(p2))); +} + +/** + * @see FuzzyEquals(double, double, double) + */ +inline bool FuzzyEquals(float p1, float p2, float eps = 1.0e-6) { + return (Abs(p1 - p2) <= eps * Min(Abs(p1), Abs(p2))); +} namespace NUtilMathPrivate { template <bool IsSigned> diff --git a/util/generic/ymath_ut.cpp b/util/generic/ymath_ut.cpp index 29190b55eb..3baea7928f 100644 --- a/util/generic/ymath_ut.cpp +++ b/util/generic/ymath_ut.cpp @@ -31,7 +31,7 @@ class TMathTest: public TTestBase { UNIT_TEST(TestErf); UNIT_TEST(TestLogGamma); UNIT_TEST(TestIsValidFloat); - UNIT_TEST(TestAbs); + UNIT_TEST(TestAbs); UNIT_TEST(TestPower); UNIT_TEST(TestSigmoid); UNIT_TEST(TestCeilDiv); @@ -42,7 +42,7 @@ private: void TestSqr(); void TestErf(); void TestLogGamma(); - void TestAbs(); + void TestAbs(); void TestPower(); void TestSigmoid(); void TestCeilDiv(); @@ -63,8 +63,8 @@ private: inline void TestLog2() { UNIT_ASSERT_DOUBLES_EQUAL(Log2(2.0), 1.0, 1e-10); - UNIT_ASSERT_DOUBLES_EQUAL(Log2(2ull), 1.0, 1e-10); - UNIT_ASSERT_DOUBLES_EQUAL(Log2(2.0f), 1.0f, 1e-7f); + UNIT_ASSERT_DOUBLES_EQUAL(Log2(2ull), 1.0, 1e-10); + UNIT_ASSERT_DOUBLES_EQUAL(Log2(2.0f), 1.0f, 1e-7f); } inline void ValueBitCount() { @@ -162,16 +162,16 @@ void TMathTest::TestLogGamma() { curVal += log(i - 0.5); } } - -void TMathTest::TestAbs() { - UNIT_ASSERT_VALUES_EQUAL(Abs(1), 1); - UNIT_ASSERT_VALUES_EQUAL(Abs(-1), 1); - UNIT_ASSERT_VALUES_EQUAL(Abs(-1000000000000ll), 1000000000000ll); - UNIT_ASSERT_VALUES_EQUAL(Abs(0), 0); - UNIT_ASSERT_VALUES_EQUAL(Abs(1.0), 1.0); - UNIT_ASSERT_VALUES_EQUAL(Abs(-1.0), 1.0); - UNIT_ASSERT_VALUES_EQUAL(Abs(0.0), 0.0); -} + +void TMathTest::TestAbs() { + UNIT_ASSERT_VALUES_EQUAL(Abs(1), 1); + UNIT_ASSERT_VALUES_EQUAL(Abs(-1), 1); + UNIT_ASSERT_VALUES_EQUAL(Abs(-1000000000000ll), 1000000000000ll); + UNIT_ASSERT_VALUES_EQUAL(Abs(0), 0); + UNIT_ASSERT_VALUES_EQUAL(Abs(1.0), 1.0); + UNIT_ASSERT_VALUES_EQUAL(Abs(-1.0), 1.0); + UNIT_ASSERT_VALUES_EQUAL(Abs(0.0), 0.0); +} void TMathTest::TestPower() { UNIT_ASSERT_VALUES_EQUAL(Power(0, 0), 1); |