include/input/RingBuffer.h - platform/frameworks/native - Git at Google

 /*
  * Copyright (C) 2023 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #pragma once

 #include <algorithm>
 #include <compare>
 #include <cstddef>
 #include <iterator>
 #include <memory>
 #include <type_traits>
 #include <utility>

 #include <android-base/stringprintf.h>

 namespace android {

 // A fixed-size ring buffer of elements.
 //
 // Elements can only be removed from the front/back or added to the front/back, but with O(1)
 // performance. Elements from the opposing side are evicted when new elements are pushed onto a full
 // buffer.
 template <typename T>
 class RingBuffer {
 public:
     using value_type = T;
     using size_type = size_t;
     using difference_type = ptrdiff_t;
     using reference = value_type&;
     using const_reference = const value_type&;
     using pointer = value_type*;
     using const_pointer = const value_type*;

     template <typename U>
     class Iterator;
     using iterator = Iterator<T>;
     using const_iterator = Iterator<const T>;

     // Creates an empty ring buffer that can hold some capacity.
     explicit RingBuffer(size_type capacity)
           : mBuffer(std::allocator<value_type>().allocate(capacity)), mCapacity(capacity) {}

     // Creates a full ring buffer holding a fixed number of elements initialised to some value.
     explicit RingBuffer(size_type count, const_reference value) : RingBuffer(count) {
         while (count) {
             pushBack(value);
             --count;
         }
     }

     RingBuffer(const RingBuffer& other) : RingBuffer(other.capacity()) {
         for (const auto& element : other) {
             pushBack(element);
         }
     }

     RingBuffer(RingBuffer&& other) noexcept { *this = std::move(other); }

     ~RingBuffer() {
         if (mBuffer) {
             clear();
             std::allocator<value_type>().deallocate(mBuffer, mCapacity);
         }
     }

     RingBuffer& operator=(const RingBuffer& other) { return *this = RingBuffer(other); }

     RingBuffer& operator=(RingBuffer&& other) noexcept {
         if (this == &other) {
             return *this;
         }
         if (mBuffer) {
             clear();
             std::allocator<value_type>().deallocate(mBuffer, mCapacity);
         }
         mBuffer = std::move(other.mBuffer);
         mCapacity = other.mCapacity;
         mBegin = other.mBegin;
         mSize = other.mSize;
         other.mBuffer = nullptr;
         other.mCapacity = 0;
         other.mBegin = 0;
         other.mSize = 0;
         return *this;
     }

     iterator begin() { return {*this, 0}; }
     const_iterator begin() const { return {*this, 0}; }
     iterator end() { return {*this, mSize}; }
     const_iterator end() const { return {*this, mSize}; }

     reference front() { return mBuffer[mBegin]; }
     const_reference front() const { return mBuffer[mBegin]; }
     reference back() { return mBuffer[bufferIndex(mSize - 1)]; }
     const_reference back() const { return mBuffer[bufferIndex(mSize - 1)]; }

     reference operator[](size_type i) { return mBuffer[bufferIndex(i)]; }
     const_reference operator[](size_type i) const { return mBuffer[bufferIndex(i)]; }

     // Removes all elements from the buffer.
     void clear() {
         std::destroy(begin(), end());
         mSize = 0;
     }

     // Removes and returns the first element from the buffer.
     value_type popFront() {
         value_type element = mBuffer[mBegin];
         std::destroy_at(std::addressof(mBuffer[mBegin]));
         mBegin = next(mBegin);
         --mSize;
         return element;
     }

     // Removes and returns the last element from the buffer.
     value_type popBack() {
         size_type backIndex = bufferIndex(mSize - 1);
         value_type element = mBuffer[backIndex];
         std::destroy_at(std::addressof(mBuffer[backIndex]));
         --mSize;
         return element;
     }

     // Adds an element to the front of the buffer.
     void pushFront(const value_type& element) { pushFront(value_type(element)); }
     void pushFront(value_type&& element) {
         mBegin = previous(mBegin);
         if (size() == capacity()) {
             mBuffer[mBegin] = std::forward<value_type>(element);
         } else {
             // The space at mBuffer[mBegin] is uninitialised.
             // TODO: Use std::construct_at when it becomes available.
             new (std::addressof(mBuffer[mBegin])) value_type(std::forward<value_type>(element));
             ++mSize;
         }
     }

     // Adds an element to the back of the buffer.
     void pushBack(const value_type& element) { pushBack(value_type(element)); }
     void pushBack(value_type&& element) {
         if (size() == capacity()) {
             mBuffer[mBegin] = std::forward<value_type>(element);
             mBegin = next(mBegin);
         } else {
             // The space at mBuffer[...] is uninitialised.
             // TODO: Use std::construct_at when it becomes available.
             new (std::addressof(mBuffer[bufferIndex(mSize)]))
                     value_type(std::forward<value_type>(element));
             ++mSize;
         }
     }

     bool empty() const { return mSize == 0; }
     size_type capacity() const { return mCapacity; }
     size_type size() const { return mSize; }

     void swap(RingBuffer& other) noexcept {
         using std::swap;
         swap(mBuffer, other.mBuffer);
         swap(mCapacity, other.mCapacity);
         swap(mBegin, other.mBegin);
         swap(mSize, other.mSize);
     }

     friend void swap(RingBuffer& lhs, RingBuffer& rhs) noexcept { lhs.swap(rhs); }

     template <typename U>
     class Iterator {
     private:
         using ContainerType = std::conditional_t<std::is_const_v<U>, const RingBuffer, RingBuffer>;

     public:
         using iterator_category = std::random_access_iterator_tag;
         using size_type = ContainerType::size_type;
         using difference_type = ContainerType::difference_type;
         using value_type = std::remove_cv_t<U>;
         using pointer = U*;
         using reference = U&;

         Iterator(ContainerType& container, size_type index)
               : mContainer(container), mIndex(index) {}

         Iterator(const Iterator&) = default;
         Iterator& operator=(const Iterator&) = default;

         Iterator& operator++() {
             ++mIndex;
             return *this;
         }

         Iterator operator++(int) {
             Iterator iterator(*this);
             ++(*this);
             return iterator;
         }

         Iterator& operator--() {
             --mIndex;
             return *this;
         }

         Iterator operator--(int) {
             Iterator iterator(*this);
             --(*this);
             return iterator;
         }

         Iterator& operator+=(difference_type n) {
             mIndex += n;
             return *this;
         }

         Iterator operator+(difference_type n) {
             Iterator iterator(*this);
             return iterator += n;
         }

         Iterator& operator-=(difference_type n) { return *this += -n; }

         Iterator operator-(difference_type n) {
             Iterator iterator(*this);
             return iterator -= n;
         }

         difference_type operator-(const Iterator& other) { return mIndex - other.mIndex; }

         bool operator==(const Iterator& rhs) const { return mIndex == rhs.mIndex; }

         bool operator!=(const Iterator& rhs) const { return !(*this == rhs); }

         friend auto operator<=>(const Iterator& lhs, const Iterator& rhs) {
             return lhs.mIndex <=> rhs.mIndex;
         }

         reference operator[](difference_type n) { return *(*this + n); }

         reference operator*() const { return mContainer[mIndex]; }
         pointer operator->() const { return std::addressof(mContainer[mIndex]); }

     private:
         ContainerType& mContainer;
         size_type mIndex = 0;
     };

 private:
     // Returns the index of the next element in mBuffer.
     size_type next(size_type index) const {
         if (index == capacity() - 1) {
             return 0;
         } else {
             return index + 1;
         }
     }

     // Returns the index of the previous element in mBuffer.
     size_type previous(size_type index) const {
         if (index == 0) {
             return capacity() - 1;
         } else {
             return index - 1;
         }
     }

     // Converts the index of an element in [0, size()] to its corresponding index in mBuffer.
     size_type bufferIndex(size_type elementIndex) const {
         if (elementIndex > size()) {
             abort();
         }
         size_type index = mBegin + elementIndex;
         if (index >= capacity()) {
             index -= capacity();
         }
         if (index >= capacity()) {
             abort();
         }
         return index;
     }

     pointer mBuffer = nullptr;
     size_type mCapacity = 0; // Total capacity of mBuffer.
     size_type mBegin = 0;    // Index of the first initialised element in mBuffer.
     size_type mSize = 0;     // Total number of initialised elements.
 };

 } // namespace android
	/*
	* Copyright (C) 2023 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#pragma once

	#include <algorithm>
	#include <compare>
	#include <cstddef>
	#include <iterator>
	#include <memory>
	#include <type_traits>
	#include <utility>

	#include <android-base/stringprintf.h>

	namespace android {

	// A fixed-size ring buffer of elements.
	//
	// Elements can only be removed from the front/back or added to the front/back, but with O(1)
	// performance. Elements from the opposing side are evicted when new elements are pushed onto a full
	// buffer.
	template <typename T>
	class RingBuffer {
	public:
	using value_type = T;
	using size_type = size_t;
	using difference_type = ptrdiff_t;
	using reference = value_type&;
	using const_reference = const value_type&;
	using pointer = value_type*;
	using const_pointer = const value_type*;

	template <typename U>
	class Iterator;
	using iterator = Iterator<T>;
	using const_iterator = Iterator<const T>;

	// Creates an empty ring buffer that can hold some capacity.
	explicit RingBuffer(size_type capacity)
	: mBuffer(std::allocator<value_type>().allocate(capacity)), mCapacity(capacity) {}

	// Creates a full ring buffer holding a fixed number of elements initialised to some value.
	explicit RingBuffer(size_type count, const_reference value) : RingBuffer(count) {
	while (count) {
	pushBack(value);
	--count;
	}
	}

	RingBuffer(const RingBuffer& other) : RingBuffer(other.capacity()) {
	for (const auto& element : other) {
	pushBack(element);
	}
	}

	RingBuffer(RingBuffer&& other) noexcept { *this = std::move(other); }

	~RingBuffer() {
	if (mBuffer) {
	clear();
	std::allocator<value_type>().deallocate(mBuffer, mCapacity);
	}
	}

	RingBuffer& operator=(const RingBuffer& other) { return *this = RingBuffer(other); }

	RingBuffer& operator=(RingBuffer&& other) noexcept {
	if (this == &other) {
	return *this;
	}
	if (mBuffer) {
	clear();
	std::allocator<value_type>().deallocate(mBuffer, mCapacity);
	}
	mBuffer = std::move(other.mBuffer);
	mCapacity = other.mCapacity;
	mBegin = other.mBegin;
	mSize = other.mSize;
	other.mBuffer = nullptr;
	other.mCapacity = 0;
	other.mBegin = 0;
	other.mSize = 0;
	return *this;
	}

	iterator begin() { return {*this, 0}; }
	const_iterator begin() const { return {*this, 0}; }
	iterator end() { return {*this, mSize}; }
	const_iterator end() const { return {*this, mSize}; }

	reference front() { return mBuffer[mBegin]; }
	const_reference front() const { return mBuffer[mBegin]; }
	reference back() { return mBuffer[bufferIndex(mSize - 1)]; }
	const_reference back() const { return mBuffer[bufferIndex(mSize - 1)]; }

	reference operator[](size_type i) { return mBuffer[bufferIndex(i)]; }
	const_reference operator[](size_type i) const { return mBuffer[bufferIndex(i)]; }

	// Removes all elements from the buffer.
	void clear() {
	std::destroy(begin(), end());
	mSize = 0;
	}

	// Removes and returns the first element from the buffer.
	value_type popFront() {
	value_type element = mBuffer[mBegin];
	std::destroy_at(std::addressof(mBuffer[mBegin]));
	mBegin = next(mBegin);
	--mSize;
	return element;
	}

	// Removes and returns the last element from the buffer.
	value_type popBack() {
	size_type backIndex = bufferIndex(mSize - 1);
	value_type element = mBuffer[backIndex];
	std::destroy_at(std::addressof(mBuffer[backIndex]));
	--mSize;
	return element;
	}

	// Adds an element to the front of the buffer.
	void pushFront(const value_type& element) { pushFront(value_type(element)); }
	void pushFront(value_type&& element) {
	mBegin = previous(mBegin);
	if (size() == capacity()) {
	mBuffer[mBegin] = std::forward<value_type>(element);
	} else {
	// The space at mBuffer[mBegin] is uninitialised.
	// TODO: Use std::construct_at when it becomes available.
	new (std::addressof(mBuffer[mBegin])) value_type(std::forward<value_type>(element));
	++mSize;
	}
	}

	// Adds an element to the back of the buffer.
	void pushBack(const value_type& element) { pushBack(value_type(element)); }
	void pushBack(value_type&& element) {
	if (size() == capacity()) {
	mBuffer[mBegin] = std::forward<value_type>(element);
	mBegin = next(mBegin);
	} else {
	// The space at mBuffer[...] is uninitialised.
	// TODO: Use std::construct_at when it becomes available.
	new (std::addressof(mBuffer[bufferIndex(mSize)]))
	value_type(std::forward<value_type>(element));
	++mSize;
	}
	}

	bool empty() const { return mSize == 0; }
	size_type capacity() const { return mCapacity; }
	size_type size() const { return mSize; }

	void swap(RingBuffer& other) noexcept {
	using std::swap;
	swap(mBuffer, other.mBuffer);
	swap(mCapacity, other.mCapacity);
	swap(mBegin, other.mBegin);
	swap(mSize, other.mSize);
	}

	friend void swap(RingBuffer& lhs, RingBuffer& rhs) noexcept { lhs.swap(rhs); }

	template <typename U>
	class Iterator {
	private:
	using ContainerType = std::conditional_t<std::is_const_v<U>, const RingBuffer, RingBuffer>;

	public:
	using iterator_category = std::random_access_iterator_tag;
	using size_type = ContainerType::size_type;
	using difference_type = ContainerType::difference_type;
	using value_type = std::remove_cv_t<U>;
	using pointer = U*;
	using reference = U&;

	Iterator(ContainerType& container, size_type index)
	: mContainer(container), mIndex(index) {}

	Iterator(const Iterator&) = default;
	Iterator& operator=(const Iterator&) = default;

	Iterator& operator++() {
	++mIndex;
	return *this;
	}

	Iterator operator++(int) {
	Iterator iterator(*this);
	++(*this);
	return iterator;
	}

	Iterator& operator--() {
	--mIndex;
	return *this;
	}

	Iterator operator--(int) {
	Iterator iterator(*this);
	--(*this);
	return iterator;
	}

	Iterator& operator+=(difference_type n) {
	mIndex += n;
	return *this;
	}

	Iterator operator+(difference_type n) {
	Iterator iterator(*this);
	return iterator += n;
	}

	Iterator& operator-=(difference_type n) { return *this += -n; }

	Iterator operator-(difference_type n) {
	Iterator iterator(*this);
	return iterator -= n;
	}

	difference_type operator-(const Iterator& other) { return mIndex - other.mIndex; }

	bool operator==(const Iterator& rhs) const { return mIndex == rhs.mIndex; }

	bool operator!=(const Iterator& rhs) const { return !(*this == rhs); }

	friend auto operator<=>(const Iterator& lhs, const Iterator& rhs) {
	return lhs.mIndex <=> rhs.mIndex;
	}

	reference operator[](difference_type n) { return (this + n); }

	reference operator*() const { return mContainer[mIndex]; }
	pointer operator->() const { return std::addressof(mContainer[mIndex]); }

	private:
	ContainerType& mContainer;
	size_type mIndex = 0;
	};

	private:
	// Returns the index of the next element in mBuffer.
	size_type next(size_type index) const {
	if (index == capacity() - 1) {
	return 0;
	} else {
	return index + 1;
	}
	}

	// Returns the index of the previous element in mBuffer.
	size_type previous(size_type index) const {
	if (index == 0) {
	return capacity() - 1;
	} else {
	return index - 1;
	}
	}

	// Converts the index of an element in [0, size()] to its corresponding index in mBuffer.
	size_type bufferIndex(size_type elementIndex) const {
	if (elementIndex > size()) {
	abort();
	}
	size_type index = mBegin + elementIndex;
	if (index >= capacity()) {
	index -= capacity();
	}
	if (index >= capacity()) {
	abort();
	}
	return index;
	}

	pointer mBuffer = nullptr;
	size_type mCapacity = 0; // Total capacity of mBuffer.
	size_type mBegin = 0; // Index of the first initialised element in mBuffer.
	size_type mSize = 0; // Total number of initialised elements.
	};

	} // namespace android