__forceinline bool operator () ( const KeyType & a, const KeyType & b ) {

return a == b;

}

Context * context = nullptr;

uint32_t valueTypeSize = 0;

enum {

minCapacity = 8,

minLookups = 4

};

public:

TableHash () = delete;

TableHash ( const TableHash & ) = delete;

TableHash ( Context * ctx, uint32_t vs ) : context(ctx), valueTypeSize(vs) {}

__forceinline uint32_t indexFromHash(uint32_t hash, uint32_t shift ) const {

return hash >> shift; // i don't know why this is faster, but it is

}

__forceinline uint32_t computeShift(uint32_t capacity) {

return __builtin_clz(capacity-1);

}

__forceinline uint32_t computeMaxLookups(uint32_t capacity) {

uint32_t desired = 32 - __builtin_clz(capacity-1);

return das::max(uint32_t(minLookups), desired * 6);

}

__forceinline int find ( const Table & tab, KeyType key, uint32_t hash ) const {

uint32_t mask = tab.capacity - 1;

uint32_t index = indexFromHash(hash, tab.shift);

uint32_t lastI = (index+tab.maxLookups) & mask;

auto pKeys = (const KeyType *) tab.keys;

auto pHashes = tab.hashes;

while ( index != lastI ) {

auto kh = pHashes[index];

if ( kh==HASH_EMPTY32 ) {

return -1;

} else if ( kh==hash && KeyCompare<KeyType>()(pKeys[index],key) ) {

return (int) index;

}

index = (index + 1) & mask;

}

return -1;

}

__forceinline int insertNew ( Table & tab, uint32_t hash ) const {

// TODO: take key under account and be less agressive?

uint32_t mask = tab.capacity - 1;

uint32_t index = indexFromHash(hash, tab.shift);

uint32_t lastI = (index+tab.maxLookups) & mask;

auto pHashes = tab.hashes;

while ( index != lastI ) {

auto kh = pHashes[index];

if ( kh==HASH_EMPTY32 ) {

return (int) index;

}

index = (index + 1) & mask;

}

return -1;

}

__forceinline int reserve ( Table & tab, KeyType key, uint32_t hash ) {

for ( ;; ) {

uint32_t mask = tab.capacity - 1;

uint32_t index = indexFromHash(hash, tab.shift);

uint32_t lastI = (index+tab.maxLookups) & mask;

uint32_t insertI = -1u;

auto pKeys = (KeyType *) tab.keys;

auto pHashes = tab.hashes;

while ( index != lastI ) {

auto kh = pHashes[index];

if (kh == HASH_EMPTY32 ) {

if ( tab.isLocked() ) context->throw_error("can't insert into locked table");

if ( insertI != -1u ) index = insertI;

pHashes[index] = hash;

pKeys[index] = key;

tab.size++;

return (int)index;

} else if (kh == HASH_KILLED32) {

if ( insertI == -1u ) insertI = index;

} else if (kh == hash && KeyCompare<KeyType>()(pKeys[index], key)) {

return (int)index;

}

index = (index + 1) & mask;

}

if ( !grow(tab) ) {

return -1;

}

}

}

__forceinline int erase ( Table & tab, KeyType key, uint32_t hash ) {

uint32_t mask = tab.capacity - 1;

uint32_t index = indexFromHash(hash, tab.shift);

uint32_t lastI = (index+tab.maxLookups) & mask;

auto pKeys = (const KeyType *) tab.keys;

auto pHashes = tab.hashes;

while ( index != lastI ) {

auto kh = pHashes[index];

if ( kh==HASH_EMPTY32 ) {

return -1;

} else if ( kh==hash && KeyCompare<KeyType>()(pKeys[index],key) ) {

tab.size--;

pHashes[index] = HASH_KILLED32;

memset(tab.data + index*valueTypeSize, 0, valueTypeSize);

return (int) index;

}

index = (index + 1) & mask;

}

return -1;

}

bool grow ( Table & tab ) {

uint32_t newCapacity = das::max(uint32_t(minCapacity), tab.capacity*2);

repeatIt:;

Table newTab;

uint32_t memSize = newCapacity * (valueTypeSize + sizeof(KeyType) + sizeof(uint32_t));

newTab.data = (char *) context->heap->allocate(memSize);

context->heap->mark_comment(newTab.data, "table");

if ( !newTab.data ) {

context->throw_error("can't grow table, out of heap");

return false;

}

newTab.keys = newTab.data + newCapacity * valueTypeSize;

newTab.hashes = (uint32_t *)(newTab.keys + newCapacity * sizeof(KeyType));

newTab.size = tab.size;

newTab.capacity = newCapacity;

newTab.lock = tab.lock;

newTab.flags = tab.flags;

newTab.maxLookups = computeMaxLookups(newCapacity);

newTab.shift = computeShift(newCapacity);

memset(newTab.data, 0, newCapacity*valueTypeSize);

auto pHashes = newTab.hashes;

memset(pHashes, 0, newCapacity * sizeof(uint32_t));

if ( tab.size ) {

auto pKeys = (KeyType *) newTab.keys;

auto pOldValues = tab.data;

auto pValues = newTab.data;

auto pOldKeys = (const KeyType *) tab.keys;

auto pOldHashes = tab.hashes;

for ( uint32_t i=0; i!=tab.capacity; ++i ) {

auto hash = pOldHashes[i];

if ( hash>HASH_KILLED32 ) {

int index = insertNew(newTab, hash);

if ( index==-1 ) {

newCapacity *= 2;

goto repeatIt;

} else {

pHashes[index] = hash;

pKeys[index] = pOldKeys[i];

memcpy ( pValues + index*valueTypeSize, pOldValues + i*valueTypeSize, valueTypeSize );

}

}

}

}

if (tab.capacity) {

uint32_t oldSize = tab.capacity * (valueTypeSize + sizeof(KeyType) + sizeof(uint32_t));

context->heap->free(tab.data, oldSize);

}

swap ( newTab, tab );

return true;

}