sourcehook/sh_tinyhash.h
author Pavol Marko <pavolmarko@gmail.com>
Sat May 12 08:57:10 2007 +0000 (2007-05-12)
changeset 329 63bb4ae624f1
parent 294 0d87bc8606f8
child 430 e735f6701dcf
permissions -rw-r--r--
Why did MSVC not complain about this?
     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 		friend class iterator;
   231 		friend class const_iterator;
   232 		class iterator
   233 		{
   234 			friend class THash;
   235 		public:
   236 			iterator() : curbucket(-1), hash(NULL), end(true)
   237 			{
   238 			};
   239 			iterator(THash *h) : curbucket(-1), hash(h), end(false)
   240 			{
   241 				if (!h->m_Buckets)
   242 					end = true;
   243 				else
   244 					_Inc();
   245 			};
   246 			//pre increment
   247 			iterator & operator++()
   248 			{
   249 				_Inc();
   250 				return *this;
   251 			}
   252 			//post increment
   253 			iterator operator++(int)
   254 			{
   255 				iterator old(*this);
   256 				_Inc();
   257 				return old;
   258 			}
   259 			const THashNode & operator * () const
   260 			{
   261 				return *(*iter);
   262 			}
   263 			THashNode & operator * ()
   264 			{
   265 				return *(*iter);
   266 			}
   267 			const THashNode * operator ->() const
   268 			{
   269 				return (*iter);
   270 			}
   271 			THashNode * operator ->()
   272 			{
   273 				return (*iter);
   274 			}
   275 			bool operator ==(const iterator &where) const
   276 			{
   277 				if (where.hash == this->hash
   278 					&& where.end == this->end
   279 					&&
   280 					 (this->end ||
   281 					   ((where.curbucket == this->curbucket)
   282 						&& (where.iter == iter))
   283 						 ))
   284 					return true;
   285 				return false;
   286 			}
   287 			bool operator !=(const iterator &where) const
   288 			{
   289 				return !( (*this) == where );
   290 			}
   291 
   292 			void erase()
   293 			{
   294 				if (end || !hash || curbucket < 0 || curbucket >= static_cast<int>(hash->m_numBuckets))
   295 					return;
   296 
   297 				// Remove this element and move to the next one
   298 				iterator tmp = *this;
   299 				++tmp;
   300 				delete (*iter);
   301 				hash->m_Buckets[curbucket]->erase(iter);
   302 				*this = tmp;
   303 
   304 				// :TODO: Maybe refactor to a lower size if required
   305 			}
   306 		private:
   307 			void _Inc()
   308 			{
   309 				if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
   310 					return;
   311 				if (curbucket < 0)
   312 				{
   313 					for (int i=0; i<(int)hash->m_numBuckets; i++)
   314 					{
   315 						if (hash->m_Buckets[i])
   316 						{
   317 							iter = hash->m_Buckets[i]->begin();
   318 							if (iter == hash->m_Buckets[i]->end())
   319 								continue;
   320 							curbucket = i;
   321 							break;
   322 						}
   323 					}
   324 					if (curbucket < 0)
   325 						end = true;
   326 				} else {
   327 					if (iter != hash->m_Buckets[curbucket]->end())
   328 						iter++;
   329 					if (iter == hash->m_Buckets[curbucket]->end())
   330 					{
   331 						int oldbucket = curbucket;
   332 						for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
   333 						{
   334 							if (hash->m_Buckets[i])
   335 							{
   336 								iter = hash->m_Buckets[i]->begin();
   337 								if (iter == hash->m_Buckets[i]->end())
   338 									continue;
   339 								curbucket = i;
   340 								break;
   341 							}
   342 						}
   343 						if (curbucket == oldbucket)
   344 							end = true;
   345 					}
   346 				}
   347 			}
   348 		private:
   349 			int curbucket;
   350 			typename SourceHook::List<THashNode *>::iterator iter;
   351 			THash *hash;
   352 			bool end;
   353 		};
   354 		class const_iterator
   355 		{
   356 			friend class THash;
   357 		public:
   358 			const_iterator() : curbucket(-1), hash(NULL), end(true)
   359 			{
   360 			};
   361 			const_iterator(const THash *h) : curbucket(-1), hash(h), end(false)
   362 			{
   363 				if (!h->m_Buckets)
   364 					end = true;
   365 				else
   366 					_Inc();
   367 			};
   368 			//pre increment
   369 			const_iterator & operator++()
   370 			{
   371 				_Inc();
   372 				return *this;
   373 			}
   374 			//post increment
   375 			const_iterator operator++(int)
   376 			{
   377 				iterator old(*this);
   378 				_Inc();
   379 				return old;
   380 			}
   381 			const THashNode & operator * () const
   382 			{
   383 				return *(*iter);
   384 			}
   385 			const THashNode * operator ->() const
   386 			{
   387 				return (*iter);
   388 			}
   389 			bool operator ==(const const_iterator &where) const
   390 			{
   391 				if (where.hash == this->hash
   392 					&& where.end == this->end
   393 					&&
   394 					 (this->end ||
   395 					   ((where.curbucket == this->curbucket)
   396 						&& (where.iter == iter))
   397 						 ))
   398 					return true;
   399 				return false;
   400 			}
   401 			bool operator !=(const const_iterator &where) const
   402 			{
   403 				return !( (*this) == where );
   404 			}
   405 		private:
   406 			void _Inc()
   407 			{
   408 				if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
   409 					return;
   410 				if (curbucket < 0)
   411 				{
   412 					for (int i=0; i<(int)hash->m_numBuckets; i++)
   413 					{
   414 						if (hash->m_Buckets[i])
   415 						{
   416 							iter = hash->m_Buckets[i]->begin();
   417 							if (iter == hash->m_Buckets[i]->end())
   418 								continue;
   419 							curbucket = i;
   420 							break;
   421 						}
   422 					}
   423 					if (curbucket < 0)
   424 						end = true;
   425 				} else {
   426 					if (iter != hash->m_Buckets[curbucket]->end())
   427 						iter++;
   428 					if (iter == hash->m_Buckets[curbucket]->end())
   429 					{
   430 						int oldbucket = curbucket;
   431 						for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
   432 						{
   433 							if (hash->m_Buckets[i])
   434 							{
   435 								iter = hash->m_Buckets[i]->begin();
   436 								if (iter == hash->m_Buckets[i]->end())
   437 									continue;
   438 								curbucket = i;
   439 								break;
   440 							}
   441 						}
   442 						if (curbucket == oldbucket)
   443 							end = true;
   444 					}
   445 				}
   446 			}
   447 		private:
   448 			int curbucket;
   449 			typename SourceHook::List<THashNode *>::iterator iter;
   450 			const THash *hash;
   451 			bool end;
   452 		};
   453 	public:
   454 		iterator begin()
   455 		{
   456 			return iterator(this);
   457 		}
   458 		iterator end()
   459 		{
   460 			iterator iter;
   461 			iter.hash = this;
   462 			return iter;
   463 		}
   464 
   465 		const_iterator begin() const
   466 		{
   467 			return const_iterator(this);
   468 		}
   469 		const_iterator end() const
   470 		{
   471 			const_iterator iter;
   472 			iter.hash = this;
   473 			return iter;
   474 		}
   475 
   476 		template <typename U>
   477 		iterator find(const U & u) const
   478 		{
   479 			iterator b = begin();
   480 			iterator e = end();
   481 			for (iterator iter = b; iter != e; iter++)
   482 			{
   483 				if ( (*iter).key == u )
   484 					return iter;
   485 			}
   486 			return end();
   487 		}
   488 		template <typename U>
   489 		iterator find(const U & u)
   490 		{
   491 			iterator b = begin();
   492 			iterator e = end();
   493 			for (iterator iter = b; iter != e; iter++)
   494 			{
   495 				if ( (*iter).key == u )
   496 					return iter;
   497 			}
   498 			return end();
   499 		}
   500 		template <typename U>
   501 		iterator FindAlt(const U & u)
   502 		{
   503 			iterator b = begin();
   504 			iterator e = end();
   505 			for (iterator iter = b; iter != e; iter++)
   506 			{
   507 				if (CompareAlt(u, (*iter).key) == 0)
   508 				{
   509 					return iter;
   510 				}
   511 			}
   512 			return e;
   513 		}
   514 		iterator erase(iterator where)
   515 		{
   516 			where.erase();
   517 			return where;
   518 		}
   519 		template <typename U>
   520 		void erase(const U & u)
   521 		{
   522 			iterator iter = find(u);
   523 			if (iter == end())
   524 				return;
   525 			iter.erase();
   526 		}
   527 	private:
   528 		NodePtr	*m_Buckets;
   529 		size_t m_numBuckets;
   530 		float m_percentUsed;
   531 	};
   532 };
   533 
   534 #endif //_INCLUDE_SH_TINYHASH_H_