DIRECTORY DragOpsCross USING [Word, wordsPerPage, ZerosWord]; SparseMemory: CEDAR DEFINITIONS = BEGIN 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 [ 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 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. 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] Κa˜codešœ™Kšœ Οmœ7™BK™0—K˜KšœŒ™ŒK˜šΟk ˜ Kšœ žœ!˜3K˜—šœžœž ˜Kšœž˜K˜—šœ™K˜šœ žœ"˜3Kšœ žœ-˜>Kšœžœ˜!Kšœ žœ˜ —šœžœ˜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˜—šΟnœžœžœ˜šœ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˜—…—&‘