-- 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.