
LRUCache: CEDAR DEFINITIONS = 
BEGIN


Handle: TYPE = REF LRUCacheRep;
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];

Include: PROC [h: Handle, value: REF] RETURNS [index: NAT, insert: BOOL, used: REF];

Search: PROC [h: Handle, value: REF] RETURNS [index: NAT, found: BOOL, val: REF];

Fetch: PROC [h: Handle, index: NAT] RETURNS [used: REF];

Peek: PROC [h: Handle, index: NAT] RETURNS [val: REF];

Reset: PROC [h: Handle];

END.


     
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
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.
A handle represents a least recently used cache.
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.
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.
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.
Fetches a value from a lru cache; this value is considered used and cache is reordered.  
index must have been previously returned with Include.
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.
Empties a lru cache again.
 Êw  –(cedarcode) style•NewlineDelimiter
™ codešœ™Kšœ	Ïeœ<™HK™1K™C—K˜ KšÏnœÏkœŸœ˜KšŸ˜K˜ šœÏbœ œ œ™8K™ Kšœ?™?KšœP™PKšœO™O—K˜ šœŸœŸœ˜Kšœ0™0KšœŸœ˜K˜ —Kšœ
ŸœŸœŸœŸœŸœ˜/KšœŸœŸœŸœŸœŸœŸœ˜1K˜ šžœŸœŸœŸœŸœŸœ
˜TKšœ,™,šœ7™7Kšœ>™>KšœK™K—šœ ™ Kšœ&™&Kšœ&™&—K˜ —šžœŸœŸœŸœ	Ÿœ
ŸœŸœ˜TKšœV™VKšœ™KšœP™PKšœO™OKšœDŸœ™IK˜ —šžœŸœŸœŸœ	Ÿœ	ŸœŸœ˜QKšœX™XKšœ™KšœU™UKšœ*™*Kšœ(™(K˜ —š
žœŸœŸœŸœŸœ˜8KšœY™YKšœ6™6K˜ —š
žœŸœŸœŸœŸœ˜6Kšœ^™^Kšœ6™6K˜ —šžœŸœ˜Jšœ™K˜ —KšŸœ˜K˜ K˜ — …—    R  ã  