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