-- 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 14-Dec-80 19:27:35
-- Copyright  Xerox Corporation 1979, 1980

DIRECTORY
  BcdDefs USING [VersionStamp],
  Environment USING [PageCount, wordsPerPage],
  Inline USING [BITAND, BITXOR],
  FileLists,
  Segments USING [PageCount],
  Space USING [
    Create, Delete, GetHandle, Handle, LongPointer, Map, 
    PageFromLongPointer, virtualMemory],
  LongString USING [AppendChar, AppendString, EquivalentString],
  IncludeCheckerTable USING [
    Allocate, AddNotify, Base, Create, Destroy, DropNotify, Notifier,
    Region, Selector];

FileListsImpl: PROGRAM
    IMPORTS Inline, Space, LongString, IncludeCheckerTable
    EXPORTS FileLists =
  BEGIN  OPEN FileLists;
  
  FilenameChars: CARDINAL = 39;
  
  
 -- DYNAMICALLY ALLOCATED TABLES
  
  userListType:    IncludeCheckerTable.Selector = 0;
  fileEntryType:   IncludeCheckerTable.Selector = 1;
  includeFileType: IncludeCheckerTable.Selector = 2;
  incFileDescType: IncludeCheckerTable.Selector = 3;
  
    
  ulb, feb, ifb, ifdb: PUBLIC IncludeCheckerTable.Base;
  
  UpdateTableBases: IncludeCheckerTable.Notifier =
    BEGIN
    ulb _ base[userListType];
    feb _ base[fileEntryType];
    ifb _ base[includeFileType];
    ifdb _ base[incFileDescType];
    END;
    

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

    Mask: WORD = 337B;
    n: CARDINAL = s.length;
    v: WORD;
    v _ CharBits[s[0], Mask]*177B + CharBits[s[n - 1], Mask];
    RETURN[Inline.BITXOR[v, n*17B] MOD HVSize]
    END;
    
  CompareString: PROC [a, b: LONG STRING] RETURNS [{less, equal, greater}] =
    BEGIN
    l: CARDINAL = MIN[a.length, b.length];
    i: CARDINAL;
    ca, cb: CHARACTER;
    
    CharAnd: PROC [CHARACTER, WORD] RETURNS [CHARACTER] = Inline.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
  
  TablePages: Segments.PageCount = 150;
  tableSpace: LONG POINTER _ NIL;
  
  Initialize: PUBLIC PROC =
    BEGIN
    tableRegion: IncludeCheckerTable.Region;
    TableWeights: ARRAY [0..3] OF CARDINAL _ [2, 4, 11, 3]; -- empiracal
    tableSpace _ GetTableStorage[pages: TablePages];
    tableRegion _ [
      origin: LOOPHOLE[tableSpace, IncludeCheckerTable.Base],
      size: (TablePages * Environment.wordsPerPage)];
    IncludeCheckerTable.Create[
      region: tableRegion, 
      weights: DESCRIPTOR[TableWeights]];
    IncludeCheckerTable.AddNotify[UpdateTableBases];
    FOR i: CARDINAL IN [0..HVSize) DO 
      ulHashVec[i] _ ULnil;
      feHashVec[i] _ FEnil;
      ifdHashVec[i] _ IFDnil;
      ENDLOOP;
    userList _ userListEnd _ ULnil;
    fileList _ FEnil;
    END;
    
  Finalize: PUBLIC PROC =
    BEGIN
    IncludeCheckerTable.DropNotify[UpdateTableBases];
    IncludeCheckerTable.Destroy[];
    FreeTableStorage[tableSpace];
    END;

  GetTableStorage: PROC [
      pages: Environment.PageCount] RETURNS [base: LONG POINTER] =
    BEGIN
    new: Space.Handle _ Space.Create[
      size: pages, parent: Space.virtualMemory];
    Space.Map[new];
    base _ Space.LongPointer[new];
    END;

  FreeTableStorage: PROC [base: LONG POINTER] = 
     {Space.Delete[Space.GetHandle[Space.PageFromLongPointer[base]]]};

    
 -- USER-SPECIFIED FILE NAME LIST
  
  userList: UserListPtr _ ULnil;
  userListEnd: UserListPtr _ ULnil;
  mainPart: STRING _ [FilenameChars + 1];
  
  InsertInUserList: PUBLIC PROC [fileName: LONG STRING] =
    BEGIN
    hash: [0..HVSize);
    newItem: UserListPtr;
    mainPart.length _ 0;
    FOR i: CARDINAL IN [0..fileName.length) DO 
      IF fileName[i] = '. THEN EXIT;
      LongString.AppendChar[mainPart, fileName[i]];
      ENDLOOP;
    hash _ HashFn[mainPart];
    FOR p: UserListPtr _ ulHashVec[hash], ulb[p].next WHILE p # ULnil DO
      IF LongString.EquivalentString[mainPart, @ulb[p].name] THEN RETURN;
      ENDLOOP;
    newItem _ ulHashVec[hash] _ NewUserListItem[mainPart, ulHashVec[hash]];
    IF userList = ULnil THEN userList _ userListEnd _ newItem
    ELSE 
      BEGIN
      ulb[userListEnd].link _ newItem;
      userListEnd _ newItem;
      END;
    END;
    
  NewUserListItem: PROC [
      name: LONG STRING, next: UserListPtr] RETURNS [p: UserListPtr] =
    BEGIN
    p _ IncludeCheckerTable.Allocate[userListType, (SIZE[UserListItem] + (name.length + 1)/2)];
    ulb[p] _ UserListItem[
      next: next, 
      link: ULnil, 
      name: [length: 0, maxlength: name.length, text: ]];
    LongString.AppendString[@ulb[p].name, name];
    RETURN[p];
    END;
    
  IsInUserList: PUBLIC PROC [fileName: LONG STRING] RETURNS [BOOLEAN] =
    BEGIN
    IF userList = ULnil THEN RETURN[FALSE]
    ELSE RETURN[ScanUserList[fileName].found];
    END;
    
  ScanUserList: PROC [
      fileName: LONG STRING]
      RETURNS [found: BOOLEAN, userListName: LONG STRING] =
    BEGIN
    hash: [0..HVSize);
    IF userList # ULnil THEN
      BEGIN
      hash _ HashFn[fileName];
      FOR p: UserListPtr _ ulHashVec[hash], ulb[p].next WHILE p # ULnil DO
        IF LongString.EquivalentString[fileName, @ulb[p].name] THEN
	  RETURN[TRUE, @ulb[p].name];
        ENDLOOP;
      END;
    RETURN[FALSE, NIL];
    END;
    
  EnumerateUserList: PUBLIC PROC [
      userProc: PROC[LONG STRING] RETURNS [BOOLEAN]] =
    BEGIN
    FOR p: UserListPtr _ userList, ulb[p].link WHILE p # ULnil DO
      IF userProc[@ulb[p].name] THEN RETURN;
      ENDLOOP;
    END;
    
  UserListLength: PUBLIC PROC RETURNS [count: CARDINAL] =
    BEGIN
     
    AddOne: PROC[LONG STRING] RETURNS [stop: BOOLEAN] = 
      {count _ count+1;  RETURN[FALSE]};
    
    count _ 0;
    IF userList # ULnil THEN EnumerateUserList[AddOne];
    RETURN[count];
    END;

    
 -- FILE LIST
  
  fileList: PUBLIC FE _ FEnil;
  userNameCopy: STRING _ [FilenameChars + 1];
  
  InsertInFileList: PUBLIC PROC [name: LONG STRING] RETURNS [fe: FE] =
    BEGIN
    found: BOOLEAN;
    userListName: LONG STRING;
    hash: [0..HVSize) _ HashFn[name];
    userNameCopy.length _ 0;
    FOR fe _ feHashVec[hash], feb[fe].next WHILE fe # FEnil DO
      IF LongString.EquivalentString[name, @feb[fe].name] THEN RETURN[fe];
      ENDLOOP;
    [found, userListName] _ ScanUserList[name]; -- use user's name if possible
    IF found THEN 
      BEGIN
      LongString.AppendString[to: userNameCopy, from: userListName];
      fe _ feHashVec[hash] _ NewFE[userNameCopy, feHashVec[hash]];
      END
    ELSE fe _ feHashVec[hash] _ NewFE[name, feHashVec[hash]];
    RETURN[fe];
    END;
    
  NewFE: PROC [name: LONG 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 _ IncludeCheckerTable.Allocate[fileEntryType, (SIZE[FileEntry] + (name.length + 1)/2)];
    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;
    LongString.AppendString[@feb[fe].name, name];
    RETURN[fe];
    END;

    
 -- INCLUDES/INCLUDED BY LISTS
  
  InsertIncludeFileItem: PUBLIC PROC [
        incList: IncFile, 
        fe: FE, feName: LONG 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 _ IncludeCheckerTable.Allocate[includeFileType, SIZE[IncludeFileItem]];
    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 (avoids duplicating data in includes/included by lists)
  
  AddIFD: PROC [
        fe: FE, feName: LONG STRING, stamp: BcdDefs.VersionStamp]
      RETURNS [d: IncFileDesc] =
    BEGIN
    i: [0..HVSize) _ HashFn[feName];
    incFile: FE;
    FOR d _ ifdHashVec[i], ifdb[d].next UNTIL d = IFDnil DO
      incFile _ ifdb[d].file;
      IF LongString.EquivalentString[feName, @feb[incFile].name] 
        AND stamp = ifdb[d].stamp THEN RETURN[d];
      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 _ IncludeCheckerTable.Allocate[incFileDescType, SIZE[IncFileDescItem]];
    ifdb[d] _ IncFileDescItem[next: next, file: fe, stamp: stamp];
    RETURN[d];
    END;
    
  END.