hashtable.h (2227B)
1 #pragma once 2 3 #include "intrinsics.h" 4 5 template< typename T, size_t N > 6 class HashTable { 7 // https://fgiesen.wordpress.com/2015/02/22/triangular-numbers-mod-2n/ 8 STATIC_ASSERT( is_power_of_2( N ) ); 9 10 public: 11 HashTable() { 12 clear(); 13 } 14 15 bool add( u64 key, const T & value ) { 16 size_t idx = find( key ); 17 if( get_state( idx ) == OCCUPIED ) { 18 return false; 19 } 20 set_state( idx, OCCUPIED ); 21 keys[ idx ] = key; 22 values[ idx ] = value; 23 return true; 24 } 25 26 bool remove( u64 key ) { 27 size_t idx = find( key ); 28 if( get_state( idx ) == OCCUPIED ) { 29 set_state( idx, DELETED ); 30 return true; 31 } 32 return false; 33 } 34 35 bool get( u64 key, T * value ) { 36 size_t idx = find( key ); 37 if( get_state( idx ) == OCCUPIED ) { 38 if( value != NULL ) { 39 *value = values[ idx ]; 40 } 41 return true; 42 } 43 return false; 44 } 45 46 void clear() { 47 for( size_t i = 0; i < sizeof( states ); i++ ) { 48 states[ i ] = 0; 49 } 50 } 51 52 private: 53 enum SlotState { 54 EMPTY, // lo = 0, hi = 0 55 OCCUPIED, // lo = 0, hi = 1 56 DELETED, // lo = 1, hi = 1 57 }; 58 59 size_t find( u64 key ) { 60 size_t idx = key % N; 61 size_t step = 1; 62 for( ;; ) { 63 if( get_state( idx ) == EMPTY ) { 64 return idx; 65 } 66 if( get_state( idx ) == OCCUPIED && keys[ idx ] == key ) { 67 return idx; 68 } 69 idx = ( idx + step ) % N; 70 step++; 71 } 72 } 73 74 SlotState get_state( size_t idx ) { 75 size_t byte = idx / 4; 76 size_t bit0 = ( idx * 2 ) % 8; 77 size_t bit1 = bit0 + 1; 78 79 int lo = states[ byte ] & ( 1 << bit0 ); 80 int hi = states[ byte ] & ( 1 << bit1 ); 81 82 if( lo == 0 ) return EMPTY; 83 return hi == 0 ? OCCUPIED : DELETED; 84 } 85 86 void set_state( size_t idx, SlotState state ) { 87 size_t byte = idx / 4; 88 size_t bit0 = ( idx * 2 ) % 8; 89 size_t bit1 = bit0 + 1; 90 91 u32 lo = state == EMPTY ? 0 : 1; 92 u32 hi = state == OCCUPIED ? 0 : 1; 93 94 states[ byte ] |= u8( ( lo << bit0 ) | ( hi << bit1 ) ); 95 } 96 97 /* 98 * states is a bitfield with 2 bits per slot. the 2 bits are used to 99 * hold one of 3 possible states: EMPTY, OCCUPIED and DELETED 100 * 101 * we want to round 2 * N up to the next multiple of 8, which is the 102 * same as rounding N up to the next multiple of 4 but avoids overflow 103 */ 104 u8 states[ slots_required( N, 4 ) ]; 105 u64 keys[ N ]; 106 T values[ N ]; 107 };