Soft ValueMap : SoftReference « Collections Data Structure « Java

Java
1. 2D Graphics GUI
2. 3D
3. Advanced Graphics
4. Ant
5. Apache Common
6. Chart
7. Class
8. Collections Data Structure
9. Data Type
10. Database SQL JDBC
11. Design Pattern
12. Development Class
13. EJB3
14. Email
15. Event
16. File Input Output
17. Game
18. Generics
19. GWT
20. Hibernate
21. I18N
22. J2EE
23. J2ME
24. JDK 6
25. JNDI LDAP
26. JPA
27. JSP
28. JSTL
29. Language Basics
30. Network Protocol
31. PDF RTF
32. Reflection
33. Regular Expressions
34. Scripting
35. Security
36. Servlets
37. Spring
38. Swing Components
39. Swing JFC
40. SWT JFace Eclipse
41. Threads
42. Tiny Application
43. Velocity
44. Web Services SOA
45. XML
Java Tutorial
Java Source Code / Java Documentation
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java » Collections Data Structure » SoftReferenceScreenshots 
Soft ValueMap
  

/* Copyright (C) 2003 Vladimir Roubtsov. All rights reserved.
 
 * This program and the accompanying materials are made available under
 * the terms of the Common Public License v1.0 which accompanies this distribution,
 * and is available at http://www.eclipse.org/legal/cpl-v10.html
 
 * $Id: SoftValueMap.java,v 1.1.1.1 2004/05/09 16:57:55 vlad_r Exp $
 */

import java.lang.ref.Reference;
import java.lang.ref.ReferenceQueue;
import java.lang.ref.SoftReference;
import java.util.Collection;
import java.util.Map;
import java.util.Set;

// ----------------------------------------------------------------------------
/**
 * MT-safety: an instance of this class is <I>not</I> safe for access from
 * multiple concurrent threads [even if access is done by a single thread at a
 * time]. The caller is expected to synchronize externally on an instance [the
 * implementation does not do internal synchronization for the sake of efficiency].
 * java.util.ConcurrentModificationException is not supported either.
 *
 @author (C) 2002, Vlad Roubtsov
 */
public
final class SoftValueMap implements Map
{
    // public: ................................................................

    // TODO: for caching, does clearing of entries make sense? only to save
    // entry memory -- which does not make sense if the set of key values is not
    // growing over time... on the other hand, if the key set is unbounded,
    // entry clearing is needed so that the hash table does not get polluted with
    // empty-valued entries 
    // TODO: provide mode that disables entry clearing 
    // TODO: add shrinking rehashes (is it worth it?)

    /**
     * Equivalent to <CODE>SoftValueMap(1, 1)</CODE>.
     */
    public SoftValueMap ()
    {
        this (11);
    }
    
    /**
     * Equivalent to <CODE>SoftValueMap(11, 0.75F, getClearCheckFrequency, putClearCheckFrequency)</CODE>.
     */
    public SoftValueMap (final int readClearCheckFrequency, final int writeClearCheckFrequency)
    {
        this (110.75F, readClearCheckFrequency, writeClearCheckFrequency);
    }
    
    /**
     * Constructs a SoftValueMap with specified initial capacity, load factor,
     * and cleared value removal frequencies.
     *
     @param initialCapacity initial number of hash buckets in the table
     * [may not be negative, 0 is equivalent to 1].
     @param loadFactor the load factor to use to determine rehashing points
     * [must be in (0.0, 1.0] range].
     @param readClearCheckFrequency specifies that every readClearCheckFrequency
     {@link #get} should check for and remove all mappings whose soft values
     * have been cleared by the garbage collector [may not be less than 1].
     @param writeClearCheckFrequency specifies that every writeClearCheckFrequency
     {@link #put} should check for and remove all mappings whose soft values
     * have been cleared by the garbage collector [may not be less than 1].
     */
    public SoftValueMap (int initialCapacity, final float loadFactor, final int readClearCheckFrequency, final int writeClearCheckFrequency)
    {
        if (initialCapacity < 0)
            throw new IllegalArgumentException ("negative input: initialCapacity [" + initialCapacity + "]");
        if ((loadFactor <= 0.0|| (loadFactor >= 1.0 1.0E-6))
            throw new IllegalArgumentException ("loadFactor not in (0.0, 1.0] range: " + loadFactor);
        if (readClearCheckFrequency < 1)
            throw new IllegalArgumentException ("readClearCheckFrequency not in [1, +inf) range: " + readClearCheckFrequency);
        if (writeClearCheckFrequency < 1)
            throw new IllegalArgumentException ("writeClearCheckFrequency not in [1, +inf) range: " + writeClearCheckFrequency);
        
        if (initialCapacity == 0initialCapacity = 1;
        
        m_valueReferenceQueue = new ReferenceQueue ();
        
        m_loadFactor = loadFactor;
        m_sizeThreshold = (int) (initialCapacity * loadFactor);
        
        m_readClearCheckFrequency = readClearCheckFrequency;
        m_writeClearCheckFrequency = writeClearCheckFrequency;
        
        m_buckets = new SoftEntry [initialCapacity];
    }
    
    
    // unsupported operations:
        
    public boolean equals (final Object rhs)
    {
        throw new UnsupportedOperationException ("not implemented: equals");
    }
    
    public int hashCode ()
    {
        throw new UnsupportedOperationException ("not implemented: hashCode");
    }
    
    
    /**
     * Overrides Object.toString() for debug purposes.
     */
    public String toString ()
    {
        final StringBuffer s = new StringBuffer ();
        debugDump (s);
        
        return s.toString ();
    }
    
    
    /**
     * Returns the number of key-value mappings in this map. Some of the values
     * may have been cleared already but not removed from the table.<P>
     *
     * <B>NOTE:</B> in contrast with the java.util.WeakHashMap implementation,
     * this is a constant time operation.
     */
    public int size ()
    {
        return m_size;
    }
    
    /**
     * Returns 'false' is this map contains key-value mappings (even if some of
     * the values may have been cleared already but not removed from the table).<P>
     *
     * <B>NOTE:</B> in contrast with the java.util.WeakHashMap implementation,
     * this is a constant time operation.
     */
    public boolean isEmpty ()
    {
        return m_size == 0;
    }
    
    /**
     * Returns the value that is mapped to a given 'key'. Returns
     * null if (a) this key has never been mapped or (b) a previously mapped
     * value has been cleared by the garbage collector and removed from the table.
     *
     @param key mapping key [may not be null].
     *
     @return Object value mapping for 'key' [can be null].
     */
    public Object get (final Object key)
    {
        if (key == nullthrow new IllegalArgumentException ("null input: key");
        
        if ((++ m_readAccessCount % m_readClearCheckFrequency== 0removeClearedValues ();
        
        // index into the corresponding hash bucket:
        final int keyHashCode = key.hashCode ();
        final SoftEntry [] buckets = m_buckets;
        final int bucketIndex = (keyHashCode & 0x7FFFFFFF% buckets.length;
        
        Object result = null
        
        // traverse the singly-linked list of entries in the bucket:
        for (SoftEntry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
        {
            final Object entryKey = entry.m_key;

            if (IDENTITY_OPTIMIZATION)
            {
                // note: this uses an early identity comparison opimization, making this a bit
                // faster for table keys that do not override equals() [Thread, etc]
                if ((key == entryKey|| ((keyHashCode == entryKey.hashCode ()) && key.equals (entryKey)))
                {
                    final Reference ref = entry.m_softValue;
                    result = ref.get ()// may return null to the caller
                    
                    // [see comment for ENQUEUE_FOUND_CLEARED_ENTRIES]
                    if (ENQUEUE_FOUND_CLEARED_ENTRIES && (result == null))
                    {
                        ref.enqueue ();
                    }
                    
                    return result;
                }
            }
            else
            {
                if ((keyHashCode == entryKey.hashCode ()) && key.equals (entryKey))
                {
                    final Reference ref = entry.m_softValue;
                    result = ref.get ()// may return null to the caller
                    
                    // [see comment for ENQUEUE_FOUND_CLEARED_ENTRIES]
                    if (ENQUEUE_FOUND_CLEARED_ENTRIES && (result == null))
                    {
                        ref.enqueue ();
                    }
                    
                    return result;
                }
            }
        }
        
        return null;
    }
    
    /**
     * Updates the table to map 'key' to 'value'. Any existing mapping is overwritten.
     *
     @param key mapping key [may not be null].
     @param value mapping value [may not be null].
     *
     @return Object previous value mapping for 'key' [null if no previous mapping
     * existed or its value has been cleared by the garbage collector and removed from the table].
     */
    public Object put (final Object key, final Object value)
    {
        if (key == nullthrow new IllegalArgumentException ("null input: key");
        if (value == nullthrow new IllegalArgumentException ("null input: value");
        
        if ((++ m_writeAccessCount % m_writeClearCheckFrequency== 0removeClearedValues ();
            
        SoftEntry currentKeyEntry = null;
        
        // detect if 'key' is already in the table [in which case, set 'currentKeyEntry' to point to its entry]:
        
        // index into the corresponding hash bucket:
        final int keyHashCode = key.hashCode ();
        SoftEntry [] buckets = m_buckets;
        int bucketIndex = (keyHashCode & 0x7FFFFFFF% buckets.length;
        
        // traverse the singly-linked list of entries in the bucket:
        for (SoftEntry entry = buckets [bucketIndex]; entry != null; entry = entry.m_next)
        {
            final Object entryKey = entry.m_key;
            
            if (IDENTITY_OPTIMIZATION)
            {
                // note: this uses an early identity comparison opimization, making this a bit
                // faster for table keys that do not override equals() [Thread, etc]
                if ((key == entryKey|| ((keyHashCode == entryKey.hashCode ()) && key.equals (entryKey)))
                {
                    currentKeyEntry = entry;
                    break;
                }
            }
            else
            {
                if ((keyHashCode == entryKey.hashCode ()) && key.equals (entryKey))
                {
                    currentKeyEntry = entry;
                    break;
                }
            }
        }
        
        if (currentKeyEntry != null)
        {
            // replace the current value:
            
            final IndexedSoftReference ref = currentKeyEntry.m_softValue;
            final Object currentKeyValue = ref.get ()// can be null already [no need to work around the get() bug, though]
            
            if (currentKeyValue == nullref.m_bucketIndex = -1// disable removal by removeClearedValues() [need to do this because of the identity comparison there]
            currentKeyEntry.m_softValue = new IndexedSoftReference (value, m_valueReferenceQueue, bucketIndex);
            
            return currentKeyValue; // may return null to the caller
        }
        else
        {
            // add a new entry:
            
            if (m_size >= m_sizeThresholdrehash ();
            
            // recompute the hash bucket index:
            buckets = m_buckets;
            bucketIndex = (keyHashCode & 0x7FFFFFFF% buckets.length;
            final SoftEntry bucketListHead = buckets [bucketIndex];
            final SoftEntry newEntry = new SoftEntry (m_valueReferenceQueue, key, value, bucketListHead, bucketIndex);
            buckets [bucketIndex= newEntry;
            
            ++ m_size;
            
            return null;
        }
    }
    
    public Object remove (final Object key)
    {
        if (key == nullthrow new IllegalArgumentException ("null input: key");
        
        if ((++ m_writeAccessCount % m_writeClearCheckFrequency== 0removeClearedValues ();

        // index into the corresponding hash bucket:
        final int keyHashCode = key.hashCode ();
        final SoftEntry [] buckets = m_buckets;
        final int bucketIndex = (keyHashCode & 0x7FFFFFFF% buckets.length;
        
        Object result = null;

        // traverse the singly-linked list of entries in the bucket:
        for (SoftEntry entry = buckets [bucketIndex], prev = null; entry != null; prev = entry, entry = entry.m_next)
        {
            final Object entryKey = entry.m_key;
            
            if ((IDENTITY_OPTIMIZATION && (entryKey == key)) || ((keyHashCode == entryKey.hashCode ()) && key.equals (entryKey)))
            {
                if (prev == null// head of the list
                {
                    buckets [bucketIndex= entry.m_next;
                }
                else
                {
                    prev.m_next = entry.m_next;
                }
                
                final IndexedSoftReference ref = entry.m_softValue; 
                result = ref.get ()// can be null already [however, no need to work around 4485942]
                
                // [regardless of whether the value has been enqueued or not, disable its processing by removeClearedValues() since the entire entry is removed here]
                ref.m_bucketIndex = -1;
                
                // help GC:
                entry.m_softValue = null;
                entry.m_key = null;
                entry.m_next = null;
                entry = null;
            
                -- m_size;
                break;
            }
        }
        
        return result;
    }

    
    public void clear ()
    {
        final SoftEntry [] buckets = m_buckets;
        
        for (int b = 0, bLimit = buckets.length; b < bLimit; ++ b)
        {
            for (SoftEntry entry = buckets [b]; entry != null)
            {
                final SoftEntry next = entry.m_next; // remember next pointer because we are going to reuse this entry

                // [regardless of whether the value has been enqueued or not, disable its processing by removeClearedValues()]
                entry.m_softValue.m_bucketIndex = -1;
                
                // help GC:
                entry.m_softValue = null;
                entry.m_next = null;
                entry.m_key = null;
                
                entry = next;
            }
            
            buckets [bnull;
        }
        
        m_size = 0;
        m_readAccessCount = 0;
        m_writeAccessCount = 0;
    }


    // unsupported operations:
    
    public boolean containsKey (final Object key)
    {
        throw new UnsupportedOperationException ("not implemented: containsKey");
    }
    
    public boolean containsValue (final Object value)
    {
        throw new UnsupportedOperationException ("not implemented: containsValue");
    }
        
    public void putAll (final Map map)
    {
        throw new UnsupportedOperationException ("not implemented: putAll");
    }
    
    public Set keySet ()
    {
        throw new UnsupportedOperationException ("not implemented: keySet");
    }
    
    public Set entrySet ()
    {
        throw new UnsupportedOperationException ("not implemented: entrySet");
    }

    public Collection values ()
    {
        throw new UnsupportedOperationException ("not implemented: values");
    }
    
    // protected: .............................................................

    // package: ...............................................................
    
    
    void debugDump (final StringBuffer out)
    {
        if (out != null)
        {
            out.append (getClass ().getName ().concat ("@").concat (Integer.toHexString (System.identityHashCode (this)))); out.append (EOL);
            out.append ("size = " + m_size + ", bucket table size = " + m_buckets.length + ", load factor = " + m_loadFactor + EOL);
            out.append ("size threshold = " + m_sizeThreshold + ", get clear frequency = " + m_readClearCheckFrequency + ", put clear frequency = " + m_writeClearCheckFrequency + EOL);
            out.append ("get count: " + m_readAccessCount + ", put count: " + m_writeAccessCount + EOL);
        }
    }

    // private: ...............................................................


    /**
     * An extension of WeakReference that can store an index of the bucket it
     * is associated with.
     */
    static class IndexedSoftReference extends SoftReference
    {
        IndexedSoftReference (final Object referent, ReferenceQueue queue, final int bucketIndex)
        {
            super (referent, queue);
            
            m_bucketIndex = bucketIndex;
        }
        
        int m_bucketIndex;
        
    // end of nested class
    
    
    /**
     * The structure used for chaining colliding keys.
     */
    static class SoftEntry
    {
        SoftEntry (final ReferenceQueue valueReferenceQueue, final Object key, Object value, final SoftEntry next, final int bucketIndex)
        {
            m_key = key;
            
            m_softValue = new IndexedSoftReference (value, valueReferenceQueue, bucketIndex)// ... do not retain a strong reference to the value
            value = null;
            
            m_next = next;
        }
        
        IndexedSoftReference m_softValue; // soft reference to the value [never null]
        Object m_key;  // strong reference to the key [never null]
        
        SoftEntry m_next; // singly-linked list link
        
    // end of nested class
    

    /**
     * Re-hashes the table into a new array of buckets. During the process
     * cleared value entries are discarded, making for another efficient cleared
     * value removal method.
     */
    private void rehash ()
    {
        // TODO: it is possible to run this method twice, first time using the 2*k+1 prime sequencer for newBucketCount
        // and then with that value reduced to actually shrink capacity. As it is right now, the bucket table can
        // only grow in size
        
        final SoftEntry [] buckets = m_buckets;
        
        final int newBucketCount = (m_buckets.length << 11;
        final SoftEntry [] newBuckets = new SoftEntry [newBucketCount];
        
        int newSize = 0;
        
        // rehash all entry chains in every bucket:
        for (int b = 0, bLimit = buckets.length; b < bLimit; ++ b)
        {
            for (SoftEntry entry = buckets [b]; entry != null)
            {
                final SoftEntry next = entry.m_next; // remember next pointer because we are going to reuse this entry
                
                IndexedSoftReference ref = entry.m_softValue; // get the soft value reference
                                
                Object entryValue = ref.get ()// convert the soft reference to a local strong one
            
                // skip entries whose keys have been cleared: this also saves on future removeClearedValues() work
                if (entryValue != null)
                {
                    // [assertion: 'softValue' couldn't have been enqueued already and can't be enqueued until strong reference in 'entryKey' is nulled out]
                    
                    // index into the corresponding new hash bucket:
                    final int entryKeyHashCode = entry.m_key.hashCode ();
                    final int newBucketIndex = (entryKeyHashCode & 0x7FFFFFFF% newBucketCount;
                    
                    final SoftEntry bucketListHead = newBuckets [newBucketIndex];
                    entry.m_next = bucketListHead;
                    newBuckets [newBucketIndex= entry;
                    
                    // adjust bucket index:
                    ref.m_bucketIndex = newBucketIndex;
            
                    ++ newSize;
                    
                    entryValue = null;
                }
                else
                {
                    // ['softValue' may or may not have been enqueued already]
                    
                    // adjust bucket index:
                    // [regardless of whether 'softValue' has been enqueued or not, disable its removal by removeClearedValues() since the buckets get restructured]
                    ref.m_bucketIndex = -1;
                }
                
                entry = next;
            }
        }
        
        if (DEBUG)
        {
            if (m_size > newSizeSystem.out.println ("DEBUG: rehash() cleared " (m_size - newSize" values, new size = " + newSize);
        }
        
        m_size = newSize;
        m_sizeThreshold = (int) (newBucketCount * m_loadFactor);
        m_buckets = newBuckets;
    }
    

    /**
     * Removes all entries whose soft values have been cleared _and_ enqueued.
     * See comments below for why this is safe wrt to rehash().
     */
    private void removeClearedValues ()
    {
        int count = 0;
        
next:   for (Reference _ref; (_ref = m_valueReferenceQueue.poll ()) != null)
        {
            // remove entry containing '_ref' using its bucket index and identity comparison:
            
            // index into the corresponding hash bucket:
            final int bucketIndex = ((IndexedSoftReference_ref).m_bucketIndex;
            
            if (bucketIndex >= 0// skip keys that were already removed by rehash()
            {
                // [assertion: this reference was not cleared when the last rehash() ran and so its m_bucketIndex is correct]
                
                // traverse the singly-linked list of entries in the bucket:
                for (SoftEntry entry = m_buckets [bucketIndex], prev = null; entry != null; prev = entry, entry = entry.m_next)
                {
                    if (entry.m_softValue == _ref)
                    {
                        if (prev == null// head of the list
                        {
                            m_buckets [bucketIndex= entry.m_next;
                        }
                        else
                        {
                            prev.m_next = entry.m_next;
                        }
                    
                        entry.m_softValue = null;
                        entry.m_key = null;
                        entry.m_next = null;
                        entry = null;
                    
                        -- m_size;
                        
                        if (DEBUG++ count;
                        continue next;
                    }
                }
                
                // no match found this can happen if a soft value got replaced by a put
                
                final StringBuffer msg = new StringBuffer ("removeClearedValues(): soft reference [" + _ref + "] did not match within bucket #" + bucketIndex + EOL);
                debugDump (msg);
            
                throw new Error (msg.toString ());
            }
            // else: it has already been removed by rehash() or other methods
        }
        
        if (DEBUG)
        {
            if (count > 0System.out.println ("DEBUG: removeClearedValues() cleared " + count + " keys, new size = " + m_size);
        }
    }
    
    
    private final ReferenceQueue m_valueReferenceQueue; // reference queue for all references used by SoftEntry objects used by this table
    private final float m_loadFactor; // determines the setting of m_sizeThreshold
    private final int m_readClearCheckFrequency, m_writeClearCheckFrequency; // parameters determining frequency of running removeClearedKeys() by get() and put()/remove(), respectively
    
    private SoftEntry [] m_buckets; // table of buckets
    private int m_size; // number of values in the table, not cleared as of last check
    private int m_sizeThreshold; // size threshold for rehashing
    private int m_readAccessCount, m_writeAccessCount;
    
    private static final String EOL = System.getProperty ("line.separator""\n");
    
    private static final boolean IDENTITY_OPTIMIZATION          = true;
    
    // setting this to 'true' is an optimization and a workaround for bug 4485942:
    private static final boolean ENQUEUE_FOUND_CLEARED_ENTRIES  = true
    
    private static final boolean DEBUG = false;

// end of class
// ----------------------------------------------------------------------------

   
    
  
Related examples in the same category
1. A soft reference holds onto its referent until memory becomes low.
2. A weak reference is used to determine when an object is no longer being referenced.
3. A phantom reference is used to determine when an object is just about to be reclaimed.
4. Testing SoftReference
5. Testing WeakReference
6. Testing PhantomReference
7. An implementation of Set that manages a map of soft references to the set values.
8. Cache based on SoftReference
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.