/*****************************************************************************/
/* SOURCE FILE */
/*****************************************************************************/
/*
$Archive: $
$Revision: $
$Date: $
$Author: $
Description: Implementation of the Hash table object
TOOL And XML FORMS License
==========================
Except where otherwise noted, all of the documentation
and software included in the TOOL package is
copyrighted by Michael Swartzendruber.
Copyright (C) 2005 Michael John Swartzendruber.
All rights reserved.
Access to this code, whether intentional or accidental,
does NOT IMPLY any transfer of rights.
This software is provided "as-is," without any express
or implied warranty. In no event shall the author be held
liable for any damages arising from the use of this software.
Permission is granted to anyone to use this software for
any purpose, including commercial applications, and to
alter and redistribute it, provided that the following
conditions are met:
1. All redistributions of source code files must retain
all copyright notices that are currently in place,
and this list of conditions without modification.
2. The origin of this software must not be misrepresented;
you must not claim that you wrote the original software.
3. If you use this software in another product, an acknowledgment
in the product documentation would be appreciated but is
not required.
4. Modified versions in source or binary form must be plainly
marked as such, and must not be misrepresented as being
the original software.
*/
static char OBJECT_ID[] = "$Revision: $ : $Date: $";
/*****************************************************************************/
#include "../../../stdafx.h"
#include "../VMException.h"
#include "../VMCoreGlobal.h"
#include "VMHashTable.h"
/*****************************************************************************/
/*
FUNCTION NAME: VMVMHashFunction
DESCRIPTION: various hash functions
INPUT: the value to hash
buckets - the number of buckets in the table
OUTPUT:
RETURNS: the hash value
*/
size_t VMHashFunction( int x, size_t buckets )
{
return( size_t( x % int( buckets ) ) );
}
size_t VMHashFunction( unsigned int x, size_t buckets )
{
return( size_t( x % (unsigned int)( buckets ) ) );
}
size_t VMHashFunction( long x, size_t buckets )
{
return( size_t( x % long( buckets ) ) );
}
size_t VMHashFunction( unsigned long x, size_t buckets )
{
return( size_t( x % (unsigned long)( buckets ) ) );
}
size_t VMHashFunction( const char* x, size_t buckets )
{
// assume that character array is null terminated!
//
unsigned long n = 0;
const char* ch = x;
while ( *ch )
{
n <<= 1;
n += size_t( *ch );
++ch; // 2b|!2b==?
}
return( size_t( n % (unsigned long)buckets ) );
}
size_t VMHashFunction( const VMVariant& x, size_t buckets )
{
unsigned long n = 0;
if ( ( DT_VAR == x.v_type )
|| ( DT_QUEUE == x.v_type )
|| ( DT_STACK == x.v_type )
|| ( DT_HASHTABLE == x.v_type )
|| ( DT_FILEFINDHANDLE == x.v_type )
|| ( DT_IOSTREAM == x.v_type )
|| ( DT_RCODE == x.v_type )
|| ( DT_BYTECODE == x.v_type )
|| ( DT_CODE == x.v_type )
|| ( DT_DICTIONARY == x.v_type )
|| ( DT_VECTOR == x.v_type )
|| ( DT_NIL == x.v_type )
|| ( DT_CLASS == x.v_type )
|| ( DT_OBJECT == x.v_type ) )
{
throw new VMException( __FILE__, __LINE__, VMException::BADKEYTYPE, VMException::fatal );
}
// derive a hash for each kind of 'hashable' variant value
return( size_t( n % (unsigned long)buckets ) );
}
/* End of function "VMHashFunction"
/*****************************************************************************/
bool VMVariant::Equals( VMVariant& xOther ) const
{
if ( v_type != xOther.v_type )
return( false );
else
{
char* pMe;
char* pHim;
switch( v_type )
{
case DT_BYTE:
return ( v.v_byte == xOther.v.v_byte );
break;
case DT_DOUBLE:
return ( v.v_double == xOther.v.v_double );
break;
case DT_INTEGER:
return ( v.v_integer == xOther.v.v_integer );
break;
case DT_STRING:
// if ( v.v_string->str_size != xOther.v.v_string->str_size )
// return( false );
pMe = v.v_string->str_data;
pHim = xOther.v.v_string->str_data;
return( 0 == strcmp( pMe, pHim ) );
break;
case DT_FILE:
case DT_KERNELHANDLE:
return ( v.v_kernelhandle == xOther.v.v_kernelhandle );
break;
case DT_NTFILEHANDLE:
case DT_HANDLE:
return ( v.v_handle == xOther.v.v_handle );
break;
case DT_DATETIME:
return ( 0 == ( memcmp( &v.v_datetime, &xOther.v.v_datetime, sizeof( SYSTEMTIME ) ) ) );
break;
case DT_DWORD:
return ( v.v_dword == xOther.v.v_dword );
break;
default:
return( false );
break;
}
}
return( false );
}
void VMHashTable::DeepCopy( const VMHashTable& ht )
{
if ( LockCount > 0 )
throw new VMException( __FILE__, __LINE__, VMException::LOCKVIO, VMException::fatal );
Count = ht.Count;
for ( size_t n = 0; n < ciNumBuckets; ++n )
Bucket[ n ] = ht.Bucket[ n ];
}
void VMHashTable::Erase( void )
{
if (LockCount > 0)
throw new VMException( __FILE__, __LINE__, VMException::LOCKVIO, VMException::fatal );
Count = 0;
for ( size_t n = 0; n < ciNumBuckets; ++n )
Bucket[ n ].Erase();
}
VMHashTable::VMHashTable( void )
{
Count = 0;
LockCount = 0;
}
VMHashTable::VMHashTable( const VMHashTable& dict )
{
Count = 0;
LockCount = 0;
DeepCopy( dict );
}
VMHashTable::~VMHashTable()
{
Erase();
}
void VMHashTable::operator = ( const VMHashTable& dict )
{
Erase();
DeepCopy( dict );
}
void VMHashTable::Insert( const VMVariant& kx, const VMVariant& dx )
{
if ( LockCount > 0 )
throw new VMException( __FILE__, __LINE__, VMException::LOCKVIO, VMException::fatal );
VMHashtableEntry e;
e.Key.CloneValue( kx );
e.Data.CloneValue( dx );
Bucket[ VMHashFunction( kx, ciNumBuckets ) ].Append( e );
++Count;
}
bool VMHashTable::Delete( const VMVariant& kx )
{
if ( LockCount > 0 )
throw new VMException( __FILE__, __LINE__, VMException::LOCKVIO, VMException::fatal );
if ( 0 == Count )
throw new VMException( __FILE__, __LINE__, VMException::EMPTY, VMException::fatal );
size_t bno = VMHashFunction( kx, ciNumBuckets );
if ( Bucket[ bno ].GetCount() != 0 )
{
Bucket[ bno ].ToHead();
do
{
if ( kx.Equals( ( *( Bucket[ bno ] ) ).Key ) )
{
Bucket[ bno ].Delete();
--Count;
return(true );
}
} while ( Bucket[ bno ].ToNext() );
}
return( false );
}
bool VMHashTable::Holds( const VMVariant& kx ) const
{
VMHashTable* pThis = const_cast<VMHashTable*>(this);
if ( Count != 0 )
{
size_t bno = VMHashFunction( kx, ciNumBuckets );
if ( pThis->Bucket[ bno ].GetCount() != 0 )
{
pThis->Bucket[ bno ].ToHead();
do
{
VMHashtableEntry xEntry;
bool bGet = pThis->Bucket[ bno ].Get( xEntry );
if ( bGet && kx.Equals( xEntry.Key ) )
return( true );
} while ( pThis->Bucket[ bno ].ToNext() );
}
}
return( false );
}
bool VMHashTable::LookUp( const VMVariant& kx, VMVariant& roOutput ) const
{
VMHashTable* pThis = const_cast<VMHashTable*>(this);
if ( 0 == Count )
return( false );
size_t bno = VMHashFunction( kx, ciNumBuckets );
if ( pThis->Bucket[ bno ].GetCount() != 0 )
{
pThis->Bucket[ bno ].ToHead();
do
{
VMHashtableEntry xEntry;
bool bGet = pThis->Bucket[ bno ].Get( xEntry );
if ( bGet && kx.Equals( xEntry.Key ) )
{
roOutput = xEntry.Data;
return( true );
}
} while ( pThis->Bucket[ bno ].ToNext() );
}
return( false );
}
void VMHashTable::Traverse( void (* func)(const VMVariant& kx,const VMVariant& dx ) )
{
if ( LockCount > 0 )
throw new VMException( __FILE__, __LINE__, VMException::LOCKVIO, VMException::fatal );
if ( 0 == Count )
throw new VMException( __FILE__, __LINE__, VMException::EMPTY, VMException::fatal );
for ( size_t n = 0; n < ciNumBuckets; ++n )
{
if ( Bucket[ n ].GetCount() != 0 )
{
Bucket[ n ].ToHead();
do
{
func( ( *Bucket[ n ] ).Key, ( *Bucket[ n ] ).Data );
} while ( Bucket[ n ].ToNext() );
}
}
}
size_t VMHashTable::GetCount( void ) const
{
return( Count );
}
size_t VMHashTable::GetNumBuck( void ) const
{
return( ciNumBuckets );
}
// constructors
VMHashTableIterator::VMHashTableIterator( const VMHashTable& d )
{
if ( UINT_MAX == d.LockCount )
throw new VMException( __FILE__, __LINE__, VMException::LOCKMAX, VMException::fatal );
if ( 0 == d.Count )
throw new VMException( __FILE__, __LINE__, VMException::EMPTY, VMException::fatal );
Dict = const_cast<VMHashTable*>( &d );
++(Dict->LockCount);
Reset();
}
VMHashTableIterator::VMHashTableIterator( const VMHashTableIterator& iter )
{
Dict = iter.Dict;
if ( UINT_MAX == Dict->LockCount )
throw new VMException( __FILE__, __LINE__, VMException::LOCKMAX, VMException::fatal );
++(Dict->LockCount);
Bno = iter.Bno;
}
// destructors
VMHashTableIterator::~VMHashTableIterator( void )
{
if ( 0 == Dict->LockCount )
throw new VMException( __FILE__, __LINE__, VMException::LOCKZERO, VMException::fatal );
--(Dict->LockCount);
}
// assignment
void VMHashTableIterator::operator =( const VMHashTableIterator& iter )
{
Dict = iter.Dict;
Bno = iter.Bno;
}
// next item
bool VMHashTableIterator::operator ++ ( void )
{
if ( Bno == ciNumBuckets )
return( false );
if ( !Dict->Bucket[ Bno ].ToNext() )
{
++Bno;
if ( Bno == ciNumBuckets )
return( false );
while ( Dict->Bucket[ Bno ].GetCount() == 0 )
{
++Bno;
if ( Bno == ciNumBuckets )
return( false );
}
Dict->Bucket[ Bno ].ToHead();
}
return( true );
}
// reset to first item
void VMHashTableIterator::Reset( void )
{
Bno = 0;
while ( Dict->Bucket[ Bno ].GetCount() == 0 )
++Bno;
Dict->Bucket[ Bno ].ToHead();
}
// get values
VMVariant& VMHashTableIterator::GetData( void )
{
return( ( *( Dict->Bucket[ Bno ] ) ).Data );
}
VMVariant& VMHashTableIterator::GetKey( void )
{
return( ( *( Dict->Bucket[ Bno ] ) ).Key );
}
/*****************************************************************************/
/* Check-in history */
/*
*$Log: $
*/
/*****************************************************************************/
Submit an article or tip