
<<ThreeC4PrimImpl4.mesa: October 18, 1985 2:04:49 pm PDT>>
<<Sturgis, October 21, 1985 10:52:36 am PDT>>

DIRECTORY
ThreeC4BaseDecl1Def USING[NameNode],
ThreeC4PrimImplDefs USING[GetNameInfo],
Rope USING[Equal, ROPE];


ThreeC4PrimImpl4: CEDAR PROGRAM IMPORTS ThreeC4PrimImplDefs, Rope EXPORTS ThreeC4PrimImplDefs = 
BEGIN OPEN ThreeC4BaseDecl1Def, ThreeC4PrimImplDefs;


-- Hash table stuff

HashTable: TYPE = REF HashTableBody;
HashTableBody: PUBLIC TYPE = REF HashTableContents;
HashTableContents: TYPE = RECORD[
nItems: CARDINAL,
items: SEQUENCE size: CARDINAL OF HashTableEntry];

HashTableEntry: TYPE = REF HashTableEntryBody;
HashTableEntryBody: TYPE = RECORD[
name: NameNode,
info: REF ANY,
next: HashTableEntry];

FindEntry: PUBLIC PROC[table: HashTable, name: NameNode] RETURNS[REF ANY] =
BEGIN
key: INT;
text: Rope.ROPE;
index: CARDINAL;
[text, key] _ GetNameInfo[name];
index _ key MOD table.size;
FOR entry: HashTableEntry _ table.items[index], entry.next WHILE entry # NIL DO
entryKey: INT;
entryText: Rope.ROPE;
[entryText, entryKey] _ GetNameInfo[entry.name];
IF entryKey = key AND Rope.Equal[entryText, text] THEN RETURN[entry.info];
ENDLOOP;
RETURN[NIL];
END;

FindExistingEntry: PUBLIC PROC[table: HashTable, name: NameNode] RETURNS[REF ANY] =
BEGIN
info: REF ANY _ FindEntry[table, name];
IF info = NIL THEN ERROR ELSE RETURN[info];
END;

MakeEntry: PUBLIC PROC[table: HashTable, name: NameNode, info: REF ANY] =
BEGIN
entry: HashTableEntry _ FindOrMakeEntry[table, name];
IF entry.info # NIL THEN ERROR;
entry.info _ info;
END;

FindOrMakeEntry: PROC[table: HashTable, name: NameNode] RETURNS[HashTableEntry] =
BEGIN
key: INT;
text: Rope.ROPE;
index: CARDINAL;
newEntry: HashTableEntry;
[text, key] _ GetNameInfo[name];
index _ key MOD table.size;
FOR entry: HashTableEntry _ table.items[index], entry.next WHILE entry # NIL DO
entryKey: INT;
entryText: Rope.ROPE;
[entryText, entryKey] _ GetNameInfo[entry.name];
IF entryKey = key AND Rope.Equal[entryText, text] THEN RETURN[entry];
ENDLOOP;
newEntry _ NEW[HashTableEntryBody_[name, NIL, table.items[index]]];
table.items[index] _ newEntry;
table.nItems _ table.nItems + 1;
IF table.nItems > 2*table.size THEN RebuildTable[table];
RETURN[newEntry];
END;

CreateHashTable: PUBLIC PROC[size: CARDINAL] RETURNS[HashTable] =
BEGIN
htb: HashTableBody _ NEW[HashTableContents[size]];
htb.nItems _ 0;
FOR index: CARDINAL IN [0..size) DO htb.items[index] _ NIL ENDLOOP;
RETURN[NEW[HashTableBody_htb]];
END;

RebuildTable: PROC[table: HashTable] =
BEGIN
oldSize: CARDINAL _ table.size;
newSize: CARDINAL _ 2*oldSize;
newBody: HashTableBody _ NEW[HashTableContents[newSize]];
newBody.nItems _ table.nItems;
FOR index: CARDINAL IN [0..newSize) DO newBody.items[index] _ NIL ENDLOOP;
FOR index: CARDINAL IN [0..oldSize) DO
nextEntry: HashTableEntry _ table.items[index];
WHILE nextEntry # NIL DO
entry: HashTableEntry _ nextEntry;
index: INT _ GetNameInfo[entry.name].key MOD newSize;
nextEntry _ entry.next;
entry.next _ newBody.items[index];
newBody.items[index] _ entry;
ENDLOOP;
ENDLOOP;
table^ _ newBody;
END;

EnumerateHashTable: PUBLIC PROC[table: HashTable, for: PROC[info: REF ANY, name: NameNode]] =
BEGIN
FOR index: CARDINAL IN [0..table.size) DO
FOR entry: HashTableEntry _ table.items[index], entry.next WHILE entry # NIL DO
for[entry.info, entry.name];
ENDLOOP;
ENDLOOP;
END;


<<>>
END..