From 6d980568070ae1d44e52613eb58ca1a64ff2649b Mon Sep 17 00:00:00 2001
From: Rich Hickey <richhickey@gmail.com>
Date: Mon, 5 Jun 2006 14:47:10 +0000
Subject: added load factor, improved docs, java/cs in sync

---
 src/cli/runtime/PersistentArray.cs | 56 ++++++++++++++++++++++++++++++--------
 1 file changed, 44 insertions(+), 12 deletions(-)

(limited to 'src/cli')

diff --git a/src/cli/runtime/PersistentArray.cs b/src/cli/runtime/PersistentArray.cs
index 654aa2e8..c618a5c3 100644
--- a/src/cli/runtime/PersistentArray.cs
+++ b/src/cli/runtime/PersistentArray.cs
@@ -17,9 +17,31 @@ using System.Collections;
 namespace org.clojure.runtime
 {
 /**
- * Hybrid range/BitArray, multi-thread-safe
- * 
+ * Note that instances of this class are constant values
+ * i.e. set() returns a new array, old one is intact
+ *
+ * Multiple revisions (thread-safely) share the same master array
+ *
+ * Constant time most-recent-revision lookups
+ * Amortized constant-time sequential revisions (when loadFactor > 1)
+ * where a sequential revision is a revision of the most recent revision
+ *
+ * Non-sequential revisions are O(length), but with a small constant multiplier of 1/32
+ * Worst-case O(r) lookups for oldest revs where r is number of revisions
+ * at index i since last (automatic or manual) isolate. If set()s are roughly evenly
+ * distributed, r should be approximately == loadFactor, i.e. constant
+ * In pathological case (all mods to same index), r == (loadFactor * length)
+ *
+ * (loadFactor * length) old values are retained, even if the array revisions aren't
+ * Default loadFactor is 2.1
+ * When the load exceeds (loadFactor * length) the next revision is automatically isolated
+ * You can determine how many values are in the shared master by calling load()
+ * and can trim them by calling isolate() or resize(), which yield a new array with no
+ * sharing and no old values
+ *
  * See Cohen for basic idea
+ * I added hybrid most-recent-sequential-range + shared-bitset idea, multi-thread-safety
+ * Java implementation is lock-free
  */
 
 public class PersistentArray : IEnumerable{
@@ -38,13 +60,14 @@ internal class Master{
 	internal readonly Object defaultVal;
 	internal int rev;
 	internal int load;
+	internal readonly int maxLoad;
 
-	internal Master(int size, Object defaultVal)
-		{
+	internal Master(int size,Object defaultVal, double loadFactor){
 		this.array = new Entry[size];
 		this.defaultVal = defaultVal;
 		this.rev = 0;
 		this.load = 0;
+		this.maxLoad = (int)(size * loadFactor);
 		}
 }
 
@@ -99,8 +122,18 @@ public void Reset()
 	internal readonly int baseline;
 	internal readonly BitArray history;
 
-public PersistentArray(int size,Object defaultVal){
-	this.master = new Master(size, defaultVal);
+public PersistentArray(int size)
+		: this(size, null)
+		{
+		}
+		
+public PersistentArray(int size, Object defaultVal)
+	:this(size,defaultVal,2.1)
+	{
+	}
+
+public PersistentArray(int size, Object defaultVal, double loadFactor){
+	this.master = new Master(size, defaultVal, loadFactor);
 	this.rev = 0;
 	this.baseline = 0;
 	this.history = null;
@@ -114,10 +147,7 @@ public PersistentArray(int size,Object defaultVal){
 	this.history = history;
 }
 
-	public PersistentArray(int size)
-		: this(size, null)
-		{
-		}
+
 
 public int length(){
 	return master.array.Length;
@@ -136,7 +166,7 @@ public bool has(int i){
 
 public PersistentArray resize(int newLength)
 	{
-	PersistentArray ret = new PersistentArray(newLength, master.defaultVal);
+	PersistentArray ret = new PersistentArray(newLength, master.defaultVal, ((double)master.maxLoad) / length());
 	for (int i = 0; i < Math.Min(length(), newLength); i++)
 		{
 		Entry e = getEntry(i);
@@ -172,6 +202,8 @@ Entry getEntry(int i){
 }
 
 public PersistentArray set(int i,Object val) {
+	if(master.load >= master.maxLoad)
+		return isolate().set(i,val);
 	PersistentArray ret = getSetArray();
 	ret.doSet(i, val);
 	return ret;
@@ -228,7 +260,7 @@ static public void Main(String[] args){
 	int size = Int32.Parse(args[0]);
 	int writes = Int32.Parse(args[1]);
 	int reads = Int32.Parse(args[2]);
-	ArrayList v = new ArrayList(size);
+	ArrayList v = ArrayList.Synchronized(new ArrayList(size));
 	//v.setSize(size);
 	PersistentArray p = new PersistentArray(size);
 
-- 
cgit v1.2.3-70-g09d2