SourceHook tests pass again! Added test for list (and a small bit of tinyhash). Woot.
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_Buckets(NULL), m_numBuckets(0), m_percentUsed(0.0f)
49 THash(const THash &other) : m_Buckets(new NodePtr[other.m_numBuckets]),
50 m_numBuckets(other.m_numBuckets), m_percentUsed(other.m_percentUsed)
52 for (size_t i=0; i<m_numBuckets; i++)
54 for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
55 _FindOrInsert(iter->key)->val = iter->val;
57 void operator=(const THash &other)
60 for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
61 _FindOrInsert(iter->key)->val = iter->val;
87 V & operator [](const K & key)
89 THashNode *pNode = _FindOrInsert(key);
93 THashNode *_FindOrInsert(const K & key)
95 size_t place = HashFunction(key) % m_numBuckets;
96 THashNode *pNode = NULL;
97 if (!m_Buckets[place])
99 m_Buckets[place] = new List<THashNode *>;
100 pNode = new THashNode(key, V());
101 m_Buckets[place]->push_back(pNode);
102 m_percentUsed += (1.0f / (float)m_numBuckets);
104 typename List<THashNode *>::iterator iter;
105 for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++)
107 if (Compare((*iter)->key, key) == 0)
110 //node does not exist
111 pNode = new THashNode(key, V());
112 m_Buckets[place]->push_back(pNode);
114 if (PercentUsed() > 0.75f)
120 m_percentUsed = 0.0f;
123 m_numBuckets = _T_INIT_HASH_SIZE;
124 m_Buckets = new NodePtr[m_numBuckets];
125 for (size_t i=0; i<m_numBuckets; i++)
128 size_t oldSize = m_numBuckets;
130 typename List<THashNode *>::iterator iter;
132 THashNode *pHashNode;
133 NodePtr *temp = new NodePtr[m_numBuckets];
134 for (size_t i=0; i<m_numBuckets; i++)
136 //look in old hash table
137 for (size_t i=0; i<oldSize; i++)
139 //does a bucket have anything?
142 //go through the list of items
143 for (iter = m_Buckets[i]->begin(); iter != m_Buckets[i]->end(); iter++)
146 //rehash it with the new bucket filter
147 place = HashFunction(pHashNode->key) % m_numBuckets;
148 //add it to the new hash table
151 temp[place] = new List<THashNode *>;
152 m_percentUsed += (1.0f / (float)m_numBuckets);
154 temp[place]->push_back(pHashNode);
156 //delete that bucket!
161 //reassign bucket table
167 friend class iterator;
168 friend class const_iterator;
173 iterator() : curbucket(-1), hash(NULL), end(true)
176 iterator(THash *h) : curbucket(-1), hash(h), end(false)
184 iterator & operator++()
190 iterator operator++(int)
196 const THashNode & operator * () const
200 THashNode & operator * ()
204 const THashNode * operator ->() const
208 THashNode * operator ->()
212 bool operator ==(const iterator &where) const
214 if (where.hash == this->hash
215 && where.end == this->end
218 ((where.curbucket == this->curbucket)
219 && (where.iter == iter))
224 bool operator !=(const iterator &where) const
226 return !( (*this) == where );
231 if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
235 for (int i=0; i<(int)hash->m_numBuckets; i++)
237 if (hash->m_Buckets[i])
239 iter = hash->m_Buckets[i]->begin();
240 if (iter == hash->m_Buckets[i]->end())
249 if (iter != hash->m_Buckets[curbucket]->end())
251 if (iter == hash->m_Buckets[curbucket]->end())
253 int oldbucket = curbucket;
254 for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
256 if (hash->m_Buckets[i])
258 iter = hash->m_Buckets[i]->begin();
259 if (iter == hash->m_Buckets[i]->end())
265 if (curbucket == oldbucket)
272 typename SourceHook::List<THashNode *>::iterator iter;
280 const_iterator() : curbucket(-1), hash(NULL), end(true)
283 const_iterator(const THash *h) : curbucket(-1), hash(h), end(false)
291 const_iterator & operator++()
297 const_iterator operator++(int)
303 const THashNode & operator * () const
307 const THashNode * operator ->() const
311 bool operator ==(const const_iterator &where) const
313 if (where.hash == this->hash
314 && where.end == this->end
317 ((where.curbucket == this->curbucket)
318 && (where.iter == iter))
323 bool operator !=(const const_iterator &where) const
325 return !( (*this) == where );
330 if (end || !hash || curbucket >= static_cast<int>(hash->m_numBuckets))
334 for (int i=0; i<(int)hash->m_numBuckets; i++)
336 if (hash->m_Buckets[i])
338 iter = hash->m_Buckets[i]->begin();
339 if (iter == hash->m_Buckets[i]->end())
348 if (iter != hash->m_Buckets[curbucket]->end())
350 if (iter == hash->m_Buckets[curbucket]->end())
352 int oldbucket = curbucket;
353 for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++)
355 if (hash->m_Buckets[i])
357 iter = hash->m_Buckets[i]->begin();
358 if (iter == hash->m_Buckets[i]->end())
364 if (curbucket == oldbucket)
371 typename SourceHook::List<THashNode *>::iterator iter;
378 return iterator(this);
387 const_iterator begin() const
389 return const_iterator(this);
391 const_iterator end() const
398 template <typename U>
399 iterator find(const U & u) const
401 iterator b = begin();
403 for (iterator iter = b; iter != e; iter++)
405 if ( (*iter).key == u )
410 template <typename U>
411 iterator find(const U & u)
413 iterator b = begin();
415 for (iterator iter = b; iter != e; iter++)
417 if ( (*iter).key == u )
429 #endif //_INCLUDE_SH_TINYHASH_H_