sourcehook/sh_tinyhash.h
branchsourcemm-1.6.0
changeset 428 40a9d2f61121
parent 370 4dc28ab1c722
child 429 cadecde4b802
     1.1 --- a/sourcehook/sh_tinyhash.h	Thu Oct 04 19:46:28 2007 +0000
     1.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.3 @@ -1,534 +0,0 @@
     1.4 -/* ======== SourceMM ========
     1.5 -* Copyright (C) 2004-2007 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_