sourcehook/sh_tinyhash.h
author Scott Ehlert <ds@alliedmods.net>
Sun Aug 13 11:34:30 2006 +0000 (2006-08-13)
changeset 238 c27105949293
parent 159 98049e816758
child 264 188e8220fdc3
permissions -rw-r--r--
Wow, lots of stuff here
1) Bumped version to 1.3
2) Fixed MSVC project files to compile and link against latest SDK
3) Fixed Linux compilation of stub_mm and sample_mm against new SDK (added -msse to makefiles)
4) Removed -fpermissive and -Wno-deprecated from Linux makefiles
5) Added -Wall -Wno-non-virtual-dtor -Werror to Linux makefiles
6) Stub_mm and sample_mm no longer dynamically link to libstdc++
7) SourceMM, stub_mm, and sample_mm compile cleanly (no warnings) with GCC 3.4.x and 4.x
     1 /* ======== SourceMM ========
     2 * Copyright (C) 2004-2005 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 K>
    24 	int Compare(const K & k1, const K & k2);
    25 
    26 	/**
    27 	 * This is a tiny, growable hash class.
    28 	 * Meant for quick and dirty dictionaries only!
    29 	 */
    30 	template <class K, class V>
    31 	class THash
    32 	{
    33 	public:
    34 		struct THashNode
    35 		{
    36 			THashNode(const K & k, const V & v) :
    37 				key(k), val(v)
    38 				{
    39 				};
    40 			THashNode & operator =(const THashNode &other)
    41 			{
    42 				key = other.key;
    43 				val = other.val;
    44 			}
    45 			K key;
    46 			V val;
    47 		};
    48 		typedef List<THashNode *> *	NodePtr;
    49 	public:
    50 		class const_iterator;
    51 		THash() : m_Buckets(NULL), m_numBuckets(0), m_percentUsed(0.0f)
    52 		{
    53 			_Refactor();
    54 		}
    55 		THash(const THash &other) : m_Buckets(new NodePtr[other.m_numBuckets]),
    56 			m_numBuckets(other.m_numBuckets), m_percentUsed(other.m_percentUsed)
    57 		{
    58 			for (size_t i=0; i<m_numBuckets; i++)
    59 					m_Buckets[i] = NULL;
    60 			for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
    61 				_FindOrInsert(iter->key)->val = iter->val;
    62 		}
    63 		void operator=(const THash &other)
    64 		{
    65 			clear();
    66 			for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
    67 				_FindOrInsert(iter->key)->val = iter->val;
    68 		}
    69 
    70 		~THash()
    71 		{
    72 			_Clear();
    73 		}
    74 		void clear()
    75 		{
    76 			_Clear();
    77 			_Refactor();
    78 		}
    79 		size_t GetBuckets()
    80 		{
    81 			return m_numBuckets;
    82 		}
    83 		float PercentUsed()
    84 		{
    85 			return m_percentUsed;
    86 		}
    87 		V & operator [](const K & key)
    88 		{
    89 			THashNode *pNode = _FindOrInsert(key);
    90 			return pNode->val;
    91 		}
    92 	private:
    93 		void _Clear()
    94 		{
    95 			typename List<THashNode *>::iterator iter, end;
    96 			for (size_t i=0; i<m_numBuckets; i++)
    97 			{
    98 				if (m_Buckets[i])
    99 				{
   100 					end = m_Buckets[i]->end();
   101 					iter = m_Buckets[i]->begin();
   102 					while (iter != end)
   103 					{
   104 						delete (*iter);
   105 						iter++;
   106 					}
   107 					delete m_Buckets[i];
   108 					m_Buckets[i] = NULL;
   109 				}
   110 			}
   111 			if (m_Buckets)
   112 				delete [] m_Buckets;
   113 			m_Buckets = NULL;
   114 			m_numBuckets = 0;
   115 		}
   116 		THashNode *_FindOrInsert(const K & key)
   117 		{
   118 			size_t place = HashFunction(key) % m_numBuckets;
   119 			THashNode *pNode = NULL;
   120 			if (!m_Buckets[place])
   121 			{
   122 				m_Buckets[place] = new List<THashNode *>;
   123 				pNode = new THashNode(key, V());
   124 				m_Buckets[place]->push_back(pNode);
   125 				m_percentUsed += (1.0f / (float)m_numBuckets);
   126 			} else {
   127 				typename List<THashNode *>::iterator iter;
   128 				for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++)
   129 				{
   130 					if (Compare((*iter)->key, key) == 0)
   131 						return (*iter);
   132 				}
   133 				//node does not exist
   134 				pNode = new THashNode(key, V());
   135 				m_Buckets[place]->push_back(pNode);
   136 			}
   137 			if (PercentUsed() > 0.75f)
   138 				_Refactor();
   139 			return pNode;
   140 		}
   141 		void _Refactor()
   142 		{
   143 			m_percentUsed = 0.0f;
   144 			if (!m_numBuckets)
   145 			{
   146 				m_numBuckets = _T_INIT_HASH_SIZE;
   147 				m_Buckets = new NodePtr[m_numBuckets];
   148 				for (size_t i=0; i<m_numBuckets; i++)
   149 					m_Buckets[i] = NULL;
   150 			} else {
   151 				size_t oldSize = m_numBuckets;
   152 				m_numBuckets *= 2;
   153 				typename List<THashNode *>::iterator iter;
   154 				size_t place;
   155 				THashNode *pHashNode;
   156 				NodePtr *temp = new NodePtr[m_numBuckets];
   157 				for (size_t i=0; i<m_numBuckets; i++)
   158 					temp[i] = NULL;
   159 				//look in old hash table
   160 				for (size_t i=0; i<oldSize; i++)
   161 				{
   162 					//does a bucket have anything?
   163 					if (m_Buckets[i])
   164 					{
   165 						//go through the list of items
   166 						for (iter = m_Buckets[i]->begin(); iter != m_Buckets[i]->end(); iter++)
   167 						{
   168 							pHashNode = (*iter);
   169 							//rehash it with the new bucket filter
   170 							place = HashFunction(pHashNode->key) % m_numBuckets;
   171 							//add it to the new hash table
   172 							if (!temp[place])
   173 							{
   174 								temp[place] = new List<THashNode *>;
   175 								m_percentUsed += (1.0f / (float)m_numBuckets);
   176 							}
   177 							temp[place]->push_back(pHashNode);
   178 						}
   179 						//delete that bucket!
   180 						delete m_Buckets[i];
   181 						m_Buckets[i] = NULL;
   182 					}
   183 				}
   184 				//reassign bucket table
   185 				delete [] m_Buckets;
   186 				m_Buckets = temp;
   187 			}
   188 		}
   189 	public:
   190 		friend class iterator;
   191 		friend class const_iterator;
   192 		class iterator
   193 		{
   194 			friend class THash;
   195 		public:
   196 			iterator() : curbucket(-1), hash(NULL), end(true)
   197 			{
   198 			};
   199 			iterator(THash *h) : curbucket(-1), hash(h), end(false)
   200 			{
   201 				if (!h->m_Buckets)
   202 					end = true;
   203 				else
   204 					_Inc();
   205 			};
   206 			//pre increment
   207 			iterator & operator++()
   208 			{
   209 				_Inc();
   210 				return *this;
   211 			}
   212 			//post increment
   213 			iterator operator++(int)
   214 			{
   215 				iterator old(*this);
   216 				_Inc();
   217 				return old;
   218 			}
   219 			const THashNode & operator * () const
   220 			{
   221 				return *(*iter);
   222 			}
   223 			THashNode & operator * ()
   224 			{
   225 				return *(*iter);
   226 			}
   227 			const THashNode * operator ->() const
   228 			{
   229 				return (*iter);
   230 			}
   231 			THashNode * operator ->()
   232 			{
   233 				return (*iter);
   234 			}
   235 			bool operator ==(const iterator &where) const
   236 			{
   237 				if (where.hash == this->hash
   238 					&& where.end == this->end
   239 					&&
   240 					 (this->end ||
   241 					   ((where.curbucket == this->curbucket)
   242 						&& (where.iter == iter))
   243 						 ))
   244 					return true;
   245 				return false;
   246 			}
   247 			bool operator !=(const iterator &where) const
   248 			{
   249 				return !( (*this) == where );
   250 			}
   251 
   252 			void erase()
   253 			{
   254 				if (end || !hash || curbucket < 0 || curbucket >= static_cast<int>(hash->m_numBuckets))
   255 					return;
   256 
   257 				// Remove this element and move to the next one
   258 				iterator tmp = *this;
   259 				++tmp;
   260 				delete (*iter);
   261 				hash->m_Buckets[curbucket]->erase(iter);
   262 				*this = tmp;
   263 
   264 				// :TODO: Maybe refactor to a lower size if required
   265 			}
   266 		private:
   267 			void _Inc()
   268 			{
   269 				if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
   270 					return;
   271 				if (curbucket < 0)
   272 				{
   273 					for (int i=0; i<(int)hash->m_numBuckets; i++)
   274 					{
   275 						if (hash->m_Buckets[i])
   276 						{
   277 							iter = hash->m_Buckets[i]->begin();
   278 							if (iter == hash->m_Buckets[i]->end())
   279 								continue;
   280 							curbucket = i;
   281 							break;
   282 						}
   283 					}
   284 					if (curbucket < 0)
   285 						end = true;
   286 				} else {
   287 					if (iter != hash->m_Buckets[curbucket]->end())
   288 						iter++;
   289 					if (iter == hash->m_Buckets[curbucket]->end())
   290 					{
   291 						int oldbucket = curbucket;
   292 						for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
   293 						{
   294 							if (hash->m_Buckets[i])
   295 							{
   296 								iter = hash->m_Buckets[i]->begin();
   297 								if (iter == hash->m_Buckets[i]->end())
   298 									continue;
   299 								curbucket = i;
   300 								break;
   301 							}
   302 						}
   303 						if (curbucket == oldbucket)
   304 							end = true;
   305 					}
   306 				}
   307 			}
   308 		private:
   309 			int curbucket;
   310 			typename SourceHook::List<THashNode *>::iterator iter;
   311 			THash *hash;
   312 			bool end;
   313 		};
   314 		class const_iterator
   315 		{
   316 			friend class THash;
   317 		public:
   318 			const_iterator() : curbucket(-1), hash(NULL), end(true)
   319 			{
   320 			};
   321 			const_iterator(const THash *h) : curbucket(-1), hash(h), end(false)
   322 			{
   323 				if (!h->m_Buckets)
   324 					end = true;
   325 				else
   326 					_Inc();
   327 			};
   328 			//pre increment
   329 			const_iterator & operator++()
   330 			{
   331 				_Inc();
   332 				return *this;
   333 			}
   334 			//post increment
   335 			const_iterator operator++(int)
   336 			{
   337 				iterator old(*this);
   338 				_Inc();
   339 				return old;
   340 			}
   341 			const THashNode & operator * () const
   342 			{
   343 				return *(*iter);
   344 			}
   345 			const THashNode * operator ->() const
   346 			{
   347 				return (*iter);
   348 			}
   349 			bool operator ==(const const_iterator &where) const
   350 			{
   351 				if (where.hash == this->hash
   352 					&& where.end == this->end
   353 					&&
   354 					 (this->end ||
   355 					   ((where.curbucket == this->curbucket)
   356 						&& (where.iter == iter))
   357 						 ))
   358 					return true;
   359 				return false;
   360 			}
   361 			bool operator !=(const const_iterator &where) const
   362 			{
   363 				return !( (*this) == where );
   364 			}
   365 		private:
   366 			void _Inc()
   367 			{
   368 				if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
   369 					return;
   370 				if (curbucket < 0)
   371 				{
   372 					for (int i=0; i<(int)hash->m_numBuckets; i++)
   373 					{
   374 						if (hash->m_Buckets[i])
   375 						{
   376 							iter = hash->m_Buckets[i]->begin();
   377 							if (iter == hash->m_Buckets[i]->end())
   378 								continue;
   379 							curbucket = i;
   380 							break;
   381 						}
   382 					}
   383 					if (curbucket < 0)
   384 						end = true;
   385 				} else {
   386 					if (iter != hash->m_Buckets[curbucket]->end())
   387 						iter++;
   388 					if (iter == hash->m_Buckets[curbucket]->end())
   389 					{
   390 						int oldbucket = curbucket;
   391 						for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
   392 						{
   393 							if (hash->m_Buckets[i])
   394 							{
   395 								iter = hash->m_Buckets[i]->begin();
   396 								if (iter == hash->m_Buckets[i]->end())
   397 									continue;
   398 								curbucket = i;
   399 								break;
   400 							}
   401 						}
   402 						if (curbucket == oldbucket)
   403 							end = true;
   404 					}
   405 				}
   406 			}
   407 		private:
   408 			int curbucket;
   409 			typename SourceHook::List<THashNode *>::iterator iter;
   410 			const THash *hash;
   411 			bool end;
   412 		};
   413 	public:
   414 		iterator begin()
   415 		{
   416 			return iterator(this);
   417 		}
   418 		iterator end()
   419 		{
   420 			iterator iter;
   421 			iter.hash = this;
   422 			return iter;
   423 		}
   424 
   425 		const_iterator begin() const
   426 		{
   427 			return const_iterator(this);
   428 		}
   429 		const_iterator end() const
   430 		{
   431 			const_iterator iter;
   432 			iter.hash = this;
   433 			return iter;
   434 		}
   435 
   436 		template <typename U>
   437 		iterator find(const U & u) const
   438 		{
   439 			iterator b = begin();
   440 			iterator e = end();
   441 			for (iterator iter = b; iter != e; iter++)
   442 			{
   443 				if ( (*iter).key == u )
   444 					return iter;
   445 			}
   446 			return end();
   447 		}
   448 		template <typename U>
   449 		iterator find(const U & u)
   450 		{
   451 			iterator b = begin();
   452 			iterator e = end();
   453 			for (iterator iter = b; iter != e; iter++)
   454 			{
   455 				if ( (*iter).key == u )
   456 					return iter;
   457 			}
   458 			return end();
   459 		}
   460 
   461 		iterator erase(iterator where)
   462 		{
   463 			where.erase();
   464 			return where;
   465 		}
   466 		template <typename U>
   467 		void erase(const U & u)
   468 		{
   469 			iterator iter = find(u);
   470 			if (iter == end())
   471 				return;
   472 			iter.erase();
   473 		}
   474 	private:
   475 		NodePtr	*m_Buckets;
   476 		size_t m_numBuckets;
   477 		float m_percentUsed;
   478 	};
   479 };
   480 
   481 #endif //_INCLUDE_SH_TINYHASH_H_