SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
hash.h
Go to the documentation of this file.
1 #include "bd.h"
2 #include <stdio.h>
3 
5 // Hash-Table-Key-Data
6 #pragma pack(push, 1) // pack class size
7 template <class TKey, class TDat>
8 class THashKeyDat{
9 public:
12  TKey Key;
13  TDat Dat;
14 public:
16  Next(-1), HashCd(-1), Key(), Dat(){}
17  THashKeyDat(const int& _Next, const int& _HashCd, const TKey& _Key):
18  Next(_Next), HashCd(_HashCd), Key(_Key), Dat(){}
19  explicit THashKeyDat(TSIn& SIn):
20  Next(SIn), HashCd(SIn), Key(SIn), Dat(SIn){}
21  void Save(TSOut& SOut) const {
22  Next.Save(SOut); HashCd.Save(SOut); Key.Save(SOut); Dat.Save(SOut);}
23  void LoadXml(const PXmlTok& XmlTok, const TStr& Nm="");
24  void SaveXml(TSOut& SOut, const TStr& Nm) const;
25 
26  template<typename TDatFunctor>
27  void LoadShM(TShMIn& ShMIn, TDatFunctor LoadDatFromShared) {
28  Next = TInt(ShMIn);
29  HashCd = TInt(ShMIn);
30  TKey K(ShMIn);
31  Key = K;
32  LoadDatFromShared(&Dat, ShMIn);
33  }
34  bool operator==(const THashKeyDat& HashKeyDat) const {
35  if (this==&HashKeyDat || (HashCd==HashKeyDat.HashCd
36  && Key==HashKeyDat.Key && Dat==HashKeyDat.Dat)){return true;}
37  return false;}
38  THashKeyDat& operator=(const THashKeyDat& HashKeyDat){
39  if (this!=&HashKeyDat){
40  Next=HashKeyDat.Next; HashCd=HashKeyDat.HashCd;
41  Key=HashKeyDat.Key; Dat=HashKeyDat.Dat;}
42  return *this;}
43 };
44 #pragma pack(pop)
45 
47 // Hash-Table-Key-Data-Iterator
48 template<class TKey, class TDat>
50 public:
52 private:
53  THKeyDat* KeyDatI;
54  THKeyDat* EndI;
55 public:
56  THashKeyDatI(): KeyDatI(NULL), EndI(NULL){}
57  THashKeyDatI(const THashKeyDatI& _HashKeyDatI):
58  KeyDatI(_HashKeyDatI.KeyDatI), EndI(_HashKeyDatI.EndI){}
59  THashKeyDatI(const THKeyDat* _KeyDatI, const THKeyDat* _EndI):
60  KeyDatI((THKeyDat*)_KeyDatI), EndI((THKeyDat*)_EndI){}
61 
62  THashKeyDatI& operator=(const THashKeyDatI& HashKeyDatI){
63  KeyDatI=HashKeyDatI.KeyDatI; EndI=HashKeyDatI.EndI; return *this;}
64  bool operator==(const THashKeyDatI& HashKeyDatI) const {
65  return KeyDatI==HashKeyDatI.KeyDatI;}
66  bool operator<(const THashKeyDatI& HashKeyDatI) const {
67  return KeyDatI<HashKeyDatI.KeyDatI;}
68  THashKeyDatI& operator++(int){ KeyDatI++; while (KeyDatI < EndI && KeyDatI->HashCd==-1) { KeyDatI++; } return *this; }
69  THashKeyDatI& operator--(int){ do { KeyDatI--; } while (KeyDatI->HashCd==-1); return *this;}
70  THKeyDat& operator*() const { return *KeyDatI; }
71  THKeyDat& operator()() const { return *KeyDatI; }
72  THKeyDat* operator->() const { return KeyDatI; }
73  THashKeyDatI& Next(){ operator++(1); return *this; }
74 
76  bool IsEmpty() const { return KeyDatI == NULL; }
78  bool IsEnd() const { return EndI == KeyDatI; }
79 
80  const TKey& GetKey() const {Assert((KeyDatI!=NULL)&&(KeyDatI->HashCd!=-1)); return KeyDatI->Key;}
81  const TDat& GetDat() const {Assert((KeyDatI!=NULL)&&(KeyDatI->HashCd!=-1)); return KeyDatI->Dat;}
82  TDat& GetDat() {Assert((KeyDatI!=NULL)&&(KeyDatI->HashCd!=-1)); return KeyDatI->Dat;}
83 };
84 
86 // Default-Hash-Function
87 template<class TKey>
89 public:
90  static inline int GetPrimHashCd(const TKey& Key) { return Key.GetPrimHashCd(); }
91  static inline int GetSecHashCd(const TKey& Key) { return Key.GetSecHashCd(); }
92 };
93 
95 // Hash-Table
96 template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey> >
97 class THash{
98 public:
99  enum {HashPrimes=32};
100  static const unsigned int HashPrimeT[HashPrimes];
101 public:
103 private:
110 private:
112  public:
114  bool CmpKey, Asc;
115  THashKeyDatCmp(THash<TKey, TDat, THashFunc>& _Hash, const bool& _CmpKey, const bool& _Asc) :
116  Hash(_Hash), CmpKey(_CmpKey), Asc(_Asc) { }
117  bool operator () (const int& KeyId1, const int& KeyId2) const {
118  if (CmpKey) {
119  if (Asc) { return Hash.GetKey(KeyId1) < Hash.GetKey(KeyId2); }
120  else { return Hash.GetKey(KeyId2) < Hash.GetKey(KeyId1); } }
121  else {
122  if (Asc) { return Hash[KeyId1] < Hash[KeyId2]; }
123  else { return Hash[KeyId2] < Hash[KeyId1]; } } }
124  };
125 
126  template<typename TDatInitFn>
128  private:
129  TDatInitFn DatInitFn;
130  public:
131  TLoadTHKeyDatInitializer(TDatInitFn Fn) { DatInitFn = Fn;}
132  void operator() (THKeyDat* HKeyDat, TShMIn& ShMIn) { HKeyDat->LoadShM(ShMIn, DatInitFn);}
133  };
134 
135 private:
136  THKeyDat& GetHashKeyDat(const int& KeyId){
137  THKeyDat& KeyDat=KeyDatV[KeyId];
138  Assert(KeyDat.HashCd!=-1); return KeyDat;}
139  const THKeyDat& GetHashKeyDat(const int& KeyId) const {
140  const THKeyDat& KeyDat=KeyDatV[KeyId];
141  Assert(KeyDat.HashCd!=-1); return KeyDat;}
142  uint GetNextPrime(const uint& Val) const;
143  void Resize();
144 public:
145  THash():
146  PortV(), KeyDatV(),
147  AutoSizeP(true), FFreeKeyId(-1), FreeKeys(0){}
148  THash(const THash& Hash):
149  PortV(Hash.PortV), KeyDatV(Hash.KeyDatV), AutoSizeP(Hash.AutoSizeP),
150  FFreeKeyId(Hash.FFreeKeyId), FreeKeys(Hash.FreeKeys){}
151  explicit THash(const int& ExpectVals, const bool& _AutoSizeP=false);
152  explicit THash(TSIn& SIn):
153  PortV(SIn), KeyDatV(SIn),
154  AutoSizeP(SIn), FFreeKeyId(SIn), FreeKeys(SIn){
155  SIn.LoadCs();}
157  void LoadShM(TShMIn& ShMIn) {
158  PortV.LoadShM(ShMIn);
159  KeyDatV.Load(ShMIn);
160  AutoSizeP=TBool(ShMIn);
161  FFreeKeyId=TInt(ShMIn);
162  FreeKeys=TInt(ShMIn);
163  ShMIn.LoadCs();
164  }
166  template <typename TDatInitFn>
167  void LoadShM(TShMIn& ShMIn, TDatInitFn Fn) {
168  TLoadTHKeyDatInitializer<TDatInitFn> HKeyDatFn(Fn);
169  PortV.LoadShM(ShMIn);
170  KeyDatV.LoadShM(ShMIn, HKeyDatFn);
171  AutoSizeP=TBool(ShMIn);
172  FFreeKeyId=TInt(ShMIn);
173  FreeKeys=TInt(ShMIn);
174  ShMIn.LoadCs();
175  }
176 
177  void Load(TSIn& SIn){
178  PortV.Load(SIn); KeyDatV.Load(SIn);
179  AutoSizeP=TBool(SIn); FFreeKeyId=TInt(SIn); FreeKeys=TInt(SIn);
180  SIn.LoadCs();
181  }
182 
183  void Save(TSOut& SOut) const {
184  PortV.Save(SOut); KeyDatV.Save(SOut);
185  AutoSizeP.Save(SOut); FFreeKeyId.Save(SOut); FreeKeys.Save(SOut);
186  SOut.SaveCs();}
187  void LoadXml(const PXmlTok& XmlTok, const TStr& Nm="");
188  void SaveXml(TSOut& SOut, const TStr& Nm);
189 
190  THash& operator=(const THash& Hash){
191  if (this!=&Hash){
192  PortV=Hash.PortV; KeyDatV=Hash.KeyDatV; AutoSizeP=Hash.AutoSizeP;
193  FFreeKeyId=Hash.FFreeKeyId; FreeKeys=Hash.FreeKeys;}
194  return *this;}
195  bool operator==(const THash& Hash) const; //J: zdaj tak kot je treba
196  bool operator < (const THash& Hash) const { Fail; return true; }
198  const TDat& operator[](const int& KeyId) const {return GetHashKeyDat(KeyId).Dat;}
199  TDat& operator[](const int& KeyId){return GetHashKeyDat(KeyId).Dat;}
200  TDat& operator()(const TKey& Key){return AddDat(Key);}
201  ::TSize GetMemUsed() const {
202  // return PortV.GetMemUsed()+KeyDatV.GetMemUsed()+sizeof(bool)+2*sizeof(int);}
203  int64 MemUsed = sizeof(bool)+2*sizeof(int);
204  MemUsed += int64(PortV.Reserved()) * int64(sizeof(TInt));
205  for (int KeyDatN = 0; KeyDatN < KeyDatV.Len(); KeyDatN++) {
206  MemUsed += int64(2 * sizeof(TInt));
207  MemUsed += int64(KeyDatV[KeyDatN].Key.GetMemUsed());
208  MemUsed += int64(KeyDatV[KeyDatN].Dat.GetMemUsed());
209  }
210  return ::TSize(MemUsed);
211  }
212 
213  TIter BegI() const {
214  if (Len() == 0){return TIter(KeyDatV.EndI(), KeyDatV.EndI());}
215  if (IsKeyIdEqKeyN()) { return TIter(KeyDatV.BegI(), KeyDatV.EndI());}
216  int FKeyId=-1; FNextKeyId(FKeyId);
217  return TIter(KeyDatV.BegI()+FKeyId, KeyDatV.EndI()); }
218  TIter EndI() const {return TIter(KeyDatV.EndI(), KeyDatV.EndI());}
219  //TIter GetI(const int& KeyId) const {return TIter(&KeyDatV[KeyId], KeyDatV.EndI());}
220  TIter GetI(const TKey& Key) const {return TIter(&KeyDatV[GetKeyId(Key)], KeyDatV.EndI());}
221 
222  void Gen(const int& ExpectVals){
223  PortV.Gen(GetNextPrime(ExpectVals/2)); KeyDatV.Gen(ExpectVals, 0);
224  FFreeKeyId=-1; FreeKeys=0; PortV.PutAll(TInt(-1));}
225 
226  void Clr(const bool& DoDel=true, const int& NoDelLim=-1, const bool& ResetDat=true);
227  bool Empty() const {return Len()==0;}
228  int Len() const {return KeyDatV.Len()-FreeKeys;}
229  int GetPorts() const {return PortV.Len();}
230  bool IsAutoSize() const {return AutoSizeP;}
231  int GetMxKeyIds() const {return KeyDatV.Len();}
232  int GetReservedKeyIds() const {return KeyDatV.Reserved();}
233  bool IsKeyIdEqKeyN() const {return FreeKeys==0;}
234 
235  int AddKey(const TKey& Key);
236  TDat& AddDatId(const TKey& Key){
237  int KeyId=AddKey(Key); return KeyDatV[KeyId].Dat=KeyId;}
238  TDat& AddDat(const TKey& Key){return KeyDatV[AddKey(Key)].Dat;}
239  TDat& AddDat(const TKey& Key, const TDat& Dat){
240  return KeyDatV[AddKey(Key)].Dat=Dat;}
241 
242  void DelKey(const TKey& Key);
243  bool DelIfKey(const TKey& Key){
244  int KeyId; if (IsKey(Key, KeyId)){DelKeyId(KeyId); return true;} return false;}
245  void DelKeyId(const int& KeyId){DelKey(GetKey(KeyId));}
246  void DelKeyIdV(const TIntV& KeyIdV){
247  for (int KeyIdN=0; KeyIdN<KeyIdV.Len(); KeyIdN++){DelKeyId(KeyIdV[KeyIdN]);}}
248 
249  void MarkDelKey(const TKey& Key); // marks the record as deleted - doesn't delete Dat (to avoid fragmentation)
250  void MarkDelKeyId(const int& KeyId){MarkDelKey(GetKey(KeyId));}
251 
252  const TKey& GetKey(const int& KeyId) const { return GetHashKeyDat(KeyId).Key;}
253  int GetKeyId(const TKey& Key) const;
255  int GetRndKeyId(TRnd& Rnd) const;
257  int GetRndKeyId(TRnd& Rnd, const double& EmptyFrac);
258  bool IsKey(const TKey& Key) const {return GetKeyId(Key)!=-1;}
259  bool IsKey(const TKey& Key, int& KeyId) const { KeyId=GetKeyId(Key); return KeyId!=-1;}
260  bool IsKeyId(const int& KeyId) const {
261  return (0<=KeyId)&&(KeyId<KeyDatV.Len())&&(KeyDatV[KeyId].HashCd!=-1);}
262  const TDat& GetDat(const TKey& Key) const {return KeyDatV[GetKeyId(Key)].Dat;}
263  TDat& GetDat(const TKey& Key){return KeyDatV[GetKeyId(Key)].Dat;}
264  TDat GetDatWithDefault(const TKey& Key, TDat DefaultValue) {
265  int KeyId = GetKeyId(Key);
266  return KeyId >= 0 ? KeyDatV[KeyId].Dat : DefaultValue;
267  }
268 // TKeyDatP GetKeyDat(const int& KeyId) const {
269 // TKeyDat& KeyDat=GetHashKeyDat(KeyId);
270 // return TKeyDatP(KeyDat.Key, KeyDat.Dat);}
271  void GetKeyDat(const int& KeyId, TKey& Key, TDat& Dat) const {
272  const THKeyDat& KeyDat=GetHashKeyDat(KeyId);
273  Key=KeyDat.Key; Dat=KeyDat.Dat;}
274  bool IsKeyGetDat(const TKey& Key, TDat& Dat) const {int KeyId;
275  if (IsKey(Key, KeyId)){Dat=GetHashKeyDat(KeyId).Dat; return true;}
276  else {return false;}}
277 
278  int FFirstKeyId() const {return 0-1;}
279  bool FNextKeyId(int& KeyId) const;
280  void GetKeyV(TVec<TKey>& KeyV) const;
281  void GetDatV(TVec<TDat>& DatV) const;
282  void GetKeyDatPrV(TVec<TPair<TKey, TDat> >& KeyDatPrV) const;
283  void GetDatKeyPrV(TVec<TPair<TDat, TKey> >& DatKeyPrV) const;
284  void GetKeyDatKdV(TVec<TKeyDat<TKey, TDat> >& KeyDatKdV) const;
285  void GetDatKeyKdV(TVec<TKeyDat<TDat, TKey> >& DatKeyKdV) const;
286 
287  void Swap(THash& Hash);
288  void Defrag();
289  void Pack(){KeyDatV.Pack();}
290  void Sort(const bool& CmpKey, const bool& Asc);
291  void SortByKey(const bool& Asc=true) { Sort(true, Asc); }
292  void SortByDat(const bool& Asc=true) { Sort(false, Asc); }
293 };
294 
295 template<class TKey, class TDat, class THashFunc>
296 const unsigned int THash<TKey, TDat, THashFunc>::HashPrimeT[HashPrimes]={
297  3ul, 5ul, 11ul, 23ul,
298  53ul, 97ul, 193ul, 389ul, 769ul,
299  1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
300  49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
301  1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
302  50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
303  1610612741ul, 3221225473ul, 4294967291ul
304 };
305 
306 template<class TKey, class TDat, class THashFunc>
308  const uint* f=(const uint*)HashPrimeT, *m, *l=(const uint*)HashPrimeT + (int)HashPrimes;
309  int h, len = (int)HashPrimes;
310  while (len > 0) {
311  h = len >> 1; m = f + h;
312  if (*m < Val) { f = m; f++; len = len - h - 1; }
313  else len = h;
314  }
315  return f == l ? *(l - 1) : *f;
316 }
317 
318 template<class TKey, class TDat, class THashFunc>
320  // resize & initialize port vector
321  //if (PortV.Len()==0){PortV.Gen(17);}
322  //else {PortV.Gen(2*PortV.Len()+1);}
323  if (PortV.Len()==0){
324  PortV.Gen(17);
325  } else if (AutoSizeP&&(KeyDatV.Len()>2*PortV.Len())){
326  PortV.Gen(GetNextPrime(PortV.Len()+1));
327  } else {
328  return;
329  }
330  PortV.PutAll(TInt(-1));
331  // rehash keys
332  for (int KeyId=0; KeyId<KeyDatV.Len(); KeyId++){
333  THKeyDat& KeyDat=KeyDatV[KeyId];
334  if (KeyDat.HashCd!=-1){
335  const int PortN = abs(THashFunc::GetPrimHashCd(KeyDat.Key) % PortV.Len());
336  KeyDat.Next=PortV[PortN];
337  PortV[PortN]=KeyId;
338  }
339  }
340 }
341 
342 template<class TKey, class TDat, class THashFunc>
343 THash<TKey, TDat, THashFunc>::THash(const int& ExpectVals, const bool& _AutoSizeP):
344  PortV(GetNextPrime(ExpectVals/2)), KeyDatV(ExpectVals, 0),
345  AutoSizeP(_AutoSizeP), FFreeKeyId(-1), FreeKeys(0){
346  PortV.PutAll(TInt(-1));
347 }
348 
349 template<class TKey, class TDat, class THashFunc>
351  if (Len() != Hash.Len()) { return false; }
352  for (int i = FFirstKeyId(); FNextKeyId(i); ) {
353  const TKey& Key = GetKey(i);
354  if (! Hash.IsKey(Key)) { return false; }
355  if (GetDat(Key) != Hash.GetDat(Key)) { return false; }
356  }
357  return true;
358 }
359 
360 template<class TKey, class TDat, class THashFunc>
361 void THash<TKey, TDat, THashFunc>::Clr(const bool& DoDel, const int& NoDelLim, const bool& ResetDat){
362  if (DoDel){
363  PortV.Clr(); KeyDatV.Clr();
364  } else {
365  PortV.PutAll(TInt(-1));
366  KeyDatV.Clr(DoDel, NoDelLim);
367  if (ResetDat){KeyDatV.PutAll(THKeyDat());}
368  }
369  FFreeKeyId=TInt(-1); FreeKeys=TInt(0);
370 }
371 
372 template<class TKey, class TDat, class THashFunc>
374  if ((KeyDatV.Len()>2*PortV.Len())||PortV.Empty()){Resize();}
375  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
376  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
377  int PrevKeyId=-1;
378  int KeyId=PortV[PortN];
379  while ((KeyId!=-1) &&
380  !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
381  PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}
382 
383  if (KeyId==-1){
384  if (FFreeKeyId==-1){
385  KeyId=KeyDatV.Add(THKeyDat(-1, HashCd, Key));
386  } else {
387  KeyId=FFreeKeyId; FFreeKeyId=KeyDatV[FFreeKeyId].Next; FreeKeys--;
388  //KeyDatV[KeyId]=TKeyDat(-1, HashCd, Key); // slow version
389  KeyDatV[KeyId].Next=-1;
390  KeyDatV[KeyId].HashCd=HashCd;
391  KeyDatV[KeyId].Key=Key;
392  //KeyDatV[KeyId].Dat=TDat(); // already empty
393  }
394  if (PrevKeyId==-1){
395  PortV[PortN]=KeyId;
396  } else {
397  KeyDatV[PrevKeyId].Next=KeyId;
398  }
399  }
400  return KeyId;
401 }
402 
403 template<class TKey, class TDat, class THashFunc>
405  IAssert(!PortV.Empty());
406  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
407  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
408  int PrevKeyId=-1;
409  int KeyId=PortV[PortN];
410 
411  while ((KeyId!=-1) &&
412  !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
413  PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}
414 
415  //IAssertR(KeyId!=-1, Key.GetStr()); //J: some classes do not provide GetStr()?
416  IAssert(KeyId!=-1); //J: some classes do not provide GetStr()?
417  if (PrevKeyId==-1){PortV[PortN]=KeyDatV[KeyId].Next;}
418  else {KeyDatV[PrevKeyId].Next=KeyDatV[KeyId].Next;}
419  KeyDatV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
420  KeyDatV[KeyId].HashCd=TInt(-1);
421  KeyDatV[KeyId].Key=TKey();
422  KeyDatV[KeyId].Dat=TDat();
423 }
424 
425 template<class TKey, class TDat, class THashFunc>
427  // MarkDelKey is same as Delkey except last two lines
428  IAssert(!PortV.Empty());
429  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
430  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
431  int PrevKeyId=-1;
432  int KeyId=PortV[PortN];
433  while ((KeyId!=-1) &&
434  !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
435  PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}
436  IAssertR(KeyId!=-1, Key.GetStr());
437  if (PrevKeyId==-1){PortV[PortN]=KeyDatV[KeyId].Next;}
438  else {KeyDatV[PrevKeyId].Next=KeyDatV[KeyId].Next;}
439  KeyDatV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
440  KeyDatV[KeyId].HashCd=TInt(-1);
441 }
442 
443 template<class TKey, class TDat, class THashFunc>
445  IAssert(! Empty());
446  int KeyId = abs(Rnd.GetUniDevInt(KeyDatV.Len()));
447  while (KeyDatV[KeyId].HashCd == -1) { // if the index is empty, just try again
448  KeyId = abs(Rnd.GetUniDevInt(KeyDatV.Len())); }
449  return KeyId;
450 }
451 
452 // return random KeyId even if the hash table contains deleted keys
453 // defrags the table if necessary
454 template<class TKey, class TDat, class THashFunc>
455 int THash<TKey, TDat, THashFunc>::GetRndKeyId(TRnd& Rnd, const double& EmptyFrac) {
456  IAssert(! Empty());
457  if (FreeKeys/double(Len()+FreeKeys) > EmptyFrac) { Defrag(); }
458  int KeyId = Rnd.GetUniDevInt(KeyDatV.Len());
459  while (KeyDatV[KeyId].HashCd == -1) { // if the index is empty, just try again
460  KeyId = Rnd.GetUniDevInt(KeyDatV.Len());
461  }
462  return KeyId;
463 }
464 
465 template<class TKey, class TDat, class THashFunc>
466 int THash<TKey, TDat, THashFunc>::GetKeyId(const TKey& Key) const {
467  if (PortV.Empty()){return -1;}
468  const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
469  const int HashCd=abs(THashFunc::GetSecHashCd(Key));
470  int KeyId=PortV[PortN];
471  while ((KeyId!=-1) &&
472  !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
473  KeyId=KeyDatV[KeyId].Next;}
474  return KeyId;
475 }
476 
477 template<class TKey, class TDat, class THashFunc>
479  do {KeyId++;} while ((KeyId<KeyDatV.Len()) && (KeyDatV[KeyId].HashCd==-1));
480  return KeyId<KeyDatV.Len();
481 }
482 
483 template<class TKey, class TDat, class THashFunc>
485  KeyV.Gen(Len(), 0);
486  int KeyId=FFirstKeyId();
487  while (FNextKeyId(KeyId)){
488  KeyV.Add(GetKey(KeyId));}
489 }
490 
491 template<class TKey, class TDat, class THashFunc>
493  DatV.Gen(Len(), 0);
494  int KeyId=FFirstKeyId();
495  while (FNextKeyId(KeyId)){
496  DatV.Add(GetHashKeyDat(KeyId).Dat);}
497 }
498 
499 template<class TKey, class TDat, class THashFunc>
501  KeyDatPrV.Gen(Len(), 0);
502  TKey Key; TDat Dat;
503  int KeyId=FFirstKeyId();
504  while (FNextKeyId(KeyId)){
505  GetKeyDat(KeyId, Key, Dat);
506  KeyDatPrV.Add(TPair<TKey, TDat>(Key, Dat));
507  }
508 }
509 
510 template<class TKey, class TDat, class THashFunc>
512  DatKeyPrV.Gen(Len(), 0);
513  TKey Key; TDat Dat;
514  int KeyId=FFirstKeyId();
515  while (FNextKeyId(KeyId)){
516  GetKeyDat(KeyId, Key, Dat);
517  DatKeyPrV.Add(TPair<TDat, TKey>(Dat, Key));
518  }
519 }
520 
521 template<class TKey, class TDat, class THashFunc>
523  KeyDatKdV.Gen(Len(), 0);
524  TKey Key; TDat Dat;
525  int KeyId=FFirstKeyId();
526  while (FNextKeyId(KeyId)){
527  GetKeyDat(KeyId, Key, Dat);
528  KeyDatKdV.Add(TKeyDat<TKey, TDat>(Key, Dat));
529  }
530 }
531 
532 template<class TKey, class TDat, class THashFunc>
534  DatKeyKdV.Gen(Len(), 0);
535  TKey Key; TDat Dat;
536  int KeyId=FFirstKeyId();
537  while (FNextKeyId(KeyId)){
538  GetKeyDat(KeyId, Key, Dat);
539  DatKeyKdV.Add(TKeyDat<TDat, TKey>(Dat, Key));
540  }
541 }
542 
543 template<class TKey, class TDat, class THashFunc>
545  if (this!=&Hash){
546  PortV.Swap(Hash.PortV);
547  KeyDatV.Swap(Hash.KeyDatV);
548  ::Swap(AutoSizeP, Hash.AutoSizeP);
549  ::Swap(FFreeKeyId, Hash.FFreeKeyId);
550  ::Swap(FreeKeys, Hash.FreeKeys);
551  }
552 }
553 
554 template<class TKey, class TDat, class THashFunc>
556  if (!IsKeyIdEqKeyN()){
557  THash<TKey, TDat, THashFunc> Hash(PortV.Len());
558  int KeyId=FFirstKeyId(); TKey Key; TDat Dat;
559  while (FNextKeyId(KeyId)){
560  GetKeyDat(KeyId, Key, Dat);
561  Hash.AddDat(Key, Dat);
562  }
563  Pack();
564  operator=(Hash);
565  IAssert(IsKeyIdEqKeyN());
566  }
567 }
568 
569 template<class TKey, class TDat, class THashFunc>
570 void THash<TKey, TDat, THashFunc>::Sort(const bool& CmpKey, const bool& Asc) {
571  IAssertR(IsKeyIdEqKeyN(), "THash::Sort only works when table has no deleted keys.");
572  TIntV TargV(Len()), MapV(Len()), StateV(Len());
573  for (int i = 0; i < TargV.Len(); i++) {
574  TargV[i] = i; MapV[i] = i; StateV[i] = i;
575  }
576  // sort KeyIds
577  THashKeyDatCmp HashCmp(*this, CmpKey, Asc);
578  TargV.SortCmp(HashCmp);
579  // now sort the update vector
581  for (int i = 0; i < TargV.Len()-1; i++) {
582  const int SrcPos = MapV[TargV[i]];
583  const int Loc = i;
584  // swap data
585  Tmp = KeyDatV[SrcPos];
586  KeyDatV[SrcPos] = KeyDatV[Loc];
587  KeyDatV[Loc] = Tmp;
588  // swap keys
589  MapV[StateV[i]] = SrcPos;
590  StateV.Swap(Loc, SrcPos);
591  }
592  for (int i = 0; i < TargV.Len(); i++) {
593  MapV[TargV[i]] = i; }
594  for (int p = 0; p < PortV.Len(); p++) {
595  if (PortV[p] != -1) {
596  PortV[p] = MapV[PortV[p]]; } }
597  for (int i = 0; i < KeyDatV.Len(); i++) {
598  if (KeyDatV[i].Next != -1) {
599  KeyDatV[i].Next = MapV[KeyDatV[i].Next]; }
600  }
601 }
602 
604 // Common-Hash-Types
677 
679 // Hash-Pointer
680 template <class TKey, class TDat>
681 class PHash{
682 private:
684 public:
686 public:
689  return new PHash<TKey, TDat>();}
690  PHash<TKey, TDat>(const int& MxVals, const int& Vals): H(MxVals, Vals){}
691  static TPt<PHash<TKey, TDat> > New(const int& MxVals, const int& Vals){
692  return new PHash<TKey, TDat>(MxVals, Vals);}
695  return new PHash<TKey, TDat>(H);}
696  explicit PHash<TKey, TDat>(TSIn& SIn): H(SIn){}
697  static TPt<PHash<TKey, TDat> > Load(TSIn& SIn){return new PHash<TKey, TDat>(SIn);}
698  void Save(TSOut& SOut) const {H.Save(SOut);}
699 
701  if (this!=&Vec){H=Vec.H;} return *this;}
702  bool operator==(const PHash<TKey, TDat>& Vec) const {return H==Vec.H;}
703  bool operator<(const PHash<TKey, TDat>& Vec) const {return H<Vec.H;}
704 
705  friend class TPt<PHash<TKey, TDat> >;
706 };
707 
709 // Big-String-Pool (holds up to 2 giga strings, storage overhead is 8(4) bytes per string)
710 //J: have to put it here since it uses TVec (can't be in dt.h)
712 private:
713  TSize MxBfL, BfL;
714  uint GrowBy;
715  char *Bf;
716  TVec<TSize> IdOffV; // string ID to offset
717  bool IsShM; //True if BigStrPool backed by shared memory
718 private:
719  void Resize(TSize _MxBfL);
720  void LoadPoolShM(TShMIn& ShMIn, bool LoadCompact = true);
721 public:
722  TBigStrPool(TSize MxBfLen = 0, uint _GrowBy = 16*1024*1024);
723  TBigStrPool(TSIn& SIn, bool LoadCompact = true);
724  TBigStrPool(const TBigStrPool& Pool) : MxBfL(Pool.MxBfL), BfL(Pool.BfL), GrowBy(Pool.GrowBy) {
725  Bf = (char *) malloc(Pool.MxBfL); IAssert(Bf); memcpy(Bf, Pool.Bf, Pool.BfL); }
726  ~TBigStrPool() { if (Bf && !IsShM) free(Bf); else IAssert(MxBfL == 0 || IsShM); MxBfL = 0; BfL = 0; }
727 
728  static PBigStrPool New(TSize _MxBfLen = 0, uint _GrowBy = 16*1024*1024) { return PBigStrPool(new TBigStrPool(_MxBfLen, _GrowBy)); }
729  static PBigStrPool New(TSIn& SIn) { return new TBigStrPool(SIn); }
730  static PBigStrPool New(const TStr& fileName) { PSIn SIn = TFIn::New(fileName); return new TBigStrPool(*SIn); }
731  static PBigStrPool Load(TSIn& SIn, bool LoadCompacted = true) { return PBigStrPool(new TBigStrPool(SIn, LoadCompacted)); }
733  static PBigStrPool LoadShM(TShMIn& ShMIn, bool LoadCompact = true) {
734  TBigStrPool* StrPool = new TBigStrPool();
735  StrPool->LoadPoolShM(ShMIn, LoadCompact);
736  return PBigStrPool(StrPool);
737  }
738  void Save(TSOut& SOut) const;
739  void Save(const TStr& fileName) { TFOut FOut(fileName); Save(FOut); }
740 
741  int GetStrs() const { return IdOffV.Len(); }
742  TSize Len() const { return BfL; }
743  TSize Size() const { return MxBfL; }
744  bool Empty() const { return ! Len(); }
745  char* operator () () const { return Bf; }
746  TBigStrPool& operator = (const TBigStrPool& Pool);
748  return 4 * sizeof(int) + IdOffV.GetMemUsed() + MxBfL;
749  }
750 
751  int AddStr(const char *Str, uint Len);
752  int AddStr(const char *Str) { return AddStr(Str, uint(strlen(Str)) + 1); }
753  int AddStr(const TStr& Str) { return AddStr(Str.CStr(), Str.Len() + 1); }
754 
755  TStr GetStr(const int& StrId) const { Assert(StrId < GetStrs());
756  if (StrId == 0) return TStr::GetNullStr(); else return TStr(Bf + (TSize)IdOffV[StrId]); }
757  const char *GetCStr(const int& StrId) const { Assert(StrId < GetStrs());
758  if (StrId == 0) return TStr::GetNullStr().CStr(); else return (Bf + (TSize)IdOffV[StrId]); }
759 
760  TStr GetStrFromOffset(const TSize& Offset) const { Assert(Offset < BfL);
761  if (Offset == 0) return TStr::GetNullStr(); else return TStr(Bf + Offset); }
762  const char *GetCStrFromOffset(const TSize& Offset) const { Assert(Offset < BfL);
763  if (Offset == 0) return TStr::GetNullStr().CStr(); else return Bf + Offset; }
764 
765  void Clr(bool DoDel = false) {
766  BfL = 0; if (DoDel && Bf) {if (!IsShM) { free(Bf);} Bf = 0; MxBfL = 0;}}
767  int Cmp(const int& StrId, const char *Str) const { Assert(StrId < GetStrs());
768  if (StrId != 0) return strcmp(Bf + (TSize)IdOffV[StrId], Str); else return strcmp("", Str); }
769 
770  static int GetPrimHashCd(const char *CStr);
771  static int GetSecHashCd(const char *CStr);
772  int GetPrimHashCd(const int& StrId) { Assert(StrId < GetStrs());
773  if (StrId != 0) return GetPrimHashCd(Bf + (TSize)IdOffV[StrId]); else return GetPrimHashCd(""); }
774  int GetSecHashCd(const int& StrId) { Assert(StrId < GetStrs());
775  if (StrId != 0) return GetSecHashCd(Bf + (TSize)IdOffV[StrId]); else return GetSecHashCd(""); }
776 };
777 
779 // String-Hash-Table
780 template <class TDat, class TStringPool = TStrPool, class THashFunc = TDefaultHashFunc<TStr> >
781 class TStrHash{
782 public:
783  //typedef typename PStringPool::TObj TStringPool;
785 private:
790  THKeyDatV KeyDatV;
793  PStringPool Pool;
794 private:
795  uint GetNextPrime(const uint& Val) const;
796  void Resize();
797  const THKeyDat& GetHashKeyDat(const int& KeyId) const {
798  const THKeyDat& KeyDat = KeyDatV[KeyId]; Assert(KeyDat.HashCd != -1); return KeyDat; }
799  THKeyDat& GetHashKeyDat(const int& KeyId) {
800  THKeyDat& KeyDat = KeyDatV[KeyId]; Assert(KeyDat.HashCd != -1); return KeyDat; }
801 public:
802  TStrHash(): PortV(), KeyDatV(), AutoSizeP(true), FFreeKeyId(-1), FreeKeys(0), Pool() { }
803  TStrHash(const PStringPool& StrPool): PortV(), KeyDatV(), AutoSizeP(true), FFreeKeyId(-1), FreeKeys(0), Pool(StrPool) { }
804  TStrHash(const int& Ports, const bool& _AutoSizeP = false, const PStringPool& StrPool = PStringPool()) :
805  PortV(Ports), KeyDatV(Ports, 0), AutoSizeP(_AutoSizeP), FFreeKeyId(-1), FreeKeys(0), Pool(StrPool) { PortV.PutAll(-1); }
806  TStrHash(const TStrHash& Hash): PortV(Hash.PortV), KeyDatV(Hash.KeyDatV), AutoSizeP(Hash.AutoSizeP),
807  FFreeKeyId(Hash.FFreeKeyId), FreeKeys(Hash.FreeKeys), Pool() {
808  if (! Hash.Pool.Empty()) { Pool=PStringPool(new TStringPool(*Hash.Pool)); } }
809  TStrHash(TSIn& SIn, bool PoolToo = true): PortV(SIn), KeyDatV(SIn), AutoSizeP(SIn), FFreeKeyId(SIn), FreeKeys(SIn){ SIn.LoadCs(); if (PoolToo) Pool = PStringPool(SIn); }
810 
811  void Load(TSIn& SIn, bool PoolToo = true) {PortV.Load(SIn); KeyDatV.Load(SIn); AutoSizeP.Load(SIn); FFreeKeyId.Load(SIn);
812  FreeKeys.Load(SIn); SIn.LoadCs(); if (PoolToo) Pool = PStringPool(SIn);}
813 
815  void LoadShM(TShMIn& ShMIn, bool SharedPool=true) {
816  PortV.LoadShM(ShMIn);
817  KeyDatV.Load(ShMIn);
818  AutoSizeP.Load(ShMIn);
819  FFreeKeyId.Load(ShMIn);
820  FreeKeys.Load(ShMIn);
821  ShMIn.LoadCs();
822  if (SharedPool) {
823  TBool isNull;
824  isNull.Load(ShMIn);
825  if (!isNull) {
826  Pool = TStringPool::LoadShM(ShMIn);
827  }
828  } else {
829  Pool = PStringPool(ShMIn);
830  }
831  }
832 
833  void Save(TSOut& SOut, bool PoolToo = true) const { PortV.Save(SOut); KeyDatV.Save(SOut);
834  AutoSizeP.Save(SOut); FFreeKeyId.Save(SOut); FreeKeys.Save(SOut); SOut.SaveCs(); if (PoolToo) Pool.Save(SOut); }
835 
836  void SetPool(const PStringPool& StrPool) { IAssert(Pool.Empty() || Pool->Empty()); Pool = StrPool; }
837  PStringPool GetPool() const { return Pool; }
838 
839  TStrHash& operator = (const TStrHash& Hash);
840 
841  bool Empty() const {return ! Len(); }
842  int Len() const { return KeyDatV.Len() - FreeKeys; }
843  int Reserved() const { return KeyDatV.Reserved(); }
844  int GetPorts() const { return PortV.Len(); }
845  bool IsAutoSize() const { return AutoSizeP; }
846  int GetMxKeyIds() const { return KeyDatV.Len(); }
847  bool IsKeyIdEqKeyN() const {return ! FreeKeys; }
848 
849  int AddKey(const char *Key);
850  int AddKey(const TStr& Key) { return AddKey(Key.CStr()); }
851  int AddKey(const TChA& Key) { return AddKey(Key.CStr()); }
852  int AddDat(const char *Key, const TDat& Dat) { const int KeyId = AddKey(Key); KeyDatV[KeyId].Dat = Dat; return KeyId; }
853  int AddDat(const TStr& Key, const TDat& Dat) { const int KeyId = AddKey(Key.CStr()); KeyDatV[KeyId].Dat = Dat; return KeyId; }
854  int AddDat(const TChA& Key, const TDat& Dat) { const int KeyId = AddKey(Key.CStr()); KeyDatV[KeyId].Dat = Dat; return KeyId; }
855  TDat& AddDat(const char *Key) { return KeyDatV[AddKey(Key)].Dat; }
856  TDat& AddDat(const TStr& Key) { return KeyDatV[AddKey(Key.CStr())].Dat; }
857  TDat& AddDat(const TChA& Key) { return KeyDatV[AddKey(Key.CStr())].Dat; }
858  TDat& AddDatId(const char *Key) { const int KeyId = AddKey(Key); return KeyDatV[KeyId].Dat = KeyId; }
859  TDat& AddDatId(const TStr& Key) { const int KeyId = AddKey(Key.CStr()); return KeyDatV[KeyId].Dat = KeyId; }
860  TDat& AddDatId(const TChA& Key) { const int KeyId = AddKey(Key.CStr()); return KeyDatV[KeyId].Dat = KeyId; }
861 
862  const TDat& operator[](const int& KeyId) const {return GetHashKeyDat(KeyId).Dat;}
863  TDat& operator[](const int& KeyId){return GetHashKeyDat(KeyId).Dat;}
864  const TDat& operator () (const char *Key) const { return GetDat(Key);}
865  //TDat& operator ()(const char *Key){return AddDat(Key);} // add if not found
866  ::TSize GetMemUsed() const {
867  int64 MemUsed = sizeof(bool)+2*sizeof(int);
868  MemUsed += int64(PortV.Reserved()) * int64(sizeof(TInt));
869  for (int KeyDatN = 0; KeyDatN < KeyDatV.Len(); KeyDatN++) {
870  MemUsed += int64(2 * sizeof(TInt));
871  MemUsed += int64(KeyDatV[KeyDatN].Key.GetMemUsed());
872  MemUsed += int64(KeyDatV[KeyDatN].Dat.GetMemUsed());
873  }
874  // printf("TStrHash: Memory used for hash table: %s\n", TUInt64::GetStr(MemUsed).CStr());
875  MemUsed += 8 + Pool->GetMemUsed();
876  return ::TSize(MemUsed/1000);
877  }
878 
879  const TDat& GetDat(const char *Key) const { return KeyDatV[GetKeyId(Key)].Dat; }
880  const TDat& GetDat(const TStr& Key) const { return GetDat(Key.CStr()); }
881  TDat& GetDat(const char *Key) { return KeyDatV[GetKeyId(Key)].Dat; }
882  const TDat& GetDat(const TStr& Key) { return GetDat(Key.CStr()); }
883  const TDat& GetDat(const TChA& Key) { return GetDat(Key.CStr()); }
884  TDat& GetDatId(const int& KeyId) { return KeyDatV[KeyId].Dat; }
885  const TDat& GetDatId(const int& KeyId) const { return KeyDatV[KeyId].Dat; }
886  void GetKeyDat(const int& KeyId, int& KeyO, TDat& Dat) const { const THKeyDat& KeyDat = GetHashKeyDat(KeyId); KeyO = KeyDat.Key; Dat = KeyDat.Dat; }
887  void GetKeyDat(const int& KeyId, const char*& Key, TDat& Dat) const { const THKeyDat& KeyDat = GetHashKeyDat(KeyId); Key = KeyFromOfs(KeyDat.Key); Dat = KeyDat.Dat; }
888  void GetKeyDat(const int& KeyId, TStr& Key, TDat& Dat) const { const THKeyDat& KeyDat = GetHashKeyDat(KeyId); Key = KeyFromOfs(KeyDat.Key); Dat = KeyDat.Dat;}
889  void GetKeyDat(const int& KeyId, TChA& Key, TDat& Dat) const { const THKeyDat& KeyDat = GetHashKeyDat(KeyId); Key = KeyFromOfs(KeyDat.Key); Dat = KeyDat.Dat;}
890 
891  int GetKeyId(const char *Key) const;
892  int GetKeyId(const TStr& Key) const { return GetKeyId(Key.CStr()); }
893  const char *GetKey(const int& KeyId) const { return Pool->GetCStr(GetHashKeyDat(KeyId).Key); }
894  int GetKeyOfs(const int& KeyId) const { return GetHashKeyDat(KeyId).Key; } // pool string id
895  const char *KeyFromOfs(const int& KeyO) const { return Pool->GetCStr(KeyO); }
896 
897  bool IsKey(const char *Key) const { return GetKeyId(Key) != -1; }
898  bool IsKey(const TStr& Key) const { return GetKeyId(Key.CStr()) != -1; }
899  bool IsKey(const TChA& Key) const { return GetKeyId(Key.CStr()) != -1; }
900  bool IsKey(const char *Key, int& KeyId) const { KeyId = GetKeyId(Key); return KeyId != -1; }
901  bool IsKeyGetDat(const char *Key, TDat& Dat) const { const int KeyId = GetKeyId(Key); if (KeyId != -1) { Dat = KeyDatV[KeyId].Dat; return true; } else return false; }
902  bool IsKeyGetDat(const TStr& Key, TDat& Dat) const { const int KeyId = GetKeyId(Key.CStr()); if (KeyId != -1) { Dat = KeyDatV[KeyId].Dat; return true; } else return false; }
903  bool IsKeyGetDat(const TChA& Key, TDat& Dat) const { const int KeyId = GetKeyId(Key.CStr()); if (KeyId != -1) { Dat = KeyDatV[KeyId].Dat; return true; } else return false; }
904  bool IsKeyId(const int& KeyId) const { return 0 <= KeyId && KeyId < KeyDatV.Len() && KeyDatV[KeyId].HashCd != -1; }
905 
906  int FFirstKeyId() const {return 0-1;}
907  bool FNextKeyId(int& KeyId) const;
908 
909  void GetKeyV(TVec<TStr>& KeyV) const;
910  void GetStrIdV(TIntV& StrIdV) const;
911  void GetDatV(TVec<TDat>& DatV) const;
912  void GetKeyDatPrV(TVec<TPair<TStr, TDat> >& KeyDatPrV) const;
913  void GetDatKeyPrV(TVec<TPair<TDat, TStr> >& DatKeyPrV) const;
914 
915  void Pack(){KeyDatV.Pack();}
916 };
917 
918 template <class TDat, class TStringPool, class THashFunc>
920  uint *f = (uint *) TIntH::HashPrimeT, *m, *l = (uint *) TIntH::HashPrimeT + (int) TIntH::HashPrimes;
921  int h, len = (int)TIntH::HashPrimes;
922  while (len > 0) {
923  h = len >> 1; m = f + h;
924  if (*m < Val) { f = m; f++; len = len - h - 1; }
925  else len = h;
926  }
927  return f == l ? *(l - 1) : *f;
928 }
929 
930 template <class TDat, class TStringPool, class THashFunc>
932  // resize & initialize port vector
933  if (PortV.Empty()) { PortV.Gen(17); PortV.PutAll(-1); }
934  else
935  if (AutoSizeP && KeyDatV.Len() > 3 * PortV.Len()) {
936  const int NxPrime = GetNextPrime(KeyDatV.Len());
937  //printf("%s resize PortV: %d -> %d, Len: %d\n", GetTypeNm(*this).CStr(), PortV.Len(), NxPrime, Len());
938  PortV.Gen(NxPrime); PortV.PutAll(-1); }
939  else
940  return;
941  // rehash keys
942  const int NPorts = PortV.Len();
943  for (int i = 0; i < KeyDatV.Len(); i++) {
944  THKeyDat& KeyDat = KeyDatV[i];
945  if (KeyDat.HashCd != -1) {
946  const int Port = abs(THashFunc::GetPrimHashCd(Pool->GetCStr(KeyDat.Key)) % NPorts);
947  KeyDat.Next = PortV[Port];
948  PortV[Port] = i;
949  }
950  }
951 }
952 
953 template <class TDat, class TStringPool, class THashFunc>
955  if (this != &Hash) {
956  PortV = Hash.PortV;
957  KeyDatV = Hash.KeyDatV;
958  AutoSizeP = Hash.AutoSizeP;
959  FFreeKeyId = Hash.FFreeKeyId;
960  FreeKeys = Hash.FreeKeys;
961  if (! Hash.Pool.Empty()) Pool = PStringPool(new TStringPool(*Hash.Pool));
962  else Pool = NULL;
963  }
964  return *this;
965 }
966 
967 template <class TDat, class TStringPool, class THashFunc>
969  if (Pool.Empty()) Pool = TStringPool::New();
970  if ((AutoSizeP && KeyDatV.Len() > PortV.Len()) || PortV.Empty()) Resize();
971  const int PortN = abs(THashFunc::GetPrimHashCd(Key) % PortV.Len());
972  const int HashCd = abs(THashFunc::GetSecHashCd(Key));
973  int PrevKeyId = -1;
974  int KeyId = PortV[PortN];
975  while (KeyId != -1 && ! (KeyDatV[KeyId].HashCd == HashCd && Pool->Cmp(KeyDatV[KeyId].Key, Key) == 0)) {
976  PrevKeyId = KeyId; KeyId = KeyDatV[KeyId].Next; }
977  if (KeyId == -1) {
978  const int StrId = Pool->AddStr(Key);
979  if (FFreeKeyId == -1) {
980  KeyId = KeyDatV.Add(THKeyDat(-1, HashCd, StrId));
981  } else {
982  KeyId = FFreeKeyId;
983  FFreeKeyId = KeyDatV[FFreeKeyId].Next;
984  FreeKeys--;
985  KeyDatV[KeyId] = THKeyDat(-1, HashCd, StrId);
986  }
987  if (PrevKeyId == -1) PortV[PortN] = KeyId;
988  else KeyDatV[PrevKeyId].Next = KeyId;
989  }
990  return KeyId;
991 }
992 
993 template <class TDat, class TStringPool, class THashFunc>
995  if (PortV.Empty()) return -1;
996  const int PortN = abs(THashFunc::GetPrimHashCd(Key) % PortV.Len());
997  const int Hc = abs(THashFunc::GetSecHashCd(Key));
998  int KeyId = PortV[PortN];
999  while (KeyId != -1 && ! (KeyDatV[KeyId].HashCd == Hc && Pool->Cmp(KeyDatV[KeyId].Key, Key) == 0))
1000  KeyId = KeyDatV[KeyId].Next;
1001  return KeyId;
1002 }
1003 
1004 template <class TDat, class TStringPool, class THashFunc>
1006  do KeyId++; while (KeyId < KeyDatV.Len() && KeyDatV[KeyId].HashCd == -1);
1007  return KeyId < KeyDatV.Len();
1008 }
1009 
1010 template <class TDat, class TStringPool, class THashFunc>
1012  KeyV.Gen(Len(), 0);
1013  int KeyId = FFirstKeyId();
1014  while (FNextKeyId(KeyId))
1015  KeyV.Add(GetKey(KeyId));
1016 }
1017 
1018 template <class TDat, class TStringPool, class THashFunc>
1020  StrIdV.Gen(Len(), 0);
1021  int KeyId = FFirstKeyId();
1022  while (FNextKeyId(KeyId))
1023  StrIdV.Add(GetKeyOfs(KeyId));
1024 }
1025 
1026 template <class TDat, class TStringPool, class THashFunc>
1028  DatV.Gen(Len(), 0);
1029  int KeyId = FFirstKeyId();
1030  while (FNextKeyId(KeyId))
1031  DatV.Add(GetHashKeyDat(KeyId).Dat);
1032 }
1033 
1034 template <class TDat, class TStringPool, class THashFunc>
1036  KeyDatPrV.Gen(Len(), 0);
1037  TStr Str; TDat Dat;
1038  int KeyId = FFirstKeyId();
1039  while (FNextKeyId(KeyId)){
1040  GetKeyDat(KeyId, Str, Dat);
1041  KeyDatPrV.Add(TPair<TStr, TDat>(Str, Dat));
1042  }
1043 }
1044 
1045 template <class TDat, class TStringPool, class THashFunc>
1047  DatKeyPrV.Gen(Len(), 0);
1048  TStr Str; TDat Dat;
1049  int KeyId = FFirstKeyId();
1050  while (FNextKeyId(KeyId)){
1051  GetKeyDat(KeyId, Str, Dat);
1052  DatKeyPrV.Add(TPair<TDat, TStr>(Dat, Str));
1053  }
1054 }
1055 
1057 // Common-String-Hash-Types
1061 
1063 // Cache
1064 template <class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey> >
1065 class TCache{
1066 private:
1072  TKeyL TimeKeyL;
1073  void* RefToBs;
1074  void Purge(const int64& MemToPurge);
1075 public:
1077  TCache(const TCache&);
1078  TCache(const int64& _MxMemUsed, const int& Ports, void* _RefToBs):
1079  MxMemUsed(_MxMemUsed), CurMemUsed(0),
1080  KeyDatH(Ports), TimeKeyL(), RefToBs(_RefToBs){}
1081 
1082  TCache& operator=(const TCache&);
1083  int64 GetMemUsed() const;
1084  int64 GetMxMemUsed() const { return MxMemUsed; }
1085  bool RefreshMemUsed();
1086 
1087  void Put(const TKey& Key, const TDat& Dat);
1088  bool Get(const TKey& Key, TDat& Dat);
1089  void Del(const TKey& Key, const bool& DoEventCall=true);
1090  void Flush();
1091  void FlushAndClr();
1092  void* FFirstKeyDat();
1093  bool FNextKeyDat(void*& KeyDatP, TKey& Key, TDat& Dat);
1094 
1095  void PutRefToBs(void* _RefToBs){RefToBs=_RefToBs;}
1096  void* GetRefToBs(){return RefToBs;}
1097 };
1098 
1099 template <class TKey, class TDat, class THashFunc>
1101  const int64 StartMemUsed = CurMemUsed;
1102  while (!TimeKeyL.Empty()&&(StartMemUsed-CurMemUsed<MemToPurge)){
1103  TKey Key=TimeKeyL.Last()->GetVal();
1104  Del(Key);
1105  }
1106 }
1107 
1108 template <class TKey, class TDat, class THashFunc>
1110  int64 MemUsed=0;
1111  int KeyId=KeyDatH.FFirstKeyId();
1112  while (KeyDatH.FNextKeyId(KeyId)){
1113  const TKey& Key=KeyDatH.GetKey(KeyId);
1114  const TKeyLNDatPr& KeyLNDatPr=KeyDatH[KeyId];
1115  TDat Dat=KeyLNDatPr.Val2;
1116  MemUsed+=int64(Key.GetMemUsed()+Dat->GetMemUsed());
1117  }
1118  return MemUsed;
1119 }
1120 
1121 template <class TKey, class TDat, class THashFunc>
1123  CurMemUsed=GetMemUsed();
1124  if (CurMemUsed>MxMemUsed){
1125  Purge(CurMemUsed-MxMemUsed);
1126  return true;
1127  }
1128  return false;
1129 }
1130 
1131 template <class TKey, class TDat, class THashFunc>
1132 void TCache<TKey, TDat, THashFunc>::Put(const TKey& Key, const TDat& Dat){
1133  int KeyId=KeyDatH.GetKeyId(Key);
1134  if (KeyId==-1){
1135  int64 KeyDatMem=int64(Key.GetMemUsed()+Dat->GetMemUsed());
1136  if (CurMemUsed+KeyDatMem>MxMemUsed){Purge(KeyDatMem);}
1137  CurMemUsed+=KeyDatMem;
1138  TKeyLN KeyLN=TimeKeyL.AddFront(Key);
1139  TKeyLNDatPr KeyLNDatPr(KeyLN, Dat);
1140  KeyDatH.AddDat(Key, KeyLNDatPr);
1141  } else {
1142  TKeyLNDatPr& KeyLNDatPr=KeyDatH[KeyId];
1143  TKeyLN KeyLN=KeyLNDatPr.Val1;
1144  KeyLNDatPr.Val2=Dat;
1145  TimeKeyL.PutFront(KeyLN);
1146  }
1147 }
1148 
1149 template <class TKey, class TDat, class THashFunc>
1150 bool TCache<TKey, TDat, THashFunc>::Get(const TKey& Key, TDat& Dat){
1151  int KeyId=KeyDatH.GetKeyId(Key);
1152  if (KeyId==-1){
1153  return false;
1154  } else {
1155  Dat=KeyDatH[KeyId].Val2;
1156  return true;
1157  }
1158 }
1159 
1160 template <class TKey, class TDat, class THashFunc>
1161 void TCache<TKey, TDat, THashFunc>::Del(const TKey& Key, const bool& DoEventCall){
1162  int KeyId=KeyDatH.GetKeyId(Key);
1163  if (KeyId!=-1){
1164  TKeyLNDatPr& KeyLNDatPr=KeyDatH[KeyId];
1165  TKeyLN KeyLN=KeyLNDatPr.Val1;
1166  TDat& Dat=KeyLNDatPr.Val2;
1167  if (DoEventCall){
1168  Dat->OnDelFromCache(Key, RefToBs);}
1169  CurMemUsed-=int64(Key.GetMemUsed()+Dat->GetMemUsed());
1170  Dat=NULL;
1171  TimeKeyL.Del(KeyLN);
1172  KeyDatH.DelKeyId(KeyId);
1173  }
1174 }
1175 
1176 template <class TKey, class TDat, class THashFunc>
1178  printf("To flush: %d\n", KeyDatH.Len());
1179  int KeyId=KeyDatH.FFirstKeyId(); int Done = 0;
1180  while (KeyDatH.FNextKeyId(KeyId)){
1181  if (Done%10000==0){printf("%d\r", Done);}
1182  const TKey& Key=KeyDatH.GetKey(KeyId);
1183  TKeyLNDatPr& KeyLNDatPr=KeyDatH[KeyId];
1184  TDat Dat=KeyLNDatPr.Val2;
1185  Dat->OnDelFromCache(Key, RefToBs);
1186  Done++;
1187  }
1188  printf("Done %d\n", KeyDatH.Len());
1189 }
1190 
1191 template <class TKey, class TDat, class THashFunc>
1193  Flush();
1194  CurMemUsed=0;
1195  KeyDatH.Clr();
1196  TimeKeyL.Clr();
1197 }
1198 
1199 template <class TKey, class TDat, class THashFunc>
1201  return TimeKeyL.First();
1202 }
1203 
1204 template <class TKey, class TDat, class THashFunc>
1205 bool TCache<TKey, TDat, THashFunc>::FNextKeyDat(void*& KeyDatP, TKey& Key, TDat& Dat){
1206  if (KeyDatP==NULL){
1207  return false;
1208  } else {
1209  Key=TKeyLN(KeyDatP)->GetVal(); Dat=KeyDatH.GetDat(Key).Val2;
1210  KeyDatP=TKeyLN(KeyDatP)->Next(); return true;
1211  }
1212 }
1213 
1215 // Old-Hash-Functions
1216 
1217 // Old-String-Hash-Function
1219 public:
1220  inline static int GetPrimHashCd(const char *p) {
1221  const int MulBy = 16; // even older version used MulBy=2
1222  int HashCd = 0;
1223  while (*p) { HashCd = (MulBy * HashCd) + *p++; HashCd &= 0x0FFFFFFF; }
1224  return HashCd; }
1225  inline static int GetSecHashCd(const char *p) {
1226  const int MulBy = 16; // even older version used MulBy=2
1227  int HashCd = 0;
1228  while (*p) { HashCd = (MulBy * HashCd) ^ *p++; HashCd &= 0x0FFFFFFF; }
1229  return HashCd; }
1230  inline static int GetPrimHashCd(const TStr& s) { return GetPrimHashCd(s.CStr()); }
1231  inline static int GetSecHashCd(const TStr& s) { return GetSecHashCd(s.CStr()); }
1232 };
1233 
1234 // Md5-Hash-Function
1236 public:
1237  static int GetPrimHashCd(const char *p);
1238  static int GetSecHashCd(const char *p);
1239  static int GetPrimHashCd(const TStr& s);
1240  static int GetSecHashCd(const TStr& s);
1241 };
1242 
1243 // DJB-Hash-Function
1245 private:
1246  inline static unsigned int DJBHash(const char* Str, const ::TSize& Len) {
1247  unsigned int hash = 5381;
1248  for(unsigned int i = 0; i < Len; Str++, i++) {
1249  hash = ((hash << 5) + hash) + (*Str); }
1250  return hash;
1251  }
1252 public:
1253  inline static int GetPrimHashCd(const char *p) {
1254  const char *r = p; while (*r) { r++; }
1255  return (int) DJBHash((const char *) p, r - p) & 0x7fffffff; }
1256  inline static int GetSecHashCd(const char *p) {
1257  const char *r = p; while (*r) { r++; }
1258  return (int) DJBHash((const char *) p, r - p) & 0x7fffffff; }
1259  inline static int GetPrimHashCd(const TStr& s) {
1260  return GetPrimHashCd(s.CStr()); }
1261  inline static int GetSecHashCd(const TStr& s) {
1262  return GetSecHashCd(s.CStr()); }
1263  inline static int GetPrimHashCd(const char *p, const ::TSize& Len) {
1264  return (int) DJBHash((const char *) p, Len) & 0x7fffffff; }
1265  inline static int GetSecHashCd(const char *p, const ::TSize& Len) {
1266  return (int) DJBHash((const char *) p, Len) & 0x7fffffff; }
1267 };
1268 
1269 // Old-Vector-Hash-Function
1270 template <class TVec>
1272 public:
1273  static inline int GetPrimHashCd(const TVec& Vec) {
1274  int HashCd=0;
1275  for (int ValN=0; ValN<Vec.Len(); ValN++){
1276  HashCd+=Vec[ValN].GetPrimHashCd();}
1277  return abs(HashCd);
1278  }
1279  inline static int GetSecHashCd(const TVec& Vec) {
1280  int HashCd=0;
1281  for (int ValN=0; ValN<Vec.Len(); ValN++){
1282  HashCd+=Vec[ValN].GetSecHashCd();}
1283  return abs(HashCd);
1284  }
1285 };
Definition: ds.h:346
Definition: bd.h:440
bool IsKey(const TChA &Key) const
Definition: hash.h:899
#define IAssert(Cond)
Definition: bd.h:262
THashKeyDatI()
Definition: hash.h:56
void GetKeyDat(const int &KeyId, TChA &Key, TDat &Dat) const
Definition: hash.h:889
bool operator==(const THashKeyDat &HashKeyDat) const
Definition: hash.h:34
const TDat & GetDat(const TStr &Key) const
Definition: hash.h:880
void GetKeyDat(const int &KeyId, TStr &Key, TDat &Dat) const
Definition: hash.h:888
TIter EndI() const
Returns an iterator referring to the past-the-end element in the vector.
Definition: ds.h:595
THash< TInt, TFltPr > TIntFltPrH
Definition: hash.h:616
THash< TStr, TStr > TStrStrH
Definition: hash.h:655
int AddDat(const TStr &Key, const TDat &Dat)
Definition: hash.h:853
int Reserved() const
Definition: hash.h:843
PStringPool GetPool() const
Definition: hash.h:837
TDat Dat
Definition: hash.h:13
bool IsKeyIdEqKeyN() const
Definition: hash.h:233
void LoadShM(TShMIn &ShMIn, TDatFunctor LoadDatFromShared)
Definition: hash.h:27
TKeyL TimeKeyL
Definition: hash.h:1072
TSizeTy Reserved() const
Returns the size of allocated storage capacity.
Definition: ds.h:577
int GetKeyOfs(const int &KeyId) const
Definition: hash.h:894
TVec< THKeyDat > THKeyDatV
Definition: hash.h:788
#define IAssertR(Cond, Reason)
Definition: bd.h:265
THash< TStr, TFltV > TStrFltVH
Definition: hash.h:654
int GetPrimHashCd() const
Returns primary hash code of the vector. Used by THash.
Definition: ds.h:999
THashKeyDatI(const THashKeyDatI &_HashKeyDatI)
Definition: hash.h:57
THash< TStr, TInt > TStrH
Definition: hash.h:645
THash< TInt, TIntVFltVPr > TIntIntVFltVPrH
Definition: hash.h:625
THash< TIntTr, TFlt > TIntTrFltH
Definition: hash.h:637
int Len() const
Definition: dt.h:490
THashKeyDat & operator=(const THashKeyDat &HashKeyDat)
Definition: hash.h:38
void GetDatV(TVec< TDat > &DatV) const
Definition: hash.h:492
TPt & operator=(const TPt &Pt)
Definition: bd.h:487
THash< TCh, TCh > TChChH
Definition: hash.h:605
THash< TIntPr, TIntPrV > TIntPrIntPrVH
Definition: hash.h:630
THash< TIntTr, TInt > TIntTrIntH
Definition: hash.h:631
PStringPool Pool
Definition: hash.h:793
::TSize GetMemUsed() const
Definition: hash.h:866
const char * GetCStr(const int &StrId) const
Definition: hash.h:757
TDat & operator[](const int &KeyId)
Definition: hash.h:863
TDat & GetDat(const char *Key)
Definition: hash.h:881
bool IsKeyGetDat(const TChA &Key, TDat &Dat) const
Definition: hash.h:903
void Sort(const bool &CmpKey, const bool &Asc)
Definition: hash.h:570
bool IsAutoSize() const
Definition: hash.h:845
THash< TInt, TStrPrV > TIntStrPrVH
Definition: hash.h:621
Definition: dt.h:11
THash & operator=(const THash &Hash)
Definition: hash.h:190
TInt FreeKeys
Definition: hash.h:792
bool operator==(const THashKeyDatI &HashKeyDatI) const
Definition: hash.h:64
void LoadPoolShM(TShMIn &ShMIn, bool LoadCompact=true)
Definition: hash.cpp:48
int GetMxKeyIds() const
Definition: hash.h:846
THash< TStr, TUInt64V > TStrUInt64VH
Definition: hash.h:651
THash< TUInt64, TInt > TUInt64H
Definition: hash.h:608
THash< TStrIntPr, TInt > TStrIntPrIntH
Definition: hash.h:671
static PBigStrPool New(TSize _MxBfLen=0, uint _GrowBy=16 *1024 *1024)
Definition: hash.h:728
void Save(TSOut &SOut) const
Definition: dt.h:1153
void * RefToBs
Definition: hash.h:1073
int FFirstKeyId() const
Definition: hash.h:906
int64 MxMemUsed
Definition: hash.h:1069
bool operator==(const THash &Hash) const
Definition: hash.h:350
THash< TStr, TIntV > TStrIntVH
Definition: hash.h:649
unsigned int uint
Definition: bd.h:11
const THKeyDat & GetHashKeyDat(const int &KeyId) const
Definition: hash.h:139
bool IsKeyId(const int &KeyId) const
Definition: hash.h:260
TDat & operator()(const TKey &Key)
Definition: hash.h:200
#define Fail
Definition: bd.h:238
TCache(const int64 &_MxMemUsed, const int &Ports, void *_RefToBs)
Definition: hash.h:1078
int64 CurMemUsed
Definition: hash.h:1070
bool Empty() const
Definition: bd.h:501
THash< TInt, TIntH > TIntIntHH
Definition: hash.h:614
void GetKeyDat(const int &KeyId, TKey &Key, TDat &Dat) const
Definition: hash.h:271
bool Empty() const
Definition: hash.h:744
void Flush()
Definition: hash.h:1177
TIter BegI() const
Definition: hash.h:213
static int GetSecHashCd(const TStr &s)
Definition: hash.h:1231
void Load(TSIn &SIn)
Definition: dt.h:994
Definition: fl.h:319
void GetKeyDat(const int &KeyId, const char *&Key, TDat &Dat) const
Definition: hash.h:887
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
void operator()(THKeyDat *HKeyDat, TShMIn &ShMIn)
Definition: hash.h:132
int Len() const
Definition: hash.h:842
int GetSecHashCd() const
Returns secondary hash code of the vector. Used by THash.
Definition: ds.h:1011
THash< TStr, TStrPr > TStrStrPrH
Definition: hash.h:656
void Save(TSOut &SOut) const
Definition: hash.h:183
TDat & AddDatId(const TStr &Key)
Definition: hash.h:859
static int GetSecHashCd(const TKey &Key)
Definition: hash.h:91
bool Empty() const
Definition: hash.h:227
static const unsigned int HashPrimeT[HashPrimes]
Definition: hash.h:100
static PBigStrPool New(const TStr &fileName)
Definition: hash.h:730
TInt Next
Definition: hash.h:10
int AddStr(const char *Str, uint Len)
Definition: hash.cpp:95
TSize Len() const
Definition: hash.h:742
TStr GetStr(const int &StrId) const
Definition: hash.h:755
int AddStr(const TStr &Str)
Definition: hash.h:753
TInt FFreeKeyId
Definition: hash.h:792
void Purge(const int64 &MemToPurge)
Definition: hash.h:1100
TCache()
Definition: hash.h:1076
TPair< TKeyLN, TDat > TKeyLNDatPr
Definition: hash.h:1068
TDat & operator[](const int &KeyId)
Definition: hash.h:199
int64 GetMemUsed() const
Definition: hash.h:1109
THashKeyDat(const int &_Next, const int &_HashCd, const TKey &_Key)
Definition: hash.h:17
void SetPool(const PStringPool &StrPool)
Definition: hash.h:836
THash< TIntPr, TStrV > TIntPrStrVH
Definition: hash.h:639
bool IsKeyGetDat(const TStr &Key, TDat &Dat) const
Definition: hash.h:902
TDat GetDatWithDefault(const TKey &Key, TDat DefaultValue)
Definition: hash.h:264
int AddDat(const char *Key, const TDat &Dat)
Definition: hash.h:852
THash< TStrTr, TInt > TStrTrIntH
Definition: hash.h:670
TDat & AddDatId(const char *Key)
Definition: hash.h:858
void Save(TSOut &SOut) const
Definition: dt.h:995
THash< TIntPr, TFlt > TIntPrFltH
Definition: hash.h:636
TStrHash()
Definition: hash.h:802
int AddKey(const TStr &Key)
Definition: hash.h:850
Definition: fl.h:384
THash< TInt, TUInt64 > TIntUInt64H
Definition: hash.h:611
THashKeyDat()
Definition: hash.h:15
static int GetPrimHashCd(const char *p)
Definition: hash.cpp:118
TPt< TBigStrPool > PBigStrPool
Definition: hash.h:711
void LoadXml(const PXmlTok &XmlTok, const TStr &Nm="")
Definition: xmlser.h:127
THash< TIntPr, TIntV > TIntPrIntVH
Definition: hash.h:629
void Put(const TKey &Key, const TDat &Dat)
Definition: hash.h:1132
TIntV PortV
Definition: hash.h:789
TCRef CRef
Definition: hash.h:683
THash< TInt, TStr > TIntStrH
Definition: hash.h:619
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
bool IsEmpty() const
Tests whether the iterator has been initialized.
Definition: hash.h:76
void DelKeyId(const int &KeyId)
Definition: hash.h:245
TIter EndI() const
Definition: hash.h:218
THashKeyDat(TSIn &SIn)
Definition: hash.h:19
void Load(TSIn &SIn)
Definition: ds.h:946
const TDat & operator[](const int &KeyId) const
Definition: hash.h:862
TDat & GetDat(const TKey &Key)
Definition: hash.h:263
THash< TIntPr, TInt > TIntPrIntH
Definition: hash.h:627
void DelKeyIdV(const TIntV &KeyIdV)
Definition: hash.h:246
TSizeTy GetMemUsed() const
Returns the memory footprint (the number of bytes) of the vector.
Definition: ds.h:511
static int GetSecHashCd(const char *p)
Definition: hash.h:1256
bool FNextKeyId(int &KeyId) const
Definition: hash.h:1005
const char * GetCStrFromOffset(const TSize &Offset) const
Definition: hash.h:762
THash< TUInt, TUInt > TUIntH
Definition: hash.h:633
void GetDatKeyPrV(TVec< TPair< TDat, TKey > > &DatKeyPrV) const
Definition: hash.h:511
void GetDatV(TVec< TDat > &DatV) const
Definition: hash.h:1027
THash< TChTr, TInt > TChTrIntH
Definition: hash.h:606
void LoadShM(TShMIn &ShMIn)
Load THash from shared memory file. Copying/Deleting Keys is illegal.
Definition: hash.h:157
TStr GetStrFromOffset(const TSize &Offset) const
Definition: hash.h:760
void Save(TSOut &SOut) const
Definition: hash.h:698
virtual void LoadCs()
Definition: fl.cpp:28
TPair< TKey, TDat > TKeyDatP
Definition: hash.h:105
void Load(TSIn &SIn)
Definition: hash.h:177
const TKey & GetKey() const
Definition: hash.h:80
void Save(const TStr &fileName)
Definition: hash.h:739
THash< TStrV, TInt > TStrVIntH
Definition: hash.h:673
void Pack()
Definition: hash.h:915
::TSize GetMemUsed()
Definition: hash.h:747
void Defrag()
Definition: hash.h:555
int GetSecHashCd(const int &StrId)
Definition: hash.h:774
TInt FreeKeys
Definition: hash.h:109
Definition: fl.h:58
void Save(TSOut &SOut) const
Definition: ds.h:954
int AddStr(const char *Str)
Definition: hash.h:752
bool Empty() const
Tests whether the vector is empty.
Definition: ds.h:570
bool Get(const TKey &Key, TDat &Dat)
Definition: hash.h:1150
THash< TDbStr, TStr > TDbStrStrH
Definition: hash.h:664
THash< TStrPr, TStrV > TStrPrStrVH
Definition: hash.h:669
#define ClassTP(TNm, PNm)
Definition: bd.h:126
THash< TStrV, TStrV > TStrVStrVH
Definition: hash.h:676
TStrHash< TInt > TStrIntSH
Definition: hash.h:1059
const char * KeyFromOfs(const int &KeyO) const
Definition: hash.h:895
static PSIn New(const TStr &FNm)
Definition: fl.cpp:290
void Swap(THash &Hash)
Definition: hash.h:544
void DelKey(const TKey &Key)
Definition: hash.h:404
TBool AutoSizeP
Definition: hash.h:108
int AddKey(const TChA &Key)
Definition: hash.h:851
int Cmp(const int &StrId, const char *Str) const
Definition: hash.h:767
void MarkDelKey(const TKey &Key)
Definition: hash.h:426
THash< TInt, TFltTr > TIntFltTrH
Definition: hash.h:617
bool operator<(const THashKeyDatI &HashKeyDatI) const
Definition: hash.h:66
THash< TInt, TFlt > TIntFltH
Definition: hash.h:615
void SaveCs()
Definition: fl.h:171
THash< TInt, TFltV > TIntFltVH
Definition: hash.h:618
void LoadXml(const PXmlTok &XmlTok, const TStr &Nm="")
Definition: xmlser.h:119
const TDat & GetDat() const
Definition: hash.h:81
static TPt< PHash< TKey, TDat > > New()
Definition: hash.h:688
THash< TInt, TInt > TIntIntH
Definition: hash.h:610
THash< TStr, TIntPr > TStrIntPrH
Definition: hash.h:648
char * CStr()
Definition: dt.h:255
void Gen(const int &ExpectVals)
Definition: hash.h:222
void GetDatKeyPrV(TVec< TPair< TDat, TStr > > &DatKeyPrV) const
Definition: hash.h:1046
bool IsKey(const char *Key) const
Definition: hash.h:897
THash< TStr, TIntFltPr > TStrIntFltPrH
Definition: hash.h:660
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:104
static int GetSecHashCd(const char *p, const ::TSize &Len)
Definition: hash.h:1265
bool IsEnd() const
Tests whether the iterator is pointing to the past-end element.
Definition: hash.h:78
TDat & AddDat(const TKey &Key, const TDat &Dat)
Definition: hash.h:239
static int GetPrimHashCd(const TStr &s)
Definition: hash.h:1230
THash< TKey, TDat > H
Definition: hash.h:685
THash< TInt, TIntFltPr > TIntIntFltPrH
Definition: hash.h:612
void PutAll(const TVal &Val)
Sets all elements of the vector to value Val.
Definition: ds.h:1229
void PutRefToBs(void *_RefToBs)
Definition: hash.h:1095
static TPt< PHash< TKey, TDat > > New(const int &MxVals, const int &Vals)
Definition: hash.h:691
bool IsKeyIdEqKeyN() const
Definition: hash.h:847
THash< TStrV, TIntV > TStrVIntVH
Definition: hash.h:674
THKeyDat * KeyDatI
Definition: hash.h:53
THash< TStr, TStrIntKdV > TStrStrIntKdVH
Definition: hash.h:662
static PBigStrPool New(TSIn &SIn)
Definition: hash.h:729
const char * GetKey(const int &KeyId) const
Definition: hash.h:893
static int GetPrimHashCd(const char *p, const ::TSize &Len)
Definition: hash.h:1263
TPair< TInt, TDat > TKeyDatP
Definition: hash.h:787
void GetKeyDatPrV(TVec< TPair< TStr, TDat > > &KeyDatPrV) const
Definition: hash.h:1035
void Del(const TKey &Key, const bool &DoEventCall=true)
Definition: hash.h:1161
static TPt< PHash< TKey, TDat > > Load(TSIn &SIn)
Definition: hash.h:697
THashKeyDatI & operator++(int)
Definition: hash.h:68
TLstNd< TKey > * TKeyLN
Definition: hash.h:1067
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
void Load(TSIn &SIn)
Definition: dt.h:1152
size_t TSize
Definition: bd.h:58
#define Assert(Cond)
Definition: bd.h:251
THashKeyDatI & Next()
Definition: hash.h:73
TLoadTHKeyDatInitializer(TDatInitFn Fn)
Definition: hash.h:131
bool IsKeyGetDat(const TKey &Key, TDat &Dat) const
Definition: hash.h:274
TStrHash< TInt > TStrSH
Definition: hash.h:1058
THash< TInt, TIntV > TIntIntVH
Definition: hash.h:613
void LoadShM(TShMIn &ShMIn, bool SharedPool=true)
Load hash from shared memory. If shared pool is true load pool from shared memory.
Definition: hash.h:815
int GetSecHashCd() const
Definition: bd.h:507
THKeyDatV KeyDatV
Definition: hash.h:790
THash< TIntIntPrPr, TFlt > TIntIntPrPrFltH
Definition: hash.h:642
THashKeyDatCmp(THash< TKey, TDat, THashFunc > &_Hash, const bool &_CmpKey, const bool &_Asc)
Definition: hash.h:115
THashKeyDatI(const THKeyDat *_KeyDatI, const THKeyDat *_EndI)
Definition: hash.h:59
THash< TIntIntPrPr, TInt > TIntIntPrPrIntH
Definition: hash.h:641
int FFirstKeyId() const
Definition: hash.h:278
TRec * operator()() const
Definition: bd.h:497
::TSize GetMemUsed() const
Definition: hash.h:201
void FlushAndClr()
Definition: hash.h:1192
const THKeyDat & GetHashKeyDat(const int &KeyId) const
Definition: hash.h:797
void Save(TSOut &SOut, bool PoolToo=true) const
Definition: hash.h:833
static int GetPrimHashCd(const char *p)
Definition: hash.h:1220
THash< TStrPr, TBool > TStrPrBoolH
Definition: hash.h:665
THash< TStr, TFlt > TStrFltH
Definition: hash.h:653
static TStr GetNullStr()
Definition: dt.cpp:1626
void GetKeyDat(const int &KeyId, int &KeyO, TDat &Dat) const
Definition: hash.h:886
THash< TIntV, TInt > TIntVIntH
Definition: hash.h:632
void Resize()
Definition: hash.h:319
int64 GetMxMemUsed() const
Definition: hash.h:1084
void Save(TSOut &SOut) const
Definition: hash.h:21
THash< TStrPr, TStr > TStrPrStrH
Definition: hash.h:668
TDat & GetDatId(const int &KeyId)
Definition: hash.h:884
void Resize()
Definition: hash.h:931
THash< TKey, TKeyLNDatPr, THashFunc > KeyDatH
Definition: hash.h:1071
TStrHash(const int &Ports, const bool &_AutoSizeP=false, const PStringPool &StrPool=PStringPool())
Definition: hash.h:804
Definition: fl.h:128
const TDat & operator[](const int &KeyId) const
The [] operator takes KeyId, use GetDat() if you need value access via the key.
Definition: hash.h:198
THash< TInt, TInt > TIntH
Definition: hash.h:607
PHash< TKey, TDat > & operator=(const PHash< TKey, TDat > &Vec)
Definition: hash.h:700
THashKeyDatI< TKey, TDat > TIter
Definition: hash.h:102
const TDat & operator()(const char *Key) const
Definition: hash.h:864
int AddKey(const char *Key)
Definition: hash.h:968
uint GetNextPrime(const uint &Val) const
Definition: hash.h:919
int GetMxKeyIds() const
Definition: hash.h:231
THash< TDbStr, TInt > TDbStrIntH
Definition: hash.h:663
THashKeyDat< TKey, TDat > THKeyDat
Definition: hash.h:51
bool FNextKeyDat(void *&KeyDatP, TKey &Key, TDat &Dat)
Definition: hash.h:1205
THash< TStr, TUInt64 > TStrUInt64H
Definition: hash.h:650
void SortByKey(const bool &Asc=true)
Definition: hash.h:291
Definition: dt.h:1137
int GetKeyId(const TKey &Key) const
Definition: hash.h:466
const TDat & GetDatId(const int &KeyId) const
Definition: hash.h:885
Definition: hash.h:781
static PBigStrPool LoadShM(TShMIn &ShMIn, bool LoadCompact=true)
Load the string pool with the buffer backed by shared memory.
Definition: hash.h:733
Definition: dt.h:201
THash< TIntStrPr, TInt > TIntStrPrIntH
Definition: hash.h:640
void LoadShM(TShMIn &ShMIn)
Constructs the vector from a shared memory input.
Definition: ds.h:932
Definition: hash.h:681
TStrHash(const PStringPool &StrPool)
Definition: hash.h:803
bool Empty() const
Definition: hash.h:841
Definition: ds.h:32
int AddKey(const TKey &Key)
Definition: hash.h:373
TInt FFreeKeyId
Definition: hash.h:109
TLst< TKey > TKeyL
Definition: hash.h:1067
static PBigStrPool Load(TSIn &SIn, bool LoadCompacted=true)
Definition: hash.h:731
void Load(TSIn &SIn, bool PoolToo=true)
Definition: hash.h:811
bool RefreshMemUsed()
Definition: hash.h:1122
TDat & AddDat(const TStr &Key)
Definition: hash.h:856
TBool AutoSizeP
Definition: hash.h:791
THash< TIntIntPrPr, TStr > TIntIntPrPrStrH
Definition: hash.h:643
int GetKeyId(const TStr &Key) const
Definition: hash.h:892
THash()
Definition: hash.h:145
THash< TStr, TStrKdV > TStrStrKdVH
Definition: hash.h:659
bool operator<(const THash &Hash) const
Definition: hash.h:196
THKeyDat * operator->() const
Definition: hash.h:72
long long int64
Definition: bd.h:27
THash< TStr, TIntPrV > TStrIntPrVH
Definition: hash.h:652
void GetStrIdV(TIntV &StrIdV) const
Definition: hash.h:1019
void GetKeyV(TVec< TKey > &KeyV) const
Definition: hash.h:484
THash< TIntPr, TStr > TIntPrStrH
Definition: hash.h:638
TStrHash(const TStrHash &Hash)
Definition: hash.h:806
THash< TStr, TStrIntPrV > TStrStrIntPrVH
Definition: hash.h:661
void Save(TSOut &SOut) const
Definition: xmlser.h:16
Definition: dt.h:412
int GetReservedKeyIds() const
Definition: hash.h:232
uint GetNextPrime(const uint &Val) const
Definition: hash.h:307
void LoadShM(TShMIn &ShMIn, TDatInitFn Fn)
Load THash from shared memory passing in the Dat initializer.
Definition: hash.h:167
const TDat & GetDat(const TStr &Key)
Definition: hash.h:882
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
THashKeyDatI & operator=(const THashKeyDatI &HashKeyDatI)
Definition: hash.h:62
THash< TStr, TStrV > TStrStrVH
Definition: hash.h:657
TSize Size() const
Definition: hash.h:743
void * FFirstKeyDat()
Definition: hash.h:1200
int GetPorts() const
Definition: hash.h:229
THash< TIntPr, TIntPr > TIntPrH
Definition: hash.h:628
THKeyDat & GetHashKeyDat(const int &KeyId)
Definition: hash.h:136
Definition: hash.h:97
TKey Key
Definition: hash.h:12
void SaveXml(TSOut &SOut, const TStr &Nm)
Definition: xmlser.h:133
TIntV PortV
Definition: hash.h:106
static int GetPrimHashCd(const TKey &Key)
Definition: hash.h:90
void GetKeyDatPrV(TVec< TPair< TKey, TDat > > &KeyDatPrV) const
Definition: hash.h:500
THKeyDat & operator*() const
Definition: hash.h:70
void GetKeyV(TVec< TStr > &KeyV) const
Definition: hash.h:1011
static int GetSecHashCd(const TVec &Vec)
Definition: hash.h:1279
bool operator()(const int &KeyId1, const int &KeyId2) const
Definition: hash.h:117
bool DelIfKey(const TKey &Key)
Definition: hash.h:243
void Clr(bool DoDel=false)
Definition: hash.h:765
TVec< THKeyDat > KeyDatV
Definition: hash.h:107
TVal1 Val1
Definition: ds.h:34
int GetPorts() const
Definition: hash.h:844
TVal2 Val2
Definition: ds.h:35
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
Definition: bd.h:196
THash< TStrV, TInt > TStrVH
Definition: hash.h:672
static int GetSecHashCd(const TStr &s)
Definition: hash.h:1261
THash< TStr, TBool > TStrBoolH
Definition: hash.h:646
TStrHash< TIntV > TStrToIntVSH
Definition: hash.h:1060
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: hash.h:444
THash< TStrV, TStr > TStrVStrH
Definition: hash.h:675
THash< TFlt, TFlt > TFltFltH
Definition: hash.h:644
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TStrHash & operator=(const TStrHash &Hash)
Definition: hash.h:954
TVal & GetVal()
Definition: ds.h:2695
THashKeyDat< TInt, TDat > THKeyDat
Definition: hash.h:786
int GetUniDevInt(const int &Range=0)
Definition: dt.cpp:39
int GetPrimHashCd(const int &StrId)
Definition: hash.h:772
TDat & AddDat(const char *Key)
Definition: hash.h:855
const THash< TKey, TDat, THashFunc > & Hash
Definition: hash.h:113
bool IsKeyGetDat(const char *Key, TDat &Dat) const
Definition: hash.h:901
TStrHash(TSIn &SIn, bool PoolToo=true)
Definition: hash.h:809
TDat & AddDatId(const TKey &Key)
Definition: hash.h:236
THKeyDat & GetHashKeyDat(const int &KeyId)
Definition: hash.h:799
~TBigStrPool()
Definition: hash.h:726
TPt< TStringPool > PStringPool
Definition: hash.h:784
bool IsKey(const TKey &Key, int &KeyId) const
Definition: hash.h:259
static int GetPrimHashCd(const TStr &s)
Definition: hash.h:1259
char * CStr()
Definition: dt.h:479
bool IsKey(const TKey &Key) const
Definition: hash.h:258
bool operator==(const PHash< TKey, TDat > &Vec) const
Definition: hash.h:702
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
static unsigned int DJBHash(const char *Str, const ::TSize &Len)
Definition: hash.h:1246
THash< TStr, TInt > TStrIntH
Definition: hash.h:647
Definition: dt.h:974
Definition: hash.h:1065
THash< TUInt64, TStrV > TUInt64StrVH
Definition: hash.h:626
int Len() const
Definition: hash.h:228
static TPt< PHash< TKey, TDat > > New(const THash< TKey, TDat > &H)
Definition: hash.h:694
TDat & GetDat()
Definition: hash.h:82
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
THKeyDat & operator()() const
Definition: hash.h:71
bool IsKey(const char *Key, int &KeyId) const
Definition: hash.h:900
bool IsAutoSize() const
Definition: hash.h:230
TCache & operator=(const TCache &)
THash< TStrPr, TFlt > TStrPrFltH
Definition: hash.h:667
THash< TStr, TStrPrV > TStrStrPrVH
Definition: hash.h:658
THKeyDat * EndI
Definition: hash.h:54
TDat & AddDat(const TChA &Key)
Definition: hash.h:857
TInt HashCd
Definition: hash.h:11
THash< TInt, TStrV > TIntStrVH
Definition: hash.h:620
THash< TInt, TIntPr > TIntIntPrH
Definition: hash.h:622
THash< TStrPr, TInt > TStrPrIntH
Definition: hash.h:666
THash(TSIn &SIn)
Definition: hash.h:152
static int GetPrimHashCd(const TVec &Vec)
Definition: hash.h:1273
void LoadCs()
Definition: fl.h:408
TDat & AddDatId(const TChA &Key)
Definition: hash.h:860
int GetPrimHashCd() const
Definition: bd.h:506
void Pack()
Definition: hash.h:289
int AddDat(const TChA &Key, const TDat &Dat)
Definition: hash.h:854
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
bool IsKey(const TStr &Key) const
Definition: hash.h:898
THash(const THash &Hash)
Definition: hash.h:148
const TDat & GetDat(const TChA &Key)
Definition: hash.h:883
void GetDatKeyKdV(TVec< TKeyDat< TDat, TKey > > &DatKeyKdV) const
Definition: hash.h:533
int GetStrs() const
Definition: hash.h:741
THash< TInt, TIntPrV > TIntIntPrVH
Definition: hash.h:623
void GetKeyDatKdV(TVec< TKeyDat< TKey, TDat > > &KeyDatKdV) const
Definition: hash.h:522
THash< TInt, TIntStrPr > TIntIntStrPrH
Definition: hash.h:624
static int GetSecHashCd(const char *p)
Definition: hash.cpp:123
THash< TInt, TBool > TIntBoolH
Definition: hash.h:609
int GetKeyId(const char *Key) const
Definition: hash.h:994
void Swap(TRec &Rec1, TRec &Rec2)
Definition: bd.h:568
void MarkDelKeyId(const int &KeyId)
Definition: hash.h:250
bool IsKeyId(const int &KeyId) const
Definition: hash.h:904
void SaveXml(TSOut &SOut, const TStr &Nm) const
Definition: xmlser.h:123
THashKeyDatI & operator--(int)
Definition: hash.h:69
const TDat & GetDat(const char *Key) const
Definition: hash.h:879
static int GetPrimHashCd(const char *p)
Definition: hash.h:1253
void * GetRefToBs()
Definition: hash.h:1096
TIter GetI(const TKey &Key) const
Definition: hash.h:220
void SortByDat(const bool &Asc=true)
Definition: hash.h:292
TLstNd * Next() const
Definition: ds.h:2694
static int GetSecHashCd(const char *p)
Definition: hash.h:1225