sourcehook/sh_tinyhash.h
author David Anderson <dvander@alliedmods.net>
Thu Sep 27 19:28:05 2007 +0000 (2007-09-27)
branchsourcemm-1.6.0
changeset 356 bbcf8dcb2aa7
parent 347 e82968c21606
permissions -rw-r--r--
removed unnecessary api call
dvander@347
     1
/* ======== SourceMM ========
dvander@347
     2
* Copyright (C) 2004-2007 Metamod:Source Development Team
dvander@347
     3
* No warranties of any kind
dvander@347
     4
*
dvander@347
     5
* License: zlib/libpng
dvander@347
     6
*
dvander@347
     7
* Author(s): David "BAILOPAN" Anderson
dvander@347
     8
* ============================
dvander@347
     9
*/
dvander@347
    10
dvander@347
    11
#ifndef _INCLUDE_SH_TINYHASH_H_
dvander@347
    12
#define _INCLUDE_SH_TINYHASH_H_
dvander@347
    13
dvander@347
    14
#include "sh_list.h"
dvander@347
    15
dvander@347
    16
#define _T_INIT_HASH_SIZE	32
dvander@347
    17
dvander@347
    18
namespace SourceHook
dvander@347
    19
{
dvander@347
    20
	template <class K>
dvander@347
    21
	int HashFunction(const K & k);
dvander@347
    22
dvander@347
    23
	template <class U>
dvander@347
    24
	int HashAlt(const U &u);
dvander@347
    25
dvander@347
    26
	template <class U, class K>
dvander@347
    27
	int CompareAlt(const U &k1, const K &k2);
dvander@347
    28
dvander@347
    29
	template <class K>
dvander@347
    30
	int Compare(const K & k1, const K & k2);
dvander@347
    31
dvander@347
    32
	/**
dvander@347
    33
	 * This is a tiny, growable hash class.
dvander@347
    34
	 * Meant for quick and dirty dictionaries only!
dvander@347
    35
	 */
dvander@347
    36
	template <class K, class V>
dvander@347
    37
	class THash
dvander@347
    38
	{
dvander@347
    39
	public:
dvander@347
    40
		struct THashNode
dvander@347
    41
		{
dvander@347
    42
			THashNode(const K & k, const V & v) :
dvander@347
    43
				key(k), val(v)
dvander@347
    44
				{
dvander@347
    45
				};
dvander@347
    46
			THashNode & operator =(const THashNode &other)
dvander@347
    47
			{
dvander@347
    48
				key = other.key;
dvander@347
    49
				val = other.val;
dvander@347
    50
			}
dvander@347
    51
			K key;
dvander@347
    52
			V val;
dvander@347
    53
		};
dvander@347
    54
		typedef List<THashNode *> *	NodePtr;
dvander@347
    55
	public:
dvander@347
    56
		class const_iterator;
dvander@347
    57
		THash() : m_Buckets(NULL), m_numBuckets(0), m_percentUsed(0.0f)
dvander@347
    58
		{
dvander@347
    59
			_Refactor();
dvander@347
    60
		}
dvander@347
    61
		THash(const THash &other) : m_Buckets(new NodePtr[other.m_numBuckets]),
dvander@347
    62
			m_numBuckets(other.m_numBuckets), m_percentUsed(other.m_percentUsed)
dvander@347
    63
		{
dvander@347
    64
			for (size_t i=0; i<m_numBuckets; i++)
dvander@347
    65
					m_Buckets[i] = NULL;
dvander@347
    66
			for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
dvander@347
    67
				_FindOrInsert(iter->key)->val = iter->val;
dvander@347
    68
		}
dvander@347
    69
		void operator=(const THash &other)
dvander@347
    70
		{
dvander@347
    71
			clear();
dvander@347
    72
			for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
dvander@347
    73
				_FindOrInsert(iter->key)->val = iter->val;
dvander@347
    74
		}
dvander@347
    75
dvander@347
    76
		~THash()
dvander@347
    77
		{
dvander@347
    78
			_Clear();
dvander@347
    79
		}
dvander@347
    80
		void clear()
dvander@347
    81
		{
dvander@347
    82
			_Clear();
dvander@347
    83
			_Refactor();
dvander@347
    84
		}
dvander@347
    85
		size_t GetBuckets()
dvander@347
    86
		{
dvander@347
    87
			return m_numBuckets;
dvander@347
    88
		}
dvander@347
    89
		float PercentUsed()
dvander@347
    90
		{
dvander@347
    91
			return m_percentUsed;
dvander@347
    92
		}
dvander@347
    93
		V & operator [](const K & key)
dvander@347
    94
		{
dvander@347
    95
			THashNode *pNode = _FindOrInsert(key);
dvander@347
    96
			return pNode->val;
dvander@347
    97
		}
dvander@347
    98
	private:
dvander@347
    99
		void _Clear()
dvander@347
   100
		{
dvander@347
   101
			typename List<THashNode *>::iterator iter, end;
dvander@347
   102
			for (size_t i=0; i<m_numBuckets; i++)
dvander@347
   103
			{
dvander@347
   104
				if (m_Buckets[i])
dvander@347
   105
				{
dvander@347
   106
					end = m_Buckets[i]->end();
dvander@347
   107
					iter = m_Buckets[i]->begin();
dvander@347
   108
					while (iter != end)
dvander@347
   109
					{
dvander@347
   110
						delete (*iter);
dvander@347
   111
						iter++;
dvander@347
   112
					}
dvander@347
   113
					delete m_Buckets[i];
dvander@347
   114
					m_Buckets[i] = NULL;
dvander@347
   115
				}
dvander@347
   116
			}
dvander@347
   117
			if (m_Buckets)
dvander@347
   118
				delete [] m_Buckets;
dvander@347
   119
			m_Buckets = NULL;
dvander@347
   120
			m_numBuckets = 0;
dvander@347
   121
		}
dvander@347
   122
	public:
dvander@347
   123
		template <typename U>
dvander@347
   124
		V & AltFindOrInsert(const U & ukey)
dvander@347
   125
		{
dvander@347
   126
			size_t place = HashAlt(ukey) % m_numBuckets;
dvander@347
   127
			THashNode *pNode = NULL;
dvander@347
   128
			if (!m_Buckets[place])
dvander@347
   129
			{
dvander@347
   130
				m_Buckets[place] = new List<THashNode *>;
dvander@347
   131
				pNode = new THashNode(ukey, V());
dvander@347
   132
				m_Buckets[place]->push_back(pNode);
dvander@347
   133
				m_percentUsed += (1.0f / (float)m_numBuckets);
dvander@347
   134
			} else {
dvander@347
   135
				typename List<THashNode *>::iterator iter;
dvander@347
   136
				for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++)
dvander@347
   137
				{
dvander@347
   138
					if (CompareAlt(ukey, (*iter)->key) == 0)
dvander@347
   139
					{
dvander@347
   140
						return (*iter)->val;
dvander@347
   141
					}
dvander@347
   142
				}
dvander@347
   143
				//node does not exist
dvander@347
   144
				pNode = new THashNode(ukey, V());
dvander@347
   145
				m_Buckets[place]->push_back(pNode);
dvander@347
   146
			}
dvander@347
   147
			if (PercentUsed() > 0.75f)
dvander@347
   148
			{
dvander@347
   149
				_Refactor();
dvander@347
   150
			}
dvander@347
   151
			return pNode->val;
dvander@347
   152
		}
dvander@347
   153
	private:
dvander@347
   154
		THashNode *_FindOrInsert(const K & key)
dvander@347
   155
		{
dvander@347
   156
			size_t place = HashFunction(key) % m_numBuckets;
dvander@347
   157
			THashNode *pNode = NULL;
dvander@347
   158
			if (!m_Buckets[place])
dvander@347
   159
			{
dvander@347
   160
				m_Buckets[place] = new List<THashNode *>;
dvander@347
   161
				pNode = new THashNode(key, V());
dvander@347
   162
				m_Buckets[place]->push_back(pNode);
dvander@347
   163
				m_percentUsed += (1.0f / (float)m_numBuckets);
dvander@347
   164
			} else {
dvander@347
   165
				typename List<THashNode *>::iterator iter;
dvander@347
   166
				for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++)
dvander@347
   167
				{
dvander@347
   168
					if (Compare((*iter)->key, key) == 0)
dvander@347
   169
						return (*iter);
dvander@347
   170
				}
dvander@347
   171
				//node does not exist
dvander@347
   172
				pNode = new THashNode(key, V());
dvander@347
   173
				m_Buckets[place]->push_back(pNode);
dvander@347
   174
			}
dvander@347
   175
			if (PercentUsed() > 0.75f)
dvander@347
   176
			{
dvander@347
   177
				_Refactor();
dvander@347
   178
			}
dvander@347
   179
			return pNode;
dvander@347
   180
		}
dvander@347
   181
		void _Refactor()
dvander@347
   182
		{
dvander@347
   183
			m_percentUsed = 0.0f;
dvander@347
   184
			if (!m_numBuckets)
dvander@347
   185
			{
dvander@347
   186
				m_numBuckets = _T_INIT_HASH_SIZE;
dvander@347
   187
				m_Buckets = new NodePtr[m_numBuckets];
dvander@347
   188
				for (size_t i=0; i<m_numBuckets; i++)
dvander@347
   189
					m_Buckets[i] = NULL;
dvander@347
   190
			} else {
dvander@347
   191
				size_t oldSize = m_numBuckets;
dvander@347
   192
				m_numBuckets *= 2;
dvander@347
   193
				typename List<THashNode *>::iterator iter;
dvander@347
   194
				size_t place;
dvander@347
   195
				THashNode *pHashNode;
dvander@347
   196
				NodePtr *temp = new NodePtr[m_numBuckets];
dvander@347
   197
				for (size_t i=0; i<m_numBuckets; i++)
dvander@347
   198
					temp[i] = NULL;
dvander@347
   199
				//look in old hash table
dvander@347
   200
				for (size_t i=0; i<oldSize; i++)
dvander@347
   201
				{
dvander@347
   202
					//does a bucket have anything?
dvander@347
   203
					if (m_Buckets[i])
dvander@347
   204
					{
dvander@347
   205
						//go through the list of items
dvander@347
   206
						for (iter = m_Buckets[i]->begin(); iter != m_Buckets[i]->end(); iter++)
dvander@347
   207
						{
dvander@347
   208
							pHashNode = (*iter);
dvander@347
   209
							//rehash it with the new bucket filter
dvander@347
   210
							place = HashFunction(pHashNode->key) % m_numBuckets;
dvander@347
   211
							//add it to the new hash table
dvander@347
   212
							if (!temp[place])
dvander@347
   213
							{
dvander@347
   214
								temp[place] = new List<THashNode *>;
dvander@347
   215
								m_percentUsed += (1.0f / (float)m_numBuckets);
dvander@347
   216
							}
dvander@347
   217
							temp[place]->push_back(pHashNode);
dvander@347
   218
						}
dvander@347
   219
						//delete that bucket!
dvander@347
   220
						delete m_Buckets[i];
dvander@347
   221
						m_Buckets[i] = NULL;
dvander@347
   222
					}
dvander@347
   223
				}
dvander@347
   224
				//reassign bucket table
dvander@347
   225
				delete [] m_Buckets;
dvander@347
   226
				m_Buckets = temp;
dvander@347
   227
			}
dvander@347
   228
		}
dvander@347
   229
	public:
dvander@347
   230
		friend class iterator;
dvander@347
   231
		friend class const_iterator;
dvander@347
   232
		class iterator
dvander@347
   233
		{
dvander@347
   234
			friend class THash;
dvander@347
   235
		public:
dvander@347
   236
			iterator() : curbucket(-1), hash(NULL), end(true)
dvander@347
   237
			{
dvander@347
   238
			};
dvander@347
   239
			iterator(THash *h) : curbucket(-1), hash(h), end(false)
dvander@347
   240
			{
dvander@347
   241
				if (!h->m_Buckets)
dvander@347
   242
					end = true;
dvander@347
   243
				else
dvander@347
   244
					_Inc();
dvander@347
   245
			};
dvander@347
   246
			//pre increment
dvander@347
   247
			iterator & operator++()
dvander@347
   248
			{
dvander@347
   249
				_Inc();
dvander@347
   250
				return *this;
dvander@347
   251
			}
dvander@347
   252
			//post increment
dvander@347
   253
			iterator operator++(int)
dvander@347
   254
			{
dvander@347
   255
				iterator old(*this);
dvander@347
   256
				_Inc();
dvander@347
   257
				return old;
dvander@347
   258
			}
dvander@347
   259
			const THashNode & operator * () const
dvander@347
   260
			{
dvander@347
   261
				return *(*iter);
dvander@347
   262
			}
dvander@347
   263
			THashNode & operator * ()
dvander@347
   264
			{
dvander@347
   265
				return *(*iter);
dvander@347
   266
			}
dvander@347
   267
			const THashNode * operator ->() const
dvander@347
   268
			{
dvander@347
   269
				return (*iter);
dvander@347
   270
			}
dvander@347
   271
			THashNode * operator ->()
dvander@347
   272
			{
dvander@347
   273
				return (*iter);
dvander@347
   274
			}
dvander@347
   275
			bool operator ==(const iterator &where) const
dvander@347
   276
			{
dvander@347
   277
				if (where.hash == this->hash
dvander@347
   278
					&& where.end == this->end
dvander@347
   279
					&&
dvander@347
   280
					 (this->end ||
dvander@347
   281
					   ((where.curbucket == this->curbucket)
dvander@347
   282
						&& (where.iter == iter))
dvander@347
   283
						 ))
dvander@347
   284
					return true;
dvander@347
   285
				return false;
dvander@347
   286
			}
dvander@347
   287
			bool operator !=(const iterator &where) const
dvander@347
   288
			{
dvander@347
   289
				return !( (*this) == where );
dvander@347
   290
			}
dvander@347
   291
dvander@347
   292
			void erase()
dvander@347
   293
			{
dvander@347
   294
				if (end || !hash || curbucket < 0 || curbucket >= static_cast<int>(hash->m_numBuckets))
dvander@347
   295
					return;
dvander@347
   296
dvander@347
   297
				// Remove this element and move to the next one
dvander@347
   298
				iterator tmp = *this;
dvander@347
   299
				++tmp;
dvander@347
   300
				delete (*iter);
dvander@347
   301
				hash->m_Buckets[curbucket]->erase(iter);
dvander@347
   302
				*this = tmp;
dvander@347
   303
dvander@347
   304
				// :TODO: Maybe refactor to a lower size if required
dvander@347
   305
			}
dvander@347
   306
		private:
dvander@347
   307
			void _Inc()
dvander@347
   308
			{
dvander@347
   309
				if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
dvander@347
   310
					return;
dvander@347
   311
				if (curbucket < 0)
dvander@347
   312
				{
dvander@347
   313
					for (int i=0; i<(int)hash->m_numBuckets; i++)
dvander@347
   314
					{
dvander@347
   315
						if (hash->m_Buckets[i])
dvander@347
   316
						{
dvander@347
   317
							iter = hash->m_Buckets[i]->begin();
dvander@347
   318
							if (iter == hash->m_Buckets[i]->end())
dvander@347
   319
								continue;
dvander@347
   320
							curbucket = i;
dvander@347
   321
							break;
dvander@347
   322
						}
dvander@347
   323
					}
dvander@347
   324
					if (curbucket < 0)
dvander@347
   325
						end = true;
dvander@347
   326
				} else {
dvander@347
   327
					if (iter != hash->m_Buckets[curbucket]->end())
dvander@347
   328
						iter++;
dvander@347
   329
					if (iter == hash->m_Buckets[curbucket]->end())
dvander@347
   330
					{
dvander@347
   331
						int oldbucket = curbucket;
dvander@347
   332
						for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
dvander@347
   333
						{
dvander@347
   334
							if (hash->m_Buckets[i])
dvander@347
   335
							{
dvander@347
   336
								iter = hash->m_Buckets[i]->begin();
dvander@347
   337
								if (iter == hash->m_Buckets[i]->end())
dvander@347
   338
									continue;
dvander@347
   339
								curbucket = i;
dvander@347
   340
								break;
dvander@347
   341
							}
dvander@347
   342
						}
dvander@347
   343
						if (curbucket == oldbucket)
dvander@347
   344
							end = true;
dvander@347
   345
					}
dvander@347
   346
				}
dvander@347
   347
			}
dvander@347
   348
		private:
dvander@347
   349
			int curbucket;
dvander@347
   350
			typename SourceHook::List<THashNode *>::iterator iter;
dvander@347
   351
			THash *hash;
dvander@347
   352
			bool end;
dvander@347
   353
		};
dvander@347
   354
		class const_iterator
dvander@347
   355
		{
dvander@347
   356
			friend class THash;
dvander@347
   357
		public:
dvander@347
   358
			const_iterator() : curbucket(-1), hash(NULL), end(true)
dvander@347
   359
			{
dvander@347
   360
			};
dvander@347
   361
			const_iterator(const THash *h) : curbucket(-1), hash(h), end(false)
dvander@347
   362
			{
dvander@347
   363
				if (!h->m_Buckets)
dvander@347
   364
					end = true;
dvander@347
   365
				else
dvander@347
   366
					_Inc();
dvander@347
   367
			};
dvander@347
   368
			//pre increment
dvander@347
   369
			const_iterator & operator++()
dvander@347
   370
			{
dvander@347
   371
				_Inc();
dvander@347
   372
				return *this;
dvander@347
   373
			}
dvander@347
   374
			//post increment
dvander@347
   375
			const_iterator operator++(int)
dvander@347
   376
			{
dvander@347
   377
				iterator old(*this);
dvander@347
   378
				_Inc();
dvander@347
   379
				return old;
dvander@347
   380
			}
dvander@347
   381
			const THashNode & operator * () const
dvander@347
   382
			{
dvander@347
   383
				return *(*iter);
dvander@347
   384
			}
dvander@347
   385
			const THashNode * operator ->() const
dvander@347
   386
			{
dvander@347
   387
				return (*iter);
dvander@347
   388
			}
dvander@347
   389
			bool operator ==(const const_iterator &where) const
dvander@347
   390
			{
dvander@347
   391
				if (where.hash == this->hash
dvander@347
   392
					&& where.end == this->end
dvander@347
   393
					&&
dvander@347
   394
					 (this->end ||
dvander@347
   395
					   ((where.curbucket == this->curbucket)
dvander@347
   396
						&& (where.iter == iter))
dvander@347
   397
						 ))
dvander@347
   398
					return true;
dvander@347
   399
				return false;
dvander@347
   400
			}
dvander@347
   401
			bool operator !=(const const_iterator &where) const
dvander@347
   402
			{
dvander@347
   403
				return !( (*this) == where );
dvander@347
   404
			}
dvander@347
   405
		private:
dvander@347
   406
			void _Inc()
dvander@347
   407
			{
dvander@347
   408
				if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
dvander@347
   409
					return;
dvander@347
   410
				if (curbucket < 0)
dvander@347
   411
				{
dvander@347
   412
					for (int i=0; i<(int)hash->m_numBuckets; i++)
dvander@347
   413
					{
dvander@347
   414
						if (hash->m_Buckets[i])
dvander@347
   415
						{
dvander@347
   416
							iter = hash->m_Buckets[i]->begin();
dvander@347
   417
							if (iter == hash->m_Buckets[i]->end())
dvander@347
   418
								continue;
dvander@347
   419
							curbucket = i;
dvander@347
   420
							break;
dvander@347
   421
						}
dvander@347
   422
					}
dvander@347
   423
					if (curbucket < 0)
dvander@347
   424
						end = true;
dvander@347
   425
				} else {
dvander@347
   426
					if (iter != hash->m_Buckets[curbucket]->end())
dvander@347
   427
						iter++;
dvander@347
   428
					if (iter == hash->m_Buckets[curbucket]->end())
dvander@347
   429
					{
dvander@347
   430
						int oldbucket = curbucket;
dvander@347
   431
						for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
dvander@347
   432
						{
dvander@347
   433
							if (hash->m_Buckets[i])
dvander@347
   434
							{
dvander@347
   435
								iter = hash->m_Buckets[i]->begin();
dvander@347
   436
								if (iter == hash->m_Buckets[i]->end())
dvander@347
   437
									continue;
dvander@347
   438
								curbucket = i;
dvander@347
   439
								break;
dvander@347
   440
							}
dvander@347
   441
						}
dvander@347
   442
						if (curbucket == oldbucket)
dvander@347
   443
							end = true;
dvander@347
   444
					}
dvander@347
   445
				}
dvander@347
   446
			}
dvander@347
   447
		private:
dvander@347
   448
			int curbucket;
dvander@347
   449
			typename SourceHook::List<THashNode *>::iterator iter;
dvander@347
   450
			const THash *hash;
dvander@347
   451
			bool end;
dvander@347
   452
		};
dvander@347
   453
	public:
dvander@347
   454
		iterator begin()
dvander@347
   455
		{
dvander@347
   456
			return iterator(this);
dvander@347
   457
		}
dvander@347
   458
		iterator end()
dvander@347
   459
		{
dvander@347
   460
			iterator iter;
dvander@347
   461
			iter.hash = this;
dvander@347
   462
			return iter;
dvander@347
   463
		}
dvander@347
   464
dvander@347
   465
		const_iterator begin() const
dvander@347
   466
		{
dvander@347
   467
			return const_iterator(this);
dvander@347
   468
		}
dvander@347
   469
		const_iterator end() const
dvander@347
   470
		{
dvander@347
   471
			const_iterator iter;
dvander@347
   472
			iter.hash = this;
dvander@347
   473
			return iter;
dvander@347
   474
		}
dvander@347
   475
dvander@347
   476
		template <typename U>
dvander@347
   477
		iterator find(const U & u) const
dvander@347
   478
		{
dvander@347
   479
			iterator b = begin();
dvander@347
   480
			iterator e = end();
dvander@347
   481
			for (iterator iter = b; iter != e; iter++)
dvander@347
   482
			{
dvander@347
   483
				if ( (*iter).key == u )
dvander@347
   484
					return iter;
dvander@347
   485
			}
dvander@347
   486
			return end();
dvander@347
   487
		}
dvander@347
   488
		template <typename U>
dvander@347
   489
		iterator find(const U & u)
dvander@347
   490
		{
dvander@347
   491
			iterator b = begin();
dvander@347
   492
			iterator e = end();
dvander@347
   493
			for (iterator iter = b; iter != e; iter++)
dvander@347
   494
			{
dvander@347
   495
				if ( (*iter).key == u )
dvander@347
   496
					return iter;
dvander@347
   497
			}
dvander@347
   498
			return end();
dvander@347
   499
		}
dvander@347
   500
		template <typename U>
dvander@347
   501
		iterator FindAlt(const U & u)
dvander@347
   502
		{
dvander@347
   503
			iterator b = begin();
dvander@347
   504
			iterator e = end();
dvander@347
   505
			for (iterator iter = b; iter != e; iter++)
dvander@347
   506
			{
dvander@347
   507
				if (CompareAlt(u, (*iter).key) == 0)
dvander@347
   508
				{
dvander@347
   509
					return iter;
dvander@347
   510
				}
dvander@347
   511
			}
dvander@347
   512
			return e;
dvander@347
   513
		}
dvander@347
   514
		iterator erase(iterator where)
dvander@347
   515
		{
dvander@347
   516
			where.erase();
dvander@347
   517
			return where;
dvander@347
   518
		}
dvander@347
   519
		template <typename U>
dvander@347
   520
		void erase(const U & u)
dvander@347
   521
		{
dvander@347
   522
			iterator iter = find(u);
dvander@347
   523
			if (iter == end())
dvander@347
   524
				return;
dvander@347
   525
			iter.erase();
dvander@347
   526
		}
dvander@347
   527
	private:
dvander@347
   528
		NodePtr	*m_Buckets;
dvander@347
   529
		size_t m_numBuckets;
dvander@347
   530
		float m_percentUsed;
dvander@347
   531
	};
dvander@347
   532
};
dvander@347
   533
dvander@347
   534
#endif //_INCLUDE_SH_TINYHASH_H_