DIRECTORY
Ascii USING [Lower],
Atom USING [GetPName],
FunctionCache USING [Cache, CacheEntry, CacheInfo, CacheRep, ClientID, CompareProc, Domain, FuncProc, Match, Range],
Rope USING [Equal, ROPE],
SafeStorage USING [ReclaimCollectibleObjects],
VMSideDoor USING [rmPages];
~
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 [equal:
BOOL ] ~ {
equal ←
IF a = b
THEN
TRUE
ELSE IF match = refs THEN FALSE
ELSE WITH a SELECT FROM
A: REF INT => (WITH b SELECT FROM B: REF INT => (A^=B^), ENDCASE => FALSE),
A: REF REAL => (WITH b SELECT FROM B: REF REAL => (A^=B^), ENDCASE => FALSE),
A: REF CHAR => (WITH b SELECT FROM B: REF CHAR => IF match = case THEN (A^=B^) ELSE (Ascii.Lower[A^]=Ascii.Lower[B^]), ENDCASE => FALSE),
A: ATOM => (WITH b SELECT FROM B: ATOM => (Rope.Equal[Atom.GetPName[A], Atom.GetPName[B], match#text]), ENDCASE => FALSE),
A: ROPE => (WITH b SELECT FROM B: ROPE => (Rope.Equal[A, B, match#text]), ENDCASE => FALSE),
A: LORA => (WITH b SELECT FROM B: LORA => ListCompare[A, B, match], ENDCASE => FALSE),
ENDCASE => 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:
LIST
OF CacheEntry] ~ {
ENABLE UNWIND => NULL;
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; -- will be set later
limit ← limit-1;
};
prev ← p;
p ← prev.rest;
ENDLOOP;
IF end#
NIL
THEN {
end.rest ← NIL;
Validate[x];
};
};
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];
};
};
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: 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
← WITH argument
SELECT
FROM
i: REF INT => (i^ = n),
ENDCASE => FALSE;
};
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];
};
};