Commits

Niklas Frykholm committed f9fd850

multi_hash support

Comments (0)

Files changed (3)

 
 * **Closed structs.** A closed struct is indicated by the fact that its members start with an underscore. You should not manipulate the members of a closed struct directly. Instead, use the functions in the namespace with the same name as the struct. (In this case: object::). These functions are found in the .h file, unlike the struct definition, which is in the \_types.h file.
 
-Note that since namespaces are "open" you can extend the functionality for the object by adding your own functions to its namespace.
+    Note that since namespaces are "open" you can extend the functionality for the object by adding your own functions to its namespace.
 
 * **Abstract classes.** Used for high-level systems that are only accessed through pointers and/or references. These are predeclared in the \_types.h file. The virtual interface is found in the .h file.
 
 
 * **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.)
+* **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.) The hash can be used as a regular hash, or as a multi_hash, through the *multi_hash* interface.
 
 ### Math
 
 		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;
 			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)
 		{
-			FindResult fr = find(h, key);
+			const FindResult fr = find(h, key);
 			if (fr.data_i != END_OF_LIST)
 				return fr.data_i;
 
-			fr.data_i = add_entry(h, key);
+			uint32_t i = add_entry(h, key);
 			if (fr.data_prev == END_OF_LIST)
-				h._hash[fr.hash_i] = fr.data_i;
+				h._hash[fr.hash_i] = i;
 			else
-				h._data[fr.data_prev].next = fr.data_i;
-			return fr.data_i;
+				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)
 				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];
-				hash::set(nh, e.key, e.value);
+				multi_hash::insert(nh, e.key, e.value);
 			}
 
 			Hash<T> empty(*h._hash._allocator);
 
 		template<typename T> void grow(Hash<T> &h)
 		{
-			uint32_t new_size = array::size(h._data) * 2 + 10;
+			const uint32_t new_size = array::size(h._data) * 2 + 10;
 			rehash(h, new_size);
 		}
 	}
 
 		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);
+			const uint32_t i = hash_internal::find_or_fail(h, key);
 			return i == hash_internal::END_OF_LIST ? deffault : h._data[i].value;
 		}
 
 			if (array::size(h._hash) == 0)
 				hash_internal::grow(h);
 
-			uint32_t i = hash_internal::find_or_make(h, key);
+			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);
 		}
 	}
 
+	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)
 	{}
 #include <stdlib.h>
 #include <string.h>
 #include <assert.h>
+#include <algorithm>
 
 #define ASSERT(x) assert(x)
 
 		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";
 	test_scratch();
 	test_temp_allocator();
 	test_hash();
+	test_multi_hash();
 	test_murmur_hash();
 	test_pointer_arithmetic();
 	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.