LRUCacheImpl.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Table of least recently used ropes
Created by Christian Jacobi, August 14, 1986 12:54:36 pm PDT
Last Edited by: Christian Jacobi, August 18, 1986 10:30:53 am PDT
DIRECTORY
LRUCache,
Rope,
Process,
RopeHash,
SafeStorage;
LRUCacheImpl:
CEDAR
MONITOR
LOCKS h
USING h: Handle
IMPORTS Process, Rope, RopeHash, SafeStorage
EXPORTS LRUCache =
BEGIN
OPEN LRUCache;
Handle: TYPE = REF LRUCacheRep;
FieldRec: TYPE = RECORD [value: REF←NIL, el: REF Element←NIL];
LRUCacheRep:
PUBLIC
TYPE =
MONITORED
RECORD [
next, size: NAT ← 0,
hash: HashProc,
equal: EqualProc,
dummy: REF Element,
s: SEQUENCE alloc: NAT OF FieldRec
];
dummy: dummy element in circular double linked list; rule:
new elements are included to the left of dummy
old elements are removed to the right of dummy
Element:
TYPE =
RECORD [
index: NAT ← 0,
hashIndex: NAT ← 0,
left, right, hashNext: REF Element ← NIL
];
Create:
PUBLIC
PROC [size:
NAT, hash: HashProc←
NIL, equal: EqualProc←
NIL]
RETURNS [h: Handle] = {
IF size<1 THEN ERROR;
h ← NEW[LRUCacheRep[size/2*2+3]];
h.size ← size;
h.dummy ← NEW[Element←[]];
h.hash ← hash;
h.equal ← equal;
Reset[h];
};
Include:
PUBLIC
ENTRY
PROC [h: Handle, value:
REF]
RETURNS [index:
NAT𡤀, insert:
BOOL, used:
REF] = {
ENABLE UNWIND => NULL;
x: NAT; --hash index
el: REF Element;
FindEl:
PROC []
RETURNS [p:
REF Element ← h.s[x].el] =
INLINE {
--quick check using pointer equality first [we assume this to succeed often]
WHILE p#
NIL
DO
IF h.s[p.index].value=value THEN RETURN;
p ← p.hashNext;
ENDLOOP;
--serious checking
p ← h.s[x].el;
WHILE p#
NIL
DO
IF h.equal#
NIL
THEN {
IF h.equal[h.s[p.index].value, value] THEN RETURN;
}
ELSE {
IF Rope.Equal[NARROW[h.s[p.index].value], NARROW[value]] THEN RETURN;
};
p ← p.hashNext;
ENDLOOP;
};
HashExcl:
PROC [] =
INLINE {
IF h.s[el.hashIndex].el=el THEN h.s[el.hashIndex].el ← el.hashNext
ELSE {
p: REF Element ← h.s[el.hashIndex].el;
WHILE p#
NIL
DO
IF p.hashNext=el THEN {p.hashNext ← el.hashNext; EXIT};
p ← p.hashNext
ENDLOOP;
};
};
HashIncl:
PROC [] =
INLINE {
el.hashIndex ← x;
el.hashNext ← h.s[x].el;
h.s[x].el ← el;
};
CircleExcl:
PROC [] =
INLINE {
--exclude el, where ever it is
el.left.right ← el.right;
el.right.left ← el.left;
};
CircleIncl:
PROC [] =
INLINE {
--include el to the left of h.dummy
el.right ← h.dummy;
el.left ← h.dummy.left;
h.dummy.left ← el.left.right ← el;
};
x ← (IF h.hash#NIL THEN h.hash[value] ELSE RopeHash.FromRope[NARROW[value]]) MOD h.alloc;
el ← FindEl[];
IF (insert ← el=
NIL)
THEN {
IF h.next>=h.size
THEN {
el ← h.dummy.right;
CircleExcl[];
CircleIncl[];
IF x#el.hashIndex
THEN {
HashExcl[];
HashIncl[];
}
}
ELSE {
el ← NEW[Element←[index: h.next]];
h.next ← h.next+1;
CircleIncl[];
HashIncl[];
};
h.s[el.index].value ← value;
}
ELSE {
--found value
CircleExcl[];
CircleIncl[];
};
index ← el.index;
used ← h.s[index].value;
};
Fetch:
PUBLIC
ENTRY
PROC [h: Handle, index:
NAT]
RETURNS [used:
REF] = {
ENABLE UNWIND => NULL;
el: REF Element;
CircleExcl:
PROC [] =
INLINE {
--identical code in Include
--exclude el, where ever it is
el.left.right ← el.right;
el.right.left ← el.left;
};
CircleIncl:
PROC [] =
INLINE {
--identical code in Include
--include el to the left of h.dummy
el.right ← h.dummy;
el.left ← h.dummy.left;
h.dummy.left ← el.left.right ← el;
};
[used, el] ← h.s[index];
CircleExcl[];
CircleIncl[];
};
Reset:
PUBLIC
ENTRY
PROC [h: Handle] = {
ENABLE UNWIND => NULL;
h.next ← 0;
h.dummy.left ← h.dummy.right ← h.dummy;
FOR i:
NAT
IN [0..h.size)
DO
h.s[i].value ← NIL;
h.s[i].el ← NIL;
ENDLOOP
};
Destroy:
PROC [h: Handle] = {
IF h=NIL OR h.dummy=NIL THEN RETURN;
--absolutely necessary
h.dummy.left ← h.dummy.right ← NIL;
--pure friendlyness to the garbage collector
FOR i:
NAT
IN [0..h.size)
DO
el: REF Element ← h.s[i].el;
IF el#NIL THEN el.left ← el.right ← el.hashNext ← NIL;
h.s[i].value ← NIL;
h.s[i].el ← NIL;
ENDLOOP;
h.dummy ← NIL;
};
LRUFinalizerProcess:
PROC[fooFQ: SafeStorage.FinalizationQueue] = {
DO
h: Handle = NARROW[SafeStorage.FQNext[fooFQ]];
Destroy[h];
ENDLOOP
};
fooFQ: SafeStorage.FinalizationQueue = SafeStorage.NewFQ[];
TRUSTED {Process.Detach[FORK LRUFinalizerProcess[fooFQ]]};
END.