// (c) 2000 by Zachary Booth Simpson
// This code may be freely used, modified, and distributed without any license
// as long as the original author is noted in the source file and all
// changes are made clear disclaimer using a "MODIFIED VERSION" disclaimer.
// There is NO warranty and the original author may not be held liable for any damages.
// http://www.totempole.net

// Hashtable v1.3
// 1.2 Ken Demarest fixed a bug on setting a key that had previously been deleted
// 1.3 ZBS changed memcmp to strncmp to fix a bug that made set read potenitally outside of bounds (causing Bounds Checker to complain)

/*
********************************** MODIFIED VERSION *************************************
Modification History:
01.03.2006 - Tamas Schlagl: Made it confortable with VC2005
********************************** MODIFIED VERSION *************************************
*/

//#pragma warning(disable: 4312 4267 4244)

#include "stdafx.h"
#include "hashtable.h"

/////////////////////////////////////////////////////////////
// HashTable 
/////////////////////////////////////////////////////////////

__w64 int HashTable::hash( char *key ) {
	// Returns a full precision hash value for key
	__w64 int last = 0;
	__w64 int sum = 0;
	while( *key ) {
		sum += (*key ^ last);
		last = *key++;
	}
	return sum;
}

int HashTable::set( char **_hashTable, int _hashTableSize, char *key, char *_recPtr ) {
	hasAnyChanged = 1;
	__w64 int keyLen = strlen( key ) + 1;

	__w64 int index = hash( key ) % _hashTableSize;
	__w64 int total = _hashTableSize;
	__w64 int totalDeleted = 0;
	__w64 int foundKey = 0;
	char *recPtr;
	__w64 int dstIndex = -1;
	while( total-- ) {
		recPtr = _hashTable[index];
		if( recPtr ) {
			// Each hash record is actually a small structure
			// 1st byte is 1 if active, 0 if deleted
			// Starting at the second byte is a null-terminated
			// string which is the key.
			// Following the key is a null-terminated value string.
			if( *recPtr & aaDELETED ) {
				// Found a deleted key. Use this space unless the key is found.
				// NOTE: This will end up using farthest deleted key from the
				// head of the chain first.
				dstIndex = index;
				totalDeleted++;
			}
			else if( !strncmp(key, recPtr + 1, keyLen) ) {
				// Found already existing key. Use this slot.
				foundKey = 1;
				dstIndex = index;
				break;
			}
		}
		else {
			// Found an empty slot, marking the end of this chain.
			// Use this slot unless we found a deleted slot above.
			if( dstIndex == -1 ) {
				dstIndex = index;
			}
			break;
		}
		index = (index+1) % _hashTableSize;
	}
	assert( total + totalDeleted );
		// There should always be some room left since we keep
		// the list at 50% free all the time to avoid collisions
	
	// Here, destIndex contains the index of the found record. The found record value can
	// be either NULL, a pointer to a deleted entry, or a pointer to the found entry.

	if( _recPtr == NULL ) {
		// We are deleting the key
		if( foundKey ) {
			// Only can delete it if it already eixsts
			*_hashTable[dstIndex] |= aaDELETED;
			return 1;
		}
		return 0;
	}
	else {
		// We are either adding a new key or setting the value of an old key.
		// Either way, if the destination record has a value, it must be deleted
		// before the new value is set.
		if( _hashTable[dstIndex] ) {
			free( _hashTable[dstIndex] );
		}
		*_recPtr = aaCHANGED;
		_hashTable[dstIndex] = _recPtr;
	}

	return !foundKey;
}


HashTable::HashTable() {
	hashTable = NULL;
	clear();
}

HashTable::~HashTable() {
	if( hashTable ) {
		free( hashTable );
	}
}

// Retrieve Values
//---------------------------------------------

__w64 int HashTable::lookup( char *key ) {
	__w64 int keyLen = strlen( key ) + 1;
	__w64 int hashRec = hash(key) % hashTableSize;
	__w64 int total = hashTableSize;
	while( total-- ) {
		char *recPtr = hashTable[hashRec];
		if( recPtr ) {
			// Each hash record is actually a small structure
			// 1st byte indicates deleted or changed
			// Starting at the second byte is a null-terminated
			// string which is the key.
			// Following the key is the value buffer.
			if( !(*recPtr & aaDELETED) ) {
				// Non-deleted element, compare
				if( !strncmp(key, recPtr + 1, keyLen) ) {
					return hashRec;
				}
			}
		}
		else {
			// Empty record found before match, terminate search
			return -1;
		}
		hashRec = (hashRec+1) % hashTableSize;
	}
	return -1;
}

char *HashTable::getKey( __w64 int i ) {
	if( 0 <= i && i < hashTableSize ) {
		char *p = hashTable[i];
		if( p && *p ) {
			if( *p & aaDELETED ) return 0;
			return p+1;
		}
	}
	return NULL;
}

char *HashTable::getVal( __w64 int i ) {
	if( 0 <= i && i < hashTableSize ) {
		char *p = hashTable[i];
		if( p && *p ) {
			if( *p & aaDELETED ) return 0;
			return p + strlen(p+1) + 2;
		}
	}
	return NULL;
}

char *HashTable::get( char *key, __w64 int retEmptyString ) {
	__w64 int keyLen = strlen( key ) + 1;
	__w64 int hashRec = hash(key) % hashTableSize;
	__w64 int total = hashTableSize;
	while( total-- ) {
		char *recPtr = hashTable[hashRec];
		if( recPtr ) {
			// Each hash record is actually a small structure
			// 1st byte indicates deleted or changed
			// Starting at the second byte is a null-terminated
			// string which is the key.
			// Following the key is the value data
			if( !(*recPtr & aaDELETED) ) {
				// Non-deleted element, compare
				if( !strncmp(key, recPtr + 1, keyLen) ) {
					// Found it
					return recPtr + 1 + keyLen;
				}
			}
		}
		else {
			// Empty record found before match, terminate search
			if( retEmptyString ) {
				return "";
			}
			return NULL;
		}
		hashRec = (hashRec+1) % hashTableSize;
	}
	if( retEmptyString ) {
		return "";
	}
	return NULL;
}

// Set Values
//---------------------------------------------

void HashTable::set( char *key, char *value, __w64 int len ) {
	hasAnyChanged = 1;
	if( value && numRecords > hashTableSize / 2 ) {
		// If the table is 50% utilized, then go double its size
		// and rebuild the whole hash table
		__w64 int _numRecords = 0;
		__w64 int _hashTableSize = hashTableSize * 2;
		char **_hashTable = (char **)malloc( sizeof(char*) * _hashTableSize );
		memset( _hashTable, 0, sizeof(char*) * _hashTableSize );
		for( __w64 int i=0; i<hashTableSize; i++ ) {
			if( hashTable[i] && !(hashTable[i][0] & aaDELETED) ) {
				// a non-deleted record to add to the new table
				char *key = &hashTable[i][1];
				set( _hashTable, _hashTableSize, key, hashTable[i] );
				_numRecords++;
			}
		}
		free( hashTable );
		hashTable = _hashTable;
		hashTableSize = _hashTableSize;
		numRecords = _numRecords;
	}
	if( value ) {
		__w64 int keyLen = strlen( key ) + 1;
		__w64 int valLen = (len == -1) ? strlen(value)+1 : len;
		char *recPtr = (char *)malloc( 1 + keyLen + valLen );
		*recPtr = 0;
		memcpy( recPtr+1, key, keyLen );
		memcpy( recPtr+1+keyLen, value, valLen );
		numRecords += set( hashTable, hashTableSize, key, recPtr );
	}
	else {
		// Deleting record
		numRecords -= set( hashTable, hashTableSize, key, NULL );
	}
}

void HashTable::clear() {
	if( hashTable ) {
		free( hashTable );
	}
	hashTableSize = 16;
	numRecords = 0;
	hashTable = (char **)malloc( sizeof(char*) * hashTableSize );
	memset( hashTable, 0, sizeof(char*) * hashTableSize );
	hasAnyChanged = 0;
}

void HashTable::copyFrom( HashTable &table ) {
	for( __w64 int i=0; i<table.size(); i++ ) {
		char *key = table.getKey(i);
		char *val = table.getVal(i);
		if( key ) {
			set( key, val );
		}
	}
}

// Change Tracking
//---------------------------------------------

int HashTable::hasChanged() {
	return hasAnyChanged;
}

int HashTable::hasChanged( __w64 int i ) {
	if( 0 <= i && i < hashTableSize ) {
		char *c = hashTable[i];
		if( c && !(*c & aaDELETED) ) {
			return (*c & aaCHANGED);
		}
	}
	return 0;
}

int HashTable::hasChanged( char *key ) {
	__w64 int i = lookup( key );
	if( i >= 0 ) {
		return hasChanged( i );
	}
	return 0;
}

void HashTable::setChanged( __w64 int i ) {
	hasAnyChanged = 1;
	if( 0 <= i && i < hashTableSize ) {
		char *c = hashTable[i];
		if( c ) {
			*c |= aaCHANGED;
		}
	}
}

void HashTable::setChanged( char *key ) {
	hasAnyChanged = 1;
	__w64 int i = lookup( key );
	if( i >= 0 ) {
		setChanged( i );
	}
}

void HashTable::clearChanged( __w64 int i ) {
	if( 0 <= i && i < hashTableSize ) {
		char *c = hashTable[i];
		if( c ) {
			*c &= ~aaCHANGED;
		}
	}
}

void HashTable::clearChanged( char *key ) {
	__w64 int i = lookup( key );
	if( i >= 0 ) {
		clearChanged( i );
	}
}

void HashTable::clearChangedAll() {
	for( __w64 int i=0; i<hashTableSize; i++ ) {
		clearChanged( i );
	}
	hasAnyChanged = 0;
}

