ds@2863: /**
ds@2863:  * vim: set ts=4 sw=4 tw=99 noet :
ds@2863:  * =============================================================================
ds@2863:  * SourceMod
ds@2863:  * Copyright (C) 2004-2009 AlliedModders LLC.  All rights reserved.
ds@2863:  * =============================================================================
ds@2863:  *
ds@2863:  * This program is free software; you can redistribute it and/or modify it under
ds@2863:  * the terms of the GNU General Public License, version 3.0, as published by the
ds@2863:  * Free Software Foundation.
ds@2863:  * 
ds@2863:  * This program is distributed in the hope that it will be useful, but WITHOUT
ds@2863:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
ds@2863:  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
ds@2863:  * details.
ds@2863:  *
ds@2863:  * You should have received a copy of the GNU General Public License along with
ds@2863:  * this program.  If not, see <http://www.gnu.org/licenses/>.
ds@2863:  *
ds@2863:  * As a special exception, AlliedModders LLC gives you permission to link the
ds@2863:  * code of this program (as well as its derivative works) to "Half-Life 2," the
ds@2863:  * "Source Engine," the "SourcePawn JIT," and any Game MODs that run on software
ds@2863:  * by the Valve Corporation.  You must obey the GNU General Public License in
ds@2863:  * all respects for all other code used.  Additionally, AlliedModders LLC grants
ds@2863:  * this exception to all derivative works.  AlliedModders LLC defines further
ds@2863:  * exceptions, found in LICENSE.txt (as of this writing, version JULY-31-2007),
ds@2863:  * or <http://www.sourcemod.net/license.php>.
ds@2863:  */
ds@2863: 
ds@2863: #ifndef _INCLUDE_SOURCEMOD_CORE_SYMBOLTABLE_H_
ds@2863: #define _INCLUDE_SOURCEMOD_CORE_SYMBOLTABLE_H_
ds@2863: 
ds@2863: #include <stdlib.h>
ds@2863: #include <string.h>
ds@2863: #include <limits.h>
ds@2863: 
ds@2863: #define KESTRING_TABLE_START_SIZE 65536
ds@2863: 
ds@2863: struct Symbol
ds@2863: {
ds@2863: 	size_t length;
ds@2863: 	uint32_t hash;
ds@2863: 	void *address;
ds@2863: 	Symbol *tbl_next;
ds@2863: 
ds@2863: 	inline char *buffer()
ds@2863: 	{
ds@2863: 		return reinterpret_cast<char *>(this + 1);
ds@2863: 	}
ds@2863: };
ds@2863: 
ds@2863: class SymbolTable
ds@2863: {
ds@2863: public:
ds@2863: 	~SymbolTable()
ds@2863: 	{
ds@2863: 		for (uint32_t i = 0; i < nbuckets; i++)
ds@2863: 		{
ds@2863: 			Symbol *sym = buckets[i];
ds@2863: 			while (sym != NULL)
ds@2863: 			{
ds@2863: 				Symbol *next = sym->tbl_next;
ds@2863: 				free(sym);
ds@2863: 				sym = next;
ds@2863: 			}
ds@2863: 		}
ds@2863: 		free(buckets);
ds@2863: 	}
ds@2863: 
ds@2863: 	bool Initialize()
ds@2863: 	{
ds@2863: 		buckets = (Symbol **)malloc(sizeof(Symbol *) * KESTRING_TABLE_START_SIZE);
ds@2863: 		if (buckets == NULL)
ds@2863: 		{
ds@2863: 			return false;
ds@2863: 		}
ds@2863: 		memset(buckets, 0, sizeof(Symbol *) * KESTRING_TABLE_START_SIZE);
ds@2863: 
ds@2863: 		nbuckets = KESTRING_TABLE_START_SIZE;
ds@2863: 		nused = 0;
ds@2863: 		bucketmask = KESTRING_TABLE_START_SIZE - 1;
ds@2863: 		return true;
ds@2863: 	}
ds@2863: 
ds@2863: 	static inline uint32_t HashString(const char *data, size_t len)
ds@2863: 	{
ds@2863: 		#undef get16bits
ds@2863: 		#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
ds@2863: 				|| defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
ds@2863: 			#define get16bits(d) (*((const uint16_t *) (d)))
ds@2863: 		#endif
ds@2863: 		#if !defined (get16bits)
ds@2863: 			#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
ds@2863: 											 +(uint32_t)(((const uint8_t *)(d))[0]) )
ds@2863: 		#endif
ds@2863: 		uint32_t hash = len, tmp;
ds@2863: 		int rem;
ds@2863: 
ds@2863: 		if (len <= 0 || data == NULL)
ds@2863: 		{
ds@2863: 			return 0;
ds@2863: 		}
ds@2863: 
ds@2863: 		rem = len & 3;
ds@2863: 		len >>= 2;
ds@2863: 
ds@2863: 		/* Main loop */
ds@2863: 		for (;len > 0; len--) {
ds@2863: 				hash	+= get16bits (data);
ds@2863: 				tmp		= (get16bits (data+2) << 11) ^ hash;
ds@2863: 				hash	 = (hash << 16) ^ tmp;
ds@2863: 				data	+= 2 * sizeof (uint16_t);
ds@2863: 				hash	+= hash >> 11;
ds@2863: 		}
ds@2863: 
ds@2863: 		/* Handle end cases */
ds@2863: 		switch (rem) {
ds@2863: 				case 3: hash += get16bits (data);
ds@2863: 								hash ^= hash << 16;
ds@2863: 								hash ^= data[sizeof (uint16_t)] << 18;
ds@2863: 								hash += hash >> 11;
ds@2863: 								break;
ds@2863: 				case 2: hash += get16bits (data);
ds@2863: 								hash ^= hash << 11;
ds@2863: 								hash += hash >> 17;
ds@2863: 								break;
ds@2863: 				case 1: hash += *data;
ds@2863: 								hash ^= hash << 10;
ds@2863: 								hash += hash >> 1;
ds@2863: 		}
ds@2863: 
ds@2863: 		/* Force "avalanching" of final 127 bits */
ds@2863: 		hash ^= hash << 3;
ds@2863: 		hash += hash >> 5;
ds@2863: 		hash ^= hash << 4;
ds@2863: 		hash += hash >> 17;
ds@2863: 		hash ^= hash << 25;
ds@2863: 		hash += hash >> 6;
ds@2863: 
ds@2863: 		return hash;
ds@2863: 
ds@2863: 		#undef get16bits
ds@2863: 	}
ds@2863: 
ds@2863: 	Symbol **FindSymbolBucket(const char *str, size_t len, uint32_t hash)
ds@2863: 	{
ds@2863: 		uint32_t bucket = hash & bucketmask;
ds@2863: 		Symbol **pkvs = &buckets[bucket];
ds@2863: 
ds@2863: 		Symbol *kvs = *pkvs;
ds@2863: 		while (kvs != NULL)
ds@2863: 		{
ds@2863: 			if (len == kvs->length && memcmp(str, kvs->buffer(), len * sizeof(char)) == 0)
ds@2863: 			{
ds@2863: 				return pkvs;
ds@2863: 			}
ds@2863: 			pkvs = &kvs->tbl_next;
ds@2863: 			kvs = *pkvs;
ds@2863: 		}
ds@2863: 
ds@2863: 		return pkvs;
ds@2863: 	}
ds@2863: 
ds@2863: 	void ResizeSymbolTable()
ds@2863: 	{
ds@2863: 		uint32_t xnbuckets = nbuckets * 2;
ds@2863: 		Symbol **xbuckets = (Symbol **)malloc(sizeof(Symbol *) * xnbuckets);
ds@2863: 		if (xbuckets == NULL)
ds@2863: 		{
ds@2863: 			return;
ds@2863: 		}
ds@2863: 		memset(xbuckets, 0, sizeof(Symbol *) * xnbuckets);
ds@2863: 		uint32_t xbucketmask = xnbuckets - 1;
ds@2863: 		for (uint32_t i = 0; i < nbuckets; i++)
ds@2863: 		{
ds@2863: 			Symbol *sym = buckets[i];
ds@2863: 			while (sym != NULL)
ds@2863: 			{
ds@2863: 				Symbol *next = sym->tbl_next;
ds@2863: 				uint32_t bucket = sym->hash & xbucketmask;
ds@2863: 				sym->tbl_next = xbuckets[bucket];
ds@2863: 				xbuckets[bucket] = sym;
ds@2863: 				sym = next;
ds@2863: 			}
ds@2863: 		}
ds@2863: 		free(buckets);
ds@2863: 		buckets = xbuckets;
ds@2863: 		nbuckets = xnbuckets;
ds@2863: 		bucketmask = xbucketmask;
ds@2863: 	}
ds@2863: 
ds@2863: 	Symbol *FindSymbol(const char *str, size_t len)
ds@2863: 	{
ds@2863: 		uint32_t hash = HashString(str, len);
ds@2863: 		Symbol **pkvs = FindSymbolBucket(str, len, hash);
ds@2863: 		return *pkvs;
ds@2863: 	}
ds@2863: 
ds@2863: 	Symbol *InternSymbol(const char* str, size_t len, void *address)
ds@2863: 	{
ds@2863: 		uint32_t hash = HashString(str, len);
ds@2863: 		Symbol **pkvs = FindSymbolBucket(str, len, hash);
ds@2863: 		if (*pkvs != NULL)
ds@2863: 		{
ds@2863: 			return *pkvs;
ds@2863: 		}
ds@2863: 
ds@2863: 		Symbol *kvs = (Symbol *)malloc(sizeof(Symbol) + sizeof(char) * (len + 1));
ds@2863: 		kvs->length = len;
ds@2863: 		kvs->hash = hash;
ds@2863: 		kvs->address = address;
ds@2863: 		kvs->tbl_next = NULL;
ds@2863: 		memcpy(kvs + 1, str, sizeof(char) * (len + 1));
ds@2863: 		*pkvs = kvs;
ds@2863: 		nused++;
ds@2863: 
ds@2863: 		if (nused > nbuckets && nbuckets <= INT_MAX / 2)
ds@2863: 		{
ds@2863: 			ResizeSymbolTable();
ds@2863: 		}
ds@2863: 
ds@2863: 		return kvs;
ds@2863: 	}
ds@2863: private:
ds@2863: 	uint32_t nbuckets;
ds@2863: 	uint32_t nused;
ds@2863: 	uint32_t bucketmask;
ds@2863: 	Symbol **buckets;
ds@2863: };
ds@2863: 
ds@2863: #endif //_INCLUDE_SOURCEMOD_CORE_SYMBOLTABLE_H_