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