-- BcdTab.Mesa
-- last edited by Satterthwaite on September 14, 1982 9:19 am
-- last edited by Lewis on 10-Dec-80 20:11:41

DIRECTORY
  Alloc: TYPE USING [AddNotify, DropNotify, Handle, Notifier, Trim, Words],
  BcdDefs: TYPE USING [httype, PackedString, sstype],
  Environment: TYPE USING [charsPerWord],
  Inline: TYPE USING [BITAND, BITXOR],
  Strings: TYPE USING [
    AppendChar, AppendSubString, EqualSubStrings, EquivalentSubStrings, String,
    SubString, SubStringDescriptor],
  Symbols: TYPE USING [HTIndex, HTNull, HTRecord, HVIndex, HVLength],
  SymbolOps: TYPE USING [],
  Table: TYPE USING [Base, Index];

BcdTab: PROGRAM 
    IMPORTS Alloc, Inline, Strings 
    EXPORTS SymbolOps = {
  OPEN Symbols;

  SubString: TYPE ~ Strings.SubString;
  SubStringDescriptor: TYPE ~ Strings.SubStringDescriptor;

  -- tables defining the current symbol table

  table: Alloc.Handle;
  
  hashVec: LONG POINTER TO ARRAY HVIndex OF HTIndex;
  ht: LONG DESCRIPTOR FOR ARRAY --HTIndex-- OF HTRecord;

  htb: Table.Base; -- hash table

  ssb: LONG POINTER TO BcdDefs.PackedString; -- id string

  UpdateBases: Alloc.Notifier ~ {
    OPEN BcdDefs;
    htb ← base[httype];
    ssb ← LOOPHOLE[base[sstype]];
    hashVec ← htb;
    ht ← DESCRIPTOR[htb + hashVec↑.LENGTH*HTIndex.SIZE, ht.LENGTH]};

  AllocateHash: PROC RETURNS [hti: HTIndex] ~ {
    next: Table.Index ~ table.Words[BcdDefs.httype, HTRecord.SIZE];
    hti ← ht.LENGTH;
    ht ← DESCRIPTOR[ht.BASE, ht.LENGTH + 1];
    ht[hti] ← HTRecord[link~HTNull, offset~ssb.string.length+1];
    RETURN [hti - 1]};

  -- variables for building the symbol string

  ssw: Table.Index;

  initialized: BOOL ← FALSE;

  Initialize: PUBLIC PROC [ownTable: Alloc.Handle] ~ {
    IF initialized THEN Finalize[];  hashVec ← NIL;
    table ← ownTable; table.AddNotify[UpdateBases];
    Reset[];
    initialized ← TRUE};

  Finalize: PUBLIC PROC ~ {
    table.DropNotify[UpdateBases];  table ← NIL;
    initialized ← FALSE};

  Reset: PUBLIC PROC ~ {
    nullSS: SubStringDescriptor ← [base~"null"L, offset~0, length~0];
    table.Trim[BcdDefs.sstype, 0];
    table.Trim[BcdDefs.httype, 0];
    [] ← table.Words[BcdDefs.httype, HVLength*HTIndex.SIZE];
    hashVec ← htb;
    hashVec↑ ← ALL[HTNull];
    ht ← DESCRIPTOR[htb + hashVec↑.LENGTH*HTIndex.SIZE, 0];
    ssw ← table.Words[BcdDefs.sstype, StringBody.SIZE] + StringBody.SIZE;
    ssb.string ← [length~0, maxlength~0, text~];
    [] ← AllocateHash[];
    IF EnterString[@nullSS] # HTNull THEN ERROR};


   -- hash entry creation

  EnterString: PUBLIC PROC [s: SubString] RETURNS [hti: HTIndex] ~ {
    hvi: HVIndex ~ HashValue[s];
    desc: SubStringDescriptor ← [base~@ssb.string, offset~, length~];
    charsPerWord: CARDINAL ~ Environment.charsPerWord;
    offset, length, nw: CARDINAL;
    ssi: Table.Index;
    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 {
      IF (ssi ← table.Words[BcdDefs.sstype, nw]) # ssw THEN ERROR;
      ssw ← ssw + nw;
      ssb.string ← [
        text~,
	length~ssb.string.length, maxlength~ssb.string.maxlength+nw*charsPerWord]};
    Strings.AppendChar[@ssb.string, LOOPHOLE[s.length, CHAR]];
    Strings.AppendSubString[@ssb.string, s];
    hti ← AllocateHash[];
    ht[hti].link ← hashVec[hvi];
    hashVec[hvi] ← hti;
    RETURN};


  -- the following copied from SymbolPack.mesa

  ignoreCases: BOOL ← FALSE;

  HashValue: PROC [s: SubString] RETURNS [HVIndex] ~ {
    CharBits: PROC [CHAR, WORD] RETURNS [WORD] ~ LOOPHOLE[Inline.BITAND];
    mask: WORD ~ 0DFh; -- masks out ASCII case shifts
    n: CARDINAL ~ s.length;
    b: Strings.String ~ s.base;
    v: WORD ~ CharBits[b[s.offset], mask]*7fh + CharBits[b[s.offset + (n-1)], mask];
    RETURN [Inline.BITXOR[v, n*0fh] MOD hashVec↑.LENGTH]};

  FindString: PUBLIC PROC [s: SubString] RETURNS [found: BOOL, hti: HTIndex] ~ {
    desc: SubStringDescriptor;
    ss: SubString ~ @desc;
    FOR hti ← hashVec[HashValue[s]], ht[hti].link UNTIL hti = HTNull DO
      SubStringForHash[ss, hti];
      found ← IF ignoreCases
	THEN Strings.EquivalentSubStrings[s, ss]
	ELSE Strings.EqualSubStrings[s, ss];
      IF found THEN RETURN;
      ENDLOOP;
    RETURN [FALSE, HTNull]};

  FindEquivalentString: PUBLIC PROC [s: SubString] RETURNS [found: BOOL, hti: HTIndex] ~ {
    oldcase: BOOL ~ ignoreCases;
    ignoreCases ← TRUE;
    [found, hti] ← FindString[s];
    ignoreCases ← oldcase;
    RETURN};

  SubStringForHash: PUBLIC PROC [s: SubString, hti: HTIndex] ~ {
    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]}};

  }.