Java > Open Source Codes > org > apache > beehive > netui > util > internal > concurrent > InternalConcurrentHashMap


1 /*
2  * Written by Doug Lea with assistance from members of JCP JSR-166
3  * Expert Group and released to the public domain, as explained at
4  * http://creativecommons.org/licenses/publicdomain
5  */
6
7 package org.apache.beehive.netui.util.internal.concurrent;
8
9 import java.util.*;
10 import java.io.Serializable ;
11 import java.io.IOException ;
12 import java.io.ObjectInputStream ;
13 import java.io.ObjectOutputStream ;
14
15 /**
16  * A hash table supporting full concurrency of retrievals and
17  * adjustable expected concurrency for updates. This class obeys the
18  * same functional specification as {@link java.util.Hashtable}, and
19  * includes versions of methods corresponding to each method of
20  * <tt>Hashtable</tt>. However, even though all operations are
21  * thread-safe, retrieval operations do <em>not</em> entail locking,
22  * and there is <em>not</em> any support for locking the entire table
23  * in a way that prevents all access. This class is fully
24  * interoperable with <tt>Hashtable</tt> in programs that rely on its
25  * thread safety but not on its synchronization details.
26  *
27  * <p> Retrieval operations (including <tt>get</tt>) generally do not
28  * block, so may overlap with update operations (including
29  * <tt>put</tt> and <tt>remove</tt>). Retrievals reflect the results
30  * of the most recently <em>completed</em> update operations holding
31  * upon their onset. For aggregate operations such as <tt>putAll</tt>
32  * and <tt>clear</tt>, concurrent retrievals may reflect insertion or
33  * removal of only some entries. Similarly, Iterators and
34  * Enumerations return elements reflecting the state of the hash table
35  * at some point at or since the creation of the iterator/enumeration.
36  * They do <em>not</em> throw
37  * {@link ConcurrentModificationException}. However, iterators are
38  * designed to be used by only one thread at a time.
39  *
40  * <p> The allowed concurrency among update operations is guided by
41  * the optional <tt>concurrencyLevel</tt> constructor argument
42  * (default 16), which is used as a hint for internal sizing. The
43  * table is internally partitioned to try to permit the indicated
44  * number of concurrent updates without contention. Because placement
45  * in hash tables is essentially random, the actual concurrency will
46  * vary. Ideally, you should choose a value to accommodate as many
47  * threads as will ever concurrently modify the table. Using a
48  * significantly higher value than you need can waste space and time,
49  * and a significantly lower value can lead to thread contention. But
50  * overestimates and underestimates within an order of magnitude do
51  * not usually have much noticeable impact. A value of one is
52  * appropriate when it is known that only one thread will modify and
53  * all others will only read. Also, resizing this or any other kind of
54  * hash table is a relatively slow operation, so, when possible, it is
55  * a good idea to provide estimates of expected table sizes in
56  * constructors.
57  *
58  * <p>This class and its views and iterators implement all of the
59  * <em>optional</em> methods of the {@link Map} and {@link Iterator}
60  * interfaces.
61  *
62  * <p> Like {@link java.util.Hashtable} but unlike {@link
63  * java.util.HashMap}, this class does NOT allow <tt>null</tt> to be
64  * used as a key or value.
65  *
66  * <p>This class is a member of the
67  * <a HREF="{@docRoot}/../guide/collections/index.html">
68  * Java Collections Framework</a>.
69  *
70  * @since 1.5
71  * @author Doug Lea
72  */
73 public class InternalConcurrentHashMap extends AbstractMap
74         implements Map, Serializable {
75     private static final long serialVersionUID = 7249069246763182397L;
76
77     /*
78      * The basic strategy is to subdivide the table among Segments,
79      * each of which itself is a concurrently readable hash table.
80      */
81
82     /* ---------------- Constants -------------- */
83
84     /**
85      * The default initial number of table slots for this table.
86      * Used when not otherwise specified in constructor.
87      */
88     static int DEFAULT_INITIAL_CAPACITY = 16;
89
90     /**
91      * The maximum capacity, used if a higher value is implicitly
92      * specified by either of the constructors with arguments. MUST
93      * be a power of two <= 1<<30 to ensure that entries are indexible
94      * using ints.
95      */
96     static final int MAXIMUM_CAPACITY = 1 << 30;
97
98     /**
99      * The default load factor for this table. Used when not
100      * otherwise specified in constructor.
101      */
102     static final float DEFAULT_LOAD_FACTOR = 0.75f;
103
104     /**
105      * The default number of concurrency control segments.
106      **/
107     static final int DEFAULT_SEGMENTS = 16;
108
109     /**
110      * The maximum number of segments to allow; used to bound
111      * constructor arguments.
112      */
113     static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
114
115     /**
116      * Number of unsynchronized retries in size and containsValue
117      * methods before resorting to locking. This is used to avoid
118      * unbounded retries if tables undergo continuous modification
119      * which would make it impossible to obtain an accurate result.
120      */
121     static final int RETRIES_BEFORE_LOCK = 2;
122
123     /* ---------------- Fields -------------- */
124
125     /**
126      * Mask value for indexing into segments. The upper bits of a
127      * key's hash code are used to choose the segment.
128      **/
129     final int segmentMask;
130
131     /**
132      * Shift value for indexing within segments.
133      **/
134     final int segmentShift;
135
136     /**
137      * The segments, each of which is a specialized hash table
138      */
139     final Segment[] segments;
140
141     transient Set keySet;
142     transient Set entrySet;
143     transient Collection values;
144
145     /* ---------------- Small Utilities -------------- */
146
147     /**
148      * Returns a hash code for non-null Object x.
149      * Uses the same hash code spreader as most other java.util hash tables.
150      * @param x the object serving as a key
151      * @return the hash code
152      */
153     static int hash(Object x) {
154         int h = x.hashCode();
155         h += ~(h << 9);
156         h ^= (h >>> 14);
157         h += (h << 4);
158         h ^= (h >>> 10);
159         return h;
160     }
161
162     /**
163      * Returns the segment that should be used for key with given hash
164      * @param hash the hash code for the key
165      * @return the segment
166      */
167     final Segment segmentFor(int hash) {
168         return (Segment) segments[(hash >>> segmentShift) & segmentMask];
169     }
170
171     /* ---------------- Inner Classes -------------- */
172
173     /**
174      * InternalConcurrentHashMap list entry. Note that this is never exported
175      * out as a user-visible Map.Entry.
176      *
177      * Because the value field is volatile, not final, it is legal wrt
178      * the Java Memory Model for an unsynchronized reader to see null
179      * instead of initial value when read via a data race. Although a
180      * reordering leading to this is not likely to ever actually
181      * occur, the Segment.readValueUnderLock method is used as a
182      * backup in case a null (pre-initialized) value is ever seen in
183      * an unsynchronized access method.
184      */
185     static final class HashEntry {
186         final Object key;
187         final int hash;
188         volatile Object value;
189         final HashEntry next;
190
191         HashEntry(Object key, int hash, HashEntry next, Object value) {
192             this.key = key;
193             this.hash = hash;
194             this.next = next;
195             this.value = value;
196         }
197     }
198
199     /**
200      * Segments are specialized versions of hash tables. This
201      * subclasses from ReentrantLock opportunistically, just to
202      * simplify some locking and avoid separate construction.
203      **/
204     static final class Segment extends ReentrantLock implements Serializable {
205         /*
206          * Segments maintain a table of entry lists that are ALWAYS
207          * kept in a consistent state, so can be read without locking.
208          * Next fields of nodes are immutable (final). All list
209          * additions are performed at the front of each bin. This
210          * makes it easy to check changes, and also fast to traverse.
211          * When nodes would otherwise be changed, new nodes are
212          * created to replace them. This works well for hash tables
213          * since the bin lists tend to be short. (The average length
214          * is less than two for the default load factor threshold.)
215          *
216          * Read operations can thus proceed without locking, but rely
217          * on selected uses of volatiles to ensure that completed
218          * write operations performed by other threads are
219          * noticed. For most purposes, the "count" field, tracking the
220          * number of elements, serves as that volatile variable
221          * ensuring visibility. This is convenient because this field
222          * needs to be read in many read operations anyway:
223          *
224          * - All (unsynchronized) read operations must first read the
225          * "count" field, and should not look at table entries if
226          * it is 0.
227          *
228          * - All (synchronized) write operations should write to
229          * the "count" field after structurally changing any bin.
230          * The operations must not take any action that could even
231          * momentarily cause a concurrent read operation to see
232          * inconsistent data. This is made easier by the nature of
233          * the read operations in Map. For example, no operation
234          * can reveal that the table has grown but the threshold
235          * has not yet been updated, so there are no atomicity
236          * requirements for this with respect to reads.
237          *
238          * As a guide, all critical volatile reads and writes to the
239          * count field are marked in code comments.
240          */
241
242         private static final long serialVersionUID = 2249069246763182397L;
243
244         /**
245          * The number of elements in this segment's region.
246          **/
247         transient volatile int count;
248
249         /**
250          * Number of updates that alter the size of the table. This is
251          * used during bulk-read methods to make sure they see a
252          * consistent snapshot: If modCounts change during a traversal
253          * of segments computing size or checking containsValue, then
254          * we might have an inconsistent view of state so (usually)
255          * must retry.
256          */
257         transient int modCount;
258
259         /**
260          * The table is rehashed when its size exceeds this threshold.
261          * (The value of this field is always (int)(capacity *
262          * loadFactor).)
263          */
264         transient int threshold;
265
266         /**
267          * The per-segment table. Declared as a raw type, casted
268          * to HashEntry on each use.
269          */
270         transient volatile HashEntry[] table;
271
272         /**
273          * The load factor for the hash table. Even though this value
274          * is same for all segments, it is replicated to avoid needing
275          * links to outer object.
276          * @serial
277          */
278         final float loadFactor;
279
280         Segment(int initialCapacity, float lf) {
281             loadFactor = lf;
282             setTable(new HashEntry[initialCapacity]);
283         }
284
285         /**
286          * Set table to new HashEntry array.
287          * Call only while holding lock or in constructor.
288          **/
289         void setTable(HashEntry[] newTable) {
290             threshold = (int)(newTable.length * loadFactor);
291             table = newTable;
292         }
293
294         /**
295          * Return properly casted first entry of bin for given hash
296          */
297         HashEntry getFirst(int hash) {
298             HashEntry[] tab = table;
299             return (HashEntry) tab[hash & (tab.length - 1)];
300         }
301
302         /**
303          * Read value field of an entry under lock. Called if value
304          * field ever appears to be null. This is possible only if a
305          * compiler happens to reorder a HashEntry initialization with
306          * its table assignment, which is legal under memory model
307          * but is not known to ever occur.
308          */
309         Object readValueUnderLock(HashEntry e) {
310             lock();
311             try {
312                 return e.value;
313             } finally {
314                 unlock();
315             }
316         }
317
318         /* Specialized implementations of map methods */
319
320         Object get(Object key, int hash) {
321             if (count != 0) { // read-volatile
322 HashEntry e = getFirst(hash);
323                 while (e != null) {
324                     if (e.hash == hash && key.equals(e.key)) {
325                         Object v = e.value;
326                         if (v != null)
327                             return v;
328                         return readValueUnderLock(e); // recheck
329 }
330                     e = e.next;
331                 }
332             }
333             return null;
334         }
335
336         boolean containsKey(Object key, int hash) {
337             if (count != 0) { // read-volatile
338 HashEntry e = getFirst(hash);
339                 while (e != null) {
340                     if (e.hash == hash && key.equals(e.key))
341                         return true;
342                     e = e.next;
343                 }
344             }
345             return false;
346         }
347
348         boolean containsValue(Object value) {
349             if (count != 0) { // read-volatile
350 HashEntry[] tab = table;
351                 int len = tab.length;
352                 for (int i = 0 ; i < len; i++) {
353                     for (HashEntry e = (HashEntry)tab[i];
354                          e != null ;
355                          e = e.next) {
356                         Object v = e.value;
357                         if (v == null) // recheck
358 v = readValueUnderLock(e);
359                         if (value.equals(v))
360                             return true;
361                     }
362                 }
363             }
364             return false;
365         }
366
367         boolean replace(Object key, int hash, Object oldValue, Object newValue) {
368             lock();
369             try {
370                 HashEntry e = getFirst(hash);
371                 while (e != null && (e.hash != hash || !key.equals(e.key)))
372                     e = e.next;
373
374                 boolean replaced = false;
375                 if (e != null && oldValue.equals(e.value)) {
376                     replaced = true;
377                     e.value = newValue;
378                 }
379                 return replaced;
380             } finally {
381                 unlock();
382             }
383         }
384
385         Object replace(Object key, int hash, Object newValue) {
386             lock();
387             try {
388                 HashEntry e = getFirst(hash);
389                 while (e != null && (e.hash != hash || !key.equals(e.key)))
390                     e = e.next;
391
392                 Object oldValue = null;
393                 if (e != null) {
394                     oldValue = e.value;
395                     e.value = newValue;
396                 }
397                 return oldValue;
398             } finally {
399                 unlock();
400             }
401         }
402
403
404         Object put(Object key, int hash, Object value, boolean onlyIfAbsent) {
405             lock();
406             try {
407                 int c = count;
408                 if (c++ > threshold) // ensure capacity
409 rehash();
410                 HashEntry[] tab = table;
411                 int index = hash & (tab.length - 1);
412                 HashEntry first = (HashEntry) tab[index];
413                 HashEntry e = first;
414                 while (e != null && (e.hash != hash || !key.equals(e.key)))
415                     e = e.next;
416
417                 Object oldValue;
418                 if (e != null) {
419                     oldValue = e.value;
420                     if (!onlyIfAbsent)
421                         e.value = value;
422                 }
423                 else {
424                     oldValue = null;
425                     ++modCount;
426                     tab[index] = new HashEntry(key, hash, first, value);
427                     count = c; // write-volatile
428 }
429                 return oldValue;
430             } finally {
431                 unlock();
432             }
433         }
434
435         void rehash() {
436             HashEntry[] oldTable = table;
437             int oldCapacity = oldTable.length;
438             if (oldCapacity >= MAXIMUM_CAPACITY)
439                 return;
440
441             /*
442              * Reclassify nodes in each list to new Map. Because we are
443              * using power-of-two expansion, the elements from each bin
444              * must either stay at same index, or move with a power of two
445              * offset. We eliminate unnecessary node creation by catching
446              * cases where old nodes can be reused because their next
447              * fields won't change. Statistically, at the default
448              * threshold, only about one-sixth of them need cloning when
449              * a table doubles. The nodes they replace will be garbage
450              * collectable as soon as they are no longer referenced by any
451              * reader thread that may be in the midst of traversing table
452              * right now.
453              */
454
455             HashEntry[] newTable = new HashEntry[oldCapacity << 1];
456             threshold = (int)(newTable.length * loadFactor);
457             int sizeMask = newTable.length - 1;
458             for (int i = 0; i < oldCapacity ; i++) {
459                 // We need to guarantee that any existing reads of old Map can
460 // proceed. So we cannot yet null out each bin.
461 HashEntry e = (HashEntry)oldTable[i];
462
463                 if (e != null) {
464                     HashEntry next = e.next;
465                     int idx = e.hash & sizeMask;
466
467                     // Single node on list
468 if (next == null)
469                         newTable[idx] = e;
470
471                     else {
472                         // Reuse trailing consecutive sequence at same slot
473 HashEntry lastRun = e;
474                         int lastIdx = idx;
475                         for (HashEntry last = next;
476                              last != null;
477                              last = last.next) {
478                             int k = last.hash & sizeMask;
479                             if (k != lastIdx) {
480                                 lastIdx = k;
481                                 lastRun = last;
482                             }
483                         }
484                         newTable[lastIdx] = lastRun;
485
486                         // Clone all remaining nodes
487 for (HashEntry p = e; p != lastRun; p = p.next) {
488                             int k = p.hash & sizeMask;
489                             HashEntry n = (HashEntry)newTable[k];
490                             newTable[k] = new HashEntry(p.key, p.hash,
491                                                              n, p.value);
492                         }
493                     }
494                 }
495             }
496             table = newTable;
497         }
498
499         /**
500          * Remove; match on key only if value null, else match both.
501          */
502         Object remove(Object key, int hash, Object value) {
503             lock();
504             try {
505                 int c = count - 1;
506                 HashEntry[] tab = table;
507                 int index = hash & (tab.length - 1);
508                 HashEntry first = (HashEntry)tab[index];
509                 HashEntry e = first;
510                 while (e != null && (e.hash != hash || !key.equals(e.key)))
511                     e = e.next;
512
513                 Object oldValue = null;
514                 if (e != null) {
515                     Object v = e.value;
516                     if (value == null || value.equals(v)) {
517                         oldValue = v;
518                         // All entries following removed node can stay
519 // in list, but all preceding ones need to be
520 // cloned.
521 ++modCount;
522                         HashEntry newFirst = e.next;
523                         for (HashEntry p = first; p != e; p = p.next)
524                             newFirst = new HashEntry(p.key, p.hash,
525                                                           newFirst, p.value);
526                         tab[index] = newFirst;
527                         count = c; // write-volatile
528 }
529                 }
530                 return oldValue;
531             } finally {
532                 unlock();
533             }
534         }
535
536         void clear() {
537             if (count != 0) {
538                 lock();
539                 try {
540                     HashEntry[] tab = table;
541                     for (int i = 0; i < tab.length ; i++)
542                         tab[i] = null;
543                     ++modCount;
544                     count = 0; // write-volatile
545 } finally {
546                     unlock();
547                 }
548             }
549         }
550     }
551
552
553
554     /* ---------------- Public operations -------------- */
555
556     /**
557      * Creates a new, empty map with the specified initial
558      * capacity and the specified load factor.
559      *
560      * @param initialCapacity the initial capacity. The implementation
561      * performs internal sizing to accommodate this many elements.
562      * @param loadFactor the load factor threshold, used to control resizing.
563      * @param concurrencyLevel the estimated number of concurrently
564      * updating threads. The implementation performs internal sizing
565      * to try to accommodate this many threads.
566      * @throws IllegalArgumentException if the initial capacity is
567      * negative or the load factor or concurrencyLevel are
568      * nonpositive.
569      */
570     public InternalConcurrentHashMap(int initialCapacity,
571                              float loadFactor, int concurrencyLevel) {
572         if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
573             throw new IllegalArgumentException ();
574
575         if (concurrencyLevel > MAX_SEGMENTS)
576             concurrencyLevel = MAX_SEGMENTS;
577
578         // Find power-of-two sizes best matching arguments
579 int sshift = 0;
580         int ssize = 1;
581         while (ssize < concurrencyLevel) {
582             ++sshift;
583             ssize <<= 1;
584         }
585         segmentShift = 32 - sshift;
586         segmentMask = ssize - 1;
587         this.segments = new Segment[ssize];
588
589         if (initialCapacity > MAXIMUM_CAPACITY)
590             initialCapacity = MAXIMUM_CAPACITY;
591         int c = initialCapacity / ssize;
592         if (c * ssize < initialCapacity)
593             ++c;
594         int cap = 1;
595         while (cap < c)
596             cap <<= 1;
597
598         for (int i = 0; i < this.segments.length; ++i)
599             this.segments[i] = new Segment(cap, loadFactor);
600     }
601
602     /**
603      * Creates a new, empty map with the specified initial
604      * Creates a new, empty map with the specified initial capacity
605      * and load factor and with the default concurrencyLevel (16).
606      *
607      * @param initialCapacity The implementation performs internal
608      * sizing to accommodate this many elements.
609      * @param loadFactor the load factor threshold, used to control resizing.
610      * @throws IllegalArgumentException if the initial capacity of
611      * elements is negative or the load factor is nonpositive
612      */
613     public InternalConcurrentHashMap(int initialCapacity, float loadFactor) {
614         this(initialCapacity, loadFactor, DEFAULT_SEGMENTS);
615     }
616
617     /**
618      * capacity, and with default load factor (0.75f) and
619      * concurrencyLevel (16).
620      *
621      * @param initialCapacity The implementation performs internal
622      * sizing to accommodate this many elements.
623      * @throws IllegalArgumentException if the initial capacity of
624      * elements is negative.
625      */
626     public InternalConcurrentHashMap(int initialCapacity) {
627         this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
628     }
629
630     /**
631      * Creates a new, empty map with a default initial capacity (16),
632      * load factor (0.75f), and concurrencyLevel (16).
633      */
634     public InternalConcurrentHashMap() {
635         this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
636     }
637
638     /**
639      * Creates a new map with the same mappings as the given map. The
640      * map is created with a capacity of 1.5 times the number of
641      * mappings in the given map or 16 (whichever is greater), and a
642      * default load factor (0.75f) and concurrencyLevel(16).
643      * @param t the map
644      */
645     public InternalConcurrentHashMap(Map t) {
646         this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1,
647                       16),
648              DEFAULT_LOAD_FACTOR, DEFAULT_SEGMENTS);
649         putAll(t);
650     }
651
652     // inherit Map javadoc
653 public boolean isEmpty() {
654         final Segment[] segments = this.segments;
655         /*
656          * We keep track of per-segment modCounts to avoid ABA
657          * problems in which an element in one segment was added and
658          * in another removed during traversal, in which case the
659          * table was never actually empty at any point. Note the
660          * similar use of modCounts in the size() and containsValue()
661          * methods, which are the only other methods also susceptible
662          * to ABA problems.
663          */
664         int[] mc = new int[segments.length];
665         int mcsum = 0;
666         for (int i = 0; i < segments.length; ++i) {
667             if (segments[i].count != 0)
668                 return false;
669             else
670                 mcsum += mc[i] = segments[i].modCount;
671         }
672         // If mcsum happens to be zero, then we know we got a snapshot
673 // before any modifications at all were made. This is
674 // probably common enough to bother tracking.
675 if (mcsum != 0) {
676             for (int i = 0; i < segments.length; ++i) {
677                 if (segments[i].count != 0 ||
678                     mc[i] != segments[i].modCount)
679                     return false;
680             }
681         }
682         return true;
683     }
684
685     // inherit Map javadoc
686 public int size() {
687         final Segment[] segments = this.segments;
688         long sum = 0;
689         long check = 0;
690         int[] mc = new int[segments.length];
691         // Try a few times to get accurate count. On failure due to
692 // continuous async changes in table, resort to locking.
693 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
694             check = 0;
695             sum = 0;
696             int mcsum = 0;
697             for (int i = 0; i < segments.length; ++i) {
698                 sum += segments[i].count;
699                 mcsum += mc[i] = segments[i].modCount;
700             }
701             if (mcsum != 0) {
702                 for (int i = 0; i < segments.length; ++i) {
703                     check += segments[i].count;
704                     if (mc[i] != segments[i].modCount) {
705                         check = -1; // force retry
706 break;
707                     }
708                 }
709             }
710             if (check == sum)
711                 break;
712         }
713         if (check != sum) { // Resort to locking all segments
714 sum = 0;
715             for (int i = 0; i < segments.length; ++i)
716                 segments[i].lock();
717             for (int i = 0; i < segments.length; ++i)
718                 sum += segments[i].count;
719             for (int i = 0; i < segments.length; ++i)
720                 segments[i].unlock();
721         }
722         if (sum > Integer.MAX_VALUE)
723             return Integer.MAX_VALUE;
724         else
725             return (int)sum;
726     }
727
728
729     /**
730      * Returns the value to which the specified key is mapped in this table.
731      *
732      * @param key a key in the table.
733      * @return the value to which the key is mapped in this table;
734      * <tt>null</tt> if the key is not mapped to any value in
735      * this table.
736      * @throws NullPointerException if the key is
737      * <tt>null</tt>.
738      */
739     public Object get(Object key) {
740         int hash = hash(key); // throws NullPointerException if key null
741 return segmentFor(hash).get(key, hash);
742     }
743
744     /**
745      * Tests if the specified object is a key in this table.
746      *
747      * @param key possible key.
748      * @return <tt>true</tt> if and only if the specified object
749      * is a key in this table, as determined by the
750      * <tt>equals</tt> method; <tt>false</tt> otherwise.
751      * @throws NullPointerException if the key is
752      * <tt>null</tt>.
753      */
754     public boolean containsKey(Object key) {
755         int hash = hash(key); // throws NullPointerException if key null
756 return segmentFor(hash).containsKey(key, hash);
757     }
758
759     /**
760      * Returns <tt>true</tt> if this map maps one or more keys to the
761      * specified value. Note: This method requires a full internal
762      * traversal of the hash table, and so is much slower than
763      * method <tt>containsKey</tt>.
764      *
765      * @param value value whose presence in this map is to be tested.
766      * @return <tt>true</tt> if this map maps one or more keys to the
767      * specified value.
768      * @throws NullPointerException if the value is <tt>null</tt>.
769      */
770     public boolean containsValue(Object value) {
771         if (value == null)
772             throw new NullPointerException ();
773
774         // See explanation of modCount use above
775
776         final Segment[] segments = this.segments;
777         int[] mc = new int[segments.length];
778
779         // Try a few times without locking
780 for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
781             int sum = 0;
782             int mcsum = 0;
783             for (int i = 0; i < segments.length; ++i) {
784                 int c = segments[i].count;
785                 mcsum += mc[i] = segments[i].modCount;
786                 if (segments[i].containsValue(value))
787                     return true;
788             }
789             boolean cleanSweep = true;
790             if (mcsum != 0) {
791                 for (int i = 0; i < segments.length; ++i) {
792                     int c = segments[i].count;
793                     if (mc[i] != segments[i].modCount) {
794                         cleanSweep = false;
795                         break;
796                     }
797                 }
798             }
799             if (cleanSweep)
800                 return false;
801         }
802         // Resort to locking all segments
803 for (int i = 0; i < segments.length; ++i)
804             segments[i].lock();
805         boolean found = false;
806         try {
807             for (int i = 0; i < segments.length; ++i) {
808                 if (segments[i].containsValue(value)) {
809                     found = true;
810                     break;
811                 }
812             }
813         } finally {
814             for (int i = 0; i < segments.length; ++i)
815                 segments[i].unlock();
816         }
817         return found;
818     }
819
820     /**
821      * Legacy method testing if some key maps into the specified value
822      * in this table. This method is identical in functionality to
823      * {@link #containsValue}, and exists solely to ensure
824      * full compatibility with class {@link java.util.Hashtable},
825      * which supported this method prior to introduction of the
826      * Java Collections framework.
827
828      * @param value a value to search for.
829      * @return <tt>true</tt> if and only if some key maps to the
830      * <tt>value</tt> argument in this table as
831      * determined by the <tt>equals</tt> method;
832      * <tt>false</tt> otherwise.
833      * @throws NullPointerException if the value is <tt>null</tt>.
834      */
835     public boolean contains(Object value) {
836         return containsValue(value);
837     }
838
839     /**
840      * Maps the specified <tt>key</tt> to the specified
841      * <tt>value</tt> in this table. Neither the key nor the
842      * value can be <tt>null</tt>.
843      *
844      * <p> The value can be retrieved by calling the <tt>get</tt> method
845      * with a key that is equal to the original key.
846      *
847      * @param key the table key.
848      * @param value the value.
849      * @return the previous value of the specified key in this table,
850      * or <tt>null</tt> if it did not have one.
851      * @throws NullPointerException if the key or value is
852      * <tt>null</tt>.
853      */
854     public Object put(Object key, Object value) {
855         if (value == null)
856             throw new NullPointerException ();
857         int hash = hash(key);
858         return segmentFor(hash).put(key, hash, value, false);
859     }
860
861     /**
862      * If the specified key is not already associated
863      * with a value, associate it with the given value.
864      * This is equivalent to
865      * <pre>
866      * if (!map.containsKey(key))
867      * return map.put(key, value);
868      * else
869      * return map.get(key);
870      * </pre>
871      * Except that the action is performed atomically.
872      * @param key key with which the specified value is to be associated.
873      * @param value value to be associated with the specified key.
874      * @return previous value associated with specified key, or <tt>null</tt>
875      * if there was no mapping for key.
876      * @throws NullPointerException if the specified key or value is
877      * <tt>null</tt>.
878      */
879     public Object putIfAbsent(Object key, Object value) {
880         if (value == null)
881             throw new NullPointerException ();
882         int hash = hash(key);
883         return segmentFor(hash).put(key, hash, value, true);
884     }
885
886
887     /**
888      * Copies all of the mappings from the specified map to this one.
889      *
890      * These mappings replace any mappings that this map had for any of the
891      * keys currently in the specified Map.
892      *
893      * @param t Mappings to be stored in this map.
894      */
895     public void putAll(Map t) {
896         for (Iterator it = t.entrySet().iterator(); it.hasNext(); ) {
897             Entry e = (Entry)it.next();
898             put(e.getKey(), e.getValue());
899         }
900     }
901
902     /**
903      * Removes the key (and its corresponding value) from this
904      * table. This method does nothing if the key is not in the table.
905      *
906      * @param key the key that needs to be removed.
907      * @return the value to which the key had been mapped in this table,
908      * or <tt>null</tt> if the key did not have a mapping.
909      * @throws NullPointerException if the key is
910      * <tt>null</tt>.
911      */
912     public Object remove(Object key) {
913         int hash = hash(key);
914         return segmentFor(hash).remove(key, hash, null);
915     }
916
917     /**
918      * Remove entry for key only if currently mapped to given value.
919      * Acts as
920      * <pre>
921      * if (map.get(key).equals(value)) {
922      * map.remove(key);
923      * return true;
924      * } else return false;
925      * </pre>
926      * except that the action is performed atomically.
927      * @param key key with which the specified value is associated.
928      * @param value value associated with the specified key.
929      * @return true if the value was removed
930      * @throws NullPointerException if the specified key is
931      * <tt>null</tt>.
932      */
933     public boolean remove(Object key, Object value) {
934         int hash = hash(key);
935         return segmentFor(hash).remove(key, hash, value) != null;
936     }
937
938
939     /**
940      * Replace entry for key only if currently mapped to given value.
941      * Acts as
942      * <pre>
943      * if (map.get(key).equals(oldValue)) {
944      * map.put(key, newValue);
945      * return true;
946      * } else return false;
947      * </pre>
948      * except that the action is performed atomically.
949      * @param key key with which the specified value is associated.
950      * @param oldValue value expected to be associated with the specified key.
951      * @param newValue value to be associated with the specified key.
952      * @return true if the value was replaced
953      * @throws NullPointerException if the specified key or values are
954      * <tt>null</tt>.
955      */
956     public boolean replace(Object key, Object oldValue, Object newValue) {
957         if (oldValue == null || newValue == null)
958             throw new NullPointerException ();
959         int hash = hash(key);
960         return segmentFor(hash).replace(key, hash, oldValue, newValue);
961     }
962
963     /**
964      * Replace entry for key only if currently mapped to some value.
965      * Acts as
966      * <pre>
967      * if ((map.containsKey(key)) {
968      * return map.put(key, value);
969      * } else return null;
970      * </pre>
971      * except that the action is performed atomically.
972      * @param key key with which the specified value is associated.
973      * @param value value to be associated with the specified key.
974      * @return previous value associated with specified key, or <tt>null</tt>
975      * if there was no mapping for key.
976      * @throws NullPointerException if the specified key or value is
977      * <tt>null</tt>.
978      */
979     public Object replace(Object key, Object value) {
980         if (value == null)
981             throw new NullPointerException ();
982         int hash = hash(key);
983         return segmentFor(hash).replace(key, hash, value);
984     }
985
986
987     /**
988      * Removes all mappings from this map.
989      */
990     public void clear() {
991         for (int i = 0; i < segments.length; ++i)
992             segments[i].clear();
993     }
994
995
996     /**
997      * Returns a set view of the keys contained in this map. The set is
998      * backed by the map, so changes to the map are reflected in the set, and
999      * vice-versa. The set supports element removal, which removes the
1000     * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
1001     * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
1002     * <tt>clear</tt> operations. It does not support the <tt>add</tt> or
1003     * <tt>addAll</tt> operations.
1004     * The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
1005     * will never throw {@link java.util.ConcurrentModificationException},
1006     * and guarantees to traverse elements as they existed upon
1007     * construction of the iterator, and may (but is not guaranteed to)
1008     * reflect any modifications subsequent to construction.
1009     *
1010     * @return a set view of the keys contained in this map.
1011     */
1012    public Set keySet() {
1013        Set ks = keySet;
1014        return (ks != null) ? ks : (keySet = new KeySet());
1015    }
1016
1017
1018    /**
1019     * Returns a collection view of the values contained in this map. The
1020     * collection is backed by the map, so changes to the map are reflected in
1021     * the collection, and vice-versa. The collection supports element
1022     * removal, which removes the corresponding mapping from this map, via the
1023     * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1024     * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1025     * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1026     * The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
1027     * will never throw {@link java.util.ConcurrentModificationException},
1028     * and guarantees to traverse elements as they existed upon
1029     * construction of the iterator, and may (but is not guaranteed to)
1030     * reflect any modifications subsequent to construction.
1031     *
1032     * @return a collection view of the values contained in this map.
1033     */
1034    public Collection values() {
1035        Collection vs = values;
1036        return (vs != null) ? vs : (values = new Values());
1037    }
1038
1039
1040    /**
1041     * Returns a collection view of the mappings contained in this map. Each
1042     * element in the returned collection is a <tt>Map.Entry</tt>. The
1043     * collection is backed by the map, so changes to the map are reflected in
1044     * the collection, and vice-versa. The collection supports element
1045     * removal, which removes the corresponding mapping from the map, via the
1046     * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
1047     * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
1048     * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
1049     * The view's returned <tt>iterator</tt> is a "weakly consistent" iterator that
1050     * will never throw {@link java.util.ConcurrentModificationException},
1051     * and guarantees to traverse elements as they existed upon
1052     * construction of the iterator, and may (but is not guaranteed to)
1053     * reflect any modifications subsequent to construction.
1054     *
1055     * @return a collection view of the mappings contained in this map.
1056     */
1057    public Set entrySet() {
1058        Set es = entrySet;
1059        return (es != null) ? es : (entrySet = new EntrySet());
1060    }
1061
1062
1063    /**
1064     * Returns an enumeration of the keys in this table.
1065     *
1066     * @return an enumeration of the keys in this table.
1067     * @see #keySet
1068     */
1069    public Enumeration keys() {
1070        return new KeyIterator();
1071    }
1072
1073    /**
1074     * Returns an enumeration of the values in this table.
1075     *
1076     * @return an enumeration of the values in this table.
1077     * @see #values
1078     */
1079    public Enumeration elements() {
1080        return new ValueIterator();
1081    }
1082
1083    /* ---------------- Iterator Support -------------- */
1084
1085    abstract class HashIterator {
1086        int nextSegmentIndex;
1087        int nextTableIndex;
1088        HashEntry[] currentTable;
1089        HashEntry nextEntry;
1090        HashEntry lastReturned;
1091
1092        HashIterator() {
1093            nextSegmentIndex = segments.length - 1;
1094            nextTableIndex = -1;
1095            advance();
1096        }
1097
1098        public boolean hasMoreElements() { return hasNext(); }
1099
1100        final void advance() {
1101            if (nextEntry != null && (nextEntry = nextEntry.next) != null)
1102                return;
1103
1104            while (nextTableIndex >= 0) {
1105                if ( (nextEntry = (HashEntry)currentTable[nextTableIndex--]) != null)
1106                    return;
1107            }
1108
1109            while (nextSegmentIndex >= 0) {
1110                Segment seg = (Segment)segments[nextSegmentIndex--];
1111                if (seg.count != 0) {
1112                    currentTable = seg.table;
1113                    for (int j = currentTable.length - 1; j >= 0; --j) {
1114                        if ( (nextEntry = (HashEntry)currentTable[j]) != null) {
1115                            nextTableIndex = j - 1;
1116                            return;
1117                        }
1118                    }
1119                }
1120            }
1121        }
1122
1123        public boolean hasNext() { return nextEntry != null; }
1124
1125        HashEntry nextEntry() {
1126            if (nextEntry == null)
1127                throw new NoSuchElementException();
1128            lastReturned = nextEntry;
1129            advance();
1130            return lastReturned;
1131        }
1132
1133        public void remove() {
1134            if (lastReturned == null)
1135                throw new IllegalStateException ();
1136            InternalConcurrentHashMap.this.remove(lastReturned.key);
1137            lastReturned = null;
1138        }
1139    }
1140
1141    final class KeyIterator extends HashIterator implements Iterator, Enumeration {
1142        public Object next() { return super.nextEntry().key; }
1143        public Object nextElement() { return super.nextEntry().key; }
1144    }
1145
1146    final class ValueIterator extends HashIterator implements Iterator, Enumeration {
1147        public Object next() { return super.nextEntry().value; }
1148        public Object nextElement() { return super.nextEntry().value; }
1149    }
1150
1151
1152
1153    /**
1154     * Entry iterator. Exported Entry objects must write-through
1155     * changes in setValue, even if the nodes have been cloned. So we
1156     * cannot return internal HashEntry objects. Instead, the iterator
1157     * itself acts as a forwarding pseudo-entry.
1158     */
1159    final class EntryIterator extends HashIterator implements Map.Entry, Iterator {
1160        public Object next() {
1161            nextEntry();
1162            return this;
1163        }
1164
1165        public Object getKey() {
1166            if (lastReturned == null)
1167                throw new IllegalStateException ("Entry was removed");
1168            return lastReturned.key;
1169        }
1170
1171        public Object getValue() {
1172            if (lastReturned == null)
1173                throw new IllegalStateException ("Entry was removed");
1174            return InternalConcurrentHashMap.this.get(lastReturned.key);
1175        }
1176
1177        public Object setValue(Object value) {
1178            if (lastReturned == null)
1179                throw new IllegalStateException ("Entry was removed");
1180            return InternalConcurrentHashMap.this.put(lastReturned.key, value);
1181        }
1182
1183        public boolean equals(Object o) {
1184            // If not acting as entry, just use default.
1185 if (lastReturned == null)
1186                return super.equals(o);
1187            if (!(o instanceof Map.Entry))
1188                return false;
1189            Map.Entry e = (Map.Entry)o;
1190            return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
1191        }
1192
1193        public int hashCode() {
1194            // If not acting as entry, just use default.
1195 if (lastReturned == null)
1196                return super.hashCode();
1197
1198            Object k = getKey();
1199            Object v = getValue();
1200            return ((k == null) ? 0 : k.hashCode()) ^
1201                   ((v == null) ? 0 : v.hashCode());
1202        }
1203
1204        public String toString() {
1205            // If not acting as entry, just use default.
1206 if (lastReturned == null)
1207                return super.toString();
1208            else
1209                return getKey() + "=" + getValue();
1210        }
1211
1212        boolean eq(Object o1, Object o2) {
1213            return (o1 == null ? o2 == null : o1.equals(o2));
1214        }
1215
1216    }
1217
1218    final class KeySet extends AbstractSet {
1219        public Iterator iterator() {
1220            return new KeyIterator();
1221        }
1222        public int size() {
1223            return InternalConcurrentHashMap.this.size();
1224        }
1225        public boolean contains(Object o) {
1226            return InternalConcurrentHashMap.this.containsKey(o);
1227        }
1228        public boolean remove(Object o) {
1229            return InternalConcurrentHashMap.this.remove(o) != null;
1230        }
1231        public void clear() {
1232            InternalConcurrentHashMap.this.clear();
1233        }
1234        public Object [] toArray() {
1235            Collection c = new ArrayList();
1236            for (Iterator i = iterator(); i.hasNext(); )
1237                c.add(i.next());
1238            return c.toArray();
1239        }
1240        public Object [] toArray(Object [] a) {
1241            Collection c = new ArrayList();
1242            for (Iterator i = iterator(); i.hasNext(); )
1243                c.add(i.next());
1244            return c.toArray(a);
1245        }
1246    }
1247
1248    final class Values extends AbstractCollection {
1249        public Iterator iterator() {
1250            return new ValueIterator();
1251        }
1252        public int size() {
1253            return InternalConcurrentHashMap.this.size();
1254        }
1255        public boolean contains(Object o) {
1256            return InternalConcurrentHashMap.this.containsValue(o);
1257        }
1258        public void clear() {
1259            InternalConcurrentHashMap.this.clear();
1260        }
1261        public Object [] toArray() {
1262            Collection c = new ArrayList();
1263            for (Iterator i = iterator(); i.hasNext(); )
1264                c.add(i.next());
1265            return c.toArray();
1266        }
1267        public Object [] toArray(Object [] a) {
1268            Collection c = new ArrayList();
1269            for (Iterator i = iterator(); i.hasNext(); )
1270                c.add(i.next());
1271            return c.toArray(a);
1272        }
1273    }
1274
1275    final class EntrySet extends AbstractSet {
1276        public Iterator iterator() {
1277            return new EntryIterator();
1278        }
1279        public boolean contains(Object o) {
1280            if (!(o instanceof Map.Entry))
1281                return false;
1282            Map.Entry e = (Map.Entry)o;
1283            Object v = InternalConcurrentHashMap.this.get(e.getKey());
1284            return v != null && v.equals(e.getValue());
1285        }
1286        public boolean remove(Object o) {
1287            if (!(o instanceof Map.Entry))
1288                return false;
1289            Map.Entry e = (Map.Entry)o;
1290            return InternalConcurrentHashMap.this.remove(e.getKey(), e.getValue());
1291        }
1292        public int size() {
1293            return InternalConcurrentHashMap.this.size();
1294        }
1295        public void clear() {
1296            InternalConcurrentHashMap.this.clear();
1297        }
1298        public Object [] toArray() {
1299            // Since we don't ordinarily have distinct Entry objects, we
1300 // must pack elements using exportable SimpleEntry
1301 Collection c = new ArrayList(size());
1302            for (Iterator i = iterator(); i.hasNext(); )
1303                c.add(new SimpleEntry((Entry)i.next()));
1304            return c.toArray();
1305        }
1306        public Object [] toArray(Object [] a) {
1307            Collection c = new ArrayList(size());
1308            for (Iterator i = iterator(); i.hasNext(); )
1309                c.add(new SimpleEntry((Entry)i.next()));
1310            return c.toArray(a);
1311        }
1312
1313    }
1314
1315    /**
1316     * This duplicates java.util.AbstractMap.SimpleEntry until this class
1317     * is made accessible.
1318     */
1319    static final class SimpleEntry implements Entry {
1320        Object key;
1321        Object value;
1322
1323        public SimpleEntry(Object key, Object value) {
1324            this.key = key;
1325            this.value = value;
1326        }
1327
1328        public SimpleEntry(Entry e) {
1329            this.key = e.getKey();
1330            this.value = e.getValue();
1331        }
1332
1333        public Object getKey() {
1334            return key;
1335        }
1336
1337        public Object getValue() {
1338            return value;
1339        }
1340
1341        public Object setValue(Object value) {
1342            Object oldValue = this.value;
1343            this.value = value;
1344            return oldValue;
1345        }
1346
1347        public boolean equals(Object o) {
1348            if (!(o instanceof Map.Entry))
1349                return false;
1350            Map.Entry e = (Map.Entry)o;
1351            return eq(key, e.getKey()) && eq(value, e.getValue());
1352        }
1353
1354        public int hashCode() {
1355            return ((key == null) ? 0 : key.hashCode()) ^
1356                   ((value == null) ? 0 : value.hashCode());
1357        }
1358
1359        public String toString() {
1360            return key + "=" + value;
1361        }
1362
1363        static boolean eq(Object o1, Object o2) {
1364            return (o1 == null ? o2 == null : o1.equals(o2));
1365        }
1366    }
1367
1368    /* ---------------- Serialization Support -------------- */
1369
1370    /**
1371     * Save the state of the <tt>InternalConcurrentHashMap</tt>
1372     * instance to a stream (i.e.,
1373     * serialize it).
1374     * @param s the stream
1375     * @serialData
1376     * the key (Object) and value (Object)
1377     * for each key-value mapping, followed by a null pair.
1378     * The key-value mappings are emitted in no particular order.
1379     */
1380    private void writeObject(java.io.ObjectOutputStream s) throws IOException {
1381        s.defaultWriteObject();
1382
1383        for (int k = 0; k < segments.length; ++k) {
1384            Segment seg = (Segment)segments[k];
1385            seg.lock();
1386            try {
1387                HashEntry[] tab = seg.table;
1388                for (int i = 0; i < tab.length; ++i) {
1389                    for (HashEntry e = (HashEntry)tab[i]; e != null; e = e.next) {
1390                        s.writeObject(e.key);
1391                        s.writeObject(e.value);
1392                    }
1393                }
1394            } finally {
1395                seg.unlock();
1396            }
1397        }
1398        s.writeObject(null);
1399        s.writeObject(null);
1400    }
1401
1402    /**
1403     * Reconstitute the <tt>InternalConcurrentHashMap</tt>
1404     * instance from a stream (i.e.,
1405     * deserialize it).
1406     * @param s the stream
1407     */
1408    private void readObject(java.io.ObjectInputStream s)
1409        throws IOException , ClassNotFoundException {
1410        s.defaultReadObject();
1411
1412        // Initialize each segment to be minimally sized, and let grow.
1413 for (int i = 0; i < segments.length; ++i) {
1414            segments[i].setTable(new HashEntry[1]);
1415        }
1416
1417        // Read the keys and values, and put the mappings in the table
1418 for (;;) {
1419            Object key = (Object ) s.readObject();
1420            Object value = (Object ) s.readObject();
1421            if (key == null)
1422                break;
1423            put(key, value);
1424        }
1425    }
1426}
1427
1428

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags