DIRECTORY Alloc USING [Base, Handle, Index, Notifier, Selector, AddNotify, DropNotify, Trim, Words], Basics USING [charsPerWord], BcdDefs USING [NameString], ConvertUnsafe USING [AppendRope, EqualSubStrings, SubString, AppendSubString], HashOps USING [], HashTypes USING [HTIndex, htNull, hvLength], PrincOpsUtils USING [BITAND, BITXOR], Rope USING [FromChar]; HashTab: PROGRAM IMPORTS Alloc, ConvertUnsafe, PrincOpsUtils, Rope EXPORTS HashOps = { OPEN HashTypes; HTRecord: TYPE~RECORD [ link: HTIndex, offset: CARDINAL]; -- gives both loc and length of name in packed string HVIndex: TYPE~NAT[0..hvLength); SubString: TYPE~ConvertUnsafe.SubString; 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: BcdDefs.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]}; 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: SubString_[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}; EnterString: PUBLIC PROC [s: SubString] RETURNS [hti: HTIndex]~{ hvi: HVIndex~HashValue[s]; desc: SubString_[base~@ssb.string, offset~, length~]; charsPerWord: CARDINAL~Basics.charsPerWord; offset, length, nw: CARDINAL; ssi: Alloc.Index; FOR hti _ hashVec[hvi], ht[hti].link UNTIL hti = htNull DO desc _ SubStringForHash[hti]; IF ConvertUnsafe.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]}; ConvertUnsafe.AppendRope[@ssb.string, Rope.FromChar[LOOPHOLE[s.length, CHAR]]]; ConvertUnsafe.AppendSubString[@ssb.string, s]; hti _ AllocateHash[]; ht[hti].link _ hashVec[hvi]; hashVec[hvi] _ hti; RETURN}; HashValue: PROC [s: SubString] RETURNS [HVIndex]~{ CharBits: PROC [CHAR, WORD] RETURNS [WORD]~LOOPHOLE[PrincOpsUtils.BITAND]; mask: WORD~0DFh; -- masks out ASCII case shifts n: CARDINAL~s.length; b: LONG 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 [PrincOpsUtils.BITXOR[v, n*0Fh] MOD hashVec^.LENGTH]}; FindString: PUBLIC PROC [s: SubString] RETURNS [hti: HTIndex]~{ ss: SubString; FOR hti _ hashVec[HashValue[s]], ht[hti].link UNTIL hti = htNull DO ss _ SubStringForHash[hti]; IF ConvertUnsafe.EqualSubStrings[s, ss] THEN RETURN; ENDLOOP; RETURN [htNull]}; FindEquivalentString: PUBLIC PROC [s: SubString] RETURNS [hti: HTIndex]~{ ss: SubString; FOR hti _ hashVec[HashValue[s]], ht[hti].link UNTIL hti = htNull DO ss _ SubStringForHash[hti]; IF ConvertUnsafe.EqualSubStrings[s, ss, FALSE] THEN RETURN; ENDLOOP; RETURN [htNull]}; SubStringForHash: PUBLIC PROC [hti: HTIndex] RETURNS[s: SubString] ~{ 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]}}; }. ProtoHashTab.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Satterthwaite, December 29, 1982 12:45 pm Maxwell, August 11, 1983 2:59 pm Paul Rovner, September 22, 1983 9:43 pm Russ Atkinson (RRA) March 7, 1985 0:08:58 am PST types tables defining the current symbol table variables for building the symbol string hash entry creation the following copied from SymbolPack.mesa ΚI˜codešœ™Kšœ Οmœ1™˜UKšžœ žœžœ˜/K˜6K˜K˜Kšœžœ˜K˜—š œžœžœ˜Kšœ'žœ˜+Kšœžœ˜K˜—š œžœžœ˜K˜5K˜K˜Kšœ*žœ˜0K˜Kšœ žœ ˜Kšœž œžœ žœ˜7Kšœ(žœžœ˜CK˜,K˜Kšžœžœžœ˜,K˜K˜——Kšœ™˜š  œžœžœžœ˜@K˜K˜5Kšœžœ˜+Kšœžœ˜K˜šžœ"žœž˜:K˜Kšžœ(žœžœ˜