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