|
dvander@102
|
1 |
/* ======== SourceMM ======== |
|
dvander@102
|
2 |
* Copyright (C) 2004-2005 Metamod:Source Development Team |
|
dvander@102
|
3 |
* No warranties of any kind |
|
dvander@102
|
4 |
* |
|
dvander@102
|
5 |
* License: zlib/libpng |
|
dvander@102
|
6 |
* |
|
dvander@102
|
7 |
* Author(s): David "BAILOPAN" Anderson |
|
dvander@102
|
8 |
* ============================ |
|
dvander@102
|
9 |
*/ |
|
dvander@102
|
10 |
|
|
dvander@102
|
11 |
#ifndef _INCLUDE_SH_TINYHASH_H_ |
|
dvander@102
|
12 |
#define _INCLUDE_SH_TINYHASH_H_ |
|
dvander@102
|
13 |
|
|
dvander@102
|
14 |
#include "sh_list.h" |
|
dvander@102
|
15 |
|
|
dvander@102
|
16 |
#define _T_INIT_HASH_SIZE 32 |
|
dvander@102
|
17 |
|
|
dvander@102
|
18 |
namespace SourceHook |
|
dvander@102
|
19 |
{ |
|
dvander@102
|
20 |
template <class K> |
|
dvander@102
|
21 |
int HashFunction(const K & k); |
|
dvander@102
|
22 |
|
|
dvander@102
|
23 |
template <class K> |
|
dvander@102
|
24 |
int Compare(const K & k1, const K & k2); |
|
dvander@102
|
25 |
|
|
dvander@102
|
26 |
/** |
|
dvander@102
|
27 |
* This is a tiny, growable hash class. |
|
dvander@102
|
28 |
* Meant for quick and dirty dictionaries only! |
|
dvander@102
|
29 |
*/ |
|
dvander@102
|
30 |
template <class K, class V> |
|
dvander@102
|
31 |
class THash |
|
dvander@102
|
32 |
{ |
|
dvander@102
|
33 |
public: |
|
dvander@102
|
34 |
struct THashNode |
|
dvander@102
|
35 |
{ |
|
dvander@102
|
36 |
THashNode(const K & k, const V & v) : |
|
dvander@102
|
37 |
key(k), val(v) |
|
dvander@102
|
38 |
{ |
|
dvander@102
|
39 |
}; |
|
dvander@102
|
40 |
K key; |
|
dvander@102
|
41 |
V val; |
|
dvander@102
|
42 |
}; |
|
dvander@102
|
43 |
typedef List<THashNode *> * NodePtr; |
|
dvander@102
|
44 |
public: |
|
dvander@102
|
45 |
THash() : m_numBuckets(0), m_Buckets(NULL) |
|
dvander@102
|
46 |
{ |
|
dvander@102
|
47 |
_Refactor(); |
|
dvander@102
|
48 |
} |
|
dvander@102
|
49 |
size_t GetBuckets() |
|
dvander@102
|
50 |
{ |
|
dvander@102
|
51 |
return m_numBuckets; |
|
dvander@102
|
52 |
} |
|
dvander@102
|
53 |
float PercentUsed() |
|
dvander@102
|
54 |
{ |
|
dvander@102
|
55 |
return m_percentUsed; |
|
dvander@102
|
56 |
} |
|
dvander@102
|
57 |
V & operator [](const K & key) |
|
dvander@102
|
58 |
{ |
|
dvander@102
|
59 |
THashNode *pNode = _FindOrInsert(key); |
|
dvander@102
|
60 |
return pNode->val; |
|
dvander@102
|
61 |
} |
|
dvander@102
|
62 |
private: |
|
dvander@102
|
63 |
THashNode *_FindOrInsert(const K & key) |
|
dvander@102
|
64 |
{ |
|
dvander@102
|
65 |
size_t place = HashFunction(key) % m_numBuckets; |
|
dvander@102
|
66 |
THashNode *pNode = NULL; |
|
dvander@102
|
67 |
if (!m_Buckets[place]) |
|
dvander@102
|
68 |
{ |
|
dvander@102
|
69 |
m_Buckets[place] = new List<THashNode *>; |
|
dvander@102
|
70 |
pNode = new THashNode(key, V()); |
|
dvander@102
|
71 |
m_Buckets[place]->push_back(pNode); |
|
dvander@102
|
72 |
m_percentUsed += (1.0f / (float)m_numBuckets); |
|
dvander@102
|
73 |
} else { |
|
dvander@102
|
74 |
List<THashNode *>::iterator iter; |
|
dvander@102
|
75 |
for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++) |
|
dvander@102
|
76 |
{ |
|
dvander@102
|
77 |
if (Compare((*iter)->key, key) == 0) |
|
dvander@102
|
78 |
return (*iter); |
|
dvander@102
|
79 |
} |
|
dvander@102
|
80 |
//node does not exist |
|
dvander@102
|
81 |
pNode = new THashNode(key, V()); |
|
dvander@102
|
82 |
m_Buckets[place]->push_back(pNode); |
|
dvander@102
|
83 |
} |
|
dvander@102
|
84 |
if (PercentUsed() > 0.75f) |
|
dvander@102
|
85 |
_Refactor(); |
|
dvander@102
|
86 |
return pNode; |
|
dvander@102
|
87 |
} |
|
dvander@102
|
88 |
void _Refactor() |
|
dvander@102
|
89 |
{ |
|
dvander@102
|
90 |
m_percentUsed = 0.0f; |
|
dvander@102
|
91 |
if (!m_numBuckets) |
|
dvander@102
|
92 |
{ |
|
dvander@102
|
93 |
m_numBuckets = _T_INIT_HASH_SIZE; |
|
dvander@102
|
94 |
m_Buckets = new NodePtr[m_numBuckets]; |
|
dvander@102
|
95 |
for (size_t i=0; i<m_numBuckets; i++) |
|
dvander@102
|
96 |
m_Buckets[i] = NULL; |
|
dvander@102
|
97 |
} else { |
|
dvander@102
|
98 |
size_t oldSize = m_numBuckets; |
|
dvander@102
|
99 |
m_numBuckets *= 2; |
|
dvander@102
|
100 |
List<THashNode *>::iterator iter; |
|
dvander@102
|
101 |
size_t place; |
|
dvander@102
|
102 |
THashNode *pHashNode; |
|
dvander@102
|
103 |
NodePtr *temp = new NodePtr[m_numBuckets]; |
|
dvander@102
|
104 |
for (size_t i=0; i<m_numBuckets; i++) |
|
dvander@102
|
105 |
temp[i] = NULL; |
|
dvander@102
|
106 |
//look in old hash table |
|
dvander@102
|
107 |
for (size_t i=0; i<oldSize; i++) |
|
dvander@102
|
108 |
{ |
|
dvander@102
|
109 |
//does a bucket have anything? |
|
dvander@102
|
110 |
if (m_Buckets[i]) |
|
dvander@102
|
111 |
{ |
|
dvander@102
|
112 |
//go through the list of items |
|
dvander@102
|
113 |
for (iter = m_Buckets[i]->begin(); iter != m_Buckets[i]->end(); iter++) |
|
dvander@102
|
114 |
{ |
|
dvander@102
|
115 |
pHashNode = (*iter); |
|
dvander@102
|
116 |
//rehash it with the new bucket filter |
|
dvander@102
|
117 |
place = HashFunction(pHashNode->key) % m_numBuckets; |
|
dvander@102
|
118 |
//add it to the new hash table |
|
dvander@102
|
119 |
if (!temp[place]) |
|
dvander@102
|
120 |
{ |
|
dvander@102
|
121 |
temp[place] = new List<THashNode *>; |
|
dvander@102
|
122 |
m_percentUsed += (1.0f / (float)m_numBuckets); |
|
dvander@102
|
123 |
} |
|
dvander@102
|
124 |
temp[place]->push_back(pHashNode); |
|
dvander@102
|
125 |
} |
|
dvander@102
|
126 |
//delete that bucket! |
|
dvander@102
|
127 |
delete m_Buckets[i]; |
|
dvander@102
|
128 |
m_Buckets[i] = NULL; |
|
dvander@102
|
129 |
} |
|
dvander@102
|
130 |
} |
|
dvander@102
|
131 |
//reassign bucket table |
|
dvander@102
|
132 |
delete [] m_Buckets; |
|
dvander@102
|
133 |
m_Buckets = temp; |
|
dvander@102
|
134 |
} |
|
dvander@102
|
135 |
} |
|
dvander@102
|
136 |
public: |
|
dvander@102
|
137 |
friend class iterator; |
|
dvander@102
|
138 |
class iterator |
|
dvander@102
|
139 |
{ |
|
dvander@102
|
140 |
friend class THash; |
|
dvander@102
|
141 |
public: |
|
dvander@102
|
142 |
iterator() : hash(NULL), end(true) |
|
dvander@102
|
143 |
{ |
|
dvander@102
|
144 |
}; |
|
dvander@102
|
145 |
iterator(THash *h) : hash(h), end(false) |
|
dvander@102
|
146 |
{ |
|
dvander@102
|
147 |
if (!h->m_Buckets) |
|
dvander@102
|
148 |
end = true; |
|
dvander@102
|
149 |
else |
|
dvander@102
|
150 |
_Inc(); |
|
dvander@102
|
151 |
}; |
|
dvander@102
|
152 |
//pre increment |
|
dvander@102
|
153 |
iterator & operator++() |
|
dvander@102
|
154 |
{ |
|
dvander@102
|
155 |
_Inc(); |
|
dvander@102
|
156 |
return *this; |
|
dvander@102
|
157 |
} |
|
dvander@102
|
158 |
//post increment |
|
dvander@102
|
159 |
iterator operator++(int) |
|
dvander@102
|
160 |
{ |
|
dvander@102
|
161 |
iterator old(*this); |
|
dvander@102
|
162 |
_Inc(); |
|
dvander@102
|
163 |
return old; |
|
dvander@102
|
164 |
} |
|
dvander@102
|
165 |
THashNode & operator * () const |
|
dvander@102
|
166 |
{ |
|
dvander@102
|
167 |
return *(*iter); |
|
dvander@102
|
168 |
} |
|
dvander@102
|
169 |
THashNode & operator * () |
|
dvander@102
|
170 |
{ |
|
dvander@102
|
171 |
return *(*iter); |
|
dvander@102
|
172 |
} |
|
dvander@102
|
173 |
THashNode * operator ->() const |
|
dvander@102
|
174 |
{ |
|
dvander@102
|
175 |
return (*iter); |
|
dvander@102
|
176 |
} |
|
dvander@102
|
177 |
THashNode * operator ->() |
|
dvander@102
|
178 |
{ |
|
dvander@102
|
179 |
return (*iter); |
|
dvander@102
|
180 |
} |
|
dvander@102
|
181 |
bool operator ==(const iterator &where) const |
|
dvander@102
|
182 |
{ |
|
dvander@102
|
183 |
if (where.hash == this->hash |
|
dvander@102
|
184 |
&& where.end == this->end |
|
dvander@102
|
185 |
&& |
|
dvander@102
|
186 |
(this->end || |
|
dvander@102
|
187 |
((where.curbucket == this->curbucket) |
|
dvander@102
|
188 |
&& (where.iter == iter)) |
|
dvander@102
|
189 |
)) |
|
dvander@102
|
190 |
return true; |
|
dvander@102
|
191 |
return false; |
|
dvander@102
|
192 |
} |
|
dvander@102
|
193 |
bool operator !=(const iterator &where) const |
|
dvander@102
|
194 |
{ |
|
dvander@102
|
195 |
return !( (*this) == where ); |
|
dvander@102
|
196 |
} |
|
dvander@102
|
197 |
private: |
|
dvander@102
|
198 |
void _Inc() |
|
dvander@102
|
199 |
{ |
|
dvander@102
|
200 |
if (end || !hash) |
|
dvander@102
|
201 |
return; |
|
dvander@102
|
202 |
if (curbucket < 0) |
|
dvander@102
|
203 |
{ |
|
dvander@102
|
204 |
for (int i=0; i<(int)hash->m_numBuckets; i++) |
|
dvander@102
|
205 |
{ |
|
dvander@102
|
206 |
if (hash->m_Buckets[i]) |
|
dvander@102
|
207 |
{ |
|
dvander@102
|
208 |
iter = hash->m_Buckets[i]->begin(); |
|
dvander@102
|
209 |
if (iter == hash->m_Buckets[i]->end()) |
|
dvander@102
|
210 |
continue; |
|
dvander@102
|
211 |
curbucket = i; |
|
dvander@102
|
212 |
break; |
|
dvander@102
|
213 |
} |
|
dvander@102
|
214 |
} |
|
dvander@102
|
215 |
if (curbucket < 0) |
|
dvander@102
|
216 |
end = true; |
|
dvander@102
|
217 |
} else { |
|
dvander@102
|
218 |
if (iter != hash->m_Buckets[curbucket]->end()) |
|
dvander@102
|
219 |
iter++; |
|
dvander@102
|
220 |
if (iter == hash->m_Buckets[curbucket]->end()) |
|
dvander@102
|
221 |
{ |
|
dvander@102
|
222 |
int oldbucket = curbucket; |
|
dvander@102
|
223 |
for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++) |
|
dvander@102
|
224 |
{ |
|
dvander@102
|
225 |
if (hash->m_Buckets[i]) |
|
dvander@102
|
226 |
{ |
|
dvander@102
|
227 |
iter = hash->m_Buckets[i]->begin(); |
|
dvander@102
|
228 |
if (iter == hash->m_Buckets[i]->end()) |
|
dvander@102
|
229 |
continue; |
|
dvander@102
|
230 |
curbucket = i; |
|
dvander@102
|
231 |
break; |
|
dvander@102
|
232 |
} |
|
dvander@102
|
233 |
} |
|
dvander@102
|
234 |
if (curbucket == oldbucket) |
|
dvander@102
|
235 |
end = true; |
|
dvander@102
|
236 |
} |
|
dvander@102
|
237 |
} |
|
dvander@102
|
238 |
} |
|
dvander@102
|
239 |
private: |
|
dvander@102
|
240 |
int curbucket; |
|
dvander@102
|
241 |
typename SourceHook::List<THashNode *>::iterator iter; |
|
dvander@102
|
242 |
THash *hash; |
|
dvander@102
|
243 |
bool end; |
|
dvander@102
|
244 |
}; |
|
dvander@102
|
245 |
public: |
|
dvander@102
|
246 |
iterator begin() |
|
dvander@102
|
247 |
{ |
|
dvander@102
|
248 |
return iterator(this); |
|
dvander@102
|
249 |
} |
|
dvander@102
|
250 |
iterator end() |
|
dvander@102
|
251 |
{ |
|
dvander@102
|
252 |
iterator iter; |
|
dvander@102
|
253 |
iter.hash = this; |
|
dvander@102
|
254 |
return iter; |
|
dvander@102
|
255 |
} |
|
dvander@102
|
256 |
template <typename U> |
|
dvander@102
|
257 |
iterator find(const U & u) const |
|
dvander@102
|
258 |
{ |
|
dvander@102
|
259 |
iterator b = begin(); |
|
dvander@102
|
260 |
iterator e = end(); |
|
dvander@102
|
261 |
for (iterator iter = b; iter != e; iter++) |
|
dvander@102
|
262 |
{ |
|
dvander@102
|
263 |
if ( (*iter).key == u ) |
|
dvander@102
|
264 |
return iter; |
|
dvander@102
|
265 |
} |
|
dvander@102
|
266 |
return end(); |
|
dvander@102
|
267 |
} |
|
dvander@102
|
268 |
template <typename U> |
|
dvander@102
|
269 |
iterator find(const U & u) |
|
dvander@102
|
270 |
{ |
|
dvander@102
|
271 |
iterator b = begin(); |
|
dvander@102
|
272 |
iterator e = end(); |
|
dvander@102
|
273 |
for (iterator iter = b; iter != e; iter++) |
|
dvander@102
|
274 |
{ |
|
dvander@102
|
275 |
if ( (*iter).key == u ) |
|
dvander@102
|
276 |
return iter; |
|
dvander@102
|
277 |
} |
|
dvander@102
|
278 |
return end(); |
|
dvander@102
|
279 |
} |
|
dvander@102
|
280 |
private: |
|
dvander@102
|
281 |
NodePtr *m_Buckets; |
|
dvander@102
|
282 |
size_t m_numBuckets; |
|
dvander@102
|
283 |
float m_percentUsed; |
|
dvander@102
|
284 |
}; |
|
dvander@102
|
285 |
}; |
|
dvander@102
|
286 |
|
|
dvander@102
|
287 |
#endif //_INCLUDE_SH_TINYHASH_H_ |