-- 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 -- , 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 -- , IF MergeDown[slot - 1] THEN -- , , IF file.runTable[slot + 1].page = page + 1 THEN RemoveRunSpace[slot - 1, 1] -- , , ELSE file.runTable[slot].page _ page + 1 -- , , ELSE -- , , BEGIN file.runTable[slot].vda _ vda; IF file.runTable[slot + 1].page ~= page + 1 THEN BEGIN -- , , InsertRunSpace[slot, 1]; file.runTable[slot + 1] _ [page + 1, fillInvDA]; END; END ELSE -- , BEGIN IF file.runTable[slot + 1].page = page + 1 THEN -- , InsertRunSpace[slot, 1] ELSE -- , {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.