Modified SoftHashMap for highly concurrent environments

git-svn-id: https://svn.apache.org/repos/asf/incubator/jsecurity/trunk@769974 13f79535-47bb-0310-9956-ffa450edef68
diff --git a/core/pom.xml b/core/pom.xml
index 4fac667..775f625 100644
--- a/core/pom.xml
+++ b/core/pom.xml
@@ -40,6 +40,12 @@
             <groupId>commons-beanutils</groupId>
             <artifactId>commons-beanutils</artifactId>
         </dependency>
+        <!-- For Java 1.4 and below only: - ->
+        <dependency>
+            <groupId>backport-util-concurrent</groupId>
+            <artifactId>backport-util-concurrent</artifactId>
+        </dependency>
+        -->
 
         <!-- Test dependencies -->
         <dependency>
diff --git a/core/src/main/java/org/apache/ki/session/mgt/SimpleSession.java b/core/src/main/java/org/apache/ki/session/mgt/SimpleSession.java
index 284a0ec..c809c6f 100644
--- a/core/src/main/java/org/apache/ki/session/mgt/SimpleSession.java
+++ b/core/src/main/java/org/apache/ki/session/mgt/SimpleSession.java
@@ -18,22 +18,17 @@
  */
 package org.apache.ki.session.mgt;
 
+import org.apache.ki.session.ExpiredSessionException;
+import org.apache.ki.session.InvalidSessionException;
+import org.apache.ki.session.StoppedSessionException;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
 import java.io.Serializable;
 import java.net.InetAddress;
 import java.net.UnknownHostException;
 import java.text.DateFormat;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.Date;
-import java.util.HashMap;
-import java.util.Map;
-
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-import org.apache.ki.session.ExpiredSessionException;
-import org.apache.ki.session.InvalidSessionException;
-import org.apache.ki.session.StoppedSessionException;
+import java.util.*;
 
 
 /**
@@ -52,7 +47,6 @@
 
     private transient static final Logger log = LoggerFactory.getLogger(SimpleSession.class);
 
-
     private Serializable id = null;
     private Date startTimestamp = null;
     private Date stopTimestamp = null;
@@ -99,7 +93,7 @@
 
     /**
      * Returns the time the session was stopped, or <tt>null</tt> if the session is still active.
-     *
+     * <p/>
      * <p>A session may become stopped under a number of conditions:
      * <ul>
      * <li>If the user logs out of the system, their current session is terminated (released).</li>
@@ -109,7 +103,7 @@
      * reflect the user's behavior, such in the case of a system crash</li>
      * </ul>
      * </p>
-     *
+     * <p/>
      * <p>Once stopped, a session may no longer be used.  It is locked from all further activity.
      *
      * @return The time the session was stopped, or <tt>null</tt> if the session is still
@@ -187,14 +181,12 @@
 
     protected void expire() {
         stop();
-        if ( !this.expired ) {
+        if (!this.expired) {
             this.expired = true;
         }
     }
 
-    /**
-     * @since 0.9
-     */
+    /** @since 0.9 */
     public boolean isValid() {
         return !isStopped() && !isExpired();
     }
diff --git a/core/src/main/java/org/apache/ki/util/SoftHashMap.java b/core/src/main/java/org/apache/ki/util/SoftHashMap.java
index a95bcde..d7d29d6 100644
--- a/core/src/main/java/org/apache/ki/util/SoftHashMap.java
+++ b/core/src/main/java/org/apache/ki/util/SoftHashMap.java
@@ -20,12 +20,7 @@
 
 import java.lang.ref.ReferenceQueue;
 import java.lang.ref.SoftReference;
-import java.util.AbstractMap;
-import java.util.Collections;
-import java.util.LinkedList;
-import java.util.Map;
-import java.util.Set;
-import java.util.WeakHashMap;
+import java.util.*;
 
 
 /**
@@ -47,14 +42,10 @@
  */
 public class SoftHashMap<K, V> extends AbstractMap<K, V> {
 
-    /**
-     * The default value of the HARD_SIZE attribute, equal to 100.
-     */
+    /** The default value of the HARD_SIZE attribute, equal to 100. */
     private static final int DEFAULT_HARD_SIZE = 100;
 
-    /**
-     * The internal HashMap that will hold the SoftReference.
-     */
+    /** The internal HashMap that will hold the SoftReference. */
     private final Map<K, SoftValue<V, K>> map;
 
     /**
@@ -63,36 +54,52 @@
      */
     private final int HARD_SIZE;
 
-    /**
-     * The FIFO list of hard references (not to be garbage collected), order of last access.
-     */
-    private final LinkedList<V> hardCache = new LinkedList<V>();
+    /** The FIFO list of hard references (not to be garbage collected), order of last access. */
+    protected final Collection<V> hardCache;
+    private int hardCacheSize = 0;
 
-    /**
-     * Reference queue for cleared SoftReference objects.
-     */
+    /** Reference queue for cleared SoftReference objects. */
     private final ReferenceQueue<? super V> queue = new ReferenceQueue<V>();
 
     public SoftHashMap() {
         this(DEFAULT_HARD_SIZE);
     }
 
+    @SuppressWarnings({"unchecked"})
     public SoftHashMap(int hardSize) {
         super();
         HARD_SIZE = hardSize;
-        if ( JavaEnvironment.isAtLeastVersion15() ) {
+        map = createSoftReferenceMap();
+        hardCache = createHardCache();
+    }
+
+    protected Map<K, SoftValue<V, K>> createSoftReferenceMap() {
+        Map<K, SoftValue<V, K>> map;
+        if (JavaEnvironment.isAtLeastVersion15()) {
             map = new java.util.concurrent.ConcurrentHashMap<K, SoftValue<V, K>>();
         } else {
-            //TODO - Will we still support 1.3 and 1.4 JVMs?
-            //noinspection unchecked
             map = (Map) ClassUtils.newInstance("edu.emory.mathcs.backport.java.util.concurrent.ConcurrentHashMap");
         }
+        return map;
+    }
+
+    @SuppressWarnings({"unchecked"})
+    protected Collection<V> createHardCache() {
+        Collection<V> c;
+        if (JavaEnvironment.isAtLeastVersion15()) {
+            c = new java.util.concurrent.ConcurrentLinkedQueue<V>();
+        } else {
+            c = (Collection) ClassUtils.newInstance("edu.emory.mathcs.backport.java.util.concurrent.ConcurrentLinkedQueue");
+        }
+        return c;
+    }
+
+    protected V pollQueue(Collection<V> queue) {
+        return ((Queue<V>) queue).poll();
     }
 
     public V get(Object key) {
-
         V result = null;
-
         SoftValue<V, K> value = map.get(key);
 
         if (value != null) {
@@ -103,40 +110,47 @@
                 map.remove(key);
             } else {
                 //Add this value to the beginning of the 'hard' reference queue (FIFO).
-                hardCache.addFirst(result);
-
-                //trim the hard ref queue if necessary:
-                if (hardCache.size() > HARD_SIZE) {
-                    hardCache.removeLast();
-                }
+                addToHardCache(result);
+                trimHardCacheIfNecessary();
             }
         }
         return result;
     }
 
-    /**
-     * We define our own subclass of SoftReference which contains
-     * not only the value but also the key to make it easier to find
-     * the entry in the HashMap after it's been garbage collected.
-     */
-    private static class SoftValue<V, K> extends SoftReference<V> {
+    protected void addToHardCache(V result) {
+        hardCache.add(result);
+        hardCacheSize++;
+    }
 
-        private final K key;
-
-        /**
-         * Constructs a new instance, wrapping the value, key, and queue, as
-         * required by the superclass.
-         *
-         * @param value the map value
-         * @param key   the map key
-         * @param queue the soft reference queue to poll to determine if the entry had been reaped by the GC.
-         */
-        private SoftValue(V value, K key, ReferenceQueue<? super V> queue) {
-            super(value, queue);
-            this.key = key;
+    protected void trimHardCacheIfNecessary() {
+        //trim the hard ref queue if necessary:
+        V trimmed = null;
+        if (hardCacheSize > HARD_SIZE) {
+            trimmed = pollHardCache();
+        }
+        if (trimmed != null) {
+            hardCacheSize--;
         }
     }
 
+    protected V pollHardCache() {
+        V polled = null;
+        if (JavaEnvironment.isAtLeastVersion15() && hardCache instanceof Queue) {
+            polled = ((Queue<V>) hardCache).poll();
+        } else {
+            Iterator<V> i = hardCache.iterator();
+            if (i.hasNext()) {
+                polled = i.next();
+                i.remove();
+            }
+        }
+        if (polled != null) {
+            hardCacheSize--;
+        }
+        return polled;
+    }
+
+
     /**
      * Traverses the ReferenceQueue and removes garbage-collected SoftValue objects from the backing map
      * by looking them up using the SoftValue.key data member.
@@ -148,9 +162,7 @@
         }
     }
 
-    /**
-     * Creates a new entry, but wraps the value in a SoftValue instance to enable auto garbage collection.
-     */
+    /** Creates a new entry, but wraps the value in a SoftValue instance to enable auto garbage collection. */
     public V put(K key, V value) {
         processQueue(); // throw out garbage collected values first
         SoftValue<V, K> sv = new SoftValue<V, K>(value, key, queue);
@@ -182,5 +194,27 @@
         return Collections.unmodifiableSet(set);
     }
 
+    /**
+     * We define our own subclass of SoftReference which contains
+     * not only the value but also the key to make it easier to find
+     * the entry in the HashMap after it's been garbage collected.
+     */
+    private static class SoftValue<V, K> extends SoftReference<V> {
 
+        private final K key;
+
+        /**
+         * Constructs a new instance, wrapping the value, key, and queue, as
+         * required by the superclass.
+         *
+         * @param value the map value
+         * @param key   the map key
+         * @param queue the soft reference queue to poll to determine if the entry had been reaped by the GC.
+         */
+        private SoftValue(V value, K key, ReferenceQueue<? super V> queue) {
+            super(value, queue);
+            this.key = key;
+        }
+
+    }
 }
diff --git a/pom.xml b/pom.xml
index c228ea9..d702ed9 100644
--- a/pom.xml
+++ b/pom.xml
@@ -58,7 +58,7 @@
         <system>Hudson</system>
         <url>http://hudson.zones.apache.org/hudson/view/Ki/</url>
     </ciManagement>
-    
+
     <scm>
         <connection>scm:svn:http://svn.apache.org/repos/asf/incubator/jsecurity/import/trunk</connection>
         <developerConnection>scm:svn:https://svn.apache.org/repos/asf/incubator/jsecurity/import/trunk
@@ -154,7 +154,7 @@
                     <xincludeSupported>true</xincludeSupported>
                     <!-- <foCustomization>src/docbkx/resources/xsl/fopdf.xsl</foCustomization>
                     <htmlCustomization>src/docbkx/resources/xsl/html_chunk.xsl</htmlCustomization>
-                    <htmlStylesheet>css/html.css</htmlStylesheet> -->                    
+                    <htmlStylesheet>css/html.css</htmlStylesheet> -->
                     <chunkedOutput>true</chunkedOutput>
                     <entities>
                         <entity>
@@ -320,6 +320,13 @@
                 <optional>true</optional>
             </dependency>
             <dependency>
+                <groupId>backport-util-concurrent</groupId>
+                <artifactId>backport-util-concurrent</artifactId>
+                <version>3.1</version>
+                <!-- Only needed for JDK 1.4 and below: -->
+                <optional>true</optional>
+            </dependency>
+            <dependency>
                 <groupId>org.springframework</groupId>
                 <artifactId>spring</artifactId>
                 <version>${springframeworkVersion}</version>