[Indigo]<Cedar5.3>Cypress>DBStorageVec.mesa!1

-- File DBStorageVec.mesa
-- Last edited by:
-- MBrown on September 26, 1980 11:18 AM
-- Cattell on January 14, 1983 2:10 pm

DIRECTORY
DBCommon,
DBEnvironment;

DBStorageVec: DEFINITIONS
IMPORTS DBEnvironment = BEGIN
-- 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

MaxWordsPerPage: CARDINAL = 512;
RestOfWord: CARDINAL = 128;
LengthField: TYPE = CARDINAL [0..MaxWordsPerPage);
SlotIndexField: TYPE = CARDINAL [0..RestOfWord);
SlotTypeField: TYPE = CARDINAL [0..RestOfWord);
-- 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).

VecPage: TYPE = PRIVATE MACHINE DEPENDENT RECORD[
tag: CARDINAL [0..377B],
-- Page type, on all pages in the system.
unused: CARDINAL [0..1] ← NULL,
highSlot: SlotIndexField,
-- Largest slot index that is valid on this page.
nFreeSlots: SlotIndexField,
-- Number of slots in [1..highSlot] that are unused.
nWordsInFreeVecs: LengthField
-- Number of words in free vecs on this page.
];--VecPage
-- Header of a page that is formatted to hold vecs. There are three possible values
--for tag: DBStoragePagetags.Tuple, .SystemTuple, and .OverflowTuple.

Slot: TYPE = PRIVATE MACHINE DEPENDENT RECORD[
type: SlotTypeField,
-- "Type" of object stored in vec.
vecOffset: LengthField
-- Page-relative pointer to a vec.
];--Slot
-- A Slot is a typed pointer to a vec. The types are irrelevant inside of this
--interface, with the following exceptions:

FreeType: SlotTypeField = 0;
-- The slot is free; ignore vecOffset.
UnFreeType: SlotTypeField = 177B;
-- The slot is not free. This is the type given to newly-created slots
--by AllocVec.

VecHeader: TYPE = PRIVATE MACHINE DEPENDENT RECORD[
slotIndex: SlotIndexField,
-- Slot index of slot that points here, or FreeSlotIndex for free vecs.
length: PUBLIC LengthField
-- Number of words in vec, including vec header.
];--VecHeader
-- 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

InitializeVecPage: PROCEDURE[p: LONG POINTER TO VecPage, pageTag: CARDINAL];
-- Creates an empty page in page p of the cache, ready to store vecs using the
--procedures below. The new page has tag = pageTag.

TagOfPage: PROCEDURE[p: LONG POINTER TO VecPage] RETURNS[--pageTag-- CARDINAL] = INLINE BEGIN
-- 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.
RETURN[p.tag];
END;--TagOfPage

AllocVec: PROCEDURE[p: LONG POINTER TO VecPage, nWords: CARDINAL]
RETURNS[--slotIndex-- CARDINAL, --success-- BOOLEAN];
-- 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.

WordsInLargestAllocableVec: PROCEDURE[p: LONG POINTER TO VecPage]
RETURNS[--nWords-- CARDINAL];
-- Returns the largest value nWords such that AllocVec[p, nWords] is guaranteed to succeed.

FreeVec: PROCEDURE[p: LONG POINTER TO VecPage, slotIndex: CARDINAL];
-- Frees the vec held in the slot at slotIndex, and the slot also.

ModifyVec: PROCEDURE
[p: LONG POINTER TO VecPage, slotIndex: CARDINAL, deltaWords: INTEGER, preserveContents: BOOLEAN]
RETURNS[--success-- BOOLEAN];
-- 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).

VecOfSlot: PROCEDURE[p: LONG POINTER TO VecPage, slotIndex: CARDINAL]
RETURNS[LONG POINTER TO VecHeader] = INLINE BEGIN
-- 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.
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: PROCEDURE[v: LONG POINTER TO VecHeader] RETURNS[CARDINAL] = INLINE BEGIN
-- Returns the number of words in vec v, including the header.
RETURN[v.length];
END;--LengthOfVec

TypeOfSlot: PROCEDURE[p: LONG POINTER TO VecPage, slotIndex: CARDINAL] RETURNS[CARDINAL] =
INLINE BEGIN
-- Returns the type code of the slotIndex-th slot of page p.
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: PROCEDURE[p: LONG POINTER TO VecPage, slotIndex: CARDINAL, newType: CARDINAL] =
INLINE BEGIN
-- Makes the type code of the slotIndex-th slot of page p be newType.
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: PROCEDURE[p: LONG POINTER TO VecPage] RETURNS[CARDINAL] = INLINE BEGIN
-- 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].
RETURN[p.nWordsInFreeVecs - SIZE[VecHeader]];
END;--WordsLeftOnPage

HighSlotIndexOfPage: PROCEDURE[p: LONG POINTER TO VecPage] RETURNS[CARDINAL] = INLINE BEGIN
-- 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.
RETURN[p.highSlot];
END;--HighSlotIndexOfPage

CheckVecPage: PROCEDURE[p: LONG POINTER TO VecPage, pageTag: CARDINAL];
-- Verifies that the internal structure of the page is consistent, and that
--it has tag = pageTag.

IndexToSlot: PRIVATE PROCEDURE[p: LONG POINTER TO VecPage, slotIndex: CARDINAL]
RETURNS[LONG POINTER TO Slot] = INLINE BEGIN
RETURN[LOOPHOLE[p + (DBCommon.WordsPerPage - SIZE[Slot]) - slotIndex*SIZE[Slot],
LONG POINTER TO Slot]];
END;--IndexToSlot

IndexToOffset: PRIVATE PROCEDURE[slotIndex: CARDINAL] RETURNS[CARDINAL] = INLINE BEGIN
RETURN[DBCommon.WordsPerPage - SIZE[Slot] - slotIndex*SIZE[Slot]];
END;--IndexToOffset

END.--DBStorageVec

-- Module History

Created by MBrown on February 15, 1980 2:47 PM

Changed by MBrown on February 15, 1980 10:31 PM
-- Reduced the size of the interface by a factor of 2 (hiding more structure inside).

Changed by MBrown on February 17, 1980 6:46 PM
-- Added CheckVecPage to interface. (This can’t be written without SHARING the interface).

Changed by MBrown on February 17, 1980 8:22 PM
-- Fixed bug in slotIndex -> slot computation; added PRIVATE IndexToSlot to localize this
--information.

Changed by MBrown on February 17, 1980 10:21 PM
-- Renamed HighSlotOFPage -> HighSlotIndexOfPage. Added PRIVATE IndexToOffset
--for use in CompactPage.