-- SymTabImpl.mesa - implementation of symbol table abstraction
-- Russ Atkinson, October 19, 1982 5:21 pm

DIRECTORY
   Inline USING [LowHalf],
   Rope USING [Equal, ROPE],
   RopeInline USING [InlineFetch, InlineSize, Lower],
   SafeStorage USING [NewZone],
   SymTab USING [EachPairAction, Key, Val];

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

  Ref: TYPE = REF SymTabRep;
  SymTabRep: PUBLIC TYPE =
    MONITORED RECORD [mod,size: CARDINAL, case: BOOL, data: REF Array];
  NodeRep: TYPE = RECORD [key: Key, val: Val, next: Node];
  Node: TYPE = REF NodeRep;

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

  pz: ZONE _ SafeStorage.NewZone[prefixed];

  -- Private Operations

  Hash: PROC [s: ROPE, mod: CARDINAL] RETURNS [CARDINAL] = TRUSTED {
    size: INT _ 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]};
    };

  -- public operations

  Create: PUBLIC PROC [mod: CARDINAL _ 17, case: BOOL _ TRUE] RETURNS [Ref] = {
    -- creates new table with suggested hash size
    -- if case is TRUE, keys are compared exactly
    -- if case is FALSE, case is ignored in comparing keys
    index: CARDINAL _ 0;
    data: REF Array _ NIL;
    IF mod < 1 THEN mod _ 1;
    IF mod > 4095 THEN mod _ 4095;
    data _ pz.NEW[Array[mod]];
    RETURN[pz.NEW[SymTabRep _ [mod: mod, size: 0, case: case, data: data]]];
    };

  GetSize: PUBLIC PROC [x: Ref] RETURNS [CARDINAL] =
    -- returns number of key-value pairs in table
    {RETURN [x^.size]};

  Fetch: PUBLIC ENTRY PROC
      [x: Ref, key: Key] RETURNS [found: BOOL, val: Val] = {
    -- looks up key in table, returns associated value (if any)
    -- if found is TRUE, val is value associated with given key
    -- if found is FALSE, val is NIL
    ENABLE UNWIND => NULL;
    hash: CARDINAL _ Hash[key, x.mod];
    node: Node _ x.data[hash];
    case: BOOL _ x.case;
    WHILE node # NIL DO
      nkey: Key _ node.key;
      IF Rope.Equal[key, node.key, case]
         THEN RETURN [TRUE, node.val];
      node _ node.next;
      ENDLOOP;
    RETURN [FALSE, NIL];
    };

  Store: PUBLIC ENTRY PROC
      [x: Ref, key: Key, val: Val] RETURNS [BOOL] = {
    -- stores new key-value pair, overwriting previous value for given key
    -- returns TRUE if new value, FALSE if previous value overwritten
    ENABLE UNWIND => NULL;
    hash: CARDINAL _ Hash[key, x.mod];
    node: Node _ x.data[hash];
    head: Node _ node;
    case: BOOL _ x.case;
    WHILE node # NIL DO
      nkey: Key _ node.key;
      IF Rope.Equal[key, node.key, case]
         THEN {node.val _ val; RETURN [FALSE]};
      node _ node.next;
      ENDLOOP;
    x.data[hash] _ pz.NEW[NodeRep _ [key: key, val: val, next: head]];
    x.size _ x.size + 1;
    RETURN [TRUE];
    };

  Insert: PUBLIC ENTRY PROC [x: Ref, key: Key, val: Val] RETURNS [BOOL] = {
    -- inserts new key-value pair, except if previous value for given key
    -- returns TRUE if inserted, FALSE if previous value for key
    ENABLE UNWIND => NULL;
    hash: CARDINAL _ Hash[key, x.mod];
    node: Node _ x.data[hash];
    head: Node _ node;
    case: BOOL _ x.case;
    WHILE node # NIL DO
      nkey: Key _ node.key;
      IF Rope.Equal[key, node.key, case]
         THEN RETURN [FALSE];
      node _ node.next;
      ENDLOOP;
    x.data[hash] _ pz.NEW[NodeRep _ [key: key, val: val, next: head]];
    x.size _ x.size + 1;
    RETURN [TRUE];
    };

  Delete: PUBLIC ENTRY PROC [x: Ref, key: Key] RETURNS [BOOL] = {
    -- deletes key-value pair associated with given key
    -- returns TRUE if deletion actually occurred, FALSE if no such key
    ENABLE UNWIND => NULL;
    hash: CARDINAL _ Hash[key, x.mod];
    node: Node _ x.data[hash];
    head: Node _ node;
    case: BOOL _ x.case;
    lag: Node _ NIL;
    WHILE node # NIL DO
      nkey: Key _ node.key;
      IF Rope.Equal[key, node.key, case]
         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];
    };

  Pairs: PUBLIC PROC [x: Ref, action: EachPairAction] RETURNS [quit: BOOL] = {
    -- enumerates pairs currently in symbol table in unspecified order
    -- pairs inserted/deleted during enumeration may or may not be seen
    -- applies action to each pair until action returns TRUE or no more pairs
    -- returns TRUE if some action returns TRUE
    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;
    };

  GetNext: ENTRY PROC
      [x: Ref, node: Node, index: CARDINAL] RETURNS [Node, CARDINAL] = {
    ENABLE UNWIND => NULL;
    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.