-- 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>,
IF match THEN --
,
IF MergeDown[slot - 1] THEN -- ,
RemoveRunSpace[slot - 1, 2]
ELSE -- ,
{RemoveRunSpace[slot, 1]; file.runTable[slot].vda _ vda}
ELSE file.runTable[slot + 1] _ [page, vda] --
ELSE
IF match THEN -- , , ,
ELSE file.runTable[slot].page _ page + 1 -- , , ,
InsertRunSpace[slot, 1]
ELSE --