151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski/* 24e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. 351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This code is free software; you can redistribute it and/or modify it 651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * under the terms of the GNU General Public License version 2 only, as 751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * published by the Free Software Foundation. Oracle designates this 851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * particular file as subject to the "Classpath" exception as provided 951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * by Oracle in the LICENSE file that accompanied this code. 1051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 1151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This code is distributed in the hope that it will be useful, but WITHOUT 1251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * version 2 for more details (a copy is included in the LICENSE file that 1551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * accompanied this code). 1651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 1751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * You should have received a copy of the GNU General Public License version 1851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 2 along with this work; if not, write to the Free Software Foundation, 1951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 2151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * or visit www.oracle.com if you need additional information or have any 2351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * questions. 2451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 2551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 2651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskipackage java.lang; 2751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskiimport java.lang.ref.*; 284e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniakimport java.util.Objects; 2951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskiimport java.util.concurrent.atomic.AtomicInteger; 304e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniakimport java.util.function.Supplier; 3151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 3251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski/** 3351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This class provides thread-local variables. These variables differ from 3451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * their normal counterparts in that each thread that accesses one (via its 354e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * {@code get} or {@code set} method) has its own, independently initialized 364e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * copy of the variable. {@code ThreadLocal} instances are typically private 3751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * static fields in classes that wish to associate state with a thread (e.g., 3851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * a user ID or Transaction ID). 3951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 4051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>For example, the class below generates unique identifiers local to each 4151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * thread. 424e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * A thread's id is assigned the first time it invokes {@code ThreadId.get()} 4351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * and remains unchanged on subsequent calls. 4451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <pre> 4551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * import java.util.concurrent.atomic.AtomicInteger; 4651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 4751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * public class ThreadId { 4851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * // Atomic integer containing the next thread ID to be assigned 4951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * private static final AtomicInteger nextId = new AtomicInteger(0); 5051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 5151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * // Thread local variable containing each thread's ID 524e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * private static final ThreadLocal<Integer> threadId = 534e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * new ThreadLocal<Integer>() { 5451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @Override protected Integer initialValue() { 5551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * return nextId.getAndIncrement(); 5651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * } 5751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * }; 5851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 5951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * // Returns the current thread's unique ID, assigning it if necessary 6051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * public static int get() { 6151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * return threadId.get(); 6251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * } 6351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * } 6451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </pre> 6551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>Each thread holds an implicit reference to its copy of a thread-local 664e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * variable as long as the thread is alive and the {@code ThreadLocal} 6751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * instance is accessible; after a thread goes away, all of its copies of 6851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * thread-local instances are subject to garbage collection (unless other 6951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * references to these copies exist). 7051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 7151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @author Josh Bloch and Doug Lea 7251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @since 1.2 7351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 7451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskipublic class ThreadLocal<T> { 7551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 7651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ThreadLocals rely on per-thread linear-probe hash maps attached 7751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * to each thread (Thread.threadLocals and 7851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * inheritableThreadLocals). The ThreadLocal objects act as keys, 7951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * searched via threadLocalHashCode. This is a custom hash code 8051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (useful only within ThreadLocalMaps) that eliminates collisions 8151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * in the common case where consecutively constructed ThreadLocals 8251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * are used by the same threads, while remaining well-behaved in 8351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * less common cases. 8451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 8551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private final int threadLocalHashCode = nextHashCode(); 8651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 8751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 8851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The next hash code to be given out. Updated atomically. Starts at 8951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * zero. 9051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 9151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static AtomicInteger nextHashCode = 9251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski new AtomicInteger(); 9351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 9451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 9551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The difference between successively generated hash codes - turns 9651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * implicit sequential thread-local IDs into near-optimally spread 9751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * multiplicative hash values for power-of-two-sized tables. 9851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 9951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final int HASH_INCREMENT = 0x61c88647; 10051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 10151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 10251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns the next hash code. 10351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 10451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static int nextHashCode() { 10551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return nextHashCode.getAndAdd(HASH_INCREMENT); 10651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 10751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 10851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 10951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns the current thread's "initial value" for this 11051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * thread-local variable. This method will be invoked the first 11151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * time a thread accesses the variable with the {@link #get} 11251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * method, unless the thread previously invoked the {@link #set} 1134e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * method, in which case the {@code initialValue} method will not 11451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * be invoked for the thread. Normally, this method is invoked at 11551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * most once per thread, but it may be invoked again in case of 11651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * subsequent invocations of {@link #remove} followed by {@link #get}. 11751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 1184e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * <p>This implementation simply returns {@code null}; if the 11951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * programmer desires thread-local variables to have an initial 1204e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * value other than {@code null}, {@code ThreadLocal} must be 12151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * subclassed, and this method overridden. Typically, an 12251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * anonymous inner class will be used. 12351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 12451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the initial value for this thread-local 12551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 12651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski protected T initialValue() { 12751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return null; 12851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 12951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 13051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 1314e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * Creates a thread local variable. The initial value of the variable is 1324e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * determined by invoking the {@code get} method on the {@code Supplier}. 1334e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * 1344e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * @param <S> the type of the thread local's value 1354e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * @param supplier the supplier to be used to determine the initial value 1364e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * @return a new thread local variable 1374e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * @throws NullPointerException if the specified supplier is null 1384e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * @since 1.8 1394e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak */ 1404e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak public static <S> ThreadLocal<S> withInitial(Supplier<? extends S> supplier) { 1414e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak return new SuppliedThreadLocal<>(supplier); 1424e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak } 1434e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak 1444e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak /** 14551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Creates a thread local variable. 1464e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * @see #withInitial(java.util.function.Supplier) 14751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 14851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public ThreadLocal() { 14951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 15051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 15151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 15251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns the value in the current thread's copy of this 15351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * thread-local variable. If the variable has no value for the 15451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * current thread, it is first initialized to the value returned 15551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * by an invocation of the {@link #initialValue} method. 15651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 15751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the current thread's value of this thread-local 15851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 15951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public T get() { 16051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Thread t = Thread.currentThread(); 16151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocalMap map = getMap(t); 16251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (map != null) { 16351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocalMap.Entry e = map.getEntry(this); 1644e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak if (e != null) { 1654e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak @SuppressWarnings("unchecked") 1664e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak T result = (T)e.value; 1674e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak return result; 1684e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak } 16951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 17051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return setInitialValue(); 17151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 17251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 17351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 17451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Variant of set() to establish initialValue. Used instead 17551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of set() in case user has overridden the set() method. 17651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 17751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the initial value 17851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 17951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private T setInitialValue() { 18051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski T value = initialValue(); 18151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Thread t = Thread.currentThread(); 18251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocalMap map = getMap(t); 18351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (map != null) 18451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski map.set(this, value); 18551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 18651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski createMap(t, value); 18751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return value; 18851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 18951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 19051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 19151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Sets the current thread's copy of this thread-local variable 19251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * to the specified value. Most subclasses will have no need to 19351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * override this method, relying solely on the {@link #initialValue} 19451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * method to set the values of thread-locals. 19551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 19651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param value the value to be stored in the current thread's copy of 19751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * this thread-local. 19851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 19951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void set(T value) { 20051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Thread t = Thread.currentThread(); 20151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocalMap map = getMap(t); 20251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (map != null) 20351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski map.set(this, value); 20451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 20551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski createMap(t, value); 20651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 20751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 20851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 20951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Removes the current thread's value for this thread-local 21051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * variable. If this thread-local variable is subsequently 21151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@linkplain #get read} by the current thread, its value will be 21251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * reinitialized by invoking its {@link #initialValue} method, 21351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * unless its value is {@linkplain #set set} by the current thread 21451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * in the interim. This may result in multiple invocations of the 2154e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * {@code initialValue} method in the current thread. 21651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 21751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @since 1.5 21851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 21951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void remove() { 22051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocalMap m = getMap(Thread.currentThread()); 22151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (m != null) 22251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski m.remove(this); 22351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 22451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 22551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 22651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Get the map associated with a ThreadLocal. Overridden in 22751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * InheritableThreadLocal. 22851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 22951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param t the current thread 23051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the map 23151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 23251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocalMap getMap(Thread t) { 23351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return t.threadLocals; 23451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 23551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 23651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 23751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Create the map associated with a ThreadLocal. Overridden in 23851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * InheritableThreadLocal. 23951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 24051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param t the current thread 24151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param firstValue value for the initial entry of the map 24251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 24351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski void createMap(Thread t, T firstValue) { 24451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski t.threadLocals = new ThreadLocalMap(this, firstValue); 24551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 24651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 24751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 24851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Factory method to create map of inherited thread locals. 24951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Designed to be called only from Thread constructor. 25051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 25151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param parentMap the map associated with parent thread 25251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return a map containing the parent's inheritable bindings 25351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 25451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski static ThreadLocalMap createInheritedMap(ThreadLocalMap parentMap) { 25551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return new ThreadLocalMap(parentMap); 25651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 25751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 25851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 25951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Method childValue is visibly defined in subclass 26051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * InheritableThreadLocal, but is internally defined here for the 26151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * sake of providing createInheritedMap factory method without 26251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * needing to subclass the map class in InheritableThreadLocal. 26351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This technique is preferable to the alternative of embedding 26451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * instanceof tests in methods. 26551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 26651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski T childValue(T parentValue) { 26751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new UnsupportedOperationException(); 26851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 26951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 27051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 2714e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * An extension of ThreadLocal that obtains its initial value from 2724e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * the specified {@code Supplier}. 2734e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak */ 2744e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak static final class SuppliedThreadLocal<T> extends ThreadLocal<T> { 2754e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak 2764e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak private final Supplier<? extends T> supplier; 2774e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak 2784e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak SuppliedThreadLocal(Supplier<? extends T> supplier) { 2794e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak this.supplier = Objects.requireNonNull(supplier); 2804e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak } 2814e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak 2824e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak @Override 2834e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak protected T initialValue() { 2844e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak return supplier.get(); 2854e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak } 2864e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak } 2874e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak 2884e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak /** 28951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ThreadLocalMap is a customized hash map suitable only for 29051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * maintaining thread local values. No operations are exported 29151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * outside of the ThreadLocal class. The class is package private to 29251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * allow declaration of fields in class Thread. To help deal with 29351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * very large and long-lived usages, the hash table entries use 29451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * WeakReferences for keys. However, since reference queues are not 29551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * used, stale entries are guaranteed to be removed only when 29651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the table starts running out of space. 29751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 29851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski static class ThreadLocalMap { 29951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 30051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 30151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The entries in this hash map extend WeakReference, using 30251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * its main ref field as the key (which is always a 30351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ThreadLocal object). Note that null keys (i.e. entry.get() 30451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * == null) mean that the key is no longer referenced, so the 30551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * entry can be expunged from table. Such entries are referred to 30651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * as "stale entries" in the code that follows. 30751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 3084e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak static class Entry extends WeakReference<ThreadLocal<?>> { 30951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** The value associated with this ThreadLocal. */ 31051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Object value; 31151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 3124e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak Entry(ThreadLocal<?> k, Object v) { 31351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski super(k); 31451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski value = v; 31551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 31651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 31751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 31851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 31951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The initial capacity -- MUST be a power of two. 32051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 32151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final int INITIAL_CAPACITY = 16; 32251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 32351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 32451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The table, resized as necessary. 32551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * table.length MUST always be a power of two. 32651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 32751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private Entry[] table; 32851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 32951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 33051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The number of entries in the table. 33151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 33251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private int size = 0; 33351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 33451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 33551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The next size value at which to resize. 33651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 33751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private int threshold; // Default to 0 33851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 33951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 34051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Set the resize threshold to maintain at worst a 2/3 load factor. 34151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 34251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void setThreshold(int len) { 34351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski threshold = len * 2 / 3; 34451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 34551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 34651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 34751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Increment i modulo len. 34851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 34951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static int nextIndex(int i, int len) { 35051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return ((i + 1 < len) ? i + 1 : 0); 35151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 35251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 35351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 35451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Decrement i modulo len. 35551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 35651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static int prevIndex(int i, int len) { 35751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return ((i - 1 >= 0) ? i - 1 : len - 1); 35851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 35951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 36051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 36151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Construct a new map initially containing (firstKey, firstValue). 36251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ThreadLocalMaps are constructed lazily, so we only create 36351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * one when we have at least one entry to put in it. 36451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 3654e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) { 36651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski table = new Entry[INITIAL_CAPACITY]; 36751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1); 36851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski table[i] = new Entry(firstKey, firstValue); 36951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size = 1; 37051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski setThreshold(INITIAL_CAPACITY); 37151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 37251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 37351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 37451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Construct a new map including all Inheritable ThreadLocals 37551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * from given parent map. Called only by createInheritedMap. 37651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 37751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param parentMap the map associated with parent thread. 37851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 37951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private ThreadLocalMap(ThreadLocalMap parentMap) { 38051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] parentTable = parentMap.table; 38151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = parentTable.length; 38251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski setThreshold(len); 38351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski table = new Entry[len]; 38451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 38551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int j = 0; j < len; j++) { 38651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry e = parentTable[j]; 38751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (e != null) { 3884e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak @SuppressWarnings("unchecked") 3894e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak ThreadLocal<Object> key = (ThreadLocal<Object>) e.get(); 39051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (key != null) { 39151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Object value = key.childValue(e.value); 39251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry c = new Entry(key, value); 39351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int h = key.threadLocalHashCode & (len - 1); 39451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (table[h] != null) 39551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski h = nextIndex(h, len); 39651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski table[h] = c; 39751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size++; 39851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 39951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 40051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 40151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 40251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 40351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 40451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Get the entry associated with key. This method 40551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * itself handles only the fast path: a direct hit of existing 40651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * key. It otherwise relays to getEntryAfterMiss. This is 40751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * designed to maximize performance for direct hits, in part 40851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * by making this method readily inlinable. 40951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 41051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param key the thread local object 41151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the entry associated with key, or null if no such 41251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 4134e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak private Entry getEntry(ThreadLocal<?> key) { 41451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int i = key.threadLocalHashCode & (table.length - 1); 41551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry e = table[i]; 41651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (e != null && e.get() == key) 41751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return e; 41851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 41951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return getEntryAfterMiss(key, i, e); 42051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 42151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 42251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 42351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Version of getEntry method for use when key is not found in 42451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * its direct hash slot. 42551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 42651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param key the thread local object 42751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param i the table index for key's hash code 42851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param e the entry at table[i] 42951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the entry associated with key, or null if no such 43051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 4314e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) { 43251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] tab = table; 43351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = tab.length; 43451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 43551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (e != null) { 4364e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak ThreadLocal<?> k = e.get(); 43751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (k == key) 43851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return e; 43951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (k == null) 44051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski expungeStaleEntry(i); 44151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 44251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i = nextIndex(i, len); 44351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e = tab[i]; 44451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 44551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return null; 44651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 44751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 44851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 44951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Set the value associated with key. 45051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 45151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param key the thread local object 45251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param value the value to be set 45351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 4544e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak private void set(ThreadLocal<?> key, Object value) { 45551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 45651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // We don't use a fast path as with get() because it is at 45751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // least as common to use set() to create new entries as 45851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // it is to replace existing ones, in which case, a fast 45951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // path would fail more often than not. 46051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 46151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] tab = table; 46251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = tab.length; 46351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int i = key.threadLocalHashCode & (len-1); 46451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 46551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (Entry e = tab[i]; 46651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e != null; 46751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e = tab[i = nextIndex(i, len)]) { 4684e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak ThreadLocal<?> k = e.get(); 46951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 47051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (k == key) { 47151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e.value = value; 47251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return; 47351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 47451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 47551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (k == null) { 47651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski replaceStaleEntry(key, value, i); 47751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return; 47851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 47951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 48051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 48151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[i] = new Entry(key, value); 48251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int sz = ++size; 48351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (!cleanSomeSlots(i, sz) && sz >= threshold) 48451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski rehash(); 48551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 48651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 48751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 48851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Remove the entry for key. 48951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 4904e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak private void remove(ThreadLocal<?> key) { 49151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] tab = table; 49251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = tab.length; 49351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int i = key.threadLocalHashCode & (len-1); 49451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (Entry e = tab[i]; 49551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e != null; 49651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e = tab[i = nextIndex(i, len)]) { 49751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (e.get() == key) { 49851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e.clear(); 49951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski expungeStaleEntry(i); 50051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return; 50151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 50251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 50351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 50451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 50551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 50651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Replace a stale entry encountered during a set operation 50751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * with an entry for the specified key. The value passed in 50851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the value parameter is stored in the entry, whether or not 50951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * an entry already exists for the specified key. 51051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 51151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * As a side effect, this method expunges all stale entries in the 51251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * "run" containing the stale entry. (A run is a sequence of entries 51351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * between two null slots.) 51451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 51551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param key the key 51651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param value the value to be associated with key 51751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param staleSlot index of the first stale entry encountered while 51851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * searching for key. 51951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 5204e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak private void replaceStaleEntry(ThreadLocal<?> key, Object value, 52151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int staleSlot) { 52251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] tab = table; 52351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = tab.length; 52451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry e; 52551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 52651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Back up to check for prior stale entry in current run. 52751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // We clean out whole runs at a time to avoid continual 52851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // incremental rehashing due to garbage collector freeing 52951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // up refs in bunches (i.e., whenever the collector runs). 53051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int slotToExpunge = staleSlot; 53151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = prevIndex(staleSlot, len); 53251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski (e = tab[i]) != null; 53351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i = prevIndex(i, len)) 53451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (e.get() == null) 53551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski slotToExpunge = i; 53651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 53751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Find either the key or trailing null slot of run, whichever 53851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // occurs first 53951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = nextIndex(staleSlot, len); 54051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski (e = tab[i]) != null; 54151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i = nextIndex(i, len)) { 5424e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak ThreadLocal<?> k = e.get(); 54351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 54451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // If we find key, then we need to swap it 54551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // with the stale entry to maintain hash table order. 54651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // The newly stale slot, or any other stale slot 54751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // encountered above it, can then be sent to expungeStaleEntry 54851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // to remove or rehash all of the other entries in run. 54951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (k == key) { 55051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e.value = value; 55151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 55251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[i] = tab[staleSlot]; 55351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[staleSlot] = e; 55451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 55551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Start expunge at preceding stale entry if it exists 55651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (slotToExpunge == staleSlot) 55751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski slotToExpunge = i; 55851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); 55951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return; 56051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 56151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 56251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // If we didn't find stale entry on backward scan, the 56351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // first stale entry seen while scanning for key is the 56451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // first still present in the run. 56551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (k == null && slotToExpunge == staleSlot) 56651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski slotToExpunge = i; 56751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 56851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 56951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // If key not found, put new entry in stale slot 57051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[staleSlot].value = null; 57151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[staleSlot] = new Entry(key, value); 57251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 57351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // If there are any other stale entries in run, expunge them 57451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (slotToExpunge != staleSlot) 57551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); 57651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 57751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 57851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 57951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Expunge a stale entry by rehashing any possibly colliding entries 58051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * lying between staleSlot and the next null slot. This also expunges 58151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * any other stale entries encountered before the trailing null. See 58251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Knuth, Section 6.4 58351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 58451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param staleSlot index of slot known to have null key 58551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the index of the next null slot after staleSlot 58651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (all between staleSlot and this slot will have been checked 58751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * for expunging). 58851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 58951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private int expungeStaleEntry(int staleSlot) { 59051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] tab = table; 59151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = tab.length; 59251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 59351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // expunge entry at staleSlot 59451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[staleSlot].value = null; 59551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[staleSlot] = null; 59651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size--; 59751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 59851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Rehash until we encounter null 59951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry e; 60051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int i; 60151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (i = nextIndex(staleSlot, len); 60251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski (e = tab[i]) != null; 60351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i = nextIndex(i, len)) { 6044e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak ThreadLocal<?> k = e.get(); 60551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (k == null) { 60651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e.value = null; 60751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[i] = null; 60851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size--; 60951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { 61051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int h = k.threadLocalHashCode & (len - 1); 61151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (h != i) { 61251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[i] = null; 61351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 61451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Unlike Knuth 6.4 Algorithm R, we must scan until 61551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // null because multiple entries could have been stale. 61651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (tab[h] != null) 61751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski h = nextIndex(h, len); 61851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[h] = e; 61951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 62051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 62151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 62251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return i; 62351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 62451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 62551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 62651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Heuristically scan some cells looking for stale entries. 62751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This is invoked when either a new element is added, or 62851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * another stale one has been expunged. It performs a 62951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * logarithmic number of scans, as a balance between no 63051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * scanning (fast but retains garbage) and a number of scans 63151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * proportional to number of elements, that would find all 63251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * garbage but would cause some insertions to take O(n) time. 63351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 63451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param i a position known NOT to hold a stale entry. The 63551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * scan starts at the element after i. 63651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 6374e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * @param n scan control: {@code log2(n)} cells are scanned, 63851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * unless a stale entry is found, in which case 6394e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak * {@code log2(table.length)-1} additional cells are scanned. 64051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * When called from insertions, this parameter is the number 64151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of elements, but when from replaceStaleEntry, it is the 64251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * table length. (Note: all this could be changed to be either 64351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * more or less aggressive by weighting n instead of just 64451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * using straight log n. But this version is simple, fast, and 64551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * seems to work well.) 64651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 64751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return true if any stale entries have been removed. 64851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 64951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private boolean cleanSomeSlots(int i, int n) { 65051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean removed = false; 65151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] tab = table; 65251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = tab.length; 65351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski do { 65451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i = nextIndex(i, len); 65551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry e = tab[i]; 65651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (e != null && e.get() == null) { 65751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski n = len; 65851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski removed = true; 65951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i = expungeStaleEntry(i); 66051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 66151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } while ( (n >>>= 1) != 0); 66251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return removed; 66351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 66451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 66551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 66651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Re-pack and/or re-size the table. First scan the entire 66751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * table removing stale entries. If this doesn't sufficiently 66851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * shrink the size of the table, double the table size. 66951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 67051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void rehash() { 67151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski expungeStaleEntries(); 67251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 67351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Use lower threshold for doubling to avoid hysteresis 67451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (size >= threshold - threshold / 4) 67551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski resize(); 67651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 67751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 67851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 67951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Double the capacity of the table. 68051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 68151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void resize() { 68251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] oldTab = table; 68351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int oldLen = oldTab.length; 68451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int newLen = oldLen * 2; 68551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] newTab = new Entry[newLen]; 68651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int count = 0; 68751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 68851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int j = 0; j < oldLen; ++j) { 68951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry e = oldTab[j]; 69051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (e != null) { 6914e73fd2bc22e704fe71465782b83be0471ac5e82Przemyslaw Szczepaniak ThreadLocal<?> k = e.get(); 69251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (k == null) { 69351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e.value = null; // Help the GC 69451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { 69551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int h = k.threadLocalHashCode & (newLen - 1); 69651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (newTab[h] != null) 69751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski h = nextIndex(h, newLen); 69851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newTab[h] = e; 69951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski count++; 70051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 70151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 70251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 70351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 70451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski setThreshold(newLen); 70551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size = count; 70651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski table = newTab; 70751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 70851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 70951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 71051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Expunge all stale entries in the table. 71151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 71251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void expungeStaleEntries() { 71351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] tab = table; 71451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = tab.length; 71551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int j = 0; j < len; j++) { 71651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry e = tab[j]; 71751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (e != null && e.get() == null) 71851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski expungeStaleEntry(j); 71951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 72051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 72151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 72251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski} 723