vrpn_HashST.h

/*
 * vrpn_HashST.H
 *
 */
 
 
#ifndef _VRPN_HASHST_H
#define _VRPN_HASHST_H
 
inline unsigned int vrpn_LinearUnsignedIntHashFunction(const unsigned int &i)
{
 return i;
}
 
template <class T>
inline unsigned int vrpn_LinearHashFunction(const T &value)
{
 return (unsigned int)value;
}
 
 
template <class TKey,class TValue>
class vrpn_Hash
{
public:
 vrpn_Hash(int init=16);
 vrpn_Hash(unsigned int (*func)(const TKey &key), int init=16);
 virtual ~vrpn_Hash();
 void Clear();
 
 unsigned int GetNrItems() const { return m_NrItems; }
    TValue& Find(const TKey &key);
 const TValue& Find(const TKey &key) const;
 bool IsPresent(const TValue &value, TKey &key) const;
 
 bool MoveFirst() const;         
 bool MoveNext() const;          
    TValue GetCurrentValue() const; 
    TKey   GetCurrentKey() const;   
 void SetCurrentValue(TValue theValue);  
 bool GetCurrentKeyAndValue(TKey &theKey, TValue &theValue) const;   
 
 bool Add(TKey key, TValue value);   
 bool Remove(TKey key);          
 
private:
 
 struct HashItem
    {
        TKey key;       
        TValue value;   
 struct HashItem *next;  
    };
 
 void ClearItems();  
 void ReHash();      
 void MakeNull(HashItem **table,int size);   
 
 unsigned int m_NrItems;     
 unsigned int m_SizeHash;    
 unsigned int m_InitialSize; 
 
    HashItem **m_Items; 
    HashItem *m_First;  
 
 unsigned int (*HashFunction)(const TKey &key);  
 
 mutable HashItem *m_CurrentItem;        
 
 unsigned int m_Owner;       
};
 
template <class TKey,class TValue>
vrpn_Hash<TKey, TValue>::vrpn_Hash(int init)
{
    HashFunction = vrpn_LinearHashFunction<TKey>;
    m_NrItems = 0;
        m_CurrentItem = 0;
        m_First = 0L;
        m_InitialSize = m_SizeHash = init;
        m_Items = new HashItem*[m_SizeHash];
    MakeNull( m_Items, m_SizeHash );
}
 
template <class TKey,class TValue>
vrpn_Hash<TKey, TValue>::vrpn_Hash(unsigned int (*func)(const TKey &key), int init)
{
    HashFunction = func;
    m_NrItems = 0;
        m_CurrentItem = 0;
        m_First = 0L;
        m_InitialSize = m_SizeHash = init;
        m_Items = new HashItem*[m_SizeHash];
        MakeNull( m_Items, m_SizeHash );
}
 
template <class TKey,class TValue>
vrpn_Hash<TKey, TValue>::~vrpn_Hash()
{   
    ClearItems();
 try {
 delete[] m_Items;
        } catch (...) {
          fprintf(stderr, "vrpn_Hash::~vrpn_Hash(): delete failed\n");
 return;
        }
}
 
template <class TKey,class TValue>
void vrpn_Hash<TKey, TValue>::Clear()
{
    ClearItems();
 
    m_NrItems = 0;
 try {
 delete[] m_Items;
        } catch (...) {
          fprintf(stderr, "vrpn_Hash::Clear(): delete failed\n");
 return;
        }
        m_Items = NULL;
        m_First = 0;
        m_CurrentItem = 0;
 
    m_SizeHash = m_InitialSize;
 try { m_Items = new HashItem*[m_SizeHash]; }
 catch (...) {
          m_SizeHash = 0;
 return;
        }
        MakeNull( m_Items, m_SizeHash );
}
 
template <class TKey,class TValue>
TValue& vrpn_Hash<TKey, TValue>::Find(const TKey &key)
{
    TValue zero = 0;
    TValue &result = zero ;
 
 unsigned int HashValue = HashFunction( key ) % m_SizeHash;
 if ( m_Items[ HashValue ] != 0 )
 if ( m_Items[ HashValue ]->key == key ) 
        {
            result = m_Items[ HashValue ]->value;   
            m_CurrentItem = m_Items[ HashValue ];
        }
 
 return result;
}
 
template <class TKey,class TValue>
const TValue& vrpn_Hash<TKey, TValue>::Find(const TKey &key) const
{
    TValue zero = 0;
    TValue &result = zero ;
 
 unsigned int HashValue = HashFunction( key ) % m_SizeHash;
 if ( m_Items[ HashValue ] != 0 )
 if ( m_Items[ HashValue ]->key == key ) 
            result = m_Items[ HashValue ]->value;   
 
 return result;
}
 
template <class TKey,class TValue>
bool vrpn_Hash<TKey, TValue>::IsPresent(const TValue &value, TKey &key) const
{
 bool searching = MoveFirst();
 
 while( searching )
    {
 if( GetCurrentValue() == value )
        {
            key = GetCurrentKey();
 return true;
        }
        searching = MoveNext();
    }
 
 return false;
 
}
 
template <class TKey,class TValue>
bool vrpn_Hash<TKey, TValue>::Add(TKey key, TValue value)
{
 bool result;
    TKey theKey;
 
 unsigned int HashValue = HashFunction( key ) % m_SizeHash;
    HashItem* elementPointer = m_Items[ HashValue ];
 if (elementPointer != 0)
        theKey = m_Items[ HashValue ]->key;
 
 //---- if object already exists
 if ( elementPointer != 0 )
    {
 if ( theKey == key )
            result = false;
 else
        {
            ReHash();   //--- private function does not have mutex in this class...                 
 
            result = Add( key, value ); //---- mutex must be released here when calling recursively
        }
    }
 
 //---- if object does not exits in the table
 else
    {
        m_NrItems++;
                HashItem *item;
 try { item = new HashItem; }
 catch (...) { return false; }
        item->key = key;
        item->value = value;
        item->next = m_First;
        m_First = item;
        m_Items[ HashValue ] = item;
        m_CurrentItem = m_Items[ HashValue ];
 
        result = true;
    }
 
 return result;
}
 
template <class TKey,class TValue>
bool vrpn_Hash<TKey, TValue>::Remove(TKey key)
{
 bool result = false;
 
 unsigned int HashValue = HashFunction( key ) % m_SizeHash;
 if ( m_Items[ HashValue ] != 0 ) {
 if ( m_Items[ HashValue ]->key == key ) {
        m_NrItems--;
        result = true;
 
 //--adjust pointers
 if ( m_Items[ HashValue ] == m_First ) {
            m_First = m_First->next;
        } else {
            HashItem *item;
 for ( item = m_First ; item->next != m_Items[ HashValue ]; item = item->next );
            item->next = item->next->next;
        }
 
 //--free memory
 try {
 delete m_Items[HashValue]; //free( m_Items[ HashValue ] );
                } catch (...) {
                  fprintf(stderr, "vrpn_Hash::Remove(): delete failed\n");
 return false;
                }
        m_Items[ HashValue ] = 0;
    }
    }
 
 return result;
}
 
template <class TKey,class TValue>
bool vrpn_Hash<TKey, TValue>::MoveFirst() const
{
    m_CurrentItem = m_First;
 
 return ( m_First==NULL ) ? false : true;
}
 
template <class TKey,class TValue>
bool vrpn_Hash<TKey, TValue>::MoveNext() const
{
 if ( m_CurrentItem == NULL ) 
 return false;
 
    m_CurrentItem = m_CurrentItem->next;
 return ( m_CurrentItem != NULL ) ;
}
 
template <class TKey,class TValue>
TValue vrpn_Hash<TKey, TValue>::GetCurrentValue() const
{
 if ( m_CurrentItem  ) 
 return m_CurrentItem->value;
 else
 return 0;
}
 
template <class TKey,class TValue>
void vrpn_Hash<TKey, TValue>::SetCurrentValue(TValue theValue) 
{
 if ( m_CurrentItem )
        m_CurrentItem->value=theValue;
}
 
template <class TKey,class TValue>
TKey vrpn_Hash<TKey, TValue>::GetCurrentKey() const
{
 
 if ( m_CurrentItem  ) 
 return m_CurrentItem->key;
 else
 return 0;
}
 
template <class TKey,class TValue>
bool vrpn_Hash<TKey, TValue>::GetCurrentKeyAndValue(TKey &theKey, TValue &theValue) const
{
 if ( m_CurrentItem  ) {
        theKey = m_CurrentItem->key;
        theValue = m_CurrentItem->value;
 return true;
    } else {
 return false;
        }
}
 
template <class TKey,class TValue>          //--- these functions do not implement the mutex (this is done in the calling function)
void vrpn_Hash<TKey, TValue>::MakeNull(HashItem **table, int size)
{
 for ( int i = 0 ; i < size ; i++ )
        table[i]=0;
}
 
template <class TKey,class TValue>
void vrpn_Hash<TKey, TValue>::ReHash()          //--- these functions do not implement the mutex (this is done in the calling function)
{
    HashItem **temp;
 int OldSizeHash = m_SizeHash;
    m_SizeHash *= 2;
 try { temp = new HashItem*[m_SizeHash]; }
 catch (...) { m_SizeHash = 0;  return; }
    MakeNull( temp, m_SizeHash );
    HashItem *NewFirst = 0;
 for ( HashItem *item = m_First ; item != 0 ; item = item->next )
    {
 unsigned int HashValue = HashFunction( item->key )% OldSizeHash;
                HashItem *NewItem;
 try { NewItem = new HashItem; }
 catch (...) { m_SizeHash = 0; return; }
        NewItem->key = item->key;
        NewItem->value = item->value;
        NewItem->next = NewFirst;
        NewFirst = NewItem;
        HashValue = HashFunction( item->key ) % m_SizeHash;
        temp[ HashValue ] = NewItem;
    }
    ClearItems();
    m_First = NewFirst;
 
 try {
 delete[] m_Items;
        } catch (...) {
          fprintf(stderr, "vrpn_Hash::ReHash(): delete failed\n");
 return;
        }
    m_Items = temp;
}
 
 
template <class TKey,class TValue>
void vrpn_Hash<TKey, TValue>::ClearItems()      
{
 for ( HashItem *item = m_First ; item != 0 ;    )
    {
        HashItem *it = item;
        item = item->next;
 try {
 delete it;
                } catch (...) {
                  fprintf(stderr, "vrpn_Hash::ClearItems(): delete failed\n");
 return;
                }
    }
    m_CurrentItem = 0;
}
 
#endif