DIRECTORY Ascii USING [Lower], Atom USING [GetPName], FunctionCache USING [Cache, CacheEntry, CacheInfo, CacheRep, ClientID, CompareProc, Domain, FuncProc, Match, Range], Rope USING [Equal, ROPE]; FunctionCacheImpl: CEDAR MONITOR LOCKS x USING x: Cache IMPORTS Ascii, Atom, Rope EXPORTS FunctionCache ~ BEGIN OPEN FunctionCache; Create: PUBLIC PROC [maxEntries: INT, maxTotalSize: INT] RETURNS [Cache] ~ { RETURN [NEW[CacheRep ¬ [nEntries: 0, maxEntries: maxEntries, totalSize: 0, maxTotalSize: maxTotalSize, entryList: LIST[[NIL, NIL, NIL, 0]]]]]; }; ROPE: TYPE ~ Rope.ROPE; LORA: TYPE ~ LIST OF REF ANY; ListCompare: PROC [a, b: LORA, match: Match] RETURNS [BOOL] ~ { UNTIL a=NIL OR b=NIL DO IF a.first=b.first OR Equal[a.first, b.first, match] THEN {a ¬ a.rest; b ¬ b.rest} ELSE RETURN [FALSE]; ENDLOOP; RETURN [a=b]; }; Equal: PUBLIC PROC [a, b: Domain, match: Match] RETURNS [BOOL] ~ { IF a = b THEN RETURN [TRUE]; IF match = refs THEN RETURN [FALSE]; WITH a SELECT FROM x: REF INT => WITH b SELECT FROM y: REF INT => RETURN [x­=y­]; ENDCASE; x: REF REAL => WITH b SELECT FROM y: REF REAL => RETURN [x­=y­]; ENDCASE; x: REF CHAR => WITH b SELECT FROM y: REF CHAR => RETURN [IF match = case THEN (x­=y­) ELSE (Ascii.Lower[x­]=Ascii.Lower[y­])]; ENDCASE; x: ATOM => WITH b SELECT FROM y: ATOM => RETURN [Rope.Equal[Atom.GetPName[x], Atom.GetPName[y], match#text]]; ENDCASE; x: ROPE => WITH b SELECT FROM y: ROPE => RETURN [Rope.Equal[x, y, match#text]]; ENDCASE; x: LORA => WITH b SELECT FROM y: LORA => RETURN [ListCompare[x, y, match]]; ENDCASE; ENDCASE; RETURN [FALSE]; }; Eval: PUBLIC PROC [x: Cache, F: FuncProc, arg: Domain, match: Match, clientID: ClientID ¬ NIL] RETURNS [value: Range] ~ { refCompare: CompareProc ~ {good ¬ arg = argument}; fancyCompare: CompareProc ~ {good ¬ arg= argument OR Equal[arg, argument, match]}; ok: BOOL; [value, ok] ¬ Lookup[x, IF match=refs THEN refCompare ELSE fancyCompare, clientID]; IF NOT ok THEN { size: INT; [value, size] ¬ F[arg]; Insert[x: x, argument: arg, value: value, size: size, clientID: clientID]; }; }; Insert: PUBLIC ENTRY PROC [x: Cache, argument: Domain, value: Range, size: INT, clientID: ClientID] ~ { x.entryList.rest ¬ CONS[[clientID: clientID, argument: argument, value: value, size: size], x.entryList.rest]; x.nEntries ¬ x.nEntries + 1; x.totalSize ¬ x.totalSize + size; Validate[x]; }; Lookup: PUBLIC ENTRY PROC [x: Cache, compare: CompareProc, clientID: ClientID ¬ NIL] RETURNS [value: Range, ok: BOOL] ~ { ENABLE UNWIND => NULL; prev: LIST OF CacheEntry ¬ x.entryList; p: LIST OF CacheEntry ¬ prev.rest; IF p # NIL THEN { IF p.first.clientID = clientID AND compare[p.first.argument] THEN RETURN [value: p.first.value, ok: TRUE]; prev ¬ p; }; UNTIL (p ¬ prev.rest) = NIL DO IF p.first.clientID = clientID AND compare[p.first.argument] THEN { prev.rest ¬ p.rest; p.rest ¬ x.entryList.rest; x.entryList.rest ¬ p; RETURN [value: p.first.value, ok: TRUE]; }; prev ¬ p; ENDLOOP; RETURN [value: NIL, ok: FALSE]; }; Any: PUBLIC CompareProc ~ {RETURN [TRUE]}; Obtain: PUBLIC ENTRY PROC [x: Cache, compare: CompareProc, limit: INT, clientID: ClientID] RETURNS [LIST OF CacheEntry] ~ { ENABLE UNWIND => NULL; list: LIST OF CacheEntry ¬ NIL; end: LIST OF CacheEntry ¬ NIL; prev: LIST OF CacheEntry ¬ x.entryList; p: LIST OF CacheEntry ¬ prev.rest; UNTIL limit = 0 OR p = NIL DO IF p.first.clientID = clientID AND compare[p.first.argument] THEN { x.nEntries ¬ x.nEntries - 1; x.totalSize ¬ x.totalSize - p.first.size; IF end = NIL THEN {list ¬ end ¬ p} ELSE {end.rest ¬ p; end ¬ p}; p ¬ prev.rest ¬ p.rest; end.rest ¬ NIL; limit ¬ limit-1; } ELSE { prev ¬ p; p ¬ prev.rest; }; ENDLOOP; IF list#NIL THEN Validate[x]; RETURN [list] }; Release: PUBLIC ENTRY PROC [x: Cache, list: LIST OF CacheEntry] ~ { IF list # NIL THEN { p: LIST OF CacheEntry ¬ list; DO x.nEntries ¬ x.nEntries + 1; x.totalSize ¬ x.totalSize + p.first.size; IF p.rest = NIL THEN EXIT; p ¬ p.rest; ENDLOOP; p.rest ¬ x.entryList.rest; x.entryList.rest ¬ list; Validate[x]; }; }; Flush: PUBLIC ENTRY PROC [x: Cache] ~ { entries: LIST OF CacheEntry ¬ x.entryList.rest; x.nEntries ¬ 0; x.totalSize ¬ 0; x.entryList.rest ¬ NIL; WHILE entries # NIL DO rest: LIST OF CacheEntry ¬ entries.rest; entries.rest ¬ NIL; entries ¬ rest; ENDLOOP; }; GetInfo: PUBLIC ENTRY PROC [x: Cache] RETURNS [CacheInfo] ~ { RETURN [[nEntries: x.nEntries, maxEntries: x.maxEntries, totalSize: x.totalSize, maxTotalSize: x.maxTotalSize]] }; GetList: PUBLIC ENTRY PROC [x: Cache] RETURNS [list: LIST OF CacheEntry] ~ { end: LIST OF CacheEntry ¬ NIL; FOR p: LIST OF CacheEntry ¬ x.entryList, p.rest UNTIL p=NIL DO IF end = NIL THEN {list ¬ end ¬ LIST[p.first]} ELSE {end.rest ¬ LIST[p.first]; end ¬ end.rest}; ENDLOOP; }; SetLimits: PUBLIC ENTRY PROC [x: Cache, maxEntries: INT, maxTotalSize: INT] ~ { x.maxEntries ¬ maxEntries; x.maxTotalSize ¬ maxTotalSize; Validate[x]; }; SetValueSize: PUBLIC ENTRY PROC [x: Cache, value: Range, size: INT] ~ { FOR p: LIST OF CacheEntry ¬ x.entryList.rest, p.rest UNTIL p = NIL DO IF p.first.value = value THEN { x.totalSize ¬ x.totalSize - p.first.size + size; p.first.size ¬ size; }; ENDLOOP; Validate[x]; }; CheckInvariants: INTERNAL PROC [x: Cache] ~ { n: INT ¬ 0; s: INT ¬ 0; FOR p: LIST OF CacheEntry ¬ x.entryList.rest, p.rest UNTIL p = NIL DO n ¬ n + 1; s ¬ s + p.first.size; ENDLOOP; IF n # x.nEntries THEN ERROR; IF s # x.totalSize THEN ERROR; }; debug: BOOL ¬ FALSE; Validate: INTERNAL PROC [x: Cache] ~ INLINE { IF debug THEN CheckInvariants[x]; IF x.nEntries > x.maxEntries OR x.totalSize > x.maxTotalSize THEN EnforceLimits[x]; IF debug THEN CheckInvariants[x]; }; triggerSize: INT ¬ 8000; trimmedSize: INT ¬ 0; EnforceLimits: INTERNAL PROC [x: Cache] ~ { e: INT ¬ 0; s: INT ¬ 0; emax: INT ~ x.maxEntries; smax: INT ~ x.maxTotalSize; last: LIST OF CacheEntry ¬ x.entryList; p: LIST OF CacheEntry; UNTIL (p ¬ last.rest) = NIL OR e+1 > emax OR s+p.first.size > smax DO e ¬ e + 1; s ¬ s + p.first.size; last ¬ p; ENDLOOP; trimmedSize ¬ (x.totalSize-s) + trimmedSize; last.rest ¬ NIL; x.nEntries ¬ e; x.totalSize ¬ s; UNTIL p = NIL DO t: LIST OF CacheEntry ¬ p.rest; p.first.argument ¬ NIL; p.first.value ¬ NIL; p.rest ¬ NIL; p ¬ t; ENDLOOP; IF trimmedSize > triggerSize THEN { trimmedSize ¬ 0; }; }; GlobalCache: PUBLIC PROC RETURNS [Cache] ~ { RETURN [globalCache] }; globalCache: Cache ¬ Create[maxEntries: 100, maxTotalSize: 1000000 --VMSideDoor.rmPages*(256/2)--]; Example: PROC [n: INT] RETURNS [result: LIST OF INT] ~ { cache: Cache ~ GlobalCache[]; compare: CompareProc ~ { good ¬ FALSE; WITH argument SELECT FROM i: REF INT => IF i­ = n THEN good ¬ TRUE; ENDCASE; }; val: REF; ok: BOOL; [val, ok] ¬ Lookup[cache, compare, $SillyExample]; IF ok THEN result ¬ NARROW[val] ELSE { result ¬ LIST[]; FOR i: INT DECREASING IN [1..n] DO result ¬ CONS[i, result]; ENDLOOP; Insert[x: cache, argument: NEW[INT ¬ n], value: result, size: n*(SIZE[INT]+SIZE[REF]+2), clientID: $SillyExample]; }; }; END. β FunctionCacheImpl.mesa Copyright Σ 1985, 1987, 1990, 1991 by Xerox Corporation. All rights reserved. Michael Plass, February 10, 1988 9:13:52 am PST Russ Atkinson (RRA) October 10, 1990 9:19 pm PDT N. B. The entryList in a CacheRep has a list head; Destroy[entries.first]; trimmedSize is not correctly monitored, but it is only a hint. SafeStorage.ReclaimCollectibleObjects[suspendMe: FALSE, traceAndSweep: FALSE]; -- silly example that returns a list of INTs from 1 to n. Κ ˜–(cedarcode) style•NewlineDelimiter ™head™Icodešœ ΟeœC™NL™/L™0L™šΟk ˜ Lšœžœ ˜Lšœžœ ˜Lšœžœa˜tLšœžœ žœ˜——šΟnœžœž˜ Kšžœžœ ˜Lšžœ˜Lšžœ˜Lšœžœžœ˜L˜šœ2™2L˜—š Ÿœžœžœžœžœžœ ˜LLš žœžœgžœžœžœžœ ˜ŽLšœ˜L˜—Lšžœžœžœ˜š žœžœžœžœžœžœ˜L˜—š Ÿ œžœžœžœžœ˜?š žœžœžœžœž˜Lšžœžœ žœ˜RLšžœžœžœ˜Lšžœ˜—Lšžœ˜ Lšœ˜L˜—š Ÿœžœžœžœžœ˜BLšžœžœžœžœ˜Lšžœžœžœžœ˜$šžœžœž˜šœžœžœ˜ Lšžœžœžœžœžœžœ žœ˜9—šœžœžœ˜Lšžœžœžœžœžœžœ žœ˜:—šœžœžœ˜š žœžœžœžœžœ˜!Lšžœžœžœ žœ$˜MLšžœ˜——šœžœ˜ šžœžœžœžœ˜Lšžœ>˜DLšžœ˜——šœžœ˜ Lš žœžœžœžœžœ!žœ˜M—šœžœ˜ Lš žœžœžœžœžœžœ˜I—Lšžœ˜—Lšžœžœ˜Lšœ˜L˜—š ŸœžœžœIžœžœ˜yL˜2Lšœ2žœ˜RLšœžœ˜ Lšœžœ žœ žœ˜Sšžœžœžœ˜Lšœžœ˜ Lšœ˜LšœJ˜JLšœ˜—Lšœ˜L˜—š Ÿœžœžœžœ2žœ˜gLšœžœW˜nLšœ˜Lšœ!˜!Lšœ ˜ Lšœ˜L˜—šŸœžœžœžœ7žœžœžœ˜yLšžœžœžœ˜Lšœžœžœ˜'Lšœžœžœ˜"šžœžœžœ˜Lš žœžœžœžœžœ˜jLšœ ˜ Lšœ˜—šžœžœž˜šžœžœžœ˜CLšœ˜Lšœ˜Lšœ˜Lšžœžœ˜(Lšœ˜—Lšœ ˜ Lšžœ˜—Lšžœ žœžœ˜Lšœ˜L˜—šŸœžœžœžœ˜*L˜—šŸœžœžœžœ)žœžœžœžœ˜{Lšžœžœžœ˜Lšœžœžœžœ˜Lšœžœžœžœ˜Lšœžœžœ˜'Lšœžœžœ˜"šžœ žœžœž˜šžœžœ˜<šžœ˜Lšœ˜Lšœ)˜)šžœž˜ Lšžœ˜Lšžœ˜—Lšœ˜Lšœ žœ˜Lšœ˜Lšœ˜—šžœ˜Lšœ ˜ Lšœ˜Lšœ˜——Lšžœ˜—Lšžœžœžœ ˜Lšžœ˜ Lšœ˜L˜—š Ÿœžœžœžœžœžœ˜Cšžœžœžœ˜Lšœžœžœ˜šž˜Lšœ˜Lšœ)˜)Lšžœ žœžœžœ˜Lšœ ˜ Lšžœ˜—Lšœ˜Lšœ˜Lšœ ˜ Lšœ˜—Lšœ˜L˜—šŸœžœž œ˜'Lšœ žœžœ˜/Lšœ˜Lšœ˜Lšœžœ˜šžœ žœž˜Lšœžœžœ˜(Lšœ™Lšœžœ˜Lšœ˜Lšžœ˜—Lšœ˜L˜—š Ÿœžœžœžœ žœ˜=Lšžœi˜oLšœ˜L˜—šŸœžœžœžœ žœžœžœ˜LLšœžœžœžœ˜š žœžœžœ"žœžœž˜>Lšžœžœžœžœ ˜.Lšžœ žœ˜0Lšžœ˜—Lšœ˜L˜—š Ÿ œžœžœžœžœžœ˜OLšœ˜Lšœ˜Lšœ ˜ Lšœ˜L˜—š Ÿ œžœžœžœ žœ˜Gš žœžœžœ'žœžœž˜Ešžœžœ˜Lšœ0˜0Lšœ˜Lšœ˜—Lšžœ˜—Lšœ ˜ Lšœ˜L˜—šŸœžœžœ˜-Lšœžœ˜ Lšœžœ˜ š žœžœžœ'žœžœž˜EL˜ Lšœ˜Lšžœ˜—Lšžœžœžœ˜Lšœžœžœ˜Lšœ˜L˜—Lšœžœžœ˜šŸœžœžœžœ˜-Lšžœžœ˜!Lšžœžœžœ˜SLšžœžœ˜!Lšœ˜L˜—Lšœ žœ˜šœ žœ˜Lšœ>™>L˜—šŸ œžœžœ˜+Lšœžœ˜ Lšœžœ˜ Lšœžœ˜Lšœžœ˜Lšœžœžœ˜'Lšœžœžœ ˜š žœžœžœžœžœžœž˜ELšœ ˜ Lšœ˜Lšœ ˜ Lšžœ˜—Lšœ,˜,Lšœ žœ˜Lšœ˜Lšœ˜šžœžœž˜Lšœžœžœ˜Lšœžœ˜Lšœžœ˜Lšœ žœ˜ L˜Lšžœ˜—šžœžœ˜#Lšœ˜Lšœ1žœžœ™NLšœ˜—Lšœ˜L˜—š Ÿ œžœžœžœ žœ˜DL˜—šœc˜cL˜—šŸœžœžœžœ žœžœžœ˜8L™9Lšœ˜šœ˜Lšœžœ˜ šžœ žœž˜Lš œžœžœžœžœžœ˜)Lšžœ˜—Lšœ˜—Lšœžœžœ˜Lšœ2˜2Lšžœžœ žœ˜šžœ˜Lšœ žœ˜š žœžœž œžœž˜"Lšœ žœ ˜Lšžœ˜—Lš œžœžœžœžœžœžœ˜rL˜—Lšœ˜L˜——L˜Lšžœ˜L˜—…—8)²