DIRECTORY DBCommon, DBEnvironment; DBStorageVec: CEDAR DEFINITIONS IMPORTS DBEnvironment = BEGIN MaxWordsPerPage: CARDINAL = 512; RestOfWord: CARDINAL = 128; LengthField: TYPE = CARDINAL [0..MaxWordsPerPage); SlotIndexField: TYPE = CARDINAL [0..RestOfWord); SlotTypeField: TYPE = CARDINAL [0..RestOfWord); VecPage: TYPE = PRIVATE MACHINE DEPENDENT RECORD[ tag: CARDINAL [0..377B], unused: CARDINAL [0..1] _ NULL, highSlot: SlotIndexField, nFreeSlots: SlotIndexField, nWordsInFreeVecs: LengthField ];--VecPage Slot: TYPE = PRIVATE MACHINE DEPENDENT RECORD[ type: SlotTypeField, vecOffset: LengthField ];--Slot FreeType: SlotTypeField = 0; UnFreeType: SlotTypeField = 177B; VecHeader: TYPE = PRIVATE MACHINE DEPENDENT RECORD[ slotIndex: SlotIndexField, length: PUBLIC LengthField ];--VecHeader InitializeVecPage: PROC[p: LONG POINTER TO VecPage, pageTag: CARDINAL]; TagOfPage: PROC[p: LONG POINTER TO VecPage] RETURNS[--pageTag-- CARDINAL] = TRUSTED INLINE BEGIN RETURN[p.tag]; END;--TagOfPage AllocVec: PROC[p: LONG POINTER TO VecPage, nWords: CARDINAL] RETURNS[--slotIndex-- CARDINAL, --success-- BOOLEAN]; WordsInLargestAllocableVec: PROC[p: LONG POINTER TO VecPage] RETURNS[--nWords-- CARDINAL]; FreeVec: PROC[p: LONG POINTER TO VecPage, slotIndex: CARDINAL]; ModifyVec: PROC[ p: LONG POINTER TO VecPage, slotIndex: CARDINAL, deltaWords: INTEGER, preserveContents: BOOLEAN] RETURNS[--success-- BOOLEAN]; VecOfSlot: PROC[p: LONG POINTER TO VecPage, slotIndex: CARDINAL] RETURNS[LONG POINTER TO VecHeader] = TRUSTED INLINE BEGIN IF slotIndex=0 OR slotIndex>HighSlotIndexOfPage[p] THEN ERROR DBEnvironment.InternalError -- BadSlotIndex --; RETURN[LOOPHOLE[p + LOOPHOLE[p + (DBCommon.WordsPerPage - SIZE[Slot]) - slotIndex*SIZE[Slot], LONG POINTER TO Slot].vecOffset, LONG POINTER TO VecHeader]]; END;--VecOfSlot LengthOfVec: PROC[v: LONG POINTER TO VecHeader] RETURNS[CARDINAL] = TRUSTED INLINE BEGIN RETURN[v.length]; END;--LengthOfVec TypeOfSlot: PROC[p: LONG POINTER TO VecPage, slotIndex: CARDINAL] RETURNS[CARDINAL] = TRUSTED INLINE BEGIN IF slotIndex=0 OR slotIndex>HighSlotIndexOfPage[p] THEN ERROR DBEnvironment.InternalError -- BadSlotIndex --; RETURN[LOOPHOLE[p + (DBCommon.WordsPerPage - SIZE[Slot]) - slotIndex*SIZE[Slot], LONG POINTER TO Slot].type]; END;--TypeOfSlot SetTypeOfSlot: PROC[ p: LONG POINTER TO VecPage, slotIndex: CARDINAL, newType: CARDINAL] = TRUSTED INLINE BEGIN IF slotIndex=0 OR slotIndex>HighSlotIndexOfPage[p] THEN ERROR DBEnvironment.InternalError -- BadSlotIndex --; LOOPHOLE[p + (DBCommon.WordsPerPage - SIZE[Slot]) - slotIndex*SIZE[Slot], LONG POINTER TO Slot].type _ newType; END;--SetTypeOfSlot WordsLeftOnPage: PROC[p: LONG POINTER TO VecPage] RETURNS[CARDINAL] = TRUSTED INLINE BEGIN RETURN[p.nWordsInFreeVecs - SIZE[VecHeader]]; END;--WordsLeftOnPage HighSlotIndexOfPage: PROC[p: LONG POINTER TO VecPage] RETURNS[CARDINAL] = TRUSTED INLINE BEGIN RETURN[p.highSlot]; END;--HighSlotIndexOfPage CheckVecPage: PROC[p: LONG POINTER TO VecPage, pageTag: CARDINAL]; IndexToSlot: PRIVATE PROC[p: LONG POINTER TO VecPage, slotIndex: CARDINAL] RETURNS[LONG POINTER TO Slot] = TRUSTED INLINE BEGIN RETURN[LOOPHOLE[p + (DBCommon.WordsPerPage - SIZE[Slot]) - slotIndex*SIZE[Slot], LONG POINTER TO Slot]]; END;--IndexToSlot IndexToOffset: PRIVATE PROC[slotIndex: CARDINAL] RETURNS[CARDINAL] = TRUSTED INLINE BEGIN RETURN[DBCommon.WordsPerPage - SIZE[Slot] - slotIndex*SIZE[Slot]]; END;--IndexToOffset END. -- DBStorageVec Created by MBrown on February 15, 1980 2:47 PM Changed by MBrown on February 15, 1980 10:31 PM Changed by MBrown on February 17, 1980 6:46 PM Changed by MBrown on February 17, 1980 8:22 PM Changed by MBrown on February 17, 1980 10:21 PM Changed by MBrown on February 24, 1980 11:37 AM --to VecPage, and "LONG POINTER --TO Page--" to "LONG POINTER TO VecPage", to gain Changed by MBrown on February 24, 1980 1:01 PM Changed by MBrown on August 22, 1980 4:21 PM Changed by MBrown on September 26, 1980 11:21 AM Changed by Willie-Sue on February 15, 1985 ÄFile DBStorageVec.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Last edited by: MBrown on September 26, 1980 11:18 AM Cattell on January 14, 1983 2:10 pm Willie-Sue, February 15, 1985 11:15:44 am PST This interface contains types and procedures relating to the vec-level structure of pages (tuple pages and overflow pages). Most of the types are PRIVATE; clients are expected to use a purely procedural interface. Types There seems to be no advantage in having these vary with the true pagesize. These structures will need to be re-thought for 1024 word pages (which may be too large for our expected applications). Page type, on all pages in the system. Largest slot index that is valid on this page. Number of slots in [1..highSlot] that are unused. Number of words in free vecs on this page. Header of a page that is formatted to hold vecs. There are three possible values for tag: DBStoragePagetags.Tuple, .SystemTuple, and .OverflowTuple. "Type" of object stored in vec. Page-relative pointer to a vec. A Slot is a typed pointer to a vec. The types are irrelevant inside of this interface, with the following exceptions: The slot is free; ignore vecOffset. The slot is not free. This is the type given to newly-created slots by AllocVec. Slot index of slot that points here, or FreeSlotIndex for free vecs. Number of words in vec, including vec header. Information located at the beginning of each vec. A pointer to a vec points to the header, so the header length must be added to get the first word of data. Procedures Creates an empty page in page p of the cache, ready to store vecs using the procedures below. The new page has tag = pageTag. Returns the page tag of page p. We intend that a page's tag be checked before any of the procedures below are called on that page. Makes a new vec of total length nWords (including vec header), a slot to hold it, and returns the index of the slot. If ~success, then the call failed for lack of space, and slotIndex is garbage. Returns the largest value nWords such that AllocVec[p, nWords] is guaranteed to succeed. Frees the vec held in the slot at slotIndex, and the slot also. Changes the length of the vec at slotIndex by deltaWords. If deltaWords<0, the final deltaWords words of data in the vec are lost forever. If deltaWords>0 and preserveContents, then the old contents of the vec will be found in the initial words of the new vec; the new words are not initialized. If ~success, then the call failed for lack of space. (The call cannot fail if deltaWords<0). Returns a LONG POINTER to the VecHeader of the vec stored in the slotIndex-th slot of page p. The pointer may be used for data retrieval from the vec, and to find the vec's length (below). When retrieving data, the header must be skipped explicitly. Returns the number of words in vec v, including the header. Returns the type code of the slotIndex-th slot of page p. Makes the type code of the slotIndex-th slot of page p be newType. Partially obsoleted by WordsInLargestAllocableVec. Returns the number of words available on the page for vec allocation. Note that slots are also allocated from this space, so the total number of words required to construct a vec of nWords words may be nWords + SIZE[Slot]. Returns the highest slot index valid on this page. This is to be used for iterations that wish to look at each slot on a page. Such an iteration runs through [1..HighSlotIndexOfPage[p]], and must ignore all slots with type = FreeType. Verifies that the internal structure of the page is consistent, and that it has tag = pageTag. Module History Reduced the size of the interface by a factor of 2 (hiding more structure inside). Added CheckVecPage to interface. (This can't be written without SHARING the interface). Fixed bug in slotIndex -> slot computation; added PRIVATE IndexToSlot to localize this information. Renamed HighSlotOFPage -> HighSlotIndexOfPage. Added PRIVATE IndexToOffset for use in CompactPage. Made length field of VecHeader PUBLIC. Added WordsLeftOnPage, and stopped having AllocVec, FreeVec, and ModifyVec return the number of words left. Changed VecPageHeader more type checking. Compiler had fatal error (no intelligible message) while compiling StorageVecImpl. Fix was to make TypeOfSlot and other inlines NOT call IndexToSlot, instead manually substituting the body. This apparently saves space in pass 5. Added WordsInLargestAllocableVec to interface. Used exception BadSlotIndex from new DBException. made Cedar, added tioga formatting Êô˜šœ™Jšœ Ïmœ1™<—šœ™Jšœ&™&Jšœ#™#—Jšœ-™-J˜J˜šÏk ˜ J˜ J˜J˜J˜—šœžœž˜Jšžœž˜JšœS™SJšœO™OJšœ2™2J˜J˜Jšœ™J˜Jšœžœ˜ Jšœžœ˜Jšœ žœžœ˜2Jšœžœžœ˜0šœžœžœ˜/JšœQ™QJšœQ™QJšœ™J˜J˜—šœ žœžœžœž œžœ˜1šœžœ˜Jšœ&™&—Jšœžœ žœ˜˜Jšœ.™.—˜Jšœ1™1—˜Jšœ*™*—šœÏc ˜JšœQ™QJšœC™C——J˜J˜šœžœžœžœž œžœ˜.˜Jšœ™—˜Jšœ™—šœŸ˜JšœL™LJšœ)™)J˜——˜Jšœ#™#—˜!JšœD™DJšœ™J˜J˜—šœžœžœžœž œžœ˜3˜JšœD™D—šœžœ˜Jšœ-™-—šœŸ˜ JšœO™OJšœM™M——Ihead1šœ ™ J˜šÏnœžœžœžœžœžœ˜GJšœK™KJšœ2™2J˜—š œžœžœžœžœ ˜+JšžœŸœžœžœžœž˜4JšœG™Gšœ<™