diff options
author | Josh Suereth <Joshua.Suereth@gmail.com> | 2012-08-30 04:59:40 -0700 |
---|---|---|
committer | Josh Suereth <Joshua.Suereth@gmail.com> | 2012-08-30 04:59:40 -0700 |
commit | 51c94a2a2ee78e23491a29a971c9f7469b221cf5 (patch) | |
tree | 8b7ab67d2734167b947af9681e9bc6a8483a890d /src | |
parent | 415639fbf6b7f1a9366e970a8850a0d735dc7a14 (diff) | |
parent | 02adfef0bec1f5c38f6821a3709e0544c52f6c91 (diff) | |
download | scala-51c94a2a2ee78e23491a29a971c9f7469b221cf5.tar.gz scala-51c94a2a2ee78e23491a29a971c9f7469b221cf5.tar.bz2 scala-51c94a2a2ee78e23491a29a971c9f7469b221cf5.zip |
Merge pull request #1169 from rklaehn/SI-6261
Si 6261
Diffstat (limited to 'src')
-rw-r--r-- | src/library/scala/collection/immutable/HashMap.scala | 78 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/ListMap.scala | 14 |
2 files changed, 52 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 } } |