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