Show hashtable_inl.h syntax highlighted
/***************************************************************************
hashtable_inl.h - Hash table implementation
-------------------
begin : Sun Sep 1 2002
copyright : (C) 2002 by Reality Rift Studios
email : mattias@realityrift.com
***************************************************************************
The contents of this file are subject to the Mozilla Public License Version
1.1 (the "License"); you may not use this file except in compliance with
the License. You may obtain a copy of the License at
http://www.mozilla.org/MPL/
Software distributed under the License is distributed on an "AS IS" basis,
WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
for the specific language governing rights and limitations under the
License.
The Original Code is the NeoEngine, hashtable_inl.h
The Initial Developer of the Original Code is Mattias Jansson.
Portions created by Mattias Jansson are Copyright (C) 2002
Reality Rift Studios. All Rights Reserved.
***************************************************************************/
template < class HashTableType > inline HashTableNode< HashTableType >::HashTableNode( const HashString &rstrKey, HashTableType *pkData ) :
m_strKey( rstrKey ),
m_pkData( pkData )
{
}
template < class HashTableType > inline HashTableNode< HashTableType >::HashTableNode( const HashTableNode< HashTableType > &rkNode ) :
m_strKey( rkNode.m_strKey ),
m_pkData( rkNode.m_pkData )
{
}
template < class HashTableType > inline typename HashTable< HashTableType >::HashTableNodeType *HashTable< HashTableType >::LookupNode( const HashString &rstrKey, int iIndex )
{
unsigned int i = ( iIndex ? iIndex : rstrKey.GetHash() ) % m_iSize;
if( !m_pvkTable[i].size() )
return 0;
typename HashTableNodeVec::iterator pkNode = m_pvkTable[i].begin();
typename HashTableNodeVec::iterator pkEnd = m_pvkTable[i].end();
for( ; pkNode != pkEnd; ++pkNode )
{
if( pkNode->m_strKey == rstrKey )
return &(*pkNode);
}
return 0;
}
template < class HashTableType > HashTable< HashTableType >::HashTable( int iSize ) :
m_pvkTable( new HashTableNodeVec[ iSize ] ),
m_iSize( iSize ),
m_uiElements( 0 )
{
}
template < class HashTableType > HashTable< HashTableType >::~HashTable()
{
delete [] m_pvkTable;
}
template < class HashTableType > HashTableType *HashTable< HashTableType >::Insert( const HashString &rstrKey, HashTableType *pkData )
{
assert( m_pvkTable );
unsigned int i = rstrKey.GetHash() % m_iSize;
HashTableNodeType *pkNode = LookupNode( rstrKey, i );
if( pkNode )
{
HashTableType *pkRet = pkNode->m_pkData;
pkNode->m_pkData = pkData;
return pkRet;
}
m_pvkTable[i].push_back( HashTableNodeType( rstrKey, pkData ) );
++m_uiElements;
return 0;
}
template < class HashTableType > HashTableType *HashTable< HashTableType >::Find( const HashString &rstrKey )
{
assert( m_pvkTable );
HashTableNodeType *pkNode = LookupNode( rstrKey );
return( pkNode ? pkNode->m_pkData : 0 );
}
template < class HashTableType > HashTableType *HashTable< HashTableType >::Delete( const HashString &rstrKey, HashTableType *pkData )
{
assert( m_pvkTable );
unsigned int i = rstrKey.GetHash() % m_iSize;
typename HashTableNodeVec::iterator pkNode = m_pvkTable[i].begin();
typename HashTableNodeVec::iterator pkEnd = m_pvkTable[i].end();
for( ; pkNode != pkEnd; ++pkNode )
{
if( pkNode->m_strKey == rstrKey )
{
if( !pkData || ( pkData == pkNode->m_pkData ) )
{
HashTableType *pkRet = pkNode->m_pkData;
m_pvkTable[i].erase( pkNode );
assert( m_uiElements );
--m_uiElements;
return pkRet;
}
return 0;
}
}
return 0;
}
template < class HashTableType > void HashTable< HashTableType >::GetAllNodes( std::vector< HashTableNode< HashTableType >* > *pvpkVector )
{
unsigned int uiSize = pvpkVector->size();
pvpkVector->resize( uiSize + m_uiElements );
typename HashTableNodePtrVec::iterator ppkDest = pvpkVector->begin() + uiSize;
for( int i = 0; i < m_iSize; ++i )
{
if( !m_pvkTable[i].size() )
continue;
typename HashTableNodeVec::iterator pkNode = m_pvkTable[i].begin();
typename HashTableNodeVec::iterator pkEnd = m_pvkTable[i].end();
for( ; pkNode != pkEnd; ++pkNode, ++ppkDest )
*ppkDest = &(*pkNode);
}
}
template < class HashTableType > void HashTable< HashTableType >::GetAllNodeData( std::vector< HashTableType* > *pvpkVector )
{
unsigned int uiSize = pvpkVector->size();
pvpkVector->resize( uiSize + m_uiElements );
typename std::vector< HashTableType* >::iterator ppkDest = pvpkVector->begin() + uiSize;
for( int i = 0; i < m_iSize; ++i )
{
if( !m_pvkTable[i].size() )
continue;
typename HashTableNodeVec::iterator pkNode = m_pvkTable[i].begin();
typename HashTableNodeVec::iterator pkEnd = m_pvkTable[i].end();
for( ; pkNode != pkEnd; ++pkNode, ++ppkDest )
*ppkDest = pkNode->m_pkData;
}
}
template < class HashTableType > void HashTable< HashTableType >::Clear()
{
for( int i = 0; i < m_iSize; ++i )
m_pvkTable[i].clear();
m_uiElements = 0;
}
See more files for this project here