diff options
author | Pavel Pavlov <pavel.e.pavlov@gmail.com> | 2012-08-27 00:12:07 +0700 |
---|---|---|
committer | Pavel Pavlov <pavel.e.pavlov@gmail.com> | 2012-08-27 19:35:53 +0700 |
commit | 3cd8eb053afcb3592770437112655023ede17505 (patch) | |
tree | e729437cdee551244dd339872f50937c67aaa05c /src/library | |
parent | a23edefac652e3be1474fceb3ee15d7eaecf1359 (diff) | |
download | scala-3cd8eb053afcb3592770437112655023ede17505.tar.gz scala-3cd8eb053afcb3592770437112655023ede17505.tar.bz2 scala-3cd8eb053afcb3592770437112655023ede17505.zip |
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
Diffstat (limited to 'src/library')
5 files changed, 140 insertions, 71 deletions
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 = { |