SNAP Library 3.0, User Reference  2016-07-20 17:56:49
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Classes | Public Types | Public Member Functions | Static Public Attributes | Private Types | Private Member Functions | Private Attributes | List of all members
THash< TKey, TDat, THashFunc > Class Template Reference

#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
 The [] operator takes KeyId, use GetDat() if you need value access via the key. More...
 
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)
 
bool 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. More...
 
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). More...
 
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)
 
TDat GetDatWithDefault (const TKey &Key, TDat DefaultValue)
 
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 88 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 95 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 93 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 96 of file hash.h.

Member Enumeration Documentation

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
anonymous enum
Enumerator
HashPrimes 

Definition at line 90 of file hash.h.

90 {HashPrimes=32};

Constructor & Destructor Documentation

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
THash< TKey, TDat, THashFunc >::THash ( )
inline

Definition at line 126 of file hash.h.

126  :
127  PortV(), KeyDatV(),
128  AutoSizeP(true), FFreeKeyId(-1), FreeKeys(0){}
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:99
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:100
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
THash< TKey, TDat, THashFunc >::THash ( const THash< TKey, TDat, THashFunc > &  Hash)
inline

Definition at line 129 of file hash.h.

129  :
130  PortV(Hash.PortV), KeyDatV(Hash.KeyDatV), AutoSizeP(Hash.AutoSizeP),
131  FFreeKeyId(Hash.FFreeKeyId), FreeKeys(Hash.FreeKeys){}
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:99
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:100
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey , class TDat , class THashFunc >
THash< TKey, TDat, THashFunc >::THash ( const int &  ExpectVals,
const bool &  _AutoSizeP = false 
)
explicit

Definition at line 301 of file hash.h.

301  :
302  PortV(GetNextPrime(ExpectVals/2)), KeyDatV(ExpectVals, 0),
303  AutoSizeP(_AutoSizeP), FFreeKeyId(-1), FreeKeys(0){
304  PortV.PutAll(TInt(-1));
305 }
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:99
TVec::PutAll
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1166
TInt
Definition: dt.h:1044
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:100
THash::GetNextPrime
uint GetNextPrime(const uint &Val) const
Definition: hash.h:265
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
THash< TKey, TDat, THashFunc >::THash ( TSIn &  SIn)
inlineexplicit

Definition at line 133 of file hash.h.

133  :
134  PortV(SIn), KeyDatV(SIn),
135  AutoSizeP(SIn), FFreeKeyId(SIn), FreeKeys(SIn){
136  SIn.LoadCs();}
TSIn::LoadCs
void LoadCs()
Definition: fl.cpp:28
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:99
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:100
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98

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 196 of file hash.h.

196 {return KeyDatV[AddKey(Key)].Dat;}
THash::AddKey
int AddKey(const TKey &Key)
Definition: hash.h:331
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
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 197 of file hash.h.

197  {
198  return KeyDatV[AddKey(Key)].Dat=Dat;}
THash::AddKey
int AddKey(const TKey &Key)
Definition: hash.h:331
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
TDat& THash< TKey, TDat, THashFunc >::AddDatId ( const TKey &  Key)
inline

Definition at line 194 of file hash.h.

194  {
195  int KeyId=AddKey(Key); return KeyDatV[KeyId].Dat=KeyId;}
THash::AddKey
int AddKey(const TKey &Key)
Definition: hash.h:331
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat , class THashFunc >
int THash< TKey, TDat, THashFunc >::AddKey ( const TKey &  Key)

Definition at line 331 of file hash.h.

331  {
332  if ((KeyDatV.Len()>2*PortV.Len())||PortV.Empty()){Resize();}
333  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
334  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
335  int PrevKeyId=-1;
336  int KeyId=PortV[PortN];
337  while ((KeyId!=-1) &&
338  !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
339  PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}
340 
341  if (KeyId==-1){
342  if (FFreeKeyId==-1){
343  KeyId=KeyDatV.Add(THKeyDat(-1, HashCd, Key));
344  } else {
345  KeyId=FFreeKeyId; FFreeKeyId=KeyDatV[FFreeKeyId].Next; FreeKeys--;
346  //KeyDatV[KeyId]=TKeyDat(-1, HashCd, Key); // slow version
347  KeyDatV[KeyId].Next=-1;
348  KeyDatV[KeyId].HashCd=HashCd;
349  KeyDatV[KeyId].Key=Key;
350  //KeyDatV[KeyId].Dat=TDat(); // already empty
351  }
352  if (PrevKeyId==-1){
353  PortV[PortN]=KeyId;
354  } else {
355  KeyDatV[PrevKeyId].Next=KeyId;
356  }
357  }
358  return KeyId;
359 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:542
THash::THKeyDat
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:95
THash::Resize
void Resize()
Definition: hash.h:277
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:100
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
TIter THash< TKey, TDat, THashFunc >::BegI ( ) const
inline

Definition at line 171 of file hash.h.

171  {
172  if (Len() == 0){return TIter(KeyDatV.EndI(), KeyDatV.EndI());}
173  if (IsKeyIdEqKeyN()) { return TIter(KeyDatV.BegI(), KeyDatV.EndI());}
174  int FKeyId=-1; FNextKeyId(FKeyId);
175  return TIter(KeyDatV.BegI()+FKeyId, KeyDatV.EndI()); }
TVec::EndI
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:567
THash::IsKeyIdEqKeyN
bool IsKeyIdEqKeyN() const
Definition: hash.h:191
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::TIter
THashKeyDatI< TKey, TDat > TIter
Definition: hash.h:93
TVec::BegI
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:565
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
THash::Len
int Len() const
Definition: hash.h:186
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 319 of file hash.h.

319  {
320  if (DoDel){
321  PortV.Clr(); KeyDatV.Clr();
322  } else {
323  PortV.PutAll(TInt(-1));
324  KeyDatV.Clr(DoDel, NoDelLim);
325  if (ResetDat){KeyDatV.PutAll(THKeyDat());}
326  }
327  FFreeKeyId=TInt(-1); FreeKeys=TInt(0);
328 }
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:971
THash::THKeyDat
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:95
TVec::PutAll
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1166
TInt
Definition: dt.h:1044
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:100
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey , class TDat , class THashFunc >
void THash< TKey, TDat, THashFunc >::Defrag ( )

Definition at line 513 of file hash.h.

513  {
514  if (!IsKeyIdEqKeyN()){
515  THash<TKey, TDat, THashFunc> Hash(PortV.Len());
516  int KeyId=FFirstKeyId(); TKey Key; TDat Dat;
517  while (FNextKeyId(KeyId)){
518  GetKeyDat(KeyId, Key, Dat);
519  Hash.AddDat(Key, Dat);
520  }
521  Pack();
522  operator=(Hash);
523  IAssert(IsKeyIdEqKeyN());
524  }
525 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
THash::IsKeyIdEqKeyN
bool IsKeyIdEqKeyN() const
Definition: hash.h:191
THash::operator=
THash & operator=(const THash &Hash)
Definition: hash.h:148
THash::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:229
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
THash
Definition: hash.h:88
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::Pack
void Pack()
Definition: hash.h:247
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
bool THash< TKey, TDat, THashFunc >::DelIfKey ( const TKey &  Key)
inline

Definition at line 201 of file hash.h.

201  {
202  int KeyId; if (IsKey(Key, KeyId)){DelKeyId(KeyId); return true;} return false;}
THash::DelKeyId
void DelKeyId(const int &KeyId)
Definition: hash.h:203
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:216
template<class TKey, class TDat , class THashFunc >
void THash< TKey, TDat, THashFunc >::DelKey ( const TKey &  Key)

Definition at line 362 of file hash.h.

362  {
363  IAssert(!PortV.Empty());
364  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
365  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
366  int PrevKeyId=-1;
367  int KeyId=PortV[PortN];
368 
369  while ((KeyId!=-1) &&
370  !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
371  PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}
372 
373  //IAssertR(KeyId!=-1, Key.GetStr()); //J: some classes do not provide GetStr()?
374  IAssert(KeyId!=-1); //J: some classes do not provide GetStr()?
375  if (PrevKeyId==-1){PortV[PortN]=KeyDatV[KeyId].Next;}
376  else {KeyDatV[PrevKeyId].Next=KeyDatV[KeyId].Next;}
377  KeyDatV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
378  KeyDatV[KeyId].HashCd=TInt(-1);
379  KeyDatV[KeyId].Key=TKey();
380  KeyDatV[KeyId].Dat=TDat();
381 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:542
TInt
Definition: dt.h:1044
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:100
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
void THash< TKey, TDat, THashFunc >::DelKeyId ( const int &  KeyId)
inline

Definition at line 203 of file hash.h.

203 {DelKey(GetKey(KeyId));}
THash::DelKey
void DelKey(const TKey &Key)
Definition: hash.h:362
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
void THash< TKey, TDat, THashFunc >::DelKeyIdV ( const TIntV &  KeyIdV)
inline

Definition at line 204 of file hash.h.

204  {
205  for (int KeyIdN=0; KeyIdN<KeyIdV.Len(); KeyIdN++){DelKeyId(KeyIdV[KeyIdN]);}}
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THash::DelKeyId
void DelKeyId(const int &KeyId)
Definition: hash.h:203
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
bool THash< TKey, TDat, THashFunc >::Empty ( ) const
inline

Definition at line 185 of file hash.h.

185 {return Len()==0;}
THash::Len
int Len() const
Definition: hash.h:186
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
TIter THash< TKey, TDat, THashFunc >::EndI ( ) const
inline

Definition at line 176 of file hash.h.

176 {return TIter(KeyDatV.EndI(), KeyDatV.EndI());}
TVec::EndI
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:567
THash::TIter
THashKeyDatI< TKey, TDat > TIter
Definition: hash.h:93
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
int THash< TKey, TDat, THashFunc >::FFirstKeyId ( ) const
inline

Definition at line 236 of file hash.h.

236 {return 0-1;}
template<class TKey , class TDat , class THashFunc >
bool THash< TKey, TDat, THashFunc >::FNextKeyId ( int &  KeyId) const

Definition at line 436 of file hash.h.

436  {
437  do {KeyId++;} while ((KeyId<KeyDatV.Len())&&(KeyDatV[KeyId].HashCd==-1));
438  return KeyId<KeyDatV.Len();
439 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
void THash< TKey, TDat, THashFunc >::Gen ( const int &  ExpectVals)
inline

Definition at line 180 of file hash.h.

180  {
181  PortV.Gen(GetNextPrime(ExpectVals/2)); KeyDatV.Gen(ExpectVals, 0);
182  FFreeKeyId=-1; FreeKeys=0; PortV.PutAll(TInt(-1));}
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
TVec::PutAll
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1166
TInt
Definition: dt.h:1044
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:100
THash::GetNextPrime
uint GetNextPrime(const uint &Val) const
Definition: hash.h:265
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
const TDat& THash< TKey, TDat, THashFunc >::GetDat ( const TKey &  Key) const
inline

Definition at line 220 of file hash.h.

220 {return KeyDatV[GetKeyId(Key)].Dat;}
THash::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: hash.h:424
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
TDat& THash< TKey, TDat, THashFunc >::GetDat ( const TKey &  Key)
inline

Definition at line 221 of file hash.h.

221 {return KeyDatV[GetKeyId(Key)].Dat;}
THash::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: hash.h:424
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat, class THashFunc >
void THash< TKey, TDat, THashFunc >::GetDatKeyKdV ( TVec< TKeyDat< TDat, TKey > > &  DatKeyKdV) const

Definition at line 491 of file hash.h.

491  {
492  DatKeyKdV.Gen(Len(), 0);
493  TKey Key; TDat Dat;
494  int KeyId=FFirstKeyId();
495  while (FNextKeyId(KeyId)){
496  GetKeyDat(KeyId, Key, Dat);
497  DatKeyKdV.Add(TKeyDat<TDat, TKey>(Dat, Key));
498  }
499 }
TKeyDat
Definition: ds.h:345
THash::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:229
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
THash::Len
int Len() const
Definition: hash.h:186
template<class TKey, class TDat, class THashFunc >
void THash< TKey, TDat, THashFunc >::GetDatKeyPrV ( TVec< TPair< TDat, TKey > > &  DatKeyPrV) const

Definition at line 469 of file hash.h.

469  {
470  DatKeyPrV.Gen(Len(), 0);
471  TKey Key; TDat Dat;
472  int KeyId=FFirstKeyId();
473  while (FNextKeyId(KeyId)){
474  GetKeyDat(KeyId, Key, Dat);
475  DatKeyPrV.Add(TPair<TDat, TKey>(Dat, Key));
476  }
477 }
THash::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:229
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
TPair
Definition: ds.h:32
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
THash::Len
int Len() const
Definition: hash.h:186
template<class TKey , class TDat, class THashFunc >
void THash< TKey, TDat, THashFunc >::GetDatV ( TVec< TDat > &  DatV) const

Definition at line 450 of file hash.h.

450  {
451  DatV.Gen(Len(), 0);
452  int KeyId=FFirstKeyId();
453  while (FNextKeyId(KeyId)){
454  DatV.Add(GetHashKeyDat(KeyId).Dat);}
455 }
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
THash::GetHashKeyDat
THKeyDat & GetHashKeyDat(const int &KeyId)
Definition: hash.h:117
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
THash::Len
int Len() const
Definition: hash.h:186
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
TDat THash< TKey, TDat, THashFunc >::GetDatWithDefault ( const TKey &  Key,
TDat  DefaultValue 
)
inline

Definition at line 222 of file hash.h.

222  {
223  int KeyId = GetKeyId(Key);
224  return KeyId >= 0 ? KeyDatV[KeyId].Dat : DefaultValue;
225  }
THash::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: hash.h:424
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
THKeyDat& THash< TKey, TDat, THashFunc >::GetHashKeyDat ( const int &  KeyId)
inlineprivate

Definition at line 117 of file hash.h.

117  {
118  THKeyDat& KeyDat=KeyDatV[KeyId];
119  Assert(KeyDat.HashCd!=-1); return KeyDat;}
THash::THKeyDat
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:95
Assert
#define Assert(Cond)
Definition: bd.h:251
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
const THKeyDat& THash< TKey, TDat, THashFunc >::GetHashKeyDat ( const int &  KeyId) const
inlineprivate

Definition at line 120 of file hash.h.

120  {
121  const THKeyDat& KeyDat=KeyDatV[KeyId];
122  Assert(KeyDat.HashCd!=-1); return KeyDat;}
THash::THKeyDat
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:95
Assert
#define Assert(Cond)
Definition: bd.h:251
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
TIter THash< TKey, TDat, THashFunc >::GetI ( const TKey &  Key) const
inline

Definition at line 178 of file hash.h.

178 {return TIter(&KeyDatV[GetKeyId(Key)], KeyDatV.EndI());}
TVec::EndI
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:567
THash::TIter
THashKeyDatI< TKey, TDat > TIter
Definition: hash.h:93
THash::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: hash.h:424
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
const TKey& THash< TKey, TDat, THashFunc >::GetKey ( const int &  KeyId) const
inline

Definition at line 210 of file hash.h.

210 { return GetHashKeyDat(KeyId).Key;}
THash::GetHashKeyDat
THKeyDat & GetHashKeyDat(const int &KeyId)
Definition: hash.h:117
THashKeyDat::Key
TKey Key
Definition: hash.h:11
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 229 of file hash.h.

229  {
230  const THKeyDat& KeyDat=GetHashKeyDat(KeyId);
231  Key=KeyDat.Key; Dat=KeyDat.Dat;}
THash::THKeyDat
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:95
THash::GetHashKeyDat
THKeyDat & GetHashKeyDat(const int &KeyId)
Definition: hash.h:117
template<class TKey, class TDat, class THashFunc >
void THash< TKey, TDat, THashFunc >::GetKeyDatKdV ( TVec< TKeyDat< TKey, TDat > > &  KeyDatKdV) const

Definition at line 480 of file hash.h.

480  {
481  KeyDatKdV.Gen(Len(), 0);
482  TKey Key; TDat Dat;
483  int KeyId=FFirstKeyId();
484  while (FNextKeyId(KeyId)){
485  GetKeyDat(KeyId, Key, Dat);
486  KeyDatKdV.Add(TKeyDat<TKey, TDat>(Key, Dat));
487  }
488 }
TKeyDat
Definition: ds.h:345
THash::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:229
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
THash::Len
int Len() const
Definition: hash.h:186
template<class TKey, class TDat, class THashFunc >
void THash< TKey, TDat, THashFunc >::GetKeyDatPrV ( TVec< TPair< TKey, TDat > > &  KeyDatPrV) const

Definition at line 458 of file hash.h.

458  {
459  KeyDatPrV.Gen(Len(), 0);
460  TKey Key; TDat Dat;
461  int KeyId=FFirstKeyId();
462  while (FNextKeyId(KeyId)){
463  GetKeyDat(KeyId, Key, Dat);
464  KeyDatPrV.Add(TPair<TKey, TDat>(Key, Dat));
465  }
466 }
THash::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:229
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
TPair
Definition: ds.h:32
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
THash::Len
int Len() const
Definition: hash.h:186
template<class TKey, class TDat , class THashFunc >
int THash< TKey, TDat, THashFunc >::GetKeyId ( const TKey &  Key) const

Definition at line 424 of file hash.h.

424  {
425  if (PortV.Empty()){return -1;}
426  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
427  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
428  int KeyId=PortV[PortN];
429  while ((KeyId!=-1) &&
430  !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
431  KeyId=KeyDatV[KeyId].Next;}
432  return KeyId;
433 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:542
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat , class THashFunc >
void THash< TKey, TDat, THashFunc >::GetKeyV ( TVec< TKey > &  KeyV) const

Definition at line 442 of file hash.h.

442  {
443  KeyV.Gen(Len(), 0);
444  int KeyId=FFirstKeyId();
445  while (FNextKeyId(KeyId)){
446  KeyV.Add(GetKey(KeyId));}
447 }
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
THash::Len
int Len() const
Definition: hash.h:186
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
::TSize THash< TKey, TDat, THashFunc >::GetMemUsed ( ) const
inline

Definition at line 159 of file hash.h.

159  {
160  // return PortV.GetMemUsed()+KeyDatV.GetMemUsed()+sizeof(bool)+2*sizeof(int);}
161  int64 MemUsed = sizeof(bool)+2*sizeof(int);
162  MemUsed += int64(PortV.Reserved()) * int64(sizeof(TInt));
163  for (int KeyDatN = 0; KeyDatN < KeyDatV.Len(); KeyDatN++) {
164  MemUsed += int64(2 * sizeof(TInt));
165  MemUsed += int64(KeyDatV[KeyDatN].Key.GetMemUsed());
166  MemUsed += int64(KeyDatV[KeyDatN].Dat.GetMemUsed());
167  }
168  return ::TSize(MemUsed);
169  }
TVec::Reserved
TSizeTy Reserved() const
Returns the size of allocated storage capacity.
Definition: ds.h:549
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
TVec::GetMemUsed
TSizeTy GetMemUsed() const
Returns the memory footprint (the number of bytes) of the vector.
Definition: ds.h:483
TSize
size_t TSize
Definition: bd.h:58
TInt
Definition: dt.h:1044
int64
long long int64
Definition: bd.h:27
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
int THash< TKey, TDat, THashFunc >::GetMxKeyIds ( ) const
inline

Definition at line 189 of file hash.h.

189 {return KeyDatV.Len();}
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey , class TDat , class THashFunc >
uint THash< TKey, TDat, THashFunc >::GetNextPrime ( const uint &  Val) const
private

Definition at line 265 of file hash.h.

265  {
266  const uint* f=(const uint*)HashPrimeT, *m, *l=(const uint*)HashPrimeT + (int)HashPrimes;
267  int h, len = (int)HashPrimes;
268  while (len > 0) {
269  h = len >> 1; m = f + h;
270  if (*m < Val) { f = m; f++; len = len - h - 1; }
271  else len = h;
272  }
273  return f == l ? *(l - 1) : *f;
274 }
uint
unsigned int uint
Definition: bd.h:11
THash::HashPrimeT
static const unsigned int HashPrimeT[HashPrimes]
Definition: hash.h:91
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
int THash< TKey, TDat, THashFunc >::GetPorts ( ) const
inline

Definition at line 187 of file hash.h.

187 {return PortV.Len();}
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THash::PortV
TIntV PortV
Definition: hash.h:97
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
int THash< TKey, TDat, THashFunc >::GetReservedKeyIds ( ) const
inline

Definition at line 190 of file hash.h.

190 {return KeyDatV.Reserved();}
TVec::Reserved
TSizeTy Reserved() const
Returns the size of allocated storage capacity.
Definition: ds.h:549
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
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 402 of file hash.h.

402  {
403  IAssert(! Empty());
404  int KeyId = abs(Rnd.GetUniDevInt(KeyDatV.Len()));
405  while (KeyDatV[KeyId].HashCd == -1) { // if the index is empty, just try again
406  KeyId = abs(Rnd.GetUniDevInt(KeyDatV.Len())); }
407  return KeyId;
408 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THash::Empty
bool Empty() const
Definition: hash.h:185
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
TRnd::GetUniDevInt
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
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 413 of file hash.h.

413  {
414  IAssert(! Empty());
415  if (FreeKeys/double(Len()+FreeKeys) > EmptyFrac) { Defrag(); }
416  int KeyId = Rnd.GetUniDevInt(KeyDatV.Len());
417  while (KeyDatV[KeyId].HashCd == -1) { // if the index is empty, just try again
418  KeyId = Rnd.GetUniDevInt(KeyDatV.Len());
419  }
420  return KeyId;
421 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THash::Empty
bool Empty() const
Definition: hash.h:185
THash::Defrag
void Defrag()
Definition: hash.h:513
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
TRnd::GetUniDevInt
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
THash::Len
int Len() const
Definition: hash.h:186
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
bool THash< TKey, TDat, THashFunc >::IsAutoSize ( ) const
inline

Definition at line 188 of file hash.h.

188 {return AutoSizeP;}
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:99
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
bool THash< TKey, TDat, THashFunc >::IsKey ( const TKey &  Key) const
inline

Definition at line 216 of file hash.h.

216 {return GetKeyId(Key)!=-1;}
THash::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: hash.h:424
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 217 of file hash.h.

217 { KeyId=GetKeyId(Key); return KeyId!=-1;}
THash::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: hash.h:424
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 232 of file hash.h.

232  {int KeyId;
233  if (IsKey(Key, KeyId)){Dat=GetHashKeyDat(KeyId).Dat; return true;}
234  else {return false;}}
THashKeyDat::Dat
TDat Dat
Definition: hash.h:12
THash::GetHashKeyDat
THKeyDat & GetHashKeyDat(const int &KeyId)
Definition: hash.h:117
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:216
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
bool THash< TKey, TDat, THashFunc >::IsKeyId ( const int &  KeyId) const
inline

Definition at line 218 of file hash.h.

218  {
219  return (0<=KeyId)&&(KeyId<KeyDatV.Len())&&(KeyDatV[KeyId].HashCd!=-1);}
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
bool THash< TKey, TDat, THashFunc >::IsKeyIdEqKeyN ( ) const
inline

Definition at line 191 of file hash.h.

191 {return FreeKeys==0;}
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
int THash< TKey, TDat, THashFunc >::Len ( ) const
inline

Definition at line 186 of file hash.h.

186 {return KeyDatV.Len()-FreeKeys;}
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
void THash< TKey, TDat, THashFunc >::Load ( TSIn &  SIn)
inline

Definition at line 137 of file hash.h.

137  {
138  PortV.Load(SIn); KeyDatV.Load(SIn);
139  AutoSizeP=TBool(SIn); FFreeKeyId=TInt(SIn); FreeKeys=TInt(SIn);
140  SIn.LoadCs();}
TVec::Load
void Load(TSIn &SIn)
Definition: ds.h:895
TSIn::LoadCs
void LoadCs()
Definition: fl.cpp:28
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:99
TInt
Definition: dt.h:1044
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:100
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
TBool
Definition: dt.h:881
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.

127  {
128  XLoadHd(Nm); TVec<THashKeyDat<TKey, TDat> > KeyDatV; XLoad(KeyDatV); XLoad(AutoSizeP);
129  for (int KeyDatN=0; KeyDatN<KeyDatV.Len(); KeyDatN++){
130  AddDat(KeyDatV[KeyDatN].Key, KeyDatV[KeyDatN].Dat);}}
XLoadHd
#define XLoadHd(Nm)
Definition: bd.h:312
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
XLoad
#define XLoad(Nm)
Definition: bd.h:315
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:99
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
TVec
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:429
template<class TKey, class TDat , class THashFunc >
void THash< TKey, TDat, THashFunc >::MarkDelKey ( const TKey &  Key)

Definition at line 384 of file hash.h.

384  {
385  // MarkDelKey is same as Delkey except last two lines
386  IAssert(!PortV.Empty());
387  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
388  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
389  int PrevKeyId=-1;
390  int KeyId=PortV[PortN];
391  while ((KeyId!=-1) &&
392  !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
393  PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}
394  IAssertR(KeyId!=-1, Key.GetStr());
395  if (PrevKeyId==-1){PortV[PortN]=KeyDatV[KeyId].Next;}
396  else {KeyDatV[PrevKeyId].Next=KeyDatV[KeyId].Next;}
397  KeyDatV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
398  KeyDatV[KeyId].HashCd=TInt(-1);
399 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:542
TInt
Definition: dt.h:1044
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:100
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
void THash< TKey, TDat, THashFunc >::MarkDelKeyId ( const int &  KeyId)
inline

Definition at line 208 of file hash.h.

208 {MarkDelKey(GetKey(KeyId));}
THash::MarkDelKey
void MarkDelKey(const TKey &Key)
Definition: hash.h:384
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
TDat& THash< TKey, TDat, THashFunc >::operator() ( const TKey &  Key)
inline

Definition at line 158 of file hash.h.

158 {return AddDat(Key);}
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:196
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 154 of file hash.h.

154 { Fail; return true; }
Fail
#define Fail
Definition: bd.h:238
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 148 of file hash.h.

148  {
149  if (this!=&Hash){
150  PortV=Hash.PortV; KeyDatV=Hash.KeyDatV; AutoSizeP=Hash.AutoSizeP;
151  FFreeKeyId=Hash.FFreeKeyId; FreeKeys=Hash.FreeKeys;}
152  return *this;}
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:99
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:100
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey , class TDat , class THashFunc >
bool THash< TKey, TDat, THashFunc >::operator== ( const THash< TKey, TDat, THashFunc > &  Hash) const

Definition at line 308 of file hash.h.

308  {
309  if (Len() != Hash.Len()) { return false; }
310  for (int i = FFirstKeyId(); FNextKeyId(i); ) {
311  const TKey& Key = GetKey(i);
312  if (! Hash.IsKey(Key)) { return false; }
313  if (GetDat(Key) != Hash.GetDat(Key)) { return false; }
314  }
315  return true;
316 }
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:436
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:236
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:216
THash::Len
int Len() const
Definition: hash.h:186
THash::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:210
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
const TDat& THash< TKey, TDat, THashFunc >::operator[] ( const int &  KeyId) const
inline

The [] operator takes KeyId, use GetDat() if you need value access via the key.

Definition at line 156 of file hash.h.

156 {return GetHashKeyDat(KeyId).Dat;}
THashKeyDat::Dat
TDat Dat
Definition: hash.h:12
THash::GetHashKeyDat
THKeyDat & GetHashKeyDat(const int &KeyId)
Definition: hash.h:117
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
TDat& THash< TKey, TDat, THashFunc >::operator[] ( const int &  KeyId)
inline

Definition at line 157 of file hash.h.

157 {return GetHashKeyDat(KeyId).Dat;}
THashKeyDat::Dat
TDat Dat
Definition: hash.h:12
THash::GetHashKeyDat
THKeyDat & GetHashKeyDat(const int &KeyId)
Definition: hash.h:117
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
void THash< TKey, TDat, THashFunc >::Pack ( )
inline

Definition at line 247 of file hash.h.

247 {KeyDatV.Pack();}
TVec::Pack
void Pack()
Reduces vector capacity (frees memory) to match its size.
Definition: ds.h:1005
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey , class TDat , class THashFunc >
void THash< TKey, TDat, THashFunc >::Resize ( )
private

Definition at line 277 of file hash.h.

277  {
278  // resize & initialize port vector
279  //if (PortV.Len()==0){PortV.Gen(17);}
280  //else {PortV.Gen(2*PortV.Len()+1);}
281  if (PortV.Len()==0){
282  PortV.Gen(17);
283  } else if (AutoSizeP&&(KeyDatV.Len()>2*PortV.Len())){
284  PortV.Gen(GetNextPrime(PortV.Len()+1));
285  } else {
286  return;
287  }
288  PortV.PutAll(TInt(-1));
289  // rehash keys
290  for (int KeyId=0; KeyId<KeyDatV.Len(); KeyId++){
291  THKeyDat& KeyDat=KeyDatV[KeyId];
292  if (KeyDat.HashCd!=-1){
293  const int PortN = abs(THashFunc::GetPrimHashCd(KeyDat.Key) % PortV.Len());
294  KeyDat.Next=PortV[PortN];
295  PortV[PortN]=KeyId;
296  }
297  }
298 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:99
THash::THKeyDat
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:95
TVec::PutAll
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1166
TInt
Definition: dt.h:1044
THash::GetNextPrime
uint GetNextPrime(const uint &Val) const
Definition: hash.h:265
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
void THash< TKey, TDat, THashFunc >::Save ( TSOut &  SOut) const
inline

Definition at line 141 of file hash.h.

141  {
142  PortV.Save(SOut); KeyDatV.Save(SOut);
143  AutoSizeP.Save(SOut); FFreeKeyId.Save(SOut); FreeKeys.Save(SOut);
144  SOut.SaveCs();}
TInt::Save
void Save(TSOut &SOut) const
Definition: dt.h:1060
TBool::Save
void Save(TSOut &SOut) const
Definition: dt.h:902
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
TVec::Save
void Save(TSOut &SOut) const
Definition: ds.h:903
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:99
TSOut::SaveCs
void SaveCs()
Definition: fl.h:171
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:100
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
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.

133  {
134  Defrag(); XSaveHd(Nm); XSave(KeyDatV); XSave(AutoSizeP);}
XSaveHd
#define XSaveHd(Nm)
Definition: bd.h:318
XSave
#define XSave(Nm)
Definition: bd.h:333
THash::Defrag
void Defrag()
Definition: hash.h:513
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:99
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
template<class TKey , class TDat , class THashFunc >
void THash< TKey, TDat, THashFunc >::Sort ( const bool &  CmpKey,
const bool &  Asc 
)

Definition at line 528 of file hash.h.

528  {
529  IAssertR(IsKeyIdEqKeyN(), "THash::Sort only works when table has no deleted keys.");
530  TIntV TargV(Len()), MapV(Len()), StateV(Len());
531  for (int i = 0; i < TargV.Len(); i++) {
532  TargV[i] = i; MapV[i] = i; StateV[i] = i;
533  }
534  // sort KeyIds
535  THashKeyDatCmp HashCmp(*this, CmpKey, Asc);
536  TargV.SortCmp(HashCmp);
537  // now sort the update vector
538  THashKeyDat<TKey, TDat> Tmp;
539  for (int i = 0; i < TargV.Len()-1; i++) {
540  const int SrcPos = MapV[TargV[i]];
541  const int Loc = i;
542  // swap data
543  Tmp = KeyDatV[SrcPos];
544  KeyDatV[SrcPos] = KeyDatV[Loc];
545  KeyDatV[Loc] = Tmp;
546  // swap keys
547  MapV[StateV[i]] = SrcPos;
548  StateV.Swap(Loc, SrcPos);
549  }
550  for (int i = 0; i < TargV.Len(); i++) {
551  MapV[TargV[i]] = i; }
552  for (int p = 0; p < PortV.Len(); p++) {
553  if (PortV[p] != -1) {
554  PortV[p] = MapV[PortV[p]]; } }
555  for (int i = 0; i < KeyDatV.Len(); i++) {
556  if (KeyDatV[i].Next != -1) {
557  KeyDatV[i].Next = MapV[KeyDatV[i].Next]; }
558  }
559 }
THash::IsKeyIdEqKeyN
bool IsKeyIdEqKeyN() const
Definition: hash.h:191
IAssertR
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:547
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98
THash::Len
int Len() const
Definition: hash.h:186
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
void THash< TKey, TDat, THashFunc >::SortByDat ( const bool &  Asc = true)
inline

Definition at line 250 of file hash.h.

250 { Sort(false, Asc); }
THash::Sort
void Sort(const bool &CmpKey, const bool &Asc)
Definition: hash.h:528
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
void THash< TKey, TDat, THashFunc >::SortByKey ( const bool &  Asc = true)
inline

Definition at line 249 of file hash.h.

249 { Sort(true, Asc); }
THash::Sort
void Sort(const bool &CmpKey, const bool &Asc)
Definition: hash.h:528
template<class TKey , class TDat , class THashFunc >
void THash< TKey, TDat, THashFunc >::Swap ( THash< TKey, TDat, THashFunc > &  Hash)

Definition at line 502 of file hash.h.

502  {
503  if (this!=&Hash){
504  PortV.Swap(Hash.PortV);
505  KeyDatV.Swap(Hash.KeyDatV);
506  ::Swap(AutoSizeP, Hash.AutoSizeP);
507  ::Swap(FFreeKeyId, Hash.FFreeKeyId);
508  ::Swap(FreeKeys, Hash.FreeKeys);
509  }
510 }
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
TVec::Swap
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1047
THash::Swap
void Swap(THash &Hash)
Definition: hash.h:502
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:99
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:100
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:98

Member Data Documentation

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
TBool THash< TKey, TDat, THashFunc >::AutoSizeP
private

Definition at line 99 of file hash.h.

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
TInt THash< TKey, TDat, THashFunc >::FFreeKeyId
private

Definition at line 100 of file hash.h.

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
TInt THash< TKey, TDat, THashFunc >::FreeKeys
private

Definition at line 100 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 91 of file hash.h.

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
TVec<THKeyDat> THash< TKey, TDat, THashFunc >::KeyDatV
private

Definition at line 98 of file hash.h.

template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
TIntV THash< TKey, TDat, THashFunc >::PortV
private

Definition at line 97 of file hash.h.

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