aboutsummaryrefslogtreecommitdiffstats
path: root/library/cpp/containers
diff options
context:
space:
mode:
authoryazevnul <yazevnul@yandex-team.ru>2022-02-10 16:46:46 +0300
committerDaniil Cherednik <dcherednik@yandex-team.ru>2022-02-10 16:46:46 +0300
commit8cbc307de0221f84c80c42dcbe07d40727537e2c (patch)
tree625d5a673015d1df891e051033e9fcde5c7be4e5 /library/cpp/containers
parent30d1ef3941e0dc835be7609de5ebee66958f215a (diff)
downloadydb-8cbc307de0221f84c80c42dcbe07d40727537e2c.tar.gz
Restoring authorship annotation for <yazevnul@yandex-team.ru>. Commit 1 of 2.
Diffstat (limited to 'library/cpp/containers')
-rw-r--r--library/cpp/containers/2d_array/2d_array.h2
-rw-r--r--library/cpp/containers/bitseq/bititerator.h4
-rw-r--r--library/cpp/containers/bitseq/bititerator_ut.cpp10
-rw-r--r--library/cpp/containers/bitseq/bitvector.h12
-rw-r--r--library/cpp/containers/bitseq/bitvector_ut.cpp12
-rw-r--r--library/cpp/containers/bitseq/traits.h4
-rw-r--r--library/cpp/containers/compact_vector/compact_vector.h10
-rw-r--r--library/cpp/containers/compact_vector/compact_vector_ut.cpp8
-rw-r--r--library/cpp/containers/comptrie/chunked_helpers_trie.h6
-rw-r--r--library/cpp/containers/comptrie/comptrie_builder.h16
-rw-r--r--library/cpp/containers/comptrie/comptrie_builder.inl82
-rw-r--r--library/cpp/containers/comptrie/comptrie_impl.h12
-rw-r--r--library/cpp/containers/comptrie/comptrie_trie.h34
-rw-r--r--library/cpp/containers/comptrie/comptrie_ut.cpp122
-rw-r--r--library/cpp/containers/comptrie/loader/loader.h2
-rw-r--r--library/cpp/containers/comptrie/loader/loader_ut.cpp4
-rw-r--r--library/cpp/containers/comptrie/make_fast_layout.h2
-rw-r--r--library/cpp/containers/comptrie/minimize.h2
-rw-r--r--library/cpp/containers/comptrie/write_trie_backwards.h4
-rw-r--r--library/cpp/containers/intrusive_avl_tree/avltree.h72
-rw-r--r--library/cpp/containers/intrusive_avl_tree/ut/avltree_ut.cpp6
-rw-r--r--library/cpp/containers/intrusive_rb_tree/rb_tree.h78
-rw-r--r--library/cpp/containers/intrusive_rb_tree/rb_tree_ut.cpp12
-rw-r--r--library/cpp/containers/ring_buffer/ring_buffer.cpp2
-rw-r--r--library/cpp/containers/ring_buffer/ring_buffer.h4
-rw-r--r--library/cpp/containers/ring_buffer/ya.make16
-rw-r--r--library/cpp/containers/stack_array/stack_array.h4
-rw-r--r--library/cpp/containers/stack_array/ut/tests_ut.cpp8
-rw-r--r--library/cpp/containers/stack_vector/stack_vec_ut.cpp10
-rw-r--r--library/cpp/containers/top_keeper/top_keeper.h8
-rw-r--r--library/cpp/containers/top_keeper/top_keeper/top_keeper.h8
-rw-r--r--library/cpp/containers/top_keeper/top_keeper/ut/top_keeper_ut.cpp16
-rw-r--r--library/cpp/containers/top_keeper/ut/top_keeper_ut.cpp16
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];