SparseMemory.mesa
Copyright © 1984, 1985 by Xerox Corporation. All rights reserved.
Russ Atkinson (RRA) July 16, 1985 0:07:45 am PDT
SparseMemory supports a full 32-bit address space, although it uses a representation that assumes that the populated portion of the addess space is rather small. The representation is reasonably efficient in cases where if one word is present, then the next word has a high probability of being present. The implementation is not monitored, so concurrent access may produce undesirable results.
DIRECTORY
DragOpsCross USING [Word, wordsPerPage, ZerosWord];
SparseMemory: CEDAR DEFINITIONS
= BEGIN
Types
IndexInPage: TYPE = [0..DragOpsCross.wordsPerPage);
IndexInBank: TYPE = [0..4*(16384/DragOpsCross.wordsPerPage) );
IndexInSpace: TYPE = IndexInPage;
IndexInBase: TYPE = IndexInBank;
Word: TYPE = DragOpsCross.Word;
ZerosWord: Word = DragOpsCross.ZerosWord;
WordParts: TYPE = MACHINE DEPENDENT RECORD [
from highest bits to lowest bits, using DragOps.Word bit order
inBase: IndexInBase,
inSpace: IndexInSpace,
inBank: IndexInBank,
inPage: IndexInPage];
Base: TYPE = REF BaseRep;
BaseRep: TYPE = ARRAY IndexInBase OF Space;
Space: TYPE = REF SpaceRep;
SpaceRep: TYPE = ARRAY IndexInSpace OF Bank;
Bank: TYPE = REF BankRep;
BankRep: TYPE = ARRAY IndexInBank OF Page;
Page: TYPE = REF PageRep;
PageRep: TYPE = RECORD [
props: REF ← NIL, -- for attachment of user data
words: ARRAY IndexInPage OF Word
];
Exports
NoMore: ERROR;
Create: PROC RETURNS [Base];
Creates a new, empty, array of words. All pages are initially not present.
base = Create[] => NOT Probe[base, index]
Fetch: PROC [base: Base, index: Word, default: Word ← ZerosWord] RETURNS [Word];
Fetches a word from the given memory, returning the default if the page containing the word is not present.
NOT Probe[base, index] => Fetch[base, index, default] = default
FetchWithCode: PROC [base: Base, index: Word] RETURNS [word: Word, present: BOOL];
Fetches a word from the given memory, present = FALSE if the page was never initialized.
NOT Probe[base, index] => FetchWithCode[base, index, default] = [0, FALSE]
FetchPage: PROC [base: Base, index: Word] RETURNS [Page];
Returns the page containing the given word index. Will return NIL if the page is not present.
Store: PROC [base: Base, index: Word, new: Word ← ZerosWord];
Stores a word into the given memory. If this is the first store into a page, the other words in the page are made present and are initializaed to zeros.
base' AFTER Store[base, index, new] & base # NIL
FetchPage[base', index] # NIL
FetchPage[base', x] # FetchPage[base', index] =>
Probe[base', x] = Probe[base, index]
FetchPage[base', x] = FetchPage[base', index] & x # index & FetchPage[base, x] = NIL
=> Fetch[base', x, default] = 0
Probe: PROC [base: Base, index: Word] RETURNS [present: BOOL];
Tests for the presence of a page initialized by a previous Store.
base = NIL => NOT Probe[base, index]
NextPresent: PROC [base: Base, start: Word] RETURNS [Word];
Scans for the next index with a present word. For the arithmetic in this definition we assume that SUCC[start] == CardToWord[SUCC[WordToCard[start]]].
NextPresent[base, start] = ERROR NoMore & start <= x < LAST[Word]=>
NOT Probe[base, x]
NextPresent[base, start] = index & start <= x < index =>
NOT Probe[base, x]
NextPresent[base, start] = index => Probe[base, index]
END.