Save This Page
Home » openjdk-7 » java » lang » [javadoc | source]
    1   /*
    2    * Copyright (c) 1997, 2007, Oracle and/or its affiliates. All rights reserved.
    3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
    4    *
    5    * This code is free software; you can redistribute it and/or modify it
    6    * under the terms of the GNU General Public License version 2 only, as
    7    * published by the Free Software Foundation.  Oracle designates this
    8    * particular file as subject to the "Classpath" exception as provided
    9    * by Oracle in the LICENSE file that accompanied this code.
   10    *
   11    * This code is distributed in the hope that it will be useful, but WITHOUT
   12    * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   13    * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   14    * version 2 for more details (a copy is included in the LICENSE file that
   15    * accompanied this code).
   16    *
   17    * You should have received a copy of the GNU General Public License version
   18    * 2 along with this work; if not, write to the Free Software Foundation,
   19    * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   20    *
   21    * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   22    * or visit www.oracle.com if you need additional information or have any
   23    * questions.
   24    */
   25   
   26   package java.lang;
   27   import java.lang.ref;
   28   import java.util.concurrent.atomic.AtomicInteger;
   29   
   30   /**
   31    * This class provides thread-local variables.  These variables differ from
   32    * their normal counterparts in that each thread that accesses one (via its
   33    * <tt>get</tt> or <tt>set</tt> method) has its own, independently initialized
   34    * copy of the variable.  <tt>ThreadLocal</tt> instances are typically private
   35    * static fields in classes that wish to associate state with a thread (e.g.,
   36    * a user ID or Transaction ID).
   37    *
   38    * <p>For example, the class below generates unique identifiers local to each
   39    * thread.
   40    * A thread's id is assigned the first time it invokes <tt>ThreadId.get()</tt>
   41    * and remains unchanged on subsequent calls.
   42    * <pre>
   43    * import java.util.concurrent.atomic.AtomicInteger;
   44    *
   45    * public class ThreadId {
   46    *     // Atomic integer containing the next thread ID to be assigned
   47    *     private static final AtomicInteger nextId = new AtomicInteger(0);
   48    *
   49    *     // Thread local variable containing each thread's ID
   50    *     private static final ThreadLocal&lt;Integer> threadId =
   51    *         new ThreadLocal&lt;Integer>() {
   52    *             &#64;Override protected Integer initialValue() {
   53    *                 return nextId.getAndIncrement();
   54    *         }
   55    *     };
   56    *
   57    *     // Returns the current thread's unique ID, assigning it if necessary
   58    *     public static int get() {
   59    *         return threadId.get();
   60    *     }
   61    * }
   62    * </pre>
   63    * <p>Each thread holds an implicit reference to its copy of a thread-local
   64    * variable as long as the thread is alive and the <tt>ThreadLocal</tt>
   65    * instance is accessible; after a thread goes away, all of its copies of
   66    * thread-local instances are subject to garbage collection (unless other
   67    * references to these copies exist).
   68    *
   69    * @author  Josh Bloch and Doug Lea
   70    * @since   1.2
   71    */
   72   public class ThreadLocal<T> {
   73       /**
   74        * ThreadLocals rely on per-thread linear-probe hash maps attached
   75        * to each thread (Thread.threadLocals and
   76        * inheritableThreadLocals).  The ThreadLocal objects act as keys,
   77        * searched via threadLocalHashCode.  This is a custom hash code
   78        * (useful only within ThreadLocalMaps) that eliminates collisions
   79        * in the common case where consecutively constructed ThreadLocals
   80        * are used by the same threads, while remaining well-behaved in
   81        * less common cases.
   82        */
   83       private final int threadLocalHashCode = nextHashCode();
   84   
   85       /**
   86        * The next hash code to be given out. Updated atomically. Starts at
   87        * zero.
   88        */
   89       private static AtomicInteger nextHashCode =
   90           new AtomicInteger();
   91   
   92       /**
   93        * The difference between successively generated hash codes - turns
   94        * implicit sequential thread-local IDs into near-optimally spread
   95        * multiplicative hash values for power-of-two-sized tables.
   96        */
   97       private static final int HASH_INCREMENT = 0x61c88647;
   98   
   99       /**
  100        * Returns the next hash code.
  101        */
  102       private static int nextHashCode() {
  103           return nextHashCode.getAndAdd(HASH_INCREMENT);
  104       }
  105   
  106       /**
  107        * Returns the current thread's "initial value" for this
  108        * thread-local variable.  This method will be invoked the first
  109        * time a thread accesses the variable with the {@link #get}
  110        * method, unless the thread previously invoked the {@link #set}
  111        * method, in which case the <tt>initialValue</tt> method will not
  112        * be invoked for the thread.  Normally, this method is invoked at
  113        * most once per thread, but it may be invoked again in case of
  114        * subsequent invocations of {@link #remove} followed by {@link #get}.
  115        *
  116        * <p>This implementation simply returns <tt>null</tt>; if the
  117        * programmer desires thread-local variables to have an initial
  118        * value other than <tt>null</tt>, <tt>ThreadLocal</tt> must be
  119        * subclassed, and this method overridden.  Typically, an
  120        * anonymous inner class will be used.
  121        *
  122        * @return the initial value for this thread-local
  123        */
  124       protected T initialValue() {
  125           return null;
  126       }
  127   
  128       /**
  129        * Creates a thread local variable.
  130        */
  131       public ThreadLocal() {
  132       }
  133   
  134       /**
  135        * Returns the value in the current thread's copy of this
  136        * thread-local variable.  If the variable has no value for the
  137        * current thread, it is first initialized to the value returned
  138        * by an invocation of the {@link #initialValue} method.
  139        *
  140        * @return the current thread's value of this thread-local
  141        */
  142       public T get() {
  143           Thread t = Thread.currentThread();
  144           ThreadLocalMap map = getMap(t);
  145           if (map != null) {
  146               ThreadLocalMap.Entry e = map.getEntry(this);
  147               if (e != null)
  148                   return (T)e.value;
  149           }
  150           return setInitialValue();
  151       }
  152   
  153       /**
  154        * Variant of set() to establish initialValue. Used instead
  155        * of set() in case user has overridden the set() method.
  156        *
  157        * @return the initial value
  158        */
  159       private T setInitialValue() {
  160           T value = initialValue();
  161           Thread t = Thread.currentThread();
  162           ThreadLocalMap map = getMap(t);
  163           if (map != null)
  164               map.set(this, value);
  165           else
  166               createMap(t, value);
  167           return value;
  168       }
  169   
  170       /**
  171        * Sets the current thread's copy of this thread-local variable
  172        * to the specified value.  Most subclasses will have no need to
  173        * override this method, relying solely on the {@link #initialValue}
  174        * method to set the values of thread-locals.
  175        *
  176        * @param value the value to be stored in the current thread's copy of
  177        *        this thread-local.
  178        */
  179       public void set(T value) {
  180           Thread t = Thread.currentThread();
  181           ThreadLocalMap map = getMap(t);
  182           if (map != null)
  183               map.set(this, value);
  184           else
  185               createMap(t, value);
  186       }
  187   
  188       /**
  189        * Removes the current thread's value for this thread-local
  190        * variable.  If this thread-local variable is subsequently
  191        * {@linkplain #get read} by the current thread, its value will be
  192        * reinitialized by invoking its {@link #initialValue} method,
  193        * unless its value is {@linkplain #set set} by the current thread
  194        * in the interim.  This may result in multiple invocations of the
  195        * <tt>initialValue</tt> method in the current thread.
  196        *
  197        * @since 1.5
  198        */
  199        public void remove() {
  200            ThreadLocalMap m = getMap(Thread.currentThread());
  201            if (m != null)
  202                m.remove(this);
  203        }
  204   
  205       /**
  206        * Get the map associated with a ThreadLocal. Overridden in
  207        * InheritableThreadLocal.
  208        *
  209        * @param  t the current thread
  210        * @return the map
  211        */
  212       ThreadLocalMap getMap(Thread t) {
  213           return t.threadLocals;
  214       }
  215   
  216       /**
  217        * Create the map associated with a ThreadLocal. Overridden in
  218        * InheritableThreadLocal.
  219        *
  220        * @param t the current thread
  221        * @param firstValue value for the initial entry of the map
  222        * @param map the map to store.
  223        */
  224       void createMap(Thread t, T firstValue) {
  225           t.threadLocals = new ThreadLocalMap(this, firstValue);
  226       }
  227   
  228       /**
  229        * Factory method to create map of inherited thread locals.
  230        * Designed to be called only from Thread constructor.
  231        *
  232        * @param  parentMap the map associated with parent thread
  233        * @return a map containing the parent's inheritable bindings
  234        */
  235       static ThreadLocalMap createInheritedMap(ThreadLocalMap parentMap) {
  236           return new ThreadLocalMap(parentMap);
  237       }
  238   
  239       /**
  240        * Method childValue is visibly defined in subclass
  241        * InheritableThreadLocal, but is internally defined here for the
  242        * sake of providing createInheritedMap factory method without
  243        * needing to subclass the map class in InheritableThreadLocal.
  244        * This technique is preferable to the alternative of embedding
  245        * instanceof tests in methods.
  246        */
  247       T childValue(T parentValue) {
  248           throw new UnsupportedOperationException();
  249       }
  250   
  251       /**
  252        * ThreadLocalMap is a customized hash map suitable only for
  253        * maintaining thread local values. No operations are exported
  254        * outside of the ThreadLocal class. The class is package private to
  255        * allow declaration of fields in class Thread.  To help deal with
  256        * very large and long-lived usages, the hash table entries use
  257        * WeakReferences for keys. However, since reference queues are not
  258        * used, stale entries are guaranteed to be removed only when
  259        * the table starts running out of space.
  260        */
  261       static class ThreadLocalMap {
  262   
  263           /**
  264            * The entries in this hash map extend WeakReference, using
  265            * its main ref field as the key (which is always a
  266            * ThreadLocal object).  Note that null keys (i.e. entry.get()
  267            * == null) mean that the key is no longer referenced, so the
  268            * entry can be expunged from table.  Such entries are referred to
  269            * as "stale entries" in the code that follows.
  270            */
  271           static class Entry extends WeakReference<ThreadLocal> {
  272               /** The value associated with this ThreadLocal. */
  273               Object value;
  274   
  275               Entry(ThreadLocal k, Object v) {
  276                   super(k);
  277                   value = v;
  278               }
  279           }
  280   
  281           /**
  282            * The initial capacity -- MUST be a power of two.
  283            */
  284           private static final int INITIAL_CAPACITY = 16;
  285   
  286           /**
  287            * The table, resized as necessary.
  288            * table.length MUST always be a power of two.
  289            */
  290           private Entry[] table;
  291   
  292           /**
  293            * The number of entries in the table.
  294            */
  295           private int size = 0;
  296   
  297           /**
  298            * The next size value at which to resize.
  299            */
  300           private int threshold; // Default to 0
  301   
  302           /**
  303            * Set the resize threshold to maintain at worst a 2/3 load factor.
  304            */
  305           private void setThreshold(int len) {
  306               threshold = len * 2 / 3;
  307           }
  308   
  309           /**
  310            * Increment i modulo len.
  311            */
  312           private static int nextIndex(int i, int len) {
  313               return ((i + 1 < len) ? i + 1 : 0);
  314           }
  315   
  316           /**
  317            * Decrement i modulo len.
  318            */
  319           private static int prevIndex(int i, int len) {
  320               return ((i - 1 >= 0) ? i - 1 : len - 1);
  321           }
  322   
  323           /**
  324            * Construct a new map initially containing (firstKey, firstValue).
  325            * ThreadLocalMaps are constructed lazily, so we only create
  326            * one when we have at least one entry to put in it.
  327            */
  328           ThreadLocalMap(ThreadLocal firstKey, Object firstValue) {
  329               table = new Entry[INITIAL_CAPACITY];
  330               int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
  331               table[i] = new Entry(firstKey, firstValue);
  332               size = 1;
  333               setThreshold(INITIAL_CAPACITY);
  334           }
  335   
  336           /**
  337            * Construct a new map including all Inheritable ThreadLocals
  338            * from given parent map. Called only by createInheritedMap.
  339            *
  340            * @param parentMap the map associated with parent thread.
  341            */
  342           private ThreadLocalMap(ThreadLocalMap parentMap) {
  343               Entry[] parentTable = parentMap.table;
  344               int len = parentTable.length;
  345               setThreshold(len);
  346               table = new Entry[len];
  347   
  348               for (int j = 0; j < len; j++) {
  349                   Entry e = parentTable[j];
  350                   if (e != null) {
  351                       ThreadLocal key = e.get();
  352                       if (key != null) {
  353                           Object value = key.childValue(e.value);
  354                           Entry c = new Entry(key, value);
  355                           int h = key.threadLocalHashCode & (len - 1);
  356                           while (table[h] != null)
  357                               h = nextIndex(h, len);
  358                           table[h] = c;
  359                           size++;
  360                       }
  361                   }
  362               }
  363           }
  364   
  365           /**
  366            * Get the entry associated with key.  This method
  367            * itself handles only the fast path: a direct hit of existing
  368            * key. It otherwise relays to getEntryAfterMiss.  This is
  369            * designed to maximize performance for direct hits, in part
  370            * by making this method readily inlinable.
  371            *
  372            * @param  key the thread local object
  373            * @return the entry associated with key, or null if no such
  374            */
  375           private Entry getEntry(ThreadLocal key) {
  376               int i = key.threadLocalHashCode & (table.length - 1);
  377               Entry e = table[i];
  378               if (e != null && e.get() == key)
  379                   return e;
  380               else
  381                   return getEntryAfterMiss(key, i, e);
  382           }
  383   
  384           /**
  385            * Version of getEntry method for use when key is not found in
  386            * its direct hash slot.
  387            *
  388            * @param  key the thread local object
  389            * @param  i the table index for key's hash code
  390            * @param  e the entry at table[i]
  391            * @return the entry associated with key, or null if no such
  392            */
  393           private Entry getEntryAfterMiss(ThreadLocal key, int i, Entry e) {
  394               Entry[] tab = table;
  395               int len = tab.length;
  396   
  397               while (e != null) {
  398                   ThreadLocal k = e.get();
  399                   if (k == key)
  400                       return e;
  401                   if (k == null)
  402                       expungeStaleEntry(i);
  403                   else
  404                       i = nextIndex(i, len);
  405                   e = tab[i];
  406               }
  407               return null;
  408           }
  409   
  410           /**
  411            * Set the value associated with key.
  412            *
  413            * @param key the thread local object
  414            * @param value the value to be set
  415            */
  416           private void set(ThreadLocal key, Object value) {
  417   
  418               // We don't use a fast path as with get() because it is at
  419               // least as common to use set() to create new entries as
  420               // it is to replace existing ones, in which case, a fast
  421               // path would fail more often than not.
  422   
  423               Entry[] tab = table;
  424               int len = tab.length;
  425               int i = key.threadLocalHashCode & (len-1);
  426   
  427               for (Entry e = tab[i];
  428                    e != null;
  429                    e = tab[i = nextIndex(i, len)]) {
  430                   ThreadLocal k = e.get();
  431   
  432                   if (k == key) {
  433                       e.value = value;
  434                       return;
  435                   }
  436   
  437                   if (k == null) {
  438                       replaceStaleEntry(key, value, i);
  439                       return;
  440                   }
  441               }
  442   
  443               tab[i] = new Entry(key, value);
  444               int sz = ++size;
  445               if (!cleanSomeSlots(i, sz) && sz >= threshold)
  446                   rehash();
  447           }
  448   
  449           /**
  450            * Remove the entry for key.
  451            */
  452           private void remove(ThreadLocal key) {
  453               Entry[] tab = table;
  454               int len = tab.length;
  455               int i = key.threadLocalHashCode & (len-1);
  456               for (Entry e = tab[i];
  457                    e != null;
  458                    e = tab[i = nextIndex(i, len)]) {
  459                   if (e.get() == key) {
  460                       e.clear();
  461                       expungeStaleEntry(i);
  462                       return;
  463                   }
  464               }
  465           }
  466   
  467           /**
  468            * Replace a stale entry encountered during a set operation
  469            * with an entry for the specified key.  The value passed in
  470            * the value parameter is stored in the entry, whether or not
  471            * an entry already exists for the specified key.
  472            *
  473            * As a side effect, this method expunges all stale entries in the
  474            * "run" containing the stale entry.  (A run is a sequence of entries
  475            * between two null slots.)
  476            *
  477            * @param  key the key
  478            * @param  value the value to be associated with key
  479            * @param  staleSlot index of the first stale entry encountered while
  480            *         searching for key.
  481            */
  482           private void replaceStaleEntry(ThreadLocal key, Object value,
  483                                          int staleSlot) {
  484               Entry[] tab = table;
  485               int len = tab.length;
  486               Entry e;
  487   
  488               // Back up to check for prior stale entry in current run.
  489               // We clean out whole runs at a time to avoid continual
  490               // incremental rehashing due to garbage collector freeing
  491               // up refs in bunches (i.e., whenever the collector runs).
  492               int slotToExpunge = staleSlot;
  493               for (int i = prevIndex(staleSlot, len);
  494                    (e = tab[i]) != null;
  495                    i = prevIndex(i, len))
  496                   if (e.get() == null)
  497                       slotToExpunge = i;
  498   
  499               // Find either the key or trailing null slot of run, whichever
  500               // occurs first
  501               for (int i = nextIndex(staleSlot, len);
  502                    (e = tab[i]) != null;
  503                    i = nextIndex(i, len)) {
  504                   ThreadLocal k = e.get();
  505   
  506                   // If we find key, then we need to swap it
  507                   // with the stale entry to maintain hash table order.
  508                   // The newly stale slot, or any other stale slot
  509                   // encountered above it, can then be sent to expungeStaleEntry
  510                   // to remove or rehash all of the other entries in run.
  511                   if (k == key) {
  512                       e.value = value;
  513   
  514                       tab[i] = tab[staleSlot];
  515                       tab[staleSlot] = e;
  516   
  517                       // Start expunge at preceding stale entry if it exists
  518                       if (slotToExpunge == staleSlot)
  519                           slotToExpunge = i;
  520                       cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
  521                       return;
  522                   }
  523   
  524                   // If we didn't find stale entry on backward scan, the
  525                   // first stale entry seen while scanning for key is the
  526                   // first still present in the run.
  527                   if (k == null && slotToExpunge == staleSlot)
  528                       slotToExpunge = i;
  529               }
  530   
  531               // If key not found, put new entry in stale slot
  532               tab[staleSlot].value = null;
  533               tab[staleSlot] = new Entry(key, value);
  534   
  535               // If there are any other stale entries in run, expunge them
  536               if (slotToExpunge != staleSlot)
  537                   cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
  538           }
  539   
  540           /**
  541            * Expunge a stale entry by rehashing any possibly colliding entries
  542            * lying between staleSlot and the next null slot.  This also expunges
  543            * any other stale entries encountered before the trailing null.  See
  544            * Knuth, Section 6.4
  545            *
  546            * @param staleSlot index of slot known to have null key
  547            * @return the index of the next null slot after staleSlot
  548            * (all between staleSlot and this slot will have been checked
  549            * for expunging).
  550            */
  551           private int expungeStaleEntry(int staleSlot) {
  552               Entry[] tab = table;
  553               int len = tab.length;
  554   
  555               // expunge entry at staleSlot
  556               tab[staleSlot].value = null;
  557               tab[staleSlot] = null;
  558               size--;
  559   
  560               // Rehash until we encounter null
  561               Entry e;
  562               int i;
  563               for (i = nextIndex(staleSlot, len);
  564                    (e = tab[i]) != null;
  565                    i = nextIndex(i, len)) {
  566                   ThreadLocal k = e.get();
  567                   if (k == null) {
  568                       e.value = null;
  569                       tab[i] = null;
  570                       size--;
  571                   } else {
  572                       int h = k.threadLocalHashCode & (len - 1);
  573                       if (h != i) {
  574                           tab[i] = null;
  575   
  576                           // Unlike Knuth 6.4 Algorithm R, we must scan until
  577                           // null because multiple entries could have been stale.
  578                           while (tab[h] != null)
  579                               h = nextIndex(h, len);
  580                           tab[h] = e;
  581                       }
  582                   }
  583               }
  584               return i;
  585           }
  586   
  587           /**
  588            * Heuristically scan some cells looking for stale entries.
  589            * This is invoked when either a new element is added, or
  590            * another stale one has been expunged. It performs a
  591            * logarithmic number of scans, as a balance between no
  592            * scanning (fast but retains garbage) and a number of scans
  593            * proportional to number of elements, that would find all
  594            * garbage but would cause some insertions to take O(n) time.
  595            *
  596            * @param i a position known NOT to hold a stale entry. The
  597            * scan starts at the element after i.
  598            *
  599            * @param n scan control: <tt>log2(n)</tt> cells are scanned,
  600            * unless a stale entry is found, in which case
  601            * <tt>log2(table.length)-1</tt> additional cells are scanned.
  602            * When called from insertions, this parameter is the number
  603            * of elements, but when from replaceStaleEntry, it is the
  604            * table length. (Note: all this could be changed to be either
  605            * more or less aggressive by weighting n instead of just
  606            * using straight log n. But this version is simple, fast, and
  607            * seems to work well.)
  608            *
  609            * @return true if any stale entries have been removed.
  610            */
  611           private boolean cleanSomeSlots(int i, int n) {
  612               boolean removed = false;
  613               Entry[] tab = table;
  614               int len = tab.length;
  615               do {
  616                   i = nextIndex(i, len);
  617                   Entry e = tab[i];
  618                   if (e != null && e.get() == null) {
  619                       n = len;
  620                       removed = true;
  621                       i = expungeStaleEntry(i);
  622                   }
  623               } while ( (n >>>= 1) != 0);
  624               return removed;
  625           }
  626   
  627           /**
  628            * Re-pack and/or re-size the table. First scan the entire
  629            * table removing stale entries. If this doesn't sufficiently
  630            * shrink the size of the table, double the table size.
  631            */
  632           private void rehash() {
  633               expungeStaleEntries();
  634   
  635               // Use lower threshold for doubling to avoid hysteresis
  636               if (size >= threshold - threshold / 4)
  637                   resize();
  638           }
  639   
  640           /**
  641            * Double the capacity of the table.
  642            */
  643           private void resize() {
  644               Entry[] oldTab = table;
  645               int oldLen = oldTab.length;
  646               int newLen = oldLen * 2;
  647               Entry[] newTab = new Entry[newLen];
  648               int count = 0;
  649   
  650               for (int j = 0; j < oldLen; ++j) {
  651                   Entry e = oldTab[j];
  652                   if (e != null) {
  653                       ThreadLocal k = e.get();
  654                       if (k == null) {
  655                           e.value = null; // Help the GC
  656                       } else {
  657                           int h = k.threadLocalHashCode & (newLen - 1);
  658                           while (newTab[h] != null)
  659                               h = nextIndex(h, newLen);
  660                           newTab[h] = e;
  661                           count++;
  662                       }
  663                   }
  664               }
  665   
  666               setThreshold(newLen);
  667               size = count;
  668               table = newTab;
  669           }
  670   
  671           /**
  672            * Expunge all stale entries in the table.
  673            */
  674           private void expungeStaleEntries() {
  675               Entry[] tab = table;
  676               int len = tab.length;
  677               for (int j = 0; j < len; j++) {
  678                   Entry e = tab[j];
  679                   if (e != null && e.get() == null)
  680                       expungeStaleEntry(j);
  681               }
  682           }
  683       }
  684   }

Save This Page
Home » openjdk-7 » java » lang » [javadoc | source]