Mercurial > hg > blitz_condensed
comparison src/EDU/oswego/cs/dl/util/concurrent/ConcurrentReaderHashMap.java @ 0:3dc0c5604566
Initial checkin of blitz 2.0 fcs - no installer yet.
author | Dan Creswell <dan.creswell@gmail.com> |
---|---|
date | Sat, 21 Mar 2009 11:00:06 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:3dc0c5604566 |
---|---|
1 /* | |
2 File: ConcurrentReaderHashMap | |
3 | |
4 Written by Doug Lea. Adapted from JDK1.2 HashMap.java and Hashtable.java | |
5 which carries the following copyright: | |
6 | |
7 * Copyright 1997 by Sun Microsystems, Inc., | |
8 * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A. | |
9 * All rights reserved. | |
10 * | |
11 * This software is the confidential and proprietary information | |
12 * of Sun Microsystems, Inc. ("Confidential Information"). You | |
13 * shall not disclose such Confidential Information and shall use | |
14 * it only in accordance with the terms of the license agreement | |
15 * you entered into with Sun. | |
16 | |
17 History: | |
18 Date Who What | |
19 28oct1999 dl Created | |
20 14dec1999 dl jmm snapshot | |
21 19apr2000 dl use barrierLock | |
22 12jan2001 dl public release | |
23 17nov2001 dl Minor tunings | |
24 20may2002 dl BarrierLock can now be serialized. | |
25 09dec2002 dl Fix interference checks. | |
26 */ | |
27 | |
28 package EDU.oswego.cs.dl.util.concurrent; | |
29 | |
30 import java.util.Map; | |
31 import java.util.AbstractMap; | |
32 import java.util.AbstractSet; | |
33 import java.util.AbstractCollection; | |
34 import java.util.Collection; | |
35 import java.util.Set; | |
36 import java.util.Iterator; | |
37 import java.util.Enumeration; | |
38 import java.util.ConcurrentModificationException; | |
39 import java.util.NoSuchElementException; | |
40 | |
41 import java.io.Serializable; | |
42 import java.io.IOException; | |
43 import java.io.ObjectInputStream; | |
44 import java.io.ObjectOutputStream; | |
45 | |
46 | |
47 /** | |
48 * A version of Hashtable that supports mostly-concurrent reading, but | |
49 * exclusive writing. Because reads are not limited to periods | |
50 * without writes, a concurrent reader policy is weaker than a classic | |
51 * reader/writer policy, but is generally faster and allows more | |
52 * concurrency. This class is a good choice especially for tables that | |
53 * are mainly created by one thread during the start-up phase of a | |
54 * program, and from then on, are mainly read (with perhaps occasional | |
55 * additions or removals) in many threads. If you also need concurrency | |
56 * among writes, consider instead using ConcurrentHashMap. | |
57 * <p> | |
58 * | |
59 * Successful retrievals using get(key) and containsKey(key) usually | |
60 * run without locking. Unsuccessful ones (i.e., when the key is not | |
61 * present) do involve brief synchronization (locking). Also, the | |
62 * size and isEmpty methods are always synchronized. | |
63 * | |
64 * <p> Because retrieval operations can ordinarily overlap with | |
65 * writing operations (i.e., put, remove, and their derivatives), | |
66 * retrievals can only be guaranteed to return the results of the most | |
67 * recently <em>completed</em> operations holding upon their | |
68 * onset. Retrieval operations may or may not return results | |
69 * reflecting in-progress writing operations. However, the retrieval | |
70 * operations do always return consistent results -- either those | |
71 * holding before any single modification or after it, but never a | |
72 * nonsense result. For aggregate operations such as putAll and | |
73 * clear, concurrent reads may reflect insertion or removal of only | |
74 * some entries. In those rare contexts in which you use a hash table | |
75 * to synchronize operations across threads (for example, to prevent | |
76 * reads until after clears), you should either encase operations | |
77 * in synchronized blocks, or instead use java.util.Hashtable. | |
78 * | |
79 * <p> | |
80 * | |
81 * This class also supports optional guaranteed | |
82 * exclusive reads, simply by surrounding a call within a synchronized | |
83 * block, as in <br> | |
84 * <code>ConcurrentReaderHashMap t; ... Object v; <br> | |
85 * synchronized(t) { v = t.get(k); } </code> <br> | |
86 * | |
87 * But this is not usually necessary in practice. For | |
88 * example, it is generally inefficient to write: | |
89 * | |
90 * <pre> | |
91 * ConcurrentReaderHashMap t; ... // Inefficient version | |
92 * Object key; ... | |
93 * Object value; ... | |
94 * synchronized(t) { | |
95 * if (!t.containsKey(key)) | |
96 * t.put(key, value); | |
97 * // other code if not previously present | |
98 * } | |
99 * else { | |
100 * // other code if it was previously present | |
101 * } | |
102 * } | |
103 *</pre> | |
104 * Instead, if the values are intended to be the same in each case, just take advantage of the fact that put returns | |
105 * null if the key was not previously present: | |
106 * <pre> | |
107 * ConcurrentReaderHashMap t; ... // Use this instead | |
108 * Object key; ... | |
109 * Object value; ... | |
110 * Object oldValue = t.put(key, value); | |
111 * if (oldValue == null) { | |
112 * // other code if not previously present | |
113 * } | |
114 * else { | |
115 * // other code if it was previously present | |
116 * } | |
117 *</pre> | |
118 * <p> | |
119 * | |
120 * Iterators and Enumerations (i.e., those returned by | |
121 * keySet().iterator(), entrySet().iterator(), values().iterator(), | |
122 * keys(), and elements()) return elements reflecting the state of the | |
123 * hash table at some point at or since the creation of the | |
124 * iterator/enumeration. They will return at most one instance of | |
125 * each element (via next()/nextElement()), but might or might not | |
126 * reflect puts and removes that have been processed since they were | |
127 * created. They do <em>not</em> throw ConcurrentModificationException. | |
128 * However, these iterators are designed to be used by only one | |
129 * thread at a time. Sharing an iterator across multiple threads may | |
130 * lead to unpredictable results if the table is being concurrently | |
131 * modified. Again, you can ensure interference-free iteration by | |
132 * enclosing the iteration in a synchronized block. <p> | |
133 * | |
134 * This class may be used as a direct replacement for any use of | |
135 * java.util.Hashtable that does not depend on readers being blocked | |
136 * during updates. Like Hashtable but unlike java.util.HashMap, | |
137 * this class does NOT allow <tt>null</tt> to be used as a key or | |
138 * value. This class is also typically faster than ConcurrentHashMap | |
139 * when there is usually only one thread updating the table, but | |
140 * possibly many retrieving values from it. | |
141 * <p> | |
142 * | |
143 * Implementation note: A slightly faster implementation of | |
144 * this class will be possible once planned Java Memory Model | |
145 * revisions are in place. | |
146 * | |
147 * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>] | |
148 | |
149 **/ | |
150 | |
151 | |
152 public class ConcurrentReaderHashMap | |
153 extends AbstractMap | |
154 implements Map, Cloneable, Serializable { | |
155 | |
156 | |
157 /* | |
158 The basic strategy is an optimistic-style scheme based on | |
159 the guarantee that the hash table and its lists are always | |
160 kept in a consistent enough state to be read without locking: | |
161 | |
162 * Read operations first proceed without locking, by traversing the | |
163 apparently correct list of the apparently correct bin. If an | |
164 entry is found, but not invalidated (value field null), it is | |
165 returned. If not found, operations must recheck (after a memory | |
166 barrier) to make sure they are using both the right list and | |
167 the right table (which can change under resizes). If | |
168 invalidated, reads must acquire main update lock to wait out | |
169 the update, and then re-traverse. | |
170 | |
171 * All list additions are at the front of each bin, making it easy | |
172 to check changes, and also fast to traverse. Entry next | |
173 pointers are never assigned. Remove() builds new nodes when | |
174 necessary to preserve this. | |
175 | |
176 * Remove() (also clear()) invalidates removed nodes to alert read | |
177 operations that they must wait out the full modifications. | |
178 | |
179 */ | |
180 | |
181 /** A Serializable class for barrier lock **/ | |
182 protected static class BarrierLock implements java.io.Serializable { } | |
183 | |
184 /** | |
185 * Lock used only for its memory effects. | |
186 **/ | |
187 protected final BarrierLock barrierLock = new BarrierLock(); | |
188 | |
189 /** | |
190 * field written to only to guarantee lock ordering. | |
191 **/ | |
192 | |
193 protected transient Object lastWrite; | |
194 | |
195 /** | |
196 * Force a memory synchronization that will cause | |
197 * all readers to see table. Call only when already | |
198 * holding main synch lock. | |
199 **/ | |
200 protected final void recordModification(Object x) { | |
201 synchronized(barrierLock) { | |
202 lastWrite = x; | |
203 } | |
204 } | |
205 | |
206 /** | |
207 * Get ref to table; the reference and the cells it | |
208 * accesses will be at least as fresh as from last | |
209 * use of barrierLock | |
210 **/ | |
211 protected final Entry[] getTableForReading() { | |
212 synchronized(barrierLock) { | |
213 return table; | |
214 } | |
215 } | |
216 | |
217 | |
218 /** | |
219 * The default initial number of table slots for this table (32). | |
220 * Used when not otherwise specified in constructor. | |
221 **/ | |
222 public static int DEFAULT_INITIAL_CAPACITY = 32; | |
223 | |
224 | |
225 /** | |
226 * The minimum capacity, used if a lower value is implicitly specified | |
227 * by either of the constructors with arguments. | |
228 * MUST be a power of two. | |
229 */ | |
230 private static final int MINIMUM_CAPACITY = 4; | |
231 | |
232 /** | |
233 * The maximum capacity, used if a higher value is implicitly specified | |
234 * by either of the constructors with arguments. | |
235 * MUST be a power of two <= 1<<30. | |
236 */ | |
237 private static final int MAXIMUM_CAPACITY = 1 << 30; | |
238 | |
239 /** | |
240 * The default load factor for this table (1.0). | |
241 * Used when not otherwise specified in constructor. | |
242 **/ | |
243 | |
244 public static final float DEFAULT_LOAD_FACTOR = 0.75f; | |
245 | |
246 | |
247 /** | |
248 * The hash table data. | |
249 */ | |
250 protected transient Entry[] table; | |
251 | |
252 /** | |
253 * The total number of mappings in the hash table. | |
254 */ | |
255 protected transient int count; | |
256 | |
257 /** | |
258 * The table is rehashed when its size exceeds this threshold. (The | |
259 * value of this field is always (int)(capacity * loadFactor).) | |
260 * | |
261 * @serial | |
262 */ | |
263 protected int threshold; | |
264 | |
265 /** | |
266 * The load factor for the hash table. | |
267 * | |
268 * @serial | |
269 */ | |
270 protected float loadFactor; | |
271 | |
272 /** | |
273 * Returns the appropriate capacity (power of two) for the specified | |
274 * initial capacity argument. | |
275 */ | |
276 private int p2capacity(int initialCapacity) { | |
277 int cap = initialCapacity; | |
278 | |
279 // Compute the appropriate capacity | |
280 int result; | |
281 if (cap > MAXIMUM_CAPACITY || cap < 0) { | |
282 result = MAXIMUM_CAPACITY; | |
283 } else { | |
284 result = MINIMUM_CAPACITY; | |
285 while (result < cap) | |
286 result <<= 1; | |
287 } | |
288 return result; | |
289 } | |
290 | |
291 /** | |
292 * Return hash code for Object x. Since we are using power-of-two | |
293 * tables, it is worth the effort to improve hashcode via | |
294 * the same multiplicative scheme as used in IdentityHashMap. | |
295 */ | |
296 private static int hash(Object x) { | |
297 int h = x.hashCode(); | |
298 // Multiply by 127 (quickly, via shifts), and mix in some high | |
299 // bits to help guard against bunching of codes that are | |
300 // consecutive or equally spaced. | |
301 return ((h << 7) - h + (h >>> 9) + (h >>> 17)); | |
302 } | |
303 | |
304 /** | |
305 * Check for equality of non-null references x and y. | |
306 **/ | |
307 protected boolean eq(Object x, Object y) { | |
308 return x == y || x.equals(y); | |
309 } | |
310 | |
311 /** | |
312 * Constructs a new, empty map with the specified initial | |
313 * capacity and the specified load factor. | |
314 * | |
315 * @param initialCapacity the initial capacity | |
316 * The actual initial capacity is rounded to the nearest power of two. | |
317 * @param loadFactor the load factor of the ConcurrentReaderHashMap | |
318 * @throws IllegalArgumentException if the initial maximum number | |
319 * of elements is less | |
320 * than zero, or if the load factor is nonpositive. | |
321 */ | |
322 | |
323 public ConcurrentReaderHashMap(int initialCapacity, float loadFactor) { | |
324 if (loadFactor <= 0) | |
325 throw new IllegalArgumentException("Illegal Load factor: "+ | |
326 loadFactor); | |
327 this.loadFactor = loadFactor; | |
328 | |
329 int cap = p2capacity(initialCapacity); | |
330 | |
331 table = new Entry[cap]; | |
332 threshold = (int)(cap * loadFactor); | |
333 } | |
334 | |
335 /** | |
336 * Constructs a new, empty map with the specified initial | |
337 * capacity and default load factor. | |
338 * | |
339 * @param initialCapacity the initial capacity of the | |
340 * ConcurrentReaderHashMap. | |
341 * @throws IllegalArgumentException if the initial maximum number | |
342 * of elements is less | |
343 * than zero. | |
344 */ | |
345 | |
346 public ConcurrentReaderHashMap(int initialCapacity) { | |
347 this(initialCapacity, DEFAULT_LOAD_FACTOR); | |
348 } | |
349 | |
350 /** | |
351 * Constructs a new, empty map with a default initial capacity | |
352 * and load factor. | |
353 */ | |
354 | |
355 public ConcurrentReaderHashMap() { | |
356 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); | |
357 } | |
358 | |
359 /** | |
360 * Constructs a new map with the same mappings as the given map. The | |
361 * map is created with a capacity of twice the number of mappings in | |
362 * the given map or 16 (whichever is greater), and a default load factor. | |
363 */ | |
364 | |
365 public ConcurrentReaderHashMap(Map t) { | |
366 this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1, 16), | |
367 DEFAULT_LOAD_FACTOR); | |
368 putAll(t); | |
369 } | |
370 | |
371 /** | |
372 * Returns the number of key-value mappings in this map. | |
373 * | |
374 * @return the number of key-value mappings in this map. | |
375 */ | |
376 | |
377 public synchronized int size() { | |
378 return count; | |
379 } | |
380 | |
381 /** | |
382 * Returns <tt>true</tt> if this map contains no key-value mappings. | |
383 * | |
384 * @return <tt>true</tt> if this map contains no key-value mappings. | |
385 */ | |
386 | |
387 public synchronized boolean isEmpty() { | |
388 return count == 0; | |
389 } | |
390 | |
391 | |
392 | |
393 /** | |
394 * Returns the value to which the specified key is mapped in this table. | |
395 * | |
396 * @param key a key in the table. | |
397 * @return the value to which the key is mapped in this table; | |
398 * <code>null</code> if the key is not mapped to any value in | |
399 * this table. | |
400 * @exception NullPointerException if the key is | |
401 * <code>null</code>. | |
402 * @see #put(Object, Object) | |
403 */ | |
404 | |
405 | |
406 public Object get(Object key) { | |
407 | |
408 // throw null pointer exception if key null | |
409 int hash = hash(key); | |
410 | |
411 /* | |
412 Start off at the apparently correct bin. If entry is found, we | |
413 need to check after a barrier anyway. If not found, we need a | |
414 barrier to check if we are actually in right bin. So either | |
415 way, we encounter only one barrier unless we need to retry. | |
416 And we only need to fully synchronize if there have been | |
417 concurrent modifications. | |
418 */ | |
419 | |
420 Entry[] tab = table; | |
421 int index = hash & (tab.length - 1); | |
422 Entry first = tab[index]; | |
423 Entry e = first; | |
424 | |
425 for (;;) { | |
426 if (e == null) { | |
427 | |
428 // If key apparently not there, check to | |
429 // make sure this was a valid read | |
430 | |
431 Entry[] reread = getTableForReading(); | |
432 if (tab == reread && first == tab[index]) | |
433 return null; | |
434 else { | |
435 // Wrong list -- must restart traversal at new first | |
436 tab = reread; | |
437 e = first = tab[index = hash & (tab.length-1)]; | |
438 } | |
439 | |
440 } | |
441 | |
442 else if (e.hash == hash && eq(key, e.key)) { | |
443 Object value = e.value; | |
444 if (value != null) | |
445 return value; | |
446 | |
447 // Entry was invalidated during deletion. But it could | |
448 // have been re-inserted, so we must retraverse. | |
449 // To avoid useless contention, get lock to wait out modifications | |
450 // before retraversing. | |
451 | |
452 synchronized(this) { | |
453 tab = table; | |
454 } | |
455 e = first = tab[index = hash & (tab.length-1)]; | |
456 | |
457 } | |
458 else | |
459 e = e.next; | |
460 } | |
461 } | |
462 | |
463 | |
464 /** | |
465 * Tests if the specified object is a key in this table. | |
466 * | |
467 * @param key possible key. | |
468 * @return <code>true</code> if and only if the specified object | |
469 * is a key in this table, as determined by the | |
470 * <tt>equals</tt> method; <code>false</code> otherwise. | |
471 * @exception NullPointerException if the key is | |
472 * <code>null</code>. | |
473 * @see #contains(Object) | |
474 */ | |
475 | |
476 | |
477 public boolean containsKey(Object key) { | |
478 return get(key) != null; | |
479 } | |
480 | |
481 /** | |
482 * Maps the specified <code>key</code> to the specified | |
483 * <code>value</code> in this table. Neither the key nor the | |
484 * value can be <code>null</code>. <p> | |
485 * | |
486 * The value can be retrieved by calling the <code>get</code> method | |
487 * with a key that is equal to the original key. | |
488 * | |
489 * @param key the table key. | |
490 * @param value the value. | |
491 * @return the previous value of the specified key in this table, | |
492 * or <code>null</code> if it did not have one. | |
493 * @exception NullPointerException if the key or value is | |
494 * <code>null</code>. | |
495 * @see Object#equals(Object) | |
496 * @see #get(Object) | |
497 */ | |
498 | |
499 public Object put(Object key, Object value) { | |
500 if (value == null) | |
501 throw new NullPointerException(); | |
502 | |
503 int hash = hash(key); | |
504 Entry[] tab = table; | |
505 int index = hash & (tab.length-1); | |
506 Entry first = tab[index]; | |
507 Entry e; | |
508 | |
509 for (e = first; e != null; e = e.next) | |
510 if (e.hash == hash && eq(key, e.key)) | |
511 break; | |
512 | |
513 synchronized(this) { | |
514 if (tab == table) { | |
515 if (e == null) { | |
516 // make sure we are adding to correct list | |
517 if (first == tab[index]) { | |
518 // Add to front of list | |
519 Entry newEntry = new Entry(hash, key, value, first); | |
520 tab[index] = newEntry; | |
521 if (++count >= threshold) rehash(); | |
522 else recordModification(newEntry); | |
523 return null; | |
524 } | |
525 } | |
526 else { | |
527 Object oldValue = e.value; | |
528 if (first == tab[index] && oldValue != null) { | |
529 e.value = value; | |
530 return oldValue; | |
531 } | |
532 } | |
533 } | |
534 | |
535 // retry if wrong list or lost race against concurrent remove | |
536 return sput(key, value, hash); | |
537 } | |
538 } | |
539 | |
540 | |
541 /** | |
542 * Continuation of put(), called only when synch lock is | |
543 * held and interference has been detected. | |
544 **/ | |
545 protected Object sput(Object key, Object value, int hash) { | |
546 | |
547 Entry[] tab = table; | |
548 int index = hash & (tab.length-1); | |
549 Entry first = tab[index]; | |
550 Entry e = first; | |
551 | |
552 for (;;) { | |
553 if (e == null) { | |
554 Entry newEntry = new Entry(hash, key, value, first); | |
555 tab[index] = newEntry; | |
556 if (++count >= threshold) rehash(); | |
557 else recordModification(newEntry); | |
558 return null; | |
559 } | |
560 else if (e.hash == hash && eq(key, e.key)) { | |
561 Object oldValue = e.value; | |
562 e.value = value; | |
563 return oldValue; | |
564 } | |
565 else | |
566 e = e.next; | |
567 } | |
568 } | |
569 | |
570 | |
571 /** | |
572 * Rehashes the contents of this map into a new table | |
573 * with a larger capacity. This method is called automatically when the | |
574 * number of keys in this map exceeds its capacity and load factor. | |
575 */ | |
576 protected void rehash() { | |
577 Entry[] oldTable = table; | |
578 int oldCapacity = oldTable.length; | |
579 if (oldCapacity >= MAXIMUM_CAPACITY) { | |
580 threshold = Integer.MAX_VALUE; // avoid retriggering | |
581 return; | |
582 } | |
583 | |
584 int newCapacity = oldCapacity << 1; | |
585 int mask = newCapacity - 1; | |
586 threshold = (int)(newCapacity * loadFactor); | |
587 | |
588 Entry[] newTable = new Entry[newCapacity]; | |
589 /* | |
590 * Reclassify nodes in each list to new Map. Because we are | |
591 * using power-of-two expansion, the elements from each bin | |
592 * must either stay at same index, or move to | |
593 * oldCapacity+index. We also eliminate unnecessary node | |
594 * creation by catching cases where old nodes can be reused | |
595 * because their next fields won't change. Statistically, at | |
596 * the default threshhold, only about one-sixth of them need | |
597 * cloning. (The nodes they replace will be garbage | |
598 * collectable as soon as they are no longer referenced by any | |
599 * reader thread that may be in the midst of traversing table | |
600 * right now.) | |
601 */ | |
602 | |
603 for (int i = 0; i < oldCapacity ; i++) { | |
604 // We need to guarantee that any existing reads of old Map can | |
605 // proceed. So we cannot yet null out each bin. | |
606 Entry e = oldTable[i]; | |
607 | |
608 if (e != null) { | |
609 int idx = e.hash & mask; | |
610 Entry next = e.next; | |
611 | |
612 // Single node on list | |
613 if (next == null) | |
614 newTable[idx] = e; | |
615 | |
616 else { | |
617 // Reuse trailing consecutive sequence of all same bit | |
618 Entry lastRun = e; | |
619 int lastIdx = idx; | |
620 for (Entry last = next; last != null; last = last.next) { | |
621 int k = last.hash & mask; | |
622 if (k != lastIdx) { | |
623 lastIdx = k; | |
624 lastRun = last; | |
625 } | |
626 } | |
627 newTable[lastIdx] = lastRun; | |
628 | |
629 // Clone all remaining nodes | |
630 for (Entry p = e; p != lastRun; p = p.next) { | |
631 int k = p.hash & mask; | |
632 newTable[k] = new Entry(p.hash, p.key, | |
633 p.value, newTable[k]); | |
634 } | |
635 } | |
636 } | |
637 } | |
638 | |
639 table = newTable; | |
640 recordModification(newTable); | |
641 } | |
642 | |
643 /** | |
644 * Removes the key (and its corresponding value) from this | |
645 * table. This method does nothing if the key is not in the table. | |
646 * | |
647 * @param key the key that needs to be removed. | |
648 * @return the value to which the key had been mapped in this table, | |
649 * or <code>null</code> if the key did not have a mapping. | |
650 * @exception NullPointerException if the key is | |
651 * <code>null</code>. | |
652 */ | |
653 | |
654 public Object remove(Object key) { | |
655 /* | |
656 Find the entry, then | |
657 1. Set value field to null, to force get() to retry | |
658 2. Rebuild the list without this entry. | |
659 All entries following removed node can stay in list, but | |
660 all preceeding ones need to be cloned. Traversals rely | |
661 on this strategy to ensure that elements will not be | |
662 repeated during iteration. | |
663 */ | |
664 | |
665 | |
666 int hash = hash(key); | |
667 Entry[] tab = table; | |
668 int index = hash & (tab.length-1); | |
669 Entry first = tab[index]; | |
670 Entry e = first; | |
671 | |
672 for (e = first; e != null; e = e.next) | |
673 if (e.hash == hash && eq(key, e.key)) | |
674 break; | |
675 | |
676 | |
677 synchronized(this) { | |
678 if (tab == table) { | |
679 if (e == null) { | |
680 if (first == tab[index]) | |
681 return null; | |
682 } | |
683 else { | |
684 Object oldValue = e.value; | |
685 if (first == tab[index] && oldValue != null) { | |
686 e.value = null; | |
687 count--; | |
688 | |
689 Entry head = e.next; | |
690 for (Entry p = first; p != e; p = p.next) | |
691 head = new Entry(p.hash, p.key, p.value, head); | |
692 | |
693 tab[index] = head; | |
694 recordModification(head); | |
695 return oldValue; | |
696 } | |
697 } | |
698 } | |
699 | |
700 // Wrong list or interference | |
701 return sremove(key, hash); | |
702 } | |
703 } | |
704 | |
705 /** | |
706 * Continuation of remove(), called only when synch lock is | |
707 * held and interference has been detected. | |
708 **/ | |
709 | |
710 protected Object sremove(Object key, int hash) { | |
711 Entry[] tab = table; | |
712 int index = hash & (tab.length-1); | |
713 Entry first = tab[index]; | |
714 | |
715 for (Entry e = first; e != null; e = e.next) { | |
716 if (e.hash == hash && eq(key, e.key)) { | |
717 Object oldValue = e.value; | |
718 e.value = null; | |
719 count--; | |
720 Entry head = e.next; | |
721 for (Entry p = first; p != e; p = p.next) | |
722 head = new Entry(p.hash, p.key, p.value, head); | |
723 | |
724 tab[index] = head; | |
725 recordModification(head); | |
726 return oldValue; | |
727 } | |
728 } | |
729 return null; | |
730 } | |
731 | |
732 | |
733 /** | |
734 * Returns <tt>true</tt> if this map maps one or more keys to the | |
735 * specified value. Note: This method requires a full internal | |
736 * traversal of the hash table, and so is much slower than | |
737 * method <tt>containsKey</tt>. | |
738 * | |
739 * @param value value whose presence in this map is to be tested. | |
740 * @return <tt>true</tt> if this map maps one or more keys to the | |
741 * specified value. | |
742 * @exception NullPointerException if the value is <code>null</code>. | |
743 */ | |
744 | |
745 public boolean containsValue(Object value) { | |
746 if (value == null) throw new NullPointerException(); | |
747 | |
748 Entry tab[] = getTableForReading(); | |
749 | |
750 for (int i = 0 ; i < tab.length; ++i) { | |
751 for (Entry e = tab[i] ; e != null ; e = e.next) | |
752 if (value.equals(e.value)) | |
753 return true; | |
754 } | |
755 | |
756 return false; | |
757 } | |
758 | |
759 /** | |
760 * Tests if some key maps into the specified value in this table. | |
761 * This operation is more expensive than the <code>containsKey</code> | |
762 * method.<p> | |
763 * | |
764 * Note that this method is identical in functionality to containsValue, | |
765 * (which is part of the Map interface in the collections framework). | |
766 * | |
767 * @param value a value to search for. | |
768 * @return <code>true</code> if and only if some key maps to the | |
769 * <code>value</code> argument in this table as | |
770 * determined by the <tt>equals</tt> method; | |
771 * <code>false</code> otherwise. | |
772 * @exception NullPointerException if the value is <code>null</code>. | |
773 * @see #containsKey(Object) | |
774 * @see #containsValue(Object) | |
775 * @see Map | |
776 */ | |
777 | |
778 public boolean contains(Object value) { | |
779 return containsValue(value); | |
780 } | |
781 | |
782 | |
783 /** | |
784 * Copies all of the mappings from the specified map to this one. | |
785 * | |
786 * These mappings replace any mappings that this map had for any of the | |
787 * keys currently in the specified Map. | |
788 * | |
789 * @param t Mappings to be stored in this map. | |
790 */ | |
791 | |
792 public synchronized void putAll(Map t) { | |
793 int n = t.size(); | |
794 if (n == 0) | |
795 return; | |
796 | |
797 // Expand enough to hold at least n elements without resizing. | |
798 // We can only resize table by factor of two at a time. | |
799 // It is faster to rehash with fewer elements, so do it now. | |
800 while (n >= threshold) | |
801 rehash(); | |
802 | |
803 for (Iterator it = t.entrySet().iterator(); it.hasNext();) { | |
804 Map.Entry entry = (Map.Entry) it.next(); | |
805 Object key = entry.getKey(); | |
806 Object value = entry.getValue(); | |
807 put(key, value); | |
808 } | |
809 } | |
810 | |
811 | |
812 /** | |
813 * Removes all mappings from this map. | |
814 */ | |
815 public synchronized void clear() { | |
816 Entry tab[] = table; | |
817 for (int i = 0; i < tab.length ; ++i) { | |
818 | |
819 // must invalidate all to force concurrent get's to wait and then retry | |
820 for (Entry e = tab[i]; e != null; e = e.next) | |
821 e.value = null; | |
822 | |
823 tab[i] = null; | |
824 } | |
825 count = 0; | |
826 recordModification(tab); | |
827 } | |
828 | |
829 /** | |
830 * Returns a shallow copy of this | |
831 * <tt>ConcurrentReaderHashMap</tt> instance: the keys and | |
832 * values themselves are not cloned. | |
833 * | |
834 * @return a shallow copy of this map. | |
835 */ | |
836 | |
837 public synchronized Object clone() { | |
838 try { | |
839 ConcurrentReaderHashMap t = (ConcurrentReaderHashMap)super.clone(); | |
840 | |
841 t.keySet = null; | |
842 t.entrySet = null; | |
843 t.values = null; | |
844 | |
845 Entry[] tab = table; | |
846 t.table = new Entry[tab.length]; | |
847 Entry[] ttab = t.table; | |
848 | |
849 for (int i = 0; i < tab.length; ++i) { | |
850 Entry first = null; | |
851 for (Entry e = tab[i]; e != null; e = e.next) | |
852 first = new Entry(e.hash, e.key, e.value, first); | |
853 ttab[i] = first; | |
854 } | |
855 | |
856 return t; | |
857 } | |
858 catch (CloneNotSupportedException e) { | |
859 // this shouldn't happen, since we are Cloneable | |
860 throw new InternalError(); | |
861 } | |
862 } | |
863 | |
864 // Views | |
865 | |
866 protected transient Set keySet = null; | |
867 protected transient Set entrySet = null; | |
868 protected transient Collection values = null; | |
869 | |
870 /** | |
871 * Returns a set view of the keys contained in this map. The set is | |
872 * backed by the map, so changes to the map are reflected in the set, and | |
873 * vice-versa. The set supports element removal, which removes the | |
874 * corresponding mapping from this map, via the <tt>Iterator.remove</tt>, | |
875 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and | |
876 * <tt>clear</tt> operations. It does not support the <tt>add</tt> or | |
877 * <tt>addAll</tt> operations. | |
878 * | |
879 * @return a set view of the keys contained in this map. | |
880 */ | |
881 | |
882 public Set keySet() { | |
883 Set ks = keySet; | |
884 return (ks != null)? ks : (keySet = new KeySet()); | |
885 } | |
886 | |
887 private class KeySet extends AbstractSet { | |
888 public Iterator iterator() { | |
889 return new KeyIterator(); | |
890 } | |
891 public int size() { | |
892 return ConcurrentReaderHashMap.this.size(); | |
893 } | |
894 public boolean contains(Object o) { | |
895 return ConcurrentReaderHashMap.this.containsKey(o); | |
896 } | |
897 public boolean remove(Object o) { | |
898 return ConcurrentReaderHashMap.this.remove(o) != null; | |
899 } | |
900 public void clear() { | |
901 ConcurrentReaderHashMap.this.clear(); | |
902 } | |
903 } | |
904 | |
905 /** | |
906 * Returns a collection view of the values contained in this map. The | |
907 * collection is backed by the map, so changes to the map are reflected in | |
908 * the collection, and vice-versa. The collection supports element | |
909 * removal, which removes the corresponding mapping from this map, via the | |
910 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, | |
911 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. | |
912 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations. | |
913 * | |
914 * @return a collection view of the values contained in this map. | |
915 */ | |
916 | |
917 public Collection values() { | |
918 Collection vs = values; | |
919 return (vs != null)? vs : (values = new Values()); | |
920 } | |
921 | |
922 private class Values extends AbstractCollection { | |
923 public Iterator iterator() { | |
924 return new ValueIterator(); | |
925 } | |
926 public int size() { | |
927 return ConcurrentReaderHashMap.this.size(); | |
928 } | |
929 public boolean contains(Object o) { | |
930 return ConcurrentReaderHashMap.this.containsValue(o); | |
931 } | |
932 public void clear() { | |
933 ConcurrentReaderHashMap.this.clear(); | |
934 } | |
935 } | |
936 | |
937 /** | |
938 * Returns a collection view of the mappings contained in this map. Each | |
939 * element in the returned collection is a <tt>Map.Entry</tt>. The | |
940 * collection is backed by the map, so changes to the map are reflected in | |
941 * the collection, and vice-versa. The collection supports element | |
942 * removal, which removes the corresponding mapping from the map, via the | |
943 * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, | |
944 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. | |
945 * It does not support the <tt>add</tt> or <tt>addAll</tt> operations. | |
946 * | |
947 * @return a collection view of the mappings contained in this map. | |
948 */ | |
949 | |
950 public Set entrySet() { | |
951 Set es = entrySet; | |
952 return (es != null) ? es : (entrySet = new EntrySet()); | |
953 } | |
954 | |
955 private class EntrySet extends AbstractSet { | |
956 public Iterator iterator() { | |
957 return new HashIterator(); | |
958 } | |
959 public boolean contains(Object o) { | |
960 if (!(o instanceof Map.Entry)) | |
961 return false; | |
962 Map.Entry entry = (Map.Entry)o; | |
963 Object v = ConcurrentReaderHashMap.this.get(entry.getKey()); | |
964 return v != null && v.equals(entry.getValue()); | |
965 } | |
966 public boolean remove(Object o) { | |
967 if (!(o instanceof Map.Entry)) | |
968 return false; | |
969 return ConcurrentReaderHashMap.this.findAndRemoveEntry((Map.Entry)o); | |
970 } | |
971 public int size() { | |
972 return ConcurrentReaderHashMap.this.size(); | |
973 } | |
974 public void clear() { | |
975 ConcurrentReaderHashMap.this.clear(); | |
976 } | |
977 } | |
978 | |
979 /** | |
980 * Helper method for entrySet.remove | |
981 **/ | |
982 protected synchronized boolean findAndRemoveEntry(Map.Entry entry) { | |
983 Object key = entry.getKey(); | |
984 Object v = get(key); | |
985 if (v != null && v.equals(entry.getValue())) { | |
986 remove(key); | |
987 return true; | |
988 } | |
989 else | |
990 return false; | |
991 } | |
992 | |
993 /** | |
994 * Returns an enumeration of the keys in this table. | |
995 * | |
996 * @return an enumeration of the keys in this table. | |
997 * @see Enumeration | |
998 * @see #elements() | |
999 * @see #keySet() | |
1000 * @see Map | |
1001 */ | |
1002 public Enumeration keys() { | |
1003 return new KeyIterator(); | |
1004 } | |
1005 | |
1006 /** | |
1007 * Returns an enumeration of the values in this table. | |
1008 * Use the Enumeration methods on the returned object to fetch the elements | |
1009 * sequentially. | |
1010 * | |
1011 * @return an enumeration of the values in this table. | |
1012 * @see java.util.Enumeration | |
1013 * @see #keys() | |
1014 * @see #values() | |
1015 * @see Map | |
1016 */ | |
1017 | |
1018 public Enumeration elements() { | |
1019 return new ValueIterator(); | |
1020 } | |
1021 | |
1022 | |
1023 /** | |
1024 * ConcurrentReaderHashMap collision list entry. | |
1025 */ | |
1026 | |
1027 protected static class Entry implements Map.Entry { | |
1028 | |
1029 /* | |
1030 The use of volatile for value field ensures that | |
1031 we can detect status changes without synchronization. | |
1032 The other fields are never changed, and are | |
1033 marked as final. | |
1034 */ | |
1035 | |
1036 protected final int hash; | |
1037 protected final Object key; | |
1038 protected final Entry next; | |
1039 protected volatile Object value; | |
1040 | |
1041 Entry(int hash, Object key, Object value, Entry next) { | |
1042 this.hash = hash; | |
1043 this.key = key; | |
1044 this.next = next; | |
1045 this.value = value; | |
1046 } | |
1047 | |
1048 // Map.Entry Ops | |
1049 | |
1050 public Object getKey() { | |
1051 return key; | |
1052 } | |
1053 | |
1054 /** | |
1055 * Get the value. Note: In an entrySet or entrySet.iterator, | |
1056 * unless the set or iterator is used under synchronization of the | |
1057 * table as a whole (or you can otherwise guarantee lack of | |
1058 * concurrent modification), <tt>getValue</tt> <em>might</em> | |
1059 * return null, reflecting the fact that the entry has been | |
1060 * concurrently removed. However, there are no assurances that | |
1061 * concurrent removals will be reflected using this method. | |
1062 * | |
1063 * @return the current value, or null if the entry has been | |
1064 * detectably removed. | |
1065 **/ | |
1066 public Object getValue() { | |
1067 return value; | |
1068 } | |
1069 | |
1070 /** | |
1071 * Set the value of this entry. Note: In an entrySet or | |
1072 * entrySet.iterator), unless the set or iterator is used under | |
1073 * synchronization of the table as a whole (or you can otherwise | |
1074 * guarantee lack of concurrent modification), <tt>setValue</tt> | |
1075 * is not strictly guaranteed to actually replace the value field | |
1076 * obtained via the <tt>get</tt> operation of the underlying hash | |
1077 * table in multithreaded applications. If iterator-wide | |
1078 * synchronization is not used, and any other concurrent | |
1079 * <tt>put</tt> or <tt>remove</tt> operations occur, sometimes | |
1080 * even to <em>other</em> entries, then this change is not | |
1081 * guaranteed to be reflected in the hash table. (It might, or it | |
1082 * might not. There are no assurances either way.) | |
1083 * | |
1084 * @param value the new value. | |
1085 * @return the previous value, or null if entry has been detectably | |
1086 * removed. | |
1087 * @exception NullPointerException if the value is <code>null</code>. | |
1088 * | |
1089 **/ | |
1090 | |
1091 public Object setValue(Object value) { | |
1092 if (value == null) | |
1093 throw new NullPointerException(); | |
1094 Object oldValue = this.value; | |
1095 this.value = value; | |
1096 return oldValue; | |
1097 } | |
1098 | |
1099 public boolean equals(Object o) { | |
1100 if (!(o instanceof Map.Entry)) | |
1101 return false; | |
1102 Map.Entry e = (Map.Entry)o; | |
1103 return (key.equals(e.getKey()) && value.equals(e.getValue())); | |
1104 } | |
1105 | |
1106 public int hashCode() { | |
1107 return key.hashCode() ^ value.hashCode(); | |
1108 } | |
1109 | |
1110 public String toString() { | |
1111 return key + "=" + value; | |
1112 } | |
1113 | |
1114 } | |
1115 | |
1116 protected class HashIterator implements Iterator, Enumeration { | |
1117 protected final Entry[] tab; // snapshot of table | |
1118 protected int index; // current slot | |
1119 protected Entry entry = null; // current node of slot | |
1120 protected Object currentKey; // key for current node | |
1121 protected Object currentValue; // value for current node | |
1122 protected Entry lastReturned = null; // last node returned by next | |
1123 | |
1124 protected HashIterator() { | |
1125 tab = ConcurrentReaderHashMap.this.getTableForReading(); | |
1126 index = tab.length - 1; | |
1127 } | |
1128 | |
1129 public boolean hasMoreElements() { return hasNext(); } | |
1130 public Object nextElement() { return next(); } | |
1131 | |
1132 | |
1133 public boolean hasNext() { | |
1134 | |
1135 /* | |
1136 currentkey and currentValue are set here to ensure that next() | |
1137 returns normally if hasNext() returns true. This avoids | |
1138 surprises especially when final element is removed during | |
1139 traversal -- instead, we just ignore the removal during | |
1140 current traversal. | |
1141 */ | |
1142 | |
1143 for (;;) { | |
1144 if (entry != null) { | |
1145 Object v = entry.value; | |
1146 if (v != null) { | |
1147 currentKey = entry.key; | |
1148 currentValue = v; | |
1149 return true; | |
1150 } | |
1151 else | |
1152 entry = entry.next; | |
1153 } | |
1154 | |
1155 while (entry == null && index >= 0) | |
1156 entry = tab[index--]; | |
1157 | |
1158 if (entry == null) { | |
1159 currentKey = currentValue = null; | |
1160 return false; | |
1161 } | |
1162 } | |
1163 } | |
1164 | |
1165 protected Object returnValueOfNext() { return entry; } | |
1166 | |
1167 public Object next() { | |
1168 if (currentKey == null && !hasNext()) | |
1169 throw new NoSuchElementException(); | |
1170 | |
1171 Object result = returnValueOfNext(); | |
1172 lastReturned = entry; | |
1173 currentKey = currentValue = null; | |
1174 entry = entry.next; | |
1175 return result; | |
1176 } | |
1177 | |
1178 public void remove() { | |
1179 if (lastReturned == null) | |
1180 throw new IllegalStateException(); | |
1181 ConcurrentReaderHashMap.this.remove(lastReturned.key); | |
1182 lastReturned = null; | |
1183 } | |
1184 | |
1185 } | |
1186 | |
1187 | |
1188 protected class KeyIterator extends HashIterator { | |
1189 protected Object returnValueOfNext() { return currentKey; } | |
1190 } | |
1191 | |
1192 protected class ValueIterator extends HashIterator { | |
1193 protected Object returnValueOfNext() { return currentValue; } | |
1194 } | |
1195 | |
1196 | |
1197 | |
1198 /** | |
1199 * Save the state of the <tt>ConcurrentReaderHashMap</tt> | |
1200 * instance to a stream (i.e., | |
1201 * serialize it). | |
1202 * | |
1203 * @serialData The <i>capacity</i> of the | |
1204 * ConcurrentReaderHashMap (the length of the | |
1205 * bucket array) is emitted (int), followed by the | |
1206 * <i>size</i> of the ConcurrentReaderHashMap (the number of key-value | |
1207 * mappings), followed by the key (Object) and value (Object) | |
1208 * for each key-value mapping represented by the ConcurrentReaderHashMap | |
1209 * The key-value mappings are emitted in no particular order. | |
1210 */ | |
1211 | |
1212 private synchronized void writeObject(java.io.ObjectOutputStream s) | |
1213 throws IOException { | |
1214 // Write out the threshold, loadfactor, and any hidden stuff | |
1215 s.defaultWriteObject(); | |
1216 | |
1217 // Write out number of buckets | |
1218 s.writeInt(table.length); | |
1219 | |
1220 // Write out size (number of Mappings) | |
1221 s.writeInt(count); | |
1222 | |
1223 // Write out keys and values (alternating) | |
1224 for (int index = table.length-1; index >= 0; index--) { | |
1225 Entry entry = table[index]; | |
1226 | |
1227 while (entry != null) { | |
1228 s.writeObject(entry.key); | |
1229 s.writeObject(entry.value); | |
1230 entry = entry.next; | |
1231 } | |
1232 } | |
1233 } | |
1234 | |
1235 /** | |
1236 * Reconstitute the <tt>ConcurrentReaderHashMap</tt> | |
1237 * instance from a stream (i.e., | |
1238 * deserialize it). | |
1239 */ | |
1240 private synchronized void readObject(java.io.ObjectInputStream s) | |
1241 throws IOException, ClassNotFoundException { | |
1242 // Read in the threshold, loadfactor, and any hidden stuff | |
1243 s.defaultReadObject(); | |
1244 | |
1245 // Read in number of buckets and allocate the bucket array; | |
1246 int numBuckets = s.readInt(); | |
1247 table = new Entry[numBuckets]; | |
1248 | |
1249 // Read in size (number of Mappings) | |
1250 int size = s.readInt(); | |
1251 | |
1252 // Read the keys and values, and put the mappings in the table | |
1253 for (int i=0; i<size; i++) { | |
1254 Object key = s.readObject(); | |
1255 Object value = s.readObject(); | |
1256 put(key, value); | |
1257 } | |
1258 } | |
1259 | |
1260 /** | |
1261 * Return the number of slots in this table | |
1262 **/ | |
1263 | |
1264 public synchronized int capacity() { | |
1265 return table.length; | |
1266 } | |
1267 | |
1268 /** | |
1269 * Return the load factor | |
1270 **/ | |
1271 public float loadFactor() { | |
1272 return loadFactor; | |
1273 } | |
1274 } |