-- PilotBTreeSupportImpl.mesa
-- last edited by Levin,  August 18, 1982 10:08 am
--	Schmidt, October 4, 1982 11:47 am
-- Schroeder, July 21, 1982 4:28 pm

DIRECTORY
  BTreeSupportDefs USING [PageHandle, PageNumber],
  BTreeSupportExtraDefs USING [],
  DCSFileTypes USING [tLeaderPage],
  Directory: TYPE USING[PutProperty],
  Environment USING [bytesPerPage, wordsPerPage],
  File USING [
    Capability, GetAttributes, GetSize, PageCount, PageNumber, SetSize,
    ShowCapability],
  FileStream USING [-- Create, GetLength, SetLength, -- SetLeaderPropertiesForCapability],
  Heap USING [systemZone],
  Inline USING [LongCOPY, LongDivMod, LowHalf],
  PropertyTypes: TYPE USING[tByteLength],
  Space USING [
    Create, CreateUniformSwapUnits, Deactivate, Delete, ForceOut, GetHandle,
    GetWindow, Handle, LongPointer, Map, PageCount, PageFromLongPointer, Unmap,
    virtualMemory, WindowOrigin],
  -- Stream USING [Delete, Handle],
  System: TYPE USING [GetGreenwichMeanTime, GreenwichMeanTime]; 

PilotBTreeSupportImpl: PROGRAM
  IMPORTS Directory, File, FileStream, Heap, Inline, Space, -- Stream, -- System
  EXPORTS BTreeSupportDefs, BTreeSupportExtraDefs =

BEGIN OPEN BTreeSupportDefs;

-- Caller Bugs

IllegalPageHandle: ERROR = CODE;
IllegalPageNumber: ERROR = CODE;
NonTrivialRemap: ERROR = CODE;

-- Implementation Bugs

HandleIndexingBotch: ERROR = CODE;


-- BTreeSupportExtraDefs implementation

pageSize: CARDINAL = Environment.wordsPerPage;

FileHandle: PUBLIC TYPE = LONG POINTER TO FileDesc;
FileDesc: TYPE = RECORD [
  cap: File.Capability,
  bias: [0..1],
  written: BOOLEAN,
  fileSize: File.PageCount,
  spaces: LONG POINTER TO SpaceHandles];

SpaceHandles: TYPE = RECORD [
  nSpaces: HandleIndex ← 0,
  spaceHandles: SEQUENCE maxHandles: CARDINAL OF Space.Handle ← NULL];

HandleIndex: TYPE = CARDINAL;

mappingIncrement: Space.PageCount = 32;
minTableSize: CARDINAL = 30;
tableSizeIncrement: CARDINAL = 15;

OpenFile: PUBLIC PROCEDURE [cap: File.Capability] RETURNS [fileH: FileHandle] =
  BEGIN
  bias: [0..1] = IF File.GetAttributes[cap].type = DCSFileTypes.tLeaderPage THEN 1 ELSE 0;
  fileSize: File.PageCount = File.GetSize[cap];
  window: Space.WindowOrigin ← [cap, bias];
  tableSize: CARDINAL = MAX[Inline.LowHalf[(fileSize-bias+mappingIncrement)/mappingIncrement], minTableSize];
  fileH ← Heap.systemZone.NEW[FileDesc ←
    [cap: cap, bias: bias, written: FALSE, fileSize: fileSize,
     spaces: Heap.systemZone.NEW[SpaceHandles[tableSize] ← []]]];
  UNTIL window.base >= fileSize DO
    space: Space.Handle = Space.Create[size: mappingIncrement, parent: Space.virtualMemory];
    index: HandleIndex = fileH.spaces.nSpaces;
    Space.CreateUniformSwapUnits[1, space];
    Space.Map[space, window];
    window.base ← window.base + mappingIncrement;
    fileH.spaces.spaceHandles[index] ← space;
    fileH.spaces.nSpaces ← index + 1;
    ENDLOOP;
  END;

CloseFile: PUBLIC PROCEDURE [fileH: FileHandle] =
  BEGIN
    FOR i: HandleIndex IN [0..fileH.spaces.nSpaces) DO
    Space.Delete[fileH.spaces.spaceHandles[i]];
    ENDLOOP;
  Heap.systemZone.FREE[@fileH.spaces];
  Heap.systemZone.FREE[@fileH];
  END;
  
-- BTreeSupportDefs implementation

ReadPage: PUBLIC PROCEDURE [fileH: FileHandle, pageN: PageNumber]
  RETURNS [pageH: PageHandle] =
  BEGIN
  IF pageN + fileH.bias >= fileH.fileSize THEN ERROR IllegalPageNumber;
  RETURN[PageNumberToPageHandle[fileH, pageN]]
  END;

UsePage: PUBLIC PROCEDURE [fileH: FileHandle, pageN: PageNumber]
  RETURNS [pageH: PageHandle] =
  BEGIN
  requiredFileSize: CARDINAL = pageN + fileH.bias + 1;
  IF fileH.fileSize < requiredFileSize THEN
    BEGIN
    index: HandleIndex ← fileH.spaces.nSpaces;
    space: Space.Handle ← fileH.spaces.spaceHandles[index-1];
    window: Space.WindowOrigin ← Space.GetWindow[space];
    Space.Unmap[space];
    File.SetSize[fileH.cap, fileH.fileSize ← requiredFileSize];
    SetLengthInLeaderPage[fileH];
    Space.Map[space, window];
    UNTIL LONG[index]*mappingIncrement + fileH.bias >= requiredFileSize DO
      space: Space.Handle = Space.Create[size: mappingIncrement, parent: Space.virtualMemory];
      Space.CreateUniformSwapUnits[1, space];
      window.base ← window.base + mappingIncrement;
      Space.Map[space, window];
      IF index = fileH.spaces.maxHandles THEN
        BEGIN
	newTable: LONG POINTER TO SpaceHandles =
	  Heap.systemZone.NEW[SpaceHandles[fileH.spaces.maxHandles+tableSizeIncrement] ← []];
	Inline.LongCOPY[from: @fileH.spaces.spaceHandles[0], to: @newTable.spaceHandles[0],
	  nwords: fileH.spaces.nSpaces*SIZE[Space.Handle]];
	Heap.systemZone.FREE[@fileH.spaces];
	fileH.spaces ← newTable;
	END;
      fileH.spaces.spaceHandles[index] ← space;
      index ← index + 1;
      ENDLOOP;
    fileH.spaces.nSpaces ← index;
    END;
  RETURN[PageNumberToPageHandle[fileH, pageN]]
  END;

WritePage: PUBLIC PROCEDURE[fileH: FileHandle, pageN: PageNumber, pageH: PageHandle] =
  BEGIN
  space: Space.Handle = Space.GetHandle[Space.PageFromLongPointer[pageH]];
  IF File.ShowCapability[Space.GetWindow[space].file].fID ~= File.ShowCapability[fileH.cap].fID THEN
    ERROR IllegalPageHandle;
  IF pageN >= fileH.fileSize - fileH.bias THEN ERROR IllegalPageNumber;
  IF PageNumberToPageHandle[fileH, pageN] ~= pageH THEN ERROR NonTrivialRemap;
  IF NOT fileH.written THEN {
    IF fileH.bias = 1 THEN {
      now: System.GreenwichMeanTime = System.GetGreenwichMeanTime[];
      FileStream.SetLeaderPropertiesForCapability[cap: fileH.cap, create: now, write: now];
      };
    fileH.written ← TRUE;
    };
  Space.ForceOut[space];
  END;

ReleasePage: PUBLIC PROCEDURE [pageH: PageHandle] =
  {Space.Deactivate[Space.GetHandle[Space.PageFromLongPointer[pageH]]]};

SetLength: PUBLIC PROCEDURE [fileH: FileHandle, pageN: PageNumber] =
  BEGIN
  newSize: File.PageCount = pageN + fileH.bias;
  SELECT newSize FROM
    > fileH.fileSize => ReleasePage[UsePage[fileH, pageN]];
    < fileH.fileSize =>
      BEGIN
      handleIndex: HandleIndex;
      relPage: CARDINAL;
      window: Space.WindowOrigin;
      [handleIndex, relPage] ← Inline.LongDivMod[pageN, mappingIncrement];
      FOR i: HandleIndex IN (handleIndex..fileH.spaces.nSpaces) DO
        Space.Delete[fileH.spaces.spaceHandles[i]];
	ENDLOOP;
      window ← Space.GetWindow[fileH.spaces.spaceHandles[handleIndex]];
      Space.Unmap[fileH.spaces.spaceHandles[handleIndex]];
      File.SetSize[fileH.cap, fileH.fileSize ← newSize];
      SetLengthInLeaderPage[fileH];
      Space.Map[fileH.spaces.spaceHandles[handleIndex], window];
      END;
    ENDCASE;
  END;

PageSize: PUBLIC PROCEDURE RETURNS [nWords: CARDINAL] = {RETURN[pageSize]};

RawStorage: TYPE = RECORD [SEQUENCE COMPUTED CARDINAL OF WORD];

AllocateWords: PUBLIC PROCEDURE [nWords: CARDINAL] RETURNS [LONG POINTER] =
  {RETURN[LOOPHOLE[Heap.systemZone.NEW[RawStorage[nWords]]]]};

FreeWords: PUBLIC PROCEDURE [p: LONG POINTER] =
  {Heap.systemZone.FREE[@p]};

-- Internal Stuff

SetLengthInLeaderPage: PROC [fileH: FileHandle] =
  BEGIN
  newLength: LONG CARDINAL;
  -- sH: Stream.Handle;
  IF fileH.bias # 1 THEN RETURN;
  newLength ← (fileH.fileSize-1)*Environment.bytesPerPage;
  Directory.PutProperty[file: fileH.cap, property: PropertyTypes.tByteLength,
  	propertyValue: DESCRIPTOR[@newLength, SIZE[LONG CARDINAL]]];
  -- sH ← FileStream.Create[fileH.cap];
  -- IF FileStream.GetLength[sH] # newLength
    -- THEN FileStream.SetLength[sH, newLength];
  -- Stream.Delete[sH];
  END; --SetLengthInLeaderPage--

PageNumberToPageHandle: PROCEDURE [fileH: FileHandle, pageN: PageNumber]
  RETURNS [pageH: PageHandle] =
  BEGIN
  handleIndex: HandleIndex;
  relPage: CARDINAL;
  [handleIndex, relPage] ← Inline.LongDivMod[pageN, mappingIncrement];
  IF handleIndex >= fileH.spaces.nSpaces THEN ERROR HandleIndexingBotch;
  RETURN[Space.LongPointer[fileH.spaces.spaceHandles[handleIndex]]+LONG[relPage]*pageSize]
  END;

END.