core-1.4/sourcehook/sh_tinyhash.h
changeset 541 35a8cda28485
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/core-1.4/sourcehook/sh_tinyhash.h	Fri Nov 14 04:25:40 2008 -0600
     1.3 @@ -0,0 +1,534 @@
     1.4 +/* ======== SourceMM ========
     1.5 +* Copyright (C) 2004-2008 Metamod:Source Development Team
     1.6 +* No warranties of any kind
     1.7 +*
     1.8 +* License: zlib/libpng
     1.9 +*
    1.10 +* Author(s): David "BAILOPAN" Anderson
    1.11 +* ============================
    1.12 +*/
    1.13 +
    1.14 +#ifndef _INCLUDE_SH_TINYHASH_H_
    1.15 +#define _INCLUDE_SH_TINYHASH_H_
    1.16 +
    1.17 +#include "sh_list.h"
    1.18 +
    1.19 +#define _T_INIT_HASH_SIZE	32
    1.20 +
    1.21 +namespace SourceHook
    1.22 +{
    1.23 +	template <class K>
    1.24 +	int HashFunction(const K & k);
    1.25 +
    1.26 +	template <class U>
    1.27 +	int HashAlt(const U &u);
    1.28 +
    1.29 +	template <class U, class K>
    1.30 +	int CompareAlt(const U &k1, const K &k2);
    1.31 +
    1.32 +	template <class K>
    1.33 +	int Compare(const K & k1, const K & k2);
    1.34 +
    1.35 +	/**
    1.36 +	 * This is a tiny, growable hash class.
    1.37 +	 * Meant for quick and dirty dictionaries only!
    1.38 +	 */
    1.39 +	template <class K, class V>
    1.40 +	class THash
    1.41 +	{
    1.42 +	public:
    1.43 +		struct THashNode
    1.44 +		{
    1.45 +			THashNode(const K & k, const V & v) :
    1.46 +				key(k), val(v)
    1.47 +				{
    1.48 +				};
    1.49 +			THashNode & operator =(const THashNode &other)
    1.50 +			{
    1.51 +				key = other.key;
    1.52 +				val = other.val;
    1.53 +			}
    1.54 +			K key;
    1.55 +			V val;
    1.56 +		};
    1.57 +		typedef List<THashNode *> *	NodePtr;
    1.58 +	public:
    1.59 +		class const_iterator;
    1.60 +		THash() : m_Buckets(NULL), m_numBuckets(0), m_percentUsed(0.0f)
    1.61 +		{
    1.62 +			_Refactor();
    1.63 +		}
    1.64 +		THash(const THash &other) : m_Buckets(new NodePtr[other.m_numBuckets]),
    1.65 +			m_numBuckets(other.m_numBuckets), m_percentUsed(other.m_percentUsed)
    1.66 +		{
    1.67 +			for (size_t i=0; i<m_numBuckets; i++)
    1.68 +					m_Buckets[i] = NULL;
    1.69 +			for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
    1.70 +				_FindOrInsert(iter->key)->val = iter->val;
    1.71 +		}
    1.72 +		void operator=(const THash &other)
    1.73 +		{
    1.74 +			clear();
    1.75 +			for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
    1.76 +				_FindOrInsert(iter->key)->val = iter->val;
    1.77 +		}
    1.78 +
    1.79 +		~THash()
    1.80 +		{
    1.81 +			_Clear();
    1.82 +		}
    1.83 +		void clear()
    1.84 +		{
    1.85 +			_Clear();
    1.86 +			_Refactor();
    1.87 +		}
    1.88 +		size_t GetBuckets()
    1.89 +		{
    1.90 +			return m_numBuckets;
    1.91 +		}
    1.92 +		float PercentUsed()
    1.93 +		{
    1.94 +			return m_percentUsed;
    1.95 +		}
    1.96 +		V & operator [](const K & key)
    1.97 +		{
    1.98 +			THashNode *pNode = _FindOrInsert(key);
    1.99 +			return pNode->val;
   1.100 +		}
   1.101 +	private:
   1.102 +		void _Clear()
   1.103 +		{
   1.104 +			typename List<THashNode *>::iterator iter, end;
   1.105 +			for (size_t i=0; i<m_numBuckets; i++)
   1.106 +			{
   1.107 +				if (m_Buckets[i])
   1.108 +				{
   1.109 +					end = m_Buckets[i]->end();
   1.110 +					iter = m_Buckets[i]->begin();
   1.111 +					while (iter != end)
   1.112 +					{
   1.113 +						delete (*iter);
   1.114 +						iter++;
   1.115 +					}
   1.116 +					delete m_Buckets[i];
   1.117 +					m_Buckets[i] = NULL;
   1.118 +				}
   1.119 +			}
   1.120 +			if (m_Buckets)
   1.121 +				delete [] m_Buckets;
   1.122 +			m_Buckets = NULL;
   1.123 +			m_numBuckets = 0;
   1.124 +		}
   1.125 +	public:
   1.126 +		template <typename U>
   1.127 +		V & AltFindOrInsert(const U & ukey)
   1.128 +		{
   1.129 +			size_t place = HashAlt(ukey) % m_numBuckets;
   1.130 +			THashNode *pNode = NULL;
   1.131 +			if (!m_Buckets[place])
   1.132 +			{
   1.133 +				m_Buckets[place] = new List<THashNode *>;
   1.134 +				pNode = new THashNode(ukey, V());
   1.135 +				m_Buckets[place]->push_back(pNode);
   1.136 +				m_percentUsed += (1.0f / (float)m_numBuckets);
   1.137 +			} else {
   1.138 +				typename List<THashNode *>::iterator iter;
   1.139 +				for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++)
   1.140 +				{
   1.141 +					if (CompareAlt(ukey, (*iter)->key) == 0)
   1.142 +					{
   1.143 +						return (*iter)->val;
   1.144 +					}
   1.145 +				}
   1.146 +				//node does not exist
   1.147 +				pNode = new THashNode(ukey, V());
   1.148 +				m_Buckets[place]->push_back(pNode);
   1.149 +			}
   1.150 +			if (PercentUsed() > 0.75f)
   1.151 +			{
   1.152 +				_Refactor();
   1.153 +			}
   1.154 +			return pNode->val;
   1.155 +		}
   1.156 +	private:
   1.157 +		THashNode *_FindOrInsert(const K & key)
   1.158 +		{
   1.159 +			size_t place = HashFunction(key) % m_numBuckets;
   1.160 +			THashNode *pNode = NULL;
   1.161 +			if (!m_Buckets[place])
   1.162 +			{
   1.163 +				m_Buckets[place] = new List<THashNode *>;
   1.164 +				pNode = new THashNode(key, V());
   1.165 +				m_Buckets[place]->push_back(pNode);
   1.166 +				m_percentUsed += (1.0f / (float)m_numBuckets);
   1.167 +			} else {
   1.168 +				typename List<THashNode *>::iterator iter;
   1.169 +				for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++)
   1.170 +				{
   1.171 +					if (Compare((*iter)->key, key) == 0)
   1.172 +						return (*iter);
   1.173 +				}
   1.174 +				//node does not exist
   1.175 +				pNode = new THashNode(key, V());
   1.176 +				m_Buckets[place]->push_back(pNode);
   1.177 +			}
   1.178 +			if (PercentUsed() > 0.75f)
   1.179 +			{
   1.180 +				_Refactor();
   1.181 +			}
   1.182 +			return pNode;
   1.183 +		}
   1.184 +		void _Refactor()
   1.185 +		{
   1.186 +			m_percentUsed = 0.0f;
   1.187 +			if (!m_numBuckets)
   1.188 +			{
   1.189 +				m_numBuckets = _T_INIT_HASH_SIZE;
   1.190 +				m_Buckets = new NodePtr[m_numBuckets];
   1.191 +				for (size_t i=0; i<m_numBuckets; i++)
   1.192 +					m_Buckets[i] = NULL;
   1.193 +			} else {
   1.194 +				size_t oldSize = m_numBuckets;
   1.195 +				m_numBuckets *= 2;
   1.196 +				typename List<THashNode *>::iterator iter;
   1.197 +				size_t place;
   1.198 +				THashNode *pHashNode;
   1.199 +				NodePtr *temp = new NodePtr[m_numBuckets];
   1.200 +				for (size_t i=0; i<m_numBuckets; i++)
   1.201 +					temp[i] = NULL;
   1.202 +				//look in old hash table
   1.203 +				for (size_t i=0; i<oldSize; i++)
   1.204 +				{
   1.205 +					//does a bucket have anything?
   1.206 +					if (m_Buckets[i])
   1.207 +					{
   1.208 +						//go through the list of items
   1.209 +						for (iter = m_Buckets[i]->begin(); iter != m_Buckets[i]->end(); iter++)
   1.210 +						{
   1.211 +							pHashNode = (*iter);
   1.212 +							//rehash it with the new bucket filter
   1.213 +							place = HashFunction(pHashNode->key) % m_numBuckets;
   1.214 +							//add it to the new hash table
   1.215 +							if (!temp[place])
   1.216 +							{
   1.217 +								temp[place] = new List<THashNode *>;
   1.218 +								m_percentUsed += (1.0f / (float)m_numBuckets);
   1.219 +							}
   1.220 +							temp[place]->push_back(pHashNode);
   1.221 +						}
   1.222 +						//delete that bucket!
   1.223 +						delete m_Buckets[i];
   1.224 +						m_Buckets[i] = NULL;
   1.225 +					}
   1.226 +				}
   1.227 +				//reassign bucket table
   1.228 +				delete [] m_Buckets;
   1.229 +				m_Buckets = temp;
   1.230 +			}
   1.231 +		}
   1.232 +	public:
   1.233 +		friend class iterator;
   1.234 +		friend class const_iterator;
   1.235 +		class iterator
   1.236 +		{
   1.237 +			friend class THash;
   1.238 +		public:
   1.239 +			iterator() : curbucket(-1), hash(NULL), end(true)
   1.240 +			{
   1.241 +			};
   1.242 +			iterator(THash *h) : curbucket(-1), hash(h), end(false)
   1.243 +			{
   1.244 +				if (!h->m_Buckets)
   1.245 +					end = true;
   1.246 +				else
   1.247 +					_Inc();
   1.248 +			};
   1.249 +			//pre increment
   1.250 +			iterator & operator++()
   1.251 +			{
   1.252 +				_Inc();
   1.253 +				return *this;
   1.254 +			}
   1.255 +			//post increment
   1.256 +			iterator operator++(int)
   1.257 +			{
   1.258 +				iterator old(*this);
   1.259 +				_Inc();
   1.260 +				return old;
   1.261 +			}
   1.262 +			const THashNode & operator * () const
   1.263 +			{
   1.264 +				return *(*iter);
   1.265 +			}
   1.266 +			THashNode & operator * ()
   1.267 +			{
   1.268 +				return *(*iter);
   1.269 +			}
   1.270 +			const THashNode * operator ->() const
   1.271 +			{
   1.272 +				return (*iter);
   1.273 +			}
   1.274 +			THashNode * operator ->()
   1.275 +			{
   1.276 +				return (*iter);
   1.277 +			}
   1.278 +			bool operator ==(const iterator &where) const
   1.279 +			{
   1.280 +				if (where.hash == this->hash
   1.281 +					&& where.end == this->end
   1.282 +					&&
   1.283 +					 (this->end ||
   1.284 +					   ((where.curbucket == this->curbucket)
   1.285 +						&& (where.iter == iter))
   1.286 +						 ))
   1.287 +					return true;
   1.288 +				return false;
   1.289 +			}
   1.290 +			bool operator !=(const iterator &where) const
   1.291 +			{
   1.292 +				return !( (*this) == where );
   1.293 +			}
   1.294 +
   1.295 +			void erase()
   1.296 +			{
   1.297 +				if (end || !hash || curbucket < 0 || curbucket >= static_cast<int>(hash->m_numBuckets))
   1.298 +					return;
   1.299 +
   1.300 +				// Remove this element and move to the next one
   1.301 +				iterator tmp = *this;
   1.302 +				++tmp;
   1.303 +				delete (*iter);
   1.304 +				hash->m_Buckets[curbucket]->erase(iter);
   1.305 +				*this = tmp;
   1.306 +
   1.307 +				// :TODO: Maybe refactor to a lower size if required
   1.308 +			}
   1.309 +		private:
   1.310 +			void _Inc()
   1.311 +			{
   1.312 +				if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
   1.313 +					return;
   1.314 +				if (curbucket < 0)
   1.315 +				{
   1.316 +					for (int i=0; i<(int)hash->m_numBuckets; i++)
   1.317 +					{
   1.318 +						if (hash->m_Buckets[i])
   1.319 +						{
   1.320 +							iter = hash->m_Buckets[i]->begin();
   1.321 +							if (iter == hash->m_Buckets[i]->end())
   1.322 +								continue;
   1.323 +							curbucket = i;
   1.324 +							break;
   1.325 +						}
   1.326 +					}
   1.327 +					if (curbucket < 0)
   1.328 +						end = true;
   1.329 +				} else {
   1.330 +					if (iter != hash->m_Buckets[curbucket]->end())
   1.331 +						iter++;
   1.332 +					if (iter == hash->m_Buckets[curbucket]->end())
   1.333 +					{
   1.334 +						int oldbucket = curbucket;
   1.335 +						for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
   1.336 +						{
   1.337 +							if (hash->m_Buckets[i])
   1.338 +							{
   1.339 +								iter = hash->m_Buckets[i]->begin();
   1.340 +								if (iter == hash->m_Buckets[i]->end())
   1.341 +									continue;
   1.342 +								curbucket = i;
   1.343 +								break;
   1.344 +							}
   1.345 +						}
   1.346 +						if (curbucket == oldbucket)
   1.347 +							end = true;
   1.348 +					}
   1.349 +				}
   1.350 +			}
   1.351 +		private:
   1.352 +			int curbucket;
   1.353 +			typename SourceHook::List<THashNode *>::iterator iter;
   1.354 +			THash *hash;
   1.355 +			bool end;
   1.356 +		};
   1.357 +		class const_iterator
   1.358 +		{
   1.359 +			friend class THash;
   1.360 +		public:
   1.361 +			const_iterator() : curbucket(-1), hash(NULL), end(true)
   1.362 +			{
   1.363 +			};
   1.364 +			const_iterator(const THash *h) : curbucket(-1), hash(h), end(false)
   1.365 +			{
   1.366 +				if (!h->m_Buckets)
   1.367 +					end = true;
   1.368 +				else
   1.369 +					_Inc();
   1.370 +			};
   1.371 +			//pre increment
   1.372 +			const_iterator & operator++()
   1.373 +			{
   1.374 +				_Inc();
   1.375 +				return *this;
   1.376 +			}
   1.377 +			//post increment
   1.378 +			const_iterator operator++(int)
   1.379 +			{
   1.380 +				iterator old(*this);
   1.381 +				_Inc();
   1.382 +				return old;
   1.383 +			}
   1.384 +			const THashNode & operator * () const
   1.385 +			{
   1.386 +				return *(*iter);
   1.387 +			}
   1.388 +			const THashNode * operator ->() const
   1.389 +			{
   1.390 +				return (*iter);
   1.391 +			}
   1.392 +			bool operator ==(const const_iterator &where) const
   1.393 +			{
   1.394 +				if (where.hash == this->hash
   1.395 +					&& where.end == this->end
   1.396 +					&&
   1.397 +					 (this->end ||
   1.398 +					   ((where.curbucket == this->curbucket)
   1.399 +						&& (where.iter == iter))
   1.400 +						 ))
   1.401 +					return true;
   1.402 +				return false;
   1.403 +			}
   1.404 +			bool operator !=(const const_iterator &where) const
   1.405 +			{
   1.406 +				return !( (*this) == where );
   1.407 +			}
   1.408 +		private:
   1.409 +			void _Inc()
   1.410 +			{
   1.411 +				if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
   1.412 +					return;
   1.413 +				if (curbucket < 0)
   1.414 +				{
   1.415 +					for (int i=0; i<(int)hash->m_numBuckets; i++)
   1.416 +					{
   1.417 +						if (hash->m_Buckets[i])
   1.418 +						{
   1.419 +							iter = hash->m_Buckets[i]->begin();
   1.420 +							if (iter == hash->m_Buckets[i]->end())
   1.421 +								continue;
   1.422 +							curbucket = i;
   1.423 +							break;
   1.424 +						}
   1.425 +					}
   1.426 +					if (curbucket < 0)
   1.427 +						end = true;
   1.428 +				} else {
   1.429 +					if (iter != hash->m_Buckets[curbucket]->end())
   1.430 +						iter++;
   1.431 +					if (iter == hash->m_Buckets[curbucket]->end())
   1.432 +					{
   1.433 +						int oldbucket = curbucket;
   1.434 +						for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
   1.435 +						{
   1.436 +							if (hash->m_Buckets[i])
   1.437 +							{
   1.438 +								iter = hash->m_Buckets[i]->begin();
   1.439 +								if (iter == hash->m_Buckets[i]->end())
   1.440 +									continue;
   1.441 +								curbucket = i;
   1.442 +								break;
   1.443 +							}
   1.444 +						}
   1.445 +						if (curbucket == oldbucket)
   1.446 +							end = true;
   1.447 +					}
   1.448 +				}
   1.449 +			}
   1.450 +		private:
   1.451 +			int curbucket;
   1.452 +			typename SourceHook::List<THashNode *>::iterator iter;
   1.453 +			const THash *hash;
   1.454 +			bool end;
   1.455 +		};
   1.456 +	public:
   1.457 +		iterator begin()
   1.458 +		{
   1.459 +			return iterator(this);
   1.460 +		}
   1.461 +		iterator end()
   1.462 +		{
   1.463 +			iterator iter;
   1.464 +			iter.hash = this;
   1.465 +			return iter;
   1.466 +		}
   1.467 +
   1.468 +		const_iterator begin() const
   1.469 +		{
   1.470 +			return const_iterator(this);
   1.471 +		}
   1.472 +		const_iterator end() const
   1.473 +		{
   1.474 +			const_iterator iter;
   1.475 +			iter.hash = this;
   1.476 +			return iter;
   1.477 +		}
   1.478 +
   1.479 +		template <typename U>
   1.480 +		iterator find(const U & u) const
   1.481 +		{
   1.482 +			iterator b = begin();
   1.483 +			iterator e = end();
   1.484 +			for (iterator iter = b; iter != e; iter++)
   1.485 +			{
   1.486 +				if ( (*iter).key == u )
   1.487 +					return iter;
   1.488 +			}
   1.489 +			return end();
   1.490 +		}
   1.491 +		template <typename U>
   1.492 +		iterator find(const U & u)
   1.493 +		{
   1.494 +			iterator b = begin();
   1.495 +			iterator e = end();
   1.496 +			for (iterator iter = b; iter != e; iter++)
   1.497 +			{
   1.498 +				if ( (*iter).key == u )
   1.499 +					return iter;
   1.500 +			}
   1.501 +			return end();
   1.502 +		}
   1.503 +		template <typename U>
   1.504 +		iterator FindAlt(const U & u)
   1.505 +		{
   1.506 +			iterator b = begin();
   1.507 +			iterator e = end();
   1.508 +			for (iterator iter = b; iter != e; iter++)
   1.509 +			{
   1.510 +				if (CompareAlt(u, (*iter).key) == 0)
   1.511 +				{
   1.512 +					return iter;
   1.513 +				}
   1.514 +			}
   1.515 +			return e;
   1.516 +		}
   1.517 +		iterator erase(iterator where)
   1.518 +		{
   1.519 +			where.erase();
   1.520 +			return where;
   1.521 +		}
   1.522 +		template <typename U>
   1.523 +		void erase(const U & u)
   1.524 +		{
   1.525 +			iterator iter = find(u);
   1.526 +			if (iter == end())
   1.527 +				return;
   1.528 +			iter.erase();
   1.529 +		}
   1.530 +	private:
   1.531 +		NodePtr	*m_Buckets;
   1.532 +		size_t m_numBuckets;
   1.533 +		float m_percentUsed;
   1.534 +	};
   1.535 +};
   1.536 +
   1.537 +#endif //_INCLUDE_SH_TINYHASH_H_