Mercurial > lasercutter
diff src/clojure/lang/PersistentHashMap.java @ 10:ef7dbbd6452c
added clojure source goodness
| author | Robert McIntyre <rlm@mit.edu> |
|---|---|
| date | Sat, 21 Aug 2010 06:25:44 -0400 |
| parents | |
| children |
line wrap: on
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/src/clojure/lang/PersistentHashMap.java Sat Aug 21 06:25:44 2010 -0400 1.3 @@ -0,0 +1,1054 @@ 1.4 +/** 1.5 + * Copyright (c) Rich Hickey. All rights reserved. 1.6 + * The use and distribution terms for this software are covered by the 1.7 + * Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php) 1.8 + * which can be found in the file epl-v10.html at the root of this distribution. 1.9 + * By using this software in any fashion, you are agreeing to be bound by 1.10 + * the terms of this license. 1.11 + * You must not remove this notice, or any other, from this software. 1.12 + **/ 1.13 + 1.14 +package clojure.lang; 1.15 + 1.16 +import java.io.Serializable; 1.17 +import java.util.Iterator; 1.18 +import java.util.List; 1.19 +import java.util.Map; 1.20 +import java.util.concurrent.atomic.AtomicReference; 1.21 + 1.22 +/* 1.23 + A persistent rendition of Phil Bagwell's Hash Array Mapped Trie 1.24 + 1.25 + Uses path copying for persistence 1.26 + HashCollision leaves vs. extended hashing 1.27 + Node polymorphism vs. conditionals 1.28 + No sub-tree pools or root-resizing 1.29 + Any errors are my own 1.30 + */ 1.31 + 1.32 +public class PersistentHashMap extends APersistentMap implements IEditableCollection, IObj { 1.33 + 1.34 +final int count; 1.35 +final INode root; 1.36 +final boolean hasNull; 1.37 +final Object nullValue; 1.38 +final IPersistentMap _meta; 1.39 + 1.40 +final public static PersistentHashMap EMPTY = new PersistentHashMap(0, null, false, null); 1.41 +final private static Object NOT_FOUND = new Object(); 1.42 + 1.43 +static public IPersistentMap create(Map other){ 1.44 + ITransientMap ret = EMPTY.asTransient(); 1.45 + for(Object o : other.entrySet()) 1.46 + { 1.47 + Map.Entry e = (Entry) o; 1.48 + ret = ret.assoc(e.getKey(), e.getValue()); 1.49 + } 1.50 + return ret.persistent(); 1.51 +} 1.52 + 1.53 +/* 1.54 + * @param init {key1,val1,key2,val2,...} 1.55 + */ 1.56 +public static PersistentHashMap create(Object... init){ 1.57 + ITransientMap ret = EMPTY.asTransient(); 1.58 + for(int i = 0; i < init.length; i += 2) 1.59 + { 1.60 + ret = ret.assoc(init[i], init[i + 1]); 1.61 + } 1.62 + return (PersistentHashMap) ret.persistent(); 1.63 +} 1.64 + 1.65 +public static PersistentHashMap createWithCheck(Object... init){ 1.66 + ITransientMap ret = EMPTY.asTransient(); 1.67 + for(int i = 0; i < init.length; i += 2) 1.68 + { 1.69 + ret = ret.assoc(init[i], init[i + 1]); 1.70 + if(ret.count() != i/2 + 1) 1.71 + throw new IllegalArgumentException("Duplicate key: " + init[i]); 1.72 + } 1.73 + return (PersistentHashMap) ret.persistent(); 1.74 +} 1.75 + 1.76 +static public PersistentHashMap create(ISeq items){ 1.77 + ITransientMap ret = EMPTY.asTransient(); 1.78 + for(; items != null; items = items.next().next()) 1.79 + { 1.80 + if(items.next() == null) 1.81 + throw new IllegalArgumentException(String.format("No value supplied for key: %s", items.first())); 1.82 + ret = ret.assoc(items.first(), RT.second(items)); 1.83 + } 1.84 + return (PersistentHashMap) ret.persistent(); 1.85 +} 1.86 + 1.87 +static public PersistentHashMap createWithCheck(ISeq items){ 1.88 + ITransientMap ret = EMPTY.asTransient(); 1.89 + for(int i=0; items != null; items = items.next().next(), ++i) 1.90 + { 1.91 + if(items.next() == null) 1.92 + throw new IllegalArgumentException(String.format("No value supplied for key: %s", items.first())); 1.93 + ret = ret.assoc(items.first(), RT.second(items)); 1.94 + if(ret.count() != i + 1) 1.95 + throw new IllegalArgumentException("Duplicate key: " + items.first()); 1.96 + } 1.97 + return (PersistentHashMap) ret.persistent(); 1.98 +} 1.99 + 1.100 +/* 1.101 + * @param init {key1,val1,key2,val2,...} 1.102 + */ 1.103 +public static PersistentHashMap create(IPersistentMap meta, Object... init){ 1.104 + return create(init).withMeta(meta); 1.105 +} 1.106 + 1.107 +PersistentHashMap(int count, INode root, boolean hasNull, Object nullValue){ 1.108 + this.count = count; 1.109 + this.root = root; 1.110 + this.hasNull = hasNull; 1.111 + this.nullValue = nullValue; 1.112 + this._meta = null; 1.113 +} 1.114 + 1.115 +public PersistentHashMap(IPersistentMap meta, int count, INode root, boolean hasNull, Object nullValue){ 1.116 + this._meta = meta; 1.117 + this.count = count; 1.118 + this.root = root; 1.119 + this.hasNull = hasNull; 1.120 + this.nullValue = nullValue; 1.121 +} 1.122 + 1.123 +public boolean containsKey(Object key){ 1.124 + if(key == null) 1.125 + return hasNull; 1.126 + return (root != null) ? root.find(0, Util.hash(key), key, NOT_FOUND) != NOT_FOUND : false; 1.127 +} 1.128 + 1.129 +public IMapEntry entryAt(Object key){ 1.130 + if(key == null) 1.131 + return hasNull ? new MapEntry(null, nullValue) : null; 1.132 + return (root != null) ? root.find(0, Util.hash(key), key) : null; 1.133 +} 1.134 + 1.135 +public IPersistentMap assoc(Object key, Object val){ 1.136 + if(key == null) { 1.137 + if(hasNull && val == nullValue) 1.138 + return this; 1.139 + return new PersistentHashMap(meta(), hasNull ? count : count + 1, root, true, val); 1.140 + } 1.141 + Box addedLeaf = new Box(null); 1.142 + INode newroot = (root == null ? BitmapIndexedNode.EMPTY : root) 1.143 + .assoc(0, Util.hash(key), key, val, addedLeaf); 1.144 + if(newroot == root) 1.145 + return this; 1.146 + return new PersistentHashMap(meta(), addedLeaf.val == null ? count : count + 1, newroot, hasNull, nullValue); 1.147 +} 1.148 + 1.149 +public Object valAt(Object key, Object notFound){ 1.150 + if(key == null) 1.151 + return hasNull ? nullValue : notFound; 1.152 + return root != null ? root.find(0, Util.hash(key), key, notFound) : notFound; 1.153 +} 1.154 + 1.155 +public Object valAt(Object key){ 1.156 + return valAt(key, null); 1.157 +} 1.158 + 1.159 +public IPersistentMap assocEx(Object key, Object val) throws Exception{ 1.160 + if(containsKey(key)) 1.161 + throw new Exception("Key already present"); 1.162 + return assoc(key, val); 1.163 +} 1.164 + 1.165 +public IPersistentMap without(Object key){ 1.166 + if(key == null) 1.167 + return hasNull ? new PersistentHashMap(meta(), count - 1, root, false, null) : this; 1.168 + if(root == null) 1.169 + return this; 1.170 + INode newroot = root.without(0, Util.hash(key), key); 1.171 + if(newroot == root) 1.172 + return this; 1.173 + return new PersistentHashMap(meta(), count - 1, newroot, hasNull, nullValue); 1.174 +} 1.175 + 1.176 +public Iterator iterator(){ 1.177 + return new SeqIterator(seq()); 1.178 +} 1.179 + 1.180 +public int count(){ 1.181 + return count; 1.182 +} 1.183 + 1.184 +public ISeq seq(){ 1.185 + ISeq s = root != null ? root.nodeSeq() : null; 1.186 + return hasNull ? new Cons(new MapEntry(null, nullValue), s) : s; 1.187 +} 1.188 + 1.189 +public IPersistentCollection empty(){ 1.190 + return EMPTY.withMeta(meta()); 1.191 +} 1.192 + 1.193 +static int mask(int hash, int shift){ 1.194 + //return ((hash << shift) >>> 27);// & 0x01f; 1.195 + return (hash >>> shift) & 0x01f; 1.196 +} 1.197 + 1.198 +public PersistentHashMap withMeta(IPersistentMap meta){ 1.199 + return new PersistentHashMap(meta, count, root, hasNull, nullValue); 1.200 +} 1.201 + 1.202 +public TransientHashMap asTransient() { 1.203 + return new TransientHashMap(this); 1.204 +} 1.205 + 1.206 +public IPersistentMap meta(){ 1.207 + return _meta; 1.208 +} 1.209 + 1.210 +static final class TransientHashMap extends ATransientMap { 1.211 + AtomicReference<Thread> edit; 1.212 + INode root; 1.213 + int count; 1.214 + boolean hasNull; 1.215 + Object nullValue; 1.216 + final Box leafFlag = new Box(null); 1.217 + 1.218 + 1.219 + TransientHashMap(PersistentHashMap m) { 1.220 + this(new AtomicReference<Thread>(Thread.currentThread()), m.root, m.count, m.hasNull, m.nullValue); 1.221 + } 1.222 + 1.223 + TransientHashMap(AtomicReference<Thread> edit, INode root, int count, boolean hasNull, Object nullValue) { 1.224 + this.edit = edit; 1.225 + this.root = root; 1.226 + this.count = count; 1.227 + this.hasNull = hasNull; 1.228 + this.nullValue = nullValue; 1.229 + } 1.230 + 1.231 + ITransientMap doAssoc(Object key, Object val) { 1.232 + if (key == null) { 1.233 + if (this.nullValue != val) 1.234 + this.nullValue = val; 1.235 + if (!hasNull) { 1.236 + this.count++; 1.237 + this.hasNull = true; 1.238 + } 1.239 + return this; 1.240 + } 1.241 +// Box leafFlag = new Box(null); 1.242 + leafFlag.val = null; 1.243 + INode n = (root == null ? BitmapIndexedNode.EMPTY : root) 1.244 + .assoc(edit, 0, Util.hash(key), key, val, leafFlag); 1.245 + if (n != this.root) 1.246 + this.root = n; 1.247 + if(leafFlag.val != null) this.count++; 1.248 + return this; 1.249 + } 1.250 + 1.251 + ITransientMap doWithout(Object key) { 1.252 + if (key == null) { 1.253 + if (!hasNull) return this; 1.254 + hasNull = false; 1.255 + nullValue = null; 1.256 + this.count--; 1.257 + return this; 1.258 + } 1.259 + if (root == null) return this; 1.260 +// Box leafFlag = new Box(null); 1.261 + leafFlag.val = null; 1.262 + INode n = root.without(edit, 0, Util.hash(key), key, leafFlag); 1.263 + if (n != root) 1.264 + this.root = n; 1.265 + if(leafFlag.val != null) this.count--; 1.266 + return this; 1.267 + } 1.268 + 1.269 + IPersistentMap doPersistent() { 1.270 + edit.set(null); 1.271 + return new PersistentHashMap(count, root, hasNull, nullValue); 1.272 + } 1.273 + 1.274 + Object doValAt(Object key, Object notFound) { 1.275 + if (key == null) 1.276 + if (hasNull) 1.277 + return nullValue; 1.278 + else 1.279 + return notFound; 1.280 + if (root == null) 1.281 + return null; 1.282 + return root.find(0, Util.hash(key), key, notFound); 1.283 + } 1.284 + 1.285 + int doCount() { 1.286 + return count; 1.287 + } 1.288 + 1.289 + void ensureEditable(){ 1.290 + Thread owner = edit.get(); 1.291 + if(owner == Thread.currentThread()) 1.292 + return; 1.293 + if(owner != null) 1.294 + throw new IllegalAccessError("Transient used by non-owner thread"); 1.295 + throw new IllegalAccessError("Transient used after persistent! call"); 1.296 + } 1.297 +} 1.298 + 1.299 +static interface INode extends Serializable { 1.300 + INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf); 1.301 + 1.302 + INode without(int shift, int hash, Object key); 1.303 + 1.304 + IMapEntry find(int shift, int hash, Object key); 1.305 + 1.306 + Object find(int shift, int hash, Object key, Object notFound); 1.307 + 1.308 + ISeq nodeSeq(); 1.309 + 1.310 + INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf); 1.311 + 1.312 + INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf); 1.313 +} 1.314 + 1.315 +final static class ArrayNode implements INode{ 1.316 + int count; 1.317 + final INode[] array; 1.318 + final AtomicReference<Thread> edit; 1.319 + 1.320 + ArrayNode(AtomicReference<Thread> edit, int count, INode[] array){ 1.321 + this.array = array; 1.322 + this.edit = edit; 1.323 + this.count = count; 1.324 + } 1.325 + 1.326 + public INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf){ 1.327 + int idx = mask(hash, shift); 1.328 + INode node = array[idx]; 1.329 + if(node == null) 1.330 + return new ArrayNode(null, count + 1, cloneAndSet(array, idx, BitmapIndexedNode.EMPTY.assoc(shift + 5, hash, key, val, addedLeaf))); 1.331 + INode n = node.assoc(shift + 5, hash, key, val, addedLeaf); 1.332 + if(n == node) 1.333 + return this; 1.334 + return new ArrayNode(null, count, cloneAndSet(array, idx, n)); 1.335 + } 1.336 + 1.337 + public INode without(int shift, int hash, Object key){ 1.338 + int idx = mask(hash, shift); 1.339 + INode node = array[idx]; 1.340 + if(node == null) 1.341 + return this; 1.342 + INode n = node.without(shift + 5, hash, key); 1.343 + if(n == node) 1.344 + return this; 1.345 + if (n == null) { 1.346 + if (count <= 8) // shrink 1.347 + return pack(null, idx); 1.348 + return new ArrayNode(null, count - 1, cloneAndSet(array, idx, n)); 1.349 + } else 1.350 + return new ArrayNode(null, count, cloneAndSet(array, idx, n)); 1.351 + } 1.352 + 1.353 + public IMapEntry find(int shift, int hash, Object key){ 1.354 + int idx = mask(hash, shift); 1.355 + INode node = array[idx]; 1.356 + if(node == null) 1.357 + return null; 1.358 + return node.find(shift + 5, hash, key); 1.359 + } 1.360 + 1.361 + public Object find(int shift, int hash, Object key, Object notFound){ 1.362 + int idx = mask(hash, shift); 1.363 + INode node = array[idx]; 1.364 + if(node == null) 1.365 + return notFound; 1.366 + return node.find(shift + 5, hash, key, notFound); 1.367 + } 1.368 + 1.369 + public ISeq nodeSeq(){ 1.370 + return Seq.create(array); 1.371 + } 1.372 + 1.373 + private ArrayNode ensureEditable(AtomicReference<Thread> edit){ 1.374 + if(this.edit == edit) 1.375 + return this; 1.376 + return new ArrayNode(edit, count, this.array.clone()); 1.377 + } 1.378 + 1.379 + private ArrayNode editAndSet(AtomicReference<Thread> edit, int i, INode n){ 1.380 + ArrayNode editable = ensureEditable(edit); 1.381 + editable.array[i] = n; 1.382 + return editable; 1.383 + } 1.384 + 1.385 + 1.386 + private INode pack(AtomicReference<Thread> edit, int idx) { 1.387 + Object[] newArray = new Object[2*(count - 1)]; 1.388 + int j = 1; 1.389 + int bitmap = 0; 1.390 + for(int i = 0; i < idx; i++) 1.391 + if (array[i] != null) { 1.392 + newArray[j] = array[i]; 1.393 + bitmap |= 1 << i; 1.394 + j += 2; 1.395 + } 1.396 + for(int i = idx + 1; i < array.length; i++) 1.397 + if (array[i] != null) { 1.398 + newArray[j] = array[i]; 1.399 + bitmap |= 1 << i; 1.400 + j += 2; 1.401 + } 1.402 + return new BitmapIndexedNode(edit, bitmap, newArray); 1.403 + } 1.404 + 1.405 + public INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf){ 1.406 + int idx = mask(hash, shift); 1.407 + INode node = array[idx]; 1.408 + if(node == null) { 1.409 + ArrayNode editable = editAndSet(edit, idx, BitmapIndexedNode.EMPTY.assoc(edit, shift + 5, hash, key, val, addedLeaf)); 1.410 + editable.count++; 1.411 + return editable; 1.412 + } 1.413 + INode n = node.assoc(edit, shift + 5, hash, key, val, addedLeaf); 1.414 + if(n == node) 1.415 + return this; 1.416 + return editAndSet(edit, idx, n); 1.417 + } 1.418 + 1.419 + public INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf){ 1.420 + int idx = mask(hash, shift); 1.421 + INode node = array[idx]; 1.422 + if(node == null) 1.423 + return this; 1.424 + INode n = node.without(edit, shift + 5, hash, key, removedLeaf); 1.425 + if(n == node) 1.426 + return this; 1.427 + if(n == null) { 1.428 + if (count <= 8) // shrink 1.429 + return pack(edit, idx); 1.430 + ArrayNode editable = editAndSet(edit, idx, n); 1.431 + editable.count--; 1.432 + return editable; 1.433 + } 1.434 + return editAndSet(edit, idx, n); 1.435 + } 1.436 + 1.437 + static class Seq extends ASeq { 1.438 + final INode[] nodes; 1.439 + final int i; 1.440 + final ISeq s; 1.441 + 1.442 + static ISeq create(INode[] nodes) { 1.443 + return create(null, nodes, 0, null); 1.444 + } 1.445 + 1.446 + private static ISeq create(IPersistentMap meta, INode[] nodes, int i, ISeq s) { 1.447 + if (s != null) 1.448 + return new Seq(meta, nodes, i, s); 1.449 + for(int j = i; j < nodes.length; j++) 1.450 + if (nodes[j] != null) { 1.451 + ISeq ns = nodes[j].nodeSeq(); 1.452 + if (ns != null) 1.453 + return new Seq(meta, nodes, j + 1, ns); 1.454 + } 1.455 + return null; 1.456 + } 1.457 + 1.458 + private Seq(IPersistentMap meta, INode[] nodes, int i, ISeq s) { 1.459 + super(meta); 1.460 + this.nodes = nodes; 1.461 + this.i = i; 1.462 + this.s = s; 1.463 + } 1.464 + 1.465 + public Obj withMeta(IPersistentMap meta) { 1.466 + return new Seq(meta, nodes, i, s); 1.467 + } 1.468 + 1.469 + public Object first() { 1.470 + return s.first(); 1.471 + } 1.472 + 1.473 + public ISeq next() { 1.474 + return create(null, nodes, i, s.next()); 1.475 + } 1.476 + 1.477 + } 1.478 +} 1.479 + 1.480 +final static class BitmapIndexedNode implements INode{ 1.481 + static final BitmapIndexedNode EMPTY = new BitmapIndexedNode(null, 0, new Object[0]); 1.482 + 1.483 + int bitmap; 1.484 + Object[] array; 1.485 + final AtomicReference<Thread> edit; 1.486 + 1.487 + final int index(int bit){ 1.488 + return Integer.bitCount(bitmap & (bit - 1)); 1.489 + } 1.490 + 1.491 + BitmapIndexedNode(AtomicReference<Thread> edit, int bitmap, Object[] array){ 1.492 + this.bitmap = bitmap; 1.493 + this.array = array; 1.494 + this.edit = edit; 1.495 + } 1.496 + 1.497 + public INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf){ 1.498 + int bit = bitpos(hash, shift); 1.499 + int idx = index(bit); 1.500 + if((bitmap & bit) != 0) { 1.501 + Object keyOrNull = array[2*idx]; 1.502 + Object valOrNode = array[2*idx+1]; 1.503 + if(keyOrNull == null) { 1.504 + INode n = ((INode) valOrNode).assoc(shift + 5, hash, key, val, addedLeaf); 1.505 + if(n == valOrNode) 1.506 + return this; 1.507 + return new BitmapIndexedNode(null, bitmap, cloneAndSet(array, 2*idx+1, n)); 1.508 + } 1.509 + if(Util.equals(key, keyOrNull)) { 1.510 + if(val == valOrNode) 1.511 + return this; 1.512 + return new BitmapIndexedNode(null, bitmap, cloneAndSet(array, 2*idx+1, val)); 1.513 + } 1.514 + addedLeaf.val = addedLeaf; 1.515 + return new BitmapIndexedNode(null, bitmap, 1.516 + cloneAndSet(array, 1.517 + 2*idx, null, 1.518 + 2*idx+1, createNode(shift + 5, keyOrNull, valOrNode, hash, key, val))); 1.519 + } else { 1.520 + int n = Integer.bitCount(bitmap); 1.521 + if(n >= 16) { 1.522 + INode[] nodes = new INode[32]; 1.523 + int jdx = mask(hash, shift); 1.524 + nodes[jdx] = EMPTY.assoc(shift + 5, hash, key, val, addedLeaf); 1.525 + int j = 0; 1.526 + for(int i = 0; i < 32; i++) 1.527 + if(((bitmap >>> i) & 1) != 0) { 1.528 + if (array[j] == null) 1.529 + nodes[i] = (INode) array[j+1]; 1.530 + else 1.531 + nodes[i] = EMPTY.assoc(shift + 5, Util.hash(array[j]), array[j], array[j+1], addedLeaf); 1.532 + j += 2; 1.533 + } 1.534 + return new ArrayNode(null, n + 1, nodes); 1.535 + } else { 1.536 + Object[] newArray = new Object[2*(n+1)]; 1.537 + System.arraycopy(array, 0, newArray, 0, 2*idx); 1.538 + newArray[2*idx] = key; 1.539 + addedLeaf.val = addedLeaf; 1.540 + newArray[2*idx+1] = val; 1.541 + System.arraycopy(array, 2*idx, newArray, 2*(idx+1), 2*(n-idx)); 1.542 + return new BitmapIndexedNode(null, bitmap | bit, newArray); 1.543 + } 1.544 + } 1.545 + } 1.546 + 1.547 + public INode without(int shift, int hash, Object key){ 1.548 + int bit = bitpos(hash, shift); 1.549 + if((bitmap & bit) == 0) 1.550 + return this; 1.551 + int idx = index(bit); 1.552 + Object keyOrNull = array[2*idx]; 1.553 + Object valOrNode = array[2*idx+1]; 1.554 + if(keyOrNull == null) { 1.555 + INode n = ((INode) valOrNode).without(shift + 5, hash, key); 1.556 + if (n == valOrNode) 1.557 + return this; 1.558 + if (n != null) 1.559 + return new BitmapIndexedNode(null, bitmap, cloneAndSet(array, 2*idx+1, n)); 1.560 + if (bitmap == bit) 1.561 + return null; 1.562 + return new BitmapIndexedNode(null, bitmap ^ bit, removePair(array, idx)); 1.563 + } 1.564 + if(Util.equals(key, keyOrNull)) 1.565 + // TODO: collapse 1.566 + return new BitmapIndexedNode(null, bitmap ^ bit, removePair(array, idx)); 1.567 + return this; 1.568 + } 1.569 + 1.570 + public IMapEntry find(int shift, int hash, Object key){ 1.571 + int bit = bitpos(hash, shift); 1.572 + if((bitmap & bit) == 0) 1.573 + return null; 1.574 + int idx = index(bit); 1.575 + Object keyOrNull = array[2*idx]; 1.576 + Object valOrNode = array[2*idx+1]; 1.577 + if(keyOrNull == null) 1.578 + return ((INode) valOrNode).find(shift + 5, hash, key); 1.579 + if(Util.equals(key, keyOrNull)) 1.580 + return new MapEntry(keyOrNull, valOrNode); 1.581 + return null; 1.582 + } 1.583 + 1.584 + public Object find(int shift, int hash, Object key, Object notFound){ 1.585 + int bit = bitpos(hash, shift); 1.586 + if((bitmap & bit) == 0) 1.587 + return notFound; 1.588 + int idx = index(bit); 1.589 + Object keyOrNull = array[2*idx]; 1.590 + Object valOrNode = array[2*idx+1]; 1.591 + if(keyOrNull == null) 1.592 + return ((INode) valOrNode).find(shift + 5, hash, key, notFound); 1.593 + if(Util.equals(key, keyOrNull)) 1.594 + return valOrNode; 1.595 + return notFound; 1.596 + } 1.597 + 1.598 + public ISeq nodeSeq(){ 1.599 + return NodeSeq.create(array); 1.600 + } 1.601 + 1.602 + private BitmapIndexedNode ensureEditable(AtomicReference<Thread> edit){ 1.603 + if(this.edit == edit) 1.604 + return this; 1.605 + int n = Integer.bitCount(bitmap); 1.606 + Object[] newArray = new Object[n >= 0 ? 2*(n+1) : 4]; // make room for next assoc 1.607 + System.arraycopy(array, 0, newArray, 0, 2*n); 1.608 + return new BitmapIndexedNode(edit, bitmap, newArray); 1.609 + } 1.610 + 1.611 + private BitmapIndexedNode editAndSet(AtomicReference<Thread> edit, int i, Object a) { 1.612 + BitmapIndexedNode editable = ensureEditable(edit); 1.613 + editable.array[i] = a; 1.614 + return editable; 1.615 + } 1.616 + 1.617 + private BitmapIndexedNode editAndSet(AtomicReference<Thread> edit, int i, Object a, int j, Object b) { 1.618 + BitmapIndexedNode editable = ensureEditable(edit); 1.619 + editable.array[i] = a; 1.620 + editable.array[j] = b; 1.621 + return editable; 1.622 + } 1.623 + 1.624 + private BitmapIndexedNode editAndRemovePair(AtomicReference<Thread> edit, int bit, int i) { 1.625 + if (bitmap == bit) 1.626 + return null; 1.627 + BitmapIndexedNode editable = ensureEditable(edit); 1.628 + editable.bitmap ^= bit; 1.629 + System.arraycopy(editable.array, 2*(i+1), editable.array, 2*i, editable.array.length - 2*(i+1)); 1.630 + editable.array[editable.array.length - 2] = null; 1.631 + editable.array[editable.array.length - 1] = null; 1.632 + return editable; 1.633 + } 1.634 + 1.635 + public INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf){ 1.636 + int bit = bitpos(hash, shift); 1.637 + int idx = index(bit); 1.638 + if((bitmap & bit) != 0) { 1.639 + Object keyOrNull = array[2*idx]; 1.640 + Object valOrNode = array[2*idx+1]; 1.641 + if(keyOrNull == null) { 1.642 + INode n = ((INode) valOrNode).assoc(edit, shift + 5, hash, key, val, addedLeaf); 1.643 + if(n == valOrNode) 1.644 + return this; 1.645 + return editAndSet(edit, 2*idx+1, n); 1.646 + } 1.647 + if(Util.equals(key, keyOrNull)) { 1.648 + if(val == valOrNode) 1.649 + return this; 1.650 + return editAndSet(edit, 2*idx+1, val); 1.651 + } 1.652 + addedLeaf.val = addedLeaf; 1.653 + return editAndSet(edit, 2*idx, null, 2*idx+1, 1.654 + createNode(edit, shift + 5, keyOrNull, valOrNode, hash, key, val)); 1.655 + } else { 1.656 + int n = Integer.bitCount(bitmap); 1.657 + if(n*2 < array.length) { 1.658 + addedLeaf.val = addedLeaf; 1.659 + BitmapIndexedNode editable = ensureEditable(edit); 1.660 + System.arraycopy(editable.array, 2*idx, editable.array, 2*(idx+1), 2*(n-idx)); 1.661 + editable.array[2*idx] = key; 1.662 + editable.array[2*idx+1] = val; 1.663 + editable.bitmap |= bit; 1.664 + return editable; 1.665 + } 1.666 + if(n >= 16) { 1.667 + INode[] nodes = new INode[32]; 1.668 + int jdx = mask(hash, shift); 1.669 + nodes[jdx] = EMPTY.assoc(edit, shift + 5, hash, key, val, addedLeaf); 1.670 + int j = 0; 1.671 + for(int i = 0; i < 32; i++) 1.672 + if(((bitmap >>> i) & 1) != 0) { 1.673 + if (array[j] == null) 1.674 + nodes[i] = (INode) array[j+1]; 1.675 + else 1.676 + nodes[i] = EMPTY.assoc(edit, shift + 5, Util.hash(array[j]), array[j], array[j+1], addedLeaf); 1.677 + j += 2; 1.678 + } 1.679 + return new ArrayNode(edit, n + 1, nodes); 1.680 + } else { 1.681 + Object[] newArray = new Object[2*(n+4)]; 1.682 + System.arraycopy(array, 0, newArray, 0, 2*idx); 1.683 + newArray[2*idx] = key; 1.684 + addedLeaf.val = addedLeaf; 1.685 + newArray[2*idx+1] = val; 1.686 + System.arraycopy(array, 2*idx, newArray, 2*(idx+1), 2*(n-idx)); 1.687 + BitmapIndexedNode editable = ensureEditable(edit); 1.688 + editable.array = newArray; 1.689 + editable.bitmap |= bit; 1.690 + return editable; 1.691 + } 1.692 + } 1.693 + } 1.694 + 1.695 + public INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf){ 1.696 + int bit = bitpos(hash, shift); 1.697 + if((bitmap & bit) == 0) 1.698 + return this; 1.699 + int idx = index(bit); 1.700 + Object keyOrNull = array[2*idx]; 1.701 + Object valOrNode = array[2*idx+1]; 1.702 + if(keyOrNull == null) { 1.703 + INode n = ((INode) valOrNode).without(edit, shift + 5, hash, key, removedLeaf); 1.704 + if (n == valOrNode) 1.705 + return this; 1.706 + if (n != null) 1.707 + return editAndSet(edit, 2*idx+1, n); 1.708 + if (bitmap == bit) 1.709 + return null; 1.710 + removedLeaf.val = removedLeaf; 1.711 + return editAndRemovePair(edit, bit, idx); 1.712 + } 1.713 + if(Util.equals(key, keyOrNull)) { 1.714 + removedLeaf.val = removedLeaf; 1.715 + // TODO: collapse 1.716 + return editAndRemovePair(edit, bit, idx); 1.717 + } 1.718 + return this; 1.719 + } 1.720 +} 1.721 + 1.722 +final static class HashCollisionNode implements INode{ 1.723 + 1.724 + final int hash; 1.725 + int count; 1.726 + Object[] array; 1.727 + final AtomicReference<Thread> edit; 1.728 + 1.729 + HashCollisionNode(AtomicReference<Thread> edit, int hash, int count, Object... array){ 1.730 + this.edit = edit; 1.731 + this.hash = hash; 1.732 + this.count = count; 1.733 + this.array = array; 1.734 + } 1.735 + 1.736 + public INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf){ 1.737 + if(hash == this.hash) { 1.738 + int idx = findIndex(key); 1.739 + if(idx != -1) { 1.740 + if(array[idx + 1] == val) 1.741 + return this; 1.742 + return new HashCollisionNode(null, hash, count, cloneAndSet(array, idx + 1, val)); 1.743 + } 1.744 + Object[] newArray = new Object[array.length + 2]; 1.745 + System.arraycopy(array, 0, newArray, 0, array.length); 1.746 + newArray[array.length] = key; 1.747 + newArray[array.length + 1] = val; 1.748 + addedLeaf.val = addedLeaf; 1.749 + return new HashCollisionNode(edit, hash, count + 1, newArray); 1.750 + } 1.751 + // nest it in a bitmap node 1.752 + return new BitmapIndexedNode(null, bitpos(this.hash, shift), new Object[] {null, this}) 1.753 + .assoc(shift, hash, key, val, addedLeaf); 1.754 + } 1.755 + 1.756 + public INode without(int shift, int hash, Object key){ 1.757 + int idx = findIndex(key); 1.758 + if(idx == -1) 1.759 + return this; 1.760 + if(count == 1) 1.761 + return null; 1.762 + return new HashCollisionNode(null, hash, count - 1, removePair(array, idx/2)); 1.763 + } 1.764 + 1.765 + public IMapEntry find(int shift, int hash, Object key){ 1.766 + int idx = findIndex(key); 1.767 + if(idx < 0) 1.768 + return null; 1.769 + if(Util.equals(key, array[idx])) 1.770 + return new MapEntry(array[idx], array[idx+1]); 1.771 + return null; 1.772 + } 1.773 + 1.774 + public Object find(int shift, int hash, Object key, Object notFound){ 1.775 + int idx = findIndex(key); 1.776 + if(idx < 0) 1.777 + return notFound; 1.778 + if(Util.equals(key, array[idx])) 1.779 + return array[idx+1]; 1.780 + return notFound; 1.781 + } 1.782 + 1.783 + public ISeq nodeSeq(){ 1.784 + return NodeSeq.create(array); 1.785 + } 1.786 + 1.787 + public int findIndex(Object key){ 1.788 + for(int i = 0; i < 2*count; i+=2) 1.789 + { 1.790 + if(Util.equals(key, array[i])) 1.791 + return i; 1.792 + } 1.793 + return -1; 1.794 + } 1.795 + 1.796 + private HashCollisionNode ensureEditable(AtomicReference<Thread> edit){ 1.797 + if(this.edit == edit) 1.798 + return this; 1.799 + return new HashCollisionNode(edit, hash, count, array); 1.800 + } 1.801 + 1.802 + private HashCollisionNode ensureEditable(AtomicReference<Thread> edit, int count, Object[] array){ 1.803 + if(this.edit == edit) { 1.804 + this.array = array; 1.805 + this.count = count; 1.806 + return this; 1.807 + } 1.808 + return new HashCollisionNode(edit, hash, count, array); 1.809 + } 1.810 + 1.811 + private HashCollisionNode editAndSet(AtomicReference<Thread> edit, int i, Object a) { 1.812 + HashCollisionNode editable = ensureEditable(edit); 1.813 + editable.array[i] = a; 1.814 + return editable; 1.815 + } 1.816 + 1.817 + private HashCollisionNode editAndSet(AtomicReference<Thread> edit, int i, Object a, int j, Object b) { 1.818 + HashCollisionNode editable = ensureEditable(edit); 1.819 + editable.array[i] = a; 1.820 + editable.array[j] = b; 1.821 + return editable; 1.822 + } 1.823 + 1.824 + 1.825 + public INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf){ 1.826 + if(hash == this.hash) { 1.827 + int idx = findIndex(key); 1.828 + if(idx != -1) { 1.829 + if(array[idx + 1] == val) 1.830 + return this; 1.831 + return editAndSet(edit, idx+1, val); 1.832 + } 1.833 + if (array.length > 2*count) { 1.834 + addedLeaf.val = addedLeaf; 1.835 + HashCollisionNode editable = editAndSet(edit, 2*count, key, 2*count+1, val); 1.836 + editable.count++; 1.837 + return editable; 1.838 + } 1.839 + Object[] newArray = new Object[array.length + 2]; 1.840 + System.arraycopy(array, 0, newArray, 0, array.length); 1.841 + newArray[array.length] = key; 1.842 + newArray[array.length + 1] = val; 1.843 + addedLeaf.val = addedLeaf; 1.844 + return ensureEditable(edit, count + 1, newArray); 1.845 + } 1.846 + // nest it in a bitmap node 1.847 + return new BitmapIndexedNode(edit, bitpos(this.hash, shift), new Object[] {null, this, null, null}) 1.848 + .assoc(edit, shift, hash, key, val, addedLeaf); 1.849 + } 1.850 + 1.851 + public INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf){ 1.852 + int idx = findIndex(key); 1.853 + if(idx == -1) 1.854 + return this; 1.855 + if(count == 1) 1.856 + return null; 1.857 + HashCollisionNode editable = ensureEditable(edit); 1.858 + editable.array[idx] = editable.array[2*count-2]; 1.859 + editable.array[idx+1] = editable.array[2*count-1]; 1.860 + editable.array[2*count-2] = editable.array[2*count-1] = null; 1.861 + editable.count--; 1.862 + return editable; 1.863 + } 1.864 +} 1.865 + 1.866 +/* 1.867 +public static void main(String[] args){ 1.868 + try 1.869 + { 1.870 + ArrayList words = new ArrayList(); 1.871 + Scanner s = new Scanner(new File(args[0])); 1.872 + s.useDelimiter(Pattern.compile("\\W")); 1.873 + while(s.hasNext()) 1.874 + { 1.875 + String word = s.next(); 1.876 + words.add(word); 1.877 + } 1.878 + System.out.println("words: " + words.size()); 1.879 + IPersistentMap map = PersistentHashMap.EMPTY; 1.880 + //IPersistentMap map = new PersistentTreeMap(); 1.881 + //Map ht = new Hashtable(); 1.882 + Map ht = new HashMap(); 1.883 + Random rand; 1.884 + 1.885 + System.out.println("Building map"); 1.886 + long startTime = System.nanoTime(); 1.887 + for(Object word5 : words) 1.888 + { 1.889 + map = map.assoc(word5, word5); 1.890 + } 1.891 + rand = new Random(42); 1.892 + IPersistentMap snapshotMap = map; 1.893 + for(int i = 0; i < words.size() / 200; i++) 1.894 + { 1.895 + map = map.without(words.get(rand.nextInt(words.size() / 2))); 1.896 + } 1.897 + long estimatedTime = System.nanoTime() - startTime; 1.898 + System.out.println("count = " + map.count() + ", time: " + estimatedTime / 1000000); 1.899 + 1.900 + System.out.println("Building ht"); 1.901 + startTime = System.nanoTime(); 1.902 + for(Object word1 : words) 1.903 + { 1.904 + ht.put(word1, word1); 1.905 + } 1.906 + rand = new Random(42); 1.907 + for(int i = 0; i < words.size() / 200; i++) 1.908 + { 1.909 + ht.remove(words.get(rand.nextInt(words.size() / 2))); 1.910 + } 1.911 + estimatedTime = System.nanoTime() - startTime; 1.912 + System.out.println("count = " + ht.size() + ", time: " + estimatedTime / 1000000); 1.913 + 1.914 + System.out.println("map lookup"); 1.915 + startTime = System.nanoTime(); 1.916 + int c = 0; 1.917 + for(Object word2 : words) 1.918 + { 1.919 + if(!map.contains(word2)) 1.920 + ++c; 1.921 + } 1.922 + estimatedTime = System.nanoTime() - startTime; 1.923 + System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000); 1.924 + System.out.println("ht lookup"); 1.925 + startTime = System.nanoTime(); 1.926 + c = 0; 1.927 + for(Object word3 : words) 1.928 + { 1.929 + if(!ht.containsKey(word3)) 1.930 + ++c; 1.931 + } 1.932 + estimatedTime = System.nanoTime() - startTime; 1.933 + System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000); 1.934 + System.out.println("snapshotMap lookup"); 1.935 + startTime = System.nanoTime(); 1.936 + c = 0; 1.937 + for(Object word4 : words) 1.938 + { 1.939 + if(!snapshotMap.contains(word4)) 1.940 + ++c; 1.941 + } 1.942 + estimatedTime = System.nanoTime() - startTime; 1.943 + System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000); 1.944 + } 1.945 + catch(FileNotFoundException e) 1.946 + { 1.947 + e.printStackTrace(); 1.948 + } 1.949 + 1.950 +} 1.951 +*/ 1.952 + 1.953 +private static INode[] cloneAndSet(INode[] array, int i, INode a) { 1.954 + INode[] clone = array.clone(); 1.955 + clone[i] = a; 1.956 + return clone; 1.957 +} 1.958 + 1.959 +private static Object[] cloneAndSet(Object[] array, int i, Object a) { 1.960 + Object[] clone = array.clone(); 1.961 + clone[i] = a; 1.962 + return clone; 1.963 +} 1.964 + 1.965 +private static Object[] cloneAndSet(Object[] array, int i, Object a, int j, Object b) { 1.966 + Object[] clone = array.clone(); 1.967 + clone[i] = a; 1.968 + clone[j] = b; 1.969 + return clone; 1.970 +} 1.971 + 1.972 +private static Object[] removePair(Object[] array, int i) { 1.973 + Object[] newArray = new Object[array.length - 2]; 1.974 + System.arraycopy(array, 0, newArray, 0, 2*i); 1.975 + System.arraycopy(array, 2*(i+1), newArray, 2*i, newArray.length - 2*i); 1.976 + return newArray; 1.977 +} 1.978 + 1.979 +private static INode createNode(int shift, Object key1, Object val1, int key2hash, Object key2, Object val2) { 1.980 + int key1hash = Util.hash(key1); 1.981 + if(key1hash == key2hash) 1.982 + return new HashCollisionNode(null, key1hash, 2, new Object[] {key1, val1, key2, val2}); 1.983 + Box _ = new Box(null); 1.984 + AtomicReference<Thread> edit = new AtomicReference<Thread>(); 1.985 + return BitmapIndexedNode.EMPTY 1.986 + .assoc(edit, shift, key1hash, key1, val1, _) 1.987 + .assoc(edit, shift, key2hash, key2, val2, _); 1.988 +} 1.989 + 1.990 +private static INode createNode(AtomicReference<Thread> edit, int shift, Object key1, Object val1, int key2hash, Object key2, Object val2) { 1.991 + int key1hash = Util.hash(key1); 1.992 + if(key1hash == key2hash) 1.993 + return new HashCollisionNode(null, key1hash, 2, new Object[] {key1, val1, key2, val2}); 1.994 + Box _ = new Box(null); 1.995 + return BitmapIndexedNode.EMPTY 1.996 + .assoc(edit, shift, key1hash, key1, val1, _) 1.997 + .assoc(edit, shift, key2hash, key2, val2, _); 1.998 +} 1.999 + 1.1000 +private static int bitpos(int hash, int shift){ 1.1001 + return 1 << mask(hash, shift); 1.1002 +} 1.1003 + 1.1004 +static final class NodeSeq extends ASeq { 1.1005 + final Object[] array; 1.1006 + final int i; 1.1007 + final ISeq s; 1.1008 + 1.1009 + NodeSeq(Object[] array, int i) { 1.1010 + this(null, array, i, null); 1.1011 + } 1.1012 + 1.1013 + static ISeq create(Object[] array) { 1.1014 + return create(array, 0, null); 1.1015 + } 1.1016 + 1.1017 + private static ISeq create(Object[] array, int i, ISeq s) { 1.1018 + if(s != null) 1.1019 + return new NodeSeq(null, array, i, s); 1.1020 + for(int j = i; j < array.length; j+=2) { 1.1021 + if(array[j] != null) 1.1022 + return new NodeSeq(null, array, j, null); 1.1023 + INode node = (INode) array[j+1]; 1.1024 + if (node != null) { 1.1025 + ISeq nodeSeq = node.nodeSeq(); 1.1026 + if(nodeSeq != null) 1.1027 + return new NodeSeq(null, array, j + 2, nodeSeq); 1.1028 + } 1.1029 + } 1.1030 + return null; 1.1031 + } 1.1032 + 1.1033 + NodeSeq(IPersistentMap meta, Object[] array, int i, ISeq s) { 1.1034 + super(meta); 1.1035 + this.array = array; 1.1036 + this.i = i; 1.1037 + this.s = s; 1.1038 + } 1.1039 + 1.1040 + public Obj withMeta(IPersistentMap meta) { 1.1041 + return new NodeSeq(meta, array, i, s); 1.1042 + } 1.1043 + 1.1044 + public Object first() { 1.1045 + if(s != null) 1.1046 + return s.first(); 1.1047 + return new MapEntry(array[i], array[i+1]); 1.1048 + } 1.1049 + 1.1050 + public ISeq next() { 1.1051 + if(s != null) 1.1052 + return create(array, i, s.next()); 1.1053 + return create(array, i + 2, null); 1.1054 + } 1.1055 +} 1.1056 + 1.1057 +} 1.1058 \ No newline at end of file