SparseMemoryImpl.mesa
Copyright © 1984, 1985 by Xerox Corporation. All rights reserved.
Russ Atkinson (RRA) July 16, 1985 0:08:43 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, ZerosWord],
SparseMemory;
SparseMemoryImpl: CEDAR PROGRAM
EXPORTS SparseMemory
SHARES SparseMemory
= BEGIN OPEN SparseMemory;
Types
Word: TYPE = DragOpsCross.Word;
ZerosWord: Word = DragOpsCross.ZerosWord;
Exports
NoMore: PUBLIC ERROR = CODE;
Create: PUBLIC PROC RETURNS [Base] = {
Creates a new, empty, array of words. All words are initially not present.
base = Create[] => NOT Probe[base, index]
RETURN [NEW[BaseRep ← ALL[NIL]]];
};
Fetch: PUBLIC PROC [base: Base, index: Word, default: Word ← ZerosWord] RETURNS [Word] = {
Fetches a word from the given memory, returning the default if the word is not present.
NOT Probe[base, index] => Fetch[base, index, default] = default
parts: WordParts = LOOPHOLE[index];
IF base # NIL THEN {
space: Space = base[parts.inBase];
IF space # NIL THEN {
bank: Bank = space[parts.inSpace];
IF bank # NIL THEN {
page: Page = bank[parts.inBank];
IF page # NIL THEN RETURN [page.words[parts.inPage]];
};
};
};
RETURN [default];
};
FetchWithCode: PUBLIC PROC [base: Base, index: Word] RETURNS [word: Word, present: BOOL] = {
Fetches a word from the given memory, returning the default if the word is not present.
NOT Probe[base, index] => Fetch[base, index, default] = default
parts: WordParts = LOOPHOLE[index];
IF base # NIL THEN {
space: Space = base[parts.inBase];
IF space # NIL THEN {
bank: Bank = space[parts.inSpace];
IF bank # NIL THEN {
page: Page = bank[parts.inBank];
IF page # NIL THEN RETURN [page.words[parts.inPage], TRUE];
};
};
};
RETURN [ZerosWord, FALSE];
};
FetchPage: PUBLIC PROC [base: Base, index: Word] RETURNS [Page] = {
Returns the page containing the given word index. Will return NIL if the page is not present.
parts: WordParts = LOOPHOLE[index];
IF base # NIL THEN {
space: Space = base[parts.inBase];
IF space # NIL THEN {
bank: Bank = space[parts.inSpace];
IF bank # NIL THEN RETURN [bank[parts.inBank]];
};
};
RETURN [NIL];
};
Store: PUBLIC PROC [base: Base, index: Word, new: Word ← ZerosWord] = {
Stores a word into the given memory.
base' AFTER Store[base, index, new]
x # index => Fetch[base', x, default] = Fetch[base, index, default]
x # index => Probe[base', x] = Probe[base, index]
base # NIL => Fetch[base', index, default] = new
base # NIL => Probe[base', index]
parts: WordParts = LOOPHOLE[index];
IF base # NIL THEN {
space: Space ← base[parts.inBase];
IF space = NIL THEN {space ← base[parts.inBase] ← NEW[SpaceRep ← ALL[NIL]]};
{bank: Bank ← space[parts.inSpace];
IF bank = NIL THEN {bank ← space[parts.inSpace] ← NEW[BankRep ← ALL[NIL]]};
{page: Page ← bank[parts.inBank];
IF page = NIL THEN {
page ← bank[parts.inBank] ← NEW[PageRep ← [NIL, ALL[ZerosWord]]]};
page.words[parts.inPage] ← new;
};
};
};
};
Probe: PUBLIC PROC [base: Base, index: Word] RETURNS [present: BOOL] = {
Tests for the presence of a word initialized by a previous Store.
base = NIL => NOT Probe[base, index]
parts: WordParts = LOOPHOLE[index];
IF base # NIL THEN {
space: Space = base[parts.inBase];
IF space # NIL THEN {
bank: Bank = space[parts.inSpace];
IF bank # NIL THEN
IF bank[parts.inBank] # NIL THEN RETURN [TRUE];
};
};
RETURN [FALSE];
};
NextPresent: PUBLIC 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]
parts: WordParts ← LOOPHOLE[start];
IF base # NIL THEN
FOR spaceIndex: IndexInBase IN [parts.inBase..LAST[IndexInBase]] DO
space: Space = base[spaceIndex];
IF space # NIL THEN
FOR bankIndex: IndexInSpace IN [parts.inSpace..LAST[IndexInSpace]] DO
bank: Bank = space[bankIndex];
IF bank # NIL THEN
FOR pageIndex: IndexInBank IN [parts.inBank..LAST[IndexInBank]] DO
IF bank[pageIndex] # NIL THEN
RETURN [LOOPHOLE[
WordParts[spaceIndex, bankIndex, pageIndex, parts.inPage]
]];
ENDLOOP;
parts.inBank ← parts.inPage ← 0;
ENDLOOP;
parts.inSpace ← parts.inBank ← parts.inPage ← 0;
ENDLOOP;
ERROR NoMore;
};
END.