94 version_hash_table
%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%--------------------------------------------------%
% Copyright (C) 2004-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: version_hash_table.m.
% Main author: rafe, wangp.
% Stability: low.
%
% (See the header comments in version_array.m for an explanation of version
% types.)
%
% Version hash tables. The "latest" version of the hash table provides roughly
% the same performance as the unique hash table implementation. "Older"
% versions of the hash table are still accessible, but will incur a growing
% performance penalty as more updates are made to the hash table.
%
%--------------------------------------------------%
%--------------------------------------------------%
:- module version_hash_table.
:- interface.
:- import_module assoc_list.
:- import_module char.
%--------------------------------------------------%
:- type version_hash_table(K, V).
:- 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)::in(hash_pred), int::in, float::in) =
(version_hash_table(K, V)::out) is det.
:- pragma obsolete(new/3).
:- func new(hash_pred(K)::in(hash_pred), int::in, float::in) =
(version_hash_table(K, V)::out) is det.
% unsafe_init(HashPred, N, MaxOccupancy)
%
% Like init/3, but the constructed hash table is backed by a non-thread safe
% version array. It is unsafe to concurrently access or update the hash
% table from different threads, or any two hash tables which were produced
% from operations on the same original hash table.
% However, if the hash table or its descendents will not be used in such a
% manner, a non-thread safe hash table can be much faster than a thread
% safe one.
%
:- func unsafe_init(hash_pred(K)::in(hash_pred), int::in, float::in) =
(version_hash_table(K, V)::out) is det.
:- pragma obsolete(unsafe_new/3).
:- func unsafe_new(hash_pred(K)::in(hash_pred), int::in, float::in) =
(version_hash_table(K, V)::out) is det.
% init_default(HashFn) constructs a hash table with default size and
% occupancy arguments.
%
:- func init_default(hash_pred(K)::in(hash_pred)) =
(version_hash_table(K, V)::out) is det.
:- pragma obsolete(new_default/1).
:- func new_default(hash_pred(K)::in(hash_pred)) =
(version_hash_table(K, V)::out) is det.
% unsafe_init_default(HashFn)
%
% Like init_default/3 but the constructed hash table is backed by a
% non-thread safe version array. See the description of unsafe_init/3 above.
%
:- func unsafe_init_default(hash_pred(K)::in(hash_pred)) =
(version_hash_table(K, V)::out) is det.
:- pragma obsolete(unsafe_new_default/1).
:- func unsafe_new_default(hash_pred(K)::in(hash_pred)) =
(version_hash_table(K, V)::out) is det.
% Retrieve the hash_pred associated with a hash table.
%
% :- func hash_pred(version_hash_table(K, V)) = hash_pred(K).
% 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(version_hash_table(K, V)) = int.
% Returns the number of occupants in a hash table.
%
:- func num_occupants(version_hash_table(K, V)) = int.
% Copy the hash table explicitly.
%
% An explicit copy allows programmers to control the cost of copying
% the table. For more information see the comments at the top of the
% version_array module.
%
% This is not a deep copy, it copies only the structure.
%
:- func copy(version_hash_table(K, V)) = version_hash_table(K, V).
% 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(version_hash_table(K, V), K, V) = version_hash_table(K, V).
:- pred set(K::in, V::in,
version_hash_table(K, V)::in, version_hash_table(K, V)::out)
is det.
% Field update for hash tables.
% HT ^ elem(K) := V is equivalent to set(HT, K, V).
%
:- func 'elem :='(K, version_hash_table(K, V), V) = version_hash_table(K, V).
% 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(version_hash_table(K, V), K, V) = version_hash_table(K, V).
:- pred det_insert(K::in, V::in,
version_hash_table(K, V)::in, version_hash_table(K, V)::out)
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(version_hash_table(K, V), K, V) = version_hash_table(K, V).
:- pred det_update(K::in, V::in,
version_hash_table(K, V)::in, version_hash_table(K, V)::out)
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(version_hash_table(K, V), K) = version_hash_table(K, V).
:- pred delete(K::in, version_hash_table(K, V)::in,
version_hash_table(K, V)::out) is det.
% Lookup the value associated with the given key. An exception
% is raised if there is no entry for the key.
%
:- func lookup(version_hash_table(K, V), K) = V.
% Field access for hash tables.
% HT ^ elem(K) is equivalent to lookup(HT, K).
%
:- func version_hash_table(K, V) ^ elem(K) = V.
% Like lookup, but just fails if there is no entry for the key.
%
:- func search(version_hash_table(K, V), K) = V is semidet.
:- pred search(version_hash_table(K, V)::in, K::in, V::out) is semidet.
% Convert a hash table into an association list.
%
:- func to_assoc_list(version_hash_table(K, V)) = assoc_list(K, V).
% 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)::in(hash_pred), int::in, float::in,
assoc_list(K, V)::in) =
(version_hash_table(K, V)::out) 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) =
(version_hash_table(K, V)::out) is det.
% Fold a function over the key-value bindings in a hash table.
%
:- func fold(func(K, V, T) = T, version_hash_table(K, V), T) = T.
% Fold a predicate over the key-value bindings in a hash table.
%
:- pred fold(pred(K, V, T, T), version_hash_table(K, V), T, T).
:- mode fold(in(pred(in, in, in, out) is det), in, in, out) is det.
:- mode fold(in(pred(in, in, mdi, muo) is det), in, mdi, muo) is det.
:- mode fold(in(pred(in, in, di, uo) is det), in, di, uo) is det.
:- mode fold(in(pred(in, in, in, out) is semidet), in, in, out) is semidet.
:- mode fold(in(pred(in, in, mdi, muo) is semidet), in, mdi, muo) is semidet.
:- mode fold(in(pred(in, in, di, uo) is semidet), in, di, uo) is semidet.
%--------------------------------------------------%
%--------------------------------------------------%