sm_symtable.h

/**
 * 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;
};

class AddrTable
{
public:
	~AddrTable()
	{
		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;
	}

	//Knuth's quick 32-bit integer hash, might not be appropriate but I don't think I care much!
	static inline uint32_t HashAddr(void *addr)
	{
		return (uint32_t)addr * (uint32_t)2654435761u;
	}

	Symbol **FindSymbolBucket(void *addr, uint32_t hash)
	{
		uint32_t bucket = hash & bucketmask;
		Symbol **pkvs = &buckets[bucket];

		Symbol *kvs = *pkvs;
		while (kvs != NULL)
		{
			if (kvs->address == addr)
			{
				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 *FindAddr(void *addr)
	{
		uint32_t hash = HashAddr(addr);
		Symbol **pkvs = FindSymbolBucket(addr, hash);
		return *pkvs;
	}

	Symbol *InternSymbol(const char* str, size_t len, void *address)
	{
		uint32_t hash = HashAddr(address);
		Symbol **pkvs = FindSymbolBucket(address, 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_