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