Move TSharedData to actors lib

fix MemoryTrack usages

move MemoryTrack to utils

move TSharedData to actors lib

1 files changed, 231 insertions, 0 deletions

diff --git a/library/cpp/actors/util/shared_data_rope_backend_ut.cpp b/library/cpp/actors/util/shared_data_rope_backend_ut.cpp
new file mode 100644
index 0000000000..3ffe14a544
--- /dev/null
+++ b/library/cpp/actors/util/shared_data_rope_backend_ut.cpp
@@ -0,0 +1,231 @@
+#include <library/cpp/actors/util/rope.h>
+#include <library/cpp/testing/unittest/registar.h>
+#include <util/random/random.h>
+
+#include "shared_data_rope_backend.h"
+
+namespace NActors {
+
+    namespace {
+
+        TRope CreateRope(TString s, size_t sliceSize) {
+            TRope res;
+            for (size_t i = 0; i < s.size(); ) {
+                size_t len = std::min(sliceSize, s.size() - i);
+                if (i % 2) {
+                    auto str = s.substr(i, len);
+                    res.Insert(res.End(), TRope(MakeIntrusive<TRopeSharedDataBackend>(
+                        TSharedData::Copy(str.data(), str.size()))));
+                } else {
+                    res.Insert(res.End(), TRope(s.substr(i, len)));
+                }
+                i += len;
+            }
+            return res;
+        }
+
+        TString RopeToString(const TRope& rope) {
+            TString res;
+            auto iter = rope.Begin();
+            while (iter != rope.End()) {
+                res.append(iter.ContiguousData(), iter.ContiguousSize());
+                iter.AdvanceToNextContiguousBlock();
+            }
+
+            UNIT_ASSERT_VALUES_EQUAL(rope.GetSize(), res.size());
+
+            TString temp = TString::Uninitialized(rope.GetSize());
+            rope.Begin().ExtractPlainDataAndAdvance(temp.Detach(), temp.size());
+            UNIT_ASSERT_VALUES_EQUAL(temp, res);
+
+            return res;
+        }
+
+        TString Text = "No elements are copied or moved, only the internal pointers of the list nodes are re-pointed.";
+
+    }
+
+    Y_UNIT_TEST_SUITE(TRopeSharedDataBackend) {
+
+        // Same tests as in TRope but with new CreateRope using TSharedData backend
+
+        Y_UNIT_TEST(Leak) {
+            const size_t begin = 10, end = 20;
+            TRope rope = CreateRope(Text, 10);
+            rope.Erase(rope.Begin() + begin, rope.Begin() + end);
+        }
+
+        Y_UNIT_TEST(BasicRange) {
+            TRope rope = CreateRope(Text, 10);
+            for (size_t begin = 0; begin < Text.size(); ++begin) {
+                for (size_t end = begin; end <= Text.size(); ++end) {
+                    TRope::TIterator rBegin = rope.Begin() + begin;
+                    TRope::TIterator rEnd = rope.Begin() + end;
+                    UNIT_ASSERT_VALUES_EQUAL(RopeToString(TRope(rBegin, rEnd)), Text.substr(begin, end - begin));
+                }
+            }
+        }
+
+        Y_UNIT_TEST(Erase) {
+            for (size_t begin = 0; begin < Text.size(); ++begin) {
+                for (size_t end = begin; end <= Text.size(); ++end) {
+                    TRope rope = CreateRope(Text, 10);
+                    rope.Erase(rope.Begin() + begin, rope.Begin() + end);
+                    TString text = Text;
+                    text.erase(text.begin() + begin, text.begin() + end);
+                    UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), text);
+                }
+            }
+        }
+
+        Y_UNIT_TEST(Insert) {
+            TRope rope = CreateRope(Text, 10);
+            for (size_t begin = 0; begin < Text.size(); ++begin) {
+                for (size_t end = begin; end <= Text.size(); ++end) {
+                    TRope part = TRope(rope.Begin() + begin, rope.Begin() + end);
+                    for (size_t where = 0; where <= Text.size(); ++where) {
+                        TRope x(rope);
+                        x.Insert(x.Begin() + where, TRope(part));
+                        UNIT_ASSERT_VALUES_EQUAL(x.GetSize(), rope.GetSize() + part.GetSize());
+                        TString text = Text;
+                        text.insert(text.begin() + where, Text.begin() + begin, Text.begin() + end);
+                        UNIT_ASSERT_VALUES_EQUAL(RopeToString(x), text);
+                    }
+                }
+            }
+        }
+
+        Y_UNIT_TEST(Extract) {
+            for (size_t begin = 0; begin < Text.size(); ++begin) {
+                for (size_t end = begin; end <= Text.size(); ++end) {
+                    TRope rope = CreateRope(Text, 10);
+                    TRope part = rope.Extract(rope.Begin() + begin, rope.Begin() + end);
+                    TString text = Text;
+                    text.erase(text.begin() + begin, text.begin() + end);
+                    UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), text);
+                    UNIT_ASSERT_VALUES_EQUAL(RopeToString(part), Text.substr(begin, end - begin));
+                }
+            }
+        }
+
+        Y_UNIT_TEST(EraseFront) {
+            for (size_t pos = 0; pos <= Text.size(); ++pos) {
+                TRope rope = CreateRope(Text, 10);
+                rope.EraseFront(pos);
+                UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), Text.substr(pos));
+            }
+        }
+
+        Y_UNIT_TEST(EraseBack) {
+            for (size_t pos = 0; pos <= Text.size(); ++pos) {
+                TRope rope = CreateRope(Text, 10);
+                rope.EraseBack(pos);
+                UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), Text.substr(0, Text.size() - pos));
+            }
+        }
+
+        Y_UNIT_TEST(ExtractFront) {
+            for (size_t step = 1; step <= Text.size(); ++step) {
+                TRope rope = CreateRope(Text, 10);
+                TRope out;
+                while (const size_t len = Min(step, rope.GetSize())) {
+                    rope.ExtractFront(len, &out);
+                    UNIT_ASSERT(rope.GetSize() + out.GetSize() == Text.size());
+                    UNIT_ASSERT_VALUES_EQUAL(RopeToString(out), Text.substr(0, out.GetSize()));
+                }
+            }
+        }
+
+        Y_UNIT_TEST(ExtractFrontPlain) {
+            for (size_t step = 1; step <= Text.size(); ++step) {
+                TRope rope = CreateRope(Text, 10);
+                TString buffer = Text;
+                auto it = rope.Begin();
+                size_t remain = rope.GetSize();
+                while (const size_t len = Min(step, remain)) {
+                    TString data = TString::Uninitialized(len);
+                    it.ExtractPlainDataAndAdvance(data.Detach(), data.size());
+                    UNIT_ASSERT_VALUES_EQUAL(data, buffer.substr(0, len));
+                    UNIT_ASSERT_VALUES_EQUAL(RopeToString(TRope(it, rope.End())), buffer.substr(len));
+                    buffer = buffer.substr(len);
+                    remain -= len;
+                }
+            }
+        }
+
+        Y_UNIT_TEST(Glueing) {
+            TRope rope = CreateRope(Text, 10);
+            for (size_t begin = 0; begin <= Text.size(); ++begin) {
+                for (size_t end = begin; end <= Text.size(); ++end) {
+                    TString repr = rope.DebugString();
+                    TRope temp = rope.Extract(rope.Position(begin), rope.Position(end));
+                    rope.Insert(rope.Position(begin), std::move(temp));
+                    UNIT_ASSERT_VALUES_EQUAL(repr, rope.DebugString());
+                    UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), Text);
+                }
+            }
+        }
+
+        Y_UNIT_TEST(IterWalk) {
+            TRope rope = CreateRope(Text, 10);
+            for (size_t step1 = 0; step1 <= rope.GetSize(); ++step1) {
+                for (size_t step2 = 0; step2 <= step1; ++step2) {
+                    TRope::TConstIterator iter = rope.Begin();
+                    iter += step1;
+                    iter -= step2;
+                    UNIT_ASSERT(iter == rope.Position(step1 - step2));
+                }
+            }
+        }
+
+        Y_UNIT_TEST(Compare) {
+            auto check = [](const TString& x, const TString& y) {
+                const TRope xRope = CreateRope(x, 7);
+                const TRope yRope = CreateRope(y, 11);
+                UNIT_ASSERT_VALUES_EQUAL(xRope == yRope, x == y);
+                UNIT_ASSERT_VALUES_EQUAL(xRope != yRope, x != y);
+                UNIT_ASSERT_VALUES_EQUAL(xRope <  yRope, x <  y);
+                UNIT_ASSERT_VALUES_EQUAL(xRope <= yRope, x <= y);
+                UNIT_ASSERT_VALUES_EQUAL(xRope >  yRope, x >  y);
+                UNIT_ASSERT_VALUES_EQUAL(xRope >= yRope, x >= y);
+            };
+
+            TVector<TString> pool;
+            for (size_t k = 0; k < 10; ++k) {
+                size_t len = RandomNumber<size_t>(100) + 100;
+                TString s = TString::Uninitialized(len);
+                char *p = s.Detach();
+                for (size_t j = 0; j < len; ++j) {
+                    *p++ = RandomNumber<unsigned char>();
+                }
+                pool.push_back(std::move(s));
+            }
+
+            for (const TString& x : pool) {
+                for (const TString& y : pool) {
+                    check(x, y);
+                }
+            }
+        }
+
+        // Specific TSharedDataRopeBackend tests
+
+        Y_UNIT_TEST(RopeOnlyBorrows) {
+            TSharedData data = TSharedData::Copy(Text.data(), Text.size());
+            {
+                TRope rope;
+                rope.Insert(rope.End(), TRope(MakeIntrusive<TRopeSharedDataBackend>(data)));
+                UNIT_ASSERT(data.IsShared());
+                TSharedData dataCopy = data;
+                UNIT_ASSERT(dataCopy.IsShared());
+                UNIT_ASSERT_EQUAL(dataCopy.data(), data.data());
+                rope.Insert(rope.End(), TRope(MakeIntrusive<TRopeSharedDataBackend>(data)));
+                rope.Insert(rope.End(), TRope(MakeIntrusive<TRopeSharedDataBackend>(data)));
+                dataCopy.Trim(10);
+                UNIT_ASSERT_EQUAL(rope.GetSize(), data.size() * 3);
+            }
+            UNIT_ASSERT(data.IsPrivate());
+        }
+    }
+
+} // namespace NActors