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 */
017package org.apache.xbean.propertyeditor;
018
019import java.lang.ref.Reference;
020import java.lang.ref.WeakReference;
021import java.lang.ref.ReferenceQueue;
022import java.util.Collection;
023import java.util.Map;
024import java.util.Set;
025
026/**
027 * Streamlined version of a WeakIdentityHashMap. Provides Identity semantics with 
028 * Weak References to keys. This allows proxies to be GC'ed when no longer referenced
029 * by clients. <code>BasicProxymanager.destroyProxy()</code> need not be invoked when a
030 * proxy is no longer needed. Note that this is not a full Map implementation. 
031 * The iteration and collection capabilities of Map have been discarded to keep the 
032 * implementation lightweight.
033 * <p>
034 * Much of this code was cribbed from the Commons Collection 3.1 implementation of 
035 * <code>ReferenceIdentityMap</code> and <code>AbstractReferenceMap</code>.
036 */
037public class ReferenceIdentityMap implements Map {
038
039    /** The default capacity to use. Always use a power of 2!!! */
040    private static final int DEFAULT_CAPACITY = 16;
041    /** The default load factor to use */
042    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
043    /** The maximum capacity allowed */
044    private static final int MAXIMUM_CAPACITY = 1 << 30;
045    
046    /** Load factor, normally 0.75 */
047    private float loadFactor;
048    /** The size of the map */
049    private transient int size;
050    /** Map entries */
051    private transient ReferenceEntry[] data;
052    /** Size at which to rehash */
053    private transient int threshold;
054
055    /**
056     * ReferenceQueue used to eliminate GC'ed entries.
057     */
058    private ReferenceQueue purgeQueue;
059
060    public ReferenceIdentityMap() {
061        this.loadFactor = DEFAULT_LOAD_FACTOR;
062        this.data = new ReferenceEntry[DEFAULT_CAPACITY];
063        this.threshold = calculateThreshold(DEFAULT_CAPACITY, loadFactor);
064        this.purgeQueue = new ReferenceQueue();
065    }
066    
067    /**
068     * Gets the size of the map.
069     * 
070     * @return the size
071     */
072    public int size() {
073        purge();
074        return size;
075    }
076
077    /**
078     * Checks whether the map is currently empty.
079     * 
080     * @return true if the map is currently size zero
081     */
082    public boolean isEmpty() {
083        purge();
084        return (size == 0);
085    }
086
087    /**
088     * Checks whether the map contains the specified key.
089     * 
090     * @param key  the key to search for
091     * @return true if the map contains the key
092     */
093    public boolean containsKey(Object key) {
094        purge();
095        ReferenceEntry entry = getEntry(key);
096        if (entry == null) {
097            return false;
098        }
099        return (entry.getValue() != null);
100    }
101
102    /**
103     * Checks whether the map contains the specified value.
104     * 
105     * @param value  the value to search for
106     * @return true if the map contains the value
107     */
108    public boolean containsValue(Object value) {
109        purge();
110        if (value == null || size == 0) {
111            return false;
112        }
113        ReferenceEntry [] table = data;
114        for (int i = 0; i < table.length; i++) {
115            ReferenceEntry entry = table[i];
116            while (entry != null) {
117                if (value.equals(entry.getValue())) {
118                    return true;
119                }
120                entry = entry.next;
121            }
122        }
123        return false;
124    }
125
126    /**
127     * Gets the value mapped to the key specified.
128     * 
129     * @param key  the key
130     * @return the mapped value, null if no match
131     */
132    public Object get(Object key) {
133        purge();
134        ReferenceEntry entry = getEntry(key);
135        if (entry == null) {
136            return null;
137        }
138        return entry.getValue();
139    }
140
141
142    /**
143     * Puts a key-value entry into this map.
144     * Neither the key nor the value may be null.
145     * 
146     * @param key  the key to add, must not be null
147     * @param value  the value to add, must not be null
148     * @return the value previously mapped to this key, null if none
149     */
150    public Object put(Object key, Object value) {
151        assert key != null: "key is null";
152        assert value != null: "value is null";
153
154        purge();
155
156        int hashCode = hash(key);
157        int index = hashIndex(hashCode, data.length);
158        ReferenceEntry entry = data[index];
159        while (entry != null) {
160            if (entry.hashCode == hashCode && key == entry.getKey()) {
161                return entry.setValue(value);
162            }
163            entry = entry.next;
164        }   
165            
166        createEntry(index, hashCode, key, value);
167        return null;
168    }
169    
170    /**
171     * Removes the specified mapping from this map.
172     * 
173     * @param key  the mapping to remove
174     * @return the value mapped to the removed key, null if key not in map
175     */
176    public Object remove(Object key) {
177        if (key == null) {
178            return null;
179        }
180        purge();
181        int hashCode = hash(key);
182        int index = hashIndex(hashCode, data.length);
183        ReferenceEntry entry = data[index];
184        ReferenceEntry previous = null;
185        while (entry != null) {
186            if (entry.hashCode == hashCode && (key == entry.getKey())) {
187                Object oldValue = entry.getValue();
188                removeEntry(entry, index, previous);
189                return oldValue;
190            }
191            previous = entry;
192            entry = entry.next;
193        }
194        return null;
195    }
196
197    /**
198     * Clears the map, resetting the size to zero and nullifying references
199     * to avoid garbage collection issues.
200     */
201    public void clear() {
202        ReferenceEntry[] data = this.data;
203        for (int i = data.length - 1; i >= 0; i--) {
204            data[i] = null;
205        }
206        size = 0;
207        while (purgeQueue.poll() != null) {} // drain the queue
208    }
209
210    public Collection values() {
211        throw new UnsupportedOperationException();
212    }
213
214    public void putAll(Map t) {
215        throw new UnsupportedOperationException();
216    }
217
218    public Set entrySet() {
219        throw new UnsupportedOperationException();
220    }
221
222    public Set keySet() {
223        throw new UnsupportedOperationException();
224    }
225
226    // end of public methods
227    
228    /**
229     * Gets the entry mapped to the key specified.
230     * @param key  the key
231     * @return the entry, null if no match
232     */
233    private ReferenceEntry getEntry(Object key) {
234        if (key == null) {
235            return null;
236        }
237        int hashCode = hash(key);
238        ReferenceEntry entry = data[hashIndex(hashCode, data.length)];
239        while (entry != null) {
240            if (entry.hashCode == hashCode && (key == entry.getKey())) {
241                return entry;
242            }
243            entry = entry.next;
244        }
245        return null;
246    }
247
248    /**
249     * Creates a new ReferenceEntry.
250     * 
251     * @param index the index into the data map
252     * @param hashCode  the hash code for the new entry
253     * @param key  the key to store
254     * @param value  the value to store
255     * @return the newly created entry
256     */
257    private ReferenceEntry createEntry(int index, int hashCode, Object key, Object value) {
258        ReferenceEntry newEntry = new ReferenceEntry(this, data[index], hashCode, key, value);
259        data[index] = newEntry;
260        size++;
261        checkCapacity();
262        return newEntry;
263    }
264
265    /**
266     * Removes an entry from the chain stored in a particular index.
267     * <p>
268     * This implementation removes the entry from the data storage table.
269     * The size is not updated.
270     * 
271     * @param entry  the entry to remove
272     * @param hashIndex  the index into the data structure
273     * @param previous  the previous entry in the chain
274     */
275    private void removeEntry(ReferenceEntry entry, int hashIndex, ReferenceEntry previous) {
276        if (previous == null) {
277            data[hashIndex] = entry.next;
278        } else {
279            previous.next = entry.next;
280        }
281        size--;
282        entry.next = null;
283        entry.clear();
284        entry.value = null;
285    }
286    
287    /**
288     * Checks the capacity of the map and enlarges it if necessary.
289     * <p>
290     * This implementation uses the threshold to check if the map needs enlarging
291     */
292    private void checkCapacity() {
293        if (size >= threshold) {
294            int newCapacity = data.length * 2;
295            if (newCapacity <= MAXIMUM_CAPACITY) {
296                ensureCapacity(newCapacity);
297            }
298        }
299    }
300    
301    /**
302     * Changes the size of the data structure to the capacity proposed.
303     * 
304     * @param newCapacity  the new capacity of the array (a power of two, less or equal to max)
305     */
306    private void ensureCapacity(int newCapacity) {
307        int oldCapacity = data.length;
308        if (newCapacity <= oldCapacity) {
309            return;
310        }
311
312        ReferenceEntry oldEntries[] = data;
313        ReferenceEntry newEntries[] = new ReferenceEntry[newCapacity];
314
315        for (int i = oldCapacity - 1; i >= 0; i--) {
316            ReferenceEntry entry = oldEntries[i];
317            if (entry != null) {
318                oldEntries[i] = null;  // gc
319                do {
320                    ReferenceEntry next = entry.next;
321                    int index = hashIndex(entry.hashCode, newCapacity);  
322                    entry.next = newEntries[index];
323                    newEntries[index] = entry;
324                    entry = next;
325                } while (entry != null);
326            }
327        }
328        threshold = calculateThreshold(newCapacity, loadFactor);
329        data = newEntries;
330    }
331
332    /**
333     * Calculates the new threshold of the map, where it will be resized.
334     * This implementation uses the load factor.
335     * 
336     * @param newCapacity  the new capacity
337     * @param factor  the load factor
338     * @return the new resize threshold
339     */
340    private int calculateThreshold(int newCapacity, float factor) {
341        return (int) (newCapacity * factor);
342    }
343
344    /**
345     * Gets the hash code for the key specified.
346     * <p>
347     * This implementation uses the identity hash code.
348     * 
349     * @param key  the key to get a hash code for
350     * @return the hash code
351     */
352    private int hash(Object key) {
353        return System.identityHashCode(key);
354    }
355
356    /**
357     * Gets the index into the data storage for the hashCode specified.
358     * This implementation uses the least significant bits of the hashCode.
359     * 
360     * @param hashCode  the hash code to use
361     * @param dataSize  the size of the data to pick a bucket from
362     * @return the bucket index
363     */
364    private int hashIndex(int hashCode, int dataSize) {
365        return hashCode & (dataSize - 1);
366    }
367
368    // Code that handles WeakReference cleanup... Invoked prior to 
369    // any operation accessing the ReferenceEntry array...
370    
371    /**
372     * Purges stale mappings from this map.
373     * <p>
374     * Note that this method is not synchronized!  Special
375     * care must be taken if, for instance, you want stale
376     * mappings to be removed on a periodic basis by some
377     * background thread.
378     */
379    private void purge() {
380        Reference entryRef = purgeQueue.poll();
381        while (entryRef != null) {
382            purge(entryRef);
383            entryRef = purgeQueue.poll();
384        }
385    }
386
387    /**
388     * Purges the specified reference.
389     * 
390     * @param purgedEntry the reference to purge
391     */
392    private void purge(Reference purgedEntry) {
393        int hash = ((ReferenceEntry)purgedEntry).hashCode;
394        int index = hashIndex(hash, data.length);
395        ReferenceEntry previous = null;
396        ReferenceEntry currentEntry = data[index];
397        while (currentEntry != null) {
398            if (currentEntry == purgedEntry) {
399                currentEntry.purged();
400                if (previous == null) {
401                    data[index] = currentEntry.next;
402                } else {
403                    previous.next = currentEntry.next;
404                }
405                this.size--;
406                return;
407            }
408            previous = currentEntry;
409            currentEntry = currentEntry.next;
410        }
411    }
412
413    /**
414     * Each entry in the Map is represented with a ReferenceEntry.
415     * <p>
416     * If getKey() or getValue() returns null, it means
417     * the mapping is stale and should be removed.
418     * 
419     * @since Commons Collections 3.1
420     */
421    private static class ReferenceEntry extends WeakReference {
422        /** The next entry in the hash chain */
423        private ReferenceEntry next;
424        /** The hash code of the key */
425        private int hashCode;
426        /** The value */
427        private Object value;
428
429        /**
430         * Creates a new entry object for the ReferenceMap.
431         * 
432         * @param parent  the parent map
433         * @param next  the next entry in the hash bucket
434         * @param hashCode  the hash code of the key
435         * @param key  the key
436         * @param value  the value
437         */
438        private ReferenceEntry(ReferenceIdentityMap parent, ReferenceEntry next, int hashCode, Object key, Object value) {
439            super(key, parent.purgeQueue);
440            this.next = next;
441            this.hashCode = hashCode;
442            this.value = value;
443        }
444
445        /**
446         * Gets the key from the entry.
447         * This method dereferences weak and soft keys and thus may return null.
448         * 
449         * @return the key, which may be null if it was garbage collected
450         */
451        private Object getKey() {
452            return this.get();
453        }
454
455        /**
456         * Gets the value from the entry.
457         * This method dereferences weak and soft value and thus may return null.
458         * 
459         * @return the value, which may be null if it was garbage collected
460         */
461        private Object getValue() {
462            return value;
463        }
464
465        /**
466         * Sets the value of the entry.
467         * 
468         * @param obj  the object to store
469         * @return the previous value
470         */
471        private Object setValue(Object obj) {
472            Object old = getValue();
473            value = obj;
474            return old;
475        }
476
477        /**
478         * Purges this entry.
479         */
480        private void purged() {
481            this.clear();
482            value = null;
483        }
484    }
485}