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