SNAP Library , Developer Reference  2013-01-07 14:03:36
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
fds.h
Go to the documentation of this file.
00001 
00002 // Forward
00003 template <class TKey, class TFDat, class TVDat>
00004 class TFHash;
00005 
00006 typedef enum {fhbtUndef, fhbtKey, fhbtVDat} TFHashBlobType;
00007 
00009 // File-Hash-Table-Key-Data
00010 template <class TKey, class TFDat, class TVDat>
00011 class TFHashKey{
00012 private:
00013   TCRef CRef;
00014   bool Modified;
00015 public:
00016   typedef TPt<TFHashKey<TKey, TFDat, TVDat> > PFHashKey;
00017   typedef TFHash<TKey, TFDat, TVDat> THash;
00018   TBlobPt Next;
00019   TKey Key;
00020   TFDat FDat;
00021   TBlobPt VDatBPt;
00022 public:
00023   TFHashKey():
00024     Modified(false), Next(), Key(), FDat(), VDatBPt(){}
00025   TFHashKey(const TBlobPt& _Next,
00026    const TKey& _Key, const TFDat& _FDat, const TBlobPt& _VDatBPt=TBlobPt()):
00027     Modified(false), Next(_Next), Key(_Key), FDat(_FDat), VDatBPt(_VDatBPt){}
00028   ~TFHashKey(){}
00029   TFHashKey(TSIn& SIn):
00030     Modified(false), Next(SIn), Key(SIn), FDat(SIn), VDatBPt(SIn){}
00031   static PFHashKey Load(TSIn& SIn){return new TFHashKey(SIn);}
00032   void Save(TSOut& SOut){
00033     Next.Save(SOut); Key.Save(SOut); FDat.Save(SOut); VDatBPt.Save(SOut);}
00034 
00035   TFHashKey& operator=(const TFHashKey& FHashKey){
00036     if (this!=&FHashKey){
00037       Modified=true; Next=FHashKey.Next;
00038       Key=FHashKey.Key; FDat=FHashKey.FDat; VDatBPt=FHashKey.VDatBPt;}
00039     return *this;}
00040   int GetMemUsed() const {
00041     return sizeof(THash*)+Next.GetMemUsed()+
00042      Key.GetMemUsed()+FDat.GetMemUsed()+VDatBPt.GetMemUsed();}
00043 
00044   void PutModified(const bool& _Modified){Modified=_Modified;}
00045 
00046   void OnDelFromCache(const TBlobPt& BlobPt, void* RefToBs);
00047 
00048   friend class TPt<TFHashKey<TKey, TFDat, TVDat> >;
00049 };
00050 
00051 template <class TKey, class TFDat, class TVDat>
00052 void TFHashKey<TKey, TFDat, TVDat>::OnDelFromCache(
00053  const TBlobPt& BlobPt, void* RefToBs){
00054   if (Modified){
00055     // prepare hash table object
00056     THash* FHash=(THash*)RefToBs;
00057     // save the key
00058     TMOut MOut; TInt(int(fhbtKey)).Save(MOut); Save(MOut);
00059     TBlobPt NewBlobPt=FHash->GetHashBBs()->PutBlob(BlobPt, MOut.GetSIn());
00060     // blob-pointer for key should not change
00061     IAssert(NewBlobPt==BlobPt);
00062   }
00063 }
00064 
00066 // File-Hash-Table
00067 
00068 template <class TKey, class TFDat, class TVDat>
00069 class TFHash{
00070 private:
00071   TCRef CRef;
00072 private:
00073   typedef TPt<TFHash<TKey, TFDat, TVDat> > PFHash;
00074   typedef TFHashKey<TKey, TFDat, TVDat> THashKey;
00075   typedef TPt<THashKey> PHashKey;
00076   TFAccess Access;
00077   PBlobBs HashBBs;
00078   TBlobPtV PortV;
00079   TInt Keys;
00080   TCache<TBlobPt, PHashKey> FHashKeyCache;
00081 private:
00082   void* GetVoidThis() const {return (void*)this;}
00083   PBlobBs GetHashBBs(){return HashBBs;}
00084   PHashKey GetFHashKey(const TBlobPt& KeyId){
00085     PHashKey FHashKey;
00086     if (!FHashKeyCache.Get(KeyId, FHashKey)){ // if the key is in cache
00087       // read the key from blob-base
00088       PSIn SIn=HashBBs->GetBlob(KeyId);
00089       TFHashBlobType Type=TFHashBlobType(int(TInt(*SIn))); IAssert(Type==fhbtKey);
00090       FHashKey=PHashKey(new THashKey(*SIn));
00091     }
00092     FHashKeyCache.Put(KeyId, FHashKey); // refresh/put key in cache
00093     return FHashKey;
00094   }
00095   void GetKeyInfo(const TKey& Key,
00096    int& PortN, TBlobPt& PrevKeyId, TBlobPt& KeyId, PHashKey& FHashKey);
00097   void GetKeyInfo(const TKey& Key, TBlobPt& KeyId, PHashKey& FHashKey){
00098     int PortN=-1; TBlobPt PrevKeyId;
00099     GetKeyInfo(Key, PortN, PrevKeyId, KeyId, FHashKey);}
00100 private:
00101   TBlobPt AddKey(const TKey& Key,
00102    const bool& ChangeFDat, const TFDat& FDat,
00103    const bool& ChangeVDatBPt, const TBlobPt& VDatBPt);
00104   TBlobPt AddDat(
00105    const TKey& Key,
00106    const bool& ChangeFDat, const TFDat& FDat,
00107    const bool& ChangeVDat, const TVDat& VDat);
00108 public:
00109   TFHash(const TStr& HashFNm, const TFAccess& _Access,
00110    const int& Ports, const int& MxMemUsed);
00111   ~TFHash();
00112   TFHash(TSIn&){Fail;}
00113   static PFHash Load(TSIn&){Fail; return NULL;}
00114   void Save(TSOut&){Fail;}
00115 
00116   TFHash& operator=(const TFHash&){Fail; return *this;}
00117   int GetMemUsed(){
00118     return PortV.GetMemUsed()+(int)FHashKeyCache.GetMemUsed();} //TODO:64bit
00119   void CacheFlushAndClr(){FHashKeyCache.FlushAndClr();}
00120 
00121   bool Empty() const {return Keys==0;}
00122   int Len() const {return Keys;}
00123 
00124   TBlobPt AddFDat(const TKey& Key, const TFDat& FDat){
00125     return AddKey(Key, true, FDat, false, TBlobPt());}
00126   TBlobPt AddVDat(const TKey& Key, const TVDat& VDat){
00127     return AddDat(Key, false, TFDat(), true, VDat);}
00128   TBlobPt AddFVDat(const TKey& Key, const TFDat& FDat, const TVDat& VDat){
00129     return AddDat(Key, true, FDat, true, VDat);}
00130 
00131   void DelKey(const TKey& Key);
00132   void DelKeyId(const TBlobPt& KeyId){
00133     TKey Key; GetKey(KeyId, Key); DelKey(Key);}
00134 
00135   void GetKey(const TBlobPt& KeyId, TKey& Key){
00136     PHashKey FHashKey=GetFHashKey(KeyId); Key=FHashKey->Key;}
00137   TBlobPt GetKeyId(const TKey& Key){
00138     TBlobPt KeyId; PHashKey FHashKey; GetKeyInfo(Key, KeyId, FHashKey);
00139     return KeyId;}
00140   bool IsKey(const TKey& Key){
00141     return !GetKeyId(Key).Empty();}
00142   bool IsKey(const TKey& Key, TBlobPt& KeyId){
00143     KeyId=GetKeyId(Key); return !KeyId.Empty();}
00144 
00145   TBlobPt GetFDat(const TKey& Key, TFDat& FDat);
00146   TBlobPt GetVDat(const TKey& Key, TVDat& VDat);
00147   TBlobPt GetFVDat(const TKey& Key, TFDat& FDat, TVDat& VDat);
00148   void GetKeyFDat(const TBlobPt& KeyId, TKey& Key, TFDat& FDat);
00149   void GetKeyFVDat(const TBlobPt& KeyId, TKey& Key, TFDat& FDat, TVDat& VDat);
00150 
00151   TBlobPt FFirstKeyId();
00152   bool FNextKeyId(TBlobPt& TrvBlobPt, TBlobPt& KeyId);
00153 
00154   friend class TFHashKey<TKey, TFDat, TVDat>;
00155   friend class TPt<TFHash<TKey, TFDat, TVDat> >;
00156 };
00157 
00158 
00159 template <class TKey, class TFDat, class TVDat>
00160 void TFHash<TKey, TFDat, TVDat>::GetKeyInfo(
00161  const TKey& Key,
00162  int& PortN, TBlobPt& PrevKeyId, TBlobPt& KeyId, PHashKey& FHashKey){
00163   // prepare key data
00164   PortN=abs(Key.GetPrimHashCd())%PortV.Len();
00165   PrevKeyId.Clr();
00166   KeyId=PortV[PortN];
00167 
00168   // test if the key exists
00169   if (!KeyId.Empty()){
00170     FHashKey=GetFHashKey(KeyId);
00171     while ((!KeyId.Empty())&&(FHashKey->Key!=Key)){
00172       PrevKeyId=KeyId;
00173       KeyId=FHashKey->Next;
00174       if (!KeyId.Empty()){FHashKey=GetFHashKey(KeyId);}
00175     }
00176   }
00177 }
00178 
00179 template <class TKey, class TFDat, class TVDat>
00180 TFHash<TKey, TFDat, TVDat>::TFHash(
00181  const TStr& HashFNm, const TFAccess& _Access,
00182  const int& Ports, const int& MxMemUsed):
00183   Access(_Access), HashBBs(), PortV(), Keys(0),
00184   FHashKeyCache(MxMemUsed, 100003, GetVoidThis()){
00185   if (Access==faCreate){
00186     IAssert(Ports>0);
00187     // create blob-base
00188     HashBBs=PBlobBs(new TGBlobBs(HashFNm, faCreate));
00189     // save initial no. of keys and port-vector
00190     PortV.Gen(Ports);
00191     TMOut HdSOut; Keys.Save(HdSOut); PortV.Save(HdSOut);
00192     HashBBs->PutBlob(HdSOut.GetSIn());
00193   } else {
00194     IAssert((Access==faUpdate)||(Access==faRdOnly));
00195     IAssert(Ports==-1);
00196     // open blob-base
00197     HashBBs=PBlobBs(new TGBlobBs(HashFNm, Access));
00198     // load initial no. of keys and port-vector
00199     TBlobPt HdBPt=HashBBs->GetFirstBlobPt();
00200     PSIn HdSIn=HashBBs->GetBlob(HdBPt);
00201     Keys=TInt(*HdSIn);
00202     PortV=TBlobPtV(*HdSIn);
00203   }
00204 }
00205 
00206 template <class TKey, class TFDat, class TVDat>
00207 TFHash<TKey, TFDat, TVDat>::~TFHash(){
00208   if ((Access==faCreate)||(Access==faUpdate)){
00209     // flush hash-key cache
00210     FHashKeyCache.Flush();
00211     // save port-vector
00212     TBlobPt HdBPt=HashBBs->GetFirstBlobPt();
00213     TMOut HdSOut; Keys.Save(HdSOut); PortV.Save(HdSOut);
00214     HashBBs->PutBlob(HdBPt, HdSOut.GetSIn());
00215   }
00216 }
00217 
00218 template <class TKey, class TFDat, class TVDat>
00219 TBlobPt TFHash<TKey, TFDat, TVDat>::AddKey(
00220  const TKey& Key,
00221  const bool& ChangeFDat, const TFDat& FDat,
00222  const bool& ChangeVDatBPt, const TBlobPt& VDatBPt){
00223   // prepare key info
00224   int PortN=-1; TBlobPt PrevKeyId; TBlobPt KeyId; PHashKey FHashKey;
00225   GetKeyInfo(Key, PortN, PrevKeyId, KeyId, FHashKey);
00226 
00227   if (KeyId.Empty()){
00228     // generate key
00229     FHashKey=PHashKey(new THashKey(TBlobPt(), Key, FDat, VDatBPt));
00230     // save key to blob-base
00231     TMOut FHashKeyMOut;
00232     TInt(int(fhbtKey)).Save(FHashKeyMOut); FHashKey->Save(FHashKeyMOut);
00233     TBlobPt FHashKeyBPt=HashBBs->PutBlob(FHashKeyMOut.GetSIn());
00234     // save key to key-cache
00235     FHashKeyCache.Put(FHashKeyBPt, FHashKey);
00236     FHashKey->PutModified(false);
00237     // connect key to the structure
00238     KeyId=FHashKeyBPt;
00239     Keys++;
00240     if (PrevKeyId.Empty()){
00241       PortV[PortN]=KeyId;
00242     } else {
00243       PHashKey PrevFHashKey=GetFHashKey(PrevKeyId);
00244       PrevFHashKey->Next=KeyId;
00245       PrevFHashKey->PutModified(true);
00246     }
00247   } else {
00248     // update the data
00249     if (ChangeFDat){FHashKey->FDat=FDat;}
00250     if (ChangeVDatBPt){FHashKey->VDatBPt=VDatBPt;}
00251     if (ChangeFDat||ChangeVDatBPt){
00252       FHashKey->PutModified(true);}
00253   }
00254   return KeyId;
00255 }
00256 
00257 template <class TKey, class TFDat, class TVDat>
00258 TBlobPt TFHash<TKey, TFDat, TVDat>::AddDat(
00259  const TKey& Key,
00260  const bool& ChangeFDat, const TFDat& FDat,
00261  const bool& ChangeVDat, const TVDat& VDat){
00262   // prepare key info
00263   TBlobPt KeyId; PHashKey FHashKey;
00264   GetKeyInfo(Key, KeyId, FHashKey);
00265 
00266   // prepare new variable-data blob-pointer
00267   TBlobPt VDatBPt;
00268   if (ChangeVDat){
00269     // save variable-data
00270     TMOut VDatMOut;
00271     TInt(int(fhbtVDat)).Save(VDatMOut); VDat.Save(VDatMOut);
00272     if (KeyId.Empty()){
00273       VDatBPt=HashBBs->PutBlob(VDatMOut.GetSIn());
00274     } else {
00275       VDatBPt=HashBBs->PutBlob(FHashKey->VDatBPt, VDatMOut.GetSIn());
00276     }
00277   }
00278 
00279   // save the data
00280   KeyId=AddKey(Key, ChangeFDat, FDat, ChangeVDat, VDatBPt);
00281   return KeyId;
00282 }
00283 
00284 template <class TKey, class TFDat, class TVDat>
00285 void TFHash<TKey, TFDat, TVDat>::DelKey(const TKey& Key){
00286   // prepare key info
00287   int PortN=-1; TBlobPt PrevKeyId; TBlobPt KeyId; PHashKey FHashKey;
00288   GetKeyInfo(Key, PortN, PrevKeyId, KeyId, FHashKey);
00289 
00290   // disconnect key
00291   IAssert(!KeyId.Empty());
00292   if (PrevKeyId.Empty()){
00293     PortV[PortN]=FHashKey->Next;
00294   } else {
00295     PHashKey PrevFHashKey=GetFHashKey(PrevKeyId);
00296     PrevFHashKey->Next=FHashKey->Next;
00297     PrevFHashKey->PutModified(true);
00298   }
00299   // delete variable data
00300   if (!FHashKey->VDatBPt.Empty()){
00301     HashBBs->DelBlob(FHashKey->VDatBPt);}
00302   // delete key/fixed data
00303   HashBBs->DelBlob(KeyId);
00304   FHashKeyCache.Del(KeyId, false);
00305 }
00306 
00307 template <class TKey, class TFDat, class TVDat>
00308 TBlobPt TFHash<TKey, TFDat, TVDat>::GetFDat(
00309  const TKey& Key, TFDat& FDat){
00310   // prepare key info
00311   TBlobPt KeyId; PHashKey FHashKey;
00312   GetKeyInfo(Key, KeyId, FHashKey);
00313   // get fixed data
00314   FDat=FHashKey->FDat;
00315   return KeyId;
00316 }
00317 
00318 template <class TKey, class TFDat, class TVDat>
00319 TBlobPt TFHash<TKey, TFDat, TVDat>::GetVDat(const TKey& Key, TVDat& VDat){
00320   // prepare key info
00321   TBlobPt KeyId; PHashKey FHashKey;
00322   GetKeyInfo(Key, KeyId, FHashKey);
00323   // get variable data
00324   PSIn SIn=HashBBs->GetBlob(FHashKey->VDatBPt);
00325   TFHashBlobType Type=TFHashBlobType(int(TInt(*SIn))); IAssert(Type==fhbtVDat);
00326   VDat=TVDat(*SIn);
00327   return KeyId;
00328 }
00329 
00330 template <class TKey, class TFDat, class TVDat>
00331 TBlobPt TFHash<TKey, TFDat, TVDat>::GetFVDat(
00332  const TKey& Key, TFDat& FDat, TVDat& VDat){
00333   // prepare key info
00334   TBlobPt KeyId; PHashKey FHashKey;
00335   GetKeyInfo(Key, KeyId, FHashKey);
00336   // get fixed data
00337   FDat=FHashKey->FDat;
00338   // get variable data
00339   PSIn SIn=HashBBs->GetBlob(FHashKey->VDatBPt);
00340   TFHashBlobType Type=TFHashBlobType(int(TInt(*SIn))); IAssert(Type==fhbtVDat);
00341   VDat=TVDat(*SIn);
00342   return KeyId;
00343 }
00344 
00345 template <class TKey, class TFDat, class TVDat>
00346 void TFHash<TKey, TFDat, TVDat>::GetKeyFDat(
00347  const TBlobPt& KeyId, TKey& Key, TFDat& FDat){
00348   // prepare key info
00349   PHashKey FHashKey=GetFHashKey(KeyId);
00350   // get key
00351   Key=FHashKey->Key;
00352   // get fixed data
00353   FDat=FHashKey->FDat;
00354 }
00355 
00356 template <class TKey, class TFDat, class TVDat>
00357 void TFHash<TKey, TFDat, TVDat>::GetKeyFVDat(
00358  const TBlobPt& KeyId, TKey& Key, TFDat& FDat, TVDat& VDat){
00359   // prepare key info
00360   PHashKey FHashKey=GetFHashKey(KeyId);
00361   // get key
00362   Key=FHashKey->Key;
00363   // get fixed data
00364   FDat=FHashKey->FDat;
00365   // get variable data
00366   PSIn SIn=HashBBs->GetBlob(FHashKey->VDatBPt);
00367   TFHashBlobType Type=TFHashBlobType(int(TInt(*SIn))); IAssert(Type==fhbtVDat);
00368   VDat=TVDat(*SIn);
00369 }
00370 
00371 template <class TKey, class TFDat, class TVDat>
00372 TBlobPt TFHash<TKey, TFDat, TVDat>::FFirstKeyId(){
00373   return HashBBs->FFirstBlobPt();
00374 }
00375 
00376 template <class TKey, class TFDat, class TVDat>
00377 bool TFHash<TKey, TFDat, TVDat>::FNextKeyId(
00378  TBlobPt& TrvBlobPt, TBlobPt& KeyId){
00379   PSIn SIn;
00380   while (HashBBs->FNextBlobPt(TrvBlobPt, KeyId, SIn)){
00381     TFHashBlobType Type=TFHashBlobType(int(TInt(*SIn)));
00382     if (Type==fhbtKey){return true;}
00383   }
00384   return false;
00385 }
00386