[m-rev.] reviewed 3/3: Add two new functions to version_hash_table and hash_table

Paul Bone paul at bone.id.au
Tue May 7 11:56:52 AEST 2013


This has already been reviewed by Julien, this diff contains work based on
Julien's feedback.

Add two new functions to version_hash_table and hash_table

library/version_hash_table.m:
    Provide a new from_assoc_list function that gives the caller more
    control over the new hash table.

    Provide a new function named copy to make a copy of a hash table,
    this makes it easier for programmers to reason about performance when
    using version hash tables.

library/hash_table.m:
    Add the same functions to hash_table.m so both modules have the same
    interface.

NEWS:
    Announce the change.
---
 NEWS                         |  3 +++
 library/hash_table.m         | 30 +++++++++++++++++++++++++++++-
 library/version_hash_table.m | 32 +++++++++++++++++++++++++++++++-
 3 files changed, 63 insertions(+), 2 deletions(-)

diff --git a/NEWS b/NEWS
index 80789f7..75382fc 100644
--- a/NEWS
+++ b/NEWS
@@ -45,6 +45,9 @@ Changes to the Mercury standard library:
 * We have added predicates to the calendar module for folding over the days
   in a given range of dates: foldl_days/5, foldl2_days/7 and  foldl3_days/9.
 
+* We have added two functions to both the hash_table and version_hash_table
+  modules: copy/1 and from_assoc_list/4.
+
 Changes to the Mercury compiler:
 
 * The option `--warn-non-tail-recursion' no longer requires
diff --git a/library/hash_table.m b/library/hash_table.m
index 215541e..4ec4959 100644
--- a/library/hash_table.m
+++ b/library/hash_table.m
@@ -114,6 +114,14 @@
 :- 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 the previous value is overwritten.
     % A predicate version is also provided.
@@ -190,7 +198,17 @@
 :- mode to_assoc_list(hash_table_ui) = out is det.
 %:- mode to_assoc_list(in) = out is det.
 
-    % Convert an association list into a hash table.
+    % 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.
@@ -320,6 +338,13 @@ find_slot_2(HashPred, K, NumBuckets, H) :-
 
 %-----------------------------------------------------------------------------%
 
+copy(Orig) = Copy :-
+    Orig = ht(NumOccupants, MaxOccupants, HashPred, Buckets0),
+    array.copy(Buckets0, Buckets),
+    Copy = ht(NumOccupants, MaxOccupants, HashPred, Buckets).
+
+%-----------------------------------------------------------------------------%
+
 set(HT0, K, V) = HT :-
     H = find_slot(HT0, K),
     HT0 = ht(NumOccupants0, MaxOccupants, HashPred, Buckets0),
@@ -528,6 +553,9 @@ to_assoc_list_2(X, AL0, AL) :-
         to_assoc_list_2(T, AL1, AL)
     ).
 
+from_assoc_list(HashPred, N, MaxOccupants, AList) = HT :-
+    from_assoc_list_2(AList, init(HashPred, N, MaxOccupants), HT).
+
 from_assoc_list(HashPred, AList) = HT :-
     from_assoc_list_2(AList, init_default(HashPred), HT).
 
diff --git a/library/version_hash_table.m b/library/version_hash_table.m
index e4fada5..04d3389 100644
--- a/library/version_hash_table.m
+++ b/library/version_hash_table.m
@@ -112,6 +112,16 @@
     %
 :- 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.
@@ -171,7 +181,17 @@
     %
 :- func to_assoc_list(version_hash_table(K, V)) = assoc_list(K, V).
 
-    % Convert an association list into a hash table.
+    % 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.
@@ -323,6 +343,13 @@ find_slot_2(HashPred, K, NumBuckets, H) :-
 
 %-----------------------------------------------------------------------------%
 
+copy(HT0) = HT :-
+    HT0 = ht(NumOccupants, MaxOccupants, HashPred, Buckets0),
+    copy(Buckets0, Buckets),
+    HT = ht(NumOccupants, MaxOccupants, HashPred, Buckets).
+
+%-----------------------------------------------------------------------------%
+
 set(HT0, K, V) = HT :-
     H = find_slot(HT0, K),
     HT0 = ht(NumOccupants0, MaxOccupants, HashPred, Buckets0),
@@ -529,6 +556,9 @@ to_assoc_list_2(X, AL0, AL) :-
         to_assoc_list_2(T, AL1, AL)
     ).
 
+from_assoc_list(HashPred, N, MaxOccupants, AList) = HT :-
+    from_assoc_list_2(AList, init(HashPred, N, MaxOccupants), HT).
+
 from_assoc_list(HashPred, AList) = HT :-
     from_assoc_list_2(AList, init_default(HashPred), HT).
 
-- 
1.8.1.3




More information about the reviews mailing list