MobHashTab.mesa
Copyright Ó 1985, 1989, 1991 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
Andy Litman May 30, 1988 7:05:43 pm PDT
JKF July 22, 1989 3:54:13 pm PDT
Foote, June 27, 1991 3:29 pm PDT
Willie-s, September 25, 1991 8:39 pm PDT
DIRECTORY
Alloc USING [Base, Handle, Index, Notifier, Selector, AddNotify, DropNotify, Trim, Units],
Basics USING [BITAND, BITXOR],
ConvertUnsafe USING [AppendSubString, EqualSubStrings, SubString],
MobHashOps USING [],
MobHashTypes USING [HTIndex, HTNull],
Symbols USING [Base, HTIndex, HTRecord, HVIndex, HashVector],
UnsafeStorage USING [GetSystemUZone];
MobHashTab: PROGRAM
IMPORTS Alloc, Basics, ConvertUnsafe, UnsafeStorage
EXPORTS MobHashOps = {
OPEN MobHashTypes;
types
SubString: TYPE~ConvertUnsafe.SubString;
tables defining the current symbol table
table: Alloc.Handle ¬ NIL;
htType, ssType: Alloc.Selector ¬ 0;
hashVec: LONG POINTER TO Symbols.HashVector ¬ NIL;
htb: Symbols.Base; -- hash table
ssb: LONG POINTER TO StringBody; -- id string
UpdateBases: Alloc.Notifier~{
ssb ¬ base[ssType];
htb ¬ base[htType];
};
AllocateHash: PROC RETURNS [Symbols.HTIndex] = {
hti: Symbols.HTIndex = table.Units[htType, Symbols.HTRecord.SIZE];
htb[hti] ¬ Symbols.HTRecord[
anyInternal: FALSE, anyPublic: FALSE,
link: HTNull,
ssIndex: ssb.length];
RETURN [hti];
};
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[];
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~{
table.Trim[ssType, 0];
table.Trim[htType, 0];
hashVec­ ¬ ALL[HTNull];
ssw ¬ table.Units[ssType, StringBody[0].SIZE] + StringBody[0].SIZE;
ssb­ ¬ [length~0, maxlength~0, text~];
IF AllocateHash[] # HTNull THEN ERROR;
};
hash entry creation
EnterString: PUBLIC PROC [s: SubString] RETURNS [hti: Symbols.HTIndex]~{
hvi: Symbols.HVIndex~HashValue[s];
desc: SubString¬[base~ssb, offset~, length~];
charsPerWord: CARDINAL = BYTES[WORD];
unitsPerWord: CARDINAL = UNITS[WORD];
offset, length, nw: CARDINAL;
ssi: Alloc.Index;
FOR hti ¬ hashVec[hvi], htb[hti].link UNTIL hti = HTNull DO
desc ¬ SubStringForHash[hti];
IF ConvertUnsafe.EqualSubStrings[s, desc] THEN RETURN [hti];
ENDLOOP;
offset ¬ ssb.length; -- current length of packed string
length ¬ s.length + 1; -- bytes to be added to packed string
nw ¬ (offset + length - ssb.maxlength + (charsPerWord-1))/charsPerWord;
IF nw # 0 THEN { -- need more words
IF (ssi ¬ table.Units[ssType, nw*unitsPerWord]) # ssw THEN ERROR;
ssw ¬ ssw + nw*unitsPerWord;
ssb­ ¬ [length: ssb.length, maxlength: ssb.maxlength+nw*charsPerWord, text:]; };
ssb[ssb.length] ¬ VAL[s.length];
ssb.length ¬ ssb.length + 1;
ConvertUnsafe.AppendSubString[ssb, s];
hti ¬ AllocateHash[];
htb[hti].link ¬ hashVec[hvi];
hashVec[hvi] ¬ hti;
RETURN };
the following copied from SymbolPack.mesa
HashValue: PROC [s: SubString] RETURNS [Symbols.HVIndex]~{
mask: WORD~0DFh; -- masks out ASCII case shifts
n: CARDINAL~s.length;
b: LONG STRING~s.base;
v: WORD ¬ Basics.BITAND[ORD[b[s.offset]], mask]*7Fh;
IF n # 0 THEN v ¬ v + Basics.BITAND[ORD[b[s.offset+(n-1)]], mask];
RETURN [Basics.BITXOR[v, n*0Fh] MOD hashVec­.LENGTH]};
FindString: PUBLIC PROC [s: SubString] RETURNS [hti: Symbols.HTIndex]~{
hti ¬ hashVec[HashValue[s]];
WHILE hti # HTNull DO
ss: SubString ¬ SubStringForHash[hti];
IF ConvertUnsafe.EqualSubStrings[s, ss] THEN EXIT;
hti ¬ htb[hti].link;
ENDLOOP;
};
FindEquivalentString: PUBLIC PROC [s: SubString] RETURNS [hti: Symbols.HTIndex]~{
hti ¬ hashVec[HashValue[s]];
WHILE hti # HTNull DO
ss: SubString ¬ SubStringForHash[hti];
IF ConvertUnsafe.EqualSubStrings[s, ss, FALSE] THEN EXIT;
hti ¬ htb[hti].link;
ENDLOOP;
};
SubStringForHash: PUBLIC PROC [hti: Symbols.HTIndex] RETURNS[s: SubString] ~{
s.base ¬ ssb;
IF hti = HTNull
THEN s.offset ¬ s.length ¬ 0
ELSE {
p: POINTER TO Symbols.HTRecord ¬ @htb[hti];
s.length ¬ htb[hti].ssIndex - (s.offset ¬ htb[hti-Symbols.HTRecord.SIZE].ssIndex+1);
}
};
START HERE
hashVec ¬ UnsafeStorage.GetSystemUZone[].NEW[Symbols.HashVector ¬ ALL[HTNull]];
}.