Commits

Anonymous committed eaa574a Draft

Oops, borked and forgot most of the important stuff.

Also added changed the math classes to floats and doubles.

Comments (0)

Files changed (18)

 *.o
 unit_test
 unit-test.exe
-foundation
+src/foundation/foundation
 foundation.lib
 CMakeFiles
-.directory
 src/*.cmake
 src/Makefile
 src/CMakeFiles

inc/foundation/win32/platform.msvc.h

+#pragma once
+// # MSVC (2010) specific code
+#ifdef _MSC_VER
+
+#include <stdarg.h>
+#include <stdio.h>
+
+/// Snprintf is not part of C89.
+/// It's standard only in C99. Microsoft has no plan supporting C99.
+#define snprintf c99_snprintf
+#define vsnprintf c99_vsnprintf
+
+/// MSVC implementation of the C99 vsnprintf function.
+inline int c99_vsnprintf( char* str, size_t size, const char* format, va_list ap )
+{
+    int count = -1;
+    if ( size != 0 )
+    {
+        count = _vsnprintf_s( str, size, _TRUNCATE, format, ap );
+    }
+    if ( count == -1 )
+    {
+        count = _vscprintf( format, ap );
+    }
+    return count;
+}
+
+
+/// MSVC implementation of the C99 snprintf function.
+inline int c99_snprintf( char* str, size_t size, const char* format, ... )
+{
+    int count;
+    va_list ap;
+    va_start( ap, format );
+    count = c99_vsnprintf( str, size, format, ap );
+    va_end( ap );
+    return count;
+}
+
+// Macro Overrides
+// ---------------
+// 
+// Ugly hack to disable warnings for macro overrides.
+__pragma(warning(push))
+__pragma(warning(disable:4005))
+
+/// Disable the compiler warning C4127 for the do {} while(0) loops.
+#define MAKE_DELETE(a, T, p) \
+    __pragma(warning(push)) \
+    __pragma(warning(disable:4127)) \
+    do {if (p) {(p)->~T(); a.deallocate(p);}} while (0) \
+    __pragma(warning(pop))
+
+// Restore the macro override warning.
+__pragma(warning(pop))
+
+#endif // _MSC_VER

inc/foundation/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

src/foundation/CMakeLists.txt

+cmake_minimum_required(VERSION 2.8)
+
+set(incDir ${CMAKE_CURRENT_SOURCE_DIR}/../../inc/)
+if (WIN32)
+  set(WIN32_FOUNDATION_PLATFORM_INCLUDES
+    ${incDir}/foundation/win32/stdint.h
+  )
+  if (MSVC)
+    set(MSVC_FOUNDATION_PLATFORM_INCLUDES
+      ${incDir}/foundation/win32/platform.msvc.h
+    )
+  endif(MSVC) 
+endif(WIN32)
+set(FOUNDATION_PLATFORM_INCLUDES
+  ${WIN32_FOUNDATION_PLATFORM_INCLUDES}
+  ${MSVC_FOUNDATION_PLATFORM_INCLUDES}
+)
+set(FOUNDATION_INCLUDES
+    ${FOUNDATION_PLATFORM_INCLUDES}
+    ${incDir}/foundation/
+    array.h
+    collection_types.h
+    hash.h
+    math_types.h
+    memory.h
+    memory_types.h
+    murmur_hash.h
+    queue.h
+    string_stream.h
+    temp_allocator.h
+    types.h
+)
+set(FOUNDATION_SOURCES
+    memory.cpp
+    murmur_hash.cpp
+    string_stream.cpp
+)
+
+
+add_library( bitsquid_foundation
+  ${FOUNDATION_INCLUDES}
+  ${FOUNDATION_SOURCES}
+  )

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);
+
+		/// Remove all elements from the hash.
+		template<typename T> void clear(Hash<T> &h);
+
+		/// 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> void clear(Hash<T> &h)
+		{
+			array::clear( h._data );
+			array::clear( h._hash );
+		}
+
+		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
+{
+	// float based
+	struct Vector2F
+	{
+		float x, y;
+	};
+
+	struct Vector3F
+	{
+		float x, y, z;
+	};
+
+	struct Vector4F
+	{
+		float x, y, z, w;
+	};
+
+	struct QuaternionF
+	{
+		float x, y, z, w;
+	};
+
+	struct Matrix3x3F
+	{
+		Vector3F x, y, z;
+	};
+
+	struct Matrix4x4F
+	{
+		Vector4F x, y, z, t;
+	};
+
+	struct AABBF
+	{
+		Vector3F min, max;
+	};
+
+	struct OOBBF
+	{
+		Matrix4x4F tm;
+		AABBF aabb;
+	};
+
+
+	// double based
+	struct Vector2D
+	{
+		double x, y;
+	};
+
+	struct Vector3D
+	{
+		double x, y, z;
+	};
+
+	struct Vector4D
+	{
+		double x, y, z, w;
+	};
+
+	struct QuaternionD
+	{
+		double x, y, z, w;
+	};
+
+	struct Matrix3x3D
+	{
+		Vector3D x, y, z;
+	};
+
+	struct Matrix4x4D
+	{
+		Vector4D x, y, z, t;
+	};
+
+	struct AABBD
+	{
+		Vector3D min, max;
+	};
+
+	struct OOBBD
+	{
+		Matrix4x4D tm;
+		AABBD 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:
+		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();
+		}
+	}
+}

src/foundation/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);
+	}
+}
+
+#if _MSC_VER
+	// Override the MAKE_DELETE macro to disable the warning in MSVC
+	#include "platform.msvc.h"
+#endif

src/foundation/memory_types.h

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

src/foundation/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;
+	}
+}

src/foundation/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);
+}

src/foundation/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/string_stream.cpp

+#include "string_stream.h"
+
+#include <stdarg.h>
+
+namespace foundation 
+{
+	namespace string_stream
+	{
+		Buffer & printf(Buffer &b, const char *format, ...)
+		{
+			va_list args;
+			
+			va_start(args, format);
+			int n = vsnprintf(NULL, 0, format, args);
+			va_end(args);
+
+			size_t end = array::size(b);
+			array::resize(b, end + n + 1);
+			
+			va_start(args, format);
+			vsnprintf(array::begin(b) + end, n + 1, format, args);
+			va_end(args);
+			
+			array::resize(b, end + n);
+
+			return b;
+		}
+
+		Buffer & tab(Buffer &b, size_t column)
+		{
+			size_t current_column = 0;
+			size_t i = array::size(b) - 1;
+			while (i != SIZE_MAX && b[i] != '\n' && b[i] != '\r') {
+				++current_column;
+				--i;
+			}
+			if (current_column < column)
+				repeat(b, column - current_column, ' ');
+			return b;
+		}
+
+		Buffer & repeat(Buffer &b, size_t count, char c)
+		{
+			for (size_t i=0; i<count; ++i)
+				array::push_back(b, c);
+			return b;
+		}
+	}
+}

src/foundation/string_stream.h

+#pragma once
+
+#include "collection_types.h"
+#include "array.h"
+
+#include <string.h>
+#include <stdio.h>
+
+
+#if _MSC_VER
+	// MSVC requires snprintf.
+	#include <win32/platform.msvc.h>
+#endif
+
+
+namespace foundation
+{
+	/// Functions for operating on an Array<char> as a stream of characters,
+	/// useful for string formatting, etc.
+	namespace string_stream
+	{
+		typedef Array<char> Buffer;
+
+		/// Dumps the item to the stream using a default formatting.
+		Buffer & operator<<(Buffer &b, char c);
+		Buffer & operator<<(Buffer &b, const char *s);
+		Buffer & operator<<(Buffer &b, float f);
+		Buffer & operator<<(Buffer &b, int32_t i);
+		Buffer & operator<<(Buffer &b, uint32_t i);
+		Buffer & operator<<(Buffer &b, uint64_t i);
+
+		/// Uses printf to print formatted data to the stream.
+		Buffer & printf(Buffer &b, const char *format, ...);
+
+		/// Pushes the raw data to the stream.
+		Buffer & push(Buffer &b, const char *data, size_t n);
+
+		/// Pads the stream with spaces until it is aligned at the specified column.
+		/// Can be used to column align data. (Assumes each char is 1 space wide,
+		/// i.e. does not work with UTF-8 data.)
+		Buffer & tab(Buffer &b, size_t column);
+
+		/// Adds the specified number of c to the stream.
+		Buffer & repeat(Buffer &b, size_t count, char c);
+
+		/// Returns the stream as a C-string. There will always be a \0 character
+		/// at the end of the returned string. You don't have to explicitly add it
+		/// to the buffer.
+		const char *c_str(Buffer &b);
+	}
+
+	namespace string_stream_internal
+	{
+		using namespace string_stream;
+
+		template <typename T>
+		inline Buffer &printf_small(Buffer &b, const char *fmt, const T &t)
+		{
+			char s[32];
+			#ifndef _WIN32
+			  snprintf(s, 32, fmt, t);
+			#else
+			  _snprintf(s, 32, fmt, t);
+			#endif
+			return (b << s);
+		}
+	}
+
+	namespace string_stream
+	{
+		inline Buffer & operator<<(Buffer &b, char c)
+		{
+			array::push_back(b, c);
+			return b;
+		}
+
+		inline Buffer & operator<<(Buffer &b, const char *s)
+		{
+			return push(b, s, strlen(s));
+		}
+
+		inline Buffer & operator<<(Buffer &b, float f)
+		{
+			return string_stream_internal::printf_small(b, "%g", f);
+		}
+
+		inline Buffer & operator<<(Buffer &b, int32_t i)
+		{
+			return string_stream_internal::printf_small(b, "%d", i);
+		}
+
+		inline Buffer & operator<<(Buffer &b, uint32_t i)
+		{
+			return string_stream_internal::printf_small(b, "%u", i);
+		}
+
+		inline Buffer & operator<<(Buffer &b, uint64_t i)
+		{
+			return string_stream_internal::printf_small(b, "%01llx", i);
+		}
+
+		inline Buffer & push(Buffer &b, const char *data, size_t n)
+		{
+			size_t end = array::size(b);
+			array::resize(b, end + n);
+			memcpy(array::begin(b) + end, data, n);
+			return b;
+		}
+
+		inline const char *c_str(Buffer &b)
+		{
+			// Ensure there is a \0 at the end of the buffer.
+			array::push_back(b, '\0');
+			array::pop_back(b);
+			return array::begin(b);
+		}
+	}
+}

src/foundation/temp_allocator.h

+#pragma once
+
+#include "memory.h"
+
+namespace foundation
+{
+	/// A temporary memory allocator that primarily allocates memory from a
+	/// local stack buffer of size BUFFER_SIZE. If that memory is exhausted it will
+	/// use the backing allocator (typically a scratch allocator).
+	///
+	/// Memory allocated with a TempAllocator does not have to be deallocated. It is
+	/// automatically deallocated when the TempAllocator is destroyed.
+	template <size_t BUFFER_SIZE>
+	class TempAllocator : public Allocator
+	{
+	public:
+		/// Creates a new temporary allocator using the specified backing allocator.
+		TempAllocator(Allocator &backing = memory_globals::default_scratch_allocator());
+		virtual ~TempAllocator();
+
+		virtual void *allocate(size_t size, size_t align = DEFAULT_ALIGN);
+		
+		/// Deallocation is a NOP for the TempAllocator. The memory is automatically
+		/// deallocated when the TempAllocator is destroyed.
+		virtual void deallocate(void *) {}
+
+		/// Returns SIZE_NOT_TRACKED.
+		virtual size_t allocated_size(void *) {return SIZE_NOT_TRACKED;}
+
+		/// Returns SIZE_NOT_TRACKED.
+		virtual size_t total_allocated() {return SIZE_NOT_TRACKED;}
+
+	private:
+		char _buffer[BUFFER_SIZE];	//< Local stack buffer for allocations.
+		Allocator &_backing;		//< Backing allocator if local memory is exhausted.
+		char *_start;				//< Start of current allocation region
+		char *_p;					//< Current allocation pointer.
+		char *_end;					//< End of current allocation region
+		unsigned _chunk_size;		//< Chunks to allocate from backing allocator
+	};
+
+	// If possible, use one of these predefined sizes for the TempAllocator to avoid
+	// unnecessary template instantiation.
+	typedef TempAllocator<64> TempAllocator64;
+	typedef TempAllocator<128> TempAllocator128;
+	typedef TempAllocator<256> TempAllocator256;
+	typedef TempAllocator<512> TempAllocator512;
+	typedef TempAllocator<1024> TempAllocator1024;
+	typedef TempAllocator<2048> TempAllocator2048;
+	typedef TempAllocator<4096> TempAllocator4096;
+
+	// ---------------------------------------------------------------
+	// Inline function implementations
+	// ---------------------------------------------------------------
+
+	template <size_t BUFFER_SIZE>
+	TempAllocator<BUFFER_SIZE>::TempAllocator(Allocator &backing) : _backing(backing), _chunk_size(4*1024)
+	{
+		_p = _start = _buffer;
+		_end = _start + BUFFER_SIZE;
+		*(void **)_start = 0;
+		_p += sizeof(void *);
+	}
+
+	template <size_t BUFFER_SIZE>
+	TempAllocator<BUFFER_SIZE>::~TempAllocator()
+	{
+		void *p = *(void **)_buffer;
+		while (p) {
+			void *next = *(void **)p;
+			_backing.deallocate(p);
+			p = next;
+		}
+	}
+
+	template <size_t BUFFER_SIZE>
+	void *TempAllocator<BUFFER_SIZE>::allocate(size_t size, size_t align)
+	{
+		_p = (char *)memory::align_forward(_p, align);
+		if ((int)size > _end - _p) {
+			size_t to_allocate = sizeof(void *) + size + align;
+			if (to_allocate < _chunk_size)
+				to_allocate = _chunk_size;
+			_chunk_size *= 2;
+			void *p = _backing.allocate(to_allocate);
+			*(void **)_start = p;
+			_p = _start = (char *)p;
+			_end = _start + to_allocate;
+			*(void **)_start = 0;
+			_p += sizeof(void *);
+			memory::align_forward(p, align);
+		}
+		void *result = _p;
+		_p += size;
+		return result;
+	}
+}

src/foundation/types.h

+#pragma once
+
+#define __STDC_LIMIT_MACROS
+#include <stdint.h>
+#include <stddef.h>
+
+#define SIZE_BITS (8*sizeof(size_t))
+
+#ifndef alignof
+	#define alignof(x) __alignof(x)
+#endif