1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/core/logic/sm_symtable.h Fri May 14 16:14:59 2010 -0700
1.3 @@ -0,0 +1,231 @@
1.4 +/**
1.5 + * vim: set ts=4 sw=4 tw=99 noet :
1.6 + * =============================================================================
1.7 + * SourceMod
1.8 + * Copyright (C) 2004-2009 AlliedModders LLC. All rights reserved.
1.9 + * =============================================================================
1.10 + *
1.11 + * This program is free software; you can redistribute it and/or modify it under
1.12 + * the terms of the GNU General Public License, version 3.0, as published by the
1.13 + * Free Software Foundation.
1.14 + *
1.15 + * This program is distributed in the hope that it will be useful, but WITHOUT
1.16 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
1.17 + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
1.18 + * details.
1.19 + *
1.20 + * You should have received a copy of the GNU General Public License along with
1.21 + * this program. If not, see <http://www.gnu.org/licenses/>.
1.22 + *
1.23 + * As a special exception, AlliedModders LLC gives you permission to link the
1.24 + * code of this program (as well as its derivative works) to "Half-Life 2," the
1.25 + * "Source Engine," the "SourcePawn JIT," and any Game MODs that run on software
1.26 + * by the Valve Corporation. You must obey the GNU General Public License in
1.27 + * all respects for all other code used. Additionally, AlliedModders LLC grants
1.28 + * this exception to all derivative works. AlliedModders LLC defines further
1.29 + * exceptions, found in LICENSE.txt (as of this writing, version JULY-31-2007),
1.30 + * or <http://www.sourcemod.net/license.php>.
1.31 + */
1.32 +
1.33 +#ifndef _INCLUDE_SOURCEMOD_CORE_SYMBOLTABLE_H_
1.34 +#define _INCLUDE_SOURCEMOD_CORE_SYMBOLTABLE_H_
1.35 +
1.36 +#include <stdlib.h>
1.37 +#include <string.h>
1.38 +#include <limits.h>
1.39 +
1.40 +#define KESTRING_TABLE_START_SIZE 65536
1.41 +
1.42 +struct Symbol
1.43 +{
1.44 + size_t length;
1.45 + uint32_t hash;
1.46 + void *address;
1.47 + Symbol *tbl_next;
1.48 +
1.49 + inline char *buffer()
1.50 + {
1.51 + return reinterpret_cast<char *>(this + 1);
1.52 + }
1.53 +};
1.54 +
1.55 +class SymbolTable
1.56 +{
1.57 +public:
1.58 + ~SymbolTable()
1.59 + {
1.60 + for (uint32_t i = 0; i < nbuckets; i++)
1.61 + {
1.62 + Symbol *sym = buckets[i];
1.63 + while (sym != NULL)
1.64 + {
1.65 + Symbol *next = sym->tbl_next;
1.66 + free(sym);
1.67 + sym = next;
1.68 + }
1.69 + }
1.70 + free(buckets);
1.71 + }
1.72 +
1.73 + bool Initialize()
1.74 + {
1.75 + buckets = (Symbol **)malloc(sizeof(Symbol *) * KESTRING_TABLE_START_SIZE);
1.76 + if (buckets == NULL)
1.77 + {
1.78 + return false;
1.79 + }
1.80 + memset(buckets, 0, sizeof(Symbol *) * KESTRING_TABLE_START_SIZE);
1.81 +
1.82 + nbuckets = KESTRING_TABLE_START_SIZE;
1.83 + nused = 0;
1.84 + bucketmask = KESTRING_TABLE_START_SIZE - 1;
1.85 + return true;
1.86 + }
1.87 +
1.88 + static inline uint32_t HashString(const char *data, size_t len)
1.89 + {
1.90 + #undef get16bits
1.91 + #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
1.92 + || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
1.93 + #define get16bits(d) (*((const uint16_t *) (d)))
1.94 + #endif
1.95 + #if !defined (get16bits)
1.96 + #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
1.97 + +(uint32_t)(((const uint8_t *)(d))[0]) )
1.98 + #endif
1.99 + uint32_t hash = len, tmp;
1.100 + int rem;
1.101 +
1.102 + if (len <= 0 || data == NULL)
1.103 + {
1.104 + return 0;
1.105 + }
1.106 +
1.107 + rem = len & 3;
1.108 + len >>= 2;
1.109 +
1.110 + /* Main loop */
1.111 + for (;len > 0; len--) {
1.112 + hash += get16bits (data);
1.113 + tmp = (get16bits (data+2) << 11) ^ hash;
1.114 + hash = (hash << 16) ^ tmp;
1.115 + data += 2 * sizeof (uint16_t);
1.116 + hash += hash >> 11;
1.117 + }
1.118 +
1.119 + /* Handle end cases */
1.120 + switch (rem) {
1.121 + case 3: hash += get16bits (data);
1.122 + hash ^= hash << 16;
1.123 + hash ^= data[sizeof (uint16_t)] << 18;
1.124 + hash += hash >> 11;
1.125 + break;
1.126 + case 2: hash += get16bits (data);
1.127 + hash ^= hash << 11;
1.128 + hash += hash >> 17;
1.129 + break;
1.130 + case 1: hash += *data;
1.131 + hash ^= hash << 10;
1.132 + hash += hash >> 1;
1.133 + }
1.134 +
1.135 + /* Force "avalanching" of final 127 bits */
1.136 + hash ^= hash << 3;
1.137 + hash += hash >> 5;
1.138 + hash ^= hash << 4;
1.139 + hash += hash >> 17;
1.140 + hash ^= hash << 25;
1.141 + hash += hash >> 6;
1.142 +
1.143 + return hash;
1.144 +
1.145 + #undef get16bits
1.146 + }
1.147 +
1.148 + Symbol **FindSymbolBucket(const char *str, size_t len, uint32_t hash)
1.149 + {
1.150 + uint32_t bucket = hash & bucketmask;
1.151 + Symbol **pkvs = &buckets[bucket];
1.152 +
1.153 + Symbol *kvs = *pkvs;
1.154 + while (kvs != NULL)
1.155 + {
1.156 + if (len == kvs->length && memcmp(str, kvs->buffer(), len * sizeof(char)) == 0)
1.157 + {
1.158 + return pkvs;
1.159 + }
1.160 + pkvs = &kvs->tbl_next;
1.161 + kvs = *pkvs;
1.162 + }
1.163 +
1.164 + return pkvs;
1.165 + }
1.166 +
1.167 + void ResizeSymbolTable()
1.168 + {
1.169 + uint32_t xnbuckets = nbuckets * 2;
1.170 + Symbol **xbuckets = (Symbol **)malloc(sizeof(Symbol *) * xnbuckets);
1.171 + if (xbuckets == NULL)
1.172 + {
1.173 + return;
1.174 + }
1.175 + memset(xbuckets, 0, sizeof(Symbol *) * xnbuckets);
1.176 + uint32_t xbucketmask = xnbuckets - 1;
1.177 + for (uint32_t i = 0; i < nbuckets; i++)
1.178 + {
1.179 + Symbol *sym = buckets[i];
1.180 + while (sym != NULL)
1.181 + {
1.182 + Symbol *next = sym->tbl_next;
1.183 + uint32_t bucket = sym->hash & xbucketmask;
1.184 + sym->tbl_next = xbuckets[bucket];
1.185 + xbuckets[bucket] = sym;
1.186 + sym = next;
1.187 + }
1.188 + }
1.189 + free(buckets);
1.190 + buckets = xbuckets;
1.191 + nbuckets = xnbuckets;
1.192 + bucketmask = xbucketmask;
1.193 + }
1.194 +
1.195 + Symbol *FindSymbol(const char *str, size_t len)
1.196 + {
1.197 + uint32_t hash = HashString(str, len);
1.198 + Symbol **pkvs = FindSymbolBucket(str, len, hash);
1.199 + return *pkvs;
1.200 + }
1.201 +
1.202 + Symbol *InternSymbol(const char* str, size_t len, void *address)
1.203 + {
1.204 + uint32_t hash = HashString(str, len);
1.205 + Symbol **pkvs = FindSymbolBucket(str, len, hash);
1.206 + if (*pkvs != NULL)
1.207 + {
1.208 + return *pkvs;
1.209 + }
1.210 +
1.211 + Symbol *kvs = (Symbol *)malloc(sizeof(Symbol) + sizeof(char) * (len + 1));
1.212 + kvs->length = len;
1.213 + kvs->hash = hash;
1.214 + kvs->address = address;
1.215 + kvs->tbl_next = NULL;
1.216 + memcpy(kvs + 1, str, sizeof(char) * (len + 1));
1.217 + *pkvs = kvs;
1.218 + nused++;
1.219 +
1.220 + if (nused > nbuckets && nbuckets <= INT_MAX / 2)
1.221 + {
1.222 + ResizeSymbolTable();
1.223 + }
1.224 +
1.225 + return kvs;
1.226 + }
1.227 +private:
1.228 + uint32_t nbuckets;
1.229 + uint32_t nused;
1.230 + uint32_t bucketmask;
1.231 + Symbol **buckets;
1.232 +};
1.233 +
1.234 +#endif //_INCLUDE_SOURCEMOD_CORE_SYMBOLTABLE_H_
