1 files changed, 230 insertions, 0 deletions
diff --git a/zen/ring_buffer.h b/zen/ring_buffer.h
new file mode 100755
index 00000000..1a67c452
--- /dev/null
+++ b/zen/ring_buffer.h
@@ -0,0 +1,230 @@
+// *****************************************************************************
+// * This file is part of the FreeFileSync project. It is distributed under    *
+// * GNU General Public License: https://www.gnu.org/licenses/gpl-3.0          *
+// * Copyright (C) Zenju (zenju AT freefilesync DOT org) - All Rights Reserved *
+// *****************************************************************************
+
+#ifndef RING_BUFFER_H_01238467085684139453534
+#define RING_BUFFER_H_01238467085684139453534
+
+#include <cassert>
+#include <vector>
+#include <stdexcept>
+#include "type_traits.h"
+#include "scope_guard.h"
+
+
+namespace zen
+{
+//basically a std::deque<> but with a non-garbage implementation => circular buffer with std::vector<>-like exponential growth!
+//https://stackoverflow.com/questions/39324192/why-is-an-stl-deque-not-implemented-as-just-a-circular-vector
+
+template <class T>
+class RingBuffer
+{
+public:
+    RingBuffer() {}
+
+    RingBuffer(RingBuffer&& tmp) noexcept : rawMem_(std::move(tmp.rawMem_)), capacity_(tmp.capacity_), bufStart_(tmp.bufStart_), size_(tmp.size_)
+    {
+        tmp.capacity_ = tmp.bufStart_ = tmp.size_ = 0;
+    }
+    RingBuffer& operator=(RingBuffer&& tmp) noexcept { swap(tmp); return *this; } //noexcept *required* to support move for reallocations in std::vector and std::swap!!!
+
+    using value_type      = T;
+    using reference       = T&;
+    using const_reference = const T&;
+
+    size_t size() const { return size_; }
+    bool  empty() const { return size_ == 0; }
+
+    ~RingBuffer() { clear(); }
+
+    reference       front()       { return getBufPtr()[bufStart_]; }
+    const_reference front() const { return getBufPtr()[bufStart_]; }
+
+    template <class U>
+    void push_back(U&& value)
+    {
+        checkInvariants();
+        reserve(size_ + 1); //throw ?
+        ::new (getBufPtr() + getBufPos(size_)) T(std::forward<U>(value)); //throw ?
+        ++size_;
+    }
+
+    void pop_front()
+    {
+        checkInvariants();
+        if (empty())
+            throw std::logic_error("Contract violation! " + std::string(__FILE__) + ":" + numberTo<std::string>(__LINE__));
+
+        front().~T();
+        ++bufStart_;
+        --size_;
+
+        if (size_ == 0 || bufStart_ == capacity_)
+            bufStart_ = 0;
+    }
+
+    void clear()
+    {
+        checkInvariants();
+
+        const size_t frontSize = std::min(size_, capacity_ - bufStart_);
+
+        std::destroy(getBufPtr() + bufStart_, getBufPtr() + bufStart_ + frontSize);
+        std::destroy(getBufPtr(), getBufPtr() + size_ - frontSize);
+        bufStart_ = size_ = 0;
+    }
+
+    template <class Iterator>
+    void insert_back(Iterator first, Iterator last) //throw ? (strong exception-safety!)
+    {
+        checkInvariants();
+
+        const size_t len = last - first;
+        reserve(size_ + len); //throw ?
+
+        const size_t endPos = getBufPos(size_);
+        const size_t tailSize = std::min(len, capacity_ - endPos);
+
+        std::uninitialized_copy(first, first + tailSize, getBufPtr() + endPos); //throw ?
+        ZEN_ON_SCOPE_FAIL(std::destroy(first, first + tailSize));
+        std::uninitialized_copy(first + tailSize, last, getBufPtr()); //throw ?
+
+        size_ += len;
+    }
+
+    //contract: last - first <= size()
+    template <class Iterator>
+    void extract_front(Iterator first, Iterator last) //throw ? strongly exception-safe! (but only basic exception safety for [first, last) range)
+    {
+        checkInvariants();
+
+        const size_t len = last - first;
+        if (size_ < len)
+            throw std::logic_error("Contract violation! " + std::string(__FILE__) + ":" + numberTo<std::string>(__LINE__));
+
+        const size_t frontSize = std::min(len, capacity_ - bufStart_);
+
+        auto itTrg = std::copy(getBufPtr() + bufStart_, getBufPtr() + bufStart_ + frontSize, first); //throw ?
+        /**/         std::copy(getBufPtr(), getBufPtr() + len - frontSize, itTrg);                   //
+
+        std::destroy(getBufPtr() + bufStart_, getBufPtr() + bufStart_ + frontSize);
+        std::destroy(getBufPtr(), getBufPtr() + len - frontSize);
+
+        bufStart_ += len;
+        size_   -= len;
+
+        if (size_ == 0)
+            bufStart_ = 0;
+        else if (bufStart_ >= capacity_)
+            bufStart_ -= capacity_;
+    }
+
+    void swap(RingBuffer& other)
+    {
+        std::swap(rawMem_,   other.rawMem_);
+        std::swap(capacity_, other.capacity_);
+        std::swap(bufStart_, other.bufStart_);
+        std::swap(size_,     other.size_);
+    }
+
+    void reserve(size_t minSize) //throw ? (strong exception-safety!)
+    {
+        if (minSize > capacity_)
+        {
+            const size_t newCapacity = std::max(minSize + minSize / 2, minSize); //no minimum capacity: just like std::vector<> implementation
+
+            RingBuffer newBuf(newCapacity); //throw ?
+
+            T* itTrg = reinterpret_cast<T*>(newBuf.rawMem_.get());
+
+            const size_t frontSize = std::min(size_, capacity_ - bufStart_);
+
+            itTrg = uninitializedMoveIfNoexcept(getBufPtr() + bufStart_, getBufPtr() + bufStart_ + frontSize, itTrg); //throw ?
+            newBuf.size_ = frontSize; //pass ownership
+            /**/    uninitializedMoveIfNoexcept(getBufPtr(), getBufPtr() + size_ - frontSize, itTrg); //throw ?
+            newBuf.size_ = size_;     //
+
+            newBuf.swap(*this);
+        }
+    }
+
+    const T& operator[](size_t offset) const
+    {
+        assert(offset < size()); //design by contract! no runtime check!
+        return getBufPtr()[getBufPos(offset)];
+    }
+
+    T& operator[](size_t offset) { return const_cast<T&>(static_cast<const RingBuffer*>(this)->operator[](offset)); }
+
+    template <class Container, class Value>
+    class Iterator
+    {
+    public:
+        Iterator(Container& container, size_t offset) : container_(&container), offset_(offset) {}
+        Iterator& operator++() { ++offset_; return *this; }
+        inline friend bool operator==(const Iterator& lhs, const Iterator& rhs) { assert(lhs.container_ == rhs.container_); return lhs.offset_ == rhs.offset_; }
+        inline friend bool operator!=(const Iterator& lhs, const Iterator& rhs) { return !(lhs == rhs); }
+        Value& operator* () const { return  (*container_)[offset_]; }
+        Value* operator->() const { return &(*container_)[offset_]; }
+    private:
+        Container* container_ = nullptr;
+        size_t offset_ = 0;
+    };
+    using iterator        = Iterator<      RingBuffer,       T>;
+    using const_iterator  = Iterator<const RingBuffer, const T>;
+
+    iterator begin() { return { *this, 0     }; }
+    iterator end  () { return { *this, size_ }; }
+
+    const_iterator begin() const { return { *this, 0     }; }
+    const_iterator end  () const { return { *this, size_ }; }
+
+    const_iterator cbegin() const { return begin(); }
+    const_iterator cend  () const { return end  (); }
+
+private:
+    RingBuffer           (const RingBuffer&) = delete; //wait until there is a reason to copy a RingBuffer
+    RingBuffer& operator=(const RingBuffer&) = delete; //
+
+    RingBuffer(size_t capacity) :
+        rawMem_(static_cast<std::byte*>(::operator new (capacity * sizeof(T)))), //throw std::bad_alloc
+        capacity_(capacity) {}
+
+    struct FreeStoreDelete { void operator()(std::byte* p) const { ::operator delete (p); } };
+
+    T*       getBufPtr()       { return reinterpret_cast<T*>(rawMem_.get()); }
+    const T* getBufPtr() const { return reinterpret_cast<T*>(rawMem_.get()); }
+
+    //unlike pure std::uninitialized_move, this one allows for strong exception-safety!
+    static T* uninitializedMoveIfNoexcept(T* first, T* last, T* firstTrg)
+    {
+        return uninitializedMoveIfNoexcept(first, last, firstTrg, std::is_nothrow_move_constructible<T>());
+    }
+    static T* uninitializedMoveIfNoexcept(T* first, T* last, T* firstTrg, std::true_type ) { return std::uninitialized_move(first, last, firstTrg); }
+    static T* uninitializedMoveIfNoexcept(T* first, T* last, T* firstTrg, std::false_type) { return std::uninitialized_copy(first, last, firstTrg); } //throw ?
+
+    void checkInvariants()
+    {
+        assert(bufStart_ == 0 || bufStart_ < capacity_);
+        assert(size_ <= capacity_);
+    }
+
+    size_t getBufPos(size_t offset) const //< capacity_
+    {
+        size_t bufPos = bufStart_ + offset;
+        if (bufPos >= capacity_)
+            bufPos -= capacity_;
+        return bufPos;
+    }
+
+    std::unique_ptr<std::byte, FreeStoreDelete> rawMem_;
+    size_t capacity_  = 0; //as number of T
+    size_t bufStart_  = 0; //<  capacity_
+    size_t size_      = 0; //<= capacity_
+};
+}
+
+#endif //RING_BUFFER_H_01238467085684139453534