Add the Ctrie concurrent map implementation.

Ctrie is a scalable concurrent map implementation that supports
constant time lock-free lazy snapshots.

Due to the well-known private volatile field problem, atomic
reference updaters cannot be used efficiently in Scala yet.
For this reason, 4 java files had to be included as well.
None of these pollute the namespace, as most of the classes
are private.

Unit tests and a scalacheck check is also included.

1 files changed, 58 insertions, 0 deletions

diff --git a/test/files/run/ctries/lnode.scala b/test/files/run/ctries/lnode.scala
new file mode 100644
index 0000000000..28da4cc62f
--- /dev/null
+++ b/test/files/run/ctries/lnode.scala
@@ -0,0 +1,58 @@
+
+
+
+import collection.mutable.Ctrie
+
+
+object LNodeSpec extends Spec {
+  
+  val initsz = 1500
+  val secondsz = 1750
+  
+  def test() {
+    "accept elements with the same hash codes" in {
+      val ct = new Ctrie[DumbHash, Int]
+      for (i <- 0 until initsz) ct.update(new DumbHash(i), i)
+    }
+    
+    "lookup elements with the same hash codes" in {
+      val ct = new Ctrie[DumbHash, Int]
+      for (i <- 0 until initsz) ct.update(new DumbHash(i), i)
+      for (i <- 0 until initsz) assert(ct.get(new DumbHash(i)) == Some(i))
+      for (i <- initsz until secondsz) assert(ct.get(new DumbHash(i)) == None)
+    }
+    
+    "remove elements with the same hash codes" in {
+      val ct = new Ctrie[DumbHash, Int]
+      for (i <- 0 until initsz) ct.update(new DumbHash(i), i)
+      for (i <- 0 until initsz) assert(ct.remove(new DumbHash(i)) == Some(i))
+      for (i <- 0 until initsz) assert(ct.get(new DumbHash(i)) == None)
+    }
+    
+    "put elements with the same hash codes if absent" in {
+      val ct = new Ctrie[DumbHash, Int]
+      for (i <- 0 until initsz) ct.put(new DumbHash(i), i)
+      for (i <- 0 until initsz) assert(ct.lookup(new DumbHash(i)) == i)
+      for (i <- 0 until initsz) assert(ct.putIfAbsent(new DumbHash(i), i) == Some(i))
+      for (i <- initsz until secondsz) assert(ct.putIfAbsent(new DumbHash(i), i) == None)
+      for (i <- initsz until secondsz) assert(ct.lookup(new DumbHash(i)) == i)
+    }
+    
+    "replace elements with the same hash codes" in {
+      val ct = new Ctrie[DumbHash, Int]
+      for (i <- 0 until initsz) assert(ct.put(new DumbHash(i), i) == None)
+      for (i <- 0 until initsz) assert(ct.lookup(new DumbHash(i)) == i)
+      for (i <- 0 until initsz) assert(ct.replace(new DumbHash(i), -i) == Some(i))
+      for (i <- 0 until initsz) assert(ct.lookup(new DumbHash(i)) == -i)
+      for (i <- 0 until initsz) assert(ct.replace(new DumbHash(i), -i, i) == true)
+    }
+    
+    "remove elements with the same hash codes if mapped to a specific value" in {
+      val ct = new Ctrie[DumbHash, Int]
+      for (i <- 0 until initsz) assert(ct.put(new DumbHash(i), i) == None)
+      for (i <- 0 until initsz) assert(ct.remove(new DumbHash(i), i) == true)
+    }
+    
+  }
+  
+}