-- 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.
(1792)\f8 283f0 2126f8 2f0 3471f8 62f0
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.