dvander@102: /* ======== SourceMM ======== ds@294: * Copyright (C) 2004-2007 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@264: template dvander@264: int HashAlt(const U &u); dvander@264: dvander@264: template dvander@264: int CompareAlt(const U &k1, const K &k2); dvander@264: 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: */ pavolmarko@117: template dvander@102: class THash dvander@102: { dvander@102: public: dvander@102: struct THashNode dvander@102: { pavolmarko@117: THashNode(const K & k, const V & v) : dvander@102: key(k), val(v) dvander@102: { dvander@102: }; dvander@154: THashNode & operator =(const THashNode &other) dvander@154: { dvander@154: key = other.key; dvander@154: val = other.val; dvander@154: } dvander@102: K key; dvander@102: V val; dvander@102: }; dvander@102: typedef List * NodePtr; dvander@102: public: pavolmarko@159: class const_iterator; pavolmarko@111: THash() : m_Buckets(NULL), m_numBuckets(0), m_percentUsed(0.0f) pavolmarko@111: { pavolmarko@111: _Refactor(); pavolmarko@111: } pavolmarko@111: THash(const THash &other) : m_Buckets(new NodePtr[other.m_numBuckets]), pavolmarko@111: m_numBuckets(other.m_numBuckets), m_percentUsed(other.m_percentUsed) pavolmarko@111: { pavolmarko@111: for (size_t i=0; ikey)->val = iter->val; pavolmarko@111: } pavolmarko@111: void operator=(const THash &other) dvander@102: { pavolmarko@111: clear(); pavolmarko@111: for (const_iterator iter = other.begin(); iter != other.end(); ++iter) pavolmarko@111: _FindOrInsert(iter->key)->val = iter->val; pavolmarko@111: } pavolmarko@111: pavolmarko@111: ~THash() pavolmarko@111: { dvander@115: _Clear(); pavolmarko@111: } pavolmarko@111: void clear() pavolmarko@111: { dvander@115: _Clear(); 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@115: void _Clear() dvander@115: { dvander@150: typename List::iterator iter, end; dvander@115: for (size_t i=0; iend(); dvander@150: iter = m_Buckets[i]->begin(); dvander@150: while (iter != end) dvander@150: { dvander@150: delete (*iter); dvander@150: iter++; dvander@150: } dvander@115: delete m_Buckets[i]; dvander@115: m_Buckets[i] = NULL; dvander@115: } dvander@115: } dvander@115: if (m_Buckets) dvander@115: delete [] m_Buckets; dvander@115: m_Buckets = NULL; dvander@115: m_numBuckets = 0; dvander@115: } dvander@264: public: dvander@264: template dvander@264: V & AltFindOrInsert(const U & ukey) dvander@264: { dvander@264: size_t place = HashAlt(ukey) % m_numBuckets; dvander@264: THashNode *pNode = NULL; dvander@264: if (!m_Buckets[place]) dvander@264: { dvander@264: m_Buckets[place] = new List; dvander@264: pNode = new THashNode(ukey, V()); dvander@264: m_Buckets[place]->push_back(pNode); dvander@264: m_percentUsed += (1.0f / (float)m_numBuckets); dvander@264: } else { dvander@264: typename List::iterator iter; dvander@264: for (iter=m_Buckets[place]->begin(); iter!=m_Buckets[place]->end(); iter++) dvander@264: { dvander@264: if (CompareAlt(ukey, (*iter)->key) == 0) dvander@264: { dvander@264: return (*iter)->val; dvander@264: } dvander@264: } dvander@264: //node does not exist dvander@264: pNode = new THashNode(ukey, V()); dvander@264: m_Buckets[place]->push_back(pNode); dvander@264: } dvander@264: if (PercentUsed() > 0.75f) dvander@264: { dvander@264: _Refactor(); dvander@264: } dvander@264: return pNode->val; dvander@264: } dvander@264: 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@107: typename 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@264: { dvander@102: _Refactor(); dvander@264: } 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; pavolmarko@117: 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; pavolmarko@111: friend class const_iterator; dvander@102: class iterator dvander@102: { dvander@102: friend class THash; dvander@102: public: pavolmarko@111: iterator() : curbucket(-1), hash(NULL), end(true) dvander@102: { dvander@102: }; pavolmarko@111: iterator(THash *h) : curbucket(-1), 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: } pavolmarko@111: const THashNode & operator * () const dvander@102: { dvander@102: return *(*iter); dvander@102: } dvander@102: THashNode & operator * () dvander@102: { dvander@102: return *(*iter); dvander@102: } pavolmarko@111: const 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 pavolmarko@117: && pavolmarko@117: (this->end || pavolmarko@117: ((where.curbucket == this->curbucket) pavolmarko@117: && (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: } pavolmarko@117: pavolmarko@117: void erase() pavolmarko@117: { pavolmarko@117: if (end || !hash || curbucket < 0 || curbucket >= static_cast(hash->m_numBuckets)) pavolmarko@117: return; pavolmarko@117: pavolmarko@117: // Remove this element and move to the next one pavolmarko@117: iterator tmp = *this; pavolmarko@117: ++tmp; dvander@151: delete (*iter); pavolmarko@117: hash->m_Buckets[curbucket]->erase(iter); pavolmarko@117: *this = tmp; pavolmarko@117: pavolmarko@117: // :TODO: Maybe refactor to a lower size if required pavolmarko@117: } dvander@102: private: dvander@102: void _Inc() dvander@102: { pavolmarko@111: if (end || !hash || curbucket >= static_cast(hash->m_numBuckets)) 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: }; pavolmarko@111: class const_iterator pavolmarko@111: { pavolmarko@111: friend class THash; pavolmarko@111: public: pavolmarko@111: const_iterator() : curbucket(-1), hash(NULL), end(true) pavolmarko@111: { pavolmarko@111: }; pavolmarko@111: const_iterator(const THash *h) : curbucket(-1), hash(h), end(false) pavolmarko@111: { pavolmarko@111: if (!h->m_Buckets) pavolmarko@111: end = true; pavolmarko@111: else pavolmarko@111: _Inc(); pavolmarko@111: }; pavolmarko@111: //pre increment pavolmarko@111: const_iterator & operator++() pavolmarko@111: { pavolmarko@111: _Inc(); pavolmarko@111: return *this; pavolmarko@111: } pavolmarko@111: //post increment pavolmarko@111: const_iterator operator++(int) pavolmarko@111: { pavolmarko@111: iterator old(*this); pavolmarko@111: _Inc(); pavolmarko@111: return old; pavolmarko@111: } pavolmarko@111: const THashNode & operator * () const pavolmarko@111: { pavolmarko@111: return *(*iter); pavolmarko@111: } pavolmarko@111: const THashNode * operator ->() const pavolmarko@111: { pavolmarko@111: return (*iter); pavolmarko@111: } pavolmarko@111: bool operator ==(const const_iterator &where) const pavolmarko@111: { pavolmarko@111: if (where.hash == this->hash pavolmarko@111: && where.end == this->end pavolmarko@117: && pavolmarko@117: (this->end || pavolmarko@117: ((where.curbucket == this->curbucket) pavolmarko@117: && (where.iter == iter)) pavolmarko@111: )) pavolmarko@111: return true; pavolmarko@111: return false; pavolmarko@111: } pavolmarko@111: bool operator !=(const const_iterator &where) const pavolmarko@111: { pavolmarko@111: return !( (*this) == where ); pavolmarko@111: } pavolmarko@111: private: pavolmarko@111: void _Inc() pavolmarko@111: { pavolmarko@111: if (end || !hash || curbucket >= static_cast(hash->m_numBuckets)) pavolmarko@111: return; pavolmarko@111: if (curbucket < 0) pavolmarko@111: { pavolmarko@111: for (int i=0; i<(int)hash->m_numBuckets; i++) pavolmarko@111: { pavolmarko@111: if (hash->m_Buckets[i]) pavolmarko@111: { pavolmarko@111: iter = hash->m_Buckets[i]->begin(); pavolmarko@111: if (iter == hash->m_Buckets[i]->end()) pavolmarko@111: continue; pavolmarko@111: curbucket = i; pavolmarko@111: break; pavolmarko@111: } pavolmarko@111: } pavolmarko@111: if (curbucket < 0) pavolmarko@111: end = true; pavolmarko@111: } else { pavolmarko@111: if (iter != hash->m_Buckets[curbucket]->end()) pavolmarko@111: iter++; pavolmarko@111: if (iter == hash->m_Buckets[curbucket]->end()) pavolmarko@111: { pavolmarko@111: int oldbucket = curbucket; pavolmarko@111: for (int i=curbucket+1; i<(int)hash->m_numBuckets; i++) pavolmarko@111: { pavolmarko@111: if (hash->m_Buckets[i]) pavolmarko@111: { pavolmarko@111: iter = hash->m_Buckets[i]->begin(); pavolmarko@111: if (iter == hash->m_Buckets[i]->end()) pavolmarko@111: continue; pavolmarko@111: curbucket = i; pavolmarko@111: break; pavolmarko@111: } pavolmarko@111: } pavolmarko@111: if (curbucket == oldbucket) pavolmarko@111: end = true; pavolmarko@111: } pavolmarko@111: } pavolmarko@111: } pavolmarko@111: private: pavolmarko@111: int curbucket; pavolmarko@111: typename SourceHook::List::iterator iter; pavolmarko@111: const THash *hash; pavolmarko@111: bool end; pavolmarko@111: }; 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: } pavolmarko@117: pavolmarko@111: const_iterator begin() const pavolmarko@111: { pavolmarko@111: return const_iterator(this); pavolmarko@111: } pavolmarko@111: const_iterator end() const pavolmarko@111: { pavolmarko@111: const_iterator iter; pavolmarko@111: iter.hash = this; pavolmarko@111: return iter; pavolmarko@111: } pavolmarko@117: 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@264: template dvander@264: iterator FindAlt(const U & u) dvander@264: { dvander@264: iterator b = begin(); dvander@264: iterator e = end(); dvander@264: for (iterator iter = b; iter != e; iter++) dvander@264: { dvander@264: if (CompareAlt(u, (*iter).key) == 0) dvander@264: { dvander@264: return iter; dvander@264: } dvander@264: } dvander@264: return e; dvander@264: } pavolmarko@117: iterator erase(iterator where) pavolmarko@117: { pavolmarko@117: where.erase(); pavolmarko@117: return where; pavolmarko@117: } pavolmarko@117: template pavolmarko@117: void erase(const U & u) pavolmarko@117: { pavolmarko@117: iterator iter = find(u); pavolmarko@117: if (iter == end()) pavolmarko@117: return; pavolmarko@117: iter.erase(); pavolmarko@117: } 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_