TSparseHash< TKey, TDat, GroupSize > Class Template Reference

#include <shash.h>

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
TSparseHash &	operator= (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.

: Table(GetMinSize(0, WantedVals)) { ResetThresh(); }

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

TSparseHash< TKey, TDat, GroupSize >::TSparseHash ( TSIn &  SIn )

inline

Definition at line 495 of file shash.h.

: ShrinkThresh(SIn), ExpandThresh(SIn), Table(SIn) { }

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.

                                                                {
  ResizeDelta(1);
  int Pos, PosToIns;  FindPos(Key, Pos, PosToIns);
  if (PosToIns != -1) {
    return Table.Set(PosToIns, THashKeyDat(Key)).Dat;
  } else { return Table.Set(Pos).Dat; }
}

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.

                                                                                 {
  ResizeDelta(1);
  int Pos, PosToIns;  FindPos(Key, Pos, PosToIns);
  if (PosToIns != -1) {
    return Table.Set(PosToIns, THashKeyDat(Key, Dat)).Dat;
  } else { return Table.Set(Pos).Dat = Dat; }
}

template<class TKey , class TDat , uint16 GroupSize>

int TSparseHash< TKey, TDat, GroupSize >::AddKey

(

const TKey &

Key

)

Definition at line 676 of file shash.h.

                                                              {
  ResizeDelta(1);
  int Pos, PosToIns;  FindPos(Key, Pos, PosToIns);
  if (Pos != -1) { return Pos; } // key exists
  else {
    Table.Set(PosToIns, THashKeyDat(Key));
    return PosToIns;
  }
}

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

TIter TSparseHash< TKey, TDat, GroupSize >::BegI ( ) const

inline

Definition at line 504 of file shash.h.

{ return Table.BegI(); }

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.

{ Table.Clr(DoDel);  ResetThresh(); }

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.

                                                                                            {
  Clr(false);
  const int NewSize = GetMinSize(HT.Reserved(), MnWanted);
  if (NewSize > Reserved()) {
    Table.Resize(NewSize);
    ResetThresh();
  }
  const uint BuckM1 = Reserved() - 1;
  for (int g = 0; g < HT.Table.Groups(); g++) {
    const TSGroup& Group = HT.Table.GetGroup(g);
    for (int b = 0; b < Group.Len(); b++) {
      int Tries = 0; uint BuckNum;
      for (BuckNum = Group.Offset(b).Hash() & BuckM1;
       ! Table.IsEmpty(BuckNum); BuckNum = (BuckNum + Tries) & BuckM1) {
        Tries++;
        Assert(Tries < Reserved());
      }
      Table.Set(BuckNum, Group.Offset(b));
    }
  }
}

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

bool TSparseHash< TKey, TDat, GroupSize >::Empty ( ) const

inline

Definition at line 508 of file shash.h.

{ return Len() == 0; }

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

TIter TSparseHash< TKey, TDat, GroupSize >::EndI ( ) const

inline

Definition at line 505 of file shash.h.

{ return Table.EndI(); }

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.

                                                                                               {
  const uint BuckM1 = Reserved() - 1;
  uint BuckNum = Key.GetPrimHashCd() & BuckM1;
  int Tries = 0;
  while (true) {
    if (Table.IsEmpty(BuckNum)) {
      Pos = -1;  PosToIns = BuckNum;  return;
    }
    else if (Key == Table.Get(BuckNum).Key) {
      Pos = BuckNum;  PosToIns = -1;  return;
    }
    Tries++;
    BuckNum = (BuckNum + Tries) & BuckM1;
    Assert(Tries < Reserved());
  }
}

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.

                                                                            {
  int Pos, PosToIns;
  FindPos(Key, Pos, PosToIns);
  Assert(Pos != -1);
  return Table.Get(Pos).Dat;
}

template<class TKey , class TDat , uint16 GroupSize>

TDat & TSparseHash< TKey, TDat, GroupSize >::GetDat

(

const TKey &

Key

)

Definition at line 713 of file shash.h.

                                                                {
  int Pos, PosToIns;
  FindPos(Key, Pos, PosToIns);
  Assert(Pos != -1);
  return Table.Set(Pos).Dat;
}

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.

{ return Table.Get(KeyId).Dat; }

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.

{ return Table.Set(KeyId).Dat; }

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.

                                                                                               {
  DatKeyPrV.Gen(Len(), 0);
  for (TIter i = BegI(); i < EndI(); i++) {
    DatKeyPrV.Add(TPair<TDat, TKey>(i->Dat, i->Key));
  }
}

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.

                                                                       {
  DatV.Gen(Len(), 0);
  for (TIter i = BegI(); i < EndI(); i++) {
    DatV.Add(i->Dat);
  }
}

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

uint TSparseHash< TKey, TDat, GroupSize >::GetDiskSz ( ) const

inline

Definition at line 511 of file shash.h.

{ return 2*sizeof(TInt) + Table.GetDiskSz(); }

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.

{ Assert(IsKey(Key));  return Table.GetI(GetKeyId(Key)); }

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.

{ return Table.Get(KeyId).Key; }

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.

                                                                                               {
  Assert(IsKey(KeyId));
  const THashKeyDat& KeyDat = Table.Get(KeyId);
  Key = KeyDat.Key;
  Dat = KeyDat.Dat;
}

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.

                                                                                               {
  KeyDatPrV.Gen(Len(), 0);
  for (TIter i = BegI(); i < EndI(); i++) {
    KeyDatPrV.Add(TPair<TKey, TDat>(i->Key, i->Dat));
  }
}

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.

                                      {
    int Pos, PosToIns;  FindPos(Key, Pos, PosToIns);  return Pos; }

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.

                                                                       {
  KeyV.Gen(Len(), 0);
  for (TIter i = BegI(); i < EndI(); i++) {
    KeyV.Add(i->Key);
  }
}

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

::TSize TSparseHash< TKey, TDat, GroupSize >::GetMemUsed ( ) const

inline

Definition at line 502 of file shash.h.

{ return 2*sizeof(TInt)+Table.GetMemUsed(); }

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.

                                                                                                  {
  int Size = MinBuckets;
  while (Size*MxOccupancy < WantedVals || CurVals >= Size * MxOccupancy) Size *= 2;
  return Size;
}

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.

                                             { Assert(Len()>0);
    int KeyId = Rnd.GetUniDevInt(Reserved());
    while (! IsKeyId(KeyId)) { KeyId = Rnd.GetUniDevInt(Reserved()); } return KeyId; }

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.

{ return GetKeyId(Key) != -1; }

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.

                                                {
    KeyId = GetKeyId(Key);  return KeyId != -1; }

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.

                                                                                     {
  int KeyId;
  if (IsKey(Key, KeyId)) {
    Dat=Table.Get(KeyId).Dat;
    return true;
  } else { return false; }
}

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.

{ return ! Table.IsEmpty(KeyId); }

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

int TSparseHash< TKey, TDat, GroupSize >::Len ( ) const

inline

Definition at line 509 of file shash.h.

{ return Table.Len(); }

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.

{ ShrinkThresh.Load(SIn);  ExpandThresh.Load(SIn);  Table.Load(SIn); }

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.

                                                                                      {
  Clr(false);
  int NewSize;
  if (MnWanted == 0) NewSize = HT.Reserved();
  else NewSize = GetMinSize(HT.Reserved(), MnWanted);
  if (NewSize > Reserved()) {
    Table.Resize(NewSize);
    ResetThresh();
  }
  const uint BuckM1 = Reserved() - 1;
  for (int g = 0; g < HT.Table.Groups(); g++) {
    TSGroup& Group = HT.Table.GetGroup(g);
    for (int b = 0; b < Group.Len(); b++) {
      int Tries = 0; uint BuckNum;
      for (BuckNum = Group.Offset(b).Hash() & BuckM1;
       ! Table.IsEmpty(BuckNum); BuckNum = (BuckNum + Tries) & BuckM1) {
        Tries++;
        Assert(Tries < Reserved());
      }
      Assert(Table.IsEmpty(BuckNum));
      Table.Set(BuckNum, Group.Offset(b));
    }
    Group.Clr(true); // delete
  }
}

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.

                                                                                 {
  return Table < SHT.Table;
}

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.

                                                                                                          {
  if (this != &SHT) {
    ShrinkThresh = SHT.ShrinkThresh;
    ExpandThresh = SHT.ExpandThresh;
    Table = SHT.Table;
  }
  return *this;
}

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.

                                                                                  {
  return Table == SHT.Table;
}

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.

{ if (MxVals > Len()) ResizeDelta(MxVals - Len(), 0); }

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

int TSparseHash< TKey, TDat, GroupSize >::Reserved ( ) const

inline

Definition at line 510 of file shash.h.

{ return Table.Reserved(); }

template<class TKey , class TDat , uint16 GroupSize>

void TSparseHash< TKey, TDat, GroupSize >::ResetThresh ( )

private

Definition at line 555 of file shash.h.

                                                     {
  ExpandThresh = int(Table.Reserved() * MxOccupancy);
  ShrinkThresh = int(Table.Reserved() * MnOccupancy);
}

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.

                                                                                              {
  if (Reserved() > MnWanted && Len()+ValsToAdd < ExpandThresh) { return; }
  const int NewSize = GetMinSize(Table.Len()+ValsToAdd, MnWanted);
  if (NewSize > Reserved()) {
    printf("***Resize SparseHash:%d->%d\n", Reserved(), NewSize);
    TSparseHash TmpHt(ValsToAdd+Len());
    TmpHt.ResetThresh();
    TmpHt.MoveFrom(*this, Len());
    Swap(TmpHt);
  }
}

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.

{ ShrinkThresh.Save(SOut); ExpandThresh.Save(SOut); Table.Save(SOut); }

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.

                                                             {
  ::Swap(ShrinkThresh, HT.ShrinkThresh);
  ::Swap(ExpandThresh, HT.ExpandThresh);
  Table.Swap(HT.Table);
}

Member Data Documentation

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

TInt TSparseHash< TKey, TDat, GroupSize >::ExpandThresh

private

Definition at line 491 of file shash.h.

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

Definition at line 491 of file shash.h.

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

TSparseTable<THashKeyDat, GroupSize> TSparseHash< TKey, TDat, GroupSize >::Table

private

Definition at line 492 of file shash.h.

---

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

• glib-core/shash.h