DIRECTORY
DBCommon USING[WordsPerPage, TIDSlotMask, InternalError],
DBStats,
DBStoragePage,
PrincOpsUtils;

DBStoragePageImpl: CEDAR PROGRAM
IMPORTS DBCommon, DBStats, DBStoragePage, I: PrincOpsUtils
EXPORTS DBStoragePage
SHARES DBStoragePage

= BEGIN

VecPage: TYPE = DBStoragePage.VecPage;
Slot: TYPE = DBStoragePage.Slot;
VecHeader: TYPE = DBStoragePage.VecHeader;



FreeSlotIndex: DBStoragePage.SlotIndexField = 0;
NonsenseSlotIndex: CARDINAL = LAST[CARDINAL];


ValidateInput: BOOL = TRUE;
CheckPage: BOOL = TRUE;
ExhaustivelyCheckPage: BOOL = FALSE;




VecOfOffset: PROC[p: LONG POINTER TO VecPage, offset: CARDINAL]
RETURNS[LONG POINTER TO VecHeader] = TRUSTED INLINE BEGIN
RETURN[LOOPHOLE[p+offset, LONG POINTER TO VecHeader]];
END;--VecOfOffset

FreeVecOffset: PROC[p: LONG POINTER TO VecPage] RETURNS[CARDINAL] = TRUSTED INLINE BEGIN
RETURN[LOOPHOLE[p + (DBCommon.WordsPerPage-SIZE[Slot]), LONG POINTER TO Slot].vecOffset];
END;--FreeVecOffset 

FreeVecPtr: PROC[p: LONG POINTER TO VecPage] RETURNS[LONG POINTER TO VecHeader] = TRUSTED INLINE BEGIN
RETURN[VecOfOffset[p, FreeVecOffset[p]]];
END;--FreeVecPtr 

InitializeVecPage: PUBLIC PROC[p: LONG POINTER TO VecPage, pageTag: CARDINAL] = TRUSTED BEGIN
WordsFree: CARDINAL = DBCommon.WordsPerPage - SIZE[VecPage] - SIZE[Slot];
DBStats.Inc[StorageInitVecPage];
p^ _ VecPage[tag: pageTag, highSlot: 0, nFreeSlots: 0, nWordsInFreeVecs: WordsFree];
LOOPHOLE[p+SIZE[VecPage], LONG POINTER TO VecHeader]^ _ 
VecHeader[slotIndex: FreeSlotIndex, length: WordsFree];
LOOPHOLE[p+DBCommon.WordsPerPage-SIZE[Slot], LONG POINTER TO Slot]^ _ 
Slot[type: DBStoragePage.UnFreeType, vecOffset: SIZE[VecPage]];
END;--InitializeVecPage


CheckVecPage: PUBLIC PROC[p: LONG POINTER TO VecPage, pageTag: CARDINAL] = TRUSTED BEGIN

OPEN pageHdr: p;

Assert: PROC[condition: BOOL] = CHECKED BEGIN
IF ~condition THEN ERROR DBCommon.InternalError; -- CheckVecPageFailed
END;--Assert

DBStats.Inc[StorageCheckVecPage];
Assert[pageTag = DBStoragePage.TagOfPage[p]];
BEGIN nFreeSlots: CARDINAL _ 0;  curSlot: CARDINAL;
FOR curSlot IN [1..DBStoragePage.HighSlotIndexOfPage[p]] DO
IF DBStoragePage.TypeOfSlot[p, curSlot] = DBStoragePage.FreeType THEN
nFreeSlots  _ nFreeSlots + 1;
ENDLOOP;
Assert[nFreeSlots = pageHdr.nFreeSlots];
END;
BEGIN freeVecPtr: LONG POINTER TO VecHeader _ FreeVecPtr[p];
Assert[LOOPHOLE[p+DBCommon.WordsPerPage-SIZE[Slot], LONG POINTER TO Slot].type =
DBStoragePage.UnFreeType];
Assert[freeVecPtr.slotIndex = FreeSlotIndex];
Assert[LOOPHOLE[freeVecPtr + freeVecPtr.length, LONG POINTER TO Slot] =
DBStoragePage.IndexToSlot[p, DBStoragePage.HighSlotIndexOfPage[p]]];
END;
BEGIN freeWords: CARDINAL _ FreeVecPtr[p].length;  nonFreeVecs: CARDINAL _ 0;
curVecPtr: LONG POINTER TO VecHeader _ VecOfOffset[p, SIZE[VecPage]];
WHILE curVecPtr # FreeVecPtr[p] DO
IF curVecPtr.slotIndex = FreeSlotIndex THEN freeWords _ freeWords + curVecPtr.length
ELSE BEGIN
Assert[DBStoragePage.TypeOfSlot[p, curVecPtr.slotIndex] # DBStoragePage.FreeType];
Assert[DBStoragePage.VecOfSlot[p, curVecPtr.slotIndex] = curVecPtr];
nonFreeVecs _ nonFreeVecs + 1;
END;--IF
curVecPtr _ curVecPtr + curVecPtr.length;
ENDLOOP;
Assert[freeWords = pageHdr.nWordsInFreeVecs];
Assert[nonFreeVecs + pageHdr.nFreeSlots = pageHdr.highSlot];
END;
END;--CheckVecPage

AllocVec: PUBLIC PROC[p: LONG POINTER TO VecPage, nWords: CARDINAL] RETURNS[--slotIndex-- CARDINAL, --success-- BOOL] = TRUSTED BEGIN

OPEN pageHdr: p;
newSlotIndex: CARDINAL;
BEGIN--block for exit GOTOs
newSlotPtr: LONG POINTER TO Slot;
freeVecPtr: LONG POINTER TO VecHeader _ FreeVecPtr[p];
oldFreeVecLength: CARDINAL;
DBStats.Inc[StorageAllocVec];
IF ExhaustivelyCheckPage THEN DBStoragePage.CheckVecPage[p, pageHdr.tag];
IF ValidateInput AND (nWords < SIZE[VecHeader]) THEN
ERROR DBCommon.InternalError; -- NWordsTooSmall
IF pageHdr.nFreeSlots = 0 THEN BEGIN
IF pageHdr.nWordsInFreeVecs < nWords+SIZE[VecHeader]+SIZE[Slot] THEN
GOTO Failure;
IF pageHdr.highSlot = DBCommon.TIDSlotMask THEN GOTO Failure;
IF freeVecPtr.length = SIZE[VecHeader] THEN BEGIN
CompactPage[p];  freeVecPtr _ FreeVecPtr[p];
END;--IF
newSlotIndex _ pageHdr.highSlot _ pageHdr.highSlot + 1;
newSlotPtr _ DBStoragePage.IndexToSlot[p, newSlotIndex];
IF CheckPage AND (freeVecPtr + freeVecPtr.length-1 #
LOOPHOLE[newSlotPtr, LONG POINTER TO VecHeader]) THEN
ERROR DBCommon.InternalError; -- FreeVecSmashed
freeVecPtr.length _ freeVecPtr.length - SIZE[Slot];
IF CheckPage AND (freeVecPtr.length < SIZE[VecHeader]) THEN
ERROR DBCommon.InternalError; -- FreeVecSmashed
pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs - SIZE[Slot];  END
ELSE BEGIN--pageHdr.nFreeSlots > 0
IF pageHdr.nWordsInFreeVecs < nWords+SIZE[VecHeader] THEN GOTO Failure;
FOR newSlotIndex IN [1..pageHdr.highSlot] DO
IF DBStoragePage.TypeOfSlot[p, newSlotIndex] = DBStoragePage.FreeType THEN EXIT;
REPEAT
FINISHED => ERROR DBCommon.InternalError; -- FreeSlotsSmashed
ENDLOOP;
newSlotPtr _ DBStoragePage.IndexToSlot[p, newSlotIndex];
pageHdr.nFreeSlots _ pageHdr.nFreeSlots - 1;
END;--IF
IF freeVecPtr.length < nWords+SIZE[VecHeader] THEN BEGIN
CompactPage[p];  freeVecPtr _ FreeVecPtr[p];
END;--IF
oldFreeVecLength _ freeVecPtr.length;
IF CheckPage AND (oldFreeVecLength < nWords+SIZE[VecHeader]) THEN
ERROR DBCommon.InternalError; -- FreeVecSmashed
freeVecPtr^ _ [slotIndex: newSlotIndex, length: nWords];
newSlotPtr^ _ [type: DBStoragePage.UnFreeType, vecOffset: FreeVecOffset[p]];
freeVecPtr _ freeVecPtr + nWords;
freeVecPtr^ _ [slotIndex: FreeSlotIndex, length: oldFreeVecLength-nWords];
newSlotPtr _ LOOPHOLE[p + (DBCommon.WordsPerPage - SIZE[Slot]),
LONG POINTER TO Slot]; -- point to freeSlot
newSlotPtr.vecOffset _ newSlotPtr.vecOffset + nWords;
pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs - nWords;
GOTO Success;
EXITS
Success => BEGIN
IF ExhaustivelyCheckPage THEN DBStoragePage.CheckVecPage[p, pageHdr.tag];
RETURN[newSlotIndex, TRUE];
END;--Success
Failure => BEGIN
IF ExhaustivelyCheckPage THEN DBStoragePage.CheckVecPage[p, pageHdr.tag];
RETURN[NonsenseSlotIndex, FALSE];
END;--Failure
END;
END;--AllocVec

WordsInLargestAllocableVec: PUBLIC PROC[p: LONG POINTER TO VecPage]
RETURNS[--nWords-- CARDINAL] = TRUSTED {
OPEN pageHdr: p;
wordsOfVecSpace: CARDINAL = pageHdr.nWordsInFreeVecs - SIZE[VecHeader];
wordsNeededForSlots: CARDINAL = IF pageHdr.nFreeSlots = 0 THEN SIZE[Slot] ELSE 0;
RETURN[IF wordsOfVecSpace <= wordsNeededForSlots THEN 0 ELSE wordsOfVecSpace-wordsNeededForSlots];
};--WordsInLargestAllocableVec


FreeVec: PUBLIC PROC[p: LONG POINTER TO VecPage, slotIndex: CARDINAL] = TRUSTED BEGIN

OPEN pageHdr: p;
slotPtr: LONG POINTER TO Slot;
DBStats.Inc[StorageFreeVec];
IF ExhaustivelyCheckPage THEN DBStoragePage.CheckVecPage[p, pageHdr.tag];
IF ValidateInput AND (slotIndex = 0 OR slotIndex > pageHdr.highSlot) THEN
ERROR DBCommon.InternalError; -- NotASlot
slotPtr _ DBStoragePage.IndexToSlot[p, slotIndex];
IF ValidateInput AND (slotPtr.type = DBStoragePage.FreeType)
THEN ERROR DBCommon.InternalError; -- SlotIsFree
BEGIN
vecPtr: LONG POINTER TO VecHeader _
LOOPHOLE[p + slotPtr.vecOffset, LONG POINTER TO VecHeader];
vecPtr.slotIndex _ FreeSlotIndex;
pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs + vecPtr.length;
END;
IF slotIndex # pageHdr.highSlot THEN BEGIN
slotPtr^ _ Slot[type: DBStoragePage.FreeType, vecOffset: 0];
pageHdr.nFreeSlots _ pageHdr.nFreeSlots + 1;  END
ELSE BEGIN
freeWordsReclaimed: CARDINAL _ 1;
IF CheckPage AND
(DBStoragePage.IndexToSlot[p, FreeSlotIndex].type # DBStoragePage.UnFreeType) THEN
ERROR DBCommon.InternalError; -- FreeVecSmashed
DO
IF (slotPtr+freeWordsReclaimed).type # DBStoragePage.FreeType THEN EXIT;
freeWordsReclaimed _ freeWordsReclaimed + 1;
ENDLOOP;
pageHdr.highSlot _ pageHdr.highSlot - freeWordsReclaimed;
pageHdr.nFreeSlots _ pageHdr.nFreeSlots - (freeWordsReclaimed-1);
BEGIN
freeVecPtr: LONG POINTER TO VecHeader _ FreeVecPtr[p];
freeVecPtr.length _ freeVecPtr.length + freeWordsReclaimed;
pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs + freeWordsReclaimed;
END;
END;--IF
IF ExhaustivelyCheckPage THEN DBStoragePage.CheckVecPage[p, pageHdr.tag];
RETURN;
END;--FreeVec

ModifyVec: PUBLIC PROC [p: LONG POINTER TO VecPage, slotIndex: CARDINAL, deltaWords: INTEGER, preserveContents: BOOL] RETURNS[--success-- BOOL] = TRUSTED BEGIN

OPEN pageHdr: LOOPHOLE[p, LONG POINTER TO VecPage];
BEGIN -- Block for EXITS GOTOs
slotPtr: LONG POINTER TO Slot; -- points to slot whose vec we're modifying
vecPtr: LONG POINTER TO VecHeader; -- points to vec we're modifying
vecLen: CARDINAL; -- original length of vec we're modifying
newVecLen: CARDINAL; -- length after modification
DBStats.Inc[StorageModifyVec];
IF ExhaustivelyCheckPage THEN DBStoragePage.CheckVecPage[p, pageHdr.tag];
IF ValidateInput AND (slotIndex = 0 OR slotIndex > pageHdr.highSlot) THEN
ERROR DBCommon.InternalError; -- NotASlot
slotPtr _ DBStoragePage.IndexToSlot[p, slotIndex];
IF ValidateInput AND (slotPtr.type = DBStoragePage.FreeType) THEN
ERROR DBCommon.InternalError; -- SlotIsFree
vecPtr _ LOOPHOLE[p + slotPtr.vecOffset, LONG POINTER TO VecHeader];
vecLen _ vecPtr.length;
IF deltaWords > 0 THEN BEGIN
valPtr: LONG POINTER;
valPtrRef: REF Block;
Block: TYPE = RECORD [SEQUENCE length: CARDINAL OF CARDINAL]; 
valWasAllocated: BOOL _ FALSE; -- TRUE later if valPtr points to heap storage
IF deltaWords + SIZE[VecHeader] > pageHdr.nWordsInFreeVecs THEN--it just won't fit
GOTO Failure;
newVecLen _ vecLen + deltaWords;
IF newVecLen + SIZE[VecHeader] > pageHdr.nWordsInFreeVecs THEN BEGIN
IF preserveContents THEN BEGIN -- copy current value to temp storage
DBStats.Inc[StorageModifyDifficultVec];
valPtrRef _ NEW[Block[vecLen-SIZE[VecHeader]]];
valPtr_ LOOPHOLE[valPtrRef, LONG POINTER]+SIZE[Block[0]];
I.LongCopy[
from: vecPtr+SIZE[VecHeader], nwords: vecLen-SIZE[VecHeader], to: valPtr];
valWasAllocated _ TRUE;
END;--IF
vecPtr.slotIndex _ FreeSlotIndex;
pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs + vecLen;
CompactPage[p];  END
ELSE BEGIN
IF ~preserveContents THEN BEGIN --free old vec now, before possible compaction
vecPtr.slotIndex _ FreeSlotIndex;
pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs + vecLen;
END;--IF
IF newVecLen + SIZE[VecHeader] > FreeVecPtr[p].length THEN BEGIN
CompactPage[p];
vecPtr _ LOOPHOLE[p + slotPtr.vecOffset, LONG POINTER TO VecHeader];
END;--IF
IF preserveContents THEN BEGIN
valPtr _ vecPtr + SIZE[VecHeader]; -- safe because no compaction can happen now.
vecPtr.slotIndex _ FreeSlotIndex;
pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs + vecLen;
END;--IF
END;--IF
IF CheckPage AND newVecLen + SIZE[VecHeader] > FreeVecPtr[p].length THEN
ERROR DBCommon.InternalError; -- Unknown
slotPtr.vecOffset _ FreeVecOffset[p];
vecPtr _ LOOPHOLE[p + slotPtr.vecOffset, LONG POINTER TO VecHeader];
IF preserveContents THEN BEGIN -- Copy preserved value back
I.LongCopy[from: valPtr, nwords: vecLen-SIZE[VecHeader], to: vecPtr+SIZE[VecHeader]];
END;--IF
vecLen _ vecPtr.length; -- Length of freeVec before allocation
vecPtr^ _ VecHeader[slotIndex: slotIndex, length: newVecLen];
vecPtr _ vecPtr + newVecLen; -- Point to freeVec
vecPtr^ _ VecHeader[slotIndex: FreeSlotIndex, length: vecLen - newVecLen];
slotPtr _ LOOPHOLE[
p + (DBCommon.WordsPerPage - SIZE[Slot]), LONG POINTER TO Slot]; -- point to FreeSlot
slotPtr.vecOffset _ slotPtr.vecOffset + newVecLen;
pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs - newVecLen;  END
ELSE BEGIN--deltaWords<=0
IF deltaWords = 0 THEN GOTO Success;
deltaWords _ -deltaWords;
IF ValidateInput AND LOOPHOLE[deltaWords, CARDINAL] > vecLen THEN
DBCommon.InternalError; -- DeltaTooSmall
newVecLen _ LOOPHOLE[vecLen - deltaWords, CARDINAL]; 
vecPtr.length _ newVecLen;
vecPtr _ vecPtr + newVecLen; --point to the fragment we're freeing
vecPtr^ _ VecHeader[slotIndex: FreeSlotIndex, length: deltaWords];
pageHdr.nWordsInFreeVecs _ pageHdr.nWordsInFreeVecs + deltaWords;
END;--IF
GOTO Success;
EXITS
Success => BEGIN
IF ExhaustivelyCheckPage THEN DBStoragePage.CheckVecPage[p, pageHdr.tag];
RETURN[TRUE];
END;--Success
Failure => BEGIN
IF ExhaustivelyCheckPage THEN DBStoragePage.CheckVecPage[p, pageHdr.tag];
RETURN[FALSE];
END;--Failure
END;
END;--ModifyVec

CompactPage: PROC[p: LONG POINTER TO VecPage] = TRUSTED BEGIN

OPEN pageHdr: p;
highSlotOff: CARDINAL _ 
DBStoragePage.IndexToOffset[DBStoragePage.HighSlotIndexOfPage[p]];
curSrc: CARDINAL _ SIZE[VecPage];
curDst: CARDINAL;
s, l: CARDINAL;
nAllocVecs: CARDINAL _ 0;

BEGIN-- block for exit GOTOs
DBStats.Inc[StorageCompactPage];
DO
IF VecOfOffset[p, curSrc].slotIndex = FreeSlotIndex THEN EXIT;
nAllocVecs _ nAllocVecs + 1;
curSrc _ curSrc + VecOfOffset[p, curSrc].length;
IF CheckPage AND (curSrc >= highSlotOff) THEN GOTO NoFreeVecs;
REPEAT
NoFreeVecs => ERROR DBCommon.InternalError; -- FreeVecSmashed, freeVec should be present
ENDLOOP;
curDst _ curSrc;
curSrc _ curSrc + VecOfOffset[p, curSrc].length;
IF curSrc >= highSlotOff THEN BEGIN
IF ~CheckPage OR (curSrc = highSlotOff) THEN GOTO Compacted
ELSE ERROR DBCommon.InternalError; -- Unknown
END;--IF
DO
DO
IF VecOfOffset[p, curSrc].slotIndex # FreeSlotIndex THEN EXIT;
curSrc _ curSrc + VecOfOffset[p, curSrc].length;
IF curSrc >= highSlotOff THEN GOTO SeenAllVecs;
ENDLOOP;
nAllocVecs _ nAllocVecs + 1;
s _ VecOfOffset[p, curSrc].slotIndex;  l _ VecOfOffset[p, curSrc].length;
I.LongCopy[from: p+curSrc, nwords: l, to: p+curDst];
DBStoragePage.IndexToSlot[p, s].vecOffset _ curDst;
curDst _ curDst + l;
curSrc _ curSrc + l;
IF curSrc >= highSlotOff THEN GOTO SeenAllVecs;
REPEAT
SeenAllVecs => BEGIN
IF ~CheckPage OR (curSrc=highSlotOff) THEN BEGIN
DBStoragePage.IndexToSlot[p, FreeSlotIndex].vecOffset _ curDst;
VecOfOffset[p, curDst]^ _ VecHeader[slotIndex: FreeSlotIndex, length: curSrc - curDst];
GOTO Compacted;
END
ELSE ERROR DBCommon.InternalError;
END;--SeenAllVecs
ENDLOOP;
EXITS
Compacted => BEGIN
IF CheckPage AND (VecOfOffset[p, curDst].length # pageHdr.nWordsInFreeVecs) THEN
ERROR DBCommon.InternalError;
RETURN;
END;--Compacted
END;--EXITS
END;--CompactPage

END.--StorageVecImpl


Created by MBrown on February 15, 1980  10:39 PM

Changed by MBrown on February 17, 1980  4:58 PM

Changed by MBrown on February 17, 1980  10:25 PM

Changed by MBrown on February 18, 1980  10:46 AM

Changed by MBrown on February 18, 1980  6:30 PM

Changed by MBrown on February 19, 1980  3:41 PM

Changed by MBrown on 20-Feb-80 11:52

Changed by MBrown on February 20, 1980  3:07 PM

Changed by MBrown on February 24, 1980  11:55 AM

Changed by MBrown on June 11, 1980  4:29 PM

Changed by MBrown on August 22, 1980  4:37 PM

Changed by MBrown on August 24, 1980  10:51 AM

Changed by MBrown on September 26, 1980  4:18 PM

Changed by MBrown on December 6, 1980  11:28 PM

Changed by MBrown on February 27, 1981  5:28 PM

Changed by MBrown on August 7, 1982 9:56 pm
Changed by Willie-Sue on February 15, 1985

ŠFile: DBStoragePageImpl.mesa
Copyright c 1985 by Xerox Corporation.  All rights reserved.
Last edited by:
MBrown on August 7, 1982 9:55 pm
Cattell, November 8, 1983 1:10 pm
Willie-Sue, March 19, 1985 6:07:13 pm PST
Widom, July 16, 1985 5:35:35 pm PDT
Donahue, May 23, 1986 10:04:53 am PDT
This module implements all of DBStoragePage.
Constants relating to persistent structure (some others are in DBStoragePage).
Distinguished values for VecHeader.slotIndex:
In a VecHeader, this means that the vec is free.  This slot points to freeVec.
Returned by failing AllocVec as the slot result; should trap if used later.
Switches to control the amount of redundant checking compiled in.
Compile code to check the nWords input to AllocVec, slotIndex to FreeVec, etc.
(Don't exhaustively check input pages).
Compile code to check properties of the page structure during AllocVec, FreeVec, etc.
(Don't exhaustively check input pages).
Compile code to exhaustively check input pages, and recheck before returning,
for AllocVec, FreeVec, ModifyVec.
PrincOpsUtils
Returns the offset of freeVec.
Returns a pointer to freeVec.
Creates an empty page in page p of the cache, ready to store vecs using the procedures below.  The new page has tag = pageTag.
Number of words free after the page header and free slot are created.
Verifies that the internal structure of the page is consistent, and that it has tag = pageTag.  This proc clearly cannot check that the data stored in the vecs themselves is correct.  May die horribly if the page is really bad.
Tag is correct.
The nFreeSlots is correct.
FreeSlot is UnFree, freeVec is free and immediately above highSlot.
The non-slot area is full of vecs.  Non-free vecs point to (unique) non-free slots, that  point back.  (We use the pigeonhole principle to test uniqueness by counting non-free vecs).
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.
Create a new slot numbered one higher than the highest existing slot.
Shrink freeVec by one Slot's worth of words.
If it weren't for paranoia, we could just use a WHILE loop here; there must be a free slot.
If freeVec is too small, compact it now.
It is large enough now, so do it.
Frees the vec held in the slot at slotIndex, and the slot also.
Check integrity of sentinel (FreeSlot).
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).
We use the following "simplified" strategy:  If the page does not contain enough free words to hold the entire expanded vec without deleting the old copy, we save the old value in heap storage (if it needs to be preserved), delete the old vec, and compact.   Else if the page has enough space but freeVec doesn't, we compact.  If the old value needn't be preserved, we free it before compaction; otherwise it is freed after the value is copied out (and hence does not join freeVec).
Possible elaborations: extending the vec by looking for a free vec behind it.  (Not too hard, but may require coalescing several free vecs).  In-place permutation during compaction (MUCH harder).
Possible simplifications: always preserveContents (not so good for long strings). Allocate fixed storage in global frame for a buffer area, to eliminate heap node allocation.  With a suitable algorithm, this area needs only contain as much  storage as the maximum number of slots, or maybe less...
WARNING: We are loopholing valPtrRef (a REF) into a LONG POINTER (valPtr) here, in the case when we need auxiliary storage to copy into (since compaction will move the data and PrincOpsUtils.LongCopy won't work).  Both the long pointer and ref are local to this block, and the space will be garbage collected sometime later.
It will fit only after the original vec's storage has been reclaimed
Note: we assume that a request for a node of size 0 is ok.
It will fit in the current free storage, but compaction may still be needed...
At this point, the following is true: vecLen, newVecLen,and slotPtr have values as described in their respective declarations above.  The slot at slotPtr may point to garbage, but its type is ok.  If preserveContents, then valPtr points to the old contents (which may go away if CompactPage is called).  If valWasAllocated, then valPtr points to a vector gotten from AllocFieldValue.  FreeVec is long enough to hold newVecLen words for the new vec, plus a minimum freeVec.
Fixup freeVec
We depend on SIZE[VecHeader] = 1 here; otherwise we must do something else when a  piece smaller than a VecHeader is freed.  (Compacting would NOT suffice).
Collects all free storage on page p into a single free vec, and returns the size of the vec.  p is a tuple page in the cache, open for writing.
Called from: AllocVec, ModifyVec.
all three quantities are p-relative
loop to find the first free vec, if any
move past the first free vec
Loop to move each allocated vec down
loop to find the next allocated vec, if any
Found an allocated vec; move it
Module History
AllocVec and CompactPage copied from preliminary versions done on February 2
(before design was "debugged" and documented, interface formalized).
Recoded AllocVec to match new interface (it now allocates slots also).  Simplified it by
forcing freeVec to always exist, and by having redundant information in header.
Coded CheckVecPage.  Converted CompactPage to new primitives and made it compact upward.
Coded FreeVec.
Bug fixes: CompactPage set freeVec length to the negative of its true value.
AllocVec didn't update FreeSlot after allocating a vec from freeVec.  First test
program runs to completion.  (This took 1 hr of debugging; all other bugs were in
testing code).
Coded ModifyVec.
Two bugs found in ModifyVec. First was a logic bug in case ~preserveContents
and ~compact. {This was due to insufficient analysis in coding a complex problem;
a symptom was the deeply nested IF-THEN-ELSE structure.  The fix caused a considerable
simplification of this.}  Second was in the case preserveContents and ~valWasAllocated,
the length of freeVec was wrong. {This was due to coding one of two cases, noting
that the tail of the second could be unified with the first, but using the already
written code in the unification without reexamining it for hidden assumptions.}
A bug in one of the redundant checks.  Expanded VecTest now runs to completion.
Minor changes to conform to changes in inteface.
TIDSlotMask now comes from DBStorageTID.
Implemented WordsInLargestAllocableVec.
WordsInLargestAllocableVec returned 177777B when called on an empty page.  This was another
CARDINAL subtraction bug.  We really need true CARDINAL arithmetic!
Converted to new DBException.
Added DBStats counter events StorageInitVecPage, StorageCheckVecPage, StorageAllocVec,
StorageFreeVec, StorageModifyVec, StorageModifyDifficultVec, StorageCompactPage.
Pre-Pilot changes.
Set ExhaustivelyCheckPage = FALSE.

made Cedar, added tioga formatting
Κ‡˜š
œ™Jšœ
Οm
œ1™<—Jš
œ™Jš
œ ™ Jš
œ!™!Jš
œ)™)™#Icode™%—J˜š
Οk	˜	Jšœ	žœ+˜9J˜J˜J˜J˜—šœžœ
ž˜ Jšžœ"žœ˜:Jšžœ˜Jšžœ˜J˜Jšœž˜J˜Jšœ	žœ˜&Jšœžœ˜ Jšœžœ˜*J˜Jš
œ,™,J˜Jš
œN™NJ˜Jš
œ-™-˜0Jš
œN™N—šœžœžœ
žœ˜-Jš
œK™KJ˜J˜—Jš
œA™Ašœžœžœ
˜Jš
œN™NJš
œ'™'—šœžœžœ
˜Jš
œU™UJš
œ'™'—šœžœžœ
˜$Jš
œM™MJš
œ!™!J˜J˜—Jš
œ
™
J˜J˜šΟnœžœžœ
žœ
žœžœ
˜?š
žœ
žœ
žœ
žœžœ
žœ
ž˜9Jš
žœ
žœžœ
žœ
žœ
˜6—Jšžœ
Οc
˜—J˜šŸ
œžœžœ
žœ
žœ	žœ
žœžœ
žœ
ž˜Xš
œ™Jšžœ
žœžœ	žœ
žœ
žœ˜Y—Jšžœ
 ˜—J˜šŸ
œžœžœ
žœ
žœ	žœ
žœ
žœ
žœžœ
žœ
ž˜fš
œ™Jšžœ#˜)—Jšžœ
 
˜—J˜šŸœžœ
žœžœ
žœ
žœžœžœ
ž˜]š
œ~™~šœžœžœžœ˜IJš
œE™E—J˜ J˜Tš
žœžœžœ
žœ
žœ˜8J˜7—š
žœžœžœ
žœ
žœ
˜FJšœ0žœ˜?——Jšžœ
 ˜J˜J˜—šŸœžœ
žœžœ
žœ
žœžœžœ
ž˜XJš
œγ
™γ
J˜Jšžœ˜J˜š	Ÿœžœžœžœ
ž˜-Jšžœžœ
žœ ˜F—Jšžœ
 ˜J˜Jš
œ™J˜!J˜-Jš
œ™Jšžœ
žœžœ
˜3šžœ	žœ+ž˜;šžœ?ž˜EJ˜——Jšžœ
˜J˜(Jšžœ
˜Jš
œC™CJšžœ
žœ
žœ
žœ˜<šœžœžœžœ
žœ
žœ
˜PJ˜—J˜-š	œžœ!žœ
žœ
žœ˜GJ˜D—Jšžœ
˜Jš
œΆ
™Ά
Jšžœžœ'žœ˜MJš	œžœ
žœ
žœžœ˜Ešžœž˜"Jšžœ%žœ)˜Tšžœ
ž˜
J˜RJ˜DJ˜—Jšžœ
 ˜J˜)—Jšžœ
˜J˜-J˜<Jšžœ
˜—Jšžœ
 ˜J˜šŸœžœ
žœžœ
žœ
žœžœ
žœ
 
œ
žœ œ
žœžœ
ž˜…
š
œΔ
™Δ
J˜Jšžœ˜Jšœžœ
˜Jšž ˜Jšœžœ
žœ
žœ˜!Jšœžœ
žœ
žœ˜6Jšœžœ
˜J˜Jšžœžœ,˜Išžœžœžœ
ž˜4Jšžœ
žœ ˜/—šžœžœ
ž˜$šžœ#žœžœž˜DJšžœ	˜
—Jšžœ)žœ
žœ	˜=šžœžœžœ
ž˜1J˜,—Jšžœ
 ˜Jš
œE™EJ˜7J˜8šžœžœ$˜4š	žœ
žœ
žœ
žœ
ž˜5Jšžœ
žœ ˜/——Jš
œ,™,Jšœ(žœ˜3šžœžœžœ
ž˜;Jšžœ
žœ ˜/—Jšœ6žœ	ž˜F—šžœ
ž ˜"Jšžœ#žœžœ
žœ	˜GJš
œ[™[šžœžœž˜,JšžœDžœ
žœ
˜P—š
ž˜Jšžœžœ
žœ ˜=—Jšžœ
˜J˜8J˜,—Jšžœ
 ˜Jš
œ(™(šžœžœžœ
ž˜8J˜,—Jšžœ
 ˜Jš
œ!™!J˜%šžœžœžœ
ž˜AJšžœ
žœ ˜/—J˜8J˜LJ˜!J˜Jšœ
žœžœ˜?Jšžœ
žœ
žœ ˜+—J˜5J˜=Jšžœ	˜
š
ž˜šœž˜Jšžœžœ,˜IJšžœžœ˜—Jšžœ
 	˜
šœž˜Jšžœžœ,˜IJšžœžœ˜!—Jšžœ
 	˜
—Jšžœ
˜—Jšžœ
 
˜—J˜šŸœžœ
žœžœ
žœ
žœ	˜Cšžœ
 
œ
žœžœ˜(Jšžœ˜Jšœžœžœ˜GJšœžœžœžœ
žœžœ˜QJšžœ
žœ(žœžœ&˜b—Jšœ ˜—J˜J˜šŸœžœ
žœžœ
žœ
žœžœž
˜UJš
œ?™?J˜Jšžœ˜Jšœ	žœ
žœ
žœ˜J˜Jšžœžœ,˜Išžœžœžœž˜IJšžœ
žœ ˜)—J˜2šžœžœ(˜<Jšžœ
žœ
žœ 
˜0—š
ž˜šœžœ
žœ
žœ˜#Jšžœžœ
žœ
žœ˜;—J˜!J˜D—Jšžœ
˜šžœžœ
ž˜*J˜<Jšœ.ž˜1—šžœ
ž˜
Jšœžœ˜!Jš
œ'™'šžœž˜JšœNž˜RJšžœ
žœ ˜/—š
ž˜Jšžœ<žœ
žœ
˜HJ˜,—Jšžœ
˜J˜9J˜Aš
ž˜Jšœžœ
žœ
žœ˜6J˜;J˜I—Jšžœ
˜—Jšžœ
 ˜Jšžœžœ,˜IJšžœ
˜Jšžœ
 	˜
—J˜šŸ	œžœ
žœžœ
žœ
žœžœžœžœ
žœ
 œ
žœžœ
ž˜Ÿ
Jš
œˆ™ˆJ˜Jš
žœ
žœžœ
žœ
žœ
˜3Jšžœ
 ˜Jšœ	žœ
žœ
žœ +˜JJšœžœ
žœ
žœ  ˜CJšœžœ )˜;Jšœžœ ˜1J˜Jšžœžœ,˜Išžœžœžœž˜IJšžœ
žœ ˜)—J˜2šžœžœ)ž˜AJšžœ
žœ 
˜+—Jš	œ	žœžœ
žœ
žœ˜DJ˜šžœžœ
ž˜Jšœžœ
žœ
˜Jšœžœ˜Jš
œžœžœžœ	žœ
žœ
žœ˜>Jšœžœžœ .˜Mšžœžœ'ž ˜RJšžœ	˜
—Jš
œβ™βJš
œΓ
™Γ
Jš
œ©™©Jš
œΔ™ΔJ˜ šžœ
žœ'žœ
ž˜DJš
œD™Dšžœžœ
žœ
 %˜DJ˜'Jšœžœžœ˜/š	œžœžœ
žœžœ˜9Jš
œ:™:—šž
œ
˜Jšœ
žœžœ˜J—Jšœžœ
˜—Jšžœ
 ˜J˜!J˜=Jšœž˜—šžœ
ž˜
Jš
œN™Nšžœžœ
žœ
 .˜NJ˜!J˜=—Jšžœ
 ˜šžœ
žœ#žœ
ž˜@J˜Jš	œ	žœžœ
žœ
žœ˜D—Jšžœ
 ˜šžœžœ
ž˜Jšœžœ
 -˜PJ˜!J˜=—Jšžœ
 ˜—Jšžœ
 ˜Jš
œΨ™Ψšžœžœ
žœ#ž˜HJšžœ
žœ 
˜(—J˜%Jš	œ	žœžœ
žœ
žœ˜Dšžœžœ
žœ
 ˜;Jšž
œ'žœžœ
˜UJšžœ
 ˜—Jšœ &˜>J˜=Jš
œ
™
Jšœ ˜0J˜Jšœ
žœ
˜Jš
œžœ	žœ
žœ
žœ ˜U—J˜2JšœBž˜E—šžœ
ž ˜Jšžœžœ
žœ	˜$Jš
œœ
™œ
J˜š	žœžœ
žœ
žœž˜AJšžœ ˜(—Jšœžœžœ˜5J˜Jšœ %˜BJ˜BJ˜A—Jšžœ
 ˜Jšžœ	˜
š
ž˜šœž˜Jšžœžœ,˜IJšžœ
žœ˜
—Jšžœ
 	˜
šœž˜Jšžœžœ,˜IJšžœ
žœ˜—Jšžœ
 	˜
—Jšžœ
˜Jšžœ
 ˜—J˜š
Ÿœžœžœ
žœ
žœžœ
ž˜=Jš
œ
™
Jš
œ!™!J˜Jšžœ˜šœ
žœ˜J˜B—Jšœžœžœ
˜!šœžœ
˜Jš
œ#™#—Jšœžœ
˜Jšœžœ˜J˜Jšž ˜J˜ š
ž˜Jš
œ'™'Jšžœ2žœ
žœ
˜>J˜J˜0Jšžœžœžœ
žœ˜>—š
ž˜Jšœžœ
žœ ,˜X—Jšžœ
˜Jš
œ™J˜J˜0šžœžœ
ž˜#Jšžœžœžœ
žœ
˜;Jšžœ
žœ
žœ 
˜-—Jšžœ
 ˜š
ž˜Jš
œ$™$š
ž˜Jš
œ+™+Jšžœ2žœ
žœ
˜>J˜0Jšžœžœ
žœ
˜/—Jšžœ
˜Jš
œ™J˜J˜IJšž
œ3˜4J˜3J˜J˜Jšžœžœ
žœ
˜/—š
ž˜šœž˜šžœžœžœ
ž˜0J˜?J˜WJšžœ˜—Jš
ž˜Jšžœ
žœ
žœ
˜"—Jšžœ
 
˜—Jšžœ
˜š
ž˜šœ
ž˜šžœžœ<ž˜PJšžœ
žœ
˜—Jšžœ
˜—Jšžœ
 ˜—Jšžœ
 ˜Jšžœ
 
˜—J˜—Jšžœ
 ˜J˜Jš
œ™J˜Jšœ.ž˜0Jš
œL™LJš
œD™DJ˜Jšœ-ž˜/Jš
œX™XJš
œO™OJ˜Jšœ.ž˜0Jš
œX™XJ˜Jšœ.ž˜0Jš
œ™J˜Jšœ-ž˜/Jš
œL™LJš
œP™PJš
œQ™QJš
œ™J˜Jšœ-ž˜/Jš
œ™J˜J˜$Jš
œL™LJš
œQ™QJš
œV™VJš
œW™WJš
œQ™QJš
œR™RJš
œO™OJ˜Jšœ-ž˜/Jš
œO™OJ˜Jšœ.ž˜0Jš
œ0™0J˜Jšœ)ž˜+Jš
œ(™(J˜Jšœ+ž˜-Jš
œ'™'J˜Jšœ,ž˜.Jš
œ[™[Jš
œC™CJ˜Jšœ.ž˜0Jš
œ™J˜Jšœ-ž˜/Jš
œV™VJš
œP™PJ˜Jšœ-ž˜/Jš
œ™J˜J˜+Jš
œ"™"J™J˜*J™"J˜—…—9Ψiι