-- SymbolTableImpl.mesa
-- last edited by Suzuki: 12 Oct. 1981 3:02 pm PDT (Monday)

DIRECTORY
  Rope: TYPE USING [Concat, Ref],
  SymbolTable: TYPE,
  SymTab: TYPE;

SymbolTableImpl: PROGRAM
  IMPORTS Rope, SymTab
  EXPORTS SymbolTable = {

PrivateRef: TYPE = REF Table;

Table: PUBLIC TYPE = RECORD [
  hash: SymTab.Ref,
  table: REF PairTable,
  nest: REF Nest,
  level: CARDINAL,
  marker: CARDINAL];
  
PairTable: TYPE = RECORD [val: SEQUENCE length: CARDINAL OF 
  RECORD[pred: CARDINAL, key: Rope.Ref, val: SymbolTable.Value, port: BOOLEAN]];
  
Nest: TYPE = RECORD [val: SEQUENCE length: CARDINAL OF CARDINAL];

Create: PUBLIC PROC [hashSize, tableSize, nestLevel:CARDINAL, case:BOOLEAN] RETURNS [PrivateRef] = {
  tab: PrivateRef ← NEW[Table];
  tab.hash ← SymTab.Create[hashSize, case];
  tab.table ← NEW[PairTable[tableSize]];
  tab.nest ← NEW[Nest[nestLevel]];
  tab.level ← 0;
  tab.marker ← 0;
  RETURN[tab]};

Mark: PUBLIC PROC [tab: PrivateRef] = {
  IF tab.nest.length<=tab.level THEN ERROR;
  tab.nest[tab.level] ← tab.marker;
  tab.level←tab.level+1};

Add: PUBLIC PROC [tab: PrivateRef, key: SymbolTable.Key, val: SymbolTable.Value, port: BOOLEAN] = {
  found: BOOLEAN;
  oldValue: SymbolTable.Value;
  pred: CARDINAL;
  storedKey: SymbolTable.Key;
  [found, storedKey, oldValue] ← SymTab.Fetch[tab.hash, key];
  IF found THEN 
    pred ← NARROW[oldValue, REF CARDINAL]↑
  ELSE {
    storedKey ← Rope.Concat[NIL, key];
    pred ← 0};
  [] ← SymTab.Store[tab.hash, storedKey, NEW[CARDINAL ← tab.marker]];
  IF tab.marker>=tab.table.length THEN ERROR Overflow;
  tab.table[tab.marker] ← [pred, storedKey, val, port];
  tab.marker ← tab.marker+1};

Get: PUBLIC PROC [tab: PrivateRef, key: SymbolTable.Key] RETURNS [found: BOOLEAN, val: SymbolTable.Value, port: BOOLEAN] = {
  value: SymbolTable.Value;
  [found, ,value] ← SymTab.Fetch[tab.hash, key];
  IF NOT found THEN RETURN[FALSE, NIL, FALSE];
  [,,val,port] ← tab.table[NARROW[value,REF CARDINAL]↑]};

Pop: PUBLIC PROC [tab: PrivateRef] = {
  FOR i: CARDINAL IN [tab.nest[tab.level-1]..tab.nest[tab.level]) DO
    [] ← SymTab.Store[tab.hash, tab.table[i].key, NEW[CARDINAL ← tab.table[i].pred]];
    ENDLOOP;
  tab.level ← tab.level-1};

Underflow: PUBLIC SIGNAL = CODE;

Overflow: PUBLIC SIGNAL = CODE;

}.