-- SymTab.Mesa  Edited by Lewis on 31-Dec-80 10:54:41
-- last edited by Levin on July 6, 1982 4:49 pm

DIRECTORY
  Alloc USING [AddNotify, DropNotify, Handle, Notifier, Trim, Words],
  Inline USING [BITAND, BITXOR],
  PackagerDefs USING [globalData, packhttype, packsstype],
  PackEnviron USING [BcdStringHandle, CharsPerWord],
  Strings USING [
    AppendChar, AppendSubString, EqualSubStrings, EquivalentSubStrings,
    String, SubString, SubStringDescriptor],
  SymTabDefs USING [HTIndex, HTNull, HTRecord, HVIndex, HVLength],
  SymTabOps,
  Table USING [Base, Index];

SymTab: PROGRAM 
    IMPORTS Alloc, Inline, PackagerDefs, Strings 
    EXPORTS SymTabOps
    SHARES SymTabDefs =
  BEGIN OPEN SymTabDefs, PackagerDefs;

  SubString: TYPE = Strings.SubString;
  SubStringDescriptor: TYPE = Strings.SubStringDescriptor;
  
  table: Alloc.Handle _ NIL;


 -- Tables defining the current symbol table

  hashVec: LONG DESCRIPTOR FOR ARRAY --HVIndex-- OF HTIndex;
  ht: LONG DESCRIPTOR FOR ARRAY --HTIndex-- OF HTRecord;

  htb: Table.Base;                   -- hash table
  ssb: PackEnviron.BcdStringHandle;  -- id string

  UpdateBases: Alloc.Notifier =
    BEGIN
    htb     _ base[packhttype];
    ssb     _ base[packsstype];
    hashVec _ DESCRIPTOR[htb, LENGTH[hashVec]];
    ht      _ DESCRIPTOR[htb + LENGTH[hashVec]*SIZE[HTIndex], LENGTH[ht]];
    END;

  AllocateHash: PROCEDURE RETURNS [hti: HTIndex] =
    BEGIN
    next: Table.Index = table.Words[packhttype, SIZE[HTRecord]];
    hti _ LENGTH[ht];
    IF hti*SIZE[HTRecord]+LENGTH[hashVec] # LOOPHOLE[next, INTEGER] THEN
      ERROR;
    ht _ DESCRIPTOR[BASE[ht], LENGTH[ht]+1];
    ht[hti] _ HTRecord[link: HTNull, offset: ssb.string.length+1];
    RETURN[hti - 1];
    END;


 -- Variables for building the symbol string

  ssw: Table.Index;

  tableOpen: BOOLEAN _ FALSE;

  Initialize: PUBLIC PROCEDURE = 
    BEGIN 
    IF tableOpen THEN Finalize[];
    hashVec _ DESCRIPTOR[NIL, HVLength];
    table _ PackagerDefs.globalData.ownTable;
    table.AddNotify[UpdateBases];
    Reset[];
    tableOpen _ TRUE;
    END;
  
  Finalize: PUBLIC PROCEDURE = 
    BEGIN
    tableOpen _ FALSE;
    table.DropNotify[UpdateBases];
    table _ NIL;
    END;
  
  Reset: PUBLIC PROCEDURE = 
    BEGIN
    nullss: SubStringDescriptor _ [base: "null"L, offset: 0, length: 0];
    table.Trim[packsstype, 0];
    table.Trim[packhttype, 0];
    [] _ table.Words[packhttype, HVLength*SIZE[HTIndex]];
    hashVec _ DESCRIPTOR[htb, HVLength];
    FOR i: HVIndex IN HVIndex DO hashVec[i] _ HTNull ENDLOOP;
    ht _ DESCRIPTOR[htb+LENGTH[hashVec]*SIZE[HTIndex], 0];
    ssw _ table.Words[packsstype, SIZE[StringBody]] + SIZE[StringBody];
    ssb.string _ [length: 0, maxlength: 0, text: ];
    [] _ AllocateHash[];
    IF EnterString[@nullss] # HTNull THEN ERROR;
    END;
  

 -- Hash entry creation

  EnterString: PUBLIC PROCEDURE [s: SubString] RETURNS [hti: HTIndex] =
    BEGIN
    hvi: HVIndex;
    desc: SubStringDescriptor _ [base: @ssb.string, offset:, length:];
    CharsPerWord: CARDINAL = PackEnviron.CharsPerWord;
    offset, length, nw: CARDINAL;
    ssi: Table.Index;
    hvi _ HashValue[s];
    FOR hti _ hashVec[hvi], ht[hti].link UNTIL hti = HTNull DO
      SubStringForHash[@desc, hti];
      IF Strings.EqualSubStrings[s, @desc] THEN RETURN[hti];
      ENDLOOP;
    offset _ ssb.string.length;  length _ s.length + 1;
    nw _ (offset+length+(CharsPerWord-1) - ssb.string.maxlength)/CharsPerWord;
    IF nw # 0 THEN
      BEGIN  
      IF (ssi _ table.Words[packsstype, nw]) # ssw THEN ERROR;
      ssw _ ssw + nw;
      ssb.string _ [
	length: ssb.string.length, 
	text: ,
	maxlength: ssb.string.maxlength + nw*CharsPerWord];
      END;
    Strings.AppendChar[@ssb.string, LOOPHOLE[s.length, CHARACTER]];
    Strings.AppendSubString[@ssb.string, s];
    hti _ AllocateHash[];
    ht[hti].link _ hashVec[hvi];  hashVec[hvi] _ hti;
    END;

  ignoreCases: BOOLEAN _ FALSE;

  HashValue: PROC [s: SubString] RETURNS [HVIndex] =
    BEGIN
    CharMask: PROC [CHARACTER, WORD] RETURNS [CARDINAL] =
      LOOPHOLE[Inline.BITAND];
    mask: WORD = 137B;                -- masks out ASCII case shifts
    n: CARDINAL = s.length;
    b: Strings.String = s.base;
    v: WORD _ 
      CharMask[b[s.offset], mask]*177B + CharMask[b[s.offset+(n-1)], mask];
    RETURN[Inline.BITXOR[v, n*17B] MOD LENGTH[hashVec]]
    END;

  FindString: PUBLIC PROC [
      s: SubString] RETURNS [found: BOOLEAN, hti: HTIndex] =
    BEGIN
    desc: SubStringDescriptor;
    ss: SubString = @desc;
    hti _ hashVec[HashValue[s]];
    WHILE hti # HTNull
      DO
      SubStringForHash[ss, hti];
      found _
        IF ignoreCases THEN Strings.EquivalentSubStrings[s,ss]
        ELSE Strings.EqualSubStrings[s,ss];
      IF found THEN RETURN;
      hti _ ht[hti].link;
      ENDLOOP;
    RETURN[FALSE, HTNull]
    END;

  FindEquivalentString: PUBLIC PROCEDURE [
      s: SubString] RETURNS [found: BOOLEAN, hti: HTIndex] =
    BEGIN
    oldcase: BOOLEAN = ignoreCases;
    ignoreCases _ TRUE;
    [found, hti] _ FindString[s];
    ignoreCases _ oldcase;
    END;

  SubStringForHash: PUBLIC PROCEDURE [s: SubString, hti: HTIndex] =
    BEGIN -- gets string for hash table entry
    s.base _ @ssb.string;
    IF hti = HTNull THEN s.offset _ s.length _ 0
    ELSE {s.offset _ ht[hti].offset;  s.length _ ssb.size[ht[hti].offset]};
    END;

  END.