/**

  * vim: set ts=4 sw=4 tw=99 noet :

  * =============================================================================

  * SourceMod

  * Copyright (C) 2004-2009 AlliedModders LLC.  All rights reserved.

  * =============================================================================

  *

  * This program is free software; you can redistribute it and/or modify it under

  * the terms of the GNU General Public License, version 3.0, as published by the

  * Free Software Foundation.

  * 

  * This program is distributed in the hope that it will be useful, but WITHOUT

  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS

  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more

  * details.

  *

  * You should have received a copy of the GNU General Public License along with

  * this program.  If not, see <http://www.gnu.org/licenses/>.

  *

  * As a special exception, AlliedModders LLC gives you permission to link the

  * code of this program (as well as its derivative works) to "Half-Life 2," the

  * "Source Engine," the "SourcePawn JIT," and any Game MODs that run on software

  * by the Valve Corporation.  You must obey the GNU General Public License in

  * all respects for all other code used.  Additionally, AlliedModders LLC grants

  * this exception to all derivative works.  AlliedModders LLC defines further

  * exceptions, found in LICENSE.txt (as of this writing, version JULY-31-2007),

  * or <http://www.sourcemod.net/license.php>.

  */

 #ifndef _INCLUDE_SOURCEMOD_CORE_SYMBOLTABLE_H_

 #define _INCLUDE_SOURCEMOD_CORE_SYMBOLTABLE_H_

 #include <stdlib.h>

 #include <string.h>

 #include <limits.h>

 #define KESTRING_TABLE_START_SIZE 65536

 struct Symbol

 {

 	size_t length;

 	uint32_t hash;

 	void *address;

 	Symbol *tbl_next;

 	inline char *buffer()

 	{

 		return reinterpret_cast<char *>(this + 1);

 	}

 };

 class SymbolTable

 {

 public:

 	~SymbolTable()

 	{

 		for (uint32_t i = 0; i < nbuckets; i++)

 		{

 			Symbol *sym = buckets[i];

 			while (sym != NULL)

 			{

 				Symbol *next = sym->tbl_next;

 				free(sym);

 				sym = next;

 			}

 		}

 		free(buckets);

 	}

 	bool Initialize()

 	{

 		buckets = (Symbol **)malloc(sizeof(Symbol *) * KESTRING_TABLE_START_SIZE);

 		if (buckets == NULL)

 		{

 			return false;

 		}

 		memset(buckets, 0, sizeof(Symbol *) * KESTRING_TABLE_START_SIZE);

 		nbuckets = KESTRING_TABLE_START_SIZE;

 		nused = 0;

 		bucketmask = KESTRING_TABLE_START_SIZE - 1;

 		return true;

 	}

 	static inline uint32_t HashString(const char *data, size_t len)

 	{

 		#undef get16bits

 		#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \

 				|| defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)

 			#define get16bits(d) (*((const uint16_t *) (d)))

 		#endif

 		#if !defined (get16bits)

 			#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\

 											 +(uint32_t)(((const uint8_t *)(d))[0]) )

 		#endif

 		uint32_t hash = len, tmp;

 		int rem;

 		if (len <= 0 || data == NULL)

 		{

 			return 0;

 		}

 		rem = len & 3;

 		len >>= 2;

 		/* Main loop */

 		for (;len > 0; len--) {

 				hash	+= get16bits (data);

 				tmp		= (get16bits (data+2) << 11) ^ hash;

 				hash	 = (hash << 16) ^ tmp;

 				data	+= 2 * sizeof (uint16_t);

 				hash	+= hash >> 11;

 		}

 		/* Handle end cases */

 		switch (rem) {

 				case 3: hash += get16bits (data);

 								hash ^= hash << 16;

 								hash ^= data[sizeof (uint16_t)] << 18;

 								hash += hash >> 11;

 								break;

 				case 2: hash += get16bits (data);

 								hash ^= hash << 11;

 								hash += hash >> 17;

 								break;

 				case 1: hash += *data;

 								hash ^= hash << 10;

 								hash += hash >> 1;

 		}

 		/* Force "avalanching" of final 127 bits */

 		hash ^= hash << 3;

 		hash += hash >> 5;

 		hash ^= hash << 4;

 		hash += hash >> 17;

 		hash ^= hash << 25;

 		hash += hash >> 6;

 		return hash;

 		#undef get16bits

 	}

 	Symbol **FindSymbolBucket(const char *str, size_t len, uint32_t hash)

 	{

 		uint32_t bucket = hash & bucketmask;

 		Symbol **pkvs = &buckets[bucket];

 		Symbol *kvs = *pkvs;

 		while (kvs != NULL)

 		{

 			if (len == kvs->length && memcmp(str, kvs->buffer(), len * sizeof(char)) == 0)

 			{

 				return pkvs;

 			}

 			pkvs = &kvs->tbl_next;

 			kvs = *pkvs;

 		}

 		return pkvs;

 	}

 	void ResizeSymbolTable()

 	{

 		uint32_t xnbuckets = nbuckets * 2;

 		Symbol **xbuckets = (Symbol **)malloc(sizeof(Symbol *) * xnbuckets);

 		if (xbuckets == NULL)

 		{

 			return;

 		}

 		memset(xbuckets, 0, sizeof(Symbol *) * xnbuckets);

 		uint32_t xbucketmask = xnbuckets - 1;

 		for (uint32_t i = 0; i < nbuckets; i++)

 		{

 			Symbol *sym = buckets[i];

 			while (sym != NULL)

 			{

 				Symbol *next = sym->tbl_next;

 				uint32_t bucket = sym->hash & xbucketmask;

 				sym->tbl_next = xbuckets[bucket];

 				xbuckets[bucket] = sym;

 				sym = next;

 			}

 		}

 		free(buckets);

 		buckets = xbuckets;

 		nbuckets = xnbuckets;

 		bucketmask = xbucketmask;

 	}

 	Symbol *FindSymbol(const char *str, size_t len)

 	{

 		uint32_t hash = HashString(str, len);

 		Symbol **pkvs = FindSymbolBucket(str, len, hash);

 		return *pkvs;

 	}

 	Symbol *InternSymbol(const char* str, size_t len, void *address)

 	{

 		uint32_t hash = HashString(str, len);

 		Symbol **pkvs = FindSymbolBucket(str, len, hash);

 		if (*pkvs != NULL)

 		{

 			return *pkvs;

 		}

 		Symbol *kvs = (Symbol *)malloc(sizeof(Symbol) + sizeof(char) * (len + 1));

 		kvs->length = len;

 		kvs->hash = hash;

 		kvs->address = address;

 		kvs->tbl_next = NULL;

 		memcpy(kvs + 1, str, sizeof(char) * (len + 1));

 		*pkvs = kvs;

 		nused++;

 		if (nused > nbuckets && nbuckets <= INT_MAX / 2)

 		{

 			ResizeSymbolTable();

 		}

 		return kvs;

 	}

 private:

 	uint32_t nbuckets;

 	uint32_t nused;

 	uint32_t bucketmask;

 	Symbol **buckets;

 };

 #endif //_INCLUDE_SOURCEMOD_CORE_SYMBOLTABLE_H_