bubel-ecs/source/bubel/ecs/hash_map.d

/************************************************************************************************************************
Copyright: Copyright © 2018-2019, Dawid Masiukiewicz, Michał Masiukiewicz
License: BSD 3-clause, see LICENSE file in project root folder.
*/
module bubel.ecs.hash_map;

import std.traits;

import bubel.ecs.vector;
import bubel.ecs.traits;

enum doNotInline = "version(DigitalMars)pragma(inline,false);version(LDC)pragma(LDC_never_inline);";

private enum HASH_EMPTY = 0;
private enum HASH_DELETED = 0x1;
private enum HASH_FILLED_MARK = ulong(1) << 8 * ulong.sizeof - 1;

export ulong defaultHashFunc(T)(auto ref T t) nothrow @nogc
{
	static if (isIntegral!(T))
	{
		return hashInt(t);
	}
	else
	{
		static if(isArray!T)return hashInt(hash((cast(byte*)t.ptr)[0 .. t.length * ForeachType!(T).sizeof]));
		else return hashInt(hash((cast(byte*)&t)[0 .. T.sizeof])); //hashInt(t.hashOf); // hashOf is not giving proper distribution between H1 and H2 hash parts
	}
}

ulong hash(byte[] array) nothrow @nogc
{
	ulong hash = 0;

	foreach(c;array)
		hash = c + (hash << 6) + (hash << 16) - hash;

	return hash;
}

// Can turn bad hash function to good one
export ulong hashInt(ulong x) nothrow @nogc @safe
{
	x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
	x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
	x = x ^ (x >> 31);
	return x;
}

struct HashMap(KeyPar, ValuePar, alias hashFunc = defaultHashFunc)
{
	alias Key = KeyPar;
	alias Value = ValuePar;
nothrow:

	enum rehashFactor = 0.75;
	enum size_t getIndexEmptyValue = size_t.max;

	static struct KeyVal
	{
		Key key;
		Value value;
	}

	static struct Bucket
	{
		ulong hash;
		KeyVal keyValue;
	}

	Vector!Bucket elements; // Length should be always power of 2
	size_t length; // Used to compute loadFactor
	size_t markerdDeleted;

	void clear()
	{
		elements.clear();
		length = 0;
		markerdDeleted = 0;
	}

	void reset()
	{
		elements.reset();
		length = 0;
		markerdDeleted = 0;
	}

	bool isIn(ref Key el)
	{
		return getIndex(el) != getIndexEmptyValue;
	}

	bool isIn(Key el)
	{
		return getIndex(el) != getIndexEmptyValue;
	}

	Value* getPtr()(auto ref Key k)
	{
		size_t index = getIndex(k);
		if (index == getIndexEmptyValue)
		{
			return null;
		}
		else
		{
			return &elements[index].keyValue.value;
		}
	}

	ref Value get()(auto ref Key k)
	{
		size_t index = getIndex(k);
		assert(index != getIndexEmptyValue);
		return elements[index].keyValue.value;
	}

	deprecated("Use get with second parameter.") auto ref Value getDefault()(
			auto ref Key k, auto ref Value defaultValue)
	{
		return get(k, defaultValue);
	}

	auto ref Value get()(auto ref Key k, auto ref Value defaultValue)
	{
		size_t index = getIndex(k);
		if (index == getIndexEmptyValue)
		{
			return defaultValue;
		}
		else
		{
			return elements[index].keyValue.value;
		}
	}

	ref Value getInsertDefault()(auto ref Key k, auto ref Value defaultValue)
	{
		size_t index = getIndex(k);
		if (index == getIndexEmptyValue)
		{
			add(k, defaultValue);
		}
		index = getIndex(k);
		assert(index != getIndexEmptyValue);
		return elements[index].keyValue.value;

	}

	bool tryRemove(Key el)
	{
		size_t index = getIndex(el);
		if (index == getIndexEmptyValue)
		{
			return false;
		}
		length--;
		elements[index].hash = HASH_DELETED;
		markerdDeleted++;
		return true;
	}

	void remove(Key el)
	{
		bool ok = tryRemove(el);
		assert(ok);
	}

	ref Value opIndex()(auto ref Key key)
	{
		return get(key);
	}

	void opIndexAssign()(auto ref Value value, auto ref Key key)
	{
		add(key, value);
	}

	void add()(auto ref Key key, auto ref Value value)
	{
		size_t index = getIndex(key);
		if (index != getIndexEmptyValue)
		{
			elements[index].keyValue.value = value;
			return;
		}

		if (getLoadFactor(length + 1) > rehashFactor
				|| getLoadFactor(length + markerdDeleted) > rehashFactor)
		{
			rehash();
		}
		length++;

		immutable ulong hash = hashFunc(key) | HASH_FILLED_MARK;
		immutable size_t rotateMask = elements.length - 1;
		index = hash & rotateMask; // Starting point

		while (true)
		{
			Bucket* gr = &elements[index];
			if ((gr.hash & HASH_FILLED_MARK) == 0)
			{
				if (gr.hash == HASH_DELETED)
				{
					markerdDeleted--;
				}
				gr.hash = hash;
				gr.keyValue.key = key;
				gr.keyValue.value = value;
				return;
			}

			index++;
			index = index & rotateMask;
		}
	}

	// For debug
	//int numA;
	//int numB;

	size_t getIndex(Key el)
	{
		return getIndex(el);
	}

	size_t getIndex(ref Key el)
	{
		mixin(doNotInline);

		immutable size_t groupsLength = elements.length;
		if (groupsLength == 0)
		{
			return getIndexEmptyValue;
		}

		immutable ulong hash = hashFunc(el) | HASH_FILLED_MARK;
		immutable size_t rotateMask = groupsLength - 1;
		size_t index = hash & rotateMask; // Starting point

		//numA++;
		while (true)
		{
			//numB++;
			Bucket* gr = &elements[index];
			if (gr.hash == hash && gr.keyValue.key == el)
			{
				return index;
			}
			if (gr.hash == HASH_EMPTY)
			{
				return getIndexEmptyValue;
			}

			index++;
			index = index & rotateMask;
		}

	}

	float getLoadFactor(size_t forElementsNum)
	{
		if (elements.length == 0)
		{
			return 1;
		}
		return cast(float) forElementsNum / (elements.length);
	}

	void rehash()()
	{
		mixin(doNotInline);
		// Get all elements
		Vector!KeyVal allElements;
		allElements.reserve(elements.length);

		foreach (ref Bucket el; elements)
		{
			if ((el.hash & HASH_FILLED_MARK) == 0)
			{
				el.hash = HASH_EMPTY;
				continue;
			}
			el.hash = HASH_EMPTY;
			allElements ~= el.keyValue;

		}

		if (getLoadFactor(length + 1) > rehashFactor)
		{ // Reallocate
			elements.length = (elements.length ? elements.length : 4) << 1; // Power of two, initially 8 elements
		}

		// Insert elements
		foreach (i, ref el; allElements)
		{
			add(el.key, el.value);
		}
		length = allElements.length;
		markerdDeleted = 0;
	}

	// foreach support
	int opApply(DG)(scope DG dg)
	{
		int result;
		foreach (ref Bucket gr; elements)
		{
			if ((gr.hash & HASH_FILLED_MARK) == 0)
			{
				continue;
			}
			static if (isForeachDelegateWithTypes!(DG, Key))
			{
				result = dg(gr.keyValue.key);
			}
			else static if (isForeachDelegateWithTypes!(DG, Value))
			{
				result = dg(gr.keyValue.value);
			}
			else static if (isForeachDelegateWithTypes!(DG, Key, Value))
			{
				result = dg(gr.keyValue.key, gr.keyValue.value);
			}
			else
			{
				static assert(0);
			}
			if (result)
				break;

		}

		return result;
	}

	int byKey(scope int delegate(ref Key k) dg)
	{
		int result;
		foreach (ref Key k; this)
		{
			result = (cast(int delegate(ref Key k) nothrow)dg)(k);
			if (result)
				break;
		}
		return result;
	}

	int byValue(scope int delegate(ref Value v) dg)
	{
		int result;
		foreach (ref Value v; this)
		{
			result = (cast(int delegate(ref Value v) nothrow)dg)(v);
			if (result)
				break;
		}
		return result;
	}

	int byKeyValue(scope int delegate(ref Key k, ref Value v) dg)
	{
		int result;
		foreach (ref Key k, ref Value v; this)
		{
			result = (cast(int delegate(ref Key k, ref Value v) nothrow)dg)(k, v);
			if (result)
				break;
		}
		return result;
	}
}