sourcehook/sh_tinyhash.h
author Pavol Marko <pavolmarko@gmail.com>
Fri Sep 23 20:14:10 2005 +0000 (2005-09-23)
changeset 111 aec58c99dafc
parent 110 77e7acc57f67
child 115 6d0d182ef25c
permissions -rw-r--r--
SourceHook tests pass again! Added test for list (and a small bit of tinyhash). Woot.
     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 			if (m_Buckets)
    67 				delete [] m_Buckets;
    68 		}
    69 		void clear()
    70 		{
    71 			if (m_Buckets)
    72 				delete [] m_Buckets;
    73 			m_Buckets = NULL;
    74 			m_numBuckets = 0;
    75 			m_percentUsed = 0.0f;
    76 			
    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 		THashNode *_FindOrInsert(const K & key)
    94 		{
    95 			size_t place = HashFunction(key) % m_numBuckets;
    96 			THashNode *pNode = NULL;
    97 			if (!m_Buckets[place])
    98 			{
    99 				m_Buckets[place] = new List<THashNode *>;
   100 				pNode = new THashNode(key, V());
   101 				m_Buckets[place]->push_back(pNode);
   102 				m_percentUsed += (1.0f / (float)m_numBuckets);
   103 			} else {
   104 				typename List<THashNode *>::iterator iter;
   105 				for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++)
   106 				{
   107 					if (Compare((*iter)->key, key) == 0)
   108 						return (*iter);
   109 				}
   110 				//node does not exist
   111 				pNode = new THashNode(key, V());
   112 				m_Buckets[place]->push_back(pNode);
   113 			}
   114 			if (PercentUsed() > 0.75f)
   115 				_Refactor();
   116 			return pNode;
   117 		}
   118 		void _Refactor()
   119 		{
   120 			m_percentUsed = 0.0f;
   121 			if (!m_numBuckets)
   122 			{
   123 				m_numBuckets = _T_INIT_HASH_SIZE;
   124 				m_Buckets = new NodePtr[m_numBuckets];
   125 				for (size_t i=0; i<m_numBuckets; i++)
   126 					m_Buckets[i] = NULL;
   127 			} else {
   128 				size_t oldSize = m_numBuckets;
   129 				m_numBuckets *= 2;
   130 				typename List<THashNode *>::iterator iter;
   131 				size_t place;
   132 				THashNode *pHashNode;
   133                 NodePtr *temp = new NodePtr[m_numBuckets];
   134 				for (size_t i=0; i<m_numBuckets; i++)
   135 					temp[i] = NULL;
   136 				//look in old hash table
   137 				for (size_t i=0; i<oldSize; i++)
   138 				{
   139 					//does a bucket have anything?
   140 					if (m_Buckets[i])
   141 					{
   142 						//go through the list of items
   143 						for (iter = m_Buckets[i]->begin(); iter != m_Buckets[i]->end(); iter++)
   144 						{
   145 							pHashNode = (*iter);
   146 							//rehash it with the new bucket filter
   147 							place = HashFunction(pHashNode->key) % m_numBuckets;
   148 							//add it to the new hash table
   149 							if (!temp[place])
   150 							{
   151 								temp[place] = new List<THashNode *>;
   152 								m_percentUsed += (1.0f / (float)m_numBuckets);
   153 							}
   154 							temp[place]->push_back(pHashNode);
   155 						}
   156 						//delete that bucket!
   157 						delete m_Buckets[i];
   158 						m_Buckets[i] = NULL;
   159 					}
   160 				}
   161 				//reassign bucket table
   162 				delete [] m_Buckets;
   163 				m_Buckets = temp;
   164 			}
   165 		}
   166 	public:
   167 		friend class iterator;
   168 		friend class const_iterator;
   169 		class iterator
   170 		{
   171 			friend class THash;
   172 		public:
   173 			iterator() : curbucket(-1), hash(NULL), end(true)
   174 			{
   175 			};
   176 			iterator(THash *h) : curbucket(-1), hash(h), end(false)
   177 			{
   178 				if (!h->m_Buckets)
   179 					end = true;
   180 				else
   181 					_Inc();
   182 			};
   183 			//pre increment
   184 			iterator & operator++()
   185 			{
   186 				_Inc();
   187 				return *this;
   188 			}
   189 			//post increment
   190 			iterator operator++(int)
   191 			{
   192 				iterator old(*this);
   193 				_Inc();
   194 				return old;
   195 			}
   196 			const THashNode & operator * () const
   197 			{
   198 				return *(*iter);
   199 			}
   200 			THashNode & operator * ()
   201 			{
   202 				return *(*iter);
   203 			}
   204 			const THashNode * operator ->() const
   205 			{
   206 				return (*iter);
   207 			}
   208 			THashNode * operator ->()
   209 			{
   210 				return (*iter);
   211 			}
   212 			bool operator ==(const iterator &where) const
   213 			{
   214 				if (where.hash == this->hash
   215 					&& where.end == this->end
   216 					&& 
   217 					 (this->end || 
   218 					   ((where.curbucket == this->curbucket) 
   219 					     && (where.iter == iter))
   220 						 ))
   221 					return true;
   222 				return false;
   223 			}
   224 			bool operator !=(const iterator &where) const
   225 			{
   226 				return !( (*this) == where );
   227 			}
   228 		private:
   229 			void _Inc()
   230 			{
   231 				if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
   232 					return;
   233 				if (curbucket < 0)
   234 				{
   235 					for (int i=0; i<(int)hash->m_numBuckets; i++)
   236 					{
   237 						if (hash->m_Buckets[i])
   238 						{
   239 							iter = hash->m_Buckets[i]->begin();
   240 							if (iter == hash->m_Buckets[i]->end())
   241 								continue;
   242 							curbucket = i;
   243 							break;
   244 						}
   245 					}
   246 					if (curbucket < 0)
   247 						end = true;
   248 				} else {
   249 					if (iter != hash->m_Buckets[curbucket]->end())
   250 						iter++;
   251 					if (iter == hash->m_Buckets[curbucket]->end())
   252 					{
   253 						int oldbucket = curbucket;
   254 						for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
   255 						{
   256 							if (hash->m_Buckets[i])
   257 							{
   258 								iter = hash->m_Buckets[i]->begin();
   259 								if (iter == hash->m_Buckets[i]->end())
   260 									continue;
   261 								curbucket = i;
   262 								break;
   263 							}
   264 						}
   265 						if (curbucket == oldbucket)
   266 							end = true;
   267 					}
   268 				}
   269 			}
   270 		private:
   271 			int curbucket;
   272 			typename SourceHook::List<THashNode *>::iterator iter;
   273 			THash *hash;
   274 			bool end;
   275 		};
   276 		class const_iterator
   277 		{
   278 			friend class THash;
   279 		public:
   280 			const_iterator() : curbucket(-1), hash(NULL), end(true)
   281 			{
   282 			};
   283 			const_iterator(const THash *h) : curbucket(-1), hash(h), end(false)
   284 			{
   285 				if (!h->m_Buckets)
   286 					end = true;
   287 				else
   288 					_Inc();
   289 			};
   290 			//pre increment
   291 			const_iterator & operator++()
   292 			{
   293 				_Inc();
   294 				return *this;
   295 			}
   296 			//post increment
   297 			const_iterator operator++(int)
   298 			{
   299 				iterator old(*this);
   300 				_Inc();
   301 				return old;
   302 			}
   303 			const THashNode & operator * () const
   304 			{
   305 				return *(*iter);
   306 			}
   307 			const THashNode * operator ->() const
   308 			{
   309 				return (*iter);
   310 			}
   311 			bool operator ==(const const_iterator &where) const
   312 			{
   313 				if (where.hash == this->hash
   314 					&& where.end == this->end
   315 					&& 
   316 					 (this->end || 
   317 					   ((where.curbucket == this->curbucket) 
   318 					     && (where.iter == iter))
   319 						 ))
   320 					return true;
   321 				return false;
   322 			}
   323 			bool operator !=(const const_iterator &where) const
   324 			{
   325 				return !( (*this) == where );
   326 			}
   327 		private:
   328 			void _Inc()
   329 			{
   330 				if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
   331 					return;
   332 				if (curbucket < 0)
   333 				{
   334 					for (int i=0; i<(int)hash->m_numBuckets; i++)
   335 					{
   336 						if (hash->m_Buckets[i])
   337 						{
   338 							iter = hash->m_Buckets[i]->begin();
   339 							if (iter == hash->m_Buckets[i]->end())
   340 								continue;
   341 							curbucket = i;
   342 							break;
   343 						}
   344 					}
   345 					if (curbucket < 0)
   346 						end = true;
   347 				} else {
   348 					if (iter != hash->m_Buckets[curbucket]->end())
   349 						iter++;
   350 					if (iter == hash->m_Buckets[curbucket]->end())
   351 					{
   352 						int oldbucket = curbucket;
   353 						for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
   354 						{
   355 							if (hash->m_Buckets[i])
   356 							{
   357 								iter = hash->m_Buckets[i]->begin();
   358 								if (iter == hash->m_Buckets[i]->end())
   359 									continue;
   360 								curbucket = i;
   361 								break;
   362 							}
   363 						}
   364 						if (curbucket == oldbucket)
   365 							end = true;
   366 					}
   367 				}
   368 			}
   369 		private:
   370 			int curbucket;
   371 			typename SourceHook::List<THashNode *>::iterator iter;
   372 			const THash *hash;
   373 			bool end;
   374 		};
   375 	public:
   376 		iterator begin()
   377 		{
   378 			return iterator(this);
   379 		}
   380 		iterator end()
   381 		{
   382 			iterator iter;
   383 			iter.hash = this;
   384 			return iter;
   385 		}
   386 		
   387 		const_iterator begin() const
   388 		{
   389 			return const_iterator(this);
   390 		}
   391 		const_iterator end() const
   392 		{
   393 			const_iterator iter;
   394 			iter.hash = this;
   395 			return iter;
   396 		}
   397 		
   398 		template <typename U>
   399 		iterator find(const U & u) const
   400 		{
   401 			iterator b = begin();
   402 			iterator e = end();
   403 			for (iterator iter = b; iter != e; iter++)
   404 			{
   405 				if ( (*iter).key == u )
   406 					return iter;
   407 			}
   408 			return end();
   409 		}
   410 		template <typename U>
   411 		iterator find(const U & u)
   412 		{
   413 			iterator b = begin();
   414 			iterator e = end();
   415 			for (iterator iter = b; iter != e; iter++)
   416 			{
   417 				if ( (*iter).key == u )
   418 					return iter;
   419 			}
   420 			return end();
   421 		}
   422 	private:
   423 		NodePtr	*m_Buckets;
   424 		size_t m_numBuckets;
   425 		float m_percentUsed;
   426 	};
   427 };
   428 
   429 #endif //_INCLUDE_SH_TINYHASH_H_