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

(* File: M3LinkAtom.m3                                         *)
(* Last modified on Mon Mar  2 15:23:54 PST 1992 by kalsow         *)

MODULE M3LinkAtom;

IMPORT Text, TextF;

TYPE
  Bucket = REF RECORD
    next: Bucket;
    hash: INTEGER;
    text: TEXT;
  END;

TYPE
  HashTable = REF ARRAY OF Bucket;

VAR
  atoms    : HashTable := NIL;
  nAtoms   : INTEGER := 0;
  overflow : INTEGER := 0;

PROCEDURE FromChars (READONLY a: ARRAY OF CHAR;  hash: INTEGER): TEXT =
  BEGIN
    RETURN Insert (a, NUMBER (a), NIL, hash);
  END FromChars;

PROCEDURE FromText (a: TEXT;  hash: INTEGER): TEXT =
  BEGIN
    RETURN Insert (a^, LAST (a^), a, hash);
  END FromText;

PROCEDURE Insert (READONLY a: ARRAY OF CHAR;  <*UNUSED*> len: INTEGER;
                                            txt: TEXT;  hash: INTEGER): TEXT =
  VAR bucket: Bucket;  cell: INTEGER;
  BEGIN
    IF (atoms = NIL) THEN Expand () END;

(************
    hash := 0;
    FOR i := 0 TO len - 1 DO
      hash := Word.Plus (Word.Times (17, hash), ORD (a[i]));
      (*** hash := Word.Plus (Word.Plus (hash, hash), ORD (a[i])); ***)
    END;
************)

    cell := hash MOD NUMBER (atoms^);
    bucket := atoms [cell];

    (* search *)
    IF (txt = NIL) THEN
      WHILE (bucket # NIL)
        AND ((bucket.hash # hash)
             OR (a # SUBARRAY (bucket.text^, 0, LAST (bucket.text^)))) DO
        bucket := bucket.next;
      END;
    ELSE
      WHILE (bucket # NIL)
        AND ((bucket.hash # hash)
              OR NOT Text.Equal (txt, bucket.text)) DO
        bucket := bucket.next;
      END;
    END;

    IF (bucket = NIL) THEN
      (* allocate a new bucket *)
      IF (txt = NIL) THEN txt := Text.FromChars (a) END;
      bucket := NEW (Bucket, hash := hash, text := txt);
      bucket.next := atoms[cell];
      atoms[cell] := bucket;
      INC (nAtoms);
      IF (nAtoms >= overflow) THEN Expand () END;
    END;

    RETURN bucket.text;
  END Insert;

PROCEDURE Expand () =
  VAR new: HashTable;  x, y: Bucket;  cell: INTEGER;
  BEGIN
    IF (atoms = NIL) THEN
      (* create the initial table *)
      atoms := NEW (HashTable, 8097);
    ELSE
      (* create a bigger table & rehash the old values *)
      INC (overflow, 7);
      new := NEW (HashTable, overflow);
      FOR i := 0 TO LAST (atoms^) DO
        x := atoms[i];
        WHILE (x # NIL) DO
          y := x.next;
          cell := x.hash MOD overflow;
          x.next := new [cell];
          new [cell] := x;
          x := y;
        END;
      END;
      atoms := new;
    END;
    overflow := 2 * NUMBER (atoms^);
  END Expand;

BEGIN
END M3LinkAtom.