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
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.
For some usefull hash and equal procs, you might look at the HashTable package.
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.