-- RefTabImpl.Mesa - implementation of REF table abstraction
-- last change: Bill Paxton - August 19, 1982 9:25 am
-- last change: Warren Teitelman - September 8, 1982 9:12 pm

DIRECTORY
   Inline USING [LongNumber],
   SafeStorage USING [GetSystemZone],
   RefTab USING [EachPairAction, Key, Val]
   ;

RefTabImpl: CEDAR MONITOR LOCKS x USING x: Ref
      IMPORTS 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[key, Inline.LongNumber].lowbits/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;

  EnterCode: TYPE = { insert, store, replace };

  Replace: PUBLIC PROC [x: Ref, key: Key, val: Val] RETURNS [BOOLEAN] =
  	{ RETURN [Enter[x, key, val, replace]] };
  
  Store: PUBLIC PROCEDURE [x: Ref, key: Key, val: Val] RETURNS [BOOLEAN] =
  	{ RETURN [Enter[x, key, val, store]] };

  Insert: PUBLIC PROCEDURE [x: Ref, key: Key, val: Val] RETURNS [BOOLEAN] =
  	{ RETURN [Enter[x, key, val, insert]] };

  Enter: ENTRY PROCEDURE [x: Ref, key: Key, val: Val, code: EnterCode]
          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 BEGIN
      	SELECT code FROM
      		store => node.val ← val;
      		replace => { node.val ← val; RETURN [TRUE] };
      		insert => NULL;
      		ENDCASE => ERROR;
      	RETURN [FALSE];
      	END;
      node ← node.next;
      ENDLOOP;
    IF code=replace THEN RETURN [FALSE];
    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...
September 8, 1982 9:17 pm [(LOOPHOLE[Inline.LowHalf[LOOPHOLE[key, LONG UNSPECIFIED]],CARDINAL]/4) MOD mod] changed to [(LOOPHOLE[key, Inline.LongNumber].lowbits/4) MOD mod] in Hash