THashMP< TKey, TDat, THashFunc > Class Template Reference

Hash-Table with multiprocessing support. More...

#include <hashmp.h>

Collaboration diagram for THashMP< TKey, TDat, THashFunc >:

Classes
class	THashMPKeyDatCmp

Public Types
enum	{ HashPrimes =32 }
typedef THashMPKeyDatI< TKey, TDat >	TIter

Public Member Functions
	THashMP ()
	THashMP (const THashMP &PHash)
	THashMP (const int &ExpectVals)
	THashMP (TSIn &SIn)
void	Load (TSIn &SIn)
void	Save (TSOut &SOut) const
THashMP &	operator= (const THashMP &Hash)
bool	operator== (const THashMP &Hash) const
const TDat &	operator[] (const int &KeyId) const
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)
bool	Empty () const
int	Len () const
void	SetLen (const int &Length)
int	GetMxKeyIds () const
int	GetReservedKeyIds () const
int	AddKey (const TKey &Key)
int	AddKey11 (const int &Idx, const TKey &Key, bool &Found)
int	AddKey12 (const int &Idx, const TKey &Key, bool &Found)
int	AddKey13 (const int &Idx, const TKey &Key)
int	AddKey1 (const TKey &Key, bool &Found)
int	AddKey2 (const int &Idx, const TKey &Key, bool &Found)
TDat &	AddDatId (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
int	GetRndKeyId (TRnd &Rnd) const
	Get an index of a random element. If the hash table has many deleted keys, this may take a long time. More...
int	GetRndKeyId (TRnd &Rnd, const double &EmptyFrac)
	Get an index of a random element. If the hash table has many deleted keys, defrag the hash table first (that's why the function is non-const). More...
bool	IsKey (const TKey &Key) const
bool	IsKey (const TKey &Key, int &KeyId) const
bool	IsKeyId (const int &KeyId) const
const TDat &	GetDat (const TKey &Key) const
TDat &	GetDat (const TKey &Key)
void	GetKeyDat (const int &KeyId, TKey &Key, TDat &Dat) const
bool	IsKeyGetDat (const TKey &Key, TDat &Dat) const
int	FFirstKeyId () const
bool	FNextKeyId (int &KeyId) const
void	GetKeyV (TVec< TKey > &KeyV) const
void	GetDatV (TVec< TDat > &DatV) const
void	GetKeyDatPrV (TVec< TPair< TKey, TDat > > &KeyDatPrV) const
void	GetDatKeyPrV (TVec< TPair< TDat, TKey > > &DatKeyPrV) const
void	GetKeyDatKdV (TVec< TKeyDat< TKey, TDat > > &KeyDatKdV) const
void	GetDatKeyKdV (TVec< TKeyDat< TDat, TKey > > &DatKeyKdV) const
void	Swap (THashMP &Hash)
void	Pack ()

Static Public Attributes
static const unsigned int	HashPrimeT [HashPrimes]

Private Types
typedef THashMPKeyDat< TKey, TDat >	TPHKeyDat
typedef TPair< TKey, TDat >	TKeyDatP

Private Member Functions
TPHKeyDat &	GetPHashKeyDat (const int &KeyId)
const TPHKeyDat &	GetPHashKeyDat (const int &KeyId) const
uint	GetNextPrime (const uint &Val) const

Private Attributes
TVec< TPHKeyDat >	Table
TInt	NumVals

Detailed Description

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

Hash-Table with multiprocessing support.

Definition at line 81 of file hashmp.h.

Member Typedef Documentation

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

typedef THashMPKeyDatI<TKey, TDat> THashMP< TKey, TDat, THashFunc >::TIter

Definition at line 86 of file hashmp.h.

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

typedef TPair<TKey, TDat> THashMP< TKey, TDat, THashFunc >::TKeyDatP

private

Definition at line 89 of file hashmp.h.

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

typedef THashMPKeyDat<TKey, TDat> THashMP< TKey, TDat, THashFunc >::TPHKeyDat

private

Definition at line 88 of file hashmp.h.

Member Enumeration Documentation

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

anonymous enum

Enumerator
HashPrimes

Definition at line 83 of file hashmp.h.

{HashPrimes=32};

Constructor & Destructor Documentation

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

THashMP< TKey, TDat, THashFunc >::THashMP ( )

inline

Definition at line 117 of file hashmp.h.

           :
    Table(), NumVals(0){}

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

THashMP< TKey, TDat, THashFunc >::THashMP ( const THashMP< TKey, TDat, THashFunc > &  PHash )

inline

Definition at line 119 of file hashmp.h.

                               :
    Table(PHash.Table), NumVals(PHash.NumVals){}

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

THashMP< TKey, TDat, THashFunc >::THashMP ( const int &  ExpectVals )

inlineexplicit

Definition at line 121 of file hashmp.h.

                                          {
    Gen(ExpectVals);}

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

THashMP< TKey, TDat, THashFunc >::THashMP ( TSIn &  SIn )

inlineexplicit

Definition at line 123 of file hashmp.h.

                             :
    Table(SIn), NumVals(SIn){
    SIn.LoadCs();}

Member Function Documentation

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

TDat& THashMP< TKey, TDat, THashFunc >::AddDat ( const TKey &  Key )

inline

Definition at line 181 of file hashmp.h.

Referenced by TNEANetMP::AddEdge(), TNEANetMP::AddFltAttrE(), TNEANetMP::AddFltAttrN(), TNEANetMP::AddIntAttrE(), TNEANetMP::AddIntAttrN(), TNGraphMP::AddNode(), TNEANetMP::AddNode(), TNGraphMP::AddNodeUnchecked(), TNEANetMP::AddStrAttrE(), TNEANetMP::AddStrAttrN(), THashMP< TInt, TEdge >::operator()(), TMMNet::ToNetworkMP(), and TTable::UpdateGrouping().

{return Table[AddKey(Key)].Dat;}

Here is the caller graph for this function:

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

TDat& THashMP< TKey, TDat, THashFunc >::AddDat ( const TKey &  Key, const TDat &  Dat  )

inline

Definition at line 182 of file hashmp.h.

                                                {
    return Table[AddKey(Key)].Dat=Dat;}

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

TDat& THashMP< TKey, TDat, THashFunc >::AddDatId ( const TKey &  Key )

inline

Definition at line 178 of file hashmp.h.

                                 {
    int KeyId=AddKey(Key); return Table[KeyId].Dat=KeyId;}

template<class TKey, class TDat , class THashFunc >

int THashMP< TKey, TDat, THashFunc >::AddKey

(

const TKey &

Key

)

Definition at line 259 of file hashmp.h.

Referenced by THashMP< TInt, TEdge >::AddDat(), and THashMP< TInt, TEdge >::AddDatId().

                                                          {
  //int CurVals = __sync_fetch_and_add(&NumVals.Val, 1);
  //IAssertR(CurVals < Table.Len(), "Table must not be full");

  const int BegTableN=abs(Key.GetPrimHashCd()%Table.Len());
  const int HashCd=abs(Key.GetSecHashCd());

  int TableN = BegTableN;
  while (Table[TableN].HashCd != -1 || 
    (!__sync_bool_compare_and_swap(&Table[TableN].HashCd.Val, -1, HashCd))) {
    TableN = (TableN + 1) % Table.Len();    
  }
  Table[TableN].Key = Key;
  __sync_fetch_and_add(&NumVals.Val, 1);
  return TableN;
}

Here is the caller graph for this function:

template<class TKey, class TDat , class THashFunc >

int THashMP< TKey, TDat, THashFunc >::AddKey1	(	const TKey &	Key,
		bool &	Found
	)

Definition at line 396 of file hashmp.h.

                                                                        {
  const int Length = Table.Len();
  //const int Length = 12582917;
  const int BegTableN = abs(Key.GetPrimHashCd() % Length);
  const int HashCd = abs(Key.GetSecHashCd());

  //printf("AddKey1 %5d %5d\n", Length, BegTableN);

  int TableN = BegTableN;
  while (Table[TableN].HashCd.Val != -1) {
    if (Table[TableN].Key == Key) {
      Found = true;
      return TableN;
    }
    TableN++;
    if (TableN >= Length) {
      TableN = 0;
    }
    //(!__sync_bool_compare_and_swap(&Table[TableN].HashCd.Val, -1, HashCd))) {
    //TableN = (TableN + 1) % Table.Len();    
  }

  NumVals.Val++;
  Found = false;
  Table[TableN].HashCd.Val = HashCd;
  Table[TableN].Key = Key;
  return TableN;

  // TODO:RS, need to set the length at the end
}

template<class TKey, class TDat , class THashFunc >

int THashMP< TKey, TDat, THashFunc >::AddKey11	(	const int &	Idx,
		const TKey &	Key,
		bool &	Found
	)

Definition at line 277 of file hashmp.h.

                                                                                               {
  //int CurVals = __sync_fetch_and_add(&NumVals.Val, 1);
  //IAssertR(CurVals < Table.Len(), "Table must not be full");

  const int Length = Table.Len();
  const int HashCd=abs(Key.GetSecHashCd());

  int TableN = BegTableN;
  Found = false;
  do {
    if (Table[TableN].HashCd.Val != -1) {
      if (Table[TableN].Key == Key) {
        Found = true;
        return TableN;
      }
    } else if (__sync_bool_compare_and_swap(&Table[TableN].HashCd.Val, -1, HashCd)) {
      break;
    }
    
    TableN++;
    if (TableN >= Length) {
      TableN = 0;
    }
  } while (1);

  Table[TableN].Key = Key;
  return TableN;
}

template<class TKey, class TDat , class THashFunc >

int THashMP< TKey, TDat, THashFunc >::AddKey12	(	const int &	Idx,
		const TKey &	Key,
		bool &	Found
	)

Definition at line 307 of file hashmp.h.

Referenced by TNGraphMP::AddInEdge1(), and TNGraphMP::AddOutEdge1().

                                                                                               {
  //int CurVals = __sync_fetch_and_add(&NumVals.Val, 1);
  //IAssertR(CurVals < Table.Len(), "Table must not be full");

  const int Length = Table.Len();
  //const int HashCd=abs(Key.GetSecHashCd());

  // HashCd values:
  //  -1: empty slot
  //   1: occupied slot, invalid key
  //   2: occupied slot, valid key

  int TableN = BegTableN;
  do {
    int HashCd = Table[TableN].HashCd.Val;
    if (HashCd == -1) {
      // an empty slot
      if (__sync_bool_compare_and_swap(&Table[TableN].HashCd.Val, -1, 1)) {
        // an empty slot has been claimed, key is invalid
        break;
      }
    } else {
      // slot is occupied
      if (HashCd != 2) {
        // key is not yet valid, wait for a valid key
        while (!__sync_bool_compare_and_swap(&Table[TableN].HashCd.Val, 2, 2)) {
          usleep(20);
        }
      }
      if (Table[TableN].Key == Key) {
        // the key matches
        Found = true;
        return TableN;
      }
      // move to the next slot
      TableN++;
      if (TableN >= Length) {
        TableN = 0;
      }
    }
  } while (1);

  // write the key, indicate a valid key
  Table[TableN].Key = Key;
  Table[TableN].HashCd.Val = 2;

  Found = false;
  return TableN;
}

Here is the caller graph for this function:

template<class TKey, class TDat , class THashFunc >

int THashMP< TKey, TDat, THashFunc >::AddKey13	(	const int &	Idx,
		const TKey &	Key
	)

Definition at line 358 of file hashmp.h.

Referenced by TNEANetMP::AddEdgeUnchecked(), TNGraphMP::AddNodeWithEdges(), and TNEANetMP::AddNodeWithEdges().

                                                                                  {
  //int CurVals = __sync_fetch_and_add(&NumVals.Val, 1);
  //IAssertR(CurVals < Table.Len(), "Table must not be full");

  const int Length = Table.Len();
  //const int HashCd=abs(Key.GetSecHashCd());

  // HashCd values:
  //  -1: empty slot
  //   1: occupied slot, invalid key
  //   2: occupied slot, valid key

  int TableN = BegTableN;
  do {
    int HashCd = Table[TableN].HashCd.Val;
    if (HashCd == -1) {
      // an empty slot
      if (__sync_bool_compare_and_swap(&Table[TableN].HashCd.Val, -1, 1)) {
        // an empty slot has been claimed, key is invalid
        break;
      }
    } else {
      // slot is occupied, move to the next slot
      TableN++;
      if (TableN >= Length) {
        TableN = 0;
      }
    }
  } while (1);

  // write the key, indicate a valid key
  Table[TableN].Key = Key;
  Table[TableN].HashCd.Val = 2;

  return TableN;
}

Here is the caller graph for this function:

template<class TKey, class TDat , class THashFunc >

int THashMP< TKey, TDat, THashFunc >::AddKey2	(	const int &	Idx,
		const TKey &	Key,
		bool &	Found
	)

Definition at line 428 of file hashmp.h.

                                                                                              {
  //const int Length = 12582917;
  const int Length = Table.Len();
  const int HashCd = abs(Key.GetSecHashCd());

  //printf("AddKey2 %5d %5d\n", Length, BegTableN);

  int TableN = BegTableN;
  while (Table[TableN].HashCd.Val != -1) {
    if (Table[TableN].Key == Key) {
      Found = true;
      return TableN;
    }
    TableN++;
    if (TableN >= Length) {
      TableN = 0;
    }
    //(!__sync_bool_compare_and_swap(&Table[TableN].HashCd.Val, -1, HashCd))) {
    //TableN = (TableN + 1) % Table.Len();    
  }

  //NumVals.Val++;
  Found = false;
  Table[TableN].HashCd.Val = HashCd;
  Table[TableN].Key = Key;
  return TableN;

  // TODO:RS, need to set the length at the end
}

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

TIter THashMP< TKey, TDat, THashFunc >::BegI ( ) const

inline

Definition at line 153 of file hashmp.h.

Referenced by TTable::Aggregate(), TNEANetMP::BegEI(), TNGraphMP::BegNI(), and TNEANetMP::BegNI().

                     {
    if (Len() == 0){return TIter(Table.EndI(), Table.EndI());}
    return TIter(Table.BegI(), Table.EndI());}

Here is the caller graph for this function:

template<class TKey , class TDat , class THashFunc >

void THashMP< TKey, TDat, THashFunc >::Clr

(

const bool &

DoDel = true

)

Definition at line 474 of file hashmp.h.

Referenced by TNGraphMP::Clr(), and TNEANetMP::Clr().

                                                         {
  if (DoDel){
    Table.Clr();
  } else {
    Table.PutAll(TPHKeyDat());
  }
  NumVals = TInt(0);
}

Here is the caller graph for this function:

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

bool THashMP< TKey, TDat, THashFunc >::Empty ( ) const

inline

Definition at line 164 of file hashmp.h.

{return Len()==0;}

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

TIter THashMP< TKey, TDat, THashFunc >::EndI ( ) const

inline

Definition at line 156 of file hashmp.h.

Referenced by TTable::Aggregate(), TNEANetMP::EndEI(), TNGraphMP::EndNI(), and TNEANetMP::EndNI().

{return TIter(Table.EndI(), Table.EndI());}

Here is the caller graph for this function:

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

int THashMP< TKey, TDat, THashFunc >::FFirstKeyId ( ) const

inline

Definition at line 207 of file hashmp.h.

Referenced by TNGraphMP::Defrag(), TNEANetMP::Defrag(), TNGraphMP::Dump(), TNGraphMP::GetEdges(), TNEANetMP::GetEIdV(), TNGraphMP::GetNIdV(), TNEANetMP::GetNIdV(), TNGraphMP::IsOk(), and TNEANetMP::IsOk().

{return 0-1;}

Here is the caller graph for this function:

template<class TKey , class TDat , class THashFunc >

bool THashMP< TKey, TDat, THashFunc >::FNextKeyId

(

int &

KeyId

)

const

Definition at line 484 of file hashmp.h.

Referenced by TNGraphMP::Defrag(), TNEANetMP::Defrag(), TNGraphMP::Dump(), TNGraphMP::GetEdges(), TNEANetMP::GetEIdV(), TNGraphMP::GetNIdV(), TNEANetMP::GetNIdV(), TNGraphMP::IsOk(), and TNEANetMP::IsOk().

                                                                {
  do {KeyId++;} while ((KeyId<Table.Len())&&(Table[KeyId].HashCd==-1));
  return KeyId<Table.Len();
}

Here is the caller graph for this function:

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

void THashMP< TKey, TDat, THashFunc >::Gen ( const int &  ExpectVals )

inline

Definition at line 160 of file hashmp.h.

Referenced by TTable::GroupByIntColMP(), TNGraphMP::Reserve(), TNEANetMP::Reserve(), TNEANetMP::ReserveAttr(), and THashMP< TInt, TEdge >::THashMP().

                                 {
    Table.Gen(GetNextPrime(2 * ExpectVals));}

Here is the caller graph for this function:

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

const TDat& THashMP< TKey, TDat, THashFunc >::GetDat ( const TKey &  Key ) const

inline

Definition at line 195 of file hashmp.h.

Referenced by TTable::Aggregate(), TNEANetMP::GetEdge(), TNEANetMP::GetFltAttrDefaultE(), TNEANetMP::GetFltAttrDefaultN(), TNEANetMP::GetIntAttrDefaultE(), TNEANetMP::GetIntAttrDefaultN(), TNGraphMP::GetNode(), TNEANetMP::GetNode(), TNEANetMP::GetStrAttrDefaultE(), TNEANetMP::GetStrAttrDefaultN(), THashMP< TKey, TDat, THashFunc >::operator==(), TMMNet::ToNetworkMP(), TTable::UpdateFltFromTableMP(), and TTable::UpdateGrouping().

{return Table[GetKeyId(Key)].Dat;}

Here is the caller graph for this function:

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

TDat& THashMP< TKey, TDat, THashFunc >::GetDat ( const TKey &  Key )

inline

Definition at line 196 of file hashmp.h.

{return Table[GetKeyId(Key)].Dat;}

template<class TKey, class TDat, class THashFunc >

void THashMP< TKey, TDat, THashFunc >::GetDatKeyKdV

(

TVec< TKeyDat< TDat, TKey > > &

DatKeyKdV

)

const

Definition at line 539 of file hashmp.h.

                                                                                             {
  DatKeyKdV.Gen(Len(), 0);
  TKey Key; TDat Dat;
  int KeyId=FFirstKeyId();
  while (FNextKeyId(KeyId)){
    GetKeyDat(KeyId, Key, Dat);
    DatKeyKdV.Add(TKeyDat<TDat, TKey>(Dat, Key));
  }
}

template<class TKey, class TDat, class THashFunc >

void THashMP< TKey, TDat, THashFunc >::GetDatKeyPrV

(

TVec< TPair< TDat, TKey > > &

DatKeyPrV

)

const

Definition at line 517 of file hashmp.h.

                                                                                           {
  DatKeyPrV.Gen(Len(), 0);
  TKey Key; TDat Dat;
  int KeyId=FFirstKeyId();
  while (FNextKeyId(KeyId)){
    GetKeyDat(KeyId, Key, Dat);
    DatKeyPrV.Add(TPair<TDat, TKey>(Dat, Key));
  }
}

template<class TKey , class TDat, class THashFunc >

void THashMP< TKey, TDat, THashFunc >::GetDatV

(

TVec< TDat > &

DatV

)

const

Definition at line 498 of file hashmp.h.

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

                                                                   {
  DatV.Gen(Len(), 0);
  int KeyId=FFirstKeyId();
  while (FNextKeyId(KeyId)){
    DatV.Add(GetPHashKeyDat(KeyId).Dat);}
}

Here is the call graph for this function:

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

TIter THashMP< TKey, TDat, THashFunc >::GetI ( const TKey &  Key ) const

inline

Definition at line 158 of file hashmp.h.

Referenced by TNEANetMP::GetEI(), TNGraphMP::GetNI(), and TNEANetMP::GetNI().

{return TIter(&Table[GetKeyId(Key)], Table.EndI());}

Here is the caller graph for this function:

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

const TKey& THashMP< TKey, TDat, THashFunc >::GetKey ( const int &  KeyId ) const

inline

Definition at line 185 of file hashmp.h.

Referenced by TNEANetMP::GetEIdV(), TNGraphMP::GetNIdV(), TNEANetMP::GetNIdV(), TNEANetMP::GetRndEId(), TNGraphMP::GetRndNId(), TNEANetMP::GetRndNId(), and THashMP< TKey, TDat, THashFunc >::THashMPKeyDatCmp::operator()().

{ return GetPHashKeyDat(KeyId).Key;}

Here is the caller graph for this function:

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

void THashMP< TKey, TDat, THashFunc >::GetKeyDat ( const int &  KeyId, TKey &  Key, TDat &  Dat  ) const

inline

Definition at line 200 of file hashmp.h.

                                                               {
    const TPHKeyDat& KeyDat=GetPHashKeyDat(KeyId);
    Key=KeyDat.Key; Dat=KeyDat.Dat;}

template<class TKey, class TDat, class THashFunc >

void THashMP< TKey, TDat, THashFunc >::GetKeyDatKdV

(

TVec< TKeyDat< TKey, TDat > > &

KeyDatKdV

)

const

Definition at line 528 of file hashmp.h.

                                                                                             {
  KeyDatKdV.Gen(Len(), 0);
  TKey Key; TDat Dat;
  int KeyId=FFirstKeyId();
  while (FNextKeyId(KeyId)){
    GetKeyDat(KeyId, Key, Dat);
    KeyDatKdV.Add(TKeyDat<TKey, TDat>(Key, Dat));
  }
}

template<class TKey, class TDat, class THashFunc >

void THashMP< TKey, TDat, THashFunc >::GetKeyDatPrV

(

TVec< TPair< TKey, TDat > > &

KeyDatPrV

)

const

Definition at line 506 of file hashmp.h.

                                                                                           {
  KeyDatPrV.Gen(Len(), 0);
  TKey Key; TDat Dat;
  int KeyId=FFirstKeyId();
  while (FNextKeyId(KeyId)){
    GetKeyDat(KeyId, Key, Dat);
    KeyDatPrV.Add(TPair<TKey, TDat>(Key, Dat));
  }
}

template<class TKey, class TDat , class THashFunc >

int THashMP< TKey, TDat, THashFunc >::GetKeyId

(

const TKey &

Key

)

const

Definition at line 459 of file hashmp.h.

Referenced by TNEANetMP::AddEdge(), TNEANetMP::AddFltAttrDatE(), TNEANetMP::AddFltAttrDatN(), TNGraphMP::AddInEdge2(), TNEANetMP::AddIntAttrDatE(), TNEANetMP::AddIntAttrDatN(), TNEANetMP::AddNode(), TNGraphMP::AddOutEdge2(), TNEANetMP::AddStrAttrDatE(), TNEANetMP::AddStrAttrDatN(), TNEANetMP::DelAttrDatE(), TNEANetMP::DelAttrDatN(), TNEANetMP::EdgeAttrIsFltDeleted(), TNEANetMP::EdgeAttrIsIntDeleted(), TNEANetMP::EdgeAttrIsStrDeleted(), TNEANetMP::FltAttrValueNI(), THashMP< TInt, TEdge >::GetDat(), TNEANetMP::GetEAFltI(), TNEANetMP::GetEAIntI(), TNEANetMP::GetEAStrI(), TNEANetMP::GetEdgeAttrValue(), TNEANetMP::GetFltAttrDatE(), TNEANetMP::GetFltAttrDatN(), TNEANetMP::GetFltKeyIdE(), THashMP< TInt, TEdge >::GetI(), TNEANetMP::GetIntAttrDatE(), TNEANetMP::GetIntAttrDatN(), TNEANetMP::GetIntAttrIndDatE(), TNEANetMP::GetIntAttrIndDatN(), TNEANetMP::GetNAFltI(), TNEANetMP::GetNAIntI(), TNEANetMP::GetNAStrI(), TNEANetMP::GetNodeAttrValue(), TNEANetMP::GetStrAttrDatE(), TNEANetMP::GetStrAttrDatN(), TNEANetMP::IntAttrValueNI(), THashMP< TInt, TEdge >::IsKey(), TNEANetMP::NodeAttrIsFltDeleted(), TNEANetMP::NodeAttrIsIntDeleted(), TNEANetMP::NodeAttrIsStrDeleted(), and TNEANetMP::StrAttrValueNI().

                                                                  {
  const int BegTableN=abs(Key.GetPrimHashCd()%Table.Len());
  //const int HashCd=abs(Key.GetSecHashCd());

  int TableN = BegTableN;
  while (Table[TableN].HashCd != -1) {
    if (Table[TableN].Key == Key) { return TableN; }
    TableN = (TableN + 1) % Table.Len();
    if (TableN == BegTableN) { return -1; }
  }

  return -1;
}

Here is the caller graph for this function:

template<class TKey, class TDat , class THashFunc >

void THashMP< TKey, TDat, THashFunc >::GetKeyV

(

TVec< TKey > &

KeyV

)

const

Definition at line 490 of file hashmp.h.

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

Referenced by TNEANetMP::AddEdge(), TNEANetMP::AddNode(), and TMMNet::ToNetworkMP().

                                                                   {
  KeyV.Gen(Len(), 0);
  int KeyId=FFirstKeyId();
  while (FNextKeyId(KeyId)){
    KeyV.Add(GetKey(KeyId));}
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

::TSize THashMP< TKey, TDat, THashFunc >::GetMemUsed ( ) const

inline

Definition at line 142 of file hashmp.h.

                           {
    // return PortV.GetMemUsed()+KeyDatV.GetMemUsed()+sizeof(bool)+2*sizeof(int);}
      int64 MemUsed = sizeof(int);
      for (int TableN = 0; TableN < Table.Len(); TableN++) {
          MemUsed += int64(sizeof(TInt));
          MemUsed += int64(Table[TableN].Key.GetMemUsed());
          MemUsed += int64(Table[TableN].Dat.GetMemUsed());
      }
      return ::TSize(MemUsed);
  }

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

int THashMP< TKey, TDat, THashFunc >::GetMxKeyIds ( ) const

inline

Definition at line 167 of file hashmp.h.

{return Table.Len();}

template<class TKey , class TDat , class THashFunc >

uint THashMP< TKey, TDat, THashFunc >::GetNextPrime ( const uint &  Val ) const

private

Definition at line 236 of file hashmp.h.

Referenced by THashMP< TInt, TEdge >::Gen().

                                                                       {
  const uint* f=(const uint*)HashPrimeT, *m, *l=(const uint*)HashPrimeT + (int)HashPrimes;
  int h, len = (int)HashPrimes;
  while (len > 0) {
    h = len >> 1;  m = f + h;
    if (*m < Val) { f = m;  f++;  len = len - h - 1; }
    else len = h;
  }
  return f == l ? *(l - 1) : *f;
}

Here is the caller graph for this function:

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

TPHKeyDat& THashMP< TKey, TDat, THashFunc >::GetPHashKeyDat ( const int &  KeyId )

inlineprivate

Definition at line 108 of file hashmp.h.

Referenced by THashMP< TInt, TEdge >::GetKey(), THashMP< TInt, TEdge >::GetKeyDat(), THashMP< TInt, TEdge >::IsKeyGetDat(), and THashMP< TInt, TEdge >::operator[]().

                                             {
    TPHKeyDat& KeyDat=Table[KeyId];
    Assert(KeyDat.HashCd!=-1); return KeyDat;}

Here is the caller graph for this function:

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

const TPHKeyDat& THashMP< TKey, TDat, THashFunc >::GetPHashKeyDat ( const int &  KeyId ) const

inlineprivate

Definition at line 111 of file hashmp.h.

                                                          {
    const TPHKeyDat& KeyDat=Table[KeyId];
    Assert(KeyDat.HashCd!=-1); return KeyDat;}

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

int THashMP< TKey, TDat, THashFunc >::GetReservedKeyIds ( ) const

inline

Definition at line 169 of file hashmp.h.

Referenced by TNGraphMP::Reserved(), TNEANetMP::Reserved(), and TNEANetMP::ReservedE().

{return Table.Reserved();}

Here is the caller graph for this function:

template<class TKey , class TDat , class THashFunc >

int THashMP< 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 558 of file hashmp.h.

Referenced by TNEANetMP::GetRndEId(), TNGraphMP::GetRndNId(), and TNEANetMP::GetRndNId().

                                                                {
  printf("*** ERROR *** THashMP<TKey, TDat, THashFunc>::GetRndKeyId called\n");
  return 0;
}

Here is the caller graph for this function:

template<class TKey , class TDat , class THashFunc >

int THashMP< 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 564 of file hashmp.h.

                                                                                  {
  printf("*** ERROR *** THashMP<TKey, TDat, THashFunc>::GetRndKeyId called\n");
  return 0;
}

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

bool THashMP< TKey, TDat, THashFunc >::IsKey ( const TKey &  Key ) const

inline

Definition at line 191 of file hashmp.h.

Referenced by TNEANetMP::AddFltAttrE(), TNEANetMP::AddFltAttrN(), TNEANetMP::AddIntAttrE(), TNEANetMP::AddIntAttrN(), TNEANetMP::AddStrAttrE(), TNEANetMP::AddStrAttrN(), TNEANetMP::GetFltAttrDefaultE(), TNEANetMP::GetFltAttrDefaultN(), TNEANetMP::GetIntAttrDefaultE(), TNEANetMP::GetIntAttrDefaultN(), TNEANetMP::GetStrAttrDefaultE(), TNEANetMP::GetStrAttrDefaultN(), TNEANetMP::IsEdge(), THashMP< TInt, TEdge >::IsKeyGetDat(), TNGraphMP::IsNode(), TNEANetMP::IsNode(), THashMP< TKey, TDat, THashFunc >::operator==(), TTable::UpdateFltFromTableMP(), and TTable::UpdateGrouping().

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

Here is the caller graph for this function:

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

bool THashMP< TKey, TDat, THashFunc >::IsKey ( const TKey &  Key, int &  KeyId  ) const

inline

Definition at line 192 of file hashmp.h.

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

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

bool THashMP< TKey, TDat, THashFunc >::IsKeyGetDat ( const TKey &  Key, TDat &  Dat  ) const

inline

Definition at line 203 of file hashmp.h.

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

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

bool THashMP< TKey, TDat, THashFunc >::IsKeyId ( const int &  KeyId ) const

inline

Definition at line 193 of file hashmp.h.

                                       {
    return (0<=KeyId)&&(KeyId<Table.Len())&&(Table[KeyId].HashCd!=-1);}

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

int THashMP< TKey, TDat, THashFunc >::Len ( ) const

inline

Definition at line 165 of file hashmp.h.

Referenced by THashMP< TInt, TEdge >::BegI(), THashMP< TInt, TEdge >::Empty(), TNEANetMP::GetEdges(), TNGraphMP::GetNodes(), TNEANetMP::GetNodes(), and THashMP< TKey, TDat, THashFunc >::operator==().

{return NumVals;}

Here is the caller graph for this function:

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

void THashMP< TKey, TDat, THashFunc >::Load ( TSIn &  SIn )

inline

Definition at line 126 of file hashmp.h.

                      {
    Table.Load(SIn); NumVals.Load(SIn);
    SIn.LoadCs();}

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

TDat& THashMP< TKey, TDat, THashFunc >::operator() ( const TKey &  Key )

inline

Definition at line 141 of file hashmp.h.

{return AddDat(Key);}

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

THashMP& THashMP< TKey, TDat, THashFunc >::operator= ( const THashMP< TKey, TDat, THashFunc > &  Hash )

inline

Definition at line 133 of file hashmp.h.

                                         {
    if (this!=&Hash){
      Table=Hash.Table; NumVals=Hash.NumVals;}
    return *this;}

template<class TKey , class TDat , class THashFunc >

bool THashMP< TKey, TDat, THashFunc >::operator==

(

const THashMP< TKey, TDat, THashFunc > &

Hash

)

const

Definition at line 248 of file hashmp.h.

References THashMP< TKey, TDat, THashFunc >::GetDat(), THashMP< TKey, TDat, THashFunc >::IsKey(), and THashMP< TKey, TDat, THashFunc >::Len().

                                                                         {
  if (Len() != Hash.Len()) { return false; }
  for (int i = FFirstKeyId(); FNextKeyId(i); ) {
    const TKey& Key = GetKey(i);
    if (! Hash.IsKey(Key)) { return false; }
    if (GetDat(Key) != Hash.GetDat(Key)) { return false; }
  }
  return true;
}

Here is the call graph for this function:

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

const TDat& THashMP< TKey, TDat, THashFunc >::operator[] ( const int &  KeyId ) const

inline

Definition at line 139 of file hashmp.h.

{return GetPHashKeyDat(KeyId).Dat;}

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

TDat& THashMP< TKey, TDat, THashFunc >::operator[] ( const int &  KeyId )

inline

Definition at line 140 of file hashmp.h.

{return GetPHashKeyDat(KeyId).Dat;}

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

void THashMP< TKey, TDat, THashFunc >::Pack ( )

inline

Definition at line 218 of file hashmp.h.

{Table.Pack();}

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

void THashMP< TKey, TDat, THashFunc >::Save ( TSOut &  SOut ) const

inline

Definition at line 129 of file hashmp.h.

Referenced by TNGraphMP::Save(), and TNEANetMP::Save().

                               {
    Table.Save(SOut); NumVals.Save(SOut);
    SOut.SaveCs();}

Here is the caller graph for this function:

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

void THashMP< TKey, TDat, THashFunc >::SetLen ( const int &  Length )

inline

Definition at line 166 of file hashmp.h.

Referenced by TNEANetMP::SetEdges(), TNGraphMP::SetNodes(), and TNEANetMP::SetNodes().

{NumVals=Length;}

Here is the caller graph for this function:

template<class TKey , class TDat , class THashFunc >

void THashMP< TKey, TDat, THashFunc >::Swap

(

THashMP< TKey, TDat, THashFunc > &

Hash

)

Definition at line 550 of file hashmp.h.

References THashMP< TKey, TDat, THashFunc >::NumVals, Swap(), and THashMP< TKey, TDat, THashFunc >::Table.

                                                       {
  if (this!=&Hash){
    Table.Swap(Hash.Table);
    ::Swap(NumVals, Hash.NumVals);
  }
}

Here is the call graph for this function:

Member Data Documentation

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

const unsigned int THashMP< 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 84 of file hashmp.h.

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

TInt THashMP< TKey, TDat, THashFunc >::NumVals

private

Definition at line 91 of file hashmp.h.

Referenced by THashMP< TInt, TEdge >::Len(), THashMP< TInt, TEdge >::operator=(), and THashMP< TKey, TDat, THashFunc >::Swap().

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

TVec<TPHKeyDat> THashMP< TKey, TDat, THashFunc >::Table

private

Definition at line 90 of file hashmp.h.

Referenced by THashMP< TInt, TEdge >::operator=(), and THashMP< TKey, TDat, THashFunc >::Swap().

---

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

• glib-core/hashmp.h