001: /*
002: * @(#)ThreadLocal.java 1.23 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027:
028: package java.lang;
029:
030: import java.lang.ref.*;
031:
032: /**
033: * This class provides thread-local variables. These variables differ from
034: * their normal counterparts in that each thread that accesses one (via its
035: * <tt>get</tt> or <tt>set</tt> method) has its own, independently initialized
036: * copy of the variable. <tt>ThreadLocal</tt> instances are typically private
037: * static fields in classes that wish to associate state with a thread (e.g.,
038: * a user ID or Transaction ID).
039: *
040: * <p>For example, in the class below, the private static <tt>ThreadLocal</tt>
041: * instance (<tt>serialNum</tt>) maintains a "serial number" for each thread
042: * that invokes the class's static <tt>SerialNum.get()</tt> method, which
043: * returns the current thread's serial number. (A thread's serial number is
044: * assigned the first time it invokes <tt>SerialNum.get()</tt>, and remains
045: * unchanged on subsequent calls.)
046: * <pre>
047: * public class SerialNum {
048: * // The next serial number to be assigned
049: * private static int nextSerialNum = 0;
050: *
051: * private static ThreadLocal serialNum = new ThreadLocal() {
052: * protected synchronized Object initialValue() {
053: * return new Integer(nextSerialNum++);
054: * }
055: * };
056: *
057: * public static int get() {
058: * return ((Integer) (serialNum.get())).intValue();
059: * }
060: * }
061: * </pre>
062: *
063: * <p>Each thread holds an implicit reference to its copy of a thread-local
064: * variable as long as the thread is alive and the <tt>ThreadLocal</tt>
065: * instance is accessible; after a thread goes away, all of its copies of
066: * thread-local instances are subject to garbage collection (unless other
067: * references to these copies exist).
068: *
069: * @author Josh Bloch and Doug Lea
070: * @version 1.23, 10/10/06
071: * @since 1.2
072: */
073: public class ThreadLocal {
074: /**
075: * ThreadLocals rely on per-thread hash maps attached to each thread
076: * (Thread.threadLocals and inheritableThreadLocals). The ThreadLocal
077: * objects act as keys, searched via threadLocalHashCode. This is a
078: * custom hash code (useful only within ThreadLocalMaps) that eliminates
079: * collisions in the common case where consecutively constructed
080: * ThreadLocals are used by the same threads, while remaining well-behaved
081: * in less common cases.
082: */
083: private final int threadLocalHashCode = nextHashCode();
084:
085: /**
086: * The next hash code to be given out. Accessed only by like-named method.
087: */
088: private static int nextHashCode = 0;
089:
090: /**
091: * The difference between successively generated hash codes - turns
092: * implicit sequential thread-local IDs into near-optimally spread
093: * multiplicative hash values for power-of-two-sized tables.
094: */
095: private static final int HASH_INCREMENT = 0x61c88647;
096:
097: /**
098: * Compute the next hash code. The static synchronization used here
099: * should not be a performance bottleneck. When ThreadLocals are
100: * generated in different threads at a fast enough rate to regularly
101: * contend on this lock, memory contention is by far a more serious
102: * problem than lock contention.
103: */
104: private static synchronized int nextHashCode() {
105: int h = nextHashCode;
106: nextHashCode = h + HASH_INCREMENT;
107: return h;
108: }
109:
110: /**
111: * Returns the current thread's initial value for this thread-local
112: * variable. This method will be invoked at most once per accessing
113: * thread for each thread-local, the first time the thread accesses the
114: * variable with the {@link #get()} method. The <tt>initialValue</tt>
115: * method will not be invoked in a thread if the thread invokes the {@link
116: * #set(Object)} method prior to the <tt>get</tt> method.
117: *
118: * <p>This implementation simply returns <tt>null</tt>; if the programmer
119: * desires thread-local variables to be initialized to some value other
120: * than <tt>null</tt>, <tt>ThreadLocal</tt> must be subclassed, and this
121: * method overridden. Typically, an anonymous inner class will be used.
122: * Typical implementations of <tt>initialValue</tt> will invoke an
123: * appropriate constructor and return the newly constructed object.
124: *
125: * @return the initial value for this thread-local
126: */
127: protected Object initialValue() {
128: return null;
129: }
130:
131: /**
132: * Returns the value in the current thread's copy of this thread-local
133: * variable. Creates and initializes the copy if this is the first time
134: * the thread has called this method.
135: *
136: * @return the current thread's value of this thread-local
137: */
138: public Object get() {
139: Thread t = Thread.currentThread();
140: ThreadLocalMap map = getMap(t);
141: if (map != null)
142: return map.get(this );
143:
144: // Maps are constructed lazily. if the map for this thread
145: // doesn't exist, create it, with this ThreadLocal and its
146: // initial value as its only entry.
147: Object value = initialValue();
148: createMap(t, value);
149: return value;
150: }
151:
152: /**
153: * Sets the current thread's copy of this thread-local variable
154: * to the specified value. Many applications will have no need for
155: * this functionality, relying solely on the {@link #initialValue()}
156: * method to set the values of thread-locals.
157: *
158: * @param value the value to be stored in the current threads' copy of
159: * this thread-local.
160: */
161: public void set(Object value) {
162: Thread t = Thread.currentThread();
163: ThreadLocalMap map = getMap(t);
164: if (map != null)
165: map.set(this , value);
166: else
167: createMap(t, value);
168: }
169:
170: /*
171: * Removes the value for this ThreadLocal.
172:
173: THIS METHOD COULD BE UNCOMMENTED TO ADD IT TO THE PUBLIC API IF THAT
174: IS THOUGHT TO DESIRABLE AT SOME POINT.
175:
176: public void remove() {
177: ThreadLocalMap m = getMap(Thread.currentThread());
178: if (m != null)
179: m.remove(this);
180: }
181:
182: */
183:
184: /**
185: * Get the map associated with a ThreadLocal. Overridden in
186: * InheritableThreadLocal.
187: *
188: * @param t the current thread
189: * @return the map
190: */
191: ThreadLocalMap getMap(Thread t) {
192: return t.threadLocals;
193: }
194:
195: /**
196: * Create the map associated with a ThreadLocal. Overridden in
197: * InheritableThreadLocal.
198: *
199: * @param t the current thread
200: * @param firstValue value for the initial entry of the map
201: * @param map the map to store.
202: */
203: void createMap(Thread t, Object firstValue) {
204: t.threadLocals = new ThreadLocalMap(this , firstValue);
205: }
206:
207: /**
208: * Factory method to create map of inherited thread locals.
209: * Designed to be called only from Thread constructor.
210: *
211: * @param parentMap the map associated with parent thread
212: * @return a map containing the parent's inheritable bindings
213: */
214: static ThreadLocalMap createInheritedMap(ThreadLocalMap parentMap) {
215: return new ThreadLocalMap(parentMap);
216: }
217:
218: /**
219: * Method childValue is visibly defined in subclass
220: * InheritableThreadLocal, but is internally defined here for the
221: * sake of providing createInheritedMap factory method without
222: * needing to subclass the map class in InheritableThreadLocal.
223: * This technique is preferable to the alternative of embedding
224: * instanceof tests in methods.
225: */
226: Object childValue(Object parentValue) {
227: throw new UnsupportedOperationException();
228: }
229:
230: /**
231: * ThreadLocalMap is a customized hash map suitable only for
232: * maintaining thread local values. No operations are exported
233: * outside of the ThreadLocal class. The class is package private to
234: * allow declaration of fields in class Thread. To help deal with
235: * very large and long-lived usages, the hash table entries use
236: * WeakReferences for keys. However, since reference queues are not
237: * used, stale entries are guaranteed to be removed only when
238: * the table starts running out of space.
239: */
240: static class ThreadLocalMap {
241:
242: /**
243: * The entries in this hash map extend WeakReference, using
244: * its main ref field as the key (which is always a
245: * ThreadLocal object). Note that null keys (i.e. entry.get()
246: * == null) mean that the key is no longer referenced, so the
247: * entry can be expunged from table. Such entries are referred to
248: * as "stale entries" in the code that follows.
249: */
250: private static class Entry extends WeakReference {
251: /** The value associated with this ThreadLocal. */
252: private Object value;
253:
254: private Entry(ThreadLocal k, Object v) {
255: super (k);
256: value = v;
257: }
258: }
259:
260: /**
261: * The initial capacity -- MUST be a power of two.
262: */
263: private static final int INITIAL_CAPACITY = 16;
264:
265: /**
266: * The table, resized as necessary.
267: * table.length MUST always be a power of two.
268: */
269: private Entry[] table;
270:
271: /**
272: * The number of entries in the table.
273: */
274: private int size = 0;
275:
276: /**
277: * The next size value at which to resize.
278: */
279: private int threshold;
280:
281: /**
282: * Set the resize threshold to maintain at worst a 2/3 load factor.
283: */
284: private void setThreshold(int len) {
285: threshold = len * 2 / 3;
286: }
287:
288: /**
289: * Increment i modulo len.
290: */
291: private static int nextIndex(int i, int len) {
292: return ((i + 1 < len) ? i + 1 : 0);
293: }
294:
295: /**
296: * Decrement i modulo len.
297: */
298: private static int prevIndex(int i, int len) {
299: return ((i - 1 >= 0) ? i - 1 : len - 1);
300: }
301:
302: /**
303: * Construct a new map initially containing (firstKey, firstValue).
304: * ThreadLocalMaps are constructed lazily, so we only create
305: * one when we have at least one entry to put in it.
306: */
307: ThreadLocalMap(ThreadLocal firstKey, Object firstValue) {
308: table = new Entry[INITIAL_CAPACITY];
309: int i = firstKey.threadLocalHashCode
310: & (INITIAL_CAPACITY - 1);
311: table[i] = new Entry(firstKey, firstValue);
312: size = 1;
313: setThreshold(INITIAL_CAPACITY);
314: }
315:
316: /**
317: * Construct a new map including all Inheritable ThreadLocals
318: * from given parent map. Called only by createInheritedMap.
319: *
320: * @param parentMap the map associated with parent thread.
321: */
322: private ThreadLocalMap(ThreadLocalMap parentMap) {
323: Entry[] parentTable = parentMap.table;
324: int len = parentTable.length;
325: setThreshold(len);
326: table = new Entry[len];
327:
328: for (int j = 0; j < len; j++) {
329: Entry e = parentTable[j];
330: if (e != null) {
331: Object k = e.get();
332: if (k != null) {
333: ThreadLocal key = (ThreadLocal) (k);
334: Object value = key.childValue(e.value);
335: Entry c = new Entry(key, value);
336: int h = key.threadLocalHashCode & (len - 1);
337: while (table[h] != null)
338: h = nextIndex(h, len);
339: table[h] = c;
340: size++;
341: }
342: }
343: }
344: }
345:
346: /**
347: * Get the value associated with key with code h. This method itself
348: * handles only the fast path: a direct hit of existing key. It
349: * otherwise relays to getAfterMiss. This is designed to maximize
350: * performance for direct hits, in part by making this method readily
351: * inlinable.
352: *
353: * @param key the thread local object
354: * @param h key's hash code
355: * @return the value associated with key
356: */
357: private Object get(ThreadLocal key) {
358: int i = key.threadLocalHashCode & (table.length - 1);
359: Entry e = table[i];
360: if (e != null && e.get() == key)
361: return e.value;
362:
363: return getAfterMiss(key, i, e);
364: }
365:
366: /**
367: * Version of get method for use when key is not found in its
368: * direct hash slot.
369: *
370: * @param key the thread local object
371: * @param i the table index for key's hash code
372: * @param e the entry at table[i];
373: * @return the value associated with key
374: */
375: private Object getAfterMiss(ThreadLocal key, int i, Entry e) {
376: Entry[] tab = table;
377: int len = tab.length;
378:
379: while (e != null) {
380: Object k = e.get();
381: if (k == key)
382: return e.value;
383: if (k == null)
384: return replaceStaleEntry(key, null, i, true);
385:
386: i = nextIndex(i, len);
387: e = tab[i];
388: }
389:
390: Object value = key.initialValue();
391: tab[i] = new Entry(key, value);
392: if (++size >= threshold)
393: rehash();
394:
395: return value;
396: }
397:
398: /**
399: * Set the value associated with key.
400: *
401: * @param key the thread local object
402: * @param value the value to be set
403: */
404: private void set(ThreadLocal key, Object value) {
405:
406: // We don't use a fast path as with get() because it is at
407: // least as common to use set() to create new entries as
408: // it is to replace existing ones, in which case, a fast
409: // path would fail more often than not.
410:
411: Entry[] tab = table;
412: int len = tab.length;
413: int i = key.threadLocalHashCode & (len - 1);
414:
415: for (Entry e = tab[i]; e != null; e = tab[i = nextIndex(i,
416: len)]) {
417: Object k = e.get();
418:
419: if (k == key) {
420: e.value = value;
421: return;
422: }
423:
424: if (k == null) {
425: replaceStaleEntry(key, value, i, false);
426: return;
427: }
428: }
429:
430: tab[i] = new Entry(key, value);
431: if (++size >= threshold)
432: rehash();
433: }
434:
435: /**
436: * Remove the entry for key.
437:
438: THIS IS USED ONLY BY ThreadLocal.remove, WHICH IS NOT CURRENTLY
439: PART OF THE PUBLIC API. IF IT IS ADDED TO THE PUBLIC API AT SOME
440: POINT, THIS METHOD MUST BE UNCOMMENTED.
441:
442: private void remove(ThreadLocal key) {
443: Entry[] tab = table;
444: int len = tab.length;
445: int i = key.threadLocalHashCode & (len-1);
446: for (Entry e = tab[i]; e != null; e = tab[i = nextIndex(i, len)]) {
447: if (e.get() == key) {
448: e.clear();
449: expungeStaleEntry(i);
450: return;
451: }
452: }
453: }
454:
455: */
456:
457: /**
458: * Replace a stale entry encountered during a get or set operation
459: * with an entry for the specified key. If actAsGet is true and an
460: * entry for the key already exists, the value in the entry is
461: * unchanged; if no entry exists for the key, the value in the new
462: * entry is obtained by calling key.initialValue. If actAsGet is
463: * false, the value passed in the value parameter is stored in the
464: * entry, whether or not an entry already exists for the specified key.
465: *
466: * As a side effect, this method expunges all stale entries in the
467: * "run" containing the stale entry. (A run is a sequence of entries
468: * between two null slots.)
469: *
470: * @param key the key
471: * @param value the value to be associated with key; meaningful only
472: * if actAsGet is false.
473: * @param staleSlot index of the first stale entry encountered while
474: * searching for key.
475: * @param actAsGet true if this method should act as a get; false
476: * it should act as a set.
477: * @return the value associated with key after the operation completes.
478: */
479: private Object replaceStaleEntry(ThreadLocal key, Object value,
480: int staleSlot, boolean actAsGet) {
481: Entry[] tab = table;
482: int len = tab.length;
483: Entry e;
484:
485: // Back up to check for prior stale entry in current run.
486: // We clean out whole runs at a time to avoid continual
487: // incremental rehashing due to garbage collector freeing
488: // up refs in bunches (i.e., whenever the collector runs).
489: int slotToExpunge = staleSlot;
490: for (int i = prevIndex(staleSlot, len); (e = tab[i]) != null; i = prevIndex(
491: i, len))
492: if (e.get() == null)
493: slotToExpunge = i;
494:
495: // Find either the key or trailing null slot of run, whichever
496: // occurs first
497: for (int i = nextIndex(staleSlot, len); (e = tab[i]) != null; i = nextIndex(
498: i, len)) {
499: Object k = e.get();
500:
501: // If we find key, then we need to swap it
502: // with the stale entry to maintain hash table order.
503: // The newly stale slot, or any other stale slot
504: // encountered above it, can then be sent to expungeStaleEntry
505: // to remove or rehash all of the other entries in run.
506: if (k == key) {
507: if (actAsGet)
508: value = e.value;
509: else
510: e.value = value;
511:
512: tab[i] = tab[staleSlot];
513: tab[staleSlot] = e;
514:
515: // Start expunge at preceding stale entry if it exists
516: if (slotToExpunge == staleSlot)
517: slotToExpunge = i;
518: expungeStaleEntry(slotToExpunge);
519: return value;
520: }
521:
522: // If we didn't find stale entry on backward scan, the
523: // the first stale entry seen while scanning for key is the
524: // first still present in the run.
525: if (k == null && slotToExpunge == staleSlot)
526: slotToExpunge = i;
527: }
528:
529: // If key not found, put new entry in stale slot
530: if (actAsGet)
531: value = key.initialValue();
532: tab[staleSlot].value = null; // Help the GC
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: expungeStaleEntry(slotToExpunge);
538:
539: return value;
540: }
541:
542: /**
543: * Expunge a stale entry by rehashing any possibly colliding entries
544: * lying between staleSlot and the next null slot. This also expunges
545: * any other stale entries encountered before the trailing null. See
546: * Knuth, Section 6.4
547: *
548: * @param staleSlot index of slot known to have null key
549: */
550: private void expungeStaleEntry(int staleSlot) {
551: Entry[] tab = table;
552: int len = tab.length;
553:
554: // expunge entry at staleSlot
555: tab[staleSlot].value = null; // Help the GC
556: tab[staleSlot] = null;
557: size--;
558:
559: // Rehash until we encounter null
560: Entry e;
561: for (int i = nextIndex(staleSlot, len); (e = tab[i]) != null; i = nextIndex(
562: i, len)) {
563: Object k = e.get();
564: if (k == null) {
565: e.value = null; // Help the GC
566: tab[i] = null;
567: size--;
568: } else {
569: ThreadLocal key = (ThreadLocal) (k);
570: int h = key.threadLocalHashCode & (len - 1);
571: if (h != i) {
572: tab[i] = null;
573:
574: // Unlike Knuth 6.4 Algorithm R, we must scan until
575: // null because multiple entries could have been stale.
576: while (tab[h] != null)
577: h = nextIndex(h, len);
578: tab[h] = e;
579: }
580: }
581: }
582: }
583:
584: /**
585: * Re-pack and/or re-size the table. First scan the entire
586: * table removing stale entries. If this doesn't sufficiently
587: * shrink the size of the table, double the table size.
588: */
589: private void rehash() {
590: expungeStaleEntries();
591:
592: // Use lower threshold for doubling to avoid hysteresis
593: if (size >= threshold - threshold / 4)
594: resize();
595: }
596:
597: /**
598: * Double the capacity of the table.
599: */
600: private void resize() {
601: Entry[] oldTab = table;
602: int oldLen = oldTab.length;
603: int newLen = oldLen * 2;
604: Entry[] newTab = new Entry[newLen];
605: int count = 0;
606:
607: for (int j = 0; j < oldLen; ++j) {
608: Entry e = oldTab[j];
609: oldTab[j] = null; // Help the GC
610: if (e != null) {
611: Object k = e.get();
612: if (k == null) {
613: e.value = null; // Help the GC
614: } else {
615: ThreadLocal key = (ThreadLocal) (k);
616: int h = key.threadLocalHashCode & (newLen - 1);
617: while (newTab[h] != null)
618: h = nextIndex(h, newLen);
619: newTab[h] = e;
620: count++;
621: }
622: }
623: }
624:
625: setThreshold(newLen);
626: size = count;
627: table = newTab;
628: }
629:
630: /**
631: * Expunge all stale entries in the table.
632: */
633: private void expungeStaleEntries() {
634: Entry[] tab = table;
635: int len = tab.length;
636: for (int j = 0; j < len; j++) {
637: Entry e = tab[j];
638: if (e != null && e.get() == null)
639: expungeStaleEntry(j);
640: }
641: }
642: }
643: }
|