[Indigo]<Cedar5.3>Binder>ProtoHashTab.mesa!1

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

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