src/test/org/apache/commons/collections/ReferenceMap.java

/*
 *  Copyright 2001-2004 The Apache Software Foundation
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */
package org.apache.commons.collections;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.lang.ref.Reference;
import java.lang.ref.ReferenceQueue;
import java.lang.ref.SoftReference;
import java.lang.ref.WeakReference;
import java.util.AbstractCollection;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

import org.apache.commons.collections.keyvalue.DefaultMapEntry;

/**
 *  Hash-based {@link Map} implementation that allows
 *  mappings to be removed by the garbage collector.<p>
 *
 *  When you construct a <code>ReferenceMap</code>, you can 
 *  specify what kind of references are used to store the
 *  map's keys and values.  If non-hard references are 
 *  used, then the garbage collector can remove mappings
 *  if a key or value becomes unreachable, or if the 
 *  JVM's memory is running low.  For information on how
 *  the different reference types behave, see
 *  {@link Reference}.<p>
 *
 *  Different types of references can be specified for keys
 *  and values.  The keys can be configured to be weak but
 *  the values hard, in which case this class will behave
 *  like a <a href="http://java.sun.com/j2se/1.4/docs/api/java/util/WeakHashMap.html">
 *  <code>WeakHashMap</code></a>.  However, you
 *  can also specify hard keys and weak values, or any other
 *  combination.  The default constructor uses hard keys
 *  and soft values, providing a memory-sensitive cache.<p>
 *
 *  The algorithms used are basically the same as those
 *  in {@link java.util.HashMap}.  In particular, you 
 *  can specify a load factor and capacity to suit your
 *  needs.  All optional {@link Map} operations are 
 *  supported.<p>
 *
 *  However, this {@link Map} implementation does <I>not</I>
 *  allow null elements.  Attempting to add a null key or
 *  or a null value to the map will raise a 
 *  <code>NullPointerException</code>.<p>
 *
 *  As usual, this implementation is not synchronized.  You
 *  can use {@link java.util.Collections#synchronizedMap} to 
 *  provide synchronized access to a <code>ReferenceMap</code>.
 *
 * @see java.lang.ref.Reference
 * 
 * @deprecated Moved to map subpackage. Due to be removed in v4.0.
 * @since Commons Collections 2.1
 * @version $Revision: 1.1 $ $Date: 2004/05/10 19:52:42 $
 * 
 * @author Paul Jack
 */
public class ReferenceMap extends AbstractMap {

    /**
     *  For serialization.
     */
    final private static long serialVersionUID = -3370601314380922368L;


    /**
     *  Constant indicating that hard references should be used.
     */
    final public static int HARD = 0;


    /**
     *  Constant indicating that soft references should be used.
     */
    final public static int SOFT = 1;


    /**
     *  Constant indicating that weak references should be used.
     */
    final public static int WEAK = 2;


    // --- serialized instance variables:


    /**
     *  The reference type for keys.  Must be HARD, SOFT, WEAK.
     *  Note: I originally marked this field as final, but then this class
     *   didn't compile under JDK1.2.2.
     *  @serial
     */
    private int keyType;


    /**
     *  The reference type for values.  Must be HARD, SOFT, WEAK.
     *  Note: I originally marked this field as final, but then this class
     *   didn't compile under JDK1.2.2.
     *  @serial
     */
    private int valueType;


    /**
     *  The threshold variable is calculated by multiplying
     *  table.length and loadFactor.  
     *  Note: I originally marked this field as final, but then this class
     *   didn't compile under JDK1.2.2.
     *  @serial
     */
    private float loadFactor;
    
    /**
     * Should the value be automatically purged when the associated key has been collected?
     */
    private boolean purgeValues = false;


    // -- Non-serialized instance variables

    /**
     *  ReferenceQueue used to eliminate stale mappings.
     *  See purge.
     */
    private transient ReferenceQueue queue = new ReferenceQueue();


    /**
     *  The hash table.  Its length is always a power of two.  
     */
    private transient Entry[] table;


    /**
     *  Number of mappings in this map.
     */
    private transient int size;


    /**
     *  When size reaches threshold, the map is resized.  
     *  See resize().
     */
    private transient int threshold;


    /**
     *  Number of times this map has been modified.
     */
    private transient volatile int modCount;


    /**
     *  Cached key set.  May be null if key set is never accessed.
     */
    private transient Set keySet;


    /**
     *  Cached entry set.  May be null if entry set is never accessed.
     */
    private transient Set entrySet;


    /**
     *  Cached values.  May be null if values() is never accessed.
     */
    private transient Collection values;


    /**
     *  Constructs a new <code>ReferenceMap</code> that will
     *  use hard references to keys and soft references to values.
     */
    public ReferenceMap() {
        this(HARD, SOFT);
    }

    /**
     *  Constructs a new <code>ReferenceMap</code> that will
     *  use the specified types of references.
     *
     *  @param keyType  the type of reference to use for keys;
     *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
     *  @param valueType  the type of reference to use for values;
     *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
     *  @param purgeValues should the value be automatically purged when the 
     *   key is garbage collected 
     */
    public ReferenceMap(int keyType, int valueType, boolean purgeValues) {
        this(keyType, valueType);
        this.purgeValues = purgeValues;
    }

    /**
     *  Constructs a new <code>ReferenceMap</code> that will
     *  use the specified types of references.
     *
     *  @param keyType  the type of reference to use for keys;
     *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
     *  @param valueType  the type of reference to use for values;
     *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
     */
    public ReferenceMap(int keyType, int valueType) {
        this(keyType, valueType, 16, 0.75f);
    }

    /**
     *  Constructs a new <code>ReferenceMap</code> with the
     *  specified reference types, load factor and initial
     *  capacity.
     *
     *  @param keyType  the type of reference to use for keys;
     *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
     *  @param valueType  the type of reference to use for values;
     *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
     *  @param capacity  the initial capacity for the map
     *  @param loadFactor  the load factor for the map
     *  @param purgeValues should the value be automatically purged when the 
     *   key is garbage collected 
     */
    public ReferenceMap(
                        int keyType, 
                        int valueType, 
                        int capacity, 
                        float loadFactor, 
                        boolean purgeValues) {
        this(keyType, valueType, capacity, loadFactor);
        this.purgeValues = purgeValues;
    }

    /**
     *  Constructs a new <code>ReferenceMap</code> with the
     *  specified reference types, load factor and initial
     *  capacity.
     *
     *  @param keyType  the type of reference to use for keys;
     *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
     *  @param valueType  the type of reference to use for values;
     *   must be {@link #HARD}, {@link #SOFT}, {@link #WEAK}
     *  @param capacity  the initial capacity for the map
     *  @param loadFactor  the load factor for the map
     */
    public ReferenceMap(int keyType, int valueType, int capacity, float loadFactor) {
        super();

        verify("keyType", keyType);
        verify("valueType", valueType);

        if (capacity <= 0) {
            throw new IllegalArgumentException("capacity must be positive");
        }
        if ((loadFactor <= 0.0f) || (loadFactor >= 1.0f)) {
            throw new IllegalArgumentException("Load factor must be greater than 0 and less than 1.");
        }

        this.keyType = keyType;
        this.valueType = valueType;

        int v = 1;
        while (v < capacity) v *= 2;

        this.table = new Entry[v];
        this.loadFactor = loadFactor;
        this.threshold = (int)(v * loadFactor);
    }


    // used by constructor
    private static void verify(String name, int type) {
        if ((type < HARD) || (type > WEAK)) {
            throw new IllegalArgumentException(name + 
               " must be HARD, SOFT, WEAK.");
        }
    }


    /**
     *  Writes this object to the given output stream.
     *
     *  @param out  the output stream to write to
     *  @throws IOException  if the stream raises it
     */
    private void writeObject(ObjectOutputStream out) throws IOException {
        out.defaultWriteObject();
        out.writeInt(table.length);

        // Have to use null-terminated list because size might shrink
        // during iteration

        for (Iterator iter = entrySet().iterator(); iter.hasNext();) {
            Map.Entry entry = (Map.Entry)iter.next();
            out.writeObject(entry.getKey());
            out.writeObject(entry.getValue());
        }
        out.writeObject(null);
    }


    /**
     *  Reads the contents of this object from the given input stream.
     *
     *  @param inp  the input stream to read from
     *  @throws IOException  if the stream raises it
     *  @throws ClassNotFoundException  if the stream raises it
     */
    private void readObject(ObjectInputStream inp) throws IOException, ClassNotFoundException {
        inp.defaultReadObject();
        table = new Entry[inp.readInt()];
        threshold = (int)(table.length * loadFactor);
        queue = new ReferenceQueue();
        Object key = inp.readObject();
        while (key != null) {
            Object value = inp.readObject();
            put(key, value);
            key = inp.readObject();
        }
    }


    /**
     *  Constructs a reference of the given type to the given 
     *  referent.  The reference is registered with the queue
     *  for later purging.
     *
     *  @param type  HARD, SOFT or WEAK
     *  @param referent  the object to refer to
     *  @param hash  the hash code of the <I>key</I> of the mapping;
     *    this number might be different from referent.hashCode() if
     *    the referent represents a value and not a key
     */
    private Object toReference(int type, Object referent, int hash) {
        switch (type) {
            case HARD: return referent;
            case SOFT: return new SoftRef(hash, referent, queue);
            case WEAK: return new WeakRef(hash, referent, queue);
            default: throw new Error();
        }
    }


    /**
     *  Returns the entry associated with the given key.
     *
     *  @param key  the key of the entry to look up
     *  @return  the entry associated with that key, or null
     *    if the key is not in this map
     */
    private Entry getEntry(Object key) {
        if (key == null) return null;
        int hash = key.hashCode();
        int index = indexFor(hash);
        for (Entry entry = table[index]; entry != null; entry = entry.next) {
            if ((entry.hash == hash) && key.equals(entry.getKey())) {
                return entry;
            }
        }
        return null;
    }


    /**
     *  Converts the given hash code into an index into the
     *  hash table.
     */
    private int indexFor(int hash) {
        // mix the bits to avoid bucket collisions...
        hash += ~(hash << 15);
        hash ^= (hash >>> 10);
        hash += (hash << 3);
        hash ^= (hash >>> 6);
        hash += ~(hash << 11);
        hash ^= (hash >>> 16);
        return hash & (table.length - 1);
    }



    /**
     *  Resizes this hash table by doubling its capacity.
     *  This is an expensive operation, as entries must
     *  be copied from the old smaller table to the new 
     *  bigger table.
     */
    private void resize() {
        Entry[] old = table;
        table = new Entry[old.length * 2];

        for (int i = 0; i < old.length; i++) {
            Entry next = old[i];
            while (next != null) {
                Entry entry = next;
                next = next.next;
                int index = indexFor(entry.hash);
                entry.next = table[index];
                table[index] = entry;
            }
            old[i] = null;
        }
        threshold = (int)(table.length * loadFactor);
    }



    /**
     * Purges stale mappings from this map.
     * <p>
     * Ordinarily, stale mappings are only removed during
     * a write operation, although this method is called for both
     * read and write operations to maintain a consistent state.
     * <p>
     * Note that this method is not synchronized!  Special
     * care must be taken if, for instance, you want stale
     * mappings to be removed on a periodic basis by some
     * background thread.
     */
    private void purge() {
        Reference ref = queue.poll();
        while (ref != null) {
            purge(ref);
            ref = queue.poll();
        }
    }


    private void purge(Reference ref) {
        // The hashCode of the reference is the hashCode of the
        // mapping key, even if the reference refers to the 
        // mapping value...
        int hash = ref.hashCode();
        int index = indexFor(hash);
        Entry previous = null;
        Entry entry = table[index];
        while (entry != null) {
            if (entry.purge(ref)) {
                if (previous == null) table[index] = entry.next;
                else previous.next = entry.next;
                this.size--;
                return;
            }
            previous = entry;
            entry = entry.next;
        }

    }


    /**
     *  Returns the size of this map.
     *
     *  @return  the size of this map
     */
    public int size() {
        purge();
        return size;
    }


    /**
     *  Returns <code>true</code> if this map is empty.
     *
     *  @return <code>true</code> if this map is empty
     */
    public boolean isEmpty() {
        purge();
        return size == 0;
    }


    /**
     *  Returns <code>true</code> if this map contains the given key.
     *
     *  @return true if the given key is in this map
     */
    public boolean containsKey(Object key) {
        purge();
        Entry entry = getEntry(key);
        if (entry == null) return false;
        return entry.getValue() != null;
    }


    /**
     *  Returns the value associated with the given key, if any.
     *
     *  @return the value associated with the given key, or <code>null</code>
     *   if the key maps to no value
     */
    public Object get(Object key) {
        purge();
        Entry entry = getEntry(key);
        if (entry == null) return null;
        return entry.getValue();
    }


    /**
     *  Associates the given key with the given value.<p>
     *  Neither the key nor the value may be null.
     *
     *  @param key  the key of the mapping
     *  @param value  the value of the mapping
     *  @return  the last value associated with that key, or 
     *   null if no value was associated with the key
     *  @throws NullPointerException if either the key or value
     *   is null
     */
    public Object put(Object key, Object value) {
        if (key == null) throw new NullPointerException("null keys not allowed");
        if (value == null) throw new NullPointerException("null values not allowed");

        purge();
        if (size + 1 > threshold) resize();

        int hash = key.hashCode();
        int index = indexFor(hash);
        Entry entry = table[index];
        while (entry != null) {
            if ((hash == entry.hash) && key.equals(entry.getKey())) {
                Object result = entry.getValue();
                entry.setValue(value);
                return result;
            }
            entry = entry.next;
        }
        this.size++; 
        modCount++;
        key = toReference(keyType, key, hash);
        value = toReference(valueType, value, hash);
        table[index] = new Entry(key, hash, value, table[index]);
        return null;
    }


    /**
     *  Removes the key and its associated value from this map.
     *
     *  @param key  the key to remove
     *  @return the value associated with that key, or null if
     *   the key was not in the map
     */
    public Object remove(Object key) {
        if (key == null) return null;
        purge();
        int hash = key.hashCode();
        int index = indexFor(hash);
        Entry previous = null;
        Entry entry = table[index];
        while (entry != null) {
            if ((hash == entry.hash) && key.equals(entry.getKey())) {
                if (previous == null) table[index] = entry.next;
                else previous.next = entry.next;
                this.size--;
                modCount++;
                return entry.getValue();
            }
            previous = entry;
            entry = entry.next;
        }
        return null;
    }


    /**
     *  Clears this map.
     */
    public void clear() {
        Arrays.fill(table, null);
        size = 0;
        while (queue.poll() != null); // drain the queue
    }


    /**
     *  Returns a set view of this map's entries.
     *
     *  @return a set view of this map's entries
     */
    public Set entrySet() {
        if (entrySet != null) {
            return entrySet;
        } 
        entrySet = new AbstractSet() {
            public int size() {
                return ReferenceMap.this.size();
            }

            public void clear() {
                ReferenceMap.this.clear();
            }

            public boolean contains(Object o) {
                if (o == null) return false;
                if (!(o instanceof Map.Entry)) return false;
                Map.Entry e = (Map.Entry)o;
                Entry e2 = getEntry(e.getKey());
                return (e2 != null) && e.equals(e2);
            }

            public boolean remove(Object o) {
                boolean r = contains(o);
                if (r) {
                    Map.Entry e = (Map.Entry)o;
                    ReferenceMap.this.remove(e.getKey());
                }
                return r;
            }

            public Iterator iterator() {
                return new EntryIterator();
            }

            public Object[] toArray() {
                return toArray(new Object[0]);
            }

            public Object[] toArray(Object[] arr) {
                ArrayList list = new ArrayList();
                Iterator iterator = iterator();
                while (iterator.hasNext()) {
                    Entry e = (Entry)iterator.next();
                    list.add(new DefaultMapEntry(e.getKey(), e.getValue()));
                }
                return list.toArray(arr);
            }
        };
        return entrySet;
    }


    /**
     *  Returns a set view of this map's keys.
     *
     *  @return a set view of this map's keys
     */
    public Set keySet() {
        if (keySet != null) return keySet;
        keySet = new AbstractSet() {
            public int size() {
                return ReferenceMap.this.size();
            }

            public Iterator iterator() {
                return new KeyIterator();
            }

            public boolean contains(Object o) {
                return containsKey(o);
            }


            public boolean remove(Object o) {
                Object r = ReferenceMap.this.remove(o);
                return r != null;
            }

            public void clear() {
                ReferenceMap.this.clear();
            }

            public Object[] toArray() {
                return toArray(new Object[0]);
            }

            public Object[] toArray(Object[] array) {
                Collection c = new ArrayList(size());
                for (Iterator it = iterator(); it.hasNext(); ) {
                    c.add(it.next());
                }
                return c.toArray(array);
            }
        };
        return keySet;
    }


    /**
     *  Returns a collection view of this map's values.
     *
     *  @return a collection view of this map's values.
     */
    public Collection values() {
        if (values != null) return values;
        values = new AbstractCollection()  {
            public int size() {
                return ReferenceMap.this.size();
            }

            public void clear() {
                ReferenceMap.this.clear();
            }

            public Iterator iterator() {
                return new ValueIterator();
            }

            public Object[] toArray() {
                return toArray(new Object[0]);
            }

            public Object[] toArray(Object[] array) {
                Collection c = new ArrayList(size());
                for (Iterator it = iterator(); it.hasNext(); ) {
                    c.add(it.next());
                }
                return c.toArray(array);
            }
        };
        return values;
    }


    // If getKey() or getValue() returns null, it means
    // the mapping is stale and should be removed.
    private class Entry implements Map.Entry, KeyValue {

        Object key;
        Object value;
        int hash;
        Entry next;


        public Entry(Object key, int hash, Object value, Entry next) {
            this.key = key;
            this.hash = hash;
            this.value = value;
            this.next = next;
        }


        public Object getKey() {
            return (keyType > HARD) ? ((Reference)key).get() : key;
        }


        public Object getValue() {
            return (valueType > HARD) ? ((Reference)value).get() : value;
        }


        public Object setValue(Object object) {
            Object old = getValue();
            if (valueType > HARD) ((Reference)value).clear();
            value = toReference(valueType, object, hash);
            return old;
        }


        public boolean equals(Object o) {
            if (o == null) return false;
            if (o == this) return true;
            if (!(o instanceof Map.Entry)) return false;
            
            Map.Entry entry = (Map.Entry)o;
            Object key = entry.getKey();
            Object value = entry.getValue();
            if ((key == null) || (value == null)) return false;
            return key.equals(getKey()) && value.equals(getValue());
        }


        public int hashCode() {
            Object v = getValue();
            return hash ^ ((v == null) ? 0 : v.hashCode());
        }


        public String toString() {
            return getKey() + "=" + getValue();
        }


        boolean purge(Reference ref) {
            boolean r = (keyType > HARD) && (key == ref);
            r = r || ((valueType > HARD) && (value == ref));
            if (r) {
                if (keyType > HARD) ((Reference)key).clear();
                if (valueType > HARD) {
                    ((Reference)value).clear();
                } else if (purgeValues) {
                    value = null;
                }
            }
            return r;
        }
    }


    private class EntryIterator implements Iterator {
        // These fields keep track of where we are in the table.
        int index;
        Entry entry;
        Entry previous;

        // These Object fields provide hard references to the
        // current and next entry; this assures that if hasNext()
        // returns true, next() will actually return a valid element.
        Object nextKey, nextValue;
        Object currentKey, currentValue;

        int expectedModCount;


        public EntryIterator() {
            index = (size() != 0 ? table.length : 0);
            // have to do this here!  size() invocation above
            // may have altered the modCount.
            expectedModCount = modCount;
        }


        public boolean hasNext() {
            checkMod();
            while (nextNull()) {
                Entry e = entry;
                int i = index;
                while ((e == null) && (i > 0)) {
                    i--;
                    e = table[i];
                }
                entry = e;
                index = i;
                if (e == null) {
                    currentKey = null;
                    currentValue = null;
                    return false;
                }
                nextKey = e.getKey();
                nextValue = e.getValue();
                if (nextNull()) entry = entry.next;
            }
            return true;
        }


        private void checkMod() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
        }


        private boolean nextNull() {
            return (nextKey == null) || (nextValue == null);
        }

        protected Entry nextEntry() {    
            checkMod();
            if (nextNull() && !hasNext()) throw new NoSuchElementException();
            previous = entry;
            entry = entry.next;
            currentKey = nextKey;
            currentValue = nextValue;
            nextKey = null;
            nextValue = null;
            return previous;
        }


        public Object next() {
            return nextEntry();
        }


        public void remove() {
            checkMod();
            if (previous == null) throw new IllegalStateException();
            ReferenceMap.this.remove(currentKey);
            previous = null;
            currentKey = null;
            currentValue = null;
            expectedModCount = modCount;
        }

    }


    private class ValueIterator extends EntryIterator {
        public Object next() {
            return nextEntry().getValue();
        }
    }


    private class KeyIterator extends EntryIterator {
        public Object next() {
            return nextEntry().getKey();
        }
    }



    // These two classes store the hashCode of the key of
    // of the mapping, so that after they're dequeued a quick
    // lookup of the bucket in the table can occur.


    private static class SoftRef extends SoftReference {
        private int hash;


        public SoftRef(int hash, Object r, ReferenceQueue q) {
            super(r, q);
            this.hash = hash;
        }


        public int hashCode() {
            return hash;
        }
    }


    private static class WeakRef extends WeakReference {
        private int hash;


        public WeakRef(int hash, Object r, ReferenceQueue q) {
            super(r, q);
            this.hash = hash;
        }


        public int hashCode() {
            return hash;
        }
    }


}