(* Copyright (C) 1989, Digital Equipment Corporation           *)
(* All rights reserved.                                        *)
(* See the file COPYRIGHT for a full description.              *)

(* File: M3LinkMap.m3                                          *)
(* Last Modified On Wed Dec  4 15:59:42 PST 1991 By kalsow     *)

UNSAFE MODULE M3LinkMap;

IMPORT Text;

TYPE
  KeyPtr = REF Key;

REVEAL
  T = BRANDED "M3LinkMap.T" REF RECORD
          n_used : INTEGER := 0;
          data   : REF ARRAY OF KeyPtr;
        END;

PROCEDURE New (initialSize: CARDINAL): T =
  VAR t := NEW (T);
  BEGIN
    t.data := NEW (REF ARRAY OF KeyPtr, MAX (16, initialSize));
    RETURN t;
  END New;

PROCEDURE Get (t: T;  READONLY k: Key): Value =
  VAR x0 := k.hash MOD NUMBER (t.data^);
  VAR x := x0;
  VAR z: KeyPtr;
  BEGIN
    LOOP
      z := t.data [x];
      IF (z = NIL) OR Text.Equal (z.text, k.text) THEN RETURN z END;
      INC (x);
      IF (x > LAST (t.data^)) THEN x := 0 END;
      IF (x = x0) THEN RETURN NIL END;
    END;
  END Get;

PROCEDURE GetDirect (t: T;  index: INTEGER): Value =
  BEGIN
    IF (0 <= index) AND (index <= LAST (t.data^))
      THEN RETURN t.data[index];
      ELSE RETURN NIL;
    END;
  END GetDirect;

PROCEDURE GetIndex (t: T;  READONLY k: Key): INTEGER =
  VAR x0 := k.hash MOD NUMBER (t.data^);
  VAR x := x0;
  VAR z: KeyPtr;
  BEGIN
    LOOP
      z := t.data [x];
      IF (z = NIL) THEN RETURN MISSING END;
      IF Text.Equal (z.text, k.text) THEN RETURN x END;
      INC (x);
      IF (x > LAST (t.data^)) THEN x := 0 END;
      IF (x = x0) THEN RETURN MISSING END;
    END;
  END GetIndex;

PROCEDURE Insert (t: T;  READONLY k: Key;  v: Value) =
  VAR x0 := k.hash MOD NUMBER (t.data^);
  VAR x := x0;
  VAR z: KeyPtr;
  BEGIN
    LOOP
      z := t.data [x];
      IF (z = NIL) OR Text.Equal (z.text, k.text) THEN (* insert it here *)
        t.data [x] := LOOPHOLE (v, KeyPtr);  (**** UNSAFE ****)
        IF (z = NIL) THEN
          INC (t.n_used);
          IF (2 * t.n_used > NUMBER (t.data^)) THEN Expand (t) END;
        END;
        RETURN;
      END;
      INC (x);
      IF (x > LAST (t.data^)) THEN x := 0 END;
      IF (x = x0) THEN (* no free slots *) Expand (t) END;
    END;
  END Insert;

PROCEDURE Expand (t: T) =
  VAR new := NEW (REF ARRAY OF KeyPtr, 2 * NUMBER (t.data^));
  VAR old := t.data;
  VAR key : KeyPtr;
  BEGIN
    t.n_used := 0;
    t.data   := new;
    FOR i := 0 TO LAST (old^) DO
      key := old[i];
      IF (key # NIL) THEN Insert (t, key^, key) END;
    END;
  END Expand;

PROCEDURE GetData (t: T): REF ARRAY OF Value =
  BEGIN
    IF (t = NIL)
      THEN RETURN NIL
      ELSE RETURN LOOPHOLE (t.data, REF ARRAY OF Value);
    END;
  END GetData;

(****************
PROCEDURE Copy (t: T): T =
  VAR u := NEW (T);
  BEGIN
    IF (t = NIL) THEN RETURN New () END;
    u.n_used := t.n_used;
    u.data := NEW (REF ARRAY OF KeyPtr, NUMBER (t.data^));
    FOR i := FIRST (t.data^) TO LAST (t.data^) DO u.data[i] := t.data[i] END;
    RETURN u;
  END Copy;
*****************)

BEGIN
END M3LinkMap.