From 2f7197c50b31386118a660833828ea720bf9d239 Mon Sep 17 00:00:00 2001
From: Aleksandar Pokopec <aleksandar.prokopec@epfl.ch>
Date: Wed, 20 Oct 2010 20:19:48 +0000
Subject: Changed hash code strategy in hash table - now ...

Changed hash code strategy in hash table - now taking most significant bits when transforming the hash code into an index.
---
 .../scala/collection/mutable/HashTable.scala       |  8 ++++++-
 .../collection/parallel/mutable/ParHashTable.scala | 25 ++++++++++++++++++++++
 2 files changed, 32 insertions(+), 1 deletion(-)
 create mode 100644 src/library/scala/collection/parallel/mutable/ParHashTable.scala

(limited to 'src')

diff --git a/src/library/scala/collection/mutable/HashTable.scala b/src/library/scala/collection/mutable/HashTable.scala
index b924a38dde..f44209286a 100644
--- a/src/library/scala/collection/mutable/HashTable.scala
+++ b/src/library/scala/collection/mutable/HashTable.scala
@@ -237,7 +237,13 @@ trait HashTable[A] {
     h ^ (h >>> 10)
   }
 
-  protected final def index(hcode: Int) = improve(hcode) & (table.length - 1)
+  // Note:
+  // we take the most significant bits of the hashcode, not the lower ones
+  // this is of crucial importance when populating the table in parallel
+  protected final def index(hcode: Int) = {
+    val ones = table.length - 1
+    (improve(hcode) >> (32 - java.lang.Integer.bitCount(ones))) & ones
+  }
 }
 
 private[collection] object HashTable {
diff --git a/src/library/scala/collection/parallel/mutable/ParHashTable.scala b/src/library/scala/collection/parallel/mutable/ParHashTable.scala
new file mode 100644
index 0000000000..9e356b7fb4
--- /dev/null
+++ b/src/library/scala/collection/parallel/mutable/ParHashTable.scala
@@ -0,0 +1,25 @@
+package scala.collection
+package parallel.mutable
+
+
+
+
+import collection.mutable.HashEntry
+
+
+
+
+/** Provides functionality for hash tables with linked list buckets,
+ *  enriching the data structure by fulfilling certain requirements
+ *  for their parallel construction and iteration.
+ */
+trait ParHashTable[K] {
+
+  protected type Entry >: Null <: HashEntry[K, Entry]
+
+}
+
+
+
+
+
-- 
cgit v1.2.3