|
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 |
*/ |
|
pavolmarko@117
|
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 |
{ |
|
pavolmarko@117
|
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: |
|
pavolmarko@111
|
45 |
THash() : m_Buckets(NULL), m_numBuckets(0), m_percentUsed(0.0f) |
|
pavolmarko@111
|
46 |
{ |
|
pavolmarko@111
|
47 |
_Refactor(); |
|
pavolmarko@111
|
48 |
} |
|
pavolmarko@111
|
49 |
THash(const THash &other) : m_Buckets(new NodePtr[other.m_numBuckets]), |
|
pavolmarko@111
|
50 |
m_numBuckets(other.m_numBuckets), m_percentUsed(other.m_percentUsed) |
|
pavolmarko@111
|
51 |
{ |
|
pavolmarko@111
|
52 |
for (size_t i=0; i<m_numBuckets; i++) |
|
pavolmarko@111
|
53 |
m_Buckets[i] = NULL; |
|
pavolmarko@111
|
54 |
for (const_iterator iter = other.begin(); iter != other.end(); ++iter) |
|
pavolmarko@111
|
55 |
_FindOrInsert(iter->key)->val = iter->val; |
|
pavolmarko@111
|
56 |
} |
|
pavolmarko@111
|
57 |
void operator=(const THash &other) |
|
dvander@102
|
58 |
{ |
|
pavolmarko@111
|
59 |
clear(); |
|
pavolmarko@111
|
60 |
for (const_iterator iter = other.begin(); iter != other.end(); ++iter) |
|
pavolmarko@111
|
61 |
_FindOrInsert(iter->key)->val = iter->val; |
|
pavolmarko@111
|
62 |
} |
|
pavolmarko@111
|
63 |
|
|
pavolmarko@111
|
64 |
~THash() |
|
pavolmarko@111
|
65 |
{ |
|
dvander@115
|
66 |
_Clear(); |
|
pavolmarko@111
|
67 |
} |
|
pavolmarko@111
|
68 |
void clear() |
|
pavolmarko@111
|
69 |
{ |
|
dvander@115
|
70 |
_Clear(); |
|
dvander@102
|
71 |
_Refactor(); |
|
dvander@102
|
72 |
} |
|
dvander@102
|
73 |
size_t GetBuckets() |
|
dvander@102
|
74 |
{ |
|
dvander@102
|
75 |
return m_numBuckets; |
|
dvander@102
|
76 |
} |
|
dvander@102
|
77 |
float PercentUsed() |
|
dvander@102
|
78 |
{ |
|
dvander@102
|
79 |
return m_percentUsed; |
|
dvander@102
|
80 |
} |
|
dvander@102
|
81 |
V & operator [](const K & key) |
|
dvander@102
|
82 |
{ |
|
dvander@102
|
83 |
THashNode *pNode = _FindOrInsert(key); |
|
dvander@102
|
84 |
return pNode->val; |
|
dvander@102
|
85 |
} |
|
dvander@102
|
86 |
private: |
|
dvander@115
|
87 |
void _Clear() |
|
dvander@115
|
88 |
{ |
|
dvander@150
|
89 |
typename List<THashNode *>::iterator iter, end; |
|
dvander@115
|
90 |
for (size_t i=0; i<m_numBuckets; i++) |
|
dvander@115
|
91 |
{ |
|
dvander@115
|
92 |
if (m_Buckets[i]) |
|
dvander@115
|
93 |
{ |
|
dvander@150
|
94 |
end = m_Buckets[i]->end(); |
|
dvander@150
|
95 |
iter = m_Buckets[i]->begin(); |
|
dvander@150
|
96 |
while (iter != end) |
|
dvander@150
|
97 |
{ |
|
dvander@150
|
98 |
delete (*iter); |
|
dvander@150
|
99 |
iter++; |
|
dvander@150
|
100 |
} |
|
dvander@115
|
101 |
delete m_Buckets[i]; |
|
dvander@115
|
102 |
m_Buckets[i] = NULL; |
|
dvander@115
|
103 |
} |
|
dvander@115
|
104 |
} |
|
dvander@115
|
105 |
if (m_Buckets) |
|
dvander@115
|
106 |
delete [] m_Buckets; |
|
dvander@115
|
107 |
m_Buckets = NULL; |
|
dvander@115
|
108 |
m_numBuckets = 0; |
|
dvander@115
|
109 |
} |
|
dvander@102
|
110 |
THashNode *_FindOrInsert(const K & key) |
|
dvander@102
|
111 |
{ |
|
dvander@102
|
112 |
size_t place = HashFunction(key) % m_numBuckets; |
|
dvander@102
|
113 |
THashNode *pNode = NULL; |
|
dvander@102
|
114 |
if (!m_Buckets[place]) |
|
dvander@102
|
115 |
{ |
|
dvander@102
|
116 |
m_Buckets[place] = new List<THashNode *>; |
|
dvander@102
|
117 |
pNode = new THashNode(key, V()); |
|
dvander@102
|
118 |
m_Buckets[place]->push_back(pNode); |
|
dvander@102
|
119 |
m_percentUsed += (1.0f / (float)m_numBuckets); |
|
dvander@102
|
120 |
} else { |
|
dvander@107
|
121 |
typename List<THashNode *>::iterator iter; |
|
dvander@102
|
122 |
for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++) |
|
dvander@102
|
123 |
{ |
|
dvander@102
|
124 |
if (Compare((*iter)->key, key) == 0) |
|
dvander@102
|
125 |
return (*iter); |
|
dvander@102
|
126 |
} |
|
dvander@102
|
127 |
//node does not exist |
|
dvander@102
|
128 |
pNode = new THashNode(key, V()); |
|
dvander@102
|
129 |
m_Buckets[place]->push_back(pNode); |
|
dvander@102
|
130 |
} |
|
dvander@102
|
131 |
if (PercentUsed() > 0.75f) |
|
dvander@102
|
132 |
_Refactor(); |
|
dvander@102
|
133 |
return pNode; |
|
dvander@102
|
134 |
} |
|
dvander@102
|
135 |
void _Refactor() |
|
dvander@102
|
136 |
{ |
|
dvander@102
|
137 |
m_percentUsed = 0.0f; |
|
dvander@102
|
138 |
if (!m_numBuckets) |
|
dvander@102
|
139 |
{ |
|
dvander@102
|
140 |
m_numBuckets = _T_INIT_HASH_SIZE; |
|
dvander@102
|
141 |
m_Buckets = new NodePtr[m_numBuckets]; |
|
dvander@102
|
142 |
for (size_t i=0; i<m_numBuckets; i++) |
|
dvander@102
|
143 |
m_Buckets[i] = NULL; |
|
dvander@102
|
144 |
} else { |
|
dvander@102
|
145 |
size_t oldSize = m_numBuckets; |
|
dvander@102
|
146 |
m_numBuckets *= 2; |
|
dvander@107
|
147 |
typename List<THashNode *>::iterator iter; |
|
dvander@102
|
148 |
size_t place; |
|
dvander@102
|
149 |
THashNode *pHashNode; |
|
pavolmarko@117
|
150 |
NodePtr *temp = new NodePtr[m_numBuckets]; |
|
dvander@102
|
151 |
for (size_t i=0; i<m_numBuckets; i++) |
|
dvander@102
|
152 |
temp[i] = NULL; |
|
dvander@102
|
153 |
//look in old hash table |
|
dvander@102
|
154 |
for (size_t i=0; i<oldSize; i++) |
|
dvander@102
|
155 |
{ |
|
dvander@102
|
156 |
//does a bucket have anything? |
|
dvander@102
|
157 |
if (m_Buckets[i]) |
|
dvander@102
|
158 |
{ |
|
dvander@102
|
159 |
//go through the list of items |
|
dvander@102
|
160 |
for (iter = m_Buckets[i]->begin(); iter != m_Buckets[i]->end(); iter++) |
|
dvander@102
|
161 |
{ |
|
dvander@102
|
162 |
pHashNode = (*iter); |
|
dvander@102
|
163 |
//rehash it with the new bucket filter |
|
dvander@102
|
164 |
place = HashFunction(pHashNode->key) % m_numBuckets; |
|
dvander@102
|
165 |
//add it to the new hash table |
|
dvander@102
|
166 |
if (!temp[place]) |
|
dvander@102
|
167 |
{ |
|
dvander@102
|
168 |
temp[place] = new List<THashNode *>; |
|
dvander@102
|
169 |
m_percentUsed += (1.0f / (float)m_numBuckets); |
|
dvander@102
|
170 |
} |
|
dvander@102
|
171 |
temp[place]->push_back(pHashNode); |
|
dvander@102
|
172 |
} |
|
dvander@102
|
173 |
//delete that bucket! |
|
dvander@102
|
174 |
delete m_Buckets[i]; |
|
dvander@102
|
175 |
m_Buckets[i] = NULL; |
|
dvander@102
|
176 |
} |
|
dvander@102
|
177 |
} |
|
dvander@102
|
178 |
//reassign bucket table |
|
dvander@102
|
179 |
delete [] m_Buckets; |
|
dvander@102
|
180 |
m_Buckets = temp; |
|
dvander@102
|
181 |
} |
|
dvander@102
|
182 |
} |
|
dvander@102
|
183 |
public: |
|
dvander@102
|
184 |
friend class iterator; |
|
pavolmarko@111
|
185 |
friend class const_iterator; |
|
dvander@102
|
186 |
class iterator |
|
dvander@102
|
187 |
{ |
|
dvander@102
|
188 |
friend class THash; |
|
dvander@102
|
189 |
public: |
|
pavolmarko@111
|
190 |
iterator() : curbucket(-1), hash(NULL), end(true) |
|
dvander@102
|
191 |
{ |
|
dvander@102
|
192 |
}; |
|
pavolmarko@111
|
193 |
iterator(THash *h) : curbucket(-1), hash(h), end(false) |
|
dvander@102
|
194 |
{ |
|
dvander@102
|
195 |
if (!h->m_Buckets) |
|
dvander@102
|
196 |
end = true; |
|
dvander@102
|
197 |
else |
|
dvander@102
|
198 |
_Inc(); |
|
dvander@102
|
199 |
}; |
|
dvander@102
|
200 |
//pre increment |
|
dvander@102
|
201 |
iterator & operator++() |
|
dvander@102
|
202 |
{ |
|
dvander@102
|
203 |
_Inc(); |
|
dvander@102
|
204 |
return *this; |
|
dvander@102
|
205 |
} |
|
dvander@102
|
206 |
//post increment |
|
dvander@102
|
207 |
iterator operator++(int) |
|
dvander@102
|
208 |
{ |
|
dvander@102
|
209 |
iterator old(*this); |
|
dvander@102
|
210 |
_Inc(); |
|
dvander@102
|
211 |
return old; |
|
dvander@102
|
212 |
} |
|
pavolmarko@111
|
213 |
const THashNode & operator * () const |
|
dvander@102
|
214 |
{ |
|
dvander@102
|
215 |
return *(*iter); |
|
dvander@102
|
216 |
} |
|
dvander@102
|
217 |
THashNode & operator * () |
|
dvander@102
|
218 |
{ |
|
dvander@102
|
219 |
return *(*iter); |
|
dvander@102
|
220 |
} |
|
pavolmarko@111
|
221 |
const THashNode * operator ->() const |
|
dvander@102
|
222 |
{ |
|
dvander@102
|
223 |
return (*iter); |
|
dvander@102
|
224 |
} |
|
dvander@102
|
225 |
THashNode * operator ->() |
|
dvander@102
|
226 |
{ |
|
dvander@102
|
227 |
return (*iter); |
|
dvander@102
|
228 |
} |
|
dvander@102
|
229 |
bool operator ==(const iterator &where) const |
|
dvander@102
|
230 |
{ |
|
dvander@102
|
231 |
if (where.hash == this->hash |
|
dvander@102
|
232 |
&& where.end == this->end |
|
pavolmarko@117
|
233 |
&& |
|
pavolmarko@117
|
234 |
(this->end || |
|
pavolmarko@117
|
235 |
((where.curbucket == this->curbucket) |
|
pavolmarko@117
|
236 |
&& (where.iter == iter)) |
|
dvander@102
|
237 |
)) |
|
dvander@102
|
238 |
return true; |
|
dvander@102
|
239 |
return false; |
|
dvander@102
|
240 |
} |
|
dvander@102
|
241 |
bool operator !=(const iterator &where) const |
|
dvander@102
|
242 |
{ |
|
dvander@102
|
243 |
return !( (*this) == where ); |
|
dvander@102
|
244 |
} |
|
pavolmarko@117
|
245 |
|
|
pavolmarko@117
|
246 |
void erase() |
|
pavolmarko@117
|
247 |
{ |
|
pavolmarko@117
|
248 |
if (end || !hash || curbucket < 0 || curbucket >= static_cast<int>(hash->m_numBuckets)) |
|
pavolmarko@117
|
249 |
return; |
|
pavolmarko@117
|
250 |
|
|
pavolmarko@117
|
251 |
// Remove this element and move to the next one |
|
pavolmarko@117
|
252 |
iterator tmp = *this; |
|
pavolmarko@117
|
253 |
++tmp; |
|
dvander@151
|
254 |
delete (*iter); |
|
pavolmarko@117
|
255 |
hash->m_Buckets[curbucket]->erase(iter); |
|
pavolmarko@117
|
256 |
*this = tmp; |
|
pavolmarko@117
|
257 |
|
|
pavolmarko@117
|
258 |
// :TODO: Maybe refactor to a lower size if required |
|
pavolmarko@117
|
259 |
} |
|
dvander@102
|
260 |
private: |
|
dvander@102
|
261 |
void _Inc() |
|
dvander@102
|
262 |
{ |
|
pavolmarko@111
|
263 |
if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets)) |
|
dvander@102
|
264 |
return; |
|
dvander@102
|
265 |
if (curbucket < 0) |
|
dvander@102
|
266 |
{ |
|
dvander@102
|
267 |
for (int i=0; i<(int)hash->m_numBuckets; i++) |
|
dvander@102
|
268 |
{ |
|
dvander@102
|
269 |
if (hash->m_Buckets[i]) |
|
dvander@102
|
270 |
{ |
|
dvander@102
|
271 |
iter = hash->m_Buckets[i]->begin(); |
|
dvander@102
|
272 |
if (iter == hash->m_Buckets[i]->end()) |
|
dvander@102
|
273 |
continue; |
|
dvander@102
|
274 |
curbucket = i; |
|
dvander@102
|
275 |
break; |
|
dvander@102
|
276 |
} |
|
dvander@102
|
277 |
} |
|
dvander@102
|
278 |
if (curbucket < 0) |
|
dvander@102
|
279 |
end = true; |
|
dvander@102
|
280 |
} else { |
|
dvander@102
|
281 |
if (iter != hash->m_Buckets[curbucket]->end()) |
|
dvander@102
|
282 |
iter++; |
|
dvander@102
|
283 |
if (iter == hash->m_Buckets[curbucket]->end()) |
|
dvander@102
|
284 |
{ |
|
dvander@102
|
285 |
int oldbucket = curbucket; |
|
dvander@102
|
286 |
for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++) |
|
dvander@102
|
287 |
{ |
|
dvander@102
|
288 |
if (hash->m_Buckets[i]) |
|
dvander@102
|
289 |
{ |
|
dvander@102
|
290 |
iter = hash->m_Buckets[i]->begin(); |
|
dvander@102
|
291 |
if (iter == hash->m_Buckets[i]->end()) |
|
dvander@102
|
292 |
continue; |
|
dvander@102
|
293 |
curbucket = i; |
|
dvander@102
|
294 |
break; |
|
dvander@102
|
295 |
} |
|
dvander@102
|
296 |
} |
|
dvander@102
|
297 |
if (curbucket == oldbucket) |
|
dvander@102
|
298 |
end = true; |
|
dvander@102
|
299 |
} |
|
dvander@102
|
300 |
} |
|
dvander@102
|
301 |
} |
|
dvander@102
|
302 |
private: |
|
dvander@102
|
303 |
int curbucket; |
|
dvander@102
|
304 |
typename SourceHook::List<THashNode *>::iterator iter; |
|
dvander@102
|
305 |
THash *hash; |
|
dvander@102
|
306 |
bool end; |
|
dvander@102
|
307 |
}; |
|
pavolmarko@111
|
308 |
class const_iterator |
|
pavolmarko@111
|
309 |
{ |
|
pavolmarko@111
|
310 |
friend class THash; |
|
pavolmarko@111
|
311 |
public: |
|
pavolmarko@111
|
312 |
const_iterator() : curbucket(-1), hash(NULL), end(true) |
|
pavolmarko@111
|
313 |
{ |
|
pavolmarko@111
|
314 |
}; |
|
pavolmarko@111
|
315 |
const_iterator(const THash *h) : curbucket(-1), hash(h), end(false) |
|
pavolmarko@111
|
316 |
{ |
|
pavolmarko@111
|
317 |
if (!h->m_Buckets) |
|
pavolmarko@111
|
318 |
end = true; |
|
pavolmarko@111
|
319 |
else |
|
pavolmarko@111
|
320 |
_Inc(); |
|
pavolmarko@111
|
321 |
}; |
|
pavolmarko@111
|
322 |
//pre increment |
|
pavolmarko@111
|
323 |
const_iterator & operator++() |
|
pavolmarko@111
|
324 |
{ |
|
pavolmarko@111
|
325 |
_Inc(); |
|
pavolmarko@111
|
326 |
return *this; |
|
pavolmarko@111
|
327 |
} |
|
pavolmarko@111
|
328 |
//post increment |
|
pavolmarko@111
|
329 |
const_iterator operator++(int) |
|
pavolmarko@111
|
330 |
{ |
|
pavolmarko@111
|
331 |
iterator old(*this); |
|
pavolmarko@111
|
332 |
_Inc(); |
|
pavolmarko@111
|
333 |
return old; |
|
pavolmarko@111
|
334 |
} |
|
pavolmarko@111
|
335 |
const THashNode & operator * () const |
|
pavolmarko@111
|
336 |
{ |
|
pavolmarko@111
|
337 |
return *(*iter); |
|
pavolmarko@111
|
338 |
} |
|
pavolmarko@111
|
339 |
const THashNode * operator ->() const |
|
pavolmarko@111
|
340 |
{ |
|
pavolmarko@111
|
341 |
return (*iter); |
|
pavolmarko@111
|
342 |
} |
|
pavolmarko@111
|
343 |
bool operator ==(const const_iterator &where) const |
|
pavolmarko@111
|
344 |
{ |
|
pavolmarko@111
|
345 |
if (where.hash == this->hash |
|
pavolmarko@111
|
346 |
&& where.end == this->end |
|
pavolmarko@117
|
347 |
&& |
|
pavolmarko@117
|
348 |
(this->end || |
|
pavolmarko@117
|
349 |
((where.curbucket == this->curbucket) |
|
pavolmarko@117
|
350 |
&& (where.iter == iter)) |
|
pavolmarko@111
|
351 |
)) |
|
pavolmarko@111
|
352 |
return true; |
|
pavolmarko@111
|
353 |
return false; |
|
pavolmarko@111
|
354 |
} |
|
pavolmarko@111
|
355 |
bool operator !=(const const_iterator &where) const |
|
pavolmarko@111
|
356 |
{ |
|
pavolmarko@111
|
357 |
return !( (*this) == where ); |
|
pavolmarko@111
|
358 |
} |
|
pavolmarko@111
|
359 |
private: |
|
pavolmarko@111
|
360 |
void _Inc() |
|
pavolmarko@111
|
361 |
{ |
|
pavolmarko@111
|
362 |
if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets)) |
|
pavolmarko@111
|
363 |
return; |
|
pavolmarko@111
|
364 |
if (curbucket < 0) |
|
pavolmarko@111
|
365 |
{ |
|
pavolmarko@111
|
366 |
for (int i=0; i<(int)hash->m_numBuckets; i++) |
|
pavolmarko@111
|
367 |
{ |
|
pavolmarko@111
|
368 |
if (hash->m_Buckets[i]) |
|
pavolmarko@111
|
369 |
{ |
|
pavolmarko@111
|
370 |
iter = hash->m_Buckets[i]->begin(); |
|
pavolmarko@111
|
371 |
if (iter == hash->m_Buckets[i]->end()) |
|
pavolmarko@111
|
372 |
continue; |
|
pavolmarko@111
|
373 |
curbucket = i; |
|
pavolmarko@111
|
374 |
break; |
|
pavolmarko@111
|
375 |
} |
|
pavolmarko@111
|
376 |
} |
|
pavolmarko@111
|
377 |
if (curbucket < 0) |
|
pavolmarko@111
|
378 |
end = true; |
|
pavolmarko@111
|
379 |
} else { |
|
pavolmarko@111
|
380 |
if (iter != hash->m_Buckets[curbucket]->end()) |
|
pavolmarko@111
|
381 |
iter++; |
|
pavolmarko@111
|
382 |
if (iter == hash->m_Buckets[curbucket]->end()) |
|
pavolmarko@111
|
383 |
{ |
|
pavolmarko@111
|
384 |
int oldbucket = curbucket; |
|
pavolmarko@111
|
385 |
for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++) |
|
pavolmarko@111
|
386 |
{ |
|
pavolmarko@111
|
387 |
if (hash->m_Buckets[i]) |
|
pavolmarko@111
|
388 |
{ |
|
pavolmarko@111
|
389 |
iter = hash->m_Buckets[i]->begin(); |
|
pavolmarko@111
|
390 |
if (iter == hash->m_Buckets[i]->end()) |
|
pavolmarko@111
|
391 |
continue; |
|
pavolmarko@111
|
392 |
curbucket = i; |
|
pavolmarko@111
|
393 |
break; |
|
pavolmarko@111
|
394 |
} |
|
pavolmarko@111
|
395 |
} |
|
pavolmarko@111
|
396 |
if (curbucket == oldbucket) |
|
pavolmarko@111
|
397 |
end = true; |
|
pavolmarko@111
|
398 |
} |
|
pavolmarko@111
|
399 |
} |
|
pavolmarko@111
|
400 |
} |
|
pavolmarko@111
|
401 |
private: |
|
pavolmarko@111
|
402 |
int curbucket; |
|
pavolmarko@111
|
403 |
typename SourceHook::List<THashNode *>::iterator iter; |
|
pavolmarko@111
|
404 |
const THash *hash; |
|
pavolmarko@111
|
405 |
bool end; |
|
pavolmarko@111
|
406 |
}; |
|
dvander@102
|
407 |
public: |
|
dvander@102
|
408 |
iterator begin() |
|
dvander@102
|
409 |
{ |
|
dvander@102
|
410 |
return iterator(this); |
|
dvander@102
|
411 |
} |
|
dvander@102
|
412 |
iterator end() |
|
dvander@102
|
413 |
{ |
|
dvander@102
|
414 |
iterator iter; |
|
dvander@102
|
415 |
iter.hash = this; |
|
dvander@102
|
416 |
return iter; |
|
dvander@102
|
417 |
} |
|
pavolmarko@117
|
418 |
|
|
pavolmarko@111
|
419 |
const_iterator begin() const |
|
pavolmarko@111
|
420 |
{ |
|
pavolmarko@111
|
421 |
return const_iterator(this); |
|
pavolmarko@111
|
422 |
} |
|
pavolmarko@111
|
423 |
const_iterator end() const |
|
pavolmarko@111
|
424 |
{ |
|
pavolmarko@111
|
425 |
const_iterator iter; |
|
pavolmarko@111
|
426 |
iter.hash = this; |
|
pavolmarko@111
|
427 |
return iter; |
|
pavolmarko@111
|
428 |
} |
|
pavolmarko@117
|
429 |
|
|
dvander@102
|
430 |
template <typename U> |
|
dvander@102
|
431 |
iterator find(const U & u) const |
|
dvander@102
|
432 |
{ |
|
dvander@102
|
433 |
iterator b = begin(); |
|
dvander@102
|
434 |
iterator e = end(); |
|
dvander@102
|
435 |
for (iterator iter = b; iter != e; iter++) |
|
dvander@102
|
436 |
{ |
|
dvander@102
|
437 |
if ( (*iter).key == u ) |
|
dvander@102
|
438 |
return iter; |
|
dvander@102
|
439 |
} |
|
dvander@102
|
440 |
return end(); |
|
dvander@102
|
441 |
} |
|
dvander@102
|
442 |
template <typename U> |
|
dvander@102
|
443 |
iterator find(const U & u) |
|
dvander@102
|
444 |
{ |
|
dvander@102
|
445 |
iterator b = begin(); |
|
dvander@102
|
446 |
iterator e = end(); |
|
dvander@102
|
447 |
for (iterator iter = b; iter != e; iter++) |
|
dvander@102
|
448 |
{ |
|
dvander@102
|
449 |
if ( (*iter).key == u ) |
|
dvander@102
|
450 |
return iter; |
|
dvander@102
|
451 |
} |
|
dvander@102
|
452 |
return end(); |
|
dvander@102
|
453 |
} |
|
pavolmarko@117
|
454 |
|
|
pavolmarko@117
|
455 |
iterator erase(iterator where) |
|
pavolmarko@117
|
456 |
{ |
|
pavolmarko@117
|
457 |
where.erase(); |
|
pavolmarko@117
|
458 |
return where; |
|
pavolmarko@117
|
459 |
} |
|
pavolmarko@117
|
460 |
template <typename U> |
|
pavolmarko@117
|
461 |
void erase(const U & u) |
|
pavolmarko@117
|
462 |
{ |
|
pavolmarko@117
|
463 |
iterator iter = find(u); |
|
pavolmarko@117
|
464 |
if (iter == end()) |
|
pavolmarko@117
|
465 |
return; |
|
pavolmarko@117
|
466 |
iter.erase(); |
|
pavolmarko@117
|
467 |
} |
|
dvander@102
|
468 |
private: |
|
dvander@102
|
469 |
NodePtr *m_Buckets; |
|
dvander@102
|
470 |
size_t m_numBuckets; |
|
dvander@102
|
471 |
float m_percentUsed; |
|
dvander@102
|
472 |
}; |
|
dvander@102
|
473 |
}; |
|
dvander@102
|
474 |
|
|
dvander@102
|
475 |
#endif //_INCLUDE_SH_TINYHASH_H_ |