SNAP Library 4.0, Developer Reference  2017-07-27 13:18:06
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
TSparseHash< TKey, TDat, GroupSize > Class Template Reference

#include <shash.h>

Collaboration diagram for TSparseHash< TKey, TDat, GroupSize >:

Public Types

typedef TSHashKeyDat< TKey, TDat > THashKeyDat
 
typedef TSparseTable
< THashKeyDat, GroupSize >
::TIter 
TIter
 
typedef TSparseTable
< THashKeyDat, GroupSize >
::TSGroup 
TSGroup
 

Public Member Functions

 TSparseHash (const int &WantedVals=0)
 
 TSparseHash (TSIn &SIn)
 
void Load (TSIn &SIn)
 
void Save (TSOut &SOut) const
 
TSparseHashoperator= (const TSparseHash &SHT)
 
bool operator== (const TSparseHash &SHT) const
 
bool operator< (const TSparseHash &SHT) const
 
::TSize GetMemUsed () const
 
TIter BegI () const
 
TIter EndI () const
 
TIter GetI (const TKey &Key) const
 
bool Empty () const
 
int Len () const
 
int Reserved () const
 
uint GetDiskSz () const
 
void Reserve (const int &MxVals)
 
void Clr (const bool &DoDel=true)
 
void Swap (TSparseHash &HT)
 
int AddKey (const TKey &Key)
 
TDat & AddDat (const TKey &Key)
 
TDat & AddDat (const TKey &Key, const TDat &Dat)
 
const TKey & GetKey (const int &KeyId) const
 
int GetKeyId (const TKey &Key) const
 
bool IsKey (const TKey &Key) const
 
bool IsKey (const TKey &Key, int &KeyId) const
 
bool IsKeyId (const int &KeyId) const
 
int GetRndKeyId (TRnd &Rnd=TInt::Rnd) const
 
const TDat & GetDat (const TKey &Key) const
 
TDat & GetDat (const TKey &Key)
 
const TDat & GetDatKeyId (const int &KeyId) const
 
TDat & GetDatKeyId (const int &KeyId)
 
void GetKeyDat (const int &KeyId, TKey &Key, TDat &Dat) const
 
bool IsKeyGetDat (const TKey &Key, TDat &Dat) 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
 

Static Public Attributes

static const float MxOccupancy = 0.8f
 
static const float MnOccupancy = 0.4f * 0.8f
 
static const int MinBuckets = 32
 

Private Member Functions

void ResetThresh ()
 
int GetMinSize (const int &CurVals, const int &WantedVals) const
 
void CopyFrom (const TSparseHash &HT, const int &MnWanted)
 
void MoveFrom (TSparseHash &HT, const int &MnWanted)
 
void ResizeDelta (const int &ValsToAdd, const int &MnWanted=0)
 
void FindPos (const TKey &Key, int &Pos, int &PosToIns) const
 

Private Attributes

TInt ShrinkThresh
 
TInt ExpandThresh
 
TSparseTable< THashKeyDat,
GroupSize > 
Table
 

Detailed Description

template<class TKey, class TDat, uint16 GroupSize = 48>
class TSparseHash< TKey, TDat, GroupSize >

Definition at line 474 of file shash.h.

Member Typedef Documentation

template<class TKey , class TDat , uint16 GroupSize = 48>
typedef TSHashKeyDat<TKey, TDat> TSparseHash< TKey, TDat, GroupSize >::THashKeyDat

Definition at line 476 of file shash.h.

template<class TKey , class TDat , uint16 GroupSize = 48>
typedef TSparseTable<THashKeyDat, GroupSize>::TIter TSparseHash< TKey, TDat, GroupSize >::TIter

Definition at line 477 of file shash.h.

template<class TKey , class TDat , uint16 GroupSize = 48>
typedef TSparseTable<THashKeyDat, GroupSize>::TSGroup TSparseHash< TKey, TDat, GroupSize >::TSGroup

Definition at line 478 of file shash.h.

Constructor & Destructor Documentation

template<class TKey , class TDat , uint16 GroupSize = 48>
TSparseHash< TKey, TDat, GroupSize >::TSparseHash ( const int &  WantedVals = 0)
inline

Definition at line 494 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::ResetThresh().

494 : Table(GetMinSize(0, WantedVals)) { ResetThresh(); }
int GetMinSize(const int &CurVals, const int &WantedVals) const
Definition: shash.h:561
void ResetThresh()
Definition: shash.h:555
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492

Here is the call graph for this function:

template<class TKey , class TDat , uint16 GroupSize = 48>
TSparseHash< TKey, TDat, GroupSize >::TSparseHash ( TSIn SIn)
inline

Definition at line 495 of file shash.h.

495 : ShrinkThresh(SIn), ExpandThresh(SIn), Table(SIn) { }
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
TInt ExpandThresh
Definition: shash.h:491
TInt ShrinkThresh
Definition: shash.h:491

Member Function Documentation

template<class TKey , class TDat , uint16 GroupSize>
TDat & TSparseHash< TKey, TDat, GroupSize >::AddDat ( const TKey &  Key)

Definition at line 687 of file shash.h.

Referenced by TBigNet< TNodeData, IsDir >::GetSubGraph().

687  {
688  ResizeDelta(1);
689  int Pos, PosToIns; FindPos(Key, Pos, PosToIns);
690  if (PosToIns != -1) {
691  return Table.Set(PosToIns, THashKeyDat(Key)).Dat;
692  } else { return Table.Set(Pos).Dat; }
693 }
void FindPos(const TKey &Key, int &Pos, int &PosToIns) const
Definition: shash.h:631
void ResizeDelta(const int &ValsToAdd, const int &MnWanted=0)
Definition: shash.h:618
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
TSHashKeyDat< TKey, TDat > THashKeyDat
Definition: shash.h:476

Here is the caller graph for this function:

template<class TKey , class TDat , uint16 GroupSize>
TDat & TSparseHash< TKey, TDat, GroupSize >::AddDat ( const TKey &  Key,
const TDat &  Dat 
)

Definition at line 696 of file shash.h.

696  {
697  ResizeDelta(1);
698  int Pos, PosToIns; FindPos(Key, Pos, PosToIns);
699  if (PosToIns != -1) {
700  return Table.Set(PosToIns, THashKeyDat(Key, Dat)).Dat;
701  } else { return Table.Set(Pos).Dat = Dat; }
702 }
void FindPos(const TKey &Key, int &Pos, int &PosToIns) const
Definition: shash.h:631
void ResizeDelta(const int &ValsToAdd, const int &MnWanted=0)
Definition: shash.h:618
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
TSHashKeyDat< TKey, TDat > THashKeyDat
Definition: shash.h:476
template<class TKey , class TDat , uint16 GroupSize>
int TSparseHash< TKey, TDat, GroupSize >::AddKey ( const TKey &  Key)

Definition at line 676 of file shash.h.

676  {
677  ResizeDelta(1);
678  int Pos, PosToIns; FindPos(Key, Pos, PosToIns);
679  if (Pos != -1) { return Pos; } // key exists
680  else {
681  Table.Set(PosToIns, THashKeyDat(Key));
682  return PosToIns;
683  }
684 }
void FindPos(const TKey &Key, int &Pos, int &PosToIns) const
Definition: shash.h:631
void ResizeDelta(const int &ValsToAdd, const int &MnWanted=0)
Definition: shash.h:618
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
TSHashKeyDat< TKey, TDat > THashKeyDat
Definition: shash.h:476
template<class TKey , class TDat , uint16 GroupSize = 48>
TIter TSparseHash< TKey, TDat, GroupSize >::BegI ( ) const
inline

Definition at line 504 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::Table.

504 { return Table.BegI(); }
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
template<class TKey , class TDat , uint16 GroupSize = 48>
void TSparseHash< TKey, TDat, GroupSize >::Clr ( const bool &  DoDel = true)
inline

Definition at line 514 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::ResetThresh(), and TSparseHash< TKey, TDat, GroupSize >::Table.

514 { Table.Clr(DoDel); ResetThresh(); }
void ResetThresh()
Definition: shash.h:555
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492

Here is the call graph for this function:

template<class TKey , class TDat , uint16 GroupSize>
void TSparseHash< TKey, TDat, GroupSize >::CopyFrom ( const TSparseHash< TKey, TDat, GroupSize > &  HT,
const int &  MnWanted 
)
private

Definition at line 568 of file shash.h.

References Assert, TSparseGroup< TVal, GroupSize >::Len(), TSparseGroup< TVal, GroupSize >::Offset(), TSparseHash< TKey, TDat, GroupSize >::Reserved(), and TSparseHash< TKey, TDat, GroupSize >::Table.

568  {
569  Clr(false);
570  const int NewSize = GetMinSize(HT.Reserved(), MnWanted);
571  if (NewSize > Reserved()) {
572  Table.Resize(NewSize);
573  ResetThresh();
574  }
575  const uint BuckM1 = Reserved() - 1;
576  for (int g = 0; g < HT.Table.Groups(); g++) {
577  const TSGroup& Group = HT.Table.GetGroup(g);
578  for (int b = 0; b < Group.Len(); b++) {
579  int Tries = 0; uint BuckNum;
580  for (BuckNum = Group.Offset(b).Hash() & BuckM1;
581  ! Table.IsEmpty(BuckNum); BuckNum = (BuckNum + Tries) & BuckM1) {
582  Tries++;
583  Assert(Tries < Reserved());
584  }
585  Table.Set(BuckNum, Group.Offset(b));
586  }
587  }
588 }
int GetMinSize(const int &CurVals, const int &WantedVals) const
Definition: shash.h:561
int Reserved() const
Definition: shash.h:510
void ResetThresh()
Definition: shash.h:555
unsigned int uint
Definition: bd.h:11
void Clr(const bool &DoDel=true)
Definition: shash.h:514
TSparseTable< THashKeyDat, GroupSize >::TSGroup TSGroup
Definition: shash.h:478
#define Assert(Cond)
Definition: bd.h:251
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492

Here is the call graph for this function:

template<class TKey , class TDat , uint16 GroupSize = 48>
bool TSparseHash< TKey, TDat, GroupSize >::Empty ( ) const
inline

Definition at line 508 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::Len().

508 { return Len() == 0; }
int Len() const
Definition: shash.h:509

Here is the call graph for this function:

template<class TKey , class TDat , uint16 GroupSize = 48>
TIter TSparseHash< TKey, TDat, GroupSize >::EndI ( ) const
inline

Definition at line 505 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::Table.

505 { return Table.EndI(); }
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
template<class TKey , class TDat , uint16 GroupSize>
void TSparseHash< TKey, TDat, GroupSize >::FindPos ( const TKey &  Key,
int &  Pos,
int &  PosToIns 
) const
private

Definition at line 631 of file shash.h.

References Assert.

Referenced by TSparseHash< TKey, TDat, GroupSize >::GetKeyId().

631  {
632  const uint BuckM1 = Reserved() - 1;
633  uint BuckNum = Key.GetPrimHashCd() & BuckM1;
634  int Tries = 0;
635  while (true) {
636  if (Table.IsEmpty(BuckNum)) {
637  Pos = -1; PosToIns = BuckNum; return;
638  }
639  else if (Key == Table.Get(BuckNum).Key) {
640  Pos = BuckNum; PosToIns = -1; return;
641  }
642  Tries++;
643  BuckNum = (BuckNum + Tries) & BuckM1;
644  Assert(Tries < Reserved());
645  }
646 }
int Reserved() const
Definition: shash.h:510
unsigned int uint
Definition: bd.h:11
#define Assert(Cond)
Definition: bd.h:251
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492

Here is the caller graph for this function:

template<class TKey , class TDat , uint16 GroupSize>
const TDat & TSparseHash< TKey, TDat, GroupSize >::GetDat ( const TKey &  Key) const

Definition at line 705 of file shash.h.

References Assert.

705  {
706  int Pos, PosToIns;
707  FindPos(Key, Pos, PosToIns);
708  Assert(Pos != -1);
709  return Table.Get(Pos).Dat;
710 }
void FindPos(const TKey &Key, int &Pos, int &PosToIns) const
Definition: shash.h:631
#define Assert(Cond)
Definition: bd.h:251
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
template<class TKey , class TDat , uint16 GroupSize>
TDat & TSparseHash< TKey, TDat, GroupSize >::GetDat ( const TKey &  Key)

Definition at line 713 of file shash.h.

References Assert.

713  {
714  int Pos, PosToIns;
715  FindPos(Key, Pos, PosToIns);
716  Assert(Pos != -1);
717  return Table.Set(Pos).Dat;
718 }
void FindPos(const TKey &Key, int &Pos, int &PosToIns) const
Definition: shash.h:631
#define Assert(Cond)
Definition: bd.h:251
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
template<class TKey , class TDat , uint16 GroupSize = 48>
const TDat& TSparseHash< TKey, TDat, GroupSize >::GetDatKeyId ( const int &  KeyId) const
inline

Definition at line 534 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::Table.

534 { return Table.Get(KeyId).Dat; }
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
template<class TKey , class TDat , uint16 GroupSize = 48>
TDat& TSparseHash< TKey, TDat, GroupSize >::GetDatKeyId ( const int &  KeyId)
inline

Definition at line 535 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::Table.

535 { return Table.Set(KeyId).Dat; }
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
template<class TKey , class TDat , uint16 GroupSize>
void TSparseHash< TKey, TDat, GroupSize >::GetDatKeyPrV ( TVec< TPair< TDat, TKey > > &  DatKeyPrV) const

Definition at line 762 of file shash.h.

762  {
763  DatKeyPrV.Gen(Len(), 0);
764  for (TIter i = BegI(); i < EndI(); i++) {
765  DatKeyPrV.Add(TPair<TDat, TKey>(i->Dat, i->Key));
766  }
767 }
int Len() const
Definition: shash.h:509
TIter EndI() const
Definition: shash.h:505
TSparseTable< THashKeyDat, GroupSize >::TIter TIter
Definition: shash.h:477
Definition: ds.h:32
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TIter BegI() const
Definition: shash.h:504
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 , uint16 GroupSize>
void TSparseHash< TKey, TDat, GroupSize >::GetDatV ( TVec< TDat > &  DatV) const

Definition at line 746 of file shash.h.

References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Gen().

746  {
747  DatV.Gen(Len(), 0);
748  for (TIter i = BegI(); i < EndI(); i++) {
749  DatV.Add(i->Dat);
750  }
751 }
int Len() const
Definition: shash.h:509
TIter EndI() const
Definition: shash.h:505
TSparseTable< THashKeyDat, GroupSize >::TIter TIter
Definition: shash.h:477
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TIter BegI() const
Definition: shash.h:504
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

template<class TKey , class TDat , uint16 GroupSize = 48>
uint TSparseHash< TKey, TDat, GroupSize >::GetDiskSz ( ) const
inline

Definition at line 511 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::Table.

511 { return 2*sizeof(TInt) + Table.GetDiskSz(); }
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
Definition: dt.h:1134
template<class TKey , class TDat , uint16 GroupSize = 48>
TIter TSparseHash< TKey, TDat, GroupSize >::GetI ( const TKey &  Key) const
inline

Definition at line 506 of file shash.h.

References Assert, TSparseHash< TKey, TDat, GroupSize >::GetKeyId(), TSparseHash< TKey, TDat, GroupSize >::IsKey(), and TSparseHash< TKey, TDat, GroupSize >::Table.

506 { Assert(IsKey(Key)); return Table.GetI(GetKeyId(Key)); }
int GetKeyId(const TKey &Key) const
Definition: shash.h:522
#define Assert(Cond)
Definition: bd.h:251
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
bool IsKey(const TKey &Key) const
Definition: shash.h:524

Here is the call graph for this function:

template<class TKey , class TDat , uint16 GroupSize = 48>
const TKey& TSparseHash< TKey, TDat, GroupSize >::GetKey ( const int &  KeyId) const
inline

Definition at line 521 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::Table.

521 { return Table.Get(KeyId).Key; }
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
template<class TKey , class TDat , uint16 GroupSize>
void TSparseHash< TKey, TDat, GroupSize >::GetKeyDat ( const int &  KeyId,
TKey &  Key,
TDat &  Dat 
) const

Definition at line 721 of file shash.h.

References Assert, TSHashKeyDat< TKey, TDat >::Dat, and TSHashKeyDat< TKey, TDat >::Key.

721  {
722  Assert(IsKey(KeyId));
723  const THashKeyDat& KeyDat = Table.Get(KeyId);
724  Key = KeyDat.Key;
725  Dat = KeyDat.Dat;
726 }
TDat Dat
Definition: hash.h:13
#define Assert(Cond)
Definition: bd.h:251
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
TKey Key
Definition: hash.h:12
bool IsKey(const TKey &Key) const
Definition: shash.h:524
template<class TKey , class TDat , uint16 GroupSize>
void TSparseHash< TKey, TDat, GroupSize >::GetKeyDatPrV ( TVec< TPair< TKey, TDat > > &  KeyDatPrV) const

Definition at line 754 of file shash.h.

754  {
755  KeyDatPrV.Gen(Len(), 0);
756  for (TIter i = BegI(); i < EndI(); i++) {
757  KeyDatPrV.Add(TPair<TKey, TDat>(i->Key, i->Dat));
758  }
759 }
int Len() const
Definition: shash.h:509
TIter EndI() const
Definition: shash.h:505
TSparseTable< THashKeyDat, GroupSize >::TIter TIter
Definition: shash.h:477
Definition: ds.h:32
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TIter BegI() const
Definition: shash.h:504
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 , uint16 GroupSize = 48>
int TSparseHash< TKey, TDat, GroupSize >::GetKeyId ( const TKey &  Key) const
inline

Definition at line 522 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::FindPos().

Referenced by TSparseHash< TKey, TDat, GroupSize >::GetI(), and TSparseHash< TKey, TDat, GroupSize >::IsKey().

522  {
523  int Pos, PosToIns; FindPos(Key, Pos, PosToIns); return Pos; }
void FindPos(const TKey &Key, int &Pos, int &PosToIns) const
Definition: shash.h:631

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TKey , class TDat , uint16 GroupSize>
void TSparseHash< TKey, TDat, GroupSize >::GetKeyV ( TVec< TKey > &  KeyV) const

Definition at line 738 of file shash.h.

References TVec< TVal, TSizeTy >::Add(), and TVec< TVal, TSizeTy >::Gen().

738  {
739  KeyV.Gen(Len(), 0);
740  for (TIter i = BegI(); i < EndI(); i++) {
741  KeyV.Add(i->Key);
742  }
743 }
int Len() const
Definition: shash.h:509
TIter EndI() const
Definition: shash.h:505
TSparseTable< THashKeyDat, GroupSize >::TIter TIter
Definition: shash.h:477
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TIter BegI() const
Definition: shash.h:504
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602

Here is the call graph for this function:

template<class TKey , class TDat , uint16 GroupSize = 48>
::TSize TSparseHash< TKey, TDat, GroupSize >::GetMemUsed ( ) const
inline

Definition at line 502 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::Table.

502 { return 2*sizeof(TInt)+Table.GetMemUsed(); }
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
Definition: dt.h:1134
template<class TKey , class TDat , uint16 GroupSize>
int TSparseHash< TKey, TDat, GroupSize >::GetMinSize ( const int &  CurVals,
const int &  WantedVals 
) const
private

Definition at line 561 of file shash.h.

561  {
562  int Size = MinBuckets;
563  while (Size*MxOccupancy < WantedVals || CurVals >= Size * MxOccupancy) Size *= 2;
564  return Size;
565 }
static const int MinBuckets
Definition: shash.h:482
static const float MxOccupancy
Definition: shash.h:480
template<class TKey , class TDat , uint16 GroupSize = 48>
int TSparseHash< TKey, TDat, GroupSize >::GetRndKeyId ( TRnd Rnd = TInt::Rnd) const
inline

Definition at line 528 of file shash.h.

References Assert, TSparseHash< TKey, TDat, GroupSize >::IsKeyId(), TSparseHash< TKey, TDat, GroupSize >::Len(), and TSparseHash< TKey, TDat, GroupSize >::Reserved().

528  { Assert(Len()>0);
529  int KeyId = Rnd.GetUniDevInt(Reserved());
530  while (! IsKeyId(KeyId)) { KeyId = Rnd.GetUniDevInt(Reserved()); } return KeyId; }
bool IsKeyId(const int &KeyId) const
Definition: shash.h:527
int Len() const
Definition: shash.h:509
int Reserved() const
Definition: shash.h:510
#define Assert(Cond)
Definition: bd.h:251
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39

Here is the call graph for this function:

template<class TKey , class TDat , uint16 GroupSize = 48>
bool TSparseHash< TKey, TDat, GroupSize >::IsKey ( const TKey &  Key) const
inline

Definition at line 524 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::GetKeyId().

Referenced by TSparseHash< TKey, TDat, GroupSize >::GetI().

524 { return GetKeyId(Key) != -1; }
int GetKeyId(const TKey &Key) const
Definition: shash.h:522

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TKey , class TDat , uint16 GroupSize = 48>
bool TSparseHash< TKey, TDat, GroupSize >::IsKey ( const TKey &  Key,
int &  KeyId 
) const
inline

Definition at line 525 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::GetKeyId().

525  {
526  KeyId = GetKeyId(Key); return KeyId != -1; }
int GetKeyId(const TKey &Key) const
Definition: shash.h:522

Here is the call graph for this function:

template<class TKey , class TDat , uint16 GroupSize>
bool TSparseHash< TKey, TDat, GroupSize >::IsKeyGetDat ( const TKey &  Key,
TDat &  Dat 
) const

Definition at line 729 of file shash.h.

729  {
730  int KeyId;
731  if (IsKey(Key, KeyId)) {
732  Dat=Table.Get(KeyId).Dat;
733  return true;
734  } else { return false; }
735 }
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
bool IsKey(const TKey &Key) const
Definition: shash.h:524
template<class TKey , class TDat , uint16 GroupSize = 48>
bool TSparseHash< TKey, TDat, GroupSize >::IsKeyId ( const int &  KeyId) const
inline

Definition at line 527 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::Table.

Referenced by TSparseHash< TKey, TDat, GroupSize >::GetRndKeyId().

527 { return ! Table.IsEmpty(KeyId); }
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492

Here is the caller graph for this function:

template<class TKey , class TDat , uint16 GroupSize = 48>
int TSparseHash< TKey, TDat, GroupSize >::Len ( ) const
inline

Definition at line 509 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::Table.

Referenced by TSparseHash< TKey, TDat, GroupSize >::Empty(), TSparseHash< TKey, TDat, GroupSize >::GetRndKeyId(), and TSparseHash< TKey, TDat, GroupSize >::Reserve().

509 { return Table.Len(); }
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492

Here is the caller graph for this function:

template<class TKey , class TDat , uint16 GroupSize = 48>
void TSparseHash< TKey, TDat, GroupSize >::Load ( TSIn SIn)
inline

Definition at line 496 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::ExpandThresh, TInt::Load(), TSparseHash< TKey, TDat, GroupSize >::ShrinkThresh, and TSparseHash< TKey, TDat, GroupSize >::Table.

496 { ShrinkThresh.Load(SIn); ExpandThresh.Load(SIn); Table.Load(SIn); }
void Load(TSIn &SIn)
Definition: dt.h:1149
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
TInt ExpandThresh
Definition: shash.h:491
TInt ShrinkThresh
Definition: shash.h:491

Here is the call graph for this function:

template<class TKey , class TDat , uint16 GroupSize>
void TSparseHash< TKey, TDat, GroupSize >::MoveFrom ( TSparseHash< TKey, TDat, GroupSize > &  HT,
const int &  MnWanted 
)
private

Definition at line 591 of file shash.h.

References Assert, TSparseGroup< TVal, GroupSize >::Clr(), TSparseGroup< TVal, GroupSize >::Len(), TSparseGroup< TVal, GroupSize >::Offset(), TSparseHash< TKey, TDat, GroupSize >::Reserved(), and TSparseHash< TKey, TDat, GroupSize >::Table.

Referenced by TSparseHash< TKey, TDat, GroupSize >::ResizeDelta().

591  {
592  Clr(false);
593  int NewSize;
594  if (MnWanted == 0) NewSize = HT.Reserved();
595  else NewSize = GetMinSize(HT.Reserved(), MnWanted);
596  if (NewSize > Reserved()) {
597  Table.Resize(NewSize);
598  ResetThresh();
599  }
600  const uint BuckM1 = Reserved() - 1;
601  for (int g = 0; g < HT.Table.Groups(); g++) {
602  TSGroup& Group = HT.Table.GetGroup(g);
603  for (int b = 0; b < Group.Len(); b++) {
604  int Tries = 0; uint BuckNum;
605  for (BuckNum = Group.Offset(b).Hash() & BuckM1;
606  ! Table.IsEmpty(BuckNum); BuckNum = (BuckNum + Tries) & BuckM1) {
607  Tries++;
608  Assert(Tries < Reserved());
609  }
610  Assert(Table.IsEmpty(BuckNum));
611  Table.Set(BuckNum, Group.Offset(b));
612  }
613  Group.Clr(true); // delete
614  }
615 }
int GetMinSize(const int &CurVals, const int &WantedVals) const
Definition: shash.h:561
int Reserved() const
Definition: shash.h:510
void ResetThresh()
Definition: shash.h:555
unsigned int uint
Definition: bd.h:11
void Clr(const bool &DoDel=true)
Definition: shash.h:514
TSparseTable< THashKeyDat, GroupSize >::TSGroup TSGroup
Definition: shash.h:478
#define Assert(Cond)
Definition: bd.h:251
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TKey , class TDat , uint16 GroupSize>
bool TSparseHash< TKey, TDat, GroupSize >::operator< ( const TSparseHash< TKey, TDat, GroupSize > &  SHT) const

Definition at line 664 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::Table.

664  {
665  return Table < SHT.Table;
666 }
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
template<class TKey , class TDat , uint16 GroupSize>
TSparseHash< TKey, TDat, GroupSize > & TSparseHash< TKey, TDat, GroupSize >::operator= ( const TSparseHash< TKey, TDat, GroupSize > &  SHT)

Definition at line 649 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::ExpandThresh, TSparseHash< TKey, TDat, GroupSize >::ShrinkThresh, and TSparseHash< TKey, TDat, GroupSize >::Table.

649  {
650  if (this != &SHT) {
653  Table = SHT.Table;
654  }
655  return *this;
656 }
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
TInt ExpandThresh
Definition: shash.h:491
TInt ShrinkThresh
Definition: shash.h:491
template<class TKey , class TDat , uint16 GroupSize>
bool TSparseHash< TKey, TDat, GroupSize >::operator== ( const TSparseHash< TKey, TDat, GroupSize > &  SHT) const

Definition at line 659 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::Table.

659  {
660  return Table == SHT.Table;
661 }
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
template<class TKey , class TDat , uint16 GroupSize = 48>
void TSparseHash< TKey, TDat, GroupSize >::Reserve ( const int &  MxVals)
inline

Definition at line 513 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::Len(), and TSparseHash< TKey, TDat, GroupSize >::ResizeDelta().

513 { if (MxVals > Len()) ResizeDelta(MxVals - Len(), 0); }
int Len() const
Definition: shash.h:509
void ResizeDelta(const int &ValsToAdd, const int &MnWanted=0)
Definition: shash.h:618

Here is the call graph for this function:

template<class TKey , class TDat , uint16 GroupSize = 48>
int TSparseHash< TKey, TDat, GroupSize >::Reserved ( ) const
inline

Definition at line 510 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::Table.

Referenced by TSparseHash< TKey, TDat, GroupSize >::CopyFrom(), TSparseHash< TKey, TDat, GroupSize >::GetRndKeyId(), and TSparseHash< TKey, TDat, GroupSize >::MoveFrom().

510 { return Table.Reserved(); }
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492

Here is the caller graph for this function:

template<class TKey , class TDat , uint16 GroupSize>
void TSparseHash< TKey, TDat, GroupSize >::ResetThresh ( )
private

Definition at line 555 of file shash.h.

Referenced by TSparseHash< TKey, TDat, GroupSize >::Clr(), TSparseHash< TKey, TDat, GroupSize >::ResizeDelta(), and TSparseHash< TKey, TDat, GroupSize >::TSparseHash().

555  {
556  ExpandThresh = int(Table.Reserved() * MxOccupancy);
557  ShrinkThresh = int(Table.Reserved() * MnOccupancy);
558 }
static const float MnOccupancy
Definition: shash.h:481
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
TInt ExpandThresh
Definition: shash.h:491
static const float MxOccupancy
Definition: shash.h:480
TInt ShrinkThresh
Definition: shash.h:491

Here is the caller graph for this function:

template<class TKey , class TDat , uint16 GroupSize>
void TSparseHash< TKey, TDat, GroupSize >::ResizeDelta ( const int &  ValsToAdd,
const int &  MnWanted = 0 
)
private

Definition at line 618 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::MoveFrom(), TSparseHash< TKey, TDat, GroupSize >::ResetThresh(), and Swap().

Referenced by TSparseHash< TKey, TDat, GroupSize >::Reserve().

618  {
619  if (Reserved() > MnWanted && Len()+ValsToAdd < ExpandThresh) { return; }
620  const int NewSize = GetMinSize(Table.Len()+ValsToAdd, MnWanted);
621  if (NewSize > Reserved()) {
622  printf("***Resize SparseHash:%d->%d\n", Reserved(), NewSize);
623  TSparseHash TmpHt(ValsToAdd+Len());
624  TmpHt.ResetThresh();
625  TmpHt.MoveFrom(*this, Len());
626  Swap(TmpHt);
627  }
628 }
int GetMinSize(const int &CurVals, const int &WantedVals) const
Definition: shash.h:561
int Len() const
Definition: shash.h:509
int Reserved() const
Definition: shash.h:510
void Swap(TSparseHash &HT)
Definition: shash.h:669
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
TInt ExpandThresh
Definition: shash.h:491

Here is the call graph for this function:

Here is the caller graph for this function:

template<class TKey , class TDat , uint16 GroupSize = 48>
void TSparseHash< TKey, TDat, GroupSize >::Save ( TSOut SOut) const
inline

Definition at line 497 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::ExpandThresh, TInt::Save(), TSparseHash< TKey, TDat, GroupSize >::ShrinkThresh, and TSparseHash< TKey, TDat, GroupSize >::Table.

497 { ShrinkThresh.Save(SOut); ExpandThresh.Save(SOut); Table.Save(SOut); }
void Save(TSOut &SOut) const
Definition: dt.h:1150
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
TInt ExpandThresh
Definition: shash.h:491
TInt ShrinkThresh
Definition: shash.h:491

Here is the call graph for this function:

template<class TKey , class TDat , uint16 GroupSize>
void TSparseHash< TKey, TDat, GroupSize >::Swap ( TSparseHash< TKey, TDat, GroupSize > &  HT)

Definition at line 669 of file shash.h.

References TSparseHash< TKey, TDat, GroupSize >::ExpandThresh, TSparseHash< TKey, TDat, GroupSize >::ShrinkThresh, Swap(), and TSparseHash< TKey, TDat, GroupSize >::Table.

669  {
672  Table.Swap(HT.Table);
673 }
void Swap(TSparseHash &HT)
Definition: shash.h:669
TSparseTable< THashKeyDat, GroupSize > Table
Definition: shash.h:492
TInt ExpandThresh
Definition: shash.h:491
TInt ShrinkThresh
Definition: shash.h:491

Here is the call graph for this function:

Member Data Documentation

template<class TKey , class TDat , uint16 GroupSize = 48>
TInt TSparseHash< TKey, TDat, GroupSize >::ExpandThresh
private
template<class TKey , class TDat , uint16 GroupSize = 48>
const int TSparseHash< TKey, TDat, GroupSize >::MinBuckets = 32
static

Definition at line 482 of file shash.h.

template<class TKey , class TDat , uint16 GroupSize = 48>
const float TSparseHash< TKey, TDat, GroupSize >::MnOccupancy = 0.4f * 0.8f
static

Definition at line 481 of file shash.h.

template<class TKey , class TDat , uint16 GroupSize = 48>
const float TSparseHash< TKey, TDat, GroupSize >::MxOccupancy = 0.8f
static

Definition at line 480 of file shash.h.

template<class TKey , class TDat , uint16 GroupSize = 48>
TInt TSparseHash< TKey, TDat, GroupSize >::ShrinkThresh
private

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