(*======================================================================*)
(*           Programming Support Routines - Managing Hash Tables        *)
(*======================================================================*)
(*  Version:  2.00              Author:   Dennis Brueni                 *)
(*  Date:     1-20-91           Changes:  original                      *)
(*  Date:     1-25-91           Changes:  Duplicate handling            *)
(*  Date:     1-25-91           Changes:  .Symbol field became pointer  *)
(*  Date:     1-26-91           Changes:  Fixed Bug in CaseSensitive    *)
(*  Date:     3-07-91           Changes:  Duplicate Handling removed    *)
(*                                        CaseSensitive proc. removed   *)
(*                                        Listify function added        *)
(*======================================================================*)
(*  HashTab contains all the routines necessary to create, use, and     *)
(*  maintain a Hash table of size n.  It is assumed herein that the     *)
(*  hash table will be used to store strings.                           *)
(*======================================================================*)
(*  Often one will want to aggregate additional information with a      *)
(*  symbol, so to make this table as general as possible, the symbol    *)
(*  must be sent as a pointer to record of the following form when      *)
(*  performing insertions.  (note: m should be less than 512)           *)
(*                                                                      *)
(*       symbolrec = RECORD OF                                          *)
(*                      Symbol:  POINTER TO ARRAY [0..m] OF CHAR;       *)
(*                      |                                               *)
(*                   END;                                               *)
(*                                                                      *)
(*======================================================================*)

DEFINITION MODULE HashTab;

FROM SYSTEM   IMPORT ADDRESS;
FROM SymLists IMPORT SymList;

(*----------------------------------------------------------------------*)
(*  Opaque definition of the hash table.  Simply a pointer.             *)
(*----------------------------------------------------------------------*)

TYPE HashTable;                         (* opaque defination of a table *)

(*----------------------------------------------------------------------*)
(*  CREATE      Creates a hash table of length n, and initialize it     *)
(*              to empty.                                               *)
(*                                                                      *)
(*  ADVICE      Chose n to be a prime.   Also, n must be <= 8000        *)
(*                                                                      *)
(*  PARAMETERS  HT -- the hash table pointer                            *)
(*              n  -- the size of the hash table                        *)
(*----------------------------------------------------------------------*)

PROCEDURE Create(VAR HT: HashTable; n: CARDINAL);

(*----------------------------------------------------------------------*)
(*  DESTROY     Destroy a hash table.  All information on the table at  *)
(*              time of invocation will be unlinked from the table,     *)
(*              possibly lost...  The hash table will be deallocated    *)
(*              and HT set to NIL.                                      *)
(*                                                                      *)
(*  PARAMETERS  HT -- the hash table pointer                            *)
(*----------------------------------------------------------------------*)

PROCEDURE Destroy(VAR HT: HashTable);

(*----------------------------------------------------------------------*)
(*  INSERT      Add a symbol to the hash table.  Chaining is used to    *)
(*              handle all collisions in the present implementation.    *)
(*                                                                      *)
(*  PARAMETERS  HT          -- the hash table                           *)
(*              SymbolEntry -- a pointer to a record of the form        *)
(*                             described above.                         *)
(*----------------------------------------------------------------------*)

PROCEDURE Insert(HT: HashTable; SymbolEntry: ADDRESS);

(*----------------------------------------------------------------------*)
(*  DELETE      Removes a symbol from the hash table.  If the symbol    *)
(*              was not present this has no effect.                     *)
(*                                                                      *)
(*  PARAMETERS  HT      -- the hash table                               *)
(*              Symbol  -- an array of char (must be null terminated)   *)
(*----------------------------------------------------------------------*)

PROCEDURE Delete(HT: HashTable; Symbol: ARRAY OF CHAR);

(*----------------------------------------------------------------------*)
(*  SEARCH      Search for a symbol in the hash table and return a      *)
(*              pointer to the record which it is found in.             *)
(*                                                                      *)
(*  PARAMETERS  HT      -- the hash table                               *)
(*              Symbol  -- an array of char (must be null terminated)   *)
(*                                                                      *)
(*  RETURNS     NIL if the symbol was not found, or a pointer if found  *)
(*----------------------------------------------------------------------*)

PROCEDURE Search(HT: HashTable; symbol: ARRAY OF CHAR): ADDRESS;

(*----------------------------------------------------------------------*)
(*  LISTIFY     Since HashTab is built upon the SymList module, it is   *)
(*              natural, and sometimes necessary to convert the         *)
(*              contents of a hashtable into a SymList.  The original   *)
(*              hashtable is left unchanged by this function.           *)
(*                                                                      *)
(*  PARAMETERS  HT -- the hashtable                                     *)
(*                                                                      *)
(*  RETURNS     A SymList holding all the entries from the HashTable    *)
(*----------------------------------------------------------------------*)

PROCEDURE Listify(HT: HashTable):SymList;

(************************************************************************)

END HashTab.  