diff options
Diffstat (limited to 'Build/source/libs/graphite-engine/src/generic/HashMap.h')
-rw-r--r-- | Build/source/libs/graphite-engine/src/generic/HashMap.h | 328 |
1 files changed, 0 insertions, 328 deletions
diff --git a/Build/source/libs/graphite-engine/src/generic/HashMap.h b/Build/source/libs/graphite-engine/src/generic/HashMap.h deleted file mode 100644 index dc2de9d0af7..00000000000 --- a/Build/source/libs/graphite-engine/src/generic/HashMap.h +++ /dev/null @@ -1,328 +0,0 @@ -/*--------------------------------------------------------------------*//*:Ignore this sentence. -Copyright (C) 2001 SIL International. All rights reserved. - -Distributable under the terms of either the Common Public License or the -GNU Lesser General Public License, as specified in the LICENSING.txt file. - -File: HashMap.h -Responsibility: Steve McConnel -Last reviewed: Not yet. - -Description: - This provides a set of template collection classes to replace std::map. Their primary - reason to exist is to allow explicit checking for internal memory allocation failures. -----------------------------------------------------------------------------------------------*/ -#pragma once -#ifndef HASHMAP_H_INCLUDED -#define HASHMAP_H_INCLUDED -//:End Ignore - -/*---------------------------------------------------------------------------------------------- - Functor class for computing a hash value from an arbitrary object. - - Hungarian: hsho -----------------------------------------------------------------------------------------------*/ -class HashObj -{ -public: - int operator () (void * pKey, int cbKey); -}; - -/*---------------------------------------------------------------------------------------------- - Functor class for comparing two arbitrary objects (of the same class) for equality. - - Hungarian: eqlo -----------------------------------------------------------------------------------------------*/ -class EqlObj -{ -public: - bool operator () (void * pKey1, void * pKey2, int cbKey); -}; - -/*---------------------------------------------------------------------------------------------- - Hash map template collection class whose keys are objects of an arbitrary class. - - Hungarian: hm[K][T] -----------------------------------------------------------------------------------------------*/ -template<class K, class T, class H = HashObj, class Eq = EqlObj> class HashMap -{ -public: - //:> Member classes - - /*------------------------------------------------------------------------------------------ - This is the basic data structure for storing one key-value pair in a hash map. In - order to handle hash collisions, this structure is a member of a linked list. - Hungarian: hsnd - ------------------------------------------------------------------------------------------*/ - class HashNode - { - public: - //:> Constructors/destructors/etc. - - HashNode(void) - : m_key(K()), m_value(T()), m_nHash(0), m_ihsndNext(0) - { - } - HashNode(K & key, T & value, int nHash, int ihsndNext = -1) - : m_key(key), m_value(value), m_nHash(nHash), m_ihsndNext(ihsndNext) - { - } - ~HashNode() - { - } - - //:> Member variable access - - void PutKey(K & key) - { - m_key = key; - } - K & GetKey() - { - return m_key; - } - void PutValue(T & value) - { - m_value = value; - } - T & GetValue() - { - return m_value; - } - void PutHash(int nHash) - { - m_nHash = nHash; - } - int GetHash() - { - return m_nHash; - } - void PutNext(int ihsndNext) - { - m_ihsndNext = ihsndNext; - } - int GetNext() - { - return m_ihsndNext; - } - - /*-------------------------------------------------------------------------------------- - Check whether the given HashNode is being used. - --------------------------------------------------------------------------------------*/ - bool InUse() - { - return m_ihsndNext >= -1; - } - - protected: - //:> Member variables - - K m_key; - T m_value; - int m_nHash; - int m_ihsndNext; // -1 means end of list, -(ihsnd + 3) for free list members - }; - - /*------------------------------------------------------------------------------------------ - This provides an iterator for stepping through all HashNodes stored in the hash map. - This is useful primarily for saving the contents of a hash map to a file. - - Hungarian: ithm[K][T] - ------------------------------------------------------------------------------------------*/ - class iterator - { - public: - // Constructors/destructors/etc. - - iterator() : m_phmParent(NULL), m_ihsnd(0) - { - } - iterator(HashMap<K,T,H,Eq> * phm, int ihsnd) : m_phmParent(phm), m_ihsnd(ihsnd) - { - } - iterator(const iterator & v) : m_phmParent(v.m_phmParent), m_ihsnd(v.m_ihsnd) - { - } - ~iterator() - { - } - - // Other public methods - - iterator & operator = (const iterator & ithm) - { - m_phmParent = ithm.m_phmParent; - m_ihsnd = ithm.m_ihsnd; - return *this; - } - T & operator * (void) - { - Assert(m_phmParent); - Assert(m_phmParent->m_prghsnd); - Assert(m_ihsnd < m_phmParent->m_ihsndLim); - return m_phmParent->m_prghsnd[m_ihsnd].GetValue(); - } - HashNode * operator -> (void) - { - Assert(m_phmParent); - Assert(m_phmParent->m_prghsnd); - Assert(m_ihsnd < m_phmParent->m_ihsndLim); - return &m_phmParent->m_prghsnd[m_ihsnd]; - } - iterator & operator ++ (void) - { - Assert(m_phmParent); - ++m_ihsnd; - // make sure that this new HashNode is actually in use - while (m_ihsnd < m_phmParent->m_ihsndLim) - { - if (m_phmParent->m_prghsnd[m_ihsnd].InUse()) - return *this; - // skip to the next one and check it - ++m_ihsnd; - } - if (m_ihsnd > m_phmParent->m_ihsndLim) - m_ihsnd = m_phmParent->m_ihsndLim; - return *this; - } - bool operator == (const iterator & ithm) - { - return (m_phmParent == ithm.m_phmParent) && (m_ihsnd == ithm.m_ihsnd); - } - bool operator != (const iterator & ithm) - { - return (m_phmParent != ithm.m_phmParent) || (m_ihsnd != ithm.m_ihsnd); - } - T & GetValue(void) - { - Assert(m_phmParent); - Assert(m_phmParent->m_prghsnd); - Assert(m_ihsnd < m_phmParent->m_ihsndLim); - Assert(m_phmParent->m_prghsnd[m_ihsnd].InUse()); - return m_phmParent->m_prghsnd[m_ihsnd].GetValue(); - } - K & GetKey(void) - { - Assert(m_phmParent); - Assert(m_phmParent->m_prghsnd); - Assert(m_ihsnd < m_phmParent->m_ihsndLim); - Assert(m_phmParent->m_prghsnd[m_ihsnd].InUse()); - return m_phmParent->m_prghsnd[m_ihsnd].GetKey(); - } - int GetHash() - { - Assert(m_phmParent); - Assert(m_phmParent->m_prghsnd); - Assert(m_ihsnd < m_phmParent->m_ihsndLim); - Assert(m_phmParent->m_prghsnd[m_ihsnd].InUse()); - return m_phmParent->m_prghsnd[m_ihsnd].GetHash(); - } - int GetIndex() - { - Assert(m_phmParent); - Assert(m_phmParent->m_prghsnd); - Assert(m_ihsnd < m_phmParent->m_ihsndLim); - Assert(m_phmParent->m_prghsnd[m_ihsnd].InUse()); - return m_ihsnd; - } - - protected: - //:> Member variables - - HashMap<K,T,H,Eq> * m_phmParent; - int m_ihsnd; - }; - friend class iterator; - - //:> Constructors/destructors/etc. - - HashMap(); - ~HashMap(); - HashMap(HashMap<K,T,H,Eq> & hm); - - //:> Other public methods - - iterator Begin(); - iterator End(); - void Insert(K & key, T & value, bool fOverwrite = false, int * pihsndOut = NULL); - bool Retrieve(K & key, T * pvalueRet); - bool Delete(K & key); - void Clear(); - void CopyTo(HashMap<K,T,H,Eq> & hmKT); - void CopyTo(HashMap<K,T,H,Eq> * phmKT); - - bool GetIndex(K & key, int * pihsndRet); - bool IndexKey(int ihsnd, K * pkeyRet); - bool IndexValue(int ihsnd, T * pvalueRet); - - int Size(); - - /*------------------------------------------------------------------------------------------ - The assignment operator allows an entire hashmap to be assigned as the value of another - hashmap. It throws an error if it runs out of memory. - - @return a reference to this hashmap. (That is how the assignment operator is defined!) - - @param hm is a reference to the other hashmap. - ------------------------------------------------------------------------------------------*/ - HashMap<K,T,H,Eq> & operator = (HashMap<K,T,H,Eq> & hm) - { - hm.CopyTo(this); - return *this; - } - - //:Ignore -#ifdef DEBUG - int _BucketCount(); - int _EmptyBuckets(); - int _BucketsUsed(); - int _FullestBucket(); - bool AssertValid() - { - AssertPtrN(m_prgihsndBuckets); - Assert(m_prgihsndBuckets || !m_cBuckets); - Assert(!m_prgihsndBuckets || m_cBuckets); - AssertArray(m_prgihsndBuckets, m_cBuckets); - AssertPtrN(m_prghsnd); - Assert(m_prghsnd || !m_ihsndMax); - Assert(!m_prghsnd || m_ihsndMax); - AssertArray(m_prghsnd, m_ihsndMax); - Assert(0 <= m_ihsndLim && m_ihsndLim <= m_ihsndMax); - Assert(-1 <= FreeListIdx(m_ihsndFirstFree)); - Assert(FreeListIdx(m_ihsndFirstFree) < m_ihsndLim); - return true; - } -#endif - //:End Ignore - -protected: - //:> Member variables - - int * m_prgihsndBuckets; - int m_cBuckets; - HashNode * m_prghsnd; - int m_ihsndLim; - int m_ihsndMax; - int m_ihsndFirstFree; // stores -(ihsnd + 3) - - //:> Protected methods - //:Ignore - - /*------------------------------------------------------------------------------------------ - Map between real index and "free list" index. Note that this mapping is bidirectional. - ------------------------------------------------------------------------------------------*/ - int FreeListIdx(int ihsnd) - { - return -(ihsnd + 3); - } - //:End Ignore -}; - - -// Local Variables: -// mode:C++ -// c-file-style:"cellar" -// tab-width:4 -// End: - -#endif /*HASHMAP_H_INCLUDED*/ |