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