WeakHashtable


1   /*
2    * Copyright 2004 The Apache Software Foundation.
3    * 
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    * 
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    * 
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */ 
16  
17  
18  package org.apache.commons.logging.impl;
19  
20  import java.lang.ref.ReferenceQueue  ;
21  import java.lang.ref.WeakReference  ;
22  import java.util.*;
23  
24  /**
25   * <p>Implementation of <code>Hashtable</code> that uses <code>WeakReference</code>'s
26   * to hold its keys thus allowing them to be reclaimed by the garbage collector.
27   * The associated values are retained using strong references.</p>
28   *
29   * <p>This class follows the symantics of <code>Hashtable</code> as closely as
30   * possible. It therefore does not accept null values or keys.</p>
31   *
32   * <p><strong>Note:</strong>
33   * This is <em>not</em> intended to be a general purpose hash table replacement.
34   * This implementation is also tuned towards a particular purpose: for use as a replacement
35   * for <code>Hashtable</code> in <code>LogFactory</code>. This application requires
36   * good liveliness for <code>get</code> and <code>put</code>. Various tradeoffs
37   * have been made with this in mind.
38   * </p>
39   * <p>
40   * <strong>Usage:</strong> typical use case is as a drop-in replacement 
41   * for the <code>Hashtable</code> used in <code>LogFactory</code> for J2EE enviroments
42   * running 1.3+ JVMs. Use of this class <i>in most cases</i> (see below) will
43   * allow classloaders to be collected by the garbage collector without the need 
44   * to call {@link org.apache.commons.logging.LogFactory#release(ClassLoader) LogFactory.release(ClassLoader)}.
45   * </p>
46   *
47   * <p><code>org.apache.commons.logging.LogFactory</code> checks whether this class
48   * can be supported by the current JVM, and if so then uses it to store
49   * references to the <code>LogFactory</code> implementationd it loads 
50   * (rather than using a standard Hashtable instance). 
51   * Having this class used instead of <code>Hashtable</code> solves
52   * certain issues related to dynamic reloading of applications in J2EE-style
53   * environments. However this class requires java 1.3 or later (due to its use
54   * of <code>java.lang.ref.WeakReference</code> and associates).
55   * And by the way, this extends <code>Hashtable</code> rather than <code>HashMap</code>
56   * for backwards compatibility reasons. See the documentation
57   * for method <code>LogFactory.createFactoryStore</code> for more details.</p>
58   *
59   * <p>The reason all this is necessary is due to a issue which
60   * arises during hot deploy in a J2EE-like containers. 
61   * Each component running in the container owns one or more classloaders; when
62   * the component loads a LogFactory instance via the component classloader
63   * a reference to it gets stored in the static LogFactory.factories member,
64   * keyed by the component's classloader so different components don't
65   * stomp on each other. When the component is later unloaded, the container
66   * sets the component's classloader to null with the intent that all the 
67   * component's classes get garbage-collected. However there's still a
68   * reference to the component's classloader from a key in the "global"
69   * <code>LogFactory</code>'s factories member! If <code>LogFactory.release()</code>
70   * is called whenever component is unloaded, the classloaders will be correctly
71   * garbage collected; this <i>should</i> be done by any container that 
72   * bundles commons-logging by default. However, holding the classloader
73   * references weakly ensures that the classloader will be garbage collected
74   * without the container performing this step. </p>
75   *
76   * <p>
77   * <strong>Limitations:</strong>
78   * There is still one (unusual) scenario in which a component will not 
79   * be correctly unloaded without an explicit release. Though weak references
80   * are used for its keys, it is necessary to use strong references for its values.
81   * </p>
82   * 
83   * <p> If the abstract class <code>LogFactory</code> is 
84   * loaded by the container classloader but a subclass of 
85   * <code>LogFactory</code> [LogFactory1] is loaded by the component's 
86   * classloader and an instance stored in the static map associated with the
87   * base LogFactory class, then there is a strong reference from the LogFactory
88   * class to the LogFactory1 instance (as normal) and a strong reference from
89   * the LogFactory1 instance to the component classloader via
90   * <code>getClass().getClassLoader()</code>. This chain of references will prevent 
91   * collection of the child classloader.</p>
92   *
93   * <p>
94   * Such a situation occurs when the commons-logging.jar is
95   * loaded by a parent classloader (e.g. a server level classloader in a
96   * servlet container) and a custom <code>LogFactory</code> implementation is
97   * loaded by a child classloader (e.g. a web app classloader).</p>
98   * 
99   * <p>To avoid this scenario, ensure
100  * that any custom LogFactory subclass is loaded by the same classloader as 
101  * the base <code>LogFactory</code>. Creating custom LogFactory subclasses is,
102  * however, rare. The standard LogFactoryImpl class should be sufficient
103  * for most or all users.</p>
104  *
105  *
106  * @author Brian Stansberry
107  * 
108  * @since 1.1
109  */
110 public final class WeakHashtable extends Hashtable {
111 
112     /** 
113      * The maximum number of times put() or remove() can be called before
114      * the map will be purged of all cleared entries.
115      */
116     private static final int MAX_CHANGES_BEFORE_PURGE = 100;
117     
118     /** 
119      * The maximum number of times put() or remove() can be called before
120      * the map will be purged of one cleared entry.
121      */
122     private static final int PARTIAL_PURGE_COUNT     = 10;
123     
124     /* ReferenceQueue we check for gc'd keys */
125     private ReferenceQueue   queue = new ReferenceQueue  ();
126     /* Counter used to control how often we purge gc'd entries */
127     private int changeCount = 0;
128     
129     /**
130      * Constructs a WeakHashtable with the Hashtable default
131      * capacity and load factor.
132      */
133     public WeakHashtable() {}
134     
135     
136     /**
137      *@see Hashtable
138      */
139     public boolean containsKey(Object   key) {
140         // purge should not be required
141         Referenced referenced = new Referenced(key);
142         return super.containsKey(referenced);
143     }
144     
145     /**
146      *@see Hashtable
147      */
148     public Enumeration elements() {
149         purge();
150         return super.elements();
151     }
152     
153     /**
154      *@see Hashtable
155      */
156     public Set entrySet() {
157         purge();
158         Set referencedEntries = super.entrySet();
159         Set unreferencedEntries = new HashSet();
160         for (Iterator it=referencedEntries.iterator(); it.hasNext();) {
161             Map.Entry entry = (Map.Entry) it.next();
162             Referenced referencedKey = (Referenced) entry.getKey();
163             Object   key = referencedKey.getValue();
164             Object   value = entry.getValue();
165             if (key != null) {
166                 Entry dereferencedEntry = new Entry(key, value);
167                 unreferencedEntries.add(dereferencedEntry);
168             }
169         }
170         return unreferencedEntries;
171     }
172     
173     /**
174      *@see Hashtable
175      */
176     public Object   get(Object   key) {
177         // for performance reasons, no purge
178         Referenced referenceKey = new Referenced(key);
179         return super.get(referenceKey);
180     }
181     
182     /**
183      *@see Hashtable
184      */
185     public Enumeration keys() {
186         purge();
187         final Enumeration enumer = super.keys();
188         return new Enumeration() {
189             public boolean hasMoreElements() {
190                 return enumer.hasMoreElements();
191             }
192             public Object   nextElement() {
193                  Referenced nextReference = (Referenced) enumer.nextElement();
194                  return nextReference.getValue();
195             }
196         };
197     }
198     
199         
200     /**
201      *@see Hashtable
202      */
203     public Set keySet() {
204         purge();
205         Set referencedKeys = super.keySet();
206         Set unreferencedKeys = new HashSet();
207         for (Iterator it=referencedKeys.iterator(); it.hasNext();) {
208             Referenced referenceKey = (Referenced) it.next();
209             Object   keyValue = referenceKey.getValue();
210             if (keyValue != null) {
211                 unreferencedKeys.add(keyValue);
212             }
213         }
214         return unreferencedKeys;
215     }
216     
217     /**
218      *@see Hashtable
219      */    
220     public Object   put(Object   key, Object   value) {
221         // check for nulls, ensuring symantics match superclass
222         if (key == null) {
223             throw new NullPointerException  ("Null keys are not allowed");
224         }
225         if (value == null) {
226             throw new NullPointerException  ("Null values are not allowed");
227         }
228 
229         // for performance reasons, only purge every 
230         // MAX_CHANGES_BEFORE_PURGE times
231         if (changeCount++ > MAX_CHANGES_BEFORE_PURGE) {
232             purge();
233             changeCount = 0;
234         }
235         // do a partial purge more often
236         else if ((changeCount % PARTIAL_PURGE_COUNT) == 0) {
237             purgeOne();
238         }
239         
240         Object   result = null;
241         Referenced keyRef = new Referenced(key, queue);
242         return super.put(keyRef, value);
243     }
244     
245     /**
246      *@see Hashtable
247      */    
248     public void putAll(Map t) {
249         if (t != null) {
250             Set entrySet = t.entrySet();
251             for (Iterator it=entrySet.iterator(); it.hasNext();) {
252                 Map.Entry entry = (Map.Entry) it.next();
253                 put(entry.getKey(), entry.getValue());
254             }
255         }
256     }
257     
258     /**
259      *@see Hashtable
260      */      
261     public Collection values() {
262         purge();
263         return super.values();
264     }
265     
266     /**
267      *@see Hashtable
268      */     
269     public Object   remove(Object   key) {
270         // for performance reasons, only purge every 
271         // MAX_CHANGES_BEFORE_PURGE times
272         if (changeCount++ > MAX_CHANGES_BEFORE_PURGE) {
273             purge();
274             changeCount = 0;
275         }
276         // do a partial purge more often
277         else if ((changeCount % PARTIAL_PURGE_COUNT) == 0) {
278             purgeOne();
279         }
280         return super.remove(new Referenced(key));
281     }
282     
283     /**
284      *@see Hashtable
285      */    
286     public boolean isEmpty() {
287         purge();
288         return super.isEmpty();
289     }
290     
291     /**
292      *@see Hashtable
293      */    
294     public int size() {
295         purge();
296         return super.size();
297     }
298     
299     /**
300      *@see Hashtable
301      */        
302     public String   toString() {
303         purge();
304         return super.toString();
305     }
306     
307     /**
308      * @see Hashtable
309      */
310     protected void rehash() {
311         // purge here to save the effort of rehashing dead entries
312         purge();
313         super.rehash();
314     }
315     
316     /**
317      * Purges all entries whose wrapped keys
318      * have been garbage collected.
319      */
320     private void purge() {
321         synchronized (queue) {
322             WeakKey key;
323             while ((key = (WeakKey) queue.poll()) != null) {
324                 super.remove(key.getReferenced());
325             }
326         }
327     }
328     
329     /**
330      * Purges one entry whose wrapped key 
331      * has been garbage collected.
332      */
333     private void purgeOne() {
334         
335         synchronized (queue) {
336             WeakKey key = (WeakKey) queue.poll();
337             if (key != null) {
338                 super.remove(key.getReferenced());
339             }
340         }
341     }
342     
343     /** Entry implementation */
344     private final static class Entry implements Map.Entry {
345     
346         private final Object   key;
347         private final Object   value;
348         
349         private Entry(Object   key, Object   value) {
350             this.key = key;
351             this.value = value;
352         }
353     
354         public boolean equals(Object   o) {
355             boolean result = false;
356             if (o != null && o instanceof Map.Entry) {
357                 Map.Entry entry = (Map.Entry) o;
358                 result =    (getKey()==null ?
359                                             entry.getKey() == null : 
360                                             getKey().equals(entry.getKey()))
361                             &&
362                             (getValue()==null ?
363                                             entry.getValue() == null : 
364                                             getValue().equals(entry.getValue()));
365             }
366             return result;
367         } 
368         
369         public int hashCode() {
370 
371             return (getKey()==null ? 0 : getKey().hashCode()) ^
372                 (getValue()==null ? 0 : getValue().hashCode());
373         }
374 
375         public Object   setValue(Object   value) {
376             throw new UnsupportedOperationException  ("Entry.setValue is not supported.");
377         }
378         
379         public Object   getValue() {
380             return value;
381         }
382         
383         public Object   getKey() {
384             return key;
385         }
386     }
387     
388     
389     /** Wrapper giving correct symantics for equals and hashcode */
390     private final static class Referenced {
391         
392         private final WeakReference   reference;
393         private final int           hashCode;
394 
395         /**
396          * 
397          * @throws NullPointerException if referant is <code>null</code>
398          */        
399         private Referenced(Object   referant) {
400             reference = new WeakReference  (referant);
401             // Calc a permanent hashCode so calls to Hashtable.remove()
402             // work if the WeakReference has been cleared
403             hashCode  = referant.hashCode();
404         }
405         
406         /**
407          * 
408          * @throws NullPointerException if key is <code>null</code>
409          */
410         private Referenced(Object   key, ReferenceQueue   queue) {
411             reference = new WeakKey(key, queue, this);
412             // Calc a permanent hashCode so calls to Hashtable.remove()
413             // work if the WeakReference has been cleared
414             hashCode  = key.hashCode();
415 
416         }
417         
418         public int hashCode() {
419             return hashCode;
420         }
421         
422         private Object   getValue() {
423             return reference.get();
424         }
425         
426         public boolean equals(Object   o) {
427             boolean result = false;
428             if (o instanceof Referenced) {
429                 Referenced otherKey = (Referenced) o;
430                 Object   thisKeyValue = getValue();
431                 Object   otherKeyValue = otherKey.getValue();
432                 if (thisKeyValue == null) {                     
433                     result = (otherKeyValue == null);
434                     
435                     // Since our hashcode was calculated from the original
436                     // non-null referant, the above check breaks the 
437                     // hashcode/equals contract, as two cleared Referenced
438                     // objects could test equal but have different hashcodes.
439                     // We can reduce (not eliminate) the chance of this
440                     // happening by comparing hashcodes.
441                     if (result == true) {
442                         result = (this.hashCode() == otherKey.hashCode());
443                     }
444                     // In any case, as our c'tor does not allow null referants
445                     // and Hashtable does not do equality checks between 
446                     // existing keys, normal hashtable operations should never 
447                     // result in an equals comparison between null referants
448                 }
449                 else
450                 {
451                     result = thisKeyValue.equals(otherKeyValue);
452                 }
453             }
454             return result;
455         }
456     }
457     
458     /**
459      * WeakReference subclass that holds a hard reference to an
460      * associated <code>value</code> and also makes accessible
461      * the Referenced object holding it.
462      */
463     private final static class WeakKey extends WeakReference   {
464 
465         private final Referenced referenced;
466         
467         private WeakKey(Object   key, 
468                         ReferenceQueue   queue,
469                         Referenced referenced) {
470             super(key, queue);
471             this.referenced = referenced;
472         }
473         
474         private Referenced getReferenced() {
475             return referenced;
476         }
477      }
478 }
479
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags