-- TexHash.mesa

-- last written by Doug Wyatt, November 10, 1979  5:50 PM

DIRECTORY
	TexDefs: FROM "TexDefs",
	TexErrorDefs: FROM "TexErrorDefs" USING[Confusion,OverFlow],
	TexHashDefs: FROM "TexHashDefs",
	TexMemDefs: FROM "TexMemDefs",
	TexStringDefs: FROM "TexStringDefs",
	TexTableDefs: FROM "TexTableDefs";

TexHash: PROGRAM
IMPORTS TexErrorDefs,TexMemDefs,TexStringDefs,TexTableDefs
EXPORTS TexHashDefs,TexTableDefs =
BEGIN OPEN TexDefs,TexHashDefs;

HashEntry: TYPE = RECORD
	[
	link: HashTableIndex,
	id: STRING
	];

HashTable: TYPE = ARRAY HashTableIndex OF HashEntry;

hprime: CARDINAL = 89; -- range of hash values
HashCode: TYPE = [0..hprime);
HHeadTable: TYPE = ARRAY HashCode OF HashTableIndex;

hash: POINTER TO HashTable←NIL;
hhead: POINTER TO HHeadTable←NIL;

havail: HashTableIndex = nilHashIndex; -- hash[havail].link points to the
	-- list of available entries in the hash table

newcontrolseqok: BOOLEAN←TRUE;

NoNewControlSeq: PUBLIC PROCEDURE[b: BOOLEAN] =
	BEGIN newcontrolseqok←NOT b END;

IdLookup: PUBLIC PROCEDURE[id: STRING] RETURNS[index: HashIndex] =
	BEGIN OPEN TexTableDefs;
	index←HashLookup[id, newcontrolseqok];
	IF NOT HashEquivDefined[index] THEN
		BEGIN -- not currently defined
		IF newcontrolseqok THEN SetHashEquiv[index,undefined,[undefined[]]]
		ELSE index←nilHashIndex;
		END;
	RETURN[index];
	END;

HashLookup: PUBLIC PROCEDURE[id: STRING, insert: BOOLEAN]
	RETURNS[i: HashIndex] =
	BEGIN
	IF id.length=1 THEN
		i←hashsize+LOOPHOLE[id[0],CARDINAL] -- single character id
	ELSE
		BEGIN -- multicharacter id
		h: HashCode←HashFunction[id];
		FOR i←hhead[h], hash[i].link UNTIL i=nilHashIndex
			DO
			IF TexStringDefs.EqualString[id,hash[i].id] THEN GOTO Found;
			ENDLOOP;
		IF insert THEN
			BEGIN
			i←hash[havail].link;
			IF i=nilHashIndex THEN ERROR TexErrorDefs.OverFlow["hash"];
			hash[havail].link←hash[i].link;
			hash[i]←[hhead[h],TexStringDefs.CopyString[id]]; hhead[h]←i;
			END;
		EXITS Found => NULL END;
	RETURN[i];
	END;

HashFunction: PROCEDURE[id: STRING] RETURNS[HashCode] =
	BEGIN i,acc: CARDINAL←0;
	FOR i IN [0..MIN[6,id.length])
		DO acc←7*acc+LOOPHOLE[id[i],INTEGER] ENDLOOP;
	RETURN[acc MOD hprime];
	END -- of HashFunction --;

IdName: PUBLIC PROCEDURE[s: STRING, h: HashIndex] =
	BEGIN OPEN TexStringDefs;
	IF h NOT IN HashIndex THEN AppendString[s,"IMPOSSIBLE"]
	ELSE IF h>=hashsize THEN AppendPrintCode[s,LOOPHOLE[h-hashsize,Char]]
	ELSE BEGIN id: STRING←hash[h].id;
		IF id=NIL THEN AppendString[s,"UNDEFINED"]
		ELSE AppendString[s,id];
		END;
	END -- of IdName --;

AppendPrintCode: PROCEDURE[s: STRING, c: Char] =
	BEGIN OPEN TexStringDefs;
	SELECT c FROM
		0C => AppendString[s, "NULL"];
		10C => AppendString[s, "BS"];
		11C => AppendString[s, "TAB"];
		12C => AppendString[s, "LF"];
		13C => AppendString[s, "VT"];
		14C => AppendString[s, "FF"];
		15C => AppendString[s, "CR"];
		33C => AppendString[s, "ESC"];
		177C => AppendString[s, "DEL"];
		ENDCASE => AppendChar[s, c];
	END;

HashOut: PUBLIC PROCEDURE[m: HashIndex] =
	BEGIN
	h: HashCode;
	p,q: HashTableIndex;
	IF m>=hashsize THEN RETURN;
	h←HashFunction[hash[m].id]; TexMemDefs.FreeString[hash[m].id];
	IF (p←hhead[h])=m THEN hhead[h]←hash[m].link
	ELSE WHILE p#nilHashIndex
		DO
		q←hash[p].link;
		IF q=m THEN BEGIN hash[p].link←hash[m].link; EXIT END
		ELSE p←q;
		REPEAT
			FINISHED => ERROR TexErrorDefs.Confusion -- hash table inconsistent
		ENDLOOP;
	hash[m]←[havail,NIL]; hash[havail].link←m;
	END;

HashInit: PROCEDURE =
	BEGIN OPEN TexMemDefs;
	i: CARDINAL;
	hhead←AllocMem[SIZE[HHeadTable]];
	hash←AllocMem[SIZE[HashTable]];
	FOR i IN HashCode DO hhead[i]←nilHashIndex ENDLOOP;
	hash[havail]←[1,NIL];
	-- this assumes havail NOT IN[1..LAST[HashTableIndex]]
	FOR i IN [1..LAST[HashTableIndex]) DO hash[i]←[i+1,NIL] ENDLOOP;
	hash[LAST[HashTableIndex]]←[nilHashIndex,NIL];
	hash[nilHashIndex].id←TexStringDefs.CopyString["UNDEFINED"];
	END;

HashInit;

END.