[m-rev.] for review: fix hash table bug
Simon Taylor
stayl at cs.mu.OZ.AU
Thu Mar 20 17:16:50 AEDT 2003
Estimated hours taken: 1
Branches: main, release
NEWS:
library/hash_table.m:
Fix a bug which caused the code to attempt to access
a negative numbered hash bucket.
Replace hash_table__search with a function, for consistency
with the rest of the interface.
tests/hard_coded/Mmakefile:
tests/hard_coded/hash_bug.{m,exp}:
Test case.
Index: NEWS
===================================================================
RCS file: /home/mercury1/repository/mercury/NEWS,v
retrieving revision 1.305
diff -u -u -r1.305 NEWS
--- NEWS 27 Feb 2003 09:21:06 -0000 1.305
+++ NEWS 20 Mar 2003 06:09:50 -0000
@@ -90,6 +90,9 @@
`is_nan_or_inf/1' to float.m. These predicates are for use only on
systems which support IEEE floating point arithmetic.
+* `hash_table__search/3' has been made obsolete and replaced by a function,
+ for consistency with the rest of the interface.
+
* getopt.m now accepts a `maybe_string_special' option type.
* builtin.m now contains types and insts `unify' and `compare' for use
Index: library/hash_table.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/hash_table.m,v
retrieving revision 1.5
diff -u -u -r1.5 hash_table.m
--- library/hash_table.m 13 Mar 2003 01:10:01 -0000 1.5
+++ library/hash_table.m 20 Mar 2003 06:13:37 -0000
@@ -162,8 +162,8 @@
% Like lookup, but just fails if there is no entry for the key.
%
-:- pred search(hash_table(K, V), K, V).
-:- mode search(hash_table_ui, in, out) is semidet.
+:- func 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.
@@ -183,9 +183,19 @@
:- implementation.
-:- import_module math, bool, exception, list, require, std_util.
+% Everything beyond here is not intended as part of the public interface,
+% and will not appear in the Mercury Library Reference Manual.
+:- interface.
+:- pred search(hash_table(K, V), K, V).
+:- mode search(hash_table_ui, in, out) is semidet.
+%:- mode search(in, in, out) is semidet.
+:- pragma obsolete(search/3).
+
+:- implementation.
+
+:- import_module math, bool, exception, list, require, std_util.
:- type hash_table(K, V)
---> ht(
@@ -209,7 +219,7 @@
% odd and is therefore coprime to the number of buckets) and
% probe the table where the Kth probe examines slot
%
- % (H1 + K * H2) `rem` num_buckets
+ % (H1 + K * H2) `mod` num_buckets
%
% The search is guaranteed to terminate because table occupancy
% must be less than 1.0.
@@ -270,15 +280,12 @@
%:- mode find_slot(in, in) = out is det.
find_slot(HT, K) = H :-
- (HT ^ hash_pred)(K, Hash1a, Hash2a),
- int__abs(Hash1a, Hash1),
- int__abs(Hash2a, Hash2),
- H0 = Hash1 rem HT ^ num_buckets,
- Delta = Hash2 + Hash2 + 1, % Have to ensure it's odd and non-zero.
+ (HT ^ hash_pred)(K, Hash1, Hash2),
+ H0 = Hash1 mod HT ^ num_buckets,
+ % Have to ensure it's odd and non-zero.
+ Delta = Hash2 + Hash2 + 1,
H = find_slot_2(HT, K, H0, Delta).
-
-
:- func find_slot_2(hash_table(K, V), K, int, int) = int.
:- mode find_slot_2(hash_table_ui, in, in, in) = out is det.
%:- mode find_slot_2(in, in, in, in) = out is det.
@@ -289,7 +296,7 @@
else if HT ^ keys ^ elem(H0) = K then
H = H0
else
- H1 = (H0 + Delta) rem HT ^ num_buckets,
+ H1 = (H0 + Delta) mod HT ^ num_buckets,
H = find_slot_2(HT, K, H1, Delta)
).
@@ -330,7 +337,9 @@
% ---------------------------------------------------------------------------- %
-search(HT, K, V) :-
+search(HT, K, search(HT, K)).
+
+search(HT, K) = V :-
H = find_slot(HT, K),
bitmap__is_set(HT ^ bitmap, H),
V = HT ^ values ^ elem(H).
@@ -372,7 +381,7 @@
% ---------------------------------------------------------------------------- %
lookup(HT, K) =
- ( if search(HT, K, V)
+ ( if V = search(HT, K)
then V
else throw(software_error("hash_table__lookup: key not found"))
).
Index: tests/hard_coded/Mmakefile
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/Mmakefile,v
retrieving revision 1.195
diff -u -u -r1.195 Mmakefile
--- tests/hard_coded/Mmakefile 15 Mar 2003 07:26:17 -0000 1.195
+++ tests/hard_coded/Mmakefile 20 Mar 2003 05:53:29 -0000
@@ -70,6 +70,7 @@
func_test \
getopt_test \
ground_dd \
+ hash_bug \
hash_init_bug \
higher_order_func_test \
higher_order_syntax \
Index: tests/hard_coded/hash_bug.exp
===================================================================
RCS file: tests/hard_coded/hash_bug.exp
diff -N tests/hard_coded/hash_bug.exp
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/hash_bug.exp 20 Mar 2003 06:10:25 -0000
@@ -0,0 +1 @@
+search failed as expected
Index: tests/hard_coded/hash_bug.m
===================================================================
RCS file: tests/hard_coded/hash_bug.m
diff -N tests/hard_coded/hash_bug.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/hash_bug.m 20 Mar 2003 06:10:20 -0000
@@ -0,0 +1,128 @@
+:- module hash_bug.
+
+:- interface.
+
+:- import_module io.
+
+:- pred main(io__state::di, io__state::uo) is det.
+
+:- implementation.
+
+:- import_module assoc_list, exception, hash_table, list.
+:- import_module map, require, std_util, string.
+
+main(!IO) :-
+ HashPred = (pred(Name::in, Hash1::out, Hash2::out) is det :-
+ sym_name_to_string(Name, ".", Str),
+ Hash1 = hash(Str),
+ Hash2 = hash(from_rev_char_list(to_char_list(Str)))
+ ),
+ HT0 = new(HashPred, 10, 0.8),
+ build_table(entries, HT0, HT),
+ (
+ hash_table__search(HT,
+ qualified(unqualified("io"), "read_word"), _)
+ ->
+ io__write_string("error: search succeeded\n", !IO)
+ ;
+ io__write_string("search failed as expected\n", !IO)
+ ).
+
+:- pred build_table(list(sym_name)::in, name_ht::hash_table_di,
+ name_ht::hash_table_uo) is det.
+
+build_table([], HT, HT).
+build_table([K | T], HT0, HT) :-
+ build_table(T, set(HT0, K, 1), HT).
+
+:- type name_ht == hash_table(sym_name, int).
+
+:- type sym_name
+ ---> unqualified(string)
+ ; qualified(sym_name, string).
+
+ % sym_name_to_string(SymName, Separator, String):
+ % convert a symbol name to a string,
+ % with module qualifiers separated by Separator.
+:- pred sym_name_to_string(sym_name, string, string).
+:- mode sym_name_to_string(in, in, out) is det.
+
+sym_name_to_string(SymName, Separator, String) :-
+ sym_name_to_string_2(SymName, Separator, Parts, []),
+ string__append_list(Parts, String).
+
+:- pred sym_name_to_string_2(sym_name, string,
+ list(string), list(string)).
+:- mode sym_name_to_string_2(in, in, out, in) is det.
+
+sym_name_to_string_2(qualified(ModuleSpec,Name), Separator) -->
+ sym_name_to_string_2(ModuleSpec, Separator),
+ [Separator, Name].
+sym_name_to_string_2(unqualified(Name), _) -->
+ [Name].
+
+:- func entries = list(sym_name).
+
+entries = [
+ unqualified("main"),
+ qualified(unqualified("hash_bug"), "main"),
+ unqualified("build_table"),
+ qualified(unqualified("hash_bug"), "build_table"),
+ unqualified("sym_name_to_string"),
+ qualified(unqualified("hash_bug"), "sym_name_to_string"),
+ unqualified("sym_name_to_string_2"),
+ qualified(unqualified("hash_bug"), "sym_name_to_string_2"),
+ unqualified("copy"),
+ qualified(unqualified("builtin"), "copy"),
+ unqualified("unsafe_promise_unique"),
+ qualified(unqualified("builtin"), "unsafe_promise_unique"),
+ unqualified("unsafe_promise_unique"),
+ qualified(unqualified("builtin"), "unsafe_promise_unique"),
+ unqualified("unsafe_promise_unique"),
+ qualified(unqualified("builtin"), "unsafe_promise_unique"),
+ unqualified("false"),
+ qualified(unqualified("builtin"), "false"),
+ unqualified("promise_only_solution"),
+ qualified(unqualified("builtin"), "promise_only_solution"),
+ unqualified("promise_only_solution"),
+ qualified(unqualified("builtin"), "promise_only_solution"),
+ unqualified("promise_only_solution"),
+ qualified(unqualified("builtin"), "promise_only_solution"),
+ unqualified("promise_only_solution"),
+ qualified(unqualified("builtin"), "promise_only_solution"),
+ unqualified("promise_only_solution"),
+ qualified(unqualified("builtin"), "promise_only_solution"),
+ unqualified("promise_only_solution_io"),
+ qualified(unqualified("builtin"), "promise_only_solution_io"),
+ unqualified("unify"),
+ qualified(unqualified("builtin"), "unify"),
+ unqualified("compare"),
+ qualified(unqualified("builtin"), "compare"),
+ unqualified("ordering"),
+ qualified(unqualified("builtin"), "ordering"),
+ unqualified("@<"),
+ qualified(unqualified("builtin"), "@<"),
+ unqualified("@=<"),
+ qualified(unqualified("builtin"), "@=<"),
+ unqualified("@>"),
+ qualified(unqualified("builtin"), "@>"),
+ unqualified("@>="),
+ qualified(unqualified("builtin"), "@>="),
+ unqualified("get_one_solution"),
+ qualified(unqualified("builtin"), "get_one_solution"),
+ unqualified("get_one_solution"),
+ qualified(unqualified("builtin"), "get_one_solution"),
+ unqualified("get_one_solution"),
+ qualified(unqualified("builtin"), "get_one_solution"),
+ unqualified("get_one_solution_io"),
+ qualified(unqualified("builtin"), "get_one_solution_io"),
+ unqualified("compare_representation"),
+ qualified(unqualified("builtin"), "compare_representation"),
+ unqualified("call_rtti_generic_unify"),
+ qualified(unqualified("builtin"), "call_rtti_generic_unify"),
+ unqualified("call_rtti_generic_compare"),
+ qualified(unqualified("builtin"), "call_rtti_generic_compare"),
+ unqualified("read_char"),
+ qualified(unqualified("io"), "read_char")
+].
+
--------------------------------------------------------------------------
mercury-reviews mailing list
post: mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------
More information about the reviews
mailing list