- new immutable HashMap implementation based on...

- new immutable HashMap implementation based on a hash trie. this is the
first iteration, more optimizations will be added later. - updated test
cases to reflect new ordering of elements - made Map.empty and Set.empty
singletons, deprecating classes Map.EmptyMap and Set.EmptySet Review by
extempore, odersky.

5 files changed, 248 insertions, 153 deletions

diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala
index 2215e22f71..1e5f79342c 100644
--- a/src/library/scala/collection/immutable/HashMap.scala
+++ b/src/library/scala/collection/immutable/HashMap.scala
@@ -16,184 +16,259 @@ import generic._
 import annotation.unchecked.uncheckedVariance
 
 /** <p>
- *    This class implements immutable maps using a hash table.
- *  </p>
- *  <p>
- *    It is optimized for sequential accesses where the last updated table is
- *    accessed most often. It supports with reasonable efficiency accesses to
- *    previous versions of the table by keeping a change log that's regularly
- *    compacted. It needs to synchronize most methods, so it is less suitable
- *    for highly concurrent accesses.
+ *    This class implements immutable maps using a hash trie.
  *  </p>
  *
  * @note the builder of a hash map returns specialized representations EmptyMap,Map1,..., Map4
  * for maps of size <= 4.
  *
  *  @author  Martin Odersky
- *  @version 2.0, 19/01/2007
+ *  @author  Tiark Rompf
  *  @since   2.3
  */
-@serializable @SerialVersionUID(1L)
-class HashMap[A, +B] extends Map[A,B] with MapLike[A, B, HashMap[A, B]] with mutable.HashTable[A] {
-
-  type Entry = scala.collection.mutable.DefaultEntry[A, Any]
+@serializable @SerialVersionUID(2L)
+class HashMap[A, +B] extends Map[A,B] with MapLike[A, B, HashMap[A, B]] {
 
-  @transient protected var later: HashMap[A, B @uncheckedVariance] = null
-  @transient protected var oldKey: A = _
-  @transient protected var oldValue: Option[B @uncheckedVariance] = _
-  @transient protected var deltaSize: Int = _
+  override def size: Int = 0
 
   override def empty = HashMap.empty[A, B]
 
-  def get(key: A): Option[B] = synchronized {
-    var m: HashMap[A, _ >: B] = this
-    var cnt = 0
-    while (m.later != null) {
-      if (key == m.oldKey) return m.oldValue.asInstanceOf[Option[B]]
-      cnt += 1
-      m = m.later
-    }
-    if (cnt > logLimit) makeCopy(m)
-    val e = m.findEntry(key)
-    if (e == null) None
-    else Some(getValue(e))
-  }
+  def iterator: Iterator[(A,B)] = Iterator.empty
 
-  override def updated [B1 >: B] (key: A, value: B1): HashMap[A, B1] = synchronized {
-    makeCopyIfUpdated()
-    val e = findEntry(key)
-    if (e == null) {
-      markUpdated(key, None, 1)
-      later.addEntry(new Entry(key, value))
-    } else {
-      markUpdated(key, Some(getValue(e)), 0)
-      e.value = value
-    }
-    later.asInstanceOf[HashMap[A, B1]]
-  }
+  override def foreach[U](f: ((A, B)) =>  U): Unit = { }
+
+  def get(key: A): Option[B] =
+    get0(key, computeHash(key), 0)
+
+  override def updated [B1 >: B] (key: A, value: B1): HashMap[A, B1] =
+    updated0(key, computeHash(key), 0, value, null)
+
+  override def + [B1 >: B] (kv: (A, B1)): HashMap[A, B1] =
+    updated0(kv._1, computeHash(kv._1), 0, kv._2, kv)
 
-  /** Add a key/value pair to this map.
-   *  @param    kv the key/value pair
-   *  @return   A new map with the new binding added to this map
-   */
-  override def + [B1 >: B] (kv: (A, B1)): HashMap[A, B1] = updated(kv._1, kv._2)
-
-  /** Adds two or more elements to this collection and returns
-   *  either the collection itself (if it is mutable), or a new collection
-   *  with the added elements.
-   *
-   *  @param elem1 the first element to add.
-   *  @param elem2 the second element to add.
-   *  @param elems the remaining elements to add.
-   */
   override def + [B1 >: B] (elem1: (A, B1), elem2: (A, B1), elems: (A, B1) *): HashMap[A, B1] =
     this + elem1 + elem2 ++ elems
+    // TODO: optimize (might be able to use mutable updates)
 
-  def - (key: A): HashMap[A, B] = synchronized {
-    makeCopyIfUpdated()
-    val e = findEntry(key)
-    if (e == null) this
-    else {
-      markUpdated(key, Some(getValue(e)), -1)
-      later removeEntry key
-      later.asInstanceOf[HashMap[A, B]]
-    }
-  }
+  def - (key: A): HashMap[A, B] =
+    removed0(key, computeHash(key), 0)
 
-  override def size: Int = synchronized {
-    var m: HashMap[A, _ >: B] = this
-    var cnt = 0
-    var s = 0
-    while (m.later != null) {
-      s -= m.deltaSize
-      cnt += 1
-      m = m.later
-    }
-    s += m.tableSize
-    if (cnt > logLimit) makeCopy(m)
-    s
-  }
+  protected def elemHashCode(key: A) = if (key == null) 0 else key.hashCode()
 
-  def iterator = synchronized {
-    makeCopyIfUpdated()
-    entriesIterator map {e => (e.key, getValue(e))}
+  protected final def improve(hcode: Int) = {
+    var h: Int = hcode + ~(hcode << 9)
+    h = h ^ (h >>> 14)
+    h = h + (h << 4)
+    h ^ (h >>> 10)
   }
 
-  private def getValue(e: Entry) =
-    e.value.asInstanceOf[B]
-
-  private def logLimit: Int = math.sqrt(table.length).toInt
-
-  private[this] def markUpdated(key: A, ov: Option[B], delta: Int) {
-    val lf = loadFactor
-    later = new HashMap[A, B] {
-      override def initialSize = 0
-      /* We need to do this to avoid a reference to the outer HashMap */
-      def _newLoadFactor = lf
-      override def loadFactor = _newLoadFactor
-      table     = HashMap.this.table
-      tableSize = HashMap.this.tableSize
-      threshold = HashMap.this.threshold
-    }
-    oldKey = key
-    oldValue = ov
-    deltaSize = delta
-  }
+  protected def computeHash(key: A) = improve(elemHashCode(key))
 
-  private def makeCopy(last: HashMap[A, _ >: B]) {
-    def undo(m: HashMap[A, _ >: B]) {
-      if (m ne last) {
-        undo(m.later)
-        if (m.deltaSize == 1) removeEntry(m.oldKey)
-        else if (m.deltaSize == 0) findEntry(m.oldKey).value = m.oldValue.get
-        else if (m.deltaSize == -1) addEntry(new Entry(m.oldKey, m.oldValue.get))
-      }
-    }
-    def copy(e: Entry): Entry =
-      if (e == null) null
-      else {
-        val rest = copy(e.next)
-        val result = new Entry(e.key, e.value)
-        result.next = rest
-        result
-      }
-    val ltable = last.table
-    val s = ltable.length
-    table = new scala.Array[collection.mutable.HashEntry[A, Entry]](s)
-    var i = 0
-    while (i < s) {
-      table(i) = copy(ltable(i).asInstanceOf[Entry])
-      i += 1
-    }
-    tableSize = last.tableSize
-    threshold = last.threshold
-    undo(this)
-    later = null
-  }
+  protected def get0(key: A, hash: Int, level: Int): Option[B] = None
 
-  private def makeCopyIfUpdated() {
-    var m: HashMap[A, _ >: B] = this
-    while (m.later != null) m = m.later
-    if (m ne this) makeCopy(m)
-  }
+  protected def updated0[B1 >: B](key: A, hash: Int, level: Int, value: B1, kv: (A, B1)): HashMap[A, B1] =
+    new HashMap.HashMap1(key, hash, value, kv)
 
-  private def writeObject(out: java.io.ObjectOutputStream) {
-    serializeTo(out, _.value)
-  }
+  protected def removed0(key: A, hash: Int, level: Int): HashMap[A, B] = this
 
-  private def readObject(in: java.io.ObjectInputStream) {
-    init[B](in, new Entry(_, _))
-  }
 }
 
 /** A factory object for immutable HashMaps.
  *
  *  @author  Martin Odersky
+ *  @author  Tiark Rompf
  *  @version 2.8
  *  @since   2.3
  */
 object HashMap extends ImmutableMapFactory[HashMap] {
   implicit def canBuildFrom[A, B]: CanBuildFrom[Coll, (A, B), HashMap[A, B]] = new MapCanBuildFrom[A, B]
-  def empty[A, B]: HashMap[A, B] = new HashMap
+  def empty[A, B]: HashMap[A, B] = EmptyHashMap.asInstanceOf[HashMap[A, B]]
+
+  private object EmptyHashMap extends HashMap[Any,Nothing] {
+
+  }
+
+  // TODO: add HashMap2, HashMap3, ...
+
+  class HashMap1[A,+B](private var key: A, private[HashMap] var hash: Int, private var value: (B @uncheckedVariance), private var kv: (A,B @uncheckedVariance)) extends HashMap[A,B] {
+    override def size = 1
+
+    override def get0(key: A, hash: Int, level: Int): Option[B] =
+      if (hash == this.hash && key == this.key) Some(value) else None
+
+    override def updated0[B1 >: B](key: A, hash: Int, level: Int, value: B1, kv: (A, B1)): HashMap[A, B1] =
+      if (hash == this.hash && key == this.key) new HashMap1(key, hash, value, kv)
+      else {
+        // TODO: handle 32-bit hash collisions (rare, but not impossible)
+        assert(hash != this.hash, "32-bit hash collisions not handled yet");
+        //new HashTrieMap[A,B1](level+5, this, new HashMap1(key, hash, value, kv))
+        val m = new HashTrieMap[A,B1](0,new Array[HashMap[A,B1]](0),0) // TODO: could save array alloc
+        m.updated0(this.key, this.hash, level, this.value, this.kv).updated0(key, hash, level, value, kv)
+      }
+
+    override def removed0(key: A, hash: Int, level: Int): HashMap[A, B] =
+      if (hash == this.hash && key == this.key) HashMap.empty[A,B] else this
+
+    override def iterator: Iterator[(A,B)] = Iterator(ensurePair)
+    override def foreach[U](f: ((A, B)) => U): Unit = f(ensurePair)
+    private def ensurePair: (A,B) = if (kv ne null) kv else { kv = (key, value); kv }
+
+    private def writeObject(out: java.io.ObjectOutputStream) {
+      out.writeObject(key)
+      out.writeObject(value)
+    }
+
+    private def readObject(in: java.io.ObjectInputStream) {
+      key = in.readObject().asInstanceOf[A]
+      value = in.readObject().asInstanceOf[B]
+      hash = computeHash(key)
+    }
+
+  }
+
+  class HashTrieMap[A,+B](private var bitmap: Int, private var elems: Array[HashMap[A,B @uncheckedVariance]],
+      private var size0: Int) extends HashMap[A,B] {
+/*
+    def this (level: Int, m1: HashMap1[A,B], m2: HashMap1[A,B]) = {
+      this(((m1.hash >>> level) & 0x1f) | ((m2.hash >>> level) & 0x1f), {
+        val idx1 = (m1.hash >>> level) & 0x1f
+        val idx2 = (m2.hash >>> level) & 0x1f
+        assert(idx1 != idx2, m1.hash + "==" + m2.hash + " at level " + level) // TODO
+        val elems = new Array[HashMap[A,B]](2)
+        if (idx1 < idx2) {
+          elems(0) = m1
+          elems(1) = m2
+        } else {
+          elems(0) = m2
+          elems(1) = m1
+        }
+        elems
+      }, 2)
+    }
+*/
+    override def size = size0
+
+    override def get0(key: A, hash: Int, level: Int): Option[B] = {
+      val index = (hash >>> level) & 0x1f
+      val mask = (1 << index)
+      if (bitmap == - 1) {
+        elems(index & 0x1f).get0(key, hash, level + 5)
+      } else if ((bitmap & mask) != 0) {
+        val offset = Integer.bitCount(bitmap & (mask-1))
+        elems(offset).get0(key, hash, level + 5)
+      } else
+        None
+    }
+
+    override def updated0[B1 >: B](key: A, hash: Int, level: Int, value: B1, kv: (A, B1)): HashMap[A, B1] = {
+      val index = (hash >>> level) & 0x1f
+      val mask = (1 << index)
+      val offset = Integer.bitCount(bitmap & (mask-1))
+      if ((bitmap & mask) != 0) {
+        val elemsNew = new Array[HashMap[A,B1]](elems.length)
+        Array.copy(elems, 0, elemsNew, 0, elems.length)
+        val sub = elems(offset)
+        val subNew = sub.updated0(key, hash, level + 5, value, kv)
+        elemsNew(offset) = subNew
+        new HashTrieMap(bitmap, elemsNew, size + (subNew.size - sub.size))
+      } else {
+        assert(offset <= elems.length, offset +">"+elems.length)
+        val elemsNew = new Array[HashMap[A,B1]](elems.length + 1)
+        Array.copy(elems, 0, elemsNew, 0, offset)
+        elemsNew(offset) = new HashMap1(key, hash, value, kv)
+        Array.copy(elems, offset, elemsNew, offset + 1, elems.length - offset)
+        val bitmapNew = bitmap | mask
+        new HashTrieMap(bitmapNew, elemsNew, size + 1)
+      }
+    }
+
+    override def removed0(key: A, hash: Int, level: Int): HashMap[A, B] = {
+      val index = (hash >>> level) & 0x1f
+      val mask = (1 << index)
+      val offset = Integer.bitCount(bitmap & (mask-1))
+      if (((bitmap >>> index) & 1) == 1) {
+        val elemsNew = new Array[HashMap[A,B]](elems.length)
+        Array.copy(elems, 0, elemsNew, 0, elems.length)
+        val sub = elems(offset)
+        val subNew = sub.removed0(key, hash, level + 5)
+        elemsNew(offset) = subNew
+        // TODO: handle shrinking
+        val sizeNew = size + (subNew.size - sub.size)
+        if (sizeNew > 0)
+          new HashTrieMap(bitmap, elemsNew, size + (subNew.size - sub.size))
+        else
+          HashMap.empty[A,B]
+      } else {
+        this
+      }
+    }
+
+
+    override def iterator = {   // TODO: optimize (use a stack to keep track of pos)
+      var it: Iterator[(A,B)] = Iterator.empty
+      if (bitmap != 0)
+        elems foreach ((m: Map[_,_]) => it = it ++ m.asInstanceOf[Map[A,B]].iterator)
+      it
+    }
+
+/*
+    override def iterator = new Iterator[A,B] {
+      var depth = 0
+      var nodeStack = new Array[HashTrieMap[A,B]](6)
+      var indexStack = new Array[Int](6)
+
+      var curNode = this[HashTrieMap]
+      var curIndex = 0
+      var maxIndex = curNode.elems.length
+
+      def hasNext = curIndex < maxIndex
+
+      def next(): (A,B) = {
+        val sub = curNode.elems(curIndex)
+        sub match {
+          case sub: HashTrieMap =>
+            // go down
+          case sub: HashMap1 =>
+            // produce value
+        }
+
+      }
+*/
+
+    override def foreach[U](f: ((A, B)) =>  U): Unit = {
+      var i = 0;
+      while (i < elems.length) {
+        elems(i).foreach(f)
+        i += 1
+      }
+    }
+
+
+    private def writeObject(out: java.io.ObjectOutputStream) {
+      // no out.defaultWriteObject()
+      out.writeInt(size)
+      foreach { p =>
+        out.writeObject(p._1)
+        out.writeObject(p._2)
+      }
+    }
+
+    private def readObject(in: java.io.ObjectInputStream) {
+      val size = in.readInt
+      var index = 0
+      var m = HashMap.empty[A,B]
+      while (index < size) {
+        // TODO: optimize (use mutable update)
+        m = m + ((in.readObject.asInstanceOf[A], in.readObject.asInstanceOf[B]))
+        index += 1
+      }
+      var tm = m.asInstanceOf[HashTrieMap[A,B]]
+      bitmap = tm.bitmap
+      elems = tm.elems
+      size0 = tm.size0
+    }
+
+  }
+
 }
 
diff --git a/src/library/scala/collection/immutable/Map.scala b/src/library/scala/collection/immutable/Map.scala
index f42794d09e..b5a852683a 100644
--- a/src/library/scala/collection/immutable/Map.scala
+++ b/src/library/scala/collection/immutable/Map.scala
@@ -44,7 +44,7 @@ trait Map[A, +B] extends Iterable[(A, B)]
 object Map extends ImmutableMapFactory[Map] {
   implicit def canBuildFrom[A, B]: CanBuildFrom[Coll, (A, B), Map[A, B]] = new MapCanBuildFrom[A, B]
 
-  def empty[A, B]: Map[A, B] = new EmptyMap[A, B]
+  def empty[A, B]: Map[A, B] = EmptyMap.asInstanceOf[Map[A, B]]
 
   class WithDefault[A, +B](underlying: Map[A, B], d: A => B) extends Map[A, B] {
     override def size = underlying.size
@@ -58,12 +58,22 @@ object Map extends ImmutableMapFactory[Map] {
   }
 
   @serializable
-  class EmptyMap[A, +B] extends Map[A, B] {
+  private object EmptyMap extends Map[Any, Nothing] {
+    override def size: Int = 0
+    def get(key: Any): Option[Nothing] = None
+    def iterator: Iterator[(Any, Nothing)] = Iterator.empty
+    override def updated [B1] (key: Any, value: B1): Map[Any, B1] = new Map1(key, value)
+    def + [B1](kv: (Any, B1)): Map[Any, B1] = updated(kv._1, kv._2)
+    def - (key: Any): Map[Any, Nothing] = this
+  }
+
+  @serializable @deprecated("use `Map.empty' instead")
+  class EmptyMap[A,B] extends Map[A,B] {
     override def size: Int = 0
     def get(key: A): Option[B] = None
     def iterator: Iterator[(A, B)] = Iterator.empty
-    override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] = new Map1(key, value)
-    def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2)
+    override def updated [B1] (key: A, value: B1): Map[A, B1] = new Map1(key, value)
+    def + [B1](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2)
     def - (key: A): Map[A, B] = this
   }
 
@@ -78,7 +88,7 @@ object Map extends ImmutableMapFactory[Map] {
       else new Map2(key1, value1, key, value)
     def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2)
     def - (key: A): Map[A, B] =
-      if (key == key1) empty else this
+      if (key == key1) Map.empty else this
     override def foreach[U](f: ((A, B)) =>  U): Unit = {
       f((key1, value1))
     }
diff --git a/src/library/scala/collection/immutable/Set.scala b/src/library/scala/collection/immutable/Set.scala
index be1e86bcdd..1bec1b9a48 100644
--- a/src/library/scala/collection/immutable/Set.scala
+++ b/src/library/scala/collection/immutable/Set.scala
@@ -41,12 +41,22 @@ trait Set[A] extends Iterable[A]
 
 object Set extends SetFactory[Set] {
   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Set[A]] = setCanBuildFrom[A]
-  override def empty[A]: Set[A] = new EmptySet[A]
+  override def empty[A]: Set[A] = EmptySet.asInstanceOf[Set[A]]
 
   private val hashSeed = "Set".hashCode
 
   /** An optimized representation for immutable empty sets */
   @serializable
+  private object EmptySet extends Set[Any] {
+    override def size: Int = 0
+    def contains(elem: Any): Boolean = false
+    def + (elem: Any): Set[Any] = new Set1(elem)
+    def - (elem: Any): Set[Any] = this
+    def iterator: Iterator[Any] = Iterator.empty
+    override def foreach[U](f: Any =>  U): Unit = {}
+  }
+
+  @serializable @deprecated("use `Set.empty' instead")
   class EmptySet[A] extends Set[A] {
     override def size: Int = 0
     def contains(elem: A): Boolean = false
@@ -66,7 +76,7 @@ object Set extends SetFactory[Set] {
       if (contains(elem)) this
       else new Set2(elem1, elem)
     def - (elem: A): Set[A] =
-      if (elem == elem1) new EmptySet[A]
+      if (elem == elem1) Set.empty
       else this
     def iterator: Iterator[A] =
       Iterator(elem1)
diff --git a/src/library/scala/reflect/generic/Trees.scala b/src/library/scala/reflect/generic/Trees.scala
index 36c7663041..db3a19a843 100755
--- a/src/library/scala/reflect/generic/Trees.scala
+++ b/src/library/scala/reflect/generic/Trees.scala
@@ -63,7 +63,7 @@ trait Trees { self: Universe =>
       copy(positions = positions + (flag -> position))
   }
 
-  def Modifiers(flags: Long, privateWithin: Name): Modifiers = Modifiers(flags, privateWithin, List(), new Map.EmptyMap)
+  def Modifiers(flags: Long, privateWithin: Name): Modifiers = Modifiers(flags, privateWithin, List(), Map.empty)
   def Modifiers(flags: Long): Modifiers = Modifiers(flags, mkTypeName(nme.EMPTY))
 
   lazy val NoMods = Modifiers(0)
diff --git a/src/library/scala/reflect/generic/UnPickler.scala b/src/library/scala/reflect/generic/UnPickler.scala
index 9d5796f63b..d0fff42d56 100755
--- a/src/library/scala/reflect/generic/UnPickler.scala
+++ b/src/library/scala/reflect/generic/UnPickler.scala
@@ -701,7 +701,7 @@ abstract class UnPickler {
       val pflags = (pflagsHi.toLong << 32) + pflagsLo
       val flags = pickledToRawFlags(pflags)
       val privateWithin = readNameRef()
-      Modifiers(flags, privateWithin, Nil, new Map.EmptyMap)
+      Modifiers(flags, privateWithin, Nil, Map.empty)
     }
 
     /* Read a reference to a pickled item */