Commits

Anonymous committed 63345aa Draft

Updated hgignore, removed files from repository that were renamed or moved.

Comments (0)

Files changed (18)

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

LICENCSE

-Copyright (C) 2012 Bitsquid AB
-
-Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
-
-The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

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> uint32_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, uint32_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, uint32_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, uint32_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, uint32_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 uint32_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, uint32_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, uint32_t new_capacity)
-		{
-			if (new_capacity > a._capacity)
-				set_capacity(a, new_capacity);
-		}
-
-		template<typename T> void set_capacity(Array<T> &a, uint32_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, uint32_t min_capacity)
-		{
-			uint32_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 uint32_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 uint32_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[](uint32_t i)
-	{
-		return _data[i];
-	}
-
-	template <typename T>
-	inline const T & Array<T>::operator[](uint32_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[](uint32_t i);
-		const T &operator[](uint32_t i) const;
-
-		Allocator *_allocator;
-		uint32_t _size;
-		uint32_t _capacity;
-		T *_data;
-	};
-
-	/// A double-ended queue/ring buffer.
-	template <typename T> struct Queue
-	{
-		Queue(Allocator &a);
-
-		T &operator[](uint32_t i);
-		const T &operator[](uint32_t i) const;
-
-		Array<T> _data;
-		uint32_t _size;
-		uint32_t _offset;
-	};
-
-	/// Hash from an uint64_t to POD objects. If you want to use a generic key
-	/// object, use a hash function to map that object to an uint64_t.
-	template<typename T> struct Hash
-	{
-	public:
-		Hash(Allocator &a);
-		
-		struct Entry {
-			uint64_t key;
-			uint32_t next;
-			T value;
-		};
-
-		Array<uint32_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, uint32_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> uint32_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 uint32_t END_OF_LIST = 0xffffffffu;
-		
-		struct FindResult
-		{
-			uint32_t hash_i;
-			uint32_t data_prev;
-			uint32_t data_i;
-		};	
-
-		template<typename T> uint32_t add_entry(Hash<T> &h, uint64_t key)
-		{
-			typename Hash<T>::Entry e;
-			e.key = key;
-			e.next = END_OF_LIST;
-			uint32_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> uint32_t find_or_fail(const Hash<T> &h, uint64_t key)
-		{
-			return find(h, key).data_i;
-		}
-
-		template<typename T> uint32_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;
-
-			uint32_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> uint32_t make(Hash<T> &h, uint64_t key)
-		{
-			const FindResult fr = find(h, key);
-			const uint32_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, uint32_t new_size)
-		{
-			Hash<T> nh(*h._hash._allocator);
-			array::resize(nh._hash, new_size);
-			array::reserve(nh._data, array::size(h._data));
-			for (uint32_t i=0; i<new_size; ++i)
-				nh._hash[i] = END_OF_LIST;
-			for (uint32_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 uint32_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 uint32_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 uint32_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, uint32_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 uint32_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)
-		{
-			uint32_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> uint32_t count(const Hash<T> &h, uint64_t key)
-		{
-			uint32_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 uint32_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)
-	{}
-}

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 {
-		uint32_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 uint32_t HEADER_PAD_VALUE = 0xffffffffu;
-
-	// Given a pointer to the header, returns a pointer to the data that follows it.
-	inline void *data_pointer(Header *header, uint32_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)
-	{
-		uint32_t *p = (uint32_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, uint32_t size)
-	{
-		header->size = size;
-		uint32_t *p = (uint32_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
-	{
-		uint32_t _total_allocated;
-
-		// Returns the size to allocate from malloc() for a given size and align.		
-		static inline uint32_t size_with_padding(uint32_t size, uint32_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(uint32_t size, uint32_t align) {
-			const uint32_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 uint32_t allocated_size(void *p) {
-			return header(p)->size;
-		}
-
-		virtual uint32_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, uint32_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(uint32_t size, uint32_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) | 0x80000000u;
-				
-				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 & 0x80000000u) == 0);
-			h->size = h->size | 0x80000000u;
-
-			// Advance the free pointer past all free slots.
-			while (_free != _allocate) {
-				Header *h = (Header *)_free;
-				if ((h->size & 0x80000000u) == 0)
-					break;
-
-				_free += h->size & 0x7fffffffu;
-				if (_free == _end)
-					_free = _begin;
-			}
-		}
-
-		virtual uint32_t allocated_size(void *p) {
-			Header *h = header(p);
-			return h->size - ((char *)p - (char *)h);
-		}
-
-		virtual uint32_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(uint32_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 uint32_t DEFAULT_ALIGN = 4;
-
-		Allocator() {}
-		virtual ~Allocator() {}
-		
-		/// Allocates the specified amount of memory aligned to the specified alignment.
-		virtual void *allocate(uint32_t size, uint32_t align = DEFAULT_ALIGN) = 0;
-
-		/// Frees an allocation previously made with allocate().
-		virtual void deallocate(void *p) = 0;
-
-		static const uint32_t SIZE_NOT_TRACKED = 0xffffffffu;
-
-		/// 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 uint32_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 uint32_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(uint32_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, uint32_t align);
-		inline void *pointer_add(void *p, uint32_t bytes);
-		inline const void *pointer_add(const void *p, uint32_t bytes);
-		inline void *pointer_sub(void *p, uint32_t bytes);
-		inline const void *pointer_sub(const void *p, uint32_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, uint32_t align) {
-		uintptr_t pi = uintptr_t(p);
-		const uint32_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, uint32_t bytes)	{
-		return (void*)((char *)p + bytes);
-	}
-
-	inline const void *memory::pointer_add(const void *p, uint32_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, uint32_t bytes)	{
-		return (void*)((char *)p - bytes);
-	}
-
-	inline const void *memory::pointer_sub(const void *p, uint32_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, uint32_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, uint32_t len, uint64_t seed);
-}

queue.h

-#include "collection_types.h"
-#include "array.h"
-
-namespace foundation
-{
-	namespace queue 
-	{
-		/// Returns the number of items in the queue.
-		template <typename T> uint32_t size(const Queue<T> &q);
-		/// Returns the ammount of free space in the queue/ring buffer.
-		/// This is the number of items we can push before the queue needs to grow.
-		template<typename T> uint32_t space(const Queue<T> &q);
-		/// Makes sure the queue has room for at least the specified number of items.
-		template<typename T> void reserve(Queue<T> &q, uint32_t size);
-
-		/// Pushes the item to the end of the queue.
-		template<typename T> void push_back(Queue<T> &q, const T &item);
-		/// Pops the last item from the queue. The queue cannot be empty.
-		template<typename T> void pop_back(Queue<T> &q);
-		/// Pushes the item to the front of the queue.
-		template<typename T> void push_front(Queue<T> &q, const T &item);
-		/// Pops the first item from the queue. The queue cannot be empty.
-		template<typename T> void pop_front(Queue<T> &q);
-
-		/// Consumes n items from the front of the queue.
-		template <typename T> void consume(Queue<T> &q, uint32_t n);
-		/// Pushes n items to the back of the queue.
-		template <typename T> void push(Queue<T> &q, const T *items, uint32_t n);
-
-		/// Returns the begin and end of the continuous chunk of elements at
-		/// the start of the queue. (Note that this chunk does not necessarily
-		/// contain all the elements in the queue (if the queue wraps around
-		/// the array).
-		///
-		/// This is useful for when you want to process many queue elements at
-		/// once.
-		template<typename T> T* begin_front(Queue<T> &q);
-		template<typename T> const T* begin_front(const Queue<T> &q);
-		template<typename T> T* end_front(Queue<T> &q);
-		template<typename T> const T* end_front(const Queue<T> &q);
-	}
-
-	namespace queue_internal
-	{
-		// Can only be used to increase the capacity.
-		template<typename T> void increase_capacity(Queue<T> &q, uint32_t new_capacity)
-		{
-			uint32_t end = array::size(q._data);
-			array::resize(q._data, new_capacity);
-			if (q._offset + q._size > end) {
-				uint32_t end_items = end - q._offset;
-				memmove(array::begin(q._data) + new_capacity - end_items, array::begin(q._data) + q._offset, end_items * sizeof(T));
-				q._offset += new_capacity - end;
-			}
-		}
-
-		template<typename T> void grow(Queue<T> &q, uint32_t min_capacity = 0)
-		{
-			uint32_t new_capacity = array::size(q._data)*2 + 8;
-			if (new_capacity < min_capacity)
-				new_capacity = min_capacity;
-			increase_capacity(q, new_capacity);
-		}
-	}
-
-	namespace queue 
-	{
-		template<typename T> inline uint32_t size(const Queue<T> &q)
-		{
-			return q._size;
-		}
-
-		template<typename T> inline uint32_t space(const Queue<T> &q)
-		{
-			return array::size(q._data) - q._size;
-		}
-
-		template<typename T> void reserve(Queue<T> &q, uint32_t size)
-		{
-			if (size > q._size)
-				queue_internal::increase_capacity(q, size);
-		}
-
-		template<typename T> inline void push_back(Queue<T> &q, const T &item)
-		{
-			if (!space(q))
-				queue_internal::grow(q);
-			q[q._size++] = item;
-		}
-
-		template<typename T> inline void pop_back(Queue<T> &q)
-		{
-			--q._size;
-		}
-		
-		template<typename T> inline void push_front(Queue<T> &q, const T &item)
-		{
-			if (!space(q))
-				queue_internal::grow(q);
-			q._offset = (q._offset - 1 + array::size(q._data)) % array::size(q._data);
-			++q._size;
-			q[0] = item;
-		}
-		
-		template<typename T> inline void pop_front(Queue<T> &q)
-		{
-			q._offset = (q._offset + 1) % array::size(q._data);
-			--q._size;
-		}
-
-		template <typename T> inline void consume(Queue<T> &q, uint32_t n)
-		{
-			q._offset = (q._offset + n) % array::size(q._data);
-			q._size -= n;
-		}
-
-		template <typename T> void push(Queue<T> &q, const T *items, uint32_t n)
-		{
-			if (space(q) < n)
-				queue_internal::grow(q, size(q) + n);
-			const uint32_t size = array::size(q._data);
-			const uint32_t insert = (q._offset + q._size) % size;
-			uint32_t to_insert = n;
-			if (insert + to_insert > size)
-				to_insert = size - insert;
-			memcpy(array::begin(q._data) + insert, items, to_insert * sizeof(T));
-			q._size += to_insert;
-			items += to_insert;
-			n -= to_insert;
-			memcpy(array::begin(q._data), items, n * sizeof(T));
-			q._size += n;
-		}
-
-		template<typename T> inline T* begin_front(Queue<T> &q)
-		{
-			return array::begin(q._data) + q._offset;
-		}
-		template<typename T> inline const T* begin_front(const Queue<T> &q)
-		{
-			return array::begin(q._data) + q._offset;
-		}
-		template<typename T> T* end_front(Queue<T> &q)
-		{
-			uint32_t end = q._offset + q._size;
-			return end > array::size(q._data) ? array::end(q._data) : array::begin(q._data) + end;
-		}
-		template<typename T> const T* end_front(const Queue<T> &q)
-		{
-			uint32_t end = q._offset + q._size;
-			return end > array::size(q._data) ? array::end(q._data) : array::begin(q._data) + end;
-		}
-	}
-
-	template <typename T> inline Queue<T>::Queue(Allocator &allocator) : _data(allocator), _size(0), _offset(0) {}
-
-	template <typename T> inline T & Queue<T>::operator[](uint32_t i)
-	{
-		return _data[(i + _offset) % array::size(_data)];
-	}
-
-	template <typename T> inline const T & Queue<T>::operator[](uint32_t i) const
-	{
-		return _data[(i + _offset) % array::size(_data)];
-	}
-}

rakefile

-# constants
-
-COMPILER = "g++"
-EXEC = "unit_test"
-# Use -DPLATFORM_BIG_ENDIAN for big endian platforms
-FLAGS = "-Wall -Wextra -g"
-
-OBJECTS = %w(unit_test.o memory.o murmur_hash.o string_stream.o)
-HEADERS = %w(array.h collection_types.h memory.h memory_types.h types.h 
-	temp_allocator.h hash.h string_stream.h queue.h)
-
-# tasks
-
-task :build => [EXEC]
-
-task :test => :build do
-	sh "./#{EXEC}"
-end
-
-task :default => :test
-
-desc "Clean stuff"
-task :clean do
-	files = (Dir["*.o"] + Dir["#{EXEC}"]).uniq
-	rm_f files unless files.empty?
-end
-
-# rules
-
-rule '.o' => '.cpp' do |target|
-	sh "#{COMPILER} #{FLAGS} -c -o #{target.name} #{target.source}"
-end
-
-file EXEC => OBJECTS do
-	sh "#{COMPILER} #{FLAGS} #{OBJECTS.join(" ")} -o #{EXEC}"
-end
-
-# dependencies
-
-file 'unit_test.o' => %w(unit_test.cpp) + HEADERS
-file 'memory.o' => %w(memory.cpp) + %w(types.h memory_types.h memory.h)
-file 'murmur_hash.o' => %w(murmur_hash.cpp) + %w(murmur_hash.h)
-file 'string_stream.o' => %w(string_stream.cpp) + %w(string_stream.h collection_types.h array.h types.h memory_types.h  )

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);
-
-			uint32_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, uint32_t column)
-		{
-			uint32_t current_column = 0;
-			uint32_t i = array::size(b) - 1;
-			while (i != 0xffffffffu && b[i] != '\n' && b[i] != '\r') {
-				++current_column;
-				--i;
-			}
-			if (current_column < column)
-				repeat(b, column - current_column, ' ');
-			return b;
-		}
-
-		Buffer & repeat(Buffer &b, uint32_t count, char c)
-		{
-			for (uint32_t i=0; i<count; ++i)
-				array::push_back(b, c);
-			return b;
-		}
-	}
-}

string_stream.h

-#pragma once
-
-#include "collection_types.h"
-#include "array.h"
-
-#include <string.h>
-#include <stdio.h>
-
-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, uint32_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, uint32_t column);
-
-		/// Adds the specified number of c to the stream.
-		Buffer & repeat(Buffer &b, uint32_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];
-			snprintf(s, 32, fmt, t);
-			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, uint32_t n)
-		{
-			unsigned int 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);
-		}
-	}
-}

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 <int 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(uint32_t size, uint32_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 uint32_t allocated_size(void *) {return SIZE_NOT_TRACKED;}
-
-		/// Returns SIZE_NOT_TRACKED.
-		virtual uint32_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 <int 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 <int BUFFER_SIZE>
-	TempAllocator<BUFFER_SIZE>::~TempAllocator()
-	{
-		void *p = *(void **)_buffer;
-		while (p) {
-			void *next = *(void **)p;
-			_backing.deallocate(p);
-			p = next;
-		}
-	}
-
-	template <int BUFFER_SIZE>
-	void *TempAllocator<BUFFER_SIZE>::allocate(uint32_t size, uint32_t align)
-	{
-		_p = (char *)memory::align_forward(_p, align);
-		if ((int)size > _end - _p) {
-			uint32_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;
-	}
-}

types.h

-#pragma once
-
-#include <stdint.h>
-
-#ifndef alignof
-	#define alignof(x) __alignof(x)
-#endif

unit_test.cpp

-#include "queue.h"
-#include "string_stream.h"
-#include "murmur_hash.h"
-#include "hash.h"
-#include "temp_allocator.h"
-#include "array.h"
-#include "memory.h"
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-#include <assert.h>
-#include <algorithm>
-
-#define ASSERT(x) assert(x)
-
-namespace {
-	using namespace foundation;
-	
-	void test_memory() {
-		memory_globals::init();
-		Allocator &a = memory_globals::default_allocator();
-
-		void *p = a.allocate(100);
-		ASSERT(a.allocated_size(p) >= 100);
-		ASSERT(a.total_allocated() >= 100);
-		void *q = a.allocate(100);
-		ASSERT(a.allocated_size(q) >= 100);
-		ASSERT(a.total_allocated() >= 200);
-		
-		a.deallocate(p);
-		a.deallocate(q);
-		
-		memory_globals::shutdown();
-	}
-
-	void test_array() {
-		memory_globals::init();
-		Allocator &a = memory_globals::default_allocator();
-
-		{
-			Array<int> v(a);
-
-			ASSERT(array::size(v) == 0);
-			array::push_back(v, 3);
-			ASSERT(array::size(v) == 1);
-			ASSERT(v[0] == 3);
-
-			Array<int> v2(v);
-			ASSERT(v2[0] == 3);
-			v2[0] = 5;
-			ASSERT(v[0] == 3);
-			ASSERT(v2[0] == 5);
-			v2 = v;
-			ASSERT(v2[0] == 3);
-			
-			ASSERT(array::end(v) - array::begin(v) == array::size(v));
-			ASSERT(*array::begin(v) == 3);
-			array::pop_back(v);
-			ASSERT(array::empty(v));
-
-			for (int i=0; i<100; ++i)
-				array::push_back(v, i);
-			ASSERT(array::size(v) == 100);
-		}
-
-		memory_globals::shutdown();
-	}
-
-	void test_scratch() {
-		memory_globals::init(256*1024);
-		Allocator &a = memory_globals::default_scratch_allocator();
-
-		char *p = (char *)a.allocate(10*1024);
-
-		char *pointers[100];
-		for (int i=0; i<100; ++i)
-			pointers[i] = (char *)a.allocate(1024);
-		for (int i=0; i<100; ++i)
-			a.deallocate(pointers[i]);
-
-		a.deallocate(p);
-
-		for (int i=0; i<100; ++i)
-			pointers[i] = (char *)a.allocate(4*1024);
-		for (int i=0; i<100; ++i)
-			a.deallocate(pointers[i]);
-
-		memory_globals::shutdown();
-	}
-
-	void test_temp_allocator() {
-		memory_globals::init();
-		{
-			TempAllocator128 ta;
-			Array<int> a(ta);
-			for (int i=0; i<100; ++i)
-				array::push_back(a, i);
-			ta.allocate(2*1024);
-		}
-		memory_globals::shutdown();
-	}
-
-	void test_hash() {
-		memory_globals::init();
-		{
-			TempAllocator128 ta;
-			Hash<int> h(ta);
-			ASSERT(hash::get(h,0,99) == 99);
-			ASSERT(!hash::has(h, 0));
-			hash::remove(h, 0);
-			hash::set(h, 1000, 123);
-			ASSERT(hash::get(h,1000,0) == 123);
-			ASSERT(hash::get(h,2000,99) == 99);
-
-			for (int i=0; i<100; ++i)
-				hash::set(h, i, i*i);
-			for (int i=0; i<100; ++i)
-				ASSERT(hash::get(h,i,0) == i*i);
-			hash::remove(h, 1000);
-			ASSERT(!hash::has(h, 1000));
-			hash::remove(h, 2000);
-			ASSERT(hash::get(h,1000,0) == 0);
-			for (int i=0; i<100; ++i)
-				ASSERT(hash::get(h,i,0) == i*i);
-		}
-		memory_globals::shutdown();
-	}
-
-	void test_multi_hash()
-	{
-		memory_globals::init();
-		{
-			TempAllocator128 ta;
-			Hash<int> h(ta);
-
-			ASSERT(multi_hash::count(h, 0) == 0);
-			multi_hash::insert(h, 0, 1);
-			multi_hash::insert(h, 0, 2);
-			multi_hash::insert(h, 0, 3);
-			ASSERT(multi_hash::count(h, 0) == 3);
-
-			Array<int> a(ta);
-			multi_hash::get(h, 0, a);
-			ASSERT(array::size(a) == 3);
-			std::sort(array::begin(a), array::end(a));
-			ASSERT(a[0] == 1 && a[1] == 2 && a[2] == 3);
-
-			multi_hash::remove(h, multi_hash::find_first(h, 0));
-			ASSERT(multi_hash::count(h,0) == 2);
-			multi_hash::remove_all(h, 0);
-			ASSERT(multi_hash::count(h, 0) == 0);
-		}
-		memory_globals::shutdown();
-	}
-
-	void test_murmur_hash()
-	{
-		const char *s = "test_string";
-		uint64_t h = murmur_hash_64(s, strlen(s), 0);
-		ASSERT(h == 0xe604acc23b568f83ull);
-	}
-
-	void test_pointer_arithmetic()
-	{
-		const char check = 0xfe;
-		const unsigned test_size = 128;
-
-		TempAllocator512 ta;
-		Array<char> buffer(ta);
-		array::set_capacity(buffer, test_size);
-		memset(array::begin(buffer), 0, array::size(buffer));
-
-		void* data = array::begin(buffer);
-		for (unsigned i = 0; i != test_size; ++i) {
-			buffer[i] = check;
-			char* value = (char*)memory::pointer_add(data, i);
-			ASSERT(*value == buffer[i]);
-		}
-	}
-
-	void test_string_stream()
-	{
-		memory_globals::init();
-		{
-			using namespace string_stream;
-
-			TempAllocator1024 ta;
-			Buffer ss(ta);
-
-			ss << "Name"; 			tab(ss, 20);	ss << "Score\n";
-			repeat(ss, 10, '-');	tab(ss, 20);	repeat(ss, 10, '-'); ss << "\n";
-			ss << "Niklas"; 		tab(ss, 20);	printf(ss, "%.2f", 2.7182818284f); ss << "\n";
-			ss << "Jim"; 			tab(ss, 20);	printf(ss, "%.2f", 3.14159265f); ss << "\n";
-
-			ASSERT(
-				0 == strcmp(c_str(ss),
-					"Name                Score\n"
-					"----------          ----------\n"
-					"Niklas              2.72\n"
-					"Jim                 3.14\n"
-				)
-			);
-		}
-		memory_globals::shutdown();
-	}
-
-	void test_queue()
-	{
-		memory_globals::init();
-		{
-			TempAllocator1024 ta;
-			Queue<int> q(ta);
-
-			queue::reserve(q, 10);
-			ASSERT(queue::space(q) == 10);
-			queue::push_back(q, 11);
-			queue::push_front(q, 22);
-			ASSERT(queue::size(q) == 2);
-			ASSERT(q[0] == 22);
-			ASSERT(q[1] == 11);
-			queue::consume(q, 2);
-			ASSERT(queue::size(q) == 0);
-			int items[] = {1,2,3,4,5,6,7,8,9,10};
-			queue::push(q,items,10);
-			ASSERT(queue::size(q) == 10);
-			for (int i=0; i<10; ++i)
-				ASSERT(q[i] == i+1);
-			queue::consume(q, queue::end_front(q) - queue::begin_front(q));
-			queue::consume(q, queue::end_front(q) - queue::begin_front(q));
-			ASSERT(queue::size(q) == 0);
-		}
-	}
-}
-
-int main(int, char **)
-{
-	test_memory();
-	test_array();
-	test_scratch();
-	test_temp_allocator();
-	test_hash();
-	test_multi_hash();
-	test_murmur_hash();
-	test_pointer_arithmetic();
-	test_string_stream();
-	test_queue();
-	return 0;
-}