From d38ad5e9877011e635b6c2cb6c4f3fcb31dfb7d2 Mon Sep 17 00:00:00 2001 From: Aleksandar Prokopec Date: Wed, 30 May 2012 14:08:41 +0200 Subject: Add Hashing and Equality typeclasses. Modify TrieMap to use hashing and equality. Modify serialization in TrieMap appropriately. --- src/library/scala/Equality.scala | 37 +++++++++++ .../scala/collection/concurrent/TrieMap.scala | 72 ++++++++++++++-------- src/library/scala/math/Hashing.scala | 40 ++++++++++++ test/files/run/triemap-hash.scala | 46 ++++++++++++++ 4 files changed, 168 insertions(+), 27 deletions(-) create mode 100644 src/library/scala/Equality.scala create mode 100644 src/library/scala/math/Hashing.scala create mode 100644 test/files/run/triemap-hash.scala diff --git a/src/library/scala/Equality.scala b/src/library/scala/Equality.scala new file mode 100644 index 0000000000..92835fb157 --- /dev/null +++ b/src/library/scala/Equality.scala @@ -0,0 +1,37 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +package scala + +/** `Equality` is a trait whose instances each represent a strategy for determining + * equality of instances of a type. + * + * `Equality`'s companion object defines a default equality for all + * objects - it calls their `==` method. + * + * @since 2.10 + */ +@annotation.implicitNotFound(msg = "No implicit Equality defined for ${T}.") +trait Equality[T] extends Serializable { + + def areEqual(x: T, y: T): Boolean + +} + + +object Equality { + + implicit def defaultEquality[T] = new Equality[T] { + def areEqual(x: T, y: T) = x == y + } + + def apply[T](f: (T, T) => Boolean) = new Equality[T] { + def areEqual(x: T, y: T) = f(x, y) + } + +} diff --git a/src/library/scala/collection/concurrent/TrieMap.scala b/src/library/scala/collection/concurrent/TrieMap.scala index 2a908aebb1..b38cb4e376 100644 --- a/src/library/scala/collection/concurrent/TrieMap.scala +++ b/src/library/scala/collection/concurrent/TrieMap.scala @@ -14,6 +14,7 @@ package concurrent import java.util.concurrent.atomic._ import collection.immutable.{ ListMap => ImmutableListMap } import collection.parallel.mutable.ParTrieMap +import math.Hashing import generic._ import annotation.tailrec import annotation.switch @@ -80,6 +81,9 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends } else false } + @inline + private def equal(k1: K, k2: K, ct: TrieMap[K, V]) = ct.equality.areEqual(k1, k2) + @inline private def inode(cn: MainNode[K, V]) = { val nin = new INode[K, V](gen) nin.WRITE(cn) @@ -117,7 +121,7 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends else false } case sn: SNode[K, V] => - if (sn.hc == hc && sn.k == k) GCAS(cn, cn.updatedAt(pos, new SNode(k, v, hc), gen), ct) + if (sn.hc == hc && equal(sn.k, k, ct)) GCAS(cn, cn.updatedAt(pos, new SNode(k, v, hc), gen), ct) else { val rn = if (cn.gen eq gen) cn else cn.renewed(gen, ct) val nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode(k, v, hc), hc, lev + 5, gen)), gen) @@ -164,7 +168,7 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends } case sn: SNode[K, V] => cond match { case null => - if (sn.hc == hc && sn.k == k) { + if (sn.hc == hc && equal(sn.k, k, ct)) { if (GCAS(cn, cn.updatedAt(pos, new SNode(k, v, hc), gen), ct)) Some(sn.v) else null } else { val rn = if (cn.gen eq gen) cn else cn.renewed(gen, ct) @@ -173,7 +177,7 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends else null } case INode.KEY_ABSENT => - if (sn.hc == hc && sn.k == k) Some(sn.v) + if (sn.hc == hc && equal(sn.k, k, ct)) Some(sn.v) else { val rn = if (cn.gen eq gen) cn else cn.renewed(gen, ct) val nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode(k, v, hc), hc, lev + 5, gen)), gen) @@ -181,11 +185,11 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends else null } case INode.KEY_PRESENT => - if (sn.hc == hc && sn.k == k) { + if (sn.hc == hc && equal(sn.k, k, ct)) { if (GCAS(cn, cn.updatedAt(pos, new SNode(k, v, hc), gen), ct)) Some(sn.v) else null } else None case otherv: V => - if (sn.hc == hc && sn.k == k && sn.v == otherv) { + if (sn.hc == hc && equal(sn.k, k, ct) && sn.v == otherv) { if (GCAS(cn, cn.updatedAt(pos, new SNode(k, v, hc), gen), ct)) Some(sn.v) else null } else None } @@ -253,7 +257,7 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends else return RESTART // used to be throw RestartException } case sn: SNode[K, V] => // 2) singleton node - if (sn.hc == hc && sn.k == k) sn.v.asInstanceOf[AnyRef] + if (sn.hc == hc && equal(sn.k, k, ct)) sn.v.asInstanceOf[AnyRef] else null } } @@ -296,7 +300,7 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends else null } case sn: SNode[K, V] => - if (sn.hc == hc && sn.k == k && (v == null || sn.v == v)) { + if (sn.hc == hc && equal(sn.k, k, ct) && (v == null || sn.v == v)) { val ncn = cn.removedAt(pos, flag, gen).toContracted(lev) if (GCAS(cn, ncn, ct)) Some(sn.v) else null } else None @@ -341,11 +345,11 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends case ln: LNode[K, V] => if (v == null) { val optv = ln.get(k) - val nn = ln.removed(k) + val nn = ln.removed(k, ct) if (GCAS(ln, nn, ct)) optv else null } else ln.get(k) match { case optv @ Some(v0) if v0 == v => - val nn = ln.removed(k) + val nn = ln.removed(k, ct) if (GCAS(ln, nn, ct)) optv else null case _ => None } @@ -433,12 +437,12 @@ extends MainNode[K, V] { def this(k: K, v: V) = this(ImmutableListMap(k -> v)) def this(k1: K, v1: V, k2: K, v2: V) = this(ImmutableListMap(k1 -> v1, k2 -> v2)) def inserted(k: K, v: V) = new LNode(listmap + ((k, v))) - def removed(k: K): MainNode[K, V] = { + def removed(k: K, ct: TrieMap[K, V]): MainNode[K, V] = { val updmap = listmap - k if (updmap.size > 1) new LNode(updmap) else { val (k, v) = updmap.iterator.next - new TNode(k, v, TrieMap.computeHash(k)) // create it tombed so that it gets compressed on subsequent accesses + new TNode(k, v, ct.computeHash(k)) // create it tombed so that it gets compressed on subsequent accesses } } def get(k: K) = listmap.get(k) @@ -627,25 +631,34 @@ private[concurrent] case class RDCSS_Descriptor[K, V](old: INode[K, V], expected * @since 2.10 */ @SerialVersionUID(0L - 6402774413839597105L) -final class TrieMap[K, V] private (r: AnyRef, rtupd: AtomicReferenceFieldUpdater[TrieMap[K, V], AnyRef]) +final class TrieMap[K, V] private (r: AnyRef, rtupd: AtomicReferenceFieldUpdater[TrieMap[K, V], AnyRef], hashf: Hashing[K], ef: Equality[K]) extends scala.collection.concurrent.Map[K, V] with scala.collection.mutable.MapLike[K, V, TrieMap[K, V]] with CustomParallelizable[(K, V), ParTrieMap[K, V]] with Serializable { - import TrieMap.computeHash - + private var hashingobj = hashf + private var equalityobj = ef private var rootupdater = rtupd + def hashing = hashingobj + def equality = equalityobj @volatile var root = r - - def this() = this( + + def this(hashf: Hashing[K], ef: Equality[K]) = this( INode.newRootNode, - AtomicReferenceFieldUpdater.newUpdater(classOf[TrieMap[K, V]], classOf[AnyRef], "root") + AtomicReferenceFieldUpdater.newUpdater(classOf[TrieMap[K, V]], classOf[AnyRef], "root"), + hashf, + ef ) - + + def this() = this(Hashing.defaultHashing, Equality.defaultEquality) + /* internal methods */ private def writeObject(out: java.io.ObjectOutputStream) { + out.writeObject(hashf) + out.writeObject(ef) + val it = iterator while (it.hasNext) { val (k, v) = it.next() @@ -659,6 +672,9 @@ extends scala.collection.concurrent.Map[K, V] root = INode.newRootNode rootupdater = AtomicReferenceFieldUpdater.newUpdater(classOf[TrieMap[K, V]], classOf[AnyRef], "root") + hashingobj = in.readObject().asInstanceOf[Hashing[K]] + equalityobj = in.readObject().asInstanceOf[Equality[K]] + var obj: AnyRef = null do { obj = in.readObject() @@ -780,7 +796,7 @@ extends scala.collection.concurrent.Map[K, V] @tailrec final def snapshot(): TrieMap[K, V] = { val r = RDCSS_READ_ROOT() val expmain = r.gcasRead(this) - if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen, this))) new TrieMap(r.copyToGen(new Gen, this), rootupdater) + if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen, this))) new TrieMap(r.copyToGen(new Gen, this), rootupdater, hashing, equality) else snapshot() } @@ -799,7 +815,7 @@ extends scala.collection.concurrent.Map[K, V] @tailrec final def readOnlySnapshot(): collection.Map[K, V] = { val r = RDCSS_READ_ROOT() val expmain = r.gcasRead(this) - if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen, this))) new TrieMap(r, null) + if (RDCSS_ROOT(r, expmain, r.copyToGen(new Gen, this))) new TrieMap(r, null, hashing, equality) else readOnlySnapshot() } @@ -807,7 +823,16 @@ extends scala.collection.concurrent.Map[K, V] val r = RDCSS_READ_ROOT() if (!RDCSS_ROOT(r, r.gcasRead(this), INode.newRootNode[K, V])) clear() } + + @inline private def mangle(hc: Int): Int = { + var hcode = hc * 0x9e3775cd + hcode = java.lang.Integer.reverseBytes(hcode) + hcode * 0x9e3775cd + } + @inline + def computeHash(k: K) = mangle(hashingobj.hashCode(k)) + final def lookup(k: K): V = { val hc = computeHash(k) lookuphc(k, hc).asInstanceOf[V] @@ -895,13 +920,6 @@ object TrieMap extends MutableMapFactory[TrieMap] { def empty[K, V]: TrieMap[K, V] = new TrieMap[K, V] - @inline final def computeHash[K](k: K): Int = { - var hcode = k.hashCode - hcode = hcode * 0x9e3775cd - hcode = java.lang.Integer.reverseBytes(hcode) - hcode * 0x9e3775cd - } - } diff --git a/src/library/scala/math/Hashing.scala b/src/library/scala/math/Hashing.scala new file mode 100644 index 0000000000..6902b3ab06 --- /dev/null +++ b/src/library/scala/math/Hashing.scala @@ -0,0 +1,40 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +package scala.math + +/** `Hashing` is a trait whose instances each represent a strategy for hashing + * instances of a type. + * + * `Hashing`'s companion object defines a default hashing strategy for all + * objects - it calls their `##` method. + * + * Note: when using a custom `Hashing`, make sure to use it with the `Equality` + * such that if any two objects are equal, then their hash codes must be equal. + * + * @since 2.10 + */ +@annotation.implicitNotFound(msg = "No implicit Hashing defined for ${T}.") +trait Hashing[T] extends Serializable { + + def hashCode(x: T): Int + +} + + +object Hashing { + + implicit def defaultHashing[T] = new Hashing[T] { + def hashCode(x: T) = x.## + } + + def apply[T](f: T => Int) = new Hashing[T] { + def hashCode(x: T) = f(x) + } + +} diff --git a/test/files/run/triemap-hash.scala b/test/files/run/triemap-hash.scala new file mode 100644 index 0000000000..23cdd26bed --- /dev/null +++ b/test/files/run/triemap-hash.scala @@ -0,0 +1,46 @@ + + + +import math.Hashing + + + +object Test { + + def main(args: Array[String]) { + hashing() + equality() + } + + def hashing() { + import collection._ + + val tm = new concurrent.TrieMap[String, String](Hashing(x => x.length + x(0).toInt), Equality.defaultEquality) + tm.put("a", "b") + tm.put("c", "d") + + assert(tm("a") == "b") + assert(tm("c") == "d") + + for (i <- 0 until 1000) tm(i.toString) = i.toString + for (i <- 0 until 1000) assert(tm(i.toString) == i.toString) + } + + def equality() { + import collection._ + + val tm = new concurrent.TrieMap[String, String](Hashing(x => x(0).toInt), Equality(_(0) == _(0))) + tm.put("a", "b") + tm.put("a1", "d") + tm.put("b", "c") + + assert(tm("a") == "d", tm) + assert(tm("b") == "c", tm) + + for (i <- 0 until 1000) tm(i.toString) = i.toString + assert(tm.size == 12, tm) + assert(tm("0") == "0", tm) + for (i <- 1 to 9) assert(tm(i.toString) == i.toString + "99", tm) + } + +} -- cgit v1.2.3 From bb30e08d71c888f923e814e7ccbeb03427fd8808 Mon Sep 17 00:00:00 2001 From: Aleksandar Prokopec Date: Fri, 1 Jun 2012 18:08:48 +0200 Subject: Remove Equality in favour of Equiv. Make Equiv serializable. --- src/library/scala/Equality.scala | 37 ---------------------- .../scala/collection/concurrent/TrieMap.scala | 10 +++--- src/library/scala/math/Equiv.scala | 2 +- src/library/scala/math/Hashing.scala | 6 ++-- test/files/run/triemap-hash.scala | 4 +-- 5 files changed, 11 insertions(+), 48 deletions(-) delete mode 100644 src/library/scala/Equality.scala diff --git a/src/library/scala/Equality.scala b/src/library/scala/Equality.scala deleted file mode 100644 index 92835fb157..0000000000 --- a/src/library/scala/Equality.scala +++ /dev/null @@ -1,37 +0,0 @@ -/* __ *\ -** ________ ___ / / ___ Scala API ** -** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL ** -** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** -** /____/\___/_/ |_/____/_/ | | ** -** |/ ** -\* */ - -package scala - -/** `Equality` is a trait whose instances each represent a strategy for determining - * equality of instances of a type. - * - * `Equality`'s companion object defines a default equality for all - * objects - it calls their `==` method. - * - * @since 2.10 - */ -@annotation.implicitNotFound(msg = "No implicit Equality defined for ${T}.") -trait Equality[T] extends Serializable { - - def areEqual(x: T, y: T): Boolean - -} - - -object Equality { - - implicit def defaultEquality[T] = new Equality[T] { - def areEqual(x: T, y: T) = x == y - } - - def apply[T](f: (T, T) => Boolean) = new Equality[T] { - def areEqual(x: T, y: T) = f(x, y) - } - -} diff --git a/src/library/scala/collection/concurrent/TrieMap.scala b/src/library/scala/collection/concurrent/TrieMap.scala index b38cb4e376..7c786619fb 100644 --- a/src/library/scala/collection/concurrent/TrieMap.scala +++ b/src/library/scala/collection/concurrent/TrieMap.scala @@ -82,7 +82,7 @@ private[collection] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends } @inline - private def equal(k1: K, k2: K, ct: TrieMap[K, V]) = ct.equality.areEqual(k1, k2) + private def equal(k1: K, k2: K, ct: TrieMap[K, V]) = ct.equality.equiv(k1, k2) @inline private def inode(cn: MainNode[K, V]) = { val nin = new INode[K, V](gen) @@ -631,7 +631,7 @@ private[concurrent] case class RDCSS_Descriptor[K, V](old: INode[K, V], expected * @since 2.10 */ @SerialVersionUID(0L - 6402774413839597105L) -final class TrieMap[K, V] private (r: AnyRef, rtupd: AtomicReferenceFieldUpdater[TrieMap[K, V], AnyRef], hashf: Hashing[K], ef: Equality[K]) +final class TrieMap[K, V] private (r: AnyRef, rtupd: AtomicReferenceFieldUpdater[TrieMap[K, V], AnyRef], hashf: Hashing[K], ef: Equiv[K]) extends scala.collection.concurrent.Map[K, V] with scala.collection.mutable.MapLike[K, V, TrieMap[K, V]] with CustomParallelizable[(K, V), ParTrieMap[K, V]] @@ -644,14 +644,14 @@ extends scala.collection.concurrent.Map[K, V] def equality = equalityobj @volatile var root = r - def this(hashf: Hashing[K], ef: Equality[K]) = this( + def this(hashf: Hashing[K], ef: Equiv[K]) = this( INode.newRootNode, AtomicReferenceFieldUpdater.newUpdater(classOf[TrieMap[K, V]], classOf[AnyRef], "root"), hashf, ef ) - def this() = this(Hashing.defaultHashing, Equality.defaultEquality) + def this() = this(Hashing.default, Equiv.universal) /* internal methods */ @@ -673,7 +673,7 @@ extends scala.collection.concurrent.Map[K, V] rootupdater = AtomicReferenceFieldUpdater.newUpdater(classOf[TrieMap[K, V]], classOf[AnyRef], "root") hashingobj = in.readObject().asInstanceOf[Hashing[K]] - equalityobj = in.readObject().asInstanceOf[Equality[K]] + equalityobj = in.readObject().asInstanceOf[Equiv[K]] var obj: AnyRef = null do { diff --git a/src/library/scala/math/Equiv.scala b/src/library/scala/math/Equiv.scala index bd8414a18d..a8ba0aa40c 100644 --- a/src/library/scala/math/Equiv.scala +++ b/src/library/scala/math/Equiv.scala @@ -29,7 +29,7 @@ import java.util.Comparator * @since 2.7 */ -trait Equiv[T] extends Any { +trait Equiv[T] extends Any with Serializable { /** Returns `true` iff `x` is equivalent to `y`. */ def equiv(x: T, y: T): Boolean diff --git a/src/library/scala/math/Hashing.scala b/src/library/scala/math/Hashing.scala index 6902b3ab06..0d0fecf442 100644 --- a/src/library/scala/math/Hashing.scala +++ b/src/library/scala/math/Hashing.scala @@ -14,7 +14,7 @@ package scala.math * `Hashing`'s companion object defines a default hashing strategy for all * objects - it calls their `##` method. * - * Note: when using a custom `Hashing`, make sure to use it with the `Equality` + * Note: when using a custom `Hashing`, make sure to use it with the `Equiv` * such that if any two objects are equal, then their hash codes must be equal. * * @since 2.10 @@ -29,11 +29,11 @@ trait Hashing[T] extends Serializable { object Hashing { - implicit def defaultHashing[T] = new Hashing[T] { + implicit def default[T] = new Hashing[T] { def hashCode(x: T) = x.## } - def apply[T](f: T => Int) = new Hashing[T] { + def fromFunction[T](f: T => Int) = new Hashing[T] { def hashCode(x: T) = f(x) } diff --git a/test/files/run/triemap-hash.scala b/test/files/run/triemap-hash.scala index 23cdd26bed..8f2347a96f 100644 --- a/test/files/run/triemap-hash.scala +++ b/test/files/run/triemap-hash.scala @@ -15,7 +15,7 @@ object Test { def hashing() { import collection._ - val tm = new concurrent.TrieMap[String, String](Hashing(x => x.length + x(0).toInt), Equality.defaultEquality) + val tm = new concurrent.TrieMap[String, String](Hashing.fromFunction(x => x.length + x(0).toInt), Equiv.universal) tm.put("a", "b") tm.put("c", "d") @@ -29,7 +29,7 @@ object Test { def equality() { import collection._ - val tm = new concurrent.TrieMap[String, String](Hashing(x => x(0).toInt), Equality(_(0) == _(0))) + val tm = new concurrent.TrieMap[String, String](Hashing.fromFunction(x => x(0).toInt), Equiv.fromFunction(_(0) == _(0))) tm.put("a", "b") tm.put("a1", "d") tm.put("b", "c") -- cgit v1.2.3 From ddaf6c5235acbf808ffd5ded710f513f4df3882e Mon Sep 17 00:00:00 2001 From: Aleksandar Prokopec Date: Fri, 1 Jun 2012 21:06:36 +0200 Subject: Fix `Hashing`. Move `Hashing` to `scala.util.hashing`. Adde `Hashing.Default` to `Hashing` companion object. Change `TrieMap` to autoswitch from `Hashing.Default` to `TrieMap.MangledHashing`. --- .../scala/collection/concurrent/TrieMap.scala | 22 ++++++------ src/library/scala/math/Hashing.scala | 40 --------------------- src/library/scala/util/MurmurHash3.scala | 8 +++++ src/library/scala/util/hashing/Hashing.scala | 42 ++++++++++++++++++++++ test/files/run/triemap-hash.scala | 2 +- 5 files changed, 63 insertions(+), 51 deletions(-) delete mode 100644 src/library/scala/math/Hashing.scala create mode 100644 src/library/scala/util/hashing/Hashing.scala diff --git a/src/library/scala/collection/concurrent/TrieMap.scala b/src/library/scala/collection/concurrent/TrieMap.scala index 7c786619fb..f944d20bdb 100644 --- a/src/library/scala/collection/concurrent/TrieMap.scala +++ b/src/library/scala/collection/concurrent/TrieMap.scala @@ -14,7 +14,7 @@ package concurrent import java.util.concurrent.atomic._ import collection.immutable.{ ListMap => ImmutableListMap } import collection.parallel.mutable.ParTrieMap -import math.Hashing +import util.hashing.Hashing import generic._ import annotation.tailrec import annotation.switch @@ -637,7 +637,7 @@ extends scala.collection.concurrent.Map[K, V] with CustomParallelizable[(K, V), ParTrieMap[K, V]] with Serializable { - private var hashingobj = hashf + private var hashingobj = if (hashf.isInstanceOf[Hashing.Default[_]]) new TrieMap.MangledHashing[K] else hashf private var equalityobj = ef private var rootupdater = rtupd def hashing = hashingobj @@ -824,14 +824,8 @@ extends scala.collection.concurrent.Map[K, V] if (!RDCSS_ROOT(r, r.gcasRead(this), INode.newRootNode[K, V])) clear() } - @inline private def mangle(hc: Int): Int = { - var hcode = hc * 0x9e3775cd - hcode = java.lang.Integer.reverseBytes(hcode) - hcode * 0x9e3775cd - } - @inline - def computeHash(k: K) = mangle(hashingobj.hashCode(k)) + def computeHash(k: K) = hashingobj.hashCode(k) final def lookup(k: K): V = { val hc = computeHash(k) @@ -919,7 +913,15 @@ object TrieMap extends MutableMapFactory[TrieMap] { implicit def canBuildFrom[K, V]: CanBuildFrom[Coll, (K, V), TrieMap[K, V]] = new MapCanBuildFrom[K, V] def empty[K, V]: TrieMap[K, V] = new TrieMap[K, V] - + + class MangledHashing[K] extends Hashing[K] { + def hashCode(k: K) = { + var hcode = k.## * 0x9e3775cd + hcode = java.lang.Integer.reverseBytes(hcode) + hcode * 0x9e3775cd + } + } + } diff --git a/src/library/scala/math/Hashing.scala b/src/library/scala/math/Hashing.scala deleted file mode 100644 index 0d0fecf442..0000000000 --- a/src/library/scala/math/Hashing.scala +++ /dev/null @@ -1,40 +0,0 @@ -/* __ *\ -** ________ ___ / / ___ Scala API ** -** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL ** -** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** -** /____/\___/_/ |_/____/_/ | | ** -** |/ ** -\* */ - -package scala.math - -/** `Hashing` is a trait whose instances each represent a strategy for hashing - * instances of a type. - * - * `Hashing`'s companion object defines a default hashing strategy for all - * objects - it calls their `##` method. - * - * Note: when using a custom `Hashing`, make sure to use it with the `Equiv` - * such that if any two objects are equal, then their hash codes must be equal. - * - * @since 2.10 - */ -@annotation.implicitNotFound(msg = "No implicit Hashing defined for ${T}.") -trait Hashing[T] extends Serializable { - - def hashCode(x: T): Int - -} - - -object Hashing { - - implicit def default[T] = new Hashing[T] { - def hashCode(x: T) = x.## - } - - def fromFunction[T](f: T => Int) = new Hashing[T] { - def hashCode(x: T) = f(x) - } - -} diff --git a/src/library/scala/util/MurmurHash3.scala b/src/library/scala/util/MurmurHash3.scala index fbb67116dd..9a7f64b4ee 100644 --- a/src/library/scala/util/MurmurHash3.scala +++ b/src/library/scala/util/MurmurHash3.scala @@ -1,3 +1,11 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2012, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + package scala.util import java.lang.Integer.{ rotateLeft => rotl } diff --git a/src/library/scala/util/hashing/Hashing.scala b/src/library/scala/util/hashing/Hashing.scala new file mode 100644 index 0000000000..f27a825125 --- /dev/null +++ b/src/library/scala/util/hashing/Hashing.scala @@ -0,0 +1,42 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +package scala.util.hashing + +/** `Hashing` is a trait whose instances each represent a strategy for hashing + * instances of a type. + * + * `Hashing`'s companion object defines a default hashing strategy for all + * objects - it calls their `##` method. + * + * Note: when using a custom `Hashing`, make sure to use it with the `Equiv` + * such that if any two objects are equal, then their hash codes must be equal. + * + * @since 2.10 + */ +@annotation.implicitNotFound(msg = "No implicit Hashing defined for ${T}.") +trait Hashing[T] extends Serializable { + + def hashCode(x: T): Int + +} + + +object Hashing { + + final class Default[T] extends Hashing[T] { + def hashCode(x: T) = x.## + } + + implicit def default[T] = new Default[T] + + def fromFunction[T](f: T => Int) = new Hashing[T] { + def hashCode(x: T) = f(x) + } + +} diff --git a/test/files/run/triemap-hash.scala b/test/files/run/triemap-hash.scala index 8f2347a96f..7f19997da0 100644 --- a/test/files/run/triemap-hash.scala +++ b/test/files/run/triemap-hash.scala @@ -1,7 +1,7 @@ -import math.Hashing +import util.hashing.Hashing -- cgit v1.2.3