-- 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
-- last change: Paul Rovner - May 13, 1983 10:40 am

DIRECTORY
   PrincOps USING [LongNumber],
   RefTab USING [EachPairAction, Key, Val]
   ;

RefTabImpl: CEDAR MONITOR LOCKS x USING x: Ref
      EXPORTS RefTab
      = BEGIN

  Int: TYPE = LONG INTEGER;
  Ref: TYPE = REF RefTabRep;
  RefTabRep: PUBLIC TYPE =
    MONITORED RECORD [mod,size: CARDINAL, 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, PrincOps.LongNumber].lowbits/4) MOD mod];
    END;

  -- public operations

  Create: PUBLIC PROCEDURE [mod: CARDINAL _ 17]
          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[RefTabRep _ [mod: mod, size: 0, 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] _ 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, PrincOps.LongNumber].lowbits/4) MOD mod] in Hash