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