Mercurial > lasercutter
comparison 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 |
comparison
equal
deleted
inserted
replaced
9:35cf337adfcf | 10:ef7dbbd6452c |
---|---|
1 /** | |
2 * Copyright (c) Rich Hickey. All rights reserved. | |
3 * The use and distribution terms for this software are covered by the | |
4 * Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php) | |
5 * which can be found in the file epl-v10.html at the root of this distribution. | |
6 * By using this software in any fashion, you are agreeing to be bound by | |
7 * the terms of this license. | |
8 * You must not remove this notice, or any other, from this software. | |
9 **/ | |
10 | |
11 package clojure.lang; | |
12 | |
13 import java.io.Serializable; | |
14 import java.util.Iterator; | |
15 import java.util.List; | |
16 import java.util.Map; | |
17 import java.util.concurrent.atomic.AtomicReference; | |
18 | |
19 /* | |
20 A persistent rendition of Phil Bagwell's Hash Array Mapped Trie | |
21 | |
22 Uses path copying for persistence | |
23 HashCollision leaves vs. extended hashing | |
24 Node polymorphism vs. conditionals | |
25 No sub-tree pools or root-resizing | |
26 Any errors are my own | |
27 */ | |
28 | |
29 public class PersistentHashMap extends APersistentMap implements IEditableCollection, IObj { | |
30 | |
31 final int count; | |
32 final INode root; | |
33 final boolean hasNull; | |
34 final Object nullValue; | |
35 final IPersistentMap _meta; | |
36 | |
37 final public static PersistentHashMap EMPTY = new PersistentHashMap(0, null, false, null); | |
38 final private static Object NOT_FOUND = new Object(); | |
39 | |
40 static public IPersistentMap create(Map other){ | |
41 ITransientMap ret = EMPTY.asTransient(); | |
42 for(Object o : other.entrySet()) | |
43 { | |
44 Map.Entry e = (Entry) o; | |
45 ret = ret.assoc(e.getKey(), e.getValue()); | |
46 } | |
47 return ret.persistent(); | |
48 } | |
49 | |
50 /* | |
51 * @param init {key1,val1,key2,val2,...} | |
52 */ | |
53 public static PersistentHashMap create(Object... init){ | |
54 ITransientMap ret = EMPTY.asTransient(); | |
55 for(int i = 0; i < init.length; i += 2) | |
56 { | |
57 ret = ret.assoc(init[i], init[i + 1]); | |
58 } | |
59 return (PersistentHashMap) ret.persistent(); | |
60 } | |
61 | |
62 public static PersistentHashMap createWithCheck(Object... init){ | |
63 ITransientMap ret = EMPTY.asTransient(); | |
64 for(int i = 0; i < init.length; i += 2) | |
65 { | |
66 ret = ret.assoc(init[i], init[i + 1]); | |
67 if(ret.count() != i/2 + 1) | |
68 throw new IllegalArgumentException("Duplicate key: " + init[i]); | |
69 } | |
70 return (PersistentHashMap) ret.persistent(); | |
71 } | |
72 | |
73 static public PersistentHashMap create(ISeq items){ | |
74 ITransientMap ret = EMPTY.asTransient(); | |
75 for(; items != null; items = items.next().next()) | |
76 { | |
77 if(items.next() == null) | |
78 throw new IllegalArgumentException(String.format("No value supplied for key: %s", items.first())); | |
79 ret = ret.assoc(items.first(), RT.second(items)); | |
80 } | |
81 return (PersistentHashMap) ret.persistent(); | |
82 } | |
83 | |
84 static public PersistentHashMap createWithCheck(ISeq items){ | |
85 ITransientMap ret = EMPTY.asTransient(); | |
86 for(int i=0; items != null; items = items.next().next(), ++i) | |
87 { | |
88 if(items.next() == null) | |
89 throw new IllegalArgumentException(String.format("No value supplied for key: %s", items.first())); | |
90 ret = ret.assoc(items.first(), RT.second(items)); | |
91 if(ret.count() != i + 1) | |
92 throw new IllegalArgumentException("Duplicate key: " + items.first()); | |
93 } | |
94 return (PersistentHashMap) ret.persistent(); | |
95 } | |
96 | |
97 /* | |
98 * @param init {key1,val1,key2,val2,...} | |
99 */ | |
100 public static PersistentHashMap create(IPersistentMap meta, Object... init){ | |
101 return create(init).withMeta(meta); | |
102 } | |
103 | |
104 PersistentHashMap(int count, INode root, boolean hasNull, Object nullValue){ | |
105 this.count = count; | |
106 this.root = root; | |
107 this.hasNull = hasNull; | |
108 this.nullValue = nullValue; | |
109 this._meta = null; | |
110 } | |
111 | |
112 public PersistentHashMap(IPersistentMap meta, int count, INode root, boolean hasNull, Object nullValue){ | |
113 this._meta = meta; | |
114 this.count = count; | |
115 this.root = root; | |
116 this.hasNull = hasNull; | |
117 this.nullValue = nullValue; | |
118 } | |
119 | |
120 public boolean containsKey(Object key){ | |
121 if(key == null) | |
122 return hasNull; | |
123 return (root != null) ? root.find(0, Util.hash(key), key, NOT_FOUND) != NOT_FOUND : false; | |
124 } | |
125 | |
126 public IMapEntry entryAt(Object key){ | |
127 if(key == null) | |
128 return hasNull ? new MapEntry(null, nullValue) : null; | |
129 return (root != null) ? root.find(0, Util.hash(key), key) : null; | |
130 } | |
131 | |
132 public IPersistentMap assoc(Object key, Object val){ | |
133 if(key == null) { | |
134 if(hasNull && val == nullValue) | |
135 return this; | |
136 return new PersistentHashMap(meta(), hasNull ? count : count + 1, root, true, val); | |
137 } | |
138 Box addedLeaf = new Box(null); | |
139 INode newroot = (root == null ? BitmapIndexedNode.EMPTY : root) | |
140 .assoc(0, Util.hash(key), key, val, addedLeaf); | |
141 if(newroot == root) | |
142 return this; | |
143 return new PersistentHashMap(meta(), addedLeaf.val == null ? count : count + 1, newroot, hasNull, nullValue); | |
144 } | |
145 | |
146 public Object valAt(Object key, Object notFound){ | |
147 if(key == null) | |
148 return hasNull ? nullValue : notFound; | |
149 return root != null ? root.find(0, Util.hash(key), key, notFound) : notFound; | |
150 } | |
151 | |
152 public Object valAt(Object key){ | |
153 return valAt(key, null); | |
154 } | |
155 | |
156 public IPersistentMap assocEx(Object key, Object val) throws Exception{ | |
157 if(containsKey(key)) | |
158 throw new Exception("Key already present"); | |
159 return assoc(key, val); | |
160 } | |
161 | |
162 public IPersistentMap without(Object key){ | |
163 if(key == null) | |
164 return hasNull ? new PersistentHashMap(meta(), count - 1, root, false, null) : this; | |
165 if(root == null) | |
166 return this; | |
167 INode newroot = root.without(0, Util.hash(key), key); | |
168 if(newroot == root) | |
169 return this; | |
170 return new PersistentHashMap(meta(), count - 1, newroot, hasNull, nullValue); | |
171 } | |
172 | |
173 public Iterator iterator(){ | |
174 return new SeqIterator(seq()); | |
175 } | |
176 | |
177 public int count(){ | |
178 return count; | |
179 } | |
180 | |
181 public ISeq seq(){ | |
182 ISeq s = root != null ? root.nodeSeq() : null; | |
183 return hasNull ? new Cons(new MapEntry(null, nullValue), s) : s; | |
184 } | |
185 | |
186 public IPersistentCollection empty(){ | |
187 return EMPTY.withMeta(meta()); | |
188 } | |
189 | |
190 static int mask(int hash, int shift){ | |
191 //return ((hash << shift) >>> 27);// & 0x01f; | |
192 return (hash >>> shift) & 0x01f; | |
193 } | |
194 | |
195 public PersistentHashMap withMeta(IPersistentMap meta){ | |
196 return new PersistentHashMap(meta, count, root, hasNull, nullValue); | |
197 } | |
198 | |
199 public TransientHashMap asTransient() { | |
200 return new TransientHashMap(this); | |
201 } | |
202 | |
203 public IPersistentMap meta(){ | |
204 return _meta; | |
205 } | |
206 | |
207 static final class TransientHashMap extends ATransientMap { | |
208 AtomicReference<Thread> edit; | |
209 INode root; | |
210 int count; | |
211 boolean hasNull; | |
212 Object nullValue; | |
213 final Box leafFlag = new Box(null); | |
214 | |
215 | |
216 TransientHashMap(PersistentHashMap m) { | |
217 this(new AtomicReference<Thread>(Thread.currentThread()), m.root, m.count, m.hasNull, m.nullValue); | |
218 } | |
219 | |
220 TransientHashMap(AtomicReference<Thread> edit, INode root, int count, boolean hasNull, Object nullValue) { | |
221 this.edit = edit; | |
222 this.root = root; | |
223 this.count = count; | |
224 this.hasNull = hasNull; | |
225 this.nullValue = nullValue; | |
226 } | |
227 | |
228 ITransientMap doAssoc(Object key, Object val) { | |
229 if (key == null) { | |
230 if (this.nullValue != val) | |
231 this.nullValue = val; | |
232 if (!hasNull) { | |
233 this.count++; | |
234 this.hasNull = true; | |
235 } | |
236 return this; | |
237 } | |
238 // Box leafFlag = new Box(null); | |
239 leafFlag.val = null; | |
240 INode n = (root == null ? BitmapIndexedNode.EMPTY : root) | |
241 .assoc(edit, 0, Util.hash(key), key, val, leafFlag); | |
242 if (n != this.root) | |
243 this.root = n; | |
244 if(leafFlag.val != null) this.count++; | |
245 return this; | |
246 } | |
247 | |
248 ITransientMap doWithout(Object key) { | |
249 if (key == null) { | |
250 if (!hasNull) return this; | |
251 hasNull = false; | |
252 nullValue = null; | |
253 this.count--; | |
254 return this; | |
255 } | |
256 if (root == null) return this; | |
257 // Box leafFlag = new Box(null); | |
258 leafFlag.val = null; | |
259 INode n = root.without(edit, 0, Util.hash(key), key, leafFlag); | |
260 if (n != root) | |
261 this.root = n; | |
262 if(leafFlag.val != null) this.count--; | |
263 return this; | |
264 } | |
265 | |
266 IPersistentMap doPersistent() { | |
267 edit.set(null); | |
268 return new PersistentHashMap(count, root, hasNull, nullValue); | |
269 } | |
270 | |
271 Object doValAt(Object key, Object notFound) { | |
272 if (key == null) | |
273 if (hasNull) | |
274 return nullValue; | |
275 else | |
276 return notFound; | |
277 if (root == null) | |
278 return null; | |
279 return root.find(0, Util.hash(key), key, notFound); | |
280 } | |
281 | |
282 int doCount() { | |
283 return count; | |
284 } | |
285 | |
286 void ensureEditable(){ | |
287 Thread owner = edit.get(); | |
288 if(owner == Thread.currentThread()) | |
289 return; | |
290 if(owner != null) | |
291 throw new IllegalAccessError("Transient used by non-owner thread"); | |
292 throw new IllegalAccessError("Transient used after persistent! call"); | |
293 } | |
294 } | |
295 | |
296 static interface INode extends Serializable { | |
297 INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf); | |
298 | |
299 INode without(int shift, int hash, Object key); | |
300 | |
301 IMapEntry find(int shift, int hash, Object key); | |
302 | |
303 Object find(int shift, int hash, Object key, Object notFound); | |
304 | |
305 ISeq nodeSeq(); | |
306 | |
307 INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf); | |
308 | |
309 INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf); | |
310 } | |
311 | |
312 final static class ArrayNode implements INode{ | |
313 int count; | |
314 final INode[] array; | |
315 final AtomicReference<Thread> edit; | |
316 | |
317 ArrayNode(AtomicReference<Thread> edit, int count, INode[] array){ | |
318 this.array = array; | |
319 this.edit = edit; | |
320 this.count = count; | |
321 } | |
322 | |
323 public INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf){ | |
324 int idx = mask(hash, shift); | |
325 INode node = array[idx]; | |
326 if(node == null) | |
327 return new ArrayNode(null, count + 1, cloneAndSet(array, idx, BitmapIndexedNode.EMPTY.assoc(shift + 5, hash, key, val, addedLeaf))); | |
328 INode n = node.assoc(shift + 5, hash, key, val, addedLeaf); | |
329 if(n == node) | |
330 return this; | |
331 return new ArrayNode(null, count, cloneAndSet(array, idx, n)); | |
332 } | |
333 | |
334 public INode without(int shift, int hash, Object key){ | |
335 int idx = mask(hash, shift); | |
336 INode node = array[idx]; | |
337 if(node == null) | |
338 return this; | |
339 INode n = node.without(shift + 5, hash, key); | |
340 if(n == node) | |
341 return this; | |
342 if (n == null) { | |
343 if (count <= 8) // shrink | |
344 return pack(null, idx); | |
345 return new ArrayNode(null, count - 1, cloneAndSet(array, idx, n)); | |
346 } else | |
347 return new ArrayNode(null, count, cloneAndSet(array, idx, n)); | |
348 } | |
349 | |
350 public IMapEntry find(int shift, int hash, Object key){ | |
351 int idx = mask(hash, shift); | |
352 INode node = array[idx]; | |
353 if(node == null) | |
354 return null; | |
355 return node.find(shift + 5, hash, key); | |
356 } | |
357 | |
358 public Object find(int shift, int hash, Object key, Object notFound){ | |
359 int idx = mask(hash, shift); | |
360 INode node = array[idx]; | |
361 if(node == null) | |
362 return notFound; | |
363 return node.find(shift + 5, hash, key, notFound); | |
364 } | |
365 | |
366 public ISeq nodeSeq(){ | |
367 return Seq.create(array); | |
368 } | |
369 | |
370 private ArrayNode ensureEditable(AtomicReference<Thread> edit){ | |
371 if(this.edit == edit) | |
372 return this; | |
373 return new ArrayNode(edit, count, this.array.clone()); | |
374 } | |
375 | |
376 private ArrayNode editAndSet(AtomicReference<Thread> edit, int i, INode n){ | |
377 ArrayNode editable = ensureEditable(edit); | |
378 editable.array[i] = n; | |
379 return editable; | |
380 } | |
381 | |
382 | |
383 private INode pack(AtomicReference<Thread> edit, int idx) { | |
384 Object[] newArray = new Object[2*(count - 1)]; | |
385 int j = 1; | |
386 int bitmap = 0; | |
387 for(int i = 0; i < idx; i++) | |
388 if (array[i] != null) { | |
389 newArray[j] = array[i]; | |
390 bitmap |= 1 << i; | |
391 j += 2; | |
392 } | |
393 for(int i = idx + 1; i < array.length; i++) | |
394 if (array[i] != null) { | |
395 newArray[j] = array[i]; | |
396 bitmap |= 1 << i; | |
397 j += 2; | |
398 } | |
399 return new BitmapIndexedNode(edit, bitmap, newArray); | |
400 } | |
401 | |
402 public INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf){ | |
403 int idx = mask(hash, shift); | |
404 INode node = array[idx]; | |
405 if(node == null) { | |
406 ArrayNode editable = editAndSet(edit, idx, BitmapIndexedNode.EMPTY.assoc(edit, shift + 5, hash, key, val, addedLeaf)); | |
407 editable.count++; | |
408 return editable; | |
409 } | |
410 INode n = node.assoc(edit, shift + 5, hash, key, val, addedLeaf); | |
411 if(n == node) | |
412 return this; | |
413 return editAndSet(edit, idx, n); | |
414 } | |
415 | |
416 public INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf){ | |
417 int idx = mask(hash, shift); | |
418 INode node = array[idx]; | |
419 if(node == null) | |
420 return this; | |
421 INode n = node.without(edit, shift + 5, hash, key, removedLeaf); | |
422 if(n == node) | |
423 return this; | |
424 if(n == null) { | |
425 if (count <= 8) // shrink | |
426 return pack(edit, idx); | |
427 ArrayNode editable = editAndSet(edit, idx, n); | |
428 editable.count--; | |
429 return editable; | |
430 } | |
431 return editAndSet(edit, idx, n); | |
432 } | |
433 | |
434 static class Seq extends ASeq { | |
435 final INode[] nodes; | |
436 final int i; | |
437 final ISeq s; | |
438 | |
439 static ISeq create(INode[] nodes) { | |
440 return create(null, nodes, 0, null); | |
441 } | |
442 | |
443 private static ISeq create(IPersistentMap meta, INode[] nodes, int i, ISeq s) { | |
444 if (s != null) | |
445 return new Seq(meta, nodes, i, s); | |
446 for(int j = i; j < nodes.length; j++) | |
447 if (nodes[j] != null) { | |
448 ISeq ns = nodes[j].nodeSeq(); | |
449 if (ns != null) | |
450 return new Seq(meta, nodes, j + 1, ns); | |
451 } | |
452 return null; | |
453 } | |
454 | |
455 private Seq(IPersistentMap meta, INode[] nodes, int i, ISeq s) { | |
456 super(meta); | |
457 this.nodes = nodes; | |
458 this.i = i; | |
459 this.s = s; | |
460 } | |
461 | |
462 public Obj withMeta(IPersistentMap meta) { | |
463 return new Seq(meta, nodes, i, s); | |
464 } | |
465 | |
466 public Object first() { | |
467 return s.first(); | |
468 } | |
469 | |
470 public ISeq next() { | |
471 return create(null, nodes, i, s.next()); | |
472 } | |
473 | |
474 } | |
475 } | |
476 | |
477 final static class BitmapIndexedNode implements INode{ | |
478 static final BitmapIndexedNode EMPTY = new BitmapIndexedNode(null, 0, new Object[0]); | |
479 | |
480 int bitmap; | |
481 Object[] array; | |
482 final AtomicReference<Thread> edit; | |
483 | |
484 final int index(int bit){ | |
485 return Integer.bitCount(bitmap & (bit - 1)); | |
486 } | |
487 | |
488 BitmapIndexedNode(AtomicReference<Thread> edit, int bitmap, Object[] array){ | |
489 this.bitmap = bitmap; | |
490 this.array = array; | |
491 this.edit = edit; | |
492 } | |
493 | |
494 public INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf){ | |
495 int bit = bitpos(hash, shift); | |
496 int idx = index(bit); | |
497 if((bitmap & bit) != 0) { | |
498 Object keyOrNull = array[2*idx]; | |
499 Object valOrNode = array[2*idx+1]; | |
500 if(keyOrNull == null) { | |
501 INode n = ((INode) valOrNode).assoc(shift + 5, hash, key, val, addedLeaf); | |
502 if(n == valOrNode) | |
503 return this; | |
504 return new BitmapIndexedNode(null, bitmap, cloneAndSet(array, 2*idx+1, n)); | |
505 } | |
506 if(Util.equals(key, keyOrNull)) { | |
507 if(val == valOrNode) | |
508 return this; | |
509 return new BitmapIndexedNode(null, bitmap, cloneAndSet(array, 2*idx+1, val)); | |
510 } | |
511 addedLeaf.val = addedLeaf; | |
512 return new BitmapIndexedNode(null, bitmap, | |
513 cloneAndSet(array, | |
514 2*idx, null, | |
515 2*idx+1, createNode(shift + 5, keyOrNull, valOrNode, hash, key, val))); | |
516 } else { | |
517 int n = Integer.bitCount(bitmap); | |
518 if(n >= 16) { | |
519 INode[] nodes = new INode[32]; | |
520 int jdx = mask(hash, shift); | |
521 nodes[jdx] = EMPTY.assoc(shift + 5, hash, key, val, addedLeaf); | |
522 int j = 0; | |
523 for(int i = 0; i < 32; i++) | |
524 if(((bitmap >>> i) & 1) != 0) { | |
525 if (array[j] == null) | |
526 nodes[i] = (INode) array[j+1]; | |
527 else | |
528 nodes[i] = EMPTY.assoc(shift + 5, Util.hash(array[j]), array[j], array[j+1], addedLeaf); | |
529 j += 2; | |
530 } | |
531 return new ArrayNode(null, n + 1, nodes); | |
532 } else { | |
533 Object[] newArray = new Object[2*(n+1)]; | |
534 System.arraycopy(array, 0, newArray, 0, 2*idx); | |
535 newArray[2*idx] = key; | |
536 addedLeaf.val = addedLeaf; | |
537 newArray[2*idx+1] = val; | |
538 System.arraycopy(array, 2*idx, newArray, 2*(idx+1), 2*(n-idx)); | |
539 return new BitmapIndexedNode(null, bitmap | bit, newArray); | |
540 } | |
541 } | |
542 } | |
543 | |
544 public INode without(int shift, int hash, Object key){ | |
545 int bit = bitpos(hash, shift); | |
546 if((bitmap & bit) == 0) | |
547 return this; | |
548 int idx = index(bit); | |
549 Object keyOrNull = array[2*idx]; | |
550 Object valOrNode = array[2*idx+1]; | |
551 if(keyOrNull == null) { | |
552 INode n = ((INode) valOrNode).without(shift + 5, hash, key); | |
553 if (n == valOrNode) | |
554 return this; | |
555 if (n != null) | |
556 return new BitmapIndexedNode(null, bitmap, cloneAndSet(array, 2*idx+1, n)); | |
557 if (bitmap == bit) | |
558 return null; | |
559 return new BitmapIndexedNode(null, bitmap ^ bit, removePair(array, idx)); | |
560 } | |
561 if(Util.equals(key, keyOrNull)) | |
562 // TODO: collapse | |
563 return new BitmapIndexedNode(null, bitmap ^ bit, removePair(array, idx)); | |
564 return this; | |
565 } | |
566 | |
567 public IMapEntry find(int shift, int hash, Object key){ | |
568 int bit = bitpos(hash, shift); | |
569 if((bitmap & bit) == 0) | |
570 return null; | |
571 int idx = index(bit); | |
572 Object keyOrNull = array[2*idx]; | |
573 Object valOrNode = array[2*idx+1]; | |
574 if(keyOrNull == null) | |
575 return ((INode) valOrNode).find(shift + 5, hash, key); | |
576 if(Util.equals(key, keyOrNull)) | |
577 return new MapEntry(keyOrNull, valOrNode); | |
578 return null; | |
579 } | |
580 | |
581 public Object find(int shift, int hash, Object key, Object notFound){ | |
582 int bit = bitpos(hash, shift); | |
583 if((bitmap & bit) == 0) | |
584 return notFound; | |
585 int idx = index(bit); | |
586 Object keyOrNull = array[2*idx]; | |
587 Object valOrNode = array[2*idx+1]; | |
588 if(keyOrNull == null) | |
589 return ((INode) valOrNode).find(shift + 5, hash, key, notFound); | |
590 if(Util.equals(key, keyOrNull)) | |
591 return valOrNode; | |
592 return notFound; | |
593 } | |
594 | |
595 public ISeq nodeSeq(){ | |
596 return NodeSeq.create(array); | |
597 } | |
598 | |
599 private BitmapIndexedNode ensureEditable(AtomicReference<Thread> edit){ | |
600 if(this.edit == edit) | |
601 return this; | |
602 int n = Integer.bitCount(bitmap); | |
603 Object[] newArray = new Object[n >= 0 ? 2*(n+1) : 4]; // make room for next assoc | |
604 System.arraycopy(array, 0, newArray, 0, 2*n); | |
605 return new BitmapIndexedNode(edit, bitmap, newArray); | |
606 } | |
607 | |
608 private BitmapIndexedNode editAndSet(AtomicReference<Thread> edit, int i, Object a) { | |
609 BitmapIndexedNode editable = ensureEditable(edit); | |
610 editable.array[i] = a; | |
611 return editable; | |
612 } | |
613 | |
614 private BitmapIndexedNode editAndSet(AtomicReference<Thread> edit, int i, Object a, int j, Object b) { | |
615 BitmapIndexedNode editable = ensureEditable(edit); | |
616 editable.array[i] = a; | |
617 editable.array[j] = b; | |
618 return editable; | |
619 } | |
620 | |
621 private BitmapIndexedNode editAndRemovePair(AtomicReference<Thread> edit, int bit, int i) { | |
622 if (bitmap == bit) | |
623 return null; | |
624 BitmapIndexedNode editable = ensureEditable(edit); | |
625 editable.bitmap ^= bit; | |
626 System.arraycopy(editable.array, 2*(i+1), editable.array, 2*i, editable.array.length - 2*(i+1)); | |
627 editable.array[editable.array.length - 2] = null; | |
628 editable.array[editable.array.length - 1] = null; | |
629 return editable; | |
630 } | |
631 | |
632 public INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf){ | |
633 int bit = bitpos(hash, shift); | |
634 int idx = index(bit); | |
635 if((bitmap & bit) != 0) { | |
636 Object keyOrNull = array[2*idx]; | |
637 Object valOrNode = array[2*idx+1]; | |
638 if(keyOrNull == null) { | |
639 INode n = ((INode) valOrNode).assoc(edit, shift + 5, hash, key, val, addedLeaf); | |
640 if(n == valOrNode) | |
641 return this; | |
642 return editAndSet(edit, 2*idx+1, n); | |
643 } | |
644 if(Util.equals(key, keyOrNull)) { | |
645 if(val == valOrNode) | |
646 return this; | |
647 return editAndSet(edit, 2*idx+1, val); | |
648 } | |
649 addedLeaf.val = addedLeaf; | |
650 return editAndSet(edit, 2*idx, null, 2*idx+1, | |
651 createNode(edit, shift + 5, keyOrNull, valOrNode, hash, key, val)); | |
652 } else { | |
653 int n = Integer.bitCount(bitmap); | |
654 if(n*2 < array.length) { | |
655 addedLeaf.val = addedLeaf; | |
656 BitmapIndexedNode editable = ensureEditable(edit); | |
657 System.arraycopy(editable.array, 2*idx, editable.array, 2*(idx+1), 2*(n-idx)); | |
658 editable.array[2*idx] = key; | |
659 editable.array[2*idx+1] = val; | |
660 editable.bitmap |= bit; | |
661 return editable; | |
662 } | |
663 if(n >= 16) { | |
664 INode[] nodes = new INode[32]; | |
665 int jdx = mask(hash, shift); | |
666 nodes[jdx] = EMPTY.assoc(edit, shift + 5, hash, key, val, addedLeaf); | |
667 int j = 0; | |
668 for(int i = 0; i < 32; i++) | |
669 if(((bitmap >>> i) & 1) != 0) { | |
670 if (array[j] == null) | |
671 nodes[i] = (INode) array[j+1]; | |
672 else | |
673 nodes[i] = EMPTY.assoc(edit, shift + 5, Util.hash(array[j]), array[j], array[j+1], addedLeaf); | |
674 j += 2; | |
675 } | |
676 return new ArrayNode(edit, n + 1, nodes); | |
677 } else { | |
678 Object[] newArray = new Object[2*(n+4)]; | |
679 System.arraycopy(array, 0, newArray, 0, 2*idx); | |
680 newArray[2*idx] = key; | |
681 addedLeaf.val = addedLeaf; | |
682 newArray[2*idx+1] = val; | |
683 System.arraycopy(array, 2*idx, newArray, 2*(idx+1), 2*(n-idx)); | |
684 BitmapIndexedNode editable = ensureEditable(edit); | |
685 editable.array = newArray; | |
686 editable.bitmap |= bit; | |
687 return editable; | |
688 } | |
689 } | |
690 } | |
691 | |
692 public INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf){ | |
693 int bit = bitpos(hash, shift); | |
694 if((bitmap & bit) == 0) | |
695 return this; | |
696 int idx = index(bit); | |
697 Object keyOrNull = array[2*idx]; | |
698 Object valOrNode = array[2*idx+1]; | |
699 if(keyOrNull == null) { | |
700 INode n = ((INode) valOrNode).without(edit, shift + 5, hash, key, removedLeaf); | |
701 if (n == valOrNode) | |
702 return this; | |
703 if (n != null) | |
704 return editAndSet(edit, 2*idx+1, n); | |
705 if (bitmap == bit) | |
706 return null; | |
707 removedLeaf.val = removedLeaf; | |
708 return editAndRemovePair(edit, bit, idx); | |
709 } | |
710 if(Util.equals(key, keyOrNull)) { | |
711 removedLeaf.val = removedLeaf; | |
712 // TODO: collapse | |
713 return editAndRemovePair(edit, bit, idx); | |
714 } | |
715 return this; | |
716 } | |
717 } | |
718 | |
719 final static class HashCollisionNode implements INode{ | |
720 | |
721 final int hash; | |
722 int count; | |
723 Object[] array; | |
724 final AtomicReference<Thread> edit; | |
725 | |
726 HashCollisionNode(AtomicReference<Thread> edit, int hash, int count, Object... array){ | |
727 this.edit = edit; | |
728 this.hash = hash; | |
729 this.count = count; | |
730 this.array = array; | |
731 } | |
732 | |
733 public INode assoc(int shift, int hash, Object key, Object val, Box addedLeaf){ | |
734 if(hash == this.hash) { | |
735 int idx = findIndex(key); | |
736 if(idx != -1) { | |
737 if(array[idx + 1] == val) | |
738 return this; | |
739 return new HashCollisionNode(null, hash, count, cloneAndSet(array, idx + 1, val)); | |
740 } | |
741 Object[] newArray = new Object[array.length + 2]; | |
742 System.arraycopy(array, 0, newArray, 0, array.length); | |
743 newArray[array.length] = key; | |
744 newArray[array.length + 1] = val; | |
745 addedLeaf.val = addedLeaf; | |
746 return new HashCollisionNode(edit, hash, count + 1, newArray); | |
747 } | |
748 // nest it in a bitmap node | |
749 return new BitmapIndexedNode(null, bitpos(this.hash, shift), new Object[] {null, this}) | |
750 .assoc(shift, hash, key, val, addedLeaf); | |
751 } | |
752 | |
753 public INode without(int shift, int hash, Object key){ | |
754 int idx = findIndex(key); | |
755 if(idx == -1) | |
756 return this; | |
757 if(count == 1) | |
758 return null; | |
759 return new HashCollisionNode(null, hash, count - 1, removePair(array, idx/2)); | |
760 } | |
761 | |
762 public IMapEntry find(int shift, int hash, Object key){ | |
763 int idx = findIndex(key); | |
764 if(idx < 0) | |
765 return null; | |
766 if(Util.equals(key, array[idx])) | |
767 return new MapEntry(array[idx], array[idx+1]); | |
768 return null; | |
769 } | |
770 | |
771 public Object find(int shift, int hash, Object key, Object notFound){ | |
772 int idx = findIndex(key); | |
773 if(idx < 0) | |
774 return notFound; | |
775 if(Util.equals(key, array[idx])) | |
776 return array[idx+1]; | |
777 return notFound; | |
778 } | |
779 | |
780 public ISeq nodeSeq(){ | |
781 return NodeSeq.create(array); | |
782 } | |
783 | |
784 public int findIndex(Object key){ | |
785 for(int i = 0; i < 2*count; i+=2) | |
786 { | |
787 if(Util.equals(key, array[i])) | |
788 return i; | |
789 } | |
790 return -1; | |
791 } | |
792 | |
793 private HashCollisionNode ensureEditable(AtomicReference<Thread> edit){ | |
794 if(this.edit == edit) | |
795 return this; | |
796 return new HashCollisionNode(edit, hash, count, array); | |
797 } | |
798 | |
799 private HashCollisionNode ensureEditable(AtomicReference<Thread> edit, int count, Object[] array){ | |
800 if(this.edit == edit) { | |
801 this.array = array; | |
802 this.count = count; | |
803 return this; | |
804 } | |
805 return new HashCollisionNode(edit, hash, count, array); | |
806 } | |
807 | |
808 private HashCollisionNode editAndSet(AtomicReference<Thread> edit, int i, Object a) { | |
809 HashCollisionNode editable = ensureEditable(edit); | |
810 editable.array[i] = a; | |
811 return editable; | |
812 } | |
813 | |
814 private HashCollisionNode editAndSet(AtomicReference<Thread> edit, int i, Object a, int j, Object b) { | |
815 HashCollisionNode editable = ensureEditable(edit); | |
816 editable.array[i] = a; | |
817 editable.array[j] = b; | |
818 return editable; | |
819 } | |
820 | |
821 | |
822 public INode assoc(AtomicReference<Thread> edit, int shift, int hash, Object key, Object val, Box addedLeaf){ | |
823 if(hash == this.hash) { | |
824 int idx = findIndex(key); | |
825 if(idx != -1) { | |
826 if(array[idx + 1] == val) | |
827 return this; | |
828 return editAndSet(edit, idx+1, val); | |
829 } | |
830 if (array.length > 2*count) { | |
831 addedLeaf.val = addedLeaf; | |
832 HashCollisionNode editable = editAndSet(edit, 2*count, key, 2*count+1, val); | |
833 editable.count++; | |
834 return editable; | |
835 } | |
836 Object[] newArray = new Object[array.length + 2]; | |
837 System.arraycopy(array, 0, newArray, 0, array.length); | |
838 newArray[array.length] = key; | |
839 newArray[array.length + 1] = val; | |
840 addedLeaf.val = addedLeaf; | |
841 return ensureEditable(edit, count + 1, newArray); | |
842 } | |
843 // nest it in a bitmap node | |
844 return new BitmapIndexedNode(edit, bitpos(this.hash, shift), new Object[] {null, this, null, null}) | |
845 .assoc(edit, shift, hash, key, val, addedLeaf); | |
846 } | |
847 | |
848 public INode without(AtomicReference<Thread> edit, int shift, int hash, Object key, Box removedLeaf){ | |
849 int idx = findIndex(key); | |
850 if(idx == -1) | |
851 return this; | |
852 if(count == 1) | |
853 return null; | |
854 HashCollisionNode editable = ensureEditable(edit); | |
855 editable.array[idx] = editable.array[2*count-2]; | |
856 editable.array[idx+1] = editable.array[2*count-1]; | |
857 editable.array[2*count-2] = editable.array[2*count-1] = null; | |
858 editable.count--; | |
859 return editable; | |
860 } | |
861 } | |
862 | |
863 /* | |
864 public static void main(String[] args){ | |
865 try | |
866 { | |
867 ArrayList words = new ArrayList(); | |
868 Scanner s = new Scanner(new File(args[0])); | |
869 s.useDelimiter(Pattern.compile("\\W")); | |
870 while(s.hasNext()) | |
871 { | |
872 String word = s.next(); | |
873 words.add(word); | |
874 } | |
875 System.out.println("words: " + words.size()); | |
876 IPersistentMap map = PersistentHashMap.EMPTY; | |
877 //IPersistentMap map = new PersistentTreeMap(); | |
878 //Map ht = new Hashtable(); | |
879 Map ht = new HashMap(); | |
880 Random rand; | |
881 | |
882 System.out.println("Building map"); | |
883 long startTime = System.nanoTime(); | |
884 for(Object word5 : words) | |
885 { | |
886 map = map.assoc(word5, word5); | |
887 } | |
888 rand = new Random(42); | |
889 IPersistentMap snapshotMap = map; | |
890 for(int i = 0; i < words.size() / 200; i++) | |
891 { | |
892 map = map.without(words.get(rand.nextInt(words.size() / 2))); | |
893 } | |
894 long estimatedTime = System.nanoTime() - startTime; | |
895 System.out.println("count = " + map.count() + ", time: " + estimatedTime / 1000000); | |
896 | |
897 System.out.println("Building ht"); | |
898 startTime = System.nanoTime(); | |
899 for(Object word1 : words) | |
900 { | |
901 ht.put(word1, word1); | |
902 } | |
903 rand = new Random(42); | |
904 for(int i = 0; i < words.size() / 200; i++) | |
905 { | |
906 ht.remove(words.get(rand.nextInt(words.size() / 2))); | |
907 } | |
908 estimatedTime = System.nanoTime() - startTime; | |
909 System.out.println("count = " + ht.size() + ", time: " + estimatedTime / 1000000); | |
910 | |
911 System.out.println("map lookup"); | |
912 startTime = System.nanoTime(); | |
913 int c = 0; | |
914 for(Object word2 : words) | |
915 { | |
916 if(!map.contains(word2)) | |
917 ++c; | |
918 } | |
919 estimatedTime = System.nanoTime() - startTime; | |
920 System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000); | |
921 System.out.println("ht lookup"); | |
922 startTime = System.nanoTime(); | |
923 c = 0; | |
924 for(Object word3 : words) | |
925 { | |
926 if(!ht.containsKey(word3)) | |
927 ++c; | |
928 } | |
929 estimatedTime = System.nanoTime() - startTime; | |
930 System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000); | |
931 System.out.println("snapshotMap lookup"); | |
932 startTime = System.nanoTime(); | |
933 c = 0; | |
934 for(Object word4 : words) | |
935 { | |
936 if(!snapshotMap.contains(word4)) | |
937 ++c; | |
938 } | |
939 estimatedTime = System.nanoTime() - startTime; | |
940 System.out.println("notfound = " + c + ", time: " + estimatedTime / 1000000); | |
941 } | |
942 catch(FileNotFoundException e) | |
943 { | |
944 e.printStackTrace(); | |
945 } | |
946 | |
947 } | |
948 */ | |
949 | |
950 private static INode[] cloneAndSet(INode[] array, int i, INode a) { | |
951 INode[] clone = array.clone(); | |
952 clone[i] = a; | |
953 return clone; | |
954 } | |
955 | |
956 private static Object[] cloneAndSet(Object[] array, int i, Object a) { | |
957 Object[] clone = array.clone(); | |
958 clone[i] = a; | |
959 return clone; | |
960 } | |
961 | |
962 private static Object[] cloneAndSet(Object[] array, int i, Object a, int j, Object b) { | |
963 Object[] clone = array.clone(); | |
964 clone[i] = a; | |
965 clone[j] = b; | |
966 return clone; | |
967 } | |
968 | |
969 private static Object[] removePair(Object[] array, int i) { | |
970 Object[] newArray = new Object[array.length - 2]; | |
971 System.arraycopy(array, 0, newArray, 0, 2*i); | |
972 System.arraycopy(array, 2*(i+1), newArray, 2*i, newArray.length - 2*i); | |
973 return newArray; | |
974 } | |
975 | |
976 private static INode createNode(int shift, Object key1, Object val1, int key2hash, Object key2, Object val2) { | |
977 int key1hash = Util.hash(key1); | |
978 if(key1hash == key2hash) | |
979 return new HashCollisionNode(null, key1hash, 2, new Object[] {key1, val1, key2, val2}); | |
980 Box _ = new Box(null); | |
981 AtomicReference<Thread> edit = new AtomicReference<Thread>(); | |
982 return BitmapIndexedNode.EMPTY | |
983 .assoc(edit, shift, key1hash, key1, val1, _) | |
984 .assoc(edit, shift, key2hash, key2, val2, _); | |
985 } | |
986 | |
987 private static INode createNode(AtomicReference<Thread> edit, int shift, Object key1, Object val1, int key2hash, Object key2, Object val2) { | |
988 int key1hash = Util.hash(key1); | |
989 if(key1hash == key2hash) | |
990 return new HashCollisionNode(null, key1hash, 2, new Object[] {key1, val1, key2, val2}); | |
991 Box _ = new Box(null); | |
992 return BitmapIndexedNode.EMPTY | |
993 .assoc(edit, shift, key1hash, key1, val1, _) | |
994 .assoc(edit, shift, key2hash, key2, val2, _); | |
995 } | |
996 | |
997 private static int bitpos(int hash, int shift){ | |
998 return 1 << mask(hash, shift); | |
999 } | |
1000 | |
1001 static final class NodeSeq extends ASeq { | |
1002 final Object[] array; | |
1003 final int i; | |
1004 final ISeq s; | |
1005 | |
1006 NodeSeq(Object[] array, int i) { | |
1007 this(null, array, i, null); | |
1008 } | |
1009 | |
1010 static ISeq create(Object[] array) { | |
1011 return create(array, 0, null); | |
1012 } | |
1013 | |
1014 private static ISeq create(Object[] array, int i, ISeq s) { | |
1015 if(s != null) | |
1016 return new NodeSeq(null, array, i, s); | |
1017 for(int j = i; j < array.length; j+=2) { | |
1018 if(array[j] != null) | |
1019 return new NodeSeq(null, array, j, null); | |
1020 INode node = (INode) array[j+1]; | |
1021 if (node != null) { | |
1022 ISeq nodeSeq = node.nodeSeq(); | |
1023 if(nodeSeq != null) | |
1024 return new NodeSeq(null, array, j + 2, nodeSeq); | |
1025 } | |
1026 } | |
1027 return null; | |
1028 } | |
1029 | |
1030 NodeSeq(IPersistentMap meta, Object[] array, int i, ISeq s) { | |
1031 super(meta); | |
1032 this.array = array; | |
1033 this.i = i; | |
1034 this.s = s; | |
1035 } | |
1036 | |
1037 public Obj withMeta(IPersistentMap meta) { | |
1038 return new NodeSeq(meta, array, i, s); | |
1039 } | |
1040 | |
1041 public Object first() { | |
1042 if(s != null) | |
1043 return s.first(); | |
1044 return new MapEntry(array[i], array[i+1]); | |
1045 } | |
1046 | |
1047 public ISeq next() { | |
1048 if(s != null) | |
1049 return create(array, i, s.next()); | |
1050 return create(array, i + 2, null); | |
1051 } | |
1052 } | |
1053 | |
1054 } |