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 >= static_cast<int>(hash->m_numBuckets))
244 for (int i=0; i<(int)hash->m_numBuckets; i++)
246 if (hash->m_Buckets[i])
248 iter = hash->m_Buckets[i]->begin();
249 if (iter == hash->m_Buckets[i]->end())
258 if (iter != hash->m_Buckets[curbucket]->end())
260 if (iter == hash->m_Buckets[curbucket]->end())
262 int oldbucket = curbucket;
263 for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
265 if (hash->m_Buckets[i])
267 iter = hash->m_Buckets[i]->begin();
268 if (iter == hash->m_Buckets[i]->end())
274 if (curbucket == oldbucket)
281 typename SourceHook::List<THashNode *>::iterator iter;
289 const_iterator() : curbucket(-1), hash(NULL), end(true)
292 const_iterator(const THash *h) : curbucket(-1), hash(h), end(false)
300 const_iterator & operator++()
306 const_iterator operator++(int)
312 const THashNode & operator * () const
316 const THashNode * operator ->() const
320 bool operator ==(const const_iterator &where) const
322 if (where.hash == this->hash
323 && where.end == this->end
326 ((where.curbucket == this->curbucket)
327 && (where.iter == iter))
332 bool operator !=(const const_iterator &where) const
334 return !( (*this) == where );
339 if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
343 for (int i=0; i<(int)hash->m_numBuckets; i++)
345 if (hash->m_Buckets[i])
347 iter = hash->m_Buckets[i]->begin();
348 if (iter == hash->m_Buckets[i]->end())
357 if (iter != hash->m_Buckets[curbucket]->end())
359 if (iter == hash->m_Buckets[curbucket]->end())
361 int oldbucket = curbucket;
362 for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
364 if (hash->m_Buckets[i])
366 iter = hash->m_Buckets[i]->begin();
367 if (iter == hash->m_Buckets[i]->end())
373 if (curbucket == oldbucket)
380 typename SourceHook::List<THashNode *>::iterator iter;
387 return iterator(this);
396 const_iterator begin() const
398 return const_iterator(this);
400 const_iterator end() const
407 template <typename U>
408 iterator find(const U & u) const
410 iterator b = begin();
412 for (iterator iter = b; iter != e; iter++)
414 if ( (*iter).key == u )
419 template <typename U>
420 iterator find(const U & u)
422 iterator b = begin();
424 for (iterator iter = b; iter != e; iter++)
426 if ( (*iter).key == u )
438 #endif //_INCLUDE_SH_TINYHASH_H_