1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/emul/compact/src/main/java/java/lang/ThreadLocal.java Thu Sep 12 12:19:53 2013 +0200
1.3 @@ -0,0 +1,684 @@
1.4 +/*
1.5 + * Copyright (c) 1997, 2007, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation. Oracle designates this
1.11 + * particular file as subject to the "Classpath" exception as provided
1.12 + * by Oracle in the LICENSE file that accompanied this code.
1.13 + *
1.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.17 + * version 2 for more details (a copy is included in the LICENSE file that
1.18 + * accompanied this code).
1.19 + *
1.20 + * You should have received a copy of the GNU General Public License version
1.21 + * 2 along with this work; if not, write to the Free Software Foundation,
1.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.23 + *
1.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.25 + * or visit www.oracle.com if you need additional information or have any
1.26 + * questions.
1.27 + */
1.28 +
1.29 +package java.lang;
1.30 +import java.lang.ref.*;
1.31 +import java.util.concurrent.atomic.AtomicInteger;
1.32 +
1.33 +/**
1.34 + * This class provides thread-local variables. These variables differ from
1.35 + * their normal counterparts in that each thread that accesses one (via its
1.36 + * <tt>get</tt> or <tt>set</tt> method) has its own, independently initialized
1.37 + * copy of the variable. <tt>ThreadLocal</tt> instances are typically private
1.38 + * static fields in classes that wish to associate state with a thread (e.g.,
1.39 + * a user ID or Transaction ID).
1.40 + *
1.41 + * <p>For example, the class below generates unique identifiers local to each
1.42 + * thread.
1.43 + * A thread's id is assigned the first time it invokes <tt>ThreadId.get()</tt>
1.44 + * and remains unchanged on subsequent calls.
1.45 + * <pre>
1.46 + * import java.util.concurrent.atomic.AtomicInteger;
1.47 + *
1.48 + * public class ThreadId {
1.49 + * // Atomic integer containing the next thread ID to be assigned
1.50 + * private static final AtomicInteger nextId = new AtomicInteger(0);
1.51 + *
1.52 + * // Thread local variable containing each thread's ID
1.53 + * private static final ThreadLocal<Integer> threadId =
1.54 + * new ThreadLocal<Integer>() {
1.55 + * @Override protected Integer initialValue() {
1.56 + * return nextId.getAndIncrement();
1.57 + * }
1.58 + * };
1.59 + *
1.60 + * // Returns the current thread's unique ID, assigning it if necessary
1.61 + * public static int get() {
1.62 + * return threadId.get();
1.63 + * }
1.64 + * }
1.65 + * </pre>
1.66 + * <p>Each thread holds an implicit reference to its copy of a thread-local
1.67 + * variable as long as the thread is alive and the <tt>ThreadLocal</tt>
1.68 + * instance is accessible; after a thread goes away, all of its copies of
1.69 + * thread-local instances are subject to garbage collection (unless other
1.70 + * references to these copies exist).
1.71 + *
1.72 + * @author Josh Bloch and Doug Lea
1.73 + * @since 1.2
1.74 + */
1.75 +public class ThreadLocal<T> {
1.76 + /**
1.77 + * ThreadLocals rely on per-thread linear-probe hash maps attached
1.78 + * to each thread (Thread.threadLocals and
1.79 + * inheritableThreadLocals). The ThreadLocal objects act as keys,
1.80 + * searched via threadLocalHashCode. This is a custom hash code
1.81 + * (useful only within ThreadLocalMaps) that eliminates collisions
1.82 + * in the common case where consecutively constructed ThreadLocals
1.83 + * are used by the same threads, while remaining well-behaved in
1.84 + * less common cases.
1.85 + */
1.86 + private final int threadLocalHashCode = nextHashCode();
1.87 +
1.88 + /**
1.89 + * The next hash code to be given out. Updated atomically. Starts at
1.90 + * zero.
1.91 + */
1.92 + private static AtomicInteger nextHashCode =
1.93 + new AtomicInteger();
1.94 +
1.95 + /**
1.96 + * The difference between successively generated hash codes - turns
1.97 + * implicit sequential thread-local IDs into near-optimally spread
1.98 + * multiplicative hash values for power-of-two-sized tables.
1.99 + */
1.100 + private static final int HASH_INCREMENT = 0x61c88647;
1.101 +
1.102 + /**
1.103 + * Returns the next hash code.
1.104 + */
1.105 + private static int nextHashCode() {
1.106 + return nextHashCode.getAndAdd(HASH_INCREMENT);
1.107 + }
1.108 +
1.109 + /**
1.110 + * Returns the current thread's "initial value" for this
1.111 + * thread-local variable. This method will be invoked the first
1.112 + * time a thread accesses the variable with the {@link #get}
1.113 + * method, unless the thread previously invoked the {@link #set}
1.114 + * method, in which case the <tt>initialValue</tt> method will not
1.115 + * be invoked for the thread. Normally, this method is invoked at
1.116 + * most once per thread, but it may be invoked again in case of
1.117 + * subsequent invocations of {@link #remove} followed by {@link #get}.
1.118 + *
1.119 + * <p>This implementation simply returns <tt>null</tt>; if the
1.120 + * programmer desires thread-local variables to have an initial
1.121 + * value other than <tt>null</tt>, <tt>ThreadLocal</tt> must be
1.122 + * subclassed, and this method overridden. Typically, an
1.123 + * anonymous inner class will be used.
1.124 + *
1.125 + * @return the initial value for this thread-local
1.126 + */
1.127 + protected T initialValue() {
1.128 + return null;
1.129 + }
1.130 +
1.131 + /**
1.132 + * Creates a thread local variable.
1.133 + */
1.134 + public ThreadLocal() {
1.135 + }
1.136 +
1.137 + /**
1.138 + * Returns the value in the current thread's copy of this
1.139 + * thread-local variable. If the variable has no value for the
1.140 + * current thread, it is first initialized to the value returned
1.141 + * by an invocation of the {@link #initialValue} method.
1.142 + *
1.143 + * @return the current thread's value of this thread-local
1.144 + */
1.145 + public T get() {
1.146 + Thread t = Thread.currentThread();
1.147 + ThreadLocalMap map = getMap(t);
1.148 + if (map != null) {
1.149 + ThreadLocalMap.Entry e = map.getEntry(this);
1.150 + if (e != null)
1.151 + return (T)e.value;
1.152 + }
1.153 + return setInitialValue();
1.154 + }
1.155 +
1.156 + /**
1.157 + * Variant of set() to establish initialValue. Used instead
1.158 + * of set() in case user has overridden the set() method.
1.159 + *
1.160 + * @return the initial value
1.161 + */
1.162 + private T setInitialValue() {
1.163 + T value = initialValue();
1.164 + Thread t = Thread.currentThread();
1.165 + ThreadLocalMap map = getMap(t);
1.166 + if (map != null)
1.167 + map.set(this, value);
1.168 + else
1.169 + createMap(t, value);
1.170 + return value;
1.171 + }
1.172 +
1.173 + /**
1.174 + * Sets the current thread's copy of this thread-local variable
1.175 + * to the specified value. Most subclasses will have no need to
1.176 + * override this method, relying solely on the {@link #initialValue}
1.177 + * method to set the values of thread-locals.
1.178 + *
1.179 + * @param value the value to be stored in the current thread's copy of
1.180 + * this thread-local.
1.181 + */
1.182 + public void set(T value) {
1.183 + Thread t = Thread.currentThread();
1.184 + ThreadLocalMap map = getMap(t);
1.185 + if (map != null)
1.186 + map.set(this, value);
1.187 + else
1.188 + createMap(t, value);
1.189 + }
1.190 +
1.191 + /**
1.192 + * Removes the current thread's value for this thread-local
1.193 + * variable. If this thread-local variable is subsequently
1.194 + * {@linkplain #get read} by the current thread, its value will be
1.195 + * reinitialized by invoking its {@link #initialValue} method,
1.196 + * unless its value is {@linkplain #set set} by the current thread
1.197 + * in the interim. This may result in multiple invocations of the
1.198 + * <tt>initialValue</tt> method in the current thread.
1.199 + *
1.200 + * @since 1.5
1.201 + */
1.202 + public void remove() {
1.203 + ThreadLocalMap m = getMap(Thread.currentThread());
1.204 + if (m != null)
1.205 + m.remove(this);
1.206 + }
1.207 +
1.208 + /**
1.209 + * Get the map associated with a ThreadLocal. Overridden in
1.210 + * InheritableThreadLocal.
1.211 + *
1.212 + * @param t the current thread
1.213 + * @return the map
1.214 + */
1.215 + ThreadLocalMap getMap(Thread t) {
1.216 + return t.threadLocals;
1.217 + }
1.218 +
1.219 + /**
1.220 + * Create the map associated with a ThreadLocal. Overridden in
1.221 + * InheritableThreadLocal.
1.222 + *
1.223 + * @param t the current thread
1.224 + * @param firstValue value for the initial entry of the map
1.225 + * @param map the map to store.
1.226 + */
1.227 + void createMap(Thread t, T firstValue) {
1.228 + t.threadLocals = new ThreadLocalMap(this, firstValue);
1.229 + }
1.230 +
1.231 + /**
1.232 + * Factory method to create map of inherited thread locals.
1.233 + * Designed to be called only from Thread constructor.
1.234 + *
1.235 + * @param parentMap the map associated with parent thread
1.236 + * @return a map containing the parent's inheritable bindings
1.237 + */
1.238 + static ThreadLocalMap createInheritedMap(ThreadLocalMap parentMap) {
1.239 + return new ThreadLocalMap(parentMap);
1.240 + }
1.241 +
1.242 + /**
1.243 + * Method childValue is visibly defined in subclass
1.244 + * InheritableThreadLocal, but is internally defined here for the
1.245 + * sake of providing createInheritedMap factory method without
1.246 + * needing to subclass the map class in InheritableThreadLocal.
1.247 + * This technique is preferable to the alternative of embedding
1.248 + * instanceof tests in methods.
1.249 + */
1.250 + T childValue(T parentValue) {
1.251 + throw new UnsupportedOperationException();
1.252 + }
1.253 +
1.254 + /**
1.255 + * ThreadLocalMap is a customized hash map suitable only for
1.256 + * maintaining thread local values. No operations are exported
1.257 + * outside of the ThreadLocal class. The class is package private to
1.258 + * allow declaration of fields in class Thread. To help deal with
1.259 + * very large and long-lived usages, the hash table entries use
1.260 + * WeakReferences for keys. However, since reference queues are not
1.261 + * used, stale entries are guaranteed to be removed only when
1.262 + * the table starts running out of space.
1.263 + */
1.264 + static class ThreadLocalMap {
1.265 +
1.266 + /**
1.267 + * The entries in this hash map extend WeakReference, using
1.268 + * its main ref field as the key (which is always a
1.269 + * ThreadLocal object). Note that null keys (i.e. entry.get()
1.270 + * == null) mean that the key is no longer referenced, so the
1.271 + * entry can be expunged from table. Such entries are referred to
1.272 + * as "stale entries" in the code that follows.
1.273 + */
1.274 + static class Entry extends WeakReference<ThreadLocal> {
1.275 + /** The value associated with this ThreadLocal. */
1.276 + Object value;
1.277 +
1.278 + Entry(ThreadLocal k, Object v) {
1.279 + super(k);
1.280 + value = v;
1.281 + }
1.282 + }
1.283 +
1.284 + /**
1.285 + * The initial capacity -- MUST be a power of two.
1.286 + */
1.287 + private static final int INITIAL_CAPACITY = 16;
1.288 +
1.289 + /**
1.290 + * The table, resized as necessary.
1.291 + * table.length MUST always be a power of two.
1.292 + */
1.293 + private Entry[] table;
1.294 +
1.295 + /**
1.296 + * The number of entries in the table.
1.297 + */
1.298 + private int size = 0;
1.299 +
1.300 + /**
1.301 + * The next size value at which to resize.
1.302 + */
1.303 + private int threshold; // Default to 0
1.304 +
1.305 + /**
1.306 + * Set the resize threshold to maintain at worst a 2/3 load factor.
1.307 + */
1.308 + private void setThreshold(int len) {
1.309 + threshold = len * 2 / 3;
1.310 + }
1.311 +
1.312 + /**
1.313 + * Increment i modulo len.
1.314 + */
1.315 + private static int nextIndex(int i, int len) {
1.316 + return ((i + 1 < len) ? i + 1 : 0);
1.317 + }
1.318 +
1.319 + /**
1.320 + * Decrement i modulo len.
1.321 + */
1.322 + private static int prevIndex(int i, int len) {
1.323 + return ((i - 1 >= 0) ? i - 1 : len - 1);
1.324 + }
1.325 +
1.326 + /**
1.327 + * Construct a new map initially containing (firstKey, firstValue).
1.328 + * ThreadLocalMaps are constructed lazily, so we only create
1.329 + * one when we have at least one entry to put in it.
1.330 + */
1.331 + ThreadLocalMap(ThreadLocal firstKey, Object firstValue) {
1.332 + table = new Entry[INITIAL_CAPACITY];
1.333 + int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
1.334 + table[i] = new Entry(firstKey, firstValue);
1.335 + size = 1;
1.336 + setThreshold(INITIAL_CAPACITY);
1.337 + }
1.338 +
1.339 + /**
1.340 + * Construct a new map including all Inheritable ThreadLocals
1.341 + * from given parent map. Called only by createInheritedMap.
1.342 + *
1.343 + * @param parentMap the map associated with parent thread.
1.344 + */
1.345 + private ThreadLocalMap(ThreadLocalMap parentMap) {
1.346 + Entry[] parentTable = parentMap.table;
1.347 + int len = parentTable.length;
1.348 + setThreshold(len);
1.349 + table = new Entry[len];
1.350 +
1.351 + for (int j = 0; j < len; j++) {
1.352 + Entry e = parentTable[j];
1.353 + if (e != null) {
1.354 + ThreadLocal key = e.get();
1.355 + if (key != null) {
1.356 + Object value = key.childValue(e.value);
1.357 + Entry c = new Entry(key, value);
1.358 + int h = key.threadLocalHashCode & (len - 1);
1.359 + while (table[h] != null)
1.360 + h = nextIndex(h, len);
1.361 + table[h] = c;
1.362 + size++;
1.363 + }
1.364 + }
1.365 + }
1.366 + }
1.367 +
1.368 + /**
1.369 + * Get the entry associated with key. This method
1.370 + * itself handles only the fast path: a direct hit of existing
1.371 + * key. It otherwise relays to getEntryAfterMiss. This is
1.372 + * designed to maximize performance for direct hits, in part
1.373 + * by making this method readily inlinable.
1.374 + *
1.375 + * @param key the thread local object
1.376 + * @return the entry associated with key, or null if no such
1.377 + */
1.378 + private Entry getEntry(ThreadLocal key) {
1.379 + int i = key.threadLocalHashCode & (table.length - 1);
1.380 + Entry e = table[i];
1.381 + if (e != null && e.get() == key)
1.382 + return e;
1.383 + else
1.384 + return getEntryAfterMiss(key, i, e);
1.385 + }
1.386 +
1.387 + /**
1.388 + * Version of getEntry method for use when key is not found in
1.389 + * its direct hash slot.
1.390 + *
1.391 + * @param key the thread local object
1.392 + * @param i the table index for key's hash code
1.393 + * @param e the entry at table[i]
1.394 + * @return the entry associated with key, or null if no such
1.395 + */
1.396 + private Entry getEntryAfterMiss(ThreadLocal key, int i, Entry e) {
1.397 + Entry[] tab = table;
1.398 + int len = tab.length;
1.399 +
1.400 + while (e != null) {
1.401 + ThreadLocal k = e.get();
1.402 + if (k == key)
1.403 + return e;
1.404 + if (k == null)
1.405 + expungeStaleEntry(i);
1.406 + else
1.407 + i = nextIndex(i, len);
1.408 + e = tab[i];
1.409 + }
1.410 + return null;
1.411 + }
1.412 +
1.413 + /**
1.414 + * Set the value associated with key.
1.415 + *
1.416 + * @param key the thread local object
1.417 + * @param value the value to be set
1.418 + */
1.419 + private void set(ThreadLocal key, Object value) {
1.420 +
1.421 + // We don't use a fast path as with get() because it is at
1.422 + // least as common to use set() to create new entries as
1.423 + // it is to replace existing ones, in which case, a fast
1.424 + // path would fail more often than not.
1.425 +
1.426 + Entry[] tab = table;
1.427 + int len = tab.length;
1.428 + int i = key.threadLocalHashCode & (len-1);
1.429 +
1.430 + for (Entry e = tab[i];
1.431 + e != null;
1.432 + e = tab[i = nextIndex(i, len)]) {
1.433 + ThreadLocal k = e.get();
1.434 +
1.435 + if (k == key) {
1.436 + e.value = value;
1.437 + return;
1.438 + }
1.439 +
1.440 + if (k == null) {
1.441 + replaceStaleEntry(key, value, i);
1.442 + return;
1.443 + }
1.444 + }
1.445 +
1.446 + tab[i] = new Entry(key, value);
1.447 + int sz = ++size;
1.448 + if (!cleanSomeSlots(i, sz) && sz >= threshold)
1.449 + rehash();
1.450 + }
1.451 +
1.452 + /**
1.453 + * Remove the entry for key.
1.454 + */
1.455 + private void remove(ThreadLocal key) {
1.456 + Entry[] tab = table;
1.457 + int len = tab.length;
1.458 + int i = key.threadLocalHashCode & (len-1);
1.459 + for (Entry e = tab[i];
1.460 + e != null;
1.461 + e = tab[i = nextIndex(i, len)]) {
1.462 + if (e.get() == key) {
1.463 + e.clear();
1.464 + expungeStaleEntry(i);
1.465 + return;
1.466 + }
1.467 + }
1.468 + }
1.469 +
1.470 + /**
1.471 + * Replace a stale entry encountered during a set operation
1.472 + * with an entry for the specified key. The value passed in
1.473 + * the value parameter is stored in the entry, whether or not
1.474 + * an entry already exists for the specified key.
1.475 + *
1.476 + * As a side effect, this method expunges all stale entries in the
1.477 + * "run" containing the stale entry. (A run is a sequence of entries
1.478 + * between two null slots.)
1.479 + *
1.480 + * @param key the key
1.481 + * @param value the value to be associated with key
1.482 + * @param staleSlot index of the first stale entry encountered while
1.483 + * searching for key.
1.484 + */
1.485 + private void replaceStaleEntry(ThreadLocal key, Object value,
1.486 + int staleSlot) {
1.487 + Entry[] tab = table;
1.488 + int len = tab.length;
1.489 + Entry e;
1.490 +
1.491 + // Back up to check for prior stale entry in current run.
1.492 + // We clean out whole runs at a time to avoid continual
1.493 + // incremental rehashing due to garbage collector freeing
1.494 + // up refs in bunches (i.e., whenever the collector runs).
1.495 + int slotToExpunge = staleSlot;
1.496 + for (int i = prevIndex(staleSlot, len);
1.497 + (e = tab[i]) != null;
1.498 + i = prevIndex(i, len))
1.499 + if (e.get() == null)
1.500 + slotToExpunge = i;
1.501 +
1.502 + // Find either the key or trailing null slot of run, whichever
1.503 + // occurs first
1.504 + for (int i = nextIndex(staleSlot, len);
1.505 + (e = tab[i]) != null;
1.506 + i = nextIndex(i, len)) {
1.507 + ThreadLocal k = e.get();
1.508 +
1.509 + // If we find key, then we need to swap it
1.510 + // with the stale entry to maintain hash table order.
1.511 + // The newly stale slot, or any other stale slot
1.512 + // encountered above it, can then be sent to expungeStaleEntry
1.513 + // to remove or rehash all of the other entries in run.
1.514 + if (k == key) {
1.515 + e.value = value;
1.516 +
1.517 + tab[i] = tab[staleSlot];
1.518 + tab[staleSlot] = e;
1.519 +
1.520 + // Start expunge at preceding stale entry if it exists
1.521 + if (slotToExpunge == staleSlot)
1.522 + slotToExpunge = i;
1.523 + cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
1.524 + return;
1.525 + }
1.526 +
1.527 + // If we didn't find stale entry on backward scan, the
1.528 + // first stale entry seen while scanning for key is the
1.529 + // first still present in the run.
1.530 + if (k == null && slotToExpunge == staleSlot)
1.531 + slotToExpunge = i;
1.532 + }
1.533 +
1.534 + // If key not found, put new entry in stale slot
1.535 + tab[staleSlot].value = null;
1.536 + tab[staleSlot] = new Entry(key, value);
1.537 +
1.538 + // If there are any other stale entries in run, expunge them
1.539 + if (slotToExpunge != staleSlot)
1.540 + cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
1.541 + }
1.542 +
1.543 + /**
1.544 + * Expunge a stale entry by rehashing any possibly colliding entries
1.545 + * lying between staleSlot and the next null slot. This also expunges
1.546 + * any other stale entries encountered before the trailing null. See
1.547 + * Knuth, Section 6.4
1.548 + *
1.549 + * @param staleSlot index of slot known to have null key
1.550 + * @return the index of the next null slot after staleSlot
1.551 + * (all between staleSlot and this slot will have been checked
1.552 + * for expunging).
1.553 + */
1.554 + private int expungeStaleEntry(int staleSlot) {
1.555 + Entry[] tab = table;
1.556 + int len = tab.length;
1.557 +
1.558 + // expunge entry at staleSlot
1.559 + tab[staleSlot].value = null;
1.560 + tab[staleSlot] = null;
1.561 + size--;
1.562 +
1.563 + // Rehash until we encounter null
1.564 + Entry e;
1.565 + int i;
1.566 + for (i = nextIndex(staleSlot, len);
1.567 + (e = tab[i]) != null;
1.568 + i = nextIndex(i, len)) {
1.569 + ThreadLocal k = e.get();
1.570 + if (k == null) {
1.571 + e.value = null;
1.572 + tab[i] = null;
1.573 + size--;
1.574 + } else {
1.575 + int h = k.threadLocalHashCode & (len - 1);
1.576 + if (h != i) {
1.577 + tab[i] = null;
1.578 +
1.579 + // Unlike Knuth 6.4 Algorithm R, we must scan until
1.580 + // null because multiple entries could have been stale.
1.581 + while (tab[h] != null)
1.582 + h = nextIndex(h, len);
1.583 + tab[h] = e;
1.584 + }
1.585 + }
1.586 + }
1.587 + return i;
1.588 + }
1.589 +
1.590 + /**
1.591 + * Heuristically scan some cells looking for stale entries.
1.592 + * This is invoked when either a new element is added, or
1.593 + * another stale one has been expunged. It performs a
1.594 + * logarithmic number of scans, as a balance between no
1.595 + * scanning (fast but retains garbage) and a number of scans
1.596 + * proportional to number of elements, that would find all
1.597 + * garbage but would cause some insertions to take O(n) time.
1.598 + *
1.599 + * @param i a position known NOT to hold a stale entry. The
1.600 + * scan starts at the element after i.
1.601 + *
1.602 + * @param n scan control: <tt>log2(n)</tt> cells are scanned,
1.603 + * unless a stale entry is found, in which case
1.604 + * <tt>log2(table.length)-1</tt> additional cells are scanned.
1.605 + * When called from insertions, this parameter is the number
1.606 + * of elements, but when from replaceStaleEntry, it is the
1.607 + * table length. (Note: all this could be changed to be either
1.608 + * more or less aggressive by weighting n instead of just
1.609 + * using straight log n. But this version is simple, fast, and
1.610 + * seems to work well.)
1.611 + *
1.612 + * @return true if any stale entries have been removed.
1.613 + */
1.614 + private boolean cleanSomeSlots(int i, int n) {
1.615 + boolean removed = false;
1.616 + Entry[] tab = table;
1.617 + int len = tab.length;
1.618 + do {
1.619 + i = nextIndex(i, len);
1.620 + Entry e = tab[i];
1.621 + if (e != null && e.get() == null) {
1.622 + n = len;
1.623 + removed = true;
1.624 + i = expungeStaleEntry(i);
1.625 + }
1.626 + } while ( (n >>>= 1) != 0);
1.627 + return removed;
1.628 + }
1.629 +
1.630 + /**
1.631 + * Re-pack and/or re-size the table. First scan the entire
1.632 + * table removing stale entries. If this doesn't sufficiently
1.633 + * shrink the size of the table, double the table size.
1.634 + */
1.635 + private void rehash() {
1.636 + expungeStaleEntries();
1.637 +
1.638 + // Use lower threshold for doubling to avoid hysteresis
1.639 + if (size >= threshold - threshold / 4)
1.640 + resize();
1.641 + }
1.642 +
1.643 + /**
1.644 + * Double the capacity of the table.
1.645 + */
1.646 + private void resize() {
1.647 + Entry[] oldTab = table;
1.648 + int oldLen = oldTab.length;
1.649 + int newLen = oldLen * 2;
1.650 + Entry[] newTab = new Entry[newLen];
1.651 + int count = 0;
1.652 +
1.653 + for (int j = 0; j < oldLen; ++j) {
1.654 + Entry e = oldTab[j];
1.655 + if (e != null) {
1.656 + ThreadLocal k = e.get();
1.657 + if (k == null) {
1.658 + e.value = null; // Help the GC
1.659 + } else {
1.660 + int h = k.threadLocalHashCode & (newLen - 1);
1.661 + while (newTab[h] != null)
1.662 + h = nextIndex(h, newLen);
1.663 + newTab[h] = e;
1.664 + count++;
1.665 + }
1.666 + }
1.667 + }
1.668 +
1.669 + setThreshold(newLen);
1.670 + size = count;
1.671 + table = newTab;
1.672 + }
1.673 +
1.674 + /**
1.675 + * Expunge all stale entries in the table.
1.676 + */
1.677 + private void expungeStaleEntries() {
1.678 + Entry[] tab = table;
1.679 + int len = tab.length;
1.680 + for (int j = 0; j < len; j++) {
1.681 + Entry e = tab[j];
1.682 + if (e != null && e.get() == null)
1.683 + expungeStaleEntry(j);
1.684 + }
1.685 + }
1.686 + }
1.687 +}