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