DIRECTORYDragOpsCross USING [Word, wordsPerPage, ZerosWord];SparseMemory: CEDAR DEFINITIONS= BEGIN OPEN DragOpsCross;IndexInPage: TYPE = [0..wordsPerPage);IndexInBank: TYPE = [0..4*(16384/wordsPerPage) );IndexInSpace: TYPE = IndexInPage;IndexInBase: TYPE = IndexInBank;WordParts: TYPE = MACHINE DEPENDENT RECORD [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];NoMore: ERROR;Create: PROC RETURNS [Base];Fetch: PROC [base: Base, index: Word, default: Word _ ZerosWord] RETURNS [Word];FetchWithCode: PROC [base: Base, index: Word] RETURNS [word: Word, present: BOOL];FetchPage: PROC [base: Base, index: Word] RETURNS [Page];Store: PROC [base: Base, index: Word, new: Word _ ZerosWord];Probe: PROC [base: Base, index: Word] RETURNS [present: BOOL];NextPresent: PROC [base: Base, start: Word] RETURNS [Word];END.   &  SparseMemory.mesaCopyright c 1984, 1985, 1986 by Xerox Corporation.  All rights reserved.Russ Atkinson (RRA) September 10, 1986 11:12:51 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.Typesfrom highest bits to lowest bits, using DragOps.Word bit orderExportsCreates a new, empty, array of words.  All pages are initially not present.base = Create[] => NOT Probe[base, index]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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]Returns the page containing the given word index.  Will return NIL if the page is not present.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Tests for the presence of a page 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]ÊU  ˜ codešœ™Kšœ
Ïmœ=™HK™6—˜ KšœŒ™ŒK˜ šÏk	˜	Kšœžœ!˜3K˜ ——šÏnœžœž˜Kšœžœž˜K˜ —šœ™K˜ šœžœ˜&Kšœžœ ˜1Kšœžœ˜!Kšœžœ˜ K˜ —š	œžœžœž	œžœ˜,Kšœ>™>Kšœ˜Kšœ˜Kšœ˜Kšœ˜K˜ —Kšœžœžœ	˜Kšœ	žœžœžœ˜+K˜ Kšœžœžœ
˜Kšœ
žœžœžœ˜,K˜ Kšœžœžœ	˜Kšœ	žœžœžœ˜*K˜ Kšœžœžœ	˜šœ	žœžœ˜KšœžœžœÏc˜1Kšœžœžœ˜ Kšœ˜—K˜ —šœ™K˜ šœžœ˜K˜ —šŸœžœžœ˜šœK™KKšœžœ™)—K˜ —šŸœžœ6žœ˜Pšœk™kKšžœ<™?—K˜ —šŸœžœžœžœ˜Ršœ0žœ#™XKšžœAžœ™J—K˜ —šŸ	œžœžœ˜9Kšœ?žœ™^K˜ —šŸœžœ2˜=šœ™™™šœžœ"ž™0Kšœž™šœ0™0Kšœ$™$—šœQž™TKšœ™—K™ ———šŸœžœžœžœ˜>šœA™AKšœžœžœ™$—K˜ —šŸœžœžœ˜;šœdžœžœ™—šœžœžœ™CKšžœ™—šœ9™9Kšžœ™—Kšœ6™6—K˜ ——Kšžœ˜˜ K˜ —K˜ — …—    Ö  Q  