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) :
43 typedef List<THashNode *> * NodePtr;
45 THash() : m_Buckets(NULL), m_numBuckets(0), m_percentUsed(0.0f)
49 THash(const THash &other) : m_Buckets(new NodePtr[other.m_numBuckets]),
50 m_numBuckets(other.m_numBuckets), m_percentUsed(other.m_percentUsed)
52 for (size_t i=0; i<m_numBuckets; i++)
54 for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
55 _FindOrInsert(iter->key)->val = iter->val;
57 void operator=(const THash &other)
60 for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
61 _FindOrInsert(iter->key)->val = iter->val;
81 V & operator [](const K & key)
83 THashNode *pNode = _FindOrInsert(key);
89 for (size_t i=0; i<m_numBuckets; i++)
102 THashNode *_FindOrInsert(const K & key)
104 size_t place = HashFunction(key) % m_numBuckets;
105 THashNode *pNode = NULL;
106 if (!m_Buckets[place])
108 m_Buckets[place] = new List<THashNode *>;
109 pNode = new THashNode(key, V());
110 m_Buckets[place]->push_back(pNode);
111 m_percentUsed += (1.0f / (float)m_numBuckets);
113 typename List<THashNode *>::iterator iter;
114 for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++)
116 if (Compare((*iter)->key, key) == 0)
119 //node does not exist
120 pNode = new THashNode(key, V());
121 m_Buckets[place]->push_back(pNode);
123 if (PercentUsed() > 0.75f)
129 m_percentUsed = 0.0f;
132 m_numBuckets = _T_INIT_HASH_SIZE;
133 m_Buckets = new NodePtr[m_numBuckets];
134 for (size_t i=0; i<m_numBuckets; i++)
137 size_t oldSize = m_numBuckets;
139 typename List<THashNode *>::iterator iter;
141 THashNode *pHashNode;
142 NodePtr *temp = new NodePtr[m_numBuckets];
143 for (size_t i=0; i<m_numBuckets; i++)
145 //look in old hash table
146 for (size_t i=0; i<oldSize; i++)
148 //does a bucket have anything?
151 //go through the list of items
152 for (iter = m_Buckets[i]->begin(); iter != m_Buckets[i]->end(); iter++)
155 //rehash it with the new bucket filter
156 place = HashFunction(pHashNode->key) % m_numBuckets;
157 //add it to the new hash table
160 temp[place] = new List<THashNode *>;
161 m_percentUsed += (1.0f / (float)m_numBuckets);
163 temp[place]->push_back(pHashNode);
165 //delete that bucket!
170 //reassign bucket table
176 friend class iterator;
177 friend class const_iterator;
182 iterator() : curbucket(-1), hash(NULL), end(true)
185 iterator(THash *h) : curbucket(-1), hash(h), end(false)
193 iterator & operator++()
199 iterator operator++(int)
205 const THashNode & operator * () const
209 THashNode & operator * ()
213 const THashNode * operator ->() const
217 THashNode * operator ->()
221 bool operator ==(const iterator &where) const
223 if (where.hash == this->hash
224 && where.end == this->end
227 ((where.curbucket == this->curbucket)
228 && (where.iter == iter))
233 bool operator !=(const iterator &where) const
235 return !( (*this) == where );
240 if (end || !hash || curbucket < 0 || curbucket >= static_cast<int>(hash->m_numBuckets))
243 // Remove this element and move to the next one
244 iterator tmp = *this;
246 hash->m_Buckets[curbucket]->erase(iter);
249 // :TODO: Maybe refactor to a lower size if required
254 if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
258 for (int i=0; i<(int)hash->m_numBuckets; i++)
260 if (hash->m_Buckets[i])
262 iter = hash->m_Buckets[i]->begin();
263 if (iter == hash->m_Buckets[i]->end())
272 if (iter != hash->m_Buckets[curbucket]->end())
274 if (iter == hash->m_Buckets[curbucket]->end())
276 int oldbucket = curbucket;
277 for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
279 if (hash->m_Buckets[i])
281 iter = hash->m_Buckets[i]->begin();
282 if (iter == hash->m_Buckets[i]->end())
288 if (curbucket == oldbucket)
295 typename SourceHook::List<THashNode *>::iterator iter;
303 const_iterator() : curbucket(-1), hash(NULL), end(true)
306 const_iterator(const THash *h) : curbucket(-1), hash(h), end(false)
314 const_iterator & operator++()
320 const_iterator operator++(int)
326 const THashNode & operator * () const
330 const THashNode * operator ->() const
334 bool operator ==(const const_iterator &where) const
336 if (where.hash == this->hash
337 && where.end == this->end
340 ((where.curbucket == this->curbucket)
341 && (where.iter == iter))
346 bool operator !=(const const_iterator &where) const
348 return !( (*this) == where );
353 if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
357 for (int i=0; i<(int)hash->m_numBuckets; i++)
359 if (hash->m_Buckets[i])
361 iter = hash->m_Buckets[i]->begin();
362 if (iter == hash->m_Buckets[i]->end())
371 if (iter != hash->m_Buckets[curbucket]->end())
373 if (iter == hash->m_Buckets[curbucket]->end())
375 int oldbucket = curbucket;
376 for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
378 if (hash->m_Buckets[i])
380 iter = hash->m_Buckets[i]->begin();
381 if (iter == hash->m_Buckets[i]->end())
387 if (curbucket == oldbucket)
394 typename SourceHook::List<THashNode *>::iterator iter;
401 return iterator(this);
410 const_iterator begin() const
412 return const_iterator(this);
414 const_iterator end() const
421 template <typename U>
422 iterator find(const U & u) const
424 iterator b = begin();
426 for (iterator iter = b; iter != e; iter++)
428 if ( (*iter).key == u )
433 template <typename U>
434 iterator find(const U & u)
436 iterator b = begin();
438 for (iterator iter = b; iter != e; iter++)
440 if ( (*iter).key == u )
446 iterator erase(iterator where)
451 template <typename U>
452 void erase(const U & u)
454 iterator iter = find(u);
466 #endif //_INCLUDE_SH_TINYHASH_H_