sourcemod-central: tools/gdc-psyfork/sm

     1 /**

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

     3  * =============================================================================

     4  * SourceMod

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

     6  * =============================================================================

     7  *

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

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

    10  * Free Software Foundation.

    11  *

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

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

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

    15  * details.

    16  *

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

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

    19  *

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

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

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

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

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

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

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

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

    28  */

    30 #ifndef _INCLUDE_SOURCEMOD_CORE_SYMBOLTABLE_H_

    31 #define _INCLUDE_SOURCEMOD_CORE_SYMBOLTABLE_H_

    33 #include <stdlib.h>

    34 #include <string.h>

    35 #include <limits.h>

    37 #define KESTRING_TABLE_START_SIZE 65536

    39 struct Symbol

    40 {

    41 	size_t length;

    42 	uint32_t hash;

    43 	void *address;

    44 	Symbol *tbl_next;

    46 	inline char *buffer()

    47 	{

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

    49 	}

    50 };

    52 class SymbolTable

    53 {

    54 public:

    55 	~SymbolTable()

    56 	{

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

    58 		{

    59 			Symbol *sym = buckets[i];

    60 			while (sym != NULL)

    61 			{

    62 				Symbol *next = sym->tbl_next;

    63 				free(sym);

    64 				sym = next;

    65 			}

    66 		}

    67 		free(buckets);

    68 	}

    70 	bool Initialize()

    71 	{

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

    73 		if (buckets == NULL)

    74 		{

    75 			return false;

    76 		}

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

    79 		nbuckets = KESTRING_TABLE_START_SIZE;

    80 		nused = 0;

    81 		bucketmask = KESTRING_TABLE_START_SIZE - 1;

    82 		return true;

    83 	}

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

    86 	{

    87 		#undef get16bits

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

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

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

    91 		#endif

    92 		#if !defined (get16bits)

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

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

    95 		#endif

    96 		uint32_t hash = len, tmp;

    97 		int rem;

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

   100 		{

   101 			return 0;

   102 		}

   104 		rem = len & 3;

   105 		len >>= 2;

   107 		/* Main loop */

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

   109 				hash	+= get16bits (data);

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

   111 				hash	 = (hash << 16) ^ tmp;

   112 				data	+= 2 * sizeof (uint16_t);

   113 				hash	+= hash >> 11;

   114 		}

   116 		/* Handle end cases */

   117 		switch (rem) {

   118 				case 3: hash += get16bits (data);

   119 								hash ^= hash << 16;

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

   121 								hash += hash >> 11;

   122 								break;

   123 				case 2: hash += get16bits (data);

   124 								hash ^= hash << 11;

   125 								hash += hash >> 17;

   126 								break;

   127 				case 1: hash += *data;

   128 								hash ^= hash << 10;

   129 								hash += hash >> 1;

   130 		}

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

   133 		hash ^= hash << 3;

   134 		hash += hash >> 5;

   135 		hash ^= hash << 4;

   136 		hash += hash >> 17;

   137 		hash ^= hash << 25;

   138 		hash += hash >> 6;

   140 		return hash;

   142 		#undef get16bits

   143 	}

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

   146 	{

   147 		uint32_t bucket = hash & bucketmask;

   148 		Symbol **pkvs = &buckets[bucket];

   150 		Symbol *kvs = *pkvs;

   151 		while (kvs != NULL)

   152 		{

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

   154 			{

   155 				return pkvs;

   156 			}

   157 			pkvs = &kvs->tbl_next;

   158 			kvs = *pkvs;

   159 		}

   161 		return pkvs;

   162 	}

   164 	void ResizeSymbolTable()

   165 	{

   166 		uint32_t xnbuckets = nbuckets * 2;

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

   168 		if (xbuckets == NULL)

   169 		{

   170 			return;

   171 		}

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

   173 		uint32_t xbucketmask = xnbuckets - 1;

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

   175 		{

   176 			Symbol *sym = buckets[i];

   177 			while (sym != NULL)

   178 			{

   179 				Symbol *next = sym->tbl_next;

   180 				uint32_t bucket = sym->hash & xbucketmask;

   181 				sym->tbl_next = xbuckets[bucket];

   182 				xbuckets[bucket] = sym;

   183 				sym = next;

   184 			}

   185 		}

   186 		free(buckets);

   187 		buckets = xbuckets;

   188 		nbuckets = xnbuckets;

   189 		bucketmask = xbucketmask;

   190 	}

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

   193 	{

   194 		uint32_t hash = HashString(str, len);

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

   196 		return *pkvs;

   197 	}

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

   200 	{

   201 		uint32_t hash = HashString(str, len);

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

   203 		if (*pkvs != NULL)

   204 		{

   205 			return *pkvs;

   206 		}

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

   209 		kvs->length = len;

   210 		kvs->hash = hash;

   211 		kvs->address = address;

   212 		kvs->tbl_next = NULL;

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

   214 		*pkvs = kvs;

   215 		nused++;

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

   218 		{

   219 			ResizeSymbolTable();

   220 		}

   222 		return kvs;

   223 	}

   224 private:

   225 	uint32_t nbuckets;

   226 	uint32_t nused;

   227 	uint32_t bucketmask;

   228 	Symbol **buckets;

   229 };

   231 class AddrTable

   232 {

   233 public:

   234 	~AddrTable()

   235 	{

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

   237 		{

   238 			Symbol *sym = buckets[i];

   239 			while (sym != NULL)

   240 			{

   241 				Symbol *next = sym->tbl_next;

   242 				free(sym);

   243 				sym = next;

   244 			}

   245 		}

   246 		free(buckets);

   247 	}

   249 	bool Initialize()

   250 	{

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

   252 		if (buckets == NULL)

   253 		{

   254 			return false;

   255 		}

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

   258 		nbuckets = KESTRING_TABLE_START_SIZE;

   259 		nused = 0;

   260 		bucketmask = KESTRING_TABLE_START_SIZE - 1;

   261 		return true;

   262 	}

   264 	//Knuth's quick 32-bit integer hash, might not be appropriate but I don't think I care much!

   265 	static inline uint32_t HashAddr(void *addr)

   266 	{

   267 		return (uint32_t)addr * (uint32_t)2654435761u;

   268 	}

   270 	Symbol **FindSymbolBucket(void *addr, uint32_t hash)

   271 	{

   272 		uint32_t bucket = hash & bucketmask;

   273 		Symbol **pkvs = &buckets[bucket];

   275 		Symbol *kvs = *pkvs;

   276 		while (kvs != NULL)

   277 		{

   278 			if (kvs->address == addr)

   279 			{

   280 				return pkvs;

   281 			}

   282 			pkvs = &kvs->tbl_next;

   283 			kvs = *pkvs;

   284 		}

   286 		return pkvs;

   287 	}

   289 	void ResizeSymbolTable()

   290 	{

   291 		uint32_t xnbuckets = nbuckets * 2;

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

   293 		if (xbuckets == NULL)

   294 		{

   295 			return;

   296 		}

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

   298 		uint32_t xbucketmask = xnbuckets - 1;

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

   300 		{

   301 			Symbol *sym = buckets[i];

   302 			while (sym != NULL)

   303 			{

   304 				Symbol *next = sym->tbl_next;

   305 				uint32_t bucket = sym->hash & xbucketmask;

   306 				sym->tbl_next = xbuckets[bucket];

   307 				xbuckets[bucket] = sym;

   308 				sym = next;

   309 			}

   310 		}

   311 		free(buckets);

   312 		buckets = xbuckets;

   313 		nbuckets = xnbuckets;

   314 		bucketmask = xbucketmask;

   315 	}

   317 	Symbol *FindAddr(void *addr)

   318 	{

   319 		uint32_t hash = HashAddr(addr);

   320 		Symbol **pkvs = FindSymbolBucket(addr, hash);

   321 		return *pkvs;

   322 	}

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

   325 	{

   326 		uint32_t hash = HashAddr(address);

   327 		Symbol **pkvs = FindSymbolBucket(address, hash);

   328 		if (*pkvs != NULL)

   329 		{

   330 			return *pkvs;

   331 		}

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

   334 		kvs->length = len;

   335 		kvs->hash = hash;

   336 		kvs->address = address;

   337 		kvs->tbl_next = NULL;

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

   339 		*pkvs = kvs;

   340 		nused++;

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

   343 		{

   344 			ResizeSymbolTable();

   345 		}

   347 		return kvs;

   348 	}

   349 private:

   350 	uint32_t nbuckets;

   351 	uint32_t nused;

   352 	uint32_t bucketmask;

   353 	Symbol **buckets;

   354 };

   356 #endif //_INCLUDE_SOURCEMOD_CORE_SYMBOLTABLE_H_

author	Nicholas Hastings <skamonkey@gmail.com>
	Sat Jun 30 09:08:06 2012 -0400 (2012-06-30)
changeset 3568	f697142dc892
parent 3513	50b5b98b3400
permissions	-rw-r--r--