diff options
author | yazevnul <yazevnul@yandex-team.ru> | 2022-02-10 16:46:46 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:46:46 +0300 |
commit | 8cbc307de0221f84c80c42dcbe07d40727537e2c (patch) | |
tree | 625d5a673015d1df891e051033e9fcde5c7be4e5 /library/cpp/containers | |
parent | 30d1ef3941e0dc835be7609de5ebee66958f215a (diff) | |
download | ydb-8cbc307de0221f84c80c42dcbe07d40727537e2c.tar.gz |
Restoring authorship annotation for <yazevnul@yandex-team.ru>. Commit 1 of 2.
Diffstat (limited to 'library/cpp/containers')
33 files changed, 304 insertions, 304 deletions
diff --git a/library/cpp/containers/2d_array/2d_array.h b/library/cpp/containers/2d_array/2d_array.h index 9e24650637..aa47f39933 100644 --- a/library/cpp/containers/2d_array/2d_array.h +++ b/library/cpp/containers/2d_array/2d_array.h @@ -13,7 +13,7 @@ struct TBoundCheck { Size = s; } T& operator[](size_t i) const { - Y_ASSERT(i >= 0 && i < Size); + Y_ASSERT(i >= 0 && i < Size); return Data[i]; } }; diff --git a/library/cpp/containers/bitseq/bititerator.h b/library/cpp/containers/bitseq/bititerator.h index 52dadd3798..bbeadb7295 100644 --- a/library/cpp/containers/bitseq/bititerator.h +++ b/library/cpp/containers/bitseq/bititerator.h @@ -44,7 +44,7 @@ public: TWord Peek(ui8 count) const { if (!count) return 0; - Y_VERIFY_DEBUG(count <= TTraits::NumBits); + Y_VERIFY_DEBUG(count <= TTraits::NumBits); if (!Mask) return *Data & TTraits::ElemMask(count); @@ -64,7 +64,7 @@ public: TWord Read(ui8 count) { if (!count) return 0; - Y_VERIFY_DEBUG(count <= TTraits::NumBits); + Y_VERIFY_DEBUG(count <= TTraits::NumBits); if (!Mask) { Current = *Data++; diff --git a/library/cpp/containers/bitseq/bititerator_ut.cpp b/library/cpp/containers/bitseq/bititerator_ut.cpp index ed0925866f..a7bbec119f 100644 --- a/library/cpp/containers/bitseq/bititerator_ut.cpp +++ b/library/cpp/containers/bitseq/bititerator_ut.cpp @@ -3,7 +3,7 @@ #include <library/cpp/testing/unittest/registar.h> #include <util/generic/vector.h> -Y_UNIT_TEST_SUITE(TBitIteratorTest) { +Y_UNIT_TEST_SUITE(TBitIteratorTest) { TVector<ui16> GenWords() { TVector<ui16> words(1, 0); for (ui16 word = 1; word; ++word) @@ -19,7 +19,7 @@ Y_UNIT_TEST_SUITE(TBitIteratorTest) { UNIT_ASSERT_EQUAL(peek, expected); } - Y_UNIT_TEST(TestNextAndPeek) { + Y_UNIT_TEST(TestNextAndPeek) { const auto& words = GenWords(); TBitIterator<ui16> iter(words.data()); @@ -37,7 +37,7 @@ Y_UNIT_TEST_SUITE(TBitIteratorTest) { UNIT_ASSERT_EQUAL(iter.NextWord(), words.data() + words.size()); } - Y_UNIT_TEST(TestAlignedReadAndPeek) { + Y_UNIT_TEST(TestAlignedReadAndPeek) { const auto& words = GenWords(); TBitIterator<ui16> iter(words.data()); @@ -50,7 +50,7 @@ Y_UNIT_TEST_SUITE(TBitIteratorTest) { UNIT_ASSERT_EQUAL(iter.NextWord(), words.data() + words.size()); } - Y_UNIT_TEST(TestForward) { + Y_UNIT_TEST(TestForward) { TVector<ui32> words; words.push_back((1 << 10) | (1 << 20) | (1 << 25)); words.push_back(1 | (1 << 5) | (1 << 6) | (1 << 30)); @@ -89,7 +89,7 @@ Y_UNIT_TEST_SUITE(TBitIteratorTest) { UNIT_ASSERT_EQUAL(iter.NextWord(), words.data() + 6); } - Y_UNIT_TEST(TestUnalignedReadAndPeek) { + Y_UNIT_TEST(TestUnalignedReadAndPeek) { TVector<ui32> words; words.push_back((1 << 10) | (1 << 20) | (1 << 25)); words.push_back(1 | (1 << 5) | (1 << 6) | (1 << 30)); diff --git a/library/cpp/containers/bitseq/bitvector.h b/library/cpp/containers/bitseq/bitvector.h index 3f8fd81ee5..9d6471ea9a 100644 --- a/library/cpp/containers/bitseq/bitvector.h +++ b/library/cpp/containers/bitseq/bitvector.h @@ -52,7 +52,7 @@ public: } bool Set(ui64 pos) { - Y_ASSERT(pos < Size_); + Y_ASSERT(pos < Size_); TWord& val = Data_[pos >> TTraits::DivShift]; if (val & TTraits::BitMask(pos & TTraits::ModMask)) return false; @@ -65,7 +65,7 @@ public: } void Reset(ui64 pos) { - Y_ASSERT(pos < Size_); + Y_ASSERT(pos < Size_); Data_[pos >> TTraits::DivShift] &= ~TTraits::BitMask(pos & TTraits::ModMask); } @@ -80,7 +80,7 @@ public: void Set(ui64 pos, TWord value, ui8 width, TWord mask) { if (!width) return; - Y_ASSERT((pos + width) <= Size_); + Y_ASSERT((pos + width) <= Size_); size_t word = pos >> TTraits::DivShift; TWord shift1 = pos & TTraits::ModMask; TWord shift2 = TTraits::NumBits - shift1; @@ -130,12 +130,12 @@ public: return Data_.data(); } - void Save(IOutputStream* out) const { + void Save(IOutputStream* out) const { ::Save(out, Size_); ::Save(out, Data_); } - void Load(IInputStream* inp) { + void Load(IInputStream* inp) { ::Load(inp, Size_); ::Load(inp, Data_); } @@ -145,7 +145,7 @@ public: Data_.size() * sizeof(TWord)); } - void Print(IOutputStream& out, size_t truncate = 128) { + void Print(IOutputStream& out, size_t truncate = 128) { for (size_t i = 0; i < Data_.size() && i < truncate; ++i) { for (int j = TTraits::NumBits - 1; j >= 0; --j) { size_t pos = TTraits::NumBits * i + j; diff --git a/library/cpp/containers/bitseq/bitvector_ut.cpp b/library/cpp/containers/bitseq/bitvector_ut.cpp index 6137adab1e..3fd4df1de6 100644 --- a/library/cpp/containers/bitseq/bitvector_ut.cpp +++ b/library/cpp/containers/bitseq/bitvector_ut.cpp @@ -6,8 +6,8 @@ #include <util/memory/blob.h> #include <util/stream/buffer.h> -Y_UNIT_TEST_SUITE(TBitVectorTest) { - Y_UNIT_TEST(TestEmpty) { +Y_UNIT_TEST_SUITE(TBitVectorTest) { + Y_UNIT_TEST(TestEmpty) { TBitVector<ui64> v64; UNIT_ASSERT_EQUAL(v64.Size(), 0); UNIT_ASSERT_EQUAL(v64.Words(), 0); @@ -17,7 +17,7 @@ Y_UNIT_TEST_SUITE(TBitVectorTest) { UNIT_ASSERT_EQUAL(v32.Words(), 0); } - Y_UNIT_TEST(TestOneWord) { + Y_UNIT_TEST(TestOneWord) { TBitVector<ui32> v; v.Append(1, 1); v.Append(0, 1); @@ -42,7 +42,7 @@ Y_UNIT_TEST_SUITE(TBitVectorTest) { UNIT_ASSERT_EQUAL(v.Words(), 1); } - Y_UNIT_TEST(TestManyWords) { + Y_UNIT_TEST(TestManyWords) { static const int BITS = 10; TBitVector<ui64> v; @@ -55,7 +55,7 @@ Y_UNIT_TEST_SUITE(TBitVectorTest) { UNIT_ASSERT_EQUAL(v.Get(i * BITS, BITS), (ui64)i); } - Y_UNIT_TEST(TestMaxWordSize) { + Y_UNIT_TEST(TestMaxWordSize) { TBitVector<ui32> v; for (int i = 0; i < 100; ++i) v.Append(i, 32); @@ -67,7 +67,7 @@ Y_UNIT_TEST_SUITE(TBitVectorTest) { UNIT_ASSERT_EQUAL(v.Get(10 * 32, 32), 100500); } - Y_UNIT_TEST(TestReadonlyVector) { + Y_UNIT_TEST(TestReadonlyVector) { TBitVector<ui64> v(100); for (ui64 i = 0; i < v.Size(); ++i) { if (i % 3 == 0) { diff --git a/library/cpp/containers/bitseq/traits.h b/library/cpp/containers/bitseq/traits.h index 2330b1b4f2..a57f15d7b3 100644 --- a/library/cpp/containers/bitseq/traits.h +++ b/library/cpp/containers/bitseq/traits.h @@ -1,6 +1,6 @@ #pragma once -#include <util/generic/bitops.h> +#include <util/generic/bitops.h> #include <util/generic/typetraits.h> #include <util/system/yassert.h> @@ -12,7 +12,7 @@ struct TBitSeqTraits { static inline TWord ElemMask(ui8 count) { // NOTE: Shifting by the type's length is UB, so we need this workaround. - if (Y_LIKELY(count)) + if (Y_LIKELY(count)) return TWord(-1) >> (NumBits - count); return 0; } diff --git a/library/cpp/containers/compact_vector/compact_vector.h b/library/cpp/containers/compact_vector/compact_vector.h index dbe7473f0c..434eda0f1a 100644 --- a/library/cpp/containers/compact_vector/compact_vector.h +++ b/library/cpp/containers/compact_vector/compact_vector.h @@ -162,14 +162,14 @@ public: } TIterator Insert(TIterator pos, const T& elem) { - Y_ASSERT(pos >= Begin()); - Y_ASSERT(pos <= End()); + Y_ASSERT(pos >= Begin()); + Y_ASSERT(pos <= End()); size_t posn = pos - Begin(); if (pos == End()) { PushBack(elem); } else { - Y_ASSERT(Size() > 0); + Y_ASSERT(Size() > 0); Reserve(Size() + 1); @@ -198,12 +198,12 @@ public: } T& operator[](size_t index) { - Y_ASSERT(index < Size()); + Y_ASSERT(index < Size()); return Ptr[index]; } const T& operator[](size_t index) const { - Y_ASSERT(index < Size()); + Y_ASSERT(index < Size()); return Ptr[index]; } }; diff --git a/library/cpp/containers/compact_vector/compact_vector_ut.cpp b/library/cpp/containers/compact_vector/compact_vector_ut.cpp index 7d413d6575..4f5ec0ad10 100644 --- a/library/cpp/containers/compact_vector/compact_vector_ut.cpp +++ b/library/cpp/containers/compact_vector/compact_vector_ut.cpp @@ -2,11 +2,11 @@ #include "compact_vector.h" -Y_UNIT_TEST_SUITE(TCompactVectorTest) { - Y_UNIT_TEST(TestSimple1) { +Y_UNIT_TEST_SUITE(TCompactVectorTest) { + Y_UNIT_TEST(TestSimple1) { } - Y_UNIT_TEST(TestSimple) { + Y_UNIT_TEST(TestSimple) { TCompactVector<ui32> vector; for (ui32 i = 0; i < 10000; ++i) { vector.PushBack(i + 20); @@ -17,7 +17,7 @@ Y_UNIT_TEST_SUITE(TCompactVectorTest) { } } - Y_UNIT_TEST(TestInsert) { + Y_UNIT_TEST(TestInsert) { TCompactVector<ui32> vector; for (ui32 i = 0; i < 10; ++i) { diff --git a/library/cpp/containers/comptrie/chunked_helpers_trie.h b/library/cpp/containers/comptrie/chunked_helpers_trie.h index cfa35f5ba2..993a9f800f 100644 --- a/library/cpp/containers/comptrie/chunked_helpers_trie.h +++ b/library/cpp/containers/comptrie/chunked_helpers_trie.h @@ -48,7 +48,7 @@ public: return Builder.Find(key, strlen(key), &dummy); } - void Save(IOutputStream& out) const { + void Save(IOutputStream& out) const { Builder.Save(out); } @@ -164,7 +164,7 @@ public: } } - void Save(IOutputStream& out, bool minimize = false) const { + void Save(IOutputStream& out, bool minimize = false) const { if (minimize) { CompactTrieMinimize<TBuilder>(out, Builder, false); } else { @@ -191,7 +191,7 @@ public: Values.push_back(TValue(key, value)); } - void Save(IOutputStream& out) { + void Save(IOutputStream& out) { Sort(Values.begin(), Values.end()); TTrieMapWriter<T, true> writer; for (typename TValues::const_iterator toValue = Values.begin(); toValue != Values.end(); ++toValue) diff --git a/library/cpp/containers/comptrie/comptrie_builder.h b/library/cpp/containers/comptrie/comptrie_builder.h index cf7d2e39a3..8b5adf060c 100644 --- a/library/cpp/containers/comptrie/comptrie_builder.h +++ b/library/cpp/containers/comptrie/comptrie_builder.h @@ -81,8 +81,8 @@ public: return FindLongestPrefix(key.data(), key.size(), prefixLen, value); } - size_t Save(IOutputStream& os) const; - size_t SaveAndDestroy(IOutputStream& os); + size_t Save(IOutputStream& os) const; + size_t SaveAndDestroy(IOutputStream& os); size_t SaveToFile(const TString& fileName) const { TFixedBufferFileOutput out(fileName); return Save(out); @@ -118,10 +118,10 @@ protected: // If you want both minimization and fast layout, do the minimization first. template <class TPacker> -size_t CompactTrieMinimize(IOutputStream& os, const char* data, size_t datalength, bool verbose = false, const TPacker& packer = TPacker(), NCompactTrie::EMinimizeMode mode = NCompactTrie::MM_DEFAULT); +size_t CompactTrieMinimize(IOutputStream& os, const char* data, size_t datalength, bool verbose = false, const TPacker& packer = TPacker(), NCompactTrie::EMinimizeMode mode = NCompactTrie::MM_DEFAULT); template <class TTrieBuilder> -size_t CompactTrieMinimize(IOutputStream& os, const TTrieBuilder& builder, bool verbose = false); +size_t CompactTrieMinimize(IOutputStream& os, const TTrieBuilder& builder, bool verbose = false); //---------------------------------------------------------------------------------------------------------------- // Lay the trie in memory in such a way that there are less cache misses when jumping from root to leaf. @@ -143,17 +143,17 @@ size_t CompactTrieMinimize(IOutputStream& os, const TTrieBuilder& builder, bool // (there is not much difference between these papers, actually). // template <class TPacker> -size_t CompactTrieMakeFastLayout(IOutputStream& os, const char* data, size_t datalength, bool verbose = false, const TPacker& packer = TPacker()); +size_t CompactTrieMakeFastLayout(IOutputStream& os, const char* data, size_t datalength, bool verbose = false, const TPacker& packer = TPacker()); template <class TTrieBuilder> -size_t CompactTrieMakeFastLayout(IOutputStream& os, const TTrieBuilder& builder, bool verbose = false); +size_t CompactTrieMakeFastLayout(IOutputStream& os, const TTrieBuilder& builder, bool verbose = false); // Composition of minimization and fast layout template <class TPacker> -size_t CompactTrieMinimizeAndMakeFastLayout(IOutputStream& os, const char* data, size_t datalength, bool verbose = false, const TPacker& packer = TPacker()); +size_t CompactTrieMinimizeAndMakeFastLayout(IOutputStream& os, const char* data, size_t datalength, bool verbose = false, const TPacker& packer = TPacker()); template <class TTrieBuilder> -size_t CompactTrieMinimizeAndMakeFastLayout(IOutputStream& os, const TTrieBuilder& builder, bool verbose = false); +size_t CompactTrieMinimizeAndMakeFastLayout(IOutputStream& os, const TTrieBuilder& builder, bool verbose = false); // Implementation details moved here. #include "comptrie_builder.inl" diff --git a/library/cpp/containers/comptrie/comptrie_builder.inl b/library/cpp/containers/comptrie/comptrie_builder.inl index f273fa6571..612a1bbe95 100644 --- a/library/cpp/containers/comptrie/comptrie_builder.inl +++ b/library/cpp/containers/comptrie/comptrie_builder.inl @@ -53,18 +53,18 @@ protected: bool FindLongestPrefixImpl(const char* keyptr, size_t keylen, size_t* prefixLen, TData* value) const; size_t NodeMeasureSubtree(TNode* thiz) const; - ui64 NodeSaveSubtree(TNode* thiz, IOutputStream& os) const; - ui64 NodeSaveSubtreeAndDestroy(TNode* thiz, IOutputStream& osy); + ui64 NodeSaveSubtree(TNode* thiz, IOutputStream& os) const; + ui64 NodeSaveSubtreeAndDestroy(TNode* thiz, IOutputStream& osy); void NodeBufferSubtree(TNode* thiz); size_t NodeMeasureLeafValue(TNode* thiz) const; - ui64 NodeSaveLeafValue(TNode* thiz, IOutputStream& os) const; + ui64 NodeSaveLeafValue(TNode* thiz, IOutputStream& os) const; virtual ui64 ArcMeasure(const TArc* thiz, size_t leftsize, size_t rightsize) const; virtual ui64 ArcSaveSelf(const TArc* thiz, IOutputStream& os) const; - ui64 ArcSave(const TArc* thiz, IOutputStream& os) const; - ui64 ArcSaveAndDestroy(const TArc* thiz, IOutputStream& os); + ui64 ArcSave(const TArc* thiz, IOutputStream& os) const; + ui64 ArcSaveAndDestroy(const TArc* thiz, IOutputStream& os); public: TCompactTrieBuilderImpl(TCompactTrieBuilderFlags flags, TPacker packer, IAllocator* alloc); @@ -83,8 +83,8 @@ public: bool FindEntry(const TSymbol* key, size_t keylen, TData* value) const; bool FindLongestPrefix(const TSymbol* key, size_t keylen, size_t* prefixlen, TData* value) const; - size_t Save(IOutputStream& os) const; - size_t SaveAndDestroy(IOutputStream& os); + size_t Save(IOutputStream& os) const; + size_t SaveAndDestroy(IOutputStream& os); void Clear(); @@ -118,8 +118,8 @@ public: virtual ~ISubtree() = default; virtual bool IsLast() const = 0; virtual ui64 Measure(const TBuilderImpl* builder) const = 0; - virtual ui64 Save(const TBuilderImpl* builder, IOutputStream& os) const = 0; - virtual ui64 SaveAndDestroy(TBuilderImpl* builder, IOutputStream& os) = 0; + virtual ui64 Save(const TBuilderImpl* builder, IOutputStream& os) const = 0; + virtual ui64 SaveAndDestroy(TBuilderImpl* builder, IOutputStream& os) = 0; virtual void Destroy(TBuilderImpl*) { } // Tries to find key in subtree. @@ -135,7 +135,7 @@ public: typedef typename TCompactVector<TArc>::const_iterator const_iterator; TArcSet() { - Y_ASSERT(reinterpret_cast<ISubtree*>(this) == static_cast<void*>(this)); // This assumption is used in TNode::Subtree() + Y_ASSERT(reinterpret_cast<ISubtree*>(this) == static_cast<void*>(this)); // This assumption is used in TNode::Subtree() } iterator Find(char ch); @@ -166,17 +166,17 @@ public: return builder->ArcMeasure(&(*this)[median], leftsize, rightsize); } - ui64 Save(const TBuilderImpl* builder, IOutputStream& os) const override { + ui64 Save(const TBuilderImpl* builder, IOutputStream& os) const override { return SaveRange(builder, 0, this->size(), os); } - ui64 SaveAndDestroy(TBuilderImpl* builder, IOutputStream& os) override { + ui64 SaveAndDestroy(TBuilderImpl* builder, IOutputStream& os) override { ui64 result = SaveRangeAndDestroy(builder, 0, this->size(), os); Destroy(builder); return result; } - ui64 SaveRange(const TBuilderImpl* builder, size_t from, size_t to, IOutputStream& os) const { + ui64 SaveRange(const TBuilderImpl* builder, size_t from, size_t to, IOutputStream& os) const { if (from >= to) return 0; @@ -188,7 +188,7 @@ public: return written; } - ui64 SaveRangeAndDestroy(TBuilderImpl* builder, size_t from, size_t to, IOutputStream& os) { + ui64 SaveRangeAndDestroy(TBuilderImpl* builder, size_t from, size_t to, IOutputStream& os) { if (from >= to) return 0; @@ -209,7 +209,7 @@ public: } ~TArcSet() override { - Y_ASSERT(this->empty()); + Y_ASSERT(this->empty()); } }; @@ -218,7 +218,7 @@ public: TArrayWithSizeHolder<char> Buffer; TBufferedSubtree() { - Y_ASSERT(reinterpret_cast<ISubtree*>(this) == static_cast<void*>(this)); // This assumption is used in TNode::Subtree() + Y_ASSERT(reinterpret_cast<ISubtree*>(this) == static_cast<void*>(this)); // This assumption is used in TNode::Subtree() } bool IsLast() const override { @@ -255,12 +255,12 @@ public: return Buffer.Size(); } - ui64 Save(const TBuilderImpl*, IOutputStream& os) const override { + ui64 Save(const TBuilderImpl*, IOutputStream& os) const override { os.Write(Buffer.Get(), Buffer.Size()); return Buffer.Size(); } - ui64 SaveAndDestroy(TBuilderImpl* builder, IOutputStream& os) override { + ui64 SaveAndDestroy(TBuilderImpl* builder, IOutputStream& os) override { ui64 result = Save(builder, os); TArrayWithSizeHolder<char>().Swap(Buffer); return result; @@ -284,7 +284,7 @@ public: Data->FileName = fileName; Data->Size = size; - Y_ASSERT(reinterpret_cast<ISubtree*>(this) == static_cast<void*>(this)); // This assumption is used in TNode::Subtree() + Y_ASSERT(reinterpret_cast<ISubtree*>(this) == static_cast<void*>(this)); // This assumption is used in TNode::Subtree() } bool IsLast() const override { @@ -320,7 +320,7 @@ public: return Data->Size; } - ui64 Save(const TBuilderImpl*, IOutputStream& os) const override { + ui64 Save(const TBuilderImpl*, IOutputStream& os) const override { TUnbufferedFileInput is(Data->FileName); ui64 written = TransferData(&is, &os); if (written != Data->Size) @@ -328,7 +328,7 @@ public: return written; } - ui64 SaveAndDestroy(TBuilderImpl* builder, IOutputStream& os) override { + ui64 SaveAndDestroy(TBuilderImpl* builder, IOutputStream& os) override { return Save(builder, os); } }; @@ -412,7 +412,7 @@ public: ~TNode() { Subtree()->~ISubtree(); - Y_ASSERT(PayloadType == DATA_ABSENT); + Y_ASSERT(PayloadType == DATA_ABSENT); } }; @@ -457,12 +457,12 @@ bool TCompactTrieBuilder<T, D, S>::FindLongestPrefix( } template <class T, class D, class S> -size_t TCompactTrieBuilder<T, D, S>::Save(IOutputStream& os) const { +size_t TCompactTrieBuilder<T, D, S>::Save(IOutputStream& os) const { return Impl->Save(os); } template <class T, class D, class S> -size_t TCompactTrieBuilder<T, D, S>::SaveAndDestroy(IOutputStream& os) { +size_t TCompactTrieBuilder<T, D, S>::SaveAndDestroy(IOutputStream& os) { return Impl->SaveAndDestroy(os); } @@ -509,13 +509,13 @@ void TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::ConvertSymbolArrayTo for (size_t i = 0; i < keylen; ++i) { TSymbol label = key[i]; for (int j = (int)NCompactTrie::ExtraBits<TSymbol>(); j >= 0; j -= 8) { - Y_ASSERT(ckeyptr < buf.Data() + buflen); + Y_ASSERT(ckeyptr < buf.Data() + buflen); *(ckeyptr++) = (char)(label >> j); } } buf.Proceed(buflen); - Y_ASSERT(ckeyptr == buf.Data() + buf.Filled()); + Y_ASSERT(ckeyptr == buf.Data() + buf.Filled()); } template <class T, class D, class S> @@ -750,7 +750,7 @@ void TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::Clear() { } template <class T, class D, class S> -size_t TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::Save(IOutputStream& os) const { +size_t TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::Save(IOutputStream& os) const { const size_t len = NodeMeasureSubtree(Root); if (len != NodeSaveSubtree(Root, os)) ythrow yexception() << "something wrong"; @@ -759,7 +759,7 @@ size_t TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::Save(IOutputStream } template <class T, class D, class S> -size_t TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::SaveAndDestroy(IOutputStream& os) { +size_t TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::SaveAndDestroy(IOutputStream& os) { const size_t len = NodeMeasureSubtree(Root); if (len != NodeSaveSubtreeAndDestroy(Root, os)) ythrow yexception() << "something wrong"; @@ -829,12 +829,12 @@ size_t TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::NodeMeasureSubtree } template <class T, class D, class S> -ui64 TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::NodeSaveSubtree(TNode* thiz, IOutputStream& os) const { +ui64 TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::NodeSaveSubtree(TNode* thiz, IOutputStream& os) const { return thiz->Subtree()->Save(this, os); } template <class T, class D, class S> -ui64 TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::NodeSaveSubtreeAndDestroy(TNode* thiz, IOutputStream& os) { +ui64 TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::NodeSaveSubtreeAndDestroy(TNode* thiz, IOutputStream& os) { return thiz->Subtree()->SaveAndDestroy(this, os); } @@ -853,7 +853,7 @@ void TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::NodeBufferSubtree(TN TMemoryOutput bufout(buffer.Get(), buffer.Size()); ui64 written = arcSet->Save(this, bufout); - Y_ASSERT(written == bufferLength); + Y_ASSERT(written == bufferLength); arcSet->Destroy(this); arcSet->~TArcSet(); @@ -872,7 +872,7 @@ size_t TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::NodeMeasureLeafVal } template <class T, class D, class S> -ui64 TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::NodeSaveLeafValue(TNode* thiz, IOutputStream& os) const { +ui64 TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::NodeSaveLeafValue(TNode* thiz, IOutputStream& os) const { if (!thiz->IsFinal()) return 0; @@ -919,7 +919,7 @@ ui64 TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::ArcMeasure( } template <class T, class D, class S> -ui64 TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::ArcSaveSelf(const TArc* thiz, IOutputStream& os) const { +ui64 TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::ArcSaveSelf(const TArc* thiz, IOutputStream& os) const { using namespace NCompactTrie; ui64 written = 0; @@ -962,14 +962,14 @@ ui64 TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::ArcSaveSelf(const TA } template <class T, class D, class S> -ui64 TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::ArcSave(const TArc* thiz, IOutputStream& os) const { +ui64 TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::ArcSave(const TArc* thiz, IOutputStream& os) const { ui64 written = ArcSaveSelf(thiz, os); written += NodeSaveSubtree(thiz->Node, os); return written; } template <class T, class D, class S> -ui64 TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::ArcSaveAndDestroy(const TArc* thiz, IOutputStream& os) { +ui64 TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::ArcSaveAndDestroy(const TArc* thiz, IOutputStream& os) { ui64 written = ArcSaveSelf(thiz, os); written += NodeSaveSubtreeAndDestroy(thiz->Node, os); return written; @@ -1061,13 +1061,13 @@ const typename TCompactTrieBuilder<T, D, S>::TCompactTrieBuilderImpl::TNode* // as you expect it to, and can destroy the trie in the making. template <class TPacker> -size_t CompactTrieMinimize(IOutputStream& os, const char* data, size_t datalength, bool verbose /*= false*/, const TPacker& packer /*= TPacker()*/, NCompactTrie::EMinimizeMode mode) { +size_t CompactTrieMinimize(IOutputStream& os, const char* data, size_t datalength, bool verbose /*= false*/, const TPacker& packer /*= TPacker()*/, NCompactTrie::EMinimizeMode mode) { using namespace NCompactTrie; return CompactTrieMinimizeImpl(os, data, datalength, verbose, &packer, mode); } template <class TTrieBuilder> -size_t CompactTrieMinimize(IOutputStream& os, const TTrieBuilder& builder, bool verbose /*=false*/) { +size_t CompactTrieMinimize(IOutputStream& os, const TTrieBuilder& builder, bool verbose /*=false*/) { TBufferStream buftmp; size_t len = builder.Save(buftmp); return CompactTrieMinimize<typename TTrieBuilder::TPacker>(os, buftmp.Buffer().Data(), len, verbose); @@ -1093,27 +1093,27 @@ size_t CompactTrieMinimize(IOutputStream& os, const TTrieBuilder& builder, bool // (there is not much difference between these papers, actually). // template <class TPacker> -size_t CompactTrieMakeFastLayout(IOutputStream& os, const char* data, size_t datalength, bool verbose /*= false*/, const TPacker& packer /*= TPacker()*/) { +size_t CompactTrieMakeFastLayout(IOutputStream& os, const char* data, size_t datalength, bool verbose /*= false*/, const TPacker& packer /*= TPacker()*/) { using namespace NCompactTrie; return CompactTrieMakeFastLayoutImpl(os, data, datalength, verbose, &packer); } template <class TTrieBuilder> -size_t CompactTrieMakeFastLayout(IOutputStream& os, const TTrieBuilder& builder, bool verbose /*=false*/) { +size_t CompactTrieMakeFastLayout(IOutputStream& os, const TTrieBuilder& builder, bool verbose /*=false*/) { TBufferStream buftmp; size_t len = builder.Save(buftmp); return CompactTrieMakeFastLayout<typename TTrieBuilder::TPacker>(os, buftmp.Buffer().Data(), len, verbose); } template <class TPacker> -size_t CompactTrieMinimizeAndMakeFastLayout(IOutputStream& os, const char* data, size_t datalength, bool verbose/*=false*/, const TPacker& packer/*= TPacker()*/) { +size_t CompactTrieMinimizeAndMakeFastLayout(IOutputStream& os, const char* data, size_t datalength, bool verbose/*=false*/, const TPacker& packer/*= TPacker()*/) { TBufferStream buftmp; size_t len = CompactTrieMinimize(buftmp, data, datalength, verbose, packer); return CompactTrieMakeFastLayout(os, buftmp.Buffer().Data(), len, verbose, packer); } template <class TTrieBuilder> -size_t CompactTrieMinimizeAndMakeFastLayout(IOutputStream& os, const TTrieBuilder& builder, bool verbose /*=false*/) { +size_t CompactTrieMinimizeAndMakeFastLayout(IOutputStream& os, const TTrieBuilder& builder, bool verbose /*=false*/) { TBufferStream buftmp; size_t len = CompactTrieMinimize(buftmp, builder, verbose); return CompactTrieMakeFastLayout<typename TTrieBuilder::TPacker>(os, buftmp.Buffer().Data(), len, verbose); diff --git a/library/cpp/containers/comptrie/comptrie_impl.h b/library/cpp/containers/comptrie/comptrie_impl.h index f41c38311a..607b8e5d32 100644 --- a/library/cpp/containers/comptrie/comptrie_impl.h +++ b/library/cpp/containers/comptrie/comptrie_impl.h @@ -18,7 +18,7 @@ namespace NCompactTrie { Y_FORCE_INLINE size_t UnpackOffset(const char* p, size_t len); size_t MeasureOffset(size_t offset); size_t PackOffset(char* buffer, size_t offset); - static inline ui64 ArcSaveOffset(size_t offset, IOutputStream& os); + static inline ui64 ArcSaveOffset(size_t offset, IOutputStream& os); Y_FORCE_INLINE char LeapByte(const char*& datapos, const char* dataend, char label); template <class T> @@ -37,7 +37,7 @@ namespace NCompactTrie { } const size_t offsetlength = flags & MT_SIZEMASK; const size_t offset = UnpackOffset(datapos + 1, offsetlength); - Y_ASSERT(offset); + Y_ASSERT(offset); datapos += offset; } @@ -89,7 +89,7 @@ namespace NCompTriePrivate { } namespace NCompactTrie { - static inline ui64 ArcSaveOffset(size_t offset, IOutputStream& os) { + static inline ui64 ArcSaveOffset(size_t offset, IOutputStream& os) { using namespace NCompactTrie; if (!offset) @@ -127,7 +127,7 @@ namespace NCompactTrie { // These links are created during minimization: original uncompressed // tree does not need them. (If we find a way to package 3 offset lengths // into 1 byte, we could get rid of them; but it looks like they do no harm. - Y_ASSERT(datapos < dataend); + Y_ASSERT(datapos < dataend); offsetlength = flags & MT_SIZEMASK; offset = UnpackOffset(datapos, offsetlength); if (!offset) @@ -185,7 +185,7 @@ namespace NCompactTrie { template <typename TSymbol, class TPacker> Y_FORCE_INLINE bool Advance(const char*& datapos, const char* const dataend, const char*& value, TSymbol label, TPacker packer) { - Y_ASSERT(datapos < dataend); + Y_ASSERT(datapos < dataend); char flags = MT_NEXT; for (int i = (int)ExtraBits<TSymbol>(); i >= 0; i -= 8) { flags = LeapByte(datapos, dataend, (char)(label >> i)); @@ -195,7 +195,7 @@ namespace NCompactTrie { value = nullptr; - Y_ASSERT(datapos <= dataend); + Y_ASSERT(datapos <= dataend); if ((flags & MT_FINAL)) { value = datapos; datapos += packer.SkipLeaf(datapos); diff --git a/library/cpp/containers/comptrie/comptrie_trie.h b/library/cpp/containers/comptrie/comptrie_trie.h index 40ec1e52b3..25a288f23d 100644 --- a/library/cpp/containers/comptrie/comptrie_trie.h +++ b/library/cpp/containers/comptrie/comptrie_trie.h @@ -11,7 +11,7 @@ #include <util/generic/vector.h> #include <util/generic/yexception.h> #include <util/memory/blob.h> -#include <util/stream/input.h> +#include <util/stream/input.h> #include <utility> template <class T, class D, class S> @@ -54,16 +54,16 @@ protected: public: TCompactTrie() = default; - TCompactTrie(const char* d, size_t len, TPacker packer); - TCompactTrie(const char* d, size_t len) + TCompactTrie(const char* d, size_t len, TPacker packer); + TCompactTrie(const char* d, size_t len) : TCompactTrie{d, len, TPacker{}} { - } - - TCompactTrie(const TBlob& data, TPacker packer); - explicit TCompactTrie(const TBlob& data) + } + + TCompactTrie(const TBlob& data, TPacker packer); + explicit TCompactTrie(const TBlob& data) : TCompactTrie{data, TPacker{}} { - } - + } + // Skipper should be initialized with &Packer, not with &other.Packer, so you have to redefine these. TCompactTrie(const TCompactTrie& other); TCompactTrie(TCompactTrie&& other) noexcept; @@ -185,7 +185,7 @@ public: // LowerBound of X cannot be greater than X. TConstIterator UpperBound(const TKeyBuf& key) const; - void Print(IOutputStream& os); + void Print(IOutputStream& os); size_t Size() const; @@ -212,7 +212,7 @@ private: TArrayHolder<char> Storage; public: - TCompactTrieHolder(IInputStream& is, size_t len); + TCompactTrieHolder(IInputStream& is, size_t len); }; //------------------------// @@ -308,7 +308,7 @@ void TCompactTrie<T, D, S>::Init(const TBlob& data, TPacker packer) { const char* emptypos = datapos; char flags = LeapByte(emptypos, dataend, 0); if (emptypos && (flags & MT_FINAL)) { - Y_ASSERT(emptypos <= dataend); + Y_ASSERT(emptypos <= dataend); EmptyValue = emptypos; } } @@ -375,7 +375,7 @@ bool TCompactTrie<T, D, S>::FindTails(const TSymbol* key, size_t keylen, TCompac if (key == keyend) { if (datapos) { - Y_ASSERT(datapos >= datastart); + Y_ASSERT(datapos >= datastart); res = TCompactTrie<T, D, S>(TBlob::NoCopy(datapos, dataend - datapos), value); } else { res = TCompactTrie<T, D, S>(value); @@ -406,7 +406,7 @@ inline bool TCompactTrie<T, D, S>::FindTails(TSymbol label, TCompactTrie<T, D, S return false; if (datapos) { - Y_ASSERT(datapos >= datastart); + Y_ASSERT(datapos >= datastart); res = TCompactTrie<T, D, S>(TBlob::NoCopy(datapos, dataend - datapos), value); } else { res = TCompactTrie<T, D, S>(value); @@ -452,7 +452,7 @@ typename TCompactTrie<T, D, S>::TConstIterator TCompactTrie<T, D, S>::UpperBound } template <class T, class D, class S> -void TCompactTrie<T, D, S>::Print(IOutputStream& os) { +void TCompactTrie<T, D, S>::Print(IOutputStream& os) { typedef typename ::TCompactTrieKeySelector<T>::TKeyBuf TSBuffer; for (TConstIterator it = Begin(); it != End(); ++it) { os << TSBuffer((*it).first.data(), (*it).first.size()) << "\t" << (*it).second << Endl; @@ -504,7 +504,7 @@ bool TCompactTrie<T, D, S>::LookupLongestPrefix(const TSymbol* key, size_t keyle return found; // no such arc } - Y_ASSERT(datapos <= dataend); + Y_ASSERT(datapos <= dataend); if ((flags & MT_FINAL)) { prefixLen = keylen - (keyend - key) - (i ? 1 : 0); valuepos = datapos; @@ -558,7 +558,7 @@ void TCompactTrie<T, D, S>::LookupPhrases( // TCompactTrieHolder template <class T, class D, class S> -TCompactTrieHolder<T, D, S>::TCompactTrieHolder(IInputStream& is, size_t len) +TCompactTrieHolder<T, D, S>::TCompactTrieHolder(IInputStream& is, size_t len) : Storage(new char[len]) { if (is.Load(Storage.Get(), len) != len) { diff --git a/library/cpp/containers/comptrie/comptrie_ut.cpp b/library/cpp/containers/comptrie/comptrie_ut.cpp index 74bee09b5d..6095f78cf8 100644 --- a/library/cpp/containers/comptrie/comptrie_ut.cpp +++ b/library/cpp/containers/comptrie/comptrie_ut.cpp @@ -1,7 +1,7 @@ #include <util/random/shuffle.h> #include <library/cpp/testing/unittest/registar.h> -#include <util/stream/output.h> +#include <util/stream/output.h> #include <utility> #include <util/charset/wide.h> @@ -105,7 +105,7 @@ private: UNIT_TEST(TestFirstSymbolIteratorChar32); UNIT_TEST(TestArrayPacker); - + UNIT_TEST(TestBuilderFindLongestPrefix); UNIT_TEST(TestBuilderFindLongestPrefixWithEmptyValue); @@ -118,7 +118,7 @@ private: static const char* SampleData[]; template <class T> - void CreateTrie(IOutputStream& out, bool minimize, bool useFastLayout); + void CreateTrie(IOutputStream& out, bool minimize, bool useFastLayout); template <class T> void CheckData(const char* src, size_t len); @@ -241,7 +241,7 @@ public: void TestFirstSymbolIterator32(); void TestFirstSymbolIteratorChar32(); - void TestArrayPacker(); + void TestArrayPacker(); void TestBuilderFindLongestPrefix(); void TestBuilderFindLongestPrefix(size_t keysCount, double branchProbability, bool isPrefixGrouped, bool hasEmptyKey); @@ -297,17 +297,17 @@ typename TCompactTrie<T>::TKey MakeWideKey(const TStringBuf& buf) { } template <class T> -void TCompactTrieTest::CreateTrie(IOutputStream& out, bool minimize, bool useFastLayout) { +void TCompactTrieTest::CreateTrie(IOutputStream& out, bool minimize, bool useFastLayout) { TCompactTrieBuilder<T> builder; - for (auto& i : SampleData) { - size_t len = strlen(i); + for (auto& i : SampleData) { + size_t len = strlen(i); - builder.Add(MakeWideKey<T>(i, len), len * 2); + builder.Add(MakeWideKey<T>(i, len), len * 2); } TBufferOutput tmp2; - IOutputStream& currentOutput = useFastLayout ? tmp2 : out; + IOutputStream& currentOutput = useFastLayout ? tmp2 : out; if (minimize) { TBufferOutput buftmp; builder.Save(buftmp); @@ -361,14 +361,14 @@ template <class T> void TCompactTrieTest::CheckData(const char* data, size_t datalen) { TCompactTrie<T> trie(data, datalen); - UNIT_ASSERT_VALUES_EQUAL(Y_ARRAY_SIZE(SampleData), trie.Size()); + UNIT_ASSERT_VALUES_EQUAL(Y_ARRAY_SIZE(SampleData), trie.Size()); - for (auto& i : SampleData) { - size_t len = strlen(i); + for (auto& i : SampleData) { + size_t len = strlen(i); ui64 value = 0; size_t prefixLen = 0; - typename TCompactTrie<T>::TKey key = MakeWideKey<T>(i, len); + typename TCompactTrie<T>::TKey key = MakeWideKey<T>(i, len); UNIT_ASSERT(trie.Find(key, &value)); UNIT_ASSERT_EQUAL(len * 2, value); UNIT_ASSERT(trie.FindLongestPrefix(key, &prefixLen, &value)); @@ -376,7 +376,7 @@ void TCompactTrieTest::CheckData(const char* data, size_t datalen) { UNIT_ASSERT_EQUAL(len * 2, value); TString badkey("bb"); - badkey += i; + badkey += i; key = MakeWideKey<T>(badkey); UNIT_ASSERT(!trie.Find(key)); value = 123; @@ -386,7 +386,7 @@ void TCompactTrieTest::CheckData(const char* data, size_t datalen) { UNIT_ASSERT_EQUAL(1, prefixLen); UNIT_ASSERT_EQUAL(2, value); - badkey = i; + badkey = i; badkey += "x"; key = MakeWideKey<T>(badkey); UNIT_ASSERT(!trie.Find(key)); @@ -425,10 +425,10 @@ void TCompactTrieTest::CheckIterator(const char* data, size_t datalen) { typedef typename TCompactTrie<T>::TValueType TValue; TMap<TKey, ui64> stored; - for (auto& i : SampleData) { - size_t len = strlen(i); + for (auto& i : SampleData) { + size_t len = strlen(i); - stored[MakeWideKey<T>(i, len)] = len * 2; + stored[MakeWideKey<T>(i, len)] = len * 2; } TCompactTrie<T> trie(data, datalen); @@ -567,7 +567,7 @@ void TCompactTrieTest::TestPhraseSearch() { TBufferOutput bufout; TCompactTrieBuilder<char> builder; - for (size_t i = 0; i < Y_ARRAY_SIZE(phrases); i++) { + for (size_t i = 0; i < Y_ARRAY_SIZE(phrases); i++) { builder.Add(phrases[i], strlen(phrases[i]), i); } builder.Save(bufout); @@ -576,8 +576,8 @@ void TCompactTrieTest::TestPhraseSearch() { TVector<TCompactTrie<char>::TPhraseMatch> matches; trie.FindPhrases(goodphrase, strlen(goodphrase), matches); - UNIT_ASSERT(matches.size() == Y_ARRAY_SIZE(phrases)); - for (size_t i = 0; i < Y_ARRAY_SIZE(phrases); i++) { + UNIT_ASSERT(matches.size() == Y_ARRAY_SIZE(phrases)); + for (size_t i = 0; i < Y_ARRAY_SIZE(phrases); i++) { UNIT_ASSERT(matches[i].first == strlen(phrases[i])); UNIT_ASSERT(matches[i].second == i); } @@ -734,11 +734,11 @@ void TCompactTrieTest::TestFindTailsImpl(const TString& prefix) { TMap<TString, ui64> input; - for (auto& i : SampleData) { + for (auto& i : SampleData) { TString temp = i; ui64 val = temp.size() * 2; builder.Add(temp.data(), temp.size(), val); - if (temp.StartsWith(prefix)) { + if (temp.StartsWith(prefix)) { input[temp.substr(prefix.size())] = val; } } @@ -789,10 +789,10 @@ void TCompactTrieTest::TestPrefixGrouped() { "Tumen", }; - for (size_t i = 0; i < Y_ARRAY_SIZE(data); ++i) { + for (size_t i = 0; i < Y_ARRAY_SIZE(data); ++i) { ui32 val = strlen(data[i]) + 1; b1.Add(data[i], strlen(data[i]), val); - for (size_t j = 0; j < Y_ARRAY_SIZE(data); ++j) { + for (size_t j = 0; j < Y_ARRAY_SIZE(data); ++j) { ui32 mustHave = strlen(data[j]) + 1; ui32 found = 0; if (j <= i) { @@ -813,10 +813,10 @@ void TCompactTrieTest::TestPrefixGrouped() { //t1.Print(Cerr); - for (auto& i : data) { + for (auto& i : data) { ui32 v; - UNIT_ASSERT(t1.Find(i, strlen(i), &v)); - UNIT_ASSERT_VALUES_EQUAL(strlen(i) + 1, v); + UNIT_ASSERT(t1.Find(i, strlen(i), &v)); + UNIT_ASSERT_VALUES_EQUAL(strlen(i) + 1, v); } } @@ -831,7 +831,7 @@ void TCompactTrieTest::CrashTestPrefixGrouped() { }; bool wasException = false; try { - for (size_t i = 0; i < Y_ARRAY_SIZE(data); ++i) { + for (size_t i = 0; i < Y_ARRAY_SIZE(data); ++i) { builder.Add(data[i], strlen(data[i]), i + 1); } } catch (const yexception& e) { @@ -947,7 +947,7 @@ void TCompactTrieTest::TestUniqueImpl(bool isPrefixGrouped) { "Fry", "Tumen", }; - for (size_t i = 0; i < Y_ARRAY_SIZE(data); ++i) { + for (size_t i = 0; i < Y_ARRAY_SIZE(data); ++i) { UNIT_ASSERT_C(builder.Add(data[i], strlen(data[i]), i + 1), i); } bool wasException = false; @@ -973,7 +973,7 @@ void TCompactTrieTest::TestAddRetValue() { "Fry", "Tumen", }; - for (size_t i = 0; i < Y_ARRAY_SIZE(data); ++i) { + for (size_t i = 0; i < Y_ARRAY_SIZE(data); ++i) { UNIT_ASSERT(builder.Add(data[i], strlen(data[i]), i + 1)); UNIT_ASSERT(!builder.Add(data[i], strlen(data[i]), i + 2)); ui32 value; @@ -995,10 +995,10 @@ void TCompactTrieTest::TestClear() { "Fry", "Tumen", }; - for (size_t i = 0; i < Y_ARRAY_SIZE(data); ++i) { + for (size_t i = 0; i < Y_ARRAY_SIZE(data); ++i) { builder.Add(data[i], strlen(data[i]), i + 1); } - UNIT_ASSERT(builder.GetEntryCount() == Y_ARRAY_SIZE(data)); + UNIT_ASSERT(builder.GetEntryCount() == Y_ARRAY_SIZE(data)); builder.Clear(); UNIT_ASSERT(builder.GetEntryCount() == 0); UNIT_ASSERT(builder.GetNodeCount() == 1); @@ -1105,7 +1105,7 @@ void TCompactTrieTest::TestTrieSet() { // Tests for trie with vector (list, set) values TVector<TUtf16String> TCompactTrieTest::GetSampleKeys(size_t nKeys) const { - Y_ASSERT(nKeys <= 10); + Y_ASSERT(nKeys <= 10); TString sampleKeys[] = {"a", "b", "ac", "bd", "abe", "bcf", "deg", "ah", "xy", "abc"}; TVector<TUtf16String> result; for (size_t i = 0; i < nKeys; i++) @@ -1332,7 +1332,7 @@ void TCompactTrieTest::TestSearchIterImpl() { TStringBuf("abbbc"), TStringBuf("bdfaa"), }; - for (size_t i = 0; i < Y_ARRAY_SIZE(data); ++i) { + for (size_t i = 0; i < Y_ARRAY_SIZE(data); ++i) { builder.Add(TConvertKey<TChar>::Convert(data[i]), i + 1); } builder.Save(buffer); @@ -1434,37 +1434,37 @@ void TCompactTrieTest::TestFirstSymbolIteratorChar32() { } -void TCompactTrieTest::TestArrayPacker() { +void TCompactTrieTest::TestArrayPacker() { using TDataInt = std::array<int, 2>; const std::pair<TString, TDataInt> dataXxx{"xxx", {{15, 16}}}; const std::pair<TString, TDataInt> dataYyy{"yyy", {{20, 30}}}; - - TCompactTrieBuilder<char, TDataInt> trieBuilderOne; - trieBuilderOne.Add(dataXxx.first, dataXxx.second); - trieBuilderOne.Add(dataYyy.first, dataYyy.second); - - TBufferOutput bufferOne; - trieBuilderOne.Save(bufferOne); - - const TCompactTrie<char, TDataInt> trieOne(bufferOne.Buffer().Data(), bufferOne.Buffer().Size()); - UNIT_ASSERT_VALUES_EQUAL(dataXxx.second, trieOne.Get(dataXxx.first)); - UNIT_ASSERT_VALUES_EQUAL(dataYyy.second, trieOne.Get(dataYyy.first)); - + + TCompactTrieBuilder<char, TDataInt> trieBuilderOne; + trieBuilderOne.Add(dataXxx.first, dataXxx.second); + trieBuilderOne.Add(dataYyy.first, dataYyy.second); + + TBufferOutput bufferOne; + trieBuilderOne.Save(bufferOne); + + const TCompactTrie<char, TDataInt> trieOne(bufferOne.Buffer().Data(), bufferOne.Buffer().Size()); + UNIT_ASSERT_VALUES_EQUAL(dataXxx.second, trieOne.Get(dataXxx.first)); + UNIT_ASSERT_VALUES_EQUAL(dataYyy.second, trieOne.Get(dataYyy.first)); + using TDataStroka = std::array<TString, 2>; const std::pair<TString, TDataStroka> dataZzz{"zzz", {{"hello", "there"}}}; const std::pair<TString, TDataStroka> dataWww{"www", {{"half", "life"}}}; - - TCompactTrieBuilder<char, TDataStroka> trieBuilderTwo; - trieBuilderTwo.Add(dataZzz.first, dataZzz.second); - trieBuilderTwo.Add(dataWww.first, dataWww.second); - - TBufferOutput bufferTwo; - trieBuilderTwo.Save(bufferTwo); - - const TCompactTrie<char, TDataStroka> trieTwo(bufferTwo.Buffer().Data(), bufferTwo.Buffer().Size()); - UNIT_ASSERT_VALUES_EQUAL(dataZzz.second, trieTwo.Get(dataZzz.first)); - UNIT_ASSERT_VALUES_EQUAL(dataWww.second, trieTwo.Get(dataWww.first)); -} + + TCompactTrieBuilder<char, TDataStroka> trieBuilderTwo; + trieBuilderTwo.Add(dataZzz.first, dataZzz.second); + trieBuilderTwo.Add(dataWww.first, dataWww.second); + + TBufferOutput bufferTwo; + trieBuilderTwo.Save(bufferTwo); + + const TCompactTrie<char, TDataStroka> trieTwo(bufferTwo.Buffer().Data(), bufferTwo.Buffer().Size()); + UNIT_ASSERT_VALUES_EQUAL(dataZzz.second, trieTwo.Get(dataZzz.first)); + UNIT_ASSERT_VALUES_EQUAL(dataWww.second, trieTwo.Get(dataWww.first)); +} void TCompactTrieTest::TestBuilderFindLongestPrefix() { const size_t sizes[] = {10, 100}; @@ -1517,7 +1517,7 @@ void TCompactTrieTest::TestBuilderFindLongestPrefix(size_t keysCount, double bra } else { size_t max = 0; for (size_t k = 0; k < i; ++k) - if (keys[k].Size() < otherKey.Size() && keys[k].Size() > max && otherKey.StartsWith(keys[k])) + if (keys[k].Size() < otherKey.Size() && keys[k].Size() > max && otherKey.StartsWith(keys[k])) max = keys[k].Size(); expectedSize = max; } diff --git a/library/cpp/containers/comptrie/loader/loader.h b/library/cpp/containers/comptrie/loader/loader.h index ee10e9b451..478c820abc 100644 --- a/library/cpp/containers/comptrie/loader/loader.h +++ b/library/cpp/containers/comptrie/loader/loader.h @@ -12,7 +12,7 @@ TrieType LoadTrieFromArchive(const TString& key, bool ignoreErrors = false) { TArchiveReader archive(TBlob::NoCopy(data, sizeof(data))); if (archive.Has(key)) { - TAutoPtr<IInputStream> trie = archive.ObjectByKey(key); + TAutoPtr<IInputStream> trie = archive.ObjectByKey(key); return TrieType(TBlob::FromStream(*trie)); } if (!ignoreErrors) { diff --git a/library/cpp/containers/comptrie/loader/loader_ut.cpp b/library/cpp/containers/comptrie/loader/loader_ut.cpp index 345063a31e..f146bfaff5 100644 --- a/library/cpp/containers/comptrie/loader/loader_ut.cpp +++ b/library/cpp/containers/comptrie/loader/loader_ut.cpp @@ -10,8 +10,8 @@ namespace { }; } -Y_UNIT_TEST_SUITE(ArchiveLoaderTests) { - Y_UNIT_TEST(BaseTest) { +Y_UNIT_TEST_SUITE(ArchiveLoaderTests) { + Y_UNIT_TEST(BaseTest) { TDummyTrie trie = LoadTrieFromArchive<TDummyTrie>("/dummy.trie", DATA, true); UNIT_ASSERT_EQUAL(trie.Size(), 3); diff --git a/library/cpp/containers/comptrie/make_fast_layout.h b/library/cpp/containers/comptrie/make_fast_layout.h index b8fab5d65b..6bb4ff0d55 100644 --- a/library/cpp/containers/comptrie/make_fast_layout.h +++ b/library/cpp/containers/comptrie/make_fast_layout.h @@ -3,7 +3,7 @@ #include "leaf_skipper.h" #include <cstddef> -class IOutputStream; +class IOutputStream; namespace NCompactTrie { // Return value: size of the resulting trie. diff --git a/library/cpp/containers/comptrie/minimize.h b/library/cpp/containers/comptrie/minimize.h index baaa431d04..5973564844 100644 --- a/library/cpp/containers/comptrie/minimize.h +++ b/library/cpp/containers/comptrie/minimize.h @@ -3,7 +3,7 @@ #include "leaf_skipper.h" #include <cstddef> -class IOutputStream; +class IOutputStream; namespace NCompactTrie { size_t MeasureOffset(size_t offset); diff --git a/library/cpp/containers/comptrie/write_trie_backwards.h b/library/cpp/containers/comptrie/write_trie_backwards.h index 634e6b811a..78e1e6ade4 100644 --- a/library/cpp/containers/comptrie/write_trie_backwards.h +++ b/library/cpp/containers/comptrie/write_trie_backwards.h @@ -17,7 +17,7 @@ namespace NCompactTrie { struct TOpaqueTrie; - size_t WriteTrieBackwards(IOutputStream& os, TReverseNodeEnumerator& enumerator, bool verbose); - size_t WriteTrieBackwardsNoAlloc(IOutputStream& os, TReverseNodeEnumerator& enumerator, TOpaqueTrie& trie, EMinimizeMode mode); + size_t WriteTrieBackwards(IOutputStream& os, TReverseNodeEnumerator& enumerator, bool verbose); + size_t WriteTrieBackwardsNoAlloc(IOutputStream& os, TReverseNodeEnumerator& enumerator, TOpaqueTrie& trie, EMinimizeMode mode); } diff --git a/library/cpp/containers/intrusive_avl_tree/avltree.h b/library/cpp/containers/intrusive_avl_tree/avltree.h index a58c63b07c..717c18cb14 100644 --- a/library/cpp/containers/intrusive_avl_tree/avltree.h +++ b/library/cpp/containers/intrusive_avl_tree/avltree.h @@ -28,11 +28,11 @@ class TAvlTree: public TNonCopyable { } inline bool IsEnd() const noexcept { - return Ptr_ == nullptr; + return Ptr_ == nullptr; } inline bool IsBegin() const noexcept { - return Ptr_ == nullptr; + return Ptr_ == nullptr; } inline bool IsFirst() const noexcept { @@ -107,10 +107,10 @@ class TAvlTree: public TNonCopyable { } inline static TIteratorBase FindPrev(TTreeItem* el) noexcept { - if (el->Left_ != nullptr) { + if (el->Left_ != nullptr) { el = el->Left_; - while (el->Right_ != nullptr) { + while (el->Right_ != nullptr) { el = el->Right_; } } else { @@ -118,7 +118,7 @@ class TAvlTree: public TNonCopyable { TTreeItem* last = el; el = el->Parent_; - if (el == nullptr || el->Right_ == last) { + if (el == nullptr || el->Right_ == last) { break; } } @@ -128,7 +128,7 @@ class TAvlTree: public TNonCopyable { } static TTreeItem* FindNext(TTreeItem* el) { - if (el->Right_ != nullptr) { + if (el->Right_ != nullptr) { el = el->Right_; while (el->Left_) { @@ -139,7 +139,7 @@ class TAvlTree: public TNonCopyable { TTreeItem* last = el; el = el->Parent_; - if (el == nullptr || el->Left_ == last) { + if (el == nullptr || el->Left_ == last) { break; } } @@ -202,14 +202,14 @@ public: el->Tree_ = this; TTreeItem* curEl = Root_; - TTreeItem* parentEl = nullptr; - TTreeItem* lastLess = nullptr; + TTreeItem* parentEl = nullptr; + TTreeItem* lastLess = nullptr; while (true) { - if (curEl == nullptr) { + if (curEl == nullptr) { AttachRebal(el, parentEl, lastLess); - if (lastFound != nullptr) { + if (lastFound != nullptr) { *lastFound = el; } @@ -223,11 +223,11 @@ public: parentEl = curEl; curEl = curEl->Right_; } else { - if (lastFound != nullptr) { + if (lastFound != nullptr) { *lastFound = curEl; } - return nullptr; + return nullptr; } } } @@ -245,12 +245,12 @@ public: } } - return nullptr; + return nullptr; } inline T* LowerBound(const TTreeItem* el) const noexcept { TTreeItem* curEl = Root_; - TTreeItem* lowerBound = nullptr; + TTreeItem* lowerBound = nullptr; while (curEl) { if (Compare(*el, *curEl)) { @@ -271,11 +271,11 @@ public: return this->EraseImpl(el); } - return nullptr; + return nullptr; } inline T* EraseImpl(TTreeItem* el) noexcept { - el->Tree_ = nullptr; + el->Tree_ = nullptr; TTreeItem* replacement; TTreeItem* fixfrom; @@ -330,10 +330,10 @@ public: Tail_ = el->Parent_; } - RemoveEl(el, nullptr); + RemoveEl(el, nullptr); } - if (fixfrom == nullptr) { + if (fixfrom == nullptr) { return AsT(el); } @@ -422,7 +422,7 @@ public: } inline iterator End() noexcept { - return iterator(nullptr, this); + return iterator(nullptr, this); } inline iterator begin() noexcept { @@ -507,7 +507,7 @@ private: } } - if (ggp == nullptr) { + if (ggp == nullptr) { Root_ = b; } else if (ggp->Left_ == gp) { ggp->Left_ = b; @@ -522,25 +522,25 @@ private: c->Parent_ = b; a->Left_ = t1; - if (t1 != nullptr) { + if (t1 != nullptr) { t1->Parent_ = a; } a->Right_ = t2; - if (t2 != nullptr) { + if (t2 != nullptr) { t2->Parent_ = a; } c->Left_ = t3; - if (t3 != nullptr) { + if (t3 != nullptr) { t3->Parent_ = c; } c->Right_ = t4; - if (t4 != nullptr) { + if (t4 != nullptr) { t4->Parent_ = c; } @@ -584,13 +584,13 @@ private: long lheight, rheight, balanceProp; TTreeItem* gp; - if (el == nullptr || el->Parent_ == nullptr || el->Parent_->Parent_ == nullptr) { - return nullptr; + if (el == nullptr || el->Parent_ == nullptr || el->Parent_->Parent_ == nullptr) { + return nullptr; } gp = el->Parent_->Parent_; - while (gp != nullptr) { + while (gp != nullptr) { lheight = gp->Left_ ? gp->Left_->Height_ : 0; rheight = gp->Right_ ? gp->Right_->Height_ : 0; balanceProp = lheight - rheight; @@ -603,12 +603,12 @@ private: gp = gp->Parent_; } - return nullptr; + return nullptr; } inline TTreeItem* FindFirstUnbalEl(TTreeItem* el) noexcept { - if (el == nullptr) { - return nullptr; + if (el == nullptr) { + return nullptr; } while (el) { @@ -623,7 +623,7 @@ private: el = el->Parent_; } - return nullptr; + return nullptr; } inline void ReplaceEl(TTreeItem* el, TTreeItem* replacement) noexcept { @@ -680,11 +680,11 @@ private: inline void AttachRebal(TTreeItem* el, TTreeItem* parentEl, TTreeItem* lastLess) { el->Parent_ = parentEl; - el->Left_ = nullptr; - el->Right_ = nullptr; + el->Left_ = nullptr; + el->Right_ = nullptr; el->Height_ = 1; - if (parentEl != nullptr) { + if (parentEl != nullptr) { if (lastLess == parentEl) { parentEl->Left_ = el; } else { @@ -707,7 +707,7 @@ private: TTreeItem* ub = FindFirstUnbalGP(el); - if (ub != nullptr) { + if (ub != nullptr) { Rebalance(ub); } } diff --git a/library/cpp/containers/intrusive_avl_tree/ut/avltree_ut.cpp b/library/cpp/containers/intrusive_avl_tree/ut/avltree_ut.cpp index cab2365cce..737da8e1e2 100644 --- a/library/cpp/containers/intrusive_avl_tree/ut/avltree_ut.cpp +++ b/library/cpp/containers/intrusive_avl_tree/ut/avltree_ut.cpp @@ -59,7 +59,7 @@ void TAvlTreeTest::TestLowerBound() { TIt it_large(1000); UNIT_ASSERT_EQUAL(its.LowerBound(&it3), &it3); UNIT_ASSERT_EQUAL(its.LowerBound(&it_zero), &it5); - UNIT_ASSERT_EQUAL(its.LowerBound(&it_large), nullptr); + UNIT_ASSERT_EQUAL(its.LowerBound(&it_large), nullptr); } void TAvlTreeTest::TestIterator() { @@ -81,7 +81,7 @@ void TAvlTreeTest::TestIterator() { its.Insert(&it2); TVector<int> res; - for (const TIt& i : its) { + for (const TIt& i : its) { res.push_back(i.Val); } @@ -89,7 +89,7 @@ void TAvlTreeTest::TestIterator() { UNIT_ASSERT_EQUAL(res, expected); res.clear(); - for (TIt& i : its) { + for (TIt& i : its) { res.push_back(i.Val); } UNIT_ASSERT_EQUAL(res, expected); diff --git a/library/cpp/containers/intrusive_rb_tree/rb_tree.h b/library/cpp/containers/intrusive_rb_tree/rb_tree.h index 0259452a14..579b1d6fc3 100644 --- a/library/cpp/containers/intrusive_rb_tree/rb_tree.h +++ b/library/cpp/containers/intrusive_rb_tree/rb_tree.h @@ -24,28 +24,28 @@ struct TRbTreeNodeBase { inline void ReInitNode() noexcept { Color_ = RBTreeBlack; - Parent_ = nullptr; - Left_ = nullptr; - Right_ = nullptr; + Parent_ = nullptr; + Left_ = nullptr; + Right_ = nullptr; Children_ = 1; } static TBasePtr MinimumNode(TBasePtr x) { - while (x->Left_ != nullptr) + while (x->Left_ != nullptr) x = x->Left_; return x; } static TBasePtr MaximumNode(TBasePtr x) { - while (x->Right_ != nullptr) + while (x->Right_ != nullptr) x = x->Right_; return x; } static TBasePtr ByIndex(TBasePtr x, size_t index) { - if (x->Left_ != nullptr) { + if (x->Left_ != nullptr) { if (index < x->Left_->Children_) return ByIndex(x->Left_, index); index -= x->Left_->Children_; @@ -178,7 +178,7 @@ public: class TRealNode: public TNodeBase { public: inline TRealNode() - : Tree_(nullptr) + : Tree_(nullptr) { } @@ -190,7 +190,7 @@ public: if (Tree_) { Tree_->EraseImpl(this); ReInitNode(); - Tree_ = nullptr; + Tree_ = nullptr; } } @@ -221,7 +221,7 @@ public: inline void Init() noexcept { Data_.Color_ = RBTreeRed; - Data_.Parent_ = nullptr; + Data_.Parent_ = nullptr; Data_.Left_ = &Data_; Data_.Right_ = &Data_; Data_.Children_ = 0; @@ -229,7 +229,7 @@ public: struct TDestroy { inline void operator()(TValue& v) const noexcept { - v.SetRbTreeParent(nullptr); + v.SetRbTreeParent(nullptr); v.ReInitNode(); } }; @@ -291,7 +291,7 @@ public: TBasePtr y = &this->Data_; TBasePtr x = Root(); - while (x != nullptr) { + while (x != nullptr) { ++(x->Children_); y = x; @@ -332,10 +332,10 @@ public: template <class T1> inline TValue* Find(const T1& k) const { - TBasePtr y = nullptr; + TBasePtr y = nullptr; TBasePtr x = Root(); // Current node. - while (x != nullptr) + while (x != nullptr) if (!KeyCompare_(ValueNode(x), k)) y = x, x = LeftNode(x); else @@ -343,7 +343,7 @@ public: if (y) { if (KeyCompare_(k, ValueNode(y))) { - y = nullptr; + y = nullptr; } } @@ -375,7 +375,7 @@ public: TBasePtr y = const_cast<TBasePtr>(&this->Data_); /* Last node which is not less than k. */ TBasePtr x = Root(); /* Current node. */ - while (x != nullptr) + while (x != nullptr) if (!KeyCompare_(ValueNode(x), k)) y = x, x = LeftNode(x); else @@ -389,7 +389,7 @@ public: TBasePtr y = const_cast<TBasePtr>(&this->Data_); /* Last node which is greater than k. */ TBasePtr x = Root(); /* Current node. */ - while (x != nullptr) + while (x != nullptr) if (KeyCompare_(k, ValueNode(x))) y = x, x = LeftNode(x); else @@ -402,11 +402,11 @@ public: inline size_t LessCount(const T1& k) const { auto x = LowerBound(k); if (x == const_cast<TBasePtr>(&this->Data_)) { - if (const auto root = Root()) { - return root->Children_; - } else { - return 0; - } + if (const auto root = Root()) { + return root->Children_; + } else { + return 0; + } } else { return GetIndex(x); } @@ -439,9 +439,9 @@ public: private: // CRP 7/10/00 inserted argument on_right, which is another hint (meant to // act like on_left and ignore a portion of the if conditions -- specify - // on_right != nullptr to bypass comparison as false or on_left != nullptr to bypass + // on_right != nullptr to bypass comparison as false or on_left != nullptr to bypass // comparison as true) - TIterator InsertImpl(TRbTreeNodeBase* parent, TRbTreeNodeBase* val, TRbTreeNodeBase* on_left = nullptr, TRbTreeNodeBase* on_right = nullptr) { + TIterator InsertImpl(TRbTreeNodeBase* parent, TRbTreeNodeBase* val, TRbTreeNodeBase* on_left = nullptr, TRbTreeNodeBase* on_right = nullptr) { ValueNode(val).SetRbTreeParent(this); TBasePtr new_node = val; @@ -450,10 +450,10 @@ private: // also makes LeftMost() = new_node Root() = new_node; RightMost() = new_node; - } else if (on_right == nullptr && - // If on_right != nullptr, the remainder fails to false - (on_left != nullptr || - // If on_left != nullptr, the remainder succeeds to true + } else if (on_right == nullptr && + // If on_right != nullptr, the remainder fails to false + (on_left != nullptr || + // If on_left != nullptr, the remainder succeeds to true KeyCompare_(ValueNode(val), ValueNode(parent)))) { LeftNode(parent) = new_node; @@ -532,7 +532,7 @@ template <class TDummy> void TRbGlobal<TDummy>::RotateLeft(TRbTreeNodeBase* x, TRbTreeNodeBase*& root) { TRbTreeNodeBase* y = x->Right_; x->Right_ = y->Left_; - if (y->Left_ != nullptr) + if (y->Left_ != nullptr) y->Left_->Parent_ = x; y->Parent_ = x->Parent_; @@ -552,7 +552,7 @@ template <class TDummy> void TRbGlobal<TDummy>::RotateRight(TRbTreeNodeBase* x, TRbTreeNodeBase*& root) { TRbTreeNodeBase* y = x->Left_; x->Left_ = y->Right_; - if (y->Right_ != nullptr) + if (y->Right_ != nullptr) y->Right_->Parent_ = x; y->Parent_ = x->Parent_; @@ -633,7 +633,7 @@ TRbTreeNodeBase* TRbGlobal<TDummy>::RebalanceForErase(TRbTreeNodeBase* z, TRbTreeNodeBase* x; TRbTreeNodeBase* x_parent; - if (y->Left_ == nullptr) // z has at most one non-null child. y == z. + if (y->Left_ == nullptr) // z has at most one non-null child. y == z. x = y->Right_; // x might be null. else { if (y->Right_ == nullptr) // z has exactly one non-null child. y == z. @@ -691,14 +691,14 @@ TRbTreeNodeBase* TRbGlobal<TDummy>::RebalanceForErase(TRbTreeNodeBase* z, } if (leftmost == z) { - if (z->Right_ == nullptr) // z->mLeft must be null also + if (z->Right_ == nullptr) // z->mLeft must be null also leftmost = z->Parent_; // makes leftmost == _M_header if z == root else leftmost = TRbTreeNodeBase::MinimumNode(x); } if (rightmost == z) { - if (z->Left_ == nullptr) // z->mRight must be null also + if (z->Left_ == nullptr) // z->mRight must be null also rightmost = z->Parent_; // makes rightmost == _M_header if z == root else // x == z->mLeft @@ -707,7 +707,7 @@ TRbTreeNodeBase* TRbGlobal<TDummy>::RebalanceForErase(TRbTreeNodeBase* z, } if (y->Color_ != RBTreeRed) { - while (x != root && (x == nullptr || x->Color_ == RBTreeBlack)) + while (x != root && (x == nullptr || x->Color_ == RBTreeBlack)) if (x == x_parent->Left_) { TRbTreeNodeBase* w = x_parent->Right_; if (w->Color_ == RBTreeRed) { @@ -716,9 +716,9 @@ TRbTreeNodeBase* TRbGlobal<TDummy>::RebalanceForErase(TRbTreeNodeBase* z, RotateLeft(x_parent, root); w = x_parent->Right_; } - if ((w->Left_ == nullptr || + if ((w->Left_ == nullptr || w->Left_->Color_ == RBTreeBlack) && - (w->Right_ == nullptr || + (w->Right_ == nullptr || w->Right_->Color_ == RBTreeBlack)) { w->Color_ = RBTreeRed; @@ -748,9 +748,9 @@ TRbTreeNodeBase* TRbGlobal<TDummy>::RebalanceForErase(TRbTreeNodeBase* z, RotateRight(x_parent, root); w = x_parent->Left_; } - if ((w->Right_ == nullptr || + if ((w->Right_ == nullptr || w->Right_->Color_ == RBTreeBlack) && - (w->Left_ == nullptr || + (w->Left_ == nullptr || w->Left_->Color_ == RBTreeBlack)) { w->Color_ = RBTreeRed; @@ -782,7 +782,7 @@ template <class TDummy> TRbTreeNodeBase* TRbGlobal<TDummy>::DecrementNode(TRbTreeNodeBase* Node_) { if (Node_->Color_ == RBTreeRed && Node_->Parent_->Parent_ == Node_) Node_ = Node_->Right_; - else if (Node_->Left_ != nullptr) { + else if (Node_->Left_ != nullptr) { Node_ = TRbTreeNodeBase::MaximumNode(Node_->Left_); } else { TBasePtr y = Node_->Parent_; @@ -797,7 +797,7 @@ TRbTreeNodeBase* TRbGlobal<TDummy>::DecrementNode(TRbTreeNodeBase* Node_) { template <class TDummy> TRbTreeNodeBase* TRbGlobal<TDummy>::IncrementNode(TRbTreeNodeBase* Node_) { - if (Node_->Right_ != nullptr) { + if (Node_->Right_ != nullptr) { Node_ = TRbTreeNodeBase::MinimumNode(Node_->Right_); } else { TBasePtr y = Node_->Parent_; diff --git a/library/cpp/containers/intrusive_rb_tree/rb_tree_ut.cpp b/library/cpp/containers/intrusive_rb_tree/rb_tree_ut.cpp index c34ed1fd9b..6ee9acbf48 100644 --- a/library/cpp/containers/intrusive_rb_tree/rb_tree_ut.cpp +++ b/library/cpp/containers/intrusive_rb_tree/rb_tree_ut.cpp @@ -46,7 +46,7 @@ class TRedBlackTreeTest: public TTestBase { UNIT_TEST(TestCheckChildrenAfterErase) UNIT_TEST(TestGettingIndexWithDifferentValuesAfterErase) UNIT_TEST(TestGettingIndexWithEqualValues) - UNIT_TEST(TestLessCountOnEmptyTree) + UNIT_TEST(TestLessCountOnEmptyTree) UNIT_TEST_SUITE_END(); private: @@ -288,11 +288,11 @@ private: UNIT_ASSERT(tree.Empty()); } - - inline void TestLessCountOnEmptyTree() { - TTree tree; - UNIT_ASSERT_VALUES_EQUAL(0, tree.LessCount(TNode(1))); - } + + inline void TestLessCountOnEmptyTree() { + TTree tree; + UNIT_ASSERT_VALUES_EQUAL(0, tree.LessCount(TNode(1))); + } }; UNIT_TEST_SUITE_REGISTRATION(TRedBlackTreeTest); diff --git a/library/cpp/containers/ring_buffer/ring_buffer.cpp b/library/cpp/containers/ring_buffer/ring_buffer.cpp index 799dad631b..f603db7283 100644 --- a/library/cpp/containers/ring_buffer/ring_buffer.cpp +++ b/library/cpp/containers/ring_buffer/ring_buffer.cpp @@ -1 +1 @@ -#include "ring_buffer.h" +#include "ring_buffer.h" diff --git a/library/cpp/containers/ring_buffer/ring_buffer.h b/library/cpp/containers/ring_buffer/ring_buffer.h index 41220dcf6b..d4eca72b34 100644 --- a/library/cpp/containers/ring_buffer/ring_buffer.h +++ b/library/cpp/containers/ring_buffer/ring_buffer.h @@ -37,12 +37,12 @@ public: } const T& operator[](size_t index) const { - Y_ASSERT(IsAvail(index)); + Y_ASSERT(IsAvail(index)); return Items[RealIndex(index)]; } T& operator[](size_t index) { - Y_ASSERT(IsAvail(index)); + Y_ASSERT(IsAvail(index)); return Items[RealIndex(index)]; } diff --git a/library/cpp/containers/ring_buffer/ya.make b/library/cpp/containers/ring_buffer/ya.make index 51333978f7..6d9967ba43 100644 --- a/library/cpp/containers/ring_buffer/ya.make +++ b/library/cpp/containers/ring_buffer/ya.make @@ -1,9 +1,9 @@ OWNER(mowgli) - -LIBRARY() - -SRCS( - ring_buffer.cpp -) - -END() + +LIBRARY() + +SRCS( + ring_buffer.cpp +) + +END() diff --git a/library/cpp/containers/stack_array/stack_array.h b/library/cpp/containers/stack_array/stack_array.h index 28e49bfc3c..4be0a5171b 100644 --- a/library/cpp/containers/stack_array/stack_array.h +++ b/library/cpp/containers/stack_array/stack_array.h @@ -23,10 +23,10 @@ namespace NStackArray { * as those might be called from a loop, and then stack overflow is in the cards. */ template <class T> - class TStackArray: public TArrayRef<T> { + class TStackArray: public TArrayRef<T> { public: inline TStackArray(void* data, size_t len) - : TArrayRef<T>((T*)data, len) + : TArrayRef<T>((T*)data, len) { NRangeOps::InitializeRange(this->begin(), this->end()); } diff --git a/library/cpp/containers/stack_array/ut/tests_ut.cpp b/library/cpp/containers/stack_array/ut/tests_ut.cpp index 3e96384f0e..29476858e6 100644 --- a/library/cpp/containers/stack_array/ut/tests_ut.cpp +++ b/library/cpp/containers/stack_array/ut/tests_ut.cpp @@ -1,7 +1,7 @@ #include <library/cpp/containers/stack_array/stack_array.h> #include <library/cpp/testing/unittest/registar.h> -Y_UNIT_TEST_SUITE(TestStackArray) { +Y_UNIT_TEST_SUITE(TestStackArray) { using namespace NStackArray; static inline void* FillWithTrash(void* d, size_t l) { @@ -12,7 +12,7 @@ Y_UNIT_TEST_SUITE(TestStackArray) { #define ALLOC(type, len) FillWithTrash(alloca(sizeof(type) * len), sizeof(type) * len), len - Y_UNIT_TEST(Test1) { + Y_UNIT_TEST(Test1) { TStackArray<ui32> s(ALLOC(ui32, 10)); UNIT_ASSERT_VALUES_EQUAL(s.size(), 10); @@ -50,7 +50,7 @@ Y_UNIT_TEST_SUITE(TestStackArray) { } }; - Y_UNIT_TEST(Test2) { + Y_UNIT_TEST(Test2) { { TStackArray<TX1> s(ALLOC(TX1, 10)); @@ -78,7 +78,7 @@ Y_UNIT_TEST_SUITE(TestStackArray) { } }; - Y_UNIT_TEST(Test3) { + Y_UNIT_TEST(Test3) { bool haveException = false; try { diff --git a/library/cpp/containers/stack_vector/stack_vec_ut.cpp b/library/cpp/containers/stack_vector/stack_vec_ut.cpp index 19f9677781..bcdec46ad4 100644 --- a/library/cpp/containers/stack_vector/stack_vec_ut.cpp +++ b/library/cpp/containers/stack_vector/stack_vec_ut.cpp @@ -43,13 +43,13 @@ namespace { }; } -Y_UNIT_TEST_SUITE(TStackBasedVectorTest) { - Y_UNIT_TEST(TestCreateEmpty) { +Y_UNIT_TEST_SUITE(TStackBasedVectorTest) { + Y_UNIT_TEST(TestCreateEmpty) { TStackVec<int> ints; UNIT_ASSERT_EQUAL(ints.size(), 0); } - Y_UNIT_TEST(TestCreateNonEmpty) { + Y_UNIT_TEST(TestCreateNonEmpty) { TStackVec<int> ints(5); UNIT_ASSERT_EQUAL(ints.size(), 5); @@ -58,7 +58,7 @@ Y_UNIT_TEST_SUITE(TStackBasedVectorTest) { } } - Y_UNIT_TEST(TestReallyOnStack) { + Y_UNIT_TEST(TestReallyOnStack) { const TStackVec<int> vec(5); UNIT_ASSERT( @@ -67,7 +67,7 @@ Y_UNIT_TEST_SUITE(TStackBasedVectorTest) { ); } - Y_UNIT_TEST(TestFallback) { + Y_UNIT_TEST(TestFallback) { TSmallVec<int> ints; for (int i = 0; i < 14; ++i) { ints.push_back(i); diff --git a/library/cpp/containers/top_keeper/top_keeper.h b/library/cpp/containers/top_keeper/top_keeper.h index 2f282b5a9e..362e430711 100644 --- a/library/cpp/containers/top_keeper/top_keeper.h +++ b/library/cpp/containers/top_keeper/top_keeper.h @@ -179,13 +179,13 @@ public: } const T& GetNext() { - Y_ENSURE(!IsEmpty(), "Trying GetNext from empty heap!"); + Y_ENSURE(!IsEmpty(), "Trying GetNext from empty heap!"); Finalize(); return Internal.Back(); } void Pop() { - Y_ENSURE(!IsEmpty(), "Trying Pop from empty heap!"); + Y_ENSURE(!IsEmpty(), "Trying Pop from empty heap!"); Finalize(); Internal.Pop(); if (IsEmpty()) { @@ -194,7 +194,7 @@ public: } T ExtractOne() { - Y_ENSURE(!IsEmpty(), "Trying ExtractOne from empty heap!"); + Y_ENSURE(!IsEmpty(), "Trying ExtractOne from empty heap!"); Finalize(); auto value = std::move(Internal.Back()); Internal.Pop(); @@ -243,7 +243,7 @@ public: } void SetMaxSize(size_t newMaxSize) { - Y_ENSURE(!Finalized, "Cannot resize after finalizing (Pop() / GetNext() / Finalize())! " + Y_ENSURE(!Finalized, "Cannot resize after finalizing (Pop() / GetNext() / Finalize())! " "Use TLimitedHeap for this scenario"); MaxSize = newMaxSize; Internal.SetMaxSize(newMaxSize); diff --git a/library/cpp/containers/top_keeper/top_keeper/top_keeper.h b/library/cpp/containers/top_keeper/top_keeper/top_keeper.h index 2f282b5a9e..362e430711 100644 --- a/library/cpp/containers/top_keeper/top_keeper/top_keeper.h +++ b/library/cpp/containers/top_keeper/top_keeper/top_keeper.h @@ -179,13 +179,13 @@ public: } const T& GetNext() { - Y_ENSURE(!IsEmpty(), "Trying GetNext from empty heap!"); + Y_ENSURE(!IsEmpty(), "Trying GetNext from empty heap!"); Finalize(); return Internal.Back(); } void Pop() { - Y_ENSURE(!IsEmpty(), "Trying Pop from empty heap!"); + Y_ENSURE(!IsEmpty(), "Trying Pop from empty heap!"); Finalize(); Internal.Pop(); if (IsEmpty()) { @@ -194,7 +194,7 @@ public: } T ExtractOne() { - Y_ENSURE(!IsEmpty(), "Trying ExtractOne from empty heap!"); + Y_ENSURE(!IsEmpty(), "Trying ExtractOne from empty heap!"); Finalize(); auto value = std::move(Internal.Back()); Internal.Pop(); @@ -243,7 +243,7 @@ public: } void SetMaxSize(size_t newMaxSize) { - Y_ENSURE(!Finalized, "Cannot resize after finalizing (Pop() / GetNext() / Finalize())! " + Y_ENSURE(!Finalized, "Cannot resize after finalizing (Pop() / GetNext() / Finalize())! " "Use TLimitedHeap for this scenario"); MaxSize = newMaxSize; Internal.SetMaxSize(newMaxSize); diff --git a/library/cpp/containers/top_keeper/top_keeper/ut/top_keeper_ut.cpp b/library/cpp/containers/top_keeper/top_keeper/ut/top_keeper_ut.cpp index a938279025..5684a00377 100644 --- a/library/cpp/containers/top_keeper/top_keeper/ut/top_keeper_ut.cpp +++ b/library/cpp/containers/top_keeper/top_keeper/ut/top_keeper_ut.cpp @@ -12,9 +12,9 @@ ui32 Rnd() { /* * Tests for TTopKeeper */ -Y_UNIT_TEST_SUITE(TTopKeeperTest) { +Y_UNIT_TEST_SUITE(TTopKeeperTest) { // Tests correctness on usual examples - Y_UNIT_TEST(CorrectnessTest) { + Y_UNIT_TEST(CorrectnessTest) { int m = 20000; TLimitedHeap<std::pair<int, int>> h1(m); @@ -40,7 +40,7 @@ Y_UNIT_TEST_SUITE(TTopKeeperTest) { } // Tests on zero-size correctness - Y_UNIT_TEST(ZeroSizeCorrectnes) { + Y_UNIT_TEST(ZeroSizeCorrectnes) { TTopKeeper<int> h(0); for (int i = 0; i < 100; ++i) { h.Insert(i % 10 + i / 10); @@ -50,7 +50,7 @@ Y_UNIT_TEST_SUITE(TTopKeeperTest) { } // Tests SetMaxSize behaviour - Y_UNIT_TEST(SetMaxSizeTest) { + Y_UNIT_TEST(SetMaxSizeTest) { int m = 20000; TLimitedHeap<int> h1(m); TTopKeeper<int> h2(m); @@ -77,7 +77,7 @@ Y_UNIT_TEST_SUITE(TTopKeeperTest) { } // Tests reuse behavior - Y_UNIT_TEST(ReuseTest) { + Y_UNIT_TEST(ReuseTest) { int m = 20000; TLimitedHeap<int> h1(m); TTopKeeper<int> h2(m); @@ -116,7 +116,7 @@ Y_UNIT_TEST_SUITE(TTopKeeperTest) { } // Tests reset behavior - Y_UNIT_TEST(ResetTest) { + Y_UNIT_TEST(ResetTest) { int m = 20000; TLimitedHeap<int> h1(m); TTopKeeper<int> h2(m); @@ -159,7 +159,7 @@ Y_UNIT_TEST_SUITE(TTopKeeperTest) { } } - Y_UNIT_TEST(PreRegressionTest) { + Y_UNIT_TEST(PreRegressionTest) { typedef std::pair<float, unsigned int> TElementType; const size_t randomTriesCount = 128; @@ -193,7 +193,7 @@ Y_UNIT_TEST_SUITE(TTopKeeperTest) { } } - Y_UNIT_TEST(CopyKeeperRegressionCase) { + Y_UNIT_TEST(CopyKeeperRegressionCase) { using TKeeper = TTopKeeper<float>; TVector<TKeeper> v(2, TKeeper(200)); auto& k = v[1]; diff --git a/library/cpp/containers/top_keeper/ut/top_keeper_ut.cpp b/library/cpp/containers/top_keeper/ut/top_keeper_ut.cpp index a938279025..5684a00377 100644 --- a/library/cpp/containers/top_keeper/ut/top_keeper_ut.cpp +++ b/library/cpp/containers/top_keeper/ut/top_keeper_ut.cpp @@ -12,9 +12,9 @@ ui32 Rnd() { /* * Tests for TTopKeeper */ -Y_UNIT_TEST_SUITE(TTopKeeperTest) { +Y_UNIT_TEST_SUITE(TTopKeeperTest) { // Tests correctness on usual examples - Y_UNIT_TEST(CorrectnessTest) { + Y_UNIT_TEST(CorrectnessTest) { int m = 20000; TLimitedHeap<std::pair<int, int>> h1(m); @@ -40,7 +40,7 @@ Y_UNIT_TEST_SUITE(TTopKeeperTest) { } // Tests on zero-size correctness - Y_UNIT_TEST(ZeroSizeCorrectnes) { + Y_UNIT_TEST(ZeroSizeCorrectnes) { TTopKeeper<int> h(0); for (int i = 0; i < 100; ++i) { h.Insert(i % 10 + i / 10); @@ -50,7 +50,7 @@ Y_UNIT_TEST_SUITE(TTopKeeperTest) { } // Tests SetMaxSize behaviour - Y_UNIT_TEST(SetMaxSizeTest) { + Y_UNIT_TEST(SetMaxSizeTest) { int m = 20000; TLimitedHeap<int> h1(m); TTopKeeper<int> h2(m); @@ -77,7 +77,7 @@ Y_UNIT_TEST_SUITE(TTopKeeperTest) { } // Tests reuse behavior - Y_UNIT_TEST(ReuseTest) { + Y_UNIT_TEST(ReuseTest) { int m = 20000; TLimitedHeap<int> h1(m); TTopKeeper<int> h2(m); @@ -116,7 +116,7 @@ Y_UNIT_TEST_SUITE(TTopKeeperTest) { } // Tests reset behavior - Y_UNIT_TEST(ResetTest) { + Y_UNIT_TEST(ResetTest) { int m = 20000; TLimitedHeap<int> h1(m); TTopKeeper<int> h2(m); @@ -159,7 +159,7 @@ Y_UNIT_TEST_SUITE(TTopKeeperTest) { } } - Y_UNIT_TEST(PreRegressionTest) { + Y_UNIT_TEST(PreRegressionTest) { typedef std::pair<float, unsigned int> TElementType; const size_t randomTriesCount = 128; @@ -193,7 +193,7 @@ Y_UNIT_TEST_SUITE(TTopKeeperTest) { } } - Y_UNIT_TEST(CopyKeeperRegressionCase) { + Y_UNIT_TEST(CopyKeeperRegressionCase) { using TKeeper = TTopKeeper<float>; TVector<TKeeper> v(2, TKeeper(200)); auto& k = v[1]; |