-- file ProtoHashTab.mesa
-- last edited by Satterthwaite, December 29, 1982 12:45 pm

DIRECTORY
  Alloc: TYPE USING [
    Base, Handle, Index, Notifier, Selector, AddNotify, DropNotify, Trim, Words],
  BcdOps: TYPE USING [NameString],
  Environment: TYPE USING [charsPerWord],
  HashOps: TYPE USING [],
  HashTypes: TYPE USING [HTIndex, htNull, hvLength],
  Inline: TYPE USING [BITAND, BITXOR],
  Strings: TYPE USING [
    String, SubString, SubStringDescriptor,
    AppendChar, AppendSubString, EqualSubStrings, EquivalentSubStrings];

HashTab: PROGRAM 
    IMPORTS Alloc, Inline, Strings 
    EXPORTS HashOps={
  OPEN HashTypes;

 -- types
 
  HTRecord: TYPE~RECORD [
    link: HTIndex,
    offset: CARDINAL];  -- gives both loc and length of name in packed string 

  HVIndex: TYPE~NAT[0..hvLength);

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

 -- tables defining the current symbol table

  table: Alloc.Handle _ NIL;
  htType, ssType: Alloc.Selector;

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

  htb: Alloc.Base;         	-- hash table
  ssb: BcdOps.NameString;  -- id string

  UpdateBases: Alloc.Notifier~{
    htb _ base[htType];  ssb _ base[ssType];
    hashVec _ htb;
    ht _ DESCRIPTOR[htb + hashVec^.LENGTH*HTIndex.SIZE, ht.LENGTH]};

  AllocateHash: PROC RETURNS [hti: HTIndex]~{
    next: Alloc.Index~table.Words[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: Alloc.Index;

  initialized: BOOL_FALSE;

  Initialize: PUBLIC PROC [ownTable: Alloc.Handle, htTable, ssTable: Alloc.Selector]~{ 
    IF initialized THEN Finalize[];  hashVec _ NIL;
    table _ ownTable;  htType _ htTable; ssType _ ssTable;
    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[ssType, 0];
    table.Trim[htType, 0];
    [] _ table.Words[htType, hvLength*HTIndex.SIZE];
    hashVec _ htb;
    hashVec^ _ ALL[htNull];
    ht _ DESCRIPTOR[htb + hashVec^.LENGTH*HTIndex.SIZE, 0];
    ssw _ table.Words[ssType, StringBody[0].SIZE] + StringBody[0].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: Alloc.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[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

  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;
    IF n # 0 THEN v _ v + CharBits[b[s.offset+(n-1)], mask];
    RETURN [Inline.BITXOR[v, n*0Fh] MOD hashVec^.LENGTH]};

  FindString: PUBLIC PROC [s: SubString] RETURNS [hti: HTIndex]~{
    desc: SubStringDescriptor;
    ss: SubString~@desc;
    FOR hti _ hashVec[HashValue[s]], ht[hti].link UNTIL hti = htNull DO
      SubStringForHash[ss, hti];
      IF Strings.EqualSubStrings[s, ss] THEN RETURN;
      ENDLOOP;
    RETURN [htNull]};

  FindEquivalentString: PUBLIC PROC [s: SubString] RETURNS [hti: HTIndex]~{
    desc: SubStringDescriptor;
    ss: SubString~@desc;
    FOR hti _ hashVec[HashValue[s]], ht[hti].link UNTIL hti = htNull DO
      SubStringForHash[ss, hti];
      IF Strings.EquivalentSubStrings[s, ss] THEN RETURN;
      ENDLOOP;
    RETURN [htNull]};

  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]}};

  }.