Skip to content

Instantly share code, notes, and snippets.

@robert-nix

robert-nix/FastHashMap.cs

Last active June 17, 2018 14:52
Show Gist options
  • Save robert-nix/6c65548aa3c41f0653d9486d6b2d81c2 to your computer and use it in GitHub Desktop.
Save robert-nix/6c65548aa3c41f0653d9486d6b2d81c2 to your computer and use it in GitHub Desktop.
Download ZIP
Unity ECS implementation of bytell_hash_map
Raw
_1.md

This is an implementation of bytell_hash_map in C# for use with Unity's new Entity-Component-System and Burst compiler.

You can see more about this hash map in Malte Skarupke's C++Now talk and in the blog post.

This implementation stores blob keys and values; it does not handle values of generic type as Unity.Collections.NativeHashMap does. It is also not thread-safe. Do not use it over NativeHashMap, and especially do not use it over NativeMultiHashMap. I just wanted an excuse to try to better understand this hash map.

Raw
FastHashMap.cs
using System;
using System.Collections;
using System.Collections.Generic;
#if FAKE_UNSAFE_UTILITY
using System.Runtime.InteropServices;
#else
using Unity.Collections;
using Unity.Collections.LowLevel.Unsafe;
#endif
namespace Container
{
#if FAKE_UNSAFE_UTILITY
public enum Allocator
{
Temp = 0,
Persistent = 1
}
public static unsafe class UnsafeUtility
{
[DllImport("kernel32.dll", SetLastError = true)]
private static extern void* HeapCreate(uint flOptions, long dwInitialSize, long dwMaximumSize);
[DllImport("kernel32.dll", SetLastError = true)]
private static extern bool HeapDestroy(void* hHeap);
[DllImport("kernel32.dll", SetLastError = true)]
private static extern void* HeapAlloc(void* hHeap, uint dwFlags, long dwBytes);
[DllImport("kernel32.dll", SetLastError = true)]
private static extern bool HeapFree(void* hHeap, uint dwFlags, void* lpMem);
[DllImport("msvcrt.dll", EntryPoint = "memset", CallingConvention = CallingConvention.Cdecl, SetLastError = false)]
private static extern void* memset(void* dst, int c, long count);
[DllImport("msvcrt.dll", EntryPoint = "memcpy", CallingConvention = CallingConvention.Cdecl, SetLastError = false)]
private static extern void* memcpy(void* dst, void* src, long count);
[DllImport("msvcrt.dll", EntryPoint = "memcmp", CallingConvention = CallingConvention.Cdecl, SetLastError = false)]
private static extern int memcmp(void* lhs, void* rhs, long count);
private static void* hTempHeap;
private static void* hPersistentHeap;
static UnsafeUtility()
{
hTempHeap = HeapCreate(0, 0, 0);
hPersistentHeap = HeapCreate(0, 0, 0);
}
public static void* Malloc(long size, int align, Allocator label)
{
void* hHeap = hTempHeap;
if (label == Allocator.Persistent)
{
hHeap = hPersistentHeap;
}
return HeapAlloc(hHeap, 0, size);
}
public static void Free(void* ptr, Allocator label)
{
void* hHeap = hTempHeap;
if (label == Allocator.Persistent)
{
hHeap = hPersistentHeap;
}
HeapFree(hHeap, 0, ptr);
}
public static void MemClear(void* ptr, long size)
{
memset(ptr, 0, size);
}
public static void MemCpy(void* dst, void* src, long size)
{
memcpy(dst, src, size);
}
public static int MemCmp(void* dst, void* src, long size)
{
return memcmp(dst, src, size);
}
}
#endif
public unsafe struct JenkinsHash
{
uint c, b, a, l;
static uint rot(uint n, int s)
{
return (n << s) | (n >> (32 - s));
}
static void mix(JenkinsHash* h)
{
uint a = h->a, b = h->b, c = h->c;
a -= c;
a ^= rot(c, 4);
c += b;
b -= a;
b ^= rot(a, 6);
a += c;
c -= b;
c ^= rot(b, 8);
b += a;
a -= c;
a ^= rot(c, 16);
c += b;
b -= a;
b ^= rot(a, 19);
a += c;
c -= b;
c ^= rot(b, 4);
b += a;
h->a = a;
h->b = b;
h->c = c;
}
static void final(JenkinsHash* h)
{
uint a = h->a, b = h->b, c = h->c;
c ^= b;
c -= rot(b, 14);
a ^= c;
a -= rot(c, 11);
b ^= a;
b -= rot(a, 25);
c ^= b;
c -= rot(b, 16);
a ^= c;
a -= rot(c, 4);
b ^= a;
b -= rot(a, 14);
c ^= b;
c -= rot(b, 24);
h->a = a;
h->b = b;
h->c = c;
}
static void add12(JenkinsHash* h, uint* k)
{
h->a += k[0];
h->b += k[1];
h->c += k[2];
mix(h);
h->l -= 12;
}
static void addLast(JenkinsHash* h, uint* k)
{
switch (h->l)
{
case 12:
h->c += k[2];
h->b += k[1];
h->a += k[0];
break;
case 11:
h->c += k[2] & 0xffffff;
h->b += k[1];
h->a += k[0];
break;
case 10:
h->c += k[2] & 0xffff;
h->b += k[1];
h->a += k[0];
break;
case 9:
h->c += k[2] & 0xff;
h->b += k[1];
h->a += k[0];
break;
case 8:
h->b += k[1];
h->a += k[0];
break;
case 7:
h->b += k[1] & 0xffffff;
h->a += k[0];
break;
case 6:
h->b += k[1] & 0xffff;
h->a += k[0];
break;
case 5:
h->b += k[1] & 0xff;
h->a += k[0];
break;
case 4:
h->a += k[0];
break;
case 3:
h->a += k[0] & 0xffffff;
break;
case 2:
h->a += k[0] & 0xffff;
break;
case 1:
h->a += k[0] & 0xff;
break;
case 0:
return; /* zero length strings require no mixing */
}
final(h);
}
static ulong value64(JenkinsHash* h)
{
return h->c | ((ulong)h->b << 32);
}
static uint value32(JenkinsHash* h)
{
return h->c;
}
public static uint Hash32(uint* k, int l)
{
JenkinsHash h = new JenkinsHash();
h.a = h.b = h.c = 0xdeadbeefu + (uint)l;
h.l = (uint)l;
while (h.l > 12)
{
add12(&h, k);
k += 3;
}
addLast(&h, k);
return value32(&h);
}
}
// FastHashMap is a map from a byte[] key to a byte[] value.
// Internally it is based off bytell_hash_map (https://github.com/skarupke/flat_hash_map/blob/master/bytell_hash_map.hpp)
// However, it uses a power-of-two size and simply trusts that the hash is good
public unsafe struct FastHashMapData
{
public byte* entries;
public int numSlotsMinusOne;
public int numElements;
public int keySize;
public int valueSize;
public bool hashKeys;
public bool pathNormalizeKeys;
public bool isMultiMap;
const float kMaxLoadFactor = 0.9375f; // 15/16
const int kSlotsPerBlock = 8;
const byte kEmptySlot = 0xff;
const byte kReservedSlot = 0xfe;
const byte kListEntry = 0x80;
const byte kDistance = 0x7f;
const byte kNumJumpDistances = 0x7e;
// Using a managed array is not allowed in burst, so we can either copy
// that array to a statically allocated memory block, or we can just use
// a giant switch statement:
private static long JumpDistance(int i)
{
switch (i)
{
default: return 0;
case 1: return 1;
case 2: return 2;
case 3: return 3;
case 4: return 4;
case 5: return 5;
case 6: return 6;
case 7: return 7;
case 8: return 8;
case 9: return 9;
case 10: return 10;
case 11: return 11;
case 12: return 12;
case 13: return 13;
case 14: return 14;
case 15: return 15;
case 16: return 21;
case 17: return 28;
case 18: return 36;
case 19: return 45;
case 20: return 55;
case 21: return 66;
case 22: return 78;
case 23: return 91;
case 24: return 105;
case 25: return 120;
case 26: return 136;
case 27: return 153;
case 28: return 171;
case 29: return 190;
case 30: return 210;
case 31: return 231;
case 32: return 253;
case 33: return 276;
case 34: return 300;
case 35: return 325;
case 36: return 351;
case 37: return 378;
case 38: return 406;
case 39: return 435;
case 40: return 465;
case 41: return 496;
case 42: return 528;
case 43: return 561;
case 44: return 595;
case 45: return 630;
case 46: return 666;
case 47: return 703;
case 48: return 741;
case 49: return 780;
case 50: return 820;
case 51: return 861;
case 52: return 903;
case 53: return 946;
case 54: return 990;
case 55: return 1035;
case 56: return 1081;
case 57: return 1128;
case 58: return 1176;
case 59: return 1225;
case 60: return 1275;
case 61: return 1326;
case 62: return 1378;
case 63: return 1431;
case 64: return 1485;
case 65: return 1540;
case 66: return 1596;
case 67: return 1653;
case 68: return 1711;
case 69: return 1770;
case 70: return 1830;
case 71: return 1891;
case 72: return 1953;
case 73: return 2016;
case 74: return 2080;
case 75: return 2145;
case 76: return 2211;
case 77: return 2278;
case 78: return 2346;
case 79: return 2415;
case 80: return 2485;
case 81: return 2556;
case 82: return 3741;
case 83: return 8385;
case 84: return 18915;
case 85: return 42486;
case 86: return 95703;
case 87: return 215496;
case 88: return 485605;
case 89: return 1091503;
case 90: return 2456436;
case 91: return 5529475;
case 92: return 12437578;
case 93: return 27986421;
case 94: return 62972253;
case 95: return 141700195;
case 96: return 318819126;
case 97: return 717314626;
case 98: return 1614000520;
case 99: return 3631437253;
case 100: return 8170829695;
case 101: return 18384318876;
case 102: return 41364501751;
case 103: return 93070021080;
case 104: return 209407709220;
case 105: return 471167588430;
case 106: return 1060127437995;
case 107: return 2385287281530;
case 108: return 5366895564381;
case 109: return 12075513791265;
case 110: return 27169907873235;
case 111: return 61132301007778;
case 112: return 137547673121001;
case 113: return 309482258302503;
case 114: return 696335090510256;
case 115: return 1566753939653640;
case 116: return 3525196427195653;
case 117: return 7931691866727775;
case 118: return 17846306747368716;
case 119: return 40154190394120111;
case 120: return 90346928493040500;
case 121: return 203280588949935750;
case 122: return 457381324898247375;
case 123: return 1029107980662394500;
case 124: return 2315492957028380766;
case 125: return 5209859150892887590;
}
}
private static int NumSlots(int items)
{
// next power of two
uint v = (uint)(items - 1);
return (int)(1 + (v | v >> 1 | v >> 2 | v >> 4 | v >> 8 | v >> 16));
}
private static int BlockSize(FastHashMapData* data)
{
return kSlotsPerBlock + (data->keySize + data->valueSize) * kSlotsPerBlock;
}
public static void Rehash(FastHashMapData* data, int numItems, Allocator label)
{
int elementCap = data->numElements * 16 / 15;
if (elementCap > numItems)
{
numItems = elementCap;
}
if (numItems < 16)
{
numItems = 16;
}
int numSlots = NumSlots(numItems);
if (numSlots == data->numSlotsMinusOne + 1)
{
return;
}
int numBlocks = (numSlots + kSlotsPerBlock - 1) / kSlotsPerBlock;
int keySize = data->keySize;
int keyValueSize = keySize + data->valueSize;
int blockSize = kSlotsPerBlock + keyValueSize * kSlotsPerBlock;
long numBytes = blockSize * numBlocks + kSlotsPerBlock;
byte* newEntries = (byte*)UnsafeUtility.Malloc(numBytes, 1, label);
byte* newEndItem = newEntries + numBlocks * blockSize;
for (byte* it = newEntries; it <= newEndItem; it += blockSize)
{
for (int i = 0; i < kSlotsPerBlock; ++i)
{
it[i] = kEmptySlot;
}
}
byte* oldEntries = data->entries;
int oldNumSlots = data->numSlotsMinusOne + 1;
data->entries = newEntries;
data->numSlotsMinusOne = numSlots - 1;
data->numElements = 0;
if (oldEntries == null)
return;
int oldNumBlocks = (oldNumSlots + kSlotsPerBlock - 1) / kSlotsPerBlock;
for (byte* it = oldEntries, end = oldEntries + oldNumBlocks * blockSize; it != end; it += blockSize)
{
for (int i = 0; i < kSlotsPerBlock; ++i)
{
byte metadata = it[i];
if (metadata != kEmptySlot && metadata != kReservedSlot)
{
byte* key = it + 8 + i * keyValueSize;
byte* value = key + keySize;
SetInternal(data, key, value, label);
}
}
}
UnsafeUtility.Free(oldEntries, label);
}
private static byte Normalize(byte c)
{
if (c >= 'a' && c <= 'z')
{
return (byte)(c & 0xdf);
}
if (c >= 'A' && c <= '_')
{
return c;
}
if (c == '/')
{
return (byte)'\\';
}
if (c >= '+' && c <= '.')
{
return c;
}
if (c >= '0' && c <= '9')
{
return c;
}
if (c >= ' ' && c <= ')')
{
return c;
}
return 0;
}
private static bool KeysEqual(FastHashMapData* data, byte* a, byte* b)
{
if (data->pathNormalizeKeys)
{
for (int i = 0; i < data->keySize; i++)
{
if (Normalize(a[i]) != Normalize(b[i]))
return false;
}
return true;
}
return UnsafeUtility.MemCmp(a, b, data->keySize) == 0;
}
public static int Hash(FastHashMapData* data, byte* key)
{
int hash = 0;
if (data->pathNormalizeKeys)
{
byte* keyCopy = stackalloc byte[data->keySize];
for (int i = 0; i < data->keySize; i++)
{
keyCopy[i] = Normalize(key[i]);
}
key = keyCopy;
}
if (data->hashKeys)
{
hash = (int)JenkinsHash.Hash32((uint*)key, data->keySize);
}
else
{
if (data->keySize >= 4)
{
hash = *(int*)key;
}
else
{
int s = data->keySize;
for (int i = 0; i < s; ++i)
{
hash <<= 8;
hash |= key[i];
}
}
}
return hash;
}
public static bool IsFull(FastHashMapData* data)
{
return (data->numElements * 16 / 15) > data->numSlotsMinusOne + 1;
}
public static FastHashMapData* Create(int capacity, int keySize, int valueSize, bool hashKeys, bool isMultiMap, Allocator label)
{
FastHashMapData* data = (FastHashMapData*)UnsafeUtility.Malloc(sizeof(FastHashMapData), 8, label);
UnsafeUtility.MemClear(data, sizeof(FastHashMapData));
data->keySize = keySize;
data->valueSize = valueSize;
data->hashKeys = hashKeys;
data->isMultiMap = isMultiMap;
Rehash(data, capacity, label);
return data;
}
public static void Destroy(FastHashMapData* data, Allocator label)
{
if (data->entries != null)
{
UnsafeUtility.Free(data->entries, label);
}
UnsafeUtility.Free(data, label);
}
// SetInternal writes a key-value pair to the map. Returns true when it has overwritten
// an existing value.
public static bool SetInternal(FastHashMapData* data, byte* key, byte* value, Allocator label)
{
int keySize = data->keySize;
int valueSize = data->valueSize;
int keyValueSize = keySize + valueSize;
int blockSize = kSlotsPerBlock + keyValueSize * kSlotsPerBlock;
int index = Hash(data, key) & data->numSlotsMinusOne;
bool first = true;
while (true)
{
int blockIndex = index >> 3;
int indexInBlock = index & 7;
byte* block = data->entries + blockIndex * blockSize;
byte* keyPtr = block + kSlotsPerBlock + indexInBlock * keyValueSize;
byte metadata = block[indexInBlock];
if (first)
{
// List entry or empty
if ((metadata & 0x80) != 0)
{
// emplace_direct_hit
if (IsFull(data))
{
// Load factor is too high, force growth:
Grow(data, label);
return SetInternal(data, key, value, label);
}
if (metadata == kEmptySlot)
{
// This is an empty slot, write to it:
block[indexInBlock] = 0;
data->numElements++;
UnsafeUtility.MemCpy(keyPtr, key, keySize);
UnsafeUtility.MemCpy(keyPtr + keySize, value, valueSize);
return false;
}
else
{
// This slot is a list entry for another key; find its parent
// and find a free slot to rehome it
int parentIndex = FindParentBlock(data, index);
int freeIndex = FindFreeIndex(data, parentIndex, out int freeJumpIndex);
if (freeJumpIndex == 0)
{
// Couldn't find a free slot, force growth:
Grow(data, label);
return SetInternal(data, key, value, label);
}
int itIndex = index;
while (true)
{
// Move what's currently at itIndex to freeIndex
int freeBlockIndex = freeIndex >> 3;
int freeIndexInBlock = freeIndex & 7;
byte* freeBlock = data->entries + freeBlockIndex * blockSize;
byte* freeKeyPtr = freeBlock + kSlotsPerBlock + freeIndexInBlock * keyValueSize;
int itBlockIndex = itIndex >> 3;
int itIndexInBlock = itIndex & 7;
byte* itBlock = data->entries + itBlockIndex * blockSize;
byte* itKeyPtr = itBlock + kSlotsPerBlock + itIndexInBlock * keyValueSize;
UnsafeUtility.MemCpy(freeKeyPtr, itKeyPtr, keyValueSize);
// Set parent's metadata to freeJumpIndex
int parentBlockIndex = parentIndex >> 3;
int parentIndexInBlock = parentIndex & 7;
byte* parentBlock = data->entries + parentBlockIndex * blockSize;
parentBlock[parentIndexInBlock] = (byte)((parentBlock[parentIndexInBlock] & 0x80) | freeJumpIndex);
// Mark free's metadata as a list entry
freeBlock[freeIndexInBlock] = kListEntry;
// If itIndex had no next, break
byte itMetadata = itBlock[itIndexInBlock];
if ((itMetadata & kDistance) == 0)
{
itBlock[itIndexInBlock] = kEmptySlot;
break;
}
// Follow itIndex so we can make its children members of the new list
int nextIndex = (int)(itIndex + JumpDistance(itMetadata & kDistance)) & data->numSlotsMinusOne;
itBlock[itIndexInBlock] = kEmptySlot;
block[indexInBlock] = kReservedSlot;
itIndex = nextIndex;
parentIndex = freeIndex;
freeIndex = FindFreeIndex(data, parentIndex, out freeJumpIndex);
if (freeJumpIndex == 0)
{
// Couldn't find a free slot, force growth:
Grow(data, label);
return SetInternal(data, key, value, label);
}
}
// Write to index
block[indexInBlock] = 0;
data->numElements++;
UnsafeUtility.MemCpy(keyPtr, key, keySize);
UnsafeUtility.MemCpy(keyPtr + keySize, value, valueSize);
return false;
}
}
first = false;
}
// If we found key, overwrite the value:
if (!data->isMultiMap && KeysEqual(data, keyPtr, key))
{
UnsafeUtility.MemCpy(keyPtr + keySize, value, valueSize);
return true;
}
// If distance is 0, this is the end of a list
// (0x00 would be a direct hit with no children, and 0x80 would be the end of a n-element list)
int distance = metadata & kDistance;
if (distance == 0)
{
// emplace_new_key
if (IsFull(data))
{
// Load factor is too high, force growth:
Grow(data, label);
return SetInternal(data, key, value, label);
}
int freeIndex = FindFreeIndex(data, index, out int freeJumpIndex);
if (freeJumpIndex == 0)
{
// Couldn't find a free slot, force growth:
Grow(data, label);
return SetInternal(data, key, value, label);
}
// Write to freeIndex
int freeBlockIndex = freeIndex >> 3;
int freeIndexInBlock = freeIndex & 7;
byte* freeBlock = data->entries + freeBlockIndex * blockSize;
byte* freeKeyPtr = freeBlock + kSlotsPerBlock + freeIndexInBlock * keyValueSize;
freeBlock[freeIndexInBlock] = kListEntry;
data->numElements++;
UnsafeUtility.MemCpy(freeKeyPtr, key, keySize);
UnsafeUtility.MemCpy(freeKeyPtr + keySize, value, valueSize);
// Set parent's next:
block[indexInBlock] = (byte)((block[indexInBlock] & 0x80) | freeJumpIndex);
return false;
}
index = (int)(index + JumpDistance(distance)) & data->numSlotsMinusOne;
}
}
// FindInternal returns a pointer in to the hashmap where the value for key is
// stored, if key is present in the hashmap.
public static byte* FindInternal(FastHashMapData* data, byte* key)
{
int index = FindIndexInternal(data, key);
if (index < 0)
{
return null;
}
int keySize = data->keySize;
int valueSize = data->valueSize;
int keyValueSize = keySize + valueSize;
int blockSize = kSlotsPerBlock + keyValueSize * kSlotsPerBlock;
int blockIndex = index >> 3;
int indexInBlock = index & 7;
byte* block = data->entries + blockIndex * blockSize;
byte* keyPtr = block + kSlotsPerBlock + indexInBlock * keyValueSize;
return keyPtr + keySize;
}
private static int FindIndexInternal(FastHashMapData* data, byte* key)
{
int keySize = data->keySize;
int valueSize = data->valueSize;
int keyValueSize = keySize + valueSize;
int blockSize = kSlotsPerBlock + keyValueSize * kSlotsPerBlock;
int index = Hash(data, key) & data->numSlotsMinusOne;
bool first = true;
while (true)
{
int blockIndex = index >> 3;
int indexInBlock = index & 7;
byte* block = data->entries + blockIndex * blockSize;
byte* keyPtr = block + kSlotsPerBlock + indexInBlock * keyValueSize;
byte metadata = block[indexInBlock];
if (first)
{
// If there's no direct hit here, then the key is guaranteed
// to not be in the table:
if ((metadata & 0x80) != 0)
{
return -1;
}
first = false;
}
// If we found key, return the value:
if (KeysEqual(data, keyPtr, key))
{
return index;
}
// If distance is 0, this is the end of a list
// (0x00 would be a direct hit with no children, and 0x80 would be the end of a n-element list)
int distance = metadata & kDistance;
if (distance == 0)
{
return -1;
}
index = (int)(index + JumpDistance(distance)) & data->numSlotsMinusOne;
}
}
private static int FindNextIndexInternal(FastHashMapData* data, byte* key, int index)
{
int keySize = data->keySize;
int valueSize = data->valueSize;
int keyValueSize = keySize + valueSize;
int blockSize = kSlotsPerBlock + keyValueSize * kSlotsPerBlock;
bool first = true;
while (true)
{
int blockIndex = index >> 3;
int indexInBlock = index & 7;
byte* block = data->entries + blockIndex * blockSize;
byte* keyPtr = block + kSlotsPerBlock + indexInBlock * keyValueSize;
byte metadata = block[indexInBlock];
// If we found key, return the value:
if (!first && KeysEqual(data, keyPtr, key))
{
return index;
}
first = false;
// If distance is 0, this is the end of a list
// (0x00 would be a direct hit with no children, and 0x80 would be the end of a n-element list)
int distance = metadata & kDistance;
if (distance == 0)
{
return -1;
}
index = (int)(index + JumpDistance(distance)) & data->numSlotsMinusOne;
}
}
public static bool EraseInternal(FastHashMapData* data, byte* key)
{
int index = FindIndexInternal(data, key);
if (index < 0)
{
return false;
}
int keySize = data->keySize;
int valueSize = data->valueSize;
int keyValueSize = keySize + valueSize;
int blockSize = kSlotsPerBlock + keyValueSize * kSlotsPerBlock;
int currentIndex = index;
int currentBlockIndex = currentIndex >> 3;
int currentIndexInBlock = currentIndex & 7;
byte* currentBlock = data->entries + currentBlockIndex * blockSize;
byte* currentKeyPtr = currentBlock + kSlotsPerBlock + currentIndexInBlock * keyValueSize;
byte currentMetadata = currentBlock[currentIndexInBlock];
if ((currentMetadata & 0x7f) != 0)
{
// Follow list to end to get the last item
int previousIndex = currentIndex;
int nextIndex = (int)(currentIndex + JumpDistance(currentMetadata & kDistance)) & data->numSlotsMinusOne;
int nextBlockIndex = nextIndex >> 3;
int nextIndexInBlock = nextIndex & 7;
byte* nextBlock = data->entries + nextBlockIndex * blockSize;
byte nextMetadata = nextBlock[nextIndexInBlock];
while ((nextMetadata & 0x7f) != 0)
{
previousIndex = nextIndex;
nextIndex = (int)(nextIndex + JumpDistance(nextMetadata & kDistance)) & data->numSlotsMinusOne;
nextBlockIndex = nextIndex >> 3;
nextIndexInBlock = nextIndex & 7;
nextBlock = data->entries + nextBlockIndex * blockSize;
nextMetadata = nextBlock[nextIndexInBlock];
}
// Rehome the last item over current
byte* nextKeyPtr = nextBlock + kSlotsPerBlock + nextIndexInBlock * keyValueSize;
UnsafeUtility.MemCpy(currentKeyPtr, nextKeyPtr, keyValueSize);
nextBlock[nextIndexInBlock] = kEmptySlot;
// Clear the jump distance from previous
int previousBlockIndex = previousIndex >> 3;
int previousIndexInBlock = previousIndex & 7;
byte* previousBlock = data->entries + previousBlockIndex * blockSize;
previousBlock[previousIndexInBlock] &= 0x80;
}
else
{
// current is at the end of a list or is a direct hit.
// Clear the previous list entry's jump distance if it
// isn't a direct hit:
if ((currentMetadata & 0x80) != 0)
{
int parentIndex = FindParentBlock(data, currentIndex);
int parentBlockIndex = parentIndex >> 3;
int parentIndexInBlock = parentIndex & 7;
byte* parentBlock = data->entries + parentBlockIndex * blockSize;
parentBlock[parentIndexInBlock] &= 0x80;
}
// clear current:
currentBlock[currentIndexInBlock] = kEmptySlot;
}
data->numElements--;
return true;
}
public static bool EraseMultiInternal(FastHashMapData* data, byte* key)
{
if (!EraseInternal(data, key)) return false;
while (EraseInternal(data, key)) ;
return true;
}
public static void Clear(FastHashMapData* data)
{
int numBlocks = (data->numSlotsMinusOne + kSlotsPerBlock) / kSlotsPerBlock;
int keySize = data->keySize;
int keyValueSize = keySize + data->valueSize;
int blockSize = kSlotsPerBlock + keyValueSize * kSlotsPerBlock;
long numBytes = blockSize * numBlocks + kSlotsPerBlock;
byte* entries = data->entries;
byte* newEndItem = entries + numBlocks * blockSize;
for (byte* it = entries; it <= newEndItem; it += blockSize)
{
for (int i = 0; i < kSlotsPerBlock; ++i)
{
it[i] = kEmptySlot;
}
}
}
private static void Grow(FastHashMapData* data, Allocator label)
{
int numItems = 2 * (data->numSlotsMinusOne + 1);
Rehash(data, numItems, label);
}
public static byte* KeyAt(FastHashMapData* data, int index)
{
int keySize = data->keySize;
int valueSize = data->valueSize;
int keyValueSize = keySize + valueSize;
int blockSize = kSlotsPerBlock + keyValueSize * kSlotsPerBlock;
int blockIndex = index >> 3;
int indexInBlock = index & 7;
byte* block = data->entries + blockIndex * blockSize;
byte* keyPtr = block + kSlotsPerBlock + indexInBlock * keyValueSize;
return keyPtr;
}
public static int IterNextIndex(FastHashMapData* data, int index)
{
if (data->numSlotsMinusOne <= index)
{
return data->numSlotsMinusOne + 1;
}
int nextIndex = index + 1;
for (; nextIndex <= data->numSlotsMinusOne; nextIndex++)
{
int keySize = data->keySize;
int valueSize = data->valueSize;
int keyValueSize = keySize + valueSize;
int blockSize = kSlotsPerBlock + keyValueSize * kSlotsPerBlock;
int nextBlockIndex = nextIndex >> 3;
int nextIndexInBlock = nextIndex & 7;
byte* nextBlock = data->entries + nextBlockIndex * blockSize;
byte* nextKeyPtr = nextBlock + kSlotsPerBlock + nextIndexInBlock * keyValueSize;
byte nextMetadata = nextBlock[nextIndexInBlock];
if (nextMetadata != kEmptySlot && nextMetadata != kReservedSlot)
{
return nextIndex;
}
}
return nextIndex;
}
private static int FindDirectHit(FastHashMapData* data, int child)
{
byte* key = KeyAt(data, child);
if (data->pathNormalizeKeys)
{
byte* keyCopy = stackalloc byte[data->keySize];
for (int i = 0; i < data->keySize; i++)
{
keyCopy[i] = Normalize(key[i]);
}
key = keyCopy;
}
int hash = Hash(data, key);
int index = hash & data->numSlotsMinusOne;
return index;
}
private static int JumpNext(FastHashMapData* data, int index)
{
int keySize = data->keySize;
int valueSize = data->valueSize;
int keyValueSize = keySize + valueSize;
int blockSize = kSlotsPerBlock + keyValueSize * kSlotsPerBlock;
int blockIndex = index >> 3;
int indexInBlock = index & 7;
byte* block = data->entries + blockIndex * blockSize;
return (int)(index + JumpDistance(block[indexInBlock] & kDistance)) & data->numSlotsMinusOne;
}
private static int FindParentBlock(FastHashMapData* data, int child)
{
int parentIndex = FindDirectHit(data, child);
while (true)
{
int next = JumpNext(data, parentIndex);
if (next == child)
{
return parentIndex;
}
parentIndex = next;
}
}
private static int FindFreeIndex(FastHashMapData* data, int parent, out int depth)
{
int keySize = data->keySize;
int valueSize = data->valueSize;
int keyValueSize = keySize + valueSize;
int blockSize = kSlotsPerBlock + keyValueSize * kSlotsPerBlock;
for (int jumpIndex = 1; jumpIndex < kNumJumpDistances; ++jumpIndex)
{
int index = (int)(parent + JumpDistance(jumpIndex)) & data->numSlotsMinusOne;
int blockIndex = index >> 3;
int indexInBlock = index & 7;
byte* block = data->entries + blockIndex * blockSize;
if (block[indexInBlock] == kEmptySlot)
{
depth = jumpIndex;
return index;
}
}
depth = 0;
return 0;
}
}
public unsafe struct FastHashMap : IDisposable, IEnumerable<KeyValuePair<byte[], byte[]>>
{
private FastHashMapData* m_data;
Allocator m_label;
public FastHashMap(int capacity, int keySize, int valueSize, bool hashKeys, Allocator label)
{
m_label = label;
m_data = FastHashMapData.Create(capacity, keySize, valueSize, hashKeys, false, label);
}
public int Length
{
get
{
return m_data->numElements;
}
}
public int Capacity
{
get
{
return m_data->numSlotsMinusOne + 1;
}
}
public void Clear()
{
FastHashMapData.Clear(m_data);
}
public void Add(byte[] key, byte[] value)
{
if (key.Length < m_data->keySize)
{
throw new ArgumentException("key is shorter than keySize bytes");
}
if (value.Length < m_data->valueSize)
{
throw new ArgumentException("value is shorter than valueSize bytes");
}
fixed (byte* pKey = key, pValue = value)
{
byte* existingValue = FastHashMapData.FindInternal(m_data, pKey);
if (existingValue != null)
{
throw new ArgumentException("An element with the same key already exists.");
}
FastHashMapData.SetInternal(m_data, pKey, pValue, m_label);
}
}
// Set sets the key-value pair in the HashMap. Set returns true when it has overwritten an existing item.
public bool Set(byte[] keyValue)
{
if (keyValue.Length < m_data->keySize + m_data->valueSize)
{
throw new ArgumentException("keyValue is shorter than keyValueSize bytes");
}
fixed (byte* pKeyValue = keyValue)
{
return FastHashMapData.SetInternal(m_data, pKeyValue, pKeyValue + m_data->keySize, m_label);
}
}
// Set sets the key-value pair in the HashMap. Set returns true when it has overwritten an existing item.
public bool Set(byte[] key, byte[] value)
{
if (key.Length < m_data->keySize)
{
throw new ArgumentException("key is shorter than keySize bytes");
}
if (value.Length < m_data->valueSize)
{
throw new ArgumentException("value is shorter than valueSize bytes");
}
fixed (byte* pKey = key, pValue = value)
{
return FastHashMapData.SetInternal(m_data, pKey, pValue, m_label);
}
}
// Set sets the key-value pair in the HashMap. Set returns true when it has overwritten an existing item.
public unsafe bool Set(byte* key, byte* value)
{
return FastHashMapData.SetInternal(m_data, key, value, m_label);
}
public bool ContainsKey(byte[] key)
{
if (key.Length < m_data->keySize)
{
throw new ArgumentException("key is shorter than keySize bytes");
}
fixed (byte* pKey = key)
{
return FastHashMapData.FindInternal(m_data, pKey) != null;
}
}
public unsafe bool ContainsKey(byte* key)
{
return FastHashMapData.FindInternal(m_data, key) != null;
}
public bool TryGetValue(byte[] key, byte[] value)
{
if (key.Length < m_data->keySize)
{
throw new ArgumentException("key is shorter than keySize bytes");
}
if (value.Length < m_data->valueSize)
{
throw new ArgumentException("value is shorter than valueSize bytes");
}
fixed (byte* pKey = key, pValue = value)
{
return TryGetValue(pKey, pValue);
}
}
public unsafe bool TryGetValue(byte* key, byte* value)
{
byte* existingValue = FastHashMapData.FindInternal(m_data, key);
if (existingValue == null)
{
return false;
}
UnsafeUtility.MemCpy(value, existingValue, m_data->valueSize);
return true;
}
// Returns a pointer to the value for key, or null if no such value exists.
public unsafe byte* GetValue(byte* key)
{
return FastHashMapData.FindInternal(m_data, key);
}
public bool Remove(byte[] key)
{
if (key.Length < m_data->keySize)
{
throw new ArgumentException("key is shorter than keySize bytes");
}
fixed (byte* pKey = key)
{
return FastHashMapData.EraseInternal(m_data, pKey);
}
}
public unsafe bool Remove(byte* key)
{
return FastHashMapData.EraseInternal(m_data, key);
}
public void Dispose()
{
if (m_data != null)
{
FastHashMapData.Destroy(m_data, m_label);
m_data = null;
}
}
public IEnumerator<KeyValuePair<byte[], byte[]>> GetEnumerator()
{
return new Enumerator(m_data);
}
IEnumerator IEnumerable.GetEnumerator()
{
return new Enumerator(m_data);
}
internal unsafe class Enumerator : IEnumerator<KeyValuePair<byte[], byte[]>>
{
FastHashMapData* data;
int index;
byte[] keyData;
byte[] valueData;
internal Enumerator(FastHashMapData* hashMap)
{
data = hashMap;
index = FastHashMapData.IterNextIndex(hashMap, -1);
keyData = new byte[hashMap->keySize];
valueData = new byte[hashMap->valueSize];
}
public KeyValuePair<byte[], byte[]> Current
{
get
{
byte* key = FastHashMapData.KeyAt(data, index);
byte* value = key + data->keySize;
fixed (byte* pKeyData = keyData, pValueData = valueData)
{
UnsafeUtility.MemCpy(pKeyData, key, data->keySize);
UnsafeUtility.MemCpy(pValueData, value, data->valueSize);
}
return new KeyValuePair<byte[], byte[]>(keyData, valueData);
}
}
object IEnumerator.Current
{
get
{
return (object)Current;
}
}
void IEnumerator.Reset()
{
index = FastHashMapData.IterNextIndex(data, -1);
}
public bool MoveNext()
{
index = FastHashMapData.IterNextIndex(data, index);
if (index > data->numSlotsMinusOne)
return false;
return true;
}
public void Dispose() { }
}
}
}
Raw
FastHashMapTest.cs
using System;
using Unity.Collections;
using Unity.Collections.LowLevel.Unsafe;
using Unity.Jobs;
using NUnit.Framework;
using Container;
public class FastHashMapTests
{
[Test]
public unsafe void FastHashMapDataSanity()
{
var hashMap = FastHashMapData.Create(16, 4, 4, true, Allocator.Temp);
byte* data = (byte*)UnsafeUtility.Malloc(8, 4, Allocator.Temp);
for (int i = 0; i < 100000; i++)
{
data[0] = (byte)i;
data[1] = (byte)(i >> 8);
data[2] = (byte)(i >> 16);
data[3] = (byte)(i >> 24);
int n = (int)(2097169 * i);
data[4] = (byte)n;
data[5] = (byte)(n >> 8);
data[6] = (byte)(n >> 16);
data[7] = (byte)(n >> 24);
FastHashMapData.SetInternal(hashMap, data, data+4, Allocator.Temp);
}
for (int i = 0; i < 100000; i++)
{
int n = (int)(2097169 * i);
data[0] = (byte)i;
data[1] = (byte)(i >> 8);
data[2] = (byte)(i >> 16);
data[3] = (byte)(i >> 24);
byte* value = FastHashMapData.FindInternal(hashMap, data);
Assert.IsTrue(value != null, "Did not find key in map");
Assert.AreEqual(value[0], (byte)n, "Got wrong 1st byte from hash table value");
Assert.AreEqual(value[1], (byte)(n >> 8), "Got wrong 2nd byte from hash table value");
Assert.AreEqual(value[2], (byte)(n >> 16), "Got wrong 3rd byte from hash table value");
Assert.AreEqual(value[3], (byte)(n >> 24), "Got wrong 4th byte from hash table value");
}
for (int i = 0; i < 100000; i+=2)
{
data[0] = (byte)i;
data[1] = (byte)(i >> 8);
data[2] = (byte)(i >> 16);
data[3] = (byte)(i >> 24);
FastHashMapData.EraseInternal(hashMap, data);
}
for (int i = 0; i < 100000; i++)
{
data[0] = (byte)i;
data[1] = (byte)(i >> 8);
data[2] = (byte)(i >> 16);
data[3] = (byte)(i >> 24);
byte* value = FastHashMapData.FindInternal(hashMap, data);
if ((i&1) == 0)
{
Assert.IsTrue(value == null, "Found deleted key in map");
}
else
{
int n = (int)(2097169 * i);
Assert.IsTrue(value != null, "Did not find key in map");
Assert.AreEqual(value[0], (byte)n, "Got wrong 1st byte from hash table value");
Assert.AreEqual(value[1], (byte)(n >> 8), "Got wrong 2nd byte from hash table value");
Assert.AreEqual(value[2], (byte)(n >> 16), "Got wrong 3rd byte from hash table value");
Assert.AreEqual(value[3], (byte)(n >> 24), "Got wrong 4th byte from hash table value");
}
}
UnsafeUtility.Free(data, Allocator.Temp);
FastHashMapData.Destroy(hashMap, Allocator.Temp);
}
[Test]
public void FastHashMapSanity()
{
byte[] key = new byte[4];
byte[] value = new byte[4];
var map = new FastHashMap(16, 4, 4, true, Allocator.Temp);
for (int i = 0; i < 100000; i++)
{
key[0] = (byte)i;
key[1] = (byte)(i >> 8);
key[2] = (byte)(i >> 16);
key[3] = (byte)(i >> 24);
int n = (int)(2097169 * i);
value[0] = (byte)n;
value[1] = (byte)(n >> 8);
value[2] = (byte)(n >> 16);
value[3] = (byte)(n >> 24);
map.Set(key, value);
}
Assert.AreEqual(100000, map.Length, "Map Length is wrong");
for (int i = 0; i < 100000; i++)
{
int n = (int)(2097169 * i);
key[0] = (byte)i;
key[1] = (byte)(i >> 8);
key[2] = (byte)(i >> 16);
key[3] = (byte)(i >> 24);
bool found = map.TryGetValue(key, value);
Assert.IsTrue(found, "Did not find key in map");
Assert.AreEqual(value[0], (byte)n, "Got wrong 1st byte from hash table value");
Assert.AreEqual(value[1], (byte)(n >> 8), "Got wrong 2nd byte from hash table value");
Assert.AreEqual(value[2], (byte)(n >> 16), "Got wrong 3rd byte from hash table value");
Assert.AreEqual(value[3], (byte)(n >> 24), "Got wrong 4th byte from hash table value");
}
for (int i = 0; i < 99999; i++)
{
key[0] = (byte)i;
key[1] = (byte)(i >> 8);
key[2] = (byte)(i >> 16);
key[3] = (byte)(i >> 24);
map.Remove(key);
}
Assert.AreEqual(1, map.Length, "Map Length is wrong");
map.Dispose();
}
[Test]
public unsafe void TestMap_Job()
{
var map = new FastHashMap(16, 4, 4, false, Allocator.Temp);
byte[] key = new byte[4];
key[0] = 0x12;
key[1] = 0x34;
key[2] = 0x56;
key[3] = 0x78;
map.Set(key, key);
int* result = (int*)UnsafeUtility.Malloc(4, 4, Allocator.Temp);
var job = new MapQueryJob { map = map, result = result };
job.Schedule().Complete();
Assert.AreEqual(0x78563412, *result, "Job result is wrong");
UnsafeUtility.Free(result, Allocator.Temp);
}
public unsafe struct MapQueryJob : IJob
{
public FastHashMap map;
[NativeDisableUnsafePtrRestriction] public int* result;
public unsafe void Execute()
{
byte* key = (byte*)UnsafeUtility.Malloc(4, 1, Allocator.Temp);
key[0] = 0x12;
key[1] = 0x34;
key[2] = 0x56;
key[3] = 0x78;
byte* value = map.GetValue(key);
*result = value[0] | (value[1] << 8) | (value[2] << 16) | (value[3] << 24);
UnsafeUtility.Free(key, Allocator.Temp);
}
}
}
Raw
LICENSE.md

bytell_hash_map is copyright 2017 Malte Skarupke

Boost Software License - Version 1.0 - August 17th, 2003

Permission is hereby granted, free of charge, to any person or organization obtaining a copy of the software and accompanying documentation covered by this license (the "Software") to use, reproduce, display, distribute, execute, and transmit the Software, and to prepare derivative works of the Software, and to permit third-parties to whom the Software is furnished to do so, all subject to the following:

The copyright notices in the Software and this entire statement, including the above license grant, this restriction and the following disclaimer, must be included in all copies of the Software, in whole or in part, and all derivative works of the Software, unless such copies or derivative works are solely in the form of machine-executable object code generated by a source language processor.

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, TITLE AND NON-INFRINGEMENT. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment