LRUCacheDoc.tioga
Created by: Christian Jacobi, August 15, 1986 1:17:29 pm PDT
Last Edited by: Christian Jacobi, February 13, 1987 12:33:35 pm PST
LRUCache
CEDAR 7.0 — FOR INTERNAL XEROX USE ONLY
LRUCache
Christian Jacobi
© Copyright 1986 Xerox Corporation. All rights reserved.
Abstract: Definitions for least recently used cache abstraction.
Created by: Christian Jacobi
Maintained by: Christian Jacobi <Jacobi.pa>
Keywords: lru, cache
XEROX Xerox Corporation
Palo Alto Research Center
3333 Coyote Hill Road
Palo Alto, California 94304
For Internal Xerox Use Only
LRUCache
Definitions for least recently used cache abstraction.
The definition
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 = ...;
A handle represents a least recently used cache.
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.
Usage
To start LRUCache:
use the install file LRUCache.Install
LRU-caches are completely garbage collected when they are no more used
For some usefull hash and equal procs, you might look at the HashTable package.
Rational
LRU caches have been used in ChipNDale for two purposes:
Compaction of output files:
Atoms are entered into a lru-cache before output. If the atom was found, only its index into the lru-cache was written. The reading routine builds an array with aequvalent entries! (For robustness: Not anoyther lru cache is used; the reader does not need to know the cache size)
Reduce of memory usage:
Immutable objects are entered into a lru-cache on creation. This allows to re-use already created objects without caching all objects: The objects are still subject to the garbage collector.