#include <hash.h>

Classes
class	THashKeyDatCmp
Public Types
enum	{ HashPrimes = 32 }
typedef THashKeyDatI< TKey, TDat >	TIter
Public Member Functions
	THash ()
	THash (const THash &Hash)
	THash (const int &ExpectVals, const bool &_AutoSizeP=false)
	THash (TSIn &SIn)
void	Load (TSIn &SIn)
void	Save (TSOut &SOut) const
void	LoadXml (const PXmlTok &XmlTok, const TStr &Nm="")
void	SaveXml (TSOut &SOut, const TStr &Nm)
THash &	operator= (const THash &Hash)
bool	operator== (const THash &Hash) const
bool	operator< (const THash &Hash) const
const TDat &	operator[] (const int &KeyId) const
TDat &	operator[] (const int &KeyId)
TDat &	operator() (const TKey &Key)
::TSize	GetMemUsed () const
TIter	BegI () const
TIter	EndI () const
TIter	GetI (const TKey &Key) const
void	Gen (const int &ExpectVals)
void	Clr (const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
bool	Empty () const
int	Len () const
int	GetPorts () const
bool	IsAutoSize () const
int	GetMxKeyIds () const
int	GetReservedKeyIds () const
bool	IsKeyIdEqKeyN () const
int	AddKey (const TKey &Key)
TDat &	AddDatId (const TKey &Key)
TDat &	AddDat (const TKey &Key)
TDat &	AddDat (const TKey &Key, const TDat &Dat)
void	DelKey (const TKey &Key)
void	DelIfKey (const TKey &Key)
void	DelKeyId (const int &KeyId)
void	DelKeyIdV (const TIntV &KeyIdV)
void	MarkDelKey (const TKey &Key)
void	MarkDelKeyId (const int &KeyId)
const TKey &	GetKey (const int &KeyId) const
int	GetKeyId (const TKey &Key) const
int	GetRndKeyId (TRnd &Rnd) const
	Get an index of a random element. If the hash table has many deleted keys, this may take a long time.
int	GetRndKeyId (TRnd &Rnd, const double &EmptyFrac)
	Get an index of a random element. If the hash table has many deleted keys, defrag the hash table first (that's why the function is non-const).
bool	IsKey (const TKey &Key) const
bool	IsKey (const TKey &Key, int &KeyId) const
bool	IsKeyId (const int &KeyId) const
const TDat &	GetDat (const TKey &Key) const
TDat &	GetDat (const TKey &Key)
void	GetKeyDat (const int &KeyId, TKey &Key, TDat &Dat) const
bool	IsKeyGetDat (const TKey &Key, TDat &Dat) const
int	FFirstKeyId () const
bool	FNextKeyId (int &KeyId) const
void	GetKeyV (TVec< TKey > &KeyV) const
void	GetDatV (TVec< TDat > &DatV) const
void	GetKeyDatPrV (TVec< TPair< TKey, TDat > > &KeyDatPrV) const
void	GetDatKeyPrV (TVec< TPair< TDat, TKey > > &DatKeyPrV) const
void	GetKeyDatKdV (TVec< TKeyDat< TKey, TDat > > &KeyDatKdV) const
void	GetDatKeyKdV (TVec< TKeyDat< TDat, TKey > > &DatKeyKdV) const
void	Swap (THash &Hash)
void	Defrag ()
void	Pack ()
void	Sort (const bool &CmpKey, const bool &Asc)
void	SortByKey (const bool &Asc=true)
void	SortByDat (const bool &Asc=true)
Static Public Attributes
static const unsigned int	HashPrimeT [HashPrimes]
Private Types
typedef THashKeyDat< TKey, TDat >	THKeyDat
typedef TPair< TKey, TDat >	TKeyDatP
Private Member Functions
THKeyDat &	GetHashKeyDat (const int &KeyId)
const THKeyDat &	GetHashKeyDat (const int &KeyId) const
uint	GetNextPrime (const uint &Val) const
void	Resize ()
Private Attributes
TIntV	PortV
TVec< THKeyDat >	KeyDatV
TBool	AutoSizeP
TInt	FFreeKeyId
TInt	FreeKeys

Detailed Description

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
class THash< TKey, TDat, THashFunc >

Definition at line 87 of file hash.h.

Member Typedef Documentation

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

typedef THashKeyDat<TKey, TDat> THash< TKey, TDat, THashFunc >::THKeyDat [private]

Definition at line 94 of file hash.h.

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

typedef THashKeyDatI<TKey, TDat> THash< TKey, TDat, THashFunc >::TIter

Definition at line 92 of file hash.h.

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

typedef TPair<TKey, TDat> THash< TKey, TDat, THashFunc >::TKeyDatP [private]

Definition at line 95 of file hash.h.

Member Enumeration Documentation

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

anonymous enum

Enumerator:

HashPrimes

Definition at line 89 of file hash.h.

{HashPrimes=32};

Constructor & Destructor Documentation

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

THash< TKey, TDat, THashFunc >::THash ( ) [inline]

Definition at line 125 of file hash.h.

         :
    PortV(), KeyDatV(),
    AutoSizeP(true), FFreeKeyId(-1), FreeKeys(0){}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

THash< TKey, TDat, THashFunc >::THash ( const THash< TKey, TDat, THashFunc > & Hash ) [inline]

Definition at line 128 of file hash.h.

                          :
    PortV(Hash.PortV), KeyDatV(Hash.KeyDatV), AutoSizeP(Hash.AutoSizeP),
    FFreeKeyId(Hash.FFreeKeyId), FreeKeys(Hash.FreeKeys){}

template<class TKey , class TDat , class THashFunc >

THash< TKey, TDat, THashFunc >::THash	(	const int &	ExpectVals,
		const bool &	_AutoSizeP = `false`
	)		`[explicit]`

Definition at line 295 of file hash.h.

                                                                                :
  PortV(GetNextPrime(ExpectVals/2)), KeyDatV(ExpectVals, 0),
  AutoSizeP(_AutoSizeP), FFreeKeyId(-1), FreeKeys(0){
  PortV.PutAll(TInt(-1));
}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

THash< TKey, TDat, THashFunc >::THash ( TSIn & SIn ) [inline, explicit]

Definition at line 132 of file hash.h.

                           :
    PortV(SIn), KeyDatV(SIn),
    AutoSizeP(SIn), FFreeKeyId(SIn), FreeKeys(SIn){
    SIn.LoadCs();}

Member Function Documentation

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

TDat& THash< TKey, TDat, THashFunc >::AddDat ( const TKey & Key ) [inline]

Definition at line 194 of file hash.h.

{return KeyDatV[AddKey(Key)].Dat;}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

TDat& THash< TKey, TDat, THashFunc >::AddDat	(	const TKey &	Key,
		const TDat &	Dat
	)		`[inline]`

Definition at line 195 of file hash.h.

                                                {
    return KeyDatV[AddKey(Key)].Dat=Dat;}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

TDat& THash< TKey, TDat, THashFunc >::AddDatId ( const TKey & Key ) [inline]

Definition at line 192 of file hash.h.

                                 {
    int KeyId=AddKey(Key); return KeyDatV[KeyId].Dat=KeyId;}

template<class TKey, class TDat , class THashFunc >

int THash< TKey, TDat, THashFunc >::AddKey ( const TKey & Key )

Definition at line 325 of file hash.h.

                                                       {
  if ((KeyDatV.Len()>2*PortV.Len())||PortV.Empty()){Resize();}
  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
  int PrevKeyId=-1;
  int KeyId=PortV[PortN];
  while ((KeyId!=-1) &&
   !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
    PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}

  if (KeyId==-1){
    if (FFreeKeyId==-1){
      KeyId=KeyDatV.Add(THKeyDat(-1, HashCd, Key));
    } else {
      KeyId=FFreeKeyId; FFreeKeyId=KeyDatV[FFreeKeyId].Next; FreeKeys--;
      //KeyDatV[KeyId]=TKeyDat(-1, HashCd, Key); // slow version
      KeyDatV[KeyId].Next=-1;
      KeyDatV[KeyId].HashCd=HashCd;
      KeyDatV[KeyId].Key=Key;
      //KeyDatV[KeyId].Dat=TDat(); // already empty
    }
    if (PrevKeyId==-1){
      PortV[PortN]=KeyId;
    } else {
      KeyDatV[PrevKeyId].Next=KeyId;
    }
  }
  return KeyId;
}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

TIter THash< TKey, TDat, THashFunc >::BegI ( ) const [inline]

Definition at line 169 of file hash.h.

                     {
    if (Len() == 0){return TIter(KeyDatV.EndI(), KeyDatV.EndI());}
    if (IsKeyIdEqKeyN()) { return TIter(KeyDatV.BegI(), KeyDatV.EndI());}
    int FKeyId=-1;  FNextKeyId(FKeyId);
    return TIter(KeyDatV.BegI()+FKeyId, KeyDatV.EndI()); }

template<class TKey , class TDat , class THashFunc >

void THash< TKey, TDat, THashFunc >::Clr	(	const bool &	DoDel = `true`,
		const int &	NoDelLim = `-1`,
		const bool &	ResetDat = `true`
	)

Definition at line 313 of file hash.h.

                                                                                                  {
  if (DoDel){
    PortV.Clr(); KeyDatV.Clr();
  } else {
    PortV.PutAll(TInt(-1));
    KeyDatV.Clr(DoDel, NoDelLim);
    if (ResetDat){KeyDatV.PutAll(THKeyDat());}
  }
  FFreeKeyId=TInt(-1); FreeKeys=TInt(0);
}

template<class TKey , class TDat , class THashFunc >

void THash< TKey, TDat, THashFunc >::Defrag ( )

Definition at line 507 of file hash.h.

                                         {
  if (!IsKeyIdEqKeyN()){
    THash<TKey, TDat, THashFunc> Hash(PortV.Len());
    int KeyId=FFirstKeyId(); TKey Key; TDat Dat;
    while (FNextKeyId(KeyId)){
      GetKeyDat(KeyId, Key, Dat);
      Hash.AddDat(Key, Dat);
    }
    Pack();
    operator=(Hash);
    IAssert(IsKeyIdEqKeyN());
  }
}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

void THash< TKey, TDat, THashFunc >::DelIfKey ( const TKey & Key ) [inline]

Definition at line 199 of file hash.h.

                                {
    int KeyId; if (IsKey(Key, KeyId)){DelKeyId(KeyId);}}

template<class TKey, class TDat , class THashFunc >

void THash< TKey, TDat, THashFunc >::DelKey ( const TKey & Key )

Definition at line 356 of file hash.h.

                                                        {
  IAssert(!PortV.Empty());
  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
  int PrevKeyId=-1;
  int KeyId=PortV[PortN];

  while ((KeyId!=-1) &&
   !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
    PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}

  //IAssertR(KeyId!=-1, Key.GetStr()); //J: vsi razredi nimajo nujno funkcije GetStr()?
  IAssert(KeyId!=-1); //J: vsi razredi nimajo nujno funkcije GetStr()?
  if (PrevKeyId==-1){PortV[PortN]=KeyDatV[KeyId].Next;}
  else {KeyDatV[PrevKeyId].Next=KeyDatV[KeyId].Next;}
  KeyDatV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
  KeyDatV[KeyId].HashCd=TInt(-1);
  KeyDatV[KeyId].Key=TKey();
  KeyDatV[KeyId].Dat=TDat();
}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

void THash< TKey, TDat, THashFunc >::DelKeyId ( const int & KeyId ) [inline]

Definition at line 201 of file hash.h.

{DelKey(GetKey(KeyId));}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

void THash< TKey, TDat, THashFunc >::DelKeyIdV ( const TIntV & KeyIdV ) [inline]

Definition at line 202 of file hash.h.

                                     {
    for (int KeyIdN=0; KeyIdN<KeyIdV.Len(); KeyIdN++){DelKeyId(KeyIdV[KeyIdN]);}}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

bool THash< TKey, TDat, THashFunc >::Empty ( ) const [inline]

Definition at line 183 of file hash.h.

{return Len()==0;}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

TIter THash< TKey, TDat, THashFunc >::EndI ( ) const [inline]

Definition at line 174 of file hash.h.

{return TIter(KeyDatV.EndI(), KeyDatV.EndI());}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

int THash< TKey, TDat, THashFunc >::FFirstKeyId ( ) const [inline]

Definition at line 230 of file hash.h.

{return 0-1;}

template<class TKey , class TDat , class THashFunc >

bool THash< TKey, TDat, THashFunc >::FNextKeyId ( int & KeyId ) const

Definition at line 430 of file hash.h.

                                                              {
  do {KeyId++;} while ((KeyId<KeyDatV.Len())&&(KeyDatV[KeyId].HashCd==-1));
  return KeyId<KeyDatV.Len();
}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

void THash< TKey, TDat, THashFunc >::Gen ( const int & ExpectVals ) [inline]

Definition at line 178 of file hash.h.

                                 {
    PortV.Gen(GetNextPrime(ExpectVals/2)); KeyDatV.Gen(ExpectVals, 0);
    FFreeKeyId=-1; FreeKeys=0; PortV.PutAll(TInt(-1));}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

const TDat& THash< TKey, TDat, THashFunc >::GetDat ( const TKey & Key ) const [inline]

Definition at line 218 of file hash.h.

{return KeyDatV[GetKeyId(Key)].Dat;}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

TDat& THash< TKey, TDat, THashFunc >::GetDat ( const TKey & Key ) [inline]

Definition at line 219 of file hash.h.

{return KeyDatV[GetKeyId(Key)].Dat;}

template<class TKey, class TDat, class THashFunc >

void THash< TKey, TDat, THashFunc >::GetDatKeyKdV ( TVec< TKeyDat< TDat, TKey > > & DatKeyKdV ) const

Definition at line 485 of file hash.h.

                                                                                           {
  DatKeyKdV.Gen(Len(), 0);
  TKey Key; TDat Dat;
  int KeyId=FFirstKeyId();
  while (FNextKeyId(KeyId)){
    GetKeyDat(KeyId, Key, Dat);
    DatKeyKdV.Add(TKeyDat<TDat, TKey>(Dat, Key));
  }
}

template<class TKey, class TDat, class THashFunc >

void THash< TKey, TDat, THashFunc >::GetDatKeyPrV ( TVec< TPair< TDat, TKey > > & DatKeyPrV ) const

Definition at line 463 of file hash.h.

                                                                                         {
  DatKeyPrV.Gen(Len(), 0);
  TKey Key; TDat Dat;
  int KeyId=FFirstKeyId();
  while (FNextKeyId(KeyId)){
    GetKeyDat(KeyId, Key, Dat);
    DatKeyPrV.Add(TPair<TDat, TKey>(Dat, Key));
  }
}

template<class TKey , class TDat, class THashFunc >

void THash< TKey, TDat, THashFunc >::GetDatV ( TVec< TDat > & DatV ) const

Definition at line 444 of file hash.h.

                                                                 {
  DatV.Gen(Len(), 0);
  int KeyId=FFirstKeyId();
  while (FNextKeyId(KeyId)){
    DatV.Add(GetHashKeyDat(KeyId).Dat);}
}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

THKeyDat& THash< TKey, TDat, THashFunc >::GetHashKeyDat ( const int & KeyId ) [inline, private]

Definition at line 116 of file hash.h.

                                           {
    THKeyDat& KeyDat=KeyDatV[KeyId];
    Assert(KeyDat.HashCd!=-1); return KeyDat;}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

const THKeyDat& THash< TKey, TDat, THashFunc >::GetHashKeyDat ( const int & KeyId ) const [inline, private]

Definition at line 119 of file hash.h.

                                                        {
    const THKeyDat& KeyDat=KeyDatV[KeyId];
    Assert(KeyDat.HashCd!=-1); return KeyDat;}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

TIter THash< TKey, TDat, THashFunc >::GetI ( const TKey & Key ) const [inline]

Definition at line 176 of file hash.h.

{return TIter(&KeyDatV[GetKeyId(Key)], KeyDatV.EndI());}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

const TKey& THash< TKey, TDat, THashFunc >::GetKey ( const int & KeyId ) const [inline]

Definition at line 208 of file hash.h.

{ return GetHashKeyDat(KeyId).Key;}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

void THash< TKey, TDat, THashFunc >::GetKeyDat	(	const int &	KeyId,
		TKey &	Key,
		TDat &	Dat
	)		const `[inline]`

Definition at line 223 of file hash.h.

                                                               {
    const THKeyDat& KeyDat=GetHashKeyDat(KeyId);
    Key=KeyDat.Key; Dat=KeyDat.Dat;}

template<class TKey, class TDat, class THashFunc >

void THash< TKey, TDat, THashFunc >::GetKeyDatKdV ( TVec< TKeyDat< TKey, TDat > > & KeyDatKdV ) const

Definition at line 474 of file hash.h.

                                                                                           {
  KeyDatKdV.Gen(Len(), 0);
  TKey Key; TDat Dat;
  int KeyId=FFirstKeyId();
  while (FNextKeyId(KeyId)){
    GetKeyDat(KeyId, Key, Dat);
    KeyDatKdV.Add(TKeyDat<TKey, TDat>(Key, Dat));
  }
}

template<class TKey, class TDat, class THashFunc >

void THash< TKey, TDat, THashFunc >::GetKeyDatPrV ( TVec< TPair< TKey, TDat > > & KeyDatPrV ) const

Definition at line 452 of file hash.h.

                                                                                         {
  KeyDatPrV.Gen(Len(), 0);
  TKey Key; TDat Dat;
  int KeyId=FFirstKeyId();
  while (FNextKeyId(KeyId)){
    GetKeyDat(KeyId, Key, Dat);
    KeyDatPrV.Add(TPair<TKey, TDat>(Key, Dat));
  }
}

template<class TKey, class TDat , class THashFunc >

int THash< TKey, TDat, THashFunc >::GetKeyId ( const TKey & Key ) const

Definition at line 418 of file hash.h.

                                                                {
  if (PortV.Empty()){return -1;}
  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
  int KeyId=PortV[PortN];
  while ((KeyId!=-1) &&
   !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
    KeyId=KeyDatV[KeyId].Next;}
  return KeyId;
}

template<class TKey, class TDat , class THashFunc >

void THash< TKey, TDat, THashFunc >::GetKeyV ( TVec< TKey > & KeyV ) const

Definition at line 436 of file hash.h.

                                                                 {
  KeyV.Gen(Len(), 0);
  int KeyId=FFirstKeyId();
  while (FNextKeyId(KeyId)){
    KeyV.Add(GetKey(KeyId));}
}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

::TSize THash< TKey, TDat, THashFunc >::GetMemUsed ( ) const [inline]

Definition at line 157 of file hash.h.

                           {
    // return PortV.GetMemUsed()+KeyDatV.GetMemUsed()+sizeof(bool)+2*sizeof(int);}
      int64 MemUsed = sizeof(bool)+2*sizeof(int);
      MemUsed += int64(PortV.Reserved()) * int64(sizeof(TInt));
      for (int KeyDatN = 0; KeyDatN < KeyDatV.Len(); KeyDatN++) {
          MemUsed += int64(2 * sizeof(TInt));
          MemUsed += int64(KeyDatV[KeyDatN].Key.GetMemUsed());
          MemUsed += int64(KeyDatV[KeyDatN].Dat.GetMemUsed());
      }
      return ::TSize(MemUsed);
  }

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

int THash< TKey, TDat, THashFunc >::GetMxKeyIds ( ) const [inline]

Definition at line 187 of file hash.h.

{return KeyDatV.Len();}

template<class TKey , class TDat , class THashFunc >

uint THash< TKey, TDat, THashFunc >::GetNextPrime ( const uint & Val ) const [private]

Definition at line 259 of file hash.h.

                                                                     {
  const uint* f=(const uint*)HashPrimeT, *m, *l=(const uint*)HashPrimeT + (int)HashPrimes;
  int h, len = (int)HashPrimes;
  while (len > 0) {
    h = len >> 1;  m = f + h;
    if (*m < Val) { f = m;  f++;  len = len - h - 1; }
    else len = h;
  }
  return f == l ? *(l - 1) : *f;
}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

int THash< TKey, TDat, THashFunc >::GetPorts ( ) const [inline]

Definition at line 185 of file hash.h.

{return PortV.Len();}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

int THash< TKey, TDat, THashFunc >::GetReservedKeyIds ( ) const [inline]

Definition at line 188 of file hash.h.

{return KeyDatV.Reserved();}

template<class TKey , class TDat , class THashFunc >

int THash< TKey, TDat, THashFunc >::GetRndKeyId ( TRnd & Rnd ) const

Get an index of a random element. If the hash table has many deleted keys, this may take a long time.

Definition at line 396 of file hash.h.

                                                              {
  IAssert(! Empty());
  int KeyId = abs(Rnd.GetUniDevInt(KeyDatV.Len()));
  while (KeyDatV[KeyId].HashCd == -1) { // if the index is empty, just try again
    KeyId = abs(Rnd.GetUniDevInt(KeyDatV.Len())); }
  return KeyId; 
}

template<class TKey , class TDat , class THashFunc >

int THash< TKey, TDat, THashFunc >::GetRndKeyId	(	TRnd &	Rnd,
		const double &	EmptyFrac
	)

Get an index of a random element. If the hash table has many deleted keys, defrag the hash table first (that's why the function is non-const).

Definition at line 407 of file hash.h.

                                                                                {
  IAssert(! Empty());
  if (FreeKeys/double(Len()+FreeKeys) > EmptyFrac) { Defrag(); }
  int KeyId = Rnd.GetUniDevInt(KeyDatV.Len());
  while (KeyDatV[KeyId].HashCd == -1) { // if the index is empty, just try again
    KeyId = Rnd.GetUniDevInt(KeyDatV.Len());
  }
  return KeyId;
}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

bool THash< TKey, TDat, THashFunc >::IsAutoSize ( ) const [inline]

Definition at line 186 of file hash.h.

{return AutoSizeP;}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

bool THash< TKey, TDat, THashFunc >::IsKey ( const TKey & Key ) const [inline]

Definition at line 214 of file hash.h.

{return GetKeyId(Key)!=-1;}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

bool THash< TKey, TDat, THashFunc >::IsKey	(	const TKey &	Key,
		int &	KeyId
	)		const `[inline]`

Definition at line 215 of file hash.h.

{ KeyId=GetKeyId(Key); return KeyId!=-1;}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

bool THash< TKey, TDat, THashFunc >::IsKeyGetDat	(	const TKey &	Key,
		TDat &	Dat
	)		const `[inline]`

Definition at line 226 of file hash.h.

                                                     {int KeyId;
    if (IsKey(Key, KeyId)){Dat=GetHashKeyDat(KeyId).Dat; return true;}
    else {return false;}}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

bool THash< TKey, TDat, THashFunc >::IsKeyId ( const int & KeyId ) const [inline]

Definition at line 216 of file hash.h.

                                       {
    return (0<=KeyId)&&(KeyId<KeyDatV.Len())&&(KeyDatV[KeyId].HashCd!=-1);}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

bool THash< TKey, TDat, THashFunc >::IsKeyIdEqKeyN ( ) const [inline]

Definition at line 189 of file hash.h.

{return FreeKeys==0;}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

int THash< TKey, TDat, THashFunc >::Len ( ) const [inline]

Definition at line 184 of file hash.h.

{return KeyDatV.Len()-FreeKeys;}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

void THash< TKey, TDat, THashFunc >::Load ( TSIn & SIn ) [inline]

Definition at line 136 of file hash.h.

                      {
    PortV.Load(SIn); KeyDatV.Load(SIn);
    AutoSizeP=TBool(SIn); FFreeKeyId=TInt(SIn); FreeKeys=TInt(SIn);
    SIn.LoadCs();}

template<class TKey , class TDat , class THashFunc >

void THash< TKey, TDat, THashFunc >::LoadXml	(	const PXmlTok &	XmlTok,
		const TStr &	Nm = `""`
	)

Definition at line 127 of file xmlser.h.

                                                                                {
  XLoadHd(Nm); TVec<THashKeyDat<TKey, TDat> > KeyDatV; XLoad(KeyDatV); XLoad(AutoSizeP);
        for (int KeyDatN=0; KeyDatN<KeyDatV.Len(); KeyDatN++){
                AddDat(KeyDatV[KeyDatN].Key, KeyDatV[KeyDatN].Dat);}}

template<class TKey, class TDat , class THashFunc >

void THash< TKey, TDat, THashFunc >::MarkDelKey ( const TKey & Key )

Definition at line 378 of file hash.h.

                                                            {
  // MarkDelKey is same as Delkey expect last two lines
  IAssert(!PortV.Empty());
  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
  int PrevKeyId=-1;
  int KeyId=PortV[PortN];
  while ((KeyId!=-1) &&
   !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
    PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}
  IAssertR(KeyId!=-1, Key.GetStr());
  if (PrevKeyId==-1){PortV[PortN]=KeyDatV[KeyId].Next;}
  else {KeyDatV[PrevKeyId].Next=KeyDatV[KeyId].Next;}
  KeyDatV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
  KeyDatV[KeyId].HashCd=TInt(-1);
}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

void THash< TKey, TDat, THashFunc >::MarkDelKeyId ( const int & KeyId ) [inline]

Definition at line 206 of file hash.h.

{MarkDelKey(GetKey(KeyId));}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

TDat& THash< TKey, TDat, THashFunc >::operator() ( const TKey & Key ) [inline]

Definition at line 156 of file hash.h.

{return AddDat(Key);}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

bool THash< TKey, TDat, THashFunc >::operator< ( const THash< TKey, TDat, THashFunc > & Hash ) const [inline]

Definition at line 153 of file hash.h.

{ Fail; return true; }

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

THash& THash< TKey, TDat, THashFunc >::operator= ( const THash< TKey, TDat, THashFunc > & Hash ) [inline]

Definition at line 147 of file hash.h.

                                     {
    if (this!=&Hash){
      PortV=Hash.PortV; KeyDatV=Hash.KeyDatV; AutoSizeP=Hash.AutoSizeP;
      FFreeKeyId=Hash.FFreeKeyId; FreeKeys=Hash.FreeKeys;}
    return *this;}

template<class TKey , class TDat , class THashFunc >

bool THash< TKey, TDat, THashFunc >::operator== ( const THash< TKey, TDat, THashFunc > & Hash ) const

Definition at line 302 of file hash.h.

                                                                     {
  if (Len() != Hash.Len()) { return false; }
  for (int i = FFirstKeyId(); FNextKeyId(i); ) {
    const TKey& Key = GetKey(i);
    if (! Hash.IsKey(Key)) { return false; }
    if (GetDat(Key) != Hash.GetDat(Key)) { return false; }
  }
  return true;
}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

const TDat& THash< TKey, TDat, THashFunc >::operator[] ( const int & KeyId ) const [inline]

Definition at line 154 of file hash.h.

{return GetHashKeyDat(KeyId).Dat;}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

TDat& THash< TKey, TDat, THashFunc >::operator[] ( const int & KeyId ) [inline]

Definition at line 155 of file hash.h.

{return GetHashKeyDat(KeyId).Dat;}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

void THash< TKey, TDat, THashFunc >::Pack ( ) [inline]

Definition at line 241 of file hash.h.

{KeyDatV.Pack();}

template<class TKey , class TDat , class THashFunc >

void THash< TKey, TDat, THashFunc >::Resize ( ) [private]

Definition at line 271 of file hash.h.

                                         {
  // resize & initialize port vector
  //if (PortV.Len()==0){PortV.Gen(17);}
  //else {PortV.Gen(2*PortV.Len()+1);}
  if (PortV.Len()==0){
    PortV.Gen(17);
  } else if (AutoSizeP&&(KeyDatV.Len()>2*PortV.Len())){
    PortV.Gen(GetNextPrime(PortV.Len()+1));
  } else {
    return;
  }
  PortV.PutAll(TInt(-1));
  // rehash keys
  for (int KeyId=0; KeyId<KeyDatV.Len(); KeyId++){
    THKeyDat& KeyDat=KeyDatV[KeyId];
    if (KeyDat.HashCd!=-1){
      const int PortN = abs(THashFunc::GetPrimHashCd(KeyDat.Key) % PortV.Len());
      KeyDat.Next=PortV[PortN];
      PortV[PortN]=KeyId;
    }
  }
}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

void THash< TKey, TDat, THashFunc >::Save ( TSOut & SOut ) const [inline]

Definition at line 140 of file hash.h.

                               {
    PortV.Save(SOut); KeyDatV.Save(SOut);
    AutoSizeP.Save(SOut); FFreeKeyId.Save(SOut); FreeKeys.Save(SOut);
    SOut.SaveCs();}

template<class TKey , class TDat , class THashFunc >

void THash< TKey, TDat, THashFunc >::SaveXml	(	TSOut &	SOut,
		const TStr &	Nm
	)

Definition at line 133 of file xmlser.h.

                                                                      {
  Defrag(); XSaveHd(Nm); XSave(KeyDatV); XSave(AutoSizeP);}

template<class TKey , class TDat , class THashFunc >

void THash< TKey, TDat, THashFunc >::Sort	(	const bool &	CmpKey,
		const bool &	Asc
	)

Definition at line 522 of file hash.h.

                                                                           {
  IAssertR(IsKeyIdEqKeyN(), "THash::Sort only works when table has no deleted keys.");
  TIntV TargV(Len()), MapV(Len()), StateV(Len());
  for (int i = 0; i < TargV.Len(); i++) {
    TargV[i] = i; MapV[i] = i; StateV[i] = i;
  }
  // sort KeyIds
  THashKeyDatCmp HashCmp(*this, CmpKey, Asc);
  TargV.SortCmp(HashCmp);
  // now sort the update vector
  THashKeyDat<TKey, TDat> Tmp;
  for (int i = 0; i < TargV.Len()-1; i++) {
    const int SrcPos = MapV[TargV[i]];
    const int Loc = i;
    // swap data
    Tmp = KeyDatV[SrcPos];
    KeyDatV[SrcPos] = KeyDatV[Loc];
    KeyDatV[Loc] = Tmp;
    // swap keys
    MapV[StateV[i]] = SrcPos;
    StateV.Swap(Loc, SrcPos);
  }
  for (int i = 0; i < TargV.Len(); i++) {
    MapV[TargV[i]] = i; }
  for (int p = 0; p < PortV.Len(); p++) {
    if (PortV[p] != -1) {
      PortV[p] = MapV[PortV[p]]; } }
  for (int i = 0; i < KeyDatV.Len(); i++) {
    if (KeyDatV[i].Next != -1) {
      KeyDatV[i].Next = MapV[KeyDatV[i].Next]; }
  }
}

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

void THash< TKey, TDat, THashFunc >::SortByDat ( const bool & Asc = true ) [inline]

Definition at line 244 of file hash.h.

{ Sort(false, Asc); }

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

void THash< TKey, TDat, THashFunc >::SortByKey ( const bool & Asc = true ) [inline]

Definition at line 243 of file hash.h.

{ Sort(true, Asc); }

template<class TKey , class TDat , class THashFunc >

void THash< TKey, TDat, THashFunc >::Swap ( THash< TKey, TDat, THashFunc > & Hash )

Definition at line 496 of file hash.h.

                                                   {
  if (this!=&Hash){
    PortV.Swap(Hash.PortV);
    KeyDatV.Swap(Hash.KeyDatV);
    ::Swap(AutoSizeP, Hash.AutoSizeP);
    ::Swap(FFreeKeyId, Hash.FFreeKeyId);
    ::Swap(FreeKeys, Hash.FreeKeys);
  }
}

Member Data Documentation

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

TBool THash< TKey, TDat, THashFunc >::AutoSizeP [private]

Definition at line 98 of file hash.h.

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

TInt THash< TKey, TDat, THashFunc >::FFreeKeyId [private]

Definition at line 99 of file hash.h.

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

TInt THash< TKey, TDat, THashFunc >::FreeKeys [private]

Definition at line 99 of file hash.h.

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

const unsigned int THash< TKey, TDat, THashFunc >::HashPrimeT [static]

Initial value:

{
  3ul, 5ul, 11ul, 23ul,
  53ul,         97ul,         193ul,       389ul,       769ul,
  1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
  49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
  1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
  50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
  1610612741ul, 3221225473ul, 4294967291ul
}

Definition at line 90 of file hash.h.

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

TVec<THKeyDat> THash< TKey, TDat, THashFunc >::KeyDatV [private]

Definition at line 97 of file hash.h.

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>

TIntV THash< TKey, TDat, THashFunc >::PortV [private]

Definition at line 96 of file hash.h.

The documentation for this class was generated from the following files:

glib-core/hash.h
glib-core/xmlser.h

Classes

Public Types

Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Private Attributes

Detailed Description

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>> class THash< TKey, TDat, THashFunc >

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
class THash< TKey, TDat, THashFunc >