INTERFACE HashWord;

(***************************************************************************)
(*                      Copyright (C) Olivetti 1989                        *)
(*                          All Rights reserved                            *)
(*                                                                         *)
(* Use and copy of this software and preparation of derivative works based *)
(* upon this software are permitted to any person, provided this same      *)
(* copyright notice and the following Olivetti warranty disclaimer are     *) 
(* included in any copy of the software or any modification thereof or     *)
(* derivative work therefrom made by any person.                           *)
(*                                                                         *)
(* This software is made available AS IS and Olivetti disclaims all        *)
(* warranties with respect to this software, whether expressed or implied  *)
(* under any law, including all implied warranties of merchantibility and  *)
(* fitness for any purpose. In no event shall Olivetti be liable for any   *)
(* damages whatsoever resulting from loss of use, data or profits or       *)
(* otherwise arising out of or in connection with the use or performance   *)
(* of this software.                                                       *)
(***************************************************************************)

(*
  HashWord supports the manipulation of tables of <Key, Value> pairs,
  where Keys are Word.T's and Values are REFANYs.

  The implementation of HashWord is not revealed. To guarantee good
  performance, the user must ensure that tables are kept appropriately
  loaded. However, the package will not fail if a table becomes full.
  Thus clients may assume that the implementation adjusts as the number
  of entries grow, but that performance may suffer.
  
  HashWord tables support iteration over their contents. 'Snapshot 
  semantics' are not supported; if a new entry is made during the course of
  iterating over a table the iterator will raise an exception.

  It is the clients responsibility to control concurrent access to table by 
  multiple threads.  Failure to do so will likely produce a checked runtime 
  error or unpredictable results. A table contains a mutex which can be used
  to serialize access.
*)

IMPORT Thread, Word;

CONST
  NullEntry = 987654321;
(* NOTE: Hashing keys with this value will lead to obscure problems... *)

TYPE
  Table <: Thread.Mutex;  (* The type of a hash table. *)

PROCEDURE New(size: CARDINAL := 0): Table RAISES {};
(* 
  Create a new hash table identified by the returned value.
  The number of entries in the table is unlimited, but the efficiency
  will fall once the number nears 'size'.
  If 'size' is zero a default value is used, which is chosen to be
  adequate for a wide range of applications; it may be insufficient for
  large numbers of entries and it may require too much memory if many
  default sized tables are created.
*)

PROCEDURE Enter(ht: Table; r: Word.T; v: REFANY := NIL): BOOLEAN RAISES {};
(*
  If an entry with key 'r' already exists then return FALSE,
  otherwise enter 'r','v' into 'ht' and RETURN TRUE. (see also 'Lookup').
*)

PROCEDURE Lookup(
    ht: Table; r: Word.T;
    VAR (*out*) v: REFANY
    ): BOOLEAN RAISES {};
(*
  If an entry with key 'r' exists return TRUE, setting 'v' to (any)
  entered value. Otherwise, return FALSE (see also 'Enter').
*)

PROCEDURE Remove(ht: Table; v: Word.T) RAISES {};
(* 
  Remove the given entry from the hash table. It is a checked runtime error
  if 'r' is not in 'ht'.
*)

(*----------------- Iterators over tables -----------------------------*)

TYPE
  Iter <: REFANY;

(* Example usage:

  VAR
    i: HashWord.Iter;
    t: HashWord.Table;
  BEGIN
    ......
    i := HashWord.NewIterator(t);
    ......
    WHILE HashWord.Next(i, key, val) DO
      (* Process <key,value> *)
    END;
*)

PROCEDURE NewIterator(t: Table): Iter RAISES {};
(* Create an iterator on 't'. *)

EXCEPTION Broken;

PROCEDURE Next(
    iter: Iter;
    VAR (*out*) key: Word.T;
    VAR (*out*) val: REFANY)
    : BOOLEAN
    RAISES {Broken};
(* If there is a next <key,value> pair in the table 'table' then
   return TRUE, setting 'key' and 'value' to its components.
   Otherwise return FALSE. If the table has been updated since
   the iterator was created, 'Broken' is raised. *)


END HashWord.