sourcehook/sh_tinyhash.h
author Pavol Marko <pavolmarko@gmail.com>
Fri Nov 09 21:14:37 2007 +0000 (2007-11-09)
branchhookman_autogen
changeset 452 2efe13dab607
parent 430 e735f6701dcf
child 523 6f1630519b81
permissions -rw-r--r--
- Removed unnecessary definitions from sh_pagealloc.h
- Added CallConv_StdCall
- Added CallConv_HasVarArgs and CallConv_HasVafmt
     1 /* ======== SourceMM ========
     2 * Copyright (C) 2004-2007 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_