Anonymous avatar Anonymous committed 2d6be05

Hash<T> implementation.

Comments (0)

Files changed (5)

 
 * **memory_globals::default_allocator()** Returns a default allocator based on malloc().
 
+* **memory_globals::default_scratch_allocator()** Returns a "scratch" allocator that can be used for temporary memory allocations. The scratch allocator allocates its memory from a fixed sized ring buffer, meaning it doesn't touch any OS resources. When the ring buffer loops around, the old memory must have been freed for the scratch buffer to be able to allocate new memory, so only use it for temporary allocations.
+
+* **TempAllocator.** An allocator suitable for temporary allocators. The TempAllocator comes in a number of variations: TempAllocator64, TempAllocator128, etc. The number indicates how much local stack space the allocator reserves. Memory is allocated first from the local stack space and only if that is exhausted from the scratch buffer. Memory allocated with the TempAllocator does not have to be freed. It is freed automatically when the allocator is destroyed.
+
 ### Collection
 
 * **Array<T>** Implements an array of objects. A lightweight version of std::vector that assumes that *T* is a POD-object (i.e. constructors and destructors do not have to be called and the object can be moved with memmove).
 
+* **Hash<T>** Implements a lightweight hash that assumes that *T* is a POD-object. The hash keys are always uint64_t numbers. If you want to use some other type of key, just hash it to a uint64_t first. (The hash function should not have any collisions in your domain.)
+
 ### Math
 
 * Basic data definitions for vectors, quaternions and matrices.

collection_types.h

 #include "memory_types.h"
 
 /// Array of POD objects.
+///
 /// * Does not call constructors & destructors on elements.
 /// * Assumes they can be moved with memmove().
 template<typename T> struct Array
 	uint32_t _size;
 	uint32_t _capacity;
 	T *_data;
+};
+
+/// Hash from an uint64_t to POD objects. If you want to use a generic key
+/// object, use a hash function to map that to an uint64_t.
+///
+/// * Does not call constructors & destructors on elements.
+/// * Assumes they can be moved with memmove().
+template<typename T> struct Hash
+{
+public:
+	Hash(Allocator &a);
+	
+	// Marks an unused _data entry.
+	static const uint64_t UNUSED_KEY = 0xffffffffeeeeeeeeull;
+	
+	// Marks end of linked next list.
+	static const uint32_t END_OF_LIST = 0xffffffffu;
+
+	struct Entry {
+		uint64_t key;
+		uint32_t next;
+		T value;
+	};
+
+	uint32_t _freelist;
+	Array<uint32_t> _hash;
+	Array<Entry> _data;
 };
+#pragma once
+
+#include "array.h"
+#include "collection_types.h"
+
+/// The hash function stores its data in a "list-in-an-array" where
+/// indices are used instead of pointers. A free list is used to keep
+/// track of free data entries.
+
+namespace hash
+{
+	template<typename T> void set(Hash<T> &h, uint64_t key, const T &value);
+}
+
+namespace hash_internal
+{
+	const uint32_t END_OF_LIST = 0xffffffffu;
+	static const uint64_t UNUSED_KEY = 0xffffffffeeeeeeeeull;
+
+	template<typename T> uint32_t find_or_fail(const Hash<T> &h, uint64_t key)
+	{
+		if (array::size(h._hash) == 0)
+			return END_OF_LIST;
+
+		uint32_t ei = h._hash[key % array::size(h._hash)];
+		while (ei != END_OF_LIST) {
+			if (h._data[ei].key == key)
+				return ei;
+			ei = h._data[ei].next;
+		}
+		return ei;
+	}
+
+	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;
+		if (h._freelist == END_OF_LIST) {
+			uint32_t ei = array::size(h._data);
+			array::push_back(h._data, e);
+			return ei;
+		}
+		uint32_t ei = h._freelist;
+		h._freelist = h._data[h._freelist].next;
+		h._data[ei] = e;
+		return ei;
+	}
+
+	template<typename T> uint32_t find_or_make(Hash<T> &h, uint64_t key)
+	{
+		uint32_t i = key % array::size(h._hash);
+		if (h._hash[i] == END_OF_LIST) {
+			uint32_t ei = add_entry(h, key);
+			h._hash[i] = ei;
+			return ei;
+		}
+		uint32_t ei = h._hash[i];
+		while (true) {
+			if (h._data[ei].key == key)
+				return ei;
+			uint32_t next = h._data[ei].next;
+			if (next == END_OF_LIST) {
+				uint32_t next_ei = add_entry(h, key);
+				h._data[ei].next = next_ei;
+				return next_ei;
+			}
+			ei = next;
+		}
+	}
+
+	template<typename T> void erase(Hash<T> &h, uint32_t i, uint32_t prev, uint32_t ei)
+	{
+		if (prev == END_OF_LIST)
+			h._hash[i] = h._data[ei].next;
+		else
+			h._data[prev].next = h._data[ei].next;
+		h._data[ei].key = UNUSED_KEY;
+		h._data[ei].next = h._freelist;
+		h._freelist = ei;
+	}
+
+	template<typename T> void find_and_erase(Hash<T> &h, uint64_t key)
+	{
+		if (array::size(h._hash) == 0)
+			return;
+
+		uint32_t prev = END_OF_LIST;
+		uint32_t i = key % array::size(h._hash);
+		uint32_t ei = h._hash[i];
+		while (ei != END_OF_LIST) {
+			if (h._data[ei].key == key) {
+				erase(h, i, prev, ei);
+				return;
+			}
+			ei = h._data[ei].next;
+		}
+	}
+
+	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];
+			if (h._data[i].key == UNUSED_KEY)
+				continue;
+			hash::set(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)
+	{
+		uint32_t new_size = array::size(h._data) * 2 + 10;
+		rehash(h, new_size);
+	}
+}
+
+namespace hash
+{
+	const uint32_t END_OF_LIST = 0xffffffffu;
+
+	template<typename T> bool has(const Hash<T> &h, uint64_t key)
+	{
+		return hash_internal::find_or_fail(h, key) != END_OF_LIST;
+	}
+
+	template<typename T> const T &get(const Hash<T> &h, uint64_t key, const T &deffault)
+	{
+		uint32_t i = hash_internal::find_or_fail(h, key);
+		return i == 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);
+
+		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> Hash<T>::Hash(Allocator &a) :
+	_freelist(END_OF_LIST), _hash(a), _data(a)
+{}
 FLAGS = "-Wall -Wextra -g"
 
 OBJECTS = %w(unit_test.o memory.o)
-HEADERS = %w(array.h collection_types.h memory.h memory_types.h types.h temp_allocator.h)
+HEADERS = %w(array.h collection_types.h memory.h memory_types.h types.h temp_allocator.h hash.h)
 
 # tasks
 
+#include "hash.h"
 #include "temp_allocator.h"
 #include "array.h"
 #include "memory.h"
 	}
 
 	void test_temp_allocator() {
-		memory_globals::init(256*1024);
+		memory_globals::init();
 		{
 			TempAllocator128 ta;
 			Array<int> a(ta);
 		}
 		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();
+	}
 }
 
 int main(int, char **)
 	test_array();
 	test_scratch();
 	test_temp_allocator();
+	test_hash();
 	return 0;
 }
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.