diff options
-rw-r--r-- | src/library/scala/collection/immutable/HashMap.scala | 78 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/ListMap.scala | 14 | ||||
-rw-r--r-- | test/files/run/t6261.scala | 130 |
3 files changed, 182 insertions, 40 deletions
diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala index 0b297aeb45..b41327ed95 100644 --- a/src/library/scala/collection/immutable/HashMap.scala +++ b/src/library/scala/collection/immutable/HashMap.scala @@ -146,6 +146,29 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { private object EmptyHashMap extends HashMap[Any, Nothing] { } + // utility method to create a HashTrieMap from two leaf HashMaps (HashMap1 or HashMapCollision1) with non-colliding hash code) + private def makeHashTrieMap[A, B](hash0:Int, elem0:HashMap[A, B], hash1:Int, elem1:HashMap[A, B], level:Int, size:Int) : HashTrieMap[A, B] = { + val index0 = (hash0 >>> level) & 0x1f + val index1 = (hash1 >>> level) & 0x1f + if(index0 != index1) { + val bitmap = (1 << index0) | (1 << index1) + val elems = new Array[HashMap[A,B]](2) + if(index0 < index1) { + elems(0) = elem0 + elems(1) = elem1 + } else { + elems(0) = elem1 + elems(1) = elem0 + } + new HashTrieMap[A, B](bitmap, elems, size) + } else { + val elems = new Array[HashMap[A,B]](1) + val bitmap = (1 << index0) + elems(0) = makeHashTrieMap(hash0, elem0, hash1, elem1, level + 5, size) + new HashTrieMap[A, B](bitmap, elems, size) + } + } + // TODO: add HashMap2, HashMap3, ... class HashMap1[A,+B](private[collection] val key: A, private[collection] val hash: Int, private[collection] val value: (B @uV), private[collection] var kv: (A,B @uV)) extends HashMap[A,B] { @@ -183,30 +206,10 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { new HashMap1(nkv._1, hash, nkv._2, nkv) } } else { - var thatindex = (hash >>> level) & 0x1f - var thisindex = (this.hash >>> level) & 0x1f if (hash != this.hash) { // they have different hashes, but may collide at this level - find a level at which they don't - var lvl = level - var top: HashTrieMap[A, B1] = null - var prev: HashTrieMap[A, B1] = null - while (thisindex == thatindex) { - val newlevel = new HashTrieMap[A, B1](1 << thisindex, new Array[HashMap[A, B1]](1), 2) - if (prev ne null) prev.elems(0) = newlevel else top = newlevel - prev = newlevel - lvl += 5 - thatindex = (hash >>> lvl) & 0x1f - thisindex = (this.hash >>> lvl) & 0x1f - } - val bottelems = new Array[HashMap[A,B1]](2) - val ind = if (thisindex < thatindex) 1 else 0 - bottelems(1 - ind) = this - bottelems(ind) = new HashMap1[A, B1](key, hash, value, kv) - val bottom = new HashTrieMap[A,B1]((1 << thisindex) | (1 << thatindex), bottelems, 2) - if (prev ne null) { - prev.elems(0) = bottom - top - } else bottom + val that = new HashMap1[A, B1](key, hash, value, kv) + makeHashTrieMap[A,B1](this.hash, this, hash, that, level, 2) } else { // 32-bit hash collision (rare, but not impossible) new HashMapCollision1(hash, ListMap.empty.updated(this.key,this.value).updated(key,value)) @@ -221,12 +224,13 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { // this method may be called multiple times in a multithreaded environment, but that's ok private[HashMap] def ensurePair: (A,B) = if (kv ne null) kv else { kv = (key, value); kv } protected override def merge0[B1 >: B](that: HashMap[A, B1], level: Int, merger: Merger[A, B1]): HashMap[A, B1] = { - that.updated0(key, hash, level, value, kv, if (merger ne null) merger.invert else null) + that.updated0(key, hash, level, value, kv, merger.invert) } } private[collection] class HashMapCollision1[A, +B](private[collection] val hash: Int, val kvs: ListMap[A, B @uV]) extends HashMap[A, B @uV] { + // assert(kvs.size > 1) override def size = kvs.size @@ -238,20 +242,20 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { if ((merger eq null) || !kvs.contains(key)) new HashMapCollision1(hash, kvs.updated(key, value)) else new HashMapCollision1(hash, kvs + merger((key, kvs(key)), kv)) } else { - var m: HashMap[A,B1] = new HashTrieMap[A,B1](0,new Array[HashMap[A,B1]](0),0) - // might be able to save some ops here, but it doesn't seem to be worth it - for ((k,v) <- kvs) - m = m.updated0(k, this.hash, level, v, null, merger) - m.updated0(key, hash, level, value, kv, merger) + val that = new HashMap1(key, hash, value, kv) + makeHashTrieMap(this.hash, this, hash, that, level, size + 1) } override def removed0(key: A, hash: Int, level: Int): HashMap[A, B] = if (hash == this.hash) { val kvs1 = kvs - key - if (!kvs1.isEmpty) - new HashMapCollision1(hash, kvs1) - else + if (kvs1.isEmpty) HashMap.empty[A,B] + else if(kvs1.tail.isEmpty) { + val kv = kvs1.head + new HashMap1[A,B](kv._1,hash,kv._2,kv) + } else + new HashMapCollision1(hash, kvs1) } else this override def iterator: Iterator[(A,B)] = kvs.iterator @@ -275,6 +279,9 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { private[collection] val size0: Int ) extends HashMap[A, B @uV] { + // assert(Integer.bitCount(bitmap) == elems.length) + // assert(elems.length > 1 || (elems.length == 1 && elems(0).isInstanceOf[HashTrieMap[_,_]])) + /* def this (level: Int, m1: HashMap1[A,B], m2: HashMap1[A,B]) = { this(((m1.hash >>> level) & 0x1f) | ((m2.hash >>> level) & 0x1f), { @@ -347,9 +354,14 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { Array.copy(elems, 0, elemsNew, 0, offset) Array.copy(elems, offset + 1, elemsNew, offset, elems.length - offset - 1) val sizeNew = size - sub.size - new HashTrieMap(bitmapNew, elemsNew, sizeNew) + if (elemsNew.length == 1 && !elemsNew(0).isInstanceOf[HashTrieMap[_,_]]) + elemsNew(0) + else + new HashTrieMap(bitmapNew, elemsNew, sizeNew) } else HashMap.empty[A,B] + } else if(elems.length == 1 && !subNew.isInstanceOf[HashTrieMap[_,_]]) { + subNew } else { val elemsNew = new Array[HashMap[A,B]](elems.length) Array.copy(elems, 0, elemsNew, 0, elems.length) @@ -480,7 +492,7 @@ time { mNew.iterator.foreach( p => ()) } } new HashTrieMap[A, B1](this.bitmap | that.bitmap, merged, totalelems) - case hm: HashMapCollision1[_, _] => that.merge0(this, level, if (merger ne null) merger.invert else null) + case hm: HashMapCollision1[_, _] => that.merge0(this, level, merger.invert) case hm: HashMap[_, _] => this case _ => sys.error("section supposed to be unreachable.") } diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala index 091443f909..c21032603f 100644 --- a/src/library/scala/collection/immutable/ListMap.scala +++ b/src/library/scala/collection/immutable/ListMap.scala @@ -121,12 +121,12 @@ extends AbstractMap[A, B] def hasNext = !self.isEmpty def next(): (A,B) = if (!hasNext) throw new NoSuchElementException("next on empty iterator") - else { val res = (self.key, self.value); self = self.next; res } + else { val res = (self.key, self.value); self = self.tail; res } }.toList.reverseIterator protected def key: A = throw new NoSuchElementException("empty map") protected def value: B = throw new NoSuchElementException("empty map") - protected def next: ListMap[A, B] = throw new NoSuchElementException("empty map") + override def tail: ListMap[A, B] = throw new NoSuchElementException("empty map") /** This class represents an entry in the `ListMap`. */ @@ -140,7 +140,7 @@ extends AbstractMap[A, B] override def size: Int = size0(this, 0) // to allow tail recursion and prevent stack overflows - @tailrec private def size0(cur: ListMap[A, B1], acc: Int): Int = if (cur.isEmpty) acc else size0(cur.next, acc + 1) + @tailrec private def size0(cur: ListMap[A, B1], acc: Int): Int = if (cur.isEmpty) acc else size0(cur.tail, acc + 1) /** Is this an empty map? * @@ -157,7 +157,7 @@ extends AbstractMap[A, B] */ override def apply(k: A): B1 = apply0(this, k) - @tailrec private def apply0(cur: ListMap[A, B1], k: A): B1 = if (k == cur.key) cur.value else apply0(cur.next, k) + @tailrec private def apply0(cur: ListMap[A, B1], k: A): B1 = if (k == cur.key) cur.value else apply0(cur.tail, k) /** Checks if this map maps `key` to a value and return the * value if it exists. @@ -169,7 +169,7 @@ extends AbstractMap[A, B] @tailrec private def get0(cur: ListMap[A, B1], k: A): Option[B1] = if (k == cur.key) Some(cur.value) - else if (cur.next.nonEmpty) get0(cur.next, k) else None + else if (cur.tail.nonEmpty) get0(cur.tail, k) else None /** This method allows one to create a new map with an additional mapping * from `key` to `value`. If the map contains already a mapping for `key`, @@ -198,7 +198,7 @@ extends AbstractMap[A, B] var lst: List[(A, B1)] = Nil while (cur.nonEmpty) { if (k != cur.key) lst ::= ((cur.key, cur.value)) - cur = cur.next + cur = cur.tail } var acc = ListMap[A, B1]() while (lst != Nil) { @@ -211,6 +211,6 @@ extends AbstractMap[A, B] } - override protected def next: ListMap[A, B1] = ListMap.this + override def tail: ListMap[A, B1] = ListMap.this } } diff --git a/test/files/run/t6261.scala b/test/files/run/t6261.scala new file mode 100644 index 0000000000..b4463256c9 --- /dev/null +++ b/test/files/run/t6261.scala @@ -0,0 +1,130 @@ +import scala.collection.immutable._ + +object Test extends App { + + def test0() { + val m=ListMap(1->2,3->4) + if(m.tail ne m.tail) + println("ListMap.tail uses a builder, so it is not O(1)") + } + + def test1() { + // test that a HashTrieMap with one leaf element is not created! + val x = HashMap.empty + (1->1) + (2->2) + if(x.getClass.getSimpleName != "HashTrieMap") + println("A hash map containing two non-colliding values should be a HashTrieMap") + + val y = x - 1 + if(y.getClass.getSimpleName != "HashMap1") + println("A hash map containing one element should always use HashMap1") + } + + def test2() { + // class that always causes hash collisions + case class Collision(value:Int) { override def hashCode = 0 } + + // create a set that should have a collison + val x = HashMap.empty + (Collision(0)->0) + (Collision(1) ->0) + if(x.getClass.getSimpleName != "HashMapCollision1") + println("HashMap of size >1 with collisions should use HashMapCollision") + + // remove the collision again by removing all but one element + val y = x - Collision(0) + if(y.getClass.getSimpleName != "HashMap1") + println("HashMap of size 1 should use HashMap1" + y.getClass) + } + def test3() { + // finds an int x such that improved(x) differs in the first bit to improved(0), + // which is the worst case for the HashTrieSet + def findWorstCaseInts() { + // copy of improve from HashSet + def improve(hcode: Int) = { + var h: Int = hcode + ~(hcode << 9) + h = h ^ (h >>> 14) + h = h + (h << 4) + h ^ (h >>> 10) + } + + // find two hashes which have a large separation + val x = 0 + var y = 1 + val ix = improve(x) + while(y!=0 && improve(y)!=ix+(1<<31)) + y+=1 + printf("%s %s %x %x\n",x,y,improve(x), improve(y)) + } + // this is not done every test run since it would slow down ant test.suite too much. + // findWorstCaseInts() + + // two numbers that are immediately adiacent when fed through HashSet.improve + val h0 = 0 + val h1 = 1270889724 + + // h is the hashcode, i is ignored for the hashcode but relevant for equality + case class Collision(h:Int, i:Int) { + override def hashCode = h + } + val a = Collision(h0,0)->0 + val b = Collision(h0,1)->0 + val c = Collision(h1,0)->0 + + // create a HashSetCollision1 + val x = HashMap(a) + b + if(x.getClass.getSimpleName != "HashMapCollision1") + println("x should be a HashMapCollision") + StructureTests.validate(x) + //StructureTests.printStructure(x) + require(x.size==2 && x.contains(a._1) && x.contains(b._1)) + + // go from a HashSetCollision1 to a HashTrieSet with maximum depth + val y = x + c + if(y.getClass.getSimpleName != "HashTrieMap") + println("y should be a HashTrieMap") + StructureTests.validate(y) + // StructureTests.printStructure(y) + require(y.size==3 && y.contains(a._1) && y.contains(b._1) && y.contains(c._1)) + + // go from a HashSet1 directly to a HashTrieSet with maximum depth + val z = HashMap(a) + c + if(y.getClass.getSimpleName != "HashTrieMap") + println("y should be a HashTrieMap") + StructureTests.validate(z) + // StructureTests.printStructure(z) + require(z.size == 2 && z.contains(a._1) && z.contains(c._1)) + } + test0() + test1() + test2() + test3() +} + + +package scala.collection.immutable { + object StructureTests { + def printStructure(x:HashMap[_,_], prefix:String="") { + x match { + case m:HashMap.HashTrieMap[_,_] => + println(prefix+m.getClass.getSimpleName + " " + m.size) + m.elems.foreach(child => printStructure(child, prefix + " ")) + case m:HashMap.HashMapCollision1[_,_] => + println(prefix+m.getClass.getSimpleName + " " + m.kvs.size) + case m:HashMap.HashMap1[_,_] => + println(prefix+m.getClass.getSimpleName + " " + m.head) + case _ => + println(prefix+"empty") + } + } + + def validate(x:HashMap[_,_]) { + x match { + case m:HashMap.HashTrieMap[_,_] => + require(m.elems.size>1 || (m.elems.size==1 && m.elems(0).isInstanceOf[HashMap.HashTrieMap[_,_]])) + m.elems.foreach(validate _) + case m:HashMap.HashMapCollision1[_,_] => + require(m.kvs.size>1) + case m:HashMap.HashMap1[_,_] => + case _ => + } + } + } +} |