Source: classlib/include/classlib/hashimp.h
|
|
|
|
/***************************************************************************
hashimp.h - impementazione di tabelle di Hashing
-------------------
begin : ven dic 7 17:40:01 CET 2001
copyright : (C) 2001 by Nicola De Nisco
email : nicola@winada.it
***************************************************************************/
/***************************************************************************
* *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 2 of the License, or *
* (at your option) any later version. *
* *
***************************************************************************/
/*
Note: Hash tables can determine the hash value of an object by
calling a member function or global function named HashValue().
For member functions, the following prototype should be used:
unsigned HashValue() const;
For global functions, then following prototype should be used:
unsigned HashValue( const T& t );
If the global function is used, the member function does not need to
be defined.
*/
#if !defined( __CLASSLIB_HASHIMP_H )
#define __CLASSLIB_HASHIMP_H
#if !defined( __CHECKS_H )
#include
#endif // __CHECKS_H
#if !defined( __CLASSLIB_DEFS_H )
#include "classlib/defs.h"
#endif // __CLASSLIB_DEFS_H
#if !defined( __CLASSLIB_LISTIMP_H )
#include "classlib/listimp.h"
#endif // __CLASSLIB_LISTIMP_H
#if !defined( __CLASSLIB_VECTIMP_H )
#include "classlib/vectimp.h"
#endif // __CLASSLIB_VECTIMP_H
/**
template unsigned HashValue( T & t )
unsigned HashValue( void *& )
Template function which calls the HashValue() member function for
an object of type T. The (void *) non-template function is
defined so that indirect container templates will compile. It
should never be called.
*/
inline unsigned HashValue( void *& t )
{
return unsigned(t);
}
/**
template unsigned HashValue( T & t )
unsigned HashValue( void *& )
Template function which calls the HashValue() member function for
an object of type T. The (void *) non-template function is
defined so that indirect container templates will compile. It
should never be called.
*/
inline unsigned HashValue( const TVoidPointer& t )
{
return unsigned(STATIC_CAST(void *,t));
}
/**
template unsigned HashValue( T & t )
unsigned HashValue( void *& )
Template function which calls the HashValue() member function for
an object of type T. The (void *) non-template function is
defined so that indirect container templates will compile. It
should never be called.
*/
template inline unsigned HashValue( const T& t )
{
return t.HashValue();
}
/**
[INTERNAL USE ONLY]
template class TMInternalHashImp
Used internally.
*/
template
class TMInternalHashTableIteratorImp;
template class TMInternalHashImp
{
public:
friend class TMInternalHashTableIteratorImp;
TMInternalHashImp( unsigned size ) :
ItemsInContainer(0),
Table(size),
Size(size)
{
}
virtual ~TMInternalHashImp()
{
}
unsigned GetItemsInContainer() const
{
return ItemsInContainer;
}
int IsEmpty() const
{
return ItemsInContainer == 0;
}
protected:
unsigned TableSize() const
{
return Size;
}
unsigned ItemsInContainer;
TMIVectorImp Table;
private:
virtual unsigned GetHashValue( const T& t ) const = 0;
unsigned Size;
};
/**
template
class TMInternalHashTableIteratorImp
Used internally.
*/
template
class TMInternalHashTableIteratorImp
{
public:
TMInternalHashTableIteratorImp( const TMInternalHashImp& h ) :
HashIter(h.Table),
ListIter(0)
{
Restart();
}
~TMInternalHashTableIteratorImp()
{
if( ListIter ) {
delete ListIter;
ListIter = 0;
}
}
operator int()
{
return HashIter ? (ListIter ? (*ListIter) : 0) : 0;
}
const T& Current()
{
PRECONDITION( ListIter != 0 );
return ListIter->Current();
}
const T& operator ++ ( int )
{
PRECONDITION( ListIter != 0 );
const T& t = ListIter->Current();
Scan();
return t;
}
T operator ++ ()
{
PRECONDITION( ListIter != 0 );
Scan();
PRECONDITION( ListIter != 0 );
return ListIter->Current();
}
void Restart();
private:
TMIVectorIteratorImp HashIter;
TMListIteratorImp *ListIter;
void Scan();
};
template
void TMInternalHashTableIteratorImp::Restart()
{
HashIter.Restart();
delete ListIter; ListIter = 0;
while( HashIter && HashIter.Current() == 0 )
HashIter++;
ListIter = HashIter ?
new TMListIteratorImp( *HashIter.Current() ) : 0;
}
template
void TMInternalHashTableIteratorImp::Scan()
{
PRECONDITION( ListIter != 0 );
// if not at end of list, then iterate to the next item
if( *ListIter )
(*ListIter)++;
// if now at end of list, then iterate to the next list (if any)
if( ! *ListIter )
{
HashIter++;
delete ListIter; ListIter = 0;
while( HashIter != 0 && HashIter.Current() == 0 )
HashIter++;
if( HashIter == 0 )
ListIter = 0;
else
ListIter =
new TMListIteratorImp( *HashIter.Current() );
}
}
template class TMHashTableIteratorImp;
/**
template class TMHashTableImp
template class TMHashTableIteratorImp
Implements a managed hash table of objects of type T, using storage
storage allocator A. Assumes that T has meaningful copy and ==
semantics as well as a default constructor.
*/
template class TMHashTableImp :
private TMInternalHashImp< T,TMListImp >
{
typedef TMInternalHashImp< T,TMListImp > Parent;
public:
friend class TMHashTableIteratorImp;
typedef void (*IterFunc)(T&, void *);
typedef int (*CondFunc)(const T &, void *);
int Add( const T& t );
int Detach( const T& t );
TMHashTableImp( unsigned size = DEFAULT_HASH_TABLE_SIZE ) :
TMInternalHashImp< T,TMListImp >(size)
{
}
void ForEach( IterFunc iter, void *args );
T *FirstThat( CondFunc cond, void *args ) const;
T *LastThat( CondFunc cond, void *args ) const;
T *Find( const T& t ) const;
void Flush();
Parent::GetItemsInContainer;
Parent::IsEmpty;
private:
unsigned GetHashValue( const T& t ) const
{
return HashValue(t) % TableSize();
}
};
template class TMHashTableIteratorImp :
public TMInternalHashTableIteratorImp >
{
public:
TMHashTableIteratorImp( const TMHashTableImp& h ) :
TMInternalHashTableIteratorImp >(h) {}
};
template
int TMHashTableImp::Add( const T& t )
{
unsigned index = GetHashValue(t);
TMListImp *list = Table[index];
if( list == 0 )
{
list = Table[index] = new TMListImp;
}
if( list == 0 )
return 0;
else
{
list->Add(t);
ItemsInContainer++;
return 1;
}
}
template
int TMHashTableImp::Detach( const T& t )
{
unsigned index = GetHashValue(t);
TMListImp *list = Table[index];
if( list == 0 || ! list->Detach(t) )
return 0;
else
{
if( list->IsEmpty() )
{
delete Table[index];
Table[index] = 0;
}
ItemsInContainer--;
return 1;
}
}
template
void TMHashTableImp::ForEach( IterFunc iter, void *args )
{
TMIVectorIteratorImp > iterator(Table);
while( iterator )
{
TMListImp *list = iterator++;
if( list != 0 )
list->ForEach(iter,args);
}
}
template
T *TMHashTableImp::FirstThat( CondFunc cond, void *args ) const
{
TMIVectorIteratorImp > iterator(Table);
while( iterator )
{
TMListImp *list = iterator++;
if( list != 0 ) {
T* Fnd = list->FirstThat(cond,args);
if( Fnd != 0 ) return Fnd;
}
}
return 0;
}
template
T *TMHashTableImp::LastThat( CondFunc cond, void *args ) const
{
T* Fnd = 0;
TMIVectorIteratorImp > iterator(Table);
while( iterator )
{
TMListImp *list = iterator++;
if( list != 0 ) {
T* TmpFnd = list->LastThat(cond,args);
if( TmpFnd != 0 ) Fnd = TmpFnd;
}
}
return Fnd;
}
template
T *TMHashTableImp::Find( const T& t ) const
{
TMListImp *list = Table[GetHashValue(t)];
return list ? list->Find(t) : 0;
}
template void TMHashTableImp::Flush()
{
for( unsigned i = 0; i < TableSize(); i++ )
{
if( Table[i] != 0 )
{
Table[i]->Flush();
delete Table[i];
Table[i] = 0;
}
}
ItemsInContainer = 0;
}
template class THashTableIteratorImp;
/**
template class THashTableImp
template class THashTableIteratorImp
Implements a hash table of objects of type T.
*/
template class THashTableImp :
public TMHashTableImp
{
public:
friend class THashTableIteratorImp;
THashTableImp( unsigned aPrime = DEFAULT_HASH_TABLE_SIZE ) :
TMHashTableImp(aPrime)
{
}
};
template class THashTableIteratorImp :
public TMHashTableIteratorImp
{
public:
THashTableIteratorImp( const THashTableImp& h ) :
TMHashTableIteratorImp(h)
{
}
};
template class TMIHashTableIteratorImp;
/**
template class TMIHashTableImp
template class TMIHashTableIteratorImp
Implements a managed hash table of pointers to objects of type T,
using the storage storage allocator A.
*/
template class TMIHashTableImp :
private TMInternalHashImp >
{
typedef TMInternalHashImp > Parent;
public:
friend class TMIHashTableIteratorImp;
typedef void (*IterFunc)(T&, void *);
typedef int (*CondFunc)(const T &, void *);
TMIHashTableImp( unsigned size = DEFAULT_HASH_TABLE_SIZE ) :
TMInternalHashImp >(size)
{
}
virtual ~TMIHashTableImp()
{
}
int Add( T *t );
int Detach( T *t, int del = 0 );
void ForEach( IterFunc iter, void *args );
T *FirstThat( CondFunc cond, void *args ) const;
T *LastThat( CondFunc cond, void *args ) const;
T *Find( const T *t ) const;
void Flush( int del = 0 );
Parent::GetItemsInContainer;
Parent::IsEmpty;
private:
unsigned GetHashValue( const TVoidPointer& t ) const
{
return HashValue(*STATIC_CAST(T *,STATIC_CAST(void *,t)))%TableSize();
}
};
template
class TMIHashTableIteratorImp :
private TMInternalHashTableIteratorImp >
{
typedef TMInternalHashTableIteratorImp > Parent;
public:
TMIHashTableIteratorImp( const TMIHashTableImp& h ) :
TMInternalHashTableIteratorImp >(h)
{
}
T *Current()
{
return STATIC_CAST(T *,STATIC_CAST(void *,Parent::Current()));
}
T *operator ++ (int)
{
return STATIC_CAST(T *,STATIC_CAST(void *,Parent::operator++(1)));
}
T *operator ++ ()
{
return STATIC_CAST(T *,STATIC_CAST(void *,Parent::operator++()));
}
Parent::Restart;
Parent::operator int;
};
template
void TMIHashTableImp::ForEach( IterFunc iter, void *args )
{
TMIVectorIteratorImp > iterator(Table);
while( iterator )
{
if( iterator.Current() != 0 )
iterator.Current()->ForEach(iter,args);
iterator++;
}
}
template
T *TMIHashTableImp::FirstThat( CondFunc cond, void *args ) const
{
TMIVectorIteratorImp > iterator(Table);
while( iterator )
{
TMIListImp *list = iterator++;
if( list != 0 ) {
T* Fnd = list->FirstThat(cond,args);
if( Fnd != 0 ) return Fnd;
}
}
return 0;
}
template
T *TMIHashTableImp::LastThat( CondFunc cond, void *args ) const
{
T* Fnd = 0;
TMIVectorIteratorImp > iterator(Table);
while( iterator )
{
TMIListImp *list = iterator++;
if( list != 0 ) {
T* TmpFnd = list->LastThat(cond,args);
if( TmpFnd != 0 ) Fnd = TmpFnd;
}
}
return Fnd;
}
template
T *TMIHashTableImp::Find( const T *t ) const
{
TMIListImp *list = Table[GetHashValue(t)];
return list ? list->Find(t) : 0;
}
template int TMIHashTableImp::Add( T *t )
{
unsigned index = GetHashValue(t);
TMIListImp *list = Table[index];
if( list == 0 )
{
list = Table[index] = new TMIListImp;
}
if( list == 0 )
return 0;
else
{
list->Add(t);
ItemsInContainer++;
return 1;
}
}
template
int TMIHashTableImp::Detach( T *t, int del )
{
unsigned index = GetHashValue(t);
TMIListImp *list = Table[index];
if( list == 0 || ! list->Detach( t, del ) )
return 0;
else
{
if( list->IsEmpty() )
{
delete Table[index];
Table[index] = 0;
}
ItemsInContainer--;
return 1;
}
}
template
void TMIHashTableImp::Flush( int del )
{
for( unsigned i = 0; i < TableSize(); i++ )
{
if( Table[i] != 0 )
{
Table[i]->Flush(del);
delete Table[i];
Table[i] = 0;
}
}
ItemsInContainer = 0;
}
template class TIHashTableIteratorImp;
/**
template class TIHashTableImp
template class TIHashTableIteratorImp
Implements a hash table of pointers to objects of type T
*/
template class TIHashTableImp :
public TMIHashTableImp
{
public:
friend class TIHashTableIteratorImp;
TIHashTableImp( unsigned aPrime = DEFAULT_HASH_TABLE_SIZE ) :
TMIHashTableImp( aPrime)
{
}
};
/**
template class TIHashTableImp
template class TIHashTableIteratorImp
Implements a hash table of pointers to objects of type T
*/
template class TIHashTableIteratorImp :
public TMIHashTableIteratorImp
{
public:
TIHashTableIteratorImp( const TIHashTableImp& h ) :
TMIHashTableIteratorImp(h)
{
}
};
#endif // __CLASSLIB_HASHIMP_H
| Generated by: nicola on gulliver.wadahome.it on Sun May 25 13:54:34 2003, using kdoc 2.0a53. |