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