SNAP Library 2.2, Developer Reference  2014-03-11 19:15:55
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
hash.h
Go to the documentation of this file.
00001 #include "bd.h"
00002 
00004 // Hash-Table-Key-Data
00005 #pragma pack(push, 1) // pack class size
00006 template <class TKey, class TDat>
00007 class THashKeyDat{
00008 public:
00009   TInt Next;
00010   TInt HashCd;
00011   TKey Key;
00012   TDat Dat;
00013 public:
00014   THashKeyDat():
00015     Next(-1), HashCd(-1), Key(), Dat(){}
00016   THashKeyDat(const int& _Next, const int& _HashCd, const TKey& _Key):
00017     Next(_Next), HashCd(_HashCd), Key(_Key), Dat(){}
00018   explicit THashKeyDat(TSIn& SIn):
00019     Next(SIn), HashCd(SIn), Key(SIn), Dat(SIn){}
00020   void Save(TSOut& SOut) const {
00021     Next.Save(SOut); HashCd.Save(SOut); Key.Save(SOut); Dat.Save(SOut);}
00022   void LoadXml(const PXmlTok& XmlTok, const TStr& Nm="");
00023   void SaveXml(TSOut& SOut, const TStr& Nm) const;
00024 
00025   bool operator==(const THashKeyDat& HashKeyDat) const {
00026     if (this==&HashKeyDat || (HashCd==HashKeyDat.HashCd
00027       && Key==HashKeyDat.Key && Dat==HashKeyDat.Dat)){return true;}
00028     return false;}
00029   THashKeyDat& operator=(const THashKeyDat& HashKeyDat){
00030     if (this!=&HashKeyDat){
00031       Next=HashKeyDat.Next; HashCd=HashKeyDat.HashCd;
00032       Key=HashKeyDat.Key; Dat=HashKeyDat.Dat;}
00033     return *this;}
00034 };
00035 #pragma pack(pop)
00036 
00038 // Hash-Table-Key-Data-Iterator
00039 template<class TKey, class TDat>
00040 class THashKeyDatI{
00041 public:
00042   typedef THashKeyDat<TKey, TDat> THKeyDat;
00043 private:
00044   THKeyDat* KeyDatI;
00045   THKeyDat* EndI;
00046 public:
00047   THashKeyDatI(): KeyDatI(NULL), EndI(NULL){}
00048   THashKeyDatI(const THashKeyDatI& _HashKeyDatI):
00049     KeyDatI(_HashKeyDatI.KeyDatI), EndI(_HashKeyDatI.EndI){}
00050   THashKeyDatI(const THKeyDat* _KeyDatI, const THKeyDat* _EndI):
00051     KeyDatI((THKeyDat*)_KeyDatI), EndI((THKeyDat*)_EndI){}
00052 
00053   THashKeyDatI& operator=(const THashKeyDatI& HashKeyDatI){
00054     KeyDatI=HashKeyDatI.KeyDatI; EndI=HashKeyDatI.EndI; return *this;}
00055   bool operator==(const THashKeyDatI& HashKeyDatI) const {
00056     return KeyDatI==HashKeyDatI.KeyDatI;}
00057   bool operator<(const THashKeyDatI& HashKeyDatI) const {
00058     return KeyDatI<HashKeyDatI.KeyDatI;}
00059   THashKeyDatI& operator++(int){ KeyDatI++; while (KeyDatI < EndI && KeyDatI->HashCd==-1) { KeyDatI++; } return *this; }
00060   THashKeyDatI& operator--(int){ do { KeyDatI--; } while (KeyDatI->HashCd==-1); return *this;}
00061   THKeyDat& operator*() const { return *KeyDatI; }
00062   THKeyDat& operator()() const { return *KeyDatI; }
00063   THKeyDat* operator->() const { return KeyDatI; }
00064   THashKeyDatI& Next(){ operator++(1); return *this; }
00065 
00067   bool IsEmpty() const { return KeyDatI == NULL; }
00069   bool IsEnd() const { return EndI == KeyDatI; }
00070   
00071   const TKey& GetKey() const {Assert((KeyDatI!=NULL)&&(KeyDatI->HashCd!=-1)); return KeyDatI->Key;}
00072   const TDat& GetDat() const {Assert((KeyDatI!=NULL)&&(KeyDatI->HashCd!=-1)); return KeyDatI->Dat;}
00073   TDat& GetDat() {Assert((KeyDatI!=NULL)&&(KeyDatI->HashCd!=-1)); return KeyDatI->Dat;}
00074 };
00075 
00077 // Default-Hash-Function
00078 template<class TKey>
00079 class TDefaultHashFunc {
00080 public:
00081  static inline int GetPrimHashCd(const TKey& Key) { return Key.GetPrimHashCd(); }
00082  static inline int GetSecHashCd(const TKey& Key) { return Key.GetSecHashCd(); }
00083 };
00084 
00086 // Hash-Table
00087 template<class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey> >
00088 class THash{
00089 public:
00090   enum {HashPrimes=32};
00091   static const unsigned int HashPrimeT[HashPrimes];
00092 public:
00093   typedef THashKeyDatI<TKey, TDat> TIter;
00094 private:
00095   typedef THashKeyDat<TKey, TDat> THKeyDat;
00096   typedef TPair<TKey, TDat> TKeyDatP;
00097   TIntV PortV;
00098   TVec<THKeyDat> KeyDatV;
00099   TBool AutoSizeP;
00100   TInt FFreeKeyId, FreeKeys;
00101 private:
00102   class THashKeyDatCmp {
00103   public:
00104     const THash<TKey, TDat, THashFunc>& Hash;
00105     bool CmpKey, Asc;
00106     THashKeyDatCmp(THash<TKey, TDat, THashFunc>& _Hash, const bool& _CmpKey, const bool& _Asc) :
00107       Hash(_Hash), CmpKey(_CmpKey), Asc(_Asc) { }
00108     bool operator () (const int& KeyId1, const int& KeyId2) const {
00109       if (CmpKey) {
00110         if (Asc) { return Hash.GetKey(KeyId1) < Hash.GetKey(KeyId2); }
00111         else { return Hash.GetKey(KeyId2) < Hash.GetKey(KeyId1); } }
00112       else {
00113         if (Asc) { return Hash[KeyId1] < Hash[KeyId2]; }
00114         else { return Hash[KeyId2] < Hash[KeyId1]; } } }
00115   };
00116 private:
00117   THKeyDat& GetHashKeyDat(const int& KeyId){
00118     THKeyDat& KeyDat=KeyDatV[KeyId];
00119     Assert(KeyDat.HashCd!=-1); return KeyDat;}
00120   const THKeyDat& GetHashKeyDat(const int& KeyId) const {
00121     const THKeyDat& KeyDat=KeyDatV[KeyId];
00122     Assert(KeyDat.HashCd!=-1); return KeyDat;}
00123   uint GetNextPrime(const uint& Val) const;
00124   void Resize();
00125 public:
00126   THash():
00127     PortV(), KeyDatV(),
00128     AutoSizeP(true), FFreeKeyId(-1), FreeKeys(0){}
00129   THash(const THash& Hash):
00130     PortV(Hash.PortV), KeyDatV(Hash.KeyDatV), AutoSizeP(Hash.AutoSizeP),
00131     FFreeKeyId(Hash.FFreeKeyId), FreeKeys(Hash.FreeKeys){}
00132   explicit THash(const int& ExpectVals, const bool& _AutoSizeP=false);
00133   explicit THash(TSIn& SIn):
00134     PortV(SIn), KeyDatV(SIn),
00135     AutoSizeP(SIn), FFreeKeyId(SIn), FreeKeys(SIn){
00136     SIn.LoadCs();}
00137   void Load(TSIn& SIn){
00138     PortV.Load(SIn); KeyDatV.Load(SIn);
00139     AutoSizeP=TBool(SIn); FFreeKeyId=TInt(SIn); FreeKeys=TInt(SIn);
00140     SIn.LoadCs();}
00141   void Save(TSOut& SOut) const {
00142     PortV.Save(SOut); KeyDatV.Save(SOut);
00143     AutoSizeP.Save(SOut); FFreeKeyId.Save(SOut); FreeKeys.Save(SOut);
00144     SOut.SaveCs();}
00145   void LoadXml(const PXmlTok& XmlTok, const TStr& Nm="");
00146   void SaveXml(TSOut& SOut, const TStr& Nm);
00147 
00148   THash& operator=(const THash& Hash){
00149     if (this!=&Hash){
00150       PortV=Hash.PortV; KeyDatV=Hash.KeyDatV; AutoSizeP=Hash.AutoSizeP;
00151       FFreeKeyId=Hash.FFreeKeyId; FreeKeys=Hash.FreeKeys;}
00152     return *this;}
00153   bool operator==(const THash& Hash) const; //J: zdaj tak kot je treba
00154   bool operator < (const THash& Hash) const { Fail; return true; }
00155   const TDat& operator[](const int& KeyId) const {return GetHashKeyDat(KeyId).Dat;}
00156   TDat& operator[](const int& KeyId){return GetHashKeyDat(KeyId).Dat;}
00157   TDat& operator()(const TKey& Key){return AddDat(Key);}
00158   ::TSize GetMemUsed() const {
00159     // return PortV.GetMemUsed()+KeyDatV.GetMemUsed()+sizeof(bool)+2*sizeof(int);}
00160       int64 MemUsed = sizeof(bool)+2*sizeof(int);
00161       MemUsed += int64(PortV.Reserved()) * int64(sizeof(TInt));
00162       for (int KeyDatN = 0; KeyDatN < KeyDatV.Len(); KeyDatN++) {
00163           MemUsed += int64(2 * sizeof(TInt));
00164           MemUsed += int64(KeyDatV[KeyDatN].Key.GetMemUsed());
00165           MemUsed += int64(KeyDatV[KeyDatN].Dat.GetMemUsed());
00166       }
00167       return ::TSize(MemUsed);
00168   }
00169 
00170   TIter BegI() const {
00171     if (Len() == 0){return TIter(KeyDatV.EndI(), KeyDatV.EndI());}
00172     if (IsKeyIdEqKeyN()) { return TIter(KeyDatV.BegI(), KeyDatV.EndI());}
00173     int FKeyId=-1;  FNextKeyId(FKeyId);
00174     return TIter(KeyDatV.BegI()+FKeyId, KeyDatV.EndI()); }
00175   TIter EndI() const {return TIter(KeyDatV.EndI(), KeyDatV.EndI());}
00176   //TIter GetI(const int& KeyId) const {return TIter(&KeyDatV[KeyId], KeyDatV.EndI());}
00177   TIter GetI(const TKey& Key) const {return TIter(&KeyDatV[GetKeyId(Key)], KeyDatV.EndI());}
00178 
00179   void Gen(const int& ExpectVals){
00180     PortV.Gen(GetNextPrime(ExpectVals/2)); KeyDatV.Gen(ExpectVals, 0);
00181     FFreeKeyId=-1; FreeKeys=0; PortV.PutAll(TInt(-1));}
00182 
00183   void Clr(const bool& DoDel=true, const int& NoDelLim=-1, const bool& ResetDat=true);
00184   bool Empty() const {return Len()==0;}
00185   int Len() const {return KeyDatV.Len()-FreeKeys;}
00186   int GetPorts() const {return PortV.Len();}
00187   bool IsAutoSize() const {return AutoSizeP;}
00188   int GetMxKeyIds() const {return KeyDatV.Len();}
00189   int GetReservedKeyIds() const {return KeyDatV.Reserved();}
00190   bool IsKeyIdEqKeyN() const {return FreeKeys==0;}
00191 
00192   int AddKey(const TKey& Key);
00193   TDat& AddDatId(const TKey& Key){
00194     int KeyId=AddKey(Key); return KeyDatV[KeyId].Dat=KeyId;}
00195   TDat& AddDat(const TKey& Key){return KeyDatV[AddKey(Key)].Dat;}
00196   TDat& AddDat(const TKey& Key, const TDat& Dat){
00197     return KeyDatV[AddKey(Key)].Dat=Dat;}
00198 
00199   void DelKey(const TKey& Key);
00200   bool DelIfKey(const TKey& Key){
00201     int KeyId; if (IsKey(Key, KeyId)){DelKeyId(KeyId); return true;} return false;}
00202   void DelKeyId(const int& KeyId){DelKey(GetKey(KeyId));}
00203   void DelKeyIdV(const TIntV& KeyIdV){
00204     for (int KeyIdN=0; KeyIdN<KeyIdV.Len(); KeyIdN++){DelKeyId(KeyIdV[KeyIdN]);}}
00205 
00206   void MarkDelKey(const TKey& Key); // marks the record as deleted - doesn't delete Dat (to avoid fragmentation)
00207   void MarkDelKeyId(const int& KeyId){MarkDelKey(GetKey(KeyId));}
00208 
00209   const TKey& GetKey(const int& KeyId) const { return GetHashKeyDat(KeyId).Key;}
00210   int GetKeyId(const TKey& Key) const;
00212   int GetRndKeyId(TRnd& Rnd) const;
00214   int GetRndKeyId(TRnd& Rnd, const double& EmptyFrac);
00215   bool IsKey(const TKey& Key) const {return GetKeyId(Key)!=-1;}
00216   bool IsKey(const TKey& Key, int& KeyId) const { KeyId=GetKeyId(Key); return KeyId!=-1;}
00217   bool IsKeyId(const int& KeyId) const {
00218     return (0<=KeyId)&&(KeyId<KeyDatV.Len())&&(KeyDatV[KeyId].HashCd!=-1);}
00219   const TDat& GetDat(const TKey& Key) const {return KeyDatV[GetKeyId(Key)].Dat;}
00220   TDat& GetDat(const TKey& Key){return KeyDatV[GetKeyId(Key)].Dat;}
00221 //  TKeyDatP GetKeyDat(const int& KeyId) const {
00222 //    TKeyDat& KeyDat=GetHashKeyDat(KeyId);
00223 //    return TKeyDatP(KeyDat.Key, KeyDat.Dat);}
00224   void GetKeyDat(const int& KeyId, TKey& Key, TDat& Dat) const {
00225     const THKeyDat& KeyDat=GetHashKeyDat(KeyId);
00226     Key=KeyDat.Key; Dat=KeyDat.Dat;}
00227   bool IsKeyGetDat(const TKey& Key, TDat& Dat) const {int KeyId;
00228     if (IsKey(Key, KeyId)){Dat=GetHashKeyDat(KeyId).Dat; return true;}
00229     else {return false;}}
00230 
00231   int FFirstKeyId() const {return 0-1;}
00232   bool FNextKeyId(int& KeyId) const;
00233   void GetKeyV(TVec<TKey>& KeyV) const;
00234   void GetDatV(TVec<TDat>& DatV) const;
00235   void GetKeyDatPrV(TVec<TPair<TKey, TDat> >& KeyDatPrV) const;
00236   void GetDatKeyPrV(TVec<TPair<TDat, TKey> >& DatKeyPrV) const;
00237   void GetKeyDatKdV(TVec<TKeyDat<TKey, TDat> >& KeyDatKdV) const;
00238   void GetDatKeyKdV(TVec<TKeyDat<TDat, TKey> >& DatKeyKdV) const;
00239 
00240   void Swap(THash& Hash);
00241   void Defrag();
00242   void Pack(){KeyDatV.Pack();}
00243   void Sort(const bool& CmpKey, const bool& Asc);
00244   void SortByKey(const bool& Asc=true) { Sort(true, Asc); }
00245   void SortByDat(const bool& Asc=true) { Sort(false, Asc); }
00246 };
00247 
00248 template<class TKey, class TDat, class THashFunc>
00249 const unsigned int THash<TKey, TDat, THashFunc>::HashPrimeT[HashPrimes]={
00250   3ul, 5ul, 11ul, 23ul,
00251   53ul,         97ul,         193ul,       389ul,       769ul,
00252   1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
00253   49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
00254   1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
00255   50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
00256   1610612741ul, 3221225473ul, 4294967291ul
00257 };
00258 
00259 template<class TKey, class TDat, class THashFunc>
00260 uint THash<TKey, TDat, THashFunc>::GetNextPrime(const uint& Val) const {
00261   const uint* f=(const uint*)HashPrimeT, *m, *l=(const uint*)HashPrimeT + (int)HashPrimes;
00262   int h, len = (int)HashPrimes;
00263   while (len > 0) {
00264     h = len >> 1;  m = f + h;
00265     if (*m < Val) { f = m;  f++;  len = len - h - 1; }
00266     else len = h;
00267   }
00268   return f == l ? *(l - 1) : *f;
00269 }
00270 
00271 template<class TKey, class TDat, class THashFunc>
00272 void THash<TKey, TDat, THashFunc>::Resize(){
00273   // resize & initialize port vector
00274   //if (PortV.Len()==0){PortV.Gen(17);}
00275   //else {PortV.Gen(2*PortV.Len()+1);}
00276   if (PortV.Len()==0){
00277     PortV.Gen(17);
00278   } else if (AutoSizeP&&(KeyDatV.Len()>2*PortV.Len())){
00279     PortV.Gen(GetNextPrime(PortV.Len()+1));
00280   } else {
00281     return;
00282   }
00283   PortV.PutAll(TInt(-1));
00284   // rehash keys
00285   for (int KeyId=0; KeyId<KeyDatV.Len(); KeyId++){
00286     THKeyDat& KeyDat=KeyDatV[KeyId];
00287     if (KeyDat.HashCd!=-1){
00288       const int PortN = abs(THashFunc::GetPrimHashCd(KeyDat.Key) % PortV.Len());
00289       KeyDat.Next=PortV[PortN];
00290       PortV[PortN]=KeyId;
00291     }
00292   }
00293 }
00294 
00295 template<class TKey, class TDat, class THashFunc>
00296 THash<TKey, TDat, THashFunc>::THash(const int& ExpectVals, const bool& _AutoSizeP):
00297   PortV(GetNextPrime(ExpectVals/2)), KeyDatV(ExpectVals, 0),
00298   AutoSizeP(_AutoSizeP), FFreeKeyId(-1), FreeKeys(0){
00299   PortV.PutAll(TInt(-1));
00300 }
00301 
00302 template<class TKey, class TDat, class THashFunc>
00303 bool THash<TKey, TDat, THashFunc>::operator==(const THash& Hash) const {
00304   if (Len() != Hash.Len()) { return false; }
00305   for (int i = FFirstKeyId(); FNextKeyId(i); ) {
00306     const TKey& Key = GetKey(i);
00307     if (! Hash.IsKey(Key)) { return false; }
00308     if (GetDat(Key) != Hash.GetDat(Key)) { return false; }
00309   }
00310   return true;
00311 }
00312 
00313 template<class TKey, class TDat, class THashFunc>
00314 void THash<TKey, TDat, THashFunc>::Clr(const bool& DoDel, const int& NoDelLim, const bool& ResetDat){
00315   if (DoDel){
00316     PortV.Clr(); KeyDatV.Clr();
00317   } else {
00318     PortV.PutAll(TInt(-1));
00319     KeyDatV.Clr(DoDel, NoDelLim);
00320     if (ResetDat){KeyDatV.PutAll(THKeyDat());}
00321   }
00322   FFreeKeyId=TInt(-1); FreeKeys=TInt(0);
00323 }
00324 
00325 template<class TKey, class TDat, class THashFunc>
00326 int THash<TKey, TDat, THashFunc>::AddKey(const TKey& Key){
00327   if ((KeyDatV.Len()>2*PortV.Len())||PortV.Empty()){Resize();}
00328   const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
00329   const int HashCd=abs(THashFunc::GetSecHashCd(Key));
00330   int PrevKeyId=-1;
00331   int KeyId=PortV[PortN];
00332   while ((KeyId!=-1) &&
00333    !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
00334     PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}
00335 
00336   if (KeyId==-1){
00337     if (FFreeKeyId==-1){
00338       KeyId=KeyDatV.Add(THKeyDat(-1, HashCd, Key));
00339     } else {
00340       KeyId=FFreeKeyId; FFreeKeyId=KeyDatV[FFreeKeyId].Next; FreeKeys--;
00341       //KeyDatV[KeyId]=TKeyDat(-1, HashCd, Key); // slow version
00342       KeyDatV[KeyId].Next=-1;
00343       KeyDatV[KeyId].HashCd=HashCd;
00344       KeyDatV[KeyId].Key=Key;
00345       //KeyDatV[KeyId].Dat=TDat(); // already empty
00346     }
00347     if (PrevKeyId==-1){
00348       PortV[PortN]=KeyId;
00349     } else {
00350       KeyDatV[PrevKeyId].Next=KeyId;
00351     }
00352   }
00353   return KeyId;
00354 }
00355 
00356 template<class TKey, class TDat, class THashFunc>
00357 void THash<TKey, TDat, THashFunc>::DelKey(const TKey& Key){
00358   IAssert(!PortV.Empty());
00359   const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
00360   const int HashCd=abs(THashFunc::GetSecHashCd(Key));
00361   int PrevKeyId=-1;
00362   int KeyId=PortV[PortN];
00363 
00364   while ((KeyId!=-1) &&
00365    !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
00366     PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}
00367 
00368   //IAssertR(KeyId!=-1, Key.GetStr()); //J: some classes do not provide GetStr()?
00369   IAssert(KeyId!=-1); //J: some classes do not provide GetStr()?
00370   if (PrevKeyId==-1){PortV[PortN]=KeyDatV[KeyId].Next;}
00371   else {KeyDatV[PrevKeyId].Next=KeyDatV[KeyId].Next;}
00372   KeyDatV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
00373   KeyDatV[KeyId].HashCd=TInt(-1);
00374   KeyDatV[KeyId].Key=TKey();
00375   KeyDatV[KeyId].Dat=TDat();
00376 }
00377 
00378 template<class TKey, class TDat, class THashFunc>
00379 void THash<TKey, TDat, THashFunc>::MarkDelKey(const TKey& Key){
00380   // MarkDelKey is same as Delkey except last two lines
00381   IAssert(!PortV.Empty());
00382   const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
00383   const int HashCd=abs(THashFunc::GetSecHashCd(Key));
00384   int PrevKeyId=-1;
00385   int KeyId=PortV[PortN];
00386   while ((KeyId!=-1) &&
00387    !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
00388     PrevKeyId=KeyId; KeyId=KeyDatV[KeyId].Next;}
00389   IAssertR(KeyId!=-1, Key.GetStr());
00390   if (PrevKeyId==-1){PortV[PortN]=KeyDatV[KeyId].Next;}
00391   else {KeyDatV[PrevKeyId].Next=KeyDatV[KeyId].Next;}
00392   KeyDatV[KeyId].Next=FFreeKeyId; FFreeKeyId=KeyId; FreeKeys++;
00393   KeyDatV[KeyId].HashCd=TInt(-1);
00394 }
00395 
00396 template<class TKey, class TDat, class THashFunc>
00397 int THash<TKey, TDat, THashFunc>::GetRndKeyId(TRnd& Rnd) const  {
00398   IAssert(! Empty());
00399   int KeyId = abs(Rnd.GetUniDevInt(KeyDatV.Len()));
00400   while (KeyDatV[KeyId].HashCd == -1) { // if the index is empty, just try again
00401     KeyId = abs(Rnd.GetUniDevInt(KeyDatV.Len())); }
00402   return KeyId; 
00403 }
00404 
00405 // return random KeyId even if the hash table contains deleted keys
00406 // defrags the table if necessary
00407 template<class TKey, class TDat, class THashFunc>
00408 int THash<TKey, TDat, THashFunc>::GetRndKeyId(TRnd& Rnd, const double& EmptyFrac) {
00409   IAssert(! Empty());
00410   if (FreeKeys/double(Len()+FreeKeys) > EmptyFrac) { Defrag(); }
00411   int KeyId = Rnd.GetUniDevInt(KeyDatV.Len());
00412   while (KeyDatV[KeyId].HashCd == -1) { // if the index is empty, just try again
00413     KeyId = Rnd.GetUniDevInt(KeyDatV.Len());
00414   }
00415   return KeyId;
00416 }
00417 
00418 template<class TKey, class TDat, class THashFunc>
00419 int THash<TKey, TDat, THashFunc>::GetKeyId(const TKey& Key) const {
00420   if (PortV.Empty()){return -1;}
00421   const int PortN=abs(THashFunc::GetPrimHashCd(Key)%PortV.Len());
00422   const int HashCd=abs(THashFunc::GetSecHashCd(Key));
00423   int KeyId=PortV[PortN];
00424   while ((KeyId!=-1) &&
00425    !((KeyDatV[KeyId].HashCd==HashCd) && (KeyDatV[KeyId].Key==Key))){
00426     KeyId=KeyDatV[KeyId].Next;}
00427   return KeyId;
00428 }
00429 
00430 template<class TKey, class TDat, class THashFunc>
00431 bool THash<TKey, TDat, THashFunc>::FNextKeyId(int& KeyId) const {
00432   do {KeyId++;} while ((KeyId<KeyDatV.Len())&&(KeyDatV[KeyId].HashCd==-1));
00433   return KeyId<KeyDatV.Len();
00434 }
00435 
00436 template<class TKey, class TDat, class THashFunc>
00437 void THash<TKey, TDat, THashFunc>::GetKeyV(TVec<TKey>& KeyV) const {
00438   KeyV.Gen(Len(), 0);
00439   int KeyId=FFirstKeyId();
00440   while (FNextKeyId(KeyId)){
00441     KeyV.Add(GetKey(KeyId));}
00442 }
00443 
00444 template<class TKey, class TDat, class THashFunc>
00445 void THash<TKey, TDat, THashFunc>::GetDatV(TVec<TDat>& DatV) const {
00446   DatV.Gen(Len(), 0);
00447   int KeyId=FFirstKeyId();
00448   while (FNextKeyId(KeyId)){
00449     DatV.Add(GetHashKeyDat(KeyId).Dat);}
00450 }
00451 
00452 template<class TKey, class TDat, class THashFunc>
00453 void THash<TKey, TDat, THashFunc>::GetKeyDatPrV(TVec<TPair<TKey, TDat> >& KeyDatPrV) const {
00454   KeyDatPrV.Gen(Len(), 0);
00455   TKey Key; TDat Dat;
00456   int KeyId=FFirstKeyId();
00457   while (FNextKeyId(KeyId)){
00458     GetKeyDat(KeyId, Key, Dat);
00459     KeyDatPrV.Add(TPair<TKey, TDat>(Key, Dat));
00460   }
00461 }
00462 
00463 template<class TKey, class TDat, class THashFunc>
00464 void THash<TKey, TDat, THashFunc>::GetDatKeyPrV(TVec<TPair<TDat, TKey> >& DatKeyPrV) const {
00465   DatKeyPrV.Gen(Len(), 0);
00466   TKey Key; TDat Dat;
00467   int KeyId=FFirstKeyId();
00468   while (FNextKeyId(KeyId)){
00469     GetKeyDat(KeyId, Key, Dat);
00470     DatKeyPrV.Add(TPair<TDat, TKey>(Dat, Key));
00471   }
00472 }
00473 
00474 template<class TKey, class TDat, class THashFunc>
00475 void THash<TKey, TDat, THashFunc>::GetKeyDatKdV(TVec<TKeyDat<TKey, TDat> >& KeyDatKdV) const {
00476   KeyDatKdV.Gen(Len(), 0);
00477   TKey Key; TDat Dat;
00478   int KeyId=FFirstKeyId();
00479   while (FNextKeyId(KeyId)){
00480     GetKeyDat(KeyId, Key, Dat);
00481     KeyDatKdV.Add(TKeyDat<TKey, TDat>(Key, Dat));
00482   }
00483 }
00484 
00485 template<class TKey, class TDat, class THashFunc>
00486 void THash<TKey, TDat, THashFunc>::GetDatKeyKdV(TVec<TKeyDat<TDat, TKey> >& DatKeyKdV) const {
00487   DatKeyKdV.Gen(Len(), 0);
00488   TKey Key; TDat Dat;
00489   int KeyId=FFirstKeyId();
00490   while (FNextKeyId(KeyId)){
00491     GetKeyDat(KeyId, Key, Dat);
00492     DatKeyKdV.Add(TKeyDat<TDat, TKey>(Dat, Key));
00493   }
00494 }
00495 
00496 template<class TKey, class TDat, class THashFunc>
00497 void THash<TKey, TDat, THashFunc>::Swap(THash& Hash) {
00498   if (this!=&Hash){
00499     PortV.Swap(Hash.PortV);
00500     KeyDatV.Swap(Hash.KeyDatV);
00501     ::Swap(AutoSizeP, Hash.AutoSizeP);
00502     ::Swap(FFreeKeyId, Hash.FFreeKeyId);
00503     ::Swap(FreeKeys, Hash.FreeKeys);
00504   }
00505 }
00506 
00507 template<class TKey, class TDat, class THashFunc>
00508 void THash<TKey, TDat, THashFunc>::Defrag(){
00509   if (!IsKeyIdEqKeyN()){
00510     THash<TKey, TDat, THashFunc> Hash(PortV.Len());
00511     int KeyId=FFirstKeyId(); TKey Key; TDat Dat;
00512     while (FNextKeyId(KeyId)){
00513       GetKeyDat(KeyId, Key, Dat);
00514       Hash.AddDat(Key, Dat);
00515     }
00516     Pack();
00517     operator=(Hash);
00518     IAssert(IsKeyIdEqKeyN());
00519   }
00520 }
00521 
00522 template<class TKey, class TDat, class THashFunc>
00523 void THash<TKey, TDat, THashFunc>::Sort(const bool& CmpKey, const bool& Asc) {
00524   IAssertR(IsKeyIdEqKeyN(), "THash::Sort only works when table has no deleted keys.");
00525   TIntV TargV(Len()), MapV(Len()), StateV(Len());
00526   for (int i = 0; i < TargV.Len(); i++) {
00527     TargV[i] = i; MapV[i] = i; StateV[i] = i;
00528   }
00529   // sort KeyIds
00530   THashKeyDatCmp HashCmp(*this, CmpKey, Asc);
00531   TargV.SortCmp(HashCmp);
00532   // now sort the update vector
00533   THashKeyDat<TKey, TDat> Tmp;
00534   for (int i = 0; i < TargV.Len()-1; i++) {
00535     const int SrcPos = MapV[TargV[i]];
00536     const int Loc = i;
00537     // swap data
00538     Tmp = KeyDatV[SrcPos];
00539     KeyDatV[SrcPos] = KeyDatV[Loc];
00540     KeyDatV[Loc] = Tmp;
00541     // swap keys
00542     MapV[StateV[i]] = SrcPos;
00543     StateV.Swap(Loc, SrcPos);
00544   }
00545   for (int i = 0; i < TargV.Len(); i++) {
00546     MapV[TargV[i]] = i; }
00547   for (int p = 0; p < PortV.Len(); p++) {
00548     if (PortV[p] != -1) {
00549       PortV[p] = MapV[PortV[p]]; } }
00550   for (int i = 0; i < KeyDatV.Len(); i++) {
00551     if (KeyDatV[i].Next != -1) {
00552       KeyDatV[i].Next = MapV[KeyDatV[i].Next]; }
00553   }
00554 }
00555 
00557 // Common-Hash-Types
00558 typedef THash<TCh, TCh> TChChH;
00559 typedef THash<TChTr, TInt> TChTrIntH;
00560 typedef THash<TInt, TInt> TIntH;
00561 typedef THash<TUInt64, TInt> TUInt64H;
00562 typedef THash<TInt, TBool> TIntBoolH;
00563 typedef THash<TInt, TInt> TIntIntH;
00564 typedef THash<TInt, TUInt64> TIntUInt64H;
00565 typedef THash<TInt, TIntFltPr> TIntIntFltPrH;
00566 typedef THash<TInt, TIntV> TIntIntVH;
00567 typedef THash<TInt, TIntH> TIntIntHH;
00568 typedef THash<TInt, TFlt> TIntFltH;
00569 typedef THash<TInt, TFltPr> TIntFltPrH;
00570 typedef THash<TInt, TFltTr> TIntFltTrH;
00571 typedef THash<TInt, TFltV> TIntFltVH;
00572 typedef THash<TInt, TStr> TIntStrH;
00573 typedef THash<TInt, TStrV> TIntStrVH;
00574 typedef THash<TInt, TIntPr> TIntIntPrH;
00575 typedef THash<TInt, TIntPrV> TIntIntPrVH;
00576 typedef THash<TUInt64, TStrV> TUInt64StrVH;
00577 typedef THash<TIntPr, TInt> TIntPrIntH;
00578 typedef THash<TIntPr, TIntV> TIntPrIntVH;
00579 typedef THash<TIntPr, TIntPrV> TIntPrIntPrVH;
00580 typedef THash<TIntTr, TInt> TIntTrIntH;
00581 typedef THash<TIntV, TInt> TIntVIntH;
00582 typedef THash<TUInt, TUInt> TUIntH;
00583 typedef THash<TIntPr, TInt> TIntPrIntH;
00584 typedef THash<TIntPr, TIntV> TIntPrIntVH;
00585 typedef THash<TIntPr, TFlt> TIntPrFltH;
00586 typedef THash<TIntTr, TFlt> TIntTrFltH;
00587 typedef THash<TIntPr, TStr> TIntPrStrH;
00588 typedef THash<TIntPr, TStrV> TIntPrStrVH;
00589 typedef THash<TIntStrPr, TInt> TIntStrPrIntH;
00590 typedef THash<TFlt, TFlt> TFltFltH;
00591 typedef THash<TStr, TInt> TStrH;
00592 typedef THash<TStr, TBool> TStrBoolH;
00593 typedef THash<TStr, TInt> TStrIntH;
00594 typedef THash<TStr, TIntPr> TStrIntPrH;
00595 typedef THash<TStr, TIntV> TStrIntVH;
00596 typedef THash<TStr, TUInt64> TStrUInt64H;
00597 typedef THash<TStr, TUInt64V> TStrUInt64VH;
00598 typedef THash<TStr, TIntPrV> TStrIntPrVH;
00599 typedef THash<TStr, TFlt> TStrFltH;
00600 typedef THash<TStr, TFltV> TStrFltVH;
00601 typedef THash<TStr, TStr> TStrStrH;
00602 typedef THash<TStr, TStrPr> TStrStrPrH;
00603 typedef THash<TStr, TStrV> TStrStrVH;
00604 typedef THash<TStr, TStrPrV> TStrStrPrVH;
00605 typedef THash<TStr, TStrKdV> TStrStrKdVH;
00606 typedef THash<TStr, TIntFltPr> TStrIntFltPrH;
00607 typedef THash<TStr, TStrIntPrV> TStrStrIntPrVH;
00608 typedef THash<TStr, TStrIntKdV> TStrStrIntKdVH;
00609 typedef THash<TDbStr, TInt> TDbStrIntH;
00610 typedef THash<TDbStr, TStr> TDbStrStrH;
00611 typedef THash<TStrPr, TBool> TStrPrBoolH;
00612 typedef THash<TStrPr, TInt> TStrPrIntH;
00613 typedef THash<TStrPr, TFlt> TStrPrFltH;
00614 typedef THash<TStrPr, TStr> TStrPrStrH;
00615 typedef THash<TStrPr, TStrV> TStrPrStrVH;
00616 typedef THash<TStrTr, TInt> TStrTrIntH;
00617 typedef THash<TStrIntPr, TInt> TStrIntPrIntH;
00618 typedef THash<TStrV, TInt> TStrVH;
00619 typedef THash<TStrV, TInt> TStrVIntH;
00620 typedef THash<TStrV, TIntV> TStrVIntVH;
00621 typedef THash<TStrV, TStr> TStrVStrH;
00622 typedef THash<TStrV, TStrV> TStrVStrVH;
00623 
00625 // Hash-Pointer
00626 template <class TKey, class TDat>
00627 class PHash{
00628 private:
00629   TCRef CRef;
00630 public:
00631   THash<TKey, TDat> H;
00632 public:
00633   PHash<TKey, TDat>(): H(){}
00634   static TPt<PHash<TKey, TDat> > New(){
00635     return new PHash<TKey, TDat>();}
00636   PHash<TKey, TDat>(const int& MxVals, const int& Vals): H(MxVals, Vals){}
00637   static TPt<PHash<TKey, TDat> > New(const int& MxVals, const int& Vals){
00638     return new PHash<TKey, TDat>(MxVals, Vals);}
00639   PHash<TKey, TDat>(const THash<TKey, TDat>& _V): H(_V){}
00640   static TPt<PHash<TKey, TDat> > New(const THash<TKey, TDat>& H){
00641     return new PHash<TKey, TDat>(H);}
00642   explicit PHash<TKey, TDat>(TSIn& SIn): H(SIn){}
00643   static TPt<PHash<TKey, TDat> > Load(TSIn& SIn){return new PHash<TKey, TDat>(SIn);}
00644   void Save(TSOut& SOut) const {H.Save(SOut);}
00645 
00646   PHash<TKey, TDat>& operator=(const PHash<TKey, TDat>& Vec){
00647     if (this!=&Vec){H=Vec.H;} return *this;}
00648   bool operator==(const PHash<TKey, TDat>& Vec) const {return H==Vec.H;}
00649   bool operator<(const PHash<TKey, TDat>& Vec) const {return H<Vec.H;}
00650 
00651   friend class TPt<PHash<TKey, TDat> >;
00652 };
00653 
00655 // Big-String-Pool (holds up to 2 giga strings, storage overhead is 8(4) bytes per string)
00656 //J: have to put it here since it uses TVec (can't be in dt.h)
00657 ClassTP(TBigStrPool, PBigStrPool)//{
00658 private:
00659   TSize MxBfL, BfL;
00660   uint GrowBy;
00661   char *Bf;
00662   TVec<TSize> IdOffV; // string ID to offset
00663 private:
00664   void Resize(TSize _MxBfL);
00665 public:
00666   TBigStrPool(TSize MxBfLen = 0, uint _GrowBy = 16*1024*1024);
00667   TBigStrPool(TSIn& SIn, bool LoadCompact = true);
00668   TBigStrPool(const TBigStrPool& Pool) : MxBfL(Pool.MxBfL), BfL(Pool.BfL), GrowBy(Pool.GrowBy) {
00669     Bf = (char *) malloc(Pool.MxBfL); IAssert(Bf); memcpy(Bf, Pool.Bf, Pool.BfL); }
00670   ~TBigStrPool() { if (Bf) free(Bf); else IAssert(MxBfL == 0);  MxBfL = 0; BfL = 0; }
00671 
00672   static PBigStrPool New(TSize _MxBfLen = 0, uint _GrowBy = 16*1024*1024) { return PBigStrPool(new TBigStrPool(_MxBfLen, _GrowBy)); }
00673   static PBigStrPool New(TSIn& SIn) { return new TBigStrPool(SIn); }
00674   static PBigStrPool New(const TStr& fileName) { PSIn SIn = TFIn::New(fileName); return new TBigStrPool(*SIn); }
00675   static PBigStrPool Load(TSIn& SIn, bool LoadCompacted = true) { return PBigStrPool(new TBigStrPool(SIn, LoadCompacted)); }
00676   void Save(TSOut& SOut) const;
00677   void Save(const TStr& fileName) { TFOut FOut(fileName); Save(FOut); }
00678 
00679   int GetStrs() const { return IdOffV.Len(); }
00680   TSize Len() const { return BfL; }
00681   TSize Size() const { return MxBfL; }
00682   bool Empty() const { return ! Len(); }
00683   char* operator () () const { return Bf; }
00684   TBigStrPool& operator = (const TBigStrPool& Pool);
00685 
00686   int AddStr(const char *Str, uint Len);
00687   int AddStr(const char *Str) { return AddStr(Str, uint(strlen(Str)) + 1); }
00688   int AddStr(const TStr& Str) { return AddStr(Str.CStr(), Str.Len() + 1); }
00689 
00690   TStr GetStr(const int& StrId) const { Assert(StrId < GetStrs());
00691     if (StrId == 0) return TStr::GetNullStr(); else return TStr(Bf + (TSize)IdOffV[StrId]); }
00692   const char *GetCStr(const int& StrId) const { Assert(StrId < GetStrs());
00693     if (StrId == 0) return TStr::GetNullStr().CStr(); else return (Bf + (TSize)IdOffV[StrId]); }
00694   
00695   TStr GetStrFromOffset(const TSize& Offset) const { Assert(Offset < BfL);
00696     if (Offset == 0) return TStr::GetNullStr(); else return TStr(Bf + Offset); }
00697   const char *GetCStrFromOffset(const TSize& Offset) const { Assert(Offset < BfL);
00698     if (Offset == 0) return TStr::GetNullStr().CStr(); else return Bf + Offset; }
00699 
00700   void Clr(bool DoDel = false) { BfL = 0; if (DoDel && Bf) { free(Bf); Bf = 0; MxBfL = 0; } }
00701   int Cmp(const int& StrId, const char *Str) const { Assert(StrId < GetStrs());
00702     if (StrId != 0) return strcmp(Bf + (TSize)IdOffV[StrId], Str); else return strcmp("", Str); }
00703 
00704   static int GetPrimHashCd(const char *CStr);
00705   static int GetSecHashCd(const char *CStr);
00706   int GetPrimHashCd(const int& StrId) { Assert(StrId < GetStrs());
00707     if (StrId != 0) return GetPrimHashCd(Bf + (TSize)IdOffV[StrId]); else return GetPrimHashCd(""); }
00708   int GetSecHashCd(const int& StrId) { Assert(StrId < GetStrs());
00709     if (StrId != 0) return GetSecHashCd(Bf + (TSize)IdOffV[StrId]); else return GetSecHashCd(""); }
00710 };
00711 
00713 // String-Hash-Table
00714 template <class TDat, class TStringPool = TStrPool, class THashFunc = TDefaultHashFunc<TStr> >
00715 class TStrHash{
00716 private:
00717   //typedef typename PStringPool::TObj TStringPool;
00718   typedef TPt<TStringPool> PStringPool;
00719   typedef THashKeyDat<TInt, TDat> THKeyDat;
00720   typedef TPair<TInt, TDat> TKeyDatP;
00721   typedef TVec<THKeyDat> THKeyDatV;
00722   TIntV PortV;
00723   THKeyDatV KeyDatV;
00724   TBool AutoSizeP;
00725   TInt FFreeKeyId, FreeKeys;
00726   PStringPool Pool;
00727 private:
00728   uint GetNextPrime(const uint& Val) const;
00729   void Resize();
00730   const THKeyDat& GetHashKeyDat(const int& KeyId) const {
00731     const THKeyDat& KeyDat = KeyDatV[KeyId];  Assert(KeyDat.HashCd != -1);  return KeyDat; }
00732   THKeyDat& GetHashKeyDat(const int& KeyId) {
00733     THKeyDat& KeyDat = KeyDatV[KeyId];  Assert(KeyDat.HashCd != -1);  return KeyDat; }
00734 public:
00735   TStrHash(): PortV(), KeyDatV(), AutoSizeP(true), FFreeKeyId(-1), FreeKeys(0), Pool() { }
00736   TStrHash(const PStringPool& StrPool): PortV(), KeyDatV(), AutoSizeP(true), FFreeKeyId(-1), FreeKeys(0), Pool(StrPool) { }
00737   TStrHash(const int& Ports, const bool& _AutoSizeP = false, const PStringPool& StrPool = PStringPool()) :
00738     PortV(Ports), KeyDatV(Ports, 0), AutoSizeP(_AutoSizeP), FFreeKeyId(-1), FreeKeys(0), Pool(StrPool) { PortV.PutAll(-1); }
00739   TStrHash(const TStrHash& Hash): PortV(Hash.PortV), KeyDatV(Hash.KeyDatV), AutoSizeP(Hash.AutoSizeP),
00740     FFreeKeyId(Hash.FFreeKeyId), FreeKeys(Hash.FreeKeys), Pool() {
00741       if (! Hash.Pool.Empty()) { Pool=PStringPool(new TStringPool(*Hash.Pool)); } }
00742   TStrHash(TSIn& SIn, bool PoolToo = true): PortV(SIn), KeyDatV(SIn), AutoSizeP(SIn), FFreeKeyId(SIn), FreeKeys(SIn){ SIn.LoadCs(); if (PoolToo) Pool = PStringPool(SIn); }
00743 
00744   void Load(TSIn& SIn, bool PoolToo = true) { PortV.Load(SIn); KeyDatV.Load(SIn); AutoSizeP.Load(SIn); FFreeKeyId.Load(SIn);
00745     FreeKeys.Load(SIn); SIn.LoadCs(); if (PoolToo) Pool = PStringPool(SIn); }
00746   void Save(TSOut& SOut, bool PoolToo = true) const { PortV.Save(SOut); KeyDatV.Save(SOut);
00747     AutoSizeP.Save(SOut); FFreeKeyId.Save(SOut); FreeKeys.Save(SOut); SOut.SaveCs(); if (PoolToo) Pool.Save(SOut); }
00748 
00749   void SetPool(const PStringPool& StrPool) { IAssert(Pool.Empty() || Pool->Empty()); Pool = StrPool; }
00750   PStringPool GetPool() const { return Pool; }
00751 
00752   TStrHash& operator = (const TStrHash& Hash);
00753 
00754   bool Empty() const {return ! Len(); }
00755   int Len() const { return KeyDatV.Len() - FreeKeys; }
00756   int Reserved() const { return KeyDatV.Reserved(); }
00757   int GetPorts() const { return PortV.Len(); }
00758   bool IsAutoSize() const { return AutoSizeP; }
00759   int GetMxKeyIds() const { return KeyDatV.Len(); }
00760   bool IsKeyIdEqKeyN() const {return ! FreeKeys; }
00761 
00762   int AddKey(const char *Key);
00763   int AddKey(const TStr& Key) { return AddKey(Key.CStr()); }
00764   int AddKey(const TChA& Key) { return AddKey(Key.CStr()); }
00765   int AddDat(const char *Key, const TDat& Dat) { const int KeyId = AddKey(Key); KeyDatV[KeyId].Dat = Dat; return KeyId; }
00766   int AddDat(const TStr& Key, const TDat& Dat) { const int KeyId = AddKey(Key.CStr()); KeyDatV[KeyId].Dat = Dat; return KeyId; }
00767   int AddDat(const TChA& Key, const TDat& Dat) { const int KeyId = AddKey(Key.CStr()); KeyDatV[KeyId].Dat = Dat; return KeyId; }
00768   TDat& AddDat(const char *Key) { return KeyDatV[AddKey(Key)].Dat; }
00769   TDat& AddDat(const TStr& Key) { return KeyDatV[AddKey(Key.CStr())].Dat; }
00770   TDat& AddDat(const TChA& Key) { return KeyDatV[AddKey(Key.CStr())].Dat; }
00771   TDat& AddDatId(const char *Key) { const int KeyId = AddKey(Key);  return KeyDatV[KeyId].Dat = KeyId; }
00772   TDat& AddDatId(const TStr& Key) { const int KeyId = AddKey(Key.CStr());  return KeyDatV[KeyId].Dat = KeyId; }
00773   TDat& AddDatId(const TChA& Key) { const int KeyId = AddKey(Key.CStr());  return KeyDatV[KeyId].Dat = KeyId; }
00774 
00775   const TDat& operator[](const int& KeyId) const {return GetHashKeyDat(KeyId).Dat;}
00776   TDat& operator[](const int& KeyId){return GetHashKeyDat(KeyId).Dat;}
00777   const TDat& operator () (const char *Key) const { return GetDat(Key);}
00778   //TDat& operator ()(const char *Key){return AddDat(Key);} // add if not found
00779 
00780   const TDat& GetDat(const char *Key) const { return KeyDatV[GetKeyId(Key)].Dat; }
00781   const TDat& GetDat(const TStr& Key) const { return GetDat(Key.CStr()); }
00782   TDat& GetDat(const char *Key) { return KeyDatV[GetKeyId(Key)].Dat; }
00783   const TDat& GetDat(const TStr& Key) { return GetDat(Key.CStr()); }
00784   const TDat& GetDat(const TChA& Key) { return GetDat(Key.CStr()); }
00785   TDat& GetDatId(const int& KeyId) { return KeyDatV[KeyId].Dat; }
00786   const TDat& GetDatId(const int& KeyId) const { return KeyDatV[KeyId].Dat; }
00787   void GetKeyDat(const int& KeyId, int& KeyO, TDat& Dat) const { const THKeyDat& KeyDat = GetHashKeyDat(KeyId); KeyO = KeyDat.Key; Dat = KeyDat.Dat; }
00788   void GetKeyDat(const int& KeyId, const char*& Key, TDat& Dat) const { const THKeyDat& KeyDat = GetHashKeyDat(KeyId); Key = KeyFromOfs(KeyDat.Key); Dat = KeyDat.Dat; }
00789   void GetKeyDat(const int& KeyId, TStr& Key, TDat& Dat) const { const THKeyDat& KeyDat = GetHashKeyDat(KeyId); Key = KeyFromOfs(KeyDat.Key); Dat = KeyDat.Dat;}
00790   void GetKeyDat(const int& KeyId, TChA& Key, TDat& Dat) const { const THKeyDat& KeyDat = GetHashKeyDat(KeyId); Key = KeyFromOfs(KeyDat.Key); Dat = KeyDat.Dat;}
00791 
00792   int GetKeyId(const char *Key) const;
00793   int GetKeyId(const TStr& Key) const { return GetKeyId(Key.CStr()); }
00794   const char *GetKey(const int& KeyId) const { return Pool->GetCStr(GetHashKeyDat(KeyId).Key); }
00795   int GetKeyOfs(const int& KeyId) const { return GetHashKeyDat(KeyId).Key; } // pool string id
00796   const char *KeyFromOfs(const int& KeyO) const { return Pool->GetCStr(KeyO); }
00797 
00798   bool IsKey(const char *Key) const { return GetKeyId(Key) != -1; }
00799   bool IsKey(const TStr& Key) const { return GetKeyId(Key.CStr()) != -1; }
00800   bool IsKey(const TChA& Key) const { return GetKeyId(Key.CStr()) != -1; }
00801   bool IsKey(const char *Key, int& KeyId) const { KeyId = GetKeyId(Key); return KeyId != -1; }
00802   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; }
00803   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; }
00804   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; }
00805   bool IsKeyId(const int& KeyId) const { return 0 <= KeyId && KeyId < KeyDatV.Len() && KeyDatV[KeyId].HashCd != -1; }
00806 
00807   int FFirstKeyId() const {return 0-1;}
00808   bool FNextKeyId(int& KeyId) const;
00809 
00810   void GetKeyV(TVec<TStr>& KeyV) const;
00811   void GetStrIdV(TIntV& StrIdV) const;
00812   void GetDatV(TVec<TDat>& DatV) const;
00813   void GetKeyDatPrV(TVec<TPair<TStr, TDat> >& KeyDatPrV) const;
00814   void GetDatKeyPrV(TVec<TPair<TDat, TStr> >& DatKeyPrV) const;
00815 
00816   void Pack(){KeyDatV.Pack();}
00817 };
00818 
00819 template <class TDat, class TStringPool, class THashFunc>
00820 uint TStrHash<TDat, TStringPool, THashFunc>::GetNextPrime(const uint& Val) const {
00821   uint *f = (uint *) TIntH::HashPrimeT, *m, *l = (uint *) TIntH::HashPrimeT + (int) TIntH::HashPrimes;
00822   int h, len = (int)TIntH::HashPrimes;
00823   while (len > 0) {
00824     h = len >> 1;  m = f + h;
00825     if (*m < Val) { f = m;  f++;  len = len - h - 1; }
00826     else len = h;
00827   }
00828   return f == l ? *(l - 1) : *f;
00829 }
00830 
00831 template <class TDat, class TStringPool, class THashFunc>
00832 void TStrHash<TDat, TStringPool, THashFunc>::Resize() {
00833   // resize & initialize port vector
00834   if (PortV.Empty()) { PortV.Gen(17);  PortV.PutAll(-1); }
00835   else
00836   if (AutoSizeP && KeyDatV.Len() > 3 * PortV.Len()) {
00837     const int NxPrime = GetNextPrime(KeyDatV.Len());
00838     //printf("%s resize PortV: %d -> %d, Len: %d\n", GetTypeNm(*this).CStr(), PortV.Len(), NxPrime, Len());
00839     PortV.Gen(NxPrime);  PortV.PutAll(-1); }
00840   else
00841     return;
00842   // rehash keys
00843   const int NPorts = PortV.Len();
00844   for (int i = 0; i < KeyDatV.Len(); i++) {
00845     THKeyDat& KeyDat = KeyDatV[i];
00846     if (KeyDat.HashCd != -1) {
00847       const int Port = abs(THashFunc::GetPrimHashCd(Pool->GetCStr(KeyDat.Key)) % NPorts);
00848       KeyDat.Next = PortV[Port];
00849       PortV[Port] = i;
00850     }
00851   }
00852 }
00853 
00854 template <class TDat, class TStringPool, class THashFunc>
00855 TStrHash<TDat, TStringPool, THashFunc>& TStrHash<TDat, TStringPool, THashFunc>:: operator = (const TStrHash& Hash) {
00856   if (this != &Hash) {
00857     PortV = Hash.PortV;
00858     KeyDatV = Hash.KeyDatV;
00859     AutoSizeP = Hash.AutoSizeP;
00860     FFreeKeyId = Hash.FFreeKeyId;
00861     FreeKeys = Hash.FreeKeys;
00862     if (! Hash.Pool.Empty()) Pool = PStringPool(new TStringPool(*Hash.Pool));
00863     else Pool = NULL;
00864   }
00865   return *this;
00866 }
00867 
00868 template <class TDat, class TStringPool, class THashFunc>
00869 int TStrHash<TDat, TStringPool, THashFunc>::AddKey(const char *Key) {
00870   if (Pool.Empty()) Pool = TStringPool::New();
00871   if ((AutoSizeP && KeyDatV.Len() > PortV.Len()) || PortV.Empty()) Resize();
00872   const int PortN = abs(THashFunc::GetPrimHashCd(Key) % PortV.Len());
00873   const int HashCd = abs(THashFunc::GetSecHashCd(Key));
00874   int PrevKeyId = -1;
00875   int KeyId = PortV[PortN];
00876   while (KeyId != -1 && ! (KeyDatV[KeyId].HashCd == HashCd && Pool->Cmp(KeyDatV[KeyId].Key, Key) == 0)) {
00877     PrevKeyId = KeyId;  KeyId = KeyDatV[KeyId].Next; }
00878   if (KeyId == -1) {
00879     const int StrId = Pool->AddStr(Key);
00880     if (FFreeKeyId == -1) {
00881       KeyId = KeyDatV.Add(THKeyDat(-1, HashCd, StrId));
00882     } else {
00883       KeyId = FFreeKeyId;
00884       FFreeKeyId = KeyDatV[FFreeKeyId].Next;
00885       FreeKeys--;
00886       KeyDatV[KeyId] = THKeyDat(-1, HashCd, StrId);
00887     }
00888     if (PrevKeyId == -1) PortV[PortN] = KeyId;
00889     else KeyDatV[PrevKeyId].Next = KeyId;
00890   }
00891   return KeyId;
00892 }
00893 
00894 template <class TDat, class TStringPool, class THashFunc>
00895 int TStrHash<TDat, TStringPool, THashFunc>::GetKeyId(const char *Key) const {
00896   if (PortV.Empty()) return -1;
00897   const int PortN = abs(THashFunc::GetPrimHashCd(Key) % PortV.Len());
00898   const int Hc = abs(THashFunc::GetSecHashCd(Key));
00899   int KeyId = PortV[PortN];
00900   while (KeyId != -1 && ! (KeyDatV[KeyId].HashCd == Hc && Pool->Cmp(KeyDatV[KeyId].Key, Key) == 0))
00901     KeyId = KeyDatV[KeyId].Next;
00902   return KeyId;
00903 }
00904 
00905 template <class TDat, class TStringPool, class THashFunc>
00906 bool TStrHash<TDat, TStringPool, THashFunc>::FNextKeyId(int& KeyId) const {
00907   do KeyId++; while (KeyId < KeyDatV.Len() && KeyDatV[KeyId].HashCd == -1);
00908   return KeyId < KeyDatV.Len();
00909 }
00910 
00911 template <class TDat, class TStringPool, class THashFunc>
00912 void TStrHash<TDat, TStringPool, THashFunc>::GetKeyV(TVec<TStr>& KeyV) const {
00913   KeyV.Gen(Len(), 0);
00914   int KeyId = FFirstKeyId();
00915   while (FNextKeyId(KeyId))
00916     KeyV.Add(GetKey(KeyId));
00917 }
00918 
00919 template <class TDat, class TStringPool, class THashFunc>
00920 void TStrHash<TDat, TStringPool, THashFunc>::GetStrIdV(TIntV& StrIdV) const {
00921   StrIdV.Gen(Len(), 0);
00922   int KeyId = FFirstKeyId();
00923   while (FNextKeyId(KeyId))
00924     StrIdV.Add(GetKeyOfs(KeyId));
00925 }
00926 
00927 template <class TDat, class TStringPool, class THashFunc>
00928 void TStrHash<TDat, TStringPool, THashFunc>::GetDatV(TVec<TDat>& DatV) const {
00929   DatV.Gen(Len(), 0);
00930   int KeyId = FFirstKeyId();
00931   while (FNextKeyId(KeyId))
00932     DatV.Add(GetHashKeyDat(KeyId).Dat);
00933 }
00934 
00935 template <class TDat, class TStringPool, class THashFunc>
00936 void TStrHash<TDat, TStringPool, THashFunc>::GetKeyDatPrV(TVec<TPair<TStr, TDat> >& KeyDatPrV) const {
00937   KeyDatPrV.Gen(Len(), 0);
00938   TStr Str; TDat Dat;
00939   int KeyId = FFirstKeyId();
00940   while (FNextKeyId(KeyId)){
00941     GetKeyDat(KeyId, Str, Dat);
00942     KeyDatPrV.Add(TPair<TStr, TDat>(Str, Dat));
00943   }
00944 }
00945 
00946 template <class TDat, class TStringPool, class THashFunc>
00947 void TStrHash<TDat, TStringPool, THashFunc>::GetDatKeyPrV(TVec<TPair<TDat, TStr> >& DatKeyPrV) const {
00948   DatKeyPrV.Gen(Len(), 0);
00949   TStr Str; TDat Dat;
00950   int KeyId = FFirstKeyId();
00951   while (FNextKeyId(KeyId)){
00952     GetKeyDat(KeyId, Str, Dat);
00953     DatKeyPrV.Add(TPair<TDat, TStr>(Dat, Str));
00954   }
00955 }
00956 
00958 // Common-String-Hash-Types
00959 typedef TStrHash<TInt> TStrSH;
00960 typedef TStrHash<TInt> TStrIntSH;
00961 typedef TStrHash<TIntV> TStrToIntVSH;
00962 
00964 // Cache
00965 template <class TKey, class TDat, class THashFunc = TDefaultHashFunc<TKey> >
00966 class TCache{
00967 private:
00968   typedef TLst<TKey> TKeyL; typedef TLstNd<TKey>* TKeyLN;
00969   typedef TPair<TKeyLN, TDat> TKeyLNDatPr;
00970   int64 MxMemUsed;
00971   int64 CurMemUsed;
00972   THash<TKey, TKeyLNDatPr, THashFunc> KeyDatH;
00973   TKeyL TimeKeyL;
00974   void* RefToBs;
00975   void Purge(const int64& MemToPurge);
00976 public:
00977   TCache(){}
00978   TCache(const TCache&);
00979   TCache(const int64& _MxMemUsed, const int& Ports, void* _RefToBs):
00980     MxMemUsed(_MxMemUsed), CurMemUsed(0),
00981     KeyDatH(Ports), TimeKeyL(), RefToBs(_RefToBs){}
00982 
00983   TCache& operator=(const TCache&);
00984   int64 GetMemUsed() const;
00985   int64 GetMxMemUsed() const { return MxMemUsed; }
00986   bool RefreshMemUsed();
00987 
00988   void Put(const TKey& Key, const TDat& Dat);
00989   bool Get(const TKey& Key, TDat& Dat);
00990   void Del(const TKey& Key, const bool& DoEventCall=true);
00991   void Flush();
00992   void FlushAndClr();
00993   void* FFirstKeyDat();
00994   bool FNextKeyDat(void*& KeyDatP, TKey& Key, TDat& Dat);
00995 
00996   void PutRefToBs(void* _RefToBs){RefToBs=_RefToBs;}
00997   void* GetRefToBs(){return RefToBs;}
00998 };
00999 
01000 template <class TKey, class TDat, class THashFunc>
01001 void TCache<TKey, TDat, THashFunc>::Purge(const int64& MemToPurge){
01002   const int64 StartMemUsed = CurMemUsed;
01003   while (!TimeKeyL.Empty()&&(StartMemUsed-CurMemUsed<MemToPurge)){
01004     TKey Key=TimeKeyL.Last()->GetVal();
01005     Del(Key);
01006   }
01007 }
01008 
01009 template <class TKey, class TDat, class THashFunc>
01010 int64 TCache<TKey, TDat, THashFunc>::GetMemUsed() const {
01011   int64 MemUsed=0;
01012   int KeyId=KeyDatH.FFirstKeyId();
01013   while (KeyDatH.FNextKeyId(KeyId)){
01014     const TKey& Key=KeyDatH.GetKey(KeyId);
01015     const TKeyLNDatPr& KeyLNDatPr=KeyDatH[KeyId];
01016     TDat Dat=KeyLNDatPr.Val2;
01017     MemUsed+=int64(Key.GetMemUsed()+Dat->GetMemUsed());
01018   }
01019   return MemUsed;
01020 }
01021 
01022 template <class TKey, class TDat, class THashFunc>
01023 bool TCache<TKey, TDat, THashFunc>::RefreshMemUsed(){
01024   CurMemUsed=GetMemUsed();
01025   if (CurMemUsed>MxMemUsed){
01026     Purge(CurMemUsed-MxMemUsed);
01027     return true;
01028   }
01029   return false;
01030 }
01031 
01032 template <class TKey, class TDat, class THashFunc>
01033 void TCache<TKey, TDat, THashFunc>::Put(const TKey& Key, const TDat& Dat){
01034   int KeyId=KeyDatH.GetKeyId(Key);
01035   if (KeyId==-1){
01036     int64 KeyDatMem=int64(Key.GetMemUsed()+Dat->GetMemUsed());
01037     if (CurMemUsed+KeyDatMem>MxMemUsed){Purge(KeyDatMem);}
01038     CurMemUsed+=KeyDatMem;
01039     TKeyLN KeyLN=TimeKeyL.AddFront(Key);
01040     TKeyLNDatPr KeyLNDatPr(KeyLN, Dat);
01041     KeyDatH.AddDat(Key, KeyLNDatPr);
01042   } else {
01043     TKeyLNDatPr& KeyLNDatPr=KeyDatH[KeyId];
01044     TKeyLN KeyLN=KeyLNDatPr.Val1;
01045     KeyLNDatPr.Val2=Dat;
01046     TimeKeyL.PutFront(KeyLN);
01047   }
01048 }
01049 
01050 template <class TKey, class TDat, class THashFunc>
01051 bool TCache<TKey, TDat, THashFunc>::Get(const TKey& Key, TDat& Dat){
01052   int KeyId=KeyDatH.GetKeyId(Key);
01053   if (KeyId==-1){
01054     return false;
01055   } else {
01056     Dat=KeyDatH[KeyId].Val2;
01057     return true;
01058   }
01059 }
01060 
01061 template <class TKey, class TDat, class THashFunc>
01062 void TCache<TKey, TDat, THashFunc>::Del(const TKey& Key, const bool& DoEventCall){
01063   int KeyId=KeyDatH.GetKeyId(Key);
01064   if (KeyId!=-1){
01065     TKeyLNDatPr& KeyLNDatPr=KeyDatH[KeyId];
01066     TKeyLN KeyLN=KeyLNDatPr.Val1;
01067     TDat& Dat=KeyLNDatPr.Val2;
01068     if (DoEventCall){
01069       Dat->OnDelFromCache(Key, RefToBs);}
01070     CurMemUsed-=int64(Key.GetMemUsed()+Dat->GetMemUsed());
01071     Dat=NULL;
01072     TimeKeyL.Del(KeyLN);
01073     KeyDatH.DelKeyId(KeyId);
01074   }
01075 }
01076 
01077 template <class TKey, class TDat, class THashFunc>
01078 void TCache<TKey, TDat, THashFunc>::Flush(){
01079   printf("To flush: %d\n", KeyDatH.Len());
01080   int KeyId=KeyDatH.FFirstKeyId(); int Done = 0;
01081   while (KeyDatH.FNextKeyId(KeyId)){
01082     if (Done%10000==0){printf("%d\r", Done);}
01083     const TKey& Key=KeyDatH.GetKey(KeyId);
01084     TKeyLNDatPr& KeyLNDatPr=KeyDatH[KeyId];
01085     TDat Dat=KeyLNDatPr.Val2;
01086     Dat->OnDelFromCache(Key, RefToBs);
01087     Done++;
01088   }
01089   printf("Done %d\n", KeyDatH.Len());
01090 }
01091 
01092 template <class TKey, class TDat, class THashFunc>
01093 void TCache<TKey, TDat, THashFunc>::FlushAndClr(){
01094   Flush();
01095   CurMemUsed=0;
01096   KeyDatH.Clr();
01097   TimeKeyL.Clr();
01098 }
01099 
01100 template <class TKey, class TDat, class THashFunc>
01101 void* TCache<TKey, TDat, THashFunc>::FFirstKeyDat(){
01102   return TimeKeyL.First();
01103 }
01104 
01105 template <class TKey, class TDat, class THashFunc>
01106 bool TCache<TKey, TDat, THashFunc>::FNextKeyDat(void*& KeyDatP, TKey& Key, TDat& Dat){
01107   if (KeyDatP==NULL){
01108     return false;
01109   } else {
01110     Key=TKeyLN(KeyDatP)->GetVal(); Dat=KeyDatH.GetDat(Key).Val2;
01111     KeyDatP=TKeyLN(KeyDatP)->Next(); return true;
01112   }
01113 }
01114 
01116 // Old-Hash-Functions
01117 
01118 // Old-String-Hash-Function
01119 class TStrHashF_OldGLib {
01120 public:
01121   inline static int GetPrimHashCd(const char *p) {
01122     const int MulBy = 16;  // even older version used MulBy=2
01123     int HashCd = 0;
01124     while (*p) { HashCd = (MulBy * HashCd) + *p++; HashCd &= 0x0FFFFFFF; }
01125     return HashCd; }
01126   inline static int GetSecHashCd(const char *p) {
01127     const int MulBy = 16;  // even older version used MulBy=2
01128     int HashCd = 0;
01129     while (*p) { HashCd = (MulBy * HashCd) ^ *p++; HashCd &= 0x0FFFFFFF; }
01130     return HashCd; }
01131   inline static int GetPrimHashCd(const TStr& s) { return GetPrimHashCd(s.CStr()); }
01132   inline static int GetSecHashCd(const TStr& s) { return GetSecHashCd(s.CStr()); }
01133 };
01134 
01135 // Md5-Hash-Function
01136 class TStrHashF_Md5 {
01137 public:
01138   static int GetPrimHashCd(const char *p);
01139   static int GetSecHashCd(const char *p);
01140   static int GetPrimHashCd(const TStr& s);
01141   static int GetSecHashCd(const TStr& s);
01142 };
01143 
01144 // DJB-Hash-Function
01145 class TStrHashF_DJB {
01146 private:
01147   inline static unsigned int DJBHash(const char* Str, const ::TSize& Len) {
01148     unsigned int hash = 5381;
01149     for(unsigned int i = 0; i < Len; Str++, i++) {
01150        hash = ((hash << 5) + hash) + (*Str); }
01151     return hash;
01152   }
01153 public:
01154   inline static int GetPrimHashCd(const char *p) {
01155     const char *r = p;  while (*r) { r++; }
01156     return (int) DJBHash((const char *) p, r - p) & 0x7fffffff; }
01157   inline static int GetSecHashCd(const char *p) {
01158     const char *r = p;  while (*r) { r++; }
01159     return (int) DJBHash((const char *) p, r - p) & 0x7fffffff; }
01160   inline static int GetPrimHashCd(const TStr& s) { return GetPrimHashCd(s.CStr()); }
01161   inline static int GetSecHashCd(const TStr& s) { return GetSecHashCd(s.CStr()); }
01162 };
01163 
01164 // Old-Vector-Hash-Function
01165 template <class TVec>
01166 class TVecHashF_OldGLib {
01167 public:
01168   static inline int GetPrimHashCd(const TVec& Vec) {
01169     int HashCd=0;
01170     for (int ValN=0; ValN<Vec.Len(); ValN++){
01171       HashCd+=Vec[ValN].GetPrimHashCd();}
01172     return abs(HashCd);
01173   }
01174   inline static int GetSecHashCd(const TVec& Vec) {
01175     int HashCd=0;
01176     for (int ValN=0; ValN<Vec.Len(); ValN++){
01177       HashCd+=Vec[ValN].GetSecHashCd();}
01178     return abs(HashCd);
01179   }
01180 };