| author | Scott Ehlert <ds@alliedmods.net> |
| Tue Sep 16 04:41:32 2008 -0500 (2008-09-16) | |
| changeset 533 | 591b88a78e35 |
| parent 523 | 6f1630519b81 |
| permissions | -rw-r--r-- |
| dvander@102 | 1 |
/* ======== SourceMM ======== |
| ds@523 | 2 |
* Copyright (C) 2004-2008 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 |
class iterator |
| dvander@102 | 231 |
{ |
| dvander@102 | 232 |
friend class THash; |
| dvander@102 | 233 |
public: |
| pavolmarko@111 | 234 |
iterator() : curbucket(-1), hash(NULL), end(true) |
| dvander@102 | 235 |
{ |
| dvander@102 | 236 |
}; |
| pavolmarko@111 | 237 |
iterator(THash *h) : curbucket(-1), hash(h), end(false) |
| dvander@102 | 238 |
{ |
| dvander@102 | 239 |
if (!h->m_Buckets) |
| dvander@102 | 240 |
end = true; |
| dvander@102 | 241 |
else |
| dvander@102 | 242 |
_Inc(); |
| dvander@102 | 243 |
}; |
| dvander@102 | 244 |
//pre increment |
| dvander@102 | 245 |
iterator & operator++() |
| dvander@102 | 246 |
{ |
| dvander@102 | 247 |
_Inc(); |
| dvander@102 | 248 |
return *this; |
| dvander@102 | 249 |
} |
| dvander@102 | 250 |
//post increment |
| dvander@102 | 251 |
iterator operator++(int) |
| dvander@102 | 252 |
{ |
| dvander@102 | 253 |
iterator old(*this); |
| dvander@102 | 254 |
_Inc(); |
| dvander@102 | 255 |
return old; |
| dvander@102 | 256 |
} |
| pavolmarko@111 | 257 |
const THashNode & operator * () const |
| dvander@102 | 258 |
{ |
| dvander@102 | 259 |
return *(*iter); |
| dvander@102 | 260 |
} |
| dvander@102 | 261 |
THashNode & operator * () |
| dvander@102 | 262 |
{ |
| dvander@102 | 263 |
return *(*iter); |
| dvander@102 | 264 |
} |
| pavolmarko@111 | 265 |
const THashNode * operator ->() const |
| dvander@102 | 266 |
{ |
| dvander@102 | 267 |
return (*iter); |
| dvander@102 | 268 |
} |
| dvander@102 | 269 |
THashNode * operator ->() |
| dvander@102 | 270 |
{ |
| dvander@102 | 271 |
return (*iter); |
| dvander@102 | 272 |
} |
| dvander@102 | 273 |
bool operator ==(const iterator &where) const |
| dvander@102 | 274 |
{ |
| dvander@102 | 275 |
if (where.hash == this->hash |
| dvander@102 | 276 |
&& where.end == this->end |
| pavolmarko@117 | 277 |
&& |
| pavolmarko@117 | 278 |
(this->end || |
| pavolmarko@117 | 279 |
((where.curbucket == this->curbucket) |
| pavolmarko@117 | 280 |
&& (where.iter == iter)) |
| dvander@102 | 281 |
)) |
| dvander@102 | 282 |
return true; |
| dvander@102 | 283 |
return false; |
| dvander@102 | 284 |
} |
| dvander@102 | 285 |
bool operator !=(const iterator &where) const |
| dvander@102 | 286 |
{ |
| dvander@102 | 287 |
return !( (*this) == where ); |
| dvander@102 | 288 |
} |
| pavolmarko@117 | 289 |
|
| pavolmarko@117 | 290 |
void erase() |
| pavolmarko@117 | 291 |
{ |
| pavolmarko@117 | 292 |
if (end || !hash || curbucket < 0 || curbucket >= static_cast<int>(hash->m_numBuckets)) |
| pavolmarko@117 | 293 |
return; |
| pavolmarko@117 | 294 |
|
| pavolmarko@117 | 295 |
// Remove this element and move to the next one |
| pavolmarko@117 | 296 |
iterator tmp = *this; |
| pavolmarko@117 | 297 |
++tmp; |
| dvander@151 | 298 |
delete (*iter); |
| pavolmarko@117 | 299 |
hash->m_Buckets[curbucket]->erase(iter); |
| pavolmarko@117 | 300 |
*this = tmp; |
| pavolmarko@117 | 301 |
|
| pavolmarko@117 | 302 |
// :TODO: Maybe refactor to a lower size if required |
| pavolmarko@117 | 303 |
} |
| dvander@102 | 304 |
private: |
| dvander@102 | 305 |
void _Inc() |
| dvander@102 | 306 |
{ |
| pavolmarko@111 | 307 |
if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets)) |
| dvander@102 | 308 |
return; |
| dvander@102 | 309 |
if (curbucket < 0) |
| dvander@102 | 310 |
{ |
| dvander@102 | 311 |
for (int i=0; i<(int)hash->m_numBuckets; i++) |
| dvander@102 | 312 |
{ |
| dvander@102 | 313 |
if (hash->m_Buckets[i]) |
| dvander@102 | 314 |
{ |
| dvander@102 | 315 |
iter = hash->m_Buckets[i]->begin(); |
| dvander@102 | 316 |
if (iter == hash->m_Buckets[i]->end()) |
| dvander@102 | 317 |
continue; |
| dvander@102 | 318 |
curbucket = i; |
| dvander@102 | 319 |
break; |
| dvander@102 | 320 |
} |
| dvander@102 | 321 |
} |
| dvander@102 | 322 |
if (curbucket < 0) |
| dvander@102 | 323 |
end = true; |
| dvander@102 | 324 |
} else { |
| dvander@102 | 325 |
if (iter != hash->m_Buckets[curbucket]->end()) |
| dvander@102 | 326 |
iter++; |
| dvander@102 | 327 |
if (iter == hash->m_Buckets[curbucket]->end()) |
| dvander@102 | 328 |
{ |
| dvander@102 | 329 |
int oldbucket = curbucket; |
| dvander@102 | 330 |
for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++) |
| dvander@102 | 331 |
{ |
| dvander@102 | 332 |
if (hash->m_Buckets[i]) |
| dvander@102 | 333 |
{ |
| dvander@102 | 334 |
iter = hash->m_Buckets[i]->begin(); |
| dvander@102 | 335 |
if (iter == hash->m_Buckets[i]->end()) |
| dvander@102 | 336 |
continue; |
| dvander@102 | 337 |
curbucket = i; |
| dvander@102 | 338 |
break; |
| dvander@102 | 339 |
} |
| dvander@102 | 340 |
} |
| dvander@102 | 341 |
if (curbucket == oldbucket) |
| dvander@102 | 342 |
end = true; |
| dvander@102 | 343 |
} |
| dvander@102 | 344 |
} |
| dvander@102 | 345 |
} |
| dvander@102 | 346 |
private: |
| dvander@102 | 347 |
int curbucket; |
| dvander@102 | 348 |
typename SourceHook::List<THashNode *>::iterator iter; |
| dvander@102 | 349 |
THash *hash; |
| dvander@102 | 350 |
bool end; |
| dvander@102 | 351 |
}; |
| pavolmarko@111 | 352 |
class const_iterator |
| pavolmarko@111 | 353 |
{ |
| pavolmarko@111 | 354 |
friend class THash; |
| pavolmarko@111 | 355 |
public: |
| pavolmarko@111 | 356 |
const_iterator() : curbucket(-1), hash(NULL), end(true) |
| pavolmarko@111 | 357 |
{ |
| pavolmarko@111 | 358 |
}; |
| pavolmarko@111 | 359 |
const_iterator(const THash *h) : curbucket(-1), hash(h), end(false) |
| pavolmarko@111 | 360 |
{ |
| pavolmarko@111 | 361 |
if (!h->m_Buckets) |
| pavolmarko@111 | 362 |
end = true; |
| pavolmarko@111 | 363 |
else |
| pavolmarko@111 | 364 |
_Inc(); |
| pavolmarko@111 | 365 |
}; |
| pavolmarko@111 | 366 |
//pre increment |
| pavolmarko@111 | 367 |
const_iterator & operator++() |
| pavolmarko@111 | 368 |
{ |
| pavolmarko@111 | 369 |
_Inc(); |
| pavolmarko@111 | 370 |
return *this; |
| pavolmarko@111 | 371 |
} |
| pavolmarko@111 | 372 |
//post increment |
| pavolmarko@111 | 373 |
const_iterator operator++(int) |
| pavolmarko@111 | 374 |
{ |
| pavolmarko@111 | 375 |
iterator old(*this); |
| pavolmarko@111 | 376 |
_Inc(); |
| pavolmarko@111 | 377 |
return old; |
| pavolmarko@111 | 378 |
} |
| pavolmarko@111 | 379 |
const THashNode & operator * () const |
| pavolmarko@111 | 380 |
{ |
| pavolmarko@111 | 381 |
return *(*iter); |
| pavolmarko@111 | 382 |
} |
| pavolmarko@111 | 383 |
const THashNode * operator ->() const |
| pavolmarko@111 | 384 |
{ |
| pavolmarko@111 | 385 |
return (*iter); |
| pavolmarko@111 | 386 |
} |
| pavolmarko@111 | 387 |
bool operator ==(const const_iterator &where) const |
| pavolmarko@111 | 388 |
{ |
| pavolmarko@111 | 389 |
if (where.hash == this->hash |
| pavolmarko@111 | 390 |
&& where.end == this->end |
| pavolmarko@117 | 391 |
&& |
| pavolmarko@117 | 392 |
(this->end || |
| pavolmarko@117 | 393 |
((where.curbucket == this->curbucket) |
| pavolmarko@117 | 394 |
&& (where.iter == iter)) |
| pavolmarko@111 | 395 |
)) |
| pavolmarko@111 | 396 |
return true; |
| pavolmarko@111 | 397 |
return false; |
| pavolmarko@111 | 398 |
} |
| pavolmarko@111 | 399 |
bool operator !=(const const_iterator &where) const |
| pavolmarko@111 | 400 |
{ |
| pavolmarko@111 | 401 |
return !( (*this) == where ); |
| pavolmarko@111 | 402 |
} |
| pavolmarko@111 | 403 |
private: |
| pavolmarko@111 | 404 |
void _Inc() |
| pavolmarko@111 | 405 |
{ |
| pavolmarko@111 | 406 |
if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets)) |
| pavolmarko@111 | 407 |
return; |
| pavolmarko@111 | 408 |
if (curbucket < 0) |
| pavolmarko@111 | 409 |
{ |
| pavolmarko@111 | 410 |
for (int i=0; i<(int)hash->m_numBuckets; i++) |
| pavolmarko@111 | 411 |
{ |
| pavolmarko@111 | 412 |
if (hash->m_Buckets[i]) |
| pavolmarko@111 | 413 |
{ |
| pavolmarko@111 | 414 |
iter = hash->m_Buckets[i]->begin(); |
| pavolmarko@111 | 415 |
if (iter == hash->m_Buckets[i]->end()) |
| pavolmarko@111 | 416 |
continue; |
| pavolmarko@111 | 417 |
curbucket = i; |
| pavolmarko@111 | 418 |
break; |
| pavolmarko@111 | 419 |
} |
| pavolmarko@111 | 420 |
} |
| pavolmarko@111 | 421 |
if (curbucket < 0) |
| pavolmarko@111 | 422 |
end = true; |
| pavolmarko@111 | 423 |
} else { |
| pavolmarko@111 | 424 |
if (iter != hash->m_Buckets[curbucket]->end()) |
| pavolmarko@111 | 425 |
iter++; |
| pavolmarko@111 | 426 |
if (iter == hash->m_Buckets[curbucket]->end()) |
| pavolmarko@111 | 427 |
{ |
| pavolmarko@111 | 428 |
int oldbucket = curbucket; |
| pavolmarko@111 | 429 |
for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++) |
| pavolmarko@111 | 430 |
{ |
| pavolmarko@111 | 431 |
if (hash->m_Buckets[i]) |
| pavolmarko@111 | 432 |
{ |
| pavolmarko@111 | 433 |
iter = hash->m_Buckets[i]->begin(); |
| pavolmarko@111 | 434 |
if (iter == hash->m_Buckets[i]->end()) |
| pavolmarko@111 | 435 |
continue; |
| pavolmarko@111 | 436 |
curbucket = i; |
| pavolmarko@111 | 437 |
break; |
| pavolmarko@111 | 438 |
} |
| pavolmarko@111 | 439 |
} |
| pavolmarko@111 | 440 |
if (curbucket == oldbucket) |
| pavolmarko@111 | 441 |
end = true; |
| pavolmarko@111 | 442 |
} |
| pavolmarko@111 | 443 |
} |
| pavolmarko@111 | 444 |
} |
| pavolmarko@111 | 445 |
private: |
| pavolmarko@111 | 446 |
int curbucket; |
| pavolmarko@111 | 447 |
typename SourceHook::List<THashNode *>::iterator iter; |
| pavolmarko@111 | 448 |
const THash *hash; |
| pavolmarko@111 | 449 |
bool end; |
| pavolmarko@111 | 450 |
}; |
| dvander@102 | 451 |
public: |
| dvander@102 | 452 |
iterator begin() |
| dvander@102 | 453 |
{ |
| dvander@102 | 454 |
return iterator(this); |
| dvander@102 | 455 |
} |
| dvander@102 | 456 |
iterator end() |
| dvander@102 | 457 |
{ |
| dvander@102 | 458 |
iterator iter; |
| dvander@102 | 459 |
iter.hash = this; |
| dvander@102 | 460 |
return iter; |
| dvander@102 | 461 |
} |
| pavolmarko@117 | 462 |
|
| pavolmarko@111 | 463 |
const_iterator begin() const |
| pavolmarko@111 | 464 |
{ |
| pavolmarko@111 | 465 |
return const_iterator(this); |
| pavolmarko@111 | 466 |
} |
| pavolmarko@111 | 467 |
const_iterator end() const |
| pavolmarko@111 | 468 |
{ |
| pavolmarko@111 | 469 |
const_iterator iter; |
| pavolmarko@111 | 470 |
iter.hash = this; |
| pavolmarko@111 | 471 |
return iter; |
| pavolmarko@111 | 472 |
} |
| pavolmarko@117 | 473 |
|
| dvander@102 | 474 |
template <typename U> |
| dvander@102 | 475 |
iterator find(const U & u) const |
| dvander@102 | 476 |
{ |
| dvander@102 | 477 |
iterator b = begin(); |
| dvander@102 | 478 |
iterator e = end(); |
| dvander@102 | 479 |
for (iterator iter = b; iter != e; iter++) |
| dvander@102 | 480 |
{ |
| dvander@102 | 481 |
if ( (*iter).key == u ) |
| dvander@102 | 482 |
return iter; |
| dvander@102 | 483 |
} |
| dvander@102 | 484 |
return end(); |
| dvander@102 | 485 |
} |
| dvander@102 | 486 |
template <typename U> |
| dvander@102 | 487 |
iterator find(const U & u) |
| dvander@102 | 488 |
{ |
| dvander@102 | 489 |
iterator b = begin(); |
| dvander@102 | 490 |
iterator e = end(); |
| dvander@102 | 491 |
for (iterator iter = b; iter != e; iter++) |
| dvander@102 | 492 |
{ |
| dvander@102 | 493 |
if ( (*iter).key == u ) |
| dvander@102 | 494 |
return iter; |
| dvander@102 | 495 |
} |
| dvander@102 | 496 |
return end(); |
| dvander@102 | 497 |
} |
| dvander@264 | 498 |
template <typename U> |
| dvander@264 | 499 |
iterator FindAlt(const U & u) |
| dvander@264 | 500 |
{ |
| dvander@264 | 501 |
iterator b = begin(); |
| dvander@264 | 502 |
iterator e = end(); |
| dvander@264 | 503 |
for (iterator iter = b; iter != e; iter++) |
| dvander@264 | 504 |
{ |
| dvander@264 | 505 |
if (CompareAlt(u, (*iter).key) == 0) |
| dvander@264 | 506 |
{ |
| dvander@264 | 507 |
return iter; |
| dvander@264 | 508 |
} |
| dvander@264 | 509 |
} |
| dvander@264 | 510 |
return e; |
| dvander@264 | 511 |
} |
| pavolmarko@117 | 512 |
iterator erase(iterator where) |
| pavolmarko@117 | 513 |
{ |
| pavolmarko@117 | 514 |
where.erase(); |
| pavolmarko@117 | 515 |
return where; |
| pavolmarko@117 | 516 |
} |
| pavolmarko@117 | 517 |
template <typename U> |
| pavolmarko@117 | 518 |
void erase(const U & u) |
| pavolmarko@117 | 519 |
{ |
| pavolmarko@117 | 520 |
iterator iter = find(u); |
| pavolmarko@117 | 521 |
if (iter == end()) |
| pavolmarko@117 | 522 |
return; |
| pavolmarko@117 | 523 |
iter.erase(); |
| pavolmarko@117 | 524 |
} |
| dvander@430 | 525 |
friend class iterator; |
| dvander@430 | 526 |
friend class const_iterator; |
| 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_ |