dvander@102: /* ======== SourceMM ======== dvander@102: * Copyright (C) 2004-2005 Metamod:Source Development Team dvander@102: * No warranties of any kind dvander@102: * dvander@102: * License: zlib/libpng dvander@102: * dvander@102: * Author(s): David "BAILOPAN" Anderson dvander@102: * ============================ dvander@102: */ dvander@102: dvander@102: #ifndef _INCLUDE_SH_TINYHASH_H_ dvander@102: #define _INCLUDE_SH_TINYHASH_H_ dvander@102: dvander@102: #include "sh_list.h" dvander@102: dvander@102: #define _T_INIT_HASH_SIZE 32 dvander@102: dvander@102: namespace SourceHook dvander@102: { dvander@102: template dvander@102: int HashFunction(const K & k); dvander@102: dvander@102: template dvander@102: int Compare(const K & k1, const K & k2); dvander@102: dvander@102: /** dvander@102: * This is a tiny, growable hash class. dvander@102: * Meant for quick and dirty dictionaries only! dvander@102: */ dvander@102: template dvander@102: class THash dvander@102: { dvander@102: public: dvander@102: struct THashNode dvander@102: { dvander@102: THashNode(const K & k, const V & v) : dvander@102: key(k), val(v) dvander@102: { dvander@102: }; dvander@102: K key; dvander@102: V val; dvander@102: }; dvander@102: typedef List * NodePtr; dvander@102: public: dvander@102: THash() : m_numBuckets(0), m_Buckets(NULL) dvander@102: { dvander@102: _Refactor(); dvander@102: } dvander@102: size_t GetBuckets() dvander@102: { dvander@102: return m_numBuckets; dvander@102: } dvander@102: float PercentUsed() dvander@102: { dvander@102: return m_percentUsed; dvander@102: } dvander@102: V & operator [](const K & key) dvander@102: { dvander@102: THashNode *pNode = _FindOrInsert(key); dvander@102: return pNode->val; dvander@102: } dvander@102: private: dvander@102: THashNode *_FindOrInsert(const K & key) dvander@102: { dvander@102: size_t place = HashFunction(key) % m_numBuckets; dvander@102: THashNode *pNode = NULL; dvander@102: if (!m_Buckets[place]) dvander@102: { dvander@102: m_Buckets[place] = new List; dvander@102: pNode = new THashNode(key, V()); dvander@102: m_Buckets[place]->push_back(pNode); dvander@102: m_percentUsed += (1.0f / (float)m_numBuckets); dvander@102: } else { dvander@102: List::iterator iter; dvander@102: for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++) dvander@102: { dvander@102: if (Compare((*iter)->key, key) == 0) dvander@102: return (*iter); dvander@102: } dvander@102: //node does not exist dvander@102: pNode = new THashNode(key, V()); dvander@102: m_Buckets[place]->push_back(pNode); dvander@102: } dvander@102: if (PercentUsed() > 0.75f) dvander@102: _Refactor(); dvander@102: return pNode; dvander@102: } dvander@102: void _Refactor() dvander@102: { dvander@102: m_percentUsed = 0.0f; dvander@102: if (!m_numBuckets) dvander@102: { dvander@102: m_numBuckets = _T_INIT_HASH_SIZE; dvander@102: m_Buckets = new NodePtr[m_numBuckets]; dvander@102: for (size_t i=0; i::iterator iter; dvander@102: size_t place; dvander@102: THashNode *pHashNode; dvander@102: NodePtr *temp = new NodePtr[m_numBuckets]; dvander@102: for (size_t i=0; ibegin(); iter != m_Buckets[i]->end(); iter++) dvander@102: { dvander@102: pHashNode = (*iter); dvander@102: //rehash it with the new bucket filter dvander@102: place = HashFunction(pHashNode->key) % m_numBuckets; dvander@102: //add it to the new hash table dvander@102: if (!temp[place]) dvander@102: { dvander@102: temp[place] = new List; dvander@102: m_percentUsed += (1.0f / (float)m_numBuckets); dvander@102: } dvander@102: temp[place]->push_back(pHashNode); dvander@102: } dvander@102: //delete that bucket! dvander@102: delete m_Buckets[i]; dvander@102: m_Buckets[i] = NULL; dvander@102: } dvander@102: } dvander@102: //reassign bucket table dvander@102: delete [] m_Buckets; dvander@102: m_Buckets = temp; dvander@102: } dvander@102: } dvander@102: public: dvander@102: friend class iterator; dvander@102: class iterator dvander@102: { dvander@102: friend class THash; dvander@102: public: dvander@102: iterator() : hash(NULL), end(true) dvander@102: { dvander@102: }; dvander@102: iterator(THash *h) : hash(h), end(false) dvander@102: { dvander@102: if (!h->m_Buckets) dvander@102: end = true; dvander@102: else dvander@102: _Inc(); dvander@102: }; dvander@102: //pre increment dvander@102: iterator & operator++() dvander@102: { dvander@102: _Inc(); dvander@102: return *this; dvander@102: } dvander@102: //post increment dvander@102: iterator operator++(int) dvander@102: { dvander@102: iterator old(*this); dvander@102: _Inc(); dvander@102: return old; dvander@102: } dvander@102: THashNode & operator * () const dvander@102: { dvander@102: return *(*iter); dvander@102: } dvander@102: THashNode & operator * () dvander@102: { dvander@102: return *(*iter); dvander@102: } dvander@102: THashNode * operator ->() const dvander@102: { dvander@102: return (*iter); dvander@102: } dvander@102: THashNode * operator ->() dvander@102: { dvander@102: return (*iter); dvander@102: } dvander@102: bool operator ==(const iterator &where) const dvander@102: { dvander@102: if (where.hash == this->hash dvander@102: && where.end == this->end dvander@102: && dvander@102: (this->end || dvander@102: ((where.curbucket == this->curbucket) dvander@102: && (where.iter == iter)) dvander@102: )) dvander@102: return true; dvander@102: return false; dvander@102: } dvander@102: bool operator !=(const iterator &where) const dvander@102: { dvander@102: return !( (*this) == where ); dvander@102: } dvander@102: private: dvander@102: void _Inc() dvander@102: { dvander@102: if (end || !hash) dvander@102: return; dvander@102: if (curbucket < 0) dvander@102: { dvander@102: for (int i=0; i<(int)hash->m_numBuckets; i++) dvander@102: { dvander@102: if (hash->m_Buckets[i]) dvander@102: { dvander@102: iter = hash->m_Buckets[i]->begin(); dvander@102: if (iter == hash->m_Buckets[i]->end()) dvander@102: continue; dvander@102: curbucket = i; dvander@102: break; dvander@102: } dvander@102: } dvander@102: if (curbucket < 0) dvander@102: end = true; dvander@102: } else { dvander@102: if (iter != hash->m_Buckets[curbucket]->end()) dvander@102: iter++; dvander@102: if (iter == hash->m_Buckets[curbucket]->end()) dvander@102: { dvander@102: int oldbucket = curbucket; dvander@102: for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++) dvander@102: { dvander@102: if (hash->m_Buckets[i]) dvander@102: { dvander@102: iter = hash->m_Buckets[i]->begin(); dvander@102: if (iter == hash->m_Buckets[i]->end()) dvander@102: continue; dvander@102: curbucket = i; dvander@102: break; dvander@102: } dvander@102: } dvander@102: if (curbucket == oldbucket) dvander@102: end = true; dvander@102: } dvander@102: } dvander@102: } dvander@102: private: dvander@102: int curbucket; dvander@102: typename SourceHook::List::iterator iter; dvander@102: THash *hash; dvander@102: bool end; dvander@102: }; dvander@102: public: dvander@102: iterator begin() dvander@102: { dvander@102: return iterator(this); dvander@102: } dvander@102: iterator end() dvander@102: { dvander@102: iterator iter; dvander@102: iter.hash = this; dvander@102: return iter; dvander@102: } dvander@102: template dvander@102: iterator find(const U & u) const dvander@102: { dvander@102: iterator b = begin(); dvander@102: iterator e = end(); dvander@102: for (iterator iter = b; iter != e; iter++) dvander@102: { dvander@102: if ( (*iter).key == u ) dvander@102: return iter; dvander@102: } dvander@102: return end(); dvander@102: } dvander@102: template dvander@102: iterator find(const U & u) dvander@102: { dvander@102: iterator b = begin(); dvander@102: iterator e = end(); dvander@102: for (iterator iter = b; iter != e; iter++) dvander@102: { dvander@102: if ( (*iter).key == u ) dvander@102: return iter; dvander@102: } dvander@102: return end(); dvander@102: } dvander@102: private: dvander@102: NodePtr *m_Buckets; dvander@102: size_t m_numBuckets; dvander@102: float m_percentUsed; dvander@102: }; dvander@102: }; dvander@102: dvander@102: #endif //_INCLUDE_SH_TINYHASH_H_