|
Java example source code file (PersistentHashMap.java)
The PersistentHashMap.java Java example source code/** * 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. **/ package clojure.lang; import java.io.Serializable; import java.util.*; import java.util.concurrent.Callable; import java.util.concurrent.atomic.AtomicReference; /* A persistent rendition of Phil Bagwell's Hash Array Mapped Trie Uses path copying for persistence HashCollision leaves vs. extended hashing Node polymorphism vs. conditionals No sub-tree pools or root-resizing Any errors are my own */ public class PersistentHashMap extends APersistentMap implements IEditableCollection, IObj, IMapIterable, IKVReduce { final int count; final INode root; final boolean hasNull; final Object nullValue; final IPersistentMap _meta; final public static PersistentHashMap EMPTY = new PersistentHashMap(0, null, false, null); final private static Object NOT_FOUND = new Object(); static public IPersistentMap create(Map other){ ITransientMap ret = EMPTY.asTransient(); for(Object o : other.entrySet()) { Map.Entry e = (Entry) o; ret = ret.assoc(e.getKey(), e.getValue()); } return ret.persistent(); } /* * @param init {key1,val1,key2,val2,...} */ public static PersistentHashMap create(Object... init){ ITransientMap ret = EMPTY.asTransient(); for(int i = 0; i < init.length; i += 2) { ret = ret.assoc(init[i], init[i + 1]); } return (PersistentHashMap) ret.persistent(); } public static PersistentHashMap createWithCheck(Object... init){ ITransientMap ret = EMPTY.asTransient(); for(int i = 0; i < init.length; i += 2) { ret = ret.assoc(init[i], init[i + 1]); if(ret.count() != i/2 + 1) throw new IllegalArgumentException("Duplicate key: " + init[i]); } return (PersistentHashMap) ret.persistent(); } static public PersistentHashMap create(ISeq items){ ITransientMap ret = EMPTY.asTransient(); for(; items != null; items = items.next().next()) { if(items.next() == null) throw new IllegalArgumentException(String.format("No value supplied for key: %s", items.first())); ret = ret.assoc(items.first(), RT.second(items)); } return (PersistentHashMap) ret.persistent(); } static public PersistentHashMap createWithCheck(ISeq items){ ITransientMap ret = EMPTY.asTransient(); for(int i=0; items != null; items = items.next().next(), ++i) { if(items.next() == null) throw new IllegalArgumentException(String.format("No value supplied for key: %s", items.first())); ret = ret.assoc(items.first(), RT.second(items)); if(ret.count() != i + 1) throw new IllegalArgumentException("Duplicate key: " + items.first()); } return (PersistentHashMap) ret.persistent(); } /* * @param init {key1,val1,key2,val2,...} */ public static PersistentHashMap create(IPersistentMap meta, Object... init){ return create(init).withMeta(meta); } PersistentHashMap(int count, INode root, boolean hasNull, Object nullValue){ this.count = count; this.root = root; this.hasNull = hasNull; this.nullValue = nullValue; this._meta = null; } public PersistentHashMap(IPersistentMap meta, int count, INode root, boolean hasNull, Object nullValue){ this._meta = meta; this.count = count; this.root = root; this.hasNull = hasNull; this.nullValue = nullValue; } static int hash(Object k){ return Util.hasheq(k); } public boolean containsKey(Object key){ if(key == null) return hasNull; return (root != null) ? root.find(0, hash(key), key, NOT_FOUND) != NOT_FOUND : false; } public IMapEntry entryAt(Object key){ if(key == null) return hasNull ? (IMapEntry) MapEntry.create(null, nullValue) : null; return (root != null) ? root.find(0, hash(key), key) : null; } public IPersistentMap assoc(Object key, Object val){ if(key == null) { if(hasNull && val == nullValue) return this; return new PersistentHashMap(meta(), hasNull ? count : count + 1, root, true, val); } Box addedLeaf = new Box(null); INode newroot = (root == null ? BitmapIndexedNode.EMPTY : root) .assoc(0, hash(key), key, val, addedLeaf); if(newroot == root) return this; return new PersistentHashMap(meta(), addedLeaf.val == null ? count : count + 1, newroot, hasNull, nullValue); } public Object valAt(Object key, Object notFound){ if(key == null) return hasNull ? nullValue : notFound; return root != null ? root.find(0, hash(key), key, notFound) : notFound; } public Object valAt(Object key){ return valAt(key, null); } public IPersistentMap assocEx(Object key, Object val) { if(containsKey(key)) throw Util.runtimeException("Key already present"); return assoc(key, val); } public IPersistentMap without(Object key){ if(key == null) return hasNull ? new PersistentHashMap(meta(), count - 1, root, false, null) : this; if(root == null) return this; INode newroot = root.without(0, hash(key), key); if(newroot == root) return this; return new PersistentHashMap(meta(), count - 1, newroot, hasNull, nullValue); } static final Iterator EMPTY_ITER = new Iterator(){ public boolean hasNext(){ return false; } public Object next(){ throw new NoSuchElementException(); } public void remove(){ throw new UnsupportedOperationException(); } }; private Iterator iterator(final IFn f){ final Iterator rootIter = (root == null) ? EMPTY_ITER : root.iterator(f); if(hasNull) { return new Iterator() { private boolean seen = false; public boolean hasNext() { if (!seen) return true; else return rootIter.hasNext(); } public Object next(){ if (!seen) { seen = true; return f.invoke(null, nullValue); } else return rootIter.next(); } public void remove(){ throw new UnsupportedOperationException(); } }; } else return rootIter; } public Iterator iterator(){ return iterator(APersistentMap.MAKE_ENTRY); } public Iterator keyIterator(){ return iterator(APersistentMap.MAKE_KEY); } public Iterator valIterator(){ return iterator(APersistentMap.MAKE_VAL); } public Object kvreduce(IFn f, Object init){ init = hasNull?f.invoke(init,null,nullValue):init; if(RT.isReduced(init)) return ((IDeref)init).deref(); if(root != null){ init = root.kvreduce(f,init); if(RT.isReduced(init)) return ((IDeref)init).deref(); else return init; } return init; } public Object fold(long n, final IFn combinef, final IFn reducef, IFn fjinvoke, final IFn fjtask, final IFn fjfork, final IFn fjjoin){ //we are ignoring n for now Callable top = new Callable(){ public Object call() throws Exception{ Object ret = combinef.invoke(); if(root != null) ret = combinef.invoke(ret, root.fold(combinef,reducef,fjtask,fjfork,fjjoin)); return hasNull? combinef.invoke(ret,reducef.invoke(combinef.invoke(),null,nullValue)) :ret; } }; return fjinvoke.invoke(top); } public int count(){ return count; } public ISeq seq(){ ISeq s = root != null ? root.nodeSeq() : null; return hasNull ? new Cons(MapEntry.create(null, nullValue), s) : s; } public IPersistentCollection empty(){ return EMPTY.withMeta(meta()); } static int mask(int hash, int shift){ //return ((hash << shift) >>> 27);// & 0x01f; return (hash >>> shift) & 0x01f; } public PersistentHashMap withMeta(IPersistentMap meta){ return new PersistentHashMap(meta, count, root, hasNull, nullValue); } public TransientHashMap asTransient() { return new TransientHashMap(this); } public IPersistentMap meta(){ return _meta; } static final class TransientHashMap extends ATransientMap { final AtomicReference<Thread> edit; volatile INode root; volatile int count; volatile boolean hasNull; volatile Object nullValue; final Box leafFlag = new Box(null); TransientHashMap(PersistentHashMap m) { this(new AtomicReference<Thread>(Thread.currentThread()), m.root, m.count, m.hasNull, m.nullValue); } TransientHashMap(AtomicReference<Thread> edit, INode root, int count, boolean hasNull, Object nullValue) { this.edit = edit; this.root = root; this.count = count; this.hasNull = hasNull; this.nullValue = nullValue; } ITransientMap doAssoc(Object key, Object val) { if (key == null) { if (this.nullValue != val) this.nullValue = val; if (!hasNull) { this.count++; this.hasNull = true; } return this; } // Box leafFlag = new Box(null); leafFlag.val = null; INode n = (root == null ? BitmapIndexedNode.EMPTY : root) .assoc(edit, 0, hash(key), key, val, leafFlag); if (n != this.root) this.root = n; if(leafFlag.val != null) this.count++; return this; } ITransientMap doWithout(Object key) { if (key == null) { if (!hasNull) return this; hasNull = false; nullValue = null; this.count--; return this; } if (root == null) return this; // Box leafFlag = new Box(null); leafFlag.val = null; INode n = root.without(edit, 0, hash(key), key, leafFlag); if (n != root) this.root = n; if(leafFlag.val != null) this.count--; return this; } IPersistentMap doPersistent() { edit.set(null); return new PersistentHashMap(count, root, hasNull, nullValue); } Object doValAt(Object key, Object notFound) { if (key == null) if (hasNull) return nullValue; else return notFound; if (root == null) return notFound; return root.find(0, hash(key), key, notFound); } int doCount() { return count; } void ensureEditable(){ if(edit.get() == null) throw new IllegalAccessError("Transient used after persistent! call"); } } static interface INode extends Serializable { INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf); INode without(int shift, int hash, Object key); IMapEntry find(int shift, int hash, Object key); Object find(int shift, int hash, Object key, Object notFound); ISeq nodeSeq(); INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf); INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf); public Object kvreduce(IFn f, Object init); Object fold(IFn combinef, IFn reducef, IFn fjtask, IFn fjfork, IFn fjjoin); // returns the result of (f [k v]) for each iterated element Iterator iterator(IFn f); } final static class ArrayNode implements INode{ int count; final INode[] array; final AtomicReference<Thread> edit; ArrayNode(AtomicReference<Thread> edit, int count, INode[] array){ this.array = array; this.edit = edit; this.count = count; } public INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf){ int idx = mask(hash, shift); INode node = array[idx]; if(node == null) return new ArrayNode(null, count + 1, cloneAndSet(array, idx, BitmapIndexedNode.EMPTY.assoc(shift + 5, hash, key, val, addedLeaf))); INode n = node.assoc(shift + 5, hash, key, val, addedLeaf); if(n == node) return this; return new ArrayNode(null, count, cloneAndSet(array, idx, n)); } public INode without(int shift, int hash, Object key){ int idx = mask(hash, shift); INode node = array[idx]; if(node == null) return this; INode n = node.without(shift + 5, hash, key); if(n == node) return this; if (n == null) { if (count <= 8) // shrink return pack(null, idx); return new ArrayNode(null, count - 1, cloneAndSet(array, idx, n)); } else return new ArrayNode(null, count, cloneAndSet(array, idx, n)); } public IMapEntry find(int shift, int hash, Object key){ int idx = mask(hash, shift); INode node = array[idx]; if(node == null) return null; return node.find(shift + 5, hash, key); } public Object find(int shift, int hash, Object key, Object notFound){ int idx = mask(hash, shift); INode node = array[idx]; if(node == null) return notFound; return node.find(shift + 5, hash, key, notFound); } public ISeq nodeSeq(){ return Seq.create(array); } public Iterator iterator(IFn f){ return new Iter(array, f); } public Object kvreduce(IFn f, Object init){ for(INode node : array){ if(node != null){ init = node.kvreduce(f,init); if(RT.isReduced(init)) return init; } } return init; } public Object fold(final IFn combinef, final IFn reducef, final IFn fjtask, final IFn fjfork, final IFn fjjoin){ List<Callable> tasks = new ArrayList(); for(final INode node : array){ if(node != null){ tasks.add(new Callable(){ public Object call() throws Exception{ return node.fold(combinef, reducef, fjtask, fjfork, fjjoin); } }); } } return foldTasks(tasks,combinef,fjtask,fjfork,fjjoin); } static public Object foldTasks(List<Callable> tasks, final IFn combinef, final IFn fjtask, final IFn fjfork, final IFn fjjoin){ if(tasks.isEmpty()) return combinef.invoke(); if(tasks.size() == 1){ Object ret = null; try { return tasks.get(0).call(); } catch(Exception e) { throw Util.sneakyThrow(e); } } List<Callable> t1 = tasks.subList(0,tasks.size()/2); final List<Callable> t2 = tasks.subList(tasks.size()/2, tasks.size()); Object forked = fjfork.invoke(fjtask.invoke(new Callable() { public Object call() throws Exception{ return foldTasks(t2,combinef,fjtask,fjfork,fjjoin); } })); return combinef.invoke(foldTasks(t1,combinef,fjtask,fjfork,fjjoin),fjjoin.invoke(forked)); } private ArrayNode ensureEditable(AtomicReference<Thread> edit){ if(this.edit == edit) return this; return new ArrayNode(edit, count, this.array.clone()); } private ArrayNode editAndSet(AtomicReference<Thread> edit, int i, INode n){ ArrayNode editable = ensureEditable(edit); editable.array[i] = n; return editable; } private INode pack(AtomicReference<Thread> edit, int idx) { Object[] newArray = new Object[2*(count - 1)]; int j = 1; int bitmap = 0; for(int i = 0; i < idx; i++) if (array[i] != null) { newArray[j] = array[i]; bitmap |= 1 << i; j += 2; } for(int i = idx + 1; i < array.length; i++) if (array[i] != null) { newArray[j] = array[i]; bitmap |= 1 << i; j += 2; } return new BitmapIndexedNode(edit, bitmap, newArray); } public INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf){ int idx = mask(hash, shift); INode node = array[idx]; if(node == null) { ArrayNode editable = editAndSet(edit, idx, BitmapIndexedNode.EMPTY.assoc(edit, shift + 5, hash, key, val, addedLeaf)); editable.count++; return editable; } INode n = node.assoc(edit, shift + 5, hash, key, val, addedLeaf); if(n == node) return this; return editAndSet(edit, idx, n); } public INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf){ int idx = mask(hash, shift); INode node = array[idx]; if(node == null) return this; INode n = node.without(edit, shift + 5, hash, key, removedLeaf); if(n == node) return this; if(n == null) { if (count <= 8) // shrink return pack(edit, idx); ArrayNode editable = editAndSet(edit, idx, n); editable.count--; return editable; } return editAndSet(edit, idx, n); } static class Seq extends ASeq { final INode[] nodes; final int i; final ISeq s; static ISeq create(INode[] nodes) { return create(null, nodes, 0, null); } private static ISeq create(IPersistentMap meta, INode[] nodes, int i, ISeq s) { if (s != null) return new Seq(meta, nodes, i, s); for(int j = i; j < nodes.length; j++) if (nodes[j] != null) { ISeq ns = nodes[j].nodeSeq(); if (ns != null) return new Seq(meta, nodes, j + 1, ns); } return null; } private Seq(IPersistentMap meta, INode[] nodes, int i, ISeq s) { super(meta); this.nodes = nodes; this.i = i; this.s = s; } public Obj withMeta(IPersistentMap meta) { return new Seq(meta, nodes, i, s); } public Object first() { return s.first(); } public ISeq next() { return create(null, nodes, i, s.next()); } } static class Iter implements Iterator { private final INode[] array; private final IFn f; private int i = 0; private Iterator nestedIter; private Iter(INode[] array, IFn f){ this.array = array; this.f = f; } public boolean hasNext(){ while(true) { if(nestedIter != null) if(nestedIter.hasNext()) return true; else nestedIter = null; if(i < array.length) { INode node = array[i++]; if (node != null) nestedIter = node.iterator(f); } else return false; } } public Object next(){ if(hasNext()) return nestedIter.next(); else throw new NoSuchElementException(); } public void remove(){ throw new UnsupportedOperationException(); } } } final static class BitmapIndexedNode implements INode{ static final BitmapIndexedNode EMPTY = new BitmapIndexedNode(null, 0, new Object[0]); int bitmap; Object[] array; final AtomicReference<Thread> edit; final int index(int bit){ return Integer.bitCount(bitmap & (bit - 1)); } BitmapIndexedNode(AtomicReference<Thread> edit, int bitmap, Object[] array){ this.bitmap = bitmap; this.array = array; this.edit = edit; } public INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf){ int bit = bitpos(hash, shift); int idx = index(bit); if((bitmap & bit) != 0) { Object keyOrNull = array[2*idx]; Object valOrNode = array[2*idx+1]; if(keyOrNull == null) { INode n = ((INode) valOrNode).assoc(shift + 5, hash, key, val, addedLeaf); if(n == valOrNode) return this; return new BitmapIndexedNode(null, bitmap, cloneAndSet(array, 2*idx+1, n)); } if(Util.equiv(key, keyOrNull)) { if(val == valOrNode) return this; return new BitmapIndexedNode(null, bitmap, cloneAndSet(array, 2*idx+1, val)); } addedLeaf.val = addedLeaf; return new BitmapIndexedNode(null, bitmap, cloneAndSet(array, 2*idx, null, 2*idx+1, createNode(shift + 5, keyOrNull, valOrNode, hash, key, val))); } else { int n = Integer.bitCount(bitmap); if(n >= 16) { INode[] nodes = new INode[32]; int jdx = mask(hash, shift); nodes[jdx] = EMPTY.assoc(shift + 5, hash, key, val, addedLeaf); int j = 0; for(int i = 0; i < 32; i++) if(((bitmap >>> i) & 1) != 0) { if (array[j] == null) nodes[i] = (INode) array[j+1]; else nodes[i] = EMPTY.assoc(shift + 5, hash(array[j]), array[j], array[j+1], addedLeaf); j += 2; } return new ArrayNode(null, n + 1, nodes); } else { Object[] newArray = new Object[2*(n+1)]; System.arraycopy(array, 0, newArray, 0, 2*idx); newArray[2*idx] = key; addedLeaf.val = addedLeaf; newArray[2*idx+1] = val; System.arraycopy(array, 2*idx, newArray, 2*(idx+1), 2*(n-idx)); return new BitmapIndexedNode(null, bitmap | bit, newArray); } } } public INode without(int shift, int hash, Object key){ int bit = bitpos(hash, shift); if((bitmap & bit) == 0) return this; int idx = index(bit); Object keyOrNull = array[2*idx]; Object valOrNode = array[2*idx+1]; if(keyOrNull == null) { INode n = ((INode) valOrNode).without(shift + 5, hash, key); if (n == valOrNode) return this; if (n != null) return new BitmapIndexedNode(null, bitmap, cloneAndSet(array, 2*idx+1, n)); if (bitmap == bit) return null; return new BitmapIndexedNode(null, bitmap ^ bit, removePair(array, idx)); } if(Util.equiv(key, keyOrNull)) // TODO: collapse return new BitmapIndexedNode(null, bitmap ^ bit, removePair(array, idx)); return this; } public IMapEntry find(int shift, int hash, Object key){ int bit = bitpos(hash, shift); if((bitmap & bit) == 0) return null; int idx = index(bit); Object keyOrNull = array[2*idx]; Object valOrNode = array[2*idx+1]; if(keyOrNull == null) return ((INode) valOrNode).find(shift + 5, hash, key); if(Util.equiv(key, keyOrNull)) return (IMapEntry) MapEntry.create(keyOrNull, valOrNode); return null; } public Object find(int shift, int hash, Object key, Object notFound){ int bit = bitpos(hash, shift); if((bitmap & bit) == 0) return notFound; int idx = index(bit); Object keyOrNull = array[2*idx]; Object valOrNode = array[2*idx+1]; if(keyOrNull == null) return ((INode) valOrNode).find(shift + 5, hash, key, notFound); if(Util.equiv(key, keyOrNull)) return valOrNode; return notFound; } public ISeq nodeSeq(){ return NodeSeq.create(array); } public Iterator iterator(IFn f){ return new NodeIter(array, f); } public Object kvreduce(IFn f, Object init){ return NodeSeq.kvreduce(array,f,init); } public Object fold(IFn combinef, IFn reducef, IFn fjtask, IFn fjfork, IFn fjjoin){ return NodeSeq.kvreduce(array, reducef, combinef.invoke()); } private BitmapIndexedNode ensureEditable(AtomicReference<Thread> edit){ if(this.edit == edit) return this; int n = Integer.bitCount(bitmap); Object[] newArray = new Object[n >= 0 ? 2*(n+1) : 4]; // make room for next assoc System.arraycopy(array, 0, newArray, 0, 2*n); return new BitmapIndexedNode(edit, bitmap, newArray); } private BitmapIndexedNode editAndSet(AtomicReference<Thread> edit, int i, Object a) { BitmapIndexedNode editable = ensureEditable(edit); editable.array[i] = a; return editable; } private BitmapIndexedNode editAndSet(AtomicReference<Thread> edit, int i, Object a, int j, Object b) { BitmapIndexedNode editable = ensureEditable(edit); editable.array[i] = a; editable.array[j] = b; return editable; } private BitmapIndexedNode editAndRemovePair(AtomicReference<Thread> edit, int bit, int i) { if (bitmap == bit) return null; BitmapIndexedNode editable = ensureEditable(edit); editable.bitmap ^= bit; System.arraycopy(editable.array, 2*(i+1), editable.array, 2*i, editable.array.length - 2*(i+1)); editable.array[editable.array.length - 2] = null; editable.array[editable.array.length - 1] = null; return editable; } public INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf){ int bit = bitpos(hash, shift); int idx = index(bit); if((bitmap & bit) != 0) { Object keyOrNull = array[2*idx]; Object valOrNode = array[2*idx+1]; if(keyOrNull == null) { INode n = ((INode) valOrNode).assoc(edit, shift + 5, hash, key, val, addedLeaf); if(n == valOrNode) return this; return editAndSet(edit, 2*idx+1, n); } if(Util.equiv(key, keyOrNull)) { if(val == valOrNode) return this; return editAndSet(edit, 2*idx+1, val); } addedLeaf.val = addedLeaf; return editAndSet(edit, 2*idx, null, 2*idx+1, createNode(edit, shift + 5, keyOrNull, valOrNode, hash, key, val)); } else { int n = Integer.bitCount(bitmap); if(n*2 < array.length) { addedLeaf.val = addedLeaf; BitmapIndexedNode editable = ensureEditable(edit); System.arraycopy(editable.array, 2*idx, editable.array, 2*(idx+1), 2*(n-idx)); editable.array[2*idx] = key; editable.array[2*idx+1] = val; editable.bitmap |= bit; return editable; } if(n >= 16) { INode[] nodes = new INode[32]; int jdx = mask(hash, shift); nodes[jdx] = EMPTY.assoc(edit, shift + 5, hash, key, val, addedLeaf); int j = 0; for(int i = 0; i < 32; i++) if(((bitmap >>> i) & 1) != 0) { if (array[j] == null) nodes[i] = (INode) array[j+1]; else nodes[i] = EMPTY.assoc(edit, shift + 5, hash(array[j]), array[j], array[j+1], addedLeaf); j += 2; } return new ArrayNode(edit, n + 1, nodes); } else { Object[] newArray = new Object[2*(n+4)]; System.arraycopy(array, 0, newArray, 0, 2*idx); newArray[2*idx] = key; addedLeaf.val = addedLeaf; newArray[2*idx+1] = val; System.arraycopy(array, 2*idx, newArray, 2*(idx+1), 2*(n-idx)); BitmapIndexedNode editable = ensureEditable(edit); editable.array = newArray; editable.bitmap |= bit; return editable; } } } public INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf){ int bit = bitpos(hash, shift); if((bitmap & bit) == 0) return this; int idx = index(bit); Object keyOrNull = array[2*idx]; Object valOrNode = array[2*idx+1]; if(keyOrNull == null) { INode n = ((INode) valOrNode).without(edit, shift + 5, hash, key, removedLeaf); if (n == valOrNode) return this; if (n != null) return editAndSet(edit, 2*idx+1, n); if (bitmap == bit) return null; return editAndRemovePair(edit, bit, idx); } if(Util.equiv(key, keyOrNull)) { removedLeaf.val = removedLeaf; // TODO: collapse return editAndRemovePair(edit, bit, idx); } return this; } } final static class HashCollisionNode implements INode{ final int hash; int count; Object[] array; final AtomicReference<Thread> edit; HashCollisionNode(AtomicReference<Thread> edit, int hash, int count, Object... array){ this.edit = edit; this.hash = hash; this.count = count; this.array = array; } public INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf){ if(hash == this.hash) { int idx = findIndex(key); if(idx != -1) { if(array[idx + 1] == val) return this; return new HashCollisionNode(null, hash, count, cloneAndSet(array, idx + 1, val)); } Object[] newArray = new Object[2 * (count + 1)]; System.arraycopy(array, 0, newArray, 0, 2 * count); newArray[2 * count] = key; newArray[2 * count + 1] = val; addedLeaf.val = addedLeaf; return new HashCollisionNode(edit, hash, count + 1, newArray); } // nest it in a bitmap node return new BitmapIndexedNode(null, bitpos(this.hash, shift), new Object[] {null, this}) .assoc(shift, hash, key, val, addedLeaf); } public INode without(int shift, int hash, Object key){ int idx = findIndex(key); if(idx == -1) return this; if(count == 1) return null; return new HashCollisionNode(null, hash, count - 1, removePair(array, idx/2)); } public IMapEntry find(int shift, int hash, Object key){ int idx = findIndex(key); if(idx < 0) return null; if(Util.equiv(key, array[idx])) return (IMapEntry) MapEntry.create(array[idx], array[idx+1]); return null; } public Object find(int shift, int hash, Object key, Object notFound){ int idx = findIndex(key); if(idx < 0) return notFound; if(Util.equiv(key, array[idx])) return array[idx+1]; return notFound; } public ISeq nodeSeq(){ return NodeSeq.create(array); } public Iterator iterator(IFn f){ return new NodeIter(array, f); } public Object kvreduce(IFn f, Object init){ return NodeSeq.kvreduce(array,f,init); } public Object fold(IFn combinef, IFn reducef, IFn fjtask, IFn fjfork, IFn fjjoin){ return NodeSeq.kvreduce(array, reducef, combinef.invoke()); } public int findIndex(Object key){ for(int i = 0; i < 2*count; i+=2) { if(Util.equiv(key, array[i])) return i; } return -1; } private HashCollisionNode ensureEditable(AtomicReference<Thread> edit){ if(this.edit == edit) return this; Object[] newArray = new Object[2*(count+1)]; // make room for next assoc System.arraycopy(array, 0, newArray, 0, 2*count); return new HashCollisionNode(edit, hash, count, newArray); } private HashCollisionNode ensureEditable(AtomicReference<Thread> edit, int count, Object[] array){ if(this.edit == edit) { this.array = array; this.count = count; return this; } return new HashCollisionNode(edit, hash, count, array); } private HashCollisionNode editAndSet(AtomicReference<Thread> edit, int i, Object a) { HashCollisionNode editable = ensureEditable(edit); editable.array[i] = a; return editable; } private HashCollisionNode editAndSet(AtomicReference<Thread> edit, int i, Object a, int j, Object b) { HashCollisionNode editable = ensureEditable(edit); editable.array[i] = a; editable.array[j] = b; return editable; } public INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf){ if(hash == this.hash) { int idx = findIndex(key); if(idx != -1) { if(array[idx + 1] == val) return this; return editAndSet(edit, idx+1, val); } if (array.length > 2*count) { addedLeaf.val = addedLeaf; HashCollisionNode editable = editAndSet(edit, 2*count, key, 2*count+1, val); editable.count++; return editable; } Object[] newArray = new Object[array.length + 2]; System.arraycopy(array, 0, newArray, 0, array.length); newArray[array.length] = key; newArray[array.length + 1] = val; addedLeaf.val = addedLeaf; return ensureEditable(edit, count + 1, newArray); } // nest it in a bitmap node return new BitmapIndexedNode(edit, bitpos(this.hash, shift), new Object[] {null, this, null, null}) .assoc(edit, shift, hash, key, val, addedLeaf); } public INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf){ int idx = findIndex(key); if(idx == -1) return this; removedLeaf.val = removedLeaf; if(count == 1) return null; HashCollisionNode editable = ensureEditable(edit); editable.array[idx] = editable.array[2*count-2]; editable.array[idx+1] = editable.array[2*count-1]; editable.array[2*count-2] = editable.array[2*count-1] = null; editable.count--; return editable; } } /* public static void main(String[] args){ try { ArrayList words = new ArrayList(); Scanner s = new Scanner(new File(args[0])); s.useDelimiter(Pattern.compile("\\W")); while(s.hasNext()) { String word = s.next(); words.add(word); } System.out.println("words: " + words.size()); IPersistentMap map = PersistentHashMap.EMPTY; //IPersistentMap map = new PersistentTreeMap(); //Map ht = new Hashtable(); Map ht = new HashMap(); Random rand; System.out.println("Building map"); long startTime = System.nanoTime(); for(Object word5 : words) { map = map.assoc(word5, word5); } rand = new Random(42); IPersistentMap snapshotMap = map; for(int i = 0; i < words.size() / 200; i++) { map = map.without(words.get(rand.nextInt(words.size() / 2))); } long estimatedTime = System.nanoTime() - startTime; System.out.println("count = " + map.count() + ", time: " + estimatedTime / 1000000); System.out.println("Building ht"); startTime = System.nanoTime(); for(Object word1 : words) { ht.put(word1, word1); } rand = new Random(42); for(int i = 0; i < words.size() / 200; i++) { ht.remove(words.get(rand.nextInt(words.size() / 2))); } estimatedTime = System.nanoTime() - startTime; System.out.println("count = " + ht.size() + ", time: " + estimatedTime / 1000000); System.out.println("map lookup"); startTime = System.nanoTime(); int c = 0; for(Object word2 : words) { if(!map.contains(word2)) ++c; } estimatedTime = System.nanoTime() - startTime; System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000); System.out.println("ht lookup"); startTime = System.nanoTime(); c = 0; for(Object word3 : words) { if(!ht.containsKey(word3)) ++c; } estimatedTime = System.nanoTime() - startTime; System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000); System.out.println("snapshotMap lookup"); startTime = System.nanoTime(); c = 0; for(Object word4 : words) { if(!snapshotMap.contains(word4)) ++c; } estimatedTime = System.nanoTime() - startTime; System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000); } catch(FileNotFoundException e) { e.printStackTrace(); } } */ private static INode[] cloneAndSet(INode[] array, int i, INode a) { INode[] clone = array.clone(); clone[i] = a; return clone; } private static Object[] cloneAndSet(Object[] array, int i, Object a) { Object[] clone = array.clone(); clone[i] = a; return clone; } private static Object[] cloneAndSet(Object[] array, int i, Object a, int j, Object b) { Object[] clone = array.clone(); clone[i] = a; clone[j] = b; return clone; } private static Object[] removePair(Object[] array, int i) { Object[] newArray = new Object[array.length - 2]; System.arraycopy(array, 0, newArray, 0, 2*i); System.arraycopy(array, 2*(i+1), newArray, 2*i, newArray.length - 2*i); return newArray; } private static INode createNode(int shift, Object key1, Object val1, int key2hash, Object key2, Object val2) { int key1hash = hash(key1); if(key1hash == key2hash) return new HashCollisionNode(null, key1hash, 2, new Object[] {key1, val1, key2, val2}); Box addedLeaf = new Box(null); AtomicReference<Thread> edit = new AtomicReference Other Java examples (source code examples)Here is a short list of links related to this Java PersistentHashMap.java source code file: |
... this post is sponsored by my books ... | |
#1 New Release! |
FP Best Seller |
Copyright 1998-2021 Alvin Alexander, alvinalexander.com
All Rights Reserved.
A percentage of advertising revenue from
pages under the /java/jwarehouse
URI on this website is
paid back to open source projects.