libjava/classpath/java/lang/ThreadLocalMap.java

   1 /* ThreadLocal -- a variable with a unique value per thread
   2    Copyright (C) 2000, 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
   3
   4 This file is part of GNU Classpath.
   5
   6 GNU Classpath is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU Classpath is distributed in the hope that it will be useful, but
  12 WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Classpath; see the file COPYING.  If not, write to the
  18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301 USA.
  20
  21 Linking this library statically or dynamically with other modules is
  22 making a combined work based on this library.  Thus, the terms and
  23 conditions of the GNU General Public License cover the whole
  24 combination.
  25
  26 As a special exception, the copyright holders of this library give you
  27 permission to link this library with independent modules to produce an
  28 executable, regardless of the license terms of these independent
  29 modules, and to copy and distribute the resulting executable under
  30 terms of your choice, provided that you also meet, for each linked
  31 independent module, the terms and conditions of the license of that
  32 module.  An independent module is a module which is not derived from
  33 or based on this library.  If you modify this library, you may extend
  34 this exception to your version of the library, but you are not
  35 obligated to do so.  If you do not wish to do so, delete this
  36 exception statement from your version. */
  37
  38 package java.lang;
  39
  40 import java.lang.ref.WeakReference;
  41
  42 /**
  43  * ThreadLocalMap is the basic storage for the map of ThreadLocal instance
  44  * to a thread's current value.
  45  *
  46  * Some applications really work out ThreadLocals, leading to this
  47  * optimized implementation.
  48  */
  49 final class ThreadLocalMap
  50 {
  51   /**
  52    * The log (base 2) of the initial size of the map
  53    */
  54   private static final int LOG_INITIAL_SIZE = 3;
  55
  56   /**
  57    * The maximum occupancy rate (after which we grow)
  58    */
  59   private static final float MAX_OCCUPANCY = 0.7f;
  60
  61   /**
  62    * The target occupancy rate.
  63    */
  64   private static final float TARGET_OCCUPANCY = 0.5f;
  65
  66   /**
  67    * The deleted entry sentinel value.
  68    */
  69   private static final Entry deletedEntry = new Entry(null);
  70
  71   /**
  72    * Constructor
  73    */
  74   ThreadLocalMap()
  75   {
  76     /* Dummy value to ensure fast path can be optimized */
  77     entries = new Entry[1];
  78     hashMask = 0;
  79     count = 0;
  80   }
  81
  82   /**
  83    * The map entries
  84    */
  85   private Entry[] entries;
  86
  87   /**
  88    * Used for start index computation
  89    */
  90   private int hashMask;
  91
  92   /**
  93    * The number of entries currently in the map
  94    */
  95   private int count;
  96
  97   /**
  98    * Create or grow the table to the specified size. The size must be a
  99    * power of two for the efficient mask/hash computation.
 100    *
 101    * @param newSize The new table size.
 102    */
 103   private void newEntryArray(int newSize)
 104   {
 105     int mask = newSize - 1;
 106     Entry[] oldEntries = this.entries;
 107     this.entries = new Entry[newSize];
 108     this.hashMask = mask;
 109
 110     /* Copy old entries to new table */
 111     count = 0;
 112     if (oldEntries != null)
 113       {
 114         for(Entry e: oldEntries)
 115           {
 116             if (e != null)
 117               {
 118                 ThreadLocal<?> key = e.get();
 119                 if (e != deletedEntry && key != null)
 120                   {
 121                     for(int i = key.fastHash & mask;; i = (i + 1) & mask)
 122                       {
 123                         if (entries[i] == null)
 124                           {
 125                             entries[i] = e;
 126                             count++;
 127                             break;
 128                           }
 129                       }
 130                   }
 131               }
 132           }
 133       }
 134   }
 135
 136   /**
 137    * We have run out of space in our locals. We use this as the
 138    * trigger to attempt to find unused slots as ThreadLocals have
 139    * died. If we recover any slots this way then we do not grow.
 140    */
 141   private void overflow()
 142   {
 143     /* First 'actual' use */
 144     if (entries.length == 1)
 145       {
 146         newEntryArray(1 << LOG_INITIAL_SIZE);
 147         return;
 148       }
 149
 150     /* Attempt to recover unused slots */
 151     int deleted = 0;
 152     for(int i=0; i < entries.length; i++)
 153       {
 154         Entry e = entries[i];
 155         if (e != null)
 156           {
 157             if (e == deletedEntry)
 158               {
 159                 deleted++;
 160               }
 161             else if (e.get() == null)
 162               {
 163                 entries[i] = deletedEntry;
 164                 deleted++;
 165               }
 166           }
 167       }
 168
 169     if ((count-deleted) <= (TARGET_OCCUPANCY * entries.length))
 170       {
 171         /* We currently rehash by simple reallocating into a same-sized table.
 172          * An alternative would be to implement a clever hashing algorithm but
 173          * as this happens infrequently this seems preferred */
 174         newEntryArray(entries.length);
 175         return;
 176       }
 177
 178     /* Double the size */
 179     newEntryArray(entries.length << 1);
 180   }
 181
 182   /**
 183    * This is the class that is used to refer to a thread local weakly.
 184    *
 185    * As we want to minimize indirections we extend WeakReference.
 186    */
 187   static final class Entry extends WeakReference<ThreadLocal<?>> {
 188     /**
 189      * The value stored in this slot
 190      */
 191     Object value;
 192
 193     /**
 194      * Constructor
 195      */
 196     Entry(ThreadLocal<?> threadLocal) {
 197       super(threadLocal);
 198     }
 199   }
 200
 201   /**
 202    * Gets the value associated with the ThreadLocal object for the currently
 203    * executing Thread. If this is the first time the current thread has called
 204    * get(), and it has not already called set(), the sentinel value is returned.
 205    *
 206    * @return the value of the variable in this thread, or sentinel if not present.
 207    */
 208   public Object get(ThreadLocal<?> key)
 209   {
 210     int mask = this.hashMask;
 211     for(int i = key.fastHash & mask;; i = (i + 1) & mask) {
 212       Entry e = entries[i];
 213       if (e != null) {
 214         if (e.get() == key) {
 215           return e.value;
 216         }
 217       } else {
 218         return ThreadLocal.sentinel;
 219       }
 220     }
 221   }
 222
 223   /**
 224    * Sets the value associated with the ThreadLocal object for the currently
 225    * executing Thread. This overrides any existing value associated with the
 226    * current Thread and prevents <code>initialValue()</code> from being
 227    * called if this is the first access to this ThreadLocal in this Thread.
 228    *
 229    * @param value the value to set this thread's view of the variable to
 230    */
 231   public void set(ThreadLocal<?> key, Object value)
 232   {
 233     /* Overflow ? */
 234     if ((count+1) >= (MAX_OCCUPANCY * entries.length))
 235       {
 236         overflow();
 237       }
 238
 239     /* Set the entry */
 240     int mask = this.hashMask;
 241     for(int i = key.fastHash & mask;; i = (i + 1) & mask)
 242       {
 243         Entry e = entries[i];
 244         if (e == null || e == deletedEntry)
 245           {
 246             /* Create entry */
 247             if (e == null) count++;
 248             entries[i] = e = new Entry(key);
 249             e.value = value;
 250             return;
 251           }
 252         else
 253           {
 254             ThreadLocal<?> entryKey = e.get();
 255             if (entryKey == null)
 256               {
 257               entries[i] = deletedEntry;
 258               }
 259             else if (entryKey == key)
 260               {
 261                 /* Update entry */
 262                 e.value = value;
 263                 return;
 264               }
 265           }
 266       }
 267   }
 268
 269   /**
 270    * Removes the value associated with the ThreadLocal object for the
 271    * currently executing Thread.
 272    * @since 1.5
 273    */
 274   public void remove(ThreadLocal<?> key)
 275   {
 276     int mask = this.hashMask;
 277     for(int i = key.fastHash & mask;; i = (i + 1) & mask)
 278       {
 279         Entry e = entries[i];
 280         if (e != null)
 281           {
 282             ThreadLocal<?> entryKey = e.get();
 283             if (entryKey != key)
 284               {
 285                 if (entryKey == null) {
 286                   entries[i] = deletedEntry;
 287                 }
 288                 continue;
 289               }
 290             else
 291               {
 292                 /* Remove from the table */
 293                 entries[i] = deletedEntry;
 294               }
 295           }
 296           return;
 297       }
 298   }
 299
 300   /**
 301    * Clear out the map. Done once during thread death.
 302    */
 303   void clear() {
 304     entries = null;
 305   }
 306
 307   /**
 308    * Inherit all the InheritableThreadLocal instances from the given parent.
 309    *
 310    * @param parentMap The map to inherit from.
 311    */
 312   public void inherit(ThreadLocalMap parentMap) {
 313     for(Entry e: parentMap.entries)
 314       {
 315         if (e != null && e != deletedEntry)
 316           {
 317             ThreadLocal<?> key = e.get();
 318             if (key instanceof InheritableThreadLocal)
 319               {
 320                 set(key, ((InheritableThreadLocal)key).childValue(e.value));
 321               }
 322           }
 323       }
 324   }
 325 }