diff options
author | Josh Suereth <Joshua.Suereth@gmail.com> | 2012-09-18 09:57:03 -0700 |
---|---|---|
committer | Josh Suereth <Joshua.Suereth@gmail.com> | 2012-09-18 09:57:03 -0700 |
commit | c9b2ef64108d75ab41ff95cc32bc503e77653e66 (patch) | |
tree | 8c20c020da84210aa3fdb09c7ab97bc6d2d4c6a4 /src | |
parent | a9f95dc29f366d935604f15a4a99cbfd1a1bd275 (diff) | |
parent | dbd641f592310d7243f675e27ecc8b9d47684309 (diff) | |
download | scala-c9b2ef64108d75ab41ff95cc32bc503e77653e66.tar.gz scala-c9b2ef64108d75ab41ff95cc32bc503e77653e66.tar.bz2 scala-c9b2ef64108d75ab41ff95cc32bc503e77653e66.zip |
Merge pull request #1298 from pavelpavlov/SI-5767
SI-5767 fix + protecting public FlatHashMap API
Diffstat (limited to 'src')
9 files changed, 175 insertions, 97 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/FlatHashTable.scala b/src/library/scala/collection/mutable/FlatHashTable.scala index 12066055e9..74f576b0f7 100644 --- a/src/library/scala/collection/mutable/FlatHashTable.scala +++ b/src/library/scala/collection/mutable/FlatHashTable.scala @@ -44,7 +44,7 @@ trait FlatHashTable[A] extends FlatHashTable.HashUtils[A] { */ @transient protected var sizemap: Array[Int] = null - @transient var seedvalue: Int = tableSizeSeed + @transient protected var seedvalue: Int = tableSizeSeed import HashTable.powerOfTwo @@ -109,7 +109,7 @@ trait FlatHashTable[A] extends FlatHashTable.HashUtils[A] { } /** Finds an entry in the hash table if such an element exists. */ - def findEntry(elem: A): Option[A] = { + protected def findEntry(elem: A): Option[A] = { var h = index(elemHashCode(elem)) var entry = table(h) while (null != entry && entry != elem) { @@ -120,7 +120,7 @@ trait FlatHashTable[A] extends FlatHashTable.HashUtils[A] { } /** Checks whether an element is contained in the hash table. */ - def containsEntry(elem: A): Boolean = { + protected def containsEntry(elem: A): Boolean = { var h = index(elemHashCode(elem)) var entry = table(h) while (null != entry && entry != elem) { @@ -133,7 +133,7 @@ trait FlatHashTable[A] extends FlatHashTable.HashUtils[A] { /** Add entry if not yet in table. * @return Returns `true` if a new entry was added, `false` otherwise. */ - def addEntry(elem: A) : Boolean = { + protected def addEntry(elem: A) : Boolean = { var h = index(elemHashCode(elem)) var entry = table(h) while (null != entry) { @@ -150,7 +150,7 @@ trait FlatHashTable[A] extends FlatHashTable.HashUtils[A] { } /** Removes an entry from the hash table, returning an option value with the element, or `None` if it didn't exist. */ - def removeEntry(elem: A) : Option[A] = { + protected def removeEntry(elem: A) : Option[A] = { if (tableDebug) checkConsistent() def precedes(i: Int, j: Int) = { val d = table.length >> 1 @@ -185,7 +185,7 @@ trait FlatHashTable[A] extends FlatHashTable.HashUtils[A] { None } - def iterator: Iterator[A] = new AbstractIterator[A] { + protected def iterator: Iterator[A] = new AbstractIterator[A] { private var i = 0 def hasNext: Boolean = { while (i < table.length && (null == table(i))) i += 1 diff --git a/src/library/scala/collection/mutable/HashMap.scala b/src/library/scala/collection/mutable/HashMap.scala index da486f4042..be85df3c28 100644 --- a/src/library/scala/collection/mutable/HashMap.scala +++ b/src/library/scala/collection/mutable/HashMap.scala @@ -49,7 +49,7 @@ extends AbstractMap[A, B] type Entry = DefaultEntry[A, B] override def empty: HashMap[A, B] = HashMap.empty[A, B] - override def clear() = clearTable() + override def clear() { clearTable() } override def size: Int = tableSize def this() = this(null) @@ -57,22 +57,23 @@ extends AbstractMap[A, B] override def par = new ParHashMap[A, B](hashTableContents) // contains and apply overridden to avoid option allocations. - override def contains(key: A) = findEntry(key) != null + override def contains(key: A): Boolean = 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 +86,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 +127,19 @@ extends AbstractMap[A, B] if (!isSizeMapDefined) sizeMapInitAndRebuild } else sizeMapDisable + protected 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/HashSet.scala b/src/library/scala/collection/mutable/HashSet.scala index b263b46d36..a5b636c83d 100644 --- a/src/library/scala/collection/mutable/HashSet.scala +++ b/src/library/scala/collection/mutable/HashSet.scala @@ -53,7 +53,7 @@ extends AbstractSet[A] override def companion: GenericCompanion[HashSet] = HashSet - override def size = tableSize + override def size: Int = tableSize def contains(elem: A): Boolean = containsEntry(elem) @@ -67,7 +67,9 @@ extends AbstractSet[A] override def remove(elem: A): Boolean = removeEntry(elem).isDefined - override def clear() = clearTable() + override def clear() { clearTable() } + + override def iterator: Iterator[A] = super[FlatHashTable].iterator override def foreach[U](f: A => U) { var i = 0 diff --git a/src/library/scala/collection/mutable/HashTable.scala b/src/library/scala/collection/mutable/HashTable.scala index 968d99d042..eb6717393b 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 @@ -52,7 +55,7 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU */ @transient protected var sizemap: Array[Int] = null - @transient var seedvalue: Int = tableSizeSeed + @transient protected var seedvalue: Int = tableSizeSeed protected def tableSizeSeed = Integer.bitCount(table.length - 1) @@ -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. + * New entries are created by calling `createNewEntry` method. + */ + 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 is guaranteed to be called only once and in case that the entry + * will be added. In other words, an implementation may be side-effecting. + */ + 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..5028884a8e 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] = { @@ -143,7 +129,7 @@ class LinkedHashMap[A, B] extends AbstractMap[A, B] else Iterator.empty.next } - override def foreach[U](f: ((A, B)) => U) = { + override def foreach[U](f: ((A, B)) => U) { var cur = firstEntry while (cur ne null) { f((cur.key, cur.value)) @@ -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 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..88bad5ff9b 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] - override def size = tableSize + @transient protected var firstEntry: Entry = null + @transient protected var lastEntry: Entry = null - def contains(elem: A): Boolean = containsEntry(elem) + override def size: Int = tableSize + + 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 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 1921727ce3..fad7ddad59 100644 --- a/src/library/scala/collection/parallel/mutable/ParHashMap.scala +++ b/src/library/scala/collection/parallel/mutable/ParHashMap.scala @@ -67,13 +67,13 @@ self => def get(key: K): Option[V] = { val e = findEntry(key) - if (e == null) None + if (e eq null) None else Some(e.value) } def put(key: K, value: V): Option[V] = { - 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) } } @@ -86,9 +86,8 @@ self => } def += (kv: (K, V)): 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 } @@ -103,12 +102,19 @@ self => new ParHashMapIterator(idxFrom, idxUntil, totalSz, es) } + protected def createNewEntry[V1](key: K, value: V1): Entry = { + new Entry(key, value.asInstanceOf[V]) + } + 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, createNewEntry(in.readObject().asInstanceOf[K], in.readObject())) } private[parallel] override def brokenInvariants = { @@ -190,7 +196,9 @@ extends scala.collection.parallel.BucketCombiner[(K, V), ParHashMap[K, V], Defau // construct a normal table and fill it sequentially // TODO parallelize by keeping separate sizemaps and merging them object table extends HashTable[K, DefaultEntry[K, V]] { - def insertEntry(e: DefaultEntry[K, V]) = if (super.findEntry(e.key) eq null) super.addEntry(e) + type Entry = DefaultEntry[K, V] + def insertEntry(e: Entry) { super.findOrAddEntry(e.key, e) } + def createNewEntry[E](key: K, entry: E): Entry = entry.asInstanceOf[Entry] sizeMapInit(table.length) } var i = 0 @@ -251,6 +259,7 @@ extends scala.collection.parallel.BucketCombiner[(K, V), ParHashMap[K, V], Defau assert(h >= block * blocksize && h < (block + 1) * blocksize) } } + protected def createNewEntry[X](key: K, x: X) = ??? } /* tasks */ diff --git a/src/library/scala/collection/parallel/mutable/ParHashSet.scala b/src/library/scala/collection/parallel/mutable/ParHashSet.scala index 7b5b8e3ceb..aef9f6856b 100644 --- a/src/library/scala/collection/parallel/mutable/ParHashSet.scala +++ b/src/library/scala/collection/parallel/mutable/ParHashSet.scala @@ -158,12 +158,12 @@ with scala.collection.mutable.FlatHashTable.HashUtils[T] { val tbl = new FlatHashTable[T] { sizeMapInit(table.length) seedvalue = ParHashSetCombiner.this.seedvalue + for { + buffer <- buckets; + if buffer ne null; + elem <- buffer + } addEntry(elem.asInstanceOf[T]) } - for { - buffer <- buckets; - if buffer ne null; - elem <- buffer - } tbl.addEntry(elem.asInstanceOf[T]) tbl.hashTableContents } |