hash-sets,hashtables: make it so the array backing the hash is non-empty

Commit 70c7f9e02910746918cc16bf588ef543fda80790 made it so the code
assumes the array is not empty. But it can be empty if the hashtable is
created using "hashtable new" and then it can crash because it reads
uninitialized memory. Setting the initial of the array slot to
a valid hash-array should fix that.

diff --git a/core/hash-sets/hash-sets.factor b/core/hash-sets/hash-sets.factor
index 03577db12a7180066509d67fd3b877fa57a74746..6bbd327371b56edd4a523cf8de16efbe932f0ef9 100644 (file)
--- a/core/hash-sets/hash-sets.factor
+++ b/core/hash-sets/hash-sets.factor
@@ -10,7 +10,10 @@ IN: hash-sets
 TUPLE: hash-set
     { count array-capacity }
     { deleted array-capacity }
-    { array array } ;
+    { array array initial: {
+          T{ tombstone } T{ tombstone } T{ tombstone } T{ tombstone }
+      }
+    } ;
 
 <PRIVATE
 

diff --git a/core/hashtables/hashtables-tests.factor b/core/hashtables/hashtables-tests.factor
index a238eef90dbd1192701f929c256da38b9f51fa06..1ae6ad353ce689df3b742362f27dc61826ce88a5 100644 (file)
--- a/core/hashtables/hashtables-tests.factor
+++ b/core/hashtables/hashtables-tests.factor
@@ -1,5 +1,11 @@
-USING: accessors assocs continuations fry hashtables kernel make
-math namespaces sequences tools.test ;
+USING: accessors arrays assocs continuations fry hashtables
+hashtables.private kernel make math memory namespaces sequences
+tools.test ;
+
+! hash@
+{ 18 } [
+    77 20 f <array> hash@
+] unit-test
 
 { H{ } } [ { } [ dup ] H{ } map>assoc ] unit-test
 
@@ -182,5 +188,14 @@ H{ } "x" set
 
 { 1 } [ 2 "h" get at ] unit-test
 
+! Previously this could break as hashtable new created a backing an
+! empty backing array and the code assumed its length was > 0.
+{ f f } [
+    compact-gc 77 hashtable new [ clone ] change-array at*
+] unit-test
+
 ! Random test case
-{ "A" } [ 100 iota [ dup ] H{ } map>assoc 32 over delete-at "A" 32 pick set-at 32 of ] unit-test
+{ "A" } [
+    100 iota [ dup ] H{ } map>assoc 32 over
+    delete-at "A" 32 pick set-at 32 of
+] unit-test

diff --git a/core/hashtables/hashtables.factor b/core/hashtables/hashtables.factor
index ee14103cb835952af7b5d5b4cc7aaaac3596c287..6e2903d8ee295581d1fcb430494c880d1cc5aeb3 100644 (file)
--- a/core/hashtables/hashtables.factor
+++ b/core/hashtables/hashtables.factor
@@ -4,10 +4,16 @@ USING: accessors arrays assocs kernel kernel.private math
 math.private sequences sequences.private slots.private vectors ;
 IN: hashtables
 
+! Required because the hashtable definition references tombstone.
+<PRIVATE PRIVATE>
+
 TUPLE: hashtable
     { count array-capacity }
     { deleted array-capacity }
-    { array array } ;
+    { array array initial: {
+          T{ tombstone } T{ tombstone } T{ tombstone } T{ tombstone }
+      }
+    } ;
 
 <PRIVATE