SI-6908 Makes FlatHashTable as well as derived classes support null values

This change adds a null sentinel object which is used to indicate that a null
value has been inserted in FlatHashTable. It also makes a strong distinction
between logical elements of the Set vs entries in the hash table. Changes
are made to mutable.HashSet and ParHashSet accordingly.

1 files changed, 63 insertions, 37 deletions

diff --git a/src/library/scala/collection/mutable/FlatHashTable.scala b/src/library/scala/collection/mutable/FlatHashTable.scala
index 7ab99fcda2..0f961b20d3 100644
--- a/src/library/scala/collection/mutable/FlatHashTable.scala
+++ b/src/library/scala/collection/mutable/FlatHashTable.scala
@@ -87,9 +87,9 @@ trait FlatHashTable[A] extends FlatHashTable.HashUtils[A] {
 
     var index = 0
     while (index < size) {
-      val elem = in.readObject().asInstanceOf[A]
+      val elem = entryToElem(in.readObject())
       f(elem)
-      addEntry(elem)
+      addElem(elem)
       index += 1
     }
   }
@@ -110,60 +110,72 @@ trait FlatHashTable[A] extends FlatHashTable.HashUtils[A] {
 
   /** Finds an entry in the hash table if such an element exists. */
   protected def findEntry(elem: A): Option[A] = {
-    val entry = findEntryImpl(elem)
-    if (null == entry) None else Some(entry.asInstanceOf[A])
+    val entry = findElemImpl(elem)
+    if (null == entry) None else Some(entryToElem(entry))
   }
 
   /** Checks whether an element is contained in the hash table. */
-  protected def containsEntry(elem: A): Boolean = {
-    null != findEntryImpl(elem)
+  protected def containsElem(elem: A): Boolean = {
+    null != findElemImpl(elem)
   }
 
-  private def findEntryImpl(elem: A): AnyRef = {
-    var h = index(elemHashCode(elem))
-    var entry = table(h)
-    while (null != entry && entry != elem) {
+  private def findElemImpl(elem: A): AnyRef = {
+    var searchEntry = elemToEntry(elem)
+    var h = index(searchEntry.hashCode)
+    var curEntry = table(h)
+    while (null != curEntry && curEntry != searchEntry) {
       h = (h + 1) % table.length
-      entry = table(h)
+      curEntry = table(h)
     }
-    entry
+    curEntry
   }
 
-  /** Add entry if not yet in table.
-   *  @return Returns `true` if a new entry was added, `false` otherwise.
+  /** Add elem if not yet in table.
+   *  @return Returns `true` if a new elem was added, `false` otherwise.
    */
-  protected def addEntry(elem: A) : Boolean = {
-    var h = index(elemHashCode(elem))
-    var entry = table(h)
-    while (null != entry) {
-      if (entry == elem) return false
+  protected def addElem(elem: A) : Boolean = {
+    addEntry(elemToEntry(elem))
+  }
+  
+  /**
+   * Add an entry (an elem converted to an entry via elemToEntry) if not yet in
+   * table. 
+   *  @return Returns `true` if a new elem was added, `false` otherwise.
+   */
+  protected def addEntry(newEntry : AnyRef) : Boolean = {
+    var h = index(newEntry.hashCode)
+    var curEntry = table(h)
+    while (null != curEntry) {
+      if (curEntry == newEntry) return false
       h = (h + 1) % table.length
-      entry = table(h)
+      curEntry = table(h)
       //Statistics.collisions += 1
     }
-    table(h) = elem.asInstanceOf[AnyRef]
+    table(h) = newEntry
     tableSize = tableSize + 1
     nnSizeMapAdd(h)
     if (tableSize >= threshold) growTable()
     true
+    
   }
 
-  /** Removes an entry from the hash table, returning an option value with the element, or `None` if it didn't exist. */
-  protected def removeEntry(elem: A) : Option[A] = {
+  /** Removes an elem from the hash table, returning an option value with the element, or `None` if it didn't exist. */
+  protected def removeElem(elem: A) : Option[A] = {
     if (tableDebug) checkConsistent()
     def precedes(i: Int, j: Int) = {
       val d = table.length >> 1
       if (i <= j) j - i < d
       else i - j > d
     }
-    var h = index(elemHashCode(elem))
-    var entry = table(h)
-    while (null != entry) {
-      if (entry == elem) {
+    val removalEntry = elemToEntry(elem)
+    var h = index(removalEntry.hashCode)
+    var curEntry = table(h)
+    while (null != curEntry) {
+      if (curEntry == removalEntry) {
         var h0 = h
         var h1 = (h0 + 1) % table.length
         while (null != table(h1)) {
-          val h2 = index(elemHashCode(table(h1).asInstanceOf[A]))
+          val h2 = index(table(h1).hashCode)
           //Console.println("shift at "+h1+":"+table(h1)+" with h2 = "+h2+"? "+(h2 != h1)+precedes(h2, h0)+table.length)
           if (h2 != h1 && precedes(h2, h0)) {
             //Console.println("shift "+h1+" to "+h0+"!")
@@ -176,10 +188,10 @@ trait FlatHashTable[A] extends FlatHashTable.HashUtils[A] {
         tableSize -= 1
         nnSizeMapRemove(h0)
         if (tableDebug) checkConsistent()
-        return Some(entry.asInstanceOf[A])
+        return Some(entryToElem(curEntry))
       }
       h = (h + 1) % table.length
-      entry = table(h)
+      curEntry = table(h)
     }
     None
   }
@@ -191,7 +203,7 @@ trait FlatHashTable[A] extends FlatHashTable.HashUtils[A] {
       i < table.length
     }
     def next(): A =
-      if (hasNext) { i += 1; table(i - 1).asInstanceOf[A] }
+      if (hasNext) { i += 1; entryToElem(table(i - 1)) }
       else Iterator.empty.next
   }
 
@@ -205,7 +217,7 @@ trait FlatHashTable[A] extends FlatHashTable.HashUtils[A] {
     var i = 0
     while (i < oldtable.length) {
       val entry = oldtable(i)
-      if (null != entry) addEntry(entry.asInstanceOf[A])
+      if (null != entry) addEntry(entry)
       i += 1
     }
     if (tableDebug) checkConsistent()
@@ -213,9 +225,10 @@ trait FlatHashTable[A] extends FlatHashTable.HashUtils[A] {
 
   private def checkConsistent() {
     for (i <- 0 until table.length)
-      if (table(i) != null && !containsEntry(table(i).asInstanceOf[A]))
+      if (table(i) != null && !containsElem(entryToElem(table(i))))
         assert(false, i+" "+table(i)+" "+table.mkString)
   }
+ 
 
   /* Size map handling code */
 
@@ -358,6 +371,10 @@ private[collection] object FlatHashTable {
   final def seedGenerator = new ThreadLocal[scala.util.Random] {
     override def initialValue = new scala.util.Random
   }
+  
+  val NullSentinel = new AnyRef {
+    override def hashCode = 0
+  }
 
   /** The load factor for the hash table; must be < 500 (0.5)
    */
@@ -386,10 +403,6 @@ private[collection] object FlatHashTable {
     // so that:
     protected final def sizeMapBucketSize = 1 << sizeMapBucketBitSize
 
-    protected def elemHashCode(elem: A) =
-      if (elem == null) throw new IllegalArgumentException("Flat hash tables cannot contain null elements.")
-      else elem.hashCode()
-
     protected final def improve(hcode: Int, seed: Int) = {
       //var h: Int = hcode + ~(hcode << 9)
       //h = h ^ (h >>> 14)
@@ -404,6 +417,19 @@ private[collection] object FlatHashTable {
       val rotated = (improved >>> rotation) | (improved << (32 - rotation))
       rotated
     }
+         
+    /**
+     * Elems have type A, but we store AnyRef in the table. Plus we need to deal with
+     * null elems, which need to be stored as NullSentinel
+     */
+    protected final def elemToEntry(elem : A) : AnyRef = 
+      if (null == elem) NullSentinel else elem.asInstanceOf[AnyRef]
+    
+    /**
+     * Does the inverse translation of elemToEntry
+     */
+    protected final def entryToElem(entry : AnyRef) : A = 
+      (if (NullSentinel eq entry) null else entry).asInstanceOf[A]
   }
 
 }