Robust/src/ClassLibrary/MGC/gnu/ThreadLocalMap.java

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