Uh.
1 /* ======== SourceMM ========
2 * Copyright (C) 2004-2005 Metamod:Source Development Team
3 * No warranties of any kind
7 * Author(s): David "BAILOPAN" Anderson
8 * ============================
11 #ifndef _INCLUDE_SH_TINYHASH_H_
12 #define _INCLUDE_SH_TINYHASH_H_
16 #define _T_INIT_HASH_SIZE 32
21 int HashFunction(const K & k);
24 int Compare(const K & k1, const K & k2);
27 * This is a tiny, growable hash class.
28 * Meant for quick and dirty dictionaries only!
30 template <class K, class V>
36 THashNode(const K & k, const V & v) :
40 THashNode & operator =(const THashNode &other)
48 typedef List<THashNode *> * NodePtr;
51 THash() : m_Buckets(NULL), m_numBuckets(0), m_percentUsed(0.0f)
55 THash(const THash &other) : m_Buckets(new NodePtr[other.m_numBuckets]),
56 m_numBuckets(other.m_numBuckets), m_percentUsed(other.m_percentUsed)
58 for (size_t i=0; i<m_numBuckets; i++)
60 for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
61 _FindOrInsert(iter->key)->val = iter->val;
63 void operator=(const THash &other)
66 for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
67 _FindOrInsert(iter->key)->val = iter->val;
87 V & operator [](const K & key)
89 THashNode *pNode = _FindOrInsert(key);
95 typename List<THashNode *>::iterator iter, end;
96 for (size_t i=0; i<m_numBuckets; i++)
100 end = m_Buckets[i]->end();
101 iter = m_Buckets[i]->begin();
116 THashNode *_FindOrInsert(const K & key)
118 size_t place = HashFunction(key) % m_numBuckets;
119 THashNode *pNode = NULL;
120 if (!m_Buckets[place])
122 m_Buckets[place] = new List<THashNode *>;
123 pNode = new THashNode(key, V());
124 m_Buckets[place]->push_back(pNode);
125 m_percentUsed += (1.0f / (float)m_numBuckets);
127 typename List<THashNode *>::iterator iter;
128 for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++)
130 if (Compare((*iter)->key, key) == 0)
133 //node does not exist
134 pNode = new THashNode(key, V());
135 m_Buckets[place]->push_back(pNode);
137 if (PercentUsed() > 0.75f)
143 m_percentUsed = 0.0f;
146 m_numBuckets = _T_INIT_HASH_SIZE;
147 m_Buckets = new NodePtr[m_numBuckets];
148 for (size_t i=0; i<m_numBuckets; i++)
151 size_t oldSize = m_numBuckets;
153 typename List<THashNode *>::iterator iter;
155 THashNode *pHashNode;
156 NodePtr *temp = new NodePtr[m_numBuckets];
157 for (size_t i=0; i<m_numBuckets; i++)
159 //look in old hash table
160 for (size_t i=0; i<oldSize; i++)
162 //does a bucket have anything?
165 //go through the list of items
166 for (iter = m_Buckets[i]->begin(); iter != m_Buckets[i]->end(); iter++)
169 //rehash it with the new bucket filter
170 place = HashFunction(pHashNode->key) % m_numBuckets;
171 //add it to the new hash table
174 temp[place] = new List<THashNode *>;
175 m_percentUsed += (1.0f / (float)m_numBuckets);
177 temp[place]->push_back(pHashNode);
179 //delete that bucket!
184 //reassign bucket table
190 friend class iterator;
191 friend class const_iterator;
196 iterator() : curbucket(-1), hash(NULL), end(true)
199 iterator(THash *h) : curbucket(-1), hash(h), end(false)
207 iterator & operator++()
213 iterator operator++(int)
219 const THashNode & operator * () const
223 THashNode & operator * ()
227 const THashNode * operator ->() const
231 THashNode * operator ->()
235 bool operator ==(const iterator &where) const
237 if (where.hash == this->hash
238 && where.end == this->end
241 ((where.curbucket == this->curbucket)
242 && (where.iter == iter))
247 bool operator !=(const iterator &where) const
249 return !( (*this) == where );
254 if (end || !hash || curbucket < 0 || curbucket >= static_cast<int>(hash->m_numBuckets))
257 // Remove this element and move to the next one
258 iterator tmp = *this;
261 hash->m_Buckets[curbucket]->erase(iter);
264 // :TODO: Maybe refactor to a lower size if required
269 if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
273 for (int i=0; i<(int)hash->m_numBuckets; i++)
275 if (hash->m_Buckets[i])
277 iter = hash->m_Buckets[i]->begin();
278 if (iter == hash->m_Buckets[i]->end())
287 if (iter != hash->m_Buckets[curbucket]->end())
289 if (iter == hash->m_Buckets[curbucket]->end())
291 int oldbucket = curbucket;
292 for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
294 if (hash->m_Buckets[i])
296 iter = hash->m_Buckets[i]->begin();
297 if (iter == hash->m_Buckets[i]->end())
303 if (curbucket == oldbucket)
310 typename SourceHook::List<THashNode *>::iterator iter;
318 const_iterator() : curbucket(-1), hash(NULL), end(true)
321 const_iterator(const THash *h) : curbucket(-1), hash(h), end(false)
329 const_iterator & operator++()
335 const_iterator operator++(int)
341 const THashNode & operator * () const
345 const THashNode * operator ->() const
349 bool operator ==(const const_iterator &where) const
351 if (where.hash == this->hash
352 && where.end == this->end
355 ((where.curbucket == this->curbucket)
356 && (where.iter == iter))
361 bool operator !=(const const_iterator &where) const
363 return !( (*this) == where );
368 if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
372 for (int i=0; i<(int)hash->m_numBuckets; i++)
374 if (hash->m_Buckets[i])
376 iter = hash->m_Buckets[i]->begin();
377 if (iter == hash->m_Buckets[i]->end())
386 if (iter != hash->m_Buckets[curbucket]->end())
388 if (iter == hash->m_Buckets[curbucket]->end())
390 int oldbucket = curbucket;
391 for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
393 if (hash->m_Buckets[i])
395 iter = hash->m_Buckets[i]->begin();
396 if (iter == hash->m_Buckets[i]->end())
402 if (curbucket == oldbucket)
409 typename SourceHook::List<THashNode *>::iterator iter;
416 return iterator(this);
425 const_iterator begin() const
427 return const_iterator(this);
429 const_iterator end() const
436 template <typename U>
437 iterator find(const U & u) const
439 iterator b = begin();
441 for (iterator iter = b; iter != e; iter++)
443 if ( (*iter).key == u )
448 template <typename U>
449 iterator find(const U & u)
451 iterator b = begin();
453 for (iterator iter = b; iter != e; iter++)
455 if ( (*iter).key == u )
461 iterator erase(iterator where)
466 template <typename U>
467 void erase(const U & u)
469 iterator iter = find(u);
481 #endif //_INCLUDE_SH_TINYHASH_H_