DIRECTORYCDLRUCache,CD;CDLRUCacheImpl: CEDAR MONITOR LOCKS lruCache USING lruCache: LRUCache IMPORTS CDEXPORTS CDLRUCache = BEGINAequivalenceProc: TYPE = PROC[mySpecific, other: REF ANY] RETURNS [BOOL];NewProc: TYPE = PROC [] RETURNS [CD.ObPtr];LRUCache: TYPE = REF LRUCacheRep;LRUCacheRep: PUBLIC TYPE = MONITORED RECORD [freeObject: CD.ObPtr_NIL,freeEntry: CARDINAL_0, aequivalence: AequivalenceProc,new: NewProc,access: SEQUENCE size: CARDINAL OF LinkRecord -- access[0] is not used but a dummy];DefaultAequivalence: PROC [mySpecific, other: REF ANY] RETURNS [BOOL] = {RETURN [mySpecific=other]};Create: PUBLIC PROC [size: CARDINAL, aequivalenceProc: AequivalenceProc, newProc: NewProc] RETURNS [LRUCache] = BEGINlru: LRUCache;size _ MAX[MIN[size, 256], 1]+1; --users don't know that access[0] is a dummylru _ NEW[LRUCacheRep[size]];lru.aequivalence _ aequivalenceProc;IF lru.aequivalence=NIL THEN lru.aequivalence_DefaultAequivalence; lru.new _ newProc;RETURN [lru]END;UnusedOrNew: PUBLIC ENTRY PROC [lruCache: LRUCache] RETURNS [CD.ObPtr] =BEGINob: CD.ObPtr;IF lruCache.new=NIL THEN RETURN WITH ERROR CD.Error[ec: callingError, explanation: "no newproc defined"];IF lruCache.freeObject=NIL THEN ob _ lruCache.new[] ELSE {ob _ lruCache.freeObject;lruCache.freeObject _ NIL};RETURN [ob]END;LinkRecord: TYPE = RECORD[object: CD.ObPtr, hash: INT,older, younger: INTEGER]; hit: INT_0;missed: INT_0;Hit: PROC = INLINE {IF hit<LAST[INT] THEN hit_hit+1};Missed: PROC = INLINE {IF missed<LAST[INT] THEN missed_missed+1};ReplaceByAequivalent: PUBLIC ENTRY PROC [lruCache: LRUCache, ob: CD.ObPtr] RETURNS [CD.ObPtr] =BEGINHash: PROC[ob: CD.ObPtr] RETURNS [INT] = INLINE {RETURN [(ob.size.x MOD 1000B)*400000B+(ob.size.y MOD 1000B)*400B+ob.level]};Aequivalent: PROC[ob, ob2: CD.ObPtr] RETURNS [BOOL] = INLINE BEGINIF ob.size#ob2.size OR ob.p#ob2.p OR ob.level#ob2.level THEN RETURN [FALSE];RETURN [lruCache.aequivalence[ob.specificRef, ob2.specificRef! ANY => GOTO SomeError]]EXITSSomeError => RETURN [FALSE]END;RemoveEntry: INTERNAL PROC[entry: INTEGER] =BEGINlruCache.access[lruCache.access[entry].older].younger _ lruCache.access[entry].younger;lruCache.access[lruCache.access[entry].younger].older _ lruCache.access[entry].older;END;IncludeEntryAsYoungest: INTERNAL PROC[entry: INTEGER] =BEGINlruCache.access[entry].older _ lruCache.access[0].older;lruCache.access[entry].younger _ 0;lruCache.access[lruCache.access[0].older].younger _ entry;lruCache.access[0].older _ i;END;i: INTEGER;hash: INT = Hash[ob];FOR i _ lruCache.access[0].older, lruCache.access[i].older WHILE i#0 DOIF hash=lruCache.access[i].hash AND Aequivalent[lruCache.access[i].object, ob] THEN {Hit[];RemoveEntry[i];IncludeEntryAsYoungest[i];lruCache.freeObject _ ob;RETURN [lruCache.access[i].object]};ENDLOOP;Missed[];IF lruCache.freeEntry<lruCache.size THEN {i _ lruCache.freeEntry; lruCache.freeEntry _ lruCache.freeEntry + 1;}ELSE {i _ lruCache.access[0].younger;RemoveEntry[i];};lruCache.access[i].object _ ob;lruCache.access[i].hash _ hash;IncludeEntryAsYoungest[i];RETURN [lruCache.access[i].object]END;END.   о  CDLRUCacheImpl.mesa        a Chipndale moduleby Christian Jacobi March 7, 1984 5:59:42 pm PSTlast change Christian March 7, 1984 5:59:46 pm PST--creates new LRU cache of suggested size--returns either "ob" or an aequivalent object to "ob"--side effect: introduces "ob" in aequivalence table to be accessed by others.--consider "ob" immutable! respectively, on any further change, it may cause--the same change made to all or some aequivalent objects in past and future--no error should be raised--do not test marked --makes no comparison of properties--assume entry properly in list--assume entry properly in list--not found--Determine where entry will go in tableЭ╩r  Ш JЪЬ-Щ-JЪЬ0Щ0JЪЬ2Щ2JШ Ъ╧k	Ш	JЪЬШJЪЭЬШЧJШ Ъ╧bЬЭЬЭЬШJЪЭЬ
ЭЬШ(JЪЭ
Ш
JЪЭЬШЧJЪЭШJЪЬЭЬЭЬЭЬЭЬЭЬЭЬШIJЪ	Ь	ЭЬЭЬЭЬЭЬШ+JШ JЪЬ
ЭЬЭЬШ!ЪЬЭЬЭ	ЬЭЬШ-JЪЬЭЬЭЬШJЪЬЭЬШJЪЬШJШJЪЬЭЬЭЬЭЬ╧c$ШRJЪЬШЧJШ Ъ╧nЬЭЬЭЬЭЬЭЬЭЬШIJЪЭЬШJШЧJШ Ъ
аЬЭЬЭЬЭЬ8ЭЬШpJЪЬ)Щ)JЪЭШJЪЬШJЪЬЭЬЭЬЯ,ШMJЪЬЭЬШJЪЬ$Ш$JЪЭЬЭЬЭЬ'ШCJЪЬШJЪЭЬШJЪЭЬШЧJШ Ъ
аЬЭЬЭЬЭЬЭЬ	ШHJЪЭШJЪЬЭЬШJЪЭЬЭЬЭЬЭЬЭЬЭЬЭЬ<ШiJЪЭЬЭЬЭЬШ4ЪЭЬШJЪЬШJЪЬЭШJШЧJЪЭЬШJЪЭЬШЧJШ ЪЬЭЬЭЬШJЪЬЭЬЭЬШJЪЬЭШJЪЬШЧJШ JЪЬЭЬШJЪЬЭЬШJЪаЬЭЬЭЬЭЬЭЬЭЬЭЬШ5JЪаЬЭЬЭЬЭЬЭЬЭЬЭЬШAJШ Ъ
аЬЭЬЭЬЭЬЭЬ	Ш_JЪЬ6Щ6JЩNJЪЬLЩLJЪЬLЩLЪЭШJЪЬЩЧJШ ЪаЬЭЬЭЬЭЬЭЬЭЬШ1ЪЭЬШJЪЬЭЬЭЬШBЧJЪЬШЧJШ ЪаЬЭЬ
ЭЬЭЬЭЬЭЬШ=JЪЬЩJЪЬ#Щ#JЪЭШЪЭЬЭЬШ"JЪЭЬЭЬЭЬЭЬШ*ЧJЪЭЬ9ЭЬЭЬШVЪЭШJЪЬЭЬЭЬШЧJЪЭЬШЧJШ ЪаЬЭЬЭЬШ,JЪЬЩJЪЭШJЪЬWШWJЪЬUШUJЪЭЬШJШ ЧЪаЬЭЬЭЬШ7JЪЬЩJЪЭШJЪЬ8Ш8JЪЬ#Ш#JЪЬ:Ш:JЪЬШJЪЭЬШЧJЩ JЪЬЭЬШJЪЬЭЬШЪЭЬ8ЭЬЭШGЪЭЬШ JЪЭЬ,ЭЬШ5JЪЬШJЪЬШJШJЪЬШJЪЭЬШ"JЪЬШЧJЪЭЬШЧJЪЬЩJЩ(JЪЬ	Ш	ЪЭЬ"ЭЬШ*JЪЬШJЪЬ,Ш,JЪЬШЧЪЭЬШJЪЬШJЪЬШJШЧJЪЬШJЪЬШJЪЬШJЪЭЬШ"JЪЭЬШЧJШ JЪЭЬШJШ Ч ЕЧ    А  а  