LRUCache.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Christian Jacobi, August 14, 1986 12:54:36 pm PDT
Last Edited by: Christian Jacobi, August 18, 1986 10:33:06 am PDT
LRUCache: CEDAR DEFINITIONS =
BEGIN
Definitions for least recently used cache abstraction.
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 mattering.
Include:
PROC [h: Handle, value:
REF]
RETURNS [index:
NAT, insert:
BOOL, used:
REF];
Includes value into a lru cache
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.
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.
Fetch:
PROC [h: Handle, index:
NAT]
RETURNS [used:
REF];
Fetches a value from a lru cache.
index must have been previously returned with Include.
Considers the returned value to be used.
Reset:
PROC [h: Handle];
Empties a lru cache again.
END.