-- AtomsPrivateImpl.mesa
-- Simple hash-table implementation of CedarPrivateAtoms.MakeAtom
-- Last Modified On March 7, 1983 9:14 am by Paul Rovner

DIRECTORY
Inline,
Rope USING[ROPE, Text],
RopeInline USING[NewText, InlineFlatten],
RTBasic USING[Type],
RTLoader USING[AcquireBasicLiterals],
RTTypesBasic USING[GetCanonicalType, Type],
RTTypesBasicPrivate USING[NotifyAtomRecType],
SafeStorageExtras USING[permanentZone],
AtomsPrivate;

AtomsPrivateImpl: MONITOR -- protects the ATOM dictionary
IMPORTS Inline, RopeInline, RTLoader, RTTypesBasic, RTTypesBasicPrivate, SafeStorageExtras
EXPORTS AtomsPrivate
SHARES Rope

= BEGIN OPEN AtomsPrivate;

-- CONSTANTS
HashSize: INTEGER = 4093; -- prime

-- TYPES
String: TYPE = LONG POINTER TO READONLY TEXT;
Atom: TYPE = REF AtomRec;
AtomDictionaryIndex: TYPE = [0..HashSize);
AAtomDict: TYPE = ARRAY AtomDictionaryIndex OF Atom;
ComparisonOutcome: TYPE = {less, greater, equal};

-- VARIABLES
atomZone: ZONE = SafeStorageExtras.permanentZone;
atomDictionary: REF AAtomDict ← atomZone.NEW[AAtomDict ← ALL[NIL]];

-- PROCEDURES

GetAtom: PUBLIC PROC[pName: Rope.ROPE] RETURNS[ATOM] =
{ t: Rope.Text = RopeInline.InlineFlatten[pName];
this, prev: Atom;
hash: AtomDictionaryIndex;
l: CARDINAL;

IF t = NIL THEN RETURN[NIL];
l ← t.length;
IF l MOD 2 = 1 -- fill residue char with 0
THEN { w: CARDINAL = Inline.BITSHIFT[t[l-1], 8];
p: LONG POINTER TO CARDINAL;
l ← l + 1;
p ← LOOPHOLE[t, LONG POINTER TO CARDINAL] + SIZE[TEXT[0]] + l/2 - 1;
IF p^ # w THEN p^ ← w};
[this, prev, hash] ← LookUpAtom[t];
IF this # NIL THEN RETURN[LOOPHOLE[this]];

-- here if not found. Make a new ATOM.
this ← atomZone.NEW[AtomRec ← [pName: t]];
InsertAtom[atom: this, prev: prev, hash: hash];
RETURN[LOOPHOLE[this]]};

UnsafeMakeAtom: PUBLIC PROC[pName: String] RETURNS[ATOM] =
{ this, prev: Atom;
hash: AtomDictionaryIndex;
l: CARDINAL;
oddLength: BOOLEAN ← FALSE;
rt: Rope.Text;

IF pName = NIL THEN RETURN[NIL];
l ← pName.length;
IF l MOD 2 = 1 -- fill residue char with 0 (NOTE violation of READONLY!!!)
THEN { w: CARDINAL = Inline.BITSHIFT[pName[l-1], 8];
p: LONG POINTER TO CARDINAL;
oddLength ← TRUE;
l ← l + 1;
p ← LOOPHOLE[pName + SIZE[TEXT[0]] + l/2 - 1];
IF p^ # w THEN p^ ← w -- NOTE violation of READONLY!!!
};
[this, prev, hash] ← LookUpAtom[LOOPHOLE[pName, Rope.Text]];
IF this # NIL THEN RETURN[LOOPHOLE[this]];
-- here if not found. Make a new ATOM.
rt ← RopeInline.NewText[l];
rt.length ← pName.length;
FOR i: CARDINAL IN [0..pName.length) DO rt[i] ← pName[i] ENDLOOP;
IF oddLength THEN {rt.length ← l; rt[l-1] ← LOOPHOLE[0]; rt.length ← l-1};
this ← atomZone.NEW[AtomRec ← [pName: rt]];
InsertAtom[atom: this, prev: prev, hash: hash];
RETURN[LOOPHOLE[this]]};

EnumerateAtoms: PUBLIC PROC[ callee: PROC[ATOM] RETURNS[stop: BOOLEAN] ]
RETURNS[ATOM--NIL if was not stopped--] =
{ FOR atom: ATOM ← Next[NIL], Next[atom]
UNTIL atom = NIL DO IF callee[atom] THEN RETURN[atom]; ENDLOOP;
RETURN[NIL]};

Next: ENTRY PROC[atom: ATOM ← NIL] RETURNS[ATOM] = INLINE
{ a: Atom = LOOPHOLE[atom];
IF a # NIL AND a.link # NIL THEN RETURN[a.link];
FOR adi: CARDINAL ← (IF a = NIL THEN 0 ELSE (Hash[LOOPHOLE[a.pName]] + 1)), adi + 1
UNTIL adi = HashSize
DO IF atomDictionary[adi] # NIL THEN RETURN[LOOPHOLE[atomDictionary[adi]]];
ENDLOOP;
RETURN[NIL]};

-- returns [NIL,ptr to last atom, hash index] if not found
LookUpAtom: ENTRY PROC[s: Rope.Text]
RETURNS[atom: Atom, prev: Atom, hash: AtomDictionaryIndex] =
INLINE
{ prev ← NIL;
hash ← Hash[s];
FOR atom ← atomDictionary[hash], LOOPHOLE[atom.link] UNTIL atom = NIL
DO
SELECT CompareStrings[s, atom.pName] FROM
equal => RETURN;
greater => {atom ← NIL; EXIT};
ENDCASE;
prev ← atom;
ENDLOOP};

InsertAtom: ENTRY PROC[atom: Atom, prev: Atom, hash: AtomDictionaryIndex] = INLINE
{ IF prev = NIL
THEN {atom.link ← LOOPHOLE[atomDictionary[hash]]; atomDictionary[hash] ← atom}
ELSE {atom.link ← prev.link; prev.link ← LOOPHOLE[atom]}};

CompareStrings: INTERNAL PROC[leftString, rightString: Rope.Text]
RETURNS[ComparisonOutcome] = INLINE
{ lLength: CARDINAL = (leftString.length+1)/2;
rLength: CARDINAL = (rightString.length+1)/2;
lp: LONG POINTER TO CARDINAL = LOOPHOLE[leftString, LONG POINTER TO CARDINAL] + SIZE[TEXT[0]];
rp: LONG POINTER TO CARDINAL = LOOPHOLE[rightString, LONG POINTER TO CARDINAL] + SIZE[TEXT[0]];
FOR i: CARDINAL IN [0..MIN[lLength, rLength]) DO
lw: CARDINAL = (lp + i)^;
rw: CARDINAL = (rp + i)^;
IF lw < rw THEN RETURN[less] ELSE IF lw > rw THEN RETURN[greater];
ENDLOOP;
RETURN[IF lLength = rLength THEN equal ELSE
IF lLength < rLength THEN less ELSE greater]};


-- stolen from TexHash.mesa
Hash: INTERNAL PROC[s: Rope.Text] RETURNS[AtomDictionaryIndex] = INLINE
{ acc: CARDINAL ← 0;
FOR i: CARDINAL IN [0..MIN[7, s.length]) DO acc ← 7*acc+LOOPHOLE[s[i], CARDINAL];
ENDLOOP;
RETURN[acc MOD HashSize]};

-- START HERE

atomRecType: RTTypesBasic.Type = RTTypesBasic.GetCanonicalType[CODE[AtomRec]];

RTTypesBasicPrivate.NotifyAtomRecType[atomRecType];
RTLoader.AcquireBasicLiterals[atomRecType];

END.