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;


SubString: TYPE~ConvertUnsafe.SubString;


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


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


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


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


hashVec м UnsafeStorage.GetSystemUZone[].NEW[Symbols.HashVector м ALL[HTNull]];

}.

  :  
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

types
tables defining the current symbol table
variables for building the symbol string
hash entry creation
the following copied from SymbolPack.mesa
START HERE
 Э╩Ъ  ХNewlineDelimiter
Ц(cedarcode) styleЩ codeЪЬЩKЪЬ
╧eЬ=ЩHKЪ╧y)Щ)KЪЮ Щ KЪЮ'Щ'KЪЬ╧kЬЯЩ0KЪЮ'Щ'KЩ KЩ KЩ(KЩ ЧЪЯ	Ш	KЪЬЯЬOШZKЪЬЯЬЯЬЯЬШKЪЬЯЬ/ШBKЪЬЯЬШKЪЬЯЬШ%KЪЬЯЬ0Ш=KЪЬЯЬШ%KШ ЧЪ╧n
ЬЯЬШKЪЯЬ,Ш3KЪЯЬШKЪЯЬШKШ KЪЬЩШ KЪЬЯЬШ(KШ ЧKЪЬ(Щ(Ш KЪЬЯЬШKШ#KЪ	Ь	ЯЬЯЬЯЬЯЬШ2KЪЬ╧cШ KЪЬЯЬЯЬЯЬбШ-KШ ЪаЬШKЪЬШKЪЬШKШKШ ЧЪаЬЯЬЯЬШ0KЪЬ<ЯЬШBЪЬШKЪЬЯЬЯЬШ%KШKШЧKЪЯЬШKЪЬШKШ ЧЧKЪЬ(Щ(Ш KШKШ KЪЬЯЬЯЬШKШ Ъа
ЬЯЬЯЬ>ШUKЪЯЬЯЬШ!KШKШKШKШKШKЪЬЯЬШKШ ЧЪаЬЯЬЯЬШKЪЬШKЪЬЯЬШKЪЬЯЬШKШ ЧЪаЬЯЬЯЬШKШKШKЪЬЯЬ	ШKЪЬ(ЯЬЯЬШCKШ&KЪЯЬЯЬЯЬШ&KЪЬШKШ KШ ЧЧKЪЬЩШ ЪаЬЯЬЯЬЯЬШHKШ"KШ-KЪЬЯЬЯЬЯЬШ%KЪЬЯЬЯЬЯЬШ%KЪЬЯЬШKШЪЯЬ#ЯЬЯШ;KШKЪЯЬ(ЯЬЯЬШ<KЪЯЬШЧKЪЬб#Ш8KЪЬб%Ш<KШGЪЯЬЯЬбШ#KЪЯЬ4ЯЬЯЬШAKЪЬШKШPЧKЪЬЯЬШ KЪЬШKЪЬ&Ш&KЪЬШKЪЬШKШKЪЯЬШ	KШ ЧЧKЪЬ)Щ)Ш Ъа	ЬЯЬЯЬШ:KЪЬЯЬбШ/KЪЬЯЬ
ШKЪЬЯЬЯЬШKЪЬЯЬ
ЯЬЯЬШ4KЪЯЬЯЬЯЬЯЬШBKЪЯЬ	ЯЬЯЬ
ЯЬШ6KШ ЧЪа
ЬЯЬЯЬЯЬШGKЪЬШЪЯЬЯШKЪЬ&Ш&KЪЯЬ&ЯЬЯЬШ2KЪЬШKЪЯЬШЧKШKШ ЧЪаЬЯЬЯЬЯЬШQKЪЬШЪЯЬЯШKЪЬ&Ш&KЪЯЬ&ЯЬЯЬЯЬШ9KЪЬШKЪЯЬШЧKЪЬШKШ ЧЪаЬЯЬЯЬЯЬШMKЪЬШЪЯЬШKЪЯЬШЪЯЬШKЪЬЯЬЯЬШ+KЪЬCЯЬШTKШЧЧKЪЬШKШ ЧЧЧKЪЯЬЯЩ
Ш KЪЬ)ЯЬЯЬ
ШOЧШ ШKШ ЧЧЧ ЕЧ    "  Ў  