SNAP Library 6.0, Developer Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
hashmp.h
Go to the documentation of this file.
1 #ifndef hashmp_h
2 #define hashmp_h
3 
4 #ifdef GCC_ATOMIC
5 
6 #include "bd.h"
7 
9 // PHash-Table-Key-Data
10 #pragma pack(push, 1) // pack class size
11 template <class TKey, class TDat>
13 public:
15  TKey Key;
16  TDat Dat;
17 public:
19  HashCd(-1), Key(), Dat(){}
20  THashMPKeyDat(const int& _HashCd, const TKey& _Key):
21  HashCd(_HashCd), Key(_Key), Dat(){}
22  explicit THashMPKeyDat(TSIn& SIn):
23  HashCd(SIn), Key(SIn), Dat(SIn){}
24  void Save(TSOut& SOut) const {
25  HashCd.Save(SOut); Key.Save(SOut); Dat.Save(SOut);}
26 
27  bool operator==(const THashMPKeyDat& HashKeyDat) const {
28  if (this==&HashKeyDat || (HashCd==HashKeyDat.HashCd
29  && Key==HashKeyDat.Key && Dat==HashKeyDat.Dat)){return true;}
30  return false;}
31  THashMPKeyDat& operator=(const THashMPKeyDat& HashKeyDat){
32  if (this!=&HashKeyDat){
33  HashCd=HashKeyDat.HashCd; Key=HashKeyDat.Key;
34  Dat=HashKeyDat.Dat;}
35  return *this;}
36 };
37 #pragma pack(pop)
38 
40 // PHash-Table-Key-Data-Iterator
41 template<class TKey, class TDat>
43 public:
45 private:
46  TPHKeyDat* KeyDatI;
47  TPHKeyDat* EndI;
48 public:
49  THashMPKeyDatI(): KeyDatI(NULL), EndI(NULL){}
50  THashMPKeyDatI(const THashMPKeyDatI& _HashKeyDatI):
51  KeyDatI(_HashKeyDatI.KeyDatI), EndI(_HashKeyDatI.EndI){}
52  THashMPKeyDatI(const TPHKeyDat* _KeyDatI, const TPHKeyDat* _EndI):
53  KeyDatI((TPHKeyDat*)_KeyDatI), EndI((TPHKeyDat*)_EndI){}
54 
55  THashMPKeyDatI& operator=(const THashMPKeyDatI& HashKeyDatI){
56  KeyDatI=HashKeyDatI.KeyDatI; EndI=HashKeyDatI.EndI; return *this;}
57  bool operator==(const THashMPKeyDatI& HashKeyDatI) const {
58  return KeyDatI==HashKeyDatI.KeyDatI;}
59  bool operator<(const THashMPKeyDatI& HashKeyDatI) const {
60  return KeyDatI<HashKeyDatI.KeyDatI;}
61  THashMPKeyDatI& operator++(int){ KeyDatI++; while (KeyDatI < EndI && KeyDatI->HashCd==-1) { KeyDatI++; } return *this; }
62  THashMPKeyDatI& operator--(int){ do { KeyDatI--; } while (KeyDatI->HashCd==-1); return *this;}
63  TPHKeyDat& operator*() const { return *KeyDatI; }
64  TPHKeyDat& operator()() const { return *KeyDatI; }
65  TPHKeyDat* operator->() const { return KeyDatI; }
66  THashMPKeyDatI& Next(){ operator++(1); return *this; }
67 
69  bool IsEmpty() const { return KeyDatI == NULL; }
71  bool IsEnd() const { return EndI == KeyDatI; }
72 
73  const TKey& GetKey() const {Assert((KeyDatI!=NULL)&&(KeyDatI->HashCd!=-1)); return KeyDatI->Key;}
74  const TDat& GetDat() const {/*Assert((KeyDatI!=NULL)&&(KeyDatI->HashCd!=-1));*/ return KeyDatI->Dat;}
75  TDat& GetDat() {Assert((KeyDatI!=NULL)&&(KeyDatI->HashCd!=-1)); return KeyDatI->Dat;}
76 };
77 
78 //#//////////////////////////////////////////////
80 template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey> >
81 class THashMP {
82 public:
83  enum {HashPrimes=32};
84  static const unsigned int HashPrimeT[HashPrimes];
85 public:
87 private:
92 private:
94  public:
96  bool CmpKey, Asc;
97  THashMPKeyDatCmp(THashMP<TKey, TDat, THashFunc>& _Hash, const bool& _CmpKey, const bool& _Asc) :
98  Hash(_Hash), CmpKey(_CmpKey), Asc(_Asc) { }
99  bool operator () (const int& KeyId1, const int& KeyId2) const {
100  if (CmpKey) {
101  if (Asc) { return Hash.GetKey(KeyId1) < Hash.GetKey(KeyId2); }
102  else { return Hash.GetKey(KeyId2) < Hash.GetKey(KeyId1); } }
103  else {
104  if (Asc) { return Hash[KeyId1] < Hash[KeyId2]; }
105  else { return Hash[KeyId2] < Hash[KeyId1]; } } }
106  };
107 private:
108  TPHKeyDat& GetPHashKeyDat(const int& KeyId){
109  TPHKeyDat& KeyDat=Table[KeyId];
110  Assert(KeyDat.HashCd!=-1); return KeyDat;}
111  const TPHKeyDat& GetPHashKeyDat(const int& KeyId) const {
112  const TPHKeyDat& KeyDat=Table[KeyId];
113  Assert(KeyDat.HashCd!=-1); return KeyDat;}
114  uint GetNextPrime(const uint& Val) const;
115 // void Resize();
116 public:
118  Table(), NumVals(0){}
120  Table(PHash.Table), NumVals(PHash.NumVals){}
121  explicit THashMP(const int& ExpectVals) {
122  Gen(ExpectVals);}
123  explicit THashMP(TSIn& SIn):
124  Table(SIn), NumVals(SIn){
125  SIn.LoadCs();}
126  void Load(TSIn& SIn){
127  Table.Load(SIn); NumVals.Load(SIn);
128  SIn.LoadCs();}
129  void Save(TSOut& SOut) const {
130  Table.Save(SOut); NumVals.Save(SOut);
131  SOut.SaveCs();}
132 
133  THashMP& operator=(const THashMP& Hash){
134  if (this!=&Hash){
135  Table=Hash.Table; NumVals=Hash.NumVals;}
136  return *this;}
137  bool operator==(const THashMP& Hash) const; //J: zdaj tak kot je treba
138 //bool operator < (const THash& Hash) const { Fail; return true; }
139  const TDat& operator[](const int& KeyId) const {return GetPHashKeyDat(KeyId).Dat;}
140  TDat& operator[](const int& KeyId){return GetPHashKeyDat(KeyId).Dat;}
141  TDat& operator()(const TKey& Key){return AddDat(Key);}
142  ::TSize GetMemUsed() const {
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  }
152 
153  TIter BegI() const {
154  if (Len() == 0){return TIter(Table.EndI(), Table.EndI());}
155  return TIter(Table.BegI(), Table.EndI());}
156  TIter EndI() const {return TIter(Table.EndI(), Table.EndI());}
157  //TIter GetI(const int& KeyId) const {return TIter(&KeyDatV[KeyId], KeyDatV.EndI());}
158  TIter GetI(const TKey& Key) const {return TIter(&Table[GetKeyId(Key)], Table.EndI());}
159 
160  void Gen(const int& ExpectVals){
161  Table.Gen(GetNextPrime(2 * ExpectVals));}
162 
163  void Clr(const bool& DoDel=true);
164  bool Empty() const {return Len()==0;}
165  int Len() const {return NumVals;}
166  void SetLen(const int& Length) {NumVals=Length;}
167  int GetMxKeyIds() const {return Table.Len();}
168 //bool IsKeyIdEqKeyN() const {return FreeKeys==0;}
169  int GetReservedKeyIds() const {return Table.Reserved();}
170 
171  // TODO: Non-unique keys
172  int AddKey(const TKey& Key);
173  int AddKey11(const int& Idx, const TKey& Key, bool& Found);
174  int AddKey12(const int& Idx, const TKey& Key, bool& Found);
175  int AddKey13(const int& Idx, const TKey& Key);
176  int AddKey1(const TKey& Key, bool& Found);
177  int AddKey2(const int& Idx, const TKey& Key, bool& Found);
178  TDat& AddDatId(const TKey& Key){
179  int KeyId=AddKey(Key); return Table[KeyId].Dat=KeyId;}
180  // TODO: Make Dat updatable
181  TDat& AddDat(const TKey& Key){return Table[AddKey(Key)].Dat;}
182  TDat& AddDat(const TKey& Key, const TDat& Dat){
183  return Table[AddKey(Key)].Dat=Dat;}
184 
185  const TKey& GetKey(const int& KeyId) const { return GetPHashKeyDat(KeyId).Key;}
186  int GetKeyId(const TKey& Key) const;
188  int GetRndKeyId(TRnd& Rnd) const;
190  int GetRndKeyId(TRnd& Rnd, const double& EmptyFrac);
191  bool IsKey(const TKey& Key) const {return GetKeyId(Key)!=-1;}
192  bool IsKey(const TKey& Key, int& KeyId) const { KeyId=GetKeyId(Key); return KeyId!=-1;}
193  bool IsKeyId(const int& KeyId) const {
194  return (0<=KeyId)&&(KeyId<Table.Len())&&(Table[KeyId].HashCd!=-1);}
195  const TDat& GetDat(const TKey& Key) const {return Table[GetKeyId(Key)].Dat;}
196  TDat& GetDat(const TKey& Key){return Table[GetKeyId(Key)].Dat;}
197 // TKeyDatP GetKeyDat(const int& KeyId) const {
198 // TPHKeyDat& KeyDat=GetPHashKeyDat(KeyId);
199 // return TKeyDatP(KeyDat.Key, KeyDat.Dat);}
200  void GetKeyDat(const int& KeyId, TKey& Key, TDat& Dat) const {
201  const TPHKeyDat& KeyDat=GetPHashKeyDat(KeyId);
202  Key=KeyDat.Key; Dat=KeyDat.Dat;}
203  bool IsKeyGetDat(const TKey& Key, TDat& Dat) const {int KeyId;
204  if (IsKey(Key, KeyId)){Dat=GetPHashKeyDat(KeyId).Dat; return true;}
205  else {return false;}}
206 
207  int FFirstKeyId() const {return 0-1;}
208  bool FNextKeyId(int& KeyId) const;
209  void GetKeyV(TVec<TKey>& KeyV) const;
210  void GetDatV(TVec<TDat>& DatV) const;
211  void GetKeyDatPrV(TVec<TPair<TKey, TDat> >& KeyDatPrV) const;
212  void GetDatKeyPrV(TVec<TPair<TDat, TKey> >& DatKeyPrV) const;
213  void GetKeyDatKdV(TVec<TKeyDat<TKey, TDat> >& KeyDatKdV) const;
214  void GetDatKeyKdV(TVec<TKeyDat<TDat, TKey> >& DatKeyKdV) const;
215 
216  void Swap(THashMP& Hash);
217 //void Defrag();
218  void Pack(){Table.Pack();}
219 /*void Sort(const bool& CmpKey, const bool& Asc);
220  void SortByKey(const bool& Asc=true) { Sort(true, Asc); }
221  void SortByDat(const bool& Asc=true) { Sort(false, Asc); }*/
222 };
223 
224 template<class TKey, class TDat, class THashFunc>
225 const unsigned int THashMP<TKey, TDat, THashFunc>::HashPrimeT[HashPrimes]={
226  3ul, 5ul, 11ul, 23ul,
227  53ul, 97ul, 193ul, 389ul, 769ul,
228  1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
229  49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
230  1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
231  50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
232  1610612741ul, 3221225473ul, 4294967291ul
233 };
234 
235 template<class TKey, class TDat, class THashFunc>
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 }
246 
247 template<class TKey, class TDat, class THashFunc>
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 }
257 
258 template<class TKey, class TDat, class THashFunc>
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 }
275 
276 template<class TKey, class TDat, class THashFunc>
277 int THashMP<TKey, TDat, THashFunc>::AddKey11(const int& BegTableN, const TKey& Key, bool& Found) {
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 }
305 
306 template<class TKey, class TDat, class THashFunc>
307 int THashMP<TKey, TDat, THashFunc>::AddKey12(const int& BegTableN, const TKey& Key, bool& Found) {
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 }
356 
357 template<class TKey, class TDat, class THashFunc>
358 int THashMP<TKey, TDat, THashFunc>::AddKey13(const int& BegTableN, const TKey& Key) {
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 }
394 
395 template<class TKey, class TDat, class THashFunc>
396 int THashMP<TKey, TDat, THashFunc>::AddKey1(const TKey& Key, bool& Found) {
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 }
426 
427 template<class TKey, class TDat, class THashFunc>
428 int THashMP<TKey, TDat, THashFunc>::AddKey2(const int& BegTableN, const TKey& Key, bool& Found) {
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 }
457 
458 template<class TKey, class TDat, class THashFunc>
459 int THashMP<TKey, TDat, THashFunc>::GetKeyId(const TKey& Key) const {
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 }
472 
473 template<class TKey, class TDat, class THashFunc>
474 void THashMP<TKey, TDat, THashFunc>::Clr(const bool& DoDel){
475  if (DoDel){
476  Table.Clr();
477  } else {
478  Table.PutAll(TPHKeyDat());
479  }
480  NumVals = TInt(0);
481 }
482 
483 template<class TKey, class TDat, class THashFunc>
485  do {KeyId++;} while ((KeyId<Table.Len())&&(Table[KeyId].HashCd==-1));
486  return KeyId<Table.Len();
487 }
488 
489 template<class TKey, class TDat, class THashFunc>
491  KeyV.Gen(Len(), 0);
492  int KeyId=FFirstKeyId();
493  while (FNextKeyId(KeyId)){
494  KeyV.Add(GetKey(KeyId));}
495 }
496 
497 template<class TKey, class TDat, class THashFunc>
499  DatV.Gen(Len(), 0);
500  int KeyId=FFirstKeyId();
501  while (FNextKeyId(KeyId)){
502  DatV.Add(GetPHashKeyDat(KeyId).Dat);}
503 }
504 
505 template<class TKey, class TDat, class THashFunc>
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 }
515 
516 template<class TKey, class TDat, class THashFunc>
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 }
526 
527 template<class TKey, class TDat, class THashFunc>
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 }
537 
538 template<class TKey, class TDat, class THashFunc>
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 }
548 
549 template<class TKey, class TDat, class THashFunc>
551  if (this!=&Hash){
552  Table.Swap(Hash.Table);
553  ::Swap(NumVals, Hash.NumVals);
554  }
555 }
556 
557 template<class TKey, class TDat, class THashFunc>
559  printf("*** ERROR *** THashMP<TKey, TDat, THashFunc>::GetRndKeyId called\n");
560  return 0;
561 }
562 
563 template<class TKey, class TDat, class THashFunc>
564 int THashMP<TKey, TDat, THashFunc>::GetRndKeyId(TRnd& Rnd, const double& EmptyFrac) {
565  printf("*** ERROR *** THashMP<TKey, TDat, THashFunc>::GetRndKeyId called\n");
566  return 0;
567 }
568 
569 #endif // GCC_ATOMIC
570 
571 #endif // hashmp_h
TPair< TKey, TDat > TKeyDatP
Definition: hashmp.h:89
Definition: ds.h:346
THashMP(const int &ExpectVals)
Definition: hashmp.h:121
TIter GetI(const TKey &Key) const
Definition: hashmp.h:158
void Pack()
Definition: hashmp.h:218
THashMPKeyDatI(const TPHKeyDat *_KeyDatI, const TPHKeyDat *_EndI)
Definition: hashmp.h:52
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
TDat & GetDat(const TKey &Key)
Definition: hashmp.h:196
uint GetNextPrime(const uint &Val) const
Definition: hashmp.h:236
TSizeTy Reserved() const
Returns the size of allocated storage capacity.
Definition: ds.h:577
void Save(TSOut &SOut) const
Definition: hashmp.h:129
Definition: dt.h:11
void Save(TSOut &SOut) const
Definition: dt.h:1153
::TSize GetMemUsed() const
Definition: hashmp.h:142
unsigned int uint
Definition: bd.h:11
int AddKey1(const TKey &Key, bool &Found)
Definition: hashmp.h:396
const TPHKeyDat & GetPHashKeyDat(const int &KeyId) const
Definition: hashmp.h:111
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
THashMPKeyDatCmp(THashMP< TKey, TDat, THashFunc > &_Hash, const bool &_CmpKey, const bool &_Asc)
Definition: hashmp.h:97
TInt NumVals
Definition: hashmp.h:91
void SetLen(const int &Length)
Definition: hashmp.h:166
THashMPKeyDat(TSIn &SIn)
Definition: hashmp.h:22
void GetKeyV(TVec< TKey > &KeyV) const
Definition: hashmp.h:490
THashMP(TSIn &SIn)
Definition: hashmp.h:123
bool operator()(const int &KeyId1, const int &KeyId2) const
Definition: hashmp.h:99
const TDat & operator[](const int &KeyId) const
Definition: hashmp.h:139
void Load(TSIn &SIn)
Definition: ds.h:946
TSizeTy GetMemUsed() const
Returns the memory footprint (the number of bytes) of the vector.
Definition: ds.h:511
THashMP & operator=(const THashMP &Hash)
Definition: hashmp.h:133
virtual void LoadCs()
Definition: fl.cpp:28
TKey Key
Definition: hashmp.h:15
bool IsKeyId(const int &KeyId) const
Definition: hashmp.h:193
TDat & AddDatId(const TKey &Key)
Definition: hashmp.h:178
Definition: fl.h:58
void Save(TSOut &SOut) const
Definition: ds.h:954
TInt HashCd
Definition: hashmp.h:14
THashMPKeyDat & operator=(const THashMPKeyDat &HashKeyDat)
Definition: hashmp.h:31
THashMPKeyDatI & Next()
Definition: hashmp.h:66
bool IsKey(const TKey &Key, int &KeyId) const
Definition: hashmp.h:192
THashMPKeyDatI & operator=(const THashMPKeyDatI &HashKeyDatI)
Definition: hashmp.h:55
THashMPKeyDatI(const THashMPKeyDatI &_HashKeyDatI)
Definition: hashmp.h:50
TIter EndI() const
Definition: hashmp.h:156
TPHKeyDat * EndI
Definition: hashmp.h:47
THashMPKeyDatI()
Definition: hashmp.h:49
THashMPKeyDat()
Definition: hashmp.h:18
void Swap(THashMP &Hash)
Definition: hashmp.h:550
void GetDatKeyKdV(TVec< TKeyDat< TDat, TKey > > &DatKeyKdV) const
Definition: hashmp.h:539
void SaveCs()
Definition: fl.h:171
static const unsigned int HashPrimeT[HashPrimes]
Definition: hashmp.h:84
int AddKey2(const int &Idx, const TKey &Key, bool &Found)
Definition: hashmp.h:428
const THashMP< TKey, TDat, THashFunc > & Hash
Definition: hashmp.h:95
bool operator<(const THashMPKeyDatI &HashKeyDatI) const
Definition: hashmp.h:59
size_t TSize
Definition: bd.h:58
void Load(TSIn &SIn)
Definition: dt.h:1152
#define Assert(Cond)
Definition: bd.h:251
int GetMxKeyIds() const
Definition: hashmp.h:167
void GetDatKeyPrV(TVec< TPair< TDat, TKey > > &DatKeyPrV) const
Definition: hashmp.h:517
bool IsKey(const TKey &Key) const
Definition: hashmp.h:191
int AddKey11(const int &Idx, const TKey &Key, bool &Found)
Definition: hashmp.h:277
bool FNextKeyId(int &KeyId) const
Definition: hashmp.h:484
Definition: fl.h:128
THashMPKeyDat< TKey, TDat > TPHKeyDat
Definition: hashmp.h:88
THashMPKeyDat(const int &_HashCd, const TKey &_Key)
Definition: hashmp.h:20
THashMPKeyDat< TKey, TDat > TPHKeyDat
Definition: hashmp.h:44
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: hashmp.h:203
Definition: dt.h:1137
THashMP()
Definition: hashmp.h:117
TDat & GetDat()
Definition: hashmp.h:75
void Load(TSIn &SIn)
Definition: hashmp.h:126
bool IsEmpty() const
Tests whether the iterator has been initialized.
Definition: hashmp.h:69
int GetReservedKeyIds() const
Definition: hashmp.h:169
TVec< TPHKeyDat > Table
Definition: hashmp.h:90
TPHKeyDat * operator->() const
Definition: hashmp.h:65
Definition: hash.h:681
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...
Definition: hashmp.h:558
Definition: ds.h:32
void Gen(const int &ExpectVals)
Definition: hashmp.h:160
TDat Dat
Definition: hashmp.h:16
TPHKeyDat & operator*() const
Definition: hashmp.h:63
TIter BegI() const
Definition: hashmp.h:153
THashMP(const THashMP &PHash)
Definition: hashmp.h:119
long long int64
Definition: bd.h:27
bool IsEnd() const
Tests whether the iterator is pointing to the past-end element.
Definition: hashmp.h:71
TDat & operator()(const TKey &Key)
Definition: hashmp.h:141
TIter BegI() const
Returns an iterator pointing to the first element in the vector.
Definition: ds.h:593
void Pack()
Reduces vector capacity (frees memory) to match its size.
Definition: ds.h:1057
const TKey & GetKey() const
Definition: hashmp.h:73
int FFirstKeyId() const
Definition: hashmp.h:207
const TDat & GetDat() const
Definition: hashmp.h:74
Hash-Table with multiprocessing support.
Definition: hashmp.h:81
bool operator==(const THashMPKeyDatI &HashKeyDatI) const
Definition: hashmp.h:57
void Clr(const bool &DoDel=true)
Definition: hashmp.h:474
void GetKeyDatKdV(TVec< TKeyDat< TKey, TDat > > &KeyDatKdV) const
Definition: hashmp.h:528
TDat & AddDat(const TKey &Key, const TDat &Dat)
Definition: hashmp.h:182
int AddKey(const TKey &Key)
Definition: hashmp.h:259
bool Empty() const
Definition: hashmp.h:164
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
int AddKey12(const int &Idx, const TKey &Key, bool &Found)
Definition: hashmp.h:307
bool operator==(const THashMP &Hash) const
Definition: hashmp.h:248
int AddKey13(const int &Idx, const TKey &Key)
Definition: hashmp.h:358
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hashmp.h:200
TDat & operator[](const int &KeyId)
Definition: hashmp.h:140
TPHKeyDat * KeyDatI
Definition: hashmp.h:46
THashMPKeyDatI & operator++(int)
Definition: hashmp.h:61
THashMPKeyDatI< TKey, TDat > TIter
Definition: hashmp.h:86
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
TDat & AddDat(const TKey &Key)
Definition: hashmp.h:181
TPHKeyDat & operator()() const
Definition: hashmp.h:64
int GetKeyId(const TKey &Key) const
Definition: hashmp.h:459
bool operator==(const THashMPKeyDat &HashKeyDat) const
Definition: hashmp.h:27
const TDat & GetDat(const TKey &Key) const
Definition: hashmp.h:195
void GetKeyDatPrV(TVec< TPair< TKey, TDat > > &KeyDatPrV) const
Definition: hashmp.h:506
TPHKeyDat & GetPHashKeyDat(const int &KeyId)
Definition: hashmp.h:108
THashMPKeyDatI & operator--(int)
Definition: hashmp.h:62
void GetDatV(TVec< TDat > &DatV) const
Definition: hashmp.h:498
void Swap(TRec &Rec1, TRec &Rec2)
Definition: bd.h:568
Vector is a sequence TVal objects representing an array that can change in size.
Definition: ds.h:430
void Save(TSOut &SOut) const
Definition: hashmp.h:24
int Len() const
Definition: hashmp.h:165
const TKey & GetKey(const int &KeyId) const
Definition: hashmp.h:185