Imported growable TinyHash class to replace std::map
authorDavid Anderson <dvander@alliedmods.net>
Tue Sep 13 16:52:14 2005 +0000 (2005-09-13)
changeset 102894e7be6c431
parent 101 7d93aa4d2bf3
child 103 3e818125b830
Imported growable TinyHash class to replace std::map
sourcehook/sh_tinyhash.h
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/sourcehook/sh_tinyhash.h	Tue Sep 13 16:52:14 2005 +0000
     1.3 @@ -0,0 +1,287 @@
     1.4 +/* ======== SourceMM ========
     1.5 +* Copyright (C) 2004-2005 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 K>
    1.27 +	int Compare(const K & k1, const K & k2);
    1.28 +
    1.29 +	/**
    1.30 +	 * This is a tiny, growable hash class.
    1.31 +	 * Meant for quick and dirty dictionaries only!
    1.32 +	 */
    1.33 +	template <class K, class V> 
    1.34 +	class THash
    1.35 +	{
    1.36 +	public:
    1.37 +		struct THashNode
    1.38 +		{
    1.39 +			THashNode(const K & k, const V & v) : 
    1.40 +				key(k), val(v)
    1.41 +				{
    1.42 +				};
    1.43 +			K key;
    1.44 +			V val;
    1.45 +		};
    1.46 +		typedef List<THashNode *> *	NodePtr;
    1.47 +	public:
    1.48 +		THash() : m_numBuckets(0), m_Buckets(NULL)
    1.49 +		{
    1.50 +			_Refactor();
    1.51 +		}
    1.52 +		size_t GetBuckets()
    1.53 +		{
    1.54 +			return m_numBuckets;
    1.55 +		}
    1.56 +		float PercentUsed()
    1.57 +		{
    1.58 +			return m_percentUsed;
    1.59 +		}
    1.60 +		V & operator [](const K & key)
    1.61 +		{
    1.62 +			THashNode *pNode = _FindOrInsert(key);
    1.63 +			return pNode->val;
    1.64 +		}
    1.65 +	private:
    1.66 +		THashNode *_FindOrInsert(const K & key)
    1.67 +		{
    1.68 +			size_t place = HashFunction(key) % m_numBuckets;
    1.69 +			THashNode *pNode = NULL;
    1.70 +			if (!m_Buckets[place])
    1.71 +			{
    1.72 +				m_Buckets[place] = new List<THashNode *>;
    1.73 +				pNode = new THashNode(key, V());
    1.74 +				m_Buckets[place]->push_back(pNode);
    1.75 +				m_percentUsed += (1.0f / (float)m_numBuckets);
    1.76 +			} else {
    1.77 +				List<THashNode *>::iterator iter;
    1.78 +				for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++)
    1.79 +				{
    1.80 +					if (Compare((*iter)->key, key) == 0)
    1.81 +						return (*iter);
    1.82 +				}
    1.83 +				//node does not exist
    1.84 +				pNode = new THashNode(key, V());
    1.85 +				m_Buckets[place]->push_back(pNode);
    1.86 +			}
    1.87 +			if (PercentUsed() > 0.75f)
    1.88 +				_Refactor();
    1.89 +			return pNode;
    1.90 +		}
    1.91 +		void _Refactor()
    1.92 +		{
    1.93 +			m_percentUsed = 0.0f;
    1.94 +			if (!m_numBuckets)
    1.95 +			{
    1.96 +				m_numBuckets = _T_INIT_HASH_SIZE;
    1.97 +				m_Buckets = new NodePtr[m_numBuckets];
    1.98 +				for (size_t i=0; i<m_numBuckets; i++)
    1.99 +					m_Buckets[i] = NULL;
   1.100 +			} else {
   1.101 +				size_t oldSize = m_numBuckets;
   1.102 +				m_numBuckets *= 2;
   1.103 +				List<THashNode *>::iterator iter;
   1.104 +				size_t place;
   1.105 +				THashNode *pHashNode;
   1.106 +                NodePtr *temp = new NodePtr[m_numBuckets];
   1.107 +				for (size_t i=0; i<m_numBuckets; i++)
   1.108 +					temp[i] = NULL;
   1.109 +				//look in old hash table
   1.110 +				for (size_t i=0; i<oldSize; i++)
   1.111 +				{
   1.112 +					//does a bucket have anything?
   1.113 +					if (m_Buckets[i])
   1.114 +					{
   1.115 +						//go through the list of items
   1.116 +						for (iter = m_Buckets[i]->begin(); iter != m_Buckets[i]->end(); iter++)
   1.117 +						{
   1.118 +							pHashNode = (*iter);
   1.119 +							//rehash it with the new bucket filter
   1.120 +							place = HashFunction(pHashNode->key) % m_numBuckets;
   1.121 +							//add it to the new hash table
   1.122 +							if (!temp[place])
   1.123 +							{
   1.124 +								temp[place] = new List<THashNode *>;
   1.125 +								m_percentUsed += (1.0f / (float)m_numBuckets);
   1.126 +							}
   1.127 +							temp[place]->push_back(pHashNode);
   1.128 +						}
   1.129 +						//delete that bucket!
   1.130 +						delete m_Buckets[i];
   1.131 +						m_Buckets[i] = NULL;
   1.132 +					}
   1.133 +				}
   1.134 +				//reassign bucket table
   1.135 +				delete [] m_Buckets;
   1.136 +				m_Buckets = temp;
   1.137 +			}
   1.138 +		}
   1.139 +	public:
   1.140 +		friend class iterator;
   1.141 +		class iterator
   1.142 +		{
   1.143 +			friend class THash;
   1.144 +		public:
   1.145 +			iterator() : hash(NULL), end(true)
   1.146 +			{
   1.147 +			};
   1.148 +			iterator(THash *h) : hash(h), end(false)
   1.149 +			{
   1.150 +				if (!h->m_Buckets)
   1.151 +					end = true;
   1.152 +				else
   1.153 +					_Inc();
   1.154 +			};
   1.155 +			//pre increment
   1.156 +			iterator & operator++()
   1.157 +			{
   1.158 +				_Inc();
   1.159 +				return *this;
   1.160 +			}
   1.161 +			//post increment
   1.162 +			iterator operator++(int)
   1.163 +			{
   1.164 +				iterator old(*this);
   1.165 +				_Inc();
   1.166 +				return old;
   1.167 +			}
   1.168 +			THashNode & operator * () const
   1.169 +			{
   1.170 +				return *(*iter);
   1.171 +			}
   1.172 +			THashNode & operator * ()
   1.173 +			{
   1.174 +				return *(*iter);
   1.175 +			}
   1.176 +			THashNode * operator ->() const
   1.177 +			{
   1.178 +				return (*iter);
   1.179 +			}
   1.180 +			THashNode * operator ->()
   1.181 +			{
   1.182 +				return (*iter);
   1.183 +			}
   1.184 +			bool operator ==(const iterator &where) const
   1.185 +			{
   1.186 +				if (where.hash == this->hash
   1.187 +					&& where.end == this->end
   1.188 +					&& 
   1.189 +					 (this->end || 
   1.190 +					   ((where.curbucket == this->curbucket) 
   1.191 +					     && (where.iter == iter))
   1.192 +						 ))
   1.193 +					return true;
   1.194 +				return false;
   1.195 +			}
   1.196 +			bool operator !=(const iterator &where) const
   1.197 +			{
   1.198 +				return !( (*this) == where );
   1.199 +			}
   1.200 +		private:
   1.201 +			void _Inc()
   1.202 +			{
   1.203 +				if (end || !hash)
   1.204 +					return;
   1.205 +				if (curbucket < 0)
   1.206 +				{
   1.207 +					for (int i=0; i<(int)hash->m_numBuckets; i++)
   1.208 +					{
   1.209 +						if (hash->m_Buckets[i])
   1.210 +						{
   1.211 +							iter = hash->m_Buckets[i]->begin();
   1.212 +							if (iter == hash->m_Buckets[i]->end())
   1.213 +								continue;
   1.214 +							curbucket = i;
   1.215 +							break;
   1.216 +						}
   1.217 +					}
   1.218 +					if (curbucket < 0)
   1.219 +						end = true;
   1.220 +				} else {
   1.221 +					if (iter != hash->m_Buckets[curbucket]->end())
   1.222 +						iter++;
   1.223 +					if (iter == hash->m_Buckets[curbucket]->end())
   1.224 +					{
   1.225 +						int oldbucket = curbucket;
   1.226 +						for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
   1.227 +						{
   1.228 +							if (hash->m_Buckets[i])
   1.229 +							{
   1.230 +								iter = hash->m_Buckets[i]->begin();
   1.231 +								if (iter == hash->m_Buckets[i]->end())
   1.232 +									continue;
   1.233 +								curbucket = i;
   1.234 +								break;
   1.235 +							}
   1.236 +						}
   1.237 +						if (curbucket == oldbucket)
   1.238 +							end = true;
   1.239 +					}
   1.240 +				}
   1.241 +			}
   1.242 +		private:
   1.243 +			int curbucket;
   1.244 +			typename SourceHook::List<THashNode *>::iterator iter;
   1.245 +			THash *hash;
   1.246 +			bool end;
   1.247 +		};
   1.248 +	public:
   1.249 +		iterator begin()
   1.250 +		{
   1.251 +			return iterator(this);
   1.252 +		}
   1.253 +		iterator end()
   1.254 +		{
   1.255 +			iterator iter;
   1.256 +			iter.hash = this;
   1.257 +			return iter;
   1.258 +		}
   1.259 +		template <typename U>
   1.260 +		iterator find(const U & u) const
   1.261 +		{
   1.262 +			iterator b = begin();
   1.263 +			iterator e = end();
   1.264 +			for (iterator iter = b; iter != e; iter++)
   1.265 +			{
   1.266 +				if ( (*iter).key == u )
   1.267 +					return iter;
   1.268 +			}
   1.269 +			return end();
   1.270 +		}
   1.271 +		template <typename U>
   1.272 +		iterator find(const U & u)
   1.273 +		{
   1.274 +			iterator b = begin();
   1.275 +			iterator e = end();
   1.276 +			for (iterator iter = b; iter != e; iter++)
   1.277 +			{
   1.278 +				if ( (*iter).key == u )
   1.279 +					return iter;
   1.280 +			}
   1.281 +			return end();
   1.282 +		}
   1.283 +	private:
   1.284 +		NodePtr	*m_Buckets;
   1.285 +		size_t m_numBuckets;
   1.286 +		float m_percentUsed;
   1.287 +	};
   1.288 +};
   1.289 +
   1.290 +#endif //_INCLUDE_SH_TINYHASH_H_