YT-18571: library/cpp/yt/small_containers -> library/cpp/yt/compact_containers

commit_hash:fc31d2770ebeffeb513c4535bd146c731b7f78fb

1 files changed, 114 insertions, 0 deletions

diff --git a/library/cpp/yt/compact_containers/unittests/compact_queue_ut.cpp b/library/cpp/yt/compact_containers/unittests/compact_queue_ut.cpp
new file mode 100644
index 00000000000..463d4ec4970
--- /dev/null
+++ b/library/cpp/yt/compact_containers/unittests/compact_queue_ut.cpp
@@ -0,0 +1,114 @@
+#include <library/cpp/yt/compact_containers/compact_queue.h>
+
+#include <library/cpp/testing/gtest/gtest.h>
+
+#include <queue>
+#include <random>
+
+namespace NYT {
+namespace {
+
+////////////////////////////////////////////////////////////////////////////////
+
+TEST(TCompactQueueTest, Simple)
+{
+    TCompactQueue<int, 4> queue;
+    queue.Push(1);
+    queue.Push(2);
+    queue.Push(3);
+
+    for (int i = 1; i <= 10; i++) {
+        EXPECT_EQ(queue.Size(), 3u);
+        EXPECT_EQ(queue.Front(), i);
+        EXPECT_EQ(queue.Pop(), i);
+        queue.Push(i + 3);
+    }
+
+    for (int i = 11; i <= 13; i++) {
+        EXPECT_EQ(queue.Front(), i);
+        queue.Pop();
+    }
+
+    EXPECT_TRUE(queue.Empty());
+}
+
+TEST(TCompactQueueTest, Reallocation1)
+{
+    TCompactQueue<int, 2> queue;
+    queue.Push(1);
+    queue.Push(2);
+    queue.Push(3);
+
+    for (int i = 1; i <= 10; i++) {
+        EXPECT_EQ(queue.Size(), 3u);
+        EXPECT_EQ(queue.Front(), i);
+        EXPECT_EQ(queue.Pop(), i);
+        queue.Push(i + 3);
+    }
+
+    for (int i = 11; i <= 13; i++) {
+        EXPECT_EQ(queue.Front(), i);
+        queue.Pop();
+    }
+
+    EXPECT_TRUE(queue.Empty());
+}
+
+TEST(TCompactQueueTest, Reallocation2)
+{
+    TCompactQueue<int, 3> queue;
+    queue.Push(1);
+    queue.Push(2);
+    queue.Push(3);
+    EXPECT_EQ(queue.Pop(), 1);
+    queue.Push(4);
+    queue.Push(5);
+
+    EXPECT_EQ(queue.Size(), 4u);
+
+    for (int i = 2; i <= 10; i++) {
+        EXPECT_EQ(queue.Size(), 4u);
+        EXPECT_EQ(queue.Front(), i);
+        EXPECT_EQ(queue.Pop(), i);
+        queue.Push(i + 4);
+    }
+
+    for (int i = 11; i <= 14; i++) {
+        EXPECT_EQ(queue.Front(), i);
+        queue.Pop();
+    }
+
+    EXPECT_TRUE(queue.Empty());
+}
+
+TEST(TCompactQueueTest, Stress)
+{
+    std::mt19937_64 rng(42);
+
+    for (int iteration = 0; iteration < 1000; ++iteration) {
+        TCompactQueue<int, 4> queue1;
+        std::queue<int> queue2;
+
+        for (int step = 0; step < 10'000; ++step) {
+            EXPECT_EQ(queue1.Size(), queue2.size());
+            EXPECT_EQ(queue1.Empty(), queue2.empty());
+            if (!queue1.Empty()) {
+                EXPECT_EQ(queue1.Front(), queue2.front());
+            }
+
+            if (queue2.empty() || rng() % 2 == 0) {
+                int value = rng() % 1'000'000;
+                queue1.Push(value);
+                queue2.push(value);
+            } else {
+                queue1.Pop();
+                queue2.pop();
+            }
+        }
+    }
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace
+} // namespace NYT