Source

foundation / queue.h

Full commit
bitsquid 4abf85d 














bitsquid 0a996d4 
bitsquid 4abf85d 
bitsquid 0a996d4 
bitsquid 4abf85d 
bitsquid 0a996d4 
bitsquid 4abf85d 
bitsquid 0a996d4 
bitsquid 4abf85d 
bitsquid 0a996d4 
















bitsquid 4abf85d 



bitsquid 0a996d4 
bitsquid 4abf85d 































































bitsquid 0a996d4 















bitsquid c9fd3c4 
bitsquid 0a996d4 


bitsquid c9fd3c4 
bitsquid 0a996d4 




















bitsquid 4abf85d 












#include "collection_types.h"
#include "array.h"

namespace foundation
{
	namespace queue 
	{
		/// Returns the number of items in the queue.
		template <typename T> uint32_t size(const Queue<T> &q);
		/// Returns the ammount of free space in the queue/ring buffer.
		/// This is the number of items we can push before the queue needs to grow.
		template<typename T> uint32_t space(const Queue<T> &q);
		/// Makes sure the queue has room for at least the specified number of items.
		template<typename T> void reserve(Queue<T> &q, uint32_t size);

		/// Pushes the item to the end of the queue.
		template<typename T> void push_back(Queue<T> &q, const T &item);
		/// Pops the last item from the queue. The queue cannot be empty.
		template<typename T> void pop_back(Queue<T> &q);
		/// Pushes the item to the front of the queue.
		template<typename T> void push_front(Queue<T> &q, const T &item);
		/// Pops the first item from the queue. The queue cannot be empty.
		template<typename T> void pop_front(Queue<T> &q);

		/// Consumes n items from the front of the queue.
		template <typename T> void consume(Queue<T> &q, uint32_t n);
		/// Pushes n items to the back of the queue.
		template <typename T> void push(Queue<T> &q, const T *items, uint32_t n);

		/// Returns the begin and end of the continuous chunk of elements at
		/// the start of the queue. (Note that this chunk does not necessarily
		/// contain all the elements in the queue (if the queue wraps around
		/// the array).
		///
		/// This is useful for when you want to process many queue elements at
		/// once.
		template<typename T> T* begin_front(Queue<T> &q);
		template<typename T> const T* begin_front(const Queue<T> &q);
		template<typename T> T* end_front(Queue<T> &q);
		template<typename T> const T* end_front(const Queue<T> &q);
	}

	namespace queue_internal
	{
		// Can only be used to increase the capacity.
		template<typename T> void increase_capacity(Queue<T> &q, uint32_t new_capacity)
		{
			uint32_t end = array::size(q._data);
			array::resize(q._data, new_capacity);
			if (q._offset + q._size > end) {
				uint32_t end_items = end - q._offset;
				memmove(array::begin(q._data) + new_capacity - end_items, array::begin(q._data) + q._offset, end_items * sizeof(T));
				q._offset += new_capacity - end;
			}
		}

		template<typename T> void grow(Queue<T> &q, uint32_t min_capacity = 0)
		{
			uint32_t new_capacity = array::size(q._data)*2 + 8;
			if (new_capacity < min_capacity)
				new_capacity = min_capacity;
			increase_capacity(q, new_capacity);
		}
	}

	namespace queue 
	{
		template<typename T> inline uint32_t size(const Queue<T> &q)
		{
			return q._size;
		}

		template<typename T> inline uint32_t space(const Queue<T> &q)
		{
			return array::size(q._data) - q._size;
		}

		template<typename T> void reserve(Queue<T> &q, uint32_t size)
		{
			if (size > q._size)
				queue_internal::increase_capacity(q, size);
		}

		template<typename T> inline void push_back(Queue<T> &q, const T &item)
		{
			if (!space(q))
				queue_internal::grow(q);
			q[q._size++] = item;
		}

		template<typename T> inline void pop_back(Queue<T> &q)
		{
			--q._size;
		}
		
		template<typename T> inline void push_front(Queue<T> &q, const T &item)
		{
			if (!space(q))
				queue_internal::grow(q);
			q._offset = (q._offset - 1 + array::size(q._data)) % array::size(q._data);
			++q._size;
			q[0] = item;
		}
		
		template<typename T> inline void pop_front(Queue<T> &q)
		{
			q._offset = (q._offset + 1) % array::size(q._data);
			--q._size;
		}

		template <typename T> inline void consume(Queue<T> &q, uint32_t n)
		{
			q._offset = (q._offset + n) % array::size(q._data);
			q._size -= n;
		}

		template <typename T> void push(Queue<T> &q, const T *items, uint32_t n)
		{
			if (space(q) < n)
				queue_internal::grow(q, size(q) + n);
			const uint32_t size = array::size(q._data);
			const uint32_t insert = (q._offset + q._size) % size;
			uint32_t to_insert = n;
			if (insert + to_insert > size)
				to_insert = size - insert;
			memcpy(array::begin(q._data) + insert, items, to_insert * sizeof(T));
			q._size += to_insert;
			items += to_insert;
			n -= to_insert;
			memcpy(array::begin(q._data), items, n * sizeof(T));
			q._size += n;
		}

		template<typename T> inline T* begin_front(Queue<T> &q)
		{
			return array::begin(q._data) + q._offset;
		}
		template<typename T> inline const T* begin_front(const Queue<T> &q)
		{
			return array::begin(q._data) + q._offset;
		}
		template<typename T> T* end_front(Queue<T> &q)
		{
			uint32_t end = q._offset + q._size;
			return end > array::size(q._data) ? array::end(q._data) : array::begin(q._data) + end;
		}
		template<typename T> const T* end_front(const Queue<T> &q)
		{
			uint32_t end = q._offset + q._size;
			return end > array::size(q._data) ? array::end(q._data) : array::begin(q._data) + end;
		}
	}

	template <typename T> inline Queue<T>::Queue(Allocator &allocator) : _data(allocator), _size(0), _offset(0) {}

	template <typename T> inline T & Queue<T>::operator[](uint32_t i)
	{
		return _data[(i + _offset) % array::size(_data)];
	}

	template <typename T> inline const T & Queue<T>::operator[](uint32_t i) const
	{
		return _data[(i + _offset) % array::size(_data)];
	}
}