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
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;
N. B. The entryList in a CacheRep has a list head;
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;
Destroy[entries.first];
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;
trimmedSize is not correctly monitored, but it is only a hint.
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;
SafeStorage.ReclaimCollectibleObjects[suspendMe: FALSE, traceAndSweep: FALSE];
};
};
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] ~ {
-- silly example that returns a list of INTs from 1 to n.
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.