1 /* ======== SourceMM ========
2 * Copyright (C) 2004-2007 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 HashAlt(const U &u);
26 template <class U, class K>
27 int CompareAlt(const U &k1, const K &k2);
30 int Compare(const K & k1, const K & k2);
33 * This is a tiny, growable hash class.
34 * Meant for quick and dirty dictionaries only!
36 template <class K, class V>
42 THashNode(const K & k, const V & v) :
46 THashNode & operator =(const THashNode &other)
54 typedef List<THashNode *> * NodePtr;
57 THash() : m_Buckets(NULL), m_numBuckets(0), m_percentUsed(0.0f)
61 THash(const THash &other) : m_Buckets(new NodePtr[other.m_numBuckets]),
62 m_numBuckets(other.m_numBuckets), m_percentUsed(other.m_percentUsed)
64 for (size_t i=0; i<m_numBuckets; i++)
66 for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
67 _FindOrInsert(iter->key)->val = iter->val;
69 void operator=(const THash &other)
72 for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
73 _FindOrInsert(iter->key)->val = iter->val;
93 V & operator [](const K & key)
95 THashNode *pNode = _FindOrInsert(key);
101 typename List<THashNode *>::iterator iter, end;
102 for (size_t i=0; i<m_numBuckets; i++)
106 end = m_Buckets[i]->end();
107 iter = m_Buckets[i]->begin();
123 template <typename U>
124 V & AltFindOrInsert(const U & ukey)
126 size_t place = HashAlt(ukey) % m_numBuckets;
127 THashNode *pNode = NULL;
128 if (!m_Buckets[place])
130 m_Buckets[place] = new List<THashNode *>;
131 pNode = new THashNode(ukey, V());
132 m_Buckets[place]->push_back(pNode);
133 m_percentUsed += (1.0f / (float)m_numBuckets);
135 typename List<THashNode *>::iterator iter;
136 for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++)
138 if (CompareAlt(ukey, (*iter)->key) == 0)
143 //node does not exist
144 pNode = new THashNode(ukey, V());
145 m_Buckets[place]->push_back(pNode);
147 if (PercentUsed() > 0.75f)
154 THashNode *_FindOrInsert(const K & key)
156 size_t place = HashFunction(key) % m_numBuckets;
157 THashNode *pNode = NULL;
158 if (!m_Buckets[place])
160 m_Buckets[place] = new List<THashNode *>;
161 pNode = new THashNode(key, V());
162 m_Buckets[place]->push_back(pNode);
163 m_percentUsed += (1.0f / (float)m_numBuckets);
165 typename List<THashNode *>::iterator iter;
166 for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++)
168 if (Compare((*iter)->key, key) == 0)
171 //node does not exist
172 pNode = new THashNode(key, V());
173 m_Buckets[place]->push_back(pNode);
175 if (PercentUsed() > 0.75f)
183 m_percentUsed = 0.0f;
186 m_numBuckets = _T_INIT_HASH_SIZE;
187 m_Buckets = new NodePtr[m_numBuckets];
188 for (size_t i=0; i<m_numBuckets; i++)
191 size_t oldSize = m_numBuckets;
193 typename List<THashNode *>::iterator iter;
195 THashNode *pHashNode;
196 NodePtr *temp = new NodePtr[m_numBuckets];
197 for (size_t i=0; i<m_numBuckets; i++)
199 //look in old hash table
200 for (size_t i=0; i<oldSize; i++)
202 //does a bucket have anything?
205 //go through the list of items
206 for (iter = m_Buckets[i]->begin(); iter != m_Buckets[i]->end(); iter++)
209 //rehash it with the new bucket filter
210 place = HashFunction(pHashNode->key) % m_numBuckets;
211 //add it to the new hash table
214 temp[place] = new List<THashNode *>;
215 m_percentUsed += (1.0f / (float)m_numBuckets);
217 temp[place]->push_back(pHashNode);
219 //delete that bucket!
224 //reassign bucket table
234 iterator() : curbucket(-1), hash(NULL), end(true)
237 iterator(THash *h) : curbucket(-1), hash(h), end(false)
245 iterator & operator++()
251 iterator operator++(int)
257 const THashNode & operator * () const
261 THashNode & operator * ()
265 const THashNode * operator ->() const
269 THashNode * operator ->()
273 bool operator ==(const iterator &where) const
275 if (where.hash == this->hash
276 && where.end == this->end
279 ((where.curbucket == this->curbucket)
280 && (where.iter == iter))
285 bool operator !=(const iterator &where) const
287 return !( (*this) == where );
292 if (end || !hash || curbucket < 0 || curbucket >= static_cast<int>(hash->m_numBuckets))
295 // Remove this element and move to the next one
296 iterator tmp = *this;
299 hash->m_Buckets[curbucket]->erase(iter);
302 // :TODO: Maybe refactor to a lower size if required
307 if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
311 for (int i=0; i<(int)hash->m_numBuckets; i++)
313 if (hash->m_Buckets[i])
315 iter = hash->m_Buckets[i]->begin();
316 if (iter == hash->m_Buckets[i]->end())
325 if (iter != hash->m_Buckets[curbucket]->end())
327 if (iter == hash->m_Buckets[curbucket]->end())
329 int oldbucket = curbucket;
330 for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
332 if (hash->m_Buckets[i])
334 iter = hash->m_Buckets[i]->begin();
335 if (iter == hash->m_Buckets[i]->end())
341 if (curbucket == oldbucket)
348 typename SourceHook::List<THashNode *>::iterator iter;
356 const_iterator() : curbucket(-1), hash(NULL), end(true)
359 const_iterator(const THash *h) : curbucket(-1), hash(h), end(false)
367 const_iterator & operator++()
373 const_iterator operator++(int)
379 const THashNode & operator * () const
383 const THashNode * operator ->() const
387 bool operator ==(const const_iterator &where) const
389 if (where.hash == this->hash
390 && where.end == this->end
393 ((where.curbucket == this->curbucket)
394 && (where.iter == iter))
399 bool operator !=(const const_iterator &where) const
401 return !( (*this) == where );
406 if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
410 for (int i=0; i<(int)hash->m_numBuckets; i++)
412 if (hash->m_Buckets[i])
414 iter = hash->m_Buckets[i]->begin();
415 if (iter == hash->m_Buckets[i]->end())
424 if (iter != hash->m_Buckets[curbucket]->end())
426 if (iter == hash->m_Buckets[curbucket]->end())
428 int oldbucket = curbucket;
429 for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
431 if (hash->m_Buckets[i])
433 iter = hash->m_Buckets[i]->begin();
434 if (iter == hash->m_Buckets[i]->end())
440 if (curbucket == oldbucket)
447 typename SourceHook::List<THashNode *>::iterator iter;
454 return iterator(this);
463 const_iterator begin() const
465 return const_iterator(this);
467 const_iterator end() const
474 template <typename U>
475 iterator find(const U & u) const
477 iterator b = begin();
479 for (iterator iter = b; iter != e; iter++)
481 if ( (*iter).key == u )
486 template <typename U>
487 iterator find(const U & u)
489 iterator b = begin();
491 for (iterator iter = b; iter != e; iter++)
493 if ( (*iter).key == u )
498 template <typename U>
499 iterator FindAlt(const U & u)
501 iterator b = begin();
503 for (iterator iter = b; iter != e; iter++)
505 if (CompareAlt(u, (*iter).key) == 0)
512 iterator erase(iterator where)
517 template <typename U>
518 void erase(const U & u)
520 iterator iter = find(u);
525 friend class iterator;
526 friend class const_iterator;
534 #endif //_INCLUDE_SH_TINYHASH_H_