package Ġcom . sup arn atural . core . cache Ċ Ċ /** Ċ Ġ* ĠA Ġthread - safe Ġ[ InMemory Cache ] Ġwith Ġa Ġcustom ĠHash Table Ġimplementation Ġusing ĠRob in ĠH ood Ġhashing . Ċ Ġ*/ Ċ class ĠRob in H ood Prob ing Cache ( ĊĠĠĠĠĠĠĠ Ġsize : ĠInt , ĊĠĠĠĠĠĠĠ Ġpersistent Stores : ĠList < Cache Store > Ġ= Ġempty List (), ĊĠĠĠĠĠĠĠ Ġreplacement Policy : ĠCache Replacement Policy Ġ= ĠF ifo Cache Replacement Policy ( size ) Ċ ) Ġ: ĠIn Memory Cache ( size , Ġpersistent Stores , Ġreplacement Policy ) Ġ{ ĊĊĠĠĠ Ġprivate Ġfun Ġ< T Ġ: ĠCache able > ĠgetObject Unsafe ( key : ĠString ): ĠTrip le < T ?, ĠInt , ĠCache able Container ?> Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġhash Ġ= ĠhashCode ( key ) ĊĠĠĠĠĠĠĠ Ġvar Ġindex Ġ= Ġhash ĊĠĠĠĠĠĠĠ Ġdo Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtarget Obj Dis placement Ġ= Ġcompute Dis placement ( index , Ġhash ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġexisting Obj Ġ= Ġstorage [ index ]. value ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġexisting Obj Dis placement Ġ= Ġif Ġ( existing Obj Ġ== Ġnull ) ĠInt . MAX _ VALUE Ġelse Ġcompute Dis placement ( index , ĠhashCode ( existing Obj . key )) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( existing Obj Ġ!= Ġnull Ġ&& Ġexisting Obj . key Ġ== Ġkey ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠTrip le ( existing Obj . obj Ġas ĠT , Ġindex , Ġexisting Obj ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġreturn Ġnull Ġif Ġempty Ġcell Ġwith Ġpositive Ġdisplacement . ĠIf Ġan Ġentry Ġexisted , Ġit Ġmust Ġhave Ġbeen Ġfound ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġof Ġif Ġthe Ġexisting Ġobj Ġhas Ġa Ġlarger Ġdisplacement Ġthan Ġtarget Ġobj , Ġthen Ġtarget Ġobj Ġis Ġabsent Ġbecause Ġit Ġshould Ġhave ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġbeen Ġplaced Ġbefore Ġthe Ġexisting Ġobject Ġsince Ġit Ġhas Ġa Ġlower Ġdisplacement ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(( existing Obj Ġ!= Ġnull Ġ&& Ġexisting Obj Dis placement Ġ> Ġtarget Obj Dis placement )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠTrip le ( null , Ġ- 1 , Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġindex Ġ= Ġ( index Ġ+ Ġ 1 ) Ġ% Ġsize ĊĠĠĠĠĠĠĠ Ġ} Ġwhile Ġ( index Ġ!= Ġhash ) Ġ// Ġstop Ġafter Ġcomplete Ġwrap Ġaround ĊĠĠĠĠĠĠĠ Ġreturn ĠTrip le ( null , Ġ- 1 , Ġnull ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġ< T Ġ: ĠCache able > ĠgetObject ( key : ĠString ): ĠT ? Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġacquire Ġreader Ġlock ĊĠĠĠĠĠĠĠ Ġtry Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlock . acquire Read Lock () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠgetObject Unsafe < T >( key ). first ĊĠĠĠĠĠĠĠ Ġ} Ġfinally Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlock . release Read Lock () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠA Ġclass Ġrepresenting Ġa Ġgroup Ġof Ġfour Ġvalues ĊĠĠĠĠ Ġ* Ġ@ param ĠA Ġthe Ġtype Ġof Ġfirst Ġvalue ĊĠĠĠĠ Ġ* Ġ@ param ĠB Ġthe Ġtype Ġof Ġsecond Ġvalue ĊĠĠĠĠ Ġ* Ġ@ param ĠC Ġthe Ġtype Ġof Ġthird Ġvalue ĊĠĠĠĠ Ġ* Ġ@ param ĠD Ġthe Ġtype Ġof Ġfourth Ġvalue ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ property Ġfirst Ġthe Ġfirst Ġvalue ĊĠĠĠĠ Ġ* Ġ@ property Ġsecond Ġthe Ġsecond Ġvalue ĊĠĠĠĠ Ġ* Ġ@ property Ġthird Ġthe Ġthird Ġvalue ĊĠĠĠĠ Ġ* Ġ@ property Ġfourth Ġthe Ġfourth Ġvalue ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġdata Ġclass ĠQu int uple < A , ĠB , ĠC , ĠD >( val Ġfirst : ĠA , Ġval Ġsecond : ĠB , Ġval Ġthird : ĠC , Ġval Ġfourth : ĠD ) ĊĊĠĠĠ Ġprivate Ġfun Ġadd Object Unsafe ( new Obj : ĠCache able Container , Ġhash : ĠInt , Ġindex : ĠInt ): ĠQu int uple < Cache able Container ?, ĠInt , ĠInt , ĠBoolean >? Ġ{ ĊĊĠĠĠĠĠĠĠ Ġval Ġold Obj Ġ= Ġstorage [ index ]. value ĊĠĠĠĠĠĠĠ Ġvar Ġresult : ĠQu int uple < Cache able Container ?, ĠInt , ĠInt , ĠBoolean >? ĊĠĠĠĠĠĠĠ Ġif Ġ( old Obj Ġ== Ġnull Ġ|| Ġold Obj . key Ġ== Ġnew Obj . key ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcas Result Ġ= Ġstorage [ index ]. compare AndSet ( old Obj , Ġnew Obj ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult Ġ= ĠQu int uple ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! cas Result ) Ġnew Obj Ġelse Ġnull , Ġhash , Ġindex , Ġcas Result ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġold Obj Hash Ġ= ĠhashCode ( old Obj . key ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( compute Dis placement ( index , Ġhash ) Ġ< Ġcompute Dis placement ( index , ĠhashCode ( old Obj . key ))) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcas Result Ġ= Ġstorage [ index ]. compare AndSet ( old Obj , Ġnew Obj ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult Ġ= ĠQu int uple ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! cas Result ) Ġnew Obj Ġelse Ġnull , Ġhash , Ġindex , Ġcas Result ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( result . four th ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult Ġ= ĠQu int uple ( old Obj , Ġold Obj Hash , Ġold Obj Hash , Ġfalse ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnext Index Ġ= Ġ( index Ġ+ Ġ 1 ) Ġ% Ġsize ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( next Index Ġ== Ġhash ) Ġ{ Ġ// Ġtest Ġwrap Ġaround ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult Ġ= ĠQu int uple ( new Obj , Ġhash , Ġnext Index , Ġfalse ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġ< T Ġ: ĠCache able > Ġadd Object ( obj : ĠT ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġtry Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlock . acquire Write Lock () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġhash Ġ= ĠhashCode ( obj . cacheKey ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcontainer Ġ= ĠCache able Container ( obj ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcreate Ġspace ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsuper . add Object < T >( container ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġresult Ġ= Ġadd Object Unsafe ( container , Ġhash , Ġhash ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile ( result Ġ!= Ġnull Ġ&& Ġ! result . four th ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult Ġ= Ġadd Object Unsafe ( result . first !! , Ġresult . second , Ġresult . third ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġresult ?. four th Ġ?: Ġtrue ĊĠĠĠĠĠĠĠ Ġ} Ġfinally Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlock . release Write Lock () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġback Shift ( empty Cell Index : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġindex Ġ= Ġempty Cell Index ĊĊĠĠĠĠĠĠĠ Ġdo Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnext Index Ġ= Ġ( index Ġ+ Ġ 1 ) Ġ% Ġsize ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġcell Ġis Ġempty , Ġreturn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġobj Ġ= Ġstorage [ next Index ]. value Ġ?: Ġreturn ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġhash Ġ= ĠhashCode ( obj . key ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdisplacement Ġ= Ġcompute Dis placement ( next Index , Ġhash ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġobject Ġalready Ġlocated Ġin Ġthe Ġideal Ġcell ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( dis placement Ġ== Ġ 0 ) Ġreturn ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġstorage [ index ]. value Ġ= Ġobj ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstorage [ next Index ]. value Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġindex Ġ= Ġnext Index ĊĊĠĠĠĠĠĠĠ Ġ} Ġwhile Ġ( index Ġ!= Ġempty Cell Index ) ĊĊĠĠĠ Ġ} ĊĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġ@ param ĠT Ġthe Ġobject Ġbeing Ġremove Ġby Ġ[ key ]. ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġoverride Ġfun Ġ< T Ġ: ĠCache able > Ġremove Object ( key : ĠString ): ĠPair < T ?, ĠBoolean > Ġ{ ĊĠĠĠĠĠĠĠ Ġtry Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlock . acquire Write Lock () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġ( obj , Ġindex , Ġcontainer ) Ġ= ĠgetObject Unsafe < T >( key ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( obj Ġ== Ġnull Ġ|| Ġcontainer Ġ== Ġnull ) Ġreturn ĠPair ( obj , Ġfalse ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġsuper . remove Object < T >( container ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! storage [ index ]. compare AndSet ( container , Ġnull )) Ġreturn Ġremove Object ( key ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġback Shift ( index ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠPair ( obj , Ġtrue ) ĊĠĠĠĠĠĠĠ Ġ} Ġfinally Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlock . release Write Lock () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġcompute Dis placement ( index : ĠInt , Ġhash : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( index Ġ>= Ġhash ) Ġindex Ġ- Ġhash ĊĠĠĠĠĠĠĠ Ġelse Ġsize Ġ- Ġhash Ġ+ Ġindex ĊĠĠĠ Ġ} Ċ Ċ }