revamped ListMap

4 files changed, 272 insertions, 153 deletions

diff --git a/src/org/clojure/runtime/HashtableMap.java b/src/org/clojure/runtime/HashtableMap.java
index 0bb1c53a..a96a9761 100644
--- a/src/org/clojure/runtime/HashtableMap.java
+++ b/src/org/clojure/runtime/HashtableMap.java
@@ -210,9 +210,9 @@ static class Iter implements Iterator, IMapEntry{
 static class Iter implements Iterator{

 	PersistentArray buckets;

 	int b;

-	ListMap.Entry e;

+	ListMap e;

 

-		Iter(PersistentArray buckets){

+	Iter(PersistentArray buckets){

         this.buckets = buckets;

         this.b = -1;

         nextBucket();

@@ -223,9 +223,9 @@ static class Iter implements Iterator{
         for(b = b+1;b<buckets.length();b++)

             {

             ListMap a = (ListMap) buckets.get(b);

-            if(a != null)

+            if(a != null && a != ListMap.EMPTY)

                 {

-                e = a.entries;

+                e = a;

                 break;

                 }

             }

@@ -236,9 +236,9 @@ static class Iter implements Iterator{
     }

 

 	public Object next() {

-		ListMap.Entry ret = e;

+		ListMap ret = e;

         e = e.rest();

-        if(e == null)

+        if(e == ListMap.EMPTY)

             nextBucket();

         return ret;

     }

@@ -248,7 +248,7 @@ static class Iter implements Iterator{
     }

 }

 

-IMap entriesFor(Object key){

+final IMap entriesFor(Object key){

     return (IMap) array.get(bucketFor(key,array));

 }

 

@@ -274,7 +274,7 @@ IMap createArrayMap(Object[] init) {
 }

 

 private IMap createListMap(Object key, Object val){

-	return new ListMap(key,val);

+	return ListMap.create(key,val);

 }

 

 }

diff --git a/src/org/clojure/runtime/ListMap.java b/src/org/clojure/runtime/ListMap.java
index 18b17ee3..a87a699a 100644
--- a/src/org/clojure/runtime/ListMap.java
+++ b/src/org/clojure/runtime/ListMap.java
@@ -14,83 +14,36 @@ package org.clojure.runtime;
 
 import java.util.Iterator;
 
-public class ListMap implements IMap
+public class ListMap implements IMap, IMapEntry
 {
-final Entry entries;
-final int _count;
 
-public ListMap(){
-	this.entries = null;
-	this._count = 0;
-}
+static public ListMap EMPTY = new ListMap();
 
-public ListMap(Object key, Object val){
-	this.entries = Entry.create(key, val, null);
-	this._count = 1;
+static public ListMap create(Object key, Object val){
+	return new Tail(key, val);
 }
 
-ListMap(int count, Entry entries){
-	this._count = count;
-	this.entries = entries;
+public Object key(){
+	return null;
 }
 
-
-
-static class Entry implements IMapEntry{
-	final Object _key;
-	final Object _val;
-
-	Entry(Object key,Object val){
-		this._key = key;
-		this._val = val;
-		}
-
-    Entry rest(){
-        return null;
-    }
-
-    static Entry create(Object key,Object val,Entry rest){
-        if(rest == null)
-            return new Entry(key,val);
-        return new EntryLink(key, val, rest);
-    }
-
-	public Object key(){
-		return _key;
-	}
-
-	public Object val(){
-		return _val;
-	}
+public Object val(){
+	return null;
 }
 
-static class EntryLink extends Entry{
-	final Entry _rest;
-
-	EntryLink(Object key,Object val,Entry rest){
-        super(key,val);
-		this._rest = rest;
-		}
-
-    Entry rest(){
-        return _rest;
+ListMap rest(){
+    return this;
     }
-}
 
 public int count(){
-	return _count;
+	return 0;
 }
 
 public boolean contains(Object key){
-	return find(key) != null;
+	return false;
 }
 
-public Entry find(Object key){
-	for(Entry e = entries;e != null;e = e.rest())
-		{
-		if(equalKey(key,e._key))
-			return e;
-		}
+public IMapEntry find(Object key){
 	return null;
 }
 
@@ -98,60 +51,36 @@ public IMap add(Object key){
 	return put(key, null);
 }
 
-public IMap put(Object key, Object val){
-	Entry remEntries = doRemove(entries, key);
-	int incr = (remEntries == entries) ? 1 : 0;
-	return new ListMap(_count + incr, Entry.create(key, val, remEntries));
+public ListMap put(Object key, Object val){
+	return new Tail(key, val);
 }
 
-Entry doRemove(Entry e, Object key){
-	if(e == null)
-		return null;
-	else if(equalKey(key,e._key))
-		{
-		return e.rest();
-		}
-	else
-		{
-		Entry er = doRemove(e.rest(), key);
-		if(er != e.rest()) //removed in tail
-			return Entry.create(e._key, e._val, er);
-		return e;
-		}
-}
-
-public IMap remove(Object key){
-	Entry remEntries = doRemove(entries, key);
-	if(remEntries == entries) //didn't have key
-		return this;
-	return new ListMap(_count - 1, remEntries);
+public ListMap remove(Object key){
+	return this;
 }
 
 public Object get(Object key){
-	Entry e = find(key);
-	if(e != null)
-		return e._val;
 	return null;
 }
 
 public int capacity(){
-	return count();
+	return 0;
 }
 
 static class Iter implements Iterator{
-	Entry e;
+	ListMap e;
 
-	Iter(Entry e)
+	Iter(ListMap e)
 	{
 	this.e = e;
 	}
 
 	public boolean hasNext(){
-		return e != null;
+		return e != EMPTY;
 	}
 
 	public Object next(){
-		Entry ret = e;
+		ListMap ret = e;
 		e = e.rest();
 		return ret;
 	}
@@ -162,7 +91,143 @@ static class Iter implements Iterator{
 }
 
 public Iterator iterator(){
-	return new Iter(entries);
+	return new Iter(this);
+}
+
+static class Tail extends ListMap{
+	final Object _key;
+	final Object _val;
+
+	Tail(Object key,Object val){
+		this._key = key;
+		this._val = val;
+		}
+
+    ListMap rest(){
+        return EMPTY;
+    }
+
+	public int count(){
+		return 1;
+	}
+
+	public Object get(Object key){
+		if(equalKey(key,_key))
+			return _val;
+		return null;
+	}
+
+	public int capacity(){
+		return 1;
+	}
+
+	public Object key(){
+		return _key;
+	}
+
+	public Object val(){
+		return _val;
+	}
+
+	public boolean contains(Object key){
+		return equalKey(key,_key);
+	}
+
+	public IMapEntry find(Object key){
+		if(equalKey(key,_key))
+			return this;
+		return null;
+	}
+
+	public ListMap put(Object key, Object val){
+		if(equalKey(key,_key))  //replace
+			{
+			if(val == _val)
+				return this;
+			return new Tail(key,val);
+			}
+		return new Link(key,val,this);
+	}
+
+	public ListMap remove(Object key){
+		if(equalKey(key,_key))
+			return EMPTY;
+		return this;
+	}
+}
+
+static class Link extends ListMap{
+	final Object _key;
+	final Object _val;
+	final ListMap _rest;
+
+	Link(Object key,Object val,ListMap rest){
+		this._key = key;
+		this._val = val;
+		this._rest = rest;
+		}
+
+	public Object key(){
+		return _key;
+	}
+
+	public Object val(){
+		return _val;
+	}
+
+	ListMap rest(){
+        return _rest;
+        }
+
+	public int count(){
+		return 1 + _rest.count();
+	}
+
+	public boolean contains(Object key){
+		return find(key) != null;
+	}
+
+	public IMapEntry find(Object key){
+		if(equalKey(key,_key))
+			return this;
+		return _rest.find(key);
+	}
+
+	public ListMap put(Object key, Object val){
+		if(equalKey(key,_key))
+			{
+			if(val == _val)
+				return this;
+			return new Link(key,val,_rest);
+			}
+		ListMap r = _rest.put(key,val);
+		if(r == _rest)  //already there with same value
+			return this;
+		return new Link(_key,_val,r);
+	}
+
+	public ListMap remove(Object key){
+		if(equalKey(key,_key))
+			return _rest;
+		ListMap r = _rest.remove(key);
+		if(r == _rest)  //not there
+			return this;
+		if(r == EMPTY)
+			return new Tail(_key,_val);
+		return new Link(_key, _val, r);
+	}
+
+	public Object get(Object key){
+		IMapEntry e = find(key);
+		if(e != null)
+			return e.val();
+		return null;
+	}
+
+	public int capacity(){
+		return count();
+	}
+
 }
 
 boolean equalKey(Object k1,Object k2){
diff --git a/src/org/clojure/runtime/PersistentArray.java b/src/org/clojure/runtime/PersistentArray.java
index 9a0acc6d..11c38be7 100644
--- a/src/org/clojure/runtime/PersistentArray.java
+++ b/src/org/clojure/runtime/PersistentArray.java
@@ -12,8 +12,8 @@
 
 package org.clojure.runtime;
 
-import java.util.concurrent.atomic.AtomicInteger;
-import java.util.concurrent.atomic.AtomicReferenceArray;
+//import java.util.concurrent.atomic.AtomicInteger;
+//import java.util.concurrent.atomic.AtomicReferenceArray;
 import java.util.BitSet;
 import java.util.Iterator;
 import java.util.Vector;
@@ -54,18 +54,18 @@ public Iterator iterator(){
 }
 
 static class Master{
-	final AtomicReferenceArray array;
+	final Entry[] array;
 	final Object defaultVal;
-    final AtomicInteger rev;
-    final AtomicInteger load;
+    int rev;
+    int load;
 	final int maxLoad;
     final float loadFactor;
 
     Master(int size,Object defaultVal, float loadFactor){
-		this.array = new AtomicReferenceArray(size);
+		this.array = new Entry[size];//new AtomicReferenceArray(size);
 		this.defaultVal = defaultVal;
-        this.rev = new AtomicInteger(0);
-        this.load = new AtomicInteger(0);
+        this.rev = 0;//new AtomicInteger(0);
+        this.load = 0;//new AtomicInteger(0);
 		this.maxLoad = (int) (size * loadFactor);
         this.loadFactor = loadFactor;
         }
@@ -155,22 +155,23 @@ PersistentArray(Master master,int rev,int baseline, BitSet history){
 
 
 
-public int length(){
-	return master.array.length();
+final public int length(){
+	return master.array.length;
+	//return master.array.length();
 }
 
-public Object get(int i) {
+final public Object get(int i) {
     Entry e = getEntry(i);
     if(e != null)
         return e.val;
     return master.defaultVal;
 }
 
-public boolean has(int i){
+final public boolean has(int i){
     return getEntry(i) != null;
 }
 
-public PersistentArray resize(int newLength) {
+final public PersistentArray resize(int newLength) {
     PersistentArray ret = new PersistentArray(newLength, master.defaultVal, master.loadFactor);
     int load = 0;
     for(int i=0;i< Math.min(length(),newLength);i++)
@@ -178,12 +179,14 @@ public PersistentArray resize(int newLength) {
         Entry e = getEntry(i);
         if(e != null)
             {
-            ret.master.array.set(i,Entry.create(0,e.val, null));
+            ret.master.array[i] = new Entry(0,e.val);
+            //ret.master.array.set(i,Entry.create(0,e.val, null));
             ++load;
             }
         }
 
-    ret.master.load.set(load);
+	ret.master.load = load;
+	//ret.master.load.set(load);
 
     return ret;
 }
@@ -192,16 +195,18 @@ public PersistentArray resize(int newLength) {
  *
  * @return number of values (of all revisions) stored in shared array
  */
-public int load(){
-    return master.load.get();
+final public int load(){
+	return master.load;
+	//return master.load.get();
 }
 
-public PersistentArray isolate() {
+final public PersistentArray isolate() {
     return resize(length());
 }
 
-Entry getEntry(int i){
-	for(Entry e = (Entry) master.array.get(i);e != null;e = e.rest())
+final Entry getEntry(int i){
+	for(Entry e = master.array[i];e != null;e = e.rest())
+	//	for(Entry e = (Entry) master.array.get(i);e != null;e = e.rest())
 		{
 		if(e.rev <= rev)
 			{
@@ -213,47 +218,52 @@ Entry getEntry(int i){
     return null;
 }
 
-public PersistentArray set(int i,Object val) {
-	if(master.load.get() >= master.maxLoad)
-		return isolate().set(i,val);
-	PersistentArray ret = getSetArray();
-	ret.doSet(i, val);
-	return ret;
+final public PersistentArray set(int i,Object val) {
+	if(master.load >= master.maxLoad)
+		//if(master.load.get() >= master.maxLoad)
+			return isolate().set(i,val);
+	synchronized(master){
+		PersistentArray ret = getSetArray();
+		ret.doSet(i, val);
+		return ret;
+	}
 }
 
-void doSet(int i, Object val){
-	Entry oldEntry, newEntry;
-	do
-		{
-		oldEntry = (Entry) master.array.get(i);
-		newEntry = Entry.create(rev, val, oldEntry);
-		} while(!master.array.compareAndSet(i, oldEntry, newEntry));
-    master.load.incrementAndGet();
+final void doSet(int i, Object val){
+//	Entry oldEntry, newEntry;
+//	do
+//		{
+//		oldEntry = (Entry) master.array.get(i);
+//		newEntry = Entry.create(rev, val, oldEntry);
+//		} while(!master.array.compareAndSet(i, oldEntry, newEntry));
+
+	//must now be called inside lock of master
+	master.array[i] = Entry.create(rev, val, master.array[i]);
+	//master.load.incrementAndGet();
+	++master.load;
 }
 
-PersistentArray getSetArray(){
-	int nextRev;
-	int nextBaseline;
-	BitSet nextHistory;
+final PersistentArray getSetArray(){
+	//must now be called inside lock of master
 	//is this a sequential update?
-	if(master.rev.compareAndSet(rev, rev + 1))
+	if(master.rev == rev)
+		//if(master.rev.compareAndSet(rev, rev + 1))
 		{
-		nextRev = rev + 1;
-		nextBaseline = baseline;
-		nextHistory = history;
+		return new PersistentArray(master, ++master.rev, baseline, history);
 		}
 	else //gap
 		{
-		nextRev = master.rev.incrementAndGet();
-		nextBaseline = nextRev;
+		//nextRev = master.rev.incrementAndGet();
+		int nextRev = ++master.rev;
+		BitSet nextHistory;
 		if(history != null)
 			nextHistory = (BitSet) history.clone();
 		else
 			nextHistory = new BitSet(rev+1);
 		nextHistory.set(baseline,rev+1);
+		return new PersistentArray(master, nextRev, nextRev, nextHistory);
 		}
 
-	return new PersistentArray(master, nextRev, nextBaseline, nextHistory);
 }
 
 
@@ -281,6 +291,7 @@ static public void main(String[] args){
 	rand = new Random(42);
 	long tv = 0;
 	System.out.println("Vector");
+	long startTime = System.nanoTime();
 	for(int i = 0; i < writes; i++)
 		{
 		v.set(rand.nextInt(size), i);
@@ -289,8 +300,11 @@ static public void main(String[] args){
 		{
 		tv += (Integer)v.get(rand.nextInt(size));
 		}
+	long estimatedTime = System.nanoTime() - startTime;
+	System.out.println("time: " + estimatedTime/1000000);
 	System.out.println("PersistentArray");
 	rand = new Random(42);
+	startTime = System.nanoTime();
 	long tp = 0;
 	for(int i = 0; i < writes; i++)
 		{
@@ -302,6 +316,8 @@ static public void main(String[] args){
 		{
 		tp += (Integer)p.get(rand.nextInt(size));
 		}
+	estimatedTime = System.nanoTime() - startTime;
+	System.out.println("time: " + estimatedTime/1000000);
 	System.out.println("Done: " + tv + ", " + tp);
 
 
diff --git a/src/org/clojure/runtime/RBTree.java b/src/org/clojure/runtime/RBTree.java
index af311db4..e9ebe7bb 100644
--- a/src/org/clojure/runtime/RBTree.java
+++ b/src/org/clojure/runtime/RBTree.java
@@ -676,21 +676,24 @@ static public void main(String args[]){
 		}
 	Collections.shuffle(Arrays.asList(ints));
 	System.out.println("Building set");
+	  long startTime = System.nanoTime();
 	//IMap set = new PersistentHashMap(1);
 	IMap set = new HashtableMap(1001);
 	//IMap set = new ListMap();
 	//IMap set = new RBTree();
-	for(int i = 0; i < ints.length; i++)
-		{
-		Integer anInt = ints[i];
-		set = set.add(anInt);
-		}
+//	for(int i = 0; i < ints.length; i++)
+//		{
+//		Integer anInt = ints[i];
+//		set = set.add(anInt);
+//		}
 	for(int i = 0; i < ints.length; i++)
 		{
 		Integer anInt = ints[i];
 		set = set.put(anInt, anInt);
 		}
     System.out.println("_count = " + set.count());
+
+
 //	System.out.println("_count = " + set._count + ", min: " + set.minKey() + ", max: " + set.maxKey()
 //	                   + ", depth: " + set.depth());
 	Iterator it = set.iterator();
@@ -710,7 +713,42 @@ static public void main(String args[]){
 		}
 
 	System.out.println();
-	System.out.println("_count = " + set.count());
+	long estimatedTime = System.nanoTime() - startTime;
+
+	System.out.println("_count = " + set.count() + ", time: " + estimatedTime/1000000);
+
+	System.out.println("Building ht");
+	Hashtable ht = new Hashtable(1001);
+	startTime = System.nanoTime();
+//	for(int i = 0; i < ints.length; i++)
+//		{
+//		Integer anInt = ints[i];
+//		ht.put(anInt,null);
+//		}
+	for(int i = 0; i < ints.length; i++)
+		{
+		Integer anInt = ints[i];
+		ht.put(anInt, anInt);
+		}
+    System.out.println("size = " + ht.size());
+	Enumeration e = ht.keys();
+	while(e.hasMoreElements())
+		{
+		Integer o = (Integer) e.nextElement();
+		if(!ht.containsKey(o))
+			System.err.println("Can't find: " + o);
+		else if(n < 2000)
+			System.out.print(o.toString() + ",");
+		}
+
+	for(int i = 0; i < ints.length/2; i++)
+		{
+		Integer anInt = ints[i];
+		ht.remove(anInt);
+		}
+	estimatedTime = System.nanoTime() - startTime;
+	System.out.println("size = " + ht.size() + ", time: " + estimatedTime/1000000);
+
 //	System.out.println("_count = " + set._count + ", min: " + set.minKey() + ", max: " + set.maxKey()
 //	                   + ", depth: " + set.depth());
 }