File DBStorageVec.mesa
Copyright © 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
DIRECTORY
DBCommon,
DBEnvironment;
DBStorageVec:
CEDAR
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:
PROC[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:
PROC[p:
LONG
POINTER
TO VecPage]
RETURNS[--pageTag-- CARDINAL] = TRUSTED 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:
PROC[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:
PROC[p:
LONG
POINTER
TO VecPage]
RETURNS[
--nWords--
CARDINAL];
Returns the largest value nWords such that AllocVec[p, nWords] is guaranteed to succeed.
FreeVec:
PROC[p:
LONG
POINTER
TO VecPage, slotIndex:
CARDINAL];
Frees the vec held in the slot at slotIndex, and the slot also.
ModifyVec:
PROC[
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:
PROC[p:
LONG
POINTER
TO VecPage, slotIndex:
CARDINAL]
RETURNS[
LONG
POINTER
TO VecHeader] =
TRUSTED
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:
PROC[v:
LONG
POINTER
TO VecHeader]
RETURNS[CARDINAL] = TRUSTED INLINE BEGIN
Returns the number of words in vec v, including the header.
RETURN[v.length];
END;--LengthOfVec
TypeOfSlot:
PROC[p:
LONG
POINTER
TO VecPage, slotIndex:
CARDINAL]
RETURNS[
CARDINAL] =
TRUSTED
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:
PROC[
p: LONG POINTER TO VecPage,
slotIndex: CARDINAL,
newType:
CARDINAL] =
TRUSTED
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:
PROC[p:
LONG
POINTER
TO VecPage]
RETURNS[CARDINAL] = TRUSTED 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:
PROC[p:
LONG
POINTER
TO VecPage]
RETURNS[CARDINAL] = TRUSTED 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:
PROC[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
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
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.
Changed by MBrown on February 24, 1980 11:37 AM
Made length field of VecHeader PUBLIC. Added WordsLeftOnPage, and stopped having
AllocVec, FreeVec, and ModifyVec return the number of words left. Changed VecPageHeader
--to VecPage, and "LONG POINTER --TO Page--" to "LONG POINTER TO VecPage", to gain
more type checking.
Changed by MBrown on February 24, 1980 1:01 PM
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.
Changed by MBrown on August 22, 1980 4:21 PM
Added WordsInLargestAllocableVec to interface.
Changed by MBrown on September 26, 1980 11:21 AM
Used exception BadSlotIndex from new DBException.
Changed by Willie-Sue on February 15, 1985
made Cedar, added tioga formatting