sourcehook/sh_tinyhash.h
author David Anderson <dvander@alliedmods.net>
Tue Sep 13 22:16:29 2005 +0000 (2005-09-13)
changeset 110 77e7acc57f67
parent 107 1d6e7e0bdcd9
child 111 aec58c99dafc
permissions -rw-r--r--
Fixed some more template bugs
     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_numBuckets(0), m_Buckets(NULL)
    46 		{
    47 			_Refactor();
    48 		}
    49 		size_t GetBuckets()
    50 		{
    51 			return m_numBuckets;
    52 		}
    53 		float PercentUsed()
    54 		{
    55 			return m_percentUsed;
    56 		}
    57 		V & operator [](const K & key)
    58 		{
    59 			THashNode *pNode = _FindOrInsert(key);
    60 			return pNode->val;
    61 		}
    62 	private:
    63 		THashNode *_FindOrInsert(const K & key)
    64 		{
    65 			size_t place = HashFunction(key) % m_numBuckets;
    66 			THashNode *pNode = NULL;
    67 			if (!m_Buckets[place])
    68 			{
    69 				m_Buckets[place] = new List<THashNode *>;
    70 				pNode = new THashNode(key, V());
    71 				m_Buckets[place]->push_back(pNode);
    72 				m_percentUsed += (1.0f / (float)m_numBuckets);
    73 			} else {
    74 				typename List<THashNode *>::iterator iter;
    75 				for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++)
    76 				{
    77 					if (Compare((*iter)->key, key) == 0)
    78 						return (*iter);
    79 				}
    80 				//node does not exist
    81 				pNode = new THashNode(key, V());
    82 				m_Buckets[place]->push_back(pNode);
    83 			}
    84 			if (PercentUsed() > 0.75f)
    85 				_Refactor();
    86 			return pNode;
    87 		}
    88 		void _Refactor()
    89 		{
    90 			m_percentUsed = 0.0f;
    91 			if (!m_numBuckets)
    92 			{
    93 				m_numBuckets = _T_INIT_HASH_SIZE;
    94 				m_Buckets = new NodePtr[m_numBuckets];
    95 				for (size_t i=0; i<m_numBuckets; i++)
    96 					m_Buckets[i] = NULL;
    97 			} else {
    98 				size_t oldSize = m_numBuckets;
    99 				m_numBuckets *= 2;
   100 				typename List<THashNode *>::iterator iter;
   101 				size_t place;
   102 				THashNode *pHashNode;
   103                 NodePtr *temp = new NodePtr[m_numBuckets];
   104 				for (size_t i=0; i<m_numBuckets; i++)
   105 					temp[i] = NULL;
   106 				//look in old hash table
   107 				for (size_t i=0; i<oldSize; i++)
   108 				{
   109 					//does a bucket have anything?
   110 					if (m_Buckets[i])
   111 					{
   112 						//go through the list of items
   113 						for (iter = m_Buckets[i]->begin(); iter != m_Buckets[i]->end(); iter++)
   114 						{
   115 							pHashNode = (*iter);
   116 							//rehash it with the new bucket filter
   117 							place = HashFunction(pHashNode->key) % m_numBuckets;
   118 							//add it to the new hash table
   119 							if (!temp[place])
   120 							{
   121 								temp[place] = new List<THashNode *>;
   122 								m_percentUsed += (1.0f / (float)m_numBuckets);
   123 							}
   124 							temp[place]->push_back(pHashNode);
   125 						}
   126 						//delete that bucket!
   127 						delete m_Buckets[i];
   128 						m_Buckets[i] = NULL;
   129 					}
   130 				}
   131 				//reassign bucket table
   132 				delete [] m_Buckets;
   133 				m_Buckets = temp;
   134 			}
   135 		}
   136 	public:
   137 		friend class iterator;
   138 		class iterator
   139 		{
   140 			friend class THash;
   141 		public:
   142 			iterator() : hash(NULL), end(true)
   143 			{
   144 			};
   145 			iterator(THash *h) : hash(h), end(false)
   146 			{
   147 				if (!h->m_Buckets)
   148 					end = true;
   149 				else
   150 					_Inc();
   151 			};
   152 			//pre increment
   153 			iterator & operator++()
   154 			{
   155 				_Inc();
   156 				return *this;
   157 			}
   158 			//post increment
   159 			iterator operator++(int)
   160 			{
   161 				iterator old(*this);
   162 				_Inc();
   163 				return old;
   164 			}
   165 			THashNode & operator * () const
   166 			{
   167 				return *(*iter);
   168 			}
   169 			THashNode & operator * ()
   170 			{
   171 				return *(*iter);
   172 			}
   173 			THashNode * operator ->() const
   174 			{
   175 				return (*iter);
   176 			}
   177 			THashNode * operator ->()
   178 			{
   179 				return (*iter);
   180 			}
   181 			bool operator ==(const iterator &where) const
   182 			{
   183 				if (where.hash == this->hash
   184 					&& where.end == this->end
   185 					&& 
   186 					 (this->end || 
   187 					   ((where.curbucket == this->curbucket) 
   188 					     && (where.iter == iter))
   189 						 ))
   190 					return true;
   191 				return false;
   192 			}
   193 			bool operator !=(const iterator &where) const
   194 			{
   195 				return !( (*this) == where );
   196 			}
   197 		private:
   198 			void _Inc()
   199 			{
   200 				if (end || !hash || curbucket >= hash->m_numBuckets)
   201 					return;
   202 				if (curbucket < 0)
   203 				{
   204 					for (int i=0; i<(int)hash->m_numBuckets; i++)
   205 					{
   206 						if (hash->m_Buckets[i])
   207 						{
   208 							iter = hash->m_Buckets[i]->begin();
   209 							if (iter == hash->m_Buckets[i]->end())
   210 								continue;
   211 							curbucket = i;
   212 							break;
   213 						}
   214 					}
   215 					if (curbucket < 0)
   216 						end = true;
   217 				} else {
   218 					if (iter != hash->m_Buckets[curbucket]->end())
   219 						iter++;
   220 					if (iter == hash->m_Buckets[curbucket]->end())
   221 					{
   222 						int oldbucket = curbucket;
   223 						for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
   224 						{
   225 							if (hash->m_Buckets[i])
   226 							{
   227 								iter = hash->m_Buckets[i]->begin();
   228 								if (iter == hash->m_Buckets[i]->end())
   229 									continue;
   230 								curbucket = i;
   231 								break;
   232 							}
   233 						}
   234 						if (curbucket == oldbucket)
   235 							end = true;
   236 					}
   237 				}
   238 			}
   239 		private:
   240 			int curbucket;
   241 			typename SourceHook::List<THashNode *>::iterator iter;
   242 			THash *hash;
   243 			bool end;
   244 		};
   245 	public:
   246 		iterator begin()
   247 		{
   248 			return iterator(this);
   249 		}
   250 		iterator end()
   251 		{
   252 			iterator iter;
   253 			iter.hash = this;
   254 			return iter;
   255 		}
   256 		template <typename U>
   257 		iterator find(const U & u) const
   258 		{
   259 			iterator b = begin();
   260 			iterator e = end();
   261 			for (iterator iter = b; iter != e; iter++)
   262 			{
   263 				if ( (*iter).key == u )
   264 					return iter;
   265 			}
   266 			return end();
   267 		}
   268 		template <typename U>
   269 		iterator find(const U & u)
   270 		{
   271 			iterator b = begin();
   272 			iterator e = end();
   273 			for (iterator iter = b; iter != e; iter++)
   274 			{
   275 				if ( (*iter).key == u )
   276 					return iter;
   277 			}
   278 			return end();
   279 		}
   280 	private:
   281 		NodePtr	*m_Buckets;
   282 		size_t m_numBuckets;
   283 		float m_percentUsed;
   284 	};
   285 };
   286 
   287 #endif //_INCLUDE_SH_TINYHASH_H_