[m-rev.] for review: Add hash table lookup predicates.
Peter Wang
novalazy at gmail.com
Thu Dec 1 13:12:28 AEDT 2022
library/hash_table.m:
Add lookup predicate.
library/version_hash_table.m:
Add lookup predicate.
Use higher-order field type with insts; delete inst casts.
Use predicates instead of functions in a couple of places.
NEWS:
Announce additions.
---
NEWS | 8 +++++
library/hash_table.m | 14 +++++---
library/version_hash_table.m | 70 +++++++++++++-----------------------
3 files changed, 43 insertions(+), 49 deletions(-)
diff --git a/NEWS b/NEWS
index 36950e063..e303cbddb 100644
--- a/NEWS
+++ b/NEWS
@@ -110,6 +110,10 @@ Changes to the Mercury standard library
### Changes to the `hash_table` module
+* The following predicate has been added:
+
+ - pred `lookup/3`
+
* The following obsolete predicates have been removed:
- pred `char_hash/2`
@@ -693,6 +697,10 @@ Changes to the Mercury standard library
### Changes to the `version_hash_table` module
+* The following predicate has been added:
+
+ - pred `lookup/3`
+
* The following obsolete predicates have been removed:
- pred `char_hash/2`
diff --git a/library/hash_table.m b/library/hash_table.m
index 359e5451c..c91ff14bf 100644
--- a/library/hash_table.m
+++ b/library/hash_table.m
@@ -168,6 +168,9 @@
:- 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).
%
@@ -590,11 +593,14 @@ hash_bucket_search(HB, Key, Value) :-
%---------------------------------------------------------------------------%
-lookup(HT, K) =
- ( if V = search(HT, K) then
- V
+lookup(HT, K) = V :-
+ lookup(HT, K, V).
+
+lookup(HT, K, V) :-
+ ( if search(HT, K, V0) then
+ V = V0
else
- func_error($pred, "key not found")
+ error($pred, "key not found")
).
% XXX The convention in other library modules is that
diff --git a/library/version_hash_table.m b/library/version_hash_table.m
index 5a2fa60b1..d4c7a823c 100644
--- a/library/version_hash_table.m
+++ b/library/version_hash_table.m
@@ -108,6 +108,7 @@
% if there is no entry for the key.
%
:- func lookup(version_hash_table(K, V), K) = V.
+:- pred lookup(version_hash_table(K, V)::in, K::in, V::out) is det.
% Field access for hash tables.
% `HT ^ elem(K)' is equivalent to `lookup(HT, K)'.
@@ -157,8 +158,7 @@
% 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.
+ 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
@@ -212,7 +212,7 @@
---> ht(
ht_num_occupants :: int,
ht_max_occupants :: int,
- ht_hash_pred :: hash_pred(K),
+ ht_hash_pred :: pred(K::in, int::out) is det,
ht_buckets :: buckets(K, V)
)
where equality is version_hash_table.equal.
@@ -230,14 +230,16 @@
%---------------------------------------------------------------------------%
-init(HashPred, N, MaxOccupancy) = init_2(HashPred, N, MaxOccupancy, yes).
+init(HashPred, N, MaxOccupancy) = HT :-
+ do_init(HashPred, N, MaxOccupancy, yes, HT).
-unsafe_init(HashPred, N, MaxOccupancy) = init_2(HashPred, N, MaxOccupancy, no).
+unsafe_init(HashPred, N, MaxOccupancy) = HT :-
+ do_init(HashPred, N, MaxOccupancy, no, HT).
-:- func init_2(hash_pred(K)::in(hash_pred), int::in, float::in, bool::in) =
- (version_hash_table(K, V)::out) is det.
+:- pred do_init(hash_pred(K)::in(hash_pred), int::in, float::in, bool::in,
+ version_hash_table(K, V)::out) is det.
-init_2(HashPred, N, MaxOccupancy, NeedSafety) = HT :-
+do_init(HashPred, N, MaxOccupancy, NeedSafety, HT) :-
( if N =< 0 then
error("version_hash_table.init: N =< 0")
else if N >= int.bits_per_int then
@@ -289,10 +291,9 @@ num_occupants(HT) = NumOccupants :-
:- pragma inline(func(find_slot/2)).
find_slot(HT, K) = H :-
- promise_equivalent_solutions [HashPred0] (
- HashPred0 = HT ^ ht_hash_pred
+ promise_equivalent_solutions [HashPred] (
+ HashPred = HT ^ ht_hash_pred
),
- unsafe_hash_pred_cast(HashPred0, HashPred),
find_slot_2(HashPred, K, HT ^ num_buckets, H).
:- pred find_slot_2(hash_pred(K)::in(hash_pred), K::in, int::in, int::out)
@@ -304,30 +305,6 @@ find_slot_2(HashPred, K, NumBuckets, H) :-
% Since NumBuckets is a power of two we can avoid mod.
H = Hash /\ (NumBuckets - 1).
-:- pred unsafe_hash_pred_cast(hash_pred(K)::in, hash_pred(K)::out(hash_pred))
- is det.
-
-:- pragma foreign_proc("C",
- unsafe_hash_pred_cast(HashPred0::in, HashPred::out(hash_pred)),
- [will_not_call_mercury, promise_pure, thread_safe],
-"
- HashPred = HashPred0;
-").
-
-:- pragma foreign_proc("C#",
- unsafe_hash_pred_cast(HashPred0::in, HashPred::out(hash_pred)),
- [will_not_call_mercury, promise_pure, thread_safe],
-"
- HashPred = HashPred0;
-").
-
-:- pragma foreign_proc("Java",
- unsafe_hash_pred_cast(HashPred0::in, HashPred::out(hash_pred)),
- [will_not_call_mercury, promise_pure, thread_safe],
-"
- HashPred = HashPred0;
-").
-
%---------------------------------------------------------------------------%
copy(HT0) = HT :-
@@ -340,6 +317,9 @@ copy(HT0) = HT :-
%---------------------------------------------------------------------------%
search(HT, K) = V :-
+ search(HT, K, V).
+
+search(HT, K, V) :-
H = find_slot(HT, K),
promise_equivalent_solutions [Buckets] (
Buckets = HT ^ ht_buckets
@@ -347,8 +327,6 @@ search(HT, K) = V :-
AL = Buckets ^ elem(H),
alist_search(AL, K, V).
-search(HT, K, search(HT, K)).
-
:- pred alist_search(hash_table_alist(K, V)::in, K::in, V::out) is semidet.
alist_search(AL, K, V) :-
@@ -369,11 +347,14 @@ alist_search(AL, K, V) :-
%---------------------------------------------------------------------------%
-lookup(HT, K) =
- ( if V = search(HT, K) then
- V
+lookup(HT, K) = V :-
+ lookup(HT, K, V).
+
+lookup(HT, K, V) :-
+ ( if search(HT, K, V0) then
+ V = V0
else
- func_error($pred, "key not found")
+ error($pred, "key not found")
).
elem(K, HT) = lookup(HT, K).
@@ -595,15 +576,14 @@ from_assoc_list_2([K - V | T], !HT) :-
% argument is not eliminated, nor is the creation of the type_info
% delayed until the (rare) call to expand.
%
-:- func expand(int, int, hash_pred(K), buckets(K, V)) =
- version_hash_table(K, V).
+:- func expand(int::in, int::in, hash_pred(K)::in(hash_pred),
+ buckets(K, V)::in) = (version_hash_table(K, V)::out) is det.
:- pragma no_inline(func(expand/4)).
-expand(NumOccupants, MaxOccupants0, HashPred0, Buckets0) = HT :-
+expand(NumOccupants, MaxOccupants0, HashPred, Buckets0) = HT :-
NumBuckets0 = size(Buckets0),
NumBuckets = NumBuckets0 + NumBuckets0,
MaxOccupants = MaxOccupants0 + MaxOccupants0,
- unsafe_hash_pred_cast(HashPred0, HashPred),
Buckets1 = version_array.init(NumBuckets, ht_nil),
reinsert_bindings(0, Buckets0, HashPred, NumBuckets, Buckets1, Buckets),
HT = ht(NumOccupants, MaxOccupants, HashPred, Buckets).
--
2.38.0
More information about the reviews
mailing list