ds.LinearProbingHashTable.h

#pragma once
#include "common.h"
#include "ds.hashtablebase.h"
#include <cstring>
#include <cstdlib>
#include <algorithm>

// enable-disable testing classes in this file
#include "test.this.module.h"

using namespace std;

namespace yasi{
namespace ds{


	using namespace testhash;


	template<
		class Key,
		class Value = Key,
		class HashFunction = IntHashFunction<int>,
		class EntryType = KVPair<Key,Value>, // must have key and value fields
		class Pred = KVPairEqualityPredicate<Key>
	>
	class LinearProbingHashTable : public HashTableBase <
		Key,
		Value,
		EntryType, // storing objects, not pointers
		HashFunction > {
		///////////////// enable testing ///////////////////
		template<typename A, typename B, typename C>
		FRIEND_TEST_CLASS(LinearProbingHashTableTestBase);

		FRIEND_TEST_CLASS(LinearProbingHashTableTest);

	public:
		// an EntryType object is stored in the table

		//typedef KVPair<Key, Value> Pair;
		//typedef EntryType	Pair; // technically, this pair may not have a value
		typedef EntryType	BucketType; // each bucket holds an EntryType object
		typedef EntryType	Pair; // which is actually a key-value pair
		typedef EntryType* BucketEntryPtr; // ptr to an entry object
		typedef Key		KeyType;
		typedef Value	ValueType;
	protected:
		// flag about the usage of the first [0] slot
		bool	_zeroUsed; // true if an entry with key=0 exists
		EntryType	_zeroKeyEntry; // the entry that was mapped to zero index
		char* _pZeroKey; // all zeros up to #bytes of a Key; used to check if a Key is zero
		char* _pZeroValue; // all zeros up to #bytes of a Value; used to set a Value to zero


		inline unsigned int circularNext(const int index) const{
			return this->modSize(index + 1);
		}
		inline unsigned int circularPrev(const int index) const{
			return this->modSize(index - 1);
		}
		inline unsigned int circularDiff(const int low, const int high) const{
			if (low == high) return 0;
			else if (low < high)
				return high - low;
			else
				return _size - low + high;
		}
		inline bool circularBetweenInclusive(const int bucket, const int left, const int right) const{
			if (left == right && bucket != left) return false;
			if (left < right){
				return left <= bucket  && bucket <= right;
			}
			else{
				// left > right
				if (bucket >= left) return true;
				else if (bucket <= right) return true;
				else return false;
			}
		}

		// if a key is already there, it is updated
		void insert(const Key& k, const Value& v){
			Pair* pair = insertKey(k);
			if (pair && pair->value != v){
				pair->value = v;
			}
			else{
				// something is wrong, insertKey() failed
			}
		}

		// the key must be present in the table

		virtual BucketEntryPtr lookupKey(const Key& k) const {
			// test the zero key
			if (isKeyZero(&k)){
				if (_zeroUsed) return const_cast<Pair*>(&_zeroKeyEntry);
				else return NULL;
			}
			else{
				// non-zero key
				Pred keyEquals;
				unsigned int firstBucket = this->index(k);
				int cur = firstBucket;
				do{

					if (isNull(cur)){
						// this slot must be empty
						// because we started from the firstBucket,
						// the key is not present in the table
						return NULL;
					}
					else{
						// this slot is occupied; check key
						if (keyEquals(k, key(cur))){
							// found match
							return entryptr(cur);
						}
						else{
							// move on to the next slot
							cur = this->modSize(cur + 1);
						}
					} // 
				} while (cur != firstBucket);
				// we checked all slots of the table; no match
				return NULL;
			}
		}

		virtual BucketEntryPtr insertKey(const Key& k) {

			// insert/update the entry with hashcode 0
			if ( isKeyZero(&k)){
				// key is zero
				// we will use a special slot for this entry
				if (_zeroUsed == false)
					_zeroUsed = true;
				_zeroKeyEntry.key = k;
				_population++;
				// see if we need to size up
				if (needGrow(_population))
					grow();
				return &_zeroKeyEntry;
			}
			else{
				// key is non-zero
				Pred keyEquals;

				// try all cells in the table, starting from the first (hashed) bucket
				// if all cells are occupied, grow the table and keep trying
				while (true){
					unsigned int firstBucket = this->index(k);
					int cur = firstBucket;
					do{
						//Pair* pEntry = table[cur];

						if (isNull(cur)){
							// if this is the zero slot, we should skip it
							// this slot must be empty,
							// we can insert here

							// see if we need to size up after this insertion
							if (needGrow(_population+1)){
								// current bucket is not appropriate anymore under new size
								// exit the do{} loop, after which we grow and try again
								break; 
							}
							else{
								// create a new entry
								makeEntry(cur,k);
								_population++;
								// return the pointer to the entry
								return entryptr(cur);
							}
						}
						else{
							// this slot is occupied; check key
							if (keyEquals(k, key(cur))){
								// found match
								return entryptr(cur);
							}
							else{
								// move on to the next slot
								cur = this->modSize(cur + 1);
							}
						} // 
					} while (cur != firstBucket);
					// we checked all slots of the table; no match
					// try again after resizing
					grow();
				}
				return NULL;
			}
		}

		virtual void removeKey(const Key& k) {
			// zero key
			if (isKeyZero(&k)){
				if (_zeroUsed) {
					_zeroUsed = false;

					_population--;
					// shrink should not be automatic 

					//if (needShrink(_population))
					//	shrink();
				}
			}
			else{
				// non-zero key
				Pred keyEquals;
				unsigned int curFirstBucket = this->index(k);
				unsigned int cur = curFirstBucket;
				const int searchStart = curFirstBucket; // remember our first posti
				do{
					//Pair* pEntry = table[cur];

					if (isNull(cur)){
						// this slot must be empty
						// because we started from the firstBucket,
						// the key is not present in the table
						return;
					}
					else{
						// this slot is occupied; check key
						if (keyEquals(k, key(cur))){
							// remove
							removeEntry(cur);
							_population--;

							// shrink should not be automatic

							//if (needShrink(_population))
							//	shrink();
							//else
							{
								// shuffle the entries from right to left until an empty slot is found
								// (there must be one because we just deleted one)
								// this will fix all other's linear probing sequence
								const unsigned int startBucket = cur;
								//bool crossedBoundary = false; // search crossed the table end and now at the beginning of the table due to mod operation
								unsigned int neighbor = circularNext(cur);
								while (neighbor != searchStart && // we have not checked all buckets
									!isNull(neighbor))// there is an entry at the neighboring bucket and
								{
									//if (!crossedBoundary && neighbor < cur) {
									//	// our search just wrapped across the table boundary
									//	crossedBoundary = true;
									//}

									unsigned int neighborFirstBucket = this->index(key(neighbor));
									if (neighborFirstBucket == neighbor || // is the neighbor at its own first bucket? then it should not move
										(
										(curFirstBucket <= cur) // search did not wrap around the end
										? neighborFirstBucket > cur // skip if neighbor's first bucket to the right of cur
										: neighborFirstBucket < cur // skip if neighbor's first bucket to the left of cur
										)
										)
									{
										// yes; skip it
										neighbor = circularNext(neighbor);
									}
									else{
										// the (possibly distant) neighbor is not at its first bucket

										// move it to the left
										table[cur] = table[neighbor];
										makeNull(neighbor);
										// prepare for the next hop
										cur = neighbor;
										neighbor = circularNext(neighbor);
										curFirstBucket = neighborFirstBucket;
									}
								}
							}
							// done
							return;
						}
						else{
							// key didn't match
							// move on to the next slot
							cur = this->modSize(cur + 1);
						}
					} // table[cur] != NULL; go to next iteration of while loop 
				} while (cur != searchStart);
				// we checked all slots of the table; no key match
				// cannot remove; done
			}
			return;


		}


		// forecefully provide a table (and associated state values)
		// for test purpose only
		void forceTable(BucketType* newTable, const unsigned int newLogSize, const unsigned int newPopulation, HashFunction& newHashFunction){
			// deallocate current table
			clear();
			deallocTable(table);
			// set new table
			table = newTable;
			_logSize = newLogSize;
			_size = 1 << _logSize;
			_population = newPopulation;
			hash = newHashFunction;
		}
		


		////////////////////////////////////////////////
		//// abstracting the data type of the table
		////////////////////////////////////////////////
		virtual inline BucketType& entry(const int bucket) const {
			return table[bucket];
		}
		virtual inline Key key(const int bucket) const {
			return table[bucket].key;
		}
		virtual inline Key* keyptr(const int bucket) const {
			return &table[bucket].key;
		}
		virtual inline BucketEntryPtr entryptr(const int bucket) const {
			return &table[bucket];
		}
		virtual inline Value value(const int bucket) const {
			return table[bucket].value;
		}
		virtual inline bool isNull(const int bucket) const{
			return isKeyZero(keyptr(bucket));
		}
		virtual inline void makeNull(const int bucket) const{
			setKeyZero(keyptr(bucket));
		}
		virtual inline void removeEntry(const int bucket) const{
			//DELETE_SAFE(table[bucket]);
			makeNull(bucket);
		}
		virtual inline bool isKeyZero(const Key* pKey) const{
			return memcmp(pKey, _pZeroKey, sizeof(Key)) == 0;
		}
		virtual inline bool isValueZero(const Value* pValue) const{
			return memcmp(pValue, _pZeroValue, sizeof(Value)) == 0;
		}
		virtual inline void setKeyZero(Key* pKey) const{
			memcpy(pKey, _pZeroKey, sizeof(Key));
		}
		virtual inline void setValueZero(Value* pValue) const{
			memcpy(pValue, _pZeroValue, sizeof(Value));
		}
		virtual inline void makeEntry(const int bucket, const Key& k){
			table[bucket] = Pair(k);
			// if we stored pointers, we would have done new Pair(k)
		}
		
		virtual inline bool isBucketEmpty(const int bucket) const override {
			return isNull(bucket);
		}
		virtual void copyTable(BucketType* oldTable, const unsigned int oldSize) override {
			// the zeroPair stays intact because it is determined by key, not hash value
			// copy table elements
			//BucketType* oldTable = (BucketType*)prevTable;
			_population = _zeroUsed ? 1 : 0;
			
			for (unsigned int i = 0; i < oldSize; i++){
				EntryType p = oldTable[i];
				if ( !isKeyZero(&p.key)){
					insert(p.key, p.value);
					// no need to delete because it is not pointer anymore
					//DELETE_SAFE(oldTable[i]);
				}
			}
			// count the zero element

		}

		virtual void clear(){
			if (table){
				for (unsigned int i = 0; i < _size; i++){
					if(!isNull(i))
						removeEntry(i);
				}
			}
			_zeroUsed = false;
			_population = 0;
		}

	public:

		LinearProbingHashTable(unsigned int logSize = INIT_LOGSIZE) : _zeroUsed(false), HashTableBase(logSize){
			_pZeroKey = new char[sizeof(Key)];
			_pZeroValue = new char[sizeof(Value)];

			memset(_pZeroKey, 0, sizeof(Key));

			setKeyZero(&_zeroKeyEntry.key);
		}
		virtual ~LinearProbingHashTable(){
			clear();
			DELETE_SAFE(_pZeroKey);
			DELETE_SAFE(_pZeroValue);
		}
		virtual Value* get(const Key& key) const override {
			Pair* kv = lookupKey(key);
			if (kv)
				return &(kv->value);
			else
				return NULL;
		}
		virtual void put(const Key& key, const Value& value) override { 
			return insert(key, value); 
		}
		virtual bool contains(const Key& key) const override { 
			return lookupKey(key) != NULL;
		}
		virtual void remove(const Key& k) override { removeKey(k); }

	};






}
}