diff options
-rw-r--r-- | src/library/scala/collection/mutable/AnyRefMap.scala | 451 | ||||
-rw-r--r-- | src/library/scala/collection/mutable/LongMap.scala | 558 | ||||
-rw-r--r-- | test/files/run/mutable-anyrefmap.scala | 91 | ||||
-rw-r--r-- | test/files/run/mutable-longmap.scala | 79 |
4 files changed, 1179 insertions, 0 deletions
diff --git a/src/library/scala/collection/mutable/AnyRefMap.scala b/src/library/scala/collection/mutable/AnyRefMap.scala new file mode 100644 index 0000000000..df74bb5187 --- /dev/null +++ b/src/library/scala/collection/mutable/AnyRefMap.scala @@ -0,0 +1,451 @@ +package scala +package collection +package mutable + +import generic.CanBuildFrom + +/** This class implements mutable maps with `AnyRef` keys based on a hash table with open addressing. + * + * Basic map operations on single entries, including `contains` and `get`, + * are typically significantly faster with `AnyRefMap` than [[HashMap]]. + * Note that numbers and characters are not handled specially in AnyRefMap; + * only plain `equals` and `hashCode` are used in comparisons. + * + * Methods that traverse or regenerate the map, including `foreach` and `map`, + * are not in general faster than with `HashMap`. The methods `foreachKey`, + * `foreachValue`, `mapValuesNow`, and `transformValues` are, however, faster + * than alternative ways to achieve the same functionality. + * + * Maps with open addressing may become less efficient at lookup after + * repeated addition/removal of elements. Although `AnyRefMap` makes a + * decent attempt to remain efficient regardless, calling `repack` + * on a map that will no longer have elements removed but will be + * used heavily may save both time and storage space. + * + * This map is not indended to contain more than 2^29 entries (approximately + * 500 million). The maximum capacity is 2^30, but performance will degrade + * rapidly as 2^30 is approached. + * + */ +final class AnyRefMap[K <: AnyRef, V] private[collection] (defaultEntry: K => V, initialBufferSize: Int, initBlank: Boolean) +extends AbstractMap[K, V] + with Map[K, V] + with MapLike[K, V, AnyRefMap[K, V]] +{ + import AnyRefMap._ + def this() = this(AnyRefMap.exceptionDefault, 16, true) + + /** Creates a new `AnyRefMap` that returns default values according to a supplied key-value mapping. */ + def this(defaultEntry: K => V) = this(defaultEntry, 16, true) + + /** Creates a new `AnyRefMap` with an initial buffer of specified size. + * + * An `AnyRefMap` can typically contain half as many elements as its buffer size + * before it requires resizing. + */ + def this(initialBufferSize: Int) = this(AnyRefMap.exceptionDefault, initialBufferSize, true) + + /** Creates a new `AnyRefMap` with specified default values and initial buffer size. */ + def this(defaultEntry: K => V, initialBufferSize: Int) = this(defaultEntry, initialBufferSize, true) + + private[this] var mask = 0 + private[this] var _size = 0 + private[this] var _vacant = 0 + private[this] var _hashes: Array[Int] = null + private[this] var _keys: Array[AnyRef] = null + private[this] var _values: Array[AnyRef] = null + + if (initBlank) defaultInitialize(initialBufferSize) + + private[this] def defaultInitialize(n: Int) { + mask = + if (n<0) 0x7 + else (((1 << (32 - java.lang.Integer.numberOfLeadingZeros(n-1))) - 1) & 0x3FFFFFFF) | 0x7 + _hashes = new Array[Int](mask+1) + _keys = new Array[AnyRef](mask+1) + _values = new Array[AnyRef](mask+1) + } + + private[collection] def initializeTo( + m: Int, sz: Int, vc: Int, hz: Array[Int], kz: Array[AnyRef], vz: Array[AnyRef] + ) { + mask = m; _size = sz; _vacant = vc; _hashes = hz; _keys = kz; _values = vz + } + + override def size: Int = _size + override def empty: AnyRefMap[K,V] = new AnyRefMap(defaultEntry) + + private def imbalanced: Boolean = + (_size + _vacant) > 0.5*mask || _vacant > _size + + private def hashOf(key: K): Int = { + if (key eq null) 0x41081989 + else { + val h = key.hashCode + // Part of the MurmurHash3 32 bit finalizer + val i = (h ^ (h >>> 16)) * 0x85EBCA6B + val j = (i ^ (i >>> 13)) + if (j==0) 0x41081989 else j & 0x7FFFFFFF + } + } + + private def seekEntry(h: Int, k: AnyRef): Int = { + var e = h & mask + var x = 0 + var g = 0 + while ({ g = _hashes(e); g != 0}) { + if (g == h && { val q = _keys(e); (q eq k) || ((q ne null) && (q equals k)) }) return e + x += 1 + e = (e + 2*(x+1)*x - 3) & mask + } + e | MissingBit + } + + private def seekEntryOrOpen(h: Int, k: AnyRef): Int = { + var e = h & mask + var x = 0 + var g = 0 + var o = -1 + while ({ g = _hashes(e); g != 0}) { + if (g == h && { val q = _keys(e); (q eq k) || ((q ne null) && (q equals k)) }) return e + else if (o == -1 && g+g == 0) o = e + x += 1 + e = (e + 2*(x+1)*x - 3) & mask + } + if (o >= 0) o | MissVacant else e | MissingBit + } + + override def contains(key: K): Boolean = seekEntry(hashOf(key), key) >= 0 + + override def get(key: K): Option[V] = { + val i = seekEntry(hashOf(key), key) + if (i < 0) None else Some(_values(i).asInstanceOf[V]) + } + + override def getOrElse[V1 >: V](key: K, default: => V1): V1 = { + val i = seekEntry(hashOf(key), key) + if (i < 0) default else _values(i).asInstanceOf[V] + } + + override def getOrElseUpdate(key: K, defaultValue: => V): V = { + val h = hashOf(key) + val i = seekEntryOrOpen(h, key) + if (i < 0) { + val value = defaultValue + _size += 1 + val j = i & IndexMask + _hashes(j) = h + _keys(j) = key.asInstanceOf[AnyRef] + _values(j) = value.asInstanceOf[AnyRef] + if ((i & VacantBit) != 0) _vacant -= 1 + else if (imbalanced) repack() + value + } + else _values(i).asInstanceOf[V] + } + + /** Retrieves the value associated with a key, or the default for that type if none exists + * (null for AnyRef, 0 for floats and integers). + * + * Note: this is the fastest way to retrieve a value that may or + * may not exist, if the default null/zero is acceptable. For key/value + * pairs that do exist, `apply` (i.e. `map(key)`) is equally fast. + */ + def getOrNull(key: K): V = { + val i = seekEntry(hashOf(key), key) + (if (i < 0) null else _values(i)).asInstanceOf[V] + } + + /** Retrieves the value associated with a key. + * If the key does not exist in the map, the `defaultEntry` for that key + * will be returned instead; an exception will be thrown if no + * `defaultEntry` was supplied. + */ + override def apply(key: K): V = { + val i = seekEntry(hashOf(key), key) + if (i < 0) defaultEntry(key) else _values(i).asInstanceOf[V] + } + + /** Defers to defaultEntry to find a default value for the key. Throws an + * exception if no other default behavior was specified. + */ + override def default(key: K) = defaultEntry(key) + + private def repack(newMask: Int) { + val oh = _hashes + val ok = _keys + val ov = _values + mask = newMask + _hashes = new Array[Int](mask+1) + _keys = new Array[AnyRef](mask+1) + _values = new Array[AnyRef](mask+1) + _vacant = 0 + var i = 0 + while (i < oh.length) { + val h = oh(i) + if (h+h != 0) { + var e = h & mask + var x = 0 + while (_hashes(e) != 0) { x += 1; e = (e + 2*(x+1)*x - 3) & mask } + _hashes(e) = h + _keys(e) = ok(i) + _values(e) = ov(i) + } + i += 1 + } + } + + /** Repacks the contents of this `AnyRefMap` for maximum efficiency of lookup. + * + * For maps that undergo a complex creation process with both addition and + * removal of keys, and then are used heavily with no further removal of + * elements, calling `repack` after the end of the creation can result in + * improved performance. Repacking takes time proportional to the number + * of entries in the map. + */ + def repack() { + var m = mask + if (_size + _vacant >= 0.5*mask && !(_vacant > 0.2*mask)) m = ((m << 1) + 1) & IndexMask + while (m > 8 && 8*_size < m) m = m >>> 1 + repack(m) + } + + override def put(key: K, value: V): Option[V] = { + val h = hashOf(key) + val k = key + var i = seekEntryOrOpen(h, k) + if (i < 0) { + val j = i & IndexMask + _hashes(j) = h + _keys(j) = k + _values(j) = value.asInstanceOf[AnyRef] + _size += 1 + if ((i & VacantBit) != 0) _vacant -= 1 + else if (imbalanced) repack() + None + } + else { + val ans = Some(_values(i).asInstanceOf[V]) + _hashes(i) = h + _keys(i) = k + _values(i) = value.asInstanceOf[AnyRef] + ans + } + } + + /** Updates the map to include a new key-value pair. + * + * This is the fastest way to add an entry to an `AnyRefMap`. + */ + override def update(key: K, value: V): Unit = { + val h = hashOf(key) + val k = key + var i = seekEntryOrOpen(h, k) + if (i < 0) { + val j = i & IndexMask + _hashes(j) = h + _keys(j) = k + _values(j) = value.asInstanceOf[AnyRef] + _size += 1 + if ((i & VacantBit) != 0) _vacant -= 1 + else if (imbalanced) repack() + } + else { + _hashes(i) = h + _keys(i) = k + _values(i) = value.asInstanceOf[AnyRef] + } + } + + /** Adds a new key/value pair to this map and returns the map. */ + def +=(key: K, value: V): this.type = { update(key, value); this } + + def +=(kv: (K, V)): this.type = { update(kv._1, kv._2); this } + + def -=(key: K): this.type = { + val i = seekEntry(hashOf(key), key) + if (i >= 0) { + _size -= 1 + _vacant += 1 + _hashes(i) = Int.MinValue + _keys(i) = null + _values(i) = null + } + this + } + + def iterator: Iterator[(K, V)] = new Iterator[(K, V)] { + private[this] val hz = _hashes + private[this] val kz = _keys + private[this] val vz = _values + + private[this] var index = 0 + private[this] var found = false + + def hasNext = found || (index<hz.length && { + var h = hz(index) + if (h+h != 0) found = true + else { + index += 1 + while (index < hz.length && { h = hz(index); h+h == 0 }) index += 1 + found = (index < hz.length) + } + found + }) + + def next = { + if (found || hasNext) { + val ans = (_keys(index).asInstanceOf[K], _values(index).asInstanceOf[V]) + index += 1 + found = false + ans + } + else throw new NoSuchElementException("next") + } + } + + override def foreach[A](f: ((K,V)) => A) { + var i = 0 + var e = _size + while (e > 0) { + while(i < _hashes.length && { val h = _hashes(i); h+h == 0 && i < _hashes.length}) i += 1 + if (i < _hashes.length) { + f((_keys(i).asInstanceOf[K], _values(i).asInstanceOf[V])) + i += 1 + e -= 1 + } + else return + } + } + + override def clone(): AnyRefMap[K, V] = { + val hz = java.util.Arrays.copyOf(_hashes, _hashes.length) + val kz = java.util.Arrays.copyOf(_keys, _keys.length) + val vz = java.util.Arrays.copyOf(_values, _values.length) + val arm = new AnyRefMap[K, V](defaultEntry, 1, false) + arm.initializeTo(mask, _size, _vacant, hz, kz, vz) + arm + } + + private[this] def foreachElement[A,B](elems: Array[AnyRef], f: A => B) { + var i,j = 0 + while (i < _hashes.length & j < _size) { + val h = _hashes(i) + if (h+h != 0) { + j += 1 + f(elems(i).asInstanceOf[A]) + } + i += 1 + } + } + + /** Applies a function to all keys of this map. */ + def foreachKey[A](f: K => A) { foreachElement[K,A](_keys, f) } + + /** Applies a function to all values of this map. */ + def foreachValue[A](f: V => A) { foreachElement[V,A](_values, f) } + + /** Creates a new `AnyRefMap` with different values. + * Unlike `mapValues`, this method generates a new + * collection immediately. + */ + def mapValuesNow[V1](f: V => V1): AnyRefMap[K, V1] = { + val arm = new AnyRefMap[K,V1](AnyRefMap.exceptionDefault, 1, false) + val hz = java.util.Arrays.copyOf(_hashes, _hashes.length) + val kz = java.util.Arrays.copyOf(_keys, _keys.length) + val vz = new Array[AnyRef](_values.length) + var i,j = 0 + while (i < _hashes.length & j < _size) { + val h = _hashes(i) + if (h+h != 0) { + j += 1 + vz(i) = f(_values(i).asInstanceOf[V]).asInstanceOf[AnyRef] + } + i += 1 + } + arm.initializeTo(mask, _size, _vacant, hz, kz, vz) + arm + } + + /** Applies a transformation function to all values stored in this map. + * Note: the default, if any, is not transformed. + */ + def transformValues(f: V => V): this.type = { + var i,j = 0 + while (i < _hashes.length & j < _size) { + val h = _hashes(i) + if (h+h != 0) { + j += 1 + _values(i) = f(_values(i).asInstanceOf[V]).asInstanceOf[AnyRef] + } + i += 1 + } + this + } + +} + +object AnyRefMap { + private final val IndexMask = 0x3FFFFFFF + private final val MissingBit = 0x80000000 + private final val VacantBit = 0x40000000 + private final val MissVacant = 0xC0000000 + + private val exceptionDefault = (k: Any) => throw new NoSuchElementException(if (k == null) "(null)" else k.toString) + + implicit def canBuildFrom[K <: AnyRef, V, J <: AnyRef, U]: CanBuildFrom[AnyRefMap[K,V], (J, U), AnyRefMap[J,U]] = + new CanBuildFrom[AnyRefMap[K,V], (J, U), AnyRefMap[J,U]] { + def apply(from: AnyRefMap[K,V]): AnyRefMapBuilder[J, U] = apply() + def apply(): AnyRefMapBuilder[J, U] = new AnyRefMapBuilder[J, U] + } + + final class AnyRefMapBuilder[K <: AnyRef, V] extends Builder[(K, V), AnyRefMap[K, V]] { + private[collection] var elems: AnyRefMap[K, V] = new AnyRefMap[K, V] + def +=(entry: (K, V)): this.type = { + elems += entry + this + } + def clear() { elems = new AnyRefMap[K, V] } + def result(): AnyRefMap[K, V] = elems + } + + /** Creates a new `AnyRefMap` with zero or more key/value pairs. */ + def apply[K <: AnyRef, V](elems: (K, V)*): AnyRefMap[K, V] = { + val sz = if (elems.hasDefiniteSize) elems.size else 4 + val arm = new AnyRefMap[K, V](sz * 2) + elems.foreach{ case (k,v) => arm(k) = v } + if (arm.size < (sz>>3)) arm.repack() + arm + } + + /** Creates a new empty `AnyRefMap`. */ + def empty[K <: AnyRef, V]: AnyRefMap[K, V] = new AnyRefMap[K, V] + + /** Creates a new empty `AnyRefMap` with the supplied default */ + def withDefault[K <: AnyRef, V](default: K => V): AnyRefMap[K, V] = new AnyRefMap[K, V](default) + + /** Creates a new `AnyRefMap` from arrays of keys and values. + * Equivalent to but more efficient than `AnyRefMap((keys zip values): _*)`. + */ + def fromZip[K <: AnyRef, V](keys: Array[K], values: Array[V]): AnyRefMap[K, V] = { + val sz = math.min(keys.length, values.length) + val arm = new AnyRefMap[K, V](sz * 2) + var i = 0 + while (i < sz) { arm(keys(i)) = values(i); i += 1 } + if (arm.size < (sz>>3)) arm.repack() + arm + } + + /** Creates a new `AnyRefMap` from keys and values. + * Equivalent to but more efficient than `AnyRefMap((keys zip values): _*)`. + */ + def fromZip[K <: AnyRef, V](keys: Iterable[K], values: Iterable[V]): AnyRefMap[K, V] = { + val sz = math.min(keys.size, values.size) + val arm = new AnyRefMap[K, V](sz * 2) + val ki = keys.iterator + val vi = values.iterator + while (ki.hasNext && vi.hasNext) arm(ki.next) = vi.next + if (arm.size < (sz >> 3)) arm.repack() + arm + } +} diff --git a/src/library/scala/collection/mutable/LongMap.scala b/src/library/scala/collection/mutable/LongMap.scala new file mode 100644 index 0000000000..81c381279f --- /dev/null +++ b/src/library/scala/collection/mutable/LongMap.scala @@ -0,0 +1,558 @@ +package scala +package collection +package mutable + +import generic.CanBuildFrom + +/** This class implements mutable maps with `Long` keys based on a hash table with open addressing. + * + * Basic map operations on single entries, including `contains` and `get`, + * are typically substantially faster with `LongMap` than [[HashMap]]. Methods + * that act on the whole map, including `foreach` and `map` are not in + * general expected to be faster than with a generic map, save for those + * that take particular advantage of the internal structure of the map: + * `foreachKey`, `foreachValue`, `mapValuesNow`, and `transformValues`. + * + * Maps with open addressing may become less efficient at lookup after + * repeated addition/removal of elements. Although `LongMap` makes a + * decent attempt to remain efficient regardless, calling `repack` + * on a map that will no longer have elements removed but will be + * used heavily may save both time and storage space. + * + * This map is not indended to contain more than 2^29 entries (approximately + * 500 million). The maximum capacity is 2^30, but performance will degrade + * rapidly as 2^30 is approached. + * + */ +final class LongMap[V] private[collection] (defaultEntry: Long => V, initialBufferSize: Int, initBlank: Boolean) +extends AbstractMap[Long, V] + with Map[Long, V] + with MapLike[Long, V, LongMap[V]] + with Serializable +{ + import LongMap._ + + def this() = this(LongMap.exceptionDefault, 16, true) + + /** Creates a new `LongMap` that returns default values according to a supplied key-value mapping. */ + def this(defaultEntry: Long => V) = this(defaultEntry, 16, true) + + /** Creates a new `LongMap` with an initial buffer of specified size. + * + * A LongMap can typically contain half as many elements as its buffer size + * before it requires resizing. + */ + def this(initialBufferSize: Int) = this(LongMap.exceptionDefault, initialBufferSize, true) + + /** Creates a new `LongMap` with specified default values and initial buffer size. */ + def this(defaultEntry: Long => V, initialBufferSize: Int) = this(defaultEntry, initialBufferSize, true) + + private[this] var mask = 0 + private[this] var extraKeys: Int = 0 + private[this] var zeroValue: AnyRef = null + private[this] var minValue: AnyRef = null + private[this] var _size = 0 + private[this] var _vacant = 0 + private[this] var _keys: Array[Long] = null + private[this] var _values: Array[AnyRef] = null + + if (initBlank) defaultInitialize(initialBufferSize) + + private[this] def defaultInitialize(n: Int) = { + mask = + if (n<0) 0x7 + else (((1 << (32 - java.lang.Integer.numberOfLeadingZeros(n-1))) - 1) & 0x3FFFFFFF) | 0x7 + _keys = new Array[Long](mask+1) + _values = new Array[AnyRef](mask+1) + } + + private[collection] def initializeTo( + m: Int, ek: Int, zv: AnyRef, mv: AnyRef, sz: Int, vc: Int, kz: Array[Long], vz: Array[AnyRef] + ) { + mask = m; extraKeys = ek; zeroValue = zv; minValue = mv; _size = sz; _vacant = vc; _keys = kz; _values = vz + } + + override def size: Int = _size + (extraKeys+1)/2 + override def empty: LongMap[V] = new LongMap() + + private def imbalanced: Boolean = + (_size + _vacant) > 0.5*mask || _vacant > _size + + private def toIndex(k: Long): Int = { + // Part of the MurmurHash3 32 bit finalizer + val h = ((k ^ (k >>> 32)) & 0xFFFFFFFFL).toInt + var x = (h ^ (h >>> 16)) * 0x85EBCA6B + (x ^ (x >>> 13)) & mask + } + + private def seekEmpty(k: Long): Int = { + var e = toIndex(k) + var x = 0 + while (_keys(e) != 0) { x += 1; e = (e + 2*(x+1)*x - 3) & mask } + e + } + + private def seekEntry(k: Long): Int = { + var e = toIndex(k) + var x = 0 + var q = 0L + while ({ q = _keys(e); if (q==k) return e; q != 0}) { x += 1; e = (e + 2*(x+1)*x - 3) & mask } + e | MissingBit + } + + private def seekEntryOrOpen(k: Long): Int = { + var e = toIndex(k) + var x = 0 + var q = 0L + while ({ q = _keys(e); if (q==k) return e; q+q != 0}) { + x += 1 + e = (e + 2*(x+1)*x - 3) & mask + } + if (q == 0) return e | MissingBit + val o = e | MissVacant + while ({ q = _keys(e); if (q==k) return e; q != 0}) { + x += 1 + e = (e + 2*(x+1)*x - 3) & mask + } + o + } + + override def contains(key: Long): Boolean = { + if (key == -key) (((key>>>63).toInt+1) & extraKeys) != 0 + else seekEntry(key) >= 0 + } + + override def get(key: Long): Option[V] = { + if (key == -key) { + if ((((key>>>63).toInt+1) & extraKeys) == 0) None + else if (key == 0) Some(zeroValue.asInstanceOf[V]) + else Some(minValue.asInstanceOf[V]) + } + else { + val i = seekEntry(key) + if (i < 0) None else Some(_values(i).asInstanceOf[V]) + } + } + + override def getOrElse[V1 >: V](key: Long, default: => V1): V1 = { + if (key == -key) { + if ((((key>>>63).toInt+1) & extraKeys) == 0) default + else if (key == 0) zeroValue.asInstanceOf[V1] + else minValue.asInstanceOf[V1] + } + else { + val i = seekEntry(key) + if (i < 0) default else _values(i).asInstanceOf[V1] + } + } + + override def getOrElseUpdate(key: Long, defaultValue: => V): V = { + if (key == -key) { + val kbits = (key>>>63).toInt + 1 + if ((kbits & extraKeys) == 0) { + val value = defaultValue + extraKeys |= kbits + if (key == 0) zeroValue = value.asInstanceOf[AnyRef] + else minValue = value.asInstanceOf[AnyRef] + value + } + else if (key == 0) zeroValue.asInstanceOf[V] + else minValue.asInstanceOf[V] + } + else { + val i = seekEntryOrOpen(key) + if (i < 0) { + val value = defaultValue + _size += 1 + val j = i & IndexMask + _keys(j) = key + _values(j) = value.asInstanceOf[AnyRef] + if ((i & VacantBit) != 0) _vacant -= 1 + else if (imbalanced) repack() + value + } + else _values(i).asInstanceOf[V] + } + } + + /** Retrieves the value associated with a key, or the default for that type if none exists + * (null for AnyRef, 0 for floats and integers). + * + * Note: this is the fastest way to retrieve a value that may or + * may not exist, if the default null/zero is acceptable. For key/value + * pairs that do exist, `apply` (i.e. `map(key)`) is equally fast. + */ + def getOrNull(key: Long): V = { + if (key == -key) { + if ((((key>>>63).toInt+1) & extraKeys) == 0) null.asInstanceOf[V] + else if (key == 0) zeroValue.asInstanceOf[V] + else minValue.asInstanceOf[V] + } + else { + val i = seekEntry(key) + if (i < 0) null.asInstanceOf[V] else _values(i).asInstanceOf[V] + } + } + + /** Retrieves the value associated with a key. + * If the key does not exist in the map, the `defaultEntry` for that key + * will be returned instead. + */ + override def apply(key: Long): V = { + if (key == -key) { + if ((((key>>>63).toInt+1) & extraKeys) == 0) defaultEntry(key) + else if (key == 0) zeroValue.asInstanceOf[V] + else minValue.asInstanceOf[V] + } + else { + val i = seekEntry(key) + if (i < 0) defaultEntry(key) else _values(i).asInstanceOf[V] + } + } + + /** The user-supplied default value for the key. Throws an exception + * if no other default behavior was specified. + */ + override def default(key: Long) = defaultEntry(key) + + private def repack(newMask: Int) { + val ok = _keys + val ov = _values + mask = newMask + _keys = new Array[Long](mask+1) + _values = new Array[AnyRef](mask+1) + _vacant = 0 + var i = 0 + while (i < ok.length) { + val k = ok(i) + if (k != -k) { + val j = seekEmpty(k) + _keys(j) = k + _values(j) = ov(i) + } + i += 1 + } + } + + /** Repacks the contents of this `LongMap` for maximum efficiency of lookup. + * + * For maps that undergo a complex creation process with both addition and + * removal of keys, and then are used heavily with no further removal of + * elements, calling `repack` after the end of the creation can result in + * improved performance. Repacking takes time proportional to the number + * of entries in the map. + */ + def repack() { + var m = mask + if (_size + _vacant >= 0.5*mask && !(_vacant > 0.2*mask)) m = ((m << 1) + 1) & IndexMask + while (m > 8 && 8*_size < m) m = m >>> 1 + repack(m) + } + + override def put(key: Long, value: V): Option[V] = { + if (key == -key) { + if (key == 0) { + val ans = if ((extraKeys&1) == 1) Some(zeroValue.asInstanceOf[V]) else None + zeroValue = value.asInstanceOf[AnyRef] + extraKeys |= 1 + ans + } + else { + val ans = if ((extraKeys&2) == 1) Some(minValue.asInstanceOf[V]) else None + minValue = value.asInstanceOf[AnyRef] + extraKeys |= 2 + ans + } + } + else { + val i = seekEntryOrOpen(key) + if (i < 0) { + val j = i & IndexMask + _keys(j) = key + _values(j) = value.asInstanceOf[AnyRef] + _size += 1 + if ((i & VacantBit) != 0) _vacant -= 1 + else if (imbalanced) repack() + None + } + else { + val ans = Some(_values(i).asInstanceOf[V]) + _keys(i) = key + _values(i) = value.asInstanceOf[AnyRef] + ans + } + } + } + + /** Updates the map to include a new key-value pair. + * + * This is the fastest way to add an entry to a `LongMap`. + */ + override def update(key: Long, value: V): Unit = { + if (key == -key) { + if (key == 0) { + zeroValue = value.asInstanceOf[AnyRef] + extraKeys |= 1 + } + else { + minValue = value.asInstanceOf[AnyRef] + extraKeys |= 2 + } + } + else { + var i = seekEntryOrOpen(key) + if (i < 0) { + val j = i & IndexMask + _keys(j) = key + _values(j) = value.asInstanceOf[AnyRef] + _size += 1 + if ((i & VacantBit) != 0) _vacant -= 1 + else if (imbalanced) repack() + } + else { + _keys(i) = key + _values(i) = value.asInstanceOf[AnyRef] + } + } + } + + /** Adds a new key/value pair to this map and returns the map. */ + def +=(key: Long, value: V): this.type = { update(key, value); this } + + def +=(kv: (Long, V)): this.type = { update(kv._1, kv._2); this } + + def -=(key: Long): this.type = { + if (key == -key) { + if (key == 0L) { + extraKeys &= 0x2 + zeroValue = null + } + else { + extraKeys &= 0x1 + minValue = null + } + } + else { + val i = seekEntry(key) + if (i >= 0) { + _size -= 1 + _vacant += 1 + _keys(i) = Long.MinValue + _values(i) = null + } + } + this + } + + def iterator: Iterator[(Long, V)] = new Iterator[(Long, V)] { + private[this] val kz = _keys + private[this] val vz = _values + + private[this] var nextPair: (Long, V) = + if (extraKeys==0) null + else if ((extraKeys&1)==1) (0L, zeroValue.asInstanceOf[V]) + else (Long.MinValue, minValue.asInstanceOf[V]) + + private[this] var anotherPair: (Long, V) = + if (extraKeys==3) (Long.MinValue, minValue.asInstanceOf[V]) + else null + + private[this] var index = 0 + + def hasNext: Boolean = nextPair != null || (index < kz.length && { + var q = kz(index) + while (q == -q) { + index += 1 + if (index >= kz.length) return false + q = kz(index) + } + nextPair = (kz(index), vz(index).asInstanceOf[V]) + index += 1 + true + }) + def next = { + if (nextPair == null && !hasNext) throw new NoSuchElementException("next") + val ans = nextPair + if (anotherPair != null) { + nextPair = anotherPair + anotherPair = null + } + nextPair = null + ans + } + } + + override def foreach[A](f: ((Long,V)) => A) { + var i,j = 0 + while (i < _keys.length & j < _size) { + val k = _keys(i) + if (k != -k) { + j += 1 + f((k, _values(i).asInstanceOf[V])) + } + i += 1 + } + if ((extraKeys & 1) == 1) f((0L, zeroValue.asInstanceOf[V])) + if ((extraKeys & 2) == 2) f((Long.MinValue, minValue.asInstanceOf[V])) + } + + override def clone(): LongMap[V] = { + val kz = java.util.Arrays.copyOf(_keys, _keys.length) + val vz = java.util.Arrays.copyOf(_values, _values.length) + val lm = new LongMap[V](defaultEntry, 1, false) + lm.initializeTo(mask, extraKeys, zeroValue, minValue, _size, _vacant, kz, vz) + lm + } + + /** Applies a function to all keys of this map. */ + def foreachKey[A](f: Long => A) { + var i,j = 0 + while (i < _keys.length & j < _size) { + val k = _keys(i) + if (k != -k) { + j += 1 + f(k) + } + i += 1 + } + if ((extraKeys & 1) == 1) f(0L) + if ((extraKeys & 2) == 2) f(Long.MinValue) + } + + /** Applies a function to all values of this map. */ + def foreachValue[A](f: V => A) { + var i,j = 0 + while (i < _keys.length & j < _size) { + val k = _keys(i) + if (k != -k) { + j += 1 + f(_values(i).asInstanceOf[V]) + } + i += 1 + } + if ((extraKeys & 1) == 1) f(zeroValue.asInstanceOf[V]) + if ((extraKeys & 2) == 2) f(minValue.asInstanceOf[V]) + } + + /** Creates a new `LongMap` with different values. + * Unlike `mapValues`, this method generates a new + * collection immediately. + */ + def mapValuesNow[V1](f: V => V1): LongMap[V1] = { + val lm = new LongMap[V1](LongMap.exceptionDefault, 1, false) + val kz = java.util.Arrays.copyOf(_keys, _keys.length) + val vz = new Array[AnyRef](_values.length) + var i,j = 0 + while (i < _keys.length & j < _size) { + val k = _keys(i) + if (k != -k) { + j += 1 + vz(i) = f(_values(i).asInstanceOf[V]).asInstanceOf[AnyRef] + } + i += 1 + } + val zv = if ((extraKeys & 1) == 1) f(zeroValue.asInstanceOf[V]).asInstanceOf[AnyRef] else null + val mv = if ((extraKeys & 2) == 2) f(minValue.asInstanceOf[V]).asInstanceOf[AnyRef] else null + lm.initializeTo(mask, extraKeys, zv, mv, _size, _vacant, kz, vz) + lm + } + + /** Applies a transformation function to all values stored in this map. + * Note: the default, if any, is not transformed. + */ + def transformValues(f: V => V): this.type = { + var i,j = 0 + while (i < _keys.length & j < _size) { + val k = _keys(i) + if (k != -k) { + j += 1 + _values(i) = f(_values(i).asInstanceOf[V]).asInstanceOf[AnyRef] + } + i += 1 + } + if ((extraKeys & 1) == 1) zeroValue = f(zeroValue.asInstanceOf[V]).asInstanceOf[AnyRef] + if ((extraKeys & 2) == 2) minValue = f(minValue.asInstanceOf[V]).asInstanceOf[AnyRef] + this + } + + /* + override def toString = { + val sb = new StringBuilder("LongMap(") + var n = 0 + foreach{ case (k,v) => + if (n > 0) sb ++= ", " + sb ++= k.toString + sb ++= " -> " + sb ++= v.toString + n += 1 + } + sb += ')' + sb.result + } + */ +} + +object LongMap { + private final val IndexMask = 0x3FFFFFFF + private final val MissingBit = 0x80000000 + private final val VacantBit = 0x40000000 + private final val MissVacant = 0xC0000000 + + private val exceptionDefault: Long => Nothing = (k: Long) => throw new NoSuchElementException(k.toString) + + implicit def canBuildFrom[V, U]: CanBuildFrom[LongMap[V], (Long, U), LongMap[U]] = + new CanBuildFrom[LongMap[V], (Long, U), LongMap[U]] { + def apply(from: LongMap[V]): LongMapBuilder[U] = apply() + def apply(): LongMapBuilder[U] = new LongMapBuilder[U] + } + + final class LongMapBuilder[V] extends Builder[(Long, V), LongMap[V]] { + private[collection] var elems: LongMap[V] = new LongMap[V] + def +=(entry: (Long, V)): this.type = { + elems += entry + this + } + def clear() { elems = new LongMap[V] } + def result(): LongMap[V] = elems + } + + /** Creates a new `LongMap` with zero or more key/value pairs. */ + def apply[V](elems: (Long, V)*): LongMap[V] = { + val sz = if (elems.hasDefiniteSize) elems.size else 4 + val lm = new LongMap[V](sz * 2) + elems.foreach{ case (k,v) => lm(k) = v } + if (lm.size < (sz>>3)) lm.repack() + lm + } + + /** Creates a new empty `LongMap`. */ + def empty[V]: LongMap[V] = new LongMap[V] + + /** Creates a new empty `LongMap` with the supplied default */ + def withDefault[V](default: Long => V): LongMap[V] = new LongMap[V](default) + + /** Creates a new `LongMap` from arrays of keys and values. + * Equivalent to but more efficient than `LongMap((keys zip values): _*)`. + */ + def fromZip[V](keys: Array[Long], values: Array[V]): LongMap[V] = { + val sz = math.min(keys.length, values.length) + val lm = new LongMap[V](sz * 2) + var i = 0 + while (i < sz) { lm(keys(i)) = values(i); i += 1 } + if (lm.size < (sz>>3)) lm.repack() + lm + } + + /** Creates a new `LongMap` from keys and values. + * Equivalent to but more efficient than `LongMap((keys zip values): _*)`. + */ + def fromZip[V](keys: Iterable[Long], values: Iterable[V]): LongMap[V] = { + val sz = math.min(keys.size, values.size) + val lm = new LongMap[V](sz * 2) + val ki = keys.iterator + val vi = values.iterator + while (ki.hasNext && vi.hasNext) lm(ki.next) = vi.next + if (lm.size < (sz >> 3)) lm.repack() + lm + } +} diff --git a/test/files/run/mutable-anyrefmap.scala b/test/files/run/mutable-anyrefmap.scala new file mode 100644 index 0000000000..ff615d0daf --- /dev/null +++ b/test/files/run/mutable-anyrefmap.scala @@ -0,0 +1,91 @@ +object Test extends App { + + import scala.collection.mutable.HashMap; + import scala.collection.mutable.AnyRefMap; + + val keys = Array( + null, "perch", "herring", "salmon", "pike", "cod", "" + ) + + val rn = new scala.util.Random(42L) + var arm = AnyRefMap.empty[String, Int] + val hm = HashMap.empty[String, Int] + + def checkConsistent = hm.forall{ case (k,v) => arm.get(k).exists(_ == v) } + + assert { + (0 to 10000).forall{ i => + val k = keys(rn.nextInt(keys.length)) + if (rn.nextInt(100) < 2) arm = arm.clone() + if (rn.nextInt(100) < 5) arm.repack() + if (rn.nextBoolean) { + hm += ((k, i)) + rn.nextInt(6) match { + case 0 => arm += ((k, i)) + case 1 => arm += (k, i) + case 2 => arm(k) = i + case 3 => arm.put(k,i) + case 4 => arm ++= List((k,i)) + case _ => if (!arm.contains(k)) arm.getOrElseUpdate(k,i) + else arm += (k,i) + } + } + else { + hm -= k + rn.nextInt(2) match { + case 0 => arm -= k + case _ => arm --= List(k) + } + } + checkConsistent + } + } + + assert { + val mapped = + arm.map{ case (k,v) => (if (k==null) "" else k+k) -> v.toString } + mapped.getClass == arm.getClass + } + + assert { + val arm2 = new AnyRefMap[java.lang.Integer,Unit](2000000) + for (i <- 0 until 1000000) arm2(java.lang.Integer.valueOf(i)) = () + + arm2.size == 1000000 && + (0 to 1100000 by 100000).map(java.lang.Integer.valueOf).forall(i => (arm2 contains i) == i < 1000000) + } + + arm = AnyRefMap("heron" -> 22, "dove" -> 5, "budgie" -> 0) + + assert{ + var s = "" + arm.foreachKey(s += _) + + s.length == "herondovebudgie".length && + s.contains("heron") && + s.contains("dove") && + s.contains("budgie") + } + + assert{ var s = 0L; arm.foreachValue(s += _); s == 27L } + + assert { + val m2 = arm.mapValuesNow(_+2) + arm.transformValues(_+2) + m2 == arm && !(m2 eq arm) && (for ((_,v) <- arm) yield v).sum == 33L + } + + assert { + val arm2 = new AnyRefMap[String, String](x => if (x==null) "null" else x) + arm2 += ("cod" -> "fish", "Rarity" -> "unicorn") + val hm2 = (new HashMap[String,String]) ++= arm2 + + List(null, "cod", "sparrow", "Rarity").forall(i => + arm2.get(i) == hm2.get(i) && + arm2.getOrElse(i, "") == hm2.getOrElse(i, "") && + arm2(i) == hm2.get(i).getOrElse(if (i==null) "null" else i.toString) && + arm2.getOrNull(i) == hm2.get(i).orNull + ) + } +} + diff --git a/test/files/run/mutable-longmap.scala b/test/files/run/mutable-longmap.scala new file mode 100644 index 0000000000..07fd80f6f0 --- /dev/null +++ b/test/files/run/mutable-longmap.scala @@ -0,0 +1,79 @@ +object Test extends App { + + import scala.collection.mutable.HashMap; + import scala.collection.mutable.LongMap; + + val keys = Array( + Long.MinValue, Int.MinValue - 1L, Int.MinValue, -9127, -1, + 0, 1, 9127, Int.MaxValue, Long.MaxValue + ) + + val rn = new scala.util.Random(42L) + var lm = LongMap.empty[Long] + val hm = HashMap.empty[Long,Long] + + def checkConsistent = hm.forall{ case (k,v) => lm.get(k).exists(_ == v) } + + assert { + (0 to 10000).forall{ i => + val k = keys(rn.nextInt(keys.length)) + if (rn.nextInt(100) < 2) lm = lm.clone() + if (rn.nextInt(100) < 5) lm.repack() + if (rn.nextBoolean) { + hm += ((k, i)) + rn.nextInt(6) match { + case 0 => lm += ((k, i)) + case 1 => lm += (k, i) + case 2 => lm(k) = i + case 3 => lm.put(k,i) + case 4 => lm ++= List((k,i)) + case _ => if (!lm.contains(k)) lm.getOrElseUpdate(k,i) + else lm += (k,i) + } + } + else { + hm -= k + rn.nextInt(2) match { + case 0 => lm -= k + case _ => lm --= List(k) + } + } + checkConsistent + } + } + + assert { + lm.map{ case (k,v) => -k*k -> v.toString }.getClass == lm.getClass + } + + assert { + val lm2 = new LongMap[Unit](2000000) + for (i <- 0 until 1000000) lm2(i) = () + + lm2.size == 1000000 && + (0 to 1100000 by 100000).forall(i => (lm2 contains i) == i < 1000000) + } + + lm = LongMap(8L -> 22L, -5L -> 5L, Long.MinValue -> 0L) + + assert{ var s = 0L; lm.foreachKey(s += _); s == Long.MinValue + 3 } + assert{ var s = 0L; lm.foreachValue(s += _); s == 27L } + assert { + val m2 = lm.mapValuesNow(_+2) + lm.transformValues(_+2) + m2 == lm && !(m2 eq lm) && (for ((_,v) <- lm) yield v).sum == 33L + } + + assert { + val lm2 = new LongMap[String](_.toString) + lm2 += (5L -> "fish", 0L -> "unicorn") + val hm2 = (new HashMap[Long,String]) ++= lm2 + + List(Long.MinValue, 0L, 1L, 5L).forall(i => + lm2.get(i) == hm2.get(i) && + lm2.getOrElse(i, "") == hm2.getOrElse(i, "") && + lm2(i) == hm2.get(i).getOrElse(i.toString) && + lm2.getOrNull(i) == hm2.get(i).orNull + ) + } +} |