31 hash_table
%--------------------------------------------------%
% vim: ts=4 sw=4 et tw=0 wm=0 ft=mercury
%--------------------------------------------------%
% Copyright (C) 2001, 2003-2006, 2010-2012 The University of Melbourne
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% File: hash_table.m.
% Main author: rafe, wangp.
% Stability: low.
%
% Hash table implementation.
%
% This implementation requires the user to supply a predicate that
% will compute a hash value for any given key.
%
% Default hash functions are provided for ints, strings and generic
% values.
%
% The number of buckets in the hash table is always a power of 2.
%
% When a user set occupancy level is achieved, the number of buckets
% in the table is doubled and the previous contents reinserted into
% the new hash table.
%
% CAVEAT: the user is referred to the warning at the head of array.m
% with regard to the current use of unique objects. Briefly, the
% problem is that the compiler does not yet properly understand
% unique modes, hence we fake it using non-unique modes.
% This means that care must be taken not to use an old version of a
% destructively updated structure (such as a hash_table) since the
% compiler will not currently detect such errors.
%
%--------------------------------------------------%
%--------------------------------------------------%
:- module hash_table.
:- interface.
:- import_module array.
:- import_module assoc_list.
:- import_module char.
%--------------------------------------------------%
:- type hash_table(K, V).
% XXX This is all fake until the compiler can handle nested unique modes.
%
:- inst hash_table == bound(ht(ground, ground, hash_pred, array)).
:- mode hash_table_ui == in(hash_table).
:- mode hash_table_di == di(hash_table).
:- mode hash_table_uo == out(hash_table).
:- type hash_pred(K) == ( pred(K, int) ).
:- inst hash_pred == ( pred(in, out) is det ).
% init(HashPred, N, MaxOccupancy)
% constructs a new hash table with initial size 2 ^ N that is
% doubled whenever MaxOccupancy is achieved; elements are
% indexed using HashPred.
%
% HashPred must compute a hash for a given key.
% N must be greater than 0.
% MaxOccupancy must be in (0.0, 1.0).
%
% XXX Values too close to the limits may cause bad things
% to happen.
%
:- func init(hash_pred(K), int, float) = hash_table(K, V).
:- mode init(in(hash_pred), in, in) = hash_table_uo is det.
% A synonym for the above.
%
:- pragma obsolete(new/3).
:- func new(hash_pred(K), int, float) = hash_table(K, V).
:- mode new(in(hash_pred), in, in) = hash_table_uo is det.
% init_default(HashFn) constructs a hash table with default size and
% occupancy arguments.
%
:- func init_default(hash_pred(K)) = hash_table(K, V).
:- mode init_default(in(hash_pred)) = hash_table_uo is det.
% A synonym for the above.
%
:- pragma obsolete(new_default/1).
:- func new_default(hash_pred(K)) = hash_table(K, V).
:- mode new_default(in(hash_pred)) = hash_table_uo is det.
% Retrieve the hash_pred associated with a hash table.
%
:- func hash_pred(hash_table(K, V)) = hash_pred(K).
:- mode hash_pred(hash_table_ui) = out(hash_pred) is det.
% Default hash_preds for ints and strings and everything (buwahahaha!)
%
:- pred int_hash(int::in, int::out) is det.
:- pred string_hash(string::in, int::out) is det.
:- pred char_hash(char::in, int::out) is det.
:- pred float_hash(float::in, int::out) is det.
:- pred generic_hash(T::in, int::out) is det.
% Returns the number of buckets in a hash table.
%
:- func num_buckets(hash_table(K, V)) = int.
:- mode num_buckets(hash_table_ui) = out is det.
%:- mode num_buckets(in) = out is det.
% Returns the number of occupants in a hash table.
%
:- func num_occupants(hash_table(K, V)) = int.
:- mode num_occupants(hash_table_ui) = out is det.
%:- mode num_occupants(in) = out is det.
% Copy the hash table.
%
% This is not a deep copy, it copies only enough of the structure to
% create a new unique table.
%
:- func copy(hash_table(K, V)) = hash_table(K, V).
:- mode copy(hash_table_ui) = hash_table_uo is det.
% Insert key-value binding into a hash table; if one is
% already there then the previous value is overwritten.
% A predicate version is also provided.
%
:- func set(hash_table(K, V), K, V) = hash_table(K, V).
:- mode set(hash_table_di, in, in) = hash_table_uo is det.
:- pred set(K::in, V::in,
hash_table(K, V)::hash_table_di, hash_table(K, V)::hash_table_uo) is det.
% Field update for hash tables.
% HT ^ elem(K) := V is equivalent to set(HT, K, V).
%
:- func 'elem :='(K, hash_table(K, V), V) = hash_table(K, V).
:- mode 'elem :='(in, hash_table_di, in) = hash_table_uo is det.
% Insert a key-value binding into a hash table. An
% exception is thrown if a binding for the key is already
% present. A predicate version is also provided.
%
:- func det_insert(hash_table(K, V), K, V) = hash_table(K, V).
:- mode det_insert(hash_table_di, in, in) = hash_table_uo is det.
:- pred det_insert(K::in, V::in,
hash_table(K, V)::hash_table_di, hash_table(K, V)::hash_table_uo) is det.
% Change a key-value binding in a hash table. An
% exception is thrown if a binding for the key does not
% already exist. A predicate version is also provided.
%
:- func det_update(hash_table(K, V), K, V) = hash_table(K, V).
:- mode det_update(hash_table_di, in, in) = hash_table_uo is det.
:- pred det_update(K::in, V::in,
hash_table(K, V)::hash_table_di, hash_table(K, V)::hash_table_uo) is det.
% Delete the entry for the given key, leaving the hash table
% unchanged if there is no such entry. A predicate version is also
% provided.
%
:- func delete(hash_table(K, V), K) = hash_table(K, V).
:- mode delete(hash_table_di, in) = hash_table_uo is det.
:- pred delete(K::in,
hash_table(K, V)::hash_table_di, hash_table(K, V)::hash_table_uo) is det.
% Lookup the value associated with the given key. An exception
% is raised if there is no entry for the key.
%
:- func lookup(hash_table(K, V), K) = V.
:- mode lookup(hash_table_ui, in) = out is det.
%:- mode lookup(in, in) = out is det.
% Field access for hash tables.
% HT ^ elem(K) is equivalent to lookup(HT, K).
%
:- func elem(K, hash_table(K, V)) = V.
:- mode elem(in, hash_table_ui) = out is det.
%:- mode elem(in, in) = out is det.
% Like lookup, but just fails if there is no entry for the key.
%
:- func search(hash_table(K, V), K) = V.
:- mode search(hash_table_ui, in) = out is semidet.
%:- mode search(in, in, out) is semidet.
:- pred search(hash_table(K, V), K, V).
:- mode search(hash_table_ui, in, out) is semidet.
%:- mode search(in, in, out) is semidet.
% Convert a hash table into an association list.
%
:- func to_assoc_list(hash_table(K, V)) = assoc_list(K, V).
:- mode to_assoc_list(hash_table_ui) = out is det.
%:- mode to_assoc_list(in) = out is det.
% from_assoc_list(HashPred, N, MaxOccupancy, AssocList) = Table:
%
% Convert an association list into a hash table. The first three
% parameters are the same as for init/3 above.
%
:- func from_assoc_list(hash_pred(K), int, float, assoc_list(K, V)) =
hash_table(K, V).
:- mode from_assoc_list(in(hash_pred), in, in, in) = hash_table_uo is det.
% A simpler version of from_assoc_list/4, the values for N and
% MaxOccupancy are configured with defaults such as in init_default/1
%
:- func from_assoc_list(hash_pred(K)::in(hash_pred), assoc_list(K, V)::in) =
(hash_table(K, V)::hash_table_uo) is det.
% Fold a function over the key-value bindings in a hash table.
%
:- func fold(func(K, V, T) = T, hash_table(K, V), T) = T.
:- mode fold(func(in, in, in) = out is det, hash_table_ui, in) = out is det.
:- mode fold(func(in, in, di) = uo is det, hash_table_ui, di) = uo is det.
% Fold a predicate over the key-value bindings in a hash table.
%
:- pred fold(pred(K, V, T, T), hash_table(K, V), T, T).
:- mode fold(in(pred(in, in, in, out) is det), hash_table_ui,
in, out) is det.
:- mode fold(in(pred(in, in, mdi, muo) is det), hash_table_ui,
mdi, muo) is det.
:- mode fold(in(pred(in, in, di, uo) is det), hash_table_ui,
di, uo) is det.
:- mode fold(in(pred(in, in, in, out) is semidet), hash_table_ui,
in, out) is semidet.
:- mode fold(in(pred(in, in, mdi, muo) is semidet), hash_table_ui,
mdi, muo) is semidet.
:- mode fold(in(pred(in, in, di, uo) is semidet), hash_table_ui,
di, uo) is semidet.
%--------------------------------------------------%
%--------------------------------------------------%