[m-rev.] for review: chaining hash tables

[Julien Fischer]

On Wed, 25 Mar 2009, Peter Wang wrote:

> Branches: main
>
> Replace the implementations of (version) hash tables by separate chaining hash
> tables.  The old open addressing scheme was broken in the presence of deletes.
> Fixes bug #68.

Thanks for doing this!

> library/hash_table.m:
> library/version_hash_table.m:
> 	As above.
>
> 	We no longer use double hashing in case of a hash collision, so hash
> 	predicates only need to return one value now.
>
> 	Add fold with predicate arguments.
>
> library/array.m:
> 	Add array.foldl for a predicate argument.
>
> 	Add array.foldl2 with a unique state pair.
>
> library/version_array.m:
> 	Add version_array.foldl for a predicate argument.
>
> compiler/make.m:
> compiler/make.program_target.m:
> compiler/make.util.m:
> library/robdd.m:
> 	Conform to change in hashing predicates.
>
> deep_profiler/dense_bitset.m:
> 	Add module qualifier to avoid ambiguity.
>
> tests/hard_coded/Mmakefile:
> tests/hard_coded/hash_table_delete.exp:
> tests/hard_coded/hash_table_delete.m:
> tests/hard_coded/hash_table_test.exp:
> tests/hard_coded/hash_table_test.m:
> tests/hard_coded/version_hash_table_delete.exp:
> tests/hard_coded/version_hash_table_delete.m:
> tests/hard_coded/version_hash_table_test2.exp:
> tests/hard_coded/version_hash_table_test2.m:
> 	Add new test cases.
>
> tests/hard_coded/hash_bug.m:
> tests/hard_coded/hash_init_bug.m:
> tests/hard_coded/version_hash_table_test.m:
> 	Conform to change in hashing predicates.
>
> NEWS:
> 	Document additions.
>

...

> diff --git a/library/array.m b/library/array.m
> index fc89794..e7d33a4 100644
> --- a/library/array.m
> +++ b/library/array.m
> @@ -376,9 +376,23 @@
> %:- mode array.foldl(func(in, di) = uo is det, array_ui, di) = uo is det.
> :- mode array.foldl(func(in, di) = uo is det, in, di) = uo is det.
>
> +    % array.foldl(Pr, Array, !X) is equivalent to
> +    %   list.foldl(Pr, array.to_list(Array), !X)
> +    % but more efficient.
> +    %
> +:- pred array.foldl(pred(T1, T2, T2), array(T1), T2, T2).
> +:- mode array.foldl(pred(in, in, out) is det, in, in, out) is det.
> +:- mode array.foldl(pred(in, di, uo) is det, in, di, uo) is det.

Please also add the (mdi, muo) mode, here and below.

> +
> +    % array.foldl2(Pr, Array, !X, !Y) is equivalent to
> +    %   list.foldl2(Pr, array.to_list(Array), !X, !Y)
> +    % but more efficient.
> +    %
> :- pred array.foldl2(pred(T1, T2, T2, T3, T3), array(T1), T2, T2, T3, T3).
> :- mode array.foldl2(pred(in, in, out, in, out) is det, in, in, out, in, out)
>     is det.
> +:- mode array.foldl2(pred(in, in, out, di, uo) is det, in, in, out, di, uo)
> +    is det.
>
>     % array.foldr(Fn, Array, X) is equivalent to
>     %   list.foldr(Fn, array.to_list(Array), X)

That looks fine.

Julien.
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------