medfall

commit 46b1ec5887a1f8529d856be9cabb7f2e1a2e283e
parent 4e22a2cef3afa525ba0ec869fe33e70faa66eeb1
Author: Michael Savage <mikejsavage@gmail.com>
Date:   Wed Aug 31 09:50:28 -0700

Add hashtable.h

Diffstat:
hashtable.h
 | 
111
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 111 insertions(+), 0 deletions(-)
diff --git a/hashtable.h b/hashtable.h
@@ -0,0 +1,111 @@
+#ifndef _HASHTABLE_H_
+#define _HASHTABLE_H_
+
+#include "intrinsics.h"
+
+template< size_t N >
+class HashTable {
+	// https://fgiesen.wordpress.com/2015/02/22/triangular-numbers-mod-2n/
+	static_assert( is_power_of_2( N ) );
+
+public:
+	HashTable() {
+		clear();
+	}
+
+	bool add( u64 key, u64 value ) {
+		size_t idx = find( key );
+		if( get_state( idx ) == OCCUPIED ) {
+			return false;
+		}
+		set_state( idx, OCCUPIED );
+		keys[ idx ] = key;
+		values[ idx ] = value;
+		return true;
+	}
+
+	bool remove( u64 key ) {
+		size_t idx = find( key );
+		if( get_state( idx ) == OCCUPIED ) {
+			set_state( idx, DELETED );
+			return true;
+		}
+		return false;
+	}
+
+	bool get( u64 key, u64 * value ) {
+		size_t idx = find( key );
+		if( get_state( idx ) == OCCUPIED ) {
+			if( value != NULL ) {
+				*value = values[ idx ];
+			}
+			return true;
+		}
+		return false;
+	}
+
+	void clear() {
+		for( size_t i = 0; i < sizeof( states ); i++ ) {
+			states[ i ] = 0;
+		}
+	}
+
+private:
+	enum SlotState {
+		EMPTY,    // lo = 0, hi = 0
+		OCCUPIED, // lo = 0, hi = 1
+		DELETED,  // lo = 1, hi = 1
+	};
+
+	size_t find( u64 key ) {
+		size_t idx = key % N;
+		size_t step = 1;
+		for( ;; ) {
+			if( get_state( idx ) == EMPTY ) {
+				return idx;
+			}
+			if( get_state( idx ) == OCCUPIED && keys[ idx ] == key ) {
+				return idx;
+			}
+			idx = ( idx + step ) % N;
+			step++;
+		}
+	}
+
+	SlotState get_state( size_t idx ) {
+		size_t byte = idx / 4;
+		size_t bit0 = ( idx * 2 ) % 8;
+		size_t bit1 = bit0 + 1;
+
+		int lo = states[ byte ] & ( 1 << bit0 );
+		int hi = states[ byte ] & ( 1 << bit1 );
+
+		if( lo == 0 ) return EMPTY;
+		return hi == 0 ? OCCUPIED : DELETED;
+	}
+
+	void set_state( size_t idx, SlotState state ) {
+		size_t byte = idx / 4;
+		size_t bit0 = ( idx * 2 ) % 8;
+		size_t bit1 = bit0 + 1;
+
+		u32 lo = state == EMPTY ? 0 : 1;
+		u32 hi = state == OCCUPIED ? 0 : 1;
+
+		states[ byte ] |= u8( ( lo << bit0 ) | ( hi << bit1 ) );
+	}
+
+	/*
+	 * states is a bitfield with 2 bits per slot. the 2 bits are used to
+	 * hold one of 3 possible states: EMPTY, OCCUPIED and DELETED
+	 *
+	 * we want to round 2 * N up to the next multiple of 8, then divide by
+	 * 8 to get the number of bytes required. the form below is simplified
+	 * so it doesn't overflow
+	 */
+	u8 states[ N / 4 + int( N % 4 != 0 ) ];
+	u64 keys[ N ];
+	u64 values[ N ];
+};
+
+#endif // _HASHTABLE_H_