Commits

bitsquid committed 4abf85d

Initial Queue implementation.

Comments (0)

Files changed (5)

 
 		template<typename T> void grow(Array<T> &a, uint32_t min_capacity)
 		{
-			uint32_t new_capacity = a._capacity*2 + 10;
+			uint32_t new_capacity = a._capacity*2 + 8;
 			if (new_capacity < min_capacity)
 				new_capacity = min_capacity;
 			set_capacity(a, new_capacity);

collection_types.h

 #include "types.h"
 #include "memory_types.h"
 
+/// All collection types assume that they are used to store POD objects. I.e. they:
+///
+/// * Don't call constructors and destructors on elements.
+/// * Move elements with memmove().
+///
+/// If you want to store items that are not PODs, use something other than these collection
+/// classes.
 namespace foundation
 {
-	/// Array of POD objects.
-	///
-	/// * Does not call constructors & destructors on elements.
-	/// * Assumes they can be moved with memmove().
+	/// Dynamically resizable array of POD objects.
 	template<typename T> struct Array
 	{
 		Array(Allocator &a);
 		T *_data;
 	};
 
+	/// A double-ended queue/ring buffer.
+	template <typename T> struct Queue
+	{
+		Queue(Allocator &a);
+
+		T &operator[](uint32_t i);
+		const T &operator[](uint32_t i) const;
+
+		Array<T> _data;
+		uint32_t _size;
+		uint32_t _offset;
+	};
+
 	/// Hash from an uint64_t to POD objects. If you want to use a generic key
 	/// object, use a hash function to map that object to an uint64_t.
-	///
-	/// * Does not call constructors & destructors on elements.
-	/// * Assumes they can be moved with memmove().
 	template<typename T> struct Hash
 	{
 	public:
+#include "collection_types.h"
+#include "array.h"
+
+#include <assert.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 array.
+		template<typename T> void push_back(Queue<T> &q, const T &item);
+		/// Pops the last item from the array. The array cannot be empty.
+		template<typename T> void pop_back(Queue<T> &q);
+		/// Pushes the item to the front of the array.
+		template<typename T> void push_front(Queue<T> &q, const T &item);
+		/// Pops the first item from the array. The array cannot be empty.
+		template<typename T> void pop_front(Queue<T> &q);
+	}
+
+	namespace queue_internal
+	{
+		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;
+				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 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)];
+	}
+}
 
 OBJECTS = %w(unit_test.o memory.o murmur_hash.o string_stream.o)
 HEADERS = %w(array.h collection_types.h memory.h memory_types.h types.h 
-	temp_allocator.h hash.h string_stream.h)
+	temp_allocator.h hash.h string_stream.h queue.h)
 
 # tasks
 
+#include "queue.h"
 #include "string_stream.h"
 #include "murmur_hash.h"
 #include "hash.h"
 		}
 		memory_globals::shutdown();
 	}
+
+	void test_queue()
+	{
+		memory_globals::init();
+		{
+			TempAllocator1024 ta;
+			Queue<int> q(ta);
+
+			queue::reserve(q, 10);
+			ASSERT(queue::space(q) == 10);
+			queue::push_back(q, 11);
+			queue::push_front(q, 22);
+			ASSERT(queue::size(q) == 2);
+			ASSERT(q[0] == 22);
+			ASSERT(q[1] == 11);
+		}
+	}
 }
 
 int main(int, char **)
 	test_murmur_hash();
 	test_pointer_arithmetic();
 	test_string_stream();
+	test_queue();
 	return 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.