(*
    Title: 	HashStrings - Implementation
    LastEdit:	"Mon Sep 17 15:36:39 1984"
    Author: 	Mick Jordan
		Cambridge University Computer Laboratory
*)

(* $T-, $R- module is self checking *)
(*
    This version uses a table of linked lists.
    The computed hash value identifies a table entry and
    this the head of one of the linked lists.
    An object entered in the hashtable is identified by
    the address of the record element in the list.
*)

IMPLEMENTATION MODULE HashStrings;

FROM SYSTEM IMPORT WORD, TSIZE;
FROM Storage IMPORT ALLOCATE, DEALLOCATE;
IMPORT Strings; FROM Strings IMPORT String;

IMPORT Slist;

CONST HashTableUpb = 4096;      (* nominal max size *)

TYPE
    HashPtr = POINTER TO Hash;
    Hash = RECORD
            link: HashPtr;
            s: String;
            value: WORD;
        END (* record *);

    HashId = HashPtr;
    HashTable = POINTER TO RECORD
            size: CARDINAL;
            table: POINTER TO ARRAY [0 .. HashTableUpb] OF HashPtr;
        END (* record *);

VAR
    hashval: CARDINAL;

PROCEDURE New(s: CARDINAL): HashTable;
    VAR
        i: CARDINAL;
        ht: HashTable;
    BEGIN
      NEW(ht);
      WITH ht^ DO
        size := s;
        ALLOCATE(table, s*TSIZE(HashPtr));
        FOR i := 0 TO s-1 DO
            table^[i] := NIL;
        END (* for *);
      END (* with *);
      RETURN ht;
    END New;

PROCEDURE Dispose(ht: HashTable);
    VAR
        h, nh: HashId;
        i: CARDINAL;
    BEGIN
      WITH ht^ DO
        FOR i := 0 TO size-1 DO
            IF table^[i] # NIL THEN
                h := table^[i];
                WHILE h # NIL DO
                    nh := h^.link;
                    DISPOSE(h);
                    h := nh;
                END (* while *);
            END (* if *);
        END (* for *);
        DEALLOCATE(table, size*TSIZE(HashPtr));
      END (* with *);
      DISPOSE(ht);
    END Dispose;

PROCEDURE EnterChars(ht: HashTable; chars: ARRAY OF CHAR; 
                     VAR h: HashId): BOOLEAN;
    BEGIN
        IF LookupChars(ht, chars, h) THEN
            RETURN FALSE;
        ELSE
            NEW(h);
            h^.s := Strings.CopyCS(chars);
            Slist.Add(ht^.table^[hashval], h);
            RETURN TRUE;
        END (* if *);
    END EnterChars;

PROCEDURE EnterString(ht: HashTable; s: String; 
                     VAR h: HashId): BOOLEAN;
    BEGIN
        IF LookupString(ht, s, h) THEN
            RETURN FALSE;
        ELSE
            NEW(h);
            h^.s := Strings.CopySS(s);
            Slist.Add(ht^.table^[hashval], h);
            RETURN TRUE;
        END (* if *);
    END EnterString;

PROCEDURE LookupString(ht: HashTable; s: String;
                      VAR h: HashId): BOOLEAN;
    VAR
        i: CARDINAL;
        lhashval: CARDINAL;
    BEGIN
        i := 0; lhashval := 0;
        WHILE (s^[i] # 0C) DO
            INC(lhashval, CARDINAL(s^[i]));
            INC(i);
        END (* while *);

        lhashval := lhashval MOD ht^.size;
(*        WriteF1("lhashval %N*N", lhashval);				  *)
        h := ht^.table^[lhashval];
        WHILE h # NIL DO
            IF (s^[0] = h^.s^[0]) AND 
               Strings.EqualSS(s, h^.s) THEN
                RETURN TRUE;
            ELSE
                h := h^.link;
            END (* if *);
        END (* while *);
        hashval := lhashval;
        RETURN FALSE;
    END LookupString;

PROCEDURE LookupChars(ht: HashTable; chars: ARRAY OF CHAR;
                      VAR h: HashId): BOOLEAN;
    VAR
        i: CARDINAL;
        lhashval: CARDINAL;
    BEGIN
        i := 0; lhashval := 0;
        WHILE (chars[i] # 0C) AND (i <= HIGH(chars)) DO
            INC(lhashval, CARDINAL(chars[i]));
            INC(i);
        END (* while *);

        lhashval := lhashval MOD ht^.size;
(*        WriteF1("lhashval %N*N", lhashval);				  *)
        h := ht^.table^[lhashval];
        WHILE h # NIL DO
            IF (chars[0] = h^.s^[0]) AND 
               Strings.EqualCS(chars, h^.s) THEN
                RETURN TRUE;
            ELSE
                h := h^.link;
            END (* if *);
        END (* while *);
        hashval := lhashval;
        RETURN FALSE;
    END LookupChars;

PROCEDURE Assoc(ht: HashTable; h: HashId; w: WORD);
(*  Since elements are actually identified by addresses
    which are unique across all hash tables, 'ht' is redundant.
*)
    BEGIN
        h^.value := w;
    END Assoc;

PROCEDURE Retrieve(ht: HashTable; h: HashId): WORD;
    BEGIN
        RETURN h^.value;
    END Retrieve;

PROCEDURE StringAt(ht: HashTable; h: HashId): String;
    BEGIN
        RETURN h^.s;
    END StringAt;

PROCEDURE CharsAt(ht: HashTable; h: HashId; VAR chars: ARRAY OF CHAR);
BEGIN
    Strings.CopySC(h^.s, chars);
END CharsAt;

END HashStrings.