LRUCache.mesa
Copyright Ó 1986, 1987, 1991 by Xerox Corporation. All rights reserved.
Christian Jacobi, August 14, 1986 12:54:36 pm PDT
Last Edited by: Christian Jacobi, February 13, 1987 11:42:22 am PST
LRUCache: CEDAR DEFINITIONS =
BEGIN
Definitions for least recently used cache abstraction.
Procedures use constant time, independent of size of lru-cache.
If two lru-caches of same size, with same hash and equal procedures are used on
the same values in the same order, they will return the same numbers for index.
Handle:
TYPE =
REF LRUCacheRep;
A handle represents a least recently used cache.
LRUCacheRep: TYPE;
HashProc: TYPE = PROC [REF] RETURNS [CARDINAL];
EqualProc: TYPE = PROC [REF, REF] RETURNS [BOOL];
Create:
PROC [size:
NAT, hash: HashProc¬
NIL, equal: EqualProc¬
NIL]
RETURNS [Handle];
Creates a new empty lru cache of given size.
The following relations for hash and equal are imposed:
-hash returns always the same value given the same argument.
-2 equal values (equal returns TRUE on them) must have the same hash key.
Defaults for hash and equal are:
hash: a [low quality, fast] rope hash.
equal: Rope equality with case matter.
Include:
PROC [h: Handle, value:
REF]
RETURNS [index:
NAT, insert:
BOOL, used:
REF];
Includes value into a lru cache; this value is considered used and cache is reordered.
Returns
index: "index" of new inserted or re-used value in lru cache; 0<=index<size.
insert: value has been inserted into table [otherwise: old value re-used].
used: the "equal" val found in table, or value again, if insert=TRUE.
Search:
PROC [h: Handle, value:
REF]
RETURNS [index:
NAT, found:
BOOL, val:
REF];
Searches value in a lru cache; this value is not considered used; cache is not reordered
Returns
index: "index" of found value in lru cache, or size if not found; 0<=index<=size.
found: value has been found in cache.
val: the "equal" val found in table.
Fetch:
PROC [h: Handle, index:
NAT]
RETURNS [used:
REF];
Fetches a value from a lru cache; this value is considered used and cache is reordered.
index must have been previously returned with Include.
Peek:
PROC [h: Handle, index:
NAT]
RETURNS [val:
REF];
Fetches a value from a lru cache; this value is not considered used; cache is not reordered.
index must have been previously returned with Include.
Reset:
PROC [h: Handle];
Empties a lru cache again.
END.