core/sourcehook/sh_tinyhash.h
author Scott Ehlert <ds@alliedmods.net>
Thu Dec 10 00:59:50 2009 -0600 (2009-12-10)
changeset 689 4065ba5e9155
parent 539 db914129ae01
child 733 2365240861a2
permissions -rw-r--r--
Rewrote user message caching code to always use IServerGameDLL::GetUserMessageInfo (bug 4117, r=dvander).

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