diff options
Diffstat (limited to 'src/library/scala/collection/mutable/AnyRefMap.scala')
| -rw-r--r-- | src/library/scala/collection/mutable/AnyRefMap.scala | 122 |
1 files changed, 61 insertions, 61 deletions
diff --git a/src/library/scala/collection/mutable/AnyRefMap.scala b/src/library/scala/collection/mutable/AnyRefMap.scala index 46991ac101..af7600ad3d 100644 --- a/src/library/scala/collection/mutable/AnyRefMap.scala +++ b/src/library/scala/collection/mutable/AnyRefMap.scala @@ -5,23 +5,23 @@ 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`, + * + * 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 intended 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. @@ -36,50 +36,50 @@ extends AbstractMap[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 = + 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 = + + private def imbalanced: Boolean = (_size + _vacant) > 0.5*mask || _vacant > _size - + private def hashOf(key: K): Int = { if (key eq null) 0x41081989 else { @@ -90,7 +90,7 @@ extends AbstractMap[K, V] if (j==0) 0x41081989 else j & 0x7FFFFFFF } } - + private def seekEntry(h: Int, k: AnyRef): Int = { var e = h & mask var x = 0 @@ -102,7 +102,7 @@ extends AbstractMap[K, V] } e | MissingBit } - + private def seekEntryOrOpen(h: Int, k: AnyRef): Int = { var e = h & mask var x = 0 @@ -116,19 +116,19 @@ extends AbstractMap[K, V] } 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) var i = seekEntryOrOpen(h, key) @@ -156,10 +156,10 @@ extends AbstractMap[K, V] } 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. @@ -168,22 +168,22 @@ extends AbstractMap[K, V] val i = seekEntry(hashOf(key), key) (if (i < 0) null else _values(i)).asInstanceOf[V] } - - /** Retrieves the value associated with a key. + + /** 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 + * 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 @@ -207,9 +207,9 @@ extends AbstractMap[K, V] 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 @@ -222,7 +222,7 @@ extends AbstractMap[K, V] 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 @@ -245,9 +245,9 @@ extends AbstractMap[K, V] 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 = { @@ -269,12 +269,12 @@ extends AbstractMap[K, V] _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) { @@ -286,14 +286,14 @@ extends AbstractMap[K, V] } 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 - + def hasNext: Boolean = index<hz.length && { var h = hz(index) while (h+h == 0) { @@ -303,7 +303,7 @@ extends AbstractMap[K, V] } true } - + def next: (K, V) = { if (hasNext) { val ans = (kz(index).asInstanceOf[K], vz(index).asInstanceOf[V]) @@ -313,8 +313,8 @@ extends AbstractMap[K, V] else throw new NoSuchElementException("next") } } - - override def foreach[A](f: ((K,V)) => A) { + + override def foreach[U](f: ((K,V)) => U) { var i = 0 var e = _size while (e > 0) { @@ -327,7 +327,7 @@ extends AbstractMap[K, V] 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) @@ -336,25 +336,25 @@ extends AbstractMap[K, V] arm.initializeTo(mask, _size, _vacant, hz, kz, vz) arm } - + override def +[V1 >: V](kv: (K, V1)): AnyRefMap[K, V1] = { val arm = clone().asInstanceOf[AnyRefMap[K, V1]] arm += kv arm } - + override def ++[V1 >: V](xs: GenTraversableOnce[(K, V1)]): AnyRefMap[K, V1] = { val arm = clone().asInstanceOf[AnyRefMap[K, V1]] xs.foreach(kv => arm += kv) arm } - + override def updated[V1 >: V](key: K, value: V1): AnyRefMap[K, V1] = { val arm = clone().asInstanceOf[AnyRefMap[K, V1]] arm += (key, value) arm } - + private[this] def foreachElement[A,B](elems: Array[AnyRef], f: A => B) { var i,j = 0 while (i < _hashes.length & j < _size) { @@ -366,13 +366,13 @@ extends AbstractMap[K, V] 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. @@ -394,8 +394,8 @@ extends AbstractMap[K, V] arm.initializeTo(mask, _size, _vacant, hz, kz, vz) arm } - - /** Applies a transformation function to all values stored in this map. + + /** 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 = { @@ -418,15 +418,15 @@ object AnyRefMap { 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 = { @@ -445,14 +445,14 @@ object AnyRefMap { 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. + + /** 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] = { @@ -463,8 +463,8 @@ object AnyRefMap { if (arm.size < (sz>>3)) arm.repack() arm } - - /** Creates a new `AnyRefMap` from keys and values. + + /** 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] = { |