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..