/*

  * Copyright (c) 1997, 2007, Oracle and/or its affiliates. All rights reserved.

  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

  *

  * This code is free software; you can redistribute it and/or modify it

  * under the terms of the GNU General Public License version 2 only, as

  * published by the Free Software Foundation.  Oracle designates this

  * particular file as subject to the "Classpath" exception as provided

  * by Oracle in the LICENSE file that accompanied this code.

  *

  * This code is distributed in the hope that it will be useful, but WITHOUT

  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

  * version 2 for more details (a copy is included in the LICENSE file that

  * accompanied this code).

  *

  * You should have received a copy of the GNU General Public License version

  * 2 along with this work; if not, write to the Free Software Foundation,

  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

  *

  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

  * or visit www.oracle.com if you need additional information or have any

  * questions.

  */

 package java.lang;

 import java.lang.ref.*;

 import java.util.concurrent.atomic.AtomicInteger;

 /**

  * This class provides thread-local variables.  These variables differ from

  * their normal counterparts in that each thread that accesses one (via its

  * <tt>get</tt> or <tt>set</tt> method) has its own, independently initialized

  * copy of the variable.  <tt>ThreadLocal</tt> instances are typically private

  * static fields in classes that wish to associate state with a thread (e.g.,

  * a user ID or Transaction ID).

  *

  * <p>For example, the class below generates unique identifiers local to each

  * thread.

  * A thread's id is assigned the first time it invokes <tt>ThreadId.get()</tt>

  * and remains unchanged on subsequent calls.

  * <pre>

  * import java.util.concurrent.atomic.AtomicInteger;

  *

  * public class ThreadId {

  *     // Atomic integer containing the next thread ID to be assigned

  *     private static final AtomicInteger nextId = new AtomicInteger(0);

  *

  *     // Thread local variable containing each thread's ID

  *     private static final ThreadLocal<Integer> threadId =

  *         new ThreadLocal<Integer>() {

  *             @Override protected Integer initialValue() {

  *                 return nextId.getAndIncrement();

  *         }

  *     };

  *

  *     // Returns the current thread's unique ID, assigning it if necessary

  *     public static int get() {

  *         return threadId.get();

  *     }

  * }

  * </pre>

  * <p>Each thread holds an implicit reference to its copy of a thread-local

  * variable as long as the thread is alive and the <tt>ThreadLocal</tt>

  * instance is accessible; after a thread goes away, all of its copies of

  * thread-local instances are subject to garbage collection (unless other

  * references to these copies exist).

  *

  * @author  Josh Bloch and Doug Lea

  * @since   1.2

  */

 public class ThreadLocal<T> {

     /**

      * ThreadLocals rely on per-thread linear-probe hash maps attached

      * to each thread (Thread.threadLocals and

      * inheritableThreadLocals).  The ThreadLocal objects act as keys,

      * searched via threadLocalHashCode.  This is a custom hash code

      * (useful only within ThreadLocalMaps) that eliminates collisions

      * in the common case where consecutively constructed ThreadLocals

      * are used by the same threads, while remaining well-behaved in

      * less common cases.

      */

     private final int threadLocalHashCode = nextHashCode();

     /**

      * The next hash code to be given out. Updated atomically. Starts at

      * zero.

      */

     private static AtomicInteger nextHashCode =

         new AtomicInteger();

     /**

      * The difference between successively generated hash codes - turns

      * implicit sequential thread-local IDs into near-optimally spread

      * multiplicative hash values for power-of-two-sized tables.

      */

     private static final int HASH_INCREMENT = 0x61c88647;

     /**

      * Returns the next hash code.

      */

     private static int nextHashCode() {

         return nextHashCode.getAndAdd(HASH_INCREMENT);

     }

     /**

      * Returns the current thread's "initial value" for this

      * thread-local variable.  This method will be invoked the first

      * time a thread accesses the variable with the {@link #get}

      * method, unless the thread previously invoked the {@link #set}

      * method, in which case the <tt>initialValue</tt> method will not

      * be invoked for the thread.  Normally, this method is invoked at

      * most once per thread, but it may be invoked again in case of

      * subsequent invocations of {@link #remove} followed by {@link #get}.

      *

      * <p>This implementation simply returns <tt>null</tt>; if the

      * programmer desires thread-local variables to have an initial

      * value other than <tt>null</tt>, <tt>ThreadLocal</tt> must be

      * subclassed, and this method overridden.  Typically, an

      * anonymous inner class will be used.

      *

      * @return the initial value for this thread-local

      */

     protected T initialValue() {

         return null;

     }

     /**

      * Creates a thread local variable.

      */

     public ThreadLocal() {

     }

     /**

      * Returns the value in the current thread's copy of this

      * thread-local variable.  If the variable has no value for the

      * current thread, it is first initialized to the value returned

      * by an invocation of the {@link #initialValue} method.

      *

      * @return the current thread's value of this thread-local

      */

     public T get() {

         Thread t = Thread.currentThread();

         ThreadLocalMap map = getMap(t);

         if (map != null) {

             ThreadLocalMap.Entry e = map.getEntry(this);

             if (e != null)

                 return (T)e.value;

         }

         return setInitialValue();

     }

     /**

      * Variant of set() to establish initialValue. Used instead

      * of set() in case user has overridden the set() method.

      *

      * @return the initial value

      */

     private T setInitialValue() {

         T value = initialValue();

         Thread t = Thread.currentThread();

         ThreadLocalMap map = getMap(t);

         if (map != null)

             map.set(this, value);

         else

             createMap(t, value);

         return value;

     }

     /**

      * Sets the current thread's copy of this thread-local variable

      * to the specified value.  Most subclasses will have no need to

      * override this method, relying solely on the {@link #initialValue}

      * method to set the values of thread-locals.

      *

      * @param value the value to be stored in the current thread's copy of

      *        this thread-local.

      */

     public void set(T value) {

         Thread t = Thread.currentThread();

         ThreadLocalMap map = getMap(t);

         if (map != null)

             map.set(this, value);

         else

             createMap(t, value);

     }

     /**

      * Removes the current thread's value for this thread-local

      * variable.  If this thread-local variable is subsequently

      * {@linkplain #get read} by the current thread, its value will be

      * reinitialized by invoking its {@link #initialValue} method,

      * unless its value is {@linkplain #set set} by the current thread

      * in the interim.  This may result in multiple invocations of the

      * <tt>initialValue</tt> method in the current thread.

      *

      * @since 1.5

      */

      public void remove() {

          ThreadLocalMap m = getMap(Thread.currentThread());

          if (m != null)

              m.remove(this);

      }

     /**

      * Get the map associated with a ThreadLocal. Overridden in

      * InheritableThreadLocal.

      *

      * @param  t the current thread

      * @return the map

      */

     ThreadLocalMap getMap(Thread t) {

         return t.threadLocals;

     }

     /**

      * Create the map associated with a ThreadLocal. Overridden in

      * InheritableThreadLocal.

      *

      * @param t the current thread

      * @param firstValue value for the initial entry of the map

      * @param map the map to store.

      */

     void createMap(Thread t, T firstValue) {

         t.threadLocals = new ThreadLocalMap(this, firstValue);

     }

     /**

      * Factory method to create map of inherited thread locals.

      * Designed to be called only from Thread constructor.

      *

      * @param  parentMap the map associated with parent thread

      * @return a map containing the parent's inheritable bindings

      */

     static ThreadLocalMap createInheritedMap(ThreadLocalMap parentMap) {

         return new ThreadLocalMap(parentMap);

     }

     /**

      * Method childValue is visibly defined in subclass

      * InheritableThreadLocal, but is internally defined here for the

      * sake of providing createInheritedMap factory method without

      * needing to subclass the map class in InheritableThreadLocal.

      * This technique is preferable to the alternative of embedding

      * instanceof tests in methods.

      */

     T childValue(T parentValue) {

         throw new UnsupportedOperationException();

     }

     /**

      * ThreadLocalMap is a customized hash map suitable only for

      * maintaining thread local values. No operations are exported

      * outside of the ThreadLocal class. The class is package private to

      * allow declaration of fields in class Thread.  To help deal with

      * very large and long-lived usages, the hash table entries use

      * WeakReferences for keys. However, since reference queues are not

      * used, stale entries are guaranteed to be removed only when

      * the table starts running out of space.

      */

     static class ThreadLocalMap {

         /**

          * The entries in this hash map extend WeakReference, using

          * its main ref field as the key (which is always a

          * ThreadLocal object).  Note that null keys (i.e. entry.get()

          * == null) mean that the key is no longer referenced, so the

          * entry can be expunged from table.  Such entries are referred to

          * as "stale entries" in the code that follows.

          */

         static class Entry extends WeakReference<ThreadLocal> {

             /** The value associated with this ThreadLocal. */

             Object value;

             Entry(ThreadLocal k, Object v) {

                 super(k);

                 value = v;

             }

         }

         /**

          * The initial capacity -- MUST be a power of two.

          */

         private static final int INITIAL_CAPACITY = 16;

         /**

          * The table, resized as necessary.

          * table.length MUST always be a power of two.

          */

         private Entry[] table;

         /**

          * The number of entries in the table.

          */

         private int size = 0;

         /**

          * The next size value at which to resize.

          */

         private int threshold; // Default to 0

         /**

          * Set the resize threshold to maintain at worst a 2/3 load factor.

          */

         private void setThreshold(int len) {

             threshold = len * 2 / 3;

         }

         /**

          * Increment i modulo len.

          */

         private static int nextIndex(int i, int len) {

             return ((i + 1 < len) ? i + 1 : 0);

         }

         /**

          * Decrement i modulo len.

          */

         private static int prevIndex(int i, int len) {

             return ((i - 1 >= 0) ? i - 1 : len - 1);

         }

         /**

          * Construct a new map initially containing (firstKey, firstValue).

          * ThreadLocalMaps are constructed lazily, so we only create

          * one when we have at least one entry to put in it.

          */

         ThreadLocalMap(ThreadLocal firstKey, Object firstValue) {

             table = new Entry[INITIAL_CAPACITY];

             int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);

             table[i] = new Entry(firstKey, firstValue);

             size = 1;

             setThreshold(INITIAL_CAPACITY);

         }

         /**

          * Construct a new map including all Inheritable ThreadLocals

          * from given parent map. Called only by createInheritedMap.

          *

          * @param parentMap the map associated with parent thread.

          */

         private ThreadLocalMap(ThreadLocalMap parentMap) {

             Entry[] parentTable = parentMap.table;

             int len = parentTable.length;

             setThreshold(len);

             table = new Entry[len];

             for (int j = 0; j < len; j++) {

                 Entry e = parentTable[j];

                 if (e != null) {

                     ThreadLocal key = e.get();

                     if (key != null) {

                         Object value = key.childValue(e.value);

                         Entry c = new Entry(key, value);

                         int h = key.threadLocalHashCode & (len - 1);

                         while (table[h] != null)

                             h = nextIndex(h, len);

                         table[h] = c;

                         size++;

                     }

                 }

             }

         }

         /**

          * Get the entry associated with key.  This method

          * itself handles only the fast path: a direct hit of existing

          * key. It otherwise relays to getEntryAfterMiss.  This is

          * designed to maximize performance for direct hits, in part

          * by making this method readily inlinable.

          *

          * @param  key the thread local object

          * @return the entry associated with key, or null if no such

          */

         private Entry getEntry(ThreadLocal key) {

             int i = key.threadLocalHashCode & (table.length - 1);

             Entry e = table[i];

             if (e != null && e.get() == key)

                 return e;

             else

                 return getEntryAfterMiss(key, i, e);

         }

         /**

          * Version of getEntry method for use when key is not found in

          * its direct hash slot.

          *

          * @param  key the thread local object

          * @param  i the table index for key's hash code

          * @param  e the entry at table[i]

          * @return the entry associated with key, or null if no such

          */

         private Entry getEntryAfterMiss(ThreadLocal key, int i, Entry e) {

             Entry[] tab = table;

             int len = tab.length;

             while (e != null) {

                 ThreadLocal k = e.get();

                 if (k == key)

                     return e;

                 if (k == null)

                     expungeStaleEntry(i);

                 else

                     i = nextIndex(i, len);

                 e = tab[i];

             }

             return null;

         }

         /**

          * Set the value associated with key.

          *

          * @param key the thread local object

          * @param value the value to be set

          */

         private void set(ThreadLocal key, Object value) {

             // We don't use a fast path as with get() because it is at

             // least as common to use set() to create new entries as

             // it is to replace existing ones, in which case, a fast

             // path would fail more often than not.

             Entry[] tab = table;

             int len = tab.length;

             int i = key.threadLocalHashCode & (len-1);

             for (Entry e = tab[i];

                  e != null;

                  e = tab[i = nextIndex(i, len)]) {

                 ThreadLocal k = e.get();

                 if (k == key) {

                     e.value = value;

                     return;

                 }

                 if (k == null) {

                     replaceStaleEntry(key, value, i);

                     return;

                 }

             }

             tab[i] = new Entry(key, value);

             int sz = ++size;

             if (!cleanSomeSlots(i, sz) && sz >= threshold)

                 rehash();

         }

         /**

          * Remove the entry for key.

          */

         private void remove(ThreadLocal key) {

             Entry[] tab = table;

             int len = tab.length;

             int i = key.threadLocalHashCode & (len-1);

             for (Entry e = tab[i];

                  e != null;

                  e = tab[i = nextIndex(i, len)]) {

                 if (e.get() == key) {

                     e.clear();

                     expungeStaleEntry(i);

                     return;

                 }

             }

         }

         /**

          * Replace a stale entry encountered during a set operation

          * with an entry for the specified key.  The value passed in

          * the value parameter is stored in the entry, whether or not

          * an entry already exists for the specified key.

          *

          * As a side effect, this method expunges all stale entries in the

          * "run" containing the stale entry.  (A run is a sequence of entries

          * between two null slots.)

          *

          * @param  key the key

          * @param  value the value to be associated with key

          * @param  staleSlot index of the first stale entry encountered while

          *         searching for key.

          */

         private void replaceStaleEntry(ThreadLocal key, Object value,

                                        int staleSlot) {

             Entry[] tab = table;

             int len = tab.length;

             Entry e;

             // Back up to check for prior stale entry in current run.

             // We clean out whole runs at a time to avoid continual

             // incremental rehashing due to garbage collector freeing

             // up refs in bunches (i.e., whenever the collector runs).

             int slotToExpunge = staleSlot;

             for (int i = prevIndex(staleSlot, len);

                  (e = tab[i]) != null;

                  i = prevIndex(i, len))

                 if (e.get() == null)

                     slotToExpunge = i;

             // Find either the key or trailing null slot of run, whichever

             // occurs first

             for (int i = nextIndex(staleSlot, len);

                  (e = tab[i]) != null;

                  i = nextIndex(i, len)) {

                 ThreadLocal k = e.get();

                 // If we find key, then we need to swap it

                 // with the stale entry to maintain hash table order.

                 // The newly stale slot, or any other stale slot

                 // encountered above it, can then be sent to expungeStaleEntry

                 // to remove or rehash all of the other entries in run.

                 if (k == key) {

                     e.value = value;

                     tab[i] = tab[staleSlot];

                     tab[staleSlot] = e;

                     // Start expunge at preceding stale entry if it exists

                     if (slotToExpunge == staleSlot)

                         slotToExpunge = i;

                     cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);

                     return;

                 }

                 // If we didn't find stale entry on backward scan, the

                 // first stale entry seen while scanning for key is the

                 // first still present in the run.

                 if (k == null && slotToExpunge == staleSlot)

                     slotToExpunge = i;

             }

             // If key not found, put new entry in stale slot

             tab[staleSlot].value = null;

             tab[staleSlot] = new Entry(key, value);

             // If there are any other stale entries in run, expunge them

             if (slotToExpunge != staleSlot)

                 cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);

         }

         /**

          * Expunge a stale entry by rehashing any possibly colliding entries

          * lying between staleSlot and the next null slot.  This also expunges

          * any other stale entries encountered before the trailing null.  See

          * Knuth, Section 6.4

          *

          * @param staleSlot index of slot known to have null key

          * @return the index of the next null slot after staleSlot

          * (all between staleSlot and this slot will have been checked

          * for expunging).

          */

         private int expungeStaleEntry(int staleSlot) {

             Entry[] tab = table;

             int len = tab.length;

             // expunge entry at staleSlot

             tab[staleSlot].value = null;

             tab[staleSlot] = null;

             size--;

             // Rehash until we encounter null

             Entry e;

             int i;

             for (i = nextIndex(staleSlot, len);

                  (e = tab[i]) != null;

                  i = nextIndex(i, len)) {

                 ThreadLocal k = e.get();

                 if (k == null) {

                     e.value = null;

                     tab[i] = null;

                     size--;

                 } else {

                     int h = k.threadLocalHashCode & (len - 1);

                     if (h != i) {

                         tab[i] = null;

                         // Unlike Knuth 6.4 Algorithm R, we must scan until

                         // null because multiple entries could have been stale.

                         while (tab[h] != null)

                             h = nextIndex(h, len);

                         tab[h] = e;

                     }

                 }

             }

             return i;

         }

         /**

          * Heuristically scan some cells looking for stale entries.

          * This is invoked when either a new element is added, or

          * another stale one has been expunged. It performs a

          * logarithmic number of scans, as a balance between no

          * scanning (fast but retains garbage) and a number of scans

          * proportional to number of elements, that would find all

          * garbage but would cause some insertions to take O(n) time.

          *

          * @param i a position known NOT to hold a stale entry. The

          * scan starts at the element after i.

          *

          * @param n scan control: <tt>log2(n)</tt> cells are scanned,

          * unless a stale entry is found, in which case

          * <tt>log2(table.length)-1</tt> additional cells are scanned.

          * When called from insertions, this parameter is the number

          * of elements, but when from replaceStaleEntry, it is the

          * table length. (Note: all this could be changed to be either

          * more or less aggressive by weighting n instead of just

          * using straight log n. But this version is simple, fast, and

          * seems to work well.)

          *

          * @return true if any stale entries have been removed.

          */

         private boolean cleanSomeSlots(int i, int n) {

             boolean removed = false;

             Entry[] tab = table;

             int len = tab.length;

             do {

                 i = nextIndex(i, len);

                 Entry e = tab[i];

                 if (e != null && e.get() == null) {

                     n = len;

                     removed = true;

                     i = expungeStaleEntry(i);

                 }

             } while ( (n >>>= 1) != 0);

             return removed;

         }

         /**

          * Re-pack and/or re-size the table. First scan the entire

          * table removing stale entries. If this doesn't sufficiently

          * shrink the size of the table, double the table size.

          */

         private void rehash() {

             expungeStaleEntries();

             // Use lower threshold for doubling to avoid hysteresis

             if (size >= threshold - threshold / 4)

                 resize();

         }

         /**

          * Double the capacity of the table.

          */

         private void resize() {

             Entry[] oldTab = table;

             int oldLen = oldTab.length;

             int newLen = oldLen * 2;

             Entry[] newTab = new Entry[newLen];

             int count = 0;

             for (int j = 0; j < oldLen; ++j) {

                 Entry e = oldTab[j];

                 if (e != null) {

                     ThreadLocal k = e.get();

                     if (k == null) {

                         e.value = null; // Help the GC

                     } else {

                         int h = k.threadLocalHashCode & (newLen - 1);

                         while (newTab[h] != null)

                             h = nextIndex(h, newLen);

                         newTab[h] = e;

                         count++;

                     }

                 }

             }

             setThreshold(newLen);

             size = count;

             table = newTab;

         }

         /**

          * Expunge all stale entries in the table.

          */

         private void expungeStaleEntries() {

             Entry[] tab = table;

             int len = tab.length;

             for (int j = 0; j < len; j++) {

                 Entry e = tab[j];

                 if (e != null && e.get() == null)

                     expungeStaleEntry(j);

             }

         }

     }

 }