SNAP Library 4.1, User Reference  2018-07-26 16:30:42
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
 
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)
 
THash & operator= (const THash &Hash)
 
bool operator== (const THash &Hash) const
 
bool operator< (const THash &Hash) const
 
const TDat & operator[] (const int &KeyId) const
 The [] operator takes KeyId, use GetDat() if you need value access via the key. More...
 
TDat & operator[] (const int &KeyId)
 
TDat & operator() (const TKey &Key)
 
::TSize GetMemUsed () const
 
TIter BegI () const
 
TIter EndI () const
 
TIter GetI (const TKey &Key) const
 
void Gen (const int &ExpectVals)
 
void Clr (const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
 
bool Empty () const
 
int Len () const
 
int GetPorts () const
 
bool IsAutoSize () const
 
int GetMxKeyIds () const
 
int GetReservedKeyIds () const
 
bool IsKeyIdEqKeyN () const
 
int AddKey (const TKey &Key)
 
TDat & AddDatId (const TKey &Key)
 
TDat & AddDat (const TKey &Key)
 
TDat & AddDat (const TKey &Key, const TDat &Dat)
 
void DelKey (const TKey &Key)
 
bool DelIfKey (const TKey &Key)
 
void DelKeyId (const int &KeyId)
 
void DelKeyIdV (const TIntV &KeyIdV)
 
void MarkDelKey (const TKey &Key)
 
void MarkDelKeyId (const int &KeyId)
 
const TKey & GetKey (const int &KeyId) const
 
int GetKeyId (const TKey &Key) const
 
int GetRndKeyId (TRnd &Rnd) const
 Get an index of a random element. If the hash table has many deleted keys, this may take a long time. More...
 
int GetRndKeyId (TRnd &Rnd, const double &EmptyFrac)
 Get an index of a random element. If the hash table has many deleted keys, defrag the hash table first (that's why the function is non-const). More...
 
bool IsKey (const TKey &Key) const
 
bool IsKey (const TKey &Key, int &KeyId) const
 
bool IsKeyId (const int &KeyId) const
 
const TDat & GetDat (const TKey &Key) const
 
TDat & GetDat (const TKey &Key)
 
TDat GetDatWithDefault (const TKey &Key, TDat DefaultValue)
 
void GetKeyDat (const int &KeyId, TKey &Key, TDat &Dat) const
 
bool IsKeyGetDat (const TKey &Key, TDat &Dat) const
 
int FFirstKeyId () const
 
bool FNextKeyId (int &KeyId) const
 
void GetKeyV (TVec< TKey > &KeyV) const
 
void GetDatV (TVec< TDat > &DatV) const
 
void GetKeyDatPrV (TVec< TPair< TKey, TDat > > &KeyDatPrV) const
 
void GetDatKeyPrV (TVec< TPair< TDat, TKey > > &DatKeyPrV) const
 
void GetKeyDatKdV (TVec< TKeyDat< TKey, TDat > > &KeyDatKdV) const
 
void GetDatKeyKdV (TVec< TKeyDat< TDat, TKey > > &DatKeyKdV) const
 
void Swap (THash &Hash)
 
void Defrag ()
 
void Pack ()
 
void Sort (const bool &CmpKey, const bool &Asc)
 
void SortByKey (const bool &Asc=true)
 
void SortByDat (const bool &Asc=true)
 

Static Public Attributes

static const unsigned int HashPrimeT [HashPrimes]
 

Private Types

typedef THashKeyDat< TKey, TDat > THKeyDat
 
typedef TPair< TKey, TDat > TKeyDatP
 

Private Member Functions

THKeyDat & GetHashKeyDat (const int &KeyId)
 
const THKeyDat & GetHashKeyDat (const int &KeyId) const
 
uint GetNextPrime (const uint &Val) const
 
void Resize ()
 

Private Attributes

TIntV PortV
 
TVec< THKeyDat > KeyDatV
 
TBool AutoSizeP
 
TInt FFreeKeyId
 
TInt FreeKeys
 

Detailed Description

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

Definition at line 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){}
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:109
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:108
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:109
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
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){}
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:109
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:108
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:109
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
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 }
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:109
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:108
TVec::PutAll
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
TInt
Definition: dt.h:1134
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:109
THash::GetNextPrime
uint GetNextPrime(const uint &Val) const
Definition: hash.h:307
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
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();}
TSIn::LoadCs
virtual void LoadCs()
Definition: fl.cpp:28
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:109
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:108
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:109
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
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;}
THash::AddKey
int AddKey(const TKey &Key)
Definition: hash.h:373
THash::KeyDatV
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;}
THash::AddKey
int AddKey(const TKey &Key)
Definition: hash.h:373
THash::KeyDatV
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;}
THash::AddKey
int AddKey(const TKey &Key)
Definition: hash.h:373
THash::KeyDatV
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 {
387  KeyId=FFreeKeyId; FFreeKeyId=KeyDatV[FFreeKeyId].Next; FreeKeys--;
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 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:109
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
THash::THKeyDat
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:104
THash::Resize
void Resize()
Definition: hash.h:319
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:109
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
TVec::Add
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()); }
TVec::EndI
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
THash::IsKeyIdEqKeyN
bool IsKeyIdEqKeyN() const
Definition: hash.h:233
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
THash::TIter
THashKeyDatI< TKey, TDat > TIter
Definition: hash.h:102
TVec::BegI
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
THash::Len
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 }
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:109
TVec::Clr
void Clr(const bool &DoDel=true, const TSizeTy &NoDelLim=-1)
Clears the contents of the vector.
Definition: ds.h:1022
THash::THKeyDat
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:104
TVec::PutAll
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
TInt
Definition: dt.h:1134
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:109
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
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()){
557  THash<TKey, TDat, THashFunc> Hash(PortV.Len());
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);
565  IAssert(IsKeyIdEqKeyN());
566  }
567 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
THash::IsKeyIdEqKeyN
bool IsKeyIdEqKeyN() const
Definition: hash.h:233
THash::operator=
THash & operator=(const THash &Hash)
Definition: hash.h:190
THash::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:271
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:278
THash
Definition: hash.h:97
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::Pack
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;}
THash::DelKeyId
void DelKeyId(const int &KeyId)
Definition: hash.h:245
THash::IsKey
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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:109
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
TInt
Definition: dt.h:1134
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:109
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
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));}
THash::DelKey
void DelKey(const TKey &Key)
Definition: hash.h:404
THash::GetKey
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]);}}
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::DelKeyId
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;}
THash::Len
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());}
TVec::EndI
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
THash::TIter
THashKeyDatI< TKey, TDat > TIter
Definition: hash.h:102
THash::KeyDatV
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 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::KeyDatV
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));}
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:109
TVec::PutAll
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
TInt
Definition: dt.h:1134
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:109
THash::GetNextPrime
uint GetNextPrime(const uint &Val) const
Definition: hash.h:307
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
TVec::Gen
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;}
THash::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: hash.h:466
THash::KeyDatV
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;}
THash::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: hash.h:466
THash::KeyDatV
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 }
TKeyDat
Definition: ds.h:346
THash::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:271
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:278
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
THash::Len
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 }
THash::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:271
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:278
TPair
Definition: ds.h:32
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
THash::Len
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 }
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:278
THash::GetHashKeyDat
THKeyDat & GetHashKeyDat(const int &KeyId)
Definition: hash.h:136
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
THash::Len
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  }
THash::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: hash.h:466
THash::KeyDatV
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;}
THash::THKeyDat
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:104
Assert
#define Assert(Cond)
Definition: bd.h:251
THash::KeyDatV
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;}
THash::THKeyDat
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:104
Assert
#define Assert(Cond)
Definition: bd.h:251
THash::KeyDatV
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());}
TVec::EndI
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
THash::TIter
THashKeyDatI< TKey, TDat > TIter
Definition: hash.h:102
THash::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: hash.h:466
THash::KeyDatV
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;}
THash::GetHashKeyDat
THKeyDat & GetHashKeyDat(const int &KeyId)
Definition: hash.h:136
THashKeyDat::Key
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;}
THash::THKeyDat
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:104
THash::GetHashKeyDat
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 }
TKeyDat
Definition: ds.h:346
THash::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:271
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:278
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
THash::Len
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 }
THash::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:271
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:278
TPair
Definition: ds.h:32
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
THash::Len
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 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
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 }
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:278
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
THash::Len
int Len() const
Definition: hash.h:228
THash::GetKey
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  }
TVec::Reserved
TSizeTy Reserved() const
Returns the size of allocated storage capacity.
Definition: ds.h:577
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TVec::GetMemUsed
TSizeTy GetMemUsed() const
Returns the memory footprint (the number of bytes) of the vector.
Definition: ds.h:511
TSize
size_t TSize
Definition: bd.h:58
TInt
Definition: dt.h:1134
int64
long long int64
Definition: bd.h:27
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
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();}
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::KeyDatV
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 }
uint
unsigned int uint
Definition: bd.h:11
THash::HashPrimeT
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();}
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::PortV
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();}
TVec::Reserved
TSizeTy Reserved() const
Returns the size of allocated storage capacity.
Definition: ds.h:577
THash::KeyDatV
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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::Empty
bool Empty() const
Definition: hash.h:227
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
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 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 }
IAssert
#define IAssert(Cond)
Definition: bd.h:262
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::Empty
bool Empty() const
Definition: hash.h:227
THash::Defrag
void Defrag()
Definition: hash.h:555
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:109
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
TRnd::GetUniDevInt
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
THash::Len
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;}
THash::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;}
THash::GetKeyId
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;}
THash::GetKeyId
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;}}
THashKeyDat::Dat
TDat Dat
Definition: hash.h:13
THash::GetHashKeyDat
THKeyDat & GetHashKeyDat(const int &KeyId)
Definition: hash.h:136
THash::IsKey
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);}
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::KeyDatV
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;}
THash::FreeKeys
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;}
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:109
THash::KeyDatV
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  }
TVec::Load
void Load(TSIn &SIn)
Definition: ds.h:946
TSIn::LoadCs
virtual void LoadCs()
Definition: fl.cpp:28
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:109
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:108
TInt
Definition: dt.h:1134
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:109
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
TBool
Definition: dt.h:971
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  }
TVec::Load
void Load(TSIn &SIn)
Definition: ds.h:946
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:109
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:108
TInt
Definition: dt.h:1134
TVec::LoadShM
void LoadShM(TShMIn &ShMIn)
Constructs the vector from a shared memory input.
Definition: ds.h:932
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:109
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
TBool
Definition: dt.h:971
TShMIn::LoadCs
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  }
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:109
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:108
TInt
Definition: dt.h:1134
TVec::LoadShM
void LoadShM(TShMIn &ShMIn)
Constructs the vector from a shared memory input.
Definition: ds.h:932
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:109
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
TBool
Definition: dt.h:971
TShMIn::LoadCs
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  {
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:575
XLoad
#define XLoad(Nm)
Definition: bd.h:315
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:108
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
THash::AddDat
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
TVec
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 }
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:575
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:109
TVec::Empty
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
TInt
Definition: dt.h:1134
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:109
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
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));}
THash::MarkDelKey
void MarkDelKey(const TKey &Key)
Definition: hash.h:426
THash::GetKey
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);}
THash::AddDat
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; }
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 190 of file hash.h.

190  {
191  if (this!=&Hash){
192  PortV=Hash.PortV; KeyDatV=Hash.KeyDatV; AutoSizeP=Hash.AutoSizeP;
193  FFreeKeyId=Hash.FFreeKeyId; FreeKeys=Hash.FreeKeys;}
194  return *this;}
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:109
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:108
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:109
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
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 }
THash::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
THash::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
THash::FFirstKeyId
int FFirstKeyId() const
Definition: hash.h:278
THash::IsKey
bool IsKey(const TKey &Key) const
Definition: hash.h:258
THash::Len
int Len() const
Definition: hash.h:228
THash::GetKey
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;}
THashKeyDat::Dat
TDat Dat
Definition: hash.h:13
THash::GetHashKeyDat
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;}
THashKeyDat::Dat
TDat Dat
Definition: hash.h:13
THash::GetHashKeyDat
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();}
TVec::Pack
void Pack()
Reduces vector capacity (frees memory) to match its size.
Definition: ds.h:1057
THash::KeyDatV
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())){
326  PortV.Gen(GetNextPrime(PortV.Len()+1));
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 }
TVec::Len
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:108
THash::THKeyDat
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:104
TVec::PutAll
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
TInt
Definition: dt.h:1134
THash::GetNextPrime
uint GetNextPrime(const uint &Val) const
Definition: hash.h:307
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
TVec::Gen
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();}
TInt::Save
void Save(TSOut &SOut) const
Definition: dt.h:1150
TBool::Save
void Save(TSOut &SOut) const
Definition: dt.h:992
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:109
TVec::Save
void Save(TSOut &SOut) const
Definition: ds.h:954
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:108
TSOut::SaveCs
void SaveCs()
Definition: fl.h:171
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:109
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
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  {
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:555
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:108
THash::KeyDatV
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
580  THashKeyDat<TKey, TDat> Tmp;
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 }
THash::IsKeyIdEqKeyN
bool IsKeyIdEqKeyN() const
Definition: hash.h:233
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:575
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
THash::Len
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); }
THash::Sort
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); }
THash::Sort
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);
549  ::Swap(FFreeKeyId, Hash.FFreeKeyId);
550  ::Swap(FreeKeys, Hash.FreeKeys);
551  }
552 }
THash::FreeKeys
TInt FreeKeys
Definition: hash.h:109
TVec::Swap
void Swap(TVec< TVal, TSizeTy > &Vec)
Swaps the contents of the vector with Vec.
Definition: ds.h:1101
THash::Swap
void Swap(THash &Hash)
Definition: hash.h:544
THash::AutoSizeP
TBool AutoSizeP
Definition: hash.h:108
THash::FFreeKeyId
TInt FFreeKeyId
Definition: hash.h:109
THash::PortV
TIntV PortV
Definition: hash.h:106
THash::KeyDatV
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: