first pass at ArrayList

4 files changed, 255 insertions, 25 deletions

diff --git a/src/cli/runtime/PerisistentArrayList.cs b/src/cli/runtime/PerisistentArrayList.cs
new file mode 100644
index 00000000..5fe1bc11
--- /dev/null
+++ b/src/cli/runtime/PerisistentArrayList.cs
@@ -0,0 +1,105 @@
+/**

+ *   Copyright (c) Rich Hickey. All rights reserved.

+ *   The use and distribution terms for this software are covered by the

+ *   Common Public License 1.0 (http://opensource.org/licenses/cpl.php)

+ *   which can be found in the file CPL.TXT at the root of this distribution.

+ *   By using this software in any fashion, you are agreeing to be bound by

+ * 	 the terms of this license.

+ *   You must not remove this notice, or any other, from this software.

+ **/

+

+using System;

+using System.Threading;

+using System.Collections;

+

+namespace clojure.lang

+{

+public class PersistentArrayList : PersistentArray{

+

+int _count;

+

+public PersistentArrayList(int initialCapacity) : base(initialCapacity){

+    

+    _count = 0;

+}

+

+PersistentArrayList(Master master,int rev,int baseline, BitArray history, int count):base(master,rev,baseline,history){

+    

+    this._count = count;

+}

+

+PersistentArrayList(int size, Object defaultVal, float loadFactor, int count):base(size, defaultVal, loadFactor) {

+    

+    this._count = count;

+}

+

+override public Object get(int i) {

+    if(i >= _count)

+        throw new IndexOutOfRangeException();

+

+    return base.get(i);

+}

+

+override public IArray set(int i,Object val) {

+    if(i >= _count)

+		throw new IndexOutOfRangeException();

+

+    return (PersistentArrayList) base.set(i, val);

+}

+

+override public int length(){

+    return _count;

+}

+

+public int count(){

+    return _count;

+}

+

+public int capacity(){

+	return data.master.array.Length;

+}

+

+public PersistentArrayList add(Object val) {

+    if(_count == data.master.array.Length) //full

+        {

+        lock(data.master){

+            if(_count == data.master.array.Length) //still full

+                grow();

+            }

+        }

+    PersistentArrayList ret =  (PersistentArrayList) base.set(_count, val);

+    ret._count = _count + 1;

+    return ret;

+}

+

+public PersistentArrayList remove() {

+    if(_count == 0)

+        throw new InvalidOperationException();

+    return new PersistentArrayList(data.master, data.rev, data.baseline, data.history, _count - 1);

+}

+

+

+private void grow() {

+    //must be called inside lock of master

+    if(data.master.next != null) //this master has been trimmed, but this rev is not yet propagated

+        trim();

+

+    Master newMaster = new Master(data.master.array.Length * 2, data.master.defaultVal, data.master.loadFactor);

+    newMaster.rev = data.master.rev;

+    newMaster.load = data.master.load;

+    newMaster.basis = data.master.basis;

+    for(int i=0;i<data.master.array.Length;i++)

+        newMaster.array[i] = data.master.array[i];

+    data.master = newMaster;

+}

+

+override internal PersistentArray create(Master master,int rev,int baseline, BitArray history){

+    return new PersistentArrayList(data.master, rev, baseline, history,_count);

+}

+

+override internal PersistentArray create(int size, Object defaultVal, float loadFactor) {

+    return new PersistentArrayList(size, defaultVal, loadFactor,_count);

+}

+

+}

+}

diff --git a/src/cli/runtime/PersistentArray.cs b/src/cli/runtime/PersistentArray.cs
index 4b83dfea..912e31cc 100644
--- a/src/cli/runtime/PersistentArray.cs
+++ b/src/cli/runtime/PersistentArray.cs
@@ -69,7 +69,7 @@ internal class Master{
 	internal int load;

 	internal readonly int maxLoad;

 	internal readonly float loadFactor;

-    internal readonly int[] basis;

+    internal int[] basis;

     internal volatile Master next;

     

 	internal Master(int size,Object defaultVal, float loadFactor){

@@ -194,7 +194,7 @@ public void Reset()
 	}

 

 internal class Data{

-	internal readonly Master master;

+	internal Master master;

 	internal readonly int rev;

 	internal readonly int baseline;

 	internal readonly BitArray history;

@@ -207,7 +207,7 @@ internal class Data{
 		}	

 	}

 

-volatile Data data;

+internal volatile Data data;

 

 public PersistentArray(int size)

 		: this(size, (Object)null)

@@ -250,11 +250,11 @@ public PersistentArray(IArray init) :this(init.length()) {
 	data.master.load = load;

 }

 

-public int length(){

+virtual public int length(){

 return data.master.array.Length;

 }

 

-public Object get(int i){

+virtual public Object get(int i){

 	Entry e = getEntry(i);

 		if(e != null)

 				return e.val;

@@ -267,7 +267,7 @@ public bool has(int i){
 

 public PersistentArray resize(int newLength)

 	{

-	PersistentArray ret = new PersistentArray(newLength, data.master.defaultVal, data.master.loadFactor);

+	PersistentArray ret = create(newLength, data.master.defaultVal, data.master.loadFactor);

 	for (int i = 0; i < Math.Min(length(), newLength); i++)

 		{

 		Entry e = getEntry(i);

@@ -317,7 +317,7 @@ for (Entry e = (Entry)data.master.array[i]; e != null; e = e.rest())
 	return null;

 }

 

-public IArray set(int i,Object val) {

+virtual public IArray set(int i,Object val) {

 //if (data.master.load >= data.master.maxLoad)

 //		{

 //		isolate();

@@ -334,7 +334,7 @@ public IArray set(int i,Object val) {
 	}

 }

 

-private void trim(){

+protected void trim(){

     //must be called inside lock of master

 	if (data.master.next == null) //this master has never been trimmed

         {

@@ -438,7 +438,7 @@ PersistentArray getSetArray(){
 	//is this a sequential update?

 if (data.master.rev == data.rev)

 		{

-		return new PersistentArray(data.master, ++data.master.rev, data.baseline, data.history);

+		return create(data.master, ++data.master.rev, data.baseline, data.history);

 		}

 	else //gap

 		{

@@ -454,10 +454,21 @@ if (data.master.rev == data.rev)
 			nextHistory = new BitArray(data.rev + 1);

 		for (int i = data.baseline; i <= data.rev; i++)

 			nextHistory.Set(i,true);

-		return new PersistentArray(data.master, nextRev, nextRev, nextHistory);

+		return create(data.master, nextRev, nextRev, nextHistory);

 		}

 }

 

+internal  virtual PersistentArray create(Master master, int rev, int baseline, BitArray history)

+	{

+	return new PersistentArray(data.master, rev, baseline, history);

+	}

+

+internal virtual PersistentArray create(int size, Object defaultVal, float loadFactor)

+	{

+	return new PersistentArray(size, defaultVal, loadFactor);

+	}

+

+

 /*

 [STAThread] 

 static public void Main(String[] args){

@@ -471,12 +482,14 @@ static public void Main(String[] args){
 	int reads = Int32.Parse(args[2]);

 	ArrayList v = ArrayList.Synchronized(new ArrayList(size));

 	//v.setSize(size);

-	IArray p = new PersistentArray(size);

+	//IArray p = new PersistentArray(size);

+	IArray p = new PersistentArrayList(size);

 

 	for(int i = 0; i < size; i++)

 		{

 		v.Add(0);

-		p = p.set(i, 0);

+		//p = p.set(i, 0);

+		p = ((PersistentArrayList)p).add(0);

 		}

 

 	Random rand;

diff --git a/src/jvm/clojure/lang/PersistentArray.java b/src/jvm/clojure/lang/PersistentArray.java
index 5eda4d11..a2f5d7b4 100644
--- a/src/jvm/clojure/lang/PersistentArray.java
+++ b/src/jvm/clojure/lang/PersistentArray.java
@@ -65,7 +65,7 @@ static class Master{
     int load;
     final int maxLoad;
     final float loadFactor;
-    final int[] basis;
+    int[] basis;
     volatile Master next;
 
     Master(int size,Object defaultVal, float loadFactor){
@@ -172,7 +172,7 @@ static class ValIter implements Iterator{
 }
 
 static class Data{
-final Master master;
+Master master;
 final int rev;
 final int baseline;
 final BitSet history;
@@ -227,11 +227,11 @@ public PersistentArray(IArray init)  {
     data.master.load = load;
 }
 
-final public int length(){
+public int length(){
 	return data.master.array.length;
 }
 
-final public Object get(int i) {
+public Object get(int i) {
     Entry e = getEntry(i);
     if(e != null)
         return e.val;
@@ -243,7 +243,7 @@ final public boolean has(int i){
 }
 
 final public PersistentArray resize(int newLength) {
-    PersistentArray ret = new PersistentArray(newLength, data.master.defaultVal, data.master.loadFactor);
+    PersistentArray ret = create(newLength, data.master.defaultVal, data.master.loadFactor);
     int load = 0;
     for(int i=0;i< Math.min(length(),newLength);i++)
         {
@@ -300,7 +300,7 @@ private Entry getEntry(int i){
     return null;
 }
 
-final public PersistentArray set(int i,Object val) {
+public PersistentArray set(int i,Object val) {
     synchronized(data.master){
         if(data.master.load >= data.master.maxLoad)
             trim();
@@ -310,7 +310,7 @@ final public PersistentArray set(int i,Object val) {
 	}
 }
 
-private void trim(){
+protected void trim(){
     //must be called inside lock of master
     if(data.master.next == null) //this master has never been trimmed
         {
@@ -412,7 +412,7 @@ private PersistentArray getSetArray(){
 	//is this a sequential update?
 	if(data.master.rev == data.rev)
 		{
-		return new PersistentArray(data.master, ++data.master.rev, data.baseline, data.history);
+		return create(data.master, ++data.master.rev, data.baseline, data.history);
 		}
 	else //gap
 		{
@@ -423,11 +423,18 @@ private PersistentArray getSetArray(){
 		else
 			nextHistory = new BitSet(data.rev+1);
 		nextHistory.set(data.baseline,data.rev+1);
-		return new PersistentArray(data.master, nextRev, nextRev, nextHistory);
+		return create(data.master, nextRev, nextRev, nextHistory);
 		}
 
 }
 
+protected PersistentArray create(Master master,int rev,int baseline, BitSet history){
+    return new PersistentArray(data.master, rev, baseline, history);
+}
+
+protected PersistentArray create(int size, Object defaultVal, float loadFactor) {
+    return new PersistentArray(size, defaultVal, loadFactor);
+}
 
 static public void main(String[] args){
 	if(args.length != 3)
@@ -440,13 +447,15 @@ static public void main(String[] args){
 	int reads = Integer.parseInt(args[2]);
 	Vector v = new Vector(size);
 	v.setSize(size);
-	PersistentArray p = new PersistentArray(size);
+    //PersistentArray p = new PersistentArray(size);
+    PersistentArrayList p = new PersistentArrayList(size);
 
 	for(int i = 0; i < size; i++)
 		{
 		v.set(i, 0);
-		p = p.set(i, 0);
-		}
+		//p = p.set(i, 0);
+        p = p.add(0);
+        }
 
 	Random rand;
 
@@ -470,12 +479,13 @@ static public void main(String[] args){
 	long tp = 0;
 
     PersistentArray oldp = p;
+    Random rand2 = new Random(42);
 
     for(int i = 0; i < writes; i++)
 		{
 		p =	p.set(rand.nextInt(size), i);
 		//dummy set to force perverse branching
-        //oldp =	oldp.set(rand.nextInt(size), i);
+        oldp =	oldp.set(rand2.nextInt(size), i);
 		}
 	for(int i = 0; i < reads; i++)
 		{
diff --git a/src/jvm/clojure/lang/PersistentArrayList.java b/src/jvm/clojure/lang/PersistentArrayList.java
new file mode 100644
index 00000000..fc786304
--- /dev/null
+++ b/src/jvm/clojure/lang/PersistentArrayList.java
@@ -0,0 +1,102 @@
+/**

+ *   Copyright (c) Rich Hickey. All rights reserved.

+ *   The use and distribution terms for this software are covered by the

+ *   Common Public License 1.0 (http://opensource.org/licenses/cpl.php)

+ *   which can be found in the file CPL.TXT at the root of this distribution.

+ *   By using this software in any fashion, you are agreeing to be bound by

+ * 	 the terms of this license.

+ *   You must not remove this notice, or any other, from this software.

+ **/

+

+package clojure.lang;

+

+import java.util.BitSet;

+

+public class PersistentArrayList extends PersistentArray{

+

+int _count;

+

+public PersistentArrayList(int initialCapacity){

+    super(initialCapacity);

+    _count = 0;

+}

+

+PersistentArrayList(Master master,int rev,int baseline, BitSet history, int count){

+    super(master,rev,baseline,history);

+    this._count = count;

+}

+

+PersistentArrayList(int size, Object defaultVal, float loadFactor, int count) {

+    super(size, defaultVal, loadFactor);

+    this._count = count;

+}

+

+public Object get(int i) {

+    if(i >= _count)

+        throw new IndexOutOfBoundsException();

+

+    return super.get(i);

+}

+

+public PersistentArrayList set(int i,Object val) {

+    if(i >= _count)

+        throw new IndexOutOfBoundsException();

+

+    return (PersistentArrayList) super.set(i, val);

+}

+

+public int length(){

+    return _count;

+}

+

+public int count(){

+    return _count;

+}

+

+public int capacity(){

+	return data.master.array.length;

+}

+

+public PersistentArrayList add(Object val) {

+    if(_count == data.master.array.length) //full

+        {

+        synchronized(data.master){

+            if(_count == data.master.array.length) //still full

+                grow();

+            }

+        }

+    PersistentArrayList ret =  (PersistentArrayList) super.set(_count, val);

+    ret._count = _count + 1;

+    return ret;

+}

+

+public PersistentArrayList remove() {

+    if(_count == 0)

+        throw new IllegalAccessError();

+    return new PersistentArrayList(data.master, data.rev, data.baseline, data.history, _count - 1);

+}

+

+

+private void grow() {

+    //must be called inside lock of master

+    if(data.master.next != null) //this master has been trimmed, but this rev is not yet propagated

+        trim();

+

+    Master newMaster = new Master(data.master.array.length * 2, data.master.defaultVal, data.master.loadFactor);

+    newMaster.rev = data.master.rev;

+    newMaster.load = data.master.load;

+    newMaster.basis = data.master.basis;

+    for(int i=0;i<data.master.array.length;i++)

+        newMaster.array[i] = data.master.array[i];

+    data.master = newMaster;

+}

+

+protected PersistentArray create(Master master,int rev,int baseline, BitSet history){

+    return new PersistentArrayList(data.master, rev, baseline, history,_count);

+}

+

+protected PersistentArray create(int size, Object defaultVal, float loadFactor) {

+    return new PersistentArrayList(size, defaultVal, loadFactor,_count);

+}

+

+}