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

        }.