SNAP Library 2.4, User Reference  2015-05-11 19:40:56
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)
 
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 297 of file hash.h.

297  :
298  PortV(GetNextPrime(ExpectVals/2)), KeyDatV(ExpectVals, 0),
299  AutoSizeP(_AutoSizeP), FFreeKeyId(-1), FreeKeys(0){
300  PortV.PutAll(TInt(-1));
301 }
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:1130
TInt
Definition: dt.h:1042
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:100
THash::GetNextPrime
uint GetNextPrime(const uint &Val) const
Definition: hash.h:261
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:327
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:327
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:327
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 327 of file hash.h.

327  {
328  if ((KeyDatV.Len()>2*PortV.Len())||PortV.Empty()){Resize();}
329  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
330  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
331  int PrevKeyId=-1;
332  int KeyId=PortV[PortN];
333  while ((KeyId!=-1) &&
334  !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
335  PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}
336 
337  if (KeyId==-1){
338  if (FFreeKeyId==-1){
339  KeyId=KeyDatV.Add(THKeyDat(-1, HashCd, Key));
340  } else {
341  KeyId=FFreeKeyId; FFreeKeyId=KeyDatV[FFreeKeyId].Next; FreeKeys--;
342  //KeyDatV[KeyId]=TKeyDat(-1, HashCd, Key); // slow version
343  KeyDatV[KeyId].Next=-1;
344  KeyDatV[KeyId].HashCd=HashCd;
345  KeyDatV[KeyId].Key=Key;
346  //KeyDatV[KeyId].Dat=TDat(); // already empty
347  }
348  if (PrevKeyId==-1){
349  PortV[PortN]=KeyId;
350  } else {
351  KeyDatV[PrevKeyId].Next=KeyId;
352  }
353  }
354  return KeyId;
355 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:530
THash::THKeyDat
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:95
THash::Resize
void Resize()
Definition: hash.h:273
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:559
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:552
THash::IsKeyIdEqKeyN
bool IsKeyIdEqKeyN() const
Definition: hash.h:191
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
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:550
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 315 of file hash.h.

315  {
316  if (DoDel){
317  PortV.Clr(); KeyDatV.Clr();
318  } else {
319  PortV.PutAll(TInt(-1));
320  KeyDatV.Clr(DoDel, NoDelLim);
321  if (ResetDat){KeyDatV.PutAll(THKeyDat());}
322  }
323  FFreeKeyId=TInt(-1); FreeKeys=TInt(0);
324 }
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:953
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:1130
TInt
Definition: dt.h:1042
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 509 of file hash.h.

509  {
510  if (!IsKeyIdEqKeyN()){
511  THash<TKey, TDat, THashFunc> Hash(PortV.Len());
512  int KeyId=FFirstKeyId(); TKey Key; TDat Dat;
513  while (FNextKeyId(KeyId)){
514  GetKeyDat(KeyId, Key, Dat);
515  Hash.AddDat(Key, Dat);
516  }
517  Pack();
518  operator=(Hash);
519  IAssert(IsKeyIdEqKeyN());
520  }
521 }
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:225
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:232
THash
Definition: hash.h:88
THash::PortV
TIntV PortV
Definition: hash.h:97
THash::Pack
void Pack()
Definition: hash.h:243
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 358 of file hash.h.

358  {
359  IAssert(!PortV.Empty());
360  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
361  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
362  int PrevKeyId=-1;
363  int KeyId=PortV[PortN];
364 
365  while ((KeyId!=-1) &&
366  !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
367  PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}
368 
369  //IAssertR(KeyId!=-1, Key.GetStr()); //J: some classes do not provide GetStr()?
370  IAssert(KeyId!=-1); //J: some classes do not provide GetStr()?
371  if (PrevKeyId==-1){PortV[PortN]=KeyDatV[KeyId].Next;}
372  else {KeyDatV[PrevKeyId].Next=KeyDatV[KeyId].Next;}
373  KeyDatV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
374  KeyDatV[KeyId].HashCd=TInt(-1);
375  KeyDatV[KeyId].Key=TKey();
376  KeyDatV[KeyId].Dat=TDat();
377 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:530
TInt
Definition: dt.h:1042
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:358
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:535
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:552
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 232 of file hash.h.

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

Definition at line 432 of file hash.h.

432  {
433  do {KeyId++;} while ((KeyId<KeyDatV.Len())&&(KeyDatV[KeyId].HashCd==-1));
434  return KeyId<KeyDatV.Len();
435 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
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:1130
TInt
Definition: dt.h:1042
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:100
THash::GetNextPrime
uint GetNextPrime(const uint &Val) const
Definition: hash.h:261
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:486
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:420
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:420
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 487 of file hash.h.

487  {
488  DatKeyKdV.Gen(Len(), 0);
489  TKey Key; TDat Dat;
490  int KeyId=FFirstKeyId();
491  while (FNextKeyId(KeyId)){
492  GetKeyDat(KeyId, Key, Dat);
493  DatKeyKdV.Add(TKeyDat<TDat, TKey>(Dat, Key));
494  }
495 }
TKeyDat
Definition: ds.h:336
THash::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:225
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:232
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:486
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
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 465 of file hash.h.

465  {
466  DatKeyPrV.Gen(Len(), 0);
467  TKey Key; TDat Dat;
468  int KeyId=FFirstKeyId();
469  while (FNextKeyId(KeyId)){
470  GetKeyDat(KeyId, Key, Dat);
471  DatKeyPrV.Add(TPair<TDat, TKey>(Dat, Key));
472  }
473 }
THash::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:225
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:232
TPair
Definition: ds.h:32
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:486
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
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 446 of file hash.h.

446  {
447  DatV.Gen(Len(), 0);
448  int KeyId=FFirstKeyId();
449  while (FNextKeyId(KeyId)){
450  DatV.Add(GetHashKeyDat(KeyId).Dat);}
451 }
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:232
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:486
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
THash::Len
int Len() const
Definition: hash.h:186
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:552
THash::TIter
THashKeyDatI< TKey, TDat > TIter
Definition: hash.h:93
THash::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: hash.h:420
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 225 of file hash.h.

225  {
226  const THKeyDat& KeyDat=GetHashKeyDat(KeyId);
227  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 476 of file hash.h.

476  {
477  KeyDatKdV.Gen(Len(), 0);
478  TKey Key; TDat Dat;
479  int KeyId=FFirstKeyId();
480  while (FNextKeyId(KeyId)){
481  GetKeyDat(KeyId, Key, Dat);
482  KeyDatKdV.Add(TKeyDat<TKey, TDat>(Key, Dat));
483  }
484 }
TKeyDat
Definition: ds.h:336
THash::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:225
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:232
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:486
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
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 454 of file hash.h.

454  {
455  KeyDatPrV.Gen(Len(), 0);
456  TKey Key; TDat Dat;
457  int KeyId=FFirstKeyId();
458  while (FNextKeyId(KeyId)){
459  GetKeyDat(KeyId, Key, Dat);
460  KeyDatPrV.Add(TPair<TKey, TDat>(Key, Dat));
461  }
462 }
THash::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:225
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:232
TPair
Definition: ds.h:32
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:486
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
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 420 of file hash.h.

420  {
421  if (PortV.Empty()){return -1;}
422  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
423  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
424  int KeyId=PortV[PortN];
425  while ((KeyId!=-1) &&
426  !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
427  KeyId=KeyDatV[KeyId].Next;}
428  return KeyId;
429 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:530
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 438 of file hash.h.

438  {
439  KeyV.Gen(Len(), 0);
440  int KeyId=FFirstKeyId();
441  while (FNextKeyId(KeyId)){
442  KeyV.Add(GetKey(KeyId));}
443 }
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:232
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:486
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:559
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:537
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
TVec::GetMemUsed
TSizeTy GetMemUsed() const
Returns the memory footprint (the number of bytes) of the vector.
Definition: ds.h:474
TSize
size_t TSize
Definition: bd.h:58
TInt
Definition: dt.h:1042
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:535
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 261 of file hash.h.

261  {
262  const uint* f=(const uint*)HashPrimeT, *m, *l=(const uint*)HashPrimeT + (int)HashPrimes;
263  int h, len = (int)HashPrimes;
264  while (len > 0) {
265  h = len >> 1; m = f + h;
266  if (*m < Val) { f = m; f++; len = len - h - 1; }
267  else len = h;
268  }
269  return f == l ? *(l - 1) : *f;
270 }
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:535
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:537
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 398 of file hash.h.

398  {
399  IAssert(! Empty());
400  int KeyId = abs(Rnd.GetUniDevInt(KeyDatV.Len()));
401  while (KeyDatV[KeyId].HashCd == -1) { // if the index is empty, just try again
402  KeyId = abs(Rnd.GetUniDevInt(KeyDatV.Len())); }
403  return KeyId;
404 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
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 409 of file hash.h.

409  {
410  IAssert(! Empty());
411  if (FreeKeys/double(Len()+FreeKeys) > EmptyFrac) { Defrag(); }
412  int KeyId = Rnd.GetUniDevInt(KeyDatV.Len());
413  while (KeyDatV[KeyId].HashCd == -1) { // if the index is empty, just try again
414  KeyId = Rnd.GetUniDevInt(KeyDatV.Len());
415  }
416  return KeyId;
417 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
THash::Empty
bool Empty() const
Definition: hash.h:185
THash::Defrag
void Defrag()
Definition: hash.h:509
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:420
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:420
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 228 of file hash.h.

228  {int KeyId;
229  if (IsKey(Key, KeyId)){Dat=GetHashKeyDat(KeyId).Dat; return true;}
230  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:535
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:535
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:877
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:1042
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:535
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:420
template<class TKey, class TDat , class THashFunc >
void THash< TKey, TDat, THashFunc >::MarkDelKey ( const TKey &  Key)

Definition at line 380 of file hash.h.

380  {
381  // MarkDelKey is same as Delkey except last two lines
382  IAssert(!PortV.Empty());
383  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
384  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
385  int PrevKeyId=-1;
386  int KeyId=PortV[PortN];
387  while ((KeyId!=-1) &&
388  !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
389  PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}
390  IAssertR(KeyId!=-1, Key.GetStr());
391  if (PrevKeyId==-1){PortV[PortN]=KeyDatV[KeyId].Next;}
392  else {KeyDatV[PrevKeyId].Next=KeyDatV[KeyId].Next;}
393  KeyDatV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
394  KeyDatV[KeyId].HashCd=TInt(-1);
395 }
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:535
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:100
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:530
TInt
Definition: dt.h:1042
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:380
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 304 of file hash.h.

304  {
305  if (Len() != Hash.Len()) { return false; }
306  for (int i = FFirstKeyId(); FNextKeyId(i); ) {
307  const TKey& Key = GetKey(i);
308  if (! Hash.IsKey(Key)) { return false; }
309  if (GetDat(Key) != Hash.GetDat(Key)) { return false; }
310  }
311  return true;
312 }
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:220
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:432
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:232
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 243 of file hash.h.

243 {KeyDatV.Pack();}
TVec::Pack
void Pack()
The vector reduces its capacity (frees memory) to match its size.
Definition: ds.h:987
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 273 of file hash.h.

273  {
274  // resize & initialize port vector
275  //if (PortV.Len()==0){PortV.Gen(17);}
276  //else {PortV.Gen(2*PortV.Len()+1);}
277  if (PortV.Len()==0){
278  PortV.Gen(17);
279  } else if (AutoSizeP&&(KeyDatV.Len()>2*PortV.Len())){
280  PortV.Gen(GetNextPrime(PortV.Len()+1));
281  } else {
282  return;
283  }
284  PortV.PutAll(TInt(-1));
285  // rehash keys
286  for (int KeyId=0; KeyId<KeyDatV.Len(); KeyId++){
287  THKeyDat& KeyDat=KeyDatV[KeyId];
288  if (KeyDat.HashCd!=-1){
289  const int PortN = abs(THashFunc::GetPrimHashCd(KeyDat.Key) % PortV.Len());
290  KeyDat.Next=PortV[PortN];
291  PortV[PortN]=KeyId;
292  }
293  }
294 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:535
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:1130
TInt
Definition: dt.h:1042
THash::GetNextPrime
uint GetNextPrime(const uint &Val) const
Definition: hash.h:261
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:486
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:1058
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:885
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:509
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 524 of file hash.h.

524  {
525  IAssertR(IsKeyIdEqKeyN(), "THash::Sort only works when table has no deleted keys.");
526  TIntV TargV(Len()), MapV(Len()), StateV(Len());
527  for (int i = 0; i < TargV.Len(); i++) {
528  TargV[i] = i; MapV[i] = i; StateV[i] = i;
529  }
530  // sort KeyIds
531  THashKeyDatCmp HashCmp(*this, CmpKey, Asc);
532  TargV.SortCmp(HashCmp);
533  // now sort the update vector
534  THashKeyDat<TKey, TDat> Tmp;
535  for (int i = 0; i < TargV.Len()-1; i++) {
536  const int SrcPos = MapV[TargV[i]];
537  const int Loc = i;
538  // swap data
539  Tmp = KeyDatV[SrcPos];
540  KeyDatV[SrcPos] = KeyDatV[Loc];
541  KeyDatV[Loc] = Tmp;
542  // swap keys
543  MapV[StateV[i]] = SrcPos;
544  StateV.Swap(Loc, SrcPos);
545  }
546  for (int i = 0; i < TargV.Len(); i++) {
547  MapV[TargV[i]] = i; }
548  for (int p = 0; p < PortV.Len(); p++) {
549  if (PortV[p] != -1) {
550  PortV[p] = MapV[PortV[p]]; } }
551  for (int i = 0; i < KeyDatV.Len(); i++) {
552  if (KeyDatV[i].Next != -1) {
553  KeyDatV[i].Next = MapV[KeyDatV[i].Next]; }
554  }
555 }
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:535
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 246 of file hash.h.

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

Definition at line 245 of file hash.h.

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

Definition at line 498 of file hash.h.

498  {
499  if (this!=&Hash){
500  PortV.Swap(Hash.PortV);
501  KeyDatV.Swap(Hash.KeyDatV);
502  ::Swap(AutoSizeP, Hash.AutoSizeP);
503  ::Swap(FFreeKeyId, Hash.FFreeKeyId);
504  ::Swap(FreeKeys, Hash.FreeKeys);
505  }
506 }
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:1011
THash::Swap
void Swap(THash &Hash)
Definition: hash.h:498
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: