FlatHash.h

#include <x86intrin.h>                                                                                                  
#include <stdint.h>

constexpr bool is_powerof2(int v) {                                                                                     
    return v && ((v & (v - 1)) == 0);                                                                                   
}

template<typename Key, size_t NumElements>                                                                              
struct aesHash                                                                                                          
{
    uint32_t operator()(const Key& k) const                                                                             
    {                                                                                                                   
        static_assert(is_powerof2(NumElements), "Not hashing power of 2 array");                                        
        static_assert(sizeof(k) <= 8, "Invalid key size");

        if constexpr(sizeof(k) <= 4)                                                                               
        {                                                                                                               
            __m128i hash_32 = _mm_set1_epi32(k);                                                                        
            hash_32 = _mm_aesenc_si128(hash_32, _mm_setzero_si128()); // _mm_set1_epi32(0xDEADBEEF));                   
            return *reinterpret_cast<uint32_t*>(&hash_32) & (NumElements - 1);                                          
        }                                                                                                               
        else if constexpr(sizeof(k) == 8)                                                                               
        {                                                                                                               
            __m128i hash_64 = _mm_set1_epi64x(k);                                                                       
            // TODO: Test this with only 1 aes call, test with xor argument other than setzero                          
            hash_64 = _mm_aesenc_si128(hash_64, _mm_setzero_si128());                                                   
            hash_64 = _mm_aesenc_si128(hash_64, _mm_setzero_si128());                                                   
            return *reinterpret_cast<uint64_t*>(&hash_64) & (NumElements - 1);                                          
        }
    }
};

class FlatHashable                                                                                                      
{                                                                                                                       
public:                                                                                                                 
    bool m_initialized : 1;                                                                                             
                                                                                                                        
    FlatHashable()                                                                                                      
    {                                                                                                                   
        m_initialized = 0;                                                                                              
    }                                                                                                                   
                                                                                                                        
    bool initialized()                                                                                                  
    {                                                                                                                   
        return m_initialized == 1;                                                                                      
    }                                                                                                                   
                                                                                                                        
    void setInitialized(bool i)                                                                                         
    {                                                                                                                   
        m_initialized = i;                                                                                              
    }                                                                                                                   
} __attribute__((packed));

template<typename Key, typename Value, int NumElements, typename Hash = pow2hash<Key, 8192> >                           
class FlatHash                                                                                                          
{                                                                                                                       
    Value m_backing[NumElements] __attribute__((aligned(64)));                                                          
    FlatHash& operator=(const FlatHash&) = delete;                                                                      
    FlatHash(const FlatHash&) = delete;                                                                                 
                                                                                                                        
public:                                                                                                                 
    FlatHash()                                                                                                          
    {                                                                                                                   
        static_assert(!std::is_polymorphic<Value>::value, "init would zero vtable pointer");                           
    }                                                                                                                   
                                                                                                                        
    constexpr Value* end() { return nullptr; }                                                                          
                                                                                                                        
    size_t m_size = 0;                                                                                                  
    size_t size() { return m_size; }                                                                                    
                                                                                                                        
    template<class ... Args>                                                                                            
    std::pair<bool, Value*> initialize(const Key& k, Args&&... args)                                                    
    {                                                                                                                   
        Key pos = Hash()(k);                                                                                            
                                                                                                                        
        bool collision = false;                                                                                         
        while((unlikely(m_backing[pos].initialized() && !(m_backing[pos] == k) )))                                      
        {                                                                                                               
            collision = true;                                                                                           
            pos = (pos + 1) % NumElements;                                                                              
        }                                                                                                               
                                                                                                                        
        if(m_backing[pos].initialized() && m_backing[pos] == k)                                                         
            return { false, &m_backing[pos] };                                                                          
                                                                                                                        
        new(&m_backing[pos]) Value(args...);                                                                            
        m_backing[pos].setInitialized(true);                                                                            
        m_size++;                                                                                                       
        return { collision, &m_backing[pos] };                                                                          
    }                                                                                                                   
                                                                                                                        
    Value* find(const Key& k)                                                                                           
    {                                                                                                                   
        Key pos = Hash()(k);                                                                                            
        while(m_backing[pos].initialized())                                                                             
        {                                                                                                               
            if(m_backing[pos] == k)                                                                                     
                return &m_backing[pos];                                                                                 
                                                                                                                        
            pos = (pos + 1) % NumElements;                                                                              
        };                                                                                                              
                                                                                                                        
        return end();                                                                                                   
    }
} __attribute((aligned(64)));