1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 package java.lang;
19
20 import java.lang.ref.WeakReference;
21 import java.lang.ref.Reference;
22 import java.util.concurrent.atomic.AtomicInteger;
23
24 /**
25 * A variable for which each thread has its own value. Supports {@code null}
26 * values.
27 *
28 * @see java.lang.Thread
29 * @author Bob Lee
30 */
31 public class ThreadLocal<T> {
32
33 /* Thanks to Josh Bloch and Doug Lea for code reviews and impl advice. */
34
35 /**
36 * Creates a new thread local variable.
37 */
38 public ThreadLocal() {}
39
40 /**
41 * Returns the value of this variable for the current thread. If an entry
42 * doesn't yet exist for this variable on this thread, this method will
43 * create an entry, populating the value with the result of
44 * {@link #initialValue()}.
45 */
46 @SuppressWarnings("unchecked")
47 public T get() {
48 // Optimized for the fast path.
49 Thread currentThread = Thread.currentThread();
50 Values values = values(currentThread);
51 if (values != null) {
52 Object[] table = values.table;
53 int index = hash & values.mask;
54 if (this.reference == table[index]) {
55 return (T) table[index + 1];
56 }
57 } else {
58 values = initializeValues(currentThread);
59 }
60
61 return (T) values.getAfterMiss(this);
62 }
63
64 /**
65 * Provides the initial value of this variable for the current thread.
66 * The default implementation returns {@code null}.
67 */
68 protected T initialValue() {
69 return null;
70 }
71
72 /**
73 * Sets the value of this variable for the current thread. If set to
74 * null, the value will be set to null and the underlying entry will still
75 * be present.
76 */
77 public void set(T value) {
78 Thread currentThread = Thread.currentThread();
79 Values values = values(currentThread);
80 if (values == null) {
81 values = initializeValues(currentThread);
82 }
83 values.put(this, value);
84 }
85
86 /**
87 * Removes the entry for this variable in the current thread. If this call
88 * is followed by a {@link #get()} before a {@link #set(Object)},
89 * {@code #get()} will call {@link #initialValue()} and create a new
90 * entry with the resulting value.
91 */
92 public void remove() {
93 Thread currentThread = Thread.currentThread();
94 Values values = values(currentThread);
95 if (values != null) {
96 values.remove(this);
97 }
98 }
99
100 /**
101 * Creates Values instance for this thread and variable type.
102 */
103 Values initializeValues(Thread current) {
104 return current.localValues = new Values();
105 }
106
107 /**
108 * Gets Values instance for this thread and variable type.
109 */
110 Values values(Thread current) {
111 return current.localValues;
112 }
113
114 /** Weak reference to this thread local instance. */
115 private final Reference<ThreadLocal<T>> reference
116 = new WeakReference<ThreadLocal<T>>(this);
117
118 /** Hash counter. */
119 private static AtomicInteger hashCounter = new AtomicInteger(0);
120
121 /**
122 * Internal hash. We deliberately don't bother with #hashCode().
123 * Hashes must be even. This ensures that the result of
124 * (hash & (table.length - 1)) points to a key and not a value.
125 *
126 * We increment by Doug Lea's Magic Number(TM) (*2 since keys are in
127 * every other bucket) to help prevent clustering.
128 */
129 private final int hash = hashCounter.getAndAdd(0x61c88647 << 1);
130
131 /**
132 * Per-thread map of ThreadLocal instances to values.
133 */
134 static class Values {
135
136 /**
137 * Size must always be a power of 2.
138 */
139 private static final int INITIAL_SIZE = 16;
140
141 /**
142 * Placeholder for deleted entries.
143 */
144 private static final Object TOMBSTONE = new Object();
145
146 /**
147 * Map entries. Contains alternating keys (ThreadLocal) and values.
148 * The length is always a power of 2.
149 */
150 private Object[] table;
151
152 /** Used to turn hashes into indices. */
153 private int mask;
154
155 /** Number of live entries. */
156 private int size;
157
158 /** Number of tombstones. */
159 private int tombstones;
160
161 /** Maximum number of live entries and tombstones. */
162 private int maximumLoad;
163
164 /** Points to the next cell to clean up. */
165 private int clean;
166
167 /**
168 * Constructs a new, empty instance.
169 */
170 Values() {
171 initializeTable(INITIAL_SIZE);
172 this.size = 0;
173 this.tombstones = 0;
174 }
175
176 /**
177 * Used for InheritableThreadLocals.
178 */
179 Values(Values fromParent) {
180 this.table = fromParent.table.clone();
181 this.mask = fromParent.mask;
182 this.size = fromParent.size;
183 this.tombstones = fromParent.tombstones;
184 this.maximumLoad = fromParent.maximumLoad;
185 this.clean = fromParent.clean;
186 inheritValues(fromParent);
187 }
188
189 /**
190 * Inherits values from a parent thread.
191 */
192 @SuppressWarnings({"unchecked"})
193 private void inheritValues(Values fromParent) {
194 // Transfer values from parent to child thread.
195 Object[] table = this.table;
196 for (int i = table.length - 2; i >= 0; i -= 2) {
197 Object k = table[i];
198
199 if (k == null || k == TOMBSTONE) {
200 // Skip this entry.
201 continue;
202 }
203
204 // The table can only contain null, tombstones and references.
205 Reference<InheritableThreadLocal<?>> reference
206 = (Reference<InheritableThreadLocal<?>>) k;
207 // Raw type enables us to pass in an Object below.
208 InheritableThreadLocal key = reference.get();
209 if (key != null) {
210 // Replace value with filtered value.
211 // We should just let exceptions bubble out and tank
212 // the thread creation
213 table[i + 1] = key.childValue(fromParent.table[i + 1]);
214 } else {
215 // The key was reclaimed.
216 table[i] = TOMBSTONE;
217 table[i + 1] = null;
218 fromParent.table[i] = TOMBSTONE;
219 fromParent.table[i + 1] = null;
220
221 tombstones++;
222 fromParent.tombstones++;
223
224 size--;
225 fromParent.size--;
226 }
227 }
228 }
229
230 /**
231 * Creates a new, empty table with the given capacity.
232 */
233 private void initializeTable(int capacity) {
234 this.table = new Object[capacity << 1];
235 this.mask = table.length - 1;
236 this.clean = 0;
237 this.maximumLoad = capacity * 2 / 3; // 2/3
238 }
239
240 /**
241 * Cleans up after garbage-collected thread locals.
242 */
243 private void cleanUp() {
244 if (rehash()) {
245 // If we rehashed, we needn't clean up (clean up happens as
246 // a side effect).
247 return;
248 }
249
250 if (size == 0) {
251 // No live entries == nothing to clean.
252 return;
253 }
254
255 // Clean log(table.length) entries picking up where we left off
256 // last time.
257 int index = clean;
258 Object[] table = this.table;
259 for (int counter = table.length; counter > 0; counter >>= 1,
260 index = next(index)) {
261 Object k = table[index];
262
263 if (k == TOMBSTONE || k == null) {
264 continue; // on to next entry
265 }
266
267 // The table can only contain null, tombstones and references.
268 @SuppressWarnings("unchecked")
269 Reference<ThreadLocal<?>> reference
270 = (Reference<ThreadLocal<?>>) k;
271 if (reference.get() == null) {
272 // This thread local was reclaimed by the garbage collector.
273 table[index] = TOMBSTONE;
274 table[index + 1] = null;
275 tombstones++;
276 size--;
277 }
278 }
279
280 // Point cursor to next index.
281 clean = index;
282 }
283
284 /**
285 * Rehashes the table, expanding or contracting it as necessary.
286 * Gets rid of tombstones. Returns true if a rehash occurred.
287 * We must rehash every time we fill a null slot; we depend on the
288 * presence of null slots to end searches (otherwise, we'll infinitely
289 * loop).
290 */
291 private boolean rehash() {
292 if (tombstones + size < maximumLoad) {
293 return false;
294 }
295
296 int capacity = table.length >> 1;
297
298 // Default to the same capacity. This will create a table of the
299 // same size and move over the live entries, analogous to a
300 // garbage collection. This should only happen if you churn a
301 // bunch of thread local garbage (removing and reinserting
302 // the same thread locals over and over will overwrite tombstones
303 // and not fill up the table).
304 int newCapacity = capacity;
305
306 if (size > (capacity >> 1)) {
307 // More than 1/2 filled w/ live entries.
308 // Double size.
309 newCapacity = capacity << 1;
310 }
311
312 Object[] oldTable = this.table;
313
314 // Allocate new table.
315 initializeTable(newCapacity);
316
317 // We won't have any tombstones after this.
318 this.tombstones = 0;
319
320 // If we have no live entries, we can quit here.
321 if (size == 0) {
322 return true;
323 }
324
325 // Move over entries.
326 for (int i = oldTable.length - 2; i >= 0; i -= 2) {
327 Object k = oldTable[i];
328 if (k == null || k == TOMBSTONE) {
329 // Skip this entry.
330 continue;
331 }
332
333 // The table can only contain null, tombstones and references.
334 @SuppressWarnings("unchecked")
335 Reference<ThreadLocal<?>> reference
336 = (Reference<ThreadLocal<?>>) k;
337 ThreadLocal<?> key = reference.get();
338 if (key != null) {
339 // Entry is still live. Move it over.
340 add(key, oldTable[i + 1]);
341 } else {
342 // The key was reclaimed.
343 size--;
344 }
345 }
346
347 return true;
348 }
349
350 /**
351 * Adds an entry during rehashing. Compared to put(), this method
352 * doesn't have to clean up, check for existing entries, account for
353 * tombstones, etc.
354 */
355 void add(ThreadLocal<?> key, Object value) {
356 for (int index = key.hash & mask;; index = next(index)) {
357 Object k = table[index];
358 if (k == null) {
359 table[index] = key.reference;
360 table[index + 1] = value;
361 return;
362 }
363 }
364 }
365
366 /**
367 * Sets entry for given ThreadLocal to given value, creating an
368 * entry if necessary.
369 */
370 void put(ThreadLocal<?> key, Object value) {
371 cleanUp();
372
373 // Keep track of first tombstone. That's where we want to go back
374 // and add an entry if necessary.
375 int firstTombstone = -1;
376
377 for (int index = key.hash & mask;; index = next(index)) {
378 Object k = table[index];
379
380 if (k == key.reference) {
381 // Replace existing entry.
382 table[index + 1] = value;
383 return;
384 }
385
386 if (k == null) {
387 if (firstTombstone == -1) {
388 // Fill in null slot.
389 table[index] = key.reference;
390 table[index + 1] = value;
391 size++;
392 return;
393 }
394
395 // Go back and replace first tombstone.
396 table[firstTombstone] = key.reference;
397 table[firstTombstone + 1] = value;
398 tombstones--;
399 size++;
400 return;
401 }
402
403 // Remember first tombstone.
404 if (firstTombstone == -1 && k == TOMBSTONE) {
405 firstTombstone = index;
406 }
407 }
408 }
409
410 /**
411 * Gets value for given ThreadLocal after not finding it in the first
412 * slot.
413 */
414 Object getAfterMiss(ThreadLocal<?> key) {
415 Object[] table = this.table;
416 int index = key.hash & mask;
417
418 // If the first slot is empty, the search is over.
419 if (table[index] == null) {
420 Object value = key.initialValue();
421
422 // If the table is still the same and the slot is still empty...
423 if (this.table == table && table[index] == null) {
424 table[index] = key.reference;
425 table[index + 1] = value;
426 size++;
427
428 cleanUp();
429 return value;
430 }
431
432 // The table changed during initialValue().
433 put(key, value);
434 return value;
435 }
436
437 // Keep track of first tombstone. That's where we want to go back
438 // and add an entry if necessary.
439 int firstTombstone = -1;
440
441 // Continue search.
442 for (index = next(index);; index = next(index)) {
443 Object reference = table[index];
444 if (reference == key.reference) {
445 return table[index + 1];
446 }
447
448 // If no entry was found...
449 if (reference == null) {
450 Object value = key.initialValue();
451
452 // If the table is still the same...
453 if (this.table == table) {
454 // If we passed a tombstone and that slot still
455 // contains a tombstone...
456 if (firstTombstone > -1
457 && table[firstTombstone] == TOMBSTONE) {
458 table[firstTombstone] = key.reference;
459 table[firstTombstone + 1] = value;
460 tombstones--;
461 size++;
462
463 // No need to clean up here. We aren't filling
464 // in a null slot.
465 return value;
466 }
467
468 // If this slot is still empty...
469 if (table[index] == null) {
470 table[index] = key.reference;
471 table[index + 1] = value;
472 size++;
473
474 cleanUp();
475 return value;
476 }
477 }
478
479 // The table changed during initialValue().
480 put(key, value);
481 return value;
482 }
483
484 if (firstTombstone == -1 && reference == TOMBSTONE) {
485 // Keep track of this tombstone so we can overwrite it.
486 firstTombstone = index;
487 }
488 }
489 }
490
491 /**
492 * Removes entry for the given ThreadLocal.
493 */
494 void remove(ThreadLocal<?> key) {
495 cleanUp();
496
497 for (int index = key.hash & mask;; index = next(index)) {
498 Object reference = table[index];
499
500 if (reference == key.reference) {
501 // Success!
502 table[index] = TOMBSTONE;
503 table[index + 1] = null;
504 tombstones++;
505 size--;
506 return;
507 }
508
509 if (reference == null) {
510 // No entry found.
511 return;
512 }
513 }
514 }
515
516 /**
517 * Gets the next index. If we're at the end of the table, we wrap back
518 * around to 0.
519 */
520 private int next(int index) {
521 return (index + 2) & mask;
522 }
523 }
524 }
Save This Page