-- RefTabImpl.Mesa - implementation of REF table abstraction
-- last change: Bill Paxton - 8-Feb-82 10:06:02

DIRECTORY
   Inline USING [LowHalf],
   SafeStorage USING [GetSystemZone],
   RefTab;

RefTabImpl: MONITOR LOCKS x USING x: Ref
      IMPORTS Inline, SafeStorage
      EXPORTS RefTab
      = BEGIN

  Int: TYPE = LONG INTEGER;
  Ref: TYPE = REF RefTabRep;
  RefTabRep: PUBLIC TYPE =
    MONITORED RECORD [mod,size: CARDINAL, zone: ZONE, data: REF Array];
  NodeRep: TYPE = RECORD [key: Key, val: Val, next: Node];
  Node: TYPE = REF NodeRep;
  Key: TYPE = RefTab.Key; 
  Val: TYPE = RefTab.Val;
  EachPairAction: TYPE = RefTab.EachPairAction; 

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

  -- Private Operations

  Hash: PROCEDURE [key: Key, mod: CARDINAL] RETURNS [CARDINAL] = INLINE BEGIN
     RETURN [(LOOPHOLE[Inline.LowHalf[key],CARDINAL]/4) MOD mod];
    END;

  -- public operations

  Create: PUBLIC PROCEDURE [mod: CARDINAL _ 17, zone: ZONE _ NIL]
          RETURNS [Ref]
    = BEGIN
    index: CARDINAL _ 0;
    data: REF Array _ NIL;
    IF mod < 1 THEN mod _ 1;
    IF mod > 4095 THEN mod _ 4095;
    IF zone=NIL THEN zone _ SafeStorage.GetSystemZone[];
    data _ zone.NEW[Array[mod]];
    RETURN[zone.NEW[RefTabRep _ [mod: mod, size: 0, zone: zone, data: data]]];
    END;

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

  Fetch: PUBLIC ENTRY PROCEDURE [x: Ref, key: Key]
         RETURNS [found: BOOLEAN, val: Val] = BEGIN
    ENABLE UNWIND => NULL;
    hash: CARDINAL _ Hash[key, x.mod];
    node: Node _ x.data[hash];
    WHILE node # NIL DO
      IF key = node.key THEN RETURN [TRUE, node.val];
      node _ node.next;
      ENDLOOP;
    RETURN [FALSE, NIL];
    END;

  Store: PUBLIC ENTRY PROCEDURE [x: Ref, key: Key, val: Val]
         RETURNS [BOOLEAN]
    = BEGIN
    ENABLE UNWIND => NULL;
    hash: CARDINAL _ Hash[key, x.mod];
    node: Node _ x.data[hash];
    head: Node _ node;
    WHILE node # NIL DO
      IF key = node.key THEN {node.val _ val; RETURN [FALSE]};
      node _ node.next;
      ENDLOOP;
    x.data[hash] _ x.zone.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
    ENABLE UNWIND => NULL;
    hash: CARDINAL _ Hash[key, x.mod];
    node: Node _ x.data[hash];
    head: Node _ node;
    WHILE node # NIL DO
      IF key = node.key THEN RETURN [FALSE];
      node _ node.next;
      ENDLOOP;
    x.data[hash] _ x.zone.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
    ENABLE UNWIND => NULL;
    hash: CARDINAL _ Hash[key, x.mod];
    node: Node _ x.data[hash];
    head: Node _ node;
    lag: Node _ NIL;
    WHILE node # NIL DO
      IF key = node.key 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] = {
    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...