(**********************************************************************

:Program.    OpenHash.mod
:Contens.    Ein Biliotheksmodul für Hashtabellen. 
:Contens.    Nur für das Programm Rechtschreib zu gebrauchen.
:Author.     Bernd Braun
:Address.    Lippestr. 11, D-3300 Braunschweig
:Phone.      0531/845498
:Copyright.  Public Domain
:Language.   Modula-2
:Translator. M2Amiga A+L V3.32d
:Imports.    DynStr, Liste, NewInOut
:History.    V1.0 3.Okt.1990

***********************************************************************)

IMPLEMENTATION MODULE OpenHash;

   FROM ASCII IMPORT
      eol, nul;
   FROM Arts IMPORT
      Assert;
   FROM DynStr IMPORT
      DynString;
   FROM Liste IMPORT
      List, LList, InitList, ExitList, MemberList, InsertList,
      FirstList, NextList;
   FROM NewInOut IMPORT
      FILE, WriteStringFile, WriteFile;
   FROM Storage IMPORT
      Available, ALLOCATE, DEALLOCATE;
   FROM SYSTEM IMPORT
      TSIZE, ADDRESS, ADR, SHIFT;

   CONST
      ErrMsg     = 'OpenHash: Tabelle ist NIL!';
      MemMsg     = 'OpenHash: Kein Speicher mehr!';
      TSADR      = TSIZE ( ADDRESS );
      MaxHashLen = 10;
      (* Es reichen 10 Zeichen zum Berechnen des Hashwertes. *)

   (* Berechnet den Hashwert eines Wortes für die Hashtabelle.
      Sollte eine möglichts gute Streuung erzeugen, und schnell
      zu berechnen sein. *)
   PROCEDURE Hashfunc ( str : DynString ) : LONGINT;
      VAR
         index  : INTEGER;
         Summe  : LONGINT;
         c      : CHAR;
   BEGIN
      index := 0;
      Summe := 0;
      c := str ^ [ index ];
      WHILE ( c # nul ) AND ( index <= MaxHashLen ) DO
         INC ( Summe, ORD ( c ) - ORD ( 'A' ) );
(* $R-   Rangescheck ausschalten
         Summe := SHIFT ( Summe, 1 );
   $R+ *)
         INC ( index );
         c := str ^ [ index ];
      END;
      RETURN Summe;
   END Hashfunc;

   (* Initialisiert eine Hashtabelle mit Max Überlauflisten. *)
   PROCEDURE InitHash ( VAR T   : Table;
                            Max : INTEGER );
      VAR
         i : INTEGER;  (* Hilfsindezies *)
   BEGIN
      (* Ist nicht genug Speicher vorhanden? *)
      Assert ( Available ( TSIZE ( TableHead ) + Max * TSADR),
               ADR ( MemMsg ) );
      ALLOCATE ( T, TSIZE ( TableHead ) );     (* Erzeuge den Tabellenkopf *)
      ALLOCATE ( T ^. Tab , Max * TSADR );       (* Erzeuge das Zeigerfeld *)
                                                 (* für die Überlauflisten *)
      WITH T ^ DO                            (* Initialisiere die Tabellen-*)
         FOR i := 0 TO Max - 1 DO           (* Initialisiere die Überlauf- *)
            InitList ( Tab ^ [ i ] );                            (* listen *)
         END;
         Hash     := Hashfunc;                               (* kopffelder *)
         MaxTable := Max;
      END;
   END InitHash;

   (* Löscht alle Überlauflisten einer Hashtabelle und sie selber. *)
   PROCEDURE ExitHash ( VAR T : Table );
      VAR
         i  : INTEGER;  (* Hilfsindex *)
   BEGIN
      Assert ( T # NIL, ADR ( ErrMsg ) );
      WITH T ^ DO
         FOR i := 0 TO MaxTable - 1 DO        (* Lösche die Überlauflisten *)
            ExitList ( Tab ^ [ i ] );
         END;
         DEALLOCATE ( Tab, MaxTable * TSADR );
      END;
      DEALLOCATE ( T, TSIZE ( TableHead ) );    (* Lösche den Tabellenkopf *)
      T := NIL;                                    (* Die Tabelle ist leer *)
   END ExitHash;

   (* Trägt einen Dynstring in eine Hashtabelle ein. *)
   PROCEDURE InsertHash ( VAR T    : Table;
                              Item : DynString );
   BEGIN
      Assert ( T # NIL, ADR ( ErrMsg ) );
      WITH T ^ DO
         InsertList ( Tab ^ [ Hash ( Item ) MOD MaxTable ], Item );
      END
   END InsertHash;

   (* Sucht einen DynString in einer Hashtabelle. Gibt bei Erfolg TRUE
      zurück, FALSE sonst. *)
   PROCEDURE MemberHash ( T    : Table;
                          Item : DynString ) : BOOLEAN;
   BEGIN
      Assert ( T # NIL, ADR ( ErrMsg ) );
      WITH T ^ DO
         RETURN MemberList ( Tab ^ [ Hash ( Item ) MOD MaxTable ], Item );
      END;
      RETURN FALSE                               (* Eintrag nicht gefunden *)
   END MemberHash;

   (* Schreibt alle DynStrings einer Hashtabelle in ein File. *)
   PROCEDURE PrintTable (    T : Table;
                          file : FILE );
   VAR
      l    : LList;    (* Hilfszeiger (Überlaufliste) *)
      i    : INTEGER;    (* Hilfsindex *)
      Item : DynString;
   BEGIN
      Assert ( T # NIL, ADR ( ErrMsg ) );
      WITH T ^ DO
         FOR i := 0 TO MaxTable - 1 DO
            (* Besuche jede Tabellenposition *)
            l := FirstList ( Tab ^ [ i ], Item );
            (* Besuche die Überlaufliste *)
            WHILE l # NIL DO
               WriteStringFile ( file, Item ^ );
               WriteFile       ( file, eol );
               l := NextList ( Tab ^ [ i ], l, Item );
            END;
         END;
      END;
   END PrintTable;

END OpenHash.