#include <stdbool.h>

struct StringSetEntry
{
	struct StringSetEntry* pNext;
	unsigned int HashValue;
	const char Key[];
};

struct StringSet
{
	struct StringSetEntry** pHashTable;
	unsigned int nHashTableSize;
	int Count;
};

#define STRING_SET_INIT \
  { NULL, 100, 0 }


bool StringSet_Find(struct StringSet* pMap, const char* Key);
bool StringSet_Remove(struct StringSet* pMap, const char* Key);
void StringSet_RemoveAll(struct StringSet* pMap);
int StringSet_Add(struct StringSet* pMap, const char* Key);
void StringSet_Destroy(struct StringSet* pMap);
#include "StringSet.h"
#include <stdlib.h>
#include <string.h>

static unsigned int String2_HashKey(const char* Key)
{
	// hash key to unsigned int value by pseudorandomizing transform
	// (algorithm copied from STL string hash in xfunctional)
	unsigned int uHashVal = 2166136261U;
	unsigned int uFirst = 0;
	unsigned int uLast = (unsigned int) strlen(Key);
	unsigned int uStride = 1 + uLast / 10;

	for (; uFirst < uLast; uFirst += uStride)
	{
		uHashVal = 16777619U * uHashVal ^ (unsigned int) Key[uFirst];
	}

	return (uHashVal);
}

void StringSet_RemoveAll(struct StringSet* pMap)
{
	if (pMap->pHashTable != NULL)
	{
		for (unsigned int nHash = 0; nHash < pMap->nHashTableSize; nHash++)
		{
			struct StringSetEntry* pKeyValue = pMap->pHashTable[nHash];

			while (pKeyValue != NULL)
			{
				struct StringSetEntry* pKeyValueCurrent = pKeyValue;
				pKeyValue = pKeyValue->pNext;
				free(pKeyValueCurrent);
			}
			pMap->pHashTable[nHash] = NULL;
		}
		
		pMap->Count = 0;
	}
}

void StringSet_Destroy(struct StringSet* pMap)
{
	StringSet_RemoveAll(pMap);
	free(pMap->pHashTable);
	pMap->pHashTable = NULL;
}

static struct StringSetEntry* StringSet_GetAssocAt(struct StringSet* pMap,
	const char* Key,
	unsigned int* nHashBucket,
	unsigned int* HashValue)
{
	if (pMap->pHashTable == NULL)
	{
		*HashValue = 0;
		*nHashBucket = 0;
		return NULL;
	}

	*HashValue = String2_HashKey(Key);
	*nHashBucket = *HashValue % pMap->nHashTableSize;

	struct StringSetEntry* pResult = NULL;

	struct StringSetEntry* pKeyValue = pMap->pHashTable[*nHashBucket];

	for (; pKeyValue != NULL; pKeyValue = pKeyValue->pNext)
	{
		if (pKeyValue->HashValue == *HashValue &&
			strcmp(pKeyValue->Key, Key) == 0)
		{
			pResult = pKeyValue;
			break;
		}
	}

	return pResult;
}

bool StringSet_Find(struct StringSet* pMap, const char* Key)
{
	bool bResult = false;

	unsigned int nHashBucket, HashValue;
	struct StringSetEntry* pKeyValue = StringSet_GetAssocAt(pMap, Key, &nHashBucket, &HashValue);

	return pKeyValue != NULL;
}


bool StringSet_Remove(struct StringSet* pMap, const char* Key)
{
	bool bResult = false;

	if (pMap->pHashTable != NULL)
	{
		unsigned int HashValue = String2_HashKey(Key);

		struct StringSetEntry** ppKeyValuePrev =
			&pMap->pHashTable[HashValue % pMap->nHashTableSize];

		struct StringSetEntry* pKeyValue = *ppKeyValuePrev;

		for (; pKeyValue != NULL; pKeyValue = pKeyValue->pNext)
		{
			if ((pKeyValue->HashValue == HashValue) &&
				(strcmp(pKeyValue->Key, Key) == 0))
			{
				// remove from list
				*ppKeyValuePrev = pKeyValue->pNext;
				free(pKeyValue);
				bResult = true;
				pMap->Count--;
				break;
			}

			ppKeyValuePrev = &pKeyValue->pNext;
		}
	}

	return bResult;
}

int StringSet_Add(struct StringSet* pMap, const char* Key)
{
	int result = 0;

	if (pMap->pHashTable == NULL)
	{
		if (pMap->nHashTableSize < 1)
		{
			pMap->nHashTableSize = 1000;
		}

		struct StringSetEntry** pHashTable =
			(struct StringSetEntry**) malloc(sizeof(struct StringSetEntry*) * pMap->nHashTableSize);

		if (pHashTable != NULL)
		{
			memset(pHashTable, 0, sizeof(struct StringSetEntry*) * pMap->nHashTableSize);
			pMap->pHashTable = pHashTable;
		}
	}

	if (pMap->pHashTable != NULL)
	{
		unsigned int nHashBucket, HashValue;
		struct StringSetEntry* pKeyValue =
			StringSet_GetAssocAt(pMap, Key, &nHashBucket, &HashValue);

		if (pKeyValue == NULL)
		{
			pKeyValue = (struct StringSetEntry*)malloc(sizeof(struct StringSetEntry) + strlen(Key) * sizeof(char) + 1);
			pKeyValue->HashValue = HashValue;
			strcpy((char*) pKeyValue->Key, Key);

			pKeyValue->pNext = pMap->pHashTable[nHashBucket];
			pMap->pHashTable[nHashBucket] = pKeyValue;
			pMap->Count++;
			result = 1; //inserted
		}
		else
		{
			//already exist
		}
	}
	else
	{
		result = -1;//out of memory
	}

	return result;
}