From 4f95defaa9c9e60f3e07f629bde8189fb6af19cf Mon Sep 17 00:00:00 2001 From: Hristian Kirtchev Date: Wed, 26 Sep 2018 09:18:23 +0000 Subject: [PATCH] [Ada] Pair miscount in Dynamic_HTable.Put This patch corrects the logic of GNAT.Dynamic_HTables.Dynamic_HTable.Put to update the number of key-value pairs in the hash table only when the put is adding a new pair, rather than updating the value of an existing pair. 2018-09-26 Hristian Kirtchev gcc/ada/ * libgnat/g-dynhta.adb (Prepend_Or_Replace): Update the number of key-value pairs in the hash table only when adding a brand new pair. gcc/testsuite/ * gnat.dg/dynhash1.adb: New testcase. From-SVN: r264623 --- gcc/ada/ChangeLog | 6 ++++ gcc/ada/libgnat/g-dynhta.adb | 10 ++++-- gcc/testsuite/ChangeLog | 4 +++ gcc/testsuite/gnat.dg/dynhash1.adb | 53 ++++++++++++++++++++++++++++++ 4 files changed, 71 insertions(+), 2 deletions(-) create mode 100644 gcc/testsuite/gnat.dg/dynhash1.adb diff --git a/gcc/ada/ChangeLog b/gcc/ada/ChangeLog index a93f5dfbe0a..b9187b6338e 100644 --- a/gcc/ada/ChangeLog +++ b/gcc/ada/ChangeLog @@ -1,3 +1,9 @@ +2018-09-26 Hristian Kirtchev + + * libgnat/g-dynhta.adb (Prepend_Or_Replace): Update the number + of key-value pairs in the hash table only when adding a brand + new pair. + 2018-09-26 Sergey Rybin * doc/gnat_ugn/gnat_utility_programs.rst: Add note about diff --git a/gcc/ada/libgnat/g-dynhta.adb b/gcc/ada/libgnat/g-dynhta.adb index 004c276070b..e442514f3b2 100644 --- a/gcc/ada/libgnat/g-dynhta.adb +++ b/gcc/ada/libgnat/g-dynhta.adb @@ -544,6 +544,9 @@ package body GNAT.Dynamic_HTables is Detach (Nod); Free (Nod); + -- The number of key-value pairs is updated when the hash table + -- contains a valid node which represents the pair. + T.Pairs := T.Pairs - 1; -- Compress the hash table if the load factor drops below @@ -1121,6 +1124,11 @@ package body GNAT.Dynamic_HTables is Nod := new Node'(Key, Value, null, null); Prepend (Nod, Head); + + -- The number of key-value pairs must be updated for a prepend, + -- never for a replace. + + T.Pairs := T.Pairs + 1; end Prepend_Or_Replace; -- Local variables @@ -1148,8 +1156,6 @@ package body GNAT.Dynamic_HTables is Prepend_Or_Replace (Head); - T.Pairs := T.Pairs + 1; - -- Expand the hash table if the ratio of pairs to buckets goes over -- Expansion_Threshold. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 459563f3eb9..6cb08cdafbb 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2018-09-26 Hristian Kirtchev + + * gnat.dg/dynhash1.adb: New testcase. + 2018-09-26 Hristian Kirtchev * gnat.dg/sets1.adb: New testcase. diff --git a/gcc/testsuite/gnat.dg/dynhash1.adb b/gcc/testsuite/gnat.dg/dynhash1.adb new file mode 100644 index 00000000000..cbe241a4c7c --- /dev/null +++ b/gcc/testsuite/gnat.dg/dynhash1.adb @@ -0,0 +1,53 @@ +with Ada.Text_IO; use Ada.Text_IO; +with GNAT; use GNAT; +with GNAT.Dynamic_HTables; use GNAT.Dynamic_HTables; + +procedure Dynhash1 is + function Hash (Key : Integer) return Bucket_Range_Type is + begin + return Bucket_Range_Type (Key); + end Hash; + + package Integer_Hash_Tables is new Dynamic_HTable + (Key_Type => Integer, + Value_Type => Integer, + No_Value => 0, + Expansion_Threshold => 1.3, + Expansion_Factor => 2, + Compression_Threshold => 0.3, + Compression_Factor => 2, + "=" => "=", + Hash => Hash); + use Integer_Hash_Tables; + + Siz : Natural; + T : Instance; + +begin + T := Create (8); + + Put (T, 1, 1); + Put (T, 1, 2); + Put (T, 1, 3); + + Siz := Size (T); + + if Siz /= 1 then + Put_Line ("ERROR: Put: wrong size"); + Put_Line ("expected: 1"); + Put_Line ("got :" & Siz'Img); + end if; + + Delete (T, 1); + Delete (T, 1); + + Siz := Size (T); + + if Siz /= 0 then + Put_Line ("ERROR: Delete: wrong size"); + Put_Line ("expected: 0"); + Put_Line ("got :" & Siz'Img); + end if; + + Destroy (T); +end Dynhash1; -- 2.30.2