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
018package org.apache.commons.logging.impl;
019
020import java.lang.ref.ReferenceQueue;
021import java.lang.ref.WeakReference;
022import java.util.ArrayList;
023import java.util.Collection;
024import java.util.Enumeration;
025import java.util.HashSet;
026import java.util.Hashtable;
027import java.util.List;
028import java.util.Map;
029import java.util.Objects;
030import java.util.Set;
031
032/**
033 * Implementation of {@code Hashtable} that uses {@code WeakReference}'s
034 * to hold its keys thus allowing them to be reclaimed by the garbage collector.
035 * The associated values are retained using strong references.
036 * <p>
037 * This class follows the semantics of {@code Hashtable} as closely as
038 * possible. It therefore does not accept null values or keys.
039 * <p>
040 * <strong>Note:</strong>
041 * This is <em>not</em> intended to be a general purpose hash table replacement.
042 * This implementation is also tuned towards a particular purpose: for use as a replacement
043 * for {@code Hashtable} in {@code LogFactory}. This application requires
044 * good liveliness for {@code get} and {@code put}. Various tradeoffs
045 * have been made with this in mind.
046 * <p>
047 * <strong>Usage:</strong> typical use case is as a drop-in replacement
048 * for the {@code Hashtable} used in {@code LogFactory} for J2EE environments
049 * running 1.3+ JVMs. Use of this class <i>in most cases</i> (see below) will
050 * allow class loaders to be collected by the garbage collector without the need
051 * to call {@link org.apache.commons.logging.LogFactory#release(ClassLoader) LogFactory.release(ClassLoader)}.
052 * <p>
053 * {@code org.apache.commons.logging.LogFactory} checks whether this class
054 * can be supported by the current JVM, and if so then uses it to store
055 * references to the {@code LogFactory} implementation it loads
056 * (rather than using a standard Hashtable instance).
057 * Having this class used instead of {@code Hashtable} solves
058 * certain issues related to dynamic reloading of applications in J2EE-style
059 * environments. However this class requires Java 1.3 or later (due to its use
060 * of {@code java.lang.ref.WeakReference} and associates).
061 * And by the way, this extends {@code Hashtable} rather than {@code HashMap}
062 * for backwards compatibility reasons. See the documentation
063 * for method {@code LogFactory.createFactoryStore} for more details.
064 * <p>
065 * The reason all this is necessary is due to a issue which
066 * arises during hot deploy in a J2EE-like containers.
067 * Each component running in the container owns one or more class loaders; when
068 * the component loads a LogFactory instance via the component class loader
069 * a reference to it gets stored in the static LogFactory.factories member,
070 * keyed by the component's class loader so different components don't
071 * stomp on each other. When the component is later unloaded, the container
072 * sets the component's class loader to null with the intent that all the
073 * component's classes get garbage-collected. However there's still a
074 * reference to the component's class loader from a key in the "global"
075 * {@code LogFactory}'s factories member! If {@code LogFactory.release()}
076 * is called whenever component is unloaded, the class loaders will be correctly
077 * garbage collected; this <i>should</i> be done by any container that
078 * bundles commons-logging by default. However, holding the class loader
079 * references weakly ensures that the class loader will be garbage collected
080 * without the container performing this step.
081 * <p>
082 * <strong>Limitations:</strong>
083 * There is still one (unusual) scenario in which a component will not
084 * be correctly unloaded without an explicit release. Though weak references
085 * are used for its keys, it is necessary to use strong references for its values.
086 * <p>
087 * If the abstract class {@code LogFactory} is
088 * loaded by the container class loader but a subclass of
089 * {@code LogFactory} [LogFactory1] is loaded by the component's
090 * class loader and an instance stored in the static map associated with the
091 * base LogFactory class, then there is a strong reference from the LogFactory
092 * class to the LogFactory1 instance (as normal) and a strong reference from
093 * the LogFactory1 instance to the component class loader via
094 * {@code getClass().getClassLoader()}. This chain of references will prevent
095 * collection of the child class loader.
096 * <p>
097 * Such a situation occurs when the commons-logging.jar is
098 * loaded by a parent class loader (e.g. a server level class loader in a
099 * servlet container) and a custom {@code LogFactory} implementation is
100 * loaded by a child class loader (e.g. a web app class loader).
101 * <p>
102 * To avoid this scenario, ensure
103 * that any custom LogFactory subclass is loaded by the same class loader as
104 * the base {@code LogFactory}. Creating custom LogFactory subclasses is,
105 * however, rare. The standard LogFactoryImpl class should be sufficient
106 * for most or all users.
107 *
108 * @since 1.1
109 * @deprecated No longer used.
110 */
111@Deprecated
112public final class WeakHashtable extends Hashtable {
113
114    /** Entry implementation */
115    private final static class Entry implements Map.Entry {
116
117        private final Object key;
118        private final Object value;
119
120        private Entry(final Object key, final Object value) {
121            this.key = key;
122            this.value = value;
123        }
124
125        @Override
126        public boolean equals(final Object o) {
127            boolean result = false;
128            if (o instanceof Map.Entry) {
129                final Map.Entry entry = (Map.Entry) o;
130                result =    (getKey()==null ?
131                                            entry.getKey() == null :
132                                            getKey().equals(entry.getKey())) &&
133                            (getValue()==null ?
134                                            entry.getValue() == null :
135                                            getValue().equals(entry.getValue()));
136            }
137            return result;
138        }
139
140        @Override
141        public Object getKey() {
142            return key;
143        }
144
145        @Override
146        public Object getValue() {
147            return value;
148        }
149
150        @Override
151        public int hashCode() {
152            return (getKey()==null ? 0 : getKey().hashCode()) ^
153                (getValue()==null ? 0 : getValue().hashCode());
154        }
155
156        @Override
157        public Object setValue(final Object value) {
158            throw new UnsupportedOperationException("Entry.setValue is not supported.");
159        }
160    }
161
162    /** Wrapper giving correct symantics for equals and hash code */
163    private final static class Referenced {
164
165        private final WeakReference reference;
166        private final int           hashCode;
167
168        /**
169         *
170         * @throws NullPointerException if referant is {@code null}
171         */
172        private Referenced(final Object referant) {
173            reference = new WeakReference(referant);
174            // Calc a permanent hashCode so calls to Hashtable.remove()
175            // work if the WeakReference has been cleared
176            hashCode  = referant.hashCode();
177        }
178
179        /**
180         *
181         * @throws NullPointerException if key is {@code null}
182         */
183        private Referenced(final Object key, final ReferenceQueue queue) {
184            reference = new WeakKey(key, queue, this);
185            // Calc a permanent hashCode so calls to Hashtable.remove()
186            // work if the WeakReference has been cleared
187            hashCode  = key.hashCode();
188
189        }
190
191        @Override
192        public boolean equals(final Object o) {
193            boolean result = false;
194            if (o instanceof Referenced) {
195                final Referenced otherKey = (Referenced) o;
196                final Object thisKeyValue = getValue();
197                final Object otherKeyValue = otherKey.getValue();
198                if (thisKeyValue == null) {
199                    result = otherKeyValue == null;
200
201                    // Since our hash code was calculated from the original
202                    // non-null referant, the above check breaks the
203                    // hash code/equals contract, as two cleared Referenced
204                    // objects could test equal but have different hash codes.
205                    // We can reduce (not eliminate) the chance of this
206                    // happening by comparing hash codes.
207                    result = result && this.hashCode() == otherKey.hashCode();
208                    // In any case, as our c'tor does not allow null referants
209                    // and Hashtable does not do equality checks between
210                    // existing keys, normal hashtable operations should never
211                    // result in an equals comparison between null referants
212                }
213                else
214                {
215                    result = thisKeyValue.equals(otherKeyValue);
216                }
217            }
218            return result;
219        }
220
221        private Object getValue() {
222            return reference.get();
223        }
224
225        @Override
226        public int hashCode() {
227            return hashCode;
228        }
229    }
230
231    /**
232     * WeakReference subclass that holds a hard reference to an
233     * associated {@code value} and also makes accessible
234     * the Referenced object holding it.
235     */
236    private final static class WeakKey extends WeakReference {
237
238        private final Referenced referenced;
239
240        private WeakKey(final Object key,
241                        final ReferenceQueue queue,
242                        final Referenced referenced) {
243            super(key, queue);
244            this.referenced = referenced;
245        }
246
247        private Referenced getReferenced() {
248            return referenced;
249        }
250     }
251
252    /** Serializable version identifier. */
253    private static final long serialVersionUID = -1546036869799732453L;
254
255    /**
256     * The maximum number of times put() or remove() can be called before
257     * the map will be purged of all cleared entries.
258     */
259    private static final int MAX_CHANGES_BEFORE_PURGE = 100;
260
261    /**
262     * The maximum number of times put() or remove() can be called before
263     * the map will be purged of one cleared entry.
264     */
265    private static final int PARTIAL_PURGE_COUNT     = 10;
266
267    /** ReferenceQueue we check for GC'd keys. */
268    private final transient ReferenceQueue queue = new ReferenceQueue();
269
270    /** Counter used to control how often we purge gc'd entries. */
271    private int changeCount;
272
273    /**
274     * Constructs a WeakHashtable with the Hashtable default
275     * capacity and load factor.
276     */
277    public WeakHashtable() {}
278
279    /**
280     *@see Hashtable
281     */
282    @Override
283    public boolean containsKey(final Object key) {
284        // purge should not be required
285        final Referenced referenced = new Referenced(key);
286        return super.containsKey(referenced);
287    }
288
289    /**
290     *@see Hashtable
291     */
292    @Override
293    public Enumeration elements() {
294        purge();
295        return super.elements();
296    }
297
298    /**
299     *@see Hashtable
300     */
301    @Override
302    public Set entrySet() {
303        purge();
304        final Set referencedEntries = super.entrySet();
305        final Set unreferencedEntries = new HashSet();
306        for (final Object referencedEntry : referencedEntries) {
307            final Map.Entry entry = (Map.Entry) referencedEntry;
308            final Referenced referencedKey = (Referenced) entry.getKey();
309            final Object key = referencedKey.getValue();
310            final Object value = entry.getValue();
311            if (key != null) {
312                final Entry dereferencedEntry = new Entry(key, value);
313                unreferencedEntries.add(dereferencedEntry);
314            }
315        }
316        return unreferencedEntries;
317    }
318
319    /**
320     *@see Hashtable
321     */
322    @Override
323    public Object get(final Object key) {
324        // for performance reasons, no purge
325        final Referenced referenceKey = new Referenced(key);
326        return super.get(referenceKey);
327    }
328
329    /**
330     *@see Hashtable
331     */
332    @Override
333    public boolean isEmpty() {
334        purge();
335        return super.isEmpty();
336    }
337
338    /**
339     *@see Hashtable
340     */
341    @Override
342    public Enumeration keys() {
343        purge();
344        final Enumeration enumer = super.keys();
345        return new Enumeration() {
346            @Override
347            public boolean hasMoreElements() {
348                return enumer.hasMoreElements();
349            }
350            @Override
351            public Object nextElement() {
352                 final Referenced nextReference = (Referenced) enumer.nextElement();
353                 return nextReference.getValue();
354            }
355        };
356    }
357
358    /**
359     *@see Hashtable
360     */
361    @Override
362    public Set keySet() {
363        purge();
364        final Set referencedKeys = super.keySet();
365        final Set unreferencedKeys = new HashSet();
366        for (final Object referencedKey : referencedKeys) {
367            final Referenced referenceKey = (Referenced) referencedKey;
368            final Object keyValue = referenceKey.getValue();
369            if (keyValue != null) {
370                unreferencedKeys.add(keyValue);
371            }
372        }
373        return unreferencedKeys;
374    }
375
376    /**
377     * Purges all entries whose wrapped keys
378     * have been garbage collected.
379     */
380    private void purge() {
381        final List toRemove = new ArrayList();
382        synchronized (queue) {
383            WeakKey key;
384            while ((key = (WeakKey) queue.poll()) != null) {
385                toRemove.add(key.getReferenced());
386            }
387        }
388
389        // LOGGING-119: do the actual removal of the keys outside the sync block
390        // to prevent deadlock scenarios as purge() may be called from
391        // non-synchronized methods too
392        final int size = toRemove.size();
393        for (int i = 0; i < size; i++) {
394            super.remove(toRemove.get(i));
395        }
396    }
397
398    /**
399     * Purges one entry whose wrapped key
400     * has been garbage collected.
401     */
402    private void purgeOne() {
403        synchronized (queue) {
404            final WeakKey key = (WeakKey) queue.poll();
405            if (key != null) {
406                super.remove(key.getReferenced());
407            }
408        }
409    }
410
411    /**
412     *@see Hashtable
413     */
414    @Override
415    public synchronized Object put(final Object key, final Object value) {
416        // check for nulls, ensuring semantics match superclass
417        Objects.requireNonNull(key, "key");
418        Objects.requireNonNull(value, "value");
419
420        // for performance reasons, only purge every
421        // MAX_CHANGES_BEFORE_PURGE times
422        if (changeCount++ > MAX_CHANGES_BEFORE_PURGE) {
423            purge();
424            changeCount = 0;
425        }
426        // do a partial purge more often
427        else if (changeCount % PARTIAL_PURGE_COUNT == 0) {
428            purgeOne();
429        }
430
431        final Referenced keyRef = new Referenced(key, queue);
432        return super.put(keyRef, value);
433    }
434
435    /**
436     *@see Hashtable
437     */
438    @Override
439    public void putAll(final Map t) {
440        if (t != null) {
441            final Set entrySet = t.entrySet();
442            for (final Object element : entrySet) {
443                final Map.Entry entry = (Map.Entry) element;
444                put(entry.getKey(), entry.getValue());
445            }
446        }
447    }
448
449    /**
450     * @see Hashtable
451     */
452    @Override
453    protected void rehash() {
454        // purge here to save the effort of rehashing dead entries
455        purge();
456        super.rehash();
457    }
458
459    /**
460     *@see Hashtable
461     */
462    @Override
463    public synchronized Object remove(final Object key) {
464        // for performance reasons, only purge every
465        // MAX_CHANGES_BEFORE_PURGE times
466        if (changeCount++ > MAX_CHANGES_BEFORE_PURGE) {
467            purge();
468            changeCount = 0;
469        }
470        // do a partial purge more often
471        else if (changeCount % PARTIAL_PURGE_COUNT == 0) {
472            purgeOne();
473        }
474        return super.remove(new Referenced(key));
475    }
476
477    /**
478     *@see Hashtable
479     */
480    @Override
481    public int size() {
482        purge();
483        return super.size();
484    }
485
486    /**
487     *@see Hashtable
488     */
489    @Override
490    public String toString() {
491        purge();
492        return super.toString();
493    }
494
495    /**
496     *@see Hashtable
497     */
498    @Override
499    public Collection values() {
500        purge();
501        return super.values();
502    }
503}