-- BcdTab.Mesa
-- last edited by Sandman on October 8, 1980  4:06 PM
-- Copyright  Xerox Corporation 1979, 1980

DIRECTORY
  AltoDefs USING [CharsPerWord],
  BcdDefs USING [httype, sstype],
  BcdOps USING [NameString],
  InlineDefs USING [BITAND, BITXOR],
  Strings USING [
    AppendChar, AppendSubString, EqualSubStrings, EquivalentSubStrings, String,
    SubString, SubStringDescriptor],
  Symbols: FROM "bcdsymbols" USING [HTIndex, HTNull, HTRecord, HVIndex, HVLength],
  SymbolOps: FROM "bcdsymbolops" USING [],
  Table USING [AddNotify, Allocate, Base, DropNotify, Index, Notifier, Trim];

BcdTab: PROGRAM IMPORTS InlineDefs, Table, Strings EXPORTS SymbolOps =
  BEGIN OPEN Symbols;

  SubString: TYPE = Strings.SubString;
  SubStringDescriptor: TYPE = Strings.SubStringDescriptor;

  -- tables defining the current symbol table

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

  htb: Table.Base; -- hash table

  ssb: BcdOps.NameString; -- id string

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

  AllocateHash: PROC RETURNS [hti: HTIndex] = {
    next: Table.Index = Table.Allocate[BcdDefs.httype, 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]};

  -- variables for building the symbol string

  ssw: Table.Index;

  initialized: BOOLEAN ← FALSE;

  Initialize: PUBLIC PROC = {
    IF initialized THEN Finalize[];
    hashVec ← NIL;
    Table.AddNotify[UpdateBases];
    Reset[];
    initialized ← TRUE};

  Finalize: PUBLIC PROC = {initialized ← FALSE; Table.DropNotify[UpdateBases]};

  Reset: PUBLIC PROC = {
    nullSS: SubStringDescriptor ← [base: ""L, offset:, length: 0];
    Table.Trim[BcdDefs.sstype, 0];
    Table.Trim[BcdDefs.httype, 0];
    [] ← Table.Allocate[BcdDefs.httype, HVLength*SIZE[HTIndex]];
    hashVec ← htb;
    hashVec↑ ← ALL[HTNull];
    ht ← DESCRIPTOR[htb + LENGTH[hashVec↑]*SIZE[HTIndex], 0];
    ssw ← Table.Allocate[BcdDefs.sstype, SIZE[StringBody]] + SIZE[StringBody];
    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 = AltoDefs.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.Allocate[BcdDefs.sstype, nw]) # ssw THEN ERROR;
      ssw ← ssw + nw;
      ssb.string ←
	[length: ssb.string.length, text:,
	  maxlength: ssb.string.maxlength + nw*CharsPerWord]};
    Strings.AppendChar[@ssb.string, LOOPHOLE[s.length, CHARACTER]];
    Strings.AppendSubString[@ssb.string, s];
    hti ← AllocateHash[];
    ht[hti].link ← hashVec[hvi];
    hashVec[hvi] ← hti;
    RETURN};

  -- the following copied from symboltable.mesa

  ignoreCases: BOOLEAN ← FALSE;

  HashValue: PROC [s: SubString] RETURNS [HVIndex] = {
    CharBits: PROC [CHARACTER, WORD] RETURNS [WORD] = LOOPHOLE[InlineDefs.BITAND];
    Mask: WORD = 337B; -- masks out ASCII case shifts
    n: CARDINAL = s.length;
    b: Strings.String = s.base;
    v: WORD =
      CharBits[b[s.offset], Mask]*177B + CharBits[b[s.offset + (n - 1)], Mask];
    RETURN[InlineDefs.BITXOR[v, n*17B] MOD LENGTH[hashVec↑]]};

  FindString: PUBLIC PROC [s: SubString] RETURNS [found: BOOLEAN, hti: HTIndex] =
    {
    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]};

  FindEquivalentString: PUBLIC PROC [s: SubString]
    RETURNS [found: BOOLEAN, hti: HTIndex] = {
    oldcase: BOOLEAN = 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]}};


  END.