core/sourcehook/sh_tinyhash.h
author Scott Ehlert <ds@alliedmods.net>
Thu Dec 10 00:59:50 2009 -0600 (2009-12-10)
changeset 689 4065ba5e9155
parent 539 db914129ae01
child 733 2365240861a2
permissions -rw-r--r--
Rewrote user message caching code to always use IServerGameDLL::GetUserMessageInfo (bug 4117, r=dvander).

Games where the above function can crash are handled by detouring tier0's Error() function and jumping back to our own code. So in theory this should work on all games now.
     1 /* ======== SourceMM ========
     2 * Copyright (C) 2004-2008 Metamod:Source Development Team
     3 * No warranties of any kind
     4 *
     5 * License: zlib/libpng
     6 *
     7 * Author(s): David "BAILOPAN" Anderson
     8 * ============================
     9 */
    10 
    11 #ifndef _INCLUDE_SH_TINYHASH_H_
    12 #define _INCLUDE_SH_TINYHASH_H_
    13 
    14 #include "sh_list.h"
    15 
    16 #define _T_INIT_HASH_SIZE	32
    17 
    18 namespace SourceHook
    19 {
    20 	template <class K>
    21 	int HashFunction(const K & k);
    22 
    23 	template <class U>
    24 	int HashAlt(const U &u);
    25 
    26 	template <class U, class K>
    27 	int CompareAlt(const U &k1, const K &k2);
    28 
    29 	template <class K>
    30 	int Compare(const K & k1, const K & k2);
    31 
    32 	/**
    33 	 * This is a tiny, growable hash class.
    34 	 * Meant for quick and dirty dictionaries only!
    35 	 */
    36 	template <class K, class V>
    37 	class THash
    38 	{
    39 	public:
    40 		struct THashNode
    41 		{
    42 			THashNode(const K & k, const V & v) :
    43 				key(k), val(v)
    44 				{
    45 				};
    46 			THashNode & operator =(const THashNode &other)
    47 			{
    48 				key = other.key;
    49 				val = other.val;
    50 			}
    51 			K key;
    52 			V val;
    53 		};
    54 		typedef List<THashNode *> *	NodePtr;
    55 	public:
    56 		class const_iterator;
    57 		THash() : m_Buckets(NULL), m_numBuckets(0), m_percentUsed(0.0f)
    58 		{
    59 			_Refactor();
    60 		}
    61 		THash(const THash &other) : m_Buckets(new NodePtr[other.m_numBuckets]),
    62 			m_numBuckets(other.m_numBuckets), m_percentUsed(other.m_percentUsed)
    63 		{
    64 			for (size_t i=0; i<m_numBuckets; i++)
    65 					m_Buckets[i] = NULL;
    66 			for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
    67 				_FindOrInsert(iter->key)->val = iter->val;
    68 		}
    69 		void operator=(const THash &other)
    70 		{
    71 			clear();
    72 			for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
    73 				_FindOrInsert(iter->key)->val = iter->val;
    74 		}
    75 
    76 		~THash()
    77 		{
    78 			_Clear();
    79 		}
    80 		void clear()
    81 		{
    82 			_Clear();
    83 			_Refactor();
    84 		}
    85 		size_t GetBuckets()
    86 		{
    87 			return m_numBuckets;
    88 		}
    89 		float PercentUsed()
    90 		{
    91 			return m_percentUsed;
    92 		}
    93 		V & operator [](const K & key)
    94 		{
    95 			THashNode *pNode = _FindOrInsert(key);
    96 			return pNode->val;
    97 		}
    98 	private:
    99 		void _Clear()
   100 		{
   101 			typename List<THashNode *>::iterator iter, end;
   102 			for (size_t i=0; i<m_numBuckets; i++)
   103 			{
   104 				if (m_Buckets[i])
   105 				{
   106 					end = m_Buckets[i]->end();
   107 					iter = m_Buckets[i]->begin();
   108 					while (iter != end)
   109 					{
   110 						delete (*iter);
   111 						iter++;
   112 					}
   113 					delete m_Buckets[i];
   114 					m_Buckets[i] = NULL;
   115 				}
   116 			}
   117 			if (m_Buckets)
   118 				delete [] m_Buckets;
   119 			m_Buckets = NULL;
   120 			m_numBuckets = 0;
   121 		}
   122 	public:
   123 		template <typename U>
   124 		V & AltFindOrInsert(const U & ukey)
   125 		{
   126 			size_t place = HashAlt(ukey) % m_numBuckets;
   127 			THashNode *pNode = NULL;
   128 			if (!m_Buckets[place])
   129 			{
   130 				m_Buckets[place] = new List<THashNode *>;
   131 				pNode = new THashNode(ukey, V());
   132 				m_Buckets[place]->push_back(pNode);
   133 				m_percentUsed += (1.0f / (float)m_numBuckets);
   134 			} else {
   135 				typename List<THashNode *>::iterator iter;
   136 				for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++)
   137 				{
   138 					if (CompareAlt(ukey, (*iter)->key) == 0)
   139 					{
   140 						return (*iter)->val;
   141 					}
   142 				}
   143 				//node does not exist
   144 				pNode = new THashNode(ukey, V());
   145 				m_Buckets[place]->push_back(pNode);
   146 			}
   147 			if (PercentUsed() > 0.75f)
   148 			{
   149 				_Refactor();
   150 			}
   151 			return pNode->val;
   152 		}
   153 	private:
   154 		THashNode *_FindOrInsert(const K & key)
   155 		{
   156 			size_t place = HashFunction(key) % m_numBuckets;
   157 			THashNode *pNode = NULL;
   158 			if (!m_Buckets[place])
   159 			{
   160 				m_Buckets[place] = new List<THashNode *>;
   161 				pNode = new THashNode(key, V());
   162 				m_Buckets[place]->push_back(pNode);
   163 				m_percentUsed += (1.0f / (float)m_numBuckets);
   164 			} else {
   165 				typename List<THashNode *>::iterator iter;
   166 				for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++)
   167 				{
   168 					if (Compare((*iter)->key, key) == 0)
   169 						return (*iter);
   170 				}
   171 				//node does not exist
   172 				pNode = new THashNode(key, V());
   173 				m_Buckets[place]->push_back(pNode);
   174 			}
   175 			if (PercentUsed() > 0.75f)
   176 			{
   177 				_Refactor();
   178 			}
   179 			return pNode;
   180 		}
   181 		void _Refactor()
   182 		{
   183 			m_percentUsed = 0.0f;
   184 			if (!m_numBuckets)
   185 			{
   186 				m_numBuckets = _T_INIT_HASH_SIZE;
   187 				m_Buckets = new NodePtr[m_numBuckets];
   188 				for (size_t i=0; i<m_numBuckets; i++)
   189 					m_Buckets[i] = NULL;
   190 			} else {
   191 				size_t oldSize = m_numBuckets;
   192 				m_numBuckets *= 2;
   193 				typename List<THashNode *>::iterator iter;
   194 				size_t place;
   195 				THashNode *pHashNode;
   196 				NodePtr *temp = new NodePtr[m_numBuckets];
   197 				for (size_t i=0; i<m_numBuckets; i++)
   198 					temp[i] = NULL;
   199 				//look in old hash table
   200 				for (size_t i=0; i<oldSize; i++)
   201 				{
   202 					//does a bucket have anything?
   203 					if (m_Buckets[i])
   204 					{
   205 						//go through the list of items
   206 						for (iter = m_Buckets[i]->begin(); iter != m_Buckets[i]->end(); iter++)
   207 						{
   208 							pHashNode = (*iter);
   209 							//rehash it with the new bucket filter
   210 							place = HashFunction(pHashNode->key) % m_numBuckets;
   211 							//add it to the new hash table
   212 							if (!temp[place])
   213 							{
   214 								temp[place] = new List<THashNode *>;
   215 								m_percentUsed += (1.0f / (float)m_numBuckets);
   216 							}
   217 							temp[place]->push_back(pHashNode);
   218 						}
   219 						//delete that bucket!
   220 						delete m_Buckets[i];
   221 						m_Buckets[i] = NULL;
   222 					}
   223 				}
   224 				//reassign bucket table
   225 				delete [] m_Buckets;
   226 				m_Buckets = temp;
   227 			}
   228 		}
   229 	public:
   230 		class iterator
   231 		{
   232 			friend class THash;
   233 		public:
   234 			iterator() : curbucket(-1), hash(NULL), end(true)
   235 			{
   236 			};
   237 			iterator(THash *h) : curbucket(-1), hash(h), end(false)
   238 			{
   239 				if (!h->m_Buckets)
   240 					end = true;
   241 				else
   242 					_Inc();
   243 			};
   244 			//pre increment
   245 			iterator & operator++()
   246 			{
   247 				_Inc();
   248 				return *this;
   249 			}
   250 			//post increment
   251 			iterator operator++(int)
   252 			{
   253 				iterator old(*this);
   254 				_Inc();
   255 				return old;
   256 			}
   257 			const THashNode & operator * () const
   258 			{
   259 				return *(*iter);
   260 			}
   261 			THashNode & operator * ()
   262 			{
   263 				return *(*iter);
   264 			}
   265 			const THashNode * operator ->() const
   266 			{
   267 				return (*iter);
   268 			}
   269 			THashNode * operator ->()
   270 			{
   271 				return (*iter);
   272 			}
   273 			bool operator ==(const iterator &where) const
   274 			{
   275 				if (where.hash == this->hash
   276 					&& where.end == this->end
   277 					&&
   278 					 (this->end ||
   279 					   ((where.curbucket == this->curbucket)
   280 						&& (where.iter == iter))
   281 						 ))
   282 					return true;
   283 				return false;
   284 			}
   285 			bool operator !=(const iterator &where) const
   286 			{
   287 				return !( (*this) == where );
   288 			}
   289 
   290 			void erase()
   291 			{
   292 				if (end || !hash || curbucket < 0 || curbucket >= static_cast<int>(hash->m_numBuckets))
   293 					return;
   294 
   295 				// Remove this element and move to the next one
   296 				iterator tmp = *this;
   297 				++tmp;
   298 				delete (*iter);
   299 				hash->m_Buckets[curbucket]->erase(iter);
   300 				*this = tmp;
   301 
   302 				// :TODO: Maybe refactor to a lower size if required
   303 			}
   304 		private:
   305 			void _Inc()
   306 			{
   307 				if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
   308 					return;
   309 				if (curbucket < 0)
   310 				{
   311 					for (int i=0; i<(int)hash->m_numBuckets; i++)
   312 					{
   313 						if (hash->m_Buckets[i])
   314 						{
   315 							iter = hash->m_Buckets[i]->begin();
   316 							if (iter == hash->m_Buckets[i]->end())
   317 								continue;
   318 							curbucket = i;
   319 							break;
   320 						}
   321 					}
   322 					if (curbucket < 0)
   323 						end = true;
   324 				} else {
   325 					if (iter != hash->m_Buckets[curbucket]->end())
   326 						iter++;
   327 					if (iter == hash->m_Buckets[curbucket]->end())
   328 					{
   329 						int oldbucket = curbucket;
   330 						for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
   331 						{
   332 							if (hash->m_Buckets[i])
   333 							{
   334 								iter = hash->m_Buckets[i]->begin();
   335 								if (iter == hash->m_Buckets[i]->end())
   336 									continue;
   337 								curbucket = i;
   338 								break;
   339 							}
   340 						}
   341 						if (curbucket == oldbucket)
   342 							end = true;
   343 					}
   344 				}
   345 			}
   346 		private:
   347 			int curbucket;
   348 			typename SourceHook::List<THashNode *>::iterator iter;
   349 			THash *hash;
   350 			bool end;
   351 		};
   352 		class const_iterator
   353 		{
   354 			friend class THash;
   355 		public:
   356 			const_iterator() : curbucket(-1), hash(NULL), end(true)
   357 			{
   358 			};
   359 			const_iterator(const THash *h) : curbucket(-1), hash(h), end(false)
   360 			{
   361 				if (!h->m_Buckets)
   362 					end = true;
   363 				else
   364 					_Inc();
   365 			};
   366 			//pre increment
   367 			const_iterator & operator++()
   368 			{
   369 				_Inc();
   370 				return *this;
   371 			}
   372 			//post increment
   373 			const_iterator operator++(int)
   374 			{
   375 				iterator old(*this);
   376 				_Inc();
   377 				return old;
   378 			}
   379 			const THashNode & operator * () const
   380 			{
   381 				return *(*iter);
   382 			}
   383 			const THashNode * operator ->() const
   384 			{
   385 				return (*iter);
   386 			}
   387 			bool operator ==(const const_iterator &where) const
   388 			{
   389 				if (where.hash == this->hash
   390 					&& where.end == this->end
   391 					&&
   392 					 (this->end ||
   393 					   ((where.curbucket == this->curbucket)
   394 						&& (where.iter == iter))
   395 						 ))
   396 					return true;
   397 				return false;
   398 			}
   399 			bool operator !=(const const_iterator &where) const
   400 			{
   401 				return !( (*this) == where );
   402 			}
   403 		private:
   404 			void _Inc()
   405 			{
   406 				if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
   407 					return;
   408 				if (curbucket < 0)
   409 				{
   410 					for (int i=0; i<(int)hash->m_numBuckets; i++)
   411 					{
   412 						if (hash->m_Buckets[i])
   413 						{
   414 							iter = hash->m_Buckets[i]->begin();
   415 							if (iter == hash->m_Buckets[i]->end())
   416 								continue;
   417 							curbucket = i;
   418 							break;
   419 						}
   420 					}
   421 					if (curbucket < 0)
   422 						end = true;
   423 				} else {
   424 					if (iter != hash->m_Buckets[curbucket]->end())
   425 						iter++;
   426 					if (iter == hash->m_Buckets[curbucket]->end())
   427 					{
   428 						int oldbucket = curbucket;
   429 						for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
   430 						{
   431 							if (hash->m_Buckets[i])
   432 							{
   433 								iter = hash->m_Buckets[i]->begin();
   434 								if (iter == hash->m_Buckets[i]->end())
   435 									continue;
   436 								curbucket = i;
   437 								break;
   438 							}
   439 						}
   440 						if (curbucket == oldbucket)
   441 							end = true;
   442 					}
   443 				}
   444 			}
   445 		private:
   446 			int curbucket;
   447 			typename SourceHook::List<THashNode *>::iterator iter;
   448 			const THash *hash;
   449 			bool end;
   450 		};
   451 	public:
   452 		iterator begin()
   453 		{
   454 			return iterator(this);
   455 		}
   456 		iterator end()
   457 		{
   458 			iterator iter;
   459 			iter.hash = this;
   460 			return iter;
   461 		}
   462 
   463 		const_iterator begin() const
   464 		{
   465 			return const_iterator(this);
   466 		}
   467 		const_iterator end() const
   468 		{
   469 			const_iterator iter;
   470 			iter.hash = this;
   471 			return iter;
   472 		}
   473 
   474 		template <typename U>
   475 		iterator find(const U & u) const
   476 		{
   477 			iterator b = begin();
   478 			iterator e = end();
   479 			for (iterator iter = b; iter != e; iter++)
   480 			{
   481 				if ( (*iter).key == u )
   482 					return iter;
   483 			}
   484 			return end();
   485 		}
   486 		template <typename U>
   487 		iterator find(const U & u)
   488 		{
   489 			iterator b = begin();
   490 			iterator e = end();
   491 			for (iterator iter = b; iter != e; iter++)
   492 			{
   493 				if ( (*iter).key == u )
   494 					return iter;
   495 			}
   496 			return end();
   497 		}
   498 		template <typename U>
   499 		iterator FindAlt(const U & u)
   500 		{
   501 			iterator b = begin();
   502 			iterator e = end();
   503 			for (iterator iter = b; iter != e; iter++)
   504 			{
   505 				if (CompareAlt(u, (*iter).key) == 0)
   506 				{
   507 					return iter;
   508 				}
   509 			}
   510 			return e;
   511 		}
   512 		iterator erase(iterator where)
   513 		{
   514 			where.erase();
   515 			return where;
   516 		}
   517 		template <typename U>
   518 		void erase(const U & u)
   519 		{
   520 			iterator iter = find(u);
   521 			if (iter == end())
   522 				return;
   523 			iter.erase();
   524 		}
   525 	friend class iterator;
   526 	friend class const_iterator;
   527 	private:
   528 		NodePtr	*m_Buckets;
   529 		size_t m_numBuckets;
   530 		float m_percentUsed;
   531 	};
   532 };
   533 
   534 #endif //_INCLUDE_SH_TINYHASH_H_