bitsquid avatar bitsquid committed 0a996d4

Added begin_front() and end_front() for queue.

Comments (0)

Files changed (3)

 
 * **Array<T>** Implements an array of objects. A lightweight version of std::vector that assumes that *T* is a POD-object (i.e. constructors and destructors do not have to be called and the object can be moved with memmove).
 
+* **Queue<T>** Implements a double-ended queue/ring-buffer of POD objects. Push items to the back of the queue and pop them from the front.
+
 * **Hash<T>** Implements a lightweight hash that assumes that *T* is a POD-object. The hash keys are always uint64_t numbers. If you want to use some other type of key, just hash it to a uint64_t first. (The hash function should not have any collisions in your domain.) The hash can be used as a regular hash, or as a multi_hash, through the *multi_hash* interface.
 
 * **string_stream** Functions for using an Array<char> as a stream of characters that you can print formatted messages to.
 #include "collection_types.h"
 #include "array.h"
 
-#include <assert.h>
-
 namespace foundation
 {
 	namespace queue 
 		/// 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 array.
+		/// 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 array. The array cannot be empty.
+		/// 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 array.
+		/// 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 array. The array cannot be empty.
+		/// 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);
-			assert(new_capacity >= end);
 			array::resize(q._data, new_capacity);
 			if (q._offset + q._size > end) {
 				uint32_t end_items = end - q._offset;
 			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);
+			q._size += to_insert;
+			items += to_insert;
+			n -= to_insert;
+			memcpy(array::begin(q._data), items, n);
+			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) {}
 			ASSERT(queue::size(q) == 2);
 			ASSERT(q[0] == 22);
 			ASSERT(q[1] == 11);
+			queue::consume(q, 2);
+			ASSERT(queue::size(q) == 0);
+			int items[] = {1,2,3,4,5,6,7,8,9,10};
+			queue::push(q,items,10);
+			ASSERT(queue::size(q) == 10);
+			ASSERT(q[0] == 1);
+			ASSERT(q[9] == 10);
+			queue::consume(q, queue::end_front(q) - queue::begin_front(q));
+			queue::consume(q, queue::end_front(q) - queue::begin_front(q));
+			ASSERT(queue::size(q) == 0);
 		}
 	}
 }
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.