SI-5767 fix + small HashSet/HashMap fixes

- `LinkedHashSet` implementation moved from `FlatHashTable` to `HashTable`
   - `remove` time reduced from O(n) to O(1)
   - `diff` time reduced from O(n^2) to O(n)
- A bit of refactoring in `HashTable` serialization code
- Putting an element into hash map now avoids double hash code/hash index
  calculation (see `HashTable#findOrAddEntry`)
- bugfix: compiler/LambdaLift occasionally breaks LinkedHashSet integrity

6 files changed, 141 insertions, 72 deletions

diff --git a/src/compiler/scala/tools/nsc/transform/LambdaLift.scala b/src/compiler/scala/tools/nsc/transform/LambdaLift.scala
index b6d54f114e..c41ff20229 100644
--- a/src/compiler/scala/tools/nsc/transform/LambdaLift.scala
+++ b/src/compiler/scala/tools/nsc/transform/LambdaLift.scala
@@ -154,7 +154,7 @@ abstract class LambdaLift extends InfoTransform {
     private def markCalled(sym: Symbol, owner: Symbol) {
       debuglog("mark called: " + sym + " of " + sym.owner + " is called by " + owner)
       symSet(called, owner) addEntry sym
-      if (sym.enclClass != owner.enclClass) calledFromInner addEntry sym
+      if (sym.enclClass != owner.enclClass) calledFromInner += sym
     }
 
     /** The traverse function */
diff --git a/src/library/scala/collection/mutable/HashMap.scala b/src/library/scala/collection/mutable/HashMap.scala
index bf640cdb90..a407fa508c 100644
--- a/src/library/scala/collection/mutable/HashMap.scala
+++ b/src/library/scala/collection/mutable/HashMap.scala
@@ -60,19 +60,19 @@ extends AbstractMap[A, B]
   override def contains(key: A) = findEntry(key) != null
   override def apply(key: A): B = {
     val result = findEntry(key)
-    if (result == null) default(key)
+    if (result eq null) default(key)
     else result.value
   }
 
   def get(key: A): Option[B] = {
     val e = findEntry(key)
-    if (e == null) None
+    if (e eq null) None
     else Some(e.value)
   }
 
   override def put(key: A, value: B): Option[B] = {
-    val e = findEntry(key)
-    if (e == null) { addEntry(new Entry(key, value)); None }
+    val e = findOrAddEntry(key, value)
+    if (e eq null) None
     else { val v = e.value; e.value = value; Some(v) }
   }
 
@@ -85,9 +85,8 @@ extends AbstractMap[A, B]
   }
 
   def += (kv: (A, B)): this.type = {
-    val e = findEntry(kv._1)
-    if (e == null) addEntry(new Entry(kv._1, kv._2))
-    else e.value = kv._2
+    val e = findOrAddEntry(kv._1, kv._2)
+    if (e ne null) e.value = kv._2
     this
   }
 
@@ -127,12 +126,19 @@ extends AbstractMap[A, B]
     if (!isSizeMapDefined) sizeMapInitAndRebuild
   } else sizeMapDisable
 
+  protected override def createNewEntry[B1](key: A, value: B1): Entry = {
+    new Entry(key, value.asInstanceOf[B])
+  }
+
   private def writeObject(out: java.io.ObjectOutputStream) {
-    serializeTo(out, _.value)
+    serializeTo(out, { entry =>
+      out.writeObject(entry.key)
+      out.writeObject(entry.value)
+    })
   }
 
   private def readObject(in: java.io.ObjectInputStream) {
-    init[B](in, new Entry(_, _))
+    init(in, createNewEntry(in.readObject().asInstanceOf[A], in.readObject()))
   }
 
 }
diff --git a/src/library/scala/collection/mutable/HashTable.scala b/src/library/scala/collection/mutable/HashTable.scala
index 97e794f06e..ff66df624d 100644
--- a/src/library/scala/collection/mutable/HashTable.scala
+++ b/src/library/scala/collection/mutable/HashTable.scala
@@ -32,6 +32,9 @@ package mutable
  *  @tparam A     type of the elements contained in this hash table.
  */
 trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashUtils[A] {
+  // Replacing Entry type parameter by abstract type member here allows to not expose to public
+  // implementation-specific entry classes such as `DefaultEntry` or `LinkedEntry`.
+  // However, I'm afraid it's too late now for such breaking change.
   import HashTable._
 
   @transient protected var _loadFactor = defaultLoadFactor
@@ -75,11 +78,10 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU
   }
 
   /**
-   * Initializes the collection from the input stream. `f` will be called for each key/value pair
-   * read from the input stream in the order determined by the stream. This is useful for
-   * structures where iteration order is important (e.g. LinkedHashMap).
+   * Initializes the collection from the input stream. `readEntry` will be called for each
+   * entry to be read from the input stream.
    */
-  private[collection] def init[B](in: java.io.ObjectInputStream, f: (A, B) => Entry) {
+  private[collection] def init(in: java.io.ObjectInputStream, readEntry: => Entry) {
     in.defaultReadObject
 
     _loadFactor = in.readInt()
@@ -100,35 +102,34 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU
 
     var index = 0
     while (index < size) {
-      addEntry(f(in.readObject().asInstanceOf[A], in.readObject().asInstanceOf[B]))
+      addEntry(readEntry)
       index += 1
     }
   }
 
   /**
    * Serializes the collection to the output stream by saving the load factor, collection
-   * size, collection keys and collection values. `value` is responsible for providing a value
-   * from an entry.
+   * size and collection entries. `writeEntry` is responsible for writing an entry to the stream.
    *
-   * `foreach` determines the order in which the key/value pairs are saved to the stream. To
+   * `foreachEntry` determines the order in which the key/value pairs are saved to the stream. To
    * deserialize, `init` should be used.
    */
-  private[collection] def serializeTo[B](out: java.io.ObjectOutputStream, value: Entry => B) {
+  private[collection] def serializeTo(out: java.io.ObjectOutputStream, writeEntry: Entry => Unit) {
     out.defaultWriteObject
     out.writeInt(_loadFactor)
     out.writeInt(tableSize)
     out.writeInt(seedvalue)
     out.writeBoolean(isSizeMapDefined)
-    foreachEntry { entry =>
-      out.writeObject(entry.key)
-      out.writeObject(value(entry))
-    }
+
+    foreachEntry(writeEntry)
   }
 
   /** Find entry with given key in table, null if not found.
    */
-  protected def findEntry(key: A): Entry = {
-    val h = index(elemHashCode(key))
+  protected def findEntry(key: A): Entry =
+    findEntry0(key, index(elemHashCode(key)))
+
+  private[this] def findEntry0(key: A, h: Int): Entry = {
     var e = table(h).asInstanceOf[Entry]
     while (e != null && !elemEquals(e.key, key)) e = e.next
     e
@@ -138,7 +139,10 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU
    *  pre: no entry with same key exists
    */
   protected def addEntry(e: Entry) {
-    val h = index(elemHashCode(e.key))
+    addEntry0(e, index(elemHashCode(e.key)))
+  }
+
+  private[this] def addEntry0(e: Entry, h: Int) {
     e.next = table(h).asInstanceOf[Entry]
     table(h) = e
     tableSize = tableSize + 1
@@ -147,6 +151,24 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU
       resize(2 * table.length)
   }
 
+  /** Find entry with given key in table, or add new one if not found.
+   *  May be somewhat faster then `findEntry`/`addEntry` pair as it
+   *  computes entry's hash index only once.
+   *  Returns entry found in table or null.
+   *  Method `createNewEntry` must be implemented in any subclass/subtrait who calls this.
+   */
+  protected def findOrAddEntry[B](key: A, value: B): Entry = {
+    val h = index(elemHashCode(key))
+    val e = findEntry0(key, h)
+    if (e ne null) e else { addEntry0(createNewEntry(key, value), h); null }
+  }
+
+  /** Creates new entry to be immediately inserted into the hashtable.
+   *  This method must be implemented for any class who calls `findOrAddEntry`.
+   *  Ideally, it should be abstract, but this will break source compatibility.
+   */
+  protected def createNewEntry[B](key: A, value: B): Entry = ???
+
   /** Remove entry from table if present.
    */
   protected def removeEntry(key: A) : Entry = {
@@ -195,7 +217,7 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU
   }
 
   /** Avoid iterator for a 2x faster traversal. */
-  protected def foreachEntry[C](f: Entry => C) {
+  protected def foreachEntry[U](f: Entry => U) {
     val iterTable = table
     var idx       = lastPopulatedIndex
     var es        = iterTable(idx)
diff --git a/src/library/scala/collection/mutable/LinkedHashMap.scala b/src/library/scala/collection/mutable/LinkedHashMap.scala
index 5643e070f8..6603447810 100644
--- a/src/library/scala/collection/mutable/LinkedHashMap.scala
+++ b/src/library/scala/collection/mutable/LinkedHashMap.scala
@@ -67,23 +67,9 @@ class LinkedHashMap[A, B] extends AbstractMap[A, B]
   }
 
   override def put(key: A, value: B): Option[B] = {
-    val e = findEntry(key)
-    if (e == null) {
-      val e = new Entry(key, value)
-      addEntry(e)
-      updateLinkedEntries(e)
-      None
-    } else {
-      val v = e.value
-      e.value = value
-      Some(v)
-    }
-  }
-
-  private def updateLinkedEntries(e: Entry) {
-    if (firstEntry == null) firstEntry = e
-    else { lastEntry.later = e; e.earlier = lastEntry }
-    lastEntry = e
+    val e = findOrAddEntry(key, value)
+    if (e eq null) None
+    else { val v = e.value; e.value = value; Some(v) }
   }
 
   override def remove(key: A): Option[B] = {
@@ -151,7 +137,7 @@ class LinkedHashMap[A, B] extends AbstractMap[A, B]
     }
   }
 
-  protected override def foreachEntry[C](f: Entry => C) {
+  protected override def foreachEntry[U](f: Entry => U) {
     var cur = firstEntry
     while (cur ne null) {
       f(cur)
@@ -159,22 +145,29 @@ class LinkedHashMap[A, B] extends AbstractMap[A, B]
     }
   }
 
+  protected override def createNewEntry[B1](key: A, value: B1): Entry = {
+    val e = new Entry(key, value.asInstanceOf[B])
+    if (firstEntry eq null) firstEntry = e
+    else { lastEntry.later = e; e.earlier = lastEntry }
+    lastEntry = e
+    e
+  }
+
   override def clear() {
     clearTable()
     firstEntry = null
   }
 
   private def writeObject(out: java.io.ObjectOutputStream) {
-    serializeTo(out, _.value)
+    serializeTo(out, { entry =>
+      out.writeObject(entry.key)
+      out.writeObject(entry.value)
+    })
   }
 
   private def readObject(in: java.io.ObjectInputStream) {
     firstEntry = null
     lastEntry = null
-    init[B](in, { (key, value) =>
-      val entry = new Entry(key, value)
-      updateLinkedEntries(entry)
-      entry
-    })
+    init(in, createNewEntry(in.readObject().asInstanceOf[A], in.readObject()))
   }
 }
diff --git a/src/library/scala/collection/mutable/LinkedHashSet.scala b/src/library/scala/collection/mutable/LinkedHashSet.scala
index 3f789f9fa2..05e233a784 100644
--- a/src/library/scala/collection/mutable/LinkedHashSet.scala
+++ b/src/library/scala/collection/mutable/LinkedHashSet.scala
@@ -19,6 +19,7 @@ import generic._
  *
  *  @author  Matthias Zenger
  *  @author  Martin Odersky
+ *  @author  Pavel Pavlov
  *  @version 2.0, 31/12/2006
  *  @since   1
  *
@@ -43,46 +44,82 @@ class LinkedHashSet[A] extends AbstractSet[A]
                           with Set[A]
                           with GenericSetTemplate[A, LinkedHashSet]
                           with SetLike[A, LinkedHashSet[A]]
-                          with FlatHashTable[A]
+                          with HashTable[A, LinkedHashSet.Entry[A]]
                           with Serializable
 {
   override def companion: GenericCompanion[LinkedHashSet] = LinkedHashSet
 
-  @transient private[this] var ordered = new ListBuffer[A]
+  type Entry = LinkedHashSet.Entry[A]
+
+  @transient protected var firstEntry: Entry = null
+  @transient protected var lastEntry: Entry = null
 
   override def size = tableSize
 
-  def contains(elem: A): Boolean = containsEntry(elem)
+  def contains(elem: A): Boolean = findEntry(elem) ne null
 
   def += (elem: A): this.type = { add(elem); this }
   def -= (elem: A): this.type = { remove(elem); this }
 
-  override def add(elem: A): Boolean =
-    if (addEntry(elem)) { ordered += elem; true }
-    else false
+  override def add(elem: A): Boolean = findOrAddEntry(elem, null) eq null
+
+  override def remove(elem: A): Boolean = {
+    val e = removeEntry(elem)
+    if (e eq null) false
+    else {
+      if (e.earlier eq null) firstEntry = e.later
+      else e.earlier.later = e.later
+      if (e.later eq null) lastEntry = e.earlier
+      else e.later.earlier = e.earlier
+      true
+    }
+  }
 
-  override def remove(elem: A): Boolean =
-    removeEntry(elem) match {
-      case None => false
-      case _ => ordered -= elem; true
+  def iterator: Iterator[A] = new AbstractIterator[A] {
+    private var cur = firstEntry
+    def hasNext = cur ne null
+    def next =
+      if (hasNext) { val res = cur.key; cur = cur.later; res }
+      else Iterator.empty.next
+  }
+  
+  override def foreach[U](f: A => U) = {
+    var cur = firstEntry
+    while (cur ne null) {
+      f(cur.key)
+      cur = cur.later
     }
+  }
 
-  override def clear() {
-    ordered.clear()
-    clearTable()
+  protected override def foreachEntry[U](f: Entry => U) {
+    var cur = firstEntry
+    while (cur ne null) {
+      f(cur)
+      cur = cur.later
+    }
   }
 
-  override def iterator: Iterator[A] = ordered.iterator
+  protected override def createNewEntry[B](key: A, dummy: B): Entry = {
+    val e = new Entry(key)
+    if (firstEntry eq null) firstEntry = e
+    else { lastEntry.later = e; e.earlier = lastEntry }
+    lastEntry = e
+    e
+  }
 
-  override def foreach[U](f: A => U) = ordered foreach f
+  override def clear() {
+    clearTable()
+    firstEntry = null
+  }
 
-  private def writeObject(s: java.io.ObjectOutputStream) {
-    serializeTo(s)
+  private def writeObject(out: java.io.ObjectOutputStream) {
+    serializeTo(out, { e => out.writeObject(e.key) })
   }
 
   private def readObject(in: java.io.ObjectInputStream) {
-    ordered = new ListBuffer[A]
-    init(in, ordered += _)
+    firstEntry = null
+    lastEntry = null
+    init(in, createNewEntry(in.readObject().asInstanceOf[A], null))
   }
 }
 
@@ -93,5 +130,13 @@ class LinkedHashSet[A] extends AbstractSet[A]
 object LinkedHashSet extends MutableSetFactory[LinkedHashSet] {
   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, LinkedHashSet[A]] = setCanBuildFrom[A]
   override def empty[A]: LinkedHashSet[A] = new LinkedHashSet[A]
+
+  /** Class for the linked hash set entry, used internally.
+   *  @since 2.10
+   */
+  private[scala] final class Entry[A](val key: A) extends HashEntry[A, Entry[A]] with Serializable {
+    var earlier: Entry[A] = null
+    var later: Entry[A] = null
+  }
 }
 
diff --git a/src/library/scala/collection/parallel/mutable/ParHashMap.scala b/src/library/scala/collection/parallel/mutable/ParHashMap.scala
index 8d39d6e0de..2ed07c81a3 100644
--- a/src/library/scala/collection/parallel/mutable/ParHashMap.scala
+++ b/src/library/scala/collection/parallel/mutable/ParHashMap.scala
@@ -104,11 +104,14 @@ self =>
   }
 
   private def writeObject(out: java.io.ObjectOutputStream) {
-    serializeTo(out, _.value)
+    serializeTo(out, { entry =>
+      out.writeObject(entry.key)
+      out.writeObject(entry.value)
+    })
   }
 
   private def readObject(in: java.io.ObjectInputStream) {
-    init[V](in, new Entry(_, _))
+    init(in, new Entry(in.readObject().asInstanceOf[K], in.readObject().asInstanceOf[V]))
   }
 
   private[parallel] override def brokenInvariants = {