-- FileListsImpl.Mesa  
--   Last edited by Sandman on July 8, 1980  9:14 AM
--   Last edited by Sweet on August 28, 1980  10:01 AM
--   Last edited by Lewis on October 7, 1980  6:21 PM
-- Copyright  Xerox Corporation 1979, 1980

DIRECTORY
  AltoDefs USING [PageSize],
  AltoFileDefs USING [FilenameChars],
  BcdDefs USING [VersionStamp],
  ImageDefs USING [StopMesa],
  InlineDefs USING [BITAND, BITXOR],
  IODefs USING [WriteLine],
  FileLists,
  SegmentDefs USING [
    Append, DefaultBase, DefaultVersion, DeleteFileSegment, DestroyFile,
    FileHandle, FileSegmentAddress, FileSegmentHandle, LockFile,
    MoveFileSegment, NewFile, NewFileSegment, PageCount, Read, SegmentFault,
    SetEndOfFile, SwapIn, SwapOut, Unlock, UnlockFile, Write],
  String USING [AppendChar, AppendString, EquivalentString],
  Table USING [
    Allocate, AddNotify, Base, Create, Destroy, DropNotify, Notifier,
    Overflow, Selector];

FileListsImpl: PROGRAM
    IMPORTS IODefs, ImageDefs, InlineDefs, SegmentDefs, String, Table
    EXPORTS FileLists =
  BEGIN OPEN FileLists;
  
 -- MANAGEMENT OF DYNAMICALLY ALLOCATED TABLES
  
  userListType: Table.Selector = 0;
  fileEntryType: Table.Selector = 1;
  includeFileType: Table.Selector = 2;
  incFileDescType: Table.Selector = 3;
  
  ulb, feb, ifb, ifdb: PUBLIC Table.Base;
  
  Tables: TYPE = Table.Selector[userListType..incFileDescType];
  Weights: ARRAY Tables OF CARDINAL ← [2, 4, 11, 3]; -- rough estimates
  
  tablesPages: PUBLIC SegmentDefs.PageCount;
  
  TablesPageStart: SegmentDefs.PageCount = 25;
  TablesPageStep: SegmentDefs.PageCount = 10;
  TablesPageLimit: SegmentDefs.PageCount = 175;
  
  tablesFile: SegmentDefs.FileHandle;
  tablesSegment: SegmentDefs.FileSegmentHandle;
  
  tablesOrigin: Table.Base;
  tablesSize: CARDINAL;
  
  EnlargingTables: PUBLIC SIGNAL = CODE;
  DoneEnlargingTables: PUBLIC SIGNAL = CODE;
  
  EnlargeTables: PUBLIC PROC =
    BEGIN OPEN SegmentDefs;
    neededPages: SegmentDefs.PageCount;
    neededPages ←
      IF tablesPages = 0 THEN TablesPageStart
      ELSE (tablesPages + TablesPageStep);
    IF neededPages > TablesPageLimit THEN
      {IODefs.WriteLine["Storage Overflow!"];  ImageDefs.StopMesa[]}
    ELSE
      BEGIN
      SIGNAL EnlargingTables;
      IF tablesPages # 0 THEN
	BEGIN
	Unlock[tablesSegment];
	SwapOut[tablesSegment];
	END;
      MoveFileSegment[tablesSegment, tablesSegment.base, neededPages];
      tablesPages ← neededPages;
      SwapIn[
	tablesSegment !
	  SegmentFault =>
	    BEGIN
	    SetEndOfFile[tablesSegment.file, tablesSegment.base + neededPages, 0];
	    RETRY;
	    END];
      tablesOrigin ← LOOPHOLE[FileSegmentAddress[tablesSegment]];
      tablesSize ← tablesPages*AltoDefs.PageSize;
      SIGNAL DoneEnlargingTables;
      END;
    END;
    
  UpdateTableBases: Table.Notifier =
    BEGIN
    ulb ← base[userListType];
    feb ← base[fileEntryType];
    ifb ← base[includeFileType];
    ifdb ← base[incFileDescType];
    END;

    
 -- HASHING
  
  HVSize: CARDINAL = 71;
  ulHashVec: ARRAY [0..HVSize) OF UserListPtr;
  feHashVec: ARRAY [0..HVSize) OF FE;
  ifdHashVec: ARRAY [0..HVSize) OF IncFileDesc;
  
  HashFn: PROC [s: STRING] RETURNS [[0..HVSize)] =
    BEGIN
    
    CharBits: PROC [CHARACTER, WORD] RETURNS [WORD] =
      LOOPHOLE[InlineDefs.BITAND];

    Mask: WORD = 337B;
    n: CARDINAL = s.length;
    v: WORD;
    v ← CharBits[s[0], Mask]*177B + CharBits[s[n - 1], Mask];
    RETURN[InlineDefs.BITXOR[v, n*17B] MOD HVSize]
    END;
    
  CompareString: PROC [a, b: STRING] RETURNS [{less, equal, greater}] =
    BEGIN
    l: CARDINAL = MIN[a.length, b.length];
    i: CARDINAL;
    ca, cb: CHARACTER;
    
    CharAnd: PROC [CHARACTER, WORD] RETURNS [CHARACTER] = InlineDefs.BITAND;
    FOR i IN [0..l) DO
      ca ← a[i];
      cb ← b[i];
      IF ca IN ['a..'z] THEN ca ← CharAnd[ca, 137B]; -- ignore case shifts
      IF cb IN ['a..'z] THEN cb ← CharAnd[cb, 137B];
      IF ca < cb THEN RETURN[less];
      IF ca > cb THEN RETURN[greater];
      ENDLOOP;
    RETURN[
      SELECT a.length FROM
	< b.length => less,
	= b.length => equal,
	ENDCASE => greater]
    END;

    
 -- INITIALIZATION AND FINALIZATION
  
  Initialize: PUBLIC PROC [debugging: BOOLEAN] =
    BEGIN OPEN SegmentDefs;
    i: CARDINAL;
    tablesFile ← NewFile[
      (IF debugging THEN "IncludeChecker.scratch$" ELSE "Swatee"),
      Read + Write + Append, DefaultVersion];
    LockFile[tablesFile];
    tablesSegment ← NewFileSegment[
      file: tablesFile, 
      base: DefaultBase, pages: 1,
      access: Read + Write];
    tablesPages ← 0;
    EnlargeTables[];
    Table.Create[
      [origin: tablesOrigin, size: tablesSize], DESCRIPTOR[Weights]];
    Table.AddNotify[UpdateTableBases];
    FOR i IN [0..HVSize) DO 
      ulHashVec[i] ← ULnil;
      feHashVec[i] ← FEnil;
      ifdHashVec[i] ← IFDnil;
      ENDLOOP;
    END;
    
  Finalize: PUBLIC PROC [debugging: BOOLEAN] =
    BEGIN OPEN SegmentDefs;
    Table.DropNotify[UpdateTableBases];
    Table.Destroy[];
    Unlock[tablesSegment];
    DeleteFileSegment[tablesSegment];
    UnlockFile[tablesFile];
    IF debugging THEN DestroyFile[tablesFile];
    END;

    
 -- USER-SPECIFIED FILE NAME LIST
  
  anyUserSpecifiedNames: BOOLEAN ← FALSE;
  
  InsertInUserList: PUBLIC PROC [fileName: STRING] =
    BEGIN
    mainPart: STRING ← [AltoFileDefs.FilenameChars + 1];
    i: CARDINAL;
    hash: [0..HVSize);
    pUL: UserListPtr;
    anyUserSpecifiedNames ← TRUE;
    FOR i IN [0..fileName.length) DO 
      IF fileName[i] = '. THEN EXIT;
      String.AppendChar[mainPart, fileName[i]];
      ENDLOOP;
    hash ← HashFn[mainPart];
    pUL ← ulHashVec[hash];
    WHILE pUL # ULnil DO
      IF String.EquivalentString[mainPart, @ulb[pUL].name] THEN RETURN;
      pUL ← ulb[pUL].next;
      ENDLOOP;
    ulHashVec[hash] ← NewUserListItem[mainPart, ulHashVec[hash]];
    END;
    
  NewUserListItem: PROC [
      name: STRING, next: UserListPtr]
      RETURNS [pUL: UserListPtr] =
    BEGIN
    pUL ← Table.Allocate[
      userListType, (SIZE[UserListItem] + (name.length + 1)/2) !
        Table.Overflow =>
	  BEGIN
	  EnlargeTables[];
	  RESUME [[origin: tablesOrigin, size: tablesSize]];
	  END];
    ulb[pUL] ← UserListItem[
      next: next, name: [length: 0, maxlength: name.length, text:]];
    String.AppendString[@ulb[pUL].name, name];
    RETURN[pUL];
    END;
    
  IsInUserList: PUBLIC PROC [fileName: STRING] RETURNS [BOOLEAN] =
    BEGIN
    IF ~anyUserSpecifiedNames THEN RETURN[TRUE]; -- process all bcds on disk
    RETURN[ScanUserList[fileName].found];
    END;
    
  ScanUserList: PROC [
      fileName: STRING]
      RETURNS [found: BOOLEAN, userListName: STRING] =
    BEGIN
    hash: [0..HVSize);
    pUL: UserListPtr;
    hash ← HashFn[fileName];
    FOR pUL ← ulHashVec[hash], ulb[pUL].next WHILE pUL # ULnil DO
      IF String.EquivalentString[fileName, @ulb[pUL].name] THEN
	RETURN[TRUE, @ulb[pUL].name];
      ENDLOOP;
    RETURN[FALSE, NIL];
    END;

    
 -- FILE LIST
  
  fileList: PUBLIC FE ← FEnil;
  
  InsertInFileList: PUBLIC PROC [name: STRING] RETURNS [fe: FE] =
    BEGIN
    found: BOOLEAN;
    userListName: STRING;
    i: [0..HVSize) ← HashFn[name];
    FOR fe ← feHashVec[i], feb[fe].next WHILE fe # FEnil DO
      IF String.EquivalentString[name, @feb[fe].name] THEN RETURN[fe];
      ENDLOOP;
    [found, userListName] ← ScanUserList[name]; -- use user's name if possible
    IF found THEN 
      BEGIN
      userNameCopy: STRING ← [AltoFileDefs.FilenameChars + 1];
      String.AppendString[to: userNameCopy, from: userListName];
      fe ← feHashVec[i] ← NewFE[userNameCopy, feHashVec[i]];
      END
    ELSE fe ← feHashVec[i] ← NewFE[name, feHashVec[i]];
    RETURN[fe];
    END;
    
  NewFE: PROC [name: STRING, next: FE] RETURNS [fe: FE] =
    BEGIN
    last: FE ← FEnil; -- follows fe
    FOR fe ← fileList, feb[fe].link UNTIL fe = FEnil DO
      SELECT CompareString[@feb[fe].name, name] FROM
	less => last ← fe;
	equal => ERROR;
	ENDCASE => EXIT;
      ENDLOOP;
    fe ← Table.Allocate[
      fileEntryType, (SIZE[FileEntry] + (name.length + 1)/2) !
        Table.Overflow =>
	  BEGIN
	  EnlargeTables[];
	  RESUME [[origin: tablesOrigin, size: tablesSize]];
	  END];
    IF last = FEnil THEN
      BEGIN
      feb[fe] ← FileEntry[
	next: next, link: fileList,
	name: StringBody[length: 0, maxlength: name.length, text:]];
      fileList ← fe;
      END
    ELSE
      BEGIN
      feb[fe] ← FileEntry[
	next: next, link: feb[last].link,
	name: [length: 0, maxlength: name.length, text:]];
      feb[last].link ← fe;
      END;
    String.AppendString[@feb[fe].name, name];
    RETURN[fe];
    END;

    
 -- INCLUDES/INCLUDED BY LISTS
  
  InsertIncludeFileItem: PUBLIC PROC [
        incList: IncFile, 
        fe: FE, feName: STRING, stamp: BcdDefs.VersionStamp,
        fileOpenedByCompiler: BOOLEAN] 
      RETURNS [IncFile] =
    BEGIN
    p: IncFile;
    incListLast: IncFile ← IFnil;
    incListFile: FE;
    FOR p ← incList, ifb[p].link UNTIL p = IFnil DO
      incListFile ← ifdb[ifb[p].includeFileDesc].file;
      SELECT CompareString[@feb[incListFile].name, feName] FROM
	less => incListLast ← p;
	equal => RETURN[incList];
	ENDCASE => EXIT;
      ENDLOOP;
    p ← Table.Allocate[
      includeFileType, SIZE[IncludeFileItem] !
        Table.Overflow => -- enlarge space for tables
	  BEGIN
	  EnlargeTables[];
	  RESUME [[origin: tablesOrigin, size: tablesSize]];
	  END];
    IF incListLast = IFnil THEN
      BEGIN
      ifb[p] ← IncludeFileItem[
	link: incList, includeFileDesc: AddIFD[fe, feName, stamp],
	fileOpenedByCompiler: fileOpenedByCompiler];
      incList ← p;
      END
    ELSE
      BEGIN
      ifb[p] ← IncludeFileItem[
	link: ifb[incListLast].link, 
        includeFileDesc: AddIFD[fe, feName, stamp],
	fileOpenedByCompiler: fileOpenedByCompiler];
      ifb[incListLast].link ← p;
      END;
    RETURN[incList];
    END;

    
 -- INCLUDED FILE DESCRIPTORS (avoid duplication of data in inc/inc by lists)
  
  AddIFD: PROC [
        fe: FE, feName: STRING, stamp: BcdDefs.VersionStamp]
      RETURNS [d: IncFileDesc] =
    BEGIN
    i: [0..HVSize) ← HashFn[feName];
    incFile: FE;
    d ← ifdHashVec[i];
    WHILE d # IFDnil DO
      incFile ← ifdb[d].file;
      IF String.EquivalentString[feName, @feb[incFile].name] 
        AND stamp = ifdb[d].stamp THEN RETURN[d];
      d ← ifdb[d].next;
      ENDLOOP;
    d ← ifdHashVec[i] ← NewIFD[fe, stamp, ifdHashVec[i]]; -- get new ifd
    RETURN[d];
    END;
    
  NewIFD: PROC [
        fe: FE, stamp: BcdDefs.VersionStamp, next: IncFileDesc]
      RETURNS [d: IncFileDesc] =
    BEGIN
    d ← Table.Allocate[
      incFileDescType, SIZE[IncFileDescItem] !
        Table.Overflow =>
	  BEGIN
	  EnlargeTables[];
	  RESUME [[origin: tablesOrigin, size: tablesSize]];
	  END];
    ifdb[d] ← IncFileDescItem[next: next, file: fe, stamp: stamp];
    RETURN[d];
    END;
    
  END.