%--------------------------------------------------%
% vim: ts=4 sw=4 et ft=mercury
%--------------------------------------------------%
% Copyright (C) 2001, 2003-2006, 2010-2012 The University of Melbourne
% Copyright (C) 2013-2023 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: hash_table.m.
% Main author: rafe, wangp.
% Stability: low.
%
% Hash table implementation.
%
% This implementation requires the user to supply a predicate that
% computes 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 the occupancy reaches a level set by the user, we create automatically
% a new hash table with double the number of buckets, insert the contents
% of the old table into it, and use it to replace the old one.
%
% CAVEAT: The warning at the head of array.m about the use of unique objects
% also applies here. 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.
%--------------------------------------------------%
:- type hash_table(K, V).
% XXX This is all fake until the compiler can handle nested unique modes.
%
:- inst hash_table for hash_table/2
== 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 whose initial size is 2 ^ N, and whose
% size 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.
% 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.
%--------------------------------------------------%
% 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.
% 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 overwrite the previous value.
%
:- 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. Throw an exception
% if a binding for the key is already present.
%
:- 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. Throw an exception
% if a binding for the key does not already exist.
%
:- 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.
%
:- 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.
% Fail 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.
% Lookup the value associated with the given key.
% Throw an exception 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.
:- pred lookup(hash_table(K, V), K, V).
:- mode lookup(hash_table_ui, 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.
%--------------------------------------------------%
% 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(in(func(in, in, in) = out is det), hash_table_ui, in) = out
is det.
:- mode fold(in(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, A, A), hash_table(K, V), A, A).
:- 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.
:- pred fold2(pred(K, V, A, A, B, B), hash_table(K, V), A, A, B, B).
:- mode fold2(in(pred(in, in, in, out, in, out) is det), hash_table_ui,
in, out, in, out) is det.
:- mode fold2(in(pred(in, in, in, out, mdi, muo) is det), hash_table_ui,
in, out, mdi, muo) is det.
:- mode fold2(in(pred(in, in, in, out, di, uo) is det), hash_table_ui,
in, out, di, uo) is det.
:- mode fold2(in(pred(in, in, in, out, in, out) is semidet), hash_table_ui,
in, out, in, out) is semidet.
:- mode fold2(in(pred(in, in, in, out, mdi, muo) is semidet), hash_table_ui,
in, out, mdi, muo) is semidet.
:- mode fold2(in(pred(in, in, in, out, di, uo) is semidet), hash_table_ui,
in, out, di, uo) is semidet.
:- pred fold3(pred(K, V, A, A, B, B, C, C), hash_table(K, V), A, A, B, B,
C, C).
:- mode fold3(in(pred(in, in, in, out, in, out, in, out) is det),
hash_table_ui, in, out, in, out, in, out) is det.
:- mode fold3(in(pred(in, in, in, out, in, out, mdi, muo) is det),
hash_table_ui, in, out, in, out, mdi, muo) is det.
:- mode fold3(in(pred(in, in, in, out, in, out, di, uo) is det),
hash_table_ui, in, out, in, out, di, uo) is det.
:- mode fold3(in(pred(in, in, in, out, in, out, in, out) is semidet),
hash_table_ui, in, out, in, out, in, out) is semidet.
:- mode fold3(in(pred(in, in, in, out, in, out, mdi, muo) is semidet),
hash_table_ui, in, out, in, out, mdi, muo) is semidet.
:- mode fold3(in(pred(in, in, in, out, in, out, di, uo) is semidet),
hash_table_ui, in, out, in, out, di, uo) is semidet.
%--------------------------------------------------%
%--------------------------------------------------%