summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/cli/runtime/PerisistentArrayList.cs105
-rw-r--r--src/cli/runtime/PersistentArray.cs37
-rw-r--r--src/jvm/clojure/lang/PersistentArray.java36
-rw-r--r--src/jvm/clojure/lang/PersistentArrayList.java102
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);
+}
+
+}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-07-18 12:23:34 +0000