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

(* Last modified on Mon Jun 29 22:12:38 PDT 1992 by muller         *)
(*      modified on Wed May  8 19:52:20 1991 by kalsow         *)


MODULE Atom;

IMPORT Text, Property;

CONST
  MaxHash      = 1024;
  MaxCharIndex = 300000;
  MaxTexts     = 1024;
  NOTEXT       = -1;

TYPE
  Index = [0..MaxCharIndex];

REVEAL
  T = Property.Set BRANDED OBJECT
    start  : Index;
    length : Index;
    class  : INTEGER;
    hash   : INTEGER;
    textID : INTEGER;
    uid    : INTEGER;
    next   : T;
  END;

VAR
  nextChar : Index := 0;
  nTexts   : INTEGER := 0;
  chars    : ARRAY Index OF CHAR;
  hashTable: ARRAY [0..MaxHash - 1] OF T := ARRAY [0..MaxHash-1] OF T {NIL,..};
  texts    : ARRAY [0..MaxTexts] OF Text.T;

PROCEDURE NewFromChars (READONLY a: ARRAY OF CHAR): T =
  VAR j := nextChar;  t: T;  length := NUMBER (a);
  BEGIN
    SUBARRAY (chars, j, length) := a;
    INC (j, length);
    t := Append (j);
    RETURN t;
  END NewFromChars;


PROCEDURE New (n: Text.T): T =
  VAR j := nextChar;  t: T;  length := Text.Length (n);
  BEGIN
    Text.SetChars (SUBARRAY (chars, j, length), n);
    INC (j, length);
    t := Append (j);
    IF t.textID = NOTEXT THEN
      t.textID := nTexts;
      texts[nTexts] := n;
      INC (nTexts); END;
    RETURN t;
  END New;

PROCEDURE Append (finish: Index): T =
  VAR len, hash, bucket: INTEGER; t: T;
  BEGIN
    len  := finish - nextChar;
    hash := 0;
    FOR i := nextChar TO nextChar + len - 1 DO
      hash := 2 * hash + ORD (chars[i]);
    END;
    bucket := hash MOD MaxHash;
    t := hashTable[bucket];
    WHILE (t # NIL) DO
      IF (t.hash = hash)
        AND (t.length = len)
        AND Equal (nextChar, t.start, len) THEN
        (* we found a hit! *)
        RETURN t;
      END;
      t := t.next;
    END;
    (* we didn't find the string *)
    t := NEW (T);
    t.start  := nextChar;
    t.length := len;
    t.class  := 0;
    t.hash   := hash;
    t.next   := hashTable [bucket];
    t.textID := NOTEXT;
    t.uid    := NOTEXT;
    hashTable [bucket] := t;
    chars[finish] := '\000';
    nextChar := finish + 1;
    RETURN t;
  END Append;

PROCEDURE Equal (a, b: Index;  len: INTEGER): BOOLEAN =
  BEGIN
    WHILE (len > 0) DO
      IF (chars[a] # chars[b]) THEN RETURN FALSE END;
      DEC (len);  INC (a);  INC (b);
    END;
    RETURN TRUE;
  END Equal;

PROCEDURE Name (t: T): Text.T =
  BEGIN
    IF (t = NIL) THEN RETURN "" END;
    IF (t.textID = NOTEXT) THEN
      t.textID := nTexts;
      texts [nTexts] := Text.FromChars (SUBARRAY (chars, t.start, t.length));
      INC (nTexts);
    END;
    RETURN texts [t.textID];
  END Name;

BEGIN
END Atom.