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_numBuckets(0), m_Buckets(NULL)
57 V & operator [](const K & key)
59 THashNode *pNode = _FindOrInsert(key);
63 THashNode *_FindOrInsert(const K & key)
65 size_t place = HashFunction(key) % m_numBuckets;
66 THashNode *pNode = NULL;
67 if (!m_Buckets[place])
69 m_Buckets[place] = new List<THashNode *>;
70 pNode = new THashNode(key, V());
71 m_Buckets[place]->push_back(pNode);
72 m_percentUsed += (1.0f / (float)m_numBuckets);
74 List<THashNode *>::iterator iter;
75 for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++)
77 if (Compare((*iter)->key, key) == 0)
81 pNode = new THashNode(key, V());
82 m_Buckets[place]->push_back(pNode);
84 if (PercentUsed() > 0.75f)
93 m_numBuckets = _T_INIT_HASH_SIZE;
94 m_Buckets = new NodePtr[m_numBuckets];
95 for (size_t i=0; i<m_numBuckets; i++)
98 size_t oldSize = m_numBuckets;
100 List<THashNode *>::iterator iter;
102 THashNode *pHashNode;
103 NodePtr *temp = new NodePtr[m_numBuckets];
104 for (size_t i=0; i<m_numBuckets; i++)
106 //look in old hash table
107 for (size_t i=0; i<oldSize; i++)
109 //does a bucket have anything?
112 //go through the list of items
113 for (iter = m_Buckets[i]->begin(); iter != m_Buckets[i]->end(); iter++)
116 //rehash it with the new bucket filter
117 place = HashFunction(pHashNode->key) % m_numBuckets;
118 //add it to the new hash table
121 temp[place] = new List<THashNode *>;
122 m_percentUsed += (1.0f / (float)m_numBuckets);
124 temp[place]->push_back(pHashNode);
126 //delete that bucket!
131 //reassign bucket table
137 friend class iterator;
142 iterator() : hash(NULL), end(true)
145 iterator(THash *h) : hash(h), end(false)
153 iterator & operator++()
159 iterator operator++(int)
165 THashNode & operator * () const
169 THashNode & operator * ()
173 THashNode * operator ->() const
177 THashNode * operator ->()
181 bool operator ==(const iterator &where) const
183 if (where.hash == this->hash
184 && where.end == this->end
187 ((where.curbucket == this->curbucket)
188 && (where.iter == iter))
193 bool operator !=(const iterator &where) const
195 return !( (*this) == where );
204 for (int i=0; i<(int)hash->m_numBuckets; i++)
206 if (hash->m_Buckets[i])
208 iter = hash->m_Buckets[i]->begin();
209 if (iter == hash->m_Buckets[i]->end())
218 if (iter != hash->m_Buckets[curbucket]->end())
220 if (iter == hash->m_Buckets[curbucket]->end())
222 int oldbucket = curbucket;
223 for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
225 if (hash->m_Buckets[i])
227 iter = hash->m_Buckets[i]->begin();
228 if (iter == hash->m_Buckets[i]->end())
234 if (curbucket == oldbucket)
241 typename SourceHook::List<THashNode *>::iterator iter;
248 return iterator(this);
256 template <typename U>
257 iterator find(const U & u) const
259 iterator b = begin();
261 for (iterator iter = b; iter != e; iter++)
263 if ( (*iter).key == u )
268 template <typename U>
269 iterator find(const U & u)
271 iterator b = begin();
273 for (iterator iter = b; iter != e; iter++)
275 if ( (*iter).key == u )
287 #endif //_INCLUDE_SH_TINYHASH_H_