summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRich Hickey <richhickey@gmail.com>2009-08-03 10:46:34 -0400
committerRich Hickey <richhickey@gmail.com>2009-08-03 10:46:34 -0400
commit6bcc5e982720788d922184f19218d3f49e184524 (patch)
tree08dd1e1cd22db85f94843be45766681ba8826105
parentc87119b00b292a296a603a2af92333e70b48071e (diff)
parent6e2ff8788fbff36d0ce019c7bfc6adff4fc58cf9 (diff)
Merge branch 'chunks' into merge-chunks
-rw-r--r--src/clj/clojure/core.clj53
-rw-r--r--src/jvm/clojure/lang/Associative.java5
-rw-r--r--src/jvm/clojure/lang/IEditableCollection.java17
-rw-r--r--src/jvm/clojure/lang/ILookup.java19
-rw-r--r--src/jvm/clojure/lang/IMutableAssociative.java18
-rw-r--r--src/jvm/clojure/lang/IMutableCollection.java20
-rw-r--r--src/jvm/clojure/lang/IMutableVector.java20
-rw-r--r--src/jvm/clojure/lang/LazilyPersistentVector.java136
-rw-r--r--src/jvm/clojure/lang/PersistentVector.java571
-rw-r--r--src/jvm/clojure/lang/RT.java8
-rw-r--r--test/clojure/test_clojure/sequences.clj14
11 files changed, 617 insertions, 264 deletions
diff --git a/src/clj/clojure/core.clj b/src/clj/clojure/core.clj
index 50e4d584..ef5f2482 100644
--- a/src/clj/clojure/core.clj
+++ b/src/clj/clojure/core.clj
@@ -251,7 +251,9 @@
(defn vec
"Creates a new vector containing the contents of coll."
([coll]
- (. clojure.lang.LazilyPersistentVector (createOwning (to-array coll)))))
+ (if (instance? java.util.Collection coll)
+ (clojure.lang.LazilyPersistentVector/create coll)
+ (. clojure.lang.LazilyPersistentVector (createOwning (to-array coll))))))
(defn hash-map
"keyval => key val
@@ -4315,3 +4317,52 @@
Delivers the supplied value to the promise, releasing any pending
derefs. A subsequent call to deliver on a promise will throw an exception."
[promise val] (promise val))
+
+;;;;;;;;;;;;;;;;;;;;; editable collections ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+(defn mutable
+ "Returns a new, mutable version of the collection, in constant time."
+ [#^clojure.lang.IEditableCollection coll]
+ (.mutable coll))
+
+(defn immutable!
+ "Returns a new, immutable version of the mutable collection, in constant time."
+ [#^clojure.lang.IMutableCollection coll]
+ (.immutable coll))
+
+(defn conj!
+ "Adds x to the mutable collection, and return coll. The 'addition'
+ may happen at different 'places' depending on the concrete type."
+ [#^clojure.lang.IMutableCollection coll x]
+ (.conj coll x))
+
+(defn assoc!
+ "When applied to a mutable map, adds mapping of key(s) to
+ val(s). When applied to a mutable vector, sets the val at index.
+ Note - index must be <= (count vector). Returns coll."
+ ([#^clojure.lang.IMutableAssociative coll key val] (.assoc coll key val))
+ ([#^clojure.lang.IMutableAssociative coll key val & kvs]
+ (let [ret (.assoc coll key val)]
+ (if kvs
+ (recur ret (first kvs) (second kvs) (nnext kvs))
+ ret))))
+
+(defn pop!
+ "Removes the last item from a mutable vector. If
+ the collection is empty, throws an exception. Returns coll"
+ [#^clojure.lang.IMutableVector coll]
+ (.pop coll))
+
+;redef into with batch support
+(defn into
+ "Returns a new coll consisting of to-coll with all of the items of
+ from-coll conjoined."
+ [to from]
+ (if (instance? clojure.lang.IEditableCollection to)
+ (#(loop [ret (mutable to) items (seq from)]
+ (if items
+ (recur (conj! ret (first items)) (next items))
+ (immutable! ret))))
+ (#(loop [ret to items (seq from)]
+ (if items
+ (recur (conj ret (first items)) (next items))
+ ret)))))
diff --git a/src/jvm/clojure/lang/Associative.java b/src/jvm/clojure/lang/Associative.java
index 891def5f..a2399946 100644
--- a/src/jvm/clojure/lang/Associative.java
+++ b/src/jvm/clojure/lang/Associative.java
@@ -9,14 +9,11 @@ package clojure.lang;
* the terms of this license.
* You must not remove this notice, or any other, from this software.
*/
-public interface Associative extends IPersistentCollection{
+public interface Associative extends IPersistentCollection, ILookup{
boolean containsKey(Object key);
IMapEntry entryAt(Object key);
Associative assoc(Object key, Object val);
-Object valAt(Object key);
-
-Object valAt(Object key, Object notFound);
}
diff --git a/src/jvm/clojure/lang/IEditableCollection.java b/src/jvm/clojure/lang/IEditableCollection.java
new file mode 100644
index 00000000..be447958
--- /dev/null
+++ b/src/jvm/clojure/lang/IEditableCollection.java
@@ -0,0 +1,17 @@
+/**
+ * Copyright (c) Rich Hickey. All rights reserved.
+ * The use and distribution terms for this software are covered by the
+ * Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
+ * which can be found in the file epl-v10.html 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.
+ **/
+
+/* rich Jul 17, 2009 */
+
+package clojure.lang;
+
+public interface IEditableCollection{
+IMutableCollection mutable();
+}
diff --git a/src/jvm/clojure/lang/ILookup.java b/src/jvm/clojure/lang/ILookup.java
new file mode 100644
index 00000000..b124955d
--- /dev/null
+++ b/src/jvm/clojure/lang/ILookup.java
@@ -0,0 +1,19 @@
+/**
+ * Copyright (c) Rich Hickey. All rights reserved.
+ * The use and distribution terms for this software are covered by the
+ * Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
+ * which can be found in the file epl-v10.html 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.
+ **/
+
+/* rich Aug 2, 2009 */
+
+package clojure.lang;
+
+public interface ILookup{
+Object valAt(Object key);
+
+Object valAt(Object key, Object notFound);
+}
diff --git a/src/jvm/clojure/lang/IMutableAssociative.java b/src/jvm/clojure/lang/IMutableAssociative.java
new file mode 100644
index 00000000..1eef92c2
--- /dev/null
+++ b/src/jvm/clojure/lang/IMutableAssociative.java
@@ -0,0 +1,18 @@
+/**
+ * Copyright (c) Rich Hickey. All rights reserved.
+ * The use and distribution terms for this software are covered by the
+ * Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
+ * which can be found in the file epl-v10.html 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.
+ **/
+
+/* rich Jul 17, 2009 */
+
+package clojure.lang;
+
+public interface IMutableAssociative extends IMutableCollection, ILookup{
+
+IMutableAssociative assoc(Object key, Object val);
+}
diff --git a/src/jvm/clojure/lang/IMutableCollection.java b/src/jvm/clojure/lang/IMutableCollection.java
new file mode 100644
index 00000000..a41f1701
--- /dev/null
+++ b/src/jvm/clojure/lang/IMutableCollection.java
@@ -0,0 +1,20 @@
+/**
+ * Copyright (c) Rich Hickey. All rights reserved.
+ * The use and distribution terms for this software are covered by the
+ * Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
+ * which can be found in the file epl-v10.html 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.
+ **/
+
+/* rich Jul 17, 2009 */
+
+package clojure.lang;
+
+public interface IMutableCollection{
+
+IMutableCollection conj(Object val);
+
+IPersistentCollection immutable();
+}
diff --git a/src/jvm/clojure/lang/IMutableVector.java b/src/jvm/clojure/lang/IMutableVector.java
new file mode 100644
index 00000000..3deab315
--- /dev/null
+++ b/src/jvm/clojure/lang/IMutableVector.java
@@ -0,0 +1,20 @@
+/**
+ * Copyright (c) Rich Hickey. All rights reserved.
+ * The use and distribution terms for this software are covered by the
+ * Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
+ * which can be found in the file epl-v10.html 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.
+ **/
+
+/* rich Jul 17, 2009 */
+
+package clojure.lang;
+
+public interface IMutableVector extends IMutableAssociative, Indexed{
+
+IMutableVector assocN(int i, Object val);
+
+IMutableVector pop();
+}
diff --git a/src/jvm/clojure/lang/LazilyPersistentVector.java b/src/jvm/clojure/lang/LazilyPersistentVector.java
index f3562cae..44985467 100644
--- a/src/jvm/clojure/lang/LazilyPersistentVector.java
+++ b/src/jvm/clojure/lang/LazilyPersistentVector.java
@@ -14,141 +14,21 @@ package clojure.lang;
import java.util.Collection;
-public class LazilyPersistentVector extends APersistentVector{
-final Object[] array;
-PersistentVector v = null;
+public class LazilyPersistentVector{
+
static public IPersistentVector createOwning(Object... items){
if(items.length == 0)
return PersistentVector.EMPTY;
- return new LazilyPersistentVector(null, items, null);
+ else if(items.length <= 32)
+ return new PersistentVector(items.length, 5, PersistentVector.EMPTY_NODE,items);
+ return PersistentVector.create(items);
}
static public IPersistentVector create(Collection coll){
- return createOwning(coll.toArray());
-}
-
-LazilyPersistentVector(IPersistentMap meta, Object[] array, PersistentVector v){
- super(meta);
- this.array = array;
- this.v = v;
-}
-
-public ISeq seq(){
- if(array.length == 0)
- return null;
- return new ChunkedSeq(array);
-}
-
-static class ChunkedSeq extends ASeq implements IChunkedSeq, IndexedSeq{
- final Object[] array;
- final int offset;
- final int end;
- static final int BLOCK = 32;
-
- ChunkedSeq(IPersistentMap meta, Object[] array, int offset, int end){
- super(meta);
- this.array = array;
- this.offset = offset;
- this.end = end;
- }
-
- ChunkedSeq(Object[] array){
- this(array, 0);
- }
-
- ChunkedSeq(Object[] array, int offset){
- this(array,offset,Math.min(offset + BLOCK, array.length));
- }
-
- ChunkedSeq(Object[] array, int offset, int end){
- this.array = array;
- this.offset = offset;
- this.end = end;
- }
-
- public Obj withMeta(IPersistentMap meta){
- if(meta != _meta)
- return new ChunkedSeq(meta, array,offset,end);
- return this;
- }
-
- public Object first(){
- return array[offset];
- }
-
- public ISeq next(){
- if(offset + 1 < end)
- return new ChunkedSeq(array,offset + 1,end);
- return chunkedNext();
- }
-
- public IChunk chunkedFirst(){
- return new ArrayChunk(array, offset, end);
- }
-
- public ISeq chunkedNext(){
- if(end < array.length)
- return new ChunkedSeq(array,end);
- return null;
- }
-
- public ISeq chunkedMore(){
- ISeq s = chunkedNext();
- if(s == null)
- return PersistentList.EMPTY;
- return s;
- }
-
- public int index(){
- return offset;
- }
-
- public int count(){
- return array.length - offset;
- }
-}
-
-public Object[] toArray(){
- return array.clone();
-}
-
-public Object nth(int i){
- return array[i];
-}
-
-public IPersistentVector assocN(int i, Object val){
- return (IPersistentVector) v().assoc(i, val);
-}
-
-public int count(){
- return array.length;
-}
-
-public IPersistentVector cons(Object o){
- return v().cons(o);
-}
-
-public IPersistentCollection empty(){
- return PersistentVector.EMPTY.withMeta(meta());
-}
-
-public IPersistentStack pop(){
- return v().pop();
-}
-
-private synchronized IPersistentVector v(){
- if(v == null)
- {
- v = PersistentVector.create(array);
- }
- return v;
-}
-
-public Obj withMeta(IPersistentMap meta){
- if(meta != _meta)
- return new LazilyPersistentVector(meta, array, v);
- return this;
+ if(!(coll instanceof ISeq) && coll.size() <= 32)
+ return createOwning(coll.toArray());
+ return PersistentVector.create(RT.seq(coll));
}
}
diff --git a/src/jvm/clojure/lang/PersistentVector.java b/src/jvm/clojure/lang/PersistentVector.java
index 5c662556..752bccf8 100644
--- a/src/jvm/clojure/lang/PersistentVector.java
+++ b/src/jvm/clojure/lang/PersistentVector.java
@@ -1,35 +1,11 @@
/**
- Copyright (c) 2007-2008, Rich Hickey
- All rights reserved.
-
- Redistribution and use in source and binary forms, with or without
- modification, are permitted provided that the following conditions
- are met:
-
- * Redistributions of source code must retain the above copyright
- notice, this list of conditions and the following disclaimer.
-
- * Redistributions in binary form must reproduce the above
- copyright notice, this list of conditions and the following
- disclaimer in the documentation and/or other materials provided
- with the distribution.
-
- * Neither the name of Clojure nor the names of its contributors
- may be used to endorse or promote products derived from this
- software without specific prior written permission.
-
- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
- FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
- COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
- INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
- BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
- LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
- CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
- ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- POSSIBILITY OF SUCH DAMAGE.
+ * Copyright (c) Rich Hickey. All rights reserved.
+ * The use and distribution terms for this software are covered by the
+ * Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
+ * which can be found in the file epl-v10.html 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.
**/
/* rich Jul 5, 2007 */
@@ -37,38 +13,57 @@
package clojure.lang;
import java.util.List;
+import java.util.concurrent.atomic.AtomicReference;
+
+public class PersistentVector extends APersistentVector implements IEditableCollection{
+
+static class Node{
+ final AtomicReference<Thread> edit;
+ final Object[] array;
+
+ Node(AtomicReference<Thread> edit, Object[] array){
+ this.edit = edit;
+ this.array = array;
+ }
+
+ Node(AtomicReference<Thread> edit){
+ this.edit = edit;
+ this.array = new Object[32];
+ }
+}
+
+final static AtomicReference<Thread> NOEDIT = new AtomicReference<Thread>(null);
+final static Node EMPTY_NODE = new Node(NOEDIT, new Object[32]);
-public class PersistentVector extends APersistentVector{
final int cnt;
final int shift;
-final Object[] root;
+final Node root;
final Object[] tail;
-public final static PersistentVector EMPTY = new PersistentVector(0, 5, RT.EMPTY_ARRAY, RT.EMPTY_ARRAY);
-
+public final static PersistentVector EMPTY = new PersistentVector(0, 5, EMPTY_NODE, new Object[]{});
static public PersistentVector create(ISeq items){
- PersistentVector ret = EMPTY;
+ MutableVector ret = EMPTY.mutable();
for(; items != null; items = items.next())
- ret = ret.cons(items.first());
- return ret;
+ ret = ret.conj(items.first());
+ return ret.immutable();
}
static public PersistentVector create(List items){
- PersistentVector ret = EMPTY;
+ MutableVector ret = EMPTY.mutable();
for(Object item : items)
- ret = ret.cons(item);
- return ret;
+ ret = ret.conj(item);
+ return ret.immutable();
}
static public PersistentVector create(Object... items){
- PersistentVector ret = EMPTY;
+ MutableVector ret = EMPTY.mutable();
for(Object item : items)
- ret = ret.cons(item);
- return ret;
+ ret = ret.conj(item);
+ return ret.immutable();
}
-PersistentVector(int cnt, int shift, Object[] root, Object[] tail){
+PersistentVector(int cnt, int shift, Node root, Object[] tail){
super(null);
this.cnt = cnt;
this.shift = shift;
@@ -77,7 +72,7 @@ PersistentVector(int cnt, int shift, Object[] root, Object[] tail){
}
-PersistentVector(IPersistentMap meta, int cnt, int shift, Object[] root, Object[] tail){
+PersistentVector(IPersistentMap meta, int cnt, int shift, Node root, Object[] tail){
super(meta);
this.cnt = cnt;
this.shift = shift;
@@ -85,25 +80,31 @@ PersistentVector(IPersistentMap meta, int cnt, int shift, Object[] root, Object[
this.tail = tail;
}
+public MutableVector mutable(){
+ return new MutableVector(this);
+}
+
final int tailoff(){
- return cnt - tail.length;
+ if(cnt < 32)
+ return 0;
+ return ((cnt - 1) >>> 5) << 5;
}
-public Object[] nodeFor(int i){
+public Object[] arrayFor(int i){
if(i >= 0 && i < cnt)
{
if(i >= tailoff())
return tail;
- Object[] arr = root;
+ Node node = root;
for(int level = shift; level > 0; level -= 5)
- arr = (Object[]) arr[(i >>> level) & 0x01f];
- return arr;
+ node = (Node) node.array[(i >>> level) & 0x01f];
+ return node.array;
}
throw new IndexOutOfBoundsException();
}
public Object nth(int i){
- Object[] node = nodeFor(i);
+ Object[] node = arrayFor(i);
return node[i & 0x01f];
}
@@ -126,16 +127,16 @@ public PersistentVector assocN(int i, Object val){
throw new IndexOutOfBoundsException();
}
-private static Object[] doAssoc(int level, Object[] arr, int i, Object val){
- Object[] ret = arr.clone();
+private static Node doAssoc(int level, Node node, int i, Object val){
+ Node ret = new Node(node.edit,node.array.clone());
if(level == 0)
{
- ret[i & 0x01f] = val;
+ ret.array[i & 0x01f] = val;
}
else
{
int subidx = (i >>> level) & 0x01f;
- ret[subidx] = doAssoc(level - 5, (Object[]) arr[subidx], i, val);
+ ret.array[subidx] = doAssoc(level - 5, (Node) node.array[subidx], i, val);
}
return ret;
}
@@ -150,24 +151,64 @@ public PersistentVector withMeta(IPersistentMap meta){
public PersistentVector cons(Object val){
- if(tail.length < 32)
+ int i = cnt;
+ //room in tail?
+// if(tail.length < 32)
+ if(cnt - tailoff() < 32)
{
Object[] newTail = new Object[tail.length + 1];
System.arraycopy(tail, 0, newTail, 0, tail.length);
newTail[tail.length] = val;
return new PersistentVector(meta(), cnt + 1, shift, root, newTail);
}
- Box expansion = new Box(null);
- Object[] newroot = pushTail(shift - 5, root, tail, expansion);
+ //full tail, push into tree
+ Node newroot;
+ Node tailnode = new Node(root.edit,tail);
int newshift = shift;
- if(expansion.val != null)
+ //overflow root?
+ if((cnt >>> 5) > (1 << shift))
{
- newroot = new Object[]{newroot, expansion.val};
+ newroot = new Node(root.edit);
+ newroot.array[0] = root;
+ newroot.array[1] = newPath(root.edit,shift, tailnode);
newshift += 5;
}
+ else
+ newroot = pushTail(shift, root, tailnode);
return new PersistentVector(meta(), cnt + 1, newshift, newroot, new Object[]{val});
}
+private Node pushTail(int level, Node parent, Node tailnode){
+ //if parent is leaf, insert node,
+ // else does it map to an existing child? -> nodeToInsert = pushNode one more level
+ // else alloc new path
+ //return nodeToInsert placed in copy of parent
+ int subidx = ((cnt - 1) >>> level) & 0x01f;
+ Node ret = new Node(parent.edit, parent.array.clone());
+ Node nodeToInsert;
+ if(level == 5)
+ {
+ nodeToInsert = tailnode;
+ }
+ else
+ {
+ Node child = (Node) parent.array[subidx];
+ nodeToInsert = (child != null)?
+ pushTail(level-5,child, tailnode)
+ :newPath(root.edit,level-5, tailnode);
+ }
+ ret.array[subidx] = nodeToInsert;
+ return ret;
+}
+
+private static Node newPath(AtomicReference<Thread> edit,int level, Node node){
+ if(level == 0)
+ return node;
+ Node ret = new Node(edit);
+ ret.array[0] = newPath(edit, level - 5, node);
+ return ret;
+}
+
public IChunkedSeq chunkedSeq(){
if(count() == 0)
return null;
@@ -189,7 +230,7 @@ static public final class ChunkedSeq extends ASeq implements IChunkedSeq{
this.vec = vec;
this.i = i;
this.offset = offset;
- this.node = vec.nodeFor(i);
+ this.node = vec.arrayFor(i);
}
ChunkedSeq(IPersistentMap meta, PersistentVector vec, Object[] node, int i, int offset){
@@ -245,84 +286,361 @@ public IPersistentCollection empty(){
return EMPTY.withMeta(meta());
}
-private Object[] pushTail(int level, Object[] arr, Object[] tailNode, Box expansion){
- Object newchild;
- if(level == 0)
- {
- newchild = tailNode;
- }
- else
- {
- newchild = pushTail(level - 5, (Object[]) arr[arr.length - 1], tailNode, expansion);
- if(expansion.val == null)
- {
- Object[] ret = arr.clone();
- ret[arr.length - 1] = newchild;
- return ret;
- }
- else
- newchild = expansion.val;
- }
- //expansion
- if(arr.length == 32)
- {
- expansion.val = new Object[]{newchild};
- return arr;
- }
- Object[] ret = new Object[arr.length + 1];
- System.arraycopy(arr, 0, ret, 0, arr.length);
- ret[arr.length] = newchild;
- expansion.val = null;
- return ret;
-}
+//private Node pushTail(int level, Node node, Object[] tailNode, Box expansion){
+// Object newchild;
+// if(level == 0)
+// {
+// newchild = tailNode;
+// }
+// else
+// {
+// newchild = pushTail(level - 5, (Object[]) arr[arr.length - 1], tailNode, expansion);
+// if(expansion.val == null)
+// {
+// Object[] ret = arr.clone();
+// ret[arr.length - 1] = newchild;
+// return ret;
+// }
+// else
+// newchild = expansion.val;
+// }
+// //expansion
+// if(arr.length == 32)
+// {
+// expansion.val = new Object[]{newchild};
+// return arr;
+// }
+// Object[] ret = new Object[arr.length + 1];
+// System.arraycopy(arr, 0, ret, 0, arr.length);
+// ret[arr.length] = newchild;
+// expansion.val = null;
+// return ret;
+//}
public PersistentVector pop(){
if(cnt == 0)
throw new IllegalStateException("Can't pop empty vector");
if(cnt == 1)
return EMPTY.withMeta(meta());
- if(tail.length > 1)
+ //if(tail.length > 1)
+ if(cnt-tailoff() > 1)
{
Object[] newTail = new Object[tail.length - 1];
System.arraycopy(tail, 0, newTail, 0, newTail.length);
return new PersistentVector(meta(), cnt - 1, shift, root, newTail);
}
- Box ptail = new Box(null);
- Object[] newroot = popTail(shift - 5, root, ptail);
+ Object[] newtail = arrayFor(cnt - 2);
+
+ Node newroot = popTail(shift, root);
int newshift = shift;
if(newroot == null)
{
- newroot = RT.EMPTY_ARRAY;
+ newroot = EMPTY_NODE;
}
- if(shift > 5 && newroot.length == 1)
+ if(shift > 5 && newroot.array[1] == null)
{
- newroot = (Object[]) newroot[0];
+ newroot = (Node) newroot.array[0];
newshift -= 5;
}
- return new PersistentVector(meta(), cnt - 1, newshift, newroot, (Object[]) ptail.val);
+ return new PersistentVector(meta(), cnt - 1, newshift, newroot, newtail);
}
-private Object[] popTail(int shift, Object[] arr, Box ptail){
- if(shift > 0)
+private Node popTail(int level, Node node){
+ int subidx = ((cnt-2) >>> level) & 0x01f;
+ if(level > 5)
{
- Object[] newchild = popTail(shift - 5, (Object[]) arr[arr.length - 1], ptail);
- if(newchild != null)
+ Node newchild = popTail(level - 5, (Node) node.array[subidx]);
+ if(newchild == null && subidx == 0)
+ return null;
+ else
{
- Object[] ret = arr.clone();
- ret[arr.length - 1] = newchild;
+ Node ret = new Node(root.edit, node.array.clone());
+ ret.array[subidx] = newchild;
return ret;
}
}
- if(shift == 0)
- ptail.val = arr[arr.length - 1];
- //contraction
- if(arr.length == 1)
+ else if(subidx == 0)
return null;
- Object[] ret = new Object[arr.length - 1];
- System.arraycopy(arr, 0, ret, 0, ret.length);
- return ret;
+ else
+ {
+ Node ret = new Node(root.edit, node.array.clone());
+ ret.array[subidx] = null;
+ return ret;
+ }
}
+static final class MutableVector extends AFn implements IMutableVector, Counted{
+ int cnt;
+ int shift;
+ Node root;
+ Object[] tail;
+
+ MutableVector(int cnt, int shift, Node root, Object[] tail){
+ this.cnt = cnt;
+ this.shift = shift;
+ this.root = root;
+ this.tail = tail;
+ }
+
+ MutableVector(PersistentVector v){
+ this(v.cnt, v.shift, editableRoot(v.root), editableTail(v.tail));
+ }
+
+ public int count(){
+ ensureEditable();
+ return cnt;
+ }
+
+ Node ensureEditable(Node node){
+ if(node.edit == root.edit)
+ return node;
+ return new Node(root.edit, node.array.clone());
+ }
+
+ void ensureEditable(){
+ Thread owner = root.edit.get();
+ if(owner == Thread.currentThread())
+ return;
+ if(owner != null)
+ throw new IllegalAccessError("Mutable used by non-owner thread");
+ throw new IllegalAccessError("Mutable used after immutable call");
+
+// root = editableRoot(root);
+// tail = editableTail(tail);
+ }
+
+ static Node editableRoot(Node node){
+ return new Node(new AtomicReference<Thread>(Thread.currentThread()), node.array.clone());
+ }
+
+ public PersistentVector immutable(){
+ ensureEditable();
+// Thread owner = root.edit.get();
+// if(owner != null && owner != Thread.currentThread())
+// {
+// throw new IllegalAccessError("Mutation release by non-owner thread");
+// }
+ root.edit.set(null);
+ Object[] trimmedTail = new Object[cnt-tailoff()];
+ System.arraycopy(tail,0,trimmedTail,0,trimmedTail.length);
+ return new PersistentVector(cnt, shift, root, trimmedTail);
+ }
+
+ static Object[] editableTail(Object[] tl){
+ Object[] ret = new Object[32];
+ System.arraycopy(tl,0,ret,0,tl.length);
+ return ret;
+ }
+
+ public MutableVector conj(Object val){
+ ensureEditable();
+ int i = cnt;
+ //room in tail?
+ if(i - tailoff() < 32)
+ {
+ tail[i & 0x01f] = val;
+ ++cnt;
+ return this;
+ }
+ //full tail, push into tree
+ Node newroot;
+ Node tailnode = new Node(root.edit, tail);
+ tail = new Object[32];
+ tail[0] = val;
+ int newshift = shift;
+ //overflow root?
+ if((cnt >>> 5) > (1 << shift))
+ {
+ newroot = new Node(root.edit);
+ newroot.array[0] = root;
+ newroot.array[1] = newPath(root.edit,shift, tailnode);
+ newshift += 5;
+ }
+ else
+ newroot = pushTail(shift, root, tailnode);
+ root = newroot;
+ shift = newshift;
+ ++cnt;
+ return this;
+ }
+
+ private Node pushTail(int level, Node parent, Node tailnode){
+ //if parent is leaf, insert node,
+ // else does it map to an existing child? -> nodeToInsert = pushNode one more level
+ // else alloc new path
+ //return nodeToInsert placed in parent
+ parent = ensureEditable(parent);
+ int subidx = ((cnt - 1) >>> level) & 0x01f;
+ Node ret = parent;
+ Node nodeToInsert;
+ if(level == 5)
+ {
+ nodeToInsert = tailnode;
+ }
+ else
+ {
+ Node child = (Node) parent.array[subidx];
+ nodeToInsert = (child != null) ?
+ pushTail(level - 5, child, tailnode)
+ : newPath(root.edit, level - 5, tailnode);
+ }
+ ret.array[subidx] = nodeToInsert;
+ return ret;
+ }
+
+ final private int tailoff(){
+ if(cnt < 32)
+ return 0;
+ return ((cnt-1) >>> 5) << 5;
+ }
+
+ private Object[] arrayFor(int i){
+ if(i >= 0 && i < cnt)
+ {
+ if(i >= tailoff())
+ return tail;
+ Node node = root;
+ for(int level = shift; level > 0; level -= 5)
+ node = (Node) node.array[(i >>> level) & 0x01f];
+ return node.array;
+ }
+ throw new IndexOutOfBoundsException();
+ }
+
+ public Object valAt(Object key){
+ //note - relies on ensureEditable in 2-arg valAt
+ return valAt(key, null);
+ }
+
+ public Object valAt(Object key, Object notFound){
+ ensureEditable();
+ if(Util.isInteger(key))
+ {
+ int i = ((Number) key).intValue();
+ if(i >= 0 && i < cnt)
+ return nth(i);
+ }
+ return notFound;
+ }
+
+ public Object invoke(Object arg1) throws Exception{
+ //note - relies on ensureEditable in nth
+ if(Util.isInteger(arg1))
+ return nth(((Number) arg1).intValue());
+ throw new IllegalArgumentException("Key must be integer");
+ }
+
+ public Object nth(int i){
+ ensureEditable();
+ Object[] node = arrayFor(i);
+ return node[i & 0x01f];
+ }
+
+ public MutableVector assocN(int i, Object val){
+ ensureEditable();
+ if(i >= 0 && i < cnt)
+ {
+ if(i >= tailoff())
+ {
+ tail[i & 0x01f] = val;
+ return this;
+ }
+
+ root = doAssoc(shift, root, i, val);
+ return this;
+ }
+ if(i == cnt)
+ return conj(val);
+ throw new IndexOutOfBoundsException();
+ }
+
+ public MutableVector assoc(Object key, Object val){
+ //note - relies on ensureEditable in assocN
+ if(Util.isInteger(key))
+ {
+ int i = ((Number) key).intValue();
+ return assocN(i, val);
+ }
+ throw new IllegalArgumentException("Key must be integer");
+ }
+
+ private Node doAssoc(int level, Node node, int i, Object val){
+ node = ensureEditable(node);
+ Node ret = node;
+ if(level == 0)
+ {
+ ret.array[i & 0x01f] = val;
+ }
+ else
+ {
+ int subidx = (i >>> level) & 0x01f;
+ ret.array[subidx] = doAssoc(level - 5, (Node) node.array[subidx], i, val);
+ }
+ return ret;
+ }
+
+ public MutableVector pop(){
+ ensureEditable();
+ if(cnt == 0)
+ throw new IllegalStateException("Can't pop empty vector");
+ if(cnt == 1)
+ {
+ cnt = 0;
+ return this;
+ }
+ int i = cnt - 1;
+ //pop in tail?
+ if((i & 0x01f) > 0)
+ {
+ --cnt;
+ return this;
+ }
+
+ Object[] newtail = arrayFor(cnt - 2);
+
+ Node newroot = popTail(shift, root);
+ int newshift = shift;
+ if(newroot == null)
+ {
+ newroot = EMPTY_NODE;
+ }
+ if(shift > 5 && newroot.array[1] == null)
+ {
+ newroot = (Node) newroot.array[0];
+ newshift -= 5;
+ }
+ root = newroot;
+ shift = newshift;
+ --cnt;
+ tail = newtail;
+ return this;
+ }
+
+ private Node popTail(int level, Node node){
+ node = ensureEditable(node);
+ int subidx = ((cnt - 2) >>> level) & 0x01f;
+ if(level > 5)
+ {
+ Node newchild = popTail(level - 5, (Node) node.array[subidx]);
+ if(newchild == null && subidx == 0)
+ return null;
+ else
+ {
+ Node ret = node;
+ ret.array[subidx] = newchild;
+ return ret;
+ }
+ }
+ else if(subidx == 0)
+ return null;
+ else
+ {
+ Node ret = node;
+ ret.array[subidx] = null;
+ return ret;
+ }
+ }
+}
/*
static public void main(String[] args){
if(args.length != 3)
@@ -333,23 +651,27 @@ static public void main(String[] args){
int size = Integer.parseInt(args[0]);
int writes = Integer.parseInt(args[1]);
int reads = Integer.parseInt(args[2]);
- Vector v = new Vector(size);
- v.setSize(size);
+// Vector v = new Vector(size);
+ ArrayList v = new ArrayList(size);
+// v.setSize(size);
//PersistentArray p = new PersistentArray(size);
PersistentVector p = PersistentVector.EMPTY;
+// MutableVector mp = p.mutable();
for(int i = 0; i < size; i++)
{
- v.set(i