1 files changed, 191 insertions, 0 deletions
diff --git a/src/brussel.common/RingBuffer.hpp b/src/brussel.common/RingBuffer.hpp
new file mode 100644
index 0000000..4eaa007
--- /dev/null
+++ b/src/brussel.common/RingBuffer.hpp
@@ -0,0 +1,191 @@
+#pragma once
+
+#include <algorithm>
+#include <cassert>
+#include <cstddef>
+#include <iterator>
+
+class RingBufferSentinel {};
+
+template <typename TContainer>
+class RingBufferIterator {
+public:
+	using difference_type = TContainer::difference_type;
+	using value_type = TContainer::value_type; // C++20 relaxed usage requirements of `typename`, now locations where a type is required (like here in a using statement) it's no longer mandatory
+	using pointer = value_type*;
+	using reference = value_type&;
+	using iterator_category = std::random_access_iterator_tag;
+
+public:
+	TContainer* container;
+	TContainer::size_type curr; // C++20 relaxed usage requirements of `typename`, same here
+	bool needsWrapAround;
+	bool hasWrappedAround = false;
+
+public:
+	reference operator*() const {
+		return container->mRing[curr];
+	}
+
+	RingBufferIterator& operator++() {
+		assert(*this != RingBufferSentinel{});
+		++curr;
+		if (needsWrapAround && curr == container->mCapacity) {
+			hasWrappedAround = true;
+			curr = 0;
+		}
+		return *this;
+	}
+
+	bool operator==(const RingBufferIterator& that) const {
+		assert(this->container == that.container);
+		return this->curr == that.curr;
+	}
+
+	bool operator==(const RingBufferSentinel&) const {
+		return curr == container->mTailIdx && (!needsWrapAround || hasWrappedAround);
+	}
+};
+
+template <typename T>
+class RingBuffer {
+public:
+	using value_type = T;
+	using reference = T&;
+	using const_reference = const T&;
+	friend class RingBufferIterator<RingBuffer>;
+	using iterator = RingBufferIterator<RingBuffer>;
+	friend class RingBufferIterator<const RingBuffer>;
+	using const_iterator = RingBufferIterator<const RingBuffer>;
+	using sentinel = RingBufferSentinel; // Not a part of C++'s Container named requirements, added here for convenience
+	using difference_type = ptrdiff_t;
+	using size_type = size_t;
+
+private:
+	T* mRing = nullptr;
+	size_type mHeadIdx = 0;
+	size_type mTailIdx = 0;
+	size_type mCapacity = 0;
+	size_type mSize = 0;
+
+public:
+	RingBuffer() noexcept = default;
+
+	~RingBuffer() noexcept {
+		delete[] mRing;
+	}
+
+	RingBuffer(const RingBuffer&) noexcept = delete;
+	RingBuffer& operator=(const RingBuffer&) noexcept = delete;
+
+	RingBuffer(RingBuffer&& that) noexcept
+		: mRing{ that.mRing }
+		, mHeadIdx{ that.mHeadIdx }
+		, mTailIdx{ that.mTailIdx }
+		, mCapacity{ that.mCapacity }
+		, mSize{ that.mSize } {
+		that.mRing = nullptr;
+	}
+
+	RingBuffer& operator=(RingBuffer&& that) noexcept {
+		if (this != &that) {
+			auto oldThisRing = this->mRing;
+			this->mRing = that.mRing;
+			that.mRing = nullptr;
+			delete oldThisRing;
+
+			this->mHeadIdx = that.mHeadIdx;
+			this->mTailIdx = that.mTailIdx;
+			this->mCapacity = that.mCapacity;
+			this->mSize = that.mSize;
+		}
+
+		return *this;
+	}
+
+	[[nodiscard]] iterator begin() {
+		return {
+			.container = this,
+			.curr = mHeadIdx,
+			.needsWrapAround = mHeadIdx >= mTailIdx,
+		};
+	}
+
+	[[nodiscard]] const_iterator begin() const { return cbegin(); }
+
+	// Same type for both const this and non-const `this`
+	[[nodiscard]] sentinel end() const { return sentinel{}; }
+
+	[[nodiscard]] const_iterator cbegin() const {
+		return {
+			.container = this,
+			.curr = mHeadIdx,
+			.needsWrapAround = mHeadIdx >= mTailIdx,
+		};
+	}
+
+	[[nodiscard]] sentinel cend() const { return sentinel{}; }
+
+	[[nodiscard]] T& operator[](size_type i) { return const_cast<T&>(const_cast<const RingBuffer&>(*this)[i]); }
+	[[nodiscard]] const T& operator[](size_type i) const {
+		assert(mRing != nullptr);
+		size_type idx = mHeadIdx + i;
+		if (idx >= mCapacity) {
+			idx -= mCapacity;
+		}
+		return mRing[idx];
+	}
+
+	void push_back(T t) {
+		assert(mRing != nullptr);
+		if (mTailIdx == mCapacity) {
+			// Ring buffer is filled to the right, warp around to the beginning
+			// mHeadIdx > 0 must be true, since we checked that as condition (1) above
+			mRing[0] = std::move(t);
+			mTailIdx = 1;
+		} else {
+			mRing[mTailIdx] = std::move(t);
+			mTailIdx += 1;
+		}
+
+		// Push mHeadIdx backwards if overwrote element in a filled buffer
+		bool bufferFilled = mSize == mCapacity;
+		if (bufferFilled && mTailIdx > mHeadIdx) {
+			mHeadIdx += 1;
+			if (mHeadIdx == mCapacity) {
+				mHeadIdx = 0;
+			}
+		}
+
+		if (!bufferFilled) {
+			++mSize;
+		}
+	}
+
+	[[nodiscard]] size_type capacity() const {
+		return mCapacity;
+	}
+
+	[[nodiscard]] size_type size() const {
+		return mSize;
+	}
+
+	[[nodiscard]] T* GetBuffer() const { return mRing; }
+	[[nodiscard]] size_type GetHeadIdx() const { return mHeadIdx; }
+	[[nodiscard]] size_type GetTailIdx() const { return mTailIdx; }
+
+	void resize(size_type newCapacity) {
+		auto size = this->size();
+
+		auto oldRing = mRing;
+		auto newRing = mRing = new T[newCapacity];
+		if (oldRing != nullptr) {
+			std::rotate_copy(oldRing, oldRing + mHeadIdx, oldRing + mCapacity, newRing);
+			delete[] oldRing;
+		}
+
+		mCapacity = newCapacity;
+		mHeadIdx = 0;
+		mTailIdx = size;
+	}
+};