Commits

Alexander Konovalov committed a89a5a7 Draft

Switched to premake4, compiled on windows

Comments (0)

Files changed (35)

 syntax: glob
-*.o
+build/*
+*.idb
+*.pdb
+*.ilk
 unit_test
-foundation
+unit-test.exe
+foundation
+foundation.lib

array.h

-#pragma once
-
-#include "collection_types.h"
-#include "memory.h"
-
-#include <memory>
-
-namespace foundation {
-	namespace array
-	{
-		/// The number of elements in the array.
-		template<typename T> size_t size(const Array<T> &a) ;
-		/// Returns true if there are any elements in the array.
-		template<typename T> bool any(const Array<T> &a);
-		/// Returns true if the array is empty.
-		template<typename T> bool empty(const Array<T> &a);
-		
-		/// Used to iterate over the array.
-		template<typename T> T* begin(Array<T> &a);
-		template<typename T> const T* begin(const Array<T> &a);
-		template<typename T> T* end(Array<T> &a);
-		template<typename T> const T* end(const Array<T> &a);
-		
-		/// Returns the first/last element of the array. Don't use these on an
-		/// empty array.
-		template<typename T> T& front(Array<T> &a);
-		template<typename T> const T& front(const Array<T> &a);
-		template<typename T> T& back(Array<T> &a);
-		template<typename T> const T& back(const Array<T> &a);
-
-		/// Changes the size of the array (does not reallocate memory unless necessary).
-		template <typename T> void resize(Array<T> &a, size_t new_size);
-		/// Removes all items in the array (does not free memory).
-		template <typename T> void clear(Array<T> &a);
-		/// Reallocates the array to the specified capacity.
-		template<typename T> void set_capacity(Array<T> &a, size_t new_capacity);
-		/// Makes sure that the array has at least the specified capacity.
-		/// (If not, the array is grown.)
-		template <typename T> void reserve(Array<T> &a, size_t new_capacity);
-		/// Grows the array using a geometric progression formula, so that the ammortized
-		/// cost of push_back() is O(1). If a min_capacity is specified, the array will
-		/// grow to at least that capacity.
-		template<typename T> void grow(Array<T> &a, size_t min_capacity = 0);
-		/// Trims the array so that its capacity matches its size.
-		template <typename T> void trim(Array<T> &a);
-
-		/// Pushes the item to the end of the array.
-		template<typename T> void push_back(Array<T> &a, const T &item);
-		/// Pops the last item from the array. The array cannot be empty.
-		template<typename T> void pop_back(Array<T> &a);
-	}
-
-	namespace array
-	{
-		template<typename T> inline size_t size(const Array<T> &a) 		{return a._size;}
-		template<typename T> inline bool any(const Array<T> &a) 			{return a._size != 0;}
-		template<typename T> inline bool empty(const Array<T> &a) 			{return a._size == 0;}
-		
-		template<typename T> inline T* begin(Array<T> &a) 					{return a._data;}
-		template<typename T> inline const T* begin(const Array<T> &a) 		{return a._data;}
-		template<typename T> inline T* end(Array<T> &a) 					{return a._data + a._size;}
-		template<typename T> inline const T* end(const Array<T> &a) 		{return a._data + a._size;}
-		
-		template<typename T> inline T& front(Array<T> &a) 					{return a._data[0];}
-		template<typename T> inline const T& front(const Array<T> &a) 		{return a._data[0];}
-		template<typename T> inline T& back(Array<T> &a) 					{return a._data[a._size-1];}
-		template<typename T> inline const T& back(const Array<T> &a) 		{return a._data[a._size-1];}
-
-		template <typename T> inline void clear(Array<T> &a) {resize(a,0);}
-		template <typename T> inline void trim(Array<T> &a) {set_capacity(a,a._size);}
-
-		template <typename T> void resize(Array<T> &a, size_t new_size)
-		{
-			if (new_size > a._capacity)
-				grow(a, new_size);
-			a._size = new_size;
-		}
-
-		template <typename T> inline void reserve(Array<T> &a, size_t new_capacity)
-		{
-			if (new_capacity > a._capacity)
-				set_capacity(a, new_capacity);
-		}
-
-		template<typename T> void set_capacity(Array<T> &a, size_t new_capacity)
-		{
-			if (new_capacity == a._capacity)
-				return;
-
-			if (new_capacity < a._size)
-				resize(a, new_capacity);
-
-			T *new_data = 0;
-			if (new_capacity > 0) {
-				new_data = (T *)a._allocator->allocate(sizeof(T)*new_capacity, alignof(T));
-				memcpy(new_data, a._data, sizeof(T)*a._size);
-			}
-			a._allocator->deallocate(a._data);
-			a._data = new_data;
-			a._capacity = new_capacity;
-		}
-
-		template<typename T> void grow(Array<T> &a, size_t min_capacity)
-		{
-			size_t new_capacity = a._capacity*2 + 8;
-			if (new_capacity < min_capacity)
-				new_capacity = min_capacity;
-			set_capacity(a, new_capacity);
-		}
-
-		template<typename T> inline void push_back(Array<T> &a, const T &item)
-		{
-			if (a._size + 1 > a._capacity)
-				grow(a);
-			a._data[a._size++] = item;
-		}
-
-		template<typename T> inline void pop_back(Array<T> &a)
-		{
-			a._size--;
-		}
-	}
-
-	template <typename T>
-	inline Array<T>::Array(Allocator &allocator) : _allocator(&allocator), _size(0), _capacity(0), _data(0) {}
-
-	template <typename T>
-	inline Array<T>::~Array()
-	{
-		_allocator->deallocate(_data);
-	}
-
-	template <typename T>
-	Array<T>::Array(const Array<T> &other) : _allocator(other._allocator), _size(0), _capacity(0), _data(0)
-	{
-		const size_t n = other._size;
-		array::set_capacity(*this, n);
-		memcpy(_data, other._data, sizeof(T) * n);
-		_size = n;
-	}
-
-	template <typename T>
-	Array<T> &Array<T>::operator=(const Array<T> &other)
-	{
-		const size_t n = other._size;
-		array::resize(*this, n);
-		memcpy(_data, other._data, sizeof(T)*n);
-		return *this;
-	}
-
-	template <typename T>
-	inline T & Array<T>::operator[](size_t i)
-	{
-		return _data[i];
-	}
-
-	template <typename T>
-	inline const T & Array<T>::operator[](size_t i) const
-	{
-		return _data[i];
-	}
-}

collection_types.h

-#pragma once
-
-#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
-{
-	/// Dynamically resizable array of POD objects.
-	template<typename T> struct Array
-	{
-		Array(Allocator &a);
-		~Array();
-		Array(const Array &other);
-		Array &operator=(const Array &other);
-		
-		T &operator[](size_t i);
-		const T &operator[](size_t i) const;
-
-		Allocator *_allocator;
-		size_t _size;
-		size_t _capacity;
-		T *_data;
-	};
-
-	/// A double-ended queue/ring buffer.
-	template <typename T> struct Queue
-	{
-		Queue(Allocator &a);
-
-		T &operator[](size_t i);
-		const T &operator[](size_t i) const;
-
-		Array<T> _data;
-		size_t _size;
-		size_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.
-	template<typename T> struct Hash
-	{
-	public:
-		Hash(Allocator &a);
-		
-		struct Entry {
-			uint64_t key;
-			size_t next;
-			T value;
-		};
-
-		Array<size_t> _hash;
-		Array<Entry> _data;
-	};
-}

hash.h

-#pragma once
-
-#include "array.h"
-#include "collection_types.h"
-
-namespace foundation {
-
-	/// The hash function stores its data in a "list-in-an-array" where
-	/// indices are used instead of pointers. 
-	///
-	/// When items are removed, the array-list is repacked to always keep
-	/// it tightly ordered.
-
-	namespace hash
-	{
-		/// Returns true if the specified key exists in the hash.
-		template<typename T> bool has(const Hash<T> &h, uint64_t key);
-
-		/// Returns the value stored for the specified key, or deffault if the key
-		/// does not exist in the hash.
-		template<typename T> const T &get(const Hash<T> &h, uint64_t key, const T &deffault);
-
-		/// Sets the value for the key.
-		template<typename T> void set(Hash<T> &h, uint64_t key, const T &value);
-
-		/// Removes the key from the hash if it exists.
-		template<typename T> void remove(Hash<T> &h, uint64_t key);
-
-		/// Resizes the hash lookup table to the specified size.
-		/// (The table will grow automatically when 70 % full.)
-		template<typename T> void reserve(Hash<T> &h, size_t size);
-
-		/// Returns a pointer to the first entry in the hash table, can be used to
-		/// efficiently iterate over the elements (in random order).
-		template<typename T> const typename Hash<T>::Entry *begin(const Hash<T> &h);
-		template<typename T> const typename Hash<T>::Entry *end(const Hash<T> &h);
-	}
-
-	namespace multi_hash
-	{
-		/// Finds the first entry with the specified key.
-		template<typename T> const typename Hash<T>::Entry *find_first(const Hash<T> &h, uint64_t key);
-
-		/// Finds the next entry with the same key as e.
-		template<typename T> const typename Hash<T>::Entry *find_next(const Hash<T> &h, const typename Hash<T>::Entry *e);
-
-		/// Returns the number of entries with the key.
-		template<typename T> size_t count(const Hash<T> &h, uint64_t key);
-
-		/// Returns all the entries with the specified key.
-		/// Use a TempAllocator for the array to avoid allocating memory.
-		template<typename T> void get(const Hash<T> &h, uint64_t key, Array<T> &items);
-
-		/// Inserts the value as an aditional value for the key.
-		template<typename T> void insert(Hash<T> &h, uint64_t key, const T &value);
-
-		/// Removes the specified entry.
-		template<typename T> void remove(Hash<T> &h, const typename Hash<T>::Entry *e);
-
-		/// Removes all entries with the specified key.
-		template<typename T> void remove_all(Hash<T> &h, uint64_t key);
-	}
-
-	namespace hash_internal
-	{
-		const size_t END_OF_LIST = SIZE_MAX;
-		
-		struct FindResult
-		{
-			size_t hash_i;
-			size_t data_prev;
-			size_t data_i;
-		};	
-
-		template<typename T> size_t add_entry(Hash<T> &h, uint64_t key)
-		{
-			typename Hash<T>::Entry e;
-			e.key = key;
-			e.next = END_OF_LIST;
-			size_t ei = array::size(h._data);
-			array::push_back(h._data, e);
-			return ei;
-		}
-
-		template<typename T> void erase(Hash<T> &h, const FindResult &fr)
-		{
-			if (fr.data_prev == END_OF_LIST)
-				h._hash[fr.hash_i] = h._data[fr.data_i].next;
-			else
-				h._data[fr.data_prev].next = h._data[fr.data_i].next;
-
-			if (fr.data_i == array::size(h._data) - 1) {
-				array::pop_back(h._data);
-				return;
-			}
-
-			h._data[fr.data_i] = h._data[array::size(h._data) - 1];
-			FindResult last = find(h, h._data[fr.data_i].key);
-
-			if (last.data_prev != END_OF_LIST)
-				h._data[last.data_prev].next = fr.data_i;
-			else
-				h._hash[last.hash_i] = fr.data_i;
-		}
-
-		template<typename T> FindResult find(const Hash<T> &h, uint64_t key)
-		{
-			FindResult fr;
-			fr.hash_i = END_OF_LIST;
-			fr.data_prev = END_OF_LIST;
-			fr.data_i = END_OF_LIST;
-
-			if (array::size(h._hash) == 0)
-				return fr;
-
-			fr.hash_i = key % array::size(h._hash);
-			fr.data_i = h._hash[fr.hash_i];
-			while (fr.data_i != END_OF_LIST) {
-				if (h._data[fr.data_i].key == key)
-					return fr;
-				fr.data_prev = fr.data_i;
-				fr.data_i = h._data[fr.data_i].next;
-			}
-			return fr;
-		}
-
-		template<typename T> FindResult find(const Hash<T> &h, const typename Hash<T>::Entry *e)
-		{
-			FindResult fr;
-			fr.hash_i = END_OF_LIST;
-			fr.data_prev = END_OF_LIST;
-			fr.data_i = END_OF_LIST;
-
-			if (array::size(h._hash) == 0)
-				return fr;
-
-			fr.hash_i = e->key % array::size(h._hash);
-			fr.data_i = h._hash[fr.hash_i];
-			while (fr.data_i != END_OF_LIST) {
-				if (&h._data[fr.data_i] == e)
-					return fr;
-				fr.data_prev = fr.data_i;
-				fr.data_i = h._data[fr.data_i].next;
-			}
-			return fr;
-		}
-
-		template<typename T> size_t find_or_fail(const Hash<T> &h, uint64_t key)
-		{
-			return find(h, key).data_i;
-		}
-
-		template<typename T> size_t find_or_make(Hash<T> &h, uint64_t key)
-		{
-			const FindResult fr = find(h, key);
-			if (fr.data_i != END_OF_LIST)
-				return fr.data_i;
-
-			size_t i = add_entry(h, key);
-			if (fr.data_prev == END_OF_LIST)
-				h._hash[fr.hash_i] = i;
-			else
-				h._data[fr.data_prev].next = i;
-			return i;
-		}
-
-		template<typename T> size_t make(Hash<T> &h, uint64_t key)
-		{
-			const FindResult fr = find(h, key);
-			const size_t i = add_entry(h, key);
-
-			if (fr.data_prev == END_OF_LIST)
-				h._hash[fr.hash_i] = i;
-			else
-				h._data[fr.data_prev].next = i;
-
-			h._data[i].next = fr.data_i;
-			return i;
-		}	
-
-		template<typename T> void find_and_erase(Hash<T> &h, uint64_t key)
-		{
-			const FindResult fr = find(h, key);
-			if (fr.data_i != END_OF_LIST)
-				erase(h, fr);
-		}
-
-		template<typename T> void rehash(Hash<T> &h, size_t new_size)
-		{
-			Hash<T> nh(*h._hash._allocator);
-			array::resize(nh._hash, new_size);
-			array::reserve(nh._data, array::size(h._data));
-			for (size_t i=0; i<new_size; ++i)
-				nh._hash[i] = END_OF_LIST;
-			for (size_t i=0; i<array::size(h._data); ++i) {
-				const typename Hash<T>::Entry &e = h._data[i];
-				multi_hash::insert(nh, e.key, e.value);
-			}
-
-			Hash<T> empty(*h._hash._allocator);
-			h.~Hash<T>();
-			memcpy(&h, &nh, sizeof(Hash<T>));
-			memcpy(&nh, &empty, sizeof(Hash<T>));
-		}
-
-		template<typename T> bool full(const Hash<T> &h)
-		{
-			const float max_load_factor = 0.7f;
-			return array::size(h._data) >= array::size(h._hash) * max_load_factor;
-		}
-
-		template<typename T> void grow(Hash<T> &h)
-		{
-			const size_t new_size = array::size(h._data) * 2 + 10;
-			rehash(h, new_size);
-		}
-	}
-
-	namespace hash
-	{
-		template<typename T> bool has(const Hash<T> &h, uint64_t key)
-		{
-			return hash_internal::find_or_fail(h, key) != hash_internal::END_OF_LIST;
-		}
-
-		template<typename T> const T &get(const Hash<T> &h, uint64_t key, const T &deffault)
-		{
-			const size_t i = hash_internal::find_or_fail(h, key);
-			return i == hash_internal::END_OF_LIST ? deffault : h._data[i].value;
-		}
-
-		template<typename T> void set(Hash<T> &h, uint64_t key, const T &value)
-		{
-			if (array::size(h._hash) == 0)
-				hash_internal::grow(h);
-
-			const size_t i = hash_internal::find_or_make(h, key);
-			h._data[i].value = value;
-			if (hash_internal::full(h))
-				hash_internal::grow(h);
-		}
-
-		template<typename T> void remove(Hash<T> &h, uint64_t key)
-		{
-			hash_internal::find_and_erase(h, key);
-		}
-
-		template<typename T> void reserve(Hash<T> &h, size_t size)
-		{
-			hash_internal::rehash(h, size);
-		}
-
-		template<typename T> const typename Hash<T>::Entry *begin(const Hash<T> &h)
-		{
-			return array::begin(h._data);
-		}
-
-		template<typename T> const typename Hash<T>::Entry *end(const Hash<T> &h)
-		{
-			return array::end(h._data);
-		}
-	}
-
-	namespace multi_hash
-	{
-		template<typename T> const typename Hash<T>::Entry *find_first(const Hash<T> &h, uint64_t key)
-		{
-			const size_t i = hash_internal::find_or_fail(h, key);
-			return i == hash_internal::END_OF_LIST ? 0 : &h._data[i];
-		}
-
-		template<typename T> const typename Hash<T>::Entry *find_next(const Hash<T> &h, const typename Hash<T>::Entry *e)
-		{
-			size_t i = e->next;
-			while (i != hash_internal::END_OF_LIST) {
-				if (h._data[i].key == e->key)
-					return &h._data[i];
-				i = h._data[i].next;
-			}
-			return 0;
-		}
-
-		template<typename T> size_t count(const Hash<T> &h, uint64_t key)
-		{
-			size_t i = 0;
-			const typename Hash<T>::Entry *e = find_first(h, key);
-			while (e) {
-				++i;
-				e = find_next(h, e);
-			}
-			return i;
-		}
-
-		template<typename T> void get(const Hash<T> &h, uint64_t key, Array<T> &items)
-		{
-			const typename Hash<T>::Entry *e = find_first(h, key);
-			while (e) {
-				array::push_back(items, e->value);
-				e = find_next(h, e);
-			}
-		}
-
-		template<typename T> void insert(Hash<T> &h, uint64_t key, const T &value)
-		{
-			if (array::size(h._hash) == 0)
-				hash_internal::grow(h);
-
-			const size_t i = hash_internal::make(h, key);
-			h._data[i].value = value;
-			if (hash_internal::full(h))
-				hash_internal::grow(h);
-		}
-
-		template<typename T> void remove(Hash<T> &h, const typename Hash<T>::Entry *e)
-		{
-			const hash_internal::FindResult fr = hash_internal::find(h, e);
-			if (fr.data_i != hash_internal::END_OF_LIST)
-				hash_internal::erase(h, fr);
-		}
-
-		template<typename T> void remove_all(Hash<T> &h, uint64_t key)
-		{
-			while (hash::has(h, key))
-				hash::remove(h, key);
-		}
-	}
-
-
-	template <typename T> Hash<T>::Hash(Allocator &a) :
-		_hash(a), _data(a)
-	{}
-}

inc/win32/stdint.h

+/* ISO C9x  7.18  Integer types <stdint.h>
+ * Based on ISO/IEC SC22/WG14 9899 Committee draft (SC22 N2794)
+ *
+ *  THIS SOFTWARE IS NOT COPYRIGHTED
+ *
+ *  Contributor: Danny Smith <danny_r_smith_2001@yahoo.co.nz>
+ *
+ *  This source code is offered for use in the public domain. You may
+ *  use, modify or distribute it freely.
+ *
+ *  This code is distributed in the hope that it will be useful but
+ *  WITHOUT ANY WARRANTY. ALL WARRANTIES, EXPRESS OR IMPLIED ARE HEREBY
+ *  DISCLAIMED. This includes but is not limited to warranties of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ *
+ *  Date: 2000-12-02
+ *
+ * mwb: This was modified in the following ways:
+ *
+ *      - make it compatible with Visual C++ 6 (which uses 
+ *          non-standard keywords and suffixes for 64-bit types)
+ *      - some environments need stddef.h included (for wchar stuff?)
+ *      - handle the fact that Microsoft's limits.h header defines
+ *          SIZE_MAX
+ *      - make corrections for SIZE_MAX, INTPTR_MIN, INTPTR_MAX, UINTPTR_MAX,
+ *          PTRDIFF_MIN, PTRDIFF_MAX, SIG_ATOMIC_MIN, and SIG_ATOMIC_MAX
+ *          to be 64-bit aware.
+ */
+
+
+#ifndef _STDINT_H
+#define _STDINT_H
+#define __need_wint_t
+#define __need_wchar_t
+#include <wchar.h>
+#include <stddef.h>
+
+#if _MSC_VER && (_MSC_VER < 1300)
+/* using MSVC 6 or earlier - no "long long" type, but might have _int64 type */
+#define __STDINT_LONGLONG           __int64
+#define __STDINT_LONGLONG_SUFFIX    i64
+#else
+#define __STDINT_LONGLONG           long long
+#define __STDINT_LONGLONG_SUFFIX    LL
+#endif
+
+#if !defined( PASTE)
+#define PASTE2( x, y) x##y
+#define PASTE( x, y)  PASTE2( x, y)
+#endif /* PASTE */
+
+
+/* 7.18.1.1  Exact-width integer types */
+typedef signed char int8_t;
+typedef unsigned char   uint8_t;
+typedef short  int16_t;
+typedef unsigned short  uint16_t;
+typedef int  int32_t;
+typedef unsigned   uint32_t;
+typedef __STDINT_LONGLONG  int64_t;
+typedef unsigned __STDINT_LONGLONG   uint64_t;
+
+/* 7.18.1.2  Minimum-width integer types */
+typedef signed char int_least8_t;
+typedef unsigned char   uint_least8_t;
+typedef short  int_least16_t;
+typedef unsigned short  uint_least16_t;
+typedef int  int_least32_t;
+typedef unsigned   uint_least32_t;
+typedef __STDINT_LONGLONG  int_least64_t;
+typedef unsigned __STDINT_LONGLONG   uint_least64_t;
+
+/*  7.18.1.3  Fastest minimum-width integer types 
+ *  Not actually guaranteed to be fastest for all purposes
+ *  Here we use the exact-width types for 8 and 16-bit ints. 
+ */
+typedef char int_fast8_t;
+typedef unsigned char uint_fast8_t;
+typedef short  int_fast16_t;
+typedef unsigned short  uint_fast16_t;
+typedef int  int_fast32_t;
+typedef unsigned  int  uint_fast32_t;
+typedef __STDINT_LONGLONG  int_fast64_t;
+typedef unsigned __STDINT_LONGLONG   uint_fast64_t;
+
+/* 7.18.1.4  Integer types capable of holding object pointers */
+#ifndef _INTPTR_T_DEFINED
+#define _INTPTR_T_DEFINED
+#ifdef _WIN64
+typedef __STDINT_LONGLONG intptr_t
+#else
+typedef int intptr_t;
+#endif /* _WIN64 */
+#endif /* _INTPTR_T_DEFINED */
+
+#ifndef _UINTPTR_T_DEFINED
+#define _UINTPTR_T_DEFINED
+#ifdef _WIN64
+typedef unsigned __STDINT_LONGLONG uintptr_t
+#else
+typedef unsigned int uintptr_t;
+#endif /* _WIN64 */
+#endif /* _UINTPTR_T_DEFINED */
+
+/* 7.18.1.5  Greatest-width integer types */
+typedef __STDINT_LONGLONG  intmax_t;
+typedef unsigned __STDINT_LONGLONG   uintmax_t;
+
+/* 7.18.2  Limits of specified-width integer types */
+#if !defined ( __cplusplus) || defined (__STDC_LIMIT_MACROS)
+
+/* 7.18.2.1  Limits of exact-width integer types */
+#define INT8_MIN (-128) 
+#define INT16_MIN (-32768)
+#define INT32_MIN (-2147483647 - 1)
+#define INT64_MIN  (PASTE( -9223372036854775807, __STDINT_LONGLONG_SUFFIX) - 1)
+
+#define INT8_MAX 127
+#define INT16_MAX 32767
+#define INT32_MAX 2147483647
+#define INT64_MAX (PASTE( 9223372036854775807, __STDINT_LONGLONG_SUFFIX))
+
+#define UINT8_MAX 0xff /* 255U */
+#define UINT16_MAX 0xffff /* 65535U */
+#define UINT32_MAX 0xffffffff  /* 4294967295U */
+#define UINT64_MAX (PASTE( 0xffffffffffffffffU, __STDINT_LONGLONG_SUFFIX)) /* 18446744073709551615ULL */
+
+/* 7.18.2.2  Limits of minimum-width integer types */
+#define INT_LEAST8_MIN INT8_MIN
+#define INT_LEAST16_MIN INT16_MIN
+#define INT_LEAST32_MIN INT32_MIN
+#define INT_LEAST64_MIN INT64_MIN
+
+#define INT_LEAST8_MAX INT8_MAX
+#define INT_LEAST16_MAX INT16_MAX
+#define INT_LEAST32_MAX INT32_MAX
+#define INT_LEAST64_MAX INT64_MAX
+
+#define UINT_LEAST8_MAX UINT8_MAX
+#define UINT_LEAST16_MAX UINT16_MAX
+#define UINT_LEAST32_MAX UINT32_MAX
+#define UINT_LEAST64_MAX UINT64_MAX
+
+/* 7.18.2.3  Limits of fastest minimum-width integer types */
+#define INT_FAST8_MIN INT8_MIN
+#define INT_FAST16_MIN INT16_MIN
+#define INT_FAST32_MIN INT32_MIN
+#define INT_FAST64_MIN INT64_MIN
+
+#define INT_FAST8_MAX INT8_MAX
+#define INT_FAST16_MAX INT16_MAX
+#define INT_FAST32_MAX INT32_MAX
+#define INT_FAST64_MAX INT64_MAX
+
+#define UINT_FAST8_MAX UINT8_MAX
+#define UINT_FAST16_MAX UINT16_MAX
+#define UINT_FAST32_MAX UINT32_MAX
+#define UINT_FAST64_MAX UINT64_MAX
+
+/* 7.18.2.4  Limits of integer types capable of holding
+    object pointers */ 
+#ifdef _WIN64
+#define INTPTR_MIN INT64_MIN
+#define INTPTR_MAX INT64_MAX
+#define UINTPTR_MAX UINT64_MAX
+#else
+#define INTPTR_MIN INT32_MIN
+#define INTPTR_MAX INT32_MAX
+#define UINTPTR_MAX UINT32_MAX
+#endif /* _WIN64 */
+
+/* 7.18.2.5  Limits of greatest-width integer types */
+#define INTMAX_MIN INT64_MIN
+#define INTMAX_MAX INT64_MAX
+#define UINTMAX_MAX UINT64_MAX
+
+/* 7.18.3  Limits of other integer types */
+#define PTRDIFF_MIN INTPTR_MIN
+#define PTRDIFF_MAX INTPTR_MAX
+
+#define SIG_ATOMIC_MIN INTPTR_MIN
+#define SIG_ATOMIC_MAX INTPTR_MAX
+
+/* we need to check for SIZE_MAX already defined because MS defines it in limits.h */
+#ifndef SIZE_MAX
+#define SIZE_MAX UINTPTR_MAX
+#endif
+
+#ifndef WCHAR_MIN  /* also in wchar.h */ 
+#define WCHAR_MIN 0
+#define WCHAR_MAX ((wchar_t)-1) /* UINT16_MAX */
+#endif
+
+/*
+ * wint_t is unsigned short for compatibility with MS runtime
+ */
+#define WINT_MIN 0
+#define WINT_MAX ((wint_t)-1) /* UINT16_MAX */
+
+#endif /* !defined ( __cplusplus) || defined __STDC_LIMIT_MACROS */
+
+
+/* 7.18.4  Macros for integer constants */
+#if !defined ( __cplusplus) || defined (__STDC_CONSTANT_MACROS)
+
+/* 7.18.4.1  Macros for minimum-width integer constants
+
+    Accoding to Douglas Gwyn <gwyn@arl.mil>:
+	"This spec was changed in ISO/IEC 9899:1999 TC1; in ISO/IEC
+	9899:1999 as initially published, the expansion was required
+	to be an integer constant of precisely matching type, which
+	is impossible to accomplish for the shorter types on most
+	platforms, because C99 provides no standard way to designate
+	an integer constant with width less than that of type int.
+	TC1 changed this to require just an integer constant
+	*expression* with *promoted* type."
+*/
+
+#define INT8_C(val) ((int8_t) + (val))
+#define UINT8_C(val) ((uint8_t) + (val##U))
+#define INT16_C(val) ((int16_t) + (val))
+#define UINT16_C(val) ((uint16_t) + (val##U))
+
+#define INT32_C(val) val##L
+#define UINT32_C(val) val##UL
+#define INT64_C(val) (PASTE( val, __STDINT_LONGLONG_SUFFIX))
+#define UINT64_C(val)(PASTE( PASTE( val, U), __STDINT_LONGLONG_SUFFIX))
+
+/* 7.18.4.2  Macros for greatest-width integer constants */
+#define INTMAX_C(val)  INT64_C(val)
+#define UINTMAX_C(val) UINT64_C(val)
+
+#endif  /* !defined ( __cplusplus) || defined __STDC_CONSTANT_MACROS */
+
+#endif

math_types.h

-#pragma once
-
-#include "types.h"
-
-namespace foundation
-{
-	struct Vector2
-	{
-		float x, y;
-	};
-
-	struct Vector3
-	{
-		float x, y, z;
-	};
-
-	struct Vector4
-	{
-		float x, y, z, w;
-	};
-
-	struct Quaternion
-	{
-		float x, y, z, w;
-	};
-
-	struct Matrix3x3
-	{
-		Vector3 x, y, z;
-	};
-
-	struct Matrix4x4
-	{
-		Vector4 x, y, z, t;
-	};
-
-	struct AABB
-	{
-		Vector3 min, max;
-	};
-
-	struct OOBB
-	{
-		Matrix4x4 tm;
-		AABB aabb;
-	};
-}

memory.cpp

-#include "memory.h"
-
-#include <stdlib.h>
-#include <assert.h>
-#include <new>
-
-namespace {
-	using namespace foundation;
-
-	// Header stored at the beginning of a memory allocation to indicate the
-	// size of the allocated data.
-	struct Header {
-		size_t size;
-	};
-
-	// If we need to align the memory allocation we pad the header with this
-	// value after storing the size. That way we can 
-	const size_t HEADER_PAD_VALUE = SIZE_MAX;
-
-	// Given a pointer to the header, returns a pointer to the data that follows it.
-	inline void *data_pointer(Header *header, size_t align) {
-		void *p = header + 1;
-		return memory::align_forward(p, align);
-	}
-
-	// Given a pointer to the data, returns a pointer to the header before it.
-	inline Header *header(void *data)
-	{
-		size_t *p = (size_t *)data;
-		while (p[-1] == HEADER_PAD_VALUE)
-			--p;
-		return (Header *)p - 1;
-	}
-
-	// Stores the size in the header and pads with HEADER_PAD_VALUE up to the
-	// data pointer.
-	inline void fill(Header *header, void *data, size_t size)
-	{
-		header->size = size;
-		size_t *p = (size_t *)(header + 1);
-		while (p < data)
-			*p++ = HEADER_PAD_VALUE;
-	}
-
-	/// An allocator that uses the default system malloc(). Allocations are
-	/// padded so that we can store the size of each allocation and align them
-	/// to the desired alignment.
-	///
-	/// (Note: An OS-specific allocator that can do alignment and tracks size
-	/// does need this padding and can thus be more efficient than the
-	/// MallocAllocator.)
-	class MallocAllocator : public Allocator
-	{
-		size_t _total_allocated;
-
-		// Returns the size to allocate from malloc() for a given size and align.		
-		static inline size_t size_with_padding(size_t size, size_t align) {
-			return size + align + sizeof(Header);
-		}
-
-	public:
-		MallocAllocator() : _total_allocated(0) {}
-
-		~MallocAllocator() {
-			// Check that we don't have any memory leaks when allocator is
-			// destroyed.
-			assert(_total_allocated == 0);
-		}
-
-		virtual void *allocate(size_t size, size_t align) {
-			const size_t ts = size_with_padding(size, align);
-			Header *h = (Header *)malloc(ts);
-			void *p = data_pointer(h, align);
-			fill(h, p, ts);
-			_total_allocated += ts;
-			return p;
-		}
-
-		virtual void deallocate(void *p) {
-			if (!p)
-				return;
-
-			Header *h = header(p);
-			_total_allocated -= h->size;
-			free(h);
-		}
-
-		virtual size_t allocated_size(void *p) {
-			return header(p)->size;
-		}
-
-		virtual size_t total_allocated() {
-			return _total_allocated;
-		}
-	};
-
-	/// An allocator used to allocate temporary "scratch" memory. The allocator
-	/// uses a fixed size ring buffer to services the requests.
-	///
-	/// Memory is always always allocated linearly. An allocation pointer is
-	/// advanced through the buffer as memory is allocated and wraps around at
-	/// the end of the buffer. Similarly, a free pointer is advanced as memory
-	/// is freed.
-	///
-	/// It is important that the scratch allocator is only used for short-lived
-	/// memory allocations. A long lived allocator will lock the "free" pointer
-	/// and prevent the "allocate" pointer from proceeding past it, which means
-	/// the ring buffer can't be used.
-	/// 
-	/// If the ring buffer is exhausted, the scratch allocator will use its backing
-	/// allocator to allocate memory instead.
-	class ScratchAllocator : public Allocator
-	{
-		Allocator &_backing;
-		
-		// Start and end of the ring buffer.
-		char *_begin, *_end;
-
-		// Pointers to where to allocate memory and where to free memory.
-		char *_allocate, *_free;
-		
-	public:
-		/// Creates a ScratchAllocator. The allocator will use the backing
-		/// allocator to create the ring buffer and to service any requests
-		/// that don't fit in the ring buffer.
-		///
-		/// size specifies the size of the ring buffer.
-		ScratchAllocator(Allocator &backing, size_t size) : _backing(backing) {
-			_begin = (char *)_backing.allocate(size);
-			_end = _begin + size;
-			_allocate = _begin;
-			_free = _begin;
-		}
-
-		~ScratchAllocator() {
-			assert(_free == _allocate);
-			_backing.deallocate(_begin);
-		}
-
-		bool in_use(void *p)
-		{
-			if (_free == _allocate)
-				return false;
-			if (_allocate > _free)
-				return p >= _free && p < _allocate;
-			return p >= _free || p < _allocate;
-		}
-
-		virtual void *allocate(size_t size, size_t align) {
-			assert(align % 4 == 0);
-			size = ((size + 3)/4)*4;
-
-			char *p = _allocate;
-			Header *h = (Header *)p;
-			char *data = (char *)data_pointer(h, align);
-			p = data + size;
-
-			// Reached the end of the buffer, wrap around to the beginning.
-			if (p > _end) {
-				h->size = (_end - (char *)h) | ((size_t)1 << (SIZE_BITS - 1));
-				
-				p = _begin;
-				h = (Header *)p;
-				data = (char *)data_pointer(h, align);
-				p = data + size;
-			}
-			
-			// If the buffer is exhausted use the backing allocator instead.
-			if (in_use(p))
-				return _backing.allocate(size, align);
-
-			fill(h, data, p - (char *)h);
-			_allocate = p;
-			return data;
-		}
-
-		virtual void deallocate(void *p) {
-			if (!p)
-				return;
-
-			if (p < _begin || p >= _end) {
-				_backing.deallocate(p);
-				return;
-			}
-
-			// Mark this slot as free
-			Header *h = header(p);
-			assert((h->size & ((size_t)1 << (SIZE_BITS - 1))) == 0);
-			h->size = h->size | ((size_t)1 << (SIZE_BITS - 1));
-
-			// Advance the free pointer past all free slots.
-			while (_free != _allocate) {
-				Header *h = (Header *)_free;
-				if ((h->size & ((size_t)1 << (SIZE_BITS - 1))) == 0)
-					break;
-
-				_free += h->size & (((size_t)1 << (SIZE_BITS - 1)) - 1);
-				if (_free == _end)
-					_free = _begin;
-			}
-		}
-
-		virtual size_t allocated_size(void *p) {
-			Header *h = header(p);
-			return h->size - ((char *)p - (char *)h);
-		}
-
-		virtual size_t total_allocated() {
-			return _end - _begin;
-		}
-	};
-
-	struct MemoryGlobals {
-		static const int ALLOCATOR_MEMORY = sizeof(MallocAllocator) + sizeof(ScratchAllocator);
-		char buffer[ALLOCATOR_MEMORY];
-
-		MallocAllocator *default_allocator;
-		ScratchAllocator *default_scratch_allocator;
-
-		MemoryGlobals() : default_allocator(0), default_scratch_allocator(0) {}
-	};
-
-	MemoryGlobals _memory_globals;
-}
-
-namespace foundation
-{
-	namespace memory_globals
-	{
-		void init(size_t temporary_memory) {
-			char *p = _memory_globals.buffer;
-			_memory_globals.default_allocator = new (p) MallocAllocator();
-			p += sizeof(MallocAllocator);
-			_memory_globals.default_scratch_allocator = new (p) ScratchAllocator(*_memory_globals.default_allocator, temporary_memory);
-		}
-
-		Allocator &default_allocator() {
-			return *_memory_globals.default_allocator;
-		}
-
-		Allocator &default_scratch_allocator() {
-			return *_memory_globals.default_scratch_allocator;
-		}
-
-		void shutdown() {
-			_memory_globals.default_scratch_allocator->~ScratchAllocator();
-			_memory_globals.default_allocator->~MallocAllocator();
-			_memory_globals = MemoryGlobals();
-		}
-	}
-}

memory.h

-#pragma once
-
-#include "types.h"
-#include "memory_types.h"
-
-namespace foundation
-{
-	/// Base class for memory allocators.
-	///
-	/// Note: Regardless of which allocator is used, prefer to allocate memory in larger chunks
-	/// instead of in many small allocations. This helps with data locality, fragmentation,
-	/// memory usage tracking, etc.
-	class Allocator
-	{
-	public:
-		/// Default alignment for memory allocations.
-		static const size_t DEFAULT_ALIGN = 4;
-
-		Allocator() {}
-		virtual ~Allocator() {}
-		
-		/// Allocates the specified amount of memory aligned to the specified alignment.
-		virtual void *allocate(size_t size, size_t align = DEFAULT_ALIGN) = 0;
-
-		/// Frees an allocation previously made with allocate().
-		virtual void deallocate(void *p) = 0;
-
-		static const size_t SIZE_NOT_TRACKED = SIZE_MAX;
-
-		/// Returns the amount of usable memory allocated at p. p must be a pointer
-		/// returned by allocate() that has not yet been deallocated. The value returned
-		/// will be at least the size specified to allocate(), but it can be bigger.
-		/// (The allocator may round up the allocation to fit into a set of predefined
-		/// slot sizes.)
-		///
-		/// Not all allocators support tracking the size of individual allocations.
-		/// An allocator that doesn't suppor it will return SIZE_NOT_TRACKED.
-		virtual size_t allocated_size(void *p) = 0;
-
-		/// Returns the total amount of memory allocated by this allocator. Note that the 
-		/// size returned can be bigger than the size of all individual allocations made,
-		/// because the allocator may keep additional structures.
-		///
-		/// If the allocator doesn't track memory, this function returns SIZE_NOT_TRACKED.
-		virtual size_t total_allocated() = 0;
-
-	private:
-		/// Allocators cannot be copied.
-	    Allocator(const Allocator& other);
-	    Allocator& operator=(const Allocator& other);
-	};
-
-	/// Creates a new object of type T using the allocator a to allocate the memory.
-	#define MAKE_NEW(a, T, ...)		(new ((a).allocate(sizeof(T), alignof(T))) T(__VA_ARGS__))
-
-	/// Frees an object allocated with MAKE_NEW.
-	#define MAKE_DELETE(a, T, p)	do {if (p) {(p)->~T(); a.deallocate(p);}} while (0)
-
-	/// Functions for accessing global memory data.
-	namespace memory_globals {
-		/// Initializes the global memory allocators. scratch_buffer_size is the size of the
-		/// memory buffer used by the scratch allocators.
-		void init(size_t scratch_buffer_size = 4*1024*1024);
-
-		/// Returns a default memory allocator that can be used for most allocations.
-		///
-		/// You need to call init() for this allocator to be available.
-		Allocator &default_allocator();
-
-		/// Returns a "scratch" allocator that can be used for temporary short-lived memory
-		/// allocations. The scratch allocator uses a ring buffer of size scratch_buffer_size
-		/// to service the allocations.
-		///
-		/// If there is not enough memory in the buffer to match requests for scratch
-		/// memory, memory from the default_allocator will be returned instaed.
-		Allocator &default_scratch_allocator();
-
-		/// Shuts down the global memory allocators created by init().
-		void shutdown();
-	}
-
-	namespace memory {
-		inline void *align_forward(void *p, size_t align);
-		inline void *pointer_add(void *p, size_t bytes);
-		inline const void *pointer_add(const void *p, size_t bytes);
-		inline void *pointer_sub(void *p, size_t bytes);
-		inline const void *pointer_sub(const void *p, size_t bytes);
-	}
-
-	// ---------------------------------------------------------------
-	// Inline function implementations
-	// ---------------------------------------------------------------
-
-	// Aligns p to the specified alignment by moving it forward if necessary
-	// and returns the result.
-	inline void *memory::align_forward(void *p, size_t align) {
-		uintptr_t pi = uintptr_t(p);
-		const size_t mod = pi % align;
-		if (mod)
-			pi += (align - mod);
-		return (void *)pi;
-	}
-
-	/// Returns the result of advancing p by the specified number of bytes
-	inline void *memory::pointer_add(void *p, size_t bytes)	{
-		return (void*)((char *)p + bytes);
-	}
-
-	inline const void *memory::pointer_add(const void *p, size_t bytes)	{
-		return (const void*)((const char *)p + bytes);
-	}
-
-	/// Returns the result of moving p back by the specified number of bytes
-	inline void *memory::pointer_sub(void *p, size_t bytes)	{
-		return (void*)((char *)p - bytes);
-	}
-
-	inline const void *memory::pointer_sub(const void *p, size_t bytes)	{
-		return (const void*)((const char *)p - bytes);
-	}
-}

memory_types.h

-#pragma once
-
-namespace foundation
-{
-	class Allocator;
-}

murmur_hash.cpp

-#include "murmur_hash.h"
-
-namespace foundation
-{
-	uint64_t murmur_hash_64(const void * key, size_t len, uint64_t seed)
-	{
-		const uint64_t m = 0xc6a4a7935bd1e995ULL;
-		const uint32_t r = 47;
-
-		uint64_t h = seed ^ (len * m);
-
-		const uint64_t * data = (const uint64_t *)key;
-		const uint64_t * end = data + (len/8);
-
-		while(data != end)
-		{
-			#ifdef PLATFORM_BIG_ENDIAN
-				uint64 k = *data++;
-				char *p = (char *)&k;
-				char c;
-				c = p[0]; p[0] = p[7]; p[7] = c;
-				c = p[1]; p[1] = p[6]; p[6] = c;
-				c = p[2]; p[2] = p[5]; p[5] = c;
-				c = p[3]; p[3] = p[4]; p[4] = c;
-			#else
-				uint64_t k = *data++;
-			#endif
-
-			k *= m;
-			k ^= k >> r;
-			k *= m;
-			
-			h ^= k;
-			h *= m;
-		}
-
-		const unsigned char * data2 = (const unsigned char*)data;
-
-		switch(len & 7)
-		{
-		case 7: h ^= uint64_t(data2[6]) << 48;
-		case 6: h ^= uint64_t(data2[5]) << 40;
-		case 5: h ^= uint64_t(data2[4]) << 32;
-		case 4: h ^= uint64_t(data2[3]) << 24;
-		case 3: h ^= uint64_t(data2[2]) << 16;
-		case 2: h ^= uint64_t(data2[1]) << 8;
-		case 1: h ^= uint64_t(data2[0]);
-				h *= m;
-		};
-		
-		h ^= h >> r;
-		h *= m;
-		h ^= h >> r;
-
-		return h;
-	}
-}

murmur_hash.h

-#pragma once
-
-#include "types.h"
-
-namespace foundation
-{
-	/// Implementation of the 64 bit MurmurHash2 function
-	/// http://murmurhash.googlepages.com/
-	uint64_t murmur_hash_64(const void *key, size_t len, uint64_t seed);
-}
Binary file added.
Binary file added.
+newaction {
+  trigger = 'clean',
+  description = 'Cleans up the project.',
+  shortname = "clean",
+  
+  execute = function()
+    os.rmdir("bin")
+    os.rmdir("build")
+  end
+}
+
+solution "foundation"
+  configurations { "debug", "release" }
+  platforms { "x32", "x64" }
+
+  location "build"
+  
+  includedirs { "inc", "src" }
+  
+  flags { "FatalWarnings", "ExtraWarnings" }
+  
+  configuration { "windows" }
+    defines { "WIN32", "_WIN32" }
+    defines { "_CRT_SECURE_NO_WARNINGS", "_CRT_NONSTDC_NO_DEPRECATE" }
+    includedirs "inc/win32"
+    
+  configuration { "debug" }
+    defines { "DEBUG" }
+    flags { "Symbols" }
+
+  configuration { "release" }
+    defines { "NDEBUG" }
+    flags { "Optimize" }
+  
+  project "unit-test"
+    kind "ConsoleApp"
+    language "C++"
+    
+    links "foundation"
+    
+    includedirs { "src" }
+    files { "src/unit-test/**.cpp",
+            "src/unit-test/**.h" }
+  
+  project "foundation"
+    kind "StaticLib"
+    language "C++"
+    
+    includedirs { "src" }
+    files { "src/foundation/**.cpp",
+            "src/foundation/**.h" }

queue.h

-#include "collection_types.h"
-#include "array.h"
-
-namespace foundation
-{
-	namespace queue 
-	{
-		/// Returns the number of items in the queue.
-		template <typename T> size_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> size_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, size_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, size_t n);
-		/// Pushes n items to the back of the queue.
-		template <typename T> void push(Queue<T> &q, const T *items, size_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, size_t new_capacity)
-		{
-			size_t end = array::size(q._data);
-			array::resize(q._data, new_capacity);
-			if (q._offset + q._size > end) {
-				size_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, size_t min_capacity = 0)
-		{
-			size_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 size_t size(const Queue<T> &q)
-		{
-			return q._size;
-		}
-
-		template<typename T> inline size_t space(const Queue<T> &q)
-		{
-			return array::size(q._data) - q._size;
-		}
-
-		template<typename T> void reserve(Queue<T> &q, size_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, size_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, size_t n)
-		{
-			if (space(q) < n)
-				queue_internal::grow(q, size(q) + n);
-			const size_t size = array::size(q._data);
-			const size_t insert = (q._offset + q._size) % size;
-			size_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)
-		{
-			size_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)
-		{
-			size_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[](size_t i)
-	{
-		return _data[(i + _offset) % array::size(_data)];
-	}
-
-	template <typename T> inline const T & Queue<T>::operator[](size_t i) const
-	{
-		return _data[(i + _offset) % array::size(_data)];
-	}
-}

src/foundation/array.h

+#pragma once
+
+#include "collection_types.h"
+#include "memory.h"
+
+#include <memory>
+
+namespace foundation {
+	namespace array
+	{
+		/// The number of elements in the array.
+		template<typename T> size_t size(const Array<T> &a) ;
+		/// Returns true if there are any elements in the array.
+		template<typename T> bool any(const Array<T> &a);
+		/// Returns true if the array is empty.
+		template<typename T> bool empty(const Array<T> &a);
+		
+		/// Used to iterate over the array.
+		template<typename T> T* begin(Array<T> &a);
+		template<typename T> const T* begin(const Array<T> &a);
+		template<typename T> T* end(Array<T> &a);
+		template<typename T> const T* end(const Array<T> &a);
+		
+		/// Returns the first/last element of the array. Don't use these on an
+		/// empty array.
+		template<typename T> T& front(Array<T> &a);
+		template<typename T> const T& front(const Array<T> &a);
+		template<typename T> T& back(Array<T> &a);
+		template<typename T> const T& back(const Array<T> &a);
+
+		/// Changes the size of the array (does not reallocate memory unless necessary).
+		template <typename T> void resize(Array<T> &a, size_t new_size);
+		/// Removes all items in the array (does not free memory).
+		template <typename T> void clear(Array<T> &a);
+		/// Reallocates the array to the specified capacity.
+		template<typename T> void set_capacity(Array<T> &a, size_t new_capacity);
+		/// Makes sure that the array has at least the specified capacity.
+		/// (If not, the array is grown.)
+		template <typename T> void reserve(Array<T> &a, size_t new_capacity);
+		/// Grows the array using a geometric progression formula, so that the ammortized
+		/// cost of push_back() is O(1). If a min_capacity is specified, the array will
+		/// grow to at least that capacity.
+		template<typename T> void grow(Array<T> &a, size_t min_capacity = 0);
+		/// Trims the array so that its capacity matches its size.
+		template <typename T> void trim(Array<T> &a);
+
+		/// Pushes the item to the end of the array.
+		template<typename T> void push_back(Array<T> &a, const T &item);
+		/// Pops the last item from the array. The array cannot be empty.
+		template<typename T> void pop_back(Array<T> &a);
+	}
+
+	namespace array
+	{
+		template<typename T> inline size_t size(const Array<T> &a) 		{return a._size;}
+		template<typename T> inline bool any(const Array<T> &a) 			{return a._size != 0;}
+		template<typename T> inline bool empty(const Array<T> &a) 			{return a._size == 0;}
+		
+		template<typename T> inline T* begin(Array<T> &a) 					{return a._data;}
+		template<typename T> inline const T* begin(const Array<T> &a) 		{return a._data;}
+		template<typename T> inline T* end(Array<T> &a) 					{return a._data + a._size;}
+		template<typename T> inline const T* end(const Array<T> &a) 		{return a._data + a._size;}
+		
+		template<typename T> inline T& front(Array<T> &a) 					{return a._data[0];}
+		template<typename T> inline const T& front(const Array<T> &a) 		{return a._data[0];}
+		template<typename T> inline T& back(Array<T> &a) 					{return a._data[a._size-1];}
+		template<typename T> inline const T& back(const Array<T> &a) 		{return a._data[a._size-1];}
+
+		template <typename T> inline void clear(Array<T> &a) {resize(a,0);}
+		template <typename T> inline void trim(Array<T> &a) {set_capacity(a,a._size);}
+
+		template <typename T> void resize(Array<T> &a, size_t new_size)
+		{
+			if (new_size > a._capacity)
+				grow(a, new_size);
+			a._size = new_size;
+		}
+
+		template <typename T> inline void reserve(Array<T> &a, size_t new_capacity)
+		{
+			if (new_capacity > a._capacity)
+				set_capacity(a, new_capacity);
+		}
+
+		template<typename T> void set_capacity(Array<T> &a, size_t new_capacity)
+		{
+			if (new_capacity == a._capacity)
+				return;
+
+			if (new_capacity < a._size)
+				resize(a, new_capacity);
+
+			T *new_data = 0;
+			if (new_capacity > 0) {
+				new_data = (T *)a._allocator->allocate(sizeof(T)*new_capacity, alignof(T));
+				memcpy(new_data, a._data, sizeof(T)*a._size);
+			}
+			a._allocator->deallocate(a._data);
+			a._data = new_data;
+			a._capacity = new_capacity;
+		}
+
+		template<typename T> void grow(Array<T> &a, size_t min_capacity)
+		{
+			size_t new_capacity = a._capacity*2 + 8;
+			if (new_capacity < min_capacity)
+				new_capacity = min_capacity;
+			set_capacity(a, new_capacity);
+		}
+
+		template<typename T> inline void push_back(Array<T> &a, const T &item)
+		{
+			if (a._size + 1 > a._capacity)
+				grow(a);
+			a._data[a._size++] = item;
+		}
+
+		template<typename T> inline void pop_back(Array<T> &a)
+		{
+			a._size--;
+		}
+	}
+
+	template <typename T>
+	inline Array<T>::Array(Allocator &allocator) : _allocator(&allocator), _size(0), _capacity(0), _data(0) {}
+
+	template <typename T>
+	inline Array<T>::~Array()
+	{
+		_allocator->deallocate(_data);
+	}
+
+	template <typename T>
+	Array<T>::Array(const Array<T> &other) : _allocator(other._allocator), _size(0), _capacity(0), _data(0)
+	{
+		const size_t n = other._size;
+		array::set_capacity(*this, n);
+		memcpy(_data, other._data, sizeof(T) * n);
+		_size = n;
+	}
+
+	template <typename T>
+	Array<T> &Array<T>::operator=(const Array<T> &other)
+	{
+		const size_t n = other._size;
+		array::resize(*this, n);
+		memcpy(_data, other._data, sizeof(T)*n);
+		return *this;
+	}
+
+	template <typename T>
+	inline T & Array<T>::operator[](size_t i)
+	{
+		return _data[i];
+	}
+
+	template <typename T>
+	inline const T & Array<T>::operator[](size_t i) const
+	{
+		return _data[i];
+	}
+}

src/foundation/collection_types.h

+#pragma once
+
+#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
+{
+	/// Dynamically resizable array of POD objects.
+	template<typename T> struct Array
+	{
+		Array(Allocator &a);
+		~Array();
+		Array(const Array &other);
+		Array &operator=(const Array &other);
+		
+		T &operator[](size_t i);
+		const T &operator[](size_t i) const;
+
+		Allocator *_allocator;
+		size_t _size;
+		size_t _capacity;
+		T *_data;
+	};
+
+	/// A double-ended queue/ring buffer.
+	template <typename T> struct Queue
+	{
+		Queue(Allocator &a);
+
+		T &operator[](size_t i);
+		const T &operator[](size_t i) const;
+
+		Array<T> _data;
+		size_t _size;
+		size_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.
+	template<typename T> struct Hash
+	{
+	public:
+		Hash(Allocator &a);
+		
+		struct Entry {
+			uint64_t key;
+			size_t next;
+			T value;
+		};
+
+		Array<size_t> _hash;
+		Array<Entry> _data;
+	};
+}

src/foundation/hash.h

+#pragma once
+
+#include "array.h"
+#include "collection_types.h"
+
+namespace foundation {
+
+	/// The hash function stores its data in a "list-in-an-array" where
+	/// indices are used instead of pointers. 
+	///
+	/// When items are removed, the array-list is repacked to always keep
+	/// it tightly ordered.
+
+	namespace hash
+	{
+		/// Returns true if the specified key exists in the hash.
+		template<typename T> bool has(const Hash<T> &h, uint64_t key);
+
+		/// Returns the value stored for the specified key, or deffault if the key
+		/// does not exist in the hash.
+		template<typename T> const T &get(const Hash<T> &h, uint64_t key, const T &deffault);
+
+		/// Sets the value for the key.
+		template<typename T> void set(Hash<T> &h, uint64_t key, const T &value);
+
+		/// Removes the key from the hash if it exists.
+		template<typename T> void remove(Hash<T> &h, uint64_t key);
+
+		/// Resizes the hash lookup table to the specified size.
+		/// (The table will grow automatically when 70 % full.)
+		template<typename T> void reserve(Hash<T> &h, size_t size);
+
+		/// Returns a pointer to the first entry in the hash table, can be used to
+		/// efficiently iterate over the elements (in random order).
+		template<typename T> const typename Hash<T>::Entry *begin(const Hash<T> &h);
+		template<typename T> const typename Hash<T>::Entry *end(const Hash<T> &h);
+	}
+
+	namespace multi_hash
+	{
+		/// Finds the first entry with the specified key.
+		template<typename T> const typename Hash<T>::Entry *find_first(const Hash<T> &h, uint64_t key);
+
+		/// Finds the next entry with the same key as e.
+		template<typename T> const typename Hash<T>::Entry *find_next(const Hash<T> &h, const typename Hash<T>::Entry *e);
+
+		/// Returns the number of entries with the key.
+		template<typename T> size_t count(const Hash<T> &h, uint64_t key);
+
+		/// Returns all the entries with the specified key.
+		/// Use a TempAllocator for the array to avoid allocating memory.
+		template<typename T> void get(const Hash<T> &h, uint64_t key, Array<T> &items);
+
+		/// Inserts the value as an aditional value for the key.
+		template<typename T> void insert(Hash<T> &h, uint64_t key, const T &value);
+
+		/// Removes the specified entry.
+		template<typename T> void remove(Hash<T> &h, const typename Hash<T>::Entry *e);
+
+		/// Removes all entries with the specified key.
+		template<typename T> void remove_all(Hash<T> &h, uint64_t key);
+	}
+
+	namespace hash_internal
+	{
+		const size_t END_OF_LIST = SIZE_MAX;
+		
+		struct FindResult
+		{
+			size_t hash_i;
+			size_t data_prev;
+			size_t data_i;
+		};	
+
+		template<typename T> size_t add_entry(Hash<T> &h, uint64_t key)
+		{
+			typename Hash<T>::Entry e;
+			e.key = key;
+			e.next = END_OF_LIST;
+			size_t ei = array::size(h._data);
+			array::push_back(h._data, e);
+			return ei;
+		}
+
+		template<typename T> void erase(Hash<T> &h, const FindResult &fr)
+		{
+			if (fr.data_prev == END_OF_LIST)
+				h._hash[fr.hash_i] = h._data[fr.data_i].next;
+			else
+				h._data[fr.data_prev].next = h._data[fr.data_i].next;
+
+			if (fr.data_i == array::size(h._data) - 1) {
+				array::pop_back(h._data);
+				return;
+			}
+
+			h._data[fr.data_i] = h._data[array::size(h._data) - 1];
+			FindResult last = find(h, h._data[fr.data_i].key);
+
+			if (last.data_prev != END_OF_LIST)
+				h._data[last.data_prev].next = fr.data_i;
+			else
+				h._hash[last.hash_i] = fr.data_i;
+		}
+
+		template<typename T> FindResult find(const Hash<T> &h, uint64_t key)
+		{
+			FindResult fr;
+			fr.hash_i = END_OF_LIST;
+			fr.data_prev = END_OF_LIST;
+			fr.data_i = END_OF_LIST;
+
+			if (array::size(h._hash) == 0)
+				return fr;
+
+			fr.hash_i = key % array::size(h._hash);
+			fr.data_i = h._hash[fr.hash_i];
+			while (fr.data_i != END_OF_LIST) {
+				if (h._data[fr.data_i].key == key)
+					return fr;
+				fr.data_prev = fr.data_i;
+				fr.data_i = h._data[fr.data_i].next;
+			}
+			return fr;
+		}
+
+		template<typename T> FindResult find(const Hash<T> &h, const typename Hash<T>::Entry *e)
+		{
+			FindResult fr;
+			fr.hash_i = END_OF_LIST;
+			fr.data_prev = END_OF_LIST;
+			fr.data_i = END_OF_LIST;
+
+			if (array::size(h._hash) == 0)
+				return fr;
+
+			fr.hash_i = e->key % array::size(h._hash);
+			fr.data_i = h._hash[fr.hash_i];
+			while (fr.data_i != END_OF_LIST) {
+				if (&h._data[fr.data_i] == e)
+					return fr;
+				fr.data_prev = fr.data_i;
+				fr.data_i = h._data[fr.data_i].next;
+			}
+			return fr;
+		}
+
+		template<typename T> size_t find_or_fail(const Hash<T> &h, uint64_t key)
+		{
+			return find(h, key).data_i;
+		}
+
+		template<typename T> size_t find_or_make(Hash<T> &h, uint64_t key)
+		{
+			const FindResult fr = find(h, key);
+			if (fr.data_i != END_OF_LIST)
+				return fr.data_i;
+
+			size_t i = add_entry(h, key);
+			if (fr.data_prev == END_OF_LIST)
+				h._hash[fr.hash_i] = i;
+			else
+				h._data[fr.data_prev].next = i;
+			return i;
+		}
+
+		template<typename T> size_t make(Hash<T> &h, uint64_t key)
+		{
+			const FindResult fr = find(h, key);
+			const size_t i = add_entry(h, key);
+
+			if (fr.data_prev == END_OF_LIST)
+				h._hash[fr.hash_i] = i;
+			else
+				h._data[fr.data_prev].next = i;
+
+			h._data[i].next = fr.data_i;
+			return i;
+		}	
+
+		template<typename T> void find_and_erase(Hash<T> &h, uint64_t key)
+		{
+			const FindResult fr = find(h, key);
+			if (fr.data_i != END_OF_LIST)
+				erase(h, fr);
+		}
+
+		template<typename T> void rehash(Hash<T> &h, size_t new_size)
+		{
+			Hash<T> nh(*h._hash._allocator);
+			array::resize(nh._hash, new_size);
+			array::reserve(nh._data, array::size(h._data));
+			for (size_t i=0; i<new_size; ++i)
+				nh._hash[i] = END_OF_LIST;
+			for (size_t i=0; i<array::size(h._data); ++i) {
+				const typename Hash<T>::Entry &e = h._data[i];
+				multi_hash::insert(nh, e.key, e.value);
+			}
+
+			Hash<T> empty(*h._hash._allocator);
+			h.~Hash<T>();
+			memcpy(&h, &nh, sizeof(Hash<T>));
+			memcpy(&nh, &empty, sizeof(Hash<T>));
+		}
+
+		template<typename T> bool full(const Hash<T> &h)
+		{
+			const float max_load_factor = 0.7f;
+			return array::size(h._data) >= array::size(h._hash) * max_load_factor;
+		}
+
+		template<typename T> void grow(Hash<T> &h)
+		{
+			const size_t new_size = array::size(h._data) * 2 + 10;
+			rehash(h, new_size);
+		}
+	}
+
+	namespace hash
+	{
+		template<typename T> bool has(const Hash<T> &h, uint64_t key)
+		{
+			return hash_internal::find_or_fail(h, key) != hash_internal::END_OF_LIST;
+		}
+
+		template<typename T> const T &get(const Hash<T> &h, uint64_t key, const T &deffault)
+		{
+			const size_t i = hash_internal::find_or_fail(h, key);
+			return i == hash_internal::END_OF_LIST ? deffault : h._data[i].value;
+		}
+
+		template<typename T> void set(Hash<T> &h, uint64_t key, const T &value)
+		{
+			if (array::size(h._hash) == 0)
+				hash_internal::grow(h);
+
+			const size_t i = hash_internal::find_or_make(h, key);
+			h._data[i].value = value;
+			if (hash_internal::full(h))
+				hash_internal::grow(h);
+		}
+
+		template<typename T> void remove(Hash<T> &h, uint64_t key)
+		{
+			hash_internal::find_and_erase(h, key);
+		}
+
+		template<typename T> void reserve(Hash<T> &h, size_t size)
+		{
+			hash_internal::rehash(h, size);
+		}
+
+		template<typename T> const typename Hash<T>::Entry *begin(const Hash<T> &h)
+		{
+			return array::begin(h._data);
+		}
+
+		template<typename T> const typename Hash<T>::Entry *end(const Hash<T> &h)
+		{
+			return array::end(h._data);
+		}
+	}
+
+	namespace multi_hash
+	{
+		template<typename T> const typename Hash<T>::Entry *find_first(const Hash<T> &h, uint64_t key)
+		{
+			const size_t i = hash_internal::find_or_fail(h, key);
+			return i == hash_internal::END_OF_LIST ? 0 : &h._data[i];
+		}
+
+		template<typename T> const typename Hash<T>::Entry *find_next(const Hash<T> &h, const typename Hash<T>::Entry *e)
+		{
+			size_t i = e->next;
+			while (i != hash_internal::END_OF_LIST) {
+				if (h._data[i].key == e->key)
+					return &h._data[i];
+				i = h._data[i].next;
+			}
+			return 0;
+		}
+
+		template<typename T> size_t count(const Hash<T> &h, uint64_t key)
+		{
+			size_t i = 0;
+			const typename Hash<T>::Entry *e = find_first(h, key);
+			while (e) {
+				++i;
+				e = find_next(h, e);
+			}
+			return i;
+		}
+
+		template<typename T> void get(const Hash<T> &h, uint64_t key, Array<T> &items)
+		{
+			const typename Hash<T>::Entry *e = find_first(h, key);
+			while (e) {
+				array::push_back(items, e->value);
+				e = find_next(h, e);
+			}
+		}
+
+		template<typename T> void insert(Hash<T> &h, uint64_t key, const T &value)
+		{
+			if (array::size(h._hash) == 0)
+				hash_internal::grow(h);
+
+			const size_t i = hash_internal::make(h, key);
+			h._data[i].value = value;
+			if (hash_internal::full(h))
+				hash_internal::grow(h);
+		}
+
+		template<typename T> void remove(Hash<T> &h, const typename Hash<T>::Entry *e)
+		{
+			const hash_internal::FindResult fr = hash_internal::find(h, e);
+			if (fr.data_i != hash_internal::END_OF_LIST)
+				hash_internal::erase(h, fr);
+		}
+
+		template<typename T> void remove_all(Hash<T> &h, uint64_t key)
+		{
+			while (hash::has(h, key))
+				hash::remove(h, key);
+		}
+	}
+
+
+	template <typename T> Hash<T>::Hash(Allocator &a) :
+		_hash(a), _data(a)
+	{}
+}

src/foundation/math_types.h

+#pragma once
+
+#include "types.h"
+
+namespace foundation
+{
+	struct Vector2
+	{
+		float x, y;
+	};
+
+	struct Vector3
+	{
+		float x, y, z;
+	};
+
+	struct Vector4
+	{
+		float x, y, z, w;
+	};
+
+	struct Quaternion
+	{
+		float x, y, z, w;
+	};
+
+	struct Matrix3x3
+	{
+		Vector3 x, y, z;
+	};
+
+	struct Matrix4x4
+	{
+		Vector4 x, y, z, t;
+	};
+
+	struct AABB
+	{
+		Vector3 min, max;
+	};
+
+	struct OOBB
+	{
+		Matrix4x4 tm;
+		AABB aabb;
+	};
+}

src/foundation/memory.cpp

+#include "memory.h"
+
+#include <stdlib.h>
+#include <assert.h>
+#include <new>
+
+namespace {
+	using namespace foundation;
+
+	// Header stored at the beginning of a memory allocation to indicate the
+	// size of the allocated data.
+	struct Header {
+		size_t size;
+	};
+
+	// If we need to align the memory allocation we pad the header with this
+	// value after storing the size. That way we can 
+	const size_t HEADER_PAD_VALUE = SIZE_MAX;
+
+	// Given a pointer to the header, returns a pointer to the data that follows it.
+	inline void *data_pointer(Header *header, size_t align) {
+		void *p = header + 1;
+		return memory::align_forward(p, align);
+	}
+
+	// Given a pointer to the data, returns a pointer to the header before it.
+	inline Header *header(void *data)
+	{
+		size_t *p = (size_t *)data;
+		while (p[-1] == HEADER_PAD_VALUE)
+			--p;
+		return (Header *)p - 1;
+	}
+
+	// Stores the size in the header and pads with HEADER_PAD_VALUE up to the
+	// data pointer.
+	inline void fill(Header *header, void *data, size_t size)
+	{
+		header->size = size;
+		size_t *p = (size_t *)(header + 1);
+		while (p < data)
+			*p++ = HEADER_PAD_VALUE;
+	}
+
+	/// An allocator that uses the default system malloc(). Allocations are
+	/// padded so that we can store the size of each allocation and align them
+	/// to the desired alignment.
+	///
+	/// (Note: An OS-specific allocator that can do alignment and tracks size
+	/// does need this padding and can thus be more efficient than the
+	/// MallocAllocator.)
+	class MallocAllocator : public Allocator
+	{
+		size_t _total_allocated;
+
+		// Returns the size to allocate from malloc() for a given size and align.		
+		static inline size_t size_with_padding(size_t size, size_t align) {
+			return size + align + sizeof(Header);
+		}
+
+	public: