DIRECTORY DragOpsCross USING [Word, ZerosWord], SparseMemory USING [Bank, BankRep, Base, BaseRep, IndexInBank, IndexInBase, IndexInSpace, Page, PageRep, Space, SpaceRep, WordParts]; SparseMemoryImpl: CEDAR PROGRAM EXPORTS SparseMemory SHARES SparseMemory = BEGIN OPEN DragOpsCross, SparseMemory; NoMore: PUBLIC ERROR = CODE; Create: PUBLIC PROC RETURNS [Base] = { RETURN [NEW[BaseRep _ ALL[NIL]]]; }; Fetch: PUBLIC PROC [base: Base, index: Word, default: Word _ ZerosWord] RETURNS [Word] = { 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] = { 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] = { 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] = { 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] = { 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] = { 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. $SparseMemoryImpl.mesa Copyright c 1984, 1985, 1986 by Xerox Corporation. All rights reserved. Russ Atkinson (RRA) September 10, 1986 11:58:45 pm 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. Exports Creates a new, empty, array of words. All words are initially not present. base = Create[] => NOT Probe[base, index] 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 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 Returns the page containing the given word index. Will return NIL if the page is not present. 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] Tests for the presence of a word initialized by a previous Store. base = NIL => NOT Probe[base, index] 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] ΚΟ˜codešœ™Kšœ Οmœ=™HK™6—˜KšœŒ™ŒK™šΟk ˜ Kšœ žœ˜%Kšœ žœs˜…K˜——šΟnœžœž˜Kšžœ ˜Kšžœ ˜Kšœžœžœ˜(K˜—šœ™K˜šœžœžœžœ˜K˜—šŸœž œžœ ˜&šœK™KKšœžœ™)—Kšžœžœ žœžœ˜!K˜K˜—šŸœž œ6žœ ˜ZšœW™WKšžœ<™?—Kšœžœ˜#šžœžœžœ˜Kšœ"˜"šžœ žœžœ˜Kšœ"˜"šžœžœžœ˜Kšœ ˜ Kšžœžœžœžœ˜5K˜—K˜—K˜—Kšžœ ˜K˜K˜—šŸ œž œžœžœ˜\šœW™WKšžœ<™?—Kšœžœ˜#šžœžœžœ˜Kšœ"˜"šžœ žœžœ˜Kšœ"˜"šžœžœžœ˜Kšœ ˜ Kš žœžœžœžœžœ˜;K˜—K˜—K˜—Kšžœ žœ˜K˜K˜—šŸ œž œžœ ˜CKšœ?žœ™^Kšœžœ˜#šžœžœžœ˜Kšœ"˜"šžœ žœžœ˜Kšœ"˜"Kšžœžœžœžœ˜/K˜—K˜—Kšžœžœ˜ K˜K˜—šŸœžœžœ5˜Gšœ$™$šœžœ™#KšœC™CKšœ1™1Kšœžœ&™0Kšœžœ™!——Kšœžœ˜#šžœžœžœ˜Kšœ"˜"Kš žœ žœžœžœ žœžœ˜Lšœ#˜#Kš žœžœžœ žœ žœžœ˜Kšœ!˜!šžœžœžœ˜Kšœžœ žœžœ˜B—Kšœ˜K˜—K˜—K˜—K˜K˜—šŸœž œžœ žœ˜HšœA™AKšœžœžœ™$—Kšœžœ˜#šžœžœžœ˜Kšœ"˜"šžœ žœžœ˜Kšœ"˜"šžœžœž˜Kš žœžœžœžœžœ˜/—K˜—K˜—Kšžœžœ˜K˜K˜—šŸ œžœžœžœ ˜Ešœdžœžœ™—šœžœžœ™CKšžœ™—šœ9™9Kšžœ™—Kšœ6™6—Kšœžœ˜#šžœžœž˜šžœžœžœž˜CKšœ ˜ šžœ žœž˜šžœžœžœž˜EKšœ˜šžœžœž˜šžœžœžœž˜Bšžœžœž˜šžœžœ˜Kšœ9˜9Kšœ˜——Kšžœ˜——Kšœ ˜ Kšžœ˜——Kšœ0˜0Kšžœ˜——Kšžœ˜ K˜K˜——Kšžœ˜˜K˜——…— ¨›