ThreadLocal.java revision 51b1b6997fd3f980076b8081f7f1165ccc2a4008
151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski/* 251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Copyright (c) 1997, 2007, 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.*; 2851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskiimport java.util.concurrent.atomic.AtomicInteger; 2951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 3051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski/** 3151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This class provides thread-local variables. These variables differ from 3251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * their normal counterparts in that each thread that accesses one (via its 3351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tt>get</tt> or <tt>set</tt> method) has its own, independently initialized 3451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * copy of the variable. <tt>ThreadLocal</tt> instances are typically private 3551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * static fields in classes that wish to associate state with a thread (e.g., 3651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * a user ID or Transaction ID). 3751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 3851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>For example, the class below generates unique identifiers local to each 3951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * thread. 4051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * A thread's id is assigned the first time it invokes <tt>ThreadId.get()</tt> 4151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * and remains unchanged on subsequent calls. 4251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <pre> 4351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * import java.util.concurrent.atomic.AtomicInteger; 4451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 4551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * public class ThreadId { 4651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * // Atomic integer containing the next thread ID to be assigned 4751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * private static final AtomicInteger nextId = new AtomicInteger(0); 4851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 4951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * // Thread local variable containing each thread's ID 5051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * private static final ThreadLocal<Integer> threadId = 5151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * new ThreadLocal<Integer>() { 5251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @Override protected Integer initialValue() { 5351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * return nextId.getAndIncrement(); 5451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * } 5551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * }; 5651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 5751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * // Returns the current thread's unique ID, assigning it if necessary 5851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * public static int get() { 5951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * return threadId.get(); 6051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * } 6151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * } 6251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </pre> 6351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>Each thread holds an implicit reference to its copy of a thread-local 6451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * variable as long as the thread is alive and the <tt>ThreadLocal</tt> 6551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * instance is accessible; after a thread goes away, all of its copies of 6651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * thread-local instances are subject to garbage collection (unless other 6751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * references to these copies exist). 6851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 6951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @author Josh Bloch and Doug Lea 7051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @since 1.2 7151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 7251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskipublic class ThreadLocal<T> { 7351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 7451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ThreadLocals rely on per-thread linear-probe hash maps attached 7551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * to each thread (Thread.threadLocals and 7651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * inheritableThreadLocals). The ThreadLocal objects act as keys, 7751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * searched via threadLocalHashCode. This is a custom hash code 7851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (useful only within ThreadLocalMaps) that eliminates collisions 7951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * in the common case where consecutively constructed ThreadLocals 8051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * are used by the same threads, while remaining well-behaved in 8151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * less common cases. 8251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 8351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private final int threadLocalHashCode = nextHashCode(); 8451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 8551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 8651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The next hash code to be given out. Updated atomically. Starts at 8751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * zero. 8851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 8951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static AtomicInteger nextHashCode = 9051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski new AtomicInteger(); 9151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 9251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 9351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The difference between successively generated hash codes - turns 9451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * implicit sequential thread-local IDs into near-optimally spread 9551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * multiplicative hash values for power-of-two-sized tables. 9651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 9751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final int HASH_INCREMENT = 0x61c88647; 9851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 9951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 10051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns the next hash code. 10151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 10251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static int nextHashCode() { 10351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return nextHashCode.getAndAdd(HASH_INCREMENT); 10451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 10551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 10651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 10751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns the current thread's "initial value" for this 10851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * thread-local variable. This method will be invoked the first 10951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * time a thread accesses the variable with the {@link #get} 11051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * method, unless the thread previously invoked the {@link #set} 11151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * method, in which case the <tt>initialValue</tt> method will not 11251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * be invoked for the thread. Normally, this method is invoked at 11351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * most once per thread, but it may be invoked again in case of 11451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * subsequent invocations of {@link #remove} followed by {@link #get}. 11551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 11651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This implementation simply returns <tt>null</tt>; if the 11751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * programmer desires thread-local variables to have an initial 11851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * value other than <tt>null</tt>, <tt>ThreadLocal</tt> must be 11951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * subclassed, and this method overridden. Typically, an 12051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * anonymous inner class will be used. 12151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 12251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the initial value for this thread-local 12351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 12451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski protected T initialValue() { 12551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return null; 12651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 12751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 12851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 12951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Creates a thread local variable. 13051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 13151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public ThreadLocal() { 13251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 13351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 13451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 13551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns the value in the current thread's copy of this 13651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * thread-local variable. If the variable has no value for the 13751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * current thread, it is first initialized to the value returned 13851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * by an invocation of the {@link #initialValue} method. 13951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 14051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the current thread's value of this thread-local 14151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 14251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public T get() { 14351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Thread t = Thread.currentThread(); 14451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocalMap map = getMap(t); 14551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (map != null) { 14651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocalMap.Entry e = map.getEntry(this); 14751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (e != null) 14851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return (T)e.value; 14951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 15051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return setInitialValue(); 15151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 15251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 15351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 15451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Variant of set() to establish initialValue. Used instead 15551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of set() in case user has overridden the set() method. 15651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 15751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the initial value 15851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 15951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private T setInitialValue() { 16051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski T value = initialValue(); 16151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Thread t = Thread.currentThread(); 16251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocalMap map = getMap(t); 16351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (map != null) 16451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski map.set(this, value); 16551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 16651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski createMap(t, value); 16751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return value; 16851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 16951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 17051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 17151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Sets the current thread's copy of this thread-local variable 17251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * to the specified value. Most subclasses will have no need to 17351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * override this method, relying solely on the {@link #initialValue} 17451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * method to set the values of thread-locals. 17551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 17651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param value the value to be stored in the current thread's copy of 17751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * this thread-local. 17851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 17951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void set(T value) { 18051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Thread t = Thread.currentThread(); 18151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocalMap map = getMap(t); 18251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (map != null) 18351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski map.set(this, value); 18451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 18551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski createMap(t, value); 18651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 18751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 18851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 18951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Removes the current thread's value for this thread-local 19051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * variable. If this thread-local variable is subsequently 19151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@linkplain #get read} by the current thread, its value will be 19251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * reinitialized by invoking its {@link #initialValue} method, 19351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * unless its value is {@linkplain #set set} by the current thread 19451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * in the interim. This may result in multiple invocations of the 19551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tt>initialValue</tt> method in the current thread. 19651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 19751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @since 1.5 19851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 19951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void remove() { 20051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocalMap m = getMap(Thread.currentThread()); 20151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (m != null) 20251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski m.remove(this); 20351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 20451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 20551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 20651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Get the map associated with a ThreadLocal. Overridden in 20751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * InheritableThreadLocal. 20851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 20951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param t the current thread 21051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the map 21151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 21251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocalMap getMap(Thread t) { 21351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return t.threadLocals; 21451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 21551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 21651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 21751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Create the map associated with a ThreadLocal. Overridden in 21851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * InheritableThreadLocal. 21951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 22051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param t the current thread 22151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param firstValue value for the initial entry of the map 22251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param map the map to store. 22351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 22451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski void createMap(Thread t, T firstValue) { 22551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski t.threadLocals = new ThreadLocalMap(this, firstValue); 22651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 22751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 22851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 22951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Factory method to create map of inherited thread locals. 23051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Designed to be called only from Thread constructor. 23151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 23251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param parentMap the map associated with parent thread 23351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return a map containing the parent's inheritable bindings 23451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 23551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski static ThreadLocalMap createInheritedMap(ThreadLocalMap parentMap) { 23651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return new ThreadLocalMap(parentMap); 23751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 23851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 23951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 24051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Method childValue is visibly defined in subclass 24151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * InheritableThreadLocal, but is internally defined here for the 24251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * sake of providing createInheritedMap factory method without 24351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * needing to subclass the map class in InheritableThreadLocal. 24451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This technique is preferable to the alternative of embedding 24551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * instanceof tests in methods. 24651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 24751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski T childValue(T parentValue) { 24851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new UnsupportedOperationException(); 24951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 25051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 25151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 25251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ThreadLocalMap is a customized hash map suitable only for 25351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * maintaining thread local values. No operations are exported 25451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * outside of the ThreadLocal class. The class is package private to 25551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * allow declaration of fields in class Thread. To help deal with 25651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * very large and long-lived usages, the hash table entries use 25751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * WeakReferences for keys. However, since reference queues are not 25851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * used, stale entries are guaranteed to be removed only when 25951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the table starts running out of space. 26051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 26151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski static class ThreadLocalMap { 26251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 26351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 26451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The entries in this hash map extend WeakReference, using 26551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * its main ref field as the key (which is always a 26651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ThreadLocal object). Note that null keys (i.e. entry.get() 26751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * == null) mean that the key is no longer referenced, so the 26851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * entry can be expunged from table. Such entries are referred to 26951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * as "stale entries" in the code that follows. 27051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 27151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski static class Entry extends WeakReference<ThreadLocal> { 27251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** The value associated with this ThreadLocal. */ 27351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Object value; 27451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 27551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry(ThreadLocal k, Object v) { 27651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski super(k); 27751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski value = v; 27851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 27951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 28051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 28151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 28251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The initial capacity -- MUST be a power of two. 28351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 28451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final int INITIAL_CAPACITY = 16; 28551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 28651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 28751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The table, resized as necessary. 28851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * table.length MUST always be a power of two. 28951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 29051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private Entry[] table; 29151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 29251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 29351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The number of entries in the table. 29451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 29551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private int size = 0; 29651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 29751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 29851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The next size value at which to resize. 29951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 30051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private int threshold; // Default to 0 30151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 30251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 30351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Set the resize threshold to maintain at worst a 2/3 load factor. 30451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 30551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void setThreshold(int len) { 30651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski threshold = len * 2 / 3; 30751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 30851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 30951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 31051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Increment i modulo len. 31151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 31251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static int nextIndex(int i, int len) { 31351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return ((i + 1 < len) ? i + 1 : 0); 31451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 31551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 31651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 31751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Decrement i modulo len. 31851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 31951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static int prevIndex(int i, int len) { 32051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return ((i - 1 >= 0) ? i - 1 : len - 1); 32151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 32251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 32351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 32451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Construct a new map initially containing (firstKey, firstValue). 32551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ThreadLocalMaps are constructed lazily, so we only create 32651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * one when we have at least one entry to put in it. 32751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 32851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocalMap(ThreadLocal firstKey, Object firstValue) { 32951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski table = new Entry[INITIAL_CAPACITY]; 33051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1); 33151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski table[i] = new Entry(firstKey, firstValue); 33251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size = 1; 33351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski setThreshold(INITIAL_CAPACITY); 33451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 33551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 33651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 33751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Construct a new map including all Inheritable ThreadLocals 33851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * from given parent map. Called only by createInheritedMap. 33951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 34051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param parentMap the map associated with parent thread. 34151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 34251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private ThreadLocalMap(ThreadLocalMap parentMap) { 34351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] parentTable = parentMap.table; 34451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = parentTable.length; 34551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski setThreshold(len); 34651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski table = new Entry[len]; 34751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 34851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int j = 0; j < len; j++) { 34951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry e = parentTable[j]; 35051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (e != null) { 35151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocal key = e.get(); 35251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (key != null) { 35351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Object value = key.childValue(e.value); 35451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry c = new Entry(key, value); 35551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int h = key.threadLocalHashCode & (len - 1); 35651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (table[h] != null) 35751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski h = nextIndex(h, len); 35851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski table[h] = c; 35951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size++; 36051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 36151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 36251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 36351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 36451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 36551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 36651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Get the entry associated with key. This method 36751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * itself handles only the fast path: a direct hit of existing 36851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * key. It otherwise relays to getEntryAfterMiss. This is 36951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * designed to maximize performance for direct hits, in part 37051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * by making this method readily inlinable. 37151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 37251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param key the thread local object 37351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the entry associated with key, or null if no such 37451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 37551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private Entry getEntry(ThreadLocal key) { 37651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int i = key.threadLocalHashCode & (table.length - 1); 37751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry e = table[i]; 37851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (e != null && e.get() == key) 37951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return e; 38051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 38151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return getEntryAfterMiss(key, i, e); 38251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 38351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 38451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 38551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Version of getEntry method for use when key is not found in 38651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * its direct hash slot. 38751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 38851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param key the thread local object 38951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param i the table index for key's hash code 39051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param e the entry at table[i] 39151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the entry associated with key, or null if no such 39251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 39351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private Entry getEntryAfterMiss(ThreadLocal key, int i, Entry e) { 39451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] tab = table; 39551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = tab.length; 39651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 39751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (e != null) { 39851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocal k = e.get(); 39951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (k == key) 40051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return e; 40151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (k == null) 40251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski expungeStaleEntry(i); 40351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 40451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i = nextIndex(i, len); 40551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e = tab[i]; 40651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 40751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return null; 40851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 40951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 41051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 41151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Set the value associated with key. 41251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 41351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param key the thread local object 41451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param value the value to be set 41551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 41651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void set(ThreadLocal key, Object value) { 41751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 41851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // We don't use a fast path as with get() because it is at 41951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // least as common to use set() to create new entries as 42051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // it is to replace existing ones, in which case, a fast 42151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // path would fail more often than not. 42251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 42351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] tab = table; 42451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = tab.length; 42551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int i = key.threadLocalHashCode & (len-1); 42651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 42751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (Entry e = tab[i]; 42851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e != null; 42951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e = tab[i = nextIndex(i, len)]) { 43051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocal k = e.get(); 43151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 43251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (k == key) { 43351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e.value = value; 43451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return; 43551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 43651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 43751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (k == null) { 43851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski replaceStaleEntry(key, value, i); 43951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return; 44051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 44151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 44251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 44351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[i] = new Entry(key, value); 44451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int sz = ++size; 44551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (!cleanSomeSlots(i, sz) && sz >= threshold) 44651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski rehash(); 44751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 44851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 44951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 45051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Remove the entry for key. 45151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 45251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void remove(ThreadLocal key) { 45351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] tab = table; 45451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = tab.length; 45551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int i = key.threadLocalHashCode & (len-1); 45651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (Entry e = tab[i]; 45751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e != null; 45851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e = tab[i = nextIndex(i, len)]) { 45951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (e.get() == key) { 46051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e.clear(); 46151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski expungeStaleEntry(i); 46251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return; 46351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 46451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 46551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 46651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 46751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 46851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Replace a stale entry encountered during a set operation 46951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * with an entry for the specified key. The value passed in 47051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the value parameter is stored in the entry, whether or not 47151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * an entry already exists for the specified key. 47251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 47351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * As a side effect, this method expunges all stale entries in the 47451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * "run" containing the stale entry. (A run is a sequence of entries 47551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * between two null slots.) 47651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 47751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param key the key 47851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param value the value to be associated with key 47951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param staleSlot index of the first stale entry encountered while 48051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * searching for key. 48151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 48251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void replaceStaleEntry(ThreadLocal key, Object value, 48351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int staleSlot) { 48451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] tab = table; 48551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = tab.length; 48651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry e; 48751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 48851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Back up to check for prior stale entry in current run. 48951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // We clean out whole runs at a time to avoid continual 49051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // incremental rehashing due to garbage collector freeing 49151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // up refs in bunches (i.e., whenever the collector runs). 49251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int slotToExpunge = staleSlot; 49351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = prevIndex(staleSlot, len); 49451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski (e = tab[i]) != null; 49551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i = prevIndex(i, len)) 49651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (e.get() == null) 49751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski slotToExpunge = i; 49851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 49951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Find either the key or trailing null slot of run, whichever 50051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // occurs first 50151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = nextIndex(staleSlot, len); 50251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski (e = tab[i]) != null; 50351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i = nextIndex(i, len)) { 50451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocal k = e.get(); 50551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 50651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // If we find key, then we need to swap it 50751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // with the stale entry to maintain hash table order. 50851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // The newly stale slot, or any other stale slot 50951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // encountered above it, can then be sent to expungeStaleEntry 51051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // to remove or rehash all of the other entries in run. 51151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (k == key) { 51251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e.value = value; 51351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 51451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[i] = tab[staleSlot]; 51551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[staleSlot] = e; 51651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 51751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Start expunge at preceding stale entry if it exists 51851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (slotToExpunge == staleSlot) 51951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski slotToExpunge = i; 52051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); 52151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return; 52251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 52351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 52451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // If we didn't find stale entry on backward scan, the 52551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // first stale entry seen while scanning for key is the 52651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // first still present in the run. 52751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (k == null && slotToExpunge == staleSlot) 52851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski slotToExpunge = i; 52951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 53051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 53151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // If key not found, put new entry in stale slot 53251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[staleSlot].value = null; 53351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[staleSlot] = new Entry(key, value); 53451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 53551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // If there are any other stale entries in run, expunge them 53651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (slotToExpunge != staleSlot) 53751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); 53851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 53951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 54051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 54151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Expunge a stale entry by rehashing any possibly colliding entries 54251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * lying between staleSlot and the next null slot. This also expunges 54351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * any other stale entries encountered before the trailing null. See 54451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Knuth, Section 6.4 54551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 54651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param staleSlot index of slot known to have null key 54751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the index of the next null slot after staleSlot 54851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (all between staleSlot and this slot will have been checked 54951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * for expunging). 55051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 55151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private int expungeStaleEntry(int staleSlot) { 55251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] tab = table; 55351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = tab.length; 55451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 55551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // expunge entry at staleSlot 55651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[staleSlot].value = null; 55751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[staleSlot] = null; 55851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size--; 55951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 56051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Rehash until we encounter null 56151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry e; 56251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int i; 56351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (i = nextIndex(staleSlot, len); 56451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski (e = tab[i]) != null; 56551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i = nextIndex(i, len)) { 56651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocal k = e.get(); 56751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (k == null) { 56851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e.value = null; 56951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[i] = null; 57051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size--; 57151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { 57251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int h = k.threadLocalHashCode & (len - 1); 57351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (h != i) { 57451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[i] = null; 57551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 57651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Unlike Knuth 6.4 Algorithm R, we must scan until 57751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // null because multiple entries could have been stale. 57851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (tab[h] != null) 57951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski h = nextIndex(h, len); 58051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski tab[h] = e; 58151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 58251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 58351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 58451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return i; 58551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 58651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 58751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 58851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Heuristically scan some cells looking for stale entries. 58951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This is invoked when either a new element is added, or 59051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * another stale one has been expunged. It performs a 59151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * logarithmic number of scans, as a balance between no 59251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * scanning (fast but retains garbage) and a number of scans 59351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * proportional to number of elements, that would find all 59451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * garbage but would cause some insertions to take O(n) time. 59551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 59651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param i a position known NOT to hold a stale entry. The 59751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * scan starts at the element after i. 59851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 59951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param n scan control: <tt>log2(n)</tt> cells are scanned, 60051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * unless a stale entry is found, in which case 60151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tt>log2(table.length)-1</tt> additional cells are scanned. 60251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * When called from insertions, this parameter is the number 60351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of elements, but when from replaceStaleEntry, it is the 60451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * table length. (Note: all this could be changed to be either 60551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * more or less aggressive by weighting n instead of just 60651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * using straight log n. But this version is simple, fast, and 60751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * seems to work well.) 60851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 60951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return true if any stale entries have been removed. 61051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 61151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private boolean cleanSomeSlots(int i, int n) { 61251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean removed = false; 61351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] tab = table; 61451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = tab.length; 61551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski do { 61651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i = nextIndex(i, len); 61751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry e = tab[i]; 61851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (e != null && e.get() == null) { 61951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski n = len; 62051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski removed = true; 62151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i = expungeStaleEntry(i); 62251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 62351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } while ( (n >>>= 1) != 0); 62451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return removed; 62551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 62651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 62751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 62851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Re-pack and/or re-size the table. First scan the entire 62951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * table removing stale entries. If this doesn't sufficiently 63051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * shrink the size of the table, double the table size. 63151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 63251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void rehash() { 63351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski expungeStaleEntries(); 63451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 63551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Use lower threshold for doubling to avoid hysteresis 63651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (size >= threshold - threshold / 4) 63751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski resize(); 63851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 63951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 64051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 64151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Double the capacity of the table. 64251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 64351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void resize() { 64451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] oldTab = table; 64551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int oldLen = oldTab.length; 64651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int newLen = oldLen * 2; 64751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] newTab = new Entry[newLen]; 64851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int count = 0; 64951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 65051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int j = 0; j < oldLen; ++j) { 65151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry e = oldTab[j]; 65251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (e != null) { 65351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ThreadLocal k = e.get(); 65451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (k == null) { 65551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski e.value = null; // Help the GC 65651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { 65751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int h = k.threadLocalHashCode & (newLen - 1); 65851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (newTab[h] != null) 65951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski h = nextIndex(h, newLen); 66051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newTab[h] = e; 66151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski count++; 66251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 66351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 66451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 66551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 66651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski setThreshold(newLen); 66751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size = count; 66851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski table = newTab; 66951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 67051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 67151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 67251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Expunge all stale entries in the table. 67351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 67451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void expungeStaleEntries() { 67551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry[] tab = table; 67651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = tab.length; 67751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int j = 0; j < len; j++) { 67851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Entry e = tab[j]; 67951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (e != null && e.get() == null) 68051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski expungeStaleEntry(j); 68151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 68251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 68351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 68451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski} 685