-- SymTabImpl - implementation of symbol table abstraction
-- last change: Russ Atkinson - 16-Sep-81 21:01:24
-- last change: Nori Suzuki - 11-Oct-81 20:35:31
-- filed on: [Indigo]<Sakura>Parser>SymTabImpl.mesa

DIRECTORY
   Inline USING [LowHalf],
   Rope USING [Compare, Ref],
   RopeInline USING [InlineFetch, InlineSize, Lower],
   SymTab;

SymTabImpl: MONITOR LOCKS x USING x: Ref
      IMPORTS Inline, Rope, RopeInline
      EXPORTS SymTab
      = BEGIN

  Int: TYPE = LONG INTEGER;
  Ref: TYPE = REF SymTabRep;
  SymTabRep: PUBLIC TYPE =
    MONITORED RECORD [mod,size: CARDINAL, case: BOOLEAN, data: REF Array];
  NodeRep: TYPE = RECORD [key: Key, val: Val, next: Node];
  Node: TYPE = REF NodeRep;
  String: TYPE = Rope.Ref;
  Key: TYPE = SymTab.Key; 
  Val: TYPE = SymTab.Val;
  EachPairAction: TYPE = SymTab.EachPairAction; 

  Array: TYPE = RECORD[nodes: SEQUENCE max: CARDINAL OF Node];

  -- Private Operations

  Hash: PROCEDURE [s: String, mod: CARDINAL] RETURNS [CARDINAL] = BEGIN
    size: LONG INTEGER ← RopeInline.InlineSize[s];
    IF size = 0 THEN RETURN [0];
    {c0: CARDINAL = RopeInline.Lower[RopeInline.InlineFetch[s, 0]] - 0C;
     c1: CARDINAL = RopeInline.Lower[RopeInline.InlineFetch[s, size-1]] - 0C;
     RETURN [(Inline.LowHalf[size] + c0 + c1) MOD mod]};
    END;

  -- public operations

  Create: PUBLIC PROCEDURE [mod: CARDINAL ← 17, case: BOOLEAN ← TRUE]
          RETURNS [Ref]
    = BEGIN
    index: CARDINAL ← 0;
    data: REF Array ← NIL;
    IF mod < 1 THEN mod ← 1;
    IF mod > 4095 THEN mod ← 4095;
    data ← NEW[Array[mod]];
    RETURN[NEW[SymTabRep ← [mod: mod, size: 0, case: case, data: data]]];
    END;

  GetSize: PUBLIC PROCEDURE [x: Ref] RETURNS [CARDINAL] =
    {RETURN [x↑.size]};

  Fetch: PUBLIC ENTRY PROCEDURE [x: Ref, key: Key]
         RETURNS [found: BOOLEAN, storedKey: Key, val: Val] = BEGIN
    hash: CARDINAL ← Hash[key, x.mod];
    node: Node ← x.data[hash];
    case: BOOLEAN ← x.case;
    WHILE node # NIL DO
      nkey: Key ← node.key;
      IF Rope.Compare[key, node.key, case] = 0
         THEN RETURN [TRUE, node.key, node.val];
      node ← node.next;
      ENDLOOP;
    RETURN [FALSE, NIL, NIL];
    END;

  Store: PUBLIC ENTRY PROCEDURE [x: Ref, key: Key, val: Val]
         RETURNS [BOOLEAN]
    = BEGIN
    hash: CARDINAL ← Hash[key, x.mod];
    node: Node ← x.data[hash];
    head: Node ← node;
    case: BOOLEAN ← x.case;
    WHILE node # NIL DO
      nkey: Key ← node.key;
      IF Rope.Compare[key, node.key, case] = 0
         THEN {node.val ← val; RETURN [FALSE]};
      node ← node.next;
      ENDLOOP;
    x.data[hash] ← NEW[NodeRep ← [key: key, val: val, next: head]];
    x.size ← x.size + 1;
    RETURN [TRUE];
    END;

  Insert: PUBLIC ENTRY PROCEDURE [x: Ref, key: Key, val: Val]
          RETURNS [BOOLEAN]
    = BEGIN
    hash: CARDINAL ← Hash[key, x.mod];
    node: Node ← x.data[hash];
    head: Node ← node;
    case: BOOLEAN ← x.case;
    WHILE node # NIL DO
      nkey: Key ← node.key;
      IF Rope.Compare[key, node.key, case] = 0
         THEN RETURN [FALSE];
      node ← node.next;
      ENDLOOP;
    x.data[hash] ← NEW[NodeRep ← [key: key, val: val, next: head]];
    x.size ← x.size + 1;
    RETURN [TRUE];
    END;

  Delete: PUBLIC ENTRY PROCEDURE [x: Ref, key: Key] RETURNS [BOOLEAN]
    = BEGIN
    hash: CARDINAL ← Hash[key, x.mod];
    node: Node ← x.data[hash];
    head: Node ← node;
    case: BOOLEAN ← x.case;
    lag: Node ← NIL;
    WHILE node # NIL DO
      nkey: Key ← node.key;
      IF Rope.Compare[key, node.key, case] = 0
         THEN {IF lag = NIL THEN x.data[hash] ← node.next
                            ELSE lag.next ← node.next;
               x.size ← x.size - 1;
               RETURN [TRUE]};
      lag ← node;
      node ← node.next;
      ENDLOOP;
    RETURN [FALSE];
    END;

  Pairs: PUBLIC PROCEDURE [x: Ref, action: EachPairAction]
           RETURNS [quit: BOOLEAN] = BEGIN
    node: Node ← NIL;
    index: CARDINAL ← 0;
    DO
        [node, index] ← GetNext[x, node, index];
        IF node = NIL THEN RETURN [FALSE];
        IF action[node.key, node.val] THEN RETURN [TRUE];
        ENDLOOP;
    END;

  GetNext: ENTRY PROCEDURE [x: Ref, node: Node, index: CARDINAL]
             RETURNS [Node, CARDINAL] = {
    mod: CARDINAL ← x.mod;
    IF node # NIL THEN {
       node ← node.next;
       IF node # NIL THEN RETURN [node, index];
       index ← index + 1}
       ELSE index ← 0;
    WHILE index < mod DO
      node ← x.data[index];
      IF node = NIL THEN {index ← index + 1; LOOP};
      RETURN [node, index];
      ENDLOOP;
    RETURN [NIL, mod];
    };

  END.
  
  Change log:
  
  Fetch returns  stored Key as well as Value