sourcehook/sh_tinyhash.h
author Pavol Marko <pavolmarko@gmail.com>
Sat Nov 17 09:53:58 2007 +0000 (2007-11-17)
branchhookman_autogen
changeset 461 2fa049f36721
parent 430 e735f6701dcf
child 523 6f1630519b81
permissions -rw-r--r--
New hookfunc local vars code; first step to vafmt support
dvander@102
     1
/* ======== SourceMM ========
ds@294
     2
* Copyright (C) 2004-2007 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_