summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/library/scala/collection/mutable/LongMap.scala558
-rw-r--r--test/files/run/mutable-longmap.scala79
2 files changed, 637 insertions, 0 deletions
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-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
+ )
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-04 13:09:08 +0000