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