SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
THash< TKey, TDat, THashFunc > Class Template Reference

#include <hash.h>

Classes

class  THashKeyDatCmp
 
class  TLoadTHKeyDatInitializer
 

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 LoadShM (TShMIn &ShMIn)
 Load THash from shared memory file. Copying/Deleting Keys is illegal. More...
 
template<typename TDatInitFn >
void LoadShM (TShMIn &ShMIn, TDatInitFn Fn)
 Load THash from shared memory passing in the Dat initializer. More...
 
void Load (TSIn &SIn)
 
void Save (TSOut &SOut) const
 
void LoadXml (const PXmlTok &XmlTok, const TStr &Nm="")
 
void SaveXml (TSOut &SOut, const TStr &Nm)
 
THashoperator= (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

THKeyDatGetHashKeyDat (const int &KeyId)
 
const THKeyDatGetHashKeyDat (const int &KeyId) const
 
uint GetNextPrime (const uint &Val) const
 
void Resize ()
 

Private Attributes

TIntV PortV
 
TVec< THKeyDatKeyDatV
 
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 97 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 104 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 102 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 105 of file hash.h.

Member Enumeration Documentation

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

Definition at line 99 of file hash.h.

99 {HashPrimes=32};

Constructor & Destructor Documentation

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

Definition at line 145 of file hash.h.

145  :
146  PortV(), KeyDatV(),
147  AutoSizeP(true), FFreeKeyId(-1), FreeKeys(0){}
TInt FreeKeys
Definition: hash.h:109
TBool AutoSizeP
Definition: hash.h:108
TInt FFreeKeyId
Definition: hash.h:109
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
THash< TKey, TDat, THashFunc >::THash ( const THash< TKey, TDat, THashFunc > &  Hash)
inline

Definition at line 148 of file hash.h.

148  :
149  PortV(Hash.PortV), KeyDatV(Hash.KeyDatV), AutoSizeP(Hash.AutoSizeP),
150  FFreeKeyId(Hash.FFreeKeyId), FreeKeys(Hash.FreeKeys){}
TInt FreeKeys
Definition: hash.h:109
TBool AutoSizeP
Definition: hash.h:108
TInt FFreeKeyId
Definition: hash.h:109
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
template<class TKey , class TDat , class THashFunc >
THash< TKey, TDat, THashFunc >::THash ( const int &  ExpectVals,
const bool &  _AutoSizeP = false 
)
explicit

Definition at line 343 of file hash.h.

343  :
344  PortV(GetNextPrime(ExpectVals/2)), KeyDatV(ExpectVals, 0),
345  AutoSizeP(_AutoSizeP), FFreeKeyId(-1), FreeKeys(0){
346  PortV.PutAll(TInt(-1));
347 }
TInt FreeKeys
Definition: hash.h:109
TBool AutoSizeP
Definition: hash.h:108
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
Definition: dt.h:1137
TInt FFreeKeyId
Definition: hash.h:109
uint GetNextPrime(const uint &Val) const
Definition: hash.h:307
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
THash< TKey, TDat, THashFunc >::THash ( TSIn SIn)
inlineexplicit

Definition at line 152 of file hash.h.

152  :
153  PortV(SIn), KeyDatV(SIn),
154  AutoSizeP(SIn), FFreeKeyId(SIn), FreeKeys(SIn){
155  SIn.LoadCs();}
virtual void LoadCs()
Definition: fl.cpp:28
TInt FreeKeys
Definition: hash.h:109
TBool AutoSizeP
Definition: hash.h:108
TInt FFreeKeyId
Definition: hash.h:109
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107

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

238 {return KeyDatV[AddKey(Key)].Dat;}
int AddKey(const TKey &Key)
Definition: hash.h:373
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
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 239 of file hash.h.

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

Definition at line 236 of file hash.h.

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

Definition at line 373 of file hash.h.

373  {
374  if ((KeyDatV.Len()>2*PortV.Len())||PortV.Empty()){Resize();}
375  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
376  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
377  int PrevKeyId=-1;
378  int KeyId=PortV[PortN];
379  while ((KeyId!=-1) &&
380  !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
381  PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}
382 
383  if (KeyId==-1){
384  if (FFreeKeyId==-1){
385  KeyId=KeyDatV.Add(THKeyDat(-1, HashCd, Key));
386  } else {
388  //KeyDatV[KeyId]=TKeyDat(-1, HashCd, Key); // slow version
389  KeyDatV[KeyId].Next=-1;
390  KeyDatV[KeyId].HashCd=HashCd;
391  KeyDatV[KeyId].Key=Key;
392  //KeyDatV[KeyId].Dat=TDat(); // already empty
393  }
394  if (PrevKeyId==-1){
395  PortV[PortN]=KeyId;
396  } else {
397  KeyDatV[PrevKeyId].Next=KeyId;
398  }
399  }
400  return KeyId;
401 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TInt FreeKeys
Definition: hash.h:109
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:104
void Resize()
Definition: hash.h:319
TInt FFreeKeyId
Definition: hash.h:109
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
TIter THash< TKey, TDat, THashFunc >::BegI ( ) const
inline

Definition at line 213 of file hash.h.

213  {
214  if (Len() == 0){return TIter(KeyDatV.EndI(), KeyDatV.EndI());}
215  if (IsKeyIdEqKeyN()) { return TIter(KeyDatV.BegI(), KeyDatV.EndI());}
216  int FKeyId=-1; FNextKeyId(FKeyId);
217  return TIter(KeyDatV.BegI()+FKeyId, KeyDatV.EndI()); }
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
bool IsKeyIdEqKeyN() const
Definition: hash.h:233
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
THashKeyDatI< TKey, TDat > TIter
Definition: hash.h:102
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
int Len() const
Definition: hash.h:228
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 361 of file hash.h.

361  {
362  if (DoDel){
363  PortV.Clr(); KeyDatV.Clr();
364  } else {
365  PortV.PutAll(TInt(-1));
366  KeyDatV.Clr(DoDel, NoDelLim);
367  if (ResetDat){KeyDatV.PutAll(THKeyDat());}
368  }
369  FFreeKeyId=TInt(-1); FreeKeys=TInt(0);
370 }
TInt FreeKeys
Definition: hash.h:109
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:104
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
Definition: dt.h:1137
TInt FFreeKeyId
Definition: hash.h:109
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
template<class TKey , class TDat , class THashFunc >
void THash< TKey, TDat, THashFunc >::Defrag ( )

Definition at line 555 of file hash.h.

555  {
556  if (!IsKeyIdEqKeyN()){
558  int KeyId=FFirstKeyId(); TKey Key; TDat Dat;
559  while (FNextKeyId(KeyId)){
560  GetKeyDat(KeyId, Key, Dat);
561  Hash.AddDat(Key, Dat);
562  }
563  Pack();
564  operator=(Hash);
566  }
567 }
#define IAssert(Cond)
Definition: bd.h:262
bool IsKeyIdEqKeyN() const
Definition: hash.h:233
THash & operator=(const THash &Hash)
Definition: hash.h:190
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:271
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
Definition: hash.h:97
TIntV PortV
Definition: hash.h:106
void Pack()
Definition: hash.h:289
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
bool THash< TKey, TDat, THashFunc >::DelIfKey ( const TKey &  Key)
inline

Definition at line 243 of file hash.h.

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

Definition at line 404 of file hash.h.

404  {
405  IAssert(!PortV.Empty());
406  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
407  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
408  int PrevKeyId=-1;
409  int KeyId=PortV[PortN];
410 
411  while ((KeyId!=-1) &&
412  !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
413  PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}
414 
415  //IAssertR(KeyId!=-1, Key.GetStr()); //J: some classes do not provide GetStr()?
416  IAssert(KeyId!=-1); //J: some classes do not provide GetStr()?
417  if (PrevKeyId==-1){PortV[PortN]=KeyDatV[KeyId].Next;}
418  else {KeyDatV[PrevKeyId].Next=KeyDatV[KeyId].Next;}
419  KeyDatV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
420  KeyDatV[KeyId].HashCd=TInt(-1);
421  KeyDatV[KeyId].Key=TKey();
422  KeyDatV[KeyId].Dat=TDat();
423 }
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TInt FreeKeys
Definition: hash.h:109
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
Definition: dt.h:1137
TInt FFreeKeyId
Definition: hash.h:109
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
void THash< TKey, TDat, THashFunc >::DelKeyId ( const int &  KeyId)
inline

Definition at line 245 of file hash.h.

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

Definition at line 246 of file hash.h.

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

Definition at line 227 of file hash.h.

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

Definition at line 218 of file hash.h.

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

Definition at line 278 of file hash.h.

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

Definition at line 478 of file hash.h.

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

Definition at line 222 of file hash.h.

222  {
223  PortV.Gen(GetNextPrime(ExpectVals/2)); KeyDatV.Gen(ExpectVals, 0);
224  FFreeKeyId=-1; FreeKeys=0; PortV.PutAll(TInt(-1));}
TInt FreeKeys
Definition: hash.h:109
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
Definition: dt.h:1137
TInt FFreeKeyId
Definition: hash.h:109
uint GetNextPrime(const uint &Val) const
Definition: hash.h:307
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
const TDat& THash< TKey, TDat, THashFunc >::GetDat ( const TKey &  Key) const
inline

Definition at line 262 of file hash.h.

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

Definition at line 263 of file hash.h.

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

Definition at line 533 of file hash.h.

533  {
534  DatKeyKdV.Gen(Len(), 0);
535  TKey Key; TDat Dat;
536  int KeyId=FFirstKeyId();
537  while (FNextKeyId(KeyId)){
538  GetKeyDat(KeyId, Key, Dat);
539  DatKeyKdV.Add(TKeyDat<TDat, TKey>(Dat, Key));
540  }
541 }
Definition: ds.h:346
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:271
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
template<class TKey, class TDat, class THashFunc >
void THash< TKey, TDat, THashFunc >::GetDatKeyPrV ( TVec< TPair< TDat, TKey > > &  DatKeyPrV) const

Definition at line 511 of file hash.h.

511  {
512  DatKeyPrV.Gen(Len(), 0);
513  TKey Key; TDat Dat;
514  int KeyId=FFirstKeyId();
515  while (FNextKeyId(KeyId)){
516  GetKeyDat(KeyId, Key, Dat);
517  DatKeyPrV.Add(TPair<TDat, TKey>(Dat, Key));
518  }
519 }
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:271
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
Definition: ds.h:32
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
template<class TKey , class TDat, class THashFunc >
void THash< TKey, TDat, THashFunc >::GetDatV ( TVec< TDat > &  DatV) const

Definition at line 492 of file hash.h.

492  {
493  DatV.Gen(Len(), 0);
494  int KeyId=FFirstKeyId();
495  while (FNextKeyId(KeyId)){
496  DatV.Add(GetHashKeyDat(KeyId).Dat);}
497 }
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
THKeyDat & GetHashKeyDat(const int &KeyId)
Definition: hash.h:136
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
TDat THash< TKey, TDat, THashFunc >::GetDatWithDefault ( const TKey &  Key,
TDat  DefaultValue 
)
inline

Definition at line 264 of file hash.h.

264  {
265  int KeyId = GetKeyId(Key);
266  return KeyId >= 0 ? KeyDatV[KeyId].Dat : DefaultValue;
267  }
int GetKeyId(const TKey &Key) const
Definition: hash.h:466
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
THKeyDat& THash< TKey, TDat, THashFunc >::GetHashKeyDat ( const int &  KeyId)
inlineprivate

Definition at line 136 of file hash.h.

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

Definition at line 139 of file hash.h.

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

Definition at line 220 of file hash.h.

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

Definition at line 252 of file hash.h.

252 { return GetHashKeyDat(KeyId).Key;}
THKeyDat & GetHashKeyDat(const int &KeyId)
Definition: hash.h:136
TKey Key
Definition: hash.h:12
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 271 of file hash.h.

271  {
272  const THKeyDat& KeyDat=GetHashKeyDat(KeyId);
273  Key=KeyDat.Key; Dat=KeyDat.Dat;}
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:104
THKeyDat & GetHashKeyDat(const int &KeyId)
Definition: hash.h:136
template<class TKey, class TDat, class THashFunc >
void THash< TKey, TDat, THashFunc >::GetKeyDatKdV ( TVec< TKeyDat< TKey, TDat > > &  KeyDatKdV) const

Definition at line 522 of file hash.h.

522  {
523  KeyDatKdV.Gen(Len(), 0);
524  TKey Key; TDat Dat;
525  int KeyId=FFirstKeyId();
526  while (FNextKeyId(KeyId)){
527  GetKeyDat(KeyId, Key, Dat);
528  KeyDatKdV.Add(TKeyDat<TKey, TDat>(Key, Dat));
529  }
530 }
Definition: ds.h:346
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:271
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
template<class TKey, class TDat, class THashFunc >
void THash< TKey, TDat, THashFunc >::GetKeyDatPrV ( TVec< TPair< TKey, TDat > > &  KeyDatPrV) const

Definition at line 500 of file hash.h.

500  {
501  KeyDatPrV.Gen(Len(), 0);
502  TKey Key; TDat Dat;
503  int KeyId=FFirstKeyId();
504  while (FNextKeyId(KeyId)){
505  GetKeyDat(KeyId, Key, Dat);
506  KeyDatPrV.Add(TPair<TKey, TDat>(Key, Dat));
507  }
508 }
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:271
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
Definition: ds.h:32
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
template<class TKey, class TDat , class THashFunc >
int THash< TKey, TDat, THashFunc >::GetKeyId ( const TKey &  Key) const

Definition at line 466 of file hash.h.

466  {
467  if (PortV.Empty()){return -1;}
468  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
469  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
470  int KeyId=PortV[PortN];
471  while ((KeyId!=-1) &&
472  !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
473  KeyId=KeyDatV[KeyId].Next;}
474  return KeyId;
475 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
template<class TKey, class TDat , class THashFunc >
void THash< TKey, TDat, THashFunc >::GetKeyV ( TVec< TKey > &  KeyV) const

Definition at line 484 of file hash.h.

484  {
485  KeyV.Gen(Len(), 0);
486  int KeyId=FFirstKeyId();
487  while (FNextKeyId(KeyId)){
488  KeyV.Add(GetKey(KeyId));}
489 }
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int Len() const
Definition: hash.h:228
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
::TSize THash< TKey, TDat, THashFunc >::GetMemUsed ( ) const
inline

Definition at line 201 of file hash.h.

201  {
202  // return PortV.GetMemUsed()+KeyDatV.GetMemUsed()+sizeof(bool)+2*sizeof(int);}
203  int64 MemUsed = sizeof(bool)+2*sizeof(int);
204  MemUsed += int64(PortV.Reserved()) * int64(sizeof(TInt));
205  for (int KeyDatN = 0; KeyDatN < KeyDatV.Len(); KeyDatN++) {
206  MemUsed += int64(2 * sizeof(TInt));
207  MemUsed += int64(KeyDatV[KeyDatN].Key.GetMemUsed());
208  MemUsed += int64(KeyDatV[KeyDatN].Dat.GetMemUsed());
209  }
210  return ::TSize(MemUsed);
211  }
TSizeTy Reserved() const
Returns the size of allocated storage capacity.
Definition: ds.h:577
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TSizeTy GetMemUsed() const
Returns the memory footprint (the number of bytes) of the vector.
Definition: ds.h:511
size_t TSize
Definition: bd.h:58
Definition: dt.h:1137
long long int64
Definition: bd.h:27
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
int THash< TKey, TDat, THashFunc >::GetMxKeyIds ( ) const
inline

Definition at line 231 of file hash.h.

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

Definition at line 307 of file hash.h.

307  {
308  const uint* f=(const uint*)HashPrimeT, *m, *l=(const uint*)HashPrimeT + (int)HashPrimes;
309  int h, len = (int)HashPrimes;
310  while (len > 0) {
311  h = len >> 1; m = f + h;
312  if (*m < Val) { f = m; f++; len = len - h - 1; }
313  else len = h;
314  }
315  return f == l ? *(l - 1) : *f;
316 }
unsigned int uint
Definition: bd.h:11
static const unsigned int HashPrimeT[HashPrimes]
Definition: hash.h:100
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
int THash< TKey, TDat, THashFunc >::GetPorts ( ) const
inline

Definition at line 229 of file hash.h.

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

Definition at line 232 of file hash.h.

232 {return KeyDatV.Reserved();}
TSizeTy Reserved() const
Returns the size of allocated storage capacity.
Definition: ds.h:577
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
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 444 of file hash.h.

444  {
445  IAssert(! Empty());
446  int KeyId = abs(Rnd.GetUniDevInt(KeyDatV.Len()));
447  while (KeyDatV[KeyId].HashCd == -1) { // if the index is empty, just try again
448  KeyId = abs(Rnd.GetUniDevInt(KeyDatV.Len())); }
449  return KeyId;
450 }
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
bool Empty() const
Definition: hash.h:227
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
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 455 of file hash.h.

455  {
456  IAssert(! Empty());
457  if (FreeKeys/double(Len()+FreeKeys) > EmptyFrac) { Defrag(); }
458  int KeyId = Rnd.GetUniDevInt(KeyDatV.Len());
459  while (KeyDatV[KeyId].HashCd == -1) { // if the index is empty, just try again
460  KeyId = Rnd.GetUniDevInt(KeyDatV.Len());
461  }
462  return KeyId;
463 }
#define IAssert(Cond)
Definition: bd.h:262
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
bool Empty() const
Definition: hash.h:227
void Defrag()
Definition: hash.h:555
TInt FreeKeys
Definition: hash.h:109
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
int Len() const
Definition: hash.h:228
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
bool THash< TKey, TDat, THashFunc >::IsAutoSize ( ) const
inline

Definition at line 230 of file hash.h.

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

Definition at line 258 of file hash.h.

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

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

274  {int KeyId;
275  if (IsKey(Key, KeyId)){Dat=GetHashKeyDat(KeyId).Dat; return true;}
276  else {return false;}}
TDat Dat
Definition: hash.h:13
THKeyDat & GetHashKeyDat(const int &KeyId)
Definition: hash.h:136
bool IsKey(const TKey &Key) const
Definition: hash.h:258
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
bool THash< TKey, TDat, THashFunc >::IsKeyId ( const int &  KeyId) const
inline

Definition at line 260 of file hash.h.

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

Definition at line 233 of file hash.h.

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

Definition at line 228 of file hash.h.

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

Definition at line 177 of file hash.h.

177  {
178  PortV.Load(SIn); KeyDatV.Load(SIn);
179  AutoSizeP=TBool(SIn); FFreeKeyId=TInt(SIn); FreeKeys=TInt(SIn);
180  SIn.LoadCs();
181  }
void Load(TSIn &SIn)
Definition: ds.h:946
virtual void LoadCs()
Definition: fl.cpp:28
TInt FreeKeys
Definition: hash.h:109
TBool AutoSizeP
Definition: hash.h:108
Definition: dt.h:1137
TInt FFreeKeyId
Definition: hash.h:109
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
Definition: dt.h:974
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
void THash< TKey, TDat, THashFunc >::LoadShM ( TShMIn ShMIn)
inline

Load THash from shared memory file. Copying/Deleting Keys is illegal.

Definition at line 157 of file hash.h.

157  {
158  PortV.LoadShM(ShMIn);
159  KeyDatV.Load(ShMIn);
160  AutoSizeP=TBool(ShMIn);
161  FFreeKeyId=TInt(ShMIn);
162  FreeKeys=TInt(ShMIn);
163  ShMIn.LoadCs();
164  }
void Load(TSIn &SIn)
Definition: ds.h:946
TInt FreeKeys
Definition: hash.h:109
TBool AutoSizeP
Definition: hash.h:108
Definition: dt.h:1137
void LoadShM(TShMIn &ShMIn)
Constructs the vector from a shared memory input.
Definition: ds.h:932
TInt FFreeKeyId
Definition: hash.h:109
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
Definition: dt.h:974
void LoadCs()
Definition: fl.h:408
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
template<typename TDatInitFn >
void THash< TKey, TDat, THashFunc >::LoadShM ( TShMIn ShMIn,
TDatInitFn  Fn 
)
inline

Load THash from shared memory passing in the Dat initializer.

Definition at line 167 of file hash.h.

167  {
168  TLoadTHKeyDatInitializer<TDatInitFn> HKeyDatFn(Fn);
169  PortV.LoadShM(ShMIn);
170  KeyDatV.LoadShM(ShMIn, HKeyDatFn);
171  AutoSizeP=TBool(ShMIn);
172  FFreeKeyId=TInt(ShMIn);
173  FreeKeys=TInt(ShMIn);
174  ShMIn.LoadCs();
175  }
TInt FreeKeys
Definition: hash.h:109
TBool AutoSizeP
Definition: hash.h:108
Definition: dt.h:1137
void LoadShM(TShMIn &ShMIn)
Constructs the vector from a shared memory input.
Definition: ds.h:932
TInt FFreeKeyId
Definition: hash.h:109
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
Definition: dt.h:974
void LoadCs()
Definition: fl.h:408
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  {
129  for (int KeyDatN=0; KeyDatN<KeyDatV.Len(); KeyDatN++){
130  AddDat(KeyDatV[KeyDatN].Key, KeyDatV[KeyDatN].Dat);}}
#define XLoadHd(Nm)
Definition: bd.h:312
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
#define XLoad(Nm)
Definition: bd.h:315
TBool AutoSizeP
Definition: hash.h:108
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
template<class TKey, class TDat , class THashFunc >
void THash< TKey, TDat, THashFunc >::MarkDelKey ( const TKey &  Key)

Definition at line 426 of file hash.h.

426  {
427  // MarkDelKey is same as Delkey except last two lines
428  IAssert(!PortV.Empty());
429  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
430  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
431  int PrevKeyId=-1;
432  int KeyId=PortV[PortN];
433  while ((KeyId!=-1) &&
434  !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
435  PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}
436  IAssertR(KeyId!=-1, Key.GetStr());
437  if (PrevKeyId==-1){PortV[PortN]=KeyDatV[KeyId].Next;}
438  else {KeyDatV[PrevKeyId].Next=KeyDatV[KeyId].Next;}
439  KeyDatV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
440  KeyDatV[KeyId].HashCd=TInt(-1);
441 }
#define IAssert(Cond)
Definition: bd.h:262
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TInt FreeKeys
Definition: hash.h:109
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
Definition: dt.h:1137
TInt FFreeKeyId
Definition: hash.h:109
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
void THash< TKey, TDat, THashFunc >::MarkDelKeyId ( const int &  KeyId)
inline

Definition at line 250 of file hash.h.

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

Definition at line 200 of file hash.h.

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

196 { Fail; return true; }
#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 190 of file hash.h.

190  {
191  if (this!=&Hash){
192  PortV=Hash.PortV; KeyDatV=Hash.KeyDatV; AutoSizeP=Hash.AutoSizeP;
194  return *this;}
TInt FreeKeys
Definition: hash.h:109
TBool AutoSizeP
Definition: hash.h:108
TInt FFreeKeyId
Definition: hash.h:109
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
template<class TKey , class TDat , class THashFunc >
bool THash< TKey, TDat, THashFunc >::operator== ( const THash< TKey, TDat, THashFunc > &  Hash) const

Definition at line 350 of file hash.h.

350  {
351  if (Len() != Hash.Len()) { return false; }
352  for (int i = FFirstKeyId(); FNextKeyId(i); ) {
353  const TKey& Key = GetKey(i);
354  if (! Hash.IsKey(Key)) { return false; }
355  if (GetDat(Key) != Hash.GetDat(Key)) { return false; }
356  }
357  return true;
358 }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
bool IsKey(const TKey &Key) const
Definition: hash.h:258
int Len() const
Definition: hash.h:228
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
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 198 of file hash.h.

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

Definition at line 199 of file hash.h.

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

Definition at line 289 of file hash.h.

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

Definition at line 319 of file hash.h.

319  {
320  // resize & initialize port vector
321  //if (PortV.Len()==0){PortV.Gen(17);}
322  //else {PortV.Gen(2*PortV.Len()+1);}
323  if (PortV.Len()==0){
324  PortV.Gen(17);
325  } else if (AutoSizeP&&(KeyDatV.Len()>2*PortV.Len())){
327  } else {
328  return;
329  }
330  PortV.PutAll(TInt(-1));
331  // rehash keys
332  for (int KeyId=0; KeyId<KeyDatV.Len(); KeyId++){
333  THKeyDat& KeyDat=KeyDatV[KeyId];
334  if (KeyDat.HashCd!=-1){
335  const int PortN = abs(THashFunc::GetPrimHashCd(KeyDat.Key) % PortV.Len());
336  KeyDat.Next=PortV[PortN];
337  PortV[PortN]=KeyId;
338  }
339  }
340 }
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TBool AutoSizeP
Definition: hash.h:108
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:104
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
Definition: dt.h:1137
uint GetNextPrime(const uint &Val) const
Definition: hash.h:307
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
void THash< TKey, TDat, THashFunc >::Save ( TSOut SOut) const
inline

Definition at line 183 of file hash.h.

183  {
184  PortV.Save(SOut); KeyDatV.Save(SOut);
185  AutoSizeP.Save(SOut); FFreeKeyId.Save(SOut); FreeKeys.Save(SOut);
186  SOut.SaveCs();}
void Save(TSOut &SOut) const
Definition: dt.h:1153
void Save(TSOut &SOut) const
Definition: dt.h:995
TInt FreeKeys
Definition: hash.h:109
void Save(TSOut &SOut) const
Definition: ds.h:954
TBool AutoSizeP
Definition: hash.h:108
void SaveCs()
Definition: fl.h:171
TInt FFreeKeyId
Definition: hash.h:109
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
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  {
#define XSaveHd(Nm)
Definition: bd.h:318
#define XSave(Nm)
Definition: bd.h:333
void Defrag()
Definition: hash.h:555
TBool AutoSizeP
Definition: hash.h:108
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
template<class TKey , class TDat , class THashFunc >
void THash< TKey, TDat, THashFunc >::Sort ( const bool &  CmpKey,
const bool &  Asc 
)

Definition at line 570 of file hash.h.

570  {
571  IAssertR(IsKeyIdEqKeyN(), "THash::Sort only works when table has no deleted keys.");
572  TIntV TargV(Len()), MapV(Len()), StateV(Len());
573  for (int i = 0; i < TargV.Len(); i++) {
574  TargV[i] = i; MapV[i] = i; StateV[i] = i;
575  }
576  // sort KeyIds
577  THashKeyDatCmp HashCmp(*this, CmpKey, Asc);
578  TargV.SortCmp(HashCmp);
579  // now sort the update vector
581  for (int i = 0; i < TargV.Len()-1; i++) {
582  const int SrcPos = MapV[TargV[i]];
583  const int Loc = i;
584  // swap data
585  Tmp = KeyDatV[SrcPos];
586  KeyDatV[SrcPos] = KeyDatV[Loc];
587  KeyDatV[Loc] = Tmp;
588  // swap keys
589  MapV[StateV[i]] = SrcPos;
590  StateV.Swap(Loc, SrcPos);
591  }
592  for (int i = 0; i < TargV.Len(); i++) {
593  MapV[TargV[i]] = i; }
594  for (int p = 0; p < PortV.Len(); p++) {
595  if (PortV[p] != -1) {
596  PortV[p] = MapV[PortV[p]]; } }
597  for (int i = 0; i < KeyDatV.Len(); i++) {
598  if (KeyDatV[i].Next != -1) {
599  KeyDatV[i].Next = MapV[KeyDatV[i].Next]; }
600  }
601 }
bool IsKeyIdEqKeyN() const
Definition: hash.h:233
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
int Len() const
Definition: hash.h:228
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
void THash< TKey, TDat, THashFunc >::SortByDat ( const bool &  Asc = true)
inline

Definition at line 292 of file hash.h.

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

Definition at line 291 of file hash.h.

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

Definition at line 544 of file hash.h.

544  {
545  if (this!=&Hash){
546  PortV.Swap(Hash.PortV);
547  KeyDatV.Swap(Hash.KeyDatV);
548  ::Swap(AutoSizeP, Hash.AutoSizeP);
550  ::Swap(FreeKeys, Hash.FreeKeys);
551  }
552 }
TInt FreeKeys
Definition: hash.h:109
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
void Swap(THash &Hash)
Definition: hash.h:544
TBool AutoSizeP
Definition: hash.h:108
TInt FFreeKeyId
Definition: hash.h:109
TIntV PortV
Definition: hash.h:106
TVec< THKeyDat > KeyDatV
Definition: hash.h:107

Member Data Documentation

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

Definition at line 108 of file hash.h.

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

Definition at line 109 of file hash.h.

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

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

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

Definition at line 107 of file hash.h.

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

Definition at line 106 of file hash.h.


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