YT-18655 Support prerequisite transactions in dynamic tables write

We are building a service that uses dynamic tables as a metadata storage. Cypress is used for a leader election and prerequisite transactions are used to prevent races, however prerequisite transactions are not supported for dynamic table operations. This PR fixes that.

I hereby agree to the terms of the CLA available at: https://yandex.ru/legal/cla/?lang=en

---

Pull Request resolved: https://github.com/ytsaurus/ytsaurus/pull/162

1 files changed, 71 insertions, 0 deletions

diff --git a/library/cpp/yt/small_containers/compact_queue-inl.h b/library/cpp/yt/small_containers/compact_queue-inl.h
new file mode 100644
index 0000000000..6e085ab260
--- /dev/null
+++ b/library/cpp/yt/small_containers/compact_queue-inl.h
@@ -0,0 +1,71 @@
+#include "compact_queue.h"
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <class T, size_t N>
+void TCompactQueue<T, N>::Push(T value)
+{
+    if (Size_ == Queue_.size()) {
+        auto oldSize = Queue_.size();
+        Queue_.resize(2 * oldSize);
+
+        if (FrontIndex_ + Size_ > oldSize) {
+            std::move(
+                Queue_.begin(),
+                Queue_.begin() + FrontIndex_,
+                Queue_.begin() + Size_);
+        }
+    }
+
+    auto index = FrontIndex_ + Size_;
+    if (index >= Queue_.size()) {
+        index -= Queue_.size();
+    }
+    Queue_[index] = std::move(value);
+    ++Size_;
+}
+
+template <class T, size_t N>
+T TCompactQueue<T, N>::Pop()
+{
+    YT_VERIFY(!Empty());
+
+    auto value = std::move(Queue_[FrontIndex_]);
+    ++FrontIndex_;
+    if (FrontIndex_ >= Queue_.size()) {
+        FrontIndex_ -= Queue_.size();
+    }
+    --Size_;
+
+    return value;
+}
+
+template <class T, size_t N>
+const T& TCompactQueue<T, N>::Front() const
+{
+    return Queue_[FrontIndex_];
+}
+
+template <class T, size_t N>
+size_t TCompactQueue<T, N>::Size() const
+{
+    return Size_;
+}
+
+template <class T, size_t N>
+size_t TCompactQueue<T, N>::Capacity() const
+{
+    return Queue_.capacity();
+}
+
+template <class T, size_t N>
+bool TCompactQueue<T, N>::Empty() const
+{
+    return Size_ == 0;
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT