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]; 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 {RemoveEntry[i];IncludeEntryAsYoungest[i];lruCache.freeObject _ ob;RETURN [lruCache.access[i].object]};ENDLOOP;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Copyright c 1984 by Xerox Corporation.  All rights reserved.by Christian Jacobi March 7, 1984 5:59:42 pm PSTlast change Christian October 22, 1984 3:00:40 pm PDT--creates new LRU cache of suggested size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};--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Hit[];--not found--Determine where entry will go in tableMissed[];Э╩  Ш ЪЬ-Щ-JЪЬ
╧mЬ1Щ<JЪЬ0Щ0JЪЬ5Щ5ЧJШ Ъ╧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Ш Ч ЕЧ    ▄  э  