file ProtoHashTab.mesa
last edited by Satterthwaite, December 29, 1982 12:45 pm
Last Edited by: Maxwell, August 11, 1983 2:59 pm
Last Edited by: Paul Rovner, September 22, 1983 9:43 pm
DIRECTORY
Alloc: TYPE USING [
Base, Handle, Index, Notifier, Selector, AddNotify, DropNotify, Trim, Words],
Basics: TYPE USING [charsPerWord],
BcdDefs: TYPE USING [NameString],
ConvertUnsafe: TYPE USING [AppendRope, EqualSubStrings, SubString, AppendSubString],
HashOps: TYPE USING [],
HashTypes: TYPE USING [HTIndex, htNull, hvLength],
PrincOpsUtils: TYPE USING [BITAND, BITXOR],
Rope USING [FromChar];
HashTab: PROGRAM
IMPORTS Alloc, ConvertUnsafe, PrincOpsUtils, Rope
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~ConvertUnsafe.SubString;
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: 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]};
variables for building the symbol string
ssw: Alloc.Index;
initialized: BOOLFALSE;
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};
hash entry creation
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};
the following copied from SymbolPack.mesa
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𡤌harBits[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]}};
}.