001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     * 
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     * 
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */ 
017    
018    
019    package org.apache.commons.logging.impl;
020    
021    import java.lang.ref.ReferenceQueue;
022    import java.lang.ref.WeakReference;
023    import java.util.*;
024    
025    /**
026     * <p>Implementation of <code>Hashtable</code> that uses <code>WeakReference</code>'s
027     * to hold its keys thus allowing them to be reclaimed by the garbage collector.
028     * The associated values are retained using strong references.</p>
029     *
030     * <p>This class follows the symantics of <code>Hashtable</code> as closely as
031     * possible. It therefore does not accept null values or keys.</p>
032     *
033     * <p><strong>Note:</strong>
034     * This is <em>not</em> intended to be a general purpose hash table replacement.
035     * This implementation is also tuned towards a particular purpose: for use as a replacement
036     * for <code>Hashtable</code> in <code>LogFactory</code>. This application requires
037     * good liveliness for <code>get</code> and <code>put</code>. Various tradeoffs
038     * have been made with this in mind.
039     * </p>
040     * <p>
041     * <strong>Usage:</strong> typical use case is as a drop-in replacement 
042     * for the <code>Hashtable</code> used in <code>LogFactory</code> for J2EE enviroments
043     * running 1.3+ JVMs. Use of this class <i>in most cases</i> (see below) will
044     * allow classloaders to be collected by the garbage collector without the need 
045     * to call {@link org.apache.commons.logging.LogFactory#release(ClassLoader) LogFactory.release(ClassLoader)}.
046     * </p>
047     *
048     * <p><code>org.apache.commons.logging.LogFactory</code> checks whether this class
049     * can be supported by the current JVM, and if so then uses it to store
050     * references to the <code>LogFactory</code> implementationd it loads 
051     * (rather than using a standard Hashtable instance). 
052     * Having this class used instead of <code>Hashtable</code> solves
053     * certain issues related to dynamic reloading of applications in J2EE-style
054     * environments. However this class requires java 1.3 or later (due to its use
055     * of <code>java.lang.ref.WeakReference</code> and associates).
056     * And by the way, this extends <code>Hashtable</code> rather than <code>HashMap</code>
057     * for backwards compatibility reasons. See the documentation
058     * for method <code>LogFactory.createFactoryStore</code> for more details.</p>
059     *
060     * <p>The reason all this is necessary is due to a issue which
061     * arises during hot deploy in a J2EE-like containers. 
062     * Each component running in the container owns one or more classloaders; when
063     * the component loads a LogFactory instance via the component classloader
064     * a reference to it gets stored in the static LogFactory.factories member,
065     * keyed by the component's classloader so different components don't
066     * stomp on each other. When the component is later unloaded, the container
067     * sets the component's classloader to null with the intent that all the 
068     * component's classes get garbage-collected. However there's still a
069     * reference to the component's classloader from a key in the "global"
070     * <code>LogFactory</code>'s factories member! If <code>LogFactory.release()</code>
071     * is called whenever component is unloaded, the classloaders will be correctly
072     * garbage collected; this <i>should</i> be done by any container that 
073     * bundles commons-logging by default. However, holding the classloader
074     * references weakly ensures that the classloader will be garbage collected
075     * without the container performing this step. </p>
076     *
077     * <p>
078     * <strong>Limitations:</strong>
079     * There is still one (unusual) scenario in which a component will not 
080     * be correctly unloaded without an explicit release. Though weak references
081     * are used for its keys, it is necessary to use strong references for its values.
082     * </p>
083     * 
084     * <p> If the abstract class <code>LogFactory</code> is 
085     * loaded by the container classloader but a subclass of 
086     * <code>LogFactory</code> [LogFactory1] is loaded by the component's 
087     * classloader and an instance stored in the static map associated with the
088     * base LogFactory class, then there is a strong reference from the LogFactory
089     * class to the LogFactory1 instance (as normal) and a strong reference from
090     * the LogFactory1 instance to the component classloader via
091     * <code>getClass().getClassLoader()</code>. This chain of references will prevent 
092     * collection of the child classloader.</p>
093     *
094     * <p>
095     * Such a situation occurs when the commons-logging.jar is
096     * loaded by a parent classloader (e.g. a server level classloader in a
097     * servlet container) and a custom <code>LogFactory</code> implementation is
098     * loaded by a child classloader (e.g. a web app classloader).</p>
099     * 
100     * <p>To avoid this scenario, ensure
101     * that any custom LogFactory subclass is loaded by the same classloader as 
102     * the base <code>LogFactory</code>. Creating custom LogFactory subclasses is,
103     * however, rare. The standard LogFactoryImpl class should be sufficient
104     * for most or all users.</p>
105     *
106     *
107     * @author Brian Stansberry
108     * 
109     * @since 1.1
110     */
111    public final class WeakHashtable extends Hashtable {
112    
113        /** 
114         * The maximum number of times put() or remove() can be called before
115         * the map will be purged of all cleared entries.
116         */
117        private static final int MAX_CHANGES_BEFORE_PURGE = 100;
118        
119        /** 
120         * The maximum number of times put() or remove() can be called before
121         * the map will be purged of one cleared entry.
122         */
123        private static final int PARTIAL_PURGE_COUNT     = 10;
124        
125        /* ReferenceQueue we check for gc'd keys */
126        private ReferenceQueue queue = new ReferenceQueue();
127        /* Counter used to control how often we purge gc'd entries */
128        private int changeCount = 0;
129        
130        /**
131         * Constructs a WeakHashtable with the Hashtable default
132         * capacity and load factor.
133         */
134        public WeakHashtable() {}
135        
136        
137        /**
138         *@see Hashtable
139         */
140        public boolean containsKey(Object key) {
141            // purge should not be required
142            Referenced referenced = new Referenced(key);
143            return super.containsKey(referenced);
144        }
145        
146        /**
147         *@see Hashtable
148         */
149        public Enumeration elements() {
150            purge();
151            return super.elements();
152        }
153        
154        /**
155         *@see Hashtable
156         */
157        public Set entrySet() {
158            purge();
159            Set referencedEntries = super.entrySet();
160            Set unreferencedEntries = new HashSet();
161            for (Iterator it=referencedEntries.iterator(); it.hasNext();) {
162                Map.Entry entry = (Map.Entry) it.next();
163                Referenced referencedKey = (Referenced) entry.getKey();
164                Object key = referencedKey.getValue();
165                Object value = entry.getValue();
166                if (key != null) {
167                    Entry dereferencedEntry = new Entry(key, value);
168                    unreferencedEntries.add(dereferencedEntry);
169                }
170            }
171            return unreferencedEntries;
172        }
173        
174        /**
175         *@see Hashtable
176         */
177        public Object get(Object key) {
178            // for performance reasons, no purge
179            Referenced referenceKey = new Referenced(key);
180            return super.get(referenceKey);
181        }
182        
183        /**
184         *@see Hashtable
185         */
186        public Enumeration keys() {
187            purge();
188            final Enumeration enumer = super.keys();
189            return new Enumeration() {
190                public boolean hasMoreElements() {
191                    return enumer.hasMoreElements();
192                }
193                public Object nextElement() {
194                     Referenced nextReference = (Referenced) enumer.nextElement();
195                     return nextReference.getValue();
196                }
197            };
198        }
199        
200            
201        /**
202         *@see Hashtable
203         */
204        public Set keySet() {
205            purge();
206            Set referencedKeys = super.keySet();
207            Set unreferencedKeys = new HashSet();
208            for (Iterator it=referencedKeys.iterator(); it.hasNext();) {
209                Referenced referenceKey = (Referenced) it.next();
210                Object keyValue = referenceKey.getValue();
211                if (keyValue != null) {
212                    unreferencedKeys.add(keyValue);
213                }
214            }
215            return unreferencedKeys;
216        }
217        
218        /**
219         *@see Hashtable
220         */    
221        public Object put(Object key, Object value) {
222            // check for nulls, ensuring symantics match superclass
223            if (key == null) {
224                throw new NullPointerException("Null keys are not allowed");
225            }
226            if (value == null) {
227                throw new NullPointerException("Null values are not allowed");
228            }
229    
230            // for performance reasons, only purge every 
231            // MAX_CHANGES_BEFORE_PURGE times
232            if (changeCount++ > MAX_CHANGES_BEFORE_PURGE) {
233                purge();
234                changeCount = 0;
235            }
236            // do a partial purge more often
237            else if ((changeCount % PARTIAL_PURGE_COUNT) == 0) {
238                purgeOne();
239            }
240            
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    }