-- File: AltoFileOpsA.mesa
-- Last edited by Levin: 30-Apr-81 14:26:02
DIRECTORY
AltoDefs USING [PageNumber],
AltoFile USING [PageNumber],
AltoFilePrivate USING [
AltoPageNumber, FileHandle, FileObject, infinityPage, maxRuns,
percentToIncrease, RunIndex, RunCount, RunTable, VdaRun],
DiskIODefs USING [eofvDA, FID, fillInvDA, vDA],
FileDefs USING [],
Inline USING [COPY],
VMStorage USING [shortTerm];
AltoFileOpsA: MONITOR LOCKS file.runTableLock USING file: AltoFilePrivate.FileHandle
IMPORTS Inline, VMStorage
EXPORTS AltoFile, AltoFilePrivate, FileDefs =
BEGIN OPEN AltoFile, AltoFilePrivate, DiskIODefs;
-- Miscellaneous Declarations --
RunTableOverflow: ERROR = CODE;
RunTableInconsistent: ERROR = CODE;
ImpossiblevDA: ERROR = CODE;
InvalidvDA: ERROR = CODE;
-- Types Exported to FileDefs --
FileObject: PUBLIC TYPE = AltoFilePrivate.FileObject;
-- Procedures and Signals Exported to AltoFile --
EnterDiskAddress: PUBLIC PROCEDURE [
file: FileHandle, page: AltoDefs.PageNumber, vda: vDA] =
LOOPHOLE[EnterPageAndvDA];
MapPageToDiskAddress: PUBLIC PROCEDURE [
file: FileHandle, page: PageNumber, successors: CARDINAL ← 0]
RETURNS [nearPage: PageNumber, nearvda: vDA, knownPages: CARDINAL] =
BEGIN
diskPage: AltoDefs.PageNumber ← AltoFromFilePageNumber[page];
entry: VdaRun;
GetInfo: ENTRY PROCEDURE [file: FileHandle] = INLINE
BEGIN
slot: RunIndex ← FindPageInTable[file, diskPage].nearest;
entry ← file.runTable[slot];
IF entry.vda = fillInvDA THEN
{diskPage ← entry.page - 1; entry ← file.runTable[slot - 1]; knownPages ← 1}
ELSE
BEGIN
knownPagesLimit: CARDINAL = successors + 1;
DO
e: VdaRun ← file.runTable[slot ← slot + 1];
known: CARDINAL ← e.page - diskPage;
IF known >= knownPagesLimit OR e.vda = fillInvDA THEN
{knownPages ← MIN[knownPagesLimit, known]; EXIT};
ENDLOOP;
END;
END;
GetInfo[file];
RETURN[
FileFromAltoPageNumber[diskPage],
vDA[VdaToCardinal[entry.vda] + diskPage - entry.page],
knownPages]
END;
GetFileID: PUBLIC PROCEDURE [file: FileHandle] RETURNS [FID] =
-- Note: since the fileID never changes, no synchronization is used here.
{RETURN[file.fileID]};
FileToAltoPageNumber: PUBLIC PROCEDURE [page: PageNumber]
RETURNS [AltoPageNumber] =
{RETURN[AltoFromFilePageNumber[page]]};
-- Procedures and Signals Exported to AltoFilePrivate --
GetvDAForPage: PUBLIC PROCEDURE [file: FileHandle, page: AltoPageNumber]
RETURNS [vDA] =
BEGIN
entry: VdaRun;
GetEntry: ENTRY PROCEDURE [file: FileHandle] = INLINE
{entry ← file.runTable[FindPageInTable[file, page].nearest]};
GetEntry[file];
SELECT entry.vda FROM
eofvDA => ERROR ImpossiblevDA;
fillInvDA => RETURN[entry.vda];
ENDCASE => RETURN[vDA[VdaToCardinal[entry.vda] + page - entry.page]];
END;
EnterPageAndvDA: PUBLIC ENTRY PROCEDURE [
file: FileHandle, page: AltoPageNumber, vda: vDA] =
BEGIN
match: BOOLEAN;
slot: RunIndex;
InsertRunSpace: PROCEDURE [where: RunIndex, slots: CARDINAL] =
-- opens up file's runTable to have a gap of length 'slots' immediately after
-- index 'where'.
BEGIN
oldLength: RunCount = file.nRuns;
newLength: RunCount = oldLength + slots;
oldSpace: RunCount = file.runTable.runSpace;
table: POINTER TO RunTable ← file.runTable;
IF newLength > oldSpace THEN
BEGIN OPEN VMStorage;
newSpace: RunCount = MIN[maxRuns, oldSpace + (oldSpace*percentToIncrease)/100];
newTable: POINTER TO RunTable;
IF oldSpace = maxRuns THEN ERROR RunTableOverflow;
newTable ← shortTerm.NEW[RunTable[newSpace]];
Inline.COPY[from: @table[0], to: @newTable[0], nwords: oldLength*SIZE[VdaRun]];
shortTerm.FREE[@table];
file.runTable ← table ← newTable;
END;
file.nRuns ← newLength;
FOR i: CARDINAL DECREASING IN [where + 1..oldLength) DO
table[i + slots] ← table[i];
ENDLOOP;
END;
RemoveRunSpace: PROCEDURE [where: RunIndex, slots: CARDINAL] =
-- eliminates slots numbered [where+1..where+slots] from file's runTable.
BEGIN
table: POINTER TO RunTable = file.runTable;
firstToMove: CARDINAL = where + slots + 1;
n: CARDINAL = file.nRuns - firstToMove;
Inline.COPY[
from: @table[firstToMove], to: @table[where + 1], nwords: n*SIZE[VdaRun]];
file.nRuns ← file.nRuns - slots;
END;
MergeDown: PROCEDURE [where: RunIndex] RETURNS [BOOLEAN] =
-- returns TRUE if [page, vda] can be merged from above into file.runTable[where],
-- FALSE otherwise. It is assumed that vda ~= fillInvDA.
BEGIN
entry: VdaRun = file.runTable[where];
RETURN[
IF entry.vda = fillInvDA THEN FALSE
ELSE vDA[VdaToCardinal[entry.vda] + page - entry.page] = vda]
END;
MergeUp: PROCEDURE [where: RunIndex] RETURNS [BOOLEAN] = INLINE
-- returns TRUE if [page, vda] can be merged from below into file.runTable[where],
-- FALSE otherwise. It is assumed that vda ~= fillInvDA.
BEGIN
entry: VdaRun = file.runTable[where];
RETURN[
IF entry.page = page + 1 THEN
IF entry.vda = fillInvDA THEN FALSE
ELSE vDA[VdaToCardinal[vda] + 1] = entry.vda ELSE FALSE]
END;
CheckSlotForFillInvDA: PROCEDURE RETURNS [isFillIn: BOOLEAN] = INLINE
-- checks that [page, vda] is consistent with the entry in file.runTable[slot].
-- If so, the value returned indicates whether file.runTable[slot] = fillInvDA.
BEGIN
entry: VdaRun = file.runTable[slot];
IF (isFillIn ← entry.vda = fillInvDA) THEN RETURN
ELSE
IF VdaToCardinal[vda] ~= VdaToCardinal[entry.vda] + page - entry.page THEN
ERROR RunTableInconsistent;
END;
SELECT vda FROM
eofvDA => RETURN; -- eliminates eof checks in CompletionProcedures
fillInvDA => ERROR InvalidvDA;
ENDCASE;
[match, slot] ← FindPageInTable[file, page];
IF CheckSlotForFillInvDA[] THEN
-- note: file.runTable[0].vda ~= fillInvDA implies slot > 0, which is assumed.
-- note: in the following comments, 'p' and 'v' are the variables 'page' and
-- 'vda', x and y are unsuitable vdas, m < p-1, p+1 < n, and ? is
-- irrelevant information.
IF MergeUp[slot + 1] THEN -- <?, fillin>, <p+1, v+1>
IF match THEN -- <p, fillin>, <p+1, v+1>
IF MergeDown[slot - 1] THEN -- <p-1, v-1>, <p, fillin>, <p+1, v+1>
RemoveRunSpace[slot - 1, 2]
ELSE -- <m | x>, <p, fillin>, <p+1, v+1>
{RemoveRunSpace[slot, 1]; file.runTable[slot].vda ← vda}
ELSE file.runTable[slot + 1] ← [page, vda] -- <m, fillin>, <p+1, v+1>
ELSE
IF match THEN -- <p, fillin>, <n | x>
IF MergeDown[slot - 1] THEN -- <p-1, v-1>, <p, fillin>, <n | x>
IF file.runTable[slot + 1].page = page + 1 THEN
RemoveRunSpace[slot - 1, 1] -- <p-1, v-1>, <p, fillin>, <p+1, x>
ELSE file.runTable[slot].page ← page + 1 -- <p-1, v-1>, <p, fillin>, <n, ?>
ELSE -- <m | x>, <p, fillin>, <n | x>
BEGIN
file.runTable[slot].vda ← vda;
IF file.runTable[slot + 1].page ~= page + 1 THEN
BEGIN -- <m | x>, <p, fillin>, <n, ?>
InsertRunSpace[slot, 1];
file.runTable[slot + 1] ← [page + 1, fillInvDA];
END;
END
ELSE -- <m, fillin>, <n | x>
BEGIN
IF file.runTable[slot + 1].page = page + 1 THEN -- <m, fillin>, <p+1, x>
InsertRunSpace[slot, 1]
ELSE -- <m, fillin>, <n, ?>
{InsertRunSpace[slot, 2]; file.runTable[slot + 2] ← [page + 1, fillInvDA]};
file.runTable[slot + 1] ← [page, vda];
END;
END;
FindLastKnownPage: PUBLIC PROCEDURE [file: FileHandle]
RETURNS [AltoPageNumber, vDA] =
BEGIN
lastPage: AltoPageNumber;
entry: VdaRun;
GetInfo: ENTRY PROCEDURE [file: FileHandle] = INLINE
BEGIN
slot: RunIndex ← file.nRuns - 3;
lastPage ← file.runTable[slot + 1].page - 1;
entry ← file.runTable[slot];
END;
GetInfo[file];
SELECT entry.vda FROM
eofvDA => ERROR ImpossiblevDA;
fillInvDA => ERROR RunTableInconsistent;
ENDCASE =>
RETURN[lastPage, vDA[VdaToCardinal[entry.vda] + lastPage - entry.page]];
END;
TruncatevDATable: PUBLIC ENTRY PROCEDURE [file: FileHandle, page: AltoPageNumber] =
BEGIN
slot: RunIndex;
slot ← FindPageInTable[file, page].nearest;
SELECT file.runTable[slot].vda FROM
eofvDA => ERROR ImpossiblevDA;
fillInvDA => NULL;
ENDCASE => file.runTable[(slot ← slot + 1)] ← [page + 1, fillInvDA];
file.runTable[slot + 1] ← [infinityPage, eofvDA];
file.nRuns ← slot + 1 + 1;
END;
-- Internal Procedures --
FindPageInTable: PROCEDURE [file: FileHandle, page: AltoPageNumber]
RETURNS [found: BOOLEAN, nearest: RunIndex] =
-- searches file.runTable for 'page'. If the page is found, then 'nearest' is
-- the index of 'page' in the table. If the page is not found, then 'nearest' is
-- the index of the largest smaller-numbered page.
BEGIN
low: RunIndex ← 0;
high: RunIndex ← file.nRuns - 1;
found ← TRUE;
UNTIL low > high DO
nearest ← (low + high)/2;
SELECT file.runTable[nearest].page FROM
page => RETURN;
< page => low ← nearest + 1;
> page => high ← nearest - 1;
ENDCASE;
ENDLOOP;
RETURN[FALSE, low - 1]
END;
AltoFromFilePageNumber: PROCEDURE [fp: PageNumber] RETURNS [AltoPageNumber] = INLINE
{RETURN[fp + 1]};
FileFromAltoPageNumber: PROCEDURE [ap: AltoPageNumber] RETURNS [PageNumber] = INLINE
{RETURN[ap - 1]};
VdaToCardinal: PROCEDURE [vda: vDA] RETURNS [CARDINAL] = INLINE
{RETURN[LOOPHOLE[vda]]};
END.