summaryrefslogtreecommitdiff
path: root/src/library/scala/collection/mutable/Ctrie.scala
diff options
context:
space:
mode:
Diffstat (limited to 'src/library/scala/collection/mutable/Ctrie.scala')
-rw-r--r--src/library/scala/collection/mutable/Ctrie.scala44
1 files changed, 43 insertions, 1 deletions
diff --git a/src/library/scala/collection/mutable/Ctrie.scala b/src/library/scala/collection/mutable/Ctrie.scala
index dbd2129f0c..f208d6555e 100644
--- a/src/library/scala/collection/mutable/Ctrie.scala
+++ b/src/library/scala/collection/mutable/Ctrie.scala
@@ -360,6 +360,11 @@ private[mutable] final class INode[K, V](bn: MainNode[K, V], g: Gen) extends INo
final def isNullInode(ct: Ctrie[K, V]) = GCAS_READ(ct) eq null
+ final def cachedSize(ct: Ctrie[K, V]): Int = {
+ val m = GCAS_READ(ct)
+ m.cachedSize(ct)
+ }
+
/* this is a quiescent method! */
def string(lev: Int) = "%sINode -> %s".format(" " * lev, mainnode match {
case null => "<null>"
@@ -389,6 +394,8 @@ private[mutable] final class FailedNode[K, V](p: MainNode[K, V]) extends MainNod
def string(lev: Int) = throw new UnsupportedOperationException
+ def cachedSize(ct: AnyRef): Int = throw new UnsupportedOperationException
+
override def toString = "FailedNode(%s)".format(p)
}
@@ -414,6 +421,7 @@ extends MainNode[K, V] with KVNode[K, V] {
final def copyTombed = new TNode(k, v, hc)
final def copyUntombed = new SNode(k, v, hc)
final def kvPair = (k, v)
+ final def cachedSize(ct: AnyRef): Int = 1
final def string(lev: Int) = (" " * lev) + "TNode(%s, %s, %x, !)".format(k, v, hc)
}
@@ -432,12 +440,37 @@ extends MainNode[K, V] {
}
}
def get(k: K) = listmap.get(k)
+ def cachedSize(ct: AnyRef): Int = listmap.size
def string(lev: Int) = (" " * lev) + "LNode(%s)".format(listmap.mkString(", "))
}
private[mutable] final class CNode[K, V](final val bitmap: Int, final val array: Array[BasicNode], final val gen: Gen)
-extends MainNode[K, V] {
+extends CNodeBase[K, V] {
+
+ // this should only be called from within read-only snapshots
+ final def cachedSize(ct: AnyRef) = {
+ val currsz = READ_SIZE()
+ if (currsz != -1) currsz
+ else {
+ val sz = computeSize(ct.asInstanceOf[Ctrie[K, V]])
+ while (READ_SIZE() == -1) CAS_SIZE(-1, sz)
+ READ_SIZE()
+ }
+ }
+
+ private def computeSize(ct: Ctrie[K, V]): Int = {
+ var i = 0
+ var sz = 0
+ while (i < array.length) {
+ array(i) match {
+ case sn: SNode[_, _] => sz += 1
+ case in: INode[K, V] => sz += in.cachedSize(ct)
+ }
+ i += 1
+ }
+ sz
+ }
final def updatedAt(pos: Int, nn: BasicNode, gen: Gen) = {
val len = array.length
@@ -830,6 +863,15 @@ extends ConcurrentMap[K, V]
if (nonReadOnly) readOnlySnapshot().iterator
else new CtrieIterator(0, this)
+ private def cachedSize() = {
+ val r = RDCSS_READ_ROOT()
+ r.cachedSize(this)
+ }
+
+ override def size: Int =
+ if (nonReadOnly) readOnlySnapshot().size
+ else cachedSize()
+
override def stringPrefix = "Ctrie"
}