SNAP Library 3.0, User Reference  2016-07-20 17:56:49
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
THashMP< TKey, TDat, THashFunc > Class Template Reference

Hash-Table with multiprocessing support. More...

#include <hashmp.h>

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.

83 {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.

117  :
118  Table(), NumVals(0){}
THashMP::NumVals
TInt NumVals
Definition: hashmp.h:91
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

119  :
120  Table(PHash.Table), NumVals(PHash.NumVals){}
THashMP::NumVals
TInt NumVals
Definition: hashmp.h:91
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

121  {
122  Gen(ExpectVals);}
THashMP::Gen
void Gen(const int &ExpectVals)
Definition: hashmp.h:160
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.

123  :
124  Table(SIn), NumVals(SIn){
125  SIn.LoadCs();}
THashMP::NumVals
TInt NumVals
Definition: hashmp.h:91
TSIn::LoadCs
void LoadCs()
Definition: fl.cpp:28
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90

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.

181 {return Table[AddKey(Key)].Dat;}
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
THashMP::AddKey
int AddKey(const TKey &Key)
Definition: hashmp.h:259
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.

182  {
183  return Table[AddKey(Key)].Dat=Dat;}
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
THashMP::AddKey
int AddKey(const TKey &Key)
Definition: hashmp.h:259
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.

178  {
179  int KeyId=AddKey(Key); return Table[KeyId].Dat=KeyId;}
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
THashMP::AddKey
int AddKey(const TKey &Key)
Definition: hashmp.h:259
template<class TKey, class TDat , class THashFunc >
int THashMP< TKey, TDat, THashFunc >::AddKey ( const TKey &  Key)

Definition at line 259 of file hashmp.h.

259  {
260  //int CurVals = __sync_fetch_and_add(&NumVals.Val, 1);
261  //IAssertR(CurVals < Table.Len(), "Table must not be full");
262 
263  const int BegTableN=abs(Key.GetPrimHashCd()%Table.Len());
264  const int HashCd=abs(Key.GetSecHashCd());
265 
266  int TableN = BegTableN;
267  while (Table[TableN].HashCd != -1 ||
268  (!__sync_bool_compare_and_swap(&Table[TableN].HashCd.Val, -1, HashCd))) {
269  TableN = (TableN + 1) % Table.Len();
270  }
271  Table[TableN].Key = Key;
272  __sync_fetch_and_add(&NumVals.Val, 1);
273  return TableN;
274 }
TInt::Val
int Val
Definition: dt.h:1046
THashMP::NumVals
TInt NumVals
Definition: hashmp.h:91
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

396  {
397  const int Length = Table.Len();
398  //const int Length = 12582917;
399  const int BegTableN = abs(Key.GetPrimHashCd() % Length);
400  const int HashCd = abs(Key.GetSecHashCd());
401 
402  //printf("AddKey1 %5d %5d\n", Length, BegTableN);
403 
404  int TableN = BegTableN;
405  while (Table[TableN].HashCd.Val != -1) {
406  if (Table[TableN].Key == Key) {
407  Found = true;
408  return TableN;
409  }
410  TableN++;
411  if (TableN >= Length) {
412  TableN = 0;
413  }
414  //(!__sync_bool_compare_and_swap(&Table[TableN].HashCd.Val, -1, HashCd))) {
415  //TableN = (TableN + 1) % Table.Len();
416  }
417 
418  NumVals.Val++;
419  Found = false;
420  Table[TableN].HashCd.Val = HashCd;
421  Table[TableN].Key = Key;
422  return TableN;
423 
424  // TODO:RS, need to set the length at the end
425 }
TInt::Val
int Val
Definition: dt.h:1046
THashMP::NumVals
TInt NumVals
Definition: hashmp.h:91
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

277  {
278  //int CurVals = __sync_fetch_and_add(&NumVals.Val, 1);
279  //IAssertR(CurVals < Table.Len(), "Table must not be full");
280 
281  const int Length = Table.Len();
282  const int HashCd=abs(Key.GetSecHashCd());
283 
284  int TableN = BegTableN;
285  Found = false;
286  do {
287  if (Table[TableN].HashCd.Val != -1) {
288  if (Table[TableN].Key == Key) {
289  Found = true;
290  return TableN;
291  }
292  } else if (__sync_bool_compare_and_swap(&Table[TableN].HashCd.Val, -1, HashCd)) {
293  break;
294  }
295 
296  TableN++;
297  if (TableN >= Length) {
298  TableN = 0;
299  }
300  } while (1);
301 
302  Table[TableN].Key = Key;
303  return TableN;
304 }
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

307  {
308  //int CurVals = __sync_fetch_and_add(&NumVals.Val, 1);
309  //IAssertR(CurVals < Table.Len(), "Table must not be full");
310 
311  const int Length = Table.Len();
312  //const int HashCd=abs(Key.GetSecHashCd());
313 
314  // HashCd values:
315  // -1: empty slot
316  // 1: occupied slot, invalid key
317  // 2: occupied slot, valid key
318 
319  int TableN = BegTableN;
320  do {
321  int HashCd = Table[TableN].HashCd.Val;
322  if (HashCd == -1) {
323  // an empty slot
324  if (__sync_bool_compare_and_swap(&Table[TableN].HashCd.Val, -1, 1)) {
325  // an empty slot has been claimed, key is invalid
326  break;
327  }
328  } else {
329  // slot is occupied
330  if (HashCd != 2) {
331  // key is not yet valid, wait for a valid key
332  while (!__sync_bool_compare_and_swap(&Table[TableN].HashCd.Val, 2, 2)) {
333  usleep(20);
334  }
335  }
336  if (Table[TableN].Key == Key) {
337  // the key matches
338  Found = true;
339  return TableN;
340  }
341  // move to the next slot
342  TableN++;
343  if (TableN >= Length) {
344  TableN = 0;
345  }
346  }
347  } while (1);
348 
349  // write the key, indicate a valid key
350  Table[TableN].Key = Key;
351  Table[TableN].HashCd.Val = 2;
352 
353  Found = false;
354  return TableN;
355 }
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

358  {
359  //int CurVals = __sync_fetch_and_add(&NumVals.Val, 1);
360  //IAssertR(CurVals < Table.Len(), "Table must not be full");
361 
362  const int Length = Table.Len();
363  //const int HashCd=abs(Key.GetSecHashCd());
364 
365  // HashCd values:
366  // -1: empty slot
367  // 1: occupied slot, invalid key
368  // 2: occupied slot, valid key
369 
370  int TableN = BegTableN;
371  do {
372  int HashCd = Table[TableN].HashCd.Val;
373  if (HashCd == -1) {
374  // an empty slot
375  if (__sync_bool_compare_and_swap(&Table[TableN].HashCd.Val, -1, 1)) {
376  // an empty slot has been claimed, key is invalid
377  break;
378  }
379  } else {
380  // slot is occupied, move to the next slot
381  TableN++;
382  if (TableN >= Length) {
383  TableN = 0;
384  }
385  }
386  } while (1);
387 
388  // write the key, indicate a valid key
389  Table[TableN].Key = Key;
390  Table[TableN].HashCd.Val = 2;
391 
392  return TableN;
393 }
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

428  {
429  //const int Length = 12582917;
430  const int Length = Table.Len();
431  const int HashCd = abs(Key.GetSecHashCd());
432 
433  //printf("AddKey2 %5d %5d\n", Length, BegTableN);
434 
435  int TableN = BegTableN;
436  while (Table[TableN].HashCd.Val != -1) {
437  if (Table[TableN].Key == Key) {
438  Found = true;
439  return TableN;
440  }
441  TableN++;
442  if (TableN >= Length) {
443  TableN = 0;
444  }
445  //(!__sync_bool_compare_and_swap(&Table[TableN].HashCd.Val, -1, HashCd))) {
446  //TableN = (TableN + 1) % Table.Len();
447  }
448 
449  //NumVals.Val++;
450  Found = false;
451  Table[TableN].HashCd.Val = HashCd;
452  Table[TableN].Key = Key;
453  return TableN;
454 
455  // TODO:RS, need to set the length at the end
456 }
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

153  {
154  if (Len() == 0){return TIter(Table.EndI(), Table.EndI());}
155  return TIter(Table.BegI(), Table.EndI());}
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
THashMP::TIter
THashMPKeyDatI< TKey, TDat > TIter
Definition: hashmp.h:86
THashMP::Len
int Len() const
Definition: hashmp.h:165
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.

474  {
475  if (DoDel){
476  Table.Clr();
477  } else {
478  Table.PutAll(TPHKeyDat());
479  }
480  NumVals = TInt(0);
481 }
THashMP::NumVals
TInt NumVals
Definition: hashmp.h:91
THashMP::TPHKeyDat
THashMPKeyDat< TKey, TDat > TPHKeyDat
Definition: hashmp.h:88
TInt
Definition: dt.h:1044
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

164 {return Len()==0;}
THashMP::Len
int Len() const
Definition: hashmp.h:165
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.

156 {return TIter(Table.EndI(), Table.EndI());}
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
THashMP::TIter
THashMPKeyDatI< TKey, TDat > TIter
Definition: hashmp.h:86
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.

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

Definition at line 484 of file hashmp.h.

484  {
485  do {KeyId++;} while ((KeyId<Table.Len())&&(Table[KeyId].HashCd==-1));
486  return KeyId<Table.Len();
487 }
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

160  {
161  Table.Gen(GetNextPrime(2 * ExpectVals));}
THashMP::GetNextPrime
uint GetNextPrime(const uint &Val) const
Definition: hashmp.h:236
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

195 {return Table[GetKeyId(Key)].Dat;}
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
THashMP::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: hashmp.h:459
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.

196 {return Table[GetKeyId(Key)].Dat;}
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
THashMP::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: hashmp.h:459
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.

539  {
540  DatKeyKdV.Gen(Len(), 0);
541  TKey Key; TDat Dat;
542  int KeyId=FFirstKeyId();
543  while (FNextKeyId(KeyId)){
544  GetKeyDat(KeyId, Key, Dat);
545  DatKeyKdV.Add(TKeyDat<TDat, TKey>(Dat, Key));
546  }
547 }
TKeyDat
Definition: ds.h:345
THashMP::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hashmp.h:484
THashMP::FFirstKeyId
int FFirstKeyId() const
Definition: hashmp.h:207
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
THashMP::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hashmp.h:200
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
THashMP::Len
int Len() const
Definition: hashmp.h:165
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.

517  {
518  DatKeyPrV.Gen(Len(), 0);
519  TKey Key; TDat Dat;
520  int KeyId=FFirstKeyId();
521  while (FNextKeyId(KeyId)){
522  GetKeyDat(KeyId, Key, Dat);
523  DatKeyPrV.Add(TPair<TDat, TKey>(Dat, Key));
524  }
525 }
THashMP::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hashmp.h:484
TPair
Definition: ds.h:32
THashMP::FFirstKeyId
int FFirstKeyId() const
Definition: hashmp.h:207
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
THashMP::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hashmp.h:200
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
THashMP::Len
int Len() const
Definition: hashmp.h:165
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.

498  {
499  DatV.Gen(Len(), 0);
500  int KeyId=FFirstKeyId();
501  while (FNextKeyId(KeyId)){
502  DatV.Add(GetPHashKeyDat(KeyId).Dat);}
503 }
THashMP::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hashmp.h:484
THashMP::FFirstKeyId
int FFirstKeyId() const
Definition: hashmp.h:207
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
THashMP::GetPHashKeyDat
TPHKeyDat & GetPHashKeyDat(const int &KeyId)
Definition: hashmp.h:108
THashMP::Len
int Len() const
Definition: hashmp.h:165
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.

158 {return TIter(&Table[GetKeyId(Key)], Table.EndI());}
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
THashMP::TIter
THashMPKeyDatI< TKey, TDat > TIter
Definition: hashmp.h:86
THashMP::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: hashmp.h:459
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.

185 { return GetPHashKeyDat(KeyId).Key;}
THashMPKeyDat::Key
TKey Key
Definition: hashmp.h:15
THashMP::GetPHashKeyDat
TPHKeyDat & GetPHashKeyDat(const int &KeyId)
Definition: hashmp.h:108
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.

200  {
201  const TPHKeyDat& KeyDat=GetPHashKeyDat(KeyId);
202  Key=KeyDat.Key; Dat=KeyDat.Dat;}
THashMP::TPHKeyDat
THashMPKeyDat< TKey, TDat > TPHKeyDat
Definition: hashmp.h:88
THashMP::GetPHashKeyDat
TPHKeyDat & GetPHashKeyDat(const int &KeyId)
Definition: hashmp.h:108
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.

528  {
529  KeyDatKdV.Gen(Len(), 0);
530  TKey Key; TDat Dat;
531  int KeyId=FFirstKeyId();
532  while (FNextKeyId(KeyId)){
533  GetKeyDat(KeyId, Key, Dat);
534  KeyDatKdV.Add(TKeyDat<TKey, TDat>(Key, Dat));
535  }
536 }
TKeyDat
Definition: ds.h:345
THashMP::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hashmp.h:484
THashMP::FFirstKeyId
int FFirstKeyId() const
Definition: hashmp.h:207
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
THashMP::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hashmp.h:200
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
THashMP::Len
int Len() const
Definition: hashmp.h:165
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.

506  {
507  KeyDatPrV.Gen(Len(), 0);
508  TKey Key; TDat Dat;
509  int KeyId=FFirstKeyId();
510  while (FNextKeyId(KeyId)){
511  GetKeyDat(KeyId, Key, Dat);
512  KeyDatPrV.Add(TPair<TKey, TDat>(Key, Dat));
513  }
514 }
THashMP::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hashmp.h:484
TPair
Definition: ds.h:32
THashMP::FFirstKeyId
int FFirstKeyId() const
Definition: hashmp.h:207
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
THashMP::GetKeyDat
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hashmp.h:200
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
THashMP::Len
int Len() const
Definition: hashmp.h:165
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.

459  {
460  const int BegTableN=abs(Key.GetPrimHashCd()%Table.Len());
461  //const int HashCd=abs(Key.GetSecHashCd());
462 
463  int TableN = BegTableN;
464  while (Table[TableN].HashCd != -1) {
465  if (Table[TableN].Key == Key) { return TableN; }
466  TableN = (TableN + 1) % Table.Len();
467  if (TableN == BegTableN) { return -1; }
468  }
469 
470  return -1;
471 }
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

490  {
491  KeyV.Gen(Len(), 0);
492  int KeyId=FFirstKeyId();
493  while (FNextKeyId(KeyId)){
494  KeyV.Add(GetKey(KeyId));}
495 }
THashMP::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hashmp.h:484
THashMP::FFirstKeyId
int FFirstKeyId() const
Definition: hashmp.h:207
TVec::Gen
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:495
TVec::Add
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:574
THashMP::Len
int Len() const
Definition: hashmp.h:165
THashMP::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hashmp.h:185
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.

142  {
143  // return PortV.GetMemUsed()+KeyDatV.GetMemUsed()+sizeof(bool)+2*sizeof(int);}
144  int64 MemUsed = sizeof(int);
145  for (int TableN = 0; TableN < Table.Len(); TableN++) {
146  MemUsed += int64(sizeof(TInt));
147  MemUsed += int64(Table[TableN].Key.GetMemUsed());
148  MemUsed += int64(Table[TableN].Dat.GetMemUsed());
149  }
150  return ::TSize(MemUsed);
151  }
TSize
size_t TSize
Definition: bd.h:58
TInt
Definition: dt.h:1044
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
int64
long long int64
Definition: bd.h:27
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.

167 {return Table.Len();}
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

236  {
237  const uint* f=(const uint*)HashPrimeT, *m, *l=(const uint*)HashPrimeT + (int)HashPrimes;
238  int h, len = (int)HashPrimes;
239  while (len > 0) {
240  h = len >> 1; m = f + h;
241  if (*m < Val) { f = m; f++; len = len - h - 1; }
242  else len = h;
243  }
244  return f == l ? *(l - 1) : *f;
245 }
uint
unsigned int uint
Definition: bd.h:11
THashMP::HashPrimeT
static const unsigned int HashPrimeT[HashPrimes]
Definition: hashmp.h:84
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.

108  {
109  TPHKeyDat& KeyDat=Table[KeyId];
110  Assert(KeyDat.HashCd!=-1); return KeyDat;}
Assert
#define Assert(Cond)
Definition: bd.h:251
THashMP::TPHKeyDat
THashMPKeyDat< TKey, TDat > TPHKeyDat
Definition: hashmp.h:88
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

111  {
112  const TPHKeyDat& KeyDat=Table[KeyId];
113  Assert(KeyDat.HashCd!=-1); return KeyDat;}
Assert
#define Assert(Cond)
Definition: bd.h:251
THashMP::TPHKeyDat
THashMPKeyDat< TKey, TDat > TPHKeyDat
Definition: hashmp.h:88
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

169 {return Table.Reserved();}
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

558  {
559  printf("*** ERROR *** THashMP<TKey, TDat, THashFunc>::GetRndKeyId called\n");
560  return 0;
561 }
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.

564  {
565  printf("*** ERROR *** THashMP<TKey, TDat, THashFunc>::GetRndKeyId called\n");
566  return 0;
567 }
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.

191 {return GetKeyId(Key)!=-1;}
THashMP::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: hashmp.h:459
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.

192 { KeyId=GetKeyId(Key); return KeyId!=-1;}
THashMP::GetKeyId
int GetKeyId(const TKey &Key) const
Definition: hashmp.h:459
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.

203  {int KeyId;
204  if (IsKey(Key, KeyId)){Dat=GetPHashKeyDat(KeyId).Dat; return true;}
205  else {return false;}}
THashMP::IsKey
bool IsKey(const TKey &Key) const
Definition: hashmp.h:191
THashMPKeyDat::Dat
TDat Dat
Definition: hashmp.h:16
THashMP::GetPHashKeyDat
TPHKeyDat & GetPHashKeyDat(const int &KeyId)
Definition: hashmp.h:108
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.

193  {
194  return (0<=KeyId)&&(KeyId<Table.Len())&&(Table[KeyId].HashCd!=-1);}
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

165 {return NumVals;}
THashMP::NumVals
TInt NumVals
Definition: hashmp.h:91
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.

126  {
127  Table.Load(SIn); NumVals.Load(SIn);
128  SIn.LoadCs();}
THashMP::NumVals
TInt NumVals
Definition: hashmp.h:91
TSIn::LoadCs
void LoadCs()
Definition: fl.cpp:28
TInt::Load
void Load(TSIn &SIn)
Definition: dt.h:1059
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

141 {return AddDat(Key);}
THashMP::AddDat
TDat & AddDat(const TKey &Key)
Definition: hashmp.h:181
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.

133  {
134  if (this!=&Hash){
135  Table=Hash.Table; NumVals=Hash.NumVals;}
136  return *this;}
THashMP::NumVals
TInt NumVals
Definition: hashmp.h:91
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

248  {
249  if (Len() != Hash.Len()) { return false; }
250  for (int i = FFirstKeyId(); FNextKeyId(i); ) {
251  const TKey& Key = GetKey(i);
252  if (! Hash.IsKey(Key)) { return false; }
253  if (GetDat(Key) != Hash.GetDat(Key)) { return false; }
254  }
255  return true;
256 }
THashMP::IsKey
bool IsKey(const TKey &Key) const
Definition: hashmp.h:191
THashMP::FNextKeyId
bool FNextKeyId(int &KeyId) const
Definition: hashmp.h:484
THashMP::FFirstKeyId
int FFirstKeyId() const
Definition: hashmp.h:207
THashMP::GetDat
const TDat & GetDat(const TKey &Key) const
Definition: hashmp.h:195
THashMP::Len
int Len() const
Definition: hashmp.h:165
THashMP::GetKey
const TKey & GetKey(const int &KeyId) const
Definition: hashmp.h:185
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.

139 {return GetPHashKeyDat(KeyId).Dat;}
THashMPKeyDat::Dat
TDat Dat
Definition: hashmp.h:16
THashMP::GetPHashKeyDat
TPHKeyDat & GetPHashKeyDat(const int &KeyId)
Definition: hashmp.h:108
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.

140 {return GetPHashKeyDat(KeyId).Dat;}
THashMPKeyDat::Dat
TDat Dat
Definition: hashmp.h:16
THashMP::GetPHashKeyDat
TPHKeyDat & GetPHashKeyDat(const int &KeyId)
Definition: hashmp.h:108
template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey>>
void THashMP< TKey, TDat, THashFunc >::Pack ( )
inline

Definition at line 218 of file hashmp.h.

218 {Table.Pack();}
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

129  {
130  Table.Save(SOut); NumVals.Save(SOut);
131  SOut.SaveCs();}
TInt::Save
void Save(TSOut &SOut) const
Definition: dt.h:1060
THashMP::NumVals
TInt NumVals
Definition: hashmp.h:91
TSOut::SaveCs
void SaveCs()
Definition: fl.h:171
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
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.

166 {NumVals=Length;}
THashMP::NumVals
TInt NumVals
Definition: hashmp.h:91
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.

550  {
551  if (this!=&Hash){
552  Table.Swap(Hash.Table);
553  ::Swap(NumVals, Hash.NumVals);
554  }
555 }
THashMP::NumVals
TInt NumVals
Definition: hashmp.h:91
THashMP::Swap
void Swap(THashMP &Hash)
Definition: hashmp.h:550
THashMP::Table
TVec< TPHKeyDat > Table
Definition: hashmp.h:90

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.

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.

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