1 files changed, 556 insertions, 0 deletions
diff --git a/library/cpp/yt/memory/range.h b/library/cpp/yt/memory/range.h
new file mode 100644
index 0000000000..6c71aa9496
--- /dev/null
+++ b/library/cpp/yt/memory/range.h
@@ -0,0 +1,556 @@
+#pragma once
+
+#include <library/cpp/yt/assert/assert.h>
+
+#include <library/cpp/yt/misc/hash.h>
+
+#include <vector>
+#include <array>
+#include <optional>
+#include <initializer_list>
+
+// For size_t.
+#include <stddef.h>
+
+namespace google::protobuf {
+
+////////////////////////////////////////////////////////////////////////////////
+// Forward declarations
+
+template <class T>
+class RepeatedField;
+
+template <class T>
+class RepeatedPtrField;
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace google::protobuf
+
+namespace NYT {
+
+////////////////////////////////////////////////////////////////////////////////
+// Forward declarations
+
+template <class T, size_t N>
+class TCompactVector;
+
+////////////////////////////////////////////////////////////////////////////////
+
+//! TRange (inspired by TArrayRef from LLVM)
+/*!
+ * Represents a constant reference to an array (zero or more elements
+ * consecutively in memory), i. e. a start pointer and a length. It allows
+ * various APIs to take consecutive elements easily and conveniently.
+ *
+ * This class does not own the underlying data, it is expected to be used in
+ * situations where the data resides in some other buffer, whose lifetime
+ * extends past that of the TRange. For this reason, it is not in general
+ * safe to store an TRange.
+ *
+ * This is intended to be trivially copyable, so it should be passed by
+ * value.
+ */
+template <class T>
+class TRange
+{
+public:
+    typedef const T* iterator;
+    typedef const T* const_iterator;
+    typedef size_t size_type;
+
+    //! Constructs a null TRange.
+    TRange()
+        : Data_(nullptr)
+        , Length_(0)
+    { }
+
+    //! Constructs a TRange from a pointer and length.
+    TRange(const T* data, size_t length)
+        : Data_(data)
+        , Length_(length)
+    { }
+
+    //! Constructs a TRange from a range.
+    TRange(const T* begin, const T* end)
+        : Data_(begin)
+        , Length_(end - begin)
+    { }
+
+    //! Constructs a TRange from a TCompactVector.
+    template <size_t N>
+    TRange(const TCompactVector<T, N>& elements)
+        : Data_(elements.data())
+        , Length_(elements.size())
+    { }
+
+    //! Constructs a TRange from an std::vector.
+    template <class A>
+    TRange(const std::vector<T, A>& elements)
+        : Data_(elements.empty() ? nullptr : elements.data())
+        , Length_(elements.size())
+    { }
+
+    //! Constructs a TRange from a C array.
+    template <size_t N>
+    TRange(const T (&elements)[N])
+        : Data_(elements)
+        , Length_(N)
+    { }
+
+    //! Constructs a TRange from std::initializer_list.
+    TRange(std::initializer_list<T> elements)
+        : Data_(elements.begin())
+        , Length_(elements.size())
+    { }
+
+    //! Constructs a TRange from std::array.
+    template <size_t N>
+    TRange(const std::array<T, N>& elements)
+        : Data_(elements.data())
+        , Length_(N)
+    { }
+
+    //! Constructs a TRange from std::optional.
+    //! Range will contain 0-1 elements.
+    explicit TRange(const std::optional<T>& element)
+        : Data_(element ? &*element : nullptr)
+        , Length_(element ? 1 : 0)
+    { }
+
+    const_iterator Begin() const
+    {
+        return Data_;
+    }
+
+    // STL interop, for gcc.
+    const_iterator begin() const
+    {
+        return Begin();
+    }
+
+    const_iterator End() const
+    {
+        return Data_ + Length_;
+    }
+
+    // STL interop, for gcc.
+    const_iterator end() const
+    {
+        return End();
+    }
+
+    bool Empty() const
+    {
+        return Length_ == 0;
+    }
+
+    bool empty() const
+    {
+        return Empty();
+    }
+
+    explicit operator bool() const
+    {
+        return Data_ != nullptr;
+    }
+
+    size_t Size() const
+    {
+        return Length_;
+    }
+
+    size_t size() const
+    {
+        return Size();
+    }
+
+    const T& operator[](size_t index) const
+    {
+        YT_ASSERT(index < Size());
+        return Data_[index];
+    }
+
+
+    const T& Front() const
+    {
+        YT_ASSERT(Length_ > 0);
+        return Data_[0];
+    }
+
+    const T& Back() const
+    {
+        YT_ASSERT(Length_ > 0);
+        return Data_[Length_ - 1];
+    }
+
+
+    TRange<T> Slice(size_t startOffset, size_t endOffset) const
+    {
+        YT_ASSERT(startOffset <= endOffset && endOffset <= Size());
+        return TRange<T>(Begin() + startOffset, endOffset - startOffset);
+    }
+
+    std::vector<T> ToVector() const
+    {
+        return std::vector<T>(Data_, Data_ + Length_);
+    }
+
+protected:
+    //! The start of the array, in an external buffer.
+    const T* Data_;
+
+    //! The number of elements.
+    size_t Length_;
+
+};
+
+// STL interop.
+template <class T>
+typename TRange<T>::const_iterator begin(TRange<T> ref)
+{
+    return ref.Begin();
+}
+
+template <class T>
+typename TRange<T>::const_iterator end(TRange<T> ref)
+{
+    return ref.End();
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+//! Constructs a TRange from a pointer and length.
+template <class T>
+TRange<T> MakeRange(const T* data, size_t length)
+{
+    return TRange<T>(data, length);
+}
+
+//! Constructs a TRange from a native range.
+template <class T>
+TRange<T> MakeRange(const T* begin, const T* end)
+{
+    return TRange<T>(begin, end);
+}
+
+//! Constructs a TRange from a TCompactVector.
+template <class T, size_t N>
+TRange<T> MakeRange(const TCompactVector<T, N>& elements)
+{
+    return elements;
+}
+
+//! "Copy-constructor".
+template <class T>
+TRange<T> MakeRange(TRange<T> range)
+{
+    return range;
+}
+
+//! Constructs a TRange from an std::vector.
+template <class T>
+TRange<T> MakeRange(const std::vector<T>& elements)
+{
+    return elements;
+}
+
+//! Constructs a TRange from an std::array.
+template <class T, size_t N>
+TRange<T> MakeRange(const std::array<T, N>& elements)
+{
+    return elements;
+}
+
+//! Constructs a TRange from a C array.
+template <class T, size_t N>
+TRange<T> MakeRange(const T (& elements)[N])
+{
+    return TRange<T>(elements);
+}
+
+//! Constructs a TRange from RepeatedField.
+template <class T>
+TRange<T> MakeRange(const google::protobuf::RepeatedField<T>& elements)
+{
+    return TRange<T>(elements.data(), elements.size());
+}
+
+//! Constructs a TRange from RepeatedPtrField.
+template <class T>
+TRange<const T*> MakeRange(const google::protobuf::RepeatedPtrField<T>& elements)
+{
+    return TRange<const T*>(elements.data(), elements.size());
+}
+
+template <class U, class T>
+TRange<U> ReinterpretCastRange(TRange<T> range)
+{
+    static_assert(sizeof(T) == sizeof(U), "T and U must have equal sizes.");
+    return TRange<U>(reinterpret_cast<const U*>(range.Begin()), range.Size());
+};
+
+////////////////////////////////////////////////////////////////////////////////
+
+// TMutableRange (inspired by TMutableArrayRef from LLVM)
+/*
+ * Represents a mutable reference to an array (zero or more elements
+ * consecutively in memory), i. e. a start pointer and a length.
+ * It allows various APIs to take and modify consecutive elements easily and
+ * conveniently.
+ *
+ * This class does not own the underlying data, it is expected to be used in
+ * situations where the data resides in some other buffer, whose lifetime
+ * extends past that of the TMutableRange. For this reason, it is not in
+ * general safe to store a TMutableRange.
+ *
+ * This is intended to be trivially copyable, so it should be passed by value.
+ */
+template <class T>
+class TMutableRange
+    : public TRange<T>
+{
+public:
+    typedef T* iterator;
+
+    //! Constructs a null TMutableRange.
+    TMutableRange()
+    { }
+
+    //! Constructs a TMutableRange from a pointer and length.
+    TMutableRange(T* data, size_t length)
+        : TRange<T>(data, length)
+    { }
+
+    //! Constructs a TMutableRange from a range.
+    TMutableRange(T* begin, T* end)
+        : TRange<T>(begin, end)
+    { }
+
+    //! Constructs a TMutableRange from a TCompactVector.
+    template <size_t N>
+    TMutableRange(TCompactVector<T, N>& elements)
+        : TRange<T>(elements)
+    { }
+
+    //! Constructs a TMutableRange from an std::vector.
+    TMutableRange(std::vector<T>& elements)
+        : TRange<T>(elements)
+    { }
+
+    //! Constructs a TMutableRange from std::array.
+    template <size_t N>
+    TMutableRange(std::array<T, N>& elements)
+        : TRange<T>(elements.data(), N)
+    { }
+
+    //! Construct a TMutableRange from an std::optional
+    //! Range will contain 0-1 elements.
+    explicit TMutableRange(std::optional<T>& optional)
+        : TRange<T>(optional)
+    { }
+
+    //! Constructs a TMutableRange from a C array.
+    template <size_t N>
+    TMutableRange(T (& elements)[N])
+        : TRange<T>(elements)
+    { }
+
+    using TRange<T>::Begin;
+    using TRange<T>::End;
+    using TRange<T>::Front;
+    using TRange<T>::Back;
+    using TRange<T>::operator[];
+
+    iterator Begin() const
+    {
+        return const_cast<T*>(this->Data_);
+    }
+
+    // STL interop, for gcc.
+    iterator begin() const
+    {
+        return Begin();
+    }
+
+    iterator End() const
+    {
+        return this->Begin() + this->Size();
+    }
+
+    // STL interop, for gcc.
+    iterator end() const
+    {
+        return End();
+    }
+
+    T& operator[](size_t index)
+    {
+        YT_ASSERT(index <= this->Size());
+        return Begin()[index];
+    }
+
+    T& Front()
+    {
+        YT_ASSERT(this->Length_ > 0);
+        return Begin()[0];
+    }
+
+    T& Back()
+    {
+        YT_ASSERT(this->Length_ > 0);
+        return Begin()[this->Length_ - 1];
+    }
+
+    TMutableRange<T> Slice(size_t startOffset, size_t endOffset) const
+    {
+        YT_ASSERT(startOffset <= endOffset && endOffset <= this->Size());
+        return TMutableRange<T>(Begin() + startOffset, endOffset - startOffset);
+    }
+
+    TMutableRange<T> Slice(T* begin, T* end) const
+    {
+        YT_ASSERT(begin >= Begin());
+        YT_ASSERT(end <= End());
+        return TMutableRange<T>(begin, end);
+    }
+};
+
+// STL interop.
+template <class T>
+typename TMutableRange<T>::iterator begin(TMutableRange<T> ref)
+{
+    return ref.Begin();
+}
+
+template <class T>
+typename TMutableRange<T>::iterator end(TMutableRange<T> ref)
+{
+    return ref.End();
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+//! Constructs a TMutableRange from a pointer and length.
+template <class T>
+TMutableRange<T> MakeMutableRange(T* data, size_t length)
+{
+    return TMutableRange<T>(data, length);
+}
+
+//! Constructs a TMutableRange from a native range.
+template <class T>
+TMutableRange<T> MakeMutableRange(T* begin, T* end)
+{
+    return TMutableRange<T>(begin, end);
+}
+
+//! Constructs a TMutableRange from a TCompactVector.
+template <class T, size_t N>
+TMutableRange<T> MakeMutableRange(TCompactVector<T, N>& elements)
+{
+    return elements;
+}
+
+//! "Copy-constructor".
+template <class T>
+TMutableRange<T> MakeMutableRange(TMutableRange<T> range)
+{
+    return range;
+}
+
+//! Constructs a TMutableRange from an std::vector.
+template <class T>
+TMutableRange<T> MakeMutableRange(std::vector<T>& elements)
+{
+    return elements;
+}
+
+//! Constructs a TMutableRange from an std::array.
+template <class T, size_t N>
+TMutableRange<T> MakeMutableRange(std::array<T, N>& elements)
+{
+    return elements;
+}
+
+//! Constructs a TMutableRange from a C array.
+template <class T, size_t N>
+TMutableRange<T> MakeMutableRange(T (& elements)[N])
+{
+    return TMutableRange<T>(elements);
+}
+
+//! Constructs a TMutableRange from RepeatedField.
+template <class T>
+TMutableRange<T> MakeMutableRange(google::protobuf::RepeatedField<T>& elements)
+{
+    return TMutableRange<T>(elements.data(), elements.size());
+}
+
+//! Constructs a TMutableRange from RepeatedPtrField.
+template <class T>
+TMutableRange<T*> MakeMutableRange(google::protobuf::RepeatedPtrField<T>& elements)
+{
+    return TMutableRange<const T*>(elements.data(), elements.size());
+}
+
+template <class U, class T>
+TMutableRange<U> ReinterpretCastMutableRange(TMutableRange<T> range)
+{
+    static_assert(sizeof(T) == sizeof(U), "T and U must have equal sizes.");
+    return TMutableRange<U>(reinterpret_cast<U*>(range.Begin()), range.Size());
+}
+
+////////////////////////////////////////////////////////////////////////////////
+
+// Mark TMutableRange and TMutableRange as PODs.
+namespace NMpl {
+
+template <class T>
+struct TIsPod;
+
+template <class T>
+struct TIsPod<TRange<T>>
+{
+    static const bool Value = true;
+};
+
+template <class T>
+struct TIsPod<TMutableRange<T>>
+{
+    static const bool Value = true;
+};
+
+} // namespace NMpl
+
+////////////////////////////////////////////////////////////////////////////////
+
+} // namespace NYT
+
+template <class T>
+struct hash<NYT::TRange<T>>
+{
+    size_t operator()(const NYT::TRange<T>& range) const
+    {
+        size_t result = 0;
+        for (const auto& element : range) {
+            NYT::HashCombine(result, element);
+        }
+        return result;
+    }
+};
+
+template <class T>
+struct hash<NYT::TMutableRange<T>>
+{
+    size_t operator()(const NYT::TMutableRange<T>& range) const
+    {
+        size_t result = 0;
+        for (const auto& element : range) {
+            NYT::HashCombine(result, element);
+        }
+        return result;
+    }
+};
+
+