Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   *  Copyright (c) 2012 Jan Kotek
   *
   *  Licensed under the Apache License, Version 2.0 (the "License");
   *  you may not use this file except in compliance with the License.
   *  You may obtain a copy of the License at
   *
   *    http://www.apache.org/licenses/LICENSE-2.0
   *
  *  Unless required by applicable law or agreed to in writing, software
  *  distributed under the License is distributed on an "AS IS" BASIS,
  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  *  See the License for the specific language governing permissions and
  *  limitations under the License.
  */
 
 /* This code was adopted from Apache Harmony 'ConcurrentHashMap' with following
  * copyright:
  *
  * Written by Doug Lea with assistance from members of JCP JSR-166
  * Expert Group and released to the public domain, as explained at
  * http://creativecommons.org/licenses/publicdomain
  */
 
 package org.mapdb;
Thread safe LongMap. Is refactored version of 'ConcurrentHashMap'

Author(s):
Jan Kotek
Doug Lea
 
 public class LongConcurrentHashMap< V>
         extends LongMap<V> implements Serializable  {
     private static final long serialVersionUID = 7249069246763182397L;
 
     /*
      * The basic strategy is to subdivide the table among Segments,
      * each of which itself is a concurrently readable hash table.
      */
 
     /* ---------------- Constants -------------- */

    
The default initial capacity for this table, used when not otherwise specified in a constructor.
 
     static final int DEFAULT_INITIAL_CAPACITY = 16;

    
Salt added to keys before hashing, so it is harder to trigger hash collision attack.
 
     protected final long hashSalt = new Random().nextLong();


    
The default load factor for this table, used when not otherwise specified in a constructor.
 
     static final float DEFAULT_LOAD_FACTOR = 0.75f;

    
The default concurrency level for this table, used when not otherwise specified in a constructor.
 
     static final int DEFAULT_CONCURRENCY_LEVEL = 16;

    
The maximum capacity, used if a higher value is implicitly specified by either of the constructors with arguments. MUST be a power of two <= 1<<30 to ensure that entries are indexable using ints.
 
     static final int MAXIMUM_CAPACITY = 1 << 30;

    
The maximum number of segments to allow; used to bound constructor arguments.
 
     static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
 
    
Number of unsynchronized retries in size and containsValue methods before resorting to locking. This is used to avoid unbounded retries if tables undergo continuous modification which would make it impossible to obtain an accurate result.
 
     static final int RETRIES_BEFORE_LOCK = 2;
 
     /* ---------------- Fields -------------- */

    
Mask value for indexing into segments. The upper bits of a key's hash code are used to choose the segment.
    final int segmentMask;

    
Shift value for indexing within segments.
    final int segmentShift;

    
The segments, each of which is a specialized hash table
    final Segment<V>[] segments;
    /* ---------------- Small Utilities -------------- */


    
Returns the segment that should be used for key with given hash

Parameters:
hash the hash code for the key
Returns:
the segment
    final Segment<V> segmentFor(int hash) {
        return [(hash >>> ) & ];
    }
    /* ---------------- Inner Classes -------------- */

    
LongConcurrentHashMap list entry. Note that this is never exported out as a user-visible Map.Entry. Because the value field is volatile, not final, it is legal wrt the Java Memory Model for an unsynchronized reader to see null instead of initial value when read via a data race. Although a reordering leading to this is not likely to ever actually occur, the Segment.readValueUnderLock method is used as a backup in case a null (pre-initialized) value is ever seen in an unsynchronized access method.
    static final class HashEntry<V> {
        final long key;
        final int hash;
        volatile V value;
        final HashEntry<V> next;
        HashEntry(long keyint hashHashEntry<V> next, V value) {
            this. = key;
            this. = hash;
            this. = next;
            this. = value;
        }
        @SuppressWarnings("unchecked")
        static <V> HashEntry<V>[] newArray(int i) {
            return new HashEntry[i];
        }
    }

    
Segments are specialized versions of hash tables. This subclasses from ReentrantLock opportunistically, just to simplify some locking and avoid separate construction.
    static final class Segment<V> extends ReentrantLock implements Serializable {
        /*
         * Segments maintain a table of entry lists that are ALWAYS
         * kept in a consistent state, so can be read without locking.
         * Next fields of nodes are immutable (final).  All list
         * additions are performed at the front of each bin. This
         * makes it easy to check changes, and also fast to traverse.
         * When nodes would otherwise be changed, new nodes are
         * created to replace them. This works well for hash tables
         * since the bin lists tend to be short. (The average length
         * is less than two for the default load factor threshold.)
         *
         * Read operations can thus proceed without locking, but rely
         * on selected uses of volatiles to ensure that completed
         * write operations performed by other threads are
         * noticed. For most purposes, the "count" field, tracking the
         * number of elements, serves as that volatile variable
         * ensuring visibility.  This is convenient because this field
         * needs to be read in many read operations anyway:
         *
         *   - All (unsynchronized) read operations must first read the
         *     "count" field, and should not look at table entries if
         *     it is 0.
         *
         *   - All (synchronized) write operations should write to
         *     the "count" field after structurally changing any bin.
         *     The operations must not take any action that could even
         *     momentarily cause a concurrent read operation to see
         *     inconsistent data. This is made easier by the nature of
         *     the read operations in Map. For example, no operation
         *     can reveal that the table has grown but the threshold
         *     has not yet been updated, so there are no atomicity
         *     requirements for this with respect to reads.
         *
         * As a guide, all critical volatile reads and writes to the
         * count field are marked in code comments.
         */
        private static final long serialVersionUID = 2249069246763182397L;

        
The number of elements in this segment's region.
        transient volatile int count;

        
Number of updates that alter the size of the table. This is used during bulk-read methods to make sure they see a consistent snapshot: If modCounts change during a traversal of segments computing size or checking containsValue, then we might have an inconsistent view of state so (usually) must retry.
        transient int modCount;

        
The table is rehashed when its size exceeds this threshold. (The value of this field is always (int)(capacity * loadFactor).)
        transient int threshold;

        
The per-segment table.
        transient volatile HashEntry<V>[] table;

        
The load factor for the hash table. Even though this value is same for all segments, it is replicated to avoid needing links to outer object.

Serial:
        final float loadFactor;
        Segment(int initialCapacityfloat lf) {
            super(.);
             = lf;
            setTable(HashEntry.<V>newArray(initialCapacity));
        }
        @SuppressWarnings("unchecked")
        static <V> Segment<V>[] newArray(int i) {
            return new Segment[i];
        }

        
Sets table to new HashEntry array. Call only while holding lock or in constructor.
        void setTable(HashEntry<V>[] newTable) {
             = (int)(newTable.length * );
             = newTable;
        }

        
Returns properly casted first entry of bin for given hash.
        HashEntry<V> getFirst(int hash) {
            HashEntry<V>[] tab = ;
            return tab[hash & (tab.length - 1)];
        }

        
Reads value field of an entry under lock. Called if value field ever appears to be null. This is possible only if a compiler happens to reorder a HashEntry initialization with its table assignment, which is legal under memory model but is not known to ever occur.
        V readValueUnderLock(HashEntry<V> e) {
            lock();
            try {
                return e.value;
            } finally {
                unlock();
            }
        }
        /* Specialized implementations of map methods */
        V get(final long keyint hash) {
            if ( != 0) { // read-volatile
                HashEntry<V> e = getFirst(hash);
                while (e != null) {
                    if (e.hash == hash && key == e.key) {
                        V v = e.value;
                        if (v != null)
                            return v;
                        return readValueUnderLock(e); // recheck
                    }
                    e = e.next;
                }
            }
            return null;
        }
        boolean containsKey(final long keyint hash) {
            if ( != 0) { // read-volatile
                HashEntry<V> e = getFirst(hash);
                while (e != null) {
                    if (e.hash == hash && key == e.key)
                        return true;
                    e = e.next;
                }
            }
            return false;
        }
        boolean containsValue(Object value) {
            if ( != 0) { // read-volatile
                HashEntry<V>[] tab = ;
                //int len = tab.length;
                for (HashEntry<V> aTab : tab) {
                    for (HashEntry<V> e = aTabe != nulle = e.next) {
                        V v = e.value;
                        if (v == null// recheck
                            v = readValueUnderLock(e);
                        if (value.equals(v))
                            return true;
                    }
                }
            }
            return false;
        }
        boolean replace(long keyint hash, V oldValue, V newValue) {
            lock();
            try {
                HashEntry<V> e = getFirst(hash);
                while (e != null && (e.hash != hash || key!=e.key))
                    e = e.next;
                boolean replaced = false;
                if (e != null && oldValue.equals(e.value)) {
                    replaced = true;
                    e.value = newValue;
                }
                return replaced;
            } finally {
                unlock();
            }
        }
        V replace(long keyint hash, V newValue) {
            lock();
            try {
                HashEntry<V> e = getFirst(hash);
                while (e != null && (e.hash != hash || key != e.key))
                    e = e.next;
                V oldValue = null;
                if (e != null) {
                    oldValue = e.value;
                    e.value = newValue;
                }
                return oldValue;
            } finally {
                unlock();
            }
        }
        V put(long keyint hash, V valueboolean onlyIfAbsent) {
            lock();
            try {
                int c = ;
                if (c++ > // ensure capacity
                    rehash();
                HashEntry<V>[] tab = ;
                int index = hash & (tab.length - 1);
                HashEntry<V> first = tab[index];
                HashEntry<V> e = first;
                while (e != null && (e.hash != hash || key!=e.key))
                    e = e.next;
                V oldValue;
                if (e != null) {
                    oldValue = e.value;
                    if (!onlyIfAbsent)
                        e.value = value;
                }
                else {
                    oldValue = null;
                    ++;
                    tab[index] = new HashEntry<V>(keyhashfirstvalue);
                     = c// write-volatile
                }
                return oldValue;
            } finally {
                unlock();
            }
        }
        void rehash() {
            HashEntry<V>[] oldTable = ;
            int oldCapacity = oldTable.length;
            if (oldCapacity >= )
                return;
            /*
             * Reclassify nodes in each list to new Map.  Because we are
             * using power-of-two expansion, the elements from each bin
             * must either stay at same index, or move with a power of two
             * offset. We eliminate unnecessary node creation by catching
             * cases where old nodes can be reused because their next
             * fields won't change. Statistically, at the default
             * threshold, only about one-sixth of them need cloning when
             * a table doubles. The nodes they replace will be garbage
             * collectable as soon as they are no longer referenced by any
             * reader thread that may be in the midst of traversing table
             * right now.
             */
            HashEntry<V>[] newTable = HashEntry.newArray(oldCapacity<<1);
             = (int)(newTable.length * );
            int sizeMask = newTable.length - 1;
            for (HashEntry<V> e : oldTable) {
                // We need to guarantee that any existing reads of old Map can
                //  proceed. So we cannot yet null out each bin.
                if (e != null) {
                    HashEntry<V> next = e.next;
                    int idx = e.hash & sizeMask;
                    //  Single node on list
                    if (next == null)
                        newTable[idx] = e;
                    else {
                        // Reuse trailing consecutive sequence at same slot
                        HashEntry<V> lastRun = e;
                        int lastIdx = idx;
                        for (HashEntry<V> last = next;
                             last != null;
                             last = last.next) {
                            int k = last.hash & sizeMask;
                            if (k != lastIdx) {
                                lastIdx = k;
                                lastRun = last;
                            }
                        }
                        newTable[lastIdx] = lastRun;
                        // Clone all remaining nodes
                        for (HashEntry<V> p = ep != lastRunp = p.next) {
                            int k = p.hash & sizeMask;
                            HashEntry<V> n = newTable[k];
                            newTable[k] = new HashEntry<V>(p.keyp.hash,
                                    np.value);
                        }
                    }
                }
            }
             = newTable;
        }

        
Remove; match on key only if value null, else match both.
        V remove(final long keyint hashObject value) {
            lock();
            try {
                int c =  - 1;
                HashEntry<V>[] tab = ;
                int index = hash & (tab.length - 1);
                HashEntry<V> first = tab[index];
                HashEntry<V> e = first;
                while (e != null && (e.hash != hash || key!=e.key))
                    e = e.next;
                V oldValue = null;
                if (e != null) {
                    V v = e.value;
                    if (value == null || value.equals(v)) {
                        oldValue = v;
                        // All entries following removed node can stay
                        // in list, but all preceding ones need to be
                        // cloned.
                        ++;
                        HashEntry<V> newFirst = e.next;
                        for (HashEntry<V> p = firstp != ep = p.next)
                            newFirst = new HashEntry<V>(p.keyp.hash,
                                                          newFirstp.value);
                        tab[index] = newFirst;
                         = c// write-volatile
                    }
                }
                return oldValue;
            } finally {
                unlock();
            }
        }
        void clear() {
            if ( != 0) {
                lock();
                try {
                    HashEntry<V>[] tab = ;
                    for (int i = 0; i < tab.length ; i++)
                        tab[i] = null;
                    ++;
                     = 0; // write-volatile
                } finally {
                    unlock();
                }
            }
        }
    }
    /* ---------------- Public operations -------------- */

    
Creates a new, empty map with the specified initial capacity, load factor and concurrency level.

Parameters:
initialCapacity the initial capacity. The implementation performs internal sizing to accommodate this many elements.
loadFactor the load factor threshold, used to control resizing. Resizing may be performed when the average number of elements per bin exceeds this threshold.
concurrencyLevel the estimated number of concurrently updating threads. The implementation performs internal sizing to try to accommodate this many threads.
Throws:
java.lang.IllegalArgumentException if the initial capacity is negative or the load factor or concurrencyLevel are nonpositive.
    public LongConcurrentHashMap(int initialCapacity,
                                 float loadFactorint concurrencyLevel) {
        if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        if (concurrencyLevel > )
            concurrencyLevel = ;
        // Find power-of-two sizes best matching arguments
        int sshift = 0;
        int ssize = 1;
        while (ssize < concurrencyLevel) {
            ++sshift;
            ssize <<= 1;
        }
         = 32 - sshift;
         = ssize - 1;
        this. = Segment.newArray(ssize);
        if (initialCapacity > )
            initialCapacity = ;
        int c = initialCapacity / ssize;
        if (c * ssize < initialCapacity)
            ++c;
        int cap = 1;
        while (cap < c)
            cap <<= 1;
        for (int i = 0; i < this..length; ++i)
            this.[i] = new Segment<V>(caploadFactor);
    }

    
Creates a new, empty map with the specified initial capacity, and with default load factor (0.75) and concurrencyLevel (16).

Parameters:
initialCapacity the initial capacity. The implementation performs internal sizing to accommodate this many elements.
Throws:
java.lang.IllegalArgumentException if the initial capacity of elements is negative.
    public LongConcurrentHashMap(int initialCapacity) {
        this(initialCapacity);
    }

    
Creates a new, empty map with a default initial capacity (16), load factor (0.75) and concurrencyLevel (16).
    public LongConcurrentHashMap() {
    }

    
Returns true if this map contains no key-value mappings.

Returns:
true if this map contains no key-value mappings
    @Override
	public boolean isEmpty() {
        final Segment<V>[] segments = this.;
        /*
         * We keep track of per-segment modCounts to avoid ABA
         * problems in which an element in one segment was added and
         * in another removed during traversal, in which case the
         * table was never actually empty at any point. Note the
         * similar use of modCounts in the size() and containsValue()
         * methods, which are the only other methods also susceptible
         * to ABA problems.
         */
        int[] mc = new int[segments.length];
        int mcsum = 0;
        for (int i = 0; i < segments.length; ++i) {
            if (segments[i]. != 0)
                return false;
            else
                mcsum += mc[i] = segments[i].;
        }
        // If mcsum happens to be zero, then we know we got a snapshot
        // before any modifications at all were made.  This is
        // probably common enough to bother tracking.
        if (mcsum != 0) {
            for (int i = 0; i < segments.length; ++i) {
                if (segments[i]. != 0 ||
                    mc[i] != segments[i].)
                    return false;
            }
        }
        return true;
    }

    
Returns the number of key-value mappings in this map. If the map contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

Returns:
the number of key-value mappings in this map
    @Override
	public int size() {
        final Segment<V>[] segments = this.;
        long sum = 0;
        long check = 0;
        int[] mc = new int[segments.length];
        // Try a few times to get accurate count. On failure due to
        // continuous async changes in table, resort to locking.
        for (int k = 0; k < ; ++k) {
            check = 0;
            sum = 0;
            int mcsum = 0;
            for (int i = 0; i < segments.length; ++i) {
                sum += segments[i].;
                mcsum += mc[i] = segments[i].;
            }
            if (mcsum != 0) {
                for (int i = 0; i < segments.length; ++i) {
                    check += segments[i].;
                    if (mc[i] != segments[i].) {
                        check = -1; // force retry
                        break;
                    }
                }
            }
            if (check == sum)
                break;
        }
        if (check != sum) { // Resort to locking all segments
            sum = 0;
            for (Segment<V> segment : segmentssegment.lock();
            for (Segment<V> segment : segmentssum += segment.count;
            for (Segment<V> segment : segmentssegment.unlock();
        }
        if (sum > .)
            return .;
        else
            return (int)sum;
    }
    @Override
    public Iterator<V> valuesIterator() {
        return new ValueIterator();
    }
    @Override
    public LongMapIterator<V> longMapIterator() {
        return new MapIterator();
    }

    
Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.

More formally, if this map contains a mapping from a key k to a value keys such that key.equals(k), then this method returns keys; otherwise it returns null. (There can be at most one such mapping.)

Throws:
java.lang.NullPointerException if the specified key is null
    @Override
	public V get(long key) {
        final int hash = LongHashMap.longHash(key^);
        return segmentFor(hash).get(keyhash);
    }

    
Tests if the specified object is a key in this table.

Parameters:
key possible key
Returns:
true if and only if the specified object is a key in this table, as determined by the equals method; false otherwise.
Throws:
java.lang.NullPointerException if the specified key is null
    public boolean containsKey(long key) {
        final int hash = LongHashMap.longHash(key^);
        return segmentFor(hash).containsKey(keyhash);
    }

    
Returns true if this map maps one or more keys to the specified value. Note: This method requires a full internal traversal of the hash table, and so is much slower than method containsKey.

Parameters:
value value whose presence in this map is to be tested
Returns:
true if this map maps one or more keys to the specified value
Throws:
java.lang.NullPointerException if the specified value is null
    public boolean containsValue(Object value) {
        if (value == null)
            throw new NullPointerException();
        // See explanation of modCount use above
        final Segment<V>[] segments = this.;
        int[] mc = new int[segments.length];
        // Try a few times without locking
        for (int k = 0; k < ; ++k) {
            //int sum = 0;
            int mcsum = 0;
            for (int i = 0; i < segments.length; ++i) {
                //int c = segments[i].count;
                mcsum += mc[i] = segments[i].;
                if (segments[i].containsValue(value))
                    return true;
            }
            boolean cleanSweep = true;
            if (mcsum != 0) {
                for (int i = 0; i < segments.length; ++i) {
                    //int c = segments[i].count;
                    if (mc[i] != segments[i].) {
                        cleanSweep = false;
                        break;
                    }
                }
            }
            if (cleanSweep)
                return false;
        }
        // Resort to locking all segments
        for (Segment<V> segment : segmentssegment.lock();
        boolean found = false;
        try {
            for (Segment<V> segment : segments) {
                if (segment.containsValue(value)) {
                    found = true;
                    break;
                }
            }
        } finally {
            for (Segment<V> segment : segmentssegment.unlock();
        }
        return found;
    }


    
Maps the specified key to the specified value in this table. Neither the key nor the value can be null.

The value can be retrieved by calling the get method with a key that is equal to the original key.

Parameters:
key key with which the specified value is to be associated
value value to be associated with the specified key
Returns:
the previous value associated with key, or null if there was no mapping for key
Throws:
java.lang.NullPointerException if the specified key or value is null
    @Override
	public V put(long key, V value) {
        if (value == null)
            throw new NullPointerException();
        final int hash = LongHashMap.longHash(key^);
        return segmentFor(hash).put(keyhashvaluefalse);
    }

    

Returns:
the previous value associated with the specified key, or null if there was no mapping for the key
Throws:
java.lang.NullPointerException if the specified key or value is null
    public V putIfAbsent(long key, V value) {
        if (value == null)
            throw new NullPointerException();
        final int hash = LongHashMap.longHash(key^);
        return segmentFor(hash).put(keyhashvaluetrue);
    }


    
Removes the key (and its corresponding value) from this map. This method does nothing if the key is not in the map.

Parameters:
key the key that needs to be removed
Returns:
the previous value associated with key, or null if there was no mapping for key
Throws:
java.lang.NullPointerException if the specified key is null
    @Override
	public V remove(long key) {
        final int hash = LongHashMap.longHash(key^);
        return segmentFor(hash).remove(keyhashnull);
    }

    

Throws:
java.lang.NullPointerException if the specified key is null
    public boolean remove(long keyObject value) {
        final int hash = LongHashMap.longHash(key^);
        return value != null && segmentFor(hash).remove(keyhashvalue) != null;
    }

    

Throws:
java.lang.NullPointerException if any of the arguments are null
    public boolean replace(long key, V oldValue, V newValue) {
        if (oldValue == null || newValue == null)
            throw new NullPointerException();
        final int hash = LongHashMap.longHash(key^);
        return segmentFor(hash).replace(keyhasholdValuenewValue);
    }

    

Returns:
the previous value associated with the specified key, or null if there was no mapping for the key
Throws:
java.lang.NullPointerException if the specified key or value is null
    public V replace(long key, V value) {
        if (value == null)
            throw new NullPointerException();
        final int hash = LongHashMap.longHash(key^);
        return segmentFor(hash).replace(keyhashvalue);
    }

    
Removes all of the mappings from this map.
    @Override
	public void clear() {
        for (Segment<V> segment : segment.clear();
    }
    /* ---------------- Iterator Support -------------- */
    abstract class HashIterator {
        int nextSegmentIndex;
        int nextTableIndex;
        HashEntry<V>[] currentTable;
        HashEntry< V> nextEntry;
        HashEntry< V> lastReturned;
        HashIterator() {
             = . - 1;
             = -1;
            advance();
        }
        final void advance() {
            if ( != null && ( = .) != null)
                return;
            while ( >= 0) {
                if ( ( = [--]) != null)
                    return;
            }
            while ( >= 0) {
                Segment<V> seg = [--];
                if (seg.count != 0) {
                     = seg.table;
                    for (int j = . - 1; j >= 0; --j) {
                        if ( ( = [j]) != null) {
                             = j - 1;
                            return;
                        }
                    }
                }
            }
        }
        public boolean hasNext() { return  != null; }
        HashEntry<V> nextEntry() {
            if ( == null)
                throw new NoSuchElementException();
             = ;
            advance();
            return ;
        }
        public void remove() {
            if ( == null)
                throw new IllegalStateException();
            LongConcurrentHashMap.this.remove(.);
             = null;
        }
    }
    final class KeyIterator
        extends HashIterator
        implements Iterator<Long>
    {
        @Override
		public Long next()        { return super.nextEntry().; }
    }
    final class ValueIterator
        extends HashIterator
        implements Iterator<V>
    {
        @Override
		public V next()        { return super.nextEntry().; }
    }
    final class MapIterator extends HashIterator implements LongMapIterator<V>{
        private long key;
        private V value;
        @Override
        public boolean moveToNext() {
            if(!hasNext()) return false;
            HashEntry<V> next = nextEntry();
             = next.key;
             = next.value;
            return true;
        }
        @Override
        public long key() {
            return ;
        }
        @Override
        public V value() {
            return ;
        }
    }
New to GrepCode? Check out our FAQ X